Sistemas de Informação Inteligentes
Aula 4
Nadilma Nunes
[email protected]
[email protected]
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 paraACO
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 Optimization
Ant Colony
Cada formiga traça um caminho seguindo uma fórmula
probabilística em função do feromônio “depositado” em
cada aresta do grafo.
Experimento de Deneubourg
ll
r  1
ls
ll
r 2
ls
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
TSP
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
Travelling Salesman
Problem (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.
TSP de matemática...
TSP e um pouco
• 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.
Aplicações
Aplicação ACO nas Telecomunicações
Telecommunications
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
Aplicações
Aplicação ACO nas Telecomunicações
Telecommunications
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, 209216.
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, 7483.
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-WavelengthPath 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ções
Aplicação ACO em Escalonamento
Scheduling (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
Aplicações
Aplicação ACO em Escalonamento
Scheduling
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 ComputerAided Scheduling of Public Transport, Boston, August 1997.
Ficha de ACO
• Leitura
• Resumo feito a mão