Algoritmo de Otimização da Colônia de Formigas

Esse campo de estudo fornece métricas que permitem a apreciação do estado da rede. No ACO, formigas artificiais constroem uma solução para o problema percorrendo um grafo, entrementes o deslocamento entre os nós do grafo, cada formiga deposita feromônio nos caminhos que elas utilizaram, formando ao final de cada iteração um grafo de feromônio. Este grafo indica a intensidade de comunicação das formigas. A presunção deste trabalho é que a aplicação de métricas de redes complexas utilizando o grafo de feromônio como base pode trazer informações sobre a circunstância de convergência do algoritmo. Palavra-chave: Algoritmo. Ants 1. Introdução Neste artigo foi implementado uma apreciação da convergência do algoritmo de otimização por colônia de formigas (ACO, Ant Colony Optimization) utilizando métricas de redes complexas.

A escolha por elaborar esse tipo de apreciação se deu pelo modo que o ACO foi modelado, de forma que a aplicação das métricas de redes complexas se torna direta considerando a matriz de feromônio gerada pelas formigas artificiais. Marco Dorigo sugeriu que o ACO é uma meta-heurística inspirada na atuação das formigas na natureza. ACO é um algoritmo de lucidez de enxames que foi concebido após a observação de várias espécies de formigas em busca de fontes de alimento. Após aparentar todas as colônias de uma geração, é feita a etapa da evolução, que consiste na avaliação das colônias e posterior escolha das mais eficientes para serem mantidas na próxima geração (em geral 10%), algumas descartadas (habitualmente 40%), outras serão cruzadas para gerar novas formigas (em geral 70% das melhores restantes), além da eventualidade de mutações (menos de 1% de possibilidade por atributo).

Com a junção sequencial destas etapas será criada uma nova geração de colônias, que então serão simuladas. O número de gerações é decidido por um parâmetro, permitindo definir quantas vezes será cumprido o cálculo de seleção natural. Ao final da simulação, gera-se um arquivo contendo todos os dados gerados durante o processo, permitindo uma clara avaliação do resultado 2. Colônia Comporta todos os dados da simulação, sendo composta por uma referência ao grafo e um conjunto de formigas de mesma carga genética. Desta forma, arestas maiores irão possuir uma maior abundancia de feromônio que as menores. No entanto cada formiga possui um valor de 0 a 1 para indicar sua capacidade de feromônio, mas ao longo da execução, haverá o acúmulo causado por conta das diversas formigas que irão percorrer o caminho.

Gerações Uma geração corresponde a um conjunto de colônias que irão conviver no mesmo tempo. Procedimento Seleção natural A seleção natural é o procedimento que permite que as formigas evoluam e se tornem mais eficientes. O processo consiste inicialmente em selecionar aquelas colônias que tiveram a melhor execução na geração, por meio da função de fitness. Otimização por Colônia de Formigas O algoritmo de otimização por colônia de formigas, ACO, compõe uma classe de algoritmos de inteligência de enxames, cuja representação de sucesso se dá por interação das formigas artificiais com o ambiente. Esta seção se dedica a apresentar mais detalhes sobre o ACO. Aço Inspiração baseada em Colônia de Formigas O ACO foi inspirado na observação da atuação de formigas na natureza, foram feitos experimentos com formigas reais de modo a intencionar o algoritmo].

Nessas observações, percebeu-se que em várias espécies de formigas, elas depositam uma substância chamada feromônio por onde passam, enquanto estão em busca de uma fonte de alimento. Este feromônio funciona como a entendimento desta formiga com as outras que também estão em busca da fonte de alimento, a presença do feromônio influencia na escolha do caminho a seguir pelas outras formigas, isto é, elas tendem a prosseguir o caminho com maior concentração de feromônio. Logo o entendimento, suponha que a distância entre D e H é igual a distância entre B e H e igual a distância entre B e D (passando por C) e que essa distância é igual a 1. Considere que C está posicionado precisamente no meio entre B e D, fazendo as distâncias BC e CD serem iguais a 0,5 como pode ser visto na Figura 2.

a. Considera-se iterações a cada intervalo de tempo: t = 0, 1, 2. tmax. Para explicação do algoritmo ACO será utilizado o problema do caixeiro viajante (TSP, Traveling Salesman Problem) [12]. Supondo um conjunto de nas cidades, o TSP pode ser definido como um problema para encontrar o menor caminho para fechar um tour entre todas as cidades sem repeti-las. O TSP será mais detalhado na Seção 4. Deixe bi(t) (i = 1,. n) ser o número de formigas na cidade i no tempo t e m igual ao número total de formigas. Redes Complexas Redes Complexas é o estudo das fundações teóricas da estrutura da rede, de seu comportamento dinâmico e da aplicação de redes para vários subcampos. Existem algumas redes que apresentam características específicas, tanto na sua estrutura, quanto em seu comportamento, para analisar estas características são utilizadas métricas de redes complexas 6.

