UNIVERSIDADE FEDERAL DO TRINGULO MINEIRO

PROGRAMA DE MESTRADO PROFISSIONAL EM INOVAO TECNOLGICA

PESQUISA INTRODUTRIA PARA A DISCIPLINA DE REDES NEURAIS E

ALGORITMOS GENTICOS

UBERABA/2015

UNIVERSIDADE FEDERAL DO TRINGULO MINEIRO

MODELOS BIOLOGICAMENTE INSPIRADOS POR COLNIA DE

FORMIGAS

PABLO SAMPAIO GOMES NATIVIDADE

UBERABA

2015

UNIVERSIDADE FEDERAL DO TRINGULO MINEIRO

MODELOS BIOLOGICAMENTE INSPIRADOS POR

COLNIA DE FORMIGAS

Pesquia introdutria apresentada por Pablo Sampaio

Gomes Natividade, Universidade Federal do

Tringulo Mineiro referente ao modelo

biologicamente inspirado em colnia de formigas,

como um dos requisitos para a concluso da

disciplina Redes Neurais e Algoritmos Genticos,

cursada no Programa de Mestrado Profissional em

Inovao Tecnolgica PMPIT.

Professor:

Prof.Dr. DAVID CALHAU JORGE

LISTA DE FIGURAS

Figura 01 Algoritmos inspirados em colnia de formigas ..................................... 07 Figura 02 Experimento realizado por Goss, Aron, Deneubourg e Pasteels ........... 08 Figura 03 Grfico obtido por Goss, Aron, Deneubourg e Pasteels ........................ 08 Figura 04 Alterao dos caminhos at a fonte de alimento .................................... 10 Figura 05 Aumento da complexidade do caminho colnia - alimentos ................. 10 Figura 06 Comportamento das formigas aps a insero de um obstculo............ 11 Figura 07 Experimento Ant System ........................................................................ 12 Figura 08 Algoritmo AS aplicado ao PCV .............................................................. 15 Figura 09 Meta-heurstica em pseudocdigo.......................................................... 17 Figura 10 Gerao e atividade das formigas - pseudocdigo ................................. 18

SUMRIO

1. INTRODUO ....................................................................................................... 6

2. DESENVOLVIMENTO.................. ........................................................................ 7

2.1. A INSPIRAO BIOLGICA .............................................................................. 7

2.2. ANT SYSTEM E O PROBLEMA DO CAIXEIRO VIAJANTE ............................ 11

2.3. OTIMIZAO POR COLNIA DE FORMGAS ................................................. 15

3. REFERNCIAS ...................................................................................................... 18

1. INTRODUO

Os modelos computacionais bioinspirados foram de suma importncia para a soluo

de diversos problemas clssicos e para desenvolvimento e aperfeioamento de inmeras

tecnologias. A computao bioinspirada procura estudar fenmenos recorrentes na

natureza de modo a compreender seus padres para uma posterior aplicao, muitas vezes

sendo implantados em algoritmos.

Atravs da bioinspirao foi possvel, por exemplo: Projetar avies, fundamentados

nos pssaros, desenvolver o velcro observando-se alguns tipos de plantas, a inveno do

sonar baseado em morcegos, o desenvolvimento de submarino atravs do comportamento

dos peixes, dentre outros. Nesse contexto, o presente trabalho exibe uma pesquisa

introdutria sobre um dos modelos biologicamente inspirados: A colnia de formigas.

Indivduos reais dessa espcie conseguem encontrar o caminho mais curto at a fonte de

alimento, praticamente sem o uso de recursos visuais, o tratamento dessa observao

possibilitou o desenvolvimento de mtodos de resoluo e otimizao em diversas reas,

como o problema do caixeiro viajante, possibilitando o melhor caminho para roteamento

de cabos em uma rede de comunicaes (COPPIN, 2013), a melhor rota de trfego

rodovirio usado por empresa de transportes. A inspirao biolgica aqui uma meta-

heurstica baseada em uma populao de formigas.

Meta-heurstica definida como conjunto de conceitos algortmicos e de estruturas de

