Algoritmos de otimização de colônia de formigas - Ant colony optimization algorithms

O comportamento da formiga foi a inspiração para a técnica de otimização metaheurística

Quando uma colônia de formigas é confrontada com a escolha de chegar ao alimento por meio de duas rotas diferentes, uma delas muito mais curta que a outra, a escolha é inteiramente aleatória. No entanto, quem usa o caminho mais curto chega mais rápido à comida e, portanto, vai e vem com mais frequência entre o formigueiro e a comida.

Em ciência da computação e pesquisa operacional , o algoritmo de otimização de colônia de formigas ( ACO ) é uma técnica probabilística para resolver problemas computacionais que podem ser reduzidos a encontrar bons caminhos por meio de gráficos . As formigas artificiais representam métodos multiagentes inspirados no comportamento de formigas reais. A comunicação baseada em feromônios de formigas biológicas é freqüentemente o paradigma predominante usado. Combinações de formigas artificiais e algoritmos de busca local tornaram-se um método de escolha para inúmeras tarefas de otimização envolvendo algum tipo de gráfico , por exemplo,roteamento de veículos e roteamento de internet .

Por exemplo, a otimização de uma colônia de formigas é uma classe de algoritmos de otimização modelados nas ações de uma colônia de formigas . 'Formigas' artificiais (por exemplo, agentes de simulação) localizam soluções ótimas movendo-se através de um espaço de parâmetros que representa todas as soluções possíveis. As formigas reais estabelecem feromônios que dirigem umas às outras para os recursos enquanto exploram seu ambiente. As 'formigas' simuladas registram de forma semelhante suas posições e a qualidade de suas soluções, de modo que, em iterações posteriores da simulação, mais formigas localizem as melhores soluções. Uma variação dessa abordagem é o algoritmo das abelhas , que é mais análogo aos padrões de forrageamento da abelha melífera , outro inseto social.

Este algoritmo é membro da família de algoritmos de colônia de formigas, em métodos de inteligência de enxame , e constitui algumas otimizações metaheurísticas . Proposto inicialmente por Marco Dorigo em 1992 em sua tese de doutorado, o primeiro algoritmo tinha como objetivo buscar um caminho ótimo em um gráfico, baseado no comportamento de formigas que buscam um caminho entre sua colônia e uma fonte de alimento. Desde então, a ideia original se diversificou para resolver uma classe mais ampla de problemas numéricos e, como resultado, vários problemas surgiram, baseados em vários aspectos do comportamento das formigas. De uma perspectiva mais ampla, o ACO realiza uma pesquisa baseada em modelo e compartilha algumas semelhanças com algoritmos de estimativa de distribuição .

Visão geral

No mundo natural, as formigas de algumas espécies (inicialmente) vagam aleatoriamente e, ao encontrarem comida, retornam à sua colônia enquanto traçam trilhas de feromônios . Se outras formigas encontrarem esse caminho, é provável que não continuem viajando aleatoriamente, mas, em vez disso, sigam a trilha, retornando e reforçando-a se por fim encontrarem alimento (consulte a comunicação com as formigas ).

Com o tempo, entretanto, a trilha de feromônio começa a evaporar, reduzindo assim sua força atrativa. Quanto mais tempo leva para uma formiga percorrer o caminho e voltar, mais tempo os feromônios têm para evaporar. Em comparação, um caminho curto é percorrido com mais frequência e, portanto, a densidade de feromônios se torna mais alta em caminhos mais curtos do que em mais longos. A evaporação de feromônios também tem a vantagem de evitar a convergência para uma solução localmente ótima. Se não houvesse evaporação nenhuma, os caminhos escolhidos pelas primeiras formigas tenderiam a ser excessivamente atraentes para as seguintes. Nesse caso, a exploração do espaço de solução seria restringida. A influência da evaporação de feromônios em sistemas reais de formigas não é clara, mas é muito importante em sistemas artificiais.

O resultado geral é que, quando uma formiga encontra um bom (ou seja, curto) caminho da colônia até uma fonte de alimento, é mais provável que outras formigas sigam esse caminho, e o feedback positivo acaba levando muitas formigas a seguirem um único caminho. A ideia do algoritmo da colônia de formigas é imitar esse comportamento com "formigas simuladas" andando ao redor do gráfico que representa o problema a ser resolvido.

Redes ambientais de objetos inteligentes

Novos conceitos são necessários, uma vez que a “inteligência” não é mais centralizada, mas pode ser encontrada em todos os objetos minúsculos. Os conceitos antropocêntricos são conhecidos por levar à produção de sistemas de TI nos quais o processamento de dados, unidades de controle e cálculo de forças são centralizados. Essas unidades centralizadas aumentaram continuamente seu desempenho e podem ser comparadas ao cérebro humano. O modelo do cérebro se tornou a visão definitiva dos computadores. Redes ambientais de objetos inteligentes e, mais cedo ou mais tarde, uma nova geração de sistemas de informação ainda mais difusos e baseados na nanotecnologia, vão mudar profundamente esse conceito. Pequenos dispositivos que podem ser comparados a insetos não dispõem de alta inteligência por conta própria. Na verdade, sua inteligência pode ser classificada como bastante limitada. É, por exemplo, impossível integrar uma calculadora de alto desempenho com o poder de resolver qualquer tipo de problema matemático em um biochip que é implantado no corpo humano ou integrado em uma etiqueta inteligente que é projetada para rastrear artigos comerciais. Porém, uma vez interligados, esses objetos dispõem de uma forma de inteligência que pode ser comparada a uma colônia de formigas ou abelhas. No caso de certos problemas, esse tipo de inteligência pode ser superior ao raciocínio de um sistema centralizado semelhante ao cérebro.

