OTIMIZAÇÃO ALGORITMO DE COLONIA DE FORMIGA

OTIMIZAÇÃO ALGORITMO DE COLONIA DE FORMIGA

Antonio Cristiano Ferreira Negrão

Leticia Oliveria Reis

Sistemas Inteligentes– Fábio Ferreira

1-Introdução

Formigas reais

Em geral, as formigas seguem o menor caminho entre o formigueiro e sua fonte de alimento.Enquanto andam, as formigas depositam no solo uma substância chamada feromônio.

Na presença de feromônio, elas possuem certa tendência a seguir o caminho marcado com a substância.Essa tendência é baseada na quantidade de feromônio presente em cada caminho: quanto maior concentração, maior a chance da trilha ser seguida.

Como as formigas caminham:

Inicialmente, como não há feromônio nos caminhos, as formigas andam aleatoriamente em busca de alimento.

As formigas que escolhem (ao acaso) o menor caminho voltam por ele. Como a ida e a volta são mais rápidas, há um pouco mais de feromônio nesse caminho. Como essa trilha possui mais feromônio, outras formigas tendem a segui-la. Com isso, o feromônio na trilha irá aumentar. Com o passar do tempo, os menores caminhos recebem uma carga maior de feromônio, sendo escolhidos pelas formigas. O feromônio também evapora com o tempo.

Dessa forma, os caminhos menos visitados perdem feromônio, levando as formigas aos caminhos escolhidos pelas demais.

Formigas artificiais

Os algoritmos de colônias de formigas:

São aplicados a problemas representados por um grafo G(V, A).

São algoritmos de construção: a cada iteração, cada formiga, individualmente, constrói uma solução para o problema.

São algoritmos que, a cada iteração, trabalham com uma população de formigas (e, portanto, com uma população de soluções).

Na construção da solução, a formiga leva em conta:

Informações heurísticas (fixas), que indicam a conveniência, para a obtenção da solução do problema, de se tomar determinado caminho.

A quantidade de feromônio (variável), que indica quão desejável é um determinado caminho.

2.1-Otimização do Algoritmo de Formigas – CUDA e Algoritmos genéticos

O artigo pesquisado trata-se da utilização do algoritmos de formigas rodando em CPU, e uma versão adaptada rodando em GPU através da tecnologia de CUDA para otimização no uso de jogos digitais, sendo seu principal objetivo o aumento de desempenho.

Conforme citado no artigo “O algoritmo da colonia de formigas já é muito conhecido por sua capacidade de solucionar problemas de caminhamentos” [Dorigo, 2004]. Mas quando utilizado em problemas mais complexo sua aplicação se torna dificil, por esse motivo o artigo tras uma solução para o problema, onde utiza-se os algoritmos geneticos.

O algoritmo de formigas é implementado da seguinte forma:

1- Existem as colonias de formigas, ambiente, e um grafo gerado.

2- Um determinado numero de formigas é criado, afim de buscar o caminho até a comida.

3- Ao encontrar comida irá gerar o feromonio do caminho percorrido(caso o caminho seja inutil não deixará rastros).

4- Após a simulação, ocorre a evolução das colonias onde todas são avaliadas e a mais eficiente é utilizada nas proximas gerações.

Os elementos que compõem o algoritmo de formigas são as colônias, grafo, formiga, feromônio, gerações, seleção natural e a função de fitness através desse atributos serão possiveis identificar todos os dados gerados pelos algoritmos e no final da simulação permite-se a avaliação.

A implementação do algoritmo para simulação em CPU funciona da seguinte forma executa a colônia; cria-se nova geração; operação é um loop.

A implementação para simulação em GPU é possivel simular as colonias de formigas, tendo como objetivo ganhar em desempenho sobre o algoritmo para CPU.

De acordo com o artigo os resultados de cada simulação encontrada foram satisfatorios, ambos conseguiram simular os casos, mas o resultado (tempo) da simulação da GPU em relação a CPU não foi satisfatorio. Por causa da alocação e desaloção constante de memória.

A CPU simulou a situação dentro das expectativas, superando até mesmo a GPU no resultado final. Com isso podemos observar que os algoritmos de colonias de formiga podem serem aplicados em jogos para otimizar problemas.

2.2 - Otimização por colônia de formigas para o problema de sequenciamento de tarefas em uma única máquina com terceirização permitida.

O problema

O problema abordado neste artigo pode ser definido como:

Seja J um conjunto de n tarefas a serem sequenciadas para produção in-house ou terceirizadas, cada tarefa Ji é definida por:

a) um tempo de processamento pi;

b) um custo de terceirização oi;

c) um tempo de entrega de terceirização li.

Como mencionado anteriormente, estes problemas contêm um conjunto de tarefas. Cada tarefa pode ser sequenciada em uma máquina única ou terceirizada. O término de uma tarefa i é definido pela Equação1. O custo total de terceirização é definido pela Equação 2. em que:

O conjunto Oπ contém todas as tarefas terceirizadas;

O conjunto Sπ contém as tarefas a serem realizadas na máquina única;

O conjunto SPk contém todas as tarefas de Sπ sequenciadas antes da tarefa k.

A função objetivo do problema a ser estudado é mostrada na Equação 3

Como utilizou o algoritmo:

O método