dados genricos para desenvolvimento e aplicaes de algoritmos heursticos resoluo

satisfatria de problemas NP-difceis (DORIGO & STUTZLE, 2004). Esses algoritmos

no garantem a melhor soluo, todavia eles tm conseguido solues com boa

regularidade e um aceitvel tempo computacional.

Fundamentado nesse modelo foram desenvolvidos diversos algoritmos aplicados em

reas distintas (Figura 01), este trabalho discute apenas os dois modelos mais difundidos:

O AS (Ant System) e o ACO (Otimizao por colnia de formigas).

7

Figura 01 Algoritmos inspirados em colnia de formigas

2 DESENVOLVIMENTO

2.1 A INSPIRAO BIOLGICA - EXPERIMENTOS COM FORMIGAS REAIS

Em 1989 Goss, Aron, Deneubourg e Pasteels realizaram a experincia com formigas

reais que posteriormente serviria como fundamento para a criao de importantes modelos

bioinspirado no comportamento de formigas. Realizada com uma colnia da espcie

Iridomyrmex humilis, a experincia consistiu basicamente aproxim-la de uma fonte de

alimentos que s poderia ser obtido por dois caminhos distintos, mas de mesma distncia.

Transcorrido algum tempo, percebeu-se que a maioria das formigas escolhia o mesmo

caminho. A explicao para tal fenmeno est na deposio de feromnio deixado pelos

insetos. As formigas so praticamente cegas, assim atravs do olfato elas escolhem o

caminho com maior deposio da substncia em consequncia da maior circulao das

8

mesmas. A trilha de feromnio auxilia a formiga a encontrar tanto a fonte de alimento

quanto o caminho de regresso para a colnia.

A princpio no existe deposio de feromnio em ambos os caminhos, por

consequncia o trajeto escolhido se d de forma aleatria. Como ambos os caminhos tm a

mesma distncia, o trajeto que apresentar uma quantidade um pouco maior de feromnio

depositado acaba estimulando as demais formigas a segui-lo.

Figura 02 Experimento realizado por Goss, Aron, Deneubourg e Pasteels Fonte: (www.inf.ufpr.br/aurora/disciplinas/topicosia2/swarm.ppt)

A figura 03 resume de modo mais claro o que ocorreu nesse experimento. Esse grfico

exibe a quantidade de formigas em cada um dos caminhos a cada trs minutos

transcorridos.