A natureza oferece vários exemplos de como organismos minúsculos, se todos seguirem a mesma regra básica, podem criar uma forma de inteligência coletiva no nível macroscópico. As colônias de insetos sociais ilustram perfeitamente esse modelo, que difere muito das sociedades humanas. Este modelo é baseado na cooperação de unidades independentes com comportamento simples e imprevisível. Eles se movem por sua área circundante para realizar certas tarefas e possuem apenas uma quantidade muito limitada de informações para fazê-lo. Uma colônia de formigas, por exemplo, representa inúmeras qualidades que também podem ser aplicadas a uma rede de objetos ambientais. As colônias de formigas têm uma capacidade muito elevada de se adaptarem às mudanças do ambiente e também uma força enorme para lidar com situações em que um indivíduo não consegue realizar uma determinada tarefa. Esse tipo de flexibilidade também seria muito útil para redes móveis de objetos que estão em constante desenvolvimento. Pacotes de informação que se movem de um computador para um objeto digital se comportam da mesma maneira que as formigas. Eles se movem pela rede e passam de um nó a outro com o objetivo de chegar ao seu destino final o mais rápido possível.

Sistema de feromônio artificial

A comunicação baseada em feromônios é uma das formas de comunicação mais eficazes, amplamente observada na natureza. O feromônio é usado por insetos sociais como abelhas, formigas e cupins; para comunicações entre agentes e agentes-enxame. Devido à sua viabilidade, feromônios artificiais têm sido adotados em sistemas robóticos multirobot e enxame. A comunicação baseada em feromônios foi implementada por diferentes meios, como químicos ou físicos (etiquetas RFID, luz, som). No entanto, essas implementações não foram capazes de replicar todos os aspectos dos feromônios vistos na natureza.

O uso de luz projetada foi apresentado em um artigo IEEE de 2007 por Garnier, Simon, et al. como uma configuração experimental para estudar a comunicação baseada em feromônios com micro robôs autônomos. Outro estudo apresentou um sistema no qual feromônios eram implementados por meio de uma tela LCD horizontal na qual os robôs se moviam, com os robôs tendo sensores de luz voltados para baixo para registrar os padrões abaixo deles.

Algoritmo e fórmulas

Nos algoritmos de otimização de colônias de formigas, uma formiga artificial é um agente computacional simples que busca boas soluções para um determinado problema de otimização. Para aplicar um algoritmo de colônia de formigas, o problema de otimização precisa ser convertido no problema de encontrar o caminho mais curto em um gráfico ponderado. Na primeira etapa de cada iteração, cada formiga constrói estocasticamente uma solução, ou seja, a ordem em que as arestas do gráfico devem ser seguidas. Na segunda etapa, os caminhos encontrados pelas diferentes formigas são comparados. A última etapa consiste em atualizar os níveis de feromônio em cada borda.

procedure ACO_MetaHeuristic is
    while not terminated do
        generateSolutions()
        daemonActions()
        pheromoneUpdate()
    repeat
end procedure

Seleção de borda

Cada formiga precisa construir uma solução para se mover pelo gráfico. Para selecionar a próxima aresta em seu passeio, uma formiga irá considerar o comprimento de cada aresta disponível em sua posição atual, bem como o nível de feromônio correspondente. A cada etapa do algoritmo, cada formiga passa de um estado a outro , correspondendo a uma solução intermediária mais completa. Assim, cada formiga calcula um conjunto de expansões viáveis ​​para seu estado atual em cada iteração e se move para uma delas em probabilidade. Para formigas , a probabilidade de se mover de um estado para outro depende da combinação de dois valores, a atratividade do movimento, conforme calculado por alguma heurística que indica a conveniência a priori desse movimento e o nível de trilha do movimento, indicando o quão proficiente ele foi no passado para fazer esse movimento específico. O nível da trilha representa a posteriori uma indicação da conveniência desse movimento. ${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle k}$${\ displaystyle A_ {k} (x)}$${\ displaystyle k}$${\ displaystyle p_ {xy} ^ {k}}$${\ displaystyle x}$${\ displaystyle y}$ ${\ displaystyle \ eta _ {xy}}$ ${\ displaystyle \ tau _ {xy}}$

Em geral, a formiga se move de um estado para outro com probabilidade ${\ displaystyle k}$${\ displaystyle x}$${\ displaystyle y}$