Métricas de Redes Complexas Várias propriedades do grafo podem ser inferidas utilizando a matriz Laplaciana. Os autovalores λ1 ≤ λ2 ≤. ≤ λn de L são importantes, pois eles relatam várias propriedades do grafo. Abaixo segue o pseudo-código do algoritmo utilizado para os experimentos: 1. Inicialização: Atribuir 0 a t (contador de tempo); Atribuir 0 a NC (Número de iterações); Para cada aresta inicializar o valor do feromônio com c; Colocar as formigas em cidades aleatórias; 2. Atribuir 1 a s (s é o índice da lista tabu) Para todas as formigas inicializar sua lista tabu com a cidade inicial; 3. Repetir até que a lista tabu esteja cheia s := s + 1; Para todas as formigas fazer escolher a cidade que irá se mover; mover-se para a cidade escolhida; Adicionar a cidade escolhida a tabu(s); 4.

Para todas as formigas fazer mover-se voltando por cada cidade que passou; 5. Parârmetro limiar de consideração de conectividade Para a aplicação das métricas de redes complexas foi utilizada a matriz de feromônio formada durante a execução do ACO. Esta matriz de feromônio varia de acordo com as iterações do ACO e indica a influência de uma formiga para as outras, por isso com base na matriz de feromônio chega-se a matriz de adjacência. O limiar, chamado de th, é utilizado exatamente na transformação da matriz de feromônio em matriz de adjacência, pois na matriz de feromônio tem-se a diagonal principal igual a zero e em qualquer outro elemento da matriz pode-se ter um valor real, contanto que a matriz se mantenha simétrica.

A matriz de adjacência utilizada no cálculo das métricas deve possuir a diagonal principal igual a zero e os valores 1 ou 0 em qualquer outro elemento, indicando conexão ou não e com a mesma obrigatoriedade que a matriz se mantenha simétrica. Assim, foi decidido utilizar um limiar, onde evita-se que conexões fracas na matriz de feromônio sejam consideradas conexões na matriz de adjacência. Problema att48 Para as simulações utilizando o problema att48, tomou-se o intervalo do resultado apenas das 50 primeiras iterações e no gráfico foi utilizada escala logarítmica, isso foi feito para uma melhor visualização do ponto importante do gráfico. O ponto onde a quantidade de autovalores iguais a zero deixa de diminuir e indica uma estagnação do algoritmo.

Pode-se dizer que se o algoritmo parou de evoluir neste ponto, a execução poderia ser parada e não seria necessário aguardar até o final das iterações. A Figura representa a evolução dos autovalores iguais a zero ao longo de 50 iterações, o valor de ρ utilizado nesta simulação foi 0,1 e o gráfico mostra um comparativo dos valores do limiar th de 0,8 até 1,2. Pode-se perceber que poucas iterações são necessárias para atingir a convergência. A avaliação feita neste trabalho consiste em avaliar os autovalores da matriz Laplaciana fornecida pelo ACO e colher as informações contidas nos autovalores. Os resultados mostrados utilizam o número de autovalores iguais a zero, isto é, a quantidade de ilhas contidas no grafo, como o grafo de feromônio está relacionado à comunicação entre as formigas no ACO, quanto mais ilhas no grafo indica uma fraca comunicação e menos ilhas indica um forte entendimento.

Por conseguinte, a partir do momento que a quantidade de zeros dos autovalores reduz, a comunicação no algoritmo aumenta. Portanto, apesar da quantidade de zeros chega a 1 pode-se dizer que o algoritmo convergiu. Assim nestes resultados, existe a possibilidade de aperfeiçoar o algoritmo de modo a ser provável obter um indicativo mais preciso e menos dependente dos parâmetros, utilizando esta informação e outras que também podem ser extraídas do grafo de feromônio utilizando outras métricas de redes complexas. – Part B, 26(1), 29, 1996. L. Barabasi and R. Albert. Emergence of scaling in random networks. A. Bastos-Filho, and R. P. Menezes, Assessing Particle Swarm Optimizers Using Network Science Metrics. In: Gourab Ghoshal, Julia Poncela-Casanovas, Robert Tolksdorf. Engelbrecht, A. P. Computational Intelligence An Introduction. ed. West Sussex, Inglaterra: Wiley, 2002.

An Idea Based on Honey Bee Swarm for Numerical Optimization, Technical Report-TR06, Erciyes University, Engineering Faculty, Computer Engineering Department, 2005. D. Karaboga, B. Basturk, Artificial Bee Colony (ABC) Optimization Algorithm for Solving Constrained Optimization Problems, LNCS: Advances in Soft Computing: Foundations of Fuzzy Logic and Soft Computing, Vol: 4529/2007, pp: 789-798, Springer- Verlag, 2007, IFSA 2007. Referências Bibliográficas [12] M. on Evolutionay Computation, Vol. No. In press. Ted G. Lewis. org/wiki/Evolução#Consequências Acesso em 24 de janeiro 2019 Disponível  https://pt. wikipedia. org/wiki/Evolução#Mecanismos Acesso em 25 de janeiro 2019 Disponível  https://pt. wikipedia. org/wiki/Evolução#Variação Acesso em 25 de janeiro 2019 Disponível https://pt.