Sistemas de Informação Inteligentes

Aula 4

Nadilma Nunesncvnp@cin.ufpe.br

nadinunes@gmail.com

Swarm Intelligence

• Algoritmos em que agentes atuam localmente realizando alguma interação com o grupo

• Individualismo x Coletivo

• As ações individuais de cada agente somadas e a interação entre eles formam a solução do problema como um todo

• Algoritmos populares: • Ant Colony Optimization

• Particle Swarm Optimization

ACO – Ant Colony Optimization

•Foi observado o comportamento das formigas na busca pelos alimentos.

•Inicialmente cada formiga segue um caminho aleatório

•Após algum tempo elas tendiam a seguir um único caminho, considerado ótimo

•Cada formiga utiliza uma comunicação indireta para indicar para as outras o quão bom foi o caminho que ela escolheu

•Para isso elas espalham uma substância chamada “feromônio”

ACO – Ant Colony Optimization• Foi colocado um ninho de formigas em um aquário com uma fonte de alimentos na outra ponta.• Para chegar até esse alimento foram criados dois caminhos, sendo um maior que o outro.

• Como as formigas que escolheram o menor caminho faziam o percurso mais rapidamente que as outras, elas acabavam depositando uma maior quantidade de feromônio nesse caminho em relação ao outro em um mesmo instante de tempo.

• Logo, em um determinado momento a intensidade do feromônio no caminho mais curto estará tão alta que quase todas as formigas seguirão por ele.

Voltando para Ant Colony Optimization

Formigas são capazes de achar o caminho mais curto entre dois pontos (como entre o formigueiro e uma fonte de comida) que pertençam ao ambiente da colônia

Dado um grafo com n vértices, colocar uma formiga artificial em cada um destes.

ACO

Ant Colony Optimization

Cada formiga traça um caminho seguindo uma fórmula probabilística em função do feromônio “depositado” em cada aresta do grafo.

ACO

Experimento de Deneubourg

1s

l

llr

2s

l

llr

Experimentos de Deneubourg

• Terceiro experimento– Movimento observado apenas com caminho

maior– Caminho menor adicionado após 30 minutos

Utilizando ACO

• O algoritmo de ACO pode ser utilizado para achar caminhos curtos em redes.

• Esses mecanismos utilizam parâmetros importantes como: quantidade de formigas por grupo, número de passos do algoritmo, entre outros.

• Nota-se que a tarefa de uma formiga sozinha é bastante simples, porém se comunicando dentro de uma colônia, são capazes de resolver problemas de difícil solução.

ACO – Ant Colony Optimization

Em 1992, Dorigo percebeu que as formigas resolviam um problema muito similar ao TSP e, inspirado nesse comportamento, resolveu modelá-lo computacionalmente e verificar como se comportava em algumas instâncias conhecidas do problema.

Relembrando...Travelling Salesman Problem (TSP)

Um caixeiro viajante deve partir de sua cidade, visitar “n” cidades diferentes, e retornar a sua origem.

TSP

Qual a seqüência de de cidades que devo percorrer de modo que eu gaste o menor tempo possível?

TSP

A solução ótima pode ser intuitiva para casos simples do problema

Travelling Salesman Problem (TSP)

A solução ótima pode ser intuitiva para casos simples do problema

TSP

Travelling Salesman Problem (TSP)

Mas aumentando um pouco a complexidade do problema, nota-se que a solução já não é mais intuitiva

TSP

?

Travelling Salesman Problem (TSP)

Mas aumentando um pouco a complexidade do problema, nota-se que a solução já não é mais intuitiva

TSP

?

Travelling Salesman Problem (TSP)

Mas aumentando um pouco a complexidade do problema, nota-se que a solução já não é mais intuitiva

TSP

?

Travelling Salesman Problem (TSP)

Mas aumentando um pouco a complexidade do problema, nota-se que a solução já não é mais intuitiva

TSP

• No exemplo anterior temos 8 cidades. Isso dá um total de (8-1)! = 5040 combinações possíveis. Fácil de resolver!

• Se aumentarmos para 20 cidades, teríamos (20-1)! = 121645100408832000. Não é tão simples.

Travelling Salesman Problem (TSP)TSP

• Agora em um problema típico com 100 cidades, teríamos (100-1)! = 9x10155 combinações possíveis!!!!

• Se um computador de 10THz consegue processar 1012 combinações por ciclo, levaríamos 9x10143 ciclos para completar essa tarefa, 9x10131 segundos, que é igual a 3x10136 anos. O universo tem aproximadamente 13,7x109 anos.

TSP e um pouco de matemática... TSP

AplicaçõesTelecommunications

Roteamento de dados em uma rede.É um problema dinâmico, ou seja, existem alterações no

ambiente otimizado em função do tempo. Ex.: uma máquina é desconectada, uma linha de transmissão fica

congestionada,...

Aplicação ACO nas Telecomunicações

AplicaçõesTelecommunications

Schoonderwoerd R., O. Holland, J. Bruten and L. Rothkrantz (1997). Ant-based Load Balancing in Telecommunications Networks. Adaptive Behavior, 5(2):169-207.

Schoonderwoerd R., O. Holland and J. Bruten (1997). Ant-like Agents for Load Balancing in Telecommunications Networks. Proceedings of Agents'97, Marina del Rey, CA, ACM Press, 209-216.

Di Caro G. and M. Dorigo (1997). AntNet: A Mobile Agents Approach to Adaptive Routing. Tech. Rep. IRIDIA/97-12, Université Libre de Bruxelles, Belgium.

Di Caro G. and M. Dorigo (1998). Mobile Agents for Adaptive Routing. Proceedings of the 31st Hawaii International Conference on System, IEEE Computer Society Press, Los Alamitos, CA, 74-83.

Di Caro G. & Dorigo M. (1998). AntNet: Distributed Stigmergetic Control for Communications Networks. Journal of Artificial Intelligence Research (JAIR), 9:317-365.

Navarro Varela G. and M.C. Sinclair (1999). Ant Colony Optimisation for Virtual-Wavelength-Path RoutiTng and Wavelength Allocation. Proceedings of the Congress on Evolutionary Computation (CEC'99), Washington DC, USA, July 1999.

Ducatelle, F., G. Di Caro and L. M. Gambardella (2005). Using Ant Agents to Combine Reactive and Proactive Strategies for Routing in Mobile Ad Hoc Networks. International Journal of Computational Intelligence and Applications (IJCIA), Special Issue on Nature-Inspired Approaches to Networks and Telecommunications, Volume 5, Number 2, Pages 169-184, June 2005

Aplicação ACO nas Telecomunicações

AplicaçõesScheduling (escalonamento)

Dividir n tarefas para m máquinas de forma obter o máximo aproveitamento ou menor tempo de processamento

possível.Ex.: escalonamento de processos em uma CPU, divisão de projetos em uma empresa, compartilhamento de máquinas

em linha de produção.

Aplicação ACO em Escalonamento

AplicaçõesScheduling

Colorni A., M. Dorigo, V. Maniezzo and M. Trubian (1994). Ant system for Job-shop Scheduling. JORBEL - Belgian Journal of Operations Research, Statistics and Computer Science, 34(1):39-53.

Forsyth P. and A. Wren (1997). An Ant System for Bus Driver Scheduling. Presented at the 7th International Workshop on Computer-Aided Scheduling of Public Transport, Boston, August 1997.

Aplicação ACO em Escalonamento

Ficha de ACO

• Leitura• Resumo feito a mão