${\ displaystyle p_ {xy} ^ {k} = {\ frac {(\ tau _ {xy} ^ {\ alpha}) (\ eta _ {xy} ^ {\ beta})} {\ sum _ {z \ em \ mathrm {permitido} _ {x}} (\ tau _ {xz} ^ {\ alpha}) (\ eta _ {xz} ^ {\ beta})}}}$

Onde

${\ displaystyle \ tau _ {xy}}$é a quantidade de feromônio depositada para a transição do estado para , 0 ≤ é um parâmetro para controlar a influência de , é a conveniência da transição de estado ( conhecimento a priori , normalmente , onde está a distância) e ≥ 1 é um parâmetro para controlar o influência de . e representam o nível de trilha e atratividade para as outras transições de estado possíveis. ${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle \ alpha}$${\ displaystyle \ tau _ {xy}}$${\ displaystyle \ eta _ {xy}}$${\ displaystyle xy}$${\ displaystyle 1 / d_ {xy}}$${\ displaystyle d}$${\ displaystyle \ beta}$${\ displaystyle \ eta _ {xy}}$${\ displaystyle \ tau _ {xz}}$${\ displaystyle \ eta _ {xz}}$

Atualização de feromônio

As trilhas geralmente são atualizadas quando todas as formigas concluem sua solução, aumentando ou diminuindo o nível das trilhas correspondentes aos movimentos que fizeram parte de soluções "boas" ou "ruins", respectivamente. Um exemplo de regra global de atualização de feromônio é

${\ displaystyle \ tau _ {xy} \ leftarrow (1- \ rho) \ tau _ {xy} + \ sum _ {k} ^ {m} \ Delta \ tau _ {xy} ^ {k}}$

onde é a quantidade de feromônio depositada para uma transição de estado , é o coeficiente de evaporação de feromônio , é o número de formigas e é a quantidade de feromônio depositada pela formiga, normalmente dada para um problema de TSP (com movimentos correspondentes aos arcos do gráfico) por ${\ displaystyle \ tau _ {xy}}$${\ displaystyle xy}$${\ displaystyle \ rho}$${\ displaystyle m}$${\ displaystyle \ Delta \ tau _ {xy} ^ {k}}$${\ displaystyle k}$

${\ displaystyle \ Delta \ tau _ {xy} ^ {k} = {\ begin {cases} Q / L_ {k} & {\ mbox {if ant}} k {\ mbox {usa curva}} xy {\ mbox {em seu passeio}} \\ 0 & {\ mbox {caso contrário}} \ end {casos}}}$

onde é o custo do passeio da ª formiga (normalmente a duração) e é uma constante. ${\ displaystyle L_ {k}}$${\ displaystyle k}$${\ displaystyle Q}$

Extensões comuns

Aqui estão algumas das variações mais populares dos algoritmos ACO.

Sistema Ant (AS)

O sistema de formigas é o primeiro algoritmo ACO. Este algoritmo corresponde ao apresentado acima. Foi desenvolvido por Dorigo.

Sistema de colônia de formigas (ACS)

No algoritmo do sistema de colônia de formigas, o sistema de formigas original foi modificado em três aspectos:

1. A seleção de arestas é tendenciosa para a exploração (ou seja, favorecendo a probabilidade de selecionar as arestas mais curtas com uma grande quantidade de feromônio);
2. Ao construir uma solução, as formigas alteram o nível de feromônio das bordas que estão selecionando aplicando uma regra de atualização local de feromônio;
3. No final de cada iteração, apenas a melhor formiga tem permissão para atualizar as trilhas, aplicando uma regra de atualização de feromônio global modificada.

Sistema de formigas elitista

Nesse algoritmo, a melhor solução global deposita feromônio em sua trilha após cada iteração (mesmo que essa trilha não tenha sido revisitada), junto com todas as outras formigas. A estratégia elitista tem como objetivo direcionar a busca de todas as formigas para construir uma solução que contenha os links da melhor rota atual.

Sistema de formiga máximo-mínimo (MMAS)

Este algoritmo controla as quantidades máximas e mínimas de feromônios em cada trilha. Apenas o melhor passeio global ou o melhor passeio de iteração podem adicionar feromônios à sua trilha. Para evitar a estagnação do algoritmo de busca, a gama de possíveis quantidades de feromônios em cada trilha é limitada a um intervalo [τ _max , τ _min ]. Todas as arestas são inicializadas em τ _max para forçar uma maior exploração de soluções. As trilhas são reinicializadas para τ _max ao se aproximar da estagnação.

Sistema de formigas baseado em classificação (ASrank)

Todas as soluções são classificadas de acordo com seu comprimento. Apenas um número fixo das melhores formigas nesta iteração tem permissão para atualizar suas tentativas. A quantidade de feromônio depositada é ponderada para cada solução, de forma que as soluções com caminhos mais curtos depositem mais feromônio do que as soluções com caminhos mais longos.

Colônia de formigas ortogonais contínuas (COAC)

