Bountoux & Feillet (2006) desenvolveram um algoritmo baseado na otimização por colônia de formigas. Esse método de otimização inspira-se nas formigas reais, quando elas procuram alimento exploram inicialmente a área que cerca o ninho de maneira aleatória. Em pouco tempo as formigas encontram o caminho para o alimento, dependendo da quantidade e da qualidade, as formigas carregam para o ninho. Durante a viagem de retorno, a formiga deposita no chão uma substancia química, o feromônio. A quantidade de feromônio depende da qualidade e da quantidade de comida, o que guiará outras formigas na busca pela comida. A comunicação indireta entre formigas via feromônio permite que elas encontrem os menores caminhos (Dorigo et al, 1996).
O algoritmo proposto por Bountoux & Feillet (2006) foi denominado Dynamic Multi-Dimensional Anamorphic Traveling Ant (DMD-ATA), trata-se de uma melhoria para o algoritmo original de colônia de formigas especializado na solução do Problema do Caixeiro Comprador Não Capacitado.
No DMD-ATA, uma formiga artificial é um agente que se move de um mercado para outro em um grafo PCC. Formigas artificiais preferem mercados que estão conectados por arestas que possuem maior quantidade de feromônio e que são mais promissores de acordo com uma heurística. Após coletar todos os produtos, a formiga não retorna para o depósito imediatamente, ela tem a possibilidade de visitar mais mercados com uma probabilidade sendo diminuída. Ao terminar o percurso, as formigas deixam nos arcos pertencentes ao percurso uma quantidade de feromônio que é proporcional à qualidade da solução. Além disso, se alguma formiga encontrar uma melhoria sobre a melhor solução encontrada, a nova solução é armazenada. A deterioração do feromônio é executada introduzindo um coeficiente de evaporação: em cada iteração, o feromônio de cada arco é reduzido de 0.1%.
A seguir serão descritos os componentes do algoritmo Dynamic Multi- Dimensional Anamorphic Traveling Ant (DMD-ATA).
3.9.1 Viagem das formigas
Inicialmente, em um algoritmo de colônia de formigas, toda vez que uma formiga retorna ao depósito, uma formiga nova sai do depósito. O componente principal da viagem das formigas consiste no fato das formigas trabalharem em paralelo. A idéia é ter um conjunto de formigas, buscando em paralelo por soluções PCC e cooperando através do feromônio. Informalmente, cada formiga constrói uma solução PCC de maneira iterativa: adiciona cidades novas a uma solução parcial explorando a informação ganha na experiência passada e uma heurística. A experiência passada é dada pela quantidade de feromônio depositado pelas formigas nas arestas das solução PCC.
Quando uma formiga alcança o depósito, uma quantidade de feromônio será depositada nas arestas que foram visitadas pela formiga. Esta quantidade depende da qualidade da solução encontrada pela formiga. Isto permite evitar o depósito de feromônio em arestas que pertencem à rotas ruins. No inicio da solução, a quantidade de feromônio é idêntica em todas as aresta. Quando uma formiga retorna ao depósito, começa uma nova rota. As rotas têm comprimentos diferentes e por esse motivo as formigas não estão sincronizadas. Esse tratamento permite um melhor controle das formigas e atualizações mais realísticas de feromônio.
3.9.2 Anamorphic
O componente Anamorphic corresponde ao uso de diferentes tipos de formiga. Cada formiga é definida por um conjunto de parâmetros:
a) Independência (d): esse parâmetro indica a habilidade de uma formiga seguir seu próprio caminho, o que significa ser menos guiada pelo feromônio.
b) Afinidade (a): esse parâmetro indica a atração da formiga para o feromônio. c) Laziness (s): esse argumento designa se a formiga prefere reduzir a distância
entre mercados no custo total, mesmo que comprando alguns produtos por preço mais alto.
d) Avidity (v): esse parâmetro especifica se a formiga prefere reduzir o custo dos produtos, mesmo que distâncias extras sejam necessárias.
Cada formiga é definida inicialmente com valores aleatórios para os parâmetros d, a, s e v. Esses parâmetros são utilizados para calcular a probabilidade de alcançar um mercado vi através do mercado vj.
3.9.3 Multi-dimensional
Um inconveniente bem conhecido para algoritmos de colônia de formigas (Dorigo et al, 1996) é o risco do feromônio concentrar-se em algumas arestas raras, proibindo arestas que poderiam pertencer à solução ótima ou próxima da ótima. Para evitar esse inconveniente Bountoux & Feillet (2006) adicionaram uma característica multi-dimensional: trinta níveis de feromônios são espalhados em paralelo e cada formiga é então influenciada por um único nível de feromônio, aquele no qual deixa o seu feromônio. O número de formigas por nível é constante durante todo o processo, no entanto existe um fator dinâmico que influencia a quantidade de níveis e permite fundir alguns níveis.
3.9.4 Dinâmico
A fim de usar eficientemente componentes precedentes, algumas características dinâmicas serão incluídas. Primeiramente, as características da população de formigas têm a possibilidade de evoluir durante todo o algoritmo. Quando o custo de uma formiga ultrapassar o valor da melhor solução encontrada multiplicado por um coeficiente dado, a formiga é cortada, tendo alcançado, ou não, o depósito.
O coeficiente é dado por: 1.5+(númerodeprodutos+númerodemercados)/100. Essa fórmula visa encontrar um acordo bom entre cortar formigas quando tendem a gerar soluções más e preservar diversidade quando as instâncias forem grandes. Quando uma formiga é cortada, estará sujeita a um ponto de penalidade e
reinicializa sua rota do depósito. Uma reserva inicial de dez pontos é dada a cada formiga. Quando uma formiga consume todos os seus pontos, será cortada definitivamente e uma formiga nova será adicionada.
Essa formiga nova é definida como um clone da formiga que encontra a melhor solução, com algumas variações em seus parâmetros para evitar a convergência prematura para um conjunto de formigas idênticas. Finalmente, a reserva dos pontos é ajustada para cinqüenta quando uma formiga ocasiona uma melhoria acrescendo a melhor solução existente. Dessa maneira, as melhores formigas são promovidas, enquanto aquelas formigas que visitam partes do espaço que não são interessantes, são eliminadas.
Uma melhoria sobre a característica multi-dimensional é dada pelo número variável de níveis de feromônio. Toda vez que uma formiga é cortada, o nível onde ela se encontra é sujeito a um ponto de penalidade. A reserva do ponto será ajustada a seu valor inicial, cem, quando uma formiga desse nível conseguir uma melhoria em cima da melhor solução encontrada. Quando um nível do feromônio esgotar sua reserva, o nível será excluído. Isso permite concentrar-se nos níveis mais promissores. Entretanto, a fim de preservar a diversidade, a exclusão para quando restam apenas dez níveis. Em vez de serem suprimidos, os níveis são fundidos com o nível onde se localiza a melhor solução encontrada. Observa-se que, quando um nível é suprimido, as formigas que estavam nesse nível serão suprimidas também.
3.9.5 Intensificação com busca local
Para conseguir melhor performance são utilizados procedimentos de busca local. Essa busca local é uma combinação dos procedimentos de inserção de exclusão de mercados. O procedimento de inserção tenta inserir mercados até que nenhuma melhoria seja conseguida. O procedimento de exclusão do mercado é excluído da solução, diminuindo o custo da viagem e aumentando o valor dos produtos.
O procedimento de busca local proposto por Bountoux & Feillet (2006) é um tipo de extensão da exclusão. No procedimento de exclusão, apenas um mercado é
excluído a cada chamada do procedimento. Riera-Ledesma & Salazar-González estenderam essa idéia para k-mercados, onde k mercados consecutivos são excluídos.Em seu procedimento Dropstar, Bountoux & Feillet (2006) se propõem a determinar um conjunto de mercados ótimos, consecutivos ou não, que não devem ser excluídos. Dessa maneira, o procedimento Dropstar gera sub-cadeias ótimas. Essa expansão aumenta consideravelmente o tamanho da vizinhança, uma vez que pode ser difícil obter-se uma sub-cadeia ótima.
Bountoux & Feillet (2006) geram sub-cadeias ótimas através de programação dinâmica recursiva, baseada no grafo obtido na rota original. O grafo é construído da seguinte forma: um vértice é adicionado a cada mercado presente na rota; dois vértices são adicionados, duplicando o depósito para início e fim da rota. Arestas são então adicionadas entre cada mercado e mercados localizados próximo na rota. O procedimento consiste em encontrar o menor caminho em um grafo entre as duas cópias do depósito, com a restrição de que todos os produtos sejam comprados.
O algoritmo é aplicado apenas ao Problema do Caixeiro Comprador não capacitado e é feita uma comparação com o algoritmo de Riera-Ledesma & Salazar- González (2005a), os resultados são qualitativamente melhores que os resultados de Riera-Ledesma & Salazar-González (2005a), no entanto, o tempo de processamento é muito maior, mesmo trabalhando com uma plataforma superior.