A proposal for an improved version of EigenAnt algorithm with performance evaluation on combinatorial optimization problems - Mahrueyan, Mahan (UFRJ, 2017)
[PT] O algoritmo denominado EigenAnt foi introduzido recentemente para a resolução do problema de encontrar o menor caminho entre dois nós de um grafo, utilizando uma dinâmica com evaporação local de feromônio. O referido algoritmo possui uma prova matemática de convergência ao menor caminho. Nesta tese, realiza-se a análise de estabilidade e sensibilidade paramêtrica do algoritmo EigenAnt aplicado a problemas de caminhos mínimos em cadeias binárias entre N nós. Motivado por esta análise, propõe-se uma extensão do algoritmo EigenAnt (denotado Improved EigenAnt), no qual a exploração de distintos equilíbrios estáveis e a velocidade de convergência a estes podem ser ajustada independentemente. Realiza-se também uma análise comparativa entre os algoritmos EigenAnt, Improved EigenAnt e outros algoritmos existentes do tipo Colônia de Formigas, no contexto de problemas de caminho mínimo em redes de roteamento. Adicionalmente, aplica-se o algoritmo novo proposto a problemas multidimensionais de mochileiro, por meio da modelagem destes como problemas de caminhos mínimos em cadeias binárias entre N nós, com restrições. Evaporação local de feromônio e convergência rápida são propriedades de algoritmos da classe EigenAnt que tornam esta classe vantajosa para rastreamento de soluções ótimas de problemas de otimização dinâmica, nos quais as instâncias do problema, a função objetivo e os parâmetros das restrições podem mudar ao longo do tempo. Uma investigação experimental da aplicação do algoritmo proposto (Improved EigenAnt) para rastrear a solução ótima em redes dinâmicas de roteamento e em problemas dinâmicos do mochileiro constituem uma outra contribuição desta tese.[EN] The EigenAnt algorithm has recently been introduced to solve the problem of finding the shortest path between two nodes by using dynamics involving local pheromone evaporation. This algorithm has a mathematical proof of convergence to the shortest path between two nodes. In this thesis, the stability and parameter impact analysis of EigenAnt algorithm applied to N-node Binary Chain Problems is carried out. Motivated by this analysis, an improved EigenAnt algorithm is proposed, in which the exploration of different stable equilibria and speed of convergence to them can be tuned separately. A comparative analysis of Improved EigenAnt algorithm with its predecessor EigenAnt and other Ant Colony Optimization algorithms is performed for combinatorial Routing Network shortest path problems. In addition, the application of the proposed Improved EigenAnt algorithm to Multidimensional Knapsack Problems is investigated, by modeling these problems as an N-node Binary Chain shortest path problems with constraints. Local pheromone evaporation and fast convergence features of the EigenAnt algorithm are advantageous for tracking the optimal solutions of dynamic optimization problems in which the problem instances, objective function and constraint parameters change over time. An experimental investigation of the application of the proposed Improved EigenAnt algorithm to track the optimal Dynamic Routing Networks and Dynamic Multidimensional Knapsack problems is another contribution of this thesis.