O mecanismo de depósito de feromônios do COAC é permitir que as formigas busquem soluções de forma colaborativa e eficaz. Usando um método de projeto ortogonal, as formigas no domínio viável podem explorar suas regiões escolhidas de forma rápida e eficiente, com capacidade e precisão de pesquisa global aprimorada. O método de projeto ortogonal e o método de ajuste de raio adaptativo também podem ser estendidos a outros algoritmos de otimização para oferecer vantagens mais amplas na resolução de problemas práticos.

Otimização de colônia de formigas recursivas

É uma forma recursiva de sistema de formigas que divide todo o domínio de pesquisa em vários subdomínios e resolve o objetivo nesses subdomínios. Os resultados de todos os subdomínios são comparados e os melhores deles são promovidos para o próximo nível. Os subdomínios correspondentes aos resultados selecionados são subdivididos e o processo é repetido até que uma saída com a precisão desejada seja obtida. Este método foi testado em problemas de inversão geofísica mal colocados e funciona bem.

Convergência

Para algumas versões do algoritmo, é possível provar que ele é convergente (ou seja, é capaz de encontrar o ótimo global em tempo finito). A primeira evidência de convergência para um algoritmo de colônia de formigas foi feita em 2000, o algoritmo do sistema de formigas baseado em gráfico, e posteriormente para os algoritmos ACS e MMAS. Como a maioria das metaheurísticas , é muito difícil estimar a velocidade teórica de convergência. Uma análise de desempenho de um algoritmo de colônia de formigas contínuo com relação aos seus vários parâmetros (estratégia de seleção de borda, medida de distância métrica e taxa de evaporação de feromônio) mostrou que seu desempenho e taxa de convergência são sensíveis aos valores dos parâmetros escolhidos e, especialmente, ao valor da taxa de evaporação do feromônio. Em 2004, Zlochin e seus colegas mostraram que algoritmos do tipo COAC poderiam ser métodos assimilados de gradiente estocástico descendente , na entropia cruzada e algoritmo de estimativa de distribuição . Eles propuseram essas metaheurísticas como um " modelo baseado em pesquisa ".

Formulários

Problema da mochila : as formigas preferem a gota menor de mel ao açúcar mais abundante, mas menos nutritivo

Algoritmos de otimização de colônia de formigas têm sido aplicados a muitos problemas de otimização combinatória , variando de atribuição quadrática a dobramento de proteínas ou veículos de roteamento e muitos métodos derivados foram adaptados para problemas dinâmicos em variáveis ​​reais, problemas estocásticos, multi-alvos e implementações paralelas . Também tem sido usado para produzir soluções quase ótimas para o problema do caixeiro viajante . Eles têm uma vantagem sobre o recozimento simulado e as abordagens de algoritmo genético de problemas semelhantes, quando o gráfico pode mudar dinamicamente; o algoritmo da colônia de formigas pode ser executado continuamente e se adaptar às mudanças em tempo real. Isso é de interesse em sistemas de roteamento de rede e transporte urbano.

O primeiro algoritmo ACO foi chamado de sistema de formigas e teve como objetivo resolver o problema do caixeiro viajante, em que o objetivo é encontrar o menor trajeto de ida e volta para ligar uma série de cidades. O algoritmo geral é relativamente simples e baseado em um conjunto de formigas, cada uma fazendo uma das possíveis viagens de ida e volta ao longo das cidades. Em cada etapa, a formiga opta por se deslocar de uma cidade para outra de acordo com algumas regras:

1. Deve visitar cada cidade exatamente uma vez;
2. Uma cidade distante tem menos chance de ser escolhida (a visibilidade);
3. Quanto mais intensa a trilha de feromônios estabelecida em uma borda entre duas cidades, maior a probabilidade de que essa borda seja escolhida;
4. Tendo completado sua jornada, a formiga deposita mais feromônios em todas as bordas que atravessou, se a jornada for curta;
5. Após cada iteração, trilhas de feromônios evaporam.

Problema de agendamento

• Problema de ordenação sequencial (SOP)
• Problema de programação de job shop (JSP)
• Problema de programação de loja aberta (OSP)
• Problema de fluxo de permutação (PFSP)
• Problema de atraso total de máquina única (SMTTP)
• Problema de atraso ponderado total de máquina única (SMTWTP)
• Problema de agendamento de projeto com restrição de recursos (RCPSP)
• Problema de programação de loja em grupo (GSP)
• Problema de atraso total de máquina única com tempos de configuração dependentes de sequência (SMTTPDST)
• Problema de programação de fluxo de fluxo de vários estágios (MFSP) com tempos de configuração / mudança dependentes de sequência

Problema de roteamento de veículos

• Problema de roteamento de veículo capacitado (CVRP)
• Problema de roteamento de veículos multi-depósito (MDVRP)
• Problema de roteamento de veículo de período (PVRP)
• Problema de roteamento de veículo de entrega dividida (SDVRP)
• Problema de roteamento de veículo estocástico (SVRP)
• Problema de roteamento de veículos com coleta e entrega (VRPPD)
• Problema de roteamento de veículos com janelas de tempo (VRPTW)
• Problema de roteamento de veículo dependente do tempo com janelas de tempo (TDVRPTW)
• Problema de roteamento de veículos com janelas de tempo e vários trabalhadores de serviço (VRPTWMS)

