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. |