Figura 03 Grfico obtido por Goss, Aron, Deneubourg e Pasteels Fonte: (http://isites.harvard.edu/fs/docs/icb.topic1514669.files/papers/deneu1989.pdf)

Percebe-se claramente uma preferncia por determinado caminho transcorridos apenas

5 minutos do incio do experimento. Aps 30 minutos aproximadamente 90% das formigas

trafega pelo mesmo caminho. Matematicamente, depois da travessia de i formigas por um

9

caminho com i unidades de feromnio temos Ai como formigas no caminho A e Bi no

caminho B, ou seja, Ai e Bi so simplesmente a quantidade de feromnio depositado em

cada caminho. A prxima formiga que chega escolhe entre os caminhos A ou B usando

probabilidades probA e probB dependendo de Ai e Bi. Aps a escolha, a formiga adiciona

feromnio ao caminho escolhido. Assim:

Onde a varivel que recebe 0 ou 1 com as probabilidades probA e probB

respectivamente. Em outras palavras A incrementado toda vez que uma formiga escolhe

o caminho A, caso contrrio B incrementado.

A equao (1) enuncia a forma com que a maior concentrao no caminho A oferece

uma probabilidade maior de escolha deste mesmo caminho, dependendo dos valores

absolutos e relativos de Ai e Bi. O parmetro n determina o grau de no linearidade da

escolha. Um valor alto de n significa que se um caminho tiver uma leve quantidade de

feromnio acima do outro, a prxima formiga que passar ter uma probabilidade alta de

escolh-lo. A varivel k representa a atratividade de um ramo sem feromnio(GOSS et al.,

1990).

Alterando o experimento, agora usando distncias diferentes, percebeu-se que a

quantidade de formigas oriundas do caminho mais curto era maior que a taxa de formigas

vindas do caminho mais longo. Desse modo, quando o inseto inicia o retorno para o ninho

ele sente uma quantidade de feromnio mais intensa depositada no caminho mais curto,

esse padro seguido pelas demais at que a grande maioria de formigas prevalea no

menor caminho.

10

Figura 04 Alterao dos caminhos at a fonte de alimento Fonte: (www.inf.ufpr.br/aurora/disciplinas/topicosia2/swarm.ppt)

Com o aumento da complexidade do problema, transcorrido algum tempo, nota-se o

mesmo padro, ou seja, as formigas escolhem o trajeto mais curto.

Figura 05 Aumento da complexidade do caminho colnia - alimentos Fonte: (www.inf.ufpr.br/aurora/disciplinas/topicosia2/swarm.ppt)

Esse comportamento coletivo que se observa denominado comportamento

autocataltico, quanto maior a quantidade de formigas que segue um caminho, mais

atrativo ele se torna. A probabilidade que uma formiga tem de escolher determinado

caminho aumenta com a quantidade de formigas que o escolheram anteriormente.

Outros experimentos nesse sentido foram realizados, por exemplo, definindo a

colnia de formigas como ponto A e a fonte de alimentos como ponto E, aps o perodo

transitrio insere-se um obstculo entre esses pontos. Inicialmente a probabilidade de

11

tomada de deciso para alterao da rota a mesma para todas as formigas, medida que

os traos de feromnio so alterados a probabilidade inicial tambm se altera. O padro de

comportamento se repete novamente, aps outro perodo transitrio gerado pela insero

do obstculo, a grande maioria das formigas volta trafegar pelo caminho mais curto.

Figura 06 Comportamento das formigas aps a insero de um obstculo Fonte: (www.cin.ufpe.br/~lma3/sih2010/aula-07-sih-10-aco-pso.ppt)

Aps a inspirao biolgica do comportamento das formigas, importantes

algoritmos foram criados atravs do uso de formigas artificiais como heursticas

construtivas.

O termo heurstico vem do grego heuriskein = descobrir, sendo um procedimento

algortmico desenvolvido atravs de um modelo cognitivo, usualmente atravs de

regras baseadas na experincia dos desenvolvedores.

2.2 ANT SYSTEM E O PROBLEMA DO CAIXEIRO VIAJANTE

Proposto por Marco Dorigo e colaboradores (DORIGO et al., 1996), o Ant System

foi o primeiro algoritmo desenvolvido baseado no comportamento da colnia de formigas

j descrito. O objetivo no era simular as colnias e formigas e sim us-las artificialmente

como uma ferramenta de otimizao.

A figura 07 mostra que a distncia entre D e H, B e H e entre B e D via C so

iguais a 1 e que C est posicionado na metade entre D e B. Considere ainda que o tempo

discreto com intervalos simtricos, ou seja, t = 0, 1, 2.

12

Figura 07 Experimento Ant System Fonte: (www.cin.ufpe.br/~lma3/sih2010/aula-07-sih-10-aco-pso.ppt)

Suponha que 30 formigas esto indo em direo a B e D partindo de A e E e que

caminham a velocidade 1 por unidade por tempo, liberando feromnio no tempo t com

intensidade 1. O feromnio evapora completamente e instantaneamente no meio do

intervalo de tempo sucessivo (t+1, t+2). 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.

Percebe-se que o tempo discreto, ao contrrio do que acontece com as formigas

reais. Essas formigas artificiais no so cegas e, alm do uso do feromnio j depositado

na construo da soluo, podem ser orientadas pela informao heurstica do caminho.

Ainda so dotadas de memria pois elas lembram os pontos por onde passaram no

retornando a eles at que tenham chegado fonte de alimento. O algoritmo proposto por

essa metodologia dotado de trs funes:

ConstruirSoluesComFormigas( );

AplicarBuscaTotal( );

AtualizarFeromonio( ).

O objetivo dessa meta-heurstica gerenciar o escalonamento dessas trs funes. As

trs atividades no tm uma forma rgida de como isso se d, ou seja, podem ser

13

executadas em paralelo e independentes, inclusive com sincronismo (DORIGO et al.,

1999).

MetaHeuristicaAS()

1 IncioDoAlgoritmo;

2 Inicializar parmetros;

3 Inicializar trilhas de feromnio;

4 While (no alcanou a condio de parada) do

5 ConstruirSoluesComFormigas();

6 AplicarBuscaLocal(); //Opcional

7 Atualizar Feromnio();

8 FimWhile;

9 FimDoAlgoritmo.

O problema do caixeiro viajante (PCV) um caso aplicado em inteligncia artificial e

NP-Completo, significando que para grandes instncias do problema pode ser muito difcil

um programa computacional resolv-lo em tempo razovel (COPPIN, 2013). Um

caixeiro viajante deve visitar cada uma das cidades de um conjunto de cidades e retornar

cidade de partida. O objetivo do problema encontrar o caminho mais curto que permita

que ele visite cada uma das cidades.

Usando a heurstica Ant System, inicialmente m formigas so distribudas nas cidades

de acordo com um critrio qualquer definido previamente, todos os caminhos (i,j) E so

iniciados com a mesma quantidade ij(1) > 0 de feromnio. A seguir cada formiga k (k =

1,2,...m) seleciona as prximas cidades a serem visitadas, atravs da regra de deciso

probabilstica:

(6)

Onde:

pkij(t): probabilidade da cidade j ser escolhida pela formiga k, atualmente situada na

cidade i, durante a t-sima iterao da heurstica AS;

14

ij(t): intensidade do feromnio presente no caminho (i,j) E na t-sima iterao de

AS;

: parmetro que regula a influncia de ij(t);

ij =1/dij : visibilidade da cidade j com relao a cidade i, sendo dij a distncia entre

a cidade i e j.

: parmetro que regula a influncia de ij;

Nki(t): conjunto de cidades ainda no visitadas pela formiga k na cidade i durante a

t-sima iterao de AS.

O processo que seleciona a prxima cidade a ser visitada repetido at que todas as

formigas tenham completado um caminho interligando todas as cidades uma nica vez.

Aps isso o processo de depsito e evaporao feromnio ocorre como estabelecido a

seguir:

(7)

(8)

(9)

Sendo (8) se a formiga k percorreu o caminho (i,j) E, caso contrrio (9).

Onde:

t: iterao atual da heurstica AS;

p [0,1]: parmetro que regula a reduo de ij(t);

ij (t): ganho total do feromnio no caminho (i,j) E, ocorrido na t-sima

iterao;

m: nmero de formigas;

kij(t): ganho de feromnio no caminho (i,j) E, causado pela formiga k, na t-

sima iterao de AS.

Q: quantidade de feromnio excretada por uma formiga a cada iterao;

Sk (t):caminho completo que interliga todas as cidades uma nica vez descoberto

pela formiga k na t-sima iterao de AS.

15

Lk (t):distncia associada ao caminho completo Sk (t) descoberto pela formiga k na

t-sima iterao de AS.

Os procedimentos se repetem a cada iterao da heurstica AS. Todavia, quando o

nmero mximo de iteraes j estabelecidas alcanado, a heurstica Ant System retorna a

melhor soluo at ento encontrada. A figura 08 traz o algoritmo Ant System (AS)

aplicado ao problema do caixeiro viajante.

Figura 08 Algoritmo AS aplicado ao PCV

Fonte: (SILVA, Ricardo.M.A)

2.3 OTIMIZAO POR COLNIA DE FORMIGAS

A Otimizao por Colnia de Formigas ACO (Dorigo & Caro, 1999) uma meta

heurstica bio-inspirada que surgiu a partir do Ant System. Esse algoritmo pode ser

utilizado para a busca de caminhos com curto mnimo em um grafo G = (C, L, W), desde

que esses caminhos estejam conforme as restries (C, L, ) definidas a seguir:

16

C = {c1, c2, c3,..., cNc}, conjunto finito de Nc componentes do problema, como por exemplo,

as cidades usadas no exemplo do caixeiro viajante.

L = {lcicj | ci , cj C} o conjunto de possveis arestas entre os elementos de C.

W: o conjunto de pesos associados, ou a C, ou a L ou a ambos.

(C, L, ) o conjunto finito de restries atribudas aos elementos C e L, com

indicandoquais mudanas de restrio ocorrem ao longo do tempo.

Os estados do problema so definidos como sequncias s = , com ai=ck

C, k = 1, ..., Nc;

Se c1 for o ltimo componente do estado s1, um estado s2, dito vizinho de s1, se c2 |

C(lc1c2 L) ^ (s2=, pode mover-se para qualquer n j, contanto

que pertena vizinhana Ni do n i em que se encontra.

d) Uma formiga k localizada sobre o n i seleciona o n j Nki segundo uma regra de

deciso probabilstica.

e) Pode-se atribuir um estado inicial Sks a uma formiga k, assim como uma ou mais