Problema de atribuição

• Problema de atribuição quadrática (QAP)
• Problema de atribuição generalizado (GAP)
• Problema de atribuição de frequência (FAP)
• Problema de alocação de redundância (RAP)

Definir problema

• Definir problema de cobertura (SCP)
• Problema de partição (SPP)
• Problema de partição de árvore de gráfico com restrição de peso (WCGTPP)
• Problema de árvore de cardinalidade L ponderada por arco (AWlCTP)
• Problema de mochila múltipla (MKP)
• Problema de conjunto independente máximo (MIS)

Problema de dimensionamento de dispositivo em design físico de nanoeletrônica

• A otimização baseada na otimização da colônia de formigas (ACO) do circuito amplificador de sentido baseado em CMOS de 45 nm pode convergir para soluções ótimas em um tempo mínimo.
• A síntese de circuito reversível baseada em otimização de colônia de formigas (ACO) pode melhorar significativamente a eficiência.

Otimização e síntese de antenas

Vibradores de loopback 10 × 10, sintetizados por meio do algoritmo ACO

Vibradores Unloopback 10 × 10, sintetizados por meio do algoritmo ACO

Para otimizar a forma das antenas, algoritmos de colônia de formigas podem ser usados. Como exemplo podem ser consideradas antenas etiquetas RFID baseadas em algoritmos de colônia de formigas (ACO), vibradores de loopback e unloopback 10 × 10

Processamento de imagem

O algoritmo ACO é usado no processamento de imagens para detecção de bordas de imagens e vinculação de bordas.

• Detecção de borda:

O gráfico aqui é a imagem 2-D e as formigas atravessam a partir de um pixel que deposita o feromônio. O movimento das formigas de um pixel para outro é direcionado pela variação local dos valores de intensidade da imagem. Este movimento faz com que a maior densidade do feromônio seja depositada nas bordas.

A seguir estão as etapas envolvidas na detecção de borda usando ACO:

Passo 1: Inicialização:
Coloque as formigas aleatoriamente na imagem onde . Matrizes de feromônios são inicializadas com um valor aleatório. O maior desafio no processo de inicialização é determinar a matriz heurística. ${\ displaystyle K}$${\ displaystyle I_ {M_ {1} M_ {2}}}$${\ displaystyle K = (M_ {1} * M_ {2}) ^ {\ tfrac {1} {2}}}$${\ displaystyle \ tau _ {(i, j)}}$

Existem vários métodos para determinar a matriz heurística. Para o exemplo abaixo, a matriz heurística foi calculada com base nas estatísticas locais: as estatísticas locais na posição do pixel (i, j).

${\ displaystyle \ eta _ {(i, j)} = {\ tfrac {1} {Z}} * Vc * I _ {(i, j)}}$

Onde está a imagem do tamanho , que é um fator de normalização ${\ displaystyle I}$${\ displaystyle M_ {1} * M_ {2}}$
${\ displaystyle Z = \ sum _ {i = 1: M_ {1}} \ sum _ {j = 1: M_ {2}} Vc (I_ {i, j})}$

${\ displaystyle {\ begin {alinhados} Vc (I_ {i, j}) = & f \ left (\ left \ vert I _ {(i-2, j-1)} - I _ {(i + 2, j + 1 )} \ right \ vert + \ left \ vert I _ {(i-2, j + 1)} - I _ {(i + 2, j-1)} \ right \ vert \ right. \\ & + \ left \ vert I _ {(i-1, j-2)} - I _ {(i + 1, j + 2)} \ direita \ vert + \ esquerda \ vert I _ {(i-1, j-1)} - I_ { (i + 1, j + 1)} \ direita \ vert \\ & + \ esquerda \ vert I _ {(i-1, j)} - I _ {(i + 1, j)} \ direita \ vert + \ esquerda \ vert I _ {(i-1, j + 1)} - I _ {(i-1, j-1)} \ right \ vert \\ & + \ left. \ left \ vert I _ {(i-1, j +2)} - I _ {(i-1, j-2)} \ direita \ vert + \ esquerda \ vert I _ {(i, j-1)} - I _ {(i, j + 1)} \ direita \ vert \ right) \ end {alinhado}}}$

