Biblioteca Digital da UEM: Sistema Nou-Rau
Pgina Principal  Portugus   English  Español   Aumentar Texto  Texto Normal  Diminuir Texto
  Principal | Apresentao | Objetivos | Instrues Autores | Estatsticas | Outras Bibliotecas Digitais
  Sistema Integrado de Bibliotecas - SIB / UEM
Entrar | acessos | verso 1.1  
ndice
Pgina principal
Documentos
Novidades
Usurios

Aes
Consultar
Procurar
Exibir estatsticas

Procurar por:
Procura avanada

Dvidas e sugestes


Consultar: Programa de Ps-Graduao em Cincia da Computao

Incio > Dissertaes e Teses > Cincias Exatas e da Terra > Cincia da Computao > Programa de Ps-Graduao em Cincia da Computao

Ttulo [PT]: Investigao da meta-heurstica de otimizao por colnia de formigas artificiais aplicada ao problema de cobertura de conjunto
Ttulo [EN]: Investigation of the ant colony optimization meta-heuristic applied to the set covering problem
Autor(es): Mauro Henrique Mulati
Palavras-chave [PT]:

Meta-heurstica. Aplicao. Otimizao por colnia de formigas artificiais. Otimizao combinatria. Problema de cobertura de conjunto. PCC.
Palavras-chave [EN]:
Ant Colony Optimization. ACO. Set covering problem. SCP. Meta-heuristic. Combinatorial optimization.
rea de concentrao: Cincia da Computao
Titulao: Mestre em Cincia da Computao
Banca:
Ademir Aparecido Constantino [Orientador] - UEM
Wesley Romo - UEM
Robinson Samuel Vieira Hoto - UEL
Resumo:
Resumo: O presente trabalho utiliza-se do problema de otimizao combinatria denominado problema de cobertura de conjunto (PCC), classificado como NP-difcil. tal problema so aplicados os algoritmos heursticos baseados em Ant Colony Optimization (ACO) Max-Min Ant System (MMAS_L) e Ant System RC_2 (AS_RC_2), alm de se propor o Adaptive Ant System (AAS_MC), ressaltando que as colunas do PCC so referidas como componentes no contexto de algoritmos ACO. Objetiva-se calibrar os parmetros de tais algoritmos de forma a conseguir solues de qualidade em tempos computacionais aceitveis, bem como fornecer algoritmos que contribuam com inovaes. Dessa forma, os aspectos mais inovadores so dados pelo estudo do AS_RC_2 e pela proposta do AAS_MC. O AS_RC_2 possui um mecanismo de formao de conjunto de componentes candidatos para o passo de construo da formiga baseado em linhas da instncia do PCC, que faz com que tal conjunto seja menor que as comumente utilizadas, enquanto que o AAS_MC apresenta mecanismo para evitar estagnao por meio da adaptao das importncias do feromnio e da informao heurstica em sua regra de deciso. Considerando que a ordem dos componentes de uma soluo no importante, o presente trabalho prope diferentes maneiras de manipular o feromnio, com a representao, a consulta e a atualizao de feromnio podendo ser feitos por componentes, seqncia de pares de componentes ou todos os pares de componentes. Assim, por componentes indica a maneira convencional de aplicao, por seqncia de pares faz com que se use as conexes entre os componentes e todos os pares indica o uso da conexo de todos com todos os componentes de uma soluo. Por fim, so reportados e analisados resultados de experimentos realizados, destacando-se trs modalidades de busca local: NBL que identifica nenhuma busca local em uso; JB2, que basicamente uma perturbao da soluo direcionada a colunas de um bom custo-benefcio; como tambm usa-se o RFL, que faz uma busca na vizinhana da soluo atual de modo a verificar todas as solues com distncia Hamming de at 3 em relao a esta.

Abstract: This thesis use the combinatorial optimization problem called set covering problem (SCP), which is classified as NP-hard. To that problem are applied the heuristic algorithms based on Ant Colony Optimization (ACO) Max-Min Ant System (MMAS_L) and Ant System RC_2 (AS_RC_2), besides the proposing of the Adaptive Ant System (AAS_MC), emphasizing that columns of the SCP are referred as components in the context of ACO algorithms. These investigations aim to calibrate the parameters of the algorithms in such a way to obtain solutions with quality in acceptable computational times, besides providing innovative algorithms. So, the more innovative aspects are the study of the AS_RC_2 and the proposition of the AAS_MC. The AS_RC_2 has a mechanism that make the set of candidate components for the construction step of the ant based on lines of the SCP instance, that mechanism makes such set smaller than the ones that are usually used, while the AAS_MC presents a way to avoid stagnation by the adaptation of the importances of pheromone and heuristic information in its decision rule. Considering that the order of the components of a solution is not important, this study proposes different manners to handle the pheromone, with the representation, the consulting and the updating of the pheromone being done by components, pair sequence of components or all pairs of components. Thus, by components we indicate the conventional way of utilization, by sequence of pairs we mean that is used the connections between the components and all pairs indicates the use of the connections from all to all components of a solution. Finally, results of experiments are reported and analyzed, emphasizing three ways of local search: NBL, which means that there is not a local search in use; JB2, that is basically a perturbation of the solution directed to columns with a good cost-benefit and there is also the RFL, which searches the neighborhood of the solution in such a way that all solutions with Hamming distance with up to 3 from the referred solution.
Data da defesa: 26/02/2009
Cdigo: vtls000170785
Informaes adicionais:
Idioma: Portugus
Data de Publicao: 2009
Local de Publicao: Maring
Orientador: Prof. Dr. Ademir Aparecido Constantino
Co-Orientador:
Instituio: Universidade Estadual de Maring . Departamento de Informtica
Nvel: Dissertao (mestrado em Cincia da Computao)/
UEM: Programa de Ps-Graduao em Cincia da Computao

Responsavel: salete
Categoria: Aplicao
Formato: Documento PDF
Arquivo: Mulati-Mauro-Henrique-2009-ME.pdf
Tamanho: 3123 Kb (3198178 bytes)
Criado: 02-05-2009 11:31
Atualizado: 02-05-2009 11:44
Visitas: 1165
Downloads: 177

[Visualizar]  [Download]

Todo material disponvel neste sistema de propriedade e responsabilidade de seus autores.