condies ek de parada.

f) As formigas partem de seus respectivos estados iniciais a um estado vizinho vivel.

17

g) A medida que se move do n i para o vizinho j, a formiga atualiza a trilha de

feromnio. (Atualizao de feromnio)

h) Encontrada a soluo, a formiga pode, ao retornar pelo caminho inverso ao

percorrido, atualizar a trilha de feromnio. (Atualizao de feromnio com atraso)

A Figura 09 descreve o pseudocdigo da meta-heurstica de otimizao por colnia de

formigas proposta por Dorigo e Caro (1999). J a Figura 10 exibe a rotina executada toda

vez que a funo gerao_e_atividade_das_formigas() chamada.

Figura 09 Meta-heurstica em pseudocdigo Fonte: (SILVA, Ricardo.M.A)

18

Figura 10 Gerao e atividade das formigas - pseudocdigo Fonte: (SILVA, Ricardo.M.A)

3. REFERNCIAS

REZENDE, Leandro. Planejamento da Expanso de Sistemas de Transmisso Atravs

da Otimizao por Colnia de Formigas. Itajub, 2006. Disponvel em:

Acesso em 21 de Junho de 2015.

SILVA, Ricardo. Otimizao Baseada em Colnia de Formigas Aplicada ao Problema

da Cobertura de Conjuntos. Recife, 2003. Disponvel em:

Acesso em 21 de Junho de 2015.

COPPIN, Ben. Inteligncia artificial. Rio de Janeiro: LTC, 2010.

DORIGO, Marco; STUTZLE, Thomas. Ant Colony Optimization. Massachussets, 2004.

DORIGO, Marco; CARO, Gianni. The Ant Colony Optimization Meta-Heuristic.

Bruxelas, 1999.

19

ARON S., DENEUBOURG JL, GOSS S. & PASTEELS JM. How Argentine ants

establish a minimal-spanning tree to link different nests. In Social Insects and the

Environment, Eds. G.K. Veeresh, B. Mallik & C.A. Viraktamath. Oxford & IBH, New

Delhi, 533-534. Disponvel em: <

http://www.ulb.ac.be/sciences/use/publications/JLD/67.pdf> Acesso em 21 de Junho de

2015.

ARON S., PASTEELS JM, GOSS S & DENEUBOURG JL. Self-organising spatial

patterns in the Argentine ant Iridomyrmex humilis (Mayr). In: Applied Myrmecology:

A World Perspective, Eds R.K. Vander Meer, K. Jaffe & R. Cedeno, Westview Press,

Boulder (Co), 438-451. Disponvel em: <

http://www.ulb.ac.be/sciences/use/publications/JLD/69.pdf> Acesso em 21 de Junho de

2015.

DENEUBOURG JL, S. ARON S, GOSS S & PASTEELS JM. The self-organizing

exploratory pattern of the argentine ant. Journal of Insect Behavior, 3, 159-168.

Disponvel em: < http://www.ulb.ac.be/sciences/use/publications/JLD/76.pdf> Acesso em

21 de Junho de 2015.