${\ displaystyle f (\ cdot)}$pode ser calculado usando as seguintes funções: O parâmetro em cada uma das funções acima ajusta os respectivos formatos das funções. Etapa 2 Processo de construção: O movimento da formiga é baseado em 4 pixels conectados ou 8 pixels conectados . A probabilidade com que a formiga se move é dada pela equação de probabilidade Etapa 3 e Etapa 5 Processo de atualização: A matriz de feromônios é atualizada duas vezes. no passo 3, o rastro da formiga (dado por ) é atualizado onde, como no passo 5, a taxa de evaporação do rastro é atualizada, o que é dado pela equação abaixo. , onde está o coeficiente de decaimento do feromônio
${\ displaystyle f (x) = \ lambda x, \ quad {\ text {para x ≥ 0; (1)}}}$
${\ displaystyle f (x) = \ lambda x ^ {2}, \ quad {\ text {para x ≥ 0; (2)}}}$
${\ displaystyle f (x) = {\ begin {cases} \ sin ({\ frac {\ pi x} {2 \ lambda}}), & {\ text {para 0 ≤ x ≤}} \ lambda {\ text {; (3)}} \\ 0, & {\ text {else}} \ end {cases}}}$
${\ displaystyle f (x) = {\ begin {cases} \ pi x \ sin ({\ frac {\ pi x} {2 \ lambda}}), & {\ text {for 0 ≤ x ≤}} \ lambda {\texto{; (4)}} \\ 0, & {\ text {else}} \ end {cases}}}$
${\ displaystyle \ lambda}$

${\ displaystyle P_ {x, y}}$

${\ displaystyle \ tau _ {(x, y)}}$
${\ displaystyle \ tau _ {novo} \ leftarrow (1- \ psi) \ tau _ {antigo} + \ psi \ tau _ {0}}$${\ displaystyle \ psi}$${\ displaystyle 0 <\ tau <1}$

Passo 7 Processo de decisão:
Uma vez que os K ants tenham se movido uma distância fixa L para N iteração, a decisão se é uma aresta ou não é baseada no limiar T na matriz de feromônioτ. O limite para o exemplo abaixo é calculado com base no método de Otsu .

Borda da imagem detectada usando ACO:
As imagens abaixo são geradas usando diferentes funções dadas pela equação (1) a (4).

• Edge linking: ACO também se provou eficaz em algoritmos de edge linking.

Outras aplicações

• Previsão de falência
• Classificação
• Roteamento de rede orientado a conexão
• Roteamento de rede sem conexão
• Mineração de dados
• Fluxos de caixa descontados na programação do projeto
• Recuperação de informação distribuída
• Projeto de rede de energia e eletricidade
• Problema de programação do fluxo de trabalho da grade
• Projeto de peptídeo inibitório para interações de proteína e proteína
• Sistema de teste inteligente
• Projeto de circuito eletrônico de potência
• Dobramento de proteínas
• Identificação do sistema

Dificuldade de definição

Com um algoritmo ACO, o caminho mais curto em um gráfico, entre dois pontos A e B, é construído a partir de uma combinação de vários caminhos. Não é fácil dar uma definição precisa de qual algoritmo é ou não uma colônia de formigas, pois a definição pode variar de acordo com os autores e usos. Em termos gerais, os algoritmos de colônias de formigas são considerados metaheurísticas populadas com cada solução representada por uma formiga se movendo no espaço de busca. As formigas marcam as melhores soluções e levam em consideração as marcações anteriores para otimizar sua busca. Eles podem ser vistos como probabilística multi-agente algoritmos utilizando uma distribuição de probabilidade de fazer a transição entre cada iteração . Em suas versões para problemas combinatórios, eles usam uma construção iterativa de soluções. Segundo alguns autores, o que distingue os algoritmos ACO de outros parentes (como os algoritmos para estimar a distribuição ou a otimização do enxame de partículas) é precisamente o seu aspecto construtivo. Em problemas combinatórios, é possível que a melhor solução eventualmente seja encontrada, mesmo que nenhuma formiga se mostre eficaz. Assim, no exemplo do problema do caixeiro viajante, não é necessário que uma formiga realmente percorra a rota mais curta: a rota mais curta pode ser construída a partir dos segmentos mais fortes das melhores soluções. No entanto, esta definição pode ser problemática no caso de problemas em variáveis ​​reais, onde não existe estrutura de 'vizinhos'. O comportamento coletivo dos insetos sociais continua sendo uma fonte de inspiração para pesquisadores. A grande variedade de algoritmos (para otimização ou não) que buscam a auto-organização em sistemas biológicos levou ao conceito de " inteligência de enxame ", que é uma estrutura muito geral na qual os algoritmos de colônia de formigas se encaixam.

Algoritmos de estigmergia

Na prática, existe um grande número de algoritmos que afirmam ser "colônias de formigas", sem sempre compartilhar o quadro geral de otimização por colônias de formigas canônicas. Na prática, o uso de uma troca de informações entre formigas via ambiente (princípio denominado " estigmergia ") é considerado suficiente para que um algoritmo pertença à classe dos algoritmos colônia de formigas. Esse princípio levou alguns autores a criarem o termo “valor” para organizar métodos e comportamentos baseados na busca de alimento, triagem de larvas, divisão do trabalho e transporte cooperativo.

Métodos relacionados

Algoritmos Genéticos (GA)

Eles mantêm um conjunto de soluções em vez de apenas uma. O processo de encontrar soluções superiores imita o da evolução, com soluções sendo combinadas ou mutadas para alterar o pool de soluções, com soluções de qualidade inferior sendo descartadas.

Estimativa de Algoritmo de Distribuição (EDA)

