Biblioteca Digital da UEM: Sistema Nou-Rau

Consultar: Programa de Pós-Graduação em Ciência da Computação

Início > Dissertações e Teses > Ciências Exatas e da Terra > Ciência da Computação > Programa de Pós-Graduação em Ciência da Computação

Título [PT]: Investigação da meta-heurística de otimização por colônia de formigas artificiais aplicada ao problema de cobertura de conjunto
Título [EN]: Investigation of the ant colony optimization meta-heuristic applied to the set covering problem
Autor(es): Mauro Henrique Mulati
Palavras-chave [PT]:

Meta-heurística. Aplicação. Otimização por colônia de formigas artificiais. Otimização combinatória. Problema de cobertura de conjunto. PCC.
Palavras-chave [EN]:
Ant Colony Optimization. ACO. Set covering problem. SCP. Meta-heuristic. Combinatorial optimization.
Área de concentração: Ciência da Computação
Titulação: Mestre em Ciência da Computação
Banca:
Ademir Aparecido Constantino [Orientador] - UEM
Wesley Romão - UEM
Robinson Samuel Vieira Hoto - UEL
Resumo:
Resumo: O presente trabalho utiliza-se do problema de otimização combinatória denominado problema de cobertura de conjunto (PCC), classificado como NP-difícil. À tal problema são aplicados os algoritmos heurísticos baseados em Ant Colony Optimization (ACO) Max-Min Ant System (MMAS_L) e Ant System RC_2 (AS_RC_2), além de se propor o Adaptive Ant System (AAS_MC), ressaltando que as colunas do PCC são referidas como componentes no contexto de algoritmos ACO. Objetiva-se calibrar os parâmetros de tais algoritmos de forma a conseguir soluções de qualidade em tempos computacionais aceitáveis, bem como fornecer algoritmos que contribuam com inovações. Dessa forma, os aspectos mais inovadores são dados pelo estudo do AS_RC_2 e pela proposta do AAS_MC. O AS_RC_2 possui um mecanismo de formação de conjunto de componentes candidatos para o passo de construção da formiga baseado em linhas da instância do PCC, que faz com que tal conjunto seja menor que as comumente utilizadas, enquanto que o AAS_MC apresenta mecanismo para evitar estagnação por meio da adaptação das importâncias do feromônio e da informação heurística em sua regra de decisão. Considerando que a ordem dos componentes de uma solução não é importante, o presente trabalho propõe diferentes maneiras de manipular o feromônio, com a representação, a consulta e a atualização de feromônio podendo ser feitos por componentes, seqüência de pares de componentes ou todos os pares de componentes. Assim, por componentes indica a maneira convencional de aplicação, por seqüência de pares faz com que se use as conexões entre os componentes e todos os pares indica o uso da conexão de todos com todos os componentes de uma solução. Por fim, são reportados e analisados resultados de experimentos realizados, destacando-se três modalidades de busca local: NBL que identifica nenhuma busca local em uso; JB2, que é basicamente uma perturbação da solução direcionada a colunas de um bom custo-benefício; como também usa-se o RFL, que faz uma busca na vizinhança da solução atual de modo a verificar todas as soluções com distância Hamming de até 3 em relação 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
Código: vtls000170785
Informações adicionais:
Idioma: Português
Data de Publicação: 2009
Local de Publicação: Maringá
Orientador: Prof. Dr. Ademir Aparecido Constantino
Co-Orientador:
Instituição: Universidade Estadual de Maringá . Departamento de Informática
Nível: Dissertação (mestrado em Ciência da Computação)/
UEM: Programa de Pós-Graduação em Ciência da Computação

Responsavel: salete
Categoria: Aplicação
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: 1624
Downloads: 177

[Visualizar]  [Download]

Todo material disponível neste sistema é de propriedade e responsabilidade de seus autores.

Voltar