Investigação da meta-heurística de otimização por colônia de formigas artificiais aplicada ao problema de cobertura de conjunto

• Ano de defesa: 2009
• Autor(a) principal: Mulati, Mauro Henrique
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Estadual de Maringá; Brasil; Programa de Pós-Graduação em Ciência da Computação; UEM; Maringá; Departamento de Informática
• Palavras-chave em Português: Meta-heurística; Aplicação; Otimização por colônia de formigas artificiais; Otimização combinatória; Problema de cobertura de conjunto; PCC.; Ant Colony Optimization; ACO; Set covering problem; SCP; Meta-heuristic; Combinatorial optimization.; Ciências Exatas e da Terra; Ciência da Computação
• Link de acesso: http://repositorio.uem.br:8080/jspui/handle/1/2532

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.