Um algoritmo evolutivo que substitui operadores de reprodução tradicionais por operadores guiados por modelos. Tais modelos são aprendidos com a população, empregando técnicas de aprendizado de máquina e representados como modelos gráficos probabilísticos, a partir dos quais novas soluções podem ser amostradas ou geradas a partir de crossover guiado.

Recozimento Simulado (SA)

Uma técnica de otimização global relacionada que atravessa o espaço de busca gerando soluções vizinhas da solução atual. Um vizinho superior é sempre aceito. Um vizinho inferior é aceito probabilisticamente com base na diferença de qualidade e em um parâmetro de temperatura. O parâmetro de temperatura é modificado conforme o algoritmo avança para alterar a natureza da pesquisa.

Otimização de pesquisa reativa

Concentra-se na combinação de aprendizado de máquina com otimização, adicionando um loop de feedback interno para autoajustar os parâmetros livres de um algoritmo para as características do problema, da instância e da situação local em torno da solução atual.

Pesquisa Tabu (TS)

Semelhante ao recozimento simulado em que ambos atravessam o espaço da solução testando mutações de uma solução individual. Enquanto o recozimento simulado gera apenas uma solução mutada, a pesquisa tabu gera muitas soluções mutadas e se move para a solução com a menor adequação das geradas. Para evitar ciclos e encorajar um maior movimento através do espaço de solução, uma lista tabu é mantida de soluções parciais ou completas. É proibido mover para uma solução que contenha elementos da lista tabu, que é atualizada conforme a solução atravessa o espaço da solução.

Sistema Imunológico Artificial (AIS)

Modelado no sistema imunológico de vertebrados.

Otimização de enxame de partículas (PSO)

Um método de inteligência de enxame .

Gotas de água inteligentes (IWD)

Um algoritmo de otimização baseado em enxame baseado em gotas de água naturais fluindo em rios

Algoritmo de pesquisa gravitacional (GSA)

Um método de inteligência de enxame .

Método de agrupamento de colônias de formigas (ACCM)

Um método que faz uso da abordagem de clustering, estendendo o ACO.

Pesquisa de difusão estocástica (SDS)

Uma pesquisa probabilística global baseada em agente e técnica de otimização mais adequada para problemas em que a função objetivo pode ser decomposta em várias funções parciais independentes.

História

Os inventores são Frans Moyson e Bernard Manderick . Os pioneiros da área incluem Marco Dorigo , Luca Maria Gambardella .

Cronologia dos algoritmos COA

Cronologia de algoritmos de otimização de colônias de formigas.

• 1959, Pierre-Paul Grassé inventou a teoria da gagueira para explicar o comportamento da construção de ninhos em cupins ;
• 1983, Deneubourg e seus colegas estudaram o comportamento coletivo das formigas ;
• 1988 e Moyson Manderick têm um artigo sobre auto-organização entre formigas;
• 1989, o trabalho de Goss, Aron, Deneubourg e Pasteels sobre o comportamento coletivo de formigas argentinas , que dará a ideia de algoritmos de otimização de colônias de formigas;
• 1989, implementação de um modelo de comportamento para alimentos por Ebling e seus colegas;
• 1991, M. Dorigo propôs o sistema de formigas em sua tese de doutorado (publicada em 1992). Um relatório técnico extraído da tese e coautor de V. Maniezzo e A. Colorni foi publicado cinco anos depois;
• 1994, Appleby e Steward of British Telecommunications Plc publicaram o primeiro aplicativo para redes de telecomunicações
• 1995, Gambardella e Dorigo propuseram ant-q , a versão preliminar do sistema de colônia de formigas como a primeira estensão do sistema de formigas.
• 1996, Gambardella e Dorigo propuseram sistema de colônia de formigas
• 1996, publicação do artigo sobre sistema de formigas;
• 2000, Hoos e Stützle inventam o sistema de formigas máximo-mínimo ;
• 1997, Dorigo e Gambardella propuseram um sistema de colônia de formigas hibridizado com busca local;
• 1997, Schoonderwoerd e seus colegas publicaram um aplicativo aprimorado para redes de telecomunicações ;
• 1998, Dorigo lança a primeira conferência dedicada aos algoritmos ACO;
• 1998, Stützle propõe implementações paralelas iniciais ;
• 1999, Gambardella, Taillard e Agazzi propuseram macs-vrptw , o primeiro sistema de colônia de múltiplas formigas aplicado a problemas de roteamento de veículos com janelas de tempo,
• 1999, Bonabeau, Dorigo e Theraulaz publicam um livro que trata principalmente de formigas artificiais
• 2000, edição especial da revista Future Generation Computer Systems sobre algoritmos de formigas
• 2000, primeiras aplicações ao agendamento , sequência de agendamento e satisfação de restrições ;
• 2000, Gutjahr fornece a primeira evidência de convergência para um algoritmo de colônias de formigas
• 2001, o primeiro uso de algoritmos COA por empresas ( Eurobios e AntOptima );
• 2001 Iredi e seus colegas publicaram o primeiro multi-objetivo algoritmo
• 2002, primeiras aplicações no desenho de cronogramas, redes Bayesianas;
• 2002, Bianchi e seus colegas sugeriram o primeiro algoritmo para o problema estocástico ;
• 2004, Dorigo e Stützle publicam o livro Ant Colony Optimization com a MIT Press
• 2004, Zlochin e Dorigo mostram que alguns algoritmos são equivalentes à descida gradiente estocástica , o método de entropia cruzada e algoritmos para estimar a distribuição
• 2005, primeiras aplicações para problemas de dobramento de proteínas .
• 2012, Prabhakar e colegas publicam pesquisas relacionadas à operação de formigas individuais se comunicando em conjunto sem feromônios, espelhando os princípios de organização de redes de computadores. O modelo de comunicação foi comparado ao Protocolo de Controle de Transmissão .
• 2016, primeira aplicação para desenho de sequência de peptídeos.
• 2017, integração bem-sucedida do método de tomada de decisão multicritério PROMETHEE no algoritmo ACO ( algoritmo HUMANT ).

