Inteligência coletiva

Páginas: 16 (3945 palavras) Publicado: 13 de junho de 2012
IA013 – Introdução à Computação Natural

Departamento de Engenharia de
Computação e Automação Industrial

Faculdade de Engenharia
Elétrica e de Computação

Tópicos
Unicamp

Ant Colony Optimization e
Swarm Intelligence

• Swarm Intelligence
•Ant Colony Optimization – ACO
•Particle Swarm Optimization – PSO
•Ant Clustering Algorithms - ACA

Fabrício Olivetti de Françaolivetti@dca.fee.unicamp.br
CAMPINAS, SP – BRASIL

março / 2007

1

2

Tópicos

Swarm Intelligence
• O que é?

• Swarm Intelligence

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

•Ant Colony Optimization – ACO

• Características:

•Particle Swarm Optimization – PSO

• Individualismo x Coletivo

•Ant Clustering Algorithms - ACA

• Cadaagente interage localmente com o ambiente
• Essa iteração causa um padrão coerente de forma global resolvendo um
problema
• Não existe centralização
• Coordenação sem comunicação evidente
3

• Algoritmos populares: Ant Colony Optimization e Particle Swarm
Optimization

Swarm Intelligence
- Motivações -

4

Swarm Intelligence
- Na Natureza -

• Na natureza, criaturas simples apresentamcomportamentos
complexos

• Busca pelo menor caminho entre o ninho e a fonte de alimento
• Organização dos corpos de indivíduos mortos e lixos dentro do
ninho

• Os comportamentos destes são alterados com coerência
conforme o ambiente muda

• Emigração de um bando

• Esse comportamento é observado em:

• Construção do ninho

• insetos

• Vôo em grupo

• pássaros
• bactérias• e outros animais que vivem em bandos
5

6

1

Swarm Intelligence
- No Dia a Dia -

Tópicos

• Trânsito (a ação dos indivíduos influi na organização do todo)
http://vwisb7.vkw.tu-dresden.de/~treiber/MicroApplet/

• Swarm Intelligence
•Ant Colony Optimization – ACO

• Atribuição de pequenas tarefas para uma equipe em um grande
projeto
• Linha de montagem

•Particle SwarmOptimization – PSO
•Ant Clustering Algorithms - ACA

• Cirurgia Médica

7

Ant Colony Optimization

8

Ant Colony Optimization

Goss, S., S. Aron e J. L. Deneubourg. Self-organized shortcuts in the Argentine ant.
Naturwissenschaften, v.76, p.579-581. 1989.

9

Ant Colony Optimization

10

Ant Colony Optimization

•Foi observado o comportamento das
formigas na busca pelosalimentos.
•Inicialmente, cada formiga segue um
caminho aleatório

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.

•Após algum tempo elas tendiam a seguir um único caminho,
considerado ótimo
•Cada formiga utiliza uma comunicação indireta para indicar
para asoutras o quão bom foi o caminho que ela escolheu
•Para isso, elas espalham uma substância chamada
“feromônio”
11

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, dado um intervalo de tempo.
Logo, dado tempo suficiente, a intensidade de feromônio nocaminho mais curto
12
estará bem mais alta e atrairá a maior parte das formigas (mas não todas).

2

Ant Colony Optimization

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

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

?

13

14

Ant Colony Optimization

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.
?

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

Por favor, assinar para o acesso.

Estes textos também podem ser interessantes

  • Inteligencia Coletiva
  • Inteligência coletiva
  • Inteligencia Coletiva
  • Sensemaking e inteligência coletiva
  • Resenha inteligência coletiva
  • Inteligência Coletiva
  • Antropologia
  • Antropologia e ética

Seja um membro do Trabalhos Feitos

CADASTRE-SE AGORA!