OTIMIZAÇÃO BASEADA EM
COLÔNIA DE FORMIGAS (ACO) E
POR ENXAMES DE PARTÍCULAS
(PSO)
1
Leandro M. Almeida
[email protected]
OTIMIZAÇÃO BASEADA EM
COLÔNIA DE FORMIGAS (ANT
COLONY OPTIMIZATION – ACO)
2
ACO - INTRODUÇÃO
Criada por Marco Dorigo
(http://iridia.ulb.ac.be/~mdorigo) em sua tese de
PhD defendia em 1992;
 Apresentada mais formalmente e
detalhadamente em 1996;
 É uma heurística baseada em probabilidade,
criada para solução de problemas computacionais
que envolvem a procura de caminhos em grafos;
 Inspirada na observação do comportamento das
formigas ao saírem de sua colônia para encontrar
comida.

3
ACO - INTRODUÇÃO
ACO é uma heurística de propósito geral que
pode ser usada para problemas de otimização
combinatórial;
 Possui as seguintes características:

Versatilidade: pode ser aplicado a versões
ligeiramente modificadas de um mesmo problema
(e.g. TSP e ATSP);
 Robustez: pode ser aplicado com mínimas
modificações de forma a tratar de outros problemas
de otimização combinatórial;
 Baseado em população: permite a explotação de
feedback positivos como um mecanismo de busca, o
que facilita a implementação paralela do mesmo.

4
ACO - INTRODUÇÃO
Devido a ser um paradigma de propósito geral
pode ser superado por um algoritmo
especializado;
 As atividades de busca são fundamentadas em
formigas;
 Existem agentes com habilidades muito simples,
de certa forma, imitando as formigas;
 Foi observado que as formigas são animais quase
cegos, mas que conseguem gerenciar e
estabelecer menores caminhos entre a colônia e a
fonte de alimento;
 Além disso, descobriu-se que o meio de
comunicação usado entre as formigas são os
traços de feromômio.

5
ACO - INTRODUÇÃO
6
ACO - INTRODUÇÃO
Uma formiga durante a sua movimentação marca
o caminho com uma dada quantidade de
feromônio;
 Enquanto uma formiga isolada realiza
movimentações essencialmente aleatórias, uma
que encontra um caminho previamente
percorrido pode detectá-lo e então decidir com
uma alta probabilidade em segui-lo, reforçando
assim o caminho com o seu próprio feromônio;
 O comportamento coletivo é da forma de um
comportamento “autocatalítico”


Quanto mais formigas seguem um caminho, mais
atrativo ele se torna.
7
ACO - INTRODUÇÃO
O processo é caracterizado pela existência de laço
de retroalimentação positivo, onde a
probabilidade a partir da qual uma formiga
escolhe um caminho aumenta com o número de
formigas que previamente escolheram o mesmo
caminho;
 Considerando um caminho ao longo do qual
formigas saem do ninho A para a fonte
alimentação E e vice-versa;

Subitamente um obstáculo surge e interrompe o
caminho;
 No início todas as formigas possuem as mesmas
probabilidades usadas na tomada de decisão;
 A partir do momento que os traços de feromônios são
reforçados as probabilidades também mudam;

8
ACO - INTRODUÇÃO
9
ACO - INTRODUÇÃO
Um sistema que utiliza informações derivadas do
estudo de colônias de formigas reais é chamado
de Ant System (AS), já os algoritmos são
chamados de Ant Algorithms (AA);
 A idéia não é simular as colônias de formigas,
mas usar colônias de formigas artificiais como
ferramenta de otimização;
 Diferenças entre o AS e o sistema biológico:

Formigas artificiais possuem alguma memória;
 Não são completamente cegas e;
 Vivem em um ambiente onde o tempo é discreto.

10
ACO - INTRODUÇÃO
Suponha que a distância entre D e H, B e H e
entre B e D – via C – são iguais a 1 e que C está
posicionado na metade entre D e B;
 Considerando que o tempo é discreto com
intervalos regulares t := 0, 1, 2;
 Suponha que 30 formigas estão indo em direção a
B e D partindo de A e E e que caminham a
velocidade 1 por unidade por tempo, liberando
feromônio no tempo t com intensidade 1;
 O feromônio evapora completamente e
instantaneamente no meio do intervalo de tempo
sucessivo (t+1, t+2);

11
ACO - INTRODUÇÃO
12
ACO - INTRODUÇÃO
No tempo t=1, 30 novas formigas indo para B
partindo de A encontraram pegadas com
intensidade 15 deixadas por 15 formigas que
foram para H e um caminho de intensidade 30 de
formigas que vieram até A e foram até D partindo
de A;
 A probabilidade de escolher um caminho é
portanto guiada pela quantidade de formigas que
já o escolheram;
 Assim, a quantidade de formigas que foram para
C é o dobro da quantidade das que foram para H:
20 versus 10;
 O mesmo se aplica as 30 formigas de D oriundas
de E;

13
ACO – ANT SYSTEM
Dado um conjunto de N cidades, o problema do
caixeiro viajante (TSP) pode ser definido como uma
busca pelo menor caminho que considera todas as
cidades;
 dij é distância entre as cidade i e j;
 bi(t) (i = 1,...,n) número
de formigas na cidade i no
n
b (t ) o número total de
tempo t e m 
i 1 i
formigas.


Escolhem a próxima cidade com uma função de
probabilidade que leva em conta a distância e a
quantidade de pegadas presentes numa aresta;
 Transições para cidades já visitadas não são permitidas
até que uma rota completa seja encontrada;
 Quando uma rota completa é encontrada, uma
substância chamada trail é colocada em cada aresta

14
ACO – ANT SYSTEM

 ij (t ) se refere à função de intensidade da
pegada (trail) na aresta (i, j) no tempo t;
 Cada formiga no tempo t escolhe a próxima
cidade que será visitada no tempo t+1;
 Se em uma iteração do algoritmo AS são
produzidos m movimentos por m formigas no
intervalo (t, t+1), então a cada n iterações (ciclos)
do algoritmo cada formiga encontrará uma rota;
 Após isso, executa-se a tarefa de aplicação da
intensidade da pegada, através da seguinte
fórmula:
15
ACO – ANT SYSTEM


Onde ρ é um coeficiente tal que (1 - ρ) representa
a evaporação da pegada entre o tempo t e t + n,
Onde
é a quantidade de substância
(feromônio) deixada na aresta (i, j) pela k-ésima
formiga entre o tempo t e t + n, que é dado por:

Q/Lk se a k-ésima formiga usa a aresta (i, j) na rota,
caso contrário é 0.

Onde Q é uma constante e Lk é o tamanho da rota.
16
ACO – ANT SYSTEM
O parâmetro ρ “intensidade da retroalimentação”
possuir um valor <1 para evitar a acumulação
ilimitada de pegadas;
 Q é um parâmetro definido normalmente com
valores >100 e possui pouca influência sob o
modelo;
 Cada formiga possui internamente uma lista
tabu com a relação de cidades visitadas;
 Função de probabilidade de transição possui um
parâmetro de visibilidade ηij como a quantidade
1/dij

17
ACO – ANT SYSTEM


Neste esquema α e β controlam a importância
relativa das pegas versus a visibilidade;
A probabilidade de transição é um trade-off entre
visibilidade (cidade mais próximas devem ser
escolhidas com alta probabilidade) e intensidade
da pegada (um alto tráfico indica uma alta
probabilidade de seguir o caminho).
18
ACO - ALGORITMO
No tempo t = 0, uma fase de inicialização
posiciona as formigas em diferentes cidades e
defini o mesmo valor de τij(0) para todas as
arestas;
 O primeiro elemento da lista tabu de cada
formiga é definido como o ponto de início do
percurso;
 Para cada movimento da cidade i para a j utilizase a função de probabilidade de transição;
 Com o tempo t = 0 tem-se um algoritmo “guloso”
de múltiplos pontos;

19
ACO - ALGORITMO
Após n iterações todas a formigas terminam
encontrando um caminho, as listas tabus estão
cheias, computa-se o Δτkij para cada Lk na lista;
 O algoritmo é executado até o número máximo de
iterações ou até atingir uma situação de
estagnação;
 Parâmetros:

α: importância relativa da pegada α >= 0;
 β: importância relativa da visibilidade β >=0;
 ρ: persistência da pegada, 0 < ρ < 1 (1 – ρ pode ser
interpretado como a evaporação da pegada);
 Q: uma constante relacionada à qualidade da pegada
deixada pelas formigas.

20
ACO – APLICADO EM OUTROS PROBLEMAS

Para a aplicação do algoritmo autocatalítico a
problemas de otimização combinatórial é
necessário:
Uma representação em grafo apropriada que permita
a busca usando muitos e simples agentes para o
problema;
 Um processo autocatalítico (positivo) de
retroalimentação;
 Uma heurística que permita uma definição
construtiva de soluções;
 Um método de satisfação de restrições (e.g. lista
tabu).

21
ACO – VANTAGENS E DESVANTAGENS

Para o TSP (Traveling Salesman Problem) é
relativamente eficiente
Para um pequeno número de nodos, TSPs podem ser
resolvidos através de buscas exaustivas;
 Para um grande número de nodos, TSPs são
computacionalmente muito difícieis de resolver (NPhard) – tempo exponencial para a convergência;


Possui um melhor desempenho do que outras
técnicas de otimização global (AG, simulated
annealing, etc), quando aplicadas ao TSP;
22
ACO – VANTAGENS E DESVANTAGENS

Comparado a AG
Retém toda a memória da colônia ao invés da geração
anterior somente;
 Pouco afetado por uma inicialização “pobre” (random
path selection and colony memory).

Pode ser utilizado em aplicações dinâmicas;
 É continuamente empregado a uma vasta
variedade de aplicações;
 É uma boa escolha para problemas de restrições
discretas;
 A análise teórica é complicada


Seqüências aleatórias, distribuição de probabilidade e
por ser uma pesquisa experimental.
23
ACO – VANTAGENS E DESVANTAGENS

A codificação é um tanto complicada, não é direta
Necessidade criar mecanismos para adição/remoção
de feromônios e atualizações locais e globais;
 Existe um grande número de algoritmos ACO para
explorar diferentes tipos de problemas.

24
ALGUNS ARTIGOS...




Martens, D.; De Backer, M.; Haesen, R.; Vanthienen, J.;
Snoeck, M.; Baesens, B. Classification With Ant Colony
Optimization. IEEE Transactions on Evolutionary
Computation, vol. 11(5), 651-665, 2007.
Solnon, C. Ants can solve constraint satisfaction
problems. IEEE Transactions on Evolutionary
Computation, vol 6(4), 347-357, 2002.
Kanade, P.M.; Hall, L.O. Fuzzy Ants and Clustering.
IEEE Transactions on Systems, Man and Cybernetics, Part
A, Vol. 37(5), 758-769, 2007.
De-Sian Lu, Chien-Chang Chen. Edge detection
improvement by ant colony optimization. Pattern
Recognition Letters, Vol. 29(4), 416-425, 2008.
25
ACO - REFERÊNCIAS
Dorigo, Marco and Stützle, Thomas. (2004) Ant
Colony Optimization, Cambridge, MA: The
MIT Press.
 Dorigo, Marco, Gambardella, Luca M.,
Middendorf, Martin. (2002) “Guest Editorial”,
IEEE Transactions on Evolutionary
Computation, 6(4): 317-320.

26
ACO - DEMOS

Ants foraging for food


http://website.lineone.net/~john.montgomery/demos/a
nts.html
The Travelling Salesman ACO Applet

http://uk.geocities.com/markcsinclair/aco.html
27
PARTICLE SWARM
OPTIMIZATION (PSO)
28
PSO - “PENSAR É SOCIAL”
 Pensar
é uma atividade social
 A cultura (grupo) e a cognição (indivíduo)
fazem parte de um mesmo processo
 Indivíduos aprendem localmente através de
seus vizinhos, compartilhando conhecimento
 Uma sociedade é um sistema autoorganizável cujas propriedades não podem
ser preditas a partir de seus componentes
 A interação cultural (grupo) melhora a
29
capacidade cognitiva de um indivíduo
PSO - “PENSAR É SOCIAL”
 Segundo
o Modelo Cultural Adaptativo
(Robert Axelrod):


As pessoas se tornam mais similares à medida que
interagem entre si
As pessoas são atraídas por aquelas que
compartilham seus ideais
 Baseado
em três processos básicos:
Avaliar (classificar estímulos em positivos ou
negativos)
 Comparar (definição de um referencial)
30
 Imitar (forma efetiva encontrada na natureza de
aprendizado)

PSO - “PENSAR É SOCIAL”
 Simulações
do ACM podem encontrar
soluções para alguns problemas
combinatórios
 Porém este não é seu objetivo
 O modelo ACM é a base teórica da
Otimização por Enxame de Partículas
 O ACM explica o comportamento “imite o
melhor do grupo” da técnica PSO
 Outros modelos também são utilizados para
31
explicar o comportamento do PSO
PARTICLE SWARM OPTIMIZATION
 Técnica
de otimização global baseada em
uma população de soluções (como nos AEs)
 Criada por Kennedy e Eberhart em meados
da década de 90
 Técnica inspirada no comportamento social
de revoadas de pássaros
 Os resultados obtidos com a simulação das
revoadas originou o PSO
32
PARTICLE SWARM OPTIMIZATION
33
PARTICLE SWARM OPTIMIZATION
 Baseado
no modelo ACM (avaliar, comparar e
imitar)
 Uma população de soluções é mantida
 Cada indivíduo da população (partícula) é um
vetor de reais que corresponde a uma possível
solução
 Cada partícula possui uma posição e uma
velocidade no n
 O processo de atualização de uma partícula possui
dois componentes:
34


Melhor experiência (posição visitada) pessoal
Melhor experiência (posição visitada) do grupo
PARTICLE SWARM OPTIMIZATION
 xi(t):
vetor posição atual da partícula i
 vi(t): vetor velocidade atual da partícula i,
pode ser visto como um x. Está limitada por
[-vmax ,vmax]
 yi(t): vetor com a melhor posição visitada pela
partícula i
 ŷ(t): índice da melhor entre as melhores
posições visitadas pelo grupo
 A avaliação das posições de cada partícula é
feita pela função de desempenho (fitness) a 35
qual se deseja otimizar
PARTICLE SWARM OPTIMIZATION
 Expressão
de atualização do PSO:
x
(
t

1
)(

x
t
)

v
(
t

1
)
i
i
i
ˆ
v
(
t

1
)

w
.
v
(
t
)
c
r
(
y
(
t
)

x
(
tc
)
)

r
(
y
(
t
)

x
(
t
)
)
i
i
1
1
i
i
2
2
i
w é o peso de inércia (momento). Seu valor geralmente
decai linearmente de 0.9 a 0.4
 r1, r2 são ambas variáveis aleatórias retiradas de
U(0,1). Representam o componente estocástico do
algoritmo
 0 < c1, c2  2 são os coeficientes de aceleração pessoal e
global que influenciam no tamanho máximo do passo
que uma partícula pode dar em uma iteração 36

PARTICLE SWARM OPTIMIZATION
- Algoritmo:
inicializar população de partículas
repetir até critério de parada
para cada partícula i da população faça
se f (xi(t)) < f (yi(t)) então yi(t) = xi(t)
se f (yi(t)) < f (ŷ(t)) então ŷ(t) = yi(t)
fim-para
atualizar velocidade e posição de cada partícula
37
PARTICLE SWARM OPTIMIZATION

Movimentação das partículas
O vetor velocidade de cada partícula sofre a ação do ótimo
individual e do ótimo global (melhor experiência do
grupo)
 Geralmente as partículas ultrapassam o ponto de ótimo
atual a partir de várias direções explorando regiões
promissoras
 Todas as partículas possuem a chance de descobrir um
ótimo global e compartilhar com as demais

38
PARTICLE SWARM OPTIMIZATION

Movimentação das partículas
Os termos aleatórios inserem um caráter estocástico à
busca
 Os coeficientes c1 e c2 aceleram o deslocamento das
partículas
 O fator de inércia controla o grau de exploração da busca

Maior inércia = mais exploração
 Menor inércia = mais explotação

39
PARTICLE SWARM OPTIMIZATION
 Princípio





básicos da inteligência de enxames:
Proximidade: a população deve ser capaz de
executar computações simples
Qualidade: a população deve ser capaz de
responder a fatores de qualidade do ambiente
Resposta Diversificada: a população deve ser
capaz de manter sua diversidade
Estabilidade: a população deve se manter estável
a mudanças bruscas no ambiente
Adaptabilidade: a população deve ser capaz de40
responder a alterações no ambiente, sempre que
valer a pena
VARIAÇÕES DO PSO
 Tipo





de Vizinhança
Refere-se à topologia dos relacionamentos entre as
partículas
Determina quais partículas são influenciadas por
uma boa posição visitada
Mais usados são Lbest e Gbest
No Gbest todos se relacionam com todos. Uma boa
posição de uma partícula é compartilhada com todos.
No Lbest uma partícula se relaciona apenas com os
vizinhos (no espaço de índices). Uma boa posição de41
uma partícula é compartilhada apenas com os
vizinhos.
VARIAÇÕES DO PSO
 Tipo
de
Vizinhança
i-1
Gbest
i
i+1
Lbest
42
VARIAÇÕES DO PSO
•
PSO Binário
– Os vetores xi e yi são formados por 0s e 1s
– O vetor velocidade continua real, mas é tratado
como uma probabilidade
– Para isso é utilizada a função logística sigmoidal
– A expressão de atualização da velocidade é a
mesma
0 se r  sig (vi , j (t  1))
xi , j (t  1)  
1 se r  sig (vi , j (t  1))
43
VARIAÇÕES DO PSO




r é um valor aleatório retirado de U(0,1)
Para evitar a saturação da função é recomendado
limitar a velocidade em [-4, 4]
Resultados mostraram que o PSO Binário chega a
resultados mais rapidamente que AG e lida
melhor com alta dimensionalidade
Podem ainda ser usados valores discretos além de
0e1
44
VARIAÇÕES DO PSO
 Peso




Não era utilizado originalmente, mas se tornou
padrão
Possui semelhança com a temperatura do Simulated
Annealing
Controla o grau de convergência da busca
Pode ser fixo ou descrescente
 Uso


de Inércia (w)
de Seleção
Aplica o conceito de seleção natural dos AEs, porém
modificado
45
Diminui a diversidade se concentrando em regiões
mais promissoras
PSO - APLICAÇÕES
 Inicialmente
utilizado no treinamento de
redes neurais
 Cada elemento de um vetor xi corresponde a
um peso da rede
 De fato, a maioria das aplicações de PSO
envolvem redes neurais artificiais
 Uma abordagem é encontrar uma região
promissora para a inicialização de um
método local
 Outra é a otimização do número de unidades
46
nas camadas escondidas
PSO - APLICAÇÕES
O
PSO Binário é geralmente utilizado para a
otimização de arquiteturas de Redes Neurais
 PSO Padrão + Binário pode ser usado para
otimizar variáveis contínuas e binárias ao mesmo
tempo
 PSO para treinar redes neuro-fuzzy (97% de
precisão no Iris Dataset)
 Otimização de misturas de ingredientes químicos
 Em geral, PSO pode ser utilizado em qualquer47
problema de otimização: contínua, binária ou
PSO - APLICAÇÕES
 Outros
exemplos:
Controle adaptativo baseado em Redes Neurais
 Configuração de antenas
 Aprendizado não-supervisionado de robôs
 PSO em ambientes dinâmicos

48
PSO - APLICAÇÕES
PSO
AG
Representação
Contínua/Binária/Discreta
Contínua/Binária/Discreta
Otimização
Contínua/Binária/Combinatória* Contínua/Binária/Combinatória
Populacional
Sim
Sim
Geracional
Não
Sim
Restrições
Não, mas pode ter
Sim
Seleção, Mutação e
Operadores
Velocidade
Recombinação
Implementação
Simples
Complexidade média
Convergência
Relativamente Rápida*
Relativamente Lenta*
49
PSO - CONCLUSÕES
PSO em geral obtém resultados semelhantes aos
obtidos por Algoritmos Genéticos
 Porém são mais rápidos (resultados relatados)
 PSO é muito mais simples de implementar
 Pode convergir prematuramente a um mínimo local,
para evitá-lo pode-se:
 Utilizar peso de inércia (w) descrescente (0.9 a 0.4)
 Utilizar arquitetura Lbest
 O enxame pode “explodir” (dispersão das partículas)
 Para evitá-lo, deve-se limitar a velocidade a [-vmax,
50
vmax]

PSO - CONCLUSÕES

Tendências
Coevolução em PSO
 Otimização multi-objetivo
 Life Models (PSO com seleção, cruzamento e
mutação)
 Partículas com tamanho variável


DEMO

http://uk.geocities.com/markcsinclair/pso.html
51
PSO - REFERÊNCIAS





J. Kennedy and R. Eberhart. Swarm Intelligence. Morgan
Kaufmann Publishers, Inc, San Francisco, CA, 2001
F. van den Bergh. “An Analysis of Particle Swarm Optimizers”.
Phd dissertation, Faculty of Natural and Agricultural Sciences,
Univ. Pretoria, Pretoria, South Africa, 2002.
J. Kennedy and R. Eberhart. Particle Swarm Optimization, in:
Proc. IEEE Int’l. Conf. on Neural Networks (Perth, Australia),
IEEE Service Center,Piscataway, NJ, IV:1942-1948.
C.A. Coello Coello, G. Toscano, M.S. Lechuga. Handling
Multiple Objectives with Particle Swarm Optimization. IEEE
Transactions on Evol. Computation, Vol. 8, No. 3, June 2004.
M. Settles, T. Soule. Breeding Swarms: A GA/PSO Hybrid. 52
Proc. of GECCO'05, Washington DC, USA, 2005.