Referências

Publicações (selecionadas)

• M. Dorigo , 1992. Otimização, Aprendizagem e Algoritmos Naturais , Tese de Doutorado, Politécnico de Milão, Itália.
• M. Dorigo, V. Maniezzo & A. Colorni, 1996. " Ant System: Optimization by a Colony of Cooperating Agents ", IEEE Transactions on Systems, Man, and Cybernetics – Part B, 26 (1): 29-41.
• M. Dorigo & LM Gambardella , 1997. " Sistema de Colônia de Formigas: Uma Abordagem de Aprendizagem Cooperativa para o Problema do Caixeiro Viajante ". IEEE Transactions on Evolutionary Computation, 1 (1): 53–66.
• M. Dorigo, G. Di Caro & LM Gambardella, 1999. " Ant Algorithms for Discrete Optimization ". Artificial Life, 5 (2): 137–172.
• E. Bonabeau, M. Dorigo et G. Theraulaz, 1999. Swarm Intelligence: From Natural to Artificial Systems , Oxford University Press. ISBN  0-19-513159-2
• M. Dorigo & T. Stützle, 2004. Ant Colony Optimization , MIT Press. ISBN  0-262-04219-3
• M. Dorigo, 2007. "Ant Colony Optimization" . Scholarpedia.
• C. Blum, 2005 " Otimização da colônia de formigas: Introdução e tendências recentes ". Physics of Life Reviews, 2: 353-373
• M. Dorigo, M. Birattari & T. Stützle, 2006 Ant Colony Optimization: Artificial Ants as a Computational Intelligence Technique . TR / IRIDIA / 2006-023
• Mohd Murtadha Mohamad, "Articulated Robots Motion Planning Using Foraging Ant Strategy", Journal of Information Technology - Special Issues in Artificial Intelligence, Vol.20, No. 4 pp. 163-181, dezembro de 2008, ISSN  0128-3790 .
• N. Monmarché, F. Guinand & P. ​​Siarry (eds), "Artificial Ants", capa dura de agosto de 2010 576 pp.  ISBN  978-1-84821-194-0 .
• A. Kazharov, V. Kureichik, 2010. " Ant colony optimization algorítmos para resolver problemas de transporte ", Journal of Computer and Systems Sciences International, Vol. 49. No. 1. pp. 30–43.
• CM. Pintea, 2014, Advances in Bioinspiring Computing for Combinatorial Optimization Problem , Springer ISBN  978-3-642-40178-7
• K. Saleem, N. Fisal, MA Baharudin, AA Ahmed, S. Hafizah e S. Kamilah, "Protocolo de roteamento auto-otimizado inspirado na colônia de formigas baseado em arquitetura de camada cruzada para redes de sensores sem fio", WSEAS Trans. Commun., Vol. 9, não. 10, pp. 669-678, 2010. ISBN  978-960-474-200-4
• K. Saleem e N. Fisal, "Enhanced Ant Colony algoritmo para dados auto-otimizados garantidos roteamento em redes de sensores sem fio", Networks (ICON) 2012 18th IEEE International Conference on, pp. 422-427. ISBN  978-1-4673-4523-1
• Abolmaali S, Roodposhti FR. Otimização de portfólio usando o método de colônia de formigas um estudo de caso na Bolsa de Valores de Teerã. Journal of Accounting. Março de 2018; 8 (1).

links externos

• Página de otimização da colônia de formigas da Scholarpedia
• Página inicial de otimização de formigas
• "Ant Colony Optimization" - comunidade científica e de pesquisa russa
• AntSim - Simulação de Algoritmos de Colônia de Formigas
• MIDACO-Solver Software de otimização de uso geral baseado na otimização de colônias de formigas (Matlab, Excel, VBA, C / C ++, R, C #, Java, Fortran e Python)
• University of Kaiserslautern, Germany, AG Wehn: Ant Colony Optimization Applet Visualização do caixeiro viajante resolvido por um sistema de formigas com várias opções e parâmetros (Java Applet)
• Simulador Ant Farm
• Simulação de algoritmo Ant (Java Applet)
• Estrutura do sistema Java Ant Colony