Modelagem do Comportamento de Colônias de Formigas e Sua ... · das colônias para continuarem alimentando seus ninhos de modo eﬁciente. Neste trabalho é ... ao longo do tempo

Universidade Federal de Pernambuco

Centro de Informática

Programa de Pós-graduação em Ciência da Computação

ELTON BERNARDO BANDEIRA DEMELO

Modelagem do comportamento de

colônias de formigas em ambientes

dinâmicos e sua aplicação a

sistemas de roteamento de pacotes

Recife, Agosto de 2009.

ELTON BERNARDO BANDEIRA DEMELO

Modelagem do comportamento de

colônias de formigas em ambientes

dinâmicos e sua aplicação a

sistemas de roteamento de pacotes

Dissertação submetida ao Programa de

Pós-Graduação em Ciência da Compu-tação Universidade Federal de Pernam-

buco como parte dos requisitos paraobtenção do grau de Mestre em Ciência

da Computação

Orientador: Prof. Aluízio Fausto Ribeiro Araújo, PhD.

Recife, Agosto de 2009.

©Elton Bernardo Bandeira de Melo, 2009

Melo, Elton Bernardo Bandeira de Modelagem do comportamento de colônias de formigas em ambientes dinâmicos e sua aplicação em sistemas de roteamento de pacotes / Elton Bernardo Bandeira de Melo. - Recife: O Autor, 2009. 151 folhas : il., fig., tab.

Dissertação (mestrado) – Universidade Federal de Pernambuco. CIn. Ciência da Computação, 2009.

Inclui bibliografia, anexos e apêndice.

1. Modelagem e Simulação Computacional. 2.Otimização. 3. Inteligência Artificial. I. Título.

003.3 CDD (22. ed.) MEI2009 - 155

Agradecimentos

A Lívia e às minhas irmãs Elga e Emily pelo suporte emocional indispensável e porque

as amo. A André Leite Wanderley pelo suporte intelectual, companheirismo e generosidadecom que me ajudou e estimulou no decorrer deste mestrado. A Hélio Burle de Menezes, que

me incentivou e permitiu que eu me lançasse nesta jornada. A Antônio Carlos Batista deLima e todos os meus colegas da Companhia Hidro Elétrica do São Francisco (CHESF), pela

tolerância e flexibilidade que demonstraram enquanto tive que conciliar trabalho e estudo.Ao Professor Aluízio, pela orientação paciente, honesta e laboriosa. À Professora Judith

Kelner e ao colega Orivaldo Júnior, pela ajuda na etapa final deste trabalho. Aos meus bonsprofessores, em especial a Alfredo Arnóbio de Souza da Gama e Fernando Menezes Campello

de Souza, pela formação. Ao meu pai Eliécio e à minha avó Lêda, aos meus amigos, à minhafamília e à família Coêlho, por todas as contribuições indiretas.

Universidade Federal de Pernambuco

28 de Agosto de 2009

E. B. B. M.

Resumo da Dissertação apresentada à ufpe como parte dos requisitos necessários para aobtenção do grau de Mestre em Ciência da Computação

MODELAGEM DO COMPORTAMENTO DE COLÔNIAS

DE FORMIGAS EM AMBIENTES DINÂMICOS E SUA

APLICAÇÃO A SISTEMAS DE ROTEAMENTO DE

PACOTES

Elton Bernardo Bandeira de Melo

Agosto/2009

Orientador: Prof. Aluízio Fausto Ribeiro Araújo, PhD.

Área de Concentração: Inteligência ArtificialPalavras-chaves: Inteligência de enxames, algoritmos de roteamento, ACO.

Número de páginas: 151

Apresenta-se a modelagem do comportamento de formigas forrageiras em ambientes dinâ-

micos a partir de experimentos realizados com formigas reais em laboratório, em um aparato

experimental composto por uma rede de túneis colocado entre o ninho das formigas a fonte

de alimento. Durante os experimentos, há mudanças na topologia da área de forrageio, com

a introdução e remoção de bloqueios de alguns túneis, o que exige a capacidade de adaptação

das colônias para continuarem alimentando seus ninhos de modo eficiente. Neste trabalho é

proposto um novo modelo para o comportamento das formigas, o Modelo FFAC-D (Formi-

gas Forrageiras em Ambientes Confinados e Dinâmicos) é inspirado em evidências extraídas

de estudos biológicos e mostra-se capaz de reproduzir os dados experimentais, superando o

problema da estagnação evidenciado em modelos anteriores. Na segunda etapa desta disser-

tação, busca-se aplicar os mecanismos bem sucedidos do Modelo FFAC-D ao problema do

roteamento em redes de pacotes. É feita uma revisão da literatura sobre algoritmos de rotea-

mento baseados em formigas, e, em seguida, propõe-se um novo sistema para o roteamento

de pacotes baseado no Modelo FFAC-D, o MARS (Memoryless Ants Routing System). O MARS

é implementado em um simulador de eventos discretos voltado à simulação de redes (NS-2),

e mostra-se eficaz para a solução do problema de roteamento, com desempenho superior ao

AntNet no que diz respeito aos tempos de convergência e ao consumo de largura de banda

(overhead). O MARS aponta ainda vatagens sobre outros algoritmos existentes relacionadas à

segurança, resiliência e qualidade de serviço (QoS).

Abstract of Dissertation presented to ufpe as a partial fulfillment of the requirements for thedegree of Master in Computer Science

MODELLING ANT COLONY BEHAVIOR IN A

DYNAMIC ENVIRONMENT AND ITS APPLICATIONS

TO PACKET ROUTING SYSTEMS

Elton Bernardo Bandeira de Melo

August/2009

Supervisor: Prof. Aluízio Fausto Ribeiro Araújo, PhD.

Area of Concentration: Artificial IntelligenceKeywords: Swarm intelligence, routing algorithms, ACO.

Number of pages: 151

The modeling of the behavior of a colony of foraging ants in a dynamic environment pre-

sented in this dissertation is based on experiments with the Argentine ant Linepithema humile

under laboratory condition, using an experimental device similar to a network, consisting

of tunnels and bifurcations, which is placed between the colony’s nest and the food source.

During the experiments, the topology of the foraging environment changes, by means of of

insertion and removal of blockages in the tunnels. This dynamics requires the ants to adapt

themselves in order to keep feeding the nest efficiently. In this dissertation, a new model for ant

colony behavior is proposed, the FFAC-D (Formigas Forrageiras em Ambiente Confinado e Dinâ-

mico is founded on evidences derived from biological studies and reproduces the experimental

data, overcoming the stagnation problem observed in previous models. In the second half

of this dissertation, we aim at applying the mechanisms of the FFACD Model to the packet

routing problem. A review of the literature about ant based routing algorithms is presented,

and, afterwards, we propose a new packet routing system based on the FFACD, the MARS

(Memoryless Ants Routing System). The MARS is implemented in a discrete event simulator,

the Network Simulator version 2 (NS-2), and shows a superior performance when compared

to the AntNet, with respect to the convergence time and overhead (bandwidth consumption).

Additionally, the MARS indicates advantages in simplicity, security and Quality of Service

(QoS), over existing algorithms.

LISTA DE FIGURAS

2.1 Dispositivo experimental . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.2 Velocidade média (e erro padrão) de sete colônias no sentido ninho-alimento

sob acesso a todos os ramos [1]. . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.3 Distribuição do número de contatos (e erro padrão) das formigas sob acesso a

todos os ramos [1]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.4 Duração do contato (e erro padrão) entre as formigas de sete colônias sob

acesso a todos os ramos [1]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

2.5 Freqüências de escolha das colônias pelos diferentes caminhos do ambiente,sob acesso a todos os ramos, em ambas as direções (0-60 min) [1]. . . . . . . . 28

2.6 Distribuição do número médio de formigas (± desvio padrão) sob acesso atodos os ramos (0-60 min) [1]. . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

2.7 Freqüências de escolha das colônias pelos diferentes caminhos do ambiente nosentido ninho-alimento sob bloqueio do acesso a um ramo após 30min (0-30

min e 30-60 min) [1]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

2.8 Distribuição das escolhas das colônias no sentido alimento-ninho sob bloqueiodo acesso a um ramo após 30 min (0-30 min e 30-60 min) [1]. . . . . . . . . . . 30

2.9 Distribuição do número médio de formigas (± desvio padrão) sob bloqueio doacesso a um ramo após 30 min (0-60 min) [1]. . . . . . . . . . . . . . . . . . . 31

2.10 Distribuição das escolhas das colônias nos dois sentidos de seu movimento sobdesbloqueio de vários ramos após 30 min (30-60min) [1]. . . . . . . . . . . . . 32

2.11 Distribuição do número médio de formigas (± desvio padrão) sob desbloqueio

do acesso a vários ramos após 30 min (0-60 min) [1]. . . . . . . . . . . . . . . 33

2.12 Distribuição média do número de formigas (± desvio-padrão) sobre o ambiente

ao longo do tempo sob acesso a todos os ramos. A linha pontilhada representaa média de 200 simulações, e o desvio-padrão é representado por linhas con-

tínuas. A linha contínua representa a média obtida em 10 experimentos e odesvio-padrão é representado por linhas pontilhadas [1]. . . . . . . . . . . . . 40

2.13 Freqüências de escolha dos caminhos nas simulações, usando o critério Me-tropolis, e nos experimentos, quando o acesso a todos os ramos foi permitido

durante 60 min (a) no sentido ninho-alimento e (b) no sentido alimento-ninho.Foram considerados os resultados de 10 experimentos 500 simulações. . . . . . 41

2.14 Freqüências de escolha dos caminhos nas simulações, usando o modelo FFAC, enos experimentos, quando o acesso a um ramo foi impedido após 30min (a) no

sentido ninho-alimento e (b) no sentido alimento-ninho. Foram considerados10 experimentos e 500 simulações [1] . . . . . . . . . . . . . . . . . . . . . . . 42

2.15 Freqüências de escolha dos caminhos nas simulações, usando o modelo FFAC, enos experimentos, quando o acesso a um ramo foi impedido após 30 min (a) no

sentido ninho-alimento e (b) no sentido alimento-ninho. Foram considerados10 experimentos e 500 simulações [1] . . . . . . . . . . . . . . . . . . . . . . . 43

2.16 Freqüências de escolha dos caminhos quando o acesso a um ramo foi impedidoapós 30min, no sentido ninho-alimento (a) nos experimentos e (b) nas simula-

ções do modelo, usando o modelo FFAC. Foram considerados 10 experimentose 500 simulações [1] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

2.17 Freqüências de escolha dos caminhos nas simulações, usando o modelo FFAC,e nos experimentos, sob desbloqueio de vários ramos após 30 min (a) no sen-

tido ninho-alimento e (b) no sentido alimento-ninho. Foram considerados osresultados de 10 experimentos 500 simulações (30-60 min) [1]. . . . . . . . . . 45

2.18 Freqüências de escolha dos caminhos sob o desbloqueio de vários ramos após

30 min, no sentido ninho-alimento (a) nos experimentos e (b) nas simulaçõesdo modelo, usando do modelo FFAC. Foram considerados os resultados de 10

experimentos 500 simulações (30-45 min e 45-60 min) [1]. . . . . . . . . . . . . 46

2.19 Freqüências de escolha dos caminhos sob o desbloqueio de vários ramos após

30 min, no sentido alimento-ninho (a) nos experimentos e (b) nas simulaçõesdo modelo, usando o do modelo FFAC. Foram considerados os resultados de

10 experimentos 500 simulações (30-45 min e 45-60 min) [1]. . . . . . . . . . . 46

3.1 Função da concentração de feromônio para valores diferentes de β. . . . . . . 62

4.1 Freqüência de escolha de caminhos nos modelo FFAC e FFAC-D e nos expe-rimentos, na Situação 1, nas direções (a) ninho-fonte de alimento e (b) fonte

de alimento-ninho. Para Modelo FFAC-D, há valores para os passos de tempo1000, 1800, 2700 e 3600. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

4.2 Freqüência de escolha de caminhos nos modelo FFAC e FFAC-D e nos experi-mentos, na Situação 2, nas direções (a) ninho – fonte de alimento e (b) fonte de

alimento – ninho. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

4.3 Freqüências de escolhas do Modelo FACC, FFAC-D e nos experimentos, nasituação 3, na direção (a) ninho-alimento, e, (b) alimento-ninho. . . . . . . . . 83

6.1 Representação de uma formiga no MARS. . . . . . . . . . . . . . . . . . . . . 105

6.2 Estrutura de nó considerada no MARS, neste caso com três portas. . . . . . . 106

6.3 Topologia de rede em anel, gerada a partir do NS-2/NAM para simulações doMARS. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

6.4 Topologia de rede em árvore, gerada a partir do NS-2/NAM para simulaçõesdo MARS. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

6

6.5 Topologia de rede em cubo, gerada a partir do NS-2/NAM para simulações doMARS. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116

6.6 Tabela de feromônio do nó 0. Média de 10 simulações da rede com topologiaem anel, para os destinos: a)1, b)2, c)3, d)4 e e)5, computadas em diversos

instantes de tempo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

6.7 Tabelas de feromônio dos nós 0 e 1. Média de 10 simulações da topologia em

árvore, a partir do nó 0 para os destinos: a)1 e b)3, e a partir do nó 1 para osdestinos: c)0, d)2, e)3 e f)6, computadas em diversos instantes de tempo. . . . . 118

6.8 Tabela de feromônio do nó 0. Média de 10 simulações da rede em cubo, apartir do nó 0 para os destinos: a)1, b)2, c)3, d)4, e)5, f)6 e g)7, computadas em

diversos instantes de tempo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119

6.9 Desvio padrão do percentual de feromônio presente na tabela do 0, para 10

simulações da rede em anel, computados em diversos instantes de tempo. . . . 120

6.10 Comparação entre o número médio de pacotes emitidos pelos algoritmos Ant-

Net e Mars. Média de dez simulações com a rede em anel. . . . . . . . . . . . 120

6.11 Média de 10 simulações da rede em anel, do percentual de feromônio do nó 1

com destino nó 5: a)MARS com interrupção no enlace 0−5 em 5 s, e; b)AntNetcom interrupção no enlace 0− 5 em 10 s. . . . . . . . . . . . . . . . . . . . . . 121

LISTA DE TABELAS

2.1 Comprimentos dos caminhos do dispositivo experimental. . . . . . . . . . . . 23

2.2 Tabela de parâmetros do modelo original . . . . . . . . . . . . . . . . . . . . . 39

4.1 Tabela de Parâmetros do FFAC-D . . . . . . . . . . . . . . . . . . . . . . . . . 79

5.1 Algoritmos baseados em formigas para redes ad hoc. . . . . . . . . . . . . . . . 101

6.1 Tabela de Roteamento Probabilística. . . . . . . . . . . . . . . . . . . . . . . . 107

6.2 Tabela de Roteamento Determinística. . . . . . . . . . . . . . . . . . . . . . . 108

6.3 Tabela de Feromônio. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

6.4 Tabela de Formigas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109

.1 ANTRALs e suas características . . . . . . . . . . . . . . . . . . . . . . . . . . 139

SUMÁRIO

1 INTRODUÇÃO 121.1 Modelagem do Comportamento de Formigas . . . . . . . . . . . . . . . . . . . . 13

1.2 Inteligência Computacional Baseada no Comportamento de Formigas . . . . . 16

1.3 Objetivos e Escopo da Pesquisa . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

1.3.1 Modelagem do Comportamento de Formigas . . . . . . . . . . . . . . . 17

1.3.2 Desenvolvimento de um ANTRAL baseado na Modelagem do Compor-tamento de Formigas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

1.4 Organização da Dissertação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2 ESTUDO EXPERIMENTAL E MODELAGEM PRÉVIA DO COMPORTAMENTO DAS FOR-MIGAS 202.1 Estudo Experimental com Formigas Forrageiras em um Ambiente Confinadoe Dinâmico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.1.1 Construção dos Experimentos . . . . . . . . . . . . . . . . . . . . . . . 21

2.1.2 Resultados Experimentais - O Comportamento Individual . . . . . . . . 24

2.1.3 Resultados Experimentais - Comportamento Coletivo . . . . . . . . . . 27

2.2 Modelagem do Comportamento das Formigas em um Ambiente Confinado . . 32

2.2.1 Recrutamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

2.2.2 Deslocamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

2.2.3 Tempo Despendido na Fonte . . . . . . . . . . . . . . . . . . . . . . . . 35

2.2.4 Retardo em Bloqueio de Caminho . . . . . . . . . . . . . . . . . . . . . 35

2.2.5 Depósito de Feromônio . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

2.2.6 Seleção de Caminhos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

2.2.7 Resultados do Modelo FFAC . . . . . . . . . . . . . . . . . . . . . . . . 39

2.2.8 Discussão acerca do Modelo FFAC . . . . . . . . . . . . . . . . . . . . . 45

3 REVISÃO BIBLIOGRÁFICA SOBRE O COMPORTAMENTO DOS INSETOS SOCIAIS 493.1 Auto-organização e Adaptação . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

3.2 Mecanismos de Navegação e Exploração do Habitat . . . . . . . . . . . . . . . . 52

3.2.1 Exploração de “Novidades” . . . . . . . . . . . . . . . . . . . . . . . . 53

3.2.2 Familiarização com o Ambiente . . . . . . . . . . . . . . . . . . . . . . 54

3.2.3 Navegação de Insetos no Deserto . . . . . . . . . . . . . . . . . . . . . . 54

3.3 Comunicação dos Insetos Sociais . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

3.3.1 Comunicação Multimodal . . . . . . . . . . . . . . . . . . . . . . . . . 59

3.4 Depósito e Percepção de Feromônios . . . . . . . . . . . . . . . . . . . . . . . . . 60

3.4.1 Depósito de Feromônio . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

3.4.2 Evaporação das Trilhas de Feromônio . . . . . . . . . . . . . . . . . . . 65

3.4.3 Feromônio “Não Entre” . . . . . . . . . . . . . . . . . . . . . . . . . . 67

3.5 Controle de Tráfego . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

3.6 Discussão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

4 MODELAGEM DO COMPORTAMENTO DAS FORMIGAS EM AMBIENTES CONFINADOSE DINÂMICOS 724.1 Depósito e Percepção de Feromônio . . . . . . . . . . . . . . . . . . . . . . . . . 73

4.1.1 Evaporação de Feromônio . . . . . . . . . . . . . . . . . . . . . . . . . 73

4.1.2 Mecanismo Exploratório . . . . . . . . . . . . . . . . . . . . . . . . . . 74

4.1.3 Parâmetros do Modelo FFAC-D . . . . . . . . . . . . . . . . . . . . . . 77

4.1.4 Pseudo-código do Modelo FFAC-D . . . . . . . . . . . . . . . . . . . . . 79

4.2 Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

4.2.1 Resultados do Modelo FFAC-D para a Primeira Situação Experimental . 81

4.2.2 Resultados do Modelo FFAC-D para a Segunda Situação Experimental 81

4.2.3 Resultados do Modelo FFAC-D para a Terceira Situação Experimental . 82

4.3 Discussão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

5 REVISÃO BIBLIOGRÁFICA SOBRE ALGORITMOS DE ROTEAMENTO BASEADOS EM FOR-MIGAS 865.1 O ACO e os ANTRALs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

5.1.1 Pseudo-código geral do ACO . . . . . . . . . . . . . . . . . . . . . . . . 89

5.1.2 O Problema de Roteamento e os ANTRALs . . . . . . . . . . . . . . . . 89

5.2 O ABC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92

5.3 O AntNet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

5.4 Principais características do AntNet . . . . . . . . . . . . . . . . . . . . . . . . . 94

5.4.1 O emprego do conhecimento global no AntNet . . . . . . . . . . . . . . 97

5.4.2 Pseudo-Código do AntNet . . . . . . . . . . . . . . . . . . . . . . . . . 98

5.5 Outros ANTRALs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98

5.5.1 Algoritmos para MANETs . . . . . . . . . . . . . . . . . . . . . . . . . 100

5.6 Discussão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

6 MARS - SISTEMA DE ROTEAMENTO BASEADO EM FORMIGAS SEM MEMÓRIA 1036.1 Modelo da Rede . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1056.2 Estruturas Internas de Dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1076.3 Características do Algoritmo MARS . . . . . . . . . . . . . . . . . . . . . . . . . 109

6.3.1 Pseudo-código do MARS . . . . . . . . . . . . . . . . . . . . . . . . . . 111

6.4 Simulações e Resultados do MARS . . . . . . . . . . . . . . . . . . . . . . . . . . 1126.4.1 O Simulador - NS-2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

10

6.4.2 Topologias Usadas nas Simulações . . . . . . . . . . . . . . . . . . . . . 114

6.4.3 Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116

6.4.4 Parâmetros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120

6.5 Discussão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121

7 CONCLUSÕES E TRABALHOS FUTUROS 1247.1 Sugestões para Estudos Futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125

Referências 127

Apêndice I – Tabela de ANTRALs 137

Capítulo I

IntroduçãoThe sciences do not try to explain, they hardly

even try to interpret, they mainly make models.

By a model is meant a mathematical construct

which, with the addition of certain verbal inter-

pretations describes observed phenomena. The

justification of such a mathematical construct is

solely and precisely that it is expected to work."

— John von Neumann

A partir da interação de indivíduos cujos comportamentos são relativamente simples,

as colônias de insetos sociais solucionam problemas inerentes à sua sobrevivência e

fazem emergir padrões complexos [2]. Esta capacidade, aprimorada pelo processo de seleção

natural, instiga pesquisas que vão desde a busca por uma melhor compreensão dos meca-

nismos biológicos envolvidos, até o desenvolvimento de novas tecnologias inspiradas nestes

mecanismos. Esta dissertação aborda estas duas linhas de pesquisa:

1. A modelagem do comportamento das colônias de formigas em sua busca por alimen-

tos. Nesta etapa, busca-se, a partir de observações experimentais, modelar as leis natu-

rais por meio da classificação e reconhecimento de padrões, da generalização e abstra-

ção das relações causais percebidas no fenômeno sob observação. Aplica-se o método

científico [3], onde é possível, a partir de deduções, hipóteses e refutações baseadas em

evidências, a construção de modelos cada vez mais representativos dos fenômenos natu-

rais;

2. A aplicação do modelo obtido ao problema de roteamento de pacotes. Esta etapa

aborda o desenvolvimento de uma tecnologia inspirada em analogias com situações ob-

———— Introdução————

servadas e modeladas. Afinal, pode-se observar na natureza um alto grau de ordena-

mento, parcimônia e eficácia, características desejadas em nossas soluções e que estão

presentes ao nosso redor, por exemplo, nas formas de estruturas cristalinas, colméias de

abelhas, bolhas de sabão, planetas, animais e plantas, bem como na dinâmica de fenôme-

nos tais como os de cristalização, reprodução, evolução e aprendizado [4]. Há evidências

desta mesma parcimônia e eficácia no comportamento das colônias de formigas [2].

Quer para busca de uma melhor modelagem do universo, quer para o desenvolvimento

de novas tecnologias, investigam-se os processos naturais, sobretudo dos sistemas biológicos,

no intuito de absorver a essência de algumas das estratégias sobreviventes ao tempo e ao

processo de seleção natural. Uma vez que se mostram mais bem adaptados ao ambiente, é

de se esperar que possuam componentes ótimos ou sub-ótimos, é de se esperar que sejam

fontes de inspiração. Seguindo este raciocínio, duas linhas de pesquisa têm se intensificado

nos últimos anos [1, 2]:

• A primeira na área da Etologia, no estudo e modelagem do comportamento das colônias

de insetos sociais, sobretudo das formigas, onde é possível observar padrões complexos

emergirem a partir da interação de indivíduos relativamente simples;

• A segunda na área da Inteligência Computacional, onde diversos métodos baseados em

sistemas biológicos têm se desenvolvido para a resolução de problemas complexos. Alguns

exemplos são as Redes Neurais Artificiais, a Computação Genética e Evolucionária e a Inte-

ligência de Enxames, sendo que esta última inclui algoritmos inspirados no comportamento

das formigas [2, 5].

1.1 Modelagem do Comportamento de Formigas

O comportamento dos insetos sociais tem atraído diversos pesquisadores nos últimos

anos, não só da biologia, mas também da Física, Matemática e Ciência da Computação.

Isso se deve ao fato de que as colônias de insetos são capazes de solucionar problemas com-

plexos por meio da interação de indivíduos relativamente simples, de forma descentralizada,

sem a necessidade de um controlador [6].

Os insetos sociais conseguem atingir coletivamente padrões complexos de comportamento

devido à combinação de dois processos: auto-organização e comunicação indireta. O primeiro

deles é um conceito que foi inicialmente introduzido nas áreas de Física e Química para des-

13

———— Elton Bernardo Bandeira de Melo————

crever como processos microscópicos originavam estruturas macroscópicas em sistemas fora

de seu estado de equilíbrio [7, 8]. Em um processo de auto-organização, a formação de pa-

drões ocorre pela interação entre elementos internos do sistema, utilizando informação local,

sem intervenção externa. No que diz respeito à comunicação, as formigas utilizam a estig-

mergia, i.e., uma comunicação indireta em que os indivíduos se comunicam através de marcas

deixadas no ambiente para estimularem algum tipo de comportamento em outros agentes que

entrem em contato com elas. No caso das formigas estas marcas consistem de trilhas de uma

substância volátil chamada de feromônio. As formigas que percebem trilhas destes feromô-

nios apresentam tendência de segui-las (ou evitá-las, a depender do tipo de feromônio [9]),

depositando mais feromônio que estimulará outras formigas a fazerem o mesmo, levando a

um processo de auto-organização [2, 5].

As colônias de formigas desenvolveram em sua evolução processos razoavelmente comple-

xos para a busca e exploração de novas fontes de alimentos, defesa das colônias e controle de

tráfego, dentre outras situações que requerem uma postura estratégica para que seja garantida

a sobrevivência da colônia [2].

Na busca por modelos que capturem os princípios e as estratégias adotadas pelas colônias

de formigas, são necessários experimentos cautelosos, com medições precisas e construtos

matemáticos que, levando em consideração a plausibilidade biológica, aproxime cada vez

mais as simulações das observações experimentais. A plausibilidade biológica fornece algumas

premissas para a construção dos modelos:

• Não existe um mecanismo decisor externo às formigas;

• Todas as formigas tomam decisões apenas com base em seus critérios e percepções indivi-

duais do ambiente;

• Todas as percepções sensoriais das formigas estão limitadas às suas capacidades físicas;

• O ambiente no qual as formigas estão inseridas é isento e inanimado, apenas obedece às leis

naturais;

No tocante às características sensoriais das formigas, bem como no que diz respeito às

suas capacidades de comunicação, algumas hipóteses estão bem evidenciadas, estudadas e

estabelecidas na literatura. As formigas possuem um campo de visão limitado e podem se

comunicar por diversos modos, como por exemplo, através de sinais acústicos, tais como

estalidos, estridulações e batidas no chão, ou mesmo através do contato entre os indivíduos

14


[10]. As formigas forrageiras, ao longo dos caminhos percorridos na busca de alimento, são

capazes de depositarem e perceberem trilhas de um composto químico volátil chamado de

feromônio. Graças a este comportamento, de marcar, seguir e reforçar trilhas de feromônio

desde o ninho até as fontes de alimento, a colônia é levada à auto-organização.

Quando as formigas escolhem um caminho longo até o alimento, levam mais tempo em

suas viagens de ida e volta, o feromônio depositado evapora mais e as trilhas tendem a ser me-

nos intensas em relação àquelas de caminhos curtos. Este efeito diferencial do comprimento

dos caminhos, juntamente com a tendência das formigas de seguirem as trilhas de feromônios

mais intensas, levam as colônias a uma auto-catálise, o que explica como as formigas encon-

tram os menores caminhos até o alimento, mesmo sem fazer uso de informações globais sobre

o ambiente de forrageio [2].

No que diz respeito ao comportamento das colônias de formigas na busca e exploração de

fontes de alimentos (forrageio), algumas observações verificadas em experimentos estão bem

estabelecidas e compõem o arcabouço inicial da modelagem[11]:

• As formigas são capazes de trazer alimento das fontes para o ninho;

• As formigas são capazes de explorarem o ambiente para a descoberta de novas fontes ou

novos caminhos até as fontes conhecidas;

• As formigas desejam acumular alimento em seus ninhos;

• As formigas aplicam o princípio do menor gasto de energia possível, sempre que percebem

oportunidade de aplicá-lo;

Poucos experimentos foram realizados com formigas em ambientes similares a grafos,

compostos de vários nós conectados por ramos e bifurcações. Alguns trabalhos têm se base-

ado em experimentos com formigas em ambientes confinados, porém não utilizam mais que

uma ou duas bifurcações [12–14]. Assim, buscando suprir esta deficiência, experimentos re-

alizados no CRCA 1 e reportados por Vittori et al.[1, 15, 16], mostram o comportamento de

formigas argentinas Linepithema humile em um ambiente confinado e relativamente complexo,

onde uma rede composta por vários túneis e bifurcações interconectados é colocada entre o

ninho das formigas e a fonte de alimentos, permitindo que as formigas tenham catorze op-

ções de caminhos diferentes, com diferentes comprimentos. O comportamento das formigas

foi observado levando-se em consideração os componentes individual e coletivo, de modo a

1Centre de Recherches sur la Cognition Animale – CRCA, ligado à Universidade Paul Sabatier, Toulouse, França.

15


permitir a modelagem de sua dinâmica. Três situações experimentais foram analisadas:

• Na primeira, as formigas têm livre acesso a todos os ramos durante todo o tempo do expe-

rimento;

• Na segunda, um dos ramos que compõem os caminhos mais curtos é bloqueado e o com-

portamento das formigas é observado sobretudo no que diz respeito à capacidade coletiva

de perceber o bloqueio e buscar novos caminhos;

• A terceira situação experimental é caracterizada pelo desbloqueio de um ramo que dá acesso

aos menores caminhos, depois de decorrido algum tempo. Agora, analisa-se a capacidade

das formigas de perceberem a nova opção, mesmo depois de terem estabelecido caminhos

preferenciais.

A modelagem do comportamento das formigas a partir dos experimentos citados acima

pode revelar importantes componentes comportamentais das formigas forrageiras, sobretudo

em relação às reações das formigas devido às modificações nos seus ambientes de forrage-

amento. O aparato experimental utilizado, permite analogia com um grafo bidirecional.

Assim, portanto, um algoritmo para o comportamento das formigas que reproduza o com-

portamento observado durante os experimentos pode revelar mecanismos da inteligência das

colônias aplicáveis a problemas de otimização envolvendo grafos.

Baseado nos experimentos citados acima, Vittori et al. [15] propõem um Modelo para

o comportamento das formigas neste ambiente confinado e dinâmico. Tal modelo considera

componentes individuais e coletivos do comportamento das formigas e, em simulações, repro-

duz satisfatoriamente o comportamento observado na primeira situação experimental, com o

ambiente de forrageio estático. Este mesmo modelo, no entanto, mostra-se incapaz de repro-

duzir o comportamento observado na segunda e terceira situação, quando há mudanças no

ambiente de forrageio, quais sejam, bloqueios e desbloqueios de ramos.

1.2 Inteligência Computacional Baseada no Comportamento de For-

migas

Um Algoritmo de Formiga pode ser informalmente definido como um sistema multi-agente

inspirado no comportamento de colônias de formigas [2]. Nos Algoritmos de Formigas, os

agentes são chamados de formigas artificiais ou simplesmente de formigas, e a coordenação

entre estes agentes é obtida pela exploração de mecanismos de comunicação estigmérgica.

16


Uma categoria particular dos Algoritmos de Formigas se inspira no comportamento du-

rante o forrageio: como as formigas se auto-organizam para buscarem alimento para a colônia

[2, 5, 17]. A maioria destes algoritmos tem sido aplicada na resolução de problemas de oti-

mização combinatória envolvendo grafos [17]. Tais grafos são tomados como análogos às

redes compostas pelo ninho das colônias, pelas fontes de alimento espalhadas no ambiente

de forrageio e pelos caminhos escolhidos pelas formigas para buscarem os alimentos [18].

Estes algoritmos baseiam-se no efeito diferencial do comprimento dos caminhos, conforme

descrito na seção anterior, e na autocatálise trazida com ele.

O AS (Ant System) [19] foi o primeiro algoritmo inspirado no comportamento de forma-

ção e seguimento de trilhas de feromônios, aplicado a um problema de otimização discreta,

o Problema do Caixeiro Viajante. O AS mostrou bons resultados quando comparado com

outras meta-heurísticas, tais como recozimento simulado, computação evolucionária ou pes-

quisa tabu [19]. A partir do AS surgiu um conjunto de aplicações bem sucedidas e de extensões

desta meta-heurística nomeada Ant Colony Optimization (ACO), que aplica a inteligência ob-

servada nas colônias de formigas aos problemas de otimização [2, 5, 11, 17].

Dentre as diversas aplicações do ACO, destaca-se uma classe particular de problemas de

otimização combinatória dinâmica, o problema do roteamento, i.e. a busca dos melhores

caminhos em uma rede de comunicação para a troca de mensagens entre seus nós. Os algo-

ritmos que aplicam a meta-heurística ACO para o problema de roteamento de pacotes são

chamados de Ant Routing Algorithms ou simplesmente ANTRALs [20].

Um ANTRAL é um algoritmo de roteamento baseado na comunicação estigmérgica ob-

servada nas colônias de insetos. Os agentes móveis (formigas) movem-se em uma rede e são

responsáveis por atualizarem, assíncrona e independentemente, as tabelas de rotas presentes

em cada nó roteador [20]. Diversos ANTRALs foram propostos nos últimos dez anos e suas

simulações indicam o desempenho superior destes ANTRALs quando comparados com ou-

tros algoritmos de roteamento usados mais comumente, como os baseados nos algoritmos de

Dijkstra (Link State – LS) e de Bellman-Ford (Distance Vector – DV) [11, 17, 20–22].

1.3 Objetivos e Escopo da Pesquisa

1.3.1 Modelagem do Comportamento de Formigas

A primeira parte desta pesquisa tem como principal objetivo a proposição de um modelo

capaz de reproduzir o comportamento das formigas observado nas três situações experimen-

17


tais reportadas por Vittori et al. [16]. Para tal, os modelos anteriormente propostos foram

implementados, tornando possível a análise dos problemas que impediram a reprodução dos

dados experimentais. Em seguida, foi necessário buscar soluções para os problemas identifi-

cados. Devido à preocupação com a preservação da plausibilidade biológica dos mecanismos

introduzidos no novo modelo, foi realizada uma revisão da literatura científica sobre o com-

portamento dos insetos. Buscou-se evidências de características das formigas, que pudessem

compor um modelo capaz de reproduzir os dados experimentais.

Esta etapa da pesquisa culminou na proposição de um Modelo para o Comportamento de

Formigas Forrageiras em Ambientes Confinados e Dinâmicos (FFAC-D), que foi bem sucedido

na reprodução do comportamento observado nos experimentos realizados por Vittori et al.[1].

O resultado desta etapa da pesquisa foi publicado inicialmente na GECCO’O8 (Genetic and

Evolutionary Computation Conference - 2008) [23]. O fato de o FFAC-D ter sido projetado tendo

em vista a preservação da plausibilidade biológica e dos requisitos da meta-heurística ACO,

possibilitou o desenvolvimento da segunda etapa desta pesquisa.

1.3.2 Desenvolvimento de um ANTRAL baseado na Modelagem do Comportamento

de Formigas

Na segunda parte da pesquisa, buscou-se aplicar os principais mecanismos do algoritmo

FFAC-D, que reproduziu bem o comportamento das formigas observados nos experimentos,

no desenvolvimento de um ANTRAL. Espera-se que, por ser baseado em experimentos com

formigas em um ambiente similar a uma rede de comunicação dinâmica e relativamente com-

plexa, o novo ANTRAL possa apresentar características e atrativos ímpares, sobretudo no

que diz respeito à sua capacidade de adaptação em casos de contingências nos enlaces da

rede.

Após revisão bibliográfica sobre os ANTRALs, visando mapear as iniciativas já reporta-

das e entender as principais demandas nesta área, propõe-se um ANTRAL que preserve as

características principais do FFAC-D, prezando pela simplicidade e atentando aos principais

requisitos a um algoritmo deste tipo. Assim, o MARS (Memoryless Ants Routing Systems) foi

proposto e implementado no simulador NS-2 (Network Simulator versão 2). Este algoritmo

tem como principal característica a simplicidade e o tamanho reduzido das formigas, que im-

plica uma menor ocupação dos recursos da rede (menor overhead) e a adaptabilidade, ou seja,

menor tempo de convergência. Os primeiros resultados apontam desempenho superior ao do

18


AntNet, um notável ANTRAL que por sua vez apresenta desempenho superior aos algoritmos

de roteamento tradicionais (Distance Vector e Link State), e que tem servido de referência nesta

área.

1.4 Organização da Dissertação

O restante da dissertação está dividido de modo que, no Capítulo 2 são apresentados o es-

tudo experimental e a modelagem do comportamento das formigas desenvolvidos por Vittori

et al. [1], e que serve como base para o desenvolvimento desta pesquisa. No Capítulo 3, novas

evidências extraídas da literatura sobre o comportamento das formigas são levantadas, com

o intuito de inspirar o desenvolvimento de um novo modelo, capaz de superar os problemas

apresentados pelo modelo proposto por Vittori et al. [1] e reproduzir o comportamento ob-

servado nos experimentos com o ambiente dinâmico. No Capítulo 4 é apresentado o FFAC-D

(Modelo de Formigas Forrageiras em Ambientes Confinados e Dinâmicos), bem como seus

resultados e conclusões. No Capítulo 5, é apresentado o problema do roteamento de paco-

tes e destacados os principais ANTRALs. No capítulo 6 é apresentado o MARS (Memoryless

Agents Routing System), um novo algoritmo de roteamento de pacotes inspirado no Modelo de

Formigas Forrageiras em Ambiente Confinado e Dinâmico, bem como seus resultados. Por

fim, no capítulo 7, as conclusões da pesquisa e as sugestões para estudos futuros são lançadas.

19

Capítulo II

Estudo Experimental eModelagem Prévia do

Comportamento das FormigasWonderful theory, wrong species.

— E. O. Wilson sobre o marxismo, que ele

considerava mais adequado para formigas.

Pesquisas recentes nas áreas da Etologia, Sociobiologia, Ecologia e Fisiologia dos Insetos

têm revelado muitos detalhes sobre o comportamento de formigas e outros insetos so-

ciais. A partir destes estudos é possível perceber o nível de sofisticação destes seres, conhecer

seus modos de comunicação, suas capacidades sensoriais e nuances de seu comportamento

individual e coletivo. Chama atenção o fato de indivíduos relativamente simples desenvolve-

rem uma capacidade de organização tal que faz emergir padrões complexos em suas colônias,

adaptando-se a ambientes selvagens, muitas vezes hostis, e garantindo sua perpetuação. Ade-

mais, a organização observada nas colônias de insetos sociais ocorre sem observador ou con-

trolador externo, dá-se através da superposição de comportamentos individuais com acesso

apenas a informações locais. Trata-se pois de auto-organização.

Dentre as facetas do comportamento dos insetos sociais que mais despertam curiosidade

na comunidade científica, está o forrageio das formigas, ou seja, a estratégia de busca de ali-

mentos para as colônias. Hoje, é sabido que as formigas forrageiras, através da comunicação

estigmérgica baseada no depósito e seguimento de trilhas de feromônios, são capazes de es-

colher os melhores caminhos entre o ninho e a fonte de alimentos. No entanto, muitos dos

detalhes envolvidos nestas estratégias de forrageio ainda são desconhecidos.

———— Estudo Experimental e Modelagem Prévia do Comportamento das Formigas————

Para que se estenda a base de conhecimentos científicos sobre os comportamentos destes

insetos, hão de ser feitas observações experimentais, e, a partir destas, a construção de mo-

delos capazes de reproduzir as observações disponíveis e permitir novas hipóteses e previsões.

Na Seção 2.1, é abordado um estudo experimental bastante inovador, desenvolvido por Vit-

tori et al. [15] com formigas forrageiras em um ambiente complexo, confinado e sujeito a

modificações em sua topologia. Este estudo foi desenvolvido com o intuito de captar nuances

do comportamento das formigas que podem ser aplicadas ao problema de roteamento. Em

seguida, na Seção 2.2, é apresentada a modelagem proposta por Vittori [1] para o comporta-

mento das formigas observado nos experimentos. Os resultados deste modelo são discutidos

na Seção 2.3. Cabe ressaltar que os experimentos e a modelagem descritos neste capítulo

servem como base para o restante desta pesquisa, sobretudo no tocante aos Capítulos 3 e 4.

2.1 Estudo Experimental com Formigas Forrageiras em um Ambi-

ente Confinado e Dinâmico

Os experimentos com formigas argentinas realizados e reportados por Vittori et al. [16],

consistiram em observações das atividades de forrageio das formigas, quando seus ninhos

eram conectados a uma rede de túneis interligados por bifurcações e conectados à fonte de

alimento.

O comportamento das formigas foi analisado sob dois diferentes enfoques: (i) no nível

coletivo, foi verificado como as colônias escolheram um caminho para atingir o alimento e

retornar ao ninho, e foi analisado o comprimento dos caminhos percorridos bem como as

freqüências destas escolhas; (ii) no nível individual, quantificou-se variáveis comportamentais

das formigas, tais como velocidade de deslocamento, número de contatos entre os insetos,

duração destes contatos, tempo de permanência sobre a fonte de alimento e incidência de

meia-volta 1 em um cada percurso.

2.1.1 Construção dos Experimentos

As formigas argentinas (pertencentes à espécie Linepithema humile2) utilizadas nos experi-

mentos foram coletadas em Sept, cidade litorânea da França, e agrupadas em dez colônias,

1 Meia-volta se caracteriza como a mudança de direção do movimento de uma formiga sobre um ramo do ambiente, que

resulta na desistência de um ramo que havia sido selecionado.2Anteriormente chamada de Iridomyrmex humilis.

21


contendo cada uma 2.000 indivíduos aproximadamente, formados somente por trabalhado-

res, sem a presença de larvas e rainha. As formigas argentinas foram escolhidas devido ao

grande número de indivíduos presentes em suas colônias, à facilidade de sua obtenção na na-

tureza e de manutenção em laboratório, e ainda pela existência de diversos estudos sobre o

comportamento desta espécie na literatura.

Durante os experimentos, as formigas eram primeiramente submetidas a um período de

jejum, e depois introduzidas em um dispositivo constituído por uma rede de túneis composta

por quatro hexágonos, conectados de um lado ao ninho das formigas, e de outro à fonte

de alimentos, conforme a Figura 2.1 [15]. Este dispositivo foi desenvolvido com o intuito

de produzir um ambiente relativamente complexo. Esta complexidade se caracteriza pelos

possíveis caminhos de comprimentos diferentes que podem ser escolhidos pelas formigas para

irem do ninho à fonte de alimentos e vice-versa. As fontes de alimentos foram colocadas nas

áreas circulares A ou B em cada experimento, para que fosse analisado o efeito da simetria.

2 cmNinho AB0

4

1

7

10

8

5

2

3a

6a

3b

9

11

13

16

6,5 cm

Figura 2.1: Dispositivo experimental

Para cada hexágono presente no dispositivo, os ângulos internos formados pela junção de

dois ramos são iguais a 60o. Por exemplo, no hexágono formado pelos ramos 1, 4, 7 e 10, os

ângulos entre os ramos 1 e 4 e entre 7 e 10 são iguais a 60o.

As formigas podem fazer o trajeto entre o ninho e a fonte de alimento através de quatorze

caminhos diferentes, os quais foram classificados em quatro categorias, de acordo com seu

comprimento, conforme a Tabela 2.1.

22


Tabela 2.1: Comprimentos dos caminhos do dispositivo experimental.

Identificador Caminho (fonte A) Comprimento

1 1-2-3a-13 curto - 21,5cm

2 1-10-8-9-6a-16

3 4-7-8-11-3a-13

4 4-5-9-11-3a-13 médio - 30,5cm

5 4-7-10-2-3a-13

6 4-5-6a-6b-3b-13

7 4-7-8-9-6a-6b-3b-13

8 1-10-8-9-6a-6b-3b-13

9 1-2-11-9-6a-6b-3b-13 longo - 39,5cm

10 1-10-7-5-6a-6b-3b-13

11 1-10-7-5-9-11-3a-13

12 4-5-9-8-10-2-3a-13 muito longo - 43,5cm

13 4-7-10-2-11-9-6a-6b-3b-13 muito longo - 48,5cm

14 1-2-11-8-7-5-6a-6b-3b-13 muito longo - 52,5cm

Pode-se observar que existem diversas rotas de mesmo comprimento, o que aumenta a

gama de possibilidades de escolhas das formigas. Por um lado a topologia do aparato expe-

rimental se aproxima das galerias subterrâneas observadas em algumas espécies de formigas

[24, 25] ou mesmo de redes de trilhas para o forrageio construídas sobre o solo [26]. Por outro

lado, esta topologia apresenta analogia com uma rede de computadores. Como o dispositivo

experimental é simétrico, as rotas que conduzem a cada uma das fontes de alimento também o

são, possuindo o mesmo comprimento. É importante mencionar que o meio é simétrico com

relação às duas fontes de alimento consideradas, contudo, considerando cada uma das fontes,

as rotas que conduzem as formigas do ninho ao alimento e vice-versa são assimétricas. Os ca-

minhos pertencentes às quatro classes consideradas foram denominados em ordem crescente:

curtos, médios, longos e muito longos. Três situações experimentais foram tratadas:

• As formigas tiveram livre acesso a todos os ramos do dispositivo durante 60 minutos;

• As formigas tiveram livre acesso a todos os ramos do dispositivo por 30 minutos, então o

acesso ao ramo que conduz ao alimento (3a ou 6a, de acordo com a posição da fonte de

alimento) foi bloqueado e o comportamento das formigas observado por mais 30 minutos;

• Durante 30 minutos as formigas tiveram acesso somente a um caminho longo para atin-

gir a fonte de alimento, sendo o caminho 1-10-7-5-9-11-3a-13 para o caso do alimento estar

presente na área A, ou 4-7-10-2-11-9-6a-16, quando este se encontrar na área B. Após 30 mi-

23


nutos, foi permitido o acesso a todos os ramos e o comportamento das formigas observado

por mais 30 minutos.

Esta série de experimentos objetivou verificar o comportamento das colônias de formigas

sob mudanças na topologia do ambiente de forrageio, de modo a permitir uma boa analogia

com as redes de roteamento de pacotes. Desta forma, na primeira situação experimental, a

escolha das formigas esteve relacionada somente com o comprimento dos caminhos dispo-

níveis. O segundo tipo de experimentos considerou o bloqueio de um dado ramo do meio,

de forma a simular uma situação de falha em um enlace de uma rede de comunicações. A

escolha do ramo a ser bloqueado foi feita considerando o grande fluxo de formigas, devido à

proximidade da fonte de alimento e fazer parte das rotas mais curtas do ambiente. A terceira

série de experimentos, por sua vez, buscou reproduzir a situação em que somente um caminho

longo se encontra disponível, e que após um período de tempo, torna-se possível o acesso a

novas rotas, mais curtas.

O comportamento das formigas foi analisado sob dois diferentes aspectos: (i) no nível

individual, onde foram observados em cada inseto aspectos supostamente independentes do

comportamento de seus pares, e; (ii) no nível coletivo, onde se acredita que as decisões de

cada formiga dependem das decisões prévias das outras formigas dentro da colônia.

2.1.2 Resultados Experimentais - O Comportamento Individual

O comportamento individual das formigas foi observado com relação (i) à velocidade de

movimento sobre o meio; (ii) ao número de contatos entre as formigas; (iii) à duração destes

contatos; (iv) ao tempo despendido em torno do alimento e (v) ao número de meia-voltas re-

alizadas sobre um ramo. Todos estes dados foram obtidos considerando a primeira situação

experimental, onde o ambiente não foi modificado, pois o intuito da análise do comporta-

mento individual das formigas foi quantificar suas características sob situações em que as

condições do meio não fossem alteradas. Além disto, a medição destas variáveis poderia ge-

rar imprecisões, se consideradas as mudanças realizadas no ambiente, devido ao acúmulo de

formigas sobre determinados ramos do meio.

A primeira medição realizada compreendeu a velocidade média de sete das dez colônias,

conforme a Figura 2.2. Isto foi obtido através da medição do tempo despendido pelas vinte

primeiras formigas, em média, para percorrer um dado caminho no sentido da fonte de ali-

mento. Os valores encontrados foram distribuídos em nove categorias de velocidade, compre-

24


Figura 2.2: Velocidade média (e erro padrão) de sete colônias no sentido ninho-alimento sob acesso a todos os

ramos [1].

endendo as medidas de 143 formigas. Verificou-se que a maior parte das formigas analisadas

encontrou-se na faixa de 0,9 a 1,1 cm/s, e que a velocidade média de todos os insetos consi-

derados foi igual a 1,10 cm/s. O desvio-padrão apresentado foi igual a 0,48 cm/s, um valor

elevado.

Figura 2.3: Distribuição do número de contatos (e erro padrão) das formigas sob acesso a todos os ramos [1].

A velocidade das formigas sobre o meio está inversamente relacionada com o número de

25


contatos físicos que elas realizam com suas companheiras ao longo de seu deslocamento, que

constitui a segunda característica analisada. Dentre as 143 formigas consideradas, em 105

delas foi observado o número de contatos com uma companheira do ninho em seu trajeto

sobre o meio, conforme ilustrado na Figura 2.3.

Figura 2.4: Duração do contato (e erro padrão) entre as formigas de sete colônias sob acesso a todos os ramos [1].

Também foram medidas as durações dos contatos entre os indivíduos de uma dada colônia

2.4. Observou-se que a maioria dos indivíduos realiza um contato físico com um companheiro

durante 24 a 32 centésimos de segundo. O valor médio obtido pela colônia foi 24,32 centé-

simos de segundo, com um desvio-padrão de 15,60 centésimos de segundo. O contato entre

as formigas de uma colônia pode definir a continuidade de seu movimento ou a mudança de

direção do mesmo.

A maior parte das formigas permaneceu sobre a fonte de alimento entre 0 e 50 s. O

valor médio obtido nas medições foi 185,28 s, e o desvio-padrão foi elevado, igual a 168,39 s.

Apesar da maioria dos insetos ter permanecido junto à fonte no intervalo de 0-50 s, o pequeno

número de indivíduos que esteve por um período maior de tempo sobre a área do alimento,

acima de 300 s, produziu um valor médio alto. Este aspecto do comportamento das formigas

está relacionado com o tamanho da fonte e do espaço reservado a ela.

Ao se deslocarem sobre o meio, algumas formigas modificaram a direção de seu percurso

ao longo de um ramo em determinados instantes de tempo, realizando um movimento de

meia-volta, como verificado anteriormente por outros pesquisadores [27]. Em cada intervalo

26


de tempo, um dado número de formigas foi analisado. No total, investigou-se o comporta-

mento de um número N = 149 formigas. Na maior parte dos 13 instantes de tempo considera-

dos, de 5% a 15% dos insetos avaliados modificaram a direção do seu movimento após terem

percorrido uma dada distância do ramo em que se encontravam. A taxa média de meias-voltas

realizadas pelos insetos foi igual a 16,28%, com um desvio-padrão igual a 9,74%.

No retorno ao ninho, o comportamento das formigas com respeito à meia-volta foi ana-

lisado novamente durante 13 intervalos de tempo, totalizando 156 formigas. Na maioria das

ocasiões, o índice de meia-volta se encontrou entre 0% e 10% dos movimentos das formigas.

A incidência desta ação ocorreu em média em 5, 32% dos deslocamentos realizados por estes

insetos após a ingestão do alimento. O desvio-padrão produzido foi igual a 6, 44%. Observou-

se que a taxa média de mudanças na direção do movimento das formigas na volta ao ninho

foi bastante inferior à obtida no sentido inverso.

O objetivo do presente trabalho é compor um bom modelo para o comportamento das

formigas, para que, a partir daí, seja feito uma proposta de adaptação ao problema de rote-

amento. Assim, o interesse nos dados dos comportamentos individuais são, prioritariamente,

para captação de aspectos qualitativos, e para a aferição do modelo, permitindo o confronto

dos aspectos quantitativos do comportamento coletivo verificado nos experimentos com as

simulações do modelo.

2.1.3 Resultados Experimentais - Comportamento Coletivo

As observações feitas em laboratório diante de cada uma das três situações experimentais

consideradas, são descritas a seguir:

Situação 1 – Ambiente Estático - Acesso a Todos os Ramos

Na primeira situação experimental, quando as formigas puderam escolher os seus cami-

nhos tendo acesso a todos os ramos, ao partirem do ninho em direção ao alimento, oito das

dez colônias utilizadas selecionaram uma única rota, sendo esta uma das mais curtas. Ape-

nas duas colônias selecionaram vários caminhos para atingir o alimento, tendo sido um deles

curto e dois médios. Entretanto, no percurso de volta ao ninho, todas as colônias escolheram

um dos caminhos curtos, conforme Figura 2.5.

Um outro aspecto do comportamento das formigas considerado foi a dinâmica de recru-

tamento ao longo do tempo, que consistiu na soma do número de insetos sobre o dispositivo

27


Figura 2.5: Freqüências de escolha das colônias pelos diferentes caminhos do ambiente, sob acesso a todos os ramos,

em ambas as direções (0-60 min) [1].

verificada a cada intervalo de três minutos, nos dois sentidos do movimento considerados,

conforme a Figura 2.6.

Figura 2.6: Distribuição do número médio de formigas (± desvio padrão) sob acesso a todos os ramos (0-60 min)

[1].

O número médio de formigas sobre o meio sofreu acréscimos até a metade do período dos

experimentos. A partir de 30 min ocorreram pequenas oscilações, que consistem em acrésci-

mos e diminuições de fluxos alternados. O número de insetos sobre o ambiente começou a

28


mostrar tendência de decrescimento no final dos experimentos.

Situação 2 – Bloqueio de um Ramo

No segundo conjunto de experimentos, um dos acessos ao ramo que conduz ao alimento

(3a ou 6a, de acordo com o número da colônia considerada) foi bloqueado após 30 min em

que ele estava livre para uso, permanecendo assim até o final de cada experimento. Neste caso,

os caminhos curtos do ambiente não estiveram disponíveis e os caminhos médios tornaram-se

as menores rotas.

Após o bloqueio de um dos acessos ao ramo mais próximo do alimento, (3a para as colô-

nias pares e 6a para as ímpares) somente três colônias não foram capazes de escolher um novo

caminho sobre o meio, devido à realização de laços (loops). Quatro colônias selecionaram no

forrageio somente um caminho médio, que constituiu uma das menores rotas do ambiente

nesta situação, e as três colônias restantes percorreram um caminho longo para atingir o ali-

mento. Deste modo, conclui-se que a maior parte das colônias demonstra eficácia em suas

decisões, obtendo o alimento através de um caminho alternativo que não constitui um dos

mais longos do meio, vide Figura 2.7.

Figura 2.7: Freqüências de escolha das colônias pelos diferentes caminhos do ambiente no sentido ninho-alimento

sob bloqueio do acesso a um ramo após 30min (0-30 min e 30-60 min) [1].

Ao se deslocarem de volta ao ninho no primeiro período de tempo, após se alimentarem,

um grande número de colônias (seis entre dez) optou pelo uso de diversos caminhos, sendo

esta quantidade superior à evidenciada na direção oposta. A colônia sete, que percorreu

29


o maior número de rotas, selecionou um caminho longo e um caminho muito longo para

atingir o ninho. Quatro colônias escolheram somente um dos menores caminhos para atingir

o ninho. Ainda assim, a maior parte das escolhas se referiu aos trajetos curtos.

No segundo período, porém, somente três colônias selecionaram dois ou três caminhos

para retornar ao ninho, havendo dentre eles um caminho longo e um muito longo. As demais

colônias, que totalizam a maioria, escolheram somente um caminho médio para atingir o

ninho. Apesar dos empates evidenciados, constatou-se que as dez colônias mostraram-se mais

eficazes em seu movimento de volta ao ninho que na direção da fonte, elegendo na maioria

dos casos os menores caminhos, de acordo com o intervalo de tempo considerado (Figura

2.8).

Figura 2.8: Distribuição das escolhas das colônias no sentido alimento-ninho sob bloqueio do acesso a um ramo

após 30 min (0-30 min e 30-60 min) [1].

O número médio de insetos sobre o meio para as dez colônias de formigas sofreu acrés-

cimos elevados em todo o primeiro período da segunda situação experimental, tendendo a

se estabilizar somente no final deste (Figura 2.9). Como as condições do meio foram modi-

ficadas após 30 min, o número de formigas sofreu novo aumento significativo no início do

segundo período. Depois de algumas oscilações, apresentou um pequeno acréscimo no final

dos experimentos, mostrando novamente uma leve tendência a se estabilizar em torno de um

dado valor somente no término dos experimentos.

30


Figura 2.9: Distribuição do número médio de formigas (± desvio padrão) sob bloqueio do acesso a um ramo após

30 min (0-60 min) [1].

Situação 3 – Desbloqueio de um Ramo

No terceiro conjunto de experimentos, as colônias tiveram acesso somente a um caminho

no primeiro período de teste (30 min), o qual constituiu uma rota longa. Para as colônias ím-

pares, cuja fonte de alimento foi localizada na área B do dispositivo experimental, o caminho

permitido foi 4-7-10-2-11-9-6a-16. Para atingir o alimento situado na área A do dispositivo

as formigas puderam utilizar somente o caminho 1-10-7-5-9-11-3a-13. Após este intervalo,

foi permitido o movimento sobre todos os ramos. Desta forma, os caminhos curtos, que

constituem os menores do ambiente, tornaram-se novamente disponíveis após 30 min.

Verificou-se que todas as colônias mantiveram em suas escolhas alguns ramos, aos quais

tiveram acesso entre 0 e 30 min dos experimentos. A maioria das colônias que foi capaz de

descobrir um caminho curto, conforme a Figura 2.10, utilizou alguns ramos percorridos no

primeiro período desta situação experimental e descobriu um atalho para interligá-los, repre-

sentado pelo ramo 8, localizado na região central do dispositivo. Este ramo substituiu então a

porção do caminho formada pelos túneis 10-2-11, quando a fonte de alimento encontrava-se

na área B, e 7-5-9 quando esteve localizada na área A.

Observou-se que a diferença entre os tempos de escolha em cada sentido do movimento

das formigas foi inferior à apresentada na segunda situação experimental. O número médio

de passagens de insetos sobre o meio sofreu acréscimos mais acentuados que nos testes an-

31


Figura 2.10: Distribuição das escolhas das colônias nos dois sentidos de seu movimento sob desbloqueio de vários

ramos após 30 min (30-60min) [1].

teriores durante praticamente todo o primeiro período dos experimentos (Figura 2.11). Este

comportamento pode estar relacionado com a impossibilidade do uso de alguns ramos neste

intervalo de tempo, o que produziu o aumento do número de passagens sobre aqueles que se

encontravam disponíveis. Após 30 min, ocorreram decréscimos mais relevantes e um número

superior de oscilações que nas demais situações. A tendência à estabilidade do número de

formigas sobre o ambiente foi mais evidente neste caso, ocorrendo antes dos instantes finais

dos experimentos.

2.2 Modelagem do Comportamento das Formigas em um Ambiente

Confinado

Dois modelos foram propostos por Vittori [1], sendo que o segundo foi uma versão apri-

morada do primeiro e apresentou melhores resultados. É este segundo modelo, doravante

chamado Modelo FFAC (Formigas Forrageiras em Ambientes Confinados), que será discutido

nesta seção. Nele, a maioria das equações utilizadas são derivadas de funções probabilísticas,

em conformidade com as ações das formigas na natureza [28]. O Modelo FFAC também é

baseado no indivíduo e pode ser desmembrado nas seguintes funções:

• Recrutamento: Diz respeito à entrada de formigas sobre o ambiente, que é definida a cada

segundo;

32


Figura 2.11: Distribuição do número médio de formigas (± desvio padrão) sob desbloqueio do acesso a vários ramos

após 30 min (0-60 min) [1].

• Deslocamento: A velocidade e distância percorrida pelas formigas ao longo do ambiente é

calculada também a cada segundo;

• Tempo Despendido na Fonte: Período de tempo em que as formigas permanecem imóveis

sobre a fonte de alimento, e;

• Retardo de Bloqueio: Período de tempo em que as formigas permanecem imóveis na obs-

trução de um ramo.

• Depósito de Feromônio: Realizado pelas formigas sobre cada ramo percorrido;

• Seleção de Caminhos: Diz respeito à escolha das formigas a cada bifurcação, pelo ramo a

ser percorrido;

No modelo de Vittori [1] foram suprimidas duas características do comportamento das

formigas: (i) a execução de meia-volta sobre um dado ramo, que corresponde à desistência

de um ramo selecionado e parcialmente percorrido e (ii) a evaporação da concentração de fe-

romônio sobre cada ramo do meio. A meia-volta foi desconsiderada porque se verificou que a

execução deste movimento não produzia diferenças significativas no desempenho do modelo,

devido ao comprimento reduzido dos ramos do ambiente. A evaporação de feromônio sobre

os ramos do ambiente foi suprimida devido à duração dos experimentos (60 min) ter sido

considerada pequena em relação ao tempo de vida desta substância sobre o meio, cujo valor

33


médio fica entre 20 e 30 min [28]. Cada ciclo de simulação (passo de tempo) foi associado ao

intervalo um segundo.

2.2.1 Recrutamento

A equação logística pode ser utilizada para representar a variação do fluxo de formigas

F (t) em um processo de recrutamento em massa [15]:

dF (t)

dt= υF (t) +

(

1−F (t)

Fmax

)

, (2.1)

na qual υ está relacionado com a intensidade do recrutamento e Fmax representa o limite

superior para o valor do fluxo de formigas na entrada da rede, e está relacionado ao número de

formigas disponíveis para o recrutamento. Integrando a Eq.2.1, obtém-se o fluxo de entrada

de formigas, F (t):

F (t) =Fmax

1 +

(

Fmax

F0− 1

)

e

−t

τ

, (2.2)

onde F0 é o fluxo inicial na entrada da rede. Os valores de Fmax, F0 e τ são estimados através

da média dos valores dos parâmetros da regressão logística para o fluxo de formigas que

ingressam na rede em função do tempo em cada experimento. O valor de F0, que representa

o número de formigas que entram no ambiente inicialmente. Foi estimado quando o tempo

tende a zero.

No Modelo FFAC, a cada passo da simulação k, uma formiga pode entrar no ambiente de

forrageio com uma probabilidade R[k], definida na Eq. 2.3:

R[k] =F [k]

Fmax

, (2.3)

onde F [k] é calculado através da substituição de t por k na Eq. 2.2, para discretizá-la. Quando

uma formiga chega de volta ao ninho, é eliminada. Nenhuma formiga pode ter uma segunda

entrada na rede de forrageio.

2.2.2 Deslocamento

A velocidade de deslocamento de uma formiga é definida no instante k em que ela seleciona

cada ramo a ser percorrido. Deste modo, uma formiga possui velocidade variável ao longo

34


de seu movimento sobre o ambiente. A velocidade se baseou na velocidade média (V ) dos

insetos e no valor do desvio-padrão (Θ) medido nos experimentos, conforme a Eq. 2.4:

V [k] = V + Θξ, (2.4)

onde V [k] representa a velocidade de deslocamento da formiga no instante k, e ξ representa

um número aleatório gerado a cada iteração (ξ ∼ N(0; 1)). Conseqüentemente a distância

percorrida por cada formiga pode ser representada pela Eq. 2.5:

D[k] = V [k]∆t, (2.5)

onde ∆t é equivalente ao intervalo de tempo transcorrido entre os instantes k e k − 1. No

presente caso, ∆t = 1s.

2.2.3 Tempo Despendido na Fonte

Quando as formigas alcançam a fonte de alimento, permanecem imobilizadas por um

período de tempo. Este tempo foi modelado por uma distribuição logarítmica, com um tempo

característico igual ao tempo médio (Ξ) obtido pelas formigas sobre a fonte nos experimentos.

Assim, a formiga permanece um período de tempo Ts[k] sobre a fonte, ao alcançá-la no

instante k, determinado pela Eq. 2.6.

Ts[k] = Ξ log(Z), (2.6)

na qual Ξ representa o tempo médio despendido pelas formigas sobre o alimento, medido nos

experimentos, e Z é um número aleatório entre zero e um, gerado a cada iteração.

2.2.4 Retardo em Bloqueio de Caminho

O modelo para o retardo (B[k]) de uma formiga sobre um ramo bloqueado num instante

k se baseou no valor médio deste retardo (B), observado nos experimentos, e no valor de

desvio-padrão (∂), conforme a Eq. 2.7:

B[k] = B + ∂Υ, (2.7)

onde Υ é um número aleatório entre zero e um, gerado a cada iteração.

35


A consideração do atraso das formigas sobre um ramo bloqueado permitiu um ajuste

melhor do modelo aos resultados obtidos nos experimentos na segunda e terceira situações

experimentais. Isto foi realizado porque, observando as fitas-cassete onde foram registrados

os experimentos realizados em laboratório, verificou-se que, na segunda situação experimen-

tal, um grande número de formigas se aglomerava sobre a extremidade bloqueada do ramo

3a ou 6a durante um dado período de tempo, logo após a realização do bloqueio. Observou-

se também que este número de formigas decaía ao longo do tempo, quando os insetos eram

capazes de encontrar uma nova solução para alcançarem o alimento. Como este atraso das

formigas sobre o ramo 3a ou 6a ainda não foi medido nos experimentos, decidiu-se utilizar

diversos valores de atraso no modelo, para verificar qual deles proporcionaria os melhores

resultados. O valor que produziu as melhores respostas encontra-se na Tabela 2.2.

2.2.5 Depósito de Feromônio

A concentração de feromônio sobre cada ramo l do meio recebe inicialmente o valor

Cl = 0. Ao deslocar-se sobre o ambiente, cada formiga incrementa a quantidade de feromô-

nio sobre o ramo visitado quando se encontra em suas extremidades, tanto no sentido do

alimento como no retorno ao ninho. Pode ser considerado um valor diferente para o incre-

mento do feromônio, de acordo com o sentido do movimento da formiga. O acréscimo no

sentido ninho-alimento, representado aqui por q, pode ser inferior àquele realizado no sen-

tido inverso, representado neste momento por Q. No atual modelo, realizou-se um estudo do

efeito da relação Q/q na escolha das formigas, e selecionou-se o valor desta relação que pro-

duziu resultados mais próximos daqueles obtidos nos experimentos diante das novas equações

utilizadas, o qual foi igual a 1. Este valor é igual ao descoberto em estudos anteriores sobre o

comportamento das formigas argentinas [29].

2.2.6 Seleção de Caminhos

O ângulo entre o túnel de procedência das formiga e os túneis seguintes (candidatos a

próximo túnel) são considerados para a classificação das bifurcações: (i) simétricas, quando

ambos os ramos candidatos possuem um ângulo de 30 com o túnel precedente, ou; (ii) assi-

métricas, quando um dos ramos faz um ângulo de 30 e o outro faz um ângulo de 120, com

o túnel precedente.

Com o intuito de estimar a influência da geometria na escolha de caminhos em bifurcações

36


assimétricas, a escolha das formigas enquanto o ambiente estava livre de feromônio (dez

primeiras formigas em cada experimento) foi considerada. Dentre 350 formigas observadas,

270 optaram pelo ramo que tem um 30, o que significa 77% das escolhas. Assim, o grau de

atração intrínseco κi do ramo i, devido à geometria, na ausência de feromônio é:

κi =

κ30 = κ, se i está a um ângulo de 30 do ramo prévio l;

κ120 = κrpref , se i está a um ângulo de 120 do ramo prévio l.(2.8)

onde 0 ≤ rpref ≤ 1 e κ determina a concentração de feromônio mínima requerida para influ-

enciar as escolhas das formigas. A equação comumente utilizada para representar a seleção

probabilística de um ramo por uma formiga foi considerada [27, 28]. Quando a formiga chega

em uma bifurcação i − j, as probabilidades que regem as escolhas dos vizinhos são definidas

conforme Eq. 2.9.

Pi[k] =(κi + Ci[k])n

(κi + Ci[k])n + (κj + Cj [k])n= 1− Pj [k], (2.9)

onde Pi[k] representa a probabilidade da formiga optar pelo ramo i no instante k, Ci[k] é a

concentração de feromônio do ramo i e κi representa o grau de atração intrínseco do ramo i,

na ausência de feromônio; n é o grau de não-linearidade das escolhas. Substituindo κ120 por

rprefκ30 na Eq.2.9, e aplicando os melhores valores obtidos nas simulações, κ = 20 e n = 4,

tem-se:

rpref =κ120

κ30

= 4

√

1

p− 1, (2.10)

onde p indica a proporção de formigas escolhendo a bifurcação de ângulo 30. Para uma

bifurcação assimétrica, no entanto, considerou-se que o grau de atração dos ramos candidatos

é diferente, uma vez que as formigas, como todos os organismos que possuem uma simetria

bilateral [30], devem apresentar a tendência de selecionar o ramo que apresenta menor desvio

com relação a sua direção inicial.

A partir das observações experimentais, calculou-se a relação entre o número de passagens

de formigas sobre o ramo que faz um ângulo de 30 com o ramo onde a formiga se encontra

e aquele que faz um ângulo de 120 com o ramo de proveniência da formiga. Dentre 350

formigas analisadas, 270 escolheram o ângulo que fazia o menor ângulo com o ramo de pro-

veniência do inseto, obtendo uma relação p = 0, 77(77%). A partir deste dado, considerou-se

37


a influência da geometria da bifurcação na escolha das formigas através da relação mostrada

na Eq. 2.8.

O Critério Metropolis foi incorporado à segunda versão do Modelo FFAC, com o intuito

de representar a aleatoriedade verificada nos experimentos, desta forma a escolha dos insetos

sobre o ramo a ser percorrido pode ser alterada. Ao atingir a bifurcação i − j, vindo do

ramo l, a formiga seleciona o ramo i ou j a ser percorrido de acordo com a Eq.(2.9). Em

seguida, calcula-se a probabilidade da formiga realizar uma ação aleatória, ou seja, de não

percorrer o vizinho que havia sido anteriormente selecionado. Supondo que o ramo i foi

escolhido, calcula-se a probabilidade P expi [k] da formiga selecionar o ramo j da bifurcação,

que representa uma ação exploratória, conforme Eq. 2.11.

P expi [k] = exp (

Fi[k]− F maxi

Γ[k]) (2.11)

na qual Fi[k] representa o fluxo de formigas sobre o ramo i até o instante k, F maxi repre-

senta o fluxo máximo de formigas sobre o ramos i, e Γ[k] é o fator responsável pelo nível de

exploração das escolhas no instante k.

O valor da variável F maxi foi estimado a partir da concentração de feromônio depositado

sobre os ramos durante as simulações. Dado que cada formiga incrementa com uma quanti-

dade q a concentração de feromônio em cada uma das extremidades do ramo que percorre,

esta substância é acrescida duas vezes por cada formiga do ambiente. Assim, considerou-se

que o fluxo total de formigas sobre um ramo ao final de uma simulação seria igual à con-

centração de feromônio sobre o dado ramo dividida por 2q. Desta forma, para q = 1o valor

de F maxi foi obtido calculando-se a média do fluxo de formigas sobre todos os ramos do

ambiente, ao final de 3.600 segundos de simulação, qualquer que seja o ramo i. A variável

Γ[k] recebeu no início de cada simulação um valor igual ao de F maxi , obtido empiricamente,

e também igual para qualquer ramo i.

A variável Γ[k] sofre um decréscimo quando uma formiga atinge a fonte de alimento

ou o ninho, que são considerados os estados finais do ambiente, de acordo com a direção

do movimento das formigas, como realizado no algoritmo da aprendizagem-Q que utiliza o

critério Metropolis [31]. Apesar do decaimento de Γ[k] poder ser realizado em geral de forma

arbitrária, foi utilizado um fator de decréscimo geométrico, conforme Eq. 2.12.

Γ[k] = ΛΓ[k], (2.12)

38


na qual k é o instante de tempo em que a formiga atinge a fonte de alimento ou o ninho, Λ

é o fator de decaimento de Γ[k] , obtido empiricamente (0, 5 < Λ < 1). O valor inicial Γ[k],

quando k = 0 é Γ0 e é obtido empiricamente. Segue abaixo uma tabela com os parâmetros

do modelo final sugerido em [1], após uma análise de sensibilidade e escolha dos valores que

mais aproximaram os resultados das simulações dos resultados experimentais:

Tabela 2.2: Tabela de parâmetros do modelo original

Função Parâmetro Valor Origem

Geração de Pmax 0,42/s Estimado a

Formigas P0 5x10−4s partir

τ 127,4s dos

Escolha de k 20 experimentos

um ramo n 4

rpref 0,74

Velocidade de V 1,06 cm/s Medido nos

deslocamento Θ 0,34 experimentos

Tempo sobre o alimento Ξ 179,9 s

Depósito de feromônio q 1 Valores

Q 1 empíricos

Critério Metrópolis Γ0 0,98

Fmaxi 1.100

Atraso em um B 100 s

ramo bloqueado ∂ 2,09 s

2.2.7 Resultados do Modelo FFAC

A análise do Modelo FFAC compreendeu a escolha ou não de um caminho que conecte

o ninho à fonte de alimento e o comprimento dos caminhos selecionados nos dois sentidos

do movimento das formigas. O objetivo das simulações era replicar os resultados obtidos

nos experimentos em laboratório. O comportamento do fluxo de formigas foi semelhante

ao observado nos experimentos, conforme Fig. 2.12. O recrutamento de insetos foi inicial-

mente acrescido, permanecendo acentuado até 30 min. Após este período, o fluxo tendeu à

estabilidade, sendo esta mais acentuada nas simulações do Modelo FFAC.

Os resultados das simulações do modelo foram avaliados de forma diferente nas três si-

tuações consideradas. Na primeira situação experimental, onde as formigas tiveram acesso a

todos os ramos do ambiente, foi estimada a probabilidade das formigas escolherem cada tipo

de caminho considerado nas simulações do modelo e nos experimentos. Entretanto, na se-

39


Figura 2.12: Distribuição média do número de formigas (± desvio-padrão) sobre o ambiente ao longo do tempo

sob acesso a todos os ramos. A linha pontilhada representa a média de 200 simulações, e o desvio-padrão é repre-

sentado por linhas contínuas. A linha contínua representa a média obtida em 10 experimentos e o desvio-padrão é

representado por linhas pontilhadas [1].

gunda e terceira situações experimentais, não foi possível medir o fluxo de insetos em todas as

bifurcações do ambiente nos experimentos. Isto está relacionado com as características físicas

da placa de vidro que cobriu o dispositivo experimental utilizado, e que impossibilitaram a

visão do número de formigas sobre as regiões do ambiente cujo acesso não foi permitido, as

quais apresentaram um grande acúmulo de insetos. Assim, os resultados obtidos pelo modelo

proposto na segunda e terceira situações experimentais estão relacionados com a freqüência

de escolha dos diferentes caminhos.

Situação 1: Acesso a Todos os Ramos

Os resultados do Modelo FFAC durante as simulações mostraram-se bastante aderentes

aos evidenciados nas medições da primeira situação experimental. A utilização do Critério

Metropolis permitiu que a probabilidade das formigas escolherem caminhos aleatórios fosse

próxima àquela dos dados experimentais e, ao mesmo tempo, manteve a tendência das formi-

gas pelos caminhos curtos, conforme a Figura 2.13.

40


Figura 2.13: Freqüências de escolha dos caminhos nas simulações, usando o critério Metropolis, e nos experimentos,

quando o acesso a todos os ramos foi permitido durante 60 min (a) no sentido ninho-alimento e (b) no sentido

alimento-ninho. Foram considerados os resultados de 10 experimentos 500 simulações.

Situação 2: Bloqueio a um Ramo

Na segunda situação, o acesso ao ramo 3a (Figura 2.1) foi impedido após 30 min. Assim,

a análise do modelo ocorreu em dois períodos, como nos experimentos: 0-30 min e 30-60 min.

Conforme mencionado no início desta seção, os resultados do modelo e dos experimentos

neste caso se referem à freqüência de escolha dos caminhos, e não à probabilidade de sua

seleção.

Nesta situação experimental, a variável Γ[k] (Eq.(2.11)) recebeu o valor atribuído a F maxi

em k = 0 (Tabela 2.2), quando uma condição do ambiente foi modificada, em k = 1.800, de

forma a tornar mais intensa a realização de escolhas aleatórias no início de uma mudança.

Assim também, quando uma formiga se encontrava sobre uma bifurcação que continha o

ramo 3a ou 6a bloqueado, este ramo poderia ser selecionado, de acordo com a função de

escolha utilizada (Eqs.(2.9)) e o Critério Metropolis (Eqs.(2.11)), no intuito de representar

as escolhas verificadas nos experimentos. Caso o ramo selecionado fosse o 3a ou o 6a, a

formiga permanecia imóvel por um determinado período de tempo (Eq.(2.6)) na extremidade

41


do ramo 3a ou 6a conectada ao ramo de sua proveniência. Após este intervalo, a formiga

selecionaria novamente um ramo a ser percorrido, a partir do ramo 3a ou 6a, aquele de onde

ela veio ou o ramo vizinho. No movimento em direção ao alimento no primeiro período

de tempo (0 − 30min), a freqüência de uso de caminhos curtos nas simulações foi a maior

produzida, sucedida pela freqüência de caminhos médios, como nos experimentos (Figura

2.14 (a)). Os resultados das simulações foram ligeiramente inferiores aos dos experimentos

para as freqüências de caminhos curtos e médios, e a diferença foi maior para caminhos longos

e muito longos. No sentido alimento-ninho, uma freqüência pequena das escolhas realizadas

envolveu caminhos longos, a qual não foi evidenciada nos experimentos (Figura 2.14 (b)).

Houve em ambos os sentidos (ninho-fonte e fonte-ninho) um acréscimo no número de loops

não percebido nos resultados experimentais.

Figura 2.14: Freqüências de escolha dos caminhos nas simulações, usando o modelo FFAC, e nos experimentos,

quando o acesso a um ramo foi impedido após 30min (a) no sentido ninho-alimento e (b) no sentido alimento-

ninho. Foram considerados 10 experimentos e 500 simulações [1]

No segundo período (30− 60min), a freqüência de loops foi muito elevada no movimento

das formigas em direção à fonte de alimento, tendo sido a maior freqüência produzida (Fi-

gura 2.15). De modo complementar, as freqüências de caminhos curtos e médios foram muito

inferiores às obtidas nos experimentos. Ainda assim, o modelo apresentou a grande maioria

dos resultados pertencentes às mesmas categorias de caminhos evidenciadas nos experimentos

no sentido ninho-alimento. Na volta ao ninho, entretanto, as respostas do modelo estiveram

mais próximas daquelas obtidas nos experimentos (Figura 2.15 (b)). A freqüência de cami-

42


nhos curtos foi a maior produzida, tendo sido seguida pela freqüência de caminhos médios

e loops. A freqüência de caminhos médios foi um pouco superior à produzida nos experi-

mentos, enquanto a diferença entre as freqüências de ausência de escolha nas simulações e

nos experimentos foi reduzida. A escolha de caminhos muito longos ocorreu somente nos

experimentos.

Figura 2.15: Freqüências de escolha dos caminhos nas simulações, usando o modelo FFAC, e nos experimentos,

quando o acesso a um ramo foi impedido após 30 min (a) no sentido ninho-alimento e (b) no sentido alimento-

ninho. Foram considerados 10 experimentos e 500 simulações [1]

Com o intuito de compreender melhor o comportamento das formigas nos experimentos e

nas simulações do modelo, calculou-se as freqüências de escolha dos caminhos em um número

superior de intervalos de tempo no sentido ninho-alimento, a partir de 30 min. Os intervalos

considerados foram 30-45 min e 45-60 min. Estes períodos foram escolhidos por representar

bem a tendência das formigas ao longo dos experimentos e simulações. Intervalos menores

abrangem um fluxo menor de formigas e, desta forma, apresentam diversos empates de cami-

nhos, dificultando o acompanhamento do comportamento dos insetos. No período de 30-45

min dos experimentos, as formigas percorreram com maior freqüência caminhos diferentes

daqueles considerados, que constituem ausência de escolha (Figura 2.16 (a)). Porém, após 45

min, as formigas conseguiram encontrar um dos quatorze caminhos considerados, havendo

uma freqüência elevada de caminhos médios, que foi a maior produzida neste período.

Nas simulações do Modelo FFAC, a maior parte das soluções também esteve relacionada

com loops no período de 30-45 min, na direção do alimento. A freqüência deste tipo de resposta

43


foi muito superior à obtida nos experimentos (Figura 2.16 (b)). Após 45 min a ocorrência

loops foi ainda superior à produzida entre 30-45 min.

Figura 2.16: Freqüências de escolha dos caminhos quando o acesso a um ramo foi impedido após 30min, no sentido

ninho-alimento (a) nos experimentos e (b) nas simulações do modelo, usando o modelo FFAC. Foram considerados

10 experimentos e 500 simulações [1]

Os resultados também estão relacionados com a função de escolha usada pelo modelo,

que se baseia fortemente na concentração de feromônio sobre os ramos, e considera o ângulo

da bifurcação com menor intensidade.

Situação 3: Desbloqueio de Vários Ramos

Na terceira situação, as formigas geradas pelo modelo foram forçadas a percorrer um

caminho longo no período de 0-30 min para atingirem a fonte de alimento sobre a área circular

A do dispositivo e retornarem o ninho, qual seja: 1-10-7-5-9-11-3a-13 (Figura 2.1). Após 30

min, foi permitido o acesso a todos os ramos do ambiente. Nas duas direções consideradas

do movimento, o modelo manteve o caminho percorrido no primeiro período das simulações

quando o acesso a todos os ramos foi permitido (Figura 2.17 (a) e (b)). Entretanto, as

formigas utilizadas nos experimentos em laboratório apresentaram uma alta freqüência de

uso de caminhos curtos, seguida pela freqüência de caminhos longos nas duas direções. Na

volta ao ninho, as formigas também percorreram caminhos médios nos experimentos, que

representaram a menor freqüência obtida.

Verificou-se que, nos experimentos, as formigas percorreram caminhos curtos e médios,

44


Figura 2.17: Freqüências de escolha dos caminhos nas simulações, usando o modelo FFAC, e nos experimentos, sob

desbloqueio de vários ramos após 30 min (a) no sentido ninho-alimento e (b) no sentido alimento-ninho. Foram

considerados os resultados de 10 experimentos 500 simulações (30-60 min) [1].

seguidos por caminhos longos e muito longos, desde o início do desbloqueio de vários ramos

do meio, para atingirem o alimento no período de 30-45 min (Figura 2.18 (a)). Neste mesmo

intervalo, as formigas geradas pelo modelo se mantiveram sobre o caminho longo utilizado

até 30 min (Figura 2.18 (b)).

Após 45 min, a freqüência dos caminhos curtos usados nos experimentos se acentuou,

juntamente com a de caminhos longos. Neste período, as formigas também escolheram cami-

nhos diferentes daqueles considerados. As escolhas realizadas nas simulações, por sua vez, se

mantiveram ligadas ao caminho longo percorrido no primeiro período. Na volta ao ninho,

as formigas percorreram caminhos das quatro categorias consideradas nos experimentos e

também entraram em loop no período de 30-45 min, onde a maior freqüência esteve ligada a

caminhos curtos (Figura 2.19 (a) e (b)). Após 45 min, elas percorreram somente caminhos

curtos e longos. As formigas geradas pelo modelo, por sua vez, percorreram o caminho longo

usado no primeiro período durante os dois intervalos de tempo considerados após 30 min.

2.2.8 Discussão acerca do Modelo FFAC

O principal objetivo deste estudo e da conseqüente proposição do modelo modificado

foi investigar a interação entre as atividades comumente realizadas pelas formigas, como o

depósito de feromônio e a parada sobre a fonte de alimento, com a seqüência de escolhas

45


Figura 2.18: Freqüências de escolha dos caminhos sob o desbloqueio de vários ramos após 30 min, no sentido ninho-

alimento (a) nos experimentos e (b) nas simulações do modelo, usando do modelo FFAC. Foram considerados os

resultados de 10 experimentos 500 simulações (30-45 min e 45-60 min) [1].

Figura 2.19: Freqüências de escolha dos caminhos sob o desbloqueio de vários ramos após 30 min, no sentido

alimento-ninho (a) nos experimentos e (b) nas simulações do modelo, usando o do modelo FFAC. Foram conside-

rados os resultados de 10 experimentos 500 simulações (30-45 min e 45-60 min) [1].

binárias nos diferentes tipos de bifurcações encontrados pelas formigas em seu trajeto rumo

ao alimento ou ao ninho. A investigação mais detalhada de determinados aspectos do com-

portamento das formigas, como a velocidade de deslocamento destes insetos e seu fluxo de

46


entrada sobre o meio, permitiu a utilização de funções mais fiéis à realidade observada nos

experimentos.

Foi possível verificar que os ângulos formados entre o ramo de proveniência da formiga

e os ramos candidatos de uma bifurcação são de extrema importância para a obtenção das

melhores soluções do meio, que correspondem aos menores caminhos. Na primeira situação,

os resultados das simulações do modelo se aproximaram daqueles obtidos nos experimentos,

onde a maior parte das escolhas das formigas esteve ligada aos caminhos curtos do ambiente.

Este comportamento do modelo sugere a sua capacidade de adaptação ao ambiente relativa-

mente complexo considerado nos experimentos em laboratório. O Critério Metropolis possi-

bilitou reproduzir o comportamento aleatório apresentado pelas formigas nos experimentos.

É possível verificar que o número de loops é maior no comportamento das formigas observado

nos experimentos.

Ao ser aplicado à segunda situação experimental, onde o acesso a um ramo próximo da

fonte de alimento foi impedido após um período de tempo, o modelo simulou aceitavelmente

o comportamento das formigas em laboratório no sentido alimento-ninho, mas apresentou

dificuldades no sentido que vai do ninho à fonte de alimento, no segundo período das simu-

lações (Figura 2.15 (a)). Isto se deve principalmente ao fato de que, em grande parte das

simulações, as formigas tenderam a usar os mesmos ramos percorridos no primeiro período,

devido à alta concentração de feromônio ali, não realizando um número suficiente de esco-

lhas aleatórias e voltando ao ninho sem atingir o alimento. Esta situação é conhecida como

“estagnação” e representa um dos grandes desafios na modelagem do comportamento destes

insetos.

Na terceira situação experimental, as formigas foram forçadas a percorrer um caminho

longo e o acesso a todos os ramos do ambiente foi permitido somente após um período de

tempo. As formigas geradas pelo modelo não foram capazes de descobrir, após o desbloqueio

do acesso a vários ramos, um caminho diferente daquele longo percorrido inicialmente. As

formigas observadas em laboratório, por sua vez, percorreram caminhos curtos e médios tanto

no sentido ninho-alimento como no inverso, neste mesmo período. Estes resultados indicam

que o FFAC não foi capaz de proporcionar a incidência de escolhas aleatórias das formigas

na terceira situação em número suficiente para a descoberta de outros caminhos após 30

min, diferentes da rota longa percorrida no primeiro período. Isto está relacionado com a

função usada na escolha das formigas pelo modelo, representada pelas Eq.(2.9). De acordo

47


com esta função, se a diferença entre as concentrações de feromônio dos ramos candidatos for

acentuada, o ramo com mais feromônio terá uma grande chance de ser selecionado, ainda que

a geometria da bifurcação seja considerada. Nesta situação experimental, os ramos utilizados

no primeiro período das simulações foram percorridos por um grande número de formigas, o

que tornou sua concentração de feromônio muito elevada após 30 min e sua chance de serem

escolhidos superior a 95%. Como os demais ramos do ambiente não possuíam nenhuma

concentração de feromônio até 30min, a chance de que eles fossem percorridos foi muito

reduzida no segundo período. O uso do critério Metropolis proporcionou a realização de

escolhas aleatórias, mas elas ocorreram em número reduzido, o que não propiciou a mudança

de decisão das formigas.

Deste modo, verificou-se que o FFAC, conforme proposto por Vittori et al. [16], não foi

capaz de simular o comportamento das formigas nas situações experimentais que envolvem

mudanças no ambiente de forrageio, i.e. segunda e terceira terceira situação experimental,

principalmente devido à estagnação.

No intuito de preencher as lacunas do modelo FFAC, buscar-se-á em uma revisão da

literatura especializada, maiores detalhes sobre o comportamento das formigas naturais que

possam inspirar a proposição dos ajustes, e que permita posteriormente o desenvolvimento

de um modelo capaz de superar a estagnação, reproduzindo o comportamento verificado

experimentalmente. Tal revisão é apresentada no próximo capítulo.

48

Capítulo III

Revisão Bibliográfica sobreo Comportamento dos

Insetos SociaisNature never lies. In biology you also have to

consider little things seriously.

—Karl von Frisch

Insetos sociais possuem muitas habilidades além da comunicação estigmérgica, que podem

afetar seu comportamento durante o forrageio. Diversas pesquisas têm enriquecido o

conhecimento científico sobre o comportamento das formigas e outros insetos sociais, reve-

lando intrigantes características e levando a uma compreensão cada vez mais apurada sobre

os processos utilizados por estes seres em sua próspera adaptação aos mais diversos habitats.

A partir de alguns destes estudos, é possível levantar hipóteses sobre as técnicas de comunica-

ção, capacidades sensoriais e cognitivas e comportamento destes insetos em várias situações,

o que propicia a construção de modelos cada vez mais representativos do comportamento das

formigas verificado em laboratório ou in natura.

Este capítulo tem como objetivo apresentar uma sucinta revisão bibliográfica sobre o com-

portamento de insetos, observando aspectos que podem servir como base para o aperfeiçoa-

mento do Modelo FFAC. Conforme discutido no capítulo anterior, as principais discrepâncias

entre os resultados deste modelo e os dados experimentais ocorreram quando foi exigido das

formigas a capacidade de se adaptarem a mudanças no ambiente.

A complexidade dos insetos é tal que impossibilita afirmar quais são os traços determi-

nantes nesta habilidade de adaptação. No entanto, a partir de observações reportadas na lite-


ratura, acredita-se ser possível obter informações que, quando agregadas ao modelo original,

torne-o mais preciso em sua representação do comportamento das formigas em um ambiente

dinâmico. Devido à vastidão de pesquisas associadas ao tema, muitos artigos relevantes não

serão aqui citados, bem como muitos tópicos importantes de alguns trabalhos citados não

serão abordados por apresentarem impacto direto no que concerne ao aperfeiçoamento do

modelo estudado.

Baseado no argumento darwinista da seleção natural, é de se esperar que as formigas que

existem hoje em nosso planeta tenham, a partir de um conjunto de modificações cumulati-

vas bem sucedidas, desenvolvido comportamentos que levaram as colônias a sobreviverem

e se adaptarem a ambientes hostis. Possivelmente, devido a condições ambientais distintas,

diferentes espécies desenvolveram diferentes características e estratégias para a busca de ali-

mento, sendo que a maioria pode carregar consigo características comuns aos seus ancestrais

[32]. Atualmente, é difícil distinguir quais propriedades estão presentes em quais grupos de

espécies, e quais espécies de formigas compartilham das mesmas características sensoriais,

cognitivas ou fisiológicas. Algumas habilidades podem ser menos exploradas por alguns gru-

pos, ou usadas como habilidades auxiliares. É difícil distinguir dentre as espécies, quais têm

parentescos tão remotos que apresentam diferenças genéticas relevantes e quais devem seus

diferentes comportamentos à influência de particularidades nos seus habitats e no tipo de

alimentação disponível [32].

O Modelo FFAC é baseado em experimentos com formigas da espécie Linepithema humile.

No entanto é possível que características observadas em outros experimentos, com outras

espécies de formigas e até mesmo com outros insetos, possam ser comuns a esta espécie, e

portanto, plausíveis e úteis ao aperfeiçoamento do modelo.

3.1 Auto-organização e Adaptação

Uma das características mais atraentes no estudo do comportamento dos insetos sociais,

diz respeito à maneira como padrões complexos, robustos e adaptados ao meio-ambiente

emergem a partir da sobreposição de comportamentos individuais relativamente simples, sem

a necessidade de nenhum controle externo. Uma vez que a capacidade das colônias de insetos

se auto-organizarem deriva da soma dos comportamentos individuais, resta saber quais são as

regras comportamentais determinantes, ou mais relevantes, para que as colônias se adaptem

ao meio-ambiente. Segundo Chialvo & Millonas [33], a reconstrução de um comportamento

50

———— Revisão Bibliográfica sobre o Comportamento dos Insetos Sociais————

em massa a partir do comportamento individual de cada membro da colônia é o problema

central da sociobiologia de insetos.

Enxames de insetos sociais 1 constroem trilhas e redes de tráfego regulares por meio de

um processo de depósito e rastreamento de sinais 2 químicos, i.e. feromônios. Estes padrões

constituem o que é conhecido em neurociências como mapa cognitivo. A principal diferença

consiste no fato de que os insetos escrevem sua memória espacial no ambiente, enquanto os

mamíferos, por exemplo, têm seus mapas cognitivos dentro do cérebro [34]. O que ocorre na

comunicação feromonal tem sido chamada de “sinapse gigante” [35], também em menção às

neurociências. Em uma grosseira analogia, memórias são consideradas como sendo escritas

como um forte acoplamento entre neurônios individuais ou em grupos, as sinapses. Estes

acoplamentos são fortalecidos por uma co-atividade neural da mesma forma que o campo

feromonal é preservado ou fortalecido pelo tráfego coerente e freqüente das formigas.

Existem duas habilidades funcionais aparentemente conflitantes na amplificação feromo-

nal dos enxames: estabilidade com respeito às mudanças aleatórias do ambiente, e; amplifi-

cação da informação, de modo que mesmo uma fraca perturbação externa (por exemplo, na

qualidade do alimento) possa levar a uma resposta significativa. Assim, o enxame possui ao

mesmo tempo memória de longo prazo, imune a flutuações sutis do ambiente, e habilidade

para aprender com novas experiências.

Em Demolin et al. [36] é apresentado um método estocástico para a simulação de sistemas

de trilhas de feromônios que leva em conta as flutuações inerentes ao processo de recruta-

mento, devido, por exemplo, à freqüência variável de indivíduos que deixam o ninho e/ou

retornam ao ponto de escolha entre trilhas. Flutuações que surgem de variabilidades externas

ou individuais – refletindo essencialmente efeitos locais – são simplesmente negligenciadas. Os

resultados provêem indícios de que um grande número de formigas depositando feromônio

melhora a otimalidade e a eficiência das escolhas coletivas.

Segundo Denny et al. [37] é esperado que a parte principal do comportamento das formi-

gas no que concerne à busca de alimento seja a maximização da eficiência da colônia através

da minimização dos comprimentos das trilhas estabelecidas. Trilhas curtas reduzem ambos os

custos de tempo e energia na entrega de comida à colônia, mas o que seria mais importante?

Para examinar a escolha de rotas nas formigas de madeira Formica rufa foram utilizadas uma

1A eusocialidade é caracterizada pela cooperação no cuidado com a prole, superposição de gerações e divisão reprodutiva

de trabalho e é encontrada em ordens de insetos.2A distinção entre sinais e rastros é que os rastros não são formados pela seleção natural, de modo que transferem informa-

ções incidentalmente.

51


série de pontes, cada uma com duas rotas alternativas, permitindo a comparação de com-

binações horizontais, verticais ou curvas, de diferentes consumo de tempo e de diferentes

comprimentos. O trabalho define eficiência como a maximização do ganho de energia por

unidade de energia consumida. Já a taxa máxima de armazenamento de energia está relacio-

nada à quantidade de energia conseguida por unidade de tempo. Os benefícios de uma fonte

de comida particular são geralmente fixados com relação ao valor calorífico da comida e a

habilidade dos indivíduos de carregarem-na apenas entre certos limites. Assim, o aumento no

fluxo de entrada de energia implica na redução do custo de busca. Contrariamente às evi-

dências anteriores, a economia de energia explica significativamente melhor as variações nas

preferências das formigas por trilhas, que economias de tempo. É sugerido que os resultados

possam explicar os ajustes de velocidade que as formigas de madeira fazem quando andam

num plano vertical em resposta ao potencial custo de energia encontrado.

Sumpter & Beekman [38] consideram que apesar de ser claro que as trilhas de feromônio

envolvem um mecanismo de realimentação através do qual as formigas podem compartilhar

informações e assim aumentar as chances de sucesso coletivo, é menos claro como preci-

samente esta realimentação resulta numa distribuição eficiente de formigas entre as fontes

disponíveis de alimento. Por exemplo, não é claro, como as formigas irão alocar melhor sua

força de trabalho para a melhor dentre duas fontes. O sucesso do mecanismo de trilhas de

feromônio provavelmente é causado, pelo menos em parte, pela resposta não-linear das for-

migas às trilhas de feromônio, no que diz respeito, por exemplo, à distância que uma formiga

segue na mesma trilha antes de deixá-la. Tal distância é uma função da concentração de

feromônio e apresenta um ponto de saturação.

3.2 Mecanismos de Navegação e Exploração do Habitat

A dinâmica das formigas na busca por alimentos em um determinado ambiente pode ser

em parte explicada pelo ciclo de vida das trilhas de feromônio, desde seu surgimento até sua

evaporação total. No entanto, uma série de outras características individuais se somam à

comunicação feromonal ou multimodal, como o efeito da memória ou a atração pelo desco-

nhecido.

Em animais que vivem em grupo, a navegação pode depender de uma memória individual,

baseada nas experiências prévias e na aprendizagem, mas também pode se basear na orien-

tação através do uso de memória externa, suportada por sinais persistentes de atividades de

52


seus semelhantes [39]. Por exemplo, as formigas Linepithema humile e Lasius niger utilizam a

comunicação de massa e a orientação através de trilhas químicas para explorarem novas fon-

tes de alimento. No entanto, enquanto a Linepithema usa predominantemente comunicação

feromonal, a Lasius pode comutar para um modo mais individual de orientação, baseado no

aprendizado de rotas pela associação com marcos do terreno. Já a formiga tropical gigante Pa-

raponera clavata utiliza uma hierarquia de meios de navegação: formigas inexperientes utilizam

feromônio, enquanto formigas experientes utilizam a memória visual de marcos presentes no

habitat. A lógica desta escolha recai na eficiência energética.

3.2.1 Exploração de “Novidades”

Há evidências de que baratas são aptas a usar trilhas químicas, apesar de utilizarem tam-

bém pistas idiotéticas 3 e o aprendizado de caminhos por meio de marcos visuais [40]. No

trabalho de Ame et al. [40] é estudado como as baratas resolvem problemas de conflitos entre

estes dois sistemas. Os experimentos foram projetados para separar o efeito do conhecimento

baseado na experiência das baratas do efeito das trilhas de feromônio. Os resultados mos-

traram que quando as baratas se deparam com uma escolha entre dois ramos sem marcação

química, as escolhas são distribuídas uniformemente.

Os experimentos mostram que as baratas preferem um ramo marcado por parceiras de

ninho enquanto não há novidades (entre um ramo marcado e um limpo sem nenhum ramo

novo). Isto mostra que as baratas são influenciadas pela presença de trilhas, mas tembém por

novidades no ambiente.

Apesar da influência das trilhas químicas, o estudo sugere que a seleção de caminhos foi

também afetada por experiências individuais prévias na plataforma. Se durante a fase de

marcação havia apenas um ramo, e durante o teste, dois ramos “novos” surgem, as baratas

preferem o ramo novo do lado oposto ao lado anteriormente marcado, mostrando uma ten-

dência à “exploração da novidade”. De fato, baratas confrontadas com uma escolha binária

entre ramos não marcados exibem uma preferência pelo ramo localizado do lado oposto ao

lado onde anteriormente havia marcação. Isto deve ser originado na tendência das baratas de

explorarem novos objetos introduzidos na sua faixa de atuação próxima ao ninho.

Quando a marcação e a novidade provêem informações conflitantes, a atração do ramo

marcado depende da intensidade da marcação. A maior assimetria das escolhas ocorre quando

3Diz respeito a pistas advindas do próprio indivíduo, como por exemplo através da Integração de Caminhos (Path Integration),

em oposição a pistas advindas do meio, tal como trilhas de feromônio ou estímulos visuais.

53


marcação e novidade agem em sinergia. Em sua conclusão, o artigo indica que as baratas

dependem da interação entre habilidades de navegação individuais adquiridas pela experiência

individual e da memória coletiva, neste caso, a marcação feromonal.

Há evidência do comportamento de exploração de novidades também por parte das for-

migas. Em Hölldobler & Wilson [35], generalizações feitas a partir de repetidas observações

durante um ano de experimentos mostram que quando as formigas emergem do ninho em um

ambiente “novo”, limpo de feromônio, o recrutamento começa em até cinco minutos, com o

depósito intensivo de feromônio até ser feita a exploração de toda a área. Após uma hora, o

número de formigas diminui na nova área e após um dia é mínimo. Quando uma nova área é

conectada à primeira, as formigas repetem o procedimento.

3.2.2 Familiarização com o Ambiente

Hölldobler & Wilson [35] mostraram que operárias de Atta cephalotes depositam um

feromônio indicador nas proximidades das saídas de seus ninhos. Algumas substâncias

orientam as operárias para as aberturas e incrementam a taxa de depósito de feromônio nas

trilhas. Quando as operárias Atta cephalotes são colocadas em uma área estranha e suas pistas

visuais são confundidas, elas se espalham de maneira devagar e abrangente, mostrando pouco

interesse em folhas frescas apresentadas a elas. O mesmo não é observado quando uma área

já utilizada (marcada com feromônio) é apresentada a elas, ali elas parecem se juntar.

3.2.3 Navegação de Insetos no Deserto

Collett [41] em seu trabalho com formigas do deserto (Lasius niger) afirma que a visu-

alização de marcos familiares, ajudam-nas em suas viagens entre o ninho e a área onde se

encontram os alimentos. Os insetos movem-se até que as imagens em suas retinas casem

com suas memórias de visões prévias do ambiente, associadas ao alcance de seus objetivos, e

assim, podem decidir quais rumos tomar. As trajetórias das formigas são então ditadas por

instruções internas, denominadas vetores-objetivo.

Se as formigas estão acostumadas a obter alimentos em um mesmo local, com a trajetória

entre o ninho e este local cerceada por marcos, os indivíduos seguirão uma rota estereotipada.

Segundo esta hipótese, as trajetórias de formigas familiarizadas, quando um obstáculo se lo-

caliza no seu caminho ao ninho, se assemelharão àquelas das formigas sem familiaridade com

os marcos nas rotas até seus ninhos, com uma diferença: formigas experientes irão apresen-

54


tar uma forte tendência nas direções de seus desvios, enquanto formigas inexperientes irão

desviar igualmente em qualquer direção.

Em Collett et al. [42] aponta-se que as formigas do deserto (Catagliphis fortis) monitoram

suas posições em relação ao ninho utilizando uma técnica de navegação conhecida como

Integração de Caminho (PI -Path Integrator ou Dead Reckoning) para estimar suas localizações

atuais baseadas nos movimentos que efetuaram anteriormente desde que saíram do último

local conhecido. Elas fazem isto com uma compasso solar e um hodômetro para atualizarem

um acumulador que registra suas posições atuais. Neste processo, chamado de navegação

vetorial, calibrado em locais reconhecidos pelas formigas, tais como a fonte de alimentos e o

ninho, foi proposto um modelo de navegação vetorial que sugere como a calibração poderia

produzir as trajetórias verificadas.

Embora a navegação num curto prazo possa operar sem marcos, num longo período,

os marcos ajudam a manter a navegação correta. Para Collett & Collett [43] a navegação

vetorial é o principal meio de navegação em terrenos não familiares ou quando marcos es-

tão indisponíveis. Integração de Caminhos (IC) é particularmente importante para formigas

cataglyphid na descoberta de novas fontes de alimentos em terrenos estranhos, quando não

há marcos visuais ou químicos que provejam pistas de orientação. Estas formigas habitam

grandes desertos sem traços característicos.

A Integração de Caminhos (IC) não requer memória de longo prazo. Formigas que nave-

gam por IC, então, aprendem a aparência de marcos visuais durante seus percursos. Quebra-

se o caminho em segmentos marcados por marcos distintos com vetores locais associados a

cada marco, tornando assim mais fácil o encontro de alvos definidos. No entanto, as formigas

não usam os marcos visuais familiares para restaurar seu sistema de IC global. Em Collett

& Collett [44], argumenta-se que formigas e abelhas têm uma memorização gradual de ter-

renos familiares. Estes insetos relembram não mais do que é necessário para sustentar suas

estratégias de navegação, separadas e em paralelo, que aplicam quando viajam entre fontes

de alimentos. A principal é a IC, melhorada por memórias de longo-prazo de locais significa-

tivos, armazenadas em termos de coordenadas entre estes e o ninho. Completamente distinto

da IC, são memórias associadas com rotas familiares, que ajudam os insetos a manterem uma

rota definida.

Ambas formigas e abelhas podem guardar as coordenadas de um local com comida. As

formigas do deserto aplicam uma estratégia diferente para a recomposição de seu sistema de

55


navegação vetorial, resolvendo conflitos entre a orientação por marcos familiares e pela Inte-

gração de Caminhos. Quando a navegação vetorial discorda das sugestões dadas pelos marcos

visuais que indicam um segmento de rota familiar, as formigas temporariamente aplicam suas

apostas nas informações dos marcos visuais.

Segundo Collett et al. [45] formigas e outros insetos freqüentemente seguem rotas fixas

dos seus ninhos até a área onde há alimentos. A forma destas rotas é definida inicialmente

por estratégias de navegação, tais como IC e as respostas naturais aos marcos visuais, que

dependem minimamente de memória. Com o aumento da experiência, estas rotas iniciais são

estabilizadas através da aprendizagem da visão de marcos e ações associadas. A substituição

de estratégias baseadas em memória faz com que as rotas dos insetos tornem-se mais robustas

e precisas.

Apesar de geralmente se presumir que formigas meramente seguem trilhas químicas, na

realidade suas estratégias de navegação são bem mais diversas. Formigas do deserto não

deixam trilhas químicas de maneira alguma. Mesmo as encarregadas da busca de alimento

(forrageio), em algumas espécies que deixam trilhas químicas, rapidamente aprendem a se

guiar através de marcos visuais que vêem das trilhas. Quando, nos experimentos, trilhas

químicas e marcos visuais são colocados em conflito, as formigas experientes são guiadas

pelos estímulos visuais, enquanto as novatas seguem os sinais químicos.

Foram revisados experimentos mostrando que apesar dos vetores locais poderem ser reco-

brados por meio do reconhecimento dos marcos visuais, o sistema de IC global é independente

das informações destes marcos e estes não possuem coordenadas associadas a eles. A maior

função dos marcos visuais é puramente procedimental, indicando ao inseto que ação tomar

em seguida.

Insetos possuem estratégias de navegação que envolvem pouca memória e podem ser usa-

das em terrenos estranhos. Estas estratégias inicialmente podem ser imprecisas ou lentas, e

com a experiência, tendem a serem suplantadas por estratégias que exigem mais da memória,

mais rápidas e mais precisas, mas que só são confiáveis após a aprendizagem de experiências

múltiplas. Uma vez que um território se torna familiar e memórias apropriadas estão disponí-

veis, estratégias mais maduras que requerem estas memórias geralmente assumem precedência

em detrimento das estratégias iniciais. Será que os insetos possuem uma representação como

mapa, ou eles simplesmente familiarizam-se com rotas particulares que levam-nos de um lugar

significativo a outro?

56


Há incerteza sobre como as formigas enlaçam estes dois tipos de informações (IC e marcos

visuais). IC fornece distância e direção em relação ao ninho. Vetores locais devem estar as-

sociados aos marcos. Um terreno familiar parece ser representado de duas maneiras distintas

e separadas. A primeira é uma representação métrica de lugares em termos de coordenadas

que estão referenciadas no ninho com coordenadas de lugares significativos armazenados em

memória de longo-prazo. A segunda é baseada nos marcos visuais, que são associadas a ve-

tores locais e provêm aos insetos uma seqüência de memórias ao longo de seus caminhos até

um determinado alvo. Não há evidências de que marcos visuais estejam associados com a IC

global. Quando as formigas são submetidas a informações conflitantes dos dois sistemas, elas

tendem geralmente e seguir o que ditam suas memórias baseadas nas rotas mais que seus sis-

temas de IC. Manter os dois sistemas independentes pode ter desvantagens, mas isto significa

que os erros de um sistema não se propagam para o outro [44].

Em Collett & Collett [46], insetos tais como formigas e abelhas também exibem uma

notável variedade de memórias para a navegação. A primeira coisa notável que as formigas

não fazem é tomar um atalho de volta direto para o ninho. Ao invés de serem usadas em

associação com memórias de marcos visuais, IC aparece como sendo reservada como uma

fonte de informação independente sobre as posições dos indivíduos, baseada apenas nas in-

formações dos movimentos da viagem em andamento. As formigas do deserto não refazem

suas rotas de ida à comida em suas voltas ao ninho, o que sugere que elas não aprenderam

incidentalmente suas rotas de retorno como rotas de ida invertidas. Como as formigas não to-

mam suas rotas ao inverso para retornarem, e tampouco tomam atalhos mais curtos de volta

ao ninho, isto sugere que elas não incorporaram suas memórias visuais em alguma espécie de

mapa cognitivo.

O trabalho de Dyer [47], levanta a questão: Como abelhas aprendem as relações espaciais

entre locais bastante amplos e separados de um “terreno familiar”? Problemas de navegação

específicos encarados por um animal dependem da escala das distâncias que separam os locais

aonde eles têm que passar, tais como fonte de alimentos e ninhos. Enquanto se reconhece que

estes problemas diferem, nunca é lembrado que deve haver uma ligação entre os processos

visuais e de aprendizagem para cada uma destas escalas espaciais. Para insetos que se movem

sobre grandes distâncias, a fonte mais importante de informações para navegação são os guias

celestes e os marcos visuais terrestres. É mostrado que as impressionantes habilidades de na-

vegação das abelhas são baseadas em uma arquitetura cognitiva minimalista. A simplicidade é

57


vantajosa porque impõe baixas demandas computacionais da capacidade do animal, cujo pro-

cessamento de informações espaciais e habilidades cognitivas são supostamente restringidas

por seu pequeno sistema nervoso.

Segundo Grah [48] as formigas do deserto (Cataglyphis fortis) usam um kit de ferramen-

tas de navegação que consiste de: compasso a partir da luz no céu, IC e uma maneira de

reconhecimento de marcos por estímulo visual. Certamente a seleção natural não permite

a um cérebro minúsculo o provimento de espaço e energia para recursos computacionais e

armazenamento que não serão de uso imediato para os navegadores, particularmente porque,

em termos energéticos, o cérebro é de longe o órgão de maior consumo em qualquer animal.

Quando a formiga Cataglyphis fortis busca alimento nos terrenos vastos e sem particularidades

do Saara, a IC é o único meio de adquirir informações de posição.

Na navegação por meio de marcos visuais, os insetos rotulam pontos particulares do

área de forrageio e fazem associações de decisões locais de navegação com as cenas visua-

lizadas. Há alguma maneira casamento destes pontos rotulados com imagens organizadas

retino-oticamente. As Cataglyphis não utilizam estas informações para adquirirem uma “me-

mória geral da paisagem”, i.e., – uma representação geocêntrica onde as relações espaciais

entre múltiplos lugares são definidas em termos cartográficos. Mesmo uma navegadora com

pequeno treinamento exibe considerável flexibilidade no acoplamento e desacoplamento de

diferentes módulos e sistemas referenciais.

Segundo Wehner et al. [49], formigas do deserto efetuam excursões circunjacentes de larga

escala mesmo sem a presença de marcos visuais através da integração de caminhos (IC). Elas

continuamente atualizam seus vetores-ninho. A associação de marcos visuais nas proximida-

des do ninho e a habilidade de associar ações às capturas instantâneas visuais associadas a

estes marcos para se sobrepor à integração de caminhos poderiam ser demonstradas.

Em Knaden & Wehner [50], as formigas do deserto utilizam a integração de caminhos

(IC) como seu sistema predominante de navegação de longas distâncias, mas elas também

fazem o uso de marcos para a definição de rotas e para a definição do ninho. Experimentos

comprovam a capacidade das formigas utilizarem o reconhecimento visual para calibrar a IC.

Devido à sua natureza egocêntrica, a IC é propensa a erros. Por esta razão, é uma estratégia

conveniente se reiniciar a IC caso a formiga tenha chegado a um destino final, o ninho. Caso

contrário, durante consecutivas buscas por alimentos, os erros iriam prontamente acumular.

58


3.3 Comunicação dos Insetos Sociais

O estudo da comunicação dos insetos sociais na busca de alimento tem uma longa his-

tória, segundo Jackson & Ratnieks [34]. Em 1880, Baron Avebury afirmou que as formigas

utilizavam o odor para se comunicarem [34]. Em 1962, Wilson associou o uso de feromô-

nio com a realimentação positiva [34]. As trilhas decaem quando a comida acaba porque as

formigas arrefecem o reforço das trilhas nos seus retornos e o feromônio existente evapora

provendo uma realimentação negativa4. Em 1980 houve a associação do uso do feromônio

com a auto-organização. Wilson [35] define comunicação como uma “ação por parte de um

organismo que altera o padrão probabilístico do comportamento em outro organismo de uma

maneira adaptativa a ambos os participantes”.

Parece ingênuo hoje afirmar que o comportamento das formigas são baseadas apenas na

quantidade de feromônio percebida em um conjunto de trilhas. A comunicação e o processo

decisório dos insetos são bem mais ricos e complexos, envolvendo muitos meios de comunica-

ção e suas interações, e podem depender de outras tantas variáveis, tais como luminosidade,

distâncias envolvidas, relevo, tipo de alimentação, predadores, quantidade de alimento dispo-

nível, etc.

3.3.1 Comunicação Multimodal

Darwin, no seu livro - A expressão das emoções em homens e animais (1872) - notou que

o poder da comunicação pela linguagem é potencializado por movimentos expressivos da face

do corpo [10]. Sinais multimodais em abelhas, inclui quatro ou cinco modalidades: auditiva,

vibracional, tátil, olfatória e gustatória. Em formigas, feromônios, batidas, estridulações,

movimentos rítmicos, empurrões, sacudidas, abanadas, apertões e antenadas combinam-se em

métodos de comunicações que podem alterar o significado de cada um destes meios quando

separados.

Até mesmo o prolongamento da estadia nas proximidades de uma presa pode modificar

a interpretação coletiva de outros sinais. Em alguns casos, as formigas podem liberar um

feromônio para recrutar companheiras em um raio de até dois metros, para que ajudem na

remoção de algum objeto maior (inseto morto, por exemplo). Este sinal também pode ser

modulado por estridulações, avançando o tempo de remoção em até dois minutos por causa de

4Vale notar aqui que a realimentação negativa aqui associada nada mais é que a diminuição da realimentação positiva

existente e não se encaixa no conceito costumeiramente utilizado para o termo na Teoria de Controle de Sistemas.

59


atitudes mais urgentes. Sinais estridulatórios no caso das formigas forrageiras não funcionam

sozinhos, apenas em comunicação multimodal.

As formigas também podem utilizar batidas no chão ou estridulações para enviar sinais de

alarmes, sinais de necessidades de resgates (neste caso castas diferentes de formigas respon-

dem diferentemente), sinais de que estão cortando alimentos, etc., a depender do contexto.

A quantidade de estridulações também varia com a qualidade do alimento. Experimentos

mostraram que os movimentos das formigas melhoram as respostas aos estímulos químicos

de recrutamento.

Quando há disputas entre colônias distintas, há uma comunicação do tipo intimidadora

(resource holding potential) para demonstrar aos inimigos a potência das garras, o tamanho

dos indivíduos, etc. Quando há uma evidente desvantagem de um dos competidores, este se

rende, podendo até ser escravizado, e a disputa acaba. Em caso contrário pode haver um

conflito direto. Hölldobler [10] mostra que há detalhes no comportamento das formigas que

são deveras importantes. Em geral, sinais visuais, sonoros e químicos estão presentes, às

vezes como canais diretos de comunicação, outras vezes como moduladores do estado de

motivação dos receptores.

3.4 Depósito e Percepção de Feromônios

É certo que diversas espécies de formigas utilizam a comunicação indireta, através do

depósito e percepção de feromônios no ambiente, para estabelecerem as estratégias na busca

de alimento, defesa da colônia e exploração do ambiente. Variações sutis nas percepções

das concentrações de feromônio, no depósito ou nas características físico-químicas destes

feromônios podem resultar em grandes mudanças no comportamento da colônia e culminar

no sucesso ou fracasso deste sistema de comunicação. O trabalho de pesquisa dos mecanismos

envolvidos no processo de percepção de feromônios, bem como das decisões tomadas a partir

destes mecanismos não é fácil, muitas vezes são monitorados e analisados indiretamente,

dando margem a uma série de hipóteses e modelos.

No que diz respeito à percepção do feromônio, Chialvo & Millonas [33] argumentam

que formigas fazem o uso de (pelo menos) dois diferentes tipos de taxis5 para lidar com o

feromônio: osmotropotaxis – um tipo de seguimento de gradiente instantâneo de feromônio,

computado através da diferença de concentração percebida entre as antenas, e; klinotaxis –

5Comportamento inato de um organismo em resposta a um estímulo direcional.

60


método seqüencial, computado por meio das diferentes amostras do ambiente para saber a

direção do estímulo. Watmough & Edelstein-Keshet [51] consideram apenas que as formigas

são capazes de detectar diferenças nas concentrações de feromônio entre suas duas antenas

(osmotropotaxis).

No intuito de inferir sobre a influência da concentração de feromônio percebida pelas

formigas em suas decisões, Watmough & Edelstein-Keshet [51] introduzem o conceito de

fidelidade de uma formiga a uma determinada trilha, que seria a probabilidade da formiga

continuar a seguir esta trilha e que, segundo seu modelo, varia linearmente com a concentra-

ção de feromônio na trilha até um ponto de saturação.

O trabalho de Vincent & Myerscough [52] analisa alguns fatores que influenciam os pa-

drões das trilhas das formigas em um ambiente aberto. O depósito de feromônio é identificado

como um destes fatores. É lançado um modelo para detecção e resposta das formigas ao fe-

romônio, consistindo de: i) um limiar mínimo para a detecção da concentração de feromônio;

ii) uma resposta acrescida para concentrações maiores, e; iii) uma saturação para concentra-

ções demasiadamente altas. Onde, para uma concentração de feromônio τ , f(τ) representa a

habilidade das formigas de detectarem e responderem a esta concentração:

f(τ) = (1 +τ

1 + cτ)β, (3.1)

onde f(.) pode ser interpretada como a fidelidade às trilhas de feromônio e foi desenvolvida a

partir de dados experimentais [33]. O parâmetro β pode ser interpretado como a sensibilidade

ao feromônio e c é uma constante de ajuste. A Figura 3.1 ilustra melhor esta função.

É de se esperar que o sistema sensorial das formigas requeira uma concentração mínima

de feromônio, necessária para influenciar suas decisões. Da mesma forma, é de se esperar que

haja um nível de saturação a partir do qual a ação do inseto será a mesma. É interessante

notar no entanto que, apesar de o modelo de Deneubourg et al.[28] não incorporar a saturação

das antenas, a formação de trilhas ainda ocorre, possivelmente devido ao efeito inibitório

(restrições de movimento) dos congestionamentos nas trilhas.

Vincent & Myerscough [52] apresentam um modelo para variação da concentração de

feromônio numa dada trilha i:

dτi

dt= −κτi + ηρi, (3.2)

onde a taxa de depósito de feromônio por formiga é representada por η, ρi é a densidade de

61


Figura 3.1: Função da concentração de feromônio para valores diferentes de β.

formigas na trilha i e a taxa de decaimento (evaporação) é representada por κ.

3.4.1 Depósito de Feromônio

No que diz respeito ao depósito de feromônio associado ao recrutamento de formigas para

forrageio, são várias as possibilidades de variações. Tipicamente, o depósito pode ser feito

por um determinado grupo de insetos da colônia ou por todos, pode ser feito no percurso

de ida e volta do ninho à fonte de alimentos ou somente na volta, pode ser influenciado pela

quantidade, qualidade ou distância do alimento, ou pelas características da colônia.

É natural que para se adaptar a mudanças no ambiente e às necessidades da colônia, mo-

dificações quantitativas e qualitativas nas trilhas de feromônio ocorram ao longo do tempo.

Edelstein-Keshet et al. [53] discutem como estas modificações são controladas no nível indi-

vidual. A hipótese lançada é que mudanças no comportamento coletivo são provenientes de

mudanças individuais. O efeito coletivo seria resultado da autocatálise ou realimentação po-

sitiva dos comportamentos individuais. No caso estudado, o comportamento individual diz

respeito ao lançamento de trilhas químicas de feromônio.

Nem todas as formigas formam redes maciças de trilhas. Em algumas espécies, apenas

indivíduos retornando de uma fonte de alimento despejam feromônio. Em outros casos isto

pode ser contínuo em todos os caminhos percorridos pelas formigas. Diversas topologias

podem ser verificadas nas redes compostas por trilhas de feromônios de diferentes espécies

62


de formigas, dentre estas topologias pode-se observar que as trilhas para o recrutamento de

formigas para fontes de alimentos são quase diretas ao ninho, sendo as menores possíveis. Já

trilhas de exploração tendem a ter o formato helicoidal reticulado, de modo a ocupar a maior

área possível.

O trabalho de Vincent & Myerscough [52] também verifica a influência do nível de depó-

sito na topologia das trilhas, ali é considerado que as formigas depositam feromônio a um dos

dois níveis: ηlow ou ηhigh, sendo que a taxa média de depósito para um grupo de formigas em

uma trilha cairia no intervalo ηlow ≥ ηi ≥ ηhigh e a flexibilidade da colônia aumenta quando

as formigas possuem a capacidade de variar este parâmetro de acordo com modificações no

ambiente, como por exemplo, na descoberta de comida.

O modelo lançado por Edelstein-Keshet et al. [53] considera que as formigas seguem as

trilhas, mas também se perdem, desviando-se das mesmas e assim apresentando uma compo-

nente aleatória em seu comportamento. Também é considerado que o comportamento dos

insetos dependem das intensidades de feromônios nas trilhas (S), que pode atingir uma valor

máximo (Smax). A taxa de formigas que se desviam das trilhas variam de acordo com S a

seguinte expressão:

ε(S) = Ee−bS, (3.3)

onde ε é a taxa de desvio das trilhas, b e E são parâmetros a serem ajustados. As transições de

parâmetros associados ao recrutamento podem estar associadas a variações no ambiente ou

na colônia ao longo do tempo (horas, dias, meses). Aqui, as formigas que seguem uma trilha

de feromônio possuem “fidelidade” variável.

Modelos e observações do comportamento das formigas, auto-organização e respostas

ao recrutamento têm sido estudadas pelo grupo de Bruxelas (Pasteels, Deneubourg, Goss e

Aaron). Uma investigação cuidadosa dos valores dos parâmetros revelam que transições no

comportamento da população ocorrem perto de valores particulares (bifurcações), para que

responda rapidamente a pressões físicas e ambientais acarretando uma vantagem competitiva.

É de se esperar que a operação perto de tais valores tenha sido recompensada pela seleção

natural.

As dimensões e longevidade de uma trilha de feromônio artificial em uma superfície não

absorvente foi primeiramente discutida por Bossert e Wilson (mais tarde foi entendido que o

substrato afeta a longevidade das trilhas). O modelo se apóia na fidelidade das formigas (ε)

63


que é definida como a probabilidade de as formigas deixarem uma dada trilha por unidade

de tempo e decai exponencialmente com da intensidade de feromônio na trilha, conforme

Equação 3.1. Watmough & Edelstein-Keshet [51] apresenta um desenvolvimento de autô-

mato celular baseado em modelos anteriormente lançados. É considerado ali que a formação

de trilhas dominantes depende da densidade total de formigas. O trabalho se concentra na

formação inicial de trilhas de formigas, que emergem a partir de um ninho centralizado. O

modelo acopla um comportamento determinístico a uma componente aleatória. Quando a

fidelidade decresce, há uma maior tendência à formação de poucos caminhos fortes. Foi mos-

trado que apenas pequenas mudanças no comportamento dos indivíduos são necessários para

habilitar a sociedade a adaptar-se a várias grandes mudanças no ambiente.

Segundo Mailleux et al. [54], quando as formigas batedoras Lasius niger descobrem uma

nova fonte de alimento, elas retornam ao ninho depositando feromônio. Se esta fonte de

alimento for fraca no que diz respeito à quantidade do alimento, elas continuam explorando

o ambiente. Se não encontram comida, voltam sem depositar feromônio. Este estudo provê

as primeiras evidências diretas dos critérios utilizados pelas formigas batedoras da espécie

Lasius niger na avaliação da quantidade de comida disponível. Tais critérios governam suas

decisões no depósito de feromônio para a formação de trilhas de recrutamento e são baseados

na possibilidade de ingerirem o volume desejado.

Em Sumpter & Beekman [38], as colônias foram estabelecidas em um ambiente experi-

mental, uma área para a busca de alimento onde poderiam explorar livremente as fontes de

alimentos que foram dispostas a distâncias fixas do ninho. A formiga Pharaoh usa exclusiva-

mente trilhas de feromônio, recrutamento em massa, para comunicar a localização da comida.

Quando as formigas foram apresentadas simultaneamente a duas fontes de alimentos, cada

uma com qualidade diferente (diferentes concentrações de açúcar no xarope), a fonte com me-

lhor qualidade foi explorada com mais freqüência. A resposta de velocidade sugere que apesar

de algumas formigas visitarem ambas as fontes, poucas tiveram oportunidade de compará-las.

A intensidade do recrutamento é determinada pela quantidade de feromônio que as formi-

gas depositam, a qual, assume-se que depende da qualidade das fontes de alimento. Quando

as formigas foram apresentadas a uma única fonte, a qualidade desta não afeta o nível máximo

de exploração da fonte, mas é verificada que uma maior realimentação positiva em fontes me-

lhores resultam num menor tempo para se atingir o mesmo nível de exploração. Quando

apresentados a duas fontes de alimentos com a mesma qualidade, as formigas não mostraram

64


nenhuma preferência para alguma delas, mas cada colônia experimentada mostrou-se com

viés para uma ou outra fonte, provavelmente relacionada com a distribuição inicial das for-

migas. Como um todo, os resultados são consistentes com as predições do modelo lançado,

onde pequenas diferenças no nível inicial de descobertas fazem com que, a longo prazo, as

formigas foquem na fonte que é mais explorada no início.

Apesar da variabilidade inerente dos padrões das formigas, a abordagem do modelo ma-

temático combinado com os experimentos mostram que padrões claros aparecem para a for-

miga Pharaoh:

1. Em média, a colônia aloca o mesmo número de trabalhadores para a busca de alimen-

tos, independente de haver uma ou duas fontes de alimentos com diferente ou mesma

qualidade.

2. Estes trabalhadores estão concentrados nas melhores fontes de alimento; Ainda segundo

Sumpter & Beekman [38], tais observações são importantes porque mostram que pa-

drões bem sucedidos de comportamentos podem emergir de regras simples em cada in-

divíduo e sem organização centralizada.

3.4.2 Evaporação das Trilhas de Feromônio

Um outro fator determinante na dinâmica das colônias de insetos que fazem o uso de

feromônios para a comunicação diz respeito às características químicas destes marcadores,

seus vários componentes e suas respectivas volatilidades, considerando inclusive os efeitos

dos diferentes substratos onde os feromônios são dispostos.

Estudos com as formigas Argentinas Linepithema humile [55], mostram evidências com-

portamentais indicando que trilhas de feromônios verdadeiras podem ser multicomponentes

- este trabalho trata de aspectos químicos da composição do feromônio. Há indícios de que o

Z9-16:ALD é o principal componente, apesar de o Z7-16:ALD também fazer com que as for-

migas sigam as trilhas. Combinações destes dois aldeídos funcionaram produzindo respostas

mais fracas que o Z9-16:ALD sozinho. O Z9-16:ALD perde sua atividade em laboratório em

duas horas.

Apesar de as formigas poderem encontrar grandes concentrações de alimento através

do contato das antenas, é mostrado que as trilhas voláteis sozinhas induzem as formigas a

seguirem-nas, e que o contato das antenas não é necessário. A velocidade linear das formi-

gas não varia com a concentração de feromônio. Os dados de longevidade das trilhas de

65


Z9-16:ALD sintético demonstraram que a perda de atividade é rápida. Em contraste, foi veri-

ficado em estudos prévios que os extratos de glândulas naturais das formigas podem induzir

o seguimento de trilhas por até oito horas. Outros componentes menos voláteis podem ser

responsáveis pela extensão do tempo normal de vida de uma trilha.

Em Lesgreenberg & Klotz [56], é comentado o resultado de Van Vorhis Key, segundo

o qual as formigas poderiam seguir uma trilha volátil a uma distância de até 6 mm de sua

fonte. Além disso, o seguimento das formigas diminui quando a concentração de feromônio

cresce além do equivalente aos extratos de uma formiga por 50 cm de trilha, sugerindo que

altas concentrações de feromônio podem ser repelentes. Também ali é verificado que quando

o feromônio é depositado em papel filtro, a atividade diminui à metade do nível original em

aproximadamente quatro horas e encerra quase que completamente em aproximadamente em

oito horas.

Mailleux et al. (2001) [54] mostram que para a Lasius niger a seleção de um dentre dois

caminhos alternativos levando até o alimento, depende das propriedades físico-químicas dos

substratos que influenciam a longevidade das trilhas de feromônio. Com oito minutos no pa-

pel de jornal e 25 min no plástico policarbonato, os agentes apresentam uma escolha aleatória

na bifurcação marcada. A persistência depende da longevidade do feromônio e de outros fa-

tores, tais como o número de formigas que depositam feromônio na trilha, a intensidade dos

depósitos e as condições do ambiente. Além disso, a marcação das trilhas pode ser modulada

pelo tráfego e pelas características da fonte de alimento.

Jeanson et al. [57] publicaram um estudo experimental publicado em 2003 apontando

que o tempo de meia-vida do feromônio para a espécieM. pharaonis é estimado em aproxi-

madamente 9 min e 3 min, no plástico ou papel, respectivamente. Os resultados mostram

que o decaimento das trilhas é rápido e afetado fortemente pelo substrato. A duração do

feromônio daM. pharaonis é similar àquela de outras espécies que vagueiam pelo ambiente,

como a formiga argentina Linepithema humile, que se aproxima de 30 min. Ambas espécies

têm alimentação e aninhamento oportunísticos e desta forma provavelmente se beneficiam de

seus feromônios de curta duração, o que pode ser um fator de adaptação ao seu estilo de vida

vagueador. Ambas depositam feromônio durante a exploração do ambiente, mesmo antes de

acharem comida. O valor adaptativo deste comportamento pode depender do tempo de vida

do feromônio, reduzindo a plasticidade destas redes de exploração em busca de alimentos.

Entretanto, o potencial para a existência de componentes de longa duração nas trilhas da

66


formiga Pharaonis não pode ser descartado.

Apesar dos feromônios de curta duração permitirem um rápido abandono de fontes de

alimento esgotadas, eles requerem um contínuo fluxo de operárias para repor o feromônio

que decai, e trilhas de formigas só podem ser estabelecidas a uma nova fonte de alimento

com um número relativamente grande de formigas. Conseqüentemente, grandes colônias

poderiam estender a rede de exploração e em contraste, colônias menores estariam restritas

pela longevidade da trilha.

Hölldobler [10] afirma que a maioria dos semioquímicos de insetos consistem em diversos

componentes, onde diferentes compostos de um mistura complexa de feromônios pode ter

diferentes efeitos no receptor. Enquanto Jackson & Ratnieks [34] afirma que a especialização

na comunicação química para a busca de alimentos entre diferentes castas de trabalhadores

se estende além das trilhas de feromônio.

Em Solé et al. [58], para uma dada taxa de evaporação, taxas inferiores de depósito de

feromônio levam a uma maior flexibilidade, que pode ser útil quando se está lidando com

fontes de alimentos pequenas e espalhadas. Este trabalho também considera a saturação

de feromônio, com um limite máximo de feromônio (τ ), e uma evaporação obedecendo a

seguinte equação de decaimento:

φ(i, j) = (1− δ)φ(i, j). (3.4)

Millor et al. [59] também consideram a evaporação proporcional à concentração de fe-

romônio. Watmough & Edelstein-Keshet. [51] apresentam uma tabela com contendo alguns

parâmetros relevantes extraídos da literatura, como duração das trilhas, velocidade média

das formigas, taxa de decaimento das trilhas, taxas de formigas que perdem suas trilhas e que

encontram seus destinos.

Segundo Jackson & Ratnieks [34], nas formigas dos Faraós (Pharaoh’s ants) um conjunto

de feromônios complementam-se provendo memória de longo prazo das trilhas utilizadas

e memórias de curto prazo que atraem naquele momento as formigas para as trilhas mais

recompensadoras, bem como sinais de “Não Entre” nas trilhas não recompensadoras.

3.4.3 Feromônio “Não Entre”

Segundo Green [60], a evaporação de feromônio tem sido assumida como sendo o meca-

nismo regulatório do recrutamento em massa de formigas. Entretanto, através da discussão

67


tanto teórica quanto empírica, também verificada a existência de sinais de recrutamento ne-

gativos como mecanismos regulatórios.

Em Robinson et al. [9] são apresentadas evidências experimentais de que existe de fato

um feromônio que repele as formigas e é depositado na entrada de trilhas que não são recom-

pensadoras, melhorando o desempenho da colônia na busca de alimento.

3.5 Controle de Tráfego

Em Couzin & Franks [61] é mostrado como as regras de movimentação de indivíduos

(formigas) em trilhas podem levar a uma escolha coletiva da direção e formação de diferentes

padrões de tráfego que minimizam congestionamentos. São estudadas as habilidades das for-

migas (Eciton burchelli) de evitar congestionamentos e responderem a concentrações locais de

feromônio. Quando não estão evitando congestionamentos, as formigas respondem a concen-

trações locais de feromônio, a concentração nestes pontos é convertida numa intensidade de

estímulos. Estes estímulos crescem rapidamente com a concentração de feromônio, mas a taxa

de crescimento decresce quando o feromônio satura as antenas (Cmax). O modelo inclui uma

zona de percepção das formigas para evitar colisões. Os resultados do modelo sugerem que

as formigas do exército desenvolveram uma resposta comportamental que resulta geralmente

em uma tendência a todas se moverem na mesma direção ao longo das trilhas.

Pressupõe-se a existência de um estímulo visual para evitar colisões. Seja rp o campo

visual local (faixa tátil das antenas) de algumas espécies ou a faixa de curto alcance de per-

cepção olfatória em outras [61]. Assim, este modelo trata a formiga como um corpo extenso,

considera suas dimensões e atribui a cada formiga um ângulo de alcance (visual, sonoro ou

olfativo) para a detecção de outros indivíduos ou obstáculos. Também é considerado um ex-

perimento em um espaço aberto, onde as dimensões e geometria das trilhas de feromônio têm

importância no comportamento de cada formiga. Aspectos como o arrefecimento gradual ra-

dial da concentração de feromônio nas trilhas podem levar as formigas a oscilações ou mesmo

divergências em suas trajetórias.

Couzin & Franks [61] dão importância a evitar colisões entre os indivíduos: quando

as formigas não estão evitando colisões, respondem às concentrações locais de feromônio.

Também é analisado em detalhe o impacto das interações entre indivíduos na posição e des-

locamento de cada formiga. O comportamento coletivo das formigas também sugere o sur-

gimento de tendências ao alinhamento dos indivíduos em um mesmo sentido, à criação de

68


trajetórias circulares, quando as formigas estão em um ambiente confinado, e a criação de

raias (lanes) como opção de otimização do tráfego bidirecional.

Em Dussutour et al. [62] é apresentado um estudo experimental de formigas Lasius niger

confrontadas com duas rotas alternativas. Quando o tráfego é denso, é observado que as for-

migas que se movem em um dos ramos começam a colidir frontalmente com outras que vêm

no sentido oposto. É demonstrada a surpreendente funcionalidade das colisões entre formigas

para manter o nível de fluxo desejado pela geração de tráfego simétrico. O comportamento

de empurrar pode ser considerada uma opção ótima para manter a alta taxa de retorno de

alimento ao ninho. As simulações têm também demonstrado que se as formigas empurradas

ao invés de se mover para o outro ramo, fazem um retorno em U e voltam na direção que

vinham, o fluxo global de formigas atravessando as pontes é afetado pela largura dos ramos

e não há a mudança para o tráfego simétrico.

O trabalho de Denny et al. [63] apresenta um estudo experimental do comportamento das

formigas forrageiras em situações de aglomeração. Para tal, foi construído um experimento

onde é apresentado um caminho com uma bifurcação entre ninho e fonte. Com o tempo,

a largura do caminho é estreitada até a verificação da transição de tráfego assimétrico para

simétrico. Foi verificado que há um mecanismo de restauração da simetria. Um modelo

analítico foi construído para representar este comportamento. O motivo principal para a

assimetria verificada foi a presença de empurrões frontais entre formigas, o que acabam por

desviar formigas no contra-fluxo para o outro ramo da bifurcação. No modelo é assumido

que há um limiar para o qual a concentração de feromônio passa a ser efetiva. Foi verificado

que a atração baseada em feromônio gera uma trilha para baixas densidades de formigas,

enquanto que para altas densidades, uma segunda trilha é estabelecida antes que o volume de

tráfego seja afetado.

No trabalho de Dussutour et al. [64], são examinados os efeitos de congestionamentos

na organização temporal do fluxo de formigas. Dois tipos de pontes foram utilizadas: uma

com e uma sem estreitamento da passagem. A contagem de tráfego mostra que, apesar dos

estreitamentos e da redução do tamanho do caminho, o volume de tráfego e a taxa de retorno

de comida foram a mesma em ambas as pontes. Isto se deu devido à mudança na organização

temporal do fluxo. Quando o caminho diminui, alternados grupos de formigas em ambos os

sentidos são observados atravessando a ponte.

69


3.6 Discussão

Neste capítulo foram apontados diversas facetas do comportamento de insetos sociais que

dão uma idéia do grau de sofisticação e complexidade que pode estar por traz da adaptação

destes seres aos mais variados ambientes, inclusive os mais hostis. Os estudos discutidos

ajudam a compor um cenário mais realista sobre as potencialidades das formigas, e assim,

colaboram na proposição de modelos mais plausíveis.

Apesar das inúmeras evidências das diversas capacidades das formigas, busca-se neste

trabalho compor um conjunto mínimo de mecanismos possivelmente usados por estes inse-

tos para encontrar os melhores caminhos nos experimentos discutidos no capítulo anterior.

Ademais, para compor um modelo de formigas que seja apto a reproduzir o comportamento

observado nos experimentos em laboratório e que ao mesmo tempo possa inspirar o desenvol-

vimento de algoritmos robustos para solucionar problemas de otimização, foram ressaltadas

as características mais simples, ou melhor, as que, poderiam ser mais simplesmente modeladas

e transferidas às formigas artificiais.

Assim, apesar das dificuldades em se estabelecer se algumas assertivas encontradas na li-

teratura sobre os insetos sociais são válidas ou não para as formigas argentinas Linepithema

humile, usadas nos experimentos, as seguintes evidências chamam a atenção, por sua plausi-

bilidade e aplicabilidade:

• Comunicação Multimodal [10]. A maioria das espécies de formigas não usam exclusiva-

mente a comunicação feromonal. Elas também usam outros mecanismos, tais como batide-

las, estridulações, sacudidas e movimentos com as antenas, que podem modular o canal de

comunicação feromonal;

• Trilhas de feromônios Multi-componentes, i.e. as formigas produzem e depositam um co-

quetel de substâncias químicas de diferentes odores e volatilidades, que podem comunicar

informações bem mais complexas do que simplesmente indicar o caminho aonde a comida

está [13, 55];

• Feromônio Repelente (“Não Entre”) [60, 65], que ao invés de atraírem formigas para uma

determinada fonte de alimentos, fazem o efeito inverso, indicando que uma determinada

trilha não é recompensante, e assim, repelindo seus pares;

• Efeito das aglomerações, quando uma formiga se depara com uma bifurcação onde um dos

ramos está lotado de formigas, aglomerado, ela tende a evitar este ramo [12, 66, 67], ou

70


mesmo a ser desviada através de empurrões para o ramo menos ocupado [68]. Isto leva a

um balanceamento do tráfego;

• Comportamento Exploratório, i.e., quando os insetos se deparam com um novo terreno,

eles começam a recrutar seus pares para explorar cada nova parte da área de forrageio [35].

Similarmente, experimentos com baratas em ambientes confinados mostram que quando

uma nova área (túnel) é inserido em seu ambiente, elas tendem a explorar este novo cami-

nho, em detrimento dos caminhos já conhecidos [69]. Em ambos os casos, a exploração do

novo é acompanhada do depósito de feromônio para recrutamento;

• Estratégias de Navegação basedas na integração de caminhos e no reconhecimento visual de

marcos [41, 42]. As formigas do deserto, até pela precariedade da comunicação feromonal

neste ambiente, desenvolveram técnicas para construção de um mapa cognitivo do ambiente

de forrageio que utiliza os marcos visuais em sua construção;

• Saturação das antenas e existência de uma concentração mínima de feromônio, necessária

para provocar algum efeito nas decisões das formigas, determinando limites às capacidades

sensoriais das formigas. Se o nível feromonal de uma trilha estiver abaixo de um deter-

minado limite inferior, as formigas simplesmente ignorarão a trilha; por outro lado, existe

um nível máximo da concentração a partir do qual, não importa o quanto a concentração

aumente, as formigas se comportam da mesma maneira [55, 70–72].

No próximo capítulo, são discutidos como e quais destas características podem ser apro-

veitadas para compor um modelo que reproduza o comportamento das formigas verificados

nos experimentos com o ambiente dinâmico, superando o problema da estagnação observado

no modelo FFAC.

71

Capítulo IV

Modelagem doComportamento das Formigas

em Ambientes Confinados eDinâmicos

All models are wrong, but some are useful.

—George Box

Com base nas evidências de características dos insetos reveladas no Capítulo 3, é pos-

sível modelar mecanismos que uma vez inseridos no comportamento das formigas

artificiais, ajudem-nas a superar o problema da estagnação discutido no Capítulo 2. Todas

as características apontadas no capítulo anterior ajudaram a melhorar a compreensão das

potencialidades nos insetos, no entanto, apenas um conjunto mínimo de mecanismos foram

necessários à implementação de um Modelo de Formigas Forrageiras em um Ambiente Con-

finado e Dinâmico - FFAC-D.

Dentre as possibilidades discutidas no capítulo anterior, três foram consideradas apropri-

adas para superar o problema da estagnação verificado no Modelo FFAC e assim reproduzir

o comportamento evidenciado nos experimentos:

• Efeito das aglomerações;

• Comportamento Exploratório, e;

• Saturação das antenas;

Portanto, apenas estas características são explicitamente incluídas no modelo para Formi-

gas Forrageiras em um Ambiente Confinado e Dinâmico (FFAC-D). Além disto, a evaporação

————Modelagem do Comportamento das Formigas em Ambientes Confinados e Dinâmicos————

do feromônio foi considerada relevante, diferentemente do que considerou-se no desenvolvi-

mento do FFAC [1], e foi inserida no modelo FFAC-D.

4.1 Depósito e Percepção de Feromônio

Considerando que o sistema sensorial das formigas necessita de uma concentração mínima

de feromônio para influenciar suas decisões [70] e que, similarmente, um nível de saturação é

biologicamente plausível, então, a taxa constante de depósito (considerada linear no modelo

FFAC), foi substituída por uma equação não linear, sigmoidal, representando a saturação da

percepção das formigas [70].

Assim, no Modelo FFAC-D, há uma limite para a máxima concentração de feromônio

(Cmax) para cada ramo. Então, a diferença dos níveis concentração de feromônio entre os

caminhos escolhidos é reduzida. Isto evita a ocorrência de caminhos marcantemente domi-

nantes, que podem causar estagnação. No Modelo FFAC-D, a concentração de feromônio em

um ramo i cresce suavemente, enquanto as formigas depositam feromônios de acordo com a

Eq. 4.1.

Ci[k + 1] = Ci[k] + ε(∆Ci[k]) (4.1)

onde Ci[k] representa a quantidade de feromônio depositada em um ramo i no instante k,

0 ≤ ε ≤ 1, e

∆Ci[k] =

Cmax − Ci[k], if Cmax ≥ Ci[k];

0, caso contrário.(4.2)

Não será considerado neste modelo, a distinção entre detecções de feromônio que afetam e

que não afetam as decisões das formigas [71]. Além disto, os limites impostos às concentrações

de feromônio pelo substrato aonde as substâncias são depositadas estão consideradas nas

equações que governam os depósitos de feromônio.

4.1.1 Evaporação de Feromônio

A evaporação dos componentes mais voláteis dos feromônios, as influências do substrato

e da velocidade do ar, dentre outros fatores, podem influenciar a percepção feromonal das

formigas. Além disso, o efeito do recrutamento químico das formigas Linepithema humile, em

73


condições de laboratório, são mínimos após transcorrido um intervalo de tempo entre 30 e 60

min [13, 36, 55], apontando que a consideração da evaporação pode ser bastante relevante.

Ratnieks et al. [13] argumentam que o tempo de meia-vida do feromônio de uma formiga

da espécie M. pharaonis é de aproximadamente nove minutos em um substrato plástico e três

minutos em um substrato de papel. A duração do feromônio da M. pharaonis é supostamente

similar ao da formiga argentina Linepithema humile devido às suas características de locomo-

ção similares. Ambas as espécies apresentam aninhamento oportunístico e provavelmente se

beneficiam da curta duração, alta volatilidade, de seus feromônios. Apesar disso, há também

evidências da presença de componentes de longa duração nestes feromônios [10].

Em Solé et al. [73], para uma dada taxa de evaporação, uma baixa taxa de depósito de

feromônios pode levar a uma maior flexibilidade, especialmente útil quando se trata de fontes

de alimentos espalhadas pelo ambiente. Eles também limitam a concentração de feromônio

a um nível limite de saturação (Cmax), e definem o decaimento das concentrações imposto

pela evaporação como na Eq. 4.3. Halloy et al. [14] também consideram a evaporação

proporcional à concentração de feromônio.

Ci[k + 1] = Ci[k]γ (4.3)

esta equação se aplica sempre que Ci > Cmin, sendo γ uma constante, 0, 92 ≤ γ ≤ 1. A Eq.

4.3, conforme usada no Modelo FFAC-D, é bem estabelecida na literatura [70], sobretudo por

sua simplicidade.

4.1.2 Mecanismo Exploratório

Um componente aleatório observado nas decisões das formigas é supostamente responsá-

vel por ajudá-las a adaptarem-se às mudanças no ambiente. E com o objetivo de reproduzir

este nível de aleatoriedade, o Critério Metropolis foi acrescido ao Modelo FFAC por Vittori

[1]. O Critério Metropolis constitui a base da técnica heurística conhecida como recozimento si-

mulado. Esta estratégia tem sido aplicada com sucesso em problemas de otimização, e ajuda os

algoritmos a evitarem ótimos locais. Com a incorporação do Critério Metropolis ao Modelo

FFAC, as escolhas das formigas nas bifurcações i−j, provenientes de um ramo l podem diver-

gir das decisões baseadas na geometria e na concentração de feromônio, conforme Eq.(2.9).

No entanto, somente o Critério Metropolis não foi suficiente para levar o o Modelo FFAC

reproduzir satisfatoriamente a capacidade exploratória das formigas observada durante as si-

74


tuações experimentais 2 e 3. Além disso, é importante notar que Γ[k] foi definida em FFAC

como uma variável global, violando portanto a característica de controle distribuído, onde os

agentes tomam decisões apenas com base em informações locais. Esta característica é con-

siderada bastante relevante para os Algoritmos de Formigas e para a meta-heurística ACO

[1, 5].

A dispeito do Critério Metropolis, considerado no Modelo FFAC para a escolha de ca-

minhos, as preferências das formigas em bifurcações com concentrações de feromônio muito

desequilibradas entre os ramos i e j, apresentam uma clara tendência no sentido de escolhe-

rem o ramo com as mais altas concentrações. Esta tendência é gradualmente amplificada e

surgem os caminhos fortemente dominantes, soluções ótimas locais que atraem o sistema e

evitam a busca pelo ótimo global.

Apesar de o Critério Metropolis não ter conseguido resolver o problema da estagnação

para as situações dinâmicas e ainda ter introduzido uma variável global, indesejável, no Mo-

delo FFAC, algumas idéias podem ser aproveitadas. Foi com base no Critério Metropolis, que

foi desenvolvido o Mecanismo Exploratório presente no Modelo FFAC-D. Similarmente ao

Critério Metropolis, no Modelo FFAC-D, o Mecanismo Exploratório foi introduzido como

um estágio de decisão adicional ao processo de escolha do caminho que caracteriza-se por uma

probabilidade de se mudança na decisão com base na concentração de feromônio e geometria

do ambiente, apontada pela Eq.2.9. Tal probabilidade depende de dois componentes:

• Percepção de aglomeração no ramo escolhido (ϕcrowd), ou;

• Detecção de novidade na área de forrageio (ϕnovelty);

A probabilidade E[k] de uma formiga escolher um ramo subseqüente diferentemente do

resultado da Eq. 2.9, é definida na Eq.4.4:

E[k] = ϕcrowd[k] + ϕnovelty[k], (4.4)

onde os componentes representam a capacidade de evitar aglomerações ϕcrowd[k], e a percep-

ção de novidade ϕnovelty[k], no instante k. Como um ramo “novo” nunca estará aglomerado,

estes componentes são mutuamente exclusivos e sua soma é limitada a um.

Condição de Aglomeração

Há uma diferença sutil, mas importante, entre a percepção do fluxo de formigas em um

determinado ramo, conforme considerado no Critério Metropolis do Modelo FFAC, e o nú-

75


mero de formigas presentes em um determinado ramo. O fluxo, pressupõe o conhecimento

do histórico do ramo, conforme exposto em [1], enquanto o número de formigas presentes

em um determinado ramo conta apenas com a percepção visual da formigas no instante em

que ela se depara com a bifurcação. A condição de aglomeração considerada aqui leva em

consideração apenas o número de formigas presentes em cada ramo da bifurcação no instante

da decisão, e usa portanto, apenas informações locais.

As formigas são capazes de detectar visualmente e evitar as aglomerações [10, 41, 68].

Nos experimentos reportados em Vittori et al. [15], aglomerações ocorrem quando um ramo

é bloqueado, porque as formigas param e esperam por algum tempo diante do bloqueio antes

de retornarem. Neste caso, mesmo se o fluxo de formigas no ramo i não for alterado, uma

pequena aglomeração ocorre, e as formigas da bifurcação i− j devem supostamente evitar o

ramo i, independentemente de sua geometria ou concentração de feromônio. Para modelar

este comportamento, foi introduzido no modelo FFAC-D a Eq.4.5:

ϕcrowd[k] = exp (Ωi[k]− Ωmax

i

Γ) (4.5)

onde Γ é um parâmetro de ajuste da curva, regulando a suavidade do mecanismo; Ωi[k] é o

número de formigas presentes no ramo escolhido i no instante k, e; Ωmaxi é o limite superior

do número de formigas permitido no ramo, antes que as formigas comecem a evitá-lo por

estar aglomerado. Ωmaxi depende da largura do ramo, i.e. quanto mais estreito é i, menor é

Ωmaxi . Como o ambiente de simulação possui todos os ramos de mesma largura, então todos

os ramos possuem o mesmo Ωmax.

Percepção e Exploração da Novidade

Na terceira situação experimental, todos os ramos são desbloqueados quando as formigas

já estão seguindo um caminho longo, onde está estabelecida uma trilha de feromônio. Neste

caso, as formigas se deparam com uma modificação na topologia do ambiente, o desbloqueio

dos ramos, e devem decidir entre explorar os novos caminhos, ou seguir a trilha de feromônio

estabelecida. Nos experimentos reportados na literatura [35, 69], insetos reais mostraram um

comportamento exploratório acentuado, tendo sido atraídos pelas novas trilhas. Acredita-se

que um comportamento similar pode ter ocorrido nos experimentos de [15].

De acordo com Hölldobler & Wilson [35], as formigas Atta Cephalotes apresentam um

comportamento exploratório quando se deparam com uma “novidade” no seu terreno. Höll-

76


dobler [10] associa a novidade no ambiente à ausência de feromônio. Ou seja, a componente

exploratória do comportamento dos insetos aumenta quando estes se deparam com uma área

livre de feromônio.

No Modelo FFAC-D, quando um ramo previamente bloqueado é desbloqueado, ele su-

postamente não possui feromônio depositado, diferentemente de qualquer outro ramo que já

tenha sido visitado. Assim, uma componente exploratória seria ativada no comportamento

das formigas quando estes ramos fossem desbloqueados. Entretanto, conforme visto nos

experimentos, a percepção da novidade é comum a um grupo de indivíduos, e não apenas

àquele primeiro indivíduo que se deparou com o novo ramo e ali depositou feromônio. Logo,

quando uma formiga detecta um “novo” ramo, ela sinaliza a descoberta a seus pares através

de uma espécie de feromônio diferente, o feromônio da novidade ϕnovelty, que possui volati-

lidade maior que o feromônio tradicional. A percepção deste sinal ativa nas outras formigas

o mesmo comportamento exploratório, e estas são também atraídas para o ramo “novo”. O

feromônio da novidade (ϕnovelty) atinge seu valor máximo quando a primeira formiga detecta

a novidade (ramo livre de feromônio) na área de forrageio e gradualmente vai evaporando.

Quanto maior o valor de (ϕnovelty) num determinado ramo, maior é o componente explora-

tório das formigas.

Seja k0 o instante onde há a detecção da novidade, ou seja, o instante em que a primeira

formiga chega a bifurcação que contém o ramo l “novo”, a concentração de feromônio Cl ali

é zero. Então a formiga deposita o feromônio da novidade. Neste instante tem-se:

ϕinovelty[k0] = ϕmax

novelty (4.6)

Depois, a cada instante k, este feromônio evapora a uma taxa proporcional a sua concen-

tração, com um fator φ (0 < φ ≤ γ < 1), de acordo com a Eq. 4.7:

ϕnovelty[k] = ϕnovelty[k − 1]φ (4.7)

4.1.3 Parâmetros do Modelo FFAC-D

A Tabela 4.1 mostra os parâmetros usados com maior sucesso nas simulações do Modelo

FFAC-D. Os parâmetros para o recrutamento (Fmax, F0 e τ ) e para a escolha de caminhos

(κ, n e rpref ) são os mesmos utilizados nas simulações do Modelo FFAC, uma vez que estes

foram estimados a partir dos experimentos, e se mostraram adequados nas simulações, repro-

77


duzindo o comportamento das formigas naturais. Similarmente, os parâmetros para o tempo

despendido sobre a fonte de alimento (Ξ), o retardo perante os ramos bloqueados (B e ∂), e

o deslocamento das formigas (V e Θ) foram medidos diretamente a partir dos experimentos e

replicados nas simulações do FFAC-D.

Em relação aos parâmetros que governam o depósito e percepção do feromônio, os limites

de saturação e de mínima sensibilização das antenas, Cmax e Cmin respectivamente, foram

escolhidos com base nas simulações do modelo FFAC para a primeira situação experimental,

que reproduziu com sucesso os resultados experimentais. Estes parâmetros foram ajustados

para evitar a estagnação, i.e. os valores deveriam inibir altas discrepâncias entre a concentra-

ção de feromônio depositada entre os ramos durante o período de simulação. Em seguida, os

parâmetros de ajuste de curva ε foi ajustado através de tentativa e erro, para permitir uma

acumulação suave de feromônio nos ramos, diminuindo assim a estagnação. A intensidade da

volatilidade γ foi também ajustada por tentativa e erro dentro das proximidades das volatili-

dades reportadas na literatura, por exemplo, se o tempo de meia-vida do feromônio é 9 min,

então γ ≈ 0, 998 [13]. Apesar do intuito de proporcionar uma equivalência entre o feromô-

nio natural e o depositado pelas formigas do Modelo FFAC-D, o valor γ = 0, 98 mostrou

melhores resultados, provavelmente devido ao fato de as formigas naturais possuírem outros

mecanismos que deixam suas respostas aos feromônios menos intensas.

Finalmente, para o Mecanismo Exploratório, no que diz respeito à aversão às aglomera-

ções, o parâmetro Ωmax foi primeiramente estimado com base no número máximo de for-

migas observadas sobre cada ramo durante as simulações do Modelo FFAC-D sem o Me-

canismo, e em seguida o parâmetro Γ foi ajustado empiricamente por tentativa e erro. Os

parâmetros da percepção da novidade, tanto o que diz respeito ao depósito do feromônio

da novidade, ϕmaxnovelty, quanto o de sua evaporação, φ, foram ajustados independentemente

com o intuito de reduzir o efeito da estagnação na terceira situação experimental. Enquanto

o valor ϕmaxnovelty = 0, 5 estimula fortemente a exploração dos ramos desbloqueados, o valor

φ = 0, 98 leva a um decaimento rápido deste feromônio e, conseqüentemente nas chances de

as formigas mudarem suas escolhas devido a ele. Estes valores levaram o modelo FFAC-D aos

melhores resultados.

78


Tabela 4.1: Tabela de Parâmetros do FFAC-D

Função Parâmetro Valor Origem

Recrutamento Fmax 0,42/s

F0 5x10−4s Estimado

τ 127,4s dos

Escolha de κ 20 experimentos

caminhos n 4

rpref 0,74

Tempo na fonte Ξ 179,9 s

Retardo no B 100s Medidos

bloqueio ∂ 2,09 s a partir

Deslocamento V 1,06 cm/s dos experimentos

Θ 0,34

Depósito de Cmax 100

feromônio Cmin 5

ε 0,05 Valores

Evaporação γ 0,98 empíricos

Mecanismo Γ 0,98

Exploratório Ωmax 10

ϕmaxnovelty 0,5

φ 0,98

4.1.4 Pseudo-código do Modelo FFAC-D

O algoritmo 1 descreve a rotina principal para a simulação do modelo FFAC-D. As formi-

gas tomam suas decisões com base apenas em informações locais, não há nenhum mecanismo

para que as formigas evitem loops. As formigas tampouco possuem memória, simplesmente

depositam feromônio, escolhem seus caminhos com base na geometria e nas trilhas de fe-

romônios estabelecidas e nos eventos que, quando percebidos, acionam seus mecanismos ex-

ploratórios, quais sejam aglomeração em um dos ramos ou “novidade”. O comportamento

idividual das formigas no que diz respeito aos seus deslocamentos, paralizações na fonte de

alimentos e retardos nos bloqueios, bem como o mecanismo de recrutamento, permanecem

semelhantes àqueles apresentados no modelo FFAC [16].

79


Inicializa Rotina Principal do Algoritmo FFAC-D ;

para cada passo da simulação k← 1 to 3.600 façaAtualize( Topologia (ramos bloqueados e desbloqueados)) ;Cal ule( probabilidadeR[k] de gerar uma nova formiga (Eq. 2.3)) ;Gere número aleatório( ζ) ;

se o número ζ ≤ R[k] entãoExe ute(recrutamento de uma nova formiga para o ambiente de forrageio) ;

fim se

para cada formiga z presente no ambiente façaCal ule(deslocamento (Eqs. 2.4 e 2.5) de z e move z) ;Deposite(feromônio de acordo com a Eq. 4.1) ;

se a formiga z está em uma bifurcação então

se a bifurcação está livre de feromônio entãoDeposite(feromônio da novidade no ramo livre de feromônio (Eq. 4.6));

fim seCal ule(probabilidadesPi e Pj de escolha dos ramos i ou j, respectivamente (Eq.2.9)) ;Cal ule(probabilidadeE, de acordo com o Mecanismo Exploratório (Eqs.4.4, 4.5 e 4.6)) ;Gere número aleatório( 1 ≥ χ ≥ 0) ;

para χ < E façaEs olha( o ramo com maior probabilidade (i, se Pi < Pj , e j, caso contrário)) ;

fim para

senão se χ ≥ E entãoEs olha( o ramo com a menor probabilidade (i, if Pi ≥ Pj , e j, caso contrário)) ;

fim se

se o ramo escolhido está bloqueado entãoEspere( tempo no bloqueio de acordo com a Eq. 2.7) ;

fim se

fim se

senão se a formiga z está na fonte de alimento entãoEspere( tempo de acordo com a Eq. 2.6 e mude sua direção) ;

fim se

senão se a formiga z chegou de volta ao ninho entãoElimine(a formiga z) ;

fim se

fim para cadaEvapore(feromônio em todos os ramos do ambiente (Eqs.4.3 e 4.7)) ;

fim para cadaAlgoritmo 1: Rotina Principal do Algoritmo FFAC-D

80


4.2 Resultados

Primeiramente, o modelo FFAC foi implementado em ANSI C de modo a reproduzir os

resultados reportados por [16]. Em seguida, as alterações no Modelo FFAC foram gradual-

mente introduzidas, incluindo as características do Modelo FFAC-D, e permitindo a análise

do comportamento das formigas. Com isto, foi verificada a cada modificação, a melhoria

na habilidade das formigas em adaptarem-se às modificações do ambiente. Os resultados

são discutidos em seguida e consistem nas análises dos caminhos escolhidos pelas formigas, e

foram computados de modo a permitir a comparação com o o Modelo FFAC e com as me-

dições experimentais. Os possíveis caminhos do dispositivo utilizado nos experimentos e nas

simulações (Fig. 2.1) foram categorizados por seus comprimentos de acordo com a Tabela

2.1.

4.2.1 Resultados do Modelo FFAC-D para a Primeira Situação Experimental

A Figura 4.1 mostra a freqüência de escolhas das formigas para cada uma das categorias de

caminhos, classificados de acordo com seu comprimento, em vários instantes das simulações

do Modelo FFAC-D, onde k mostra o número de iterações, para o Modelo FFAC em k =

3600 e para os experimentos após uma hora de observações. Conforme ilustrado na Fig.

4.1, as escolhas das formigas ao longo das simulações mostram que há uma tendência do

modelo em se estabilizar, como nos dados experimentais. O maior percentual de escolhas é

dos caminhos menores, seguido de caminhos médios e de loops, tanto em formigas naturais

quanto nas artificiais. As maiores discrepâncias são encontradas na direção ninho-fonte de

alimento, quando as formigas artificiais mostram maior preferência por caminhos médios e

menor freqüência de loops que as formigas naturais.

4.2.2 Resultados do Modelo FFAC-D para a Segunda Situação Experimental

Antes de o ramo 3a (ou 6a) ser bloqueado, no instante k = 1800, as formigas obviamente

se comportam de maneira similar à primeira situação, i.e. preferindo os caminhos curtos e

com um taxa decrescente de loops. Depois do bloqueio, o número de formigas que tomam

rotas inválidas (loops) aumenta, então gradualmente as rotas médias começam a ser mais esco-

lhidas e em a taxa de loops começa a diminuir, conforme mostrado na Fig. 4.2(a). O Modelo

FFAC-D reproduz tal comportamento muito precisamente, apesar de uma pequena deficiência

remanescente na replicação do número de formigas que tomam caminhos longos no trajeto

81


Figura 4.1: Freqüência de escolha de caminhos nos modelo FFAC e FFAC-D e nos experimentos, na Situação 1,

nas direções (a) ninho-fonte de alimento e (b) fonte de alimento-ninho. Para Modelo FFAC-D, há valores para os

passos de tempo 1000, 1800, 2700 e 3600.

ninho-fonte. Na direção contrária, fonte-ninho, uma pequena discrepância é observada para

rotas muito longas, conforme ilustrado na Fig. 4.2(b). Ademais, é possível observar a conver-

gência da preferência das formigas depois que as mudanças no ambiente ocorrem.

Figura 4.2: Freqüência de escolha de caminhos nos modelo FFAC e FFAC-D e nos experimentos, na Situação 2,

nas direções (a) ninho – fonte de alimento e (b) fonte de alimento – ninho.

4.2.3 Resultados do Modelo FFAC-D para a Terceira Situação Experimental

O Modelo FFAC-D, diferentemente do FFAC, reproduziu acuradamente o comportamento

das formigas observado em laboratório, conforme ilustrado na Fig. 4.3. Depois do desblo-

queio (30 min) é possível observar que não ocorreu estagnação nas simulações. As formigas

82


que estavam anteriormente seguindo uma rota longa aprenderam e se redistribuíram em ca-

minhos médios, curtos ou “loops”. Com o decorrer do tempo, durante as simulações, as

formigas acham e os menores caminhos disponíveis e começam a escolhê-los, mantendo esta

tendência até o final das simulações. Tais observações são muito similares às medições dos

experimentos, apesar de as formigas naturais apresentarem ainda taxas de “loops” menores.

Vale à pena observar na Fig. 4.3(a) que as formigas naturais mantêm o mesmo percentual de

escolhas pelos caminhos longos, enquanto reduziram suas escolhas por caminhos médios de-

pois do desbloqueio. Tal comportamento não foi claramente explicado e não foi reproduzido

nos Modelos FFAC e FFAC-D.

Na direção alimento-ninho, as simulações mostraram bons resultados, conforme a Fig.

4.3(b). Então, mais uma vez, as formigas mostraram um comportamento intrigante, o desblo-

queio reduziu a ocorrência de rotas longas. Entretanto,as formigas optaram pelos caminhos

longos nos últimos 15 min dos experimentos. Este comportamento também não foi comple-

tamente reproduzido nas simulações.

Figura 4.3: Freqüências de escolhas do Modelo FACC, FFAC-D e nos experimentos, na situação 3, na direção (a)

ninho-alimento, e, (b) alimento-ninho.

4.3 Discussão

O Modelo FFAC-D mostrou-se habilitado a reproduzir com boa fidelidade o compor-

tamento da formiga argentina Linepithema humile, conforme observado em laboratório. As

formigas mostraram capacidade auto-organização e adaptação, escolhendo os menores cami-

nhos disponíveis até a fonte de alimento mesmo em situações de mudanças na topologia do

83


ambiente, com a inserção ou remoção de bloqueios em caminhos estratégicos durante as si-

mulações. O FFAC-D mostra avanços em relação ao modelos anterior proposto por Vittori et

al. [16], sobretudo porque superou o problema da estagnação, ou seja, as formigas não mais

se atém a uma rota previamente estabelecida, elas mantém uma boa capacidade de exploração

de novas soluções, ao mesmo tempo em que reforçam as menores rotas.

Para que uma formiga do FFAC-D se comporte semelhantemente a uma formiga real, foi

inserido em seu comportamento uma componente exploratória, que é disparada sempre que

esta depara-se com congestionamentos ou novidades em sua área de forrageio. Ademais, as

formigas do FFAC-D mostram limitações sensoriais e depósito de taxa variável de depósito

feromônios, o que não ocorre com as formigas do modelo proposto por Vittori et al. [16], o

FFAC.

Apesar do sucesso na reprodução do comportamento observado nos experimentas, nem

todas as características do FFAC-D foram extraídas de evidências científicas extraídas de estu-

dos da espécie Linepithema humile, e outros experimentos são necessários para validar algumas

premissas adotadas na modelagem do FFAC-D, e checar outras predições do modelo. Além

disso, a versão atual do modelo foi bastante orientada à topologia do dispositivo experi-

mental (Fig. 2.1), com bifurcações do tipo i − j e apenas uma fonte de alimento para cada

experimento. Pesquisas futuras, com outros aparatos experimentais podem revelar outras ca-

racterísticas das formigas e levar a uma grande generalização do modelo. Outro aspecto im-

portante a ser explorado em uma pesquisa futura é a análise de sensibilidade dos parâmetros

do modelo. Nas simulações reportadas neste capítulo, muitos parâmetros foram ajustados

empiricamente.

Tendo em vista a aplicação do FFAC-D e seus mecanismos à solução de problemas de

otimização, as premissas adotadas em seu projeto não comprometem a a plausibilidade bi-

ológica do modelo, e pode ajudar outros modelos a superarem o problema da estagnação

[70]. O modelo FFAC-D foi projetado com vistas à solução de um problema prático, qual

seja, a implementação de um algoritmo de roteamento robusto e apto a lidar com uma rede

de topologia dinâmica. A inserção e remoção de bloqueios nos ramos do ambiente de forra-

geio são análogos às falhas intermitentes em enlaces de uma rede de comunicação, quando os

algoritmos de roteamento dinâmico mais são requisitados.

Também foi buscado na implementação do FFAC-D, um controle completamente distri-

buído, baseado apenas em informações locais, i.e. as formigas não dependem de nenhuma

84


informação global sobre o sistema, e todas as decisões podem ser feitas assincronamente. As

formigas do FFAC-D também não necessitam de qualquer memória, logo um algoritmo de

otimização baseado no FFAC-D deve ser simples e computacionalmente parcimonioso. A

próxima parte desta dissertação tratará exatamente da aplicação dos princípios presentes no

modelo FFAC-D ao problema de roteamento.

85

Capítulo V

Revisão Bibliográfica sobreAlgoritmos de Roteamento

Baseados em FormigasCommunication is the action on the part of one

organism (or cell) that alters the probability pat-

tern of behavior in another organism (or cell) in a

fashion adaptive to either one or both of the par-

ticipants.

—Bert Hölldobler

Um Algoritmo de Formiga (AF) pode ser informalmente definido como um sistema multi-

agentes inspirado no comportamento de formigas reais. Em um AF os agentes são

chamados de formigas artificiais ou simplesmente formigas, e a coordenação entre elas se dá

através da exploração dos mecanismos de comunicação estigmérgica. Um caso particular de

AF foi inspirado no comportamento de formigas forrageiras e em como se auto-organizam

para alimentar seu ninho [2, 5, 17]. O Ant System (AS) foi o primeiro algoritmo inspirado

no comportamento de depósito e seguimento de feromônio e aplicado a um problema de

otimização discreta, o problema do caixeiro viajante (Traveling Salesman Problem – TSP). O

AS obteve bom desempenho quando comparado a outras meta-heurísticas de propósito geral,

tal como Recozimento Simulado, a Computação Evolucionária e a Pesquisa Tabu, de modo

que deu origem a um conjunto de aplicações bem sucedidas e extensões que compuseram uma

nova classe de meta-heurísticas chamada de Otimização de Colônias de Formigas, ou, ACO

(Ant Colony Optimization), que consistem na aplicação da inteligência das formigas forrageiras

aos problemas de otimização [2, 5, 11, 17].

———— Revisão Bibliográfica sobre Algoritmos de Roteamento Baseados em Formigas————

Entre as diversas aplicações do ACO, uma classe particular de problemas de otimização

combinatória chama a atenção: o problema do roteamento de pacotes, ou seja, a entrega

de mensagens discretas em uma rede de comunicações. Um algoritmo que aplica a meta-

heurística ACO na solução do roteamento de pacotes é chamado ANTRAL (Ant Routing Al-

gorithm). Os agentes móveis, ou formigas, movem-se na rede e são usados para atualizar as

tabelas de roteamento de maneira assíncrona e independente [20]. Diversos ANTRALs foram

propostos nos últimos dez anos, apontando em diversas implementações desempenho supe-

rior aos algoritmos de roteamento convencionais, tais como o Link State ou Distance Vector,

que são utilizados nos protocolos OSPF e RIP, respectivamente [11, 17, 20–22].

Neste capítulo são discutidos alguns dos ANTRALs mais importantes, de modo que seja

possível estabelecer o panorama que servirá de plano de fundo para o Capítulo 6, onde é

proposto um novo ANTRAL. A organização deste Capítulo se dá da seguinte maneira:

• Na Seção 5.1 apresenta-se meta-heurística ACO e sua aplicação ao roteamento. Apresenta-se

também os ANTRALs e suas principais características;

• Na Seção 5.2 é apresentado o ABC (Ant Based Control), o primeiro ANTRAL reportado na

literatura;

• Na Seção 5.3 introduz-se o AntNet, que é o mais notável ANTRAL e também o que inspira

o maior número de outros algoritmos. O Antnet superou o desempenho dos tradicionais

algoritmos de roteamento dinâmico DV (Distance Vector) e LS (Link State), e serve como

benchmark para outros ANTRALs;

• Na Seção 5.4 é feita uma compilação de trabalhos relacionados aos ANTRALs, o que deixa

transparecer as principais linhas de pesquisa nesta área, objetivos e motivações;

• Na Seção 5.5 Faz-se uma discussão do capítulo como um todo, destacando os pontos de

maior relevância, que podem subsidiar a engenharia de um novo ANTRAL baseado no

FFAC-D.

5.1 O ACO e os ANTRALs

A principal característica da meta-heurística ACO é a analogia com as formigas reais, em

particular, o uso de: (i) uma colônia de indivíduos cooperativos; (ii) trilhas de feromônios (ar-

tificiais) para a comunicação estigmérgica local; (iii) uma seqüência de deslocamentos locais

para que se encontre os menores caminhos, e; (iv) uma política estocástica de decisão com

87


base apenas na informação local [74] [75]. Vale mencionar que, pelo uso da metáfora de for-

migas artificiais em problemas de otimização, várias características e habilidades das formigas

biológicas são omitidas, além do que, outras técnicas (tais como funções heurísticas) podem

ser usadas para complementar as necessidades dos algoritmos. As principais atividades de um

algoritmo ACO são:

• Recrutamento (ou geração) de formigas: Controla a entrada de formigas no ambiente de

forrageio. O número de formigas tem impacto direto na dinâmica do algoritmo;

• Atividades das formigas: Essencialmente uma formiga tem que se mover ao longo da área

de forrageio e tomar decisões baseadas nas informações locais, incluindo a percepção e

depósito de trilhas de feromônio. Entretanto, as formigas podem possuir capacidades adi-

cionais como decisões baseadas em memória, (visão panorâmica (lookahead), otimização

local, memorização do caminho, etc.);

• Evaporação do feromônio: Faz com que as formigas lentamente apaguem seu passado re-

moto, de modo que possam direcionar suas buscas em novas direções, sem estarem restritas

às soluções bem sucedidas anteriormente [11];

• Ações daemon: A meta-heurística ACO, como um todo, pode também compreender alguns

componentes extras, que usam informações globais e que não podem ser acionados por

simples formigas [17];

• Atividades agendadas: Porque as atividades acima precisam de algum tipo de sincronismo

entre si.

Na perspectiva da engenharia, as características mais relevantes de um ACO são adapta-

ção, robustez e controle distribuído. Estas características vêm com a capacidade de agentes

independentes encontrarem soluções globais para problemas complexos de otimização atra-

vés de regras simples de decisão, baseadas em informações locais. O conhecimento da colônia

é codificado no ambiente. O sistema não depende dos indivíduos de maneira individual, mas

sim coletivamente, de sua comunicação indireta em massa.

São diversas as aplicações para o ACO, dentre as quais estão: o problema do caixeiro

viajante (TSP - Traveling Salesman Problem), alocação quadrática, agendamento, roteamento de

veículos, ordenamento seqüencial, colorimento de grafos, busca de super-seqüências comuns,

alocação de freqüência, alocação generalizada, múltipla mochila (multiple knapsack), rotea-

mento em redes de comunicações ópticas, alocação de redundâncias, e roteamento de pacotes

88


ANTRAL (Ant Routing Algorithms) para redes orientadas ou não à conexão [17].

5.1.1 Pseudo-código geral do ACO

O pseudo-código geral para o ACO compreende sua rotina principal e duas sub-rotinas

pré-formatadas, conforme mostrado no Algoritmo 2. A rotina principal estabelece a execução

de cinco sub-rotinas:

1. O agendamento de atividades –Necessário para que o algoritmo dispare todos os proce-

dimentos pré-programados, tais como a geração de formigas, a evaporação de feromônio

a atualização e outras atividades específicas previstas no algoritmo, como por exemplo

o reencaminhamento de formigas e atualização das tabelas de rotas;

2. A geração e ativação de formigas – Atividade pré-agendada, normalmente condiciona-

das a disponibilidade de algum recurso (e.g. formigas disponíveis no ninho) e executada

em intervalos regulares de tempo. É responsável pelo controle do fluxo de formigas que

ingressam ao ambiente de forrageio virtual;

3. A evaporação de feromônio – Reproduz artificialmente o processo de evaporação do

feromônio. A intensidade e periodicidade desta evaporação influenciam diretamente a

formação de caminhos dominantes nas tabelas de feromônio;

4. As ações daemon – Atividades não necessariamente baseadas em informações locais,

auxiliam o algoritmo na construção de condições favoráveis para que a otimização seja

possível;

5. As atividades agendadas – Compreende a execução de todas as atividades previstas no

primeiro item, inclusive a execução do ciclo de vida das formigas presentes no ambiente

de forrageio. No procedimento para o ciclo de vida das formigas, estão previstas ativi-

dades de leitura e escrita na memória das formigas, a escolha dos caminhos (next hop), o

depósito de feromônio e a eliminação das formigas.;

5.1.2 O Problema de Roteamento e os ANTRALs

No contexto das redes de computadores o roteamento de pacotes designa o processo de

reencaminhamento de pacotes. Trata-se de uma operação da terceira camada do modelo OSI,

cuja finalidade principal é permitir que pacotes endereçados a um computador remoto, de

outro segmento da rede ou de outra rede, sigam através de nós intermediários (roteadores) de

89


Rotina Principal do ACO;

início

enquanto Critério de saída não é satisfeito façaExe ute(Procedimento de agendamento de atividades) ;Exe ute(Procedimento de geração e ativação de formigas) ;Exe ute(Evaporação de feromônio) ;Exe ute(Ações daemon) ;Finalize(Atividades agendadas) ;

fim

fim

Procedimento para geração e ativação de formigas:;

início

enquanto recursos disponíveis façaAgende(Criação de uma nova formiga a) ;Ative nova formiga a;fim

fim

Procedimento para ciclo de vida das formigas:;

inícioIni ialize(formiga a) ;Atualize(memória de a,M) ;

enquanto estado atual 6= meta façaExe ute(leitura de tabela de rotas locais A) ;Cal ule(probabilidades de transições de a, baseado em A eM);Cal ule(próximo estado = aplica decisão da formiga considerando restrições);Exe ute(movimento para próximo estado);

se há atualização feromonal passo-a-passo entãoDeposite(feromônio no arco visitado);Atualize(tabela de roteamento de formigas);

fim seAtualize(memóriaM);fim

se há atualização feromonal retardada entãoAvalie(soluções);Deposite(feromônio em todos os arcos visitados);Atualize(tabela de roteamento de formigas);

fim seElimine(formiga a);

fimAlgoritmo 2: Rotina Geral de um Algoritmo ACO.

90


modo a encontrar seu destino. Este processo pressupõe uma tabela de roteamento presente em

cada roteador que descreve para qual de seus vizinhos cada pacote deve ser reencaminhada de

modo a que chegue ao destino desejado. Esta tabela de roteamento pode ser pré-estabelecida

pelos administradores da rede, no caso do roteamento estático, ou pode ser construída auto-

maticamente através dos protocolos de roteamento dinâmico, tais como RIP, OSPF e BGP. O

roteamento dinâmico oferece como vantagem principal a possibilidade de que as tabelas de

roteamento adaptem-se a modificações nas topologia do sistema autônomo em que atua.

Tradicionalmente, em redes com infra-estrutura razoavelmente estável, as tabelas de rote-

amento devem ser construídas de modo que os caminhos percorridos pelas mensagens entre

quaisquer dois nós otimize métricas estabelecidas (e.g. menor custo ou menor número de nós

intermediários). Já em sistemas ad hoc, o objetivo principal pode ser simplesmente encontrar

um caminho viável entre dois nós. Outros objetivos também podem estar presentes na con-

cepção dos algoritmos de roteamento, tais como o balanceamento de carga, a qualidade do

serviço (QoS) e a segurança das informações [63].

As redes de comunicações por pacotes podem ser classificadas em orientada ou não orien-

tada à conexão. No primeiro caso, uma fase de inicialização busca e aloca recursos que serão

requeridos para cada sessão (seqüência de mensagens entre dois nós) requisitada, todas as

mensagens (pacotes) pertencentes à mesma sessão seguirão pelo mesmo caminho, utilizando

os recursos alocados (conexão). Neste caso é necessário que os roteadores mantenham tabelas

com as informações sobre as conexões ativas. No caso de redes não orientadas à conexão, não

há etapa de alocação de recursos, não há informações do estado das conexões e os pacotes

podem seguir por caminhos diferentes, mesmo saindo de um mesmo nó fonte e destinados ao

mesmo receptor. Em cada nó intermediário, uma decisão autônoma é tomada, para escolher

o enlace por onde o pacote será encaminhado, para que chegue ao seu destino.

A analogia entre atividade de forrageio das formigas e o roteamento de pacotes pode ser

facilmente construída: o ambiente de forrageio é mapeado em uma rede, o ninho representa

o nó fonte e a fonte de alimentos representa o nó de destino, para onde as mensagens devem

ser roteadas. As formigas são representadas por pacotes de controle especiais, que modificam

as informações de feromônio nos nós intermediários por onde passam. Após algum tempo

de convergência, as formigas devem encontrar as melhores rotas e os nós podem converter as

informações de feromônio em tabelas de roteamento, que servem para direcionar o tráfego de

dados.

91


Um ANTRAL (Ant Routing Algorithm) é um algoritmo ACO projetado para redes de comu-

nicações por pacotes. Uma rede de comunicações pode ser modelada por um grafo G(N,L)

com N nós e L enlaces. Todos os enlaces da rede são considerados bidirecionais e especi-

ficados por uma capacidade e um retardo de transmissão, que são associados às portas dos

nós. Cada nó possui uma identificação exclusiva (endereço) e é considerado tanto como um

terminal de comunicação (host) como um encaminhador ou roteador de mensagens, e cada

enlace conecta um determinado par de nós. A comunicação entre dois quaisquer nós (unicast)

pode ser vista como uma troca de mensagens. As mensagens são originadas em um nó fonte

s e endereçadas a um nó destino d. O problema do roteamento consiste em construir tabelas

de roteamento em cada nó, para que, quando uma mensagem chegar a um nó endereçada a

um destino qualquer, estas tabelas indiquem o melhor enlace (vizinho) para onde a mensagem

deve seguir a fim de chegar adequadamente ao seu destino.

Apesar de as principais idéias relacionando a meta-heurística ACO ao roteamento terem

sido reportadas primeiramente por Appleby & Steward [19] em 1994, o primeiro ANTRAL

conhecido foi o Ant-Based Control (ABC), proposto por Schoonderwoerd et al. [76] em 1996. O

ABC tem como objetivo o balanceamento de carga, e usa formigas como agentes móveis para

descobrir as melhores rotas em uma rede de telecomunicações. Neste caso, uma rede orientada

à conexão, bem mais compatível com uma rede de telefonia convencional (comutação de

circuitos) que com uma rede de pacotes. Depois do ABC, o AntNet [75] foi proposto por

Dorigo & Di Caro em 1997 como o primeiro ANTRAL para redes não orientadas à conexão.

O AntNet tem sido o mais influente ANTRAL para redes não orientadas à conexão, e, ainda

hoje, a maioria dos ANTRALs propostos herdam suas características. A seguir são descritos

o ABC e o AntNet.

5.2 O ABC

No ABC (Ant Based Control) [76], as formigas são lançadas regularmente a partir de todos

os nós da rede e cada formiga segue para um destino aleatório d. Cada enlace i − j da rede é

associado a uma quantidade de feromônio τijd, associada a cada destino d. A informação de

estado que cada formiga mantém internamente contém apenas o endereço do nó de origem

s, destino d e o registro de tempo do momento de seu lançamento. As formigas depositam

feromônio, passo-a-passo, com taxas de depósito dependentes do tempo que levam entre cada

par de nós. As tabelas de feromônio em cada nó são utilizadas como probabilidades para o

92


roteamento probabilístico. Por exemplo, uma formiga o originada em um nó s, e que em um

dado instante t chega em um nó j, proveniente de i, adiciona um valor 0 ≤ ∆τs,i[k]) < 0

a τs,i[k] na tabela de feromônio do nó j, onde τs,i[k] indica o grau de atratividade de se ir

de j a s via i. O método usado para a atualização das probabilidades é simples: se num

instante k que uma formiga destinada a s que chega em um nó j a partir de um vizinho i,

a probabilidade Ps,i[k] de se escolher o vizinho i para se chegar ao nó s e as probabilidades

Ps,l6=i[k] de se escolher quaisquer outros vizinhos l 6= i são modificadas conforme as Eqs. 5.1

e 5.2.

Ps,i[k] =Ps,i[k − 1] + ∆τs,i[k]

1 + ∆τs,i[k], (5.1)

Ps,l6=i[k] =Ps,l6=i[k − 1]

1 + ∆τs,i[k]. (5.2)

É importante notar que as formigas que têm s como nó fonte, influenciam apenas as

formigas que possuem o nó s como destino. A Evaporação do feromônio depositado nos

enlaces ocorre pela normalização mostrada na Eq. 5.2. Nenhuma memória a respeito dos nós

visitados é mantida para dar suporte a funções de eliminação de laços ou para que as formigas

refaçam na volta o caminho de ida. As tabelas de roteamento para as conexões são obtidas a

partir das tabelas de feromônio, de uma maneira determinística. Adicionalmente, no ABC não

há qualquer outra heurística para a escolha das rotas além das tabelas de feromônios. Uma

componente aleatória foi adicionada às probabilidades de escolha dos próximos nós (next hop)

para se evitar o “congelamento” das rotas em situações de redes cujas topologias permanecem

estáticas por um longo tempo e mudam repentinamente.

Para encorajar as formigas a encontrarem rotas relativamente pequenas, e ainda assim

evitarem nós que estejam congestionados, dois mecanismos foram propostos. O primeiro é o

envelhecimento do parâmetro que controla o depósito de feromônio, ∆τs,i[k], que é reduzido

progressivamente de acordo com a idade das formiga que o deposita. O segundo é o retardo

das formigas nos nós que estão congestionados com pedidos de conexões, o grau de retardo

depende do grau de congestionamento do canal para onde a formiga será encaminhada. De

modo a evitar o congelamento das trilhas que foram repetidamente reforçadas, adiciona-se

uma probabilidade f de que as formigas não sigam o roteamento de acordo com a tabelas de

feromônio, e sim de acordo com uma distribuição uniforme de probabilidade, considerando

todos os vizinhos. No ABC, as “chamadas” interagem apenas indiretamente com as formigas,

93


por meio das tabelas de rotas.

5.3 O AntNet

O primeiro ANTRAL para redes não orientadas à conexão foi o AntNet, proposto por

Dorigo et al. [17] em 1998, e que mostrou melhor desempenho que uma série de algoritmos

convencionais aplicados às redes IP, tais como OSPF, SPF, BF, Q-R e P-QR, para uma série

de problemas de benchmark [75]. Desde então, uma série de modificações foram propostas

ao AntNet original, objetivando melhores performances para condições específicas de tráfego

e de topologias. O AntNet é a mais conhecida aplicação do comportamento das formigas

forrageiras para o problema de roteamento em redes de comunicações. Atualmente há um

grande número de ANTRALs baseados no AntNet, mantendo suas características fundamen-

tais, conforme discutido na Seção 5.5.

5.4 Principais características do AntNet

No AntNet, formigas tornam-se pacotes de controle que fluem através da rede de maneira

semelhante aos pacotes de dados regulares. Formigas e pacotes de dados compartilham da

mesma rede, mas são roteados de acordo com políticas diferentes, os pacotes de dados usam

tabelas de roteamento diferentes das formigas para irem de suas fontes até seus destinos. Em

cada nó da rede, uma tabela de roteamento é mantida além de uma tabela adicional contendo

estatísticas sobre as características de tráfego na rede e uma tabela de feromônio. O AntNet

usa dois conjuntos homogêneos de agentes móveis, chamados de formigas forward e formigas

backward [20, 22, 75].

As formigas forward são criadas regularmente em todos os nós e envidas para todos os

possíveis nós de destino. Elas compartilham as mesmas filas com os pacotes de dados, de

modo que experimentam as mesmas dificuldades de tráfego. Cada formiga, individualmente,

é associada a um par de nós origem-destino e seguem do nó de origem até o nó de destino ar-

mazenando informações dos tempos associados a cada trecho da rede. Cada formiga backward

faz exatamente o caminho inverso de uma formiga forward, atualizando as tabelas de feromô-

nios em cada nó de seu percurso até o seu destino (origem da formiga forward). Dorigo &

DiCaro propuseram duas diferentes versões do AntNet [77]. Em sua segunda versão, também

chamada de AntNet-FA, as formigas backward não compartilham as mesmas filas que os paco-

94


tes de dados, ao invés disto, usam uma fila de alta prioridade na entrada dos nós, para serem

mais rápidas que os outros pacotes, já que devem propagarem rapidamente as informações

acumuladas pelas formigas forward para as tabelas de roteamento. O AntNet-FA mostra um

desempenho bem melhor que o AntNet original, que foi praticamente abolido, de modo que

doravante referir-se-á ao AntNet-FA simplesmente por AntNet.

• Recrutamento – Em intervalos regulares, e concomitantemente com o tráfego de dados

de cada nó da rede, agentes móveis são assincronamente lançados (formigas forward ) e

destinados a nós escolhidos aleatoriamente. A probabilidade psd de criar, no nó s, uma

formiga forward para o nó de destino d é mostrada na Eq.5.3.

psd =fsd

∑Ni=1 fsi

, (5.3)

onde fij representa uma medida do fluxo de dados entre os nós i e j, e N é o número de

nós na rede.

• Escolha de caminhos – Cada formiga se move nó-a-nó (hop-by-hop) no sentido de seu nó de

destino. Em cada nó intermediário, uma função estocástica de política ambiciosa é aplicada

à escolha no próximo nó para onde seguir. A política faz uso de (i) informações geradas e

mantidas localmente; (ii) informações de heurísticas dependentes do problema em questão,

e; (iii) informações privativas à formiga. Em cada nó i, cada formiga seleciona o nó j para

seguir com probabilidade Pijd, mostrada na Eq.5.4.

Pijd =τijd + αηij

1 + α(| Ni | −1), (5.4)

onde τij representa a soma normalizada do feromônio depositado no nó i para cada destino

d e que tenha escolhido j como próximo nó; ηij representa uma função heurística que leva

em consideração o comprimento da fila i − j, como na Eq. 5.5; α pondera a importância

da heurística na escolha dos caminhos, e; Ni representa o conjunto de vizinhos do nó i, e

| Ni | a cardinalidade deste conjunto.

ηij = 1−qij

∑|Ni|l=1 qil

, (5.5)

onde qij representa o tamanho da fila do enlace i− j.

95


• Uso de memória – Enquanto as formigas se movem na rede, elas armazenam em sua memó-

ria as informações sobre as rotas que escolheram e os tempos observados para cada trecho

de seu percurso Oid desde o nó i até o destino d ser atingido.

• Detecção e eliminação de laços (loops – Se uma formiga forward passa pelo mesmo nó duas

vezes antes de chegar ao seu destino, um laço é detectado, então a informação do laço é

apagada da memória da formiga e ela deve seguir por um caminho distinto. Caso o laço

dure mais que o tempo de vida de uma formiga, isto é, se o tempo despendido no laço é

maior que metade da idade da formiga, a formiga é destruída.

• Transição forward para backward – Quando uma formiga forward atinge o seu nó destino,

ocorre a sua conversão em uma formiga backward, que carrega consigo, em sua memória,

as informações de tráfego acumuladas no percurso origem-destino. Esta formiga utilizará

sua memória para fazer exatamente o percurso inverso ao feito anteriormente, agora será

destino-origem.

• Percurso de volta pela rota escolhida e modificação das tabelas de modelo de tráfego

– Durante a viagem de volta ao seu nó de origem, enquanto refaz em sentido inverso o

caminho anteriormente traçado, a formiga backward é responsável por atualizar as tabelas

de modelo de tráfego em cada um dos nós de seu percurso. A tabela de modelo de tráfego

de um nó i carrega estatísticas do tráfego experimentado pelas formigas para cada par i−d.

Logo, a média dos tempos de viagens observados entre i e d, computada no instante k

(µid[k]), onde d representa os possíveis destinos, a variância destas medidas (σ2id[k]) e, o

tamanho da janela de tempo na qual as observações são consideradas, Wid.

µid[k] = µid[k − 1] + δ(Oid − µid), (5.6)

σ2id[k] = σ2

id[k − 1] + δ(Oid − µid)2 − σ2), (5.7)

onde δ pondera a importância das amostras mais recentes.

• Atualização das tabelas de feromônios e de roteamento de dados – As medidas de inten-

sidade do feromônio, presentes na tabela de feromônio de cada nó i, servem como pro-

babilidades para o roteamento probabilístico 1. O depósito e a evaporação do feromônio

1A tabela de roteamento ℜ para os pacotes de dados pode alternativamente ser obtida através do remapeamento da tabela

de feromônios usada pelas formigas forward, pela aplicação de uma função de potência a ser definida [20, 22, 75].

96


associado a cada par v− d, aumenta ou diminui, respectivamente, as chances do nó v servir

como próximo nó para pacotes que chegam endereçados a d. Se uma formiga chega em

um nó i proveniente de um nó vizinho v, uma formiga backward com destino d atualiza a

concentração de feromônio Tivd[k], presente na tabela de feromônio do nó i conforme a

Eq.5.8.

Tivd[k] = Tivd[k − 1] + r(1− Tivd[k − 1]), (5.8)

onde r é uma função da conformidade dos tempos observados nas viagens i − v, estimado

a partir da tabela de modelo de tráfego. r é adimensional, r ∈ (0; 1].

Uma vez que as concentrações de feromônio no AntNet representam probabilidades para o

roteamento das formigas, os valores de Tij [k], com j 6= v i.e. para outros vizinhos, devem

ser ajustados para satisfazerem a Eq. 5.9.

|Nk|∑

j=1

Tij [k] = 1. (5.9)

• Evaporação – Feromônios Tivd[k] associados ao destino d e a qualquer outro nó j da vizi-

nhança no instante k, j ∈ Ni, j 6= v, evaporam implicitamente na normalização realizada

de acordo com a Eq.5.10.

Tivd[k] = Tivd[k − 1]− r(Tivd) (5.10)

• Eliminação das formigas – Depois de alcançado o nó de origem, a formiga backward é

eliminada.

• Tempo de vida (TTL -Time-to-live) das formigas – Se uma formiga não alcança seu destino

em um tempo inferior ao assinalado como seu máximo tempo de vida, a formiga é eliminada

[78]. O tempo de vida pode também ser associado a um número máximo de saltos (hops)

que a formiga pode realizar.

5.4.1 O emprego do conhecimento global no AntNet

Ao contrário do que se poderia esperar, o AntNet e a maioria dos ANTRALs também

são dependentes de informações globais que não estão disponíveis em situações práticas do

mundo real. No AntNet proposto por Dorigo e Di Caro [17], os nós possuem uma tabela de

97


roteamento global, com entradas para todos possíveis destinos da rede, e também sincronismo

global [79]. Estes aspectos não têm sido explicitados, e não são considerados no AntNet, uma

vez que não são tão cruciais para o roteamento em redes IP cabeadas, onde relógios “pratica-

mente” sincronizados são comuns [78]. O carregamento inicial da tabela de roteamento e o

sincronismo dos nós podem ser vistos como exemplos de ações daemon do AntNet, de acordo

com a definição destas ações.

Conforme discutido anteriormente, o uso de informações globais não é uma caracterís-

tica desejável nos ANTRALs, sobretudo quando se está interessado no roteamento de redes

dinâmicas. Diversas idéias para a construção de ANTRALs dependente apenas de informa-

ções locais surgiram com os algoritmos projetados para as redes móveis ad hoc (Mobile Ad hoc

Networks), ou MANETs [78], [80].

5.4.2 Pseudo-Código do AntNet

O pseudo-código genérico do AntNet é mostrado no Algoritmo 3. A rotina prevê o pro-

cessamento das formigas geradas no próprio nó ou recebidas dos nós adjacentes. Tal pro-

cessamento envolve a escolha do próximo salto e atualização das tabelas de feromônio, caso

as formigas não sejam destinadas ao nó onde estão sendo processadas, ou a eliminação, que

no caso das formigas forward, envolvem a transferência de memória para uma nova formiga

backward, que fará o trajeto inverso de acordo com a memória recebida.

5.5 Outros ANTRALs

Na tabela disposta no Apêndice I, estão tabelados os principais ANTRALs, ordenados

pelo ano de publicação. A partir desta tabela, percebe-se o quanto o AntNet tem influenciado

as novas propostas de ANTRALs, bem como é possível identificar uma tendência de novos

algoritmos voltados para a Qualidade de Serviço (QoS), além do balanceamento de carga e o

aumento da eficiência, sobretudo no que diz respeito ao problema da estagnação. Aspectos

de segurança têm sido relativamente negligenciados na pesquisa de ANTRALs e irão prova-

velmente chamar mais atenção nas próximas abordagens, um exemplo deste tipo de trabalho

é o de Saffarian & Morogan [81], que propõe um método para mitigação de ameaças de

segurança ao roteamento do AntNet.

Adicionalmente aos trabalhos relacionados no Apêndice I, há uma série de trabalhos re-

lacionados aos ANTRALs que não necessariamente propõem novos algoritmos, dentre estes

98


Inicializa Rotina Principal do AntNet;

para cada passo de tempo k faça

para cada nó s da rede façaExe ute(o recrutamento de uma formiga forward o para o nó de destino d) ;

para cada nó i, i 6= d, façaIn remente(memória da formiga o com as condições de tráfego do percurso) ;

fim para cadaEs olha(probabilisticamente o próximo salto o, de acordo com a tabela de feromônio) ;

se um laço (loop) é detectado então

se o laço durou mais que o tempo de vida da formiga antes de entrar no laço entãoElimine(a formiga o) ;

fim se

fim se

fim para cada

se o nó de destino d é alcançado entãoExe ute(transferência de memória da formiga forward o para a formiga backward b) ;Elimine( a formiga o) ;

fim se

para cada nó j, j 6= s faça

enquanto recebe formiga backward b façaAtualize(tabela de modelo de tráfego local) ;Atualize(tabela de feromônio local) ;

se o nó de origem s é alcançado entãoElimine(a formiga backward b) ;

fim se

senãoEn aminhe(a formiga backward b de acordo com caminho registrado na memória) ;

fim se

fim

fim para cada

fim para cadaAlgoritmo 3: Pseudo-código do AntNet

99


pode-se citar uma série de compilações (surveys), tais como em Wedde & Farooq [63], Sim

& Sun [82], Blum [11] e Di Caro & Dorigo [75]. Há também, embora poucos, trabalhos na

análise de desempenho dos ANTRALs, como por exemplo em Dhillon & Mieghem [20] e em

Simonin et al. [83]. Também percebe-se um déficit de estudos analíticos, como os de Bean

& Costa [22], Park & Kim [84] e Yoo et al. [85] e Qu et al. [86], cuja análise com relação

às capacidades de reação dos agentes revela informações sobre comportamento dos agentes e

provê ferramentas úteis à condução das formigas em grandes redes.

Outros trabalhos apontam resultados de implementações dos ANTRALs, como em Strobbe

et al. [87], onde reporta-se uma implementação física do AntNet com o uso de um software

modular chamado Click. Os resultados mostram que o AntNet é bem superior ao OSPF com

relação à vazão proporcionada, devido a suas características de balanceamento de carga. Por

outro lado, não foi identificado um vencedor claro com respeito a capacidade de adaptação.

O AntNet reage primeiro para modificações nos enlaces e o OSPF para falhas. Em Yang, et

al. [88], o AntNet é implementado em uma rede física local pequena, e compara-se os resulta-

dos de estratégias estática e dinâmica de reforço do feromônio. O reforço dinâmico mostrou

melhores resultados para encontrar rapidamente um bom caminho, enquanto o reforço cons-

tante é mais apropriado para redes com muitas falhas, devido à capacidade de comutar entre

rotas alternativas rapidamente. O desempenho de ambas as estratégias mostrou-se bastante

sensível aos parâmetros.

5.5.1 Algoritmos para MANETs

MANETS (Mobile Ad hoc Networks) são redes de comunicações nas quais os nós são móveis

e comunicam-se uns aos outros por redes sem-fio. Não há infra-estrutura fixa. Todos os nós

são iguais e não há controle central ou supervisão. Não há roteadores designados: todos os

nós servem como hosts e como roteadores, e os pacotes de dados são encaminhados nó a nó,

com vários saltos [89].

O interesse por MANETs cresce desde 1990 [90]. Estas redes são mais dinâmicas e possuem

menos recursos que as redes cabeadas, e, por causa disso, a engenharia de um algoritmo de

roteamento adequado é um problema desafiador. Os tradicionais LS e DV não são compatí-

veis para grandes MANETs por causa de suas freqüentes atualizações de rotas, que consomem

energia e parte significativa da largura de banda disponível. Os principais problemas para as

MANETs são o roteamento em redes de topologia muito dinâmica, a conservação de potên-

100


cia em redes sem-fio e o provisionamento de QoS. Os algoritmos de roteamento devem ter

propriedades como robustez, otimalidade e estabilidade, o que tornam o problema intrigante

[91].

Um algoritmo de roteamento para MANETs pode ser classificado em três tipos:

• Proativo ou dirigido à tabela, se ele avalia as rotas antes que seja requisitado e mantém

informações atualizadas de roteamento para todos os nós;

• Reativo ou sob demanda, se o algoritmo de roteamento tenta estabelecer cada rota apenas

quando é necessário, e não mantém informações de rotas de todos os nós sempre atualiza-

das, ou;

• Híbrido, buscando uma relação custo benefício entre ambas as estratégias anteriores.

Por um lado, os algoritmos de roteamento proativos para MANETs, como o DSDV

(Destination Sequenced Distance Vector) requerem o conhecimento da topologia da rede toda.

Assim, não é apropriado para redes muito dinâmicas, como comumente são as MANETs.

Por outro lado, esquemas de roteamento reativo, como o AODV e o DSR (Dynamic Source

Routing), requerem que a transmissão de informações seja retardada até que uma rota seja

encontrada, assim, tornam-se não apropriadas para comunicações de tempo real. Na Tabela

5.5.1 são listados alguns importantes ANTRALs projetados para MANETs.

Tabela 5.1: Algoritmos baseados em formigas para redes ad hoc.

Algoritmo Ano Autor

ARS 2000 Oida & Sekido [92]

ARH e ARHnr 2002 Fujita et al. [93]

Ant-AODV 2002 Marwaha et al. [94]

ARA 2002 Günes et al. [95]

PERA 2003 Baras & Mehta [96]

Termite 2003 Roth & Wicker [97]

AntHocNet 2004 Di Caro et al. [98]

ADRA 2004 Zheng et al. [99]

ABC-AdHoc 2004 Tatomir & Rothkrantz [100]

ANSI 2005 Rajagopalan & Shen [101]

W-AntNet 2007 Dhillon et al. [102]

101


5.6 Discussão

Os ANTRALs mostram um desempenho superior aos algoritmos tradicionais, seja sim-

plesmente para a busca de melhores caminhos em redes de pacotes, seja para a solução de

problemas adjacentes, tais como o roteamento orientado à Qualidade de Serviço (QoS) e ba-

lanceamento de carga. Apesar de terem se passado cerca de quinze anos desde a publicação

dos primeiros ANTRALs, somente agora as primeiras implementações em redes físicas es-

tão sendo reportadas. As Pesquisas relacionadas aos ANTRALs têm sido bastante focadas

em modificações dos primeiros algoritmos (ABC e AntNet), com eventuais ganhos de desem-

penho, sobretudo no que diz respeito a superação do problema de estagnação. Percebe-se

também uma carência em trabalhos analíticos nesta área, bem como algoritmos que consi-

derem questões de segurança em sua concepção. É notável também uma grande pesquisa na

área dos ANTRALs aplicados às redes móveis ad hocMobile Ad hoc Networks (MANETs). Estas

redes também chamadas “redes sem infra-estrutura” são muito dinâmicas e possuem fortes

restrições de seus recursos, o que torna mais difícil uma solução adequada de roteamento, e

por isso mesmo, os ANTRAls aparecem como soluções atraentes.

A pesquisa relacionada aos ANTRALs está em uma fase em que, se por um lado já existem

várias evidências de que estes algoritmos mostram desempenho superior aos convencionais e

podem ser ajustados para responder adequadamente aos desafios colocados pela evolução

das redes de computadores, por outro, ainda é necessário avançar bastante no aprimora-

mento destes algoritmos até que se estabeleçam padrões que permitam a implementação de

ANTRALs em redes reais e a disseminação de seu uso.

102

Capítulo VI

MARS - Sistema deRoteamento Baseado emFormigas Sem Memória

It is possible to make things of great complexity

out of things that are very simple. There is no

conservation of simplicity.

— Stephen Wolfram

Para a solução do problema de roteamento em redes de comunicação por pacotes, con-

forme apresentado no Capítulo 5, um dos maiores problemas é a busca por equilíbrio

entre objetivos muitas vezes conflitantes, tais como:

• Baixa ocupação dos canais de comunicação (overhead) – Com a redução do consumo dos re-

cursos da rede, o algoritmo libera espaço para o tráfego das informações úteis aos usuários

e reduz a latência (retardo) média da rede para suas aplicações;

• Adaptabilidade – No caso de mudanças na topologia da rede, e.g. falhas nos canais de

comunicação, o Sistema de Roteamento deve minimizar o tempo de adaptação à nova situ-

ação, e rapidamente encontrar as melhores soluções de roteamento para a nova topologia;

• Alta Disponibilidade – Possuir robustez e alta confiabilidade para permanecer o maior

tempo possível em perfeito estado operacional;

• Resiliência – Manter sua funcionalidade, mesmo quando alguns componentes do sistema

de roteamento falhar, por exemplo quando algum roteador estiver fora de operação;

• Provisão de QoS – Levar em consideração as restrições de Qualidade de Serviço (QoS), tais

como retardo e jitter, quando há o roteamento de dados sensíveis a tal;


• Eficiência – Permitir que a rede, a partir de uma quantidade limitada de recursos, maximize

a quantidade seus serviços prestados aos usuários;

• Flexibilidade – Moldar-se a qualquer arquitetura de rede, e quaisquer tipos de serviços

presentes nas camadas superiores e inferiores do Modelo OSI;

• Segurança –O Sistema de Roteamento deve prever o uso de criptografia e outras proteções

contra ataques maliciosos;

• Simplicidade – Possuir poucos parâmetros de ajuste e permitir configuração inicial e ma-

nutenção amigáveis;

Este capítulo aborda a concepção de um sistema baseado no FFAC-D, abordado no Ca-

pítulo 4, para a solução do problema de roteamento em redes de pacotes e que leva em

consideração os objetivos mencionados acima, embora em sua primeira implementação, al-

gumas preocupações, como por exemplo a provisão de QoS, não estejam explícitas. A base

para a analogia entre o modelo FFAC-D, apresentado no Capítulo 4, e o novo algoritmo,

denominado MARS (do inglês Memoryless Ants Routing System) é semelhante àquela utilizada

na maioria dos ANTRALs: as formigas são pacotes de controle que trafegam pela rede, con-

comitantemente com os pacotes de dados, e se comunicam estigmergicamente. Elas se auto-

organizam e finalmente estabelecem trilhas de feromônio, cujas intensidades influenciam as

probabilidades de escolhas dos caminhos usados para o roteamento do tráfego de dados e das

próprias formigas. É esperado que o efeito diferencial do comprimento conduza as tabelas de

feromônios para a escolha dos melhores caminhos.

Devido à notoriedade do AntNet dentre os ANTRALs para redes de pacotes cabeadas

e unicast, freqüentemente este algoritmo é tomado como benchmark e como base para o de-

senvolvimento de outros ANTRALs, conforme discutido no Capítulo 5. No caso do MARS,

pode-se afirmar que há tanto similaridades com o AntNet quanto com o ABC, embora ele não

seja uma versão modificada nem de um nem de outro, pois há diferenças substanciais para

com ambos. Para simplificar a descrição do MARS, no entanto, serão destacadas no decorrer

deste capítulo as similaridades e diferenças seja com o AntNet, seja com o ABC. Além disso,

conforme será abordado na Seção 6.4, a primeira implementação do MARS foi feita no simu-

lador de redes NS-2 (Network Simulator 2), onde também há uma implementação do AntNet

disponível [103] e que pode ser tomada como referência.

Com a exceção dos algoritmos ABC [76] e CAF [104], que foram aplicados a redes orien-

tadas à conexão, todos os ANTRALs verificados no levantamento da literatura, do Capítulo

104

————MARS - Sistema de Roteamento Baseado em Formigas Sem Memória————

5, fazem uso de agentes com memória. Ademais, a maioria destes algoritmos, incluindo o

AntNet [17], dependem de algum tipo de informação global. O MARS foi concebido como

um sistema baseado em agentes sem memória e que dependem exclusivamente de informações

locais para sua tomada de decisão. O MARS foi projetado de forma a independer de ações

daemon ou informações globais. Espera-se que, desta forma, seja possível alcançar maior

eficiência, segurança, cofiabilidade, resiliência e flexibilidade que os ANTRALs existentes.

Similarmente ao AntNet, o MARS foi projetado inicialmente para redes de comutação de

pacotes ponto-a-ponto não orientadas à conexão, com tráfego simétrico e enlaces bidirecio-

nais, conforme descrito a seguir.

6.1 Modelo da Rede

A rede utilizada no desenvolvimento do MARS pode ser representada por um grafo G(N,L)

com, N nós e L enlaces bidirecionais-direcionais que conectam os nós a seus vizinhos. É si-

milar ao modelo usado em Dhilon e Mieghen [20] e em Dorigo e Di Caro [75]. A seguir são

descritas as principais estruturas da rede consideradas na concepção do MARS.

• Pacotes de dados – Contém as informações trocadas entre os usuários finais da rede.

Figura 6.1: Representação de uma formiga no MARS.

• Formiga– Consiste em um seqüência de bits (pacote) contendo informações dos endereços

de origem e destino, além de um número de identificação da formiga (ID. #) e um rótulo de

direção que indica se a formiga está indo de seu nó de origem até o destino (forward) ou de

volta do destino à origem (backward). Estas formigas são os pacotes de controle responsáveis

pelo funcionamento do MARS, e é com base no tráfego destas formigas que as tabelas de

feromônio, e conseqüentemente de roteamento, são atualizadas. No MARS, diferentemente

do AntNet, a única diferença entre uma formiga forward e um backward está em seu rótulo

de direção, que é alterado quando uma formiga forward chega a seu destino. No MARS, as

105


formigas são muito menores que em ANTRALs tradicionais, donde já se pode esperar uma

redução do uso dos canais de comunicação.

• Nó MARS – Um nó pode ser visto como um host se atua como origem ou destino de

pacotes, ou como um roteador, se estiver reencaminhando os pacotes destinados a outros

nós. Cada nó pode possuir várias portas, e cada porta pode sustentar um enlace com um nó

vizinho. Conforme ilustrado na Fig. 6.2, cada nó da rede mantém uma memória (buffer) de

entrada composta por uma fila orientada ao melhor esforço (best-effort) e uma memória de

saída, composta de duas filas para cada porta, uma fila de alta prioridade e outra de baixa

prioridade.

Figura 6.2: Estrutura de nó considerada no MARS, neste caso com três portas.

Na saída dos nós MARS, as formigas ocupam as filas de alta prioridade, enquanto os

pacotes de dados ocupam filas de menor prioridade. Dentro de cada fila, assume-se que os

pacotes são encaminhados de acordo com o esquema PEPS (Primeiro que Entra é o Primeiro

que Sai).

• Enlace MARS – É similar a um enlace no AntNet, um canal de comunicação bi-direcional

106


especificado por sua capacidade (em bits por segundo) e tempo de retardo (em segundos).

No MARS, os enlaces possuem características idênticas em ambos os sentidos, ou seja, são

simétricos.

6.2 Estruturas Internas de Dados

Cada nó que possui o MARS implementado, deve gerar, encaminhar, receber e processar

formigas. O processamento de uma formiga pode implicar na sua eliminação ou na escolha do

próximo salto para onde o pacote deve ser reencaminhado. Também durante o processamnto

das formigas há a atualização dos campos das formigas (rótulo de direção e último nó) e de

estruturas de dados bem definidas, internas ao nó, e necessárias para o funcionamento do

algoritmo, conforme segue abaixo:

• Tabela de roteamento R – Consiste de uma matriz que indica o próximo vizinho, para

onde os pacotes devem ser encaminhados de forma a alcançarem seus respectivos nós de

destino. Cada linha nesta tabela corresponde a um destino d ∈ D da rede e aponta para um

vizinho v ∈ V para onde os pacotes de dados devem ser encaminhados. Esta tabela pode ser

probabilística ou determinística. No primeiro caso, ilustrado na Tabela 6.1, para cada linha

associada a um dado destino, os valores presentes em cada coluna associada a um vizinho

indicam as probabilidades de que o próximo salto seja para este vizinho. No caso da tabela

determinística, ilustrado na Tabela 6.2, apenas um vizinho é indicado para o próximo salto,

ou seja, o melhor vizinho para se chegar a um dado destino recebe probabilidade igual a

um, e todos os demais com probabilidade igual a zero;

Tabela 6.1: Tabela de Roteamento Probabilística.

destino vizinho 1 vizinho 2 ... vizinho V

nó 1 p11 p2

1 ... pP1

nó 2 p12 p2

2 ... pP2

... ... ... ... ...

nó N p1N p2

N ... pPN

107


Tabela 6.2: Tabela de Roteamento Determinística.

destino próximo salto

nó 1 (melhor vizinho para chegar até o nó 1)

nó 2 (melhor vizinho para chegar até o nó 2)

... ...

nó N (melhor vizinho para chegar até o nó N)

• Uma tabela de feromônio Q 6.2, similar à tabela de roteamento, mas, para cada destinho,

mostra a quantidade de feromônio depositada em cada uma das portas do roteador, ou seja,

no enlace com cada um dos vizinhos;

Tabela 6.3: Tabela de Feromônio.

destino vizinho 1 vizinho 2 ... vizinho V

nó 1 q11 q2

1 ... qP1

nó 2 q12 q2

2 ... qP2

... ... ... ... ...

nó N q1N q2

N ... qPN

• Uma lista de destinos D que contém todos os nós de destino d da rede para os quais o agente

deve se preocupar em apontar os melhores caminhos. A cada destino deve estar associado

um selo de tempo tsd com o instante em que o destino foi inserido na lista. Esta lista pode

ser atualizada de maneira proativa, buscando conter todos os possíveis destinos da rede, ou

de maneira reativa, ou seja, sob demanda, de acordo com as necessidades do roteamento

de dados;

• Uma lista de vizinhos V contendo todos os vizinhos v diretamente, ponto-a-ponto, conec-

tados ao nó, através de uma de suas portas;

• Uma tabela de formigas A (Tabela 6.2), com um número y de linhas, contendo o número de

identificação de cada formigas enviada, seu destino e o vizinho para onde foi encaminhada.

Esta tabela deve ser preenchida utilizando o método PEPS, de modo que contenha apenas

as últimas y formigas encaminhadas para cada destino, por cada vizinho.

108


Tabela 6.4: Tabela de Formigas.

ident. da formiga destino vizinho

a da i

b db j

... ... ...

c dc y

6.3 Características do Algoritmo MARS

A seguir, são descritos os principais componentes do algoritmo MARS, que é implemen-

tado em cada nó MARS presente na rede:

• Recrutamento – A cada iteração do algoritmo é calculada para cada destino d ∈ D, a

probabilidade rd[k] de recrutar uma formiga destinada ao nó d no instante k, conforme a

Eq.6.1. Estas probabilidades determinam o possível lançamento de tais formigas na rede.

rd[k] =rmd

1 + (rm

d

ro

d

− 1)e−κ(k−ksd), (6.1)

onde rod e rm

d representam os limites inferiores e superiores da probabilidade de recruta-

mento para o destino d, respectivamente, e, κ é uma constante que controla a suavidade da

curva de recrutamento, e k − ksd é o tempo decorrido desde que o destino d entrou na lista

D.

• Escolha do Próximo Nó – Tanto as formigas recrutadas, quanto aquelas recebidas que

apontam para um outro nó de destino d, devem ser encaminhadas a um vizinho v ∈ V,

que tem probabilidade Pdv[k], conforme mostra a Eq.6.2. A Eq.6.2 representa apenas uma

adaptação da Eq. 2.9, descrita no Capítulo 2, generalizada para um número qualquer de

ramos nas bifurcações.

Pdv[k] =

(

qvd [k] + αv

∑|Nv|l=1 (ql

d[k] + αl)

)n

, (6.2)

onde qvd [k] representa a quantidade de feromônio associado ao destino d e à porta ligada ao

vizinho v no instante k; n representa o grau de não linearidade das escolhas; αv representa

o grau de preferência intrínseca pelo o enlace v na ausência de feromônio. Assim, foi

considerada a capacidade do enlace na ausência de tráfego desta variável.

109


No Modelo FFACD, as formigas possuem uma característica exploratória que é estimulada

a partir da percepção de aglomerações ou de novidades na área de forrageio. Assim, a

escolha “usual” das formigas, baseada apenas na geometria e na quantidade de feromônio,

podem ser alteradas. Semelhantemente, no MARS, a escolha resultante da Eq. 6.2 pode

mudar, a depender do comportamento exploratório das formigas. Este comportamento

exploratório cresce quando as formigas se deparam com congestionamentos (aglomerações)

ou alterações em seus enlaces (ambiente de forrageio). Assim, a probabilidade P expdv de

uma formiga mudar sua escolha baseada na Eq.6.2, devido ao comportamento exploratório

prévio, é definida pela Eq. 6.3.

P expdv [k] = exp(

ηdv[k]− ηmax

Γ) + ϕnovelty

v [k], (6.3)

onde ηdv[k] é o número de formigas enviadas pelo nó i com destino d e encaminhadas ao

nó v nos período entre k − T e k que não retornaram ao nó i; enquanto ηmax é o número

máximo de formigas enviadas a um determinado nó que não retornaram, a partir do qual

é detectada a queda de desempenho de uma determinada rota. Ou seja, a partir do qual

pode-se identificar um vizinho v como um nó congestionado ou “sem saída” para o nó d;

Γ é uma constante de ajuste. Na segunda componente da Eq. 6.3, ϕnoveltyv [k] representa

a intensidade de novidade presente no enlace associado ao vizinho v. Quando uma for-

miga se depara com uma novidade no nó, tal como uma nova conexão, ela deposita uma

quantidade ϕmax de um sinalizador de novidade, uma espécie de “feromônio da novidade”

que comunica às outras formigas sobre a descoberta e estimula os seus comportamentos

exploratórios. O ϕnoveltyv [k] possui uma alta volatilidade 0 ≤ φ ≤ 1, e deve persistir apenas

durante a exploração da novidade por parte das formigas. O modelo para a exploração de

novidade é mostrado na Eq. 6.4.

Se a novidade é detectada no instante k, ϕnoveltyv [k] = ϕMAX ;

Então, a partir do instante k + 1 há evaporação, ϕnoveltyv [k + 1] = φϕnovelty

v [k].(6.4)

• Transição Forward → Backward – Quando uma formiga “forward” chega ao seu destino,

sua direção é invertida (seu endereço de destino se torna o endereço de origem e vice-versa)

e sua direção é alterada para “backward”.

• Depósito de Feromônio – As formigas depositam feromônio por onde passam. No MARS,

110


o depósito de feromônio é feito toda vez que uma formiga é recebida ou encaminhada a um

nó vizinho. No depósito do encaminhamento, ao escolher um nó v, v ∈ N como próximo

nó para chegar ao destino d, cada formiga (backward ou forward) modifica a tabela de fe-

romônio do nós por onde passam, depositando uma determinada quantidade de feromônio

no instante k, ∆q[k], calculada de acordo com a Eq. 6.5. A mesma fórmula se aplica no caso

de uma formiga ser recebida, neste caso, v representará o nó de proveniência da formiga

recebida e d, seu nó de origem. Este depósito de feromônio efetuado no recebimento de

formigas é semelhante àquele visto no ABC [76].

qvd [k + 1] = qv

d [k] + ∆qvd [k], (6.5)

∆qvd [k] =

ε(qmax − qvd [k]), se qmax ≥ qv

d [k];

0, caso contrário.(6.6)

onde ε é uma constante, 0 ≤ ε ≤ 1.

• Atualizando as tabelas de roteamento de dados – A quantidade de feromônio depositada

para cada vizinho v, para cada destino d, qvd [k] é convertida em probabilidade para o ro-

teamento de dados R. Isto é obtido pela função de mapeamento ℑ : Q → R da tabela de

feromônios Q na tabela de roteamento R. No caso de uma tabela de roteamento deter-

minístico, esta função aloca na tabela de roteamento aqueles vizinhos que possuem maior

intensidade de feromônio para cada destino.

• Eliminação das Formigas – Depois de retornarem ao nó de origem, as formigas backward

são eliminadas.

• Evaporação – A evaporação do feromônio ocorre de maneira eqüânime para toda a tabela

de feromônio Q em intervalos regulares, de acordo com a Eq.6.7.

qid[k + 1] = γqi

d[k], (6.7)

onde γ é uma constante, 0 ≤ γ ≤ 1.

6.3.1 Pseudo-código do MARS

A rotina principal e as sub-rotinas de recrutamento de formigas e recebimento de pacotes

do MARS são delineadas no Algoritmo 4. Trata-se de um algoritmo relativamente simples,

111


onde não há escrita nem leitura de informações a partir das formigas, pois estas não possuem

memória. O tempo titer determina o intervalo entre cada iteração do algoritmo, onde ocorrem

as atividades agendadas de evaporação e recrutamento. As demais atividades são disparadas

a partir da necessidade de processamento das formigas, envolvendo atividades de encaminha-

mento, eliminação e depósito de feromônio com conseqüente atualização das Tabelas Q e R,

tenham sido elas originadas ou não no próprio nó.

6.4 Simulações e Resultados do MARS

Nesta seção são apresentados os primeiros resultados do algoritmo do MARS, a partir

de sua implementação no simulador de redes NS-2. O objetivo é verificar a viabilidade de se

aplicar a analogia entre o forrageio das formigas verificados nos experimentos e reproduzidos

no modelo FFAC-D, e o roteamento de pacotes em redes de comunicações. Assim, de maneira

semelhante ao que ocorre no caso do AntNet, onde após visto o desempenho superior ao

da primeira versão em relação aos algoritmos de roteamento tradicionais, diversas melhorias

foram acrescentadas ao longo do tempo. Espera-se que, uma vez constatadas vantagens na

utilização dos princípios subjacentes ao MARS, melhorias incrementais surjam, até que seja

possível fazer o uso prático desta tecnologia.

6.4.1 O Simulador - NS-2

O NS-2 (Network Simulator v.2) é um simulador de eventos discretos, fruto do projeto VINT

(Virtual InterNetwork Testbed), composto por DARPA, USC/ISI, Xerox PARC, LBNL, e a uni-

versidade de Berkeley, dentre outros [105]. Uma grande vantagem do NS-2 reside no fato de

ele ser totalmente gratuito e com código fonte aberto, o que permite ao usuário introduzir

ajustes e novas funcionalidades, inclusive novos protocolos de comunicação. Diversos proto-

colos da pilha TCP/IP já são suportados pelo NS-2 de maneira default, inclusive algoritmos de

roteamento dinâmico tradicionais, tais como o LS (Link State) e DV (Distance Vector).

A programação do NS é feita em duas linguagens: C++ para a estrutura básica (protoco-

los, agentes, etc) e OTCL (Object-oriented Tool Command Language) para programação dos

scripts de simulação, ajustes de parâmetros e interface entre alguns módulos programados em

C++. O OTCL é uma linguagem interpretada, desenvolvida pelo MIT (Massachussets Institute

of Technology). O motivo para se utilizar duas linguagens de programação baseia-se em duas

diferentes necessidades. De um lado existe a necessidade de uma linguagem mais robusta para

112


Inicializa Rotina Principal do MARS;

inícioIni ialize(Tabelas de FeromônioQ e de Roteamento R);Ini ialize(Listas de destinosD e de vizinhos V);

para cada intervalo de tempo titer façaAtualize(Lista de vizinhosV);Atualize(Lista de destinosD);Exe ute(recrutamento de formigas);Exe ute(recebimento de formigas);Atualize(Tabela de feromônioQ);Atualize(Tabela de roteamentoR);fim

fim

Rotina do Recrutamento de Formigas;

inícioExe ute(recrutamento de formiga para cada destino d, de acordo com a probabilidade da Eq. 6.1) ;En aminhe(para o próximo vizinho de acordo com as Eq.6.2 e 6.3);Deposite(Feromônio de acordo com Eq.6.5);

fim

Rotina do Recebimento de Pacotes do MARS;

início

se o pacote é do tipo MARS entãoDeposite(feromônio de acordo com Eq.6.5);

se a formiga é para outro nó entãoEn aminhe(para o próximo vizinho de acordo com as Eq.6.2 e 6.3);Deposite(feromônio de acordo com Eq.6.5);

fim

senão se a formiga é do tipo forward entãoExe ute(transição Forward→ Backward);En aminhe(para o próximo vizinho de acordo com as Eq.6.2 e 6.3);Deposite(feromônio de acordo com Eq.6.5);

fim

senãoElimine(formiga);

fim

fim

senãoEn aminhe(pacote de acordo com a tabela de roteamento);

fim

fimAlgoritmo 4: Pseudo-código do MARS

113


a manipulação de bit a bit dos pacotes e para se implementar algoritmos que possam simular o

processamento de um grande conjunto de dados em diversos nós de uma rede paralelamente.

Nesse contexto C++, que é uma linguagem compilada e de uso tradicional, mostrou-se a fer-

ramenta mais eficaz. Por outro lado, é fato que, durante o processo de simulação, ajustes são

necessários com certa freqüência. O uso da linguagem OTCL, que é interpretada, evita que a

cada ajuste de parâmetro, seja necessário compilar todo o código, possibilitando uma simpli-

ficação no processo interativo de mudar e re-executar o modelo. Além de fornecer arquivos

textos com os dados de saída das simulações, que podem ser interpretados externamente,

de maneira offline, o NS permite também a utilização de módulos adicionais, como o NAM

(Network Animator) que é um visualizador gráfico de simulações e o Xgraph, que permite a

criação de gráficos [105, 106].

6.4.2 Topologias Usadas nas Simulações

Para realizar a avaliação de desempenho da implementação do MARS, a partir das simu-

lações implementadas no NS-2, foram utilizadas três topologias de redes diferentes:

1. Anel – Consiste em uma rede em anel, com seis nós interligados conforme a Fig.6.3

extraída do NAM;

2. Árvore – Consiste em uma árvore composta por um nó raiz, dois ramos principais, cada

um com três derivações, conforme a Fig.6.4 extraída do NAM;

3. Cubo – Consiste em uma rede com oito nós, cada um com três enlaces, logicamente

conectados de maneira semelhante aos vértices de um cubo, conforme a Fig.6.5 extraída

do NAM;

Foram considerados enlaces com capacidade de 1, 5 Mbps de taxa de transmissão, e 1, 5 ms

de retardo. Estas redes foram escolhidas devido a sua simplicidade e suas diferentes caracterís-

ticas topológicas, apropriadas para um primeiro conjunto de simulações do novo algoritmo.

Almeja-se, prioritariamente, a partir destas simulações, comprovar a funcionalidade dos

princípios utilizados no MARS, sobretudo a analogia criada a partir do modelo FFAC-D, e

sua eficácia na construção de tabelas de roteamento. Além disso, é analisada a ocupação de

largura de banda (overhead) e os tempos de convergência, tanto na inicialização das tabelas,

quanto na adaptação a mudanças na topologia. Durante as simulações não foi introduzido

tráfego de dados, uma vez que o intuito é verificar a capacidade do MARS de encontrar os

melhores caminhos disponíveis nas diferentes topologias de testes.

114


Figura 6.3: Topologia de rede em anel, gerada a partir do NS-2/NAM para simulações do MARS.

Figura 6.4: Topologia de rede em árvore, gerada a partir do NS-2/NAM para simulações do MARS.

Tradicionalmente, os parâmetros utilizados para a comparação de desempenho entre al-

goritmos de roteamento distintos são: Latência fim-a-fim, jitter (variação da latência), taxa de

perda de pacotes, ocupação de largura de banda e tempo de convergência [21]. No entanto, é

possível com base no desempenho observado no que diz respeito aos tempos de convergência e

ocupação de largura de banda, ter idéia do quão promissora pode ser a solução de roteamento

lançada com o MARS.

115


Figura 6.5: Topologia de rede em cubo, gerada a partir do NS-2/NAM para simulações do MARS.

6.4.3 Resultados

Foi verificado que o MARS é capaz de encontrar os melhores (menores) caminhos na rede

e compor tabelas de feromônio que refletem o grau de otimalidade das escolhas disponíveis

em cada topologia. Para cada topologia, foram feitas dez simulações, onde se pode verifi-

car a convergência do algoritmo em todos os casos. A Figura 6.6 mostra os resultados das

simulações do MARS na rede em anel para o nó 0.

Por exemplo, na Figura 6.6-a) reflete o percentual médio de feromônio presente na tabela

de feromônio do nó 0 para o destino 1. O nó 0 possui como vizinhos os nós 1 e 5, de modo que

para cada instante, a barra à esquerda indica a probabilidade de que o nó 1 seja escolhido para

o reencaminhamento dos pacotes destinados ao nó 1 e a barra à direita indica a probabilidade

de escolha do nó 5. No caso de se utilizar uma tabela de roteamento determinística, apenas

o vizinho com maior concentração de feromônio seria escolhido, neste caso, o nó 1, que é

o caminho mais curto. O mesmo raciocínio se aplica para as figuras 6.6-b), 6.6-c), 6.6-d), e

6.6-e), para os nós de destino 2, 3, 4 e 5, respectivamente.

No caso da topologia em árvore, os nós 3, 4, 5, 6, 7 e 8 possuem apenas um vizinho para

onde devem encaminhar todos os seus pacotes. Nas Figuras 6.7-a) e 6.7-b) são mostrados os

percentuais de feromônio do nó 0, para os destinos 1 e 3, nestes casos as melhores escolhas

para o roteamento é o nó 1. Nas Figuras 6.7-c), 6.7-d), 6.7-e) e 6.7-f), são mostrados percen-

tuais de feromônio da tabela do nó 1, para os destinos 0, 2, 3, e 6, respectivamente. Dado o

116


Figura 6.6: Tabela de feromônio do nó 0. Média de 10 simulações da rede com topologia em anel, para os destinos:

a)1, b)2, c)3, d)4 e e)5, computadas em diversos instantes de tempo.

efeito de simetria, a partir destes resultados é possível verificar a convergência do MARS para

as melhores escolhas em todas as situações possíveis nesta topologia.

A Figura 6.8 ilustra os percentuais médios de feromônio disponíveis no nó 0 para todos

os possíveis destinos da topologia em cubo. O nó 0 possui como vizinhos os nós 1, 2 e 3, as

Figuras 6.8-a), 6.8-b), 6.8-c), 6.8-d), 6.8-e), 6.8-f), e 6.8-g) apontam as preferências de escolhas

para os destinos 1, 2, 3, 4, 5, 6 e 7, respectivamente.

A Figura 6.9 ilustra o comportamento do desvio-padrão do percentual de feromônio do

nó 0, para cada um dos possíveis destinos da topologia em anel. É possível verificar um de-

créscimo do desvio padrão com o decorrer do tempo, o que ilustra o processo de convergência

das tabelas de feromônio no MARS.

Na comparação do MARS com o AntNet, ilustrada na Figura 6.10, é possível perceber

117


Figura 6.7: Tabelas de feromônio dos nós 0 e 1. Média de 10 simulações da topologia em árvore, a partir do nó 0

para os destinos: a)1 e b)3, e a partir do nó 1 para os destinos: c)0, d)2, e)3 e f)6, computadas em diversos instantes

de tempo.

que o MARS emite em média, cerca de três vezes mais pacotes que o AntNet. Os parâmetros

do MARS foram ajustados para que o tempo de convergência, tempo despendido para que os

algoritmos encontrem as melhores escolhas na rede, fossem similares para MARS e AntNet.

Este resultado confirma a expectativa de que o MARS possui um menor consumo de largura

de banda overhead. Isto se dá devido à diferença de tamanho entre os pacotes do MARS e do

AntNet. Os pacotes do MARS possuem um tamanho fixo e reduzido (aproximadamente 10

bytes) enquanto no AntNet, os pacotes os pacotes possuem um tamanho variável, devido à

memória das formigas, que depende do tamanho da topologia (estimado entre 30 e 70 bytes

para uma rede com 6 nós). Para redes maiores, o desempenho do MARS em relação ao

consumo de largura de banda seria ainda mais expressivo.

Para avaliar o tempo de convergência quando modificações na topologia ocorrem após

118


Figura 6.8: Tabela de feromônio do nó 0. Média de 10 simulações da rede em cubo, a partir do nó 0 para os

destinos: a)1, b)2, c)3, d)4, e)5, f )6 e g)7, computadas em diversos instantes de tempo.

a convergência inicial dos algoritmos, simulações foram realizadas a partir da topologia em

anel, com o bloqueio do enlace que conecta os nós 0 e 1 em um dado instante de tempo. É de

esperar que decorrido algum tempo após esta mudança na topologia, as tabelas de feromônio

adaptem-se às novas condições. Na Figura 6.11, apresenta-se os resultados médios (10 simu-

lações) do MARS e do AntNet para o processo de convergência das tabelas de feromônio do

nó 1 para o destino 5. Antes da interrupção do enlace 0− 5, a melhor escolha para se chegar

até o nó 5 a partir do nó 1 é o caminho 1− 0− 5, após a interrupção a melhor escolha passa

a ser o caminho 1 − 2 − 3 − 4 − 5. Na Figura 6.11-a), mostra-se os resultados para o MARS

quando o bloqueio é feito no instante t = 5 s, vê se a convergência ocorrer em poucos décimos

de segundo. Na Figura 6.11-b), mostra-se os resultados para o AntNet quando o bloqueio é

feito no instante t = 10 s, a convergência é lenta, e não ocorre mesmo após decorrido algumas

119


Figura 6.9: Desvio padrão do percentual de feromônio presente na tabela do 0, para 10 simulações da rede em

anel, computados em diversos instantes de tempo.

Figura 6.10: Comparação entre o número médio de pacotes emitidos pelos algoritmos AntNet e Mars. Média de

dez simulações com a rede em anel.

dezenas de segundos.

6.4.4 Parâmetros

Os parâmetros utilizados nas simulações discutidas acima foram ajustados de modo a per-

mitir ao MARS e AntNet, tempos equivalentes de convergência para situação de topologia

120


Figura 6.11: Média de 10 simulações da rede em anel, do percentual de feromônio do nó 1 com destino nó 5:

a)MARS com interrupção no enlace 0− 5 em 5 s, e; b)AntNet com interrupção no enlace 0− 5 em 10 s.

estática, ou seja, sem o bloqueio de nenhum enlace. Para o Antnet, os parâmetros utilizados

foram tempo de recrutamento de 0, 03 s, e fator de exploração de 0, 05 s [103], [75]. Para

o MARS, o algoritmo de recrutamento e evaporação é executado a cada 0, 001 s, com parâ-

metros que variam em torno dos seguintes valores: rod = 0, 01, rm

d = 0, 001, κ = 1, n = 4,

ε = 0, 05, γ = 0, 995 e ϕMAX = 100. A função exploratória foi omitida na implementação do

MARS apresentada nas simulações descritas na seção anterior, uma vez que não se mostraram

necessárias para os testes realizados.

6.5 Discussão

A simplicidade das formigas MARS e possibilidade de independer de ações daemon é uma

grande vantagem deste algoritmo. No MARS, a estratégia para a escolha dos melhores ca-

minhos baseia-se exclusivamente no princípio diferencial dos comprimentos (condições de

tráfego) e na auto-organização das formigas resultante de seu comportamento e sua comuni-

cação estigmérgica. Além disso, no sentido de evitar estagnação, aplicou-se duas heurísticas

bastante plausíveis do ponto de vista biológico e dependentes apenas de informações locais,

quais sejam: aversão a congestionamentos e exploração e novidades na área de forrageio,

ambas extraídas do FFAC-D.

Os resultados mostram a eficácia do método, com a convergência verificada nas três topo-

121


logias de teste escolhidas (anel, árvore e cubo), bem como o desempenho superior do MARS

em relação à ocupação de largura de banda (overhead) e tempos de convergência em rela-

ção ao AntNet. Vale ressaltar que o AntNet já mostra resultados superiores aos algoritmos

tradicionais Link State (LS) e Distance Vector (DV) [75].

Convém, na continuidade desta pesquisa, ampliar o escopo dos testes para topologias

maiores, dinâmicas mais completas e introdução de diferentes tráfegos de dados nas redes

durante as simulações. Para tal, algumas melhorias estruturais serão necessárias à atual versão

do MARS para o NS-2. Com isto é possível que o MARS possa levar ao universo das redes de

comunicações, uma estratégia de otimização mais próxima daquela observada em formigas

reais. Algumas características do MARS apontam vantagens em relação a outros algoritmos,

tais como o AntNet e os tradicionais LS e DV:

• Segurança, Alta Disponibilidade e Resiliência – A construção das tabelas de roteamento

em cada nó do MARS, depende exclusivamente de informações locais. Não há troca de

informações entre os nós. Com isto, mesmo que um dos nós da rede apresente um com-

portamento anômalo, por exemplo, enviando muitos pacotes, não há o risco deste com-

portamento anômalo ser propagado dentre o MARS. Ademais, o próprio controle interno

presente na componente exploratória do MARS (Eq. 6.3), impede a manutenção de rotas

inadequadas na tabela de roteamento, pois caso haja uma perda de pacotes significativa, o

algoritmo trata de buscar rotas alternativas. Opcionalmente, pode ser implementada uma

função a mais de segurança, com a geração de um HASH baseado no número de identifi-

cação de cada formiga, e que ocuparia este campo no pacote. Isto impediria que um nó

impostor enviasse formigas falsas com os mesmos números de identificação das formigas

autênticas presentes na tabela 6.2, o que desabilitaria a função de detecção de enlaces falto-

sos;

• Eficiência e baixo overhead – As formigas no MARS, possuem um tamanho muito reduzido,

na ordem de 20 bits, o que faz com que sua ocupação de largura de banda (overhead) seja

minimizada. Ademais, o fato de não possuir memória, de não ter que carregar dados adi-

cionais sobre as características da rede, reduzem o custo computacional de processamento

em cada um dos nós, fazendo do MARS um Sistema bastante eficiente;

• Provisão de QoS – Conforme foi discutido na seção introdutória deste capítulo, o MARS

em sua primeira implementação não se voltou especificamente para a provisão de QoS.

Entretanto, cabe observar que os mesmos mecanismos adicionados ao AntNet para este

122


objetivo específico, pode também ser adicionado ao MARS sem nenhum prejuízo, bastando

que para cada CoS (Class of Service), seja implementado um tipo (cor) de formiga e feromônio

[107–109], com requisitos mais rígidos para a manutenção das rotas , conforme a Eq. 6.3.

Ademais, por possuir formigas de tamanhos constantes, emitidas em intervalos regulares,

o MARS pode sim, apresentar vantagens para a redução de jitter, o que é um desafio para

outros algoritmos;

• Adaptabilidade – Conforme constatado a partir dos resultados das simulações, o MARS

permite que, em um curto intervalo de tempo, as melhores rotas sejam encontradas. Há um

limite na minimização deste tempo de convergência, a partir do qual qualquer algoritmo

pode comprometer sua robustez, efetuando modificações em suas tabelas de rotas como

respostas a variações locais ou puntuais de curta duração, o que pode levar a instabilidades.

É evidente que um estudo mais aprofundado, envolvendo a análise de sensibilidade dos

parâmetros e suas respostas a variações de tráfego, pode fornecer maiores subsídios para

que se otimize esta “adaptabilidade” em algoritmos de roteamento, inclusive no MARS.

Ainda assim, os resultados apontam um excelente desempenho do MARS em relação aos

outros algoritmos analisados;

• Simplicidade e Flexibilidade – A simplicidade foi premissa no desenvolvimento tanto do

FFAC-D, conforme visto no Capítulo 4, como do MARS. O resultado é um algoritmo que

mimetiza bem a auto-organização observada em formigas a partir de pacotes muito simples

e tomando decisões com base apenas em informações locais. Com relação à flexibilidade,

a partir das evidências observadas nas simulações, pode-se dizer que é pequeno o efeito

da mudança de topologia em relação ao desempenho do MARS, no entanto, simulações

mais rigorosas e com redes mais diversas são necessárias para permitir uma análise mais

quantitativa desta flexibilidade e escalabilidade. Com relação a outros aspectos, por funci-

onar apenas com base em informações locais geradas por seus próprios agentes, o MARS

independe dos tipos de serviços presentes nas camadas superiores e inferiores do Modelo

OSI.

123

Capítulo VII

Conclusões e TrabalhosFuturos

A abordagem na qual se constrói analogias entre observações da natureza e situações do

cotidiano, mostra-se capaz de levar à superação de muitos dos problemas que desa-

fiam a tecnologia. Estas analogias buscam capturar estratégias aperfeiçoadas pelo processo

evolucionário natural para propor soluções inovadoras a problemas dos mais diversos contex-

tos. Inúmeros exemplos destas soluções podem ser vistos na literatura associada à Inteligência

Computacional, onde meta-heurísticas inspiradas em fenômenos naturais, tais como Algorit-

mos Genéticos, Computação Evolucionária e Co-evolucionária, Redes Neurais e Otimização

de Enxames de Partículas e PSO (Particle Swarm Optimization têm resultado em diversas tecno-

logias de uso prático [2, 5].

Nesta pesquisa, buscou-se, primeiramente, a partir de uma abordagem mais científica [3]

justamente capturar as estratégias utilizadas pelas colônias de formigas para encontrar os

melhores caminhos entre o ninho e os alimentos. Para tal, no Capítulo 2 foi analisado o

comportamento das colônias de formigas observado em experimentos de laboratório e um

primeiro modelo proposto para o comportamento destas colônias [15], o modelo FFAC [1],

cujos resultados são satisfatórios para os experimentos com o ambiente de forrageio estático,

mas que apresenta o problema da estagnação para ambientes dinâmicos.

No Capítulo 3, buscou-se mais evidências na literatura sobre a etologia, sociobiologia e

fisiologia dos insetos. O intuito foi subsidiar o refinamento do modelo FFAC proposto anteri-

ormente [1], superando a estagnação e tornando-o capaz de reproduzir o comportamento das

———— Conclusões e Trabalhos Futuros————

formigas em situações nas quais ocorrem mudanças em sua área de forrageio. No Capítulo 4,

propõe-se modelo FFAC-D, a primeira contribuição relevante desta pesquisa, cuja versão pre-

liminar foi publicada em Bandeira de Melo & Araújo [23], e que incorpora ao modelo FFAC

o comportamento exploratório observado nas formigas naturais, a evaporação do feromônio,

e as limitações de suas capacidades sensoriais. O FFAC-D manteve a plausibilidade biológica

em toda sua formulação e seus resultados mostram a superação das deficiências do modelo

FFAC, com simulações representativas do comportamento experimental observado.

Em seguida, estabeleceu-se a analogia entre as redes de comunicações e o comportamento

das colônias de formigas forrageiras observado em laboratório e modelado pelo FFAC-D. Para

tal, no Capítulo 5 foi feita uma breve revisão da literatura sobre os algoritmos de roteamento

baseados no comportamento das formigas, e, no Capítulo 6, propões-se o MARS (Memoryless

Ants Routing System.

O MARS, a segunda contribuição desta pesquisa, é uma nova solução de roteamento e

possui em sua formulação a preocupação com aspectos tais como simplicidade, flexibilidade,

segurança, resiliência e eficiência, o que o torna promissor para o problema do roteamento.

Os primeiros resultados do MARS, a partir de sua implementação no NS-2 (Network Simulator

versão 2) apontam um desempenho superior ao AntNet, que por sua vez apresenta desempe-

nho superior aos tradicionais algoritmos de roteamento DV (Distance Vector) e LS(Link State.

Resultados ainda mais expressivos podem ser obtidos com a continuidade das investiga-

ções, tanto em busca de modelos mais representativos dos comportamentos das formigas,

quanto em busca de algoritmos de roteamento superiores, dados os seus contextos e aplica-

ções. Seguem algumas sugestões de trabalhos futuros.

7.1 Sugestões para Estudos Futuros

• Novos experimentos com formigas em laboratório, com outros aparatos para a área de

forrageio e outras dinâmicas para a introdução de obstáculos entre a fonte de alimentos e

o ninho das colônias;

• Análise de sensibilidade dos parâmetros do FFAC-D e refinamento do modelo;

• Estudo analítico dos sistemas dinâmicos associados ao FFAC-D e ao MARS;

• Extensão do FFAC-D para otimização em domínios contínuos;

• Aperfeiçoamento da implementação do MARS no NS-2, permitindo a construção de simu-

125


lações mais realísticas;

• Análise de sensibilidade dos parâmetros do MARS sob diferentes condições de tráfego;

• Aplicação do MARS ao roteamento em redes móveis ad hoc.

126

———— Referências————

Referências

[1] K. Vittori, Experimental study, modeling and implementation of ant colony behavior

in a dynamic environment. Tese, Escola de Engenharia de São Carlos, Universidade de

São Paulo, 2005.

[2] E. Bonabeau, M. Dorigo, & G. Theraulaz, Swarm Intelligence: From Natural to Ar-

tificial Systems. Oxford University Press, New York, 1999.

[3] K. R. Popper, A lógica da pesquisa científica. São Paulo: Cultrix, 1972.

[4] S. Hildebrandt & A. Tromba, The Parsimonious Universe. Copernicus Springer-

Verlag, New York,Inc., 1996.

[5] J. Kennedy, R. C. Eberhart, & Y. Shi, Swarm intelligence. Morgan Kaufmann Press,

San Francisco, 2001.

[6] S. Camazine, J.-L. Deneubourg, F. N., S. Sneyd, E. Bonabeau, & G. Theraulaz, Self-

organisation in Biological Systems. Princeton University Press., 2001.

[7] H. Haken, Synergetics. Springer-Verlag., 1977.

[8] G. Nicolis & I. Prigogine, Self-organization in Non-equilibrium Systems. Wiley.,

1977.

[9] E. J. H. Robinson, D. E. Jackson, M. Holcombe, & F. L. W. Ratnieks, ’no entry’ signal

in ant foraging, Nature, v. 438, p. 442, 2005.

[10] B. Hölldobler, Multimodal signals in ant communication. J. Comp. Physiol. A, v. 184,

p. 129 – 141, 1999.

[11] C. Blum, Ant colony optimization: Introduction and recent trends. Phys. Life Rev., v. 2,

p. 353 – 373., 2005.

127


[12] D. Helbing & J.-L. Deneubourg, Optimal traffic organization in ants under crowded

conditions. Nature, v. 428, p. 137 – 172, 2004.

[13] F. L. W. Ratnieks, J. L. Deneubourg, & R. Jeason, Pheromone trail decay rates on dif-

ferent substrates in the pharaoh’s ant, monomorium pharaonis. Physiol. Ento., v. 28, p.

192 – 198, 2003.

[14] J. Halloy, J. L. Deneubourg, J. Millor, & J. M. Amé, Individual discrimination capabi-

lity and collective decision-making. J. Theor. Biol., v. 239, p. 313 – 323, 2006.

[15] K. Vittori, G. Talbot, J. Gautrais, A. F. R. Araújo, & V. Fourcassié, Path efficiency of

ant foraging trails in an artificial network, J. Theor. Biol., v. 239, p. 507 – 515, 2006.

[16] K. Vittori, J. Gautrais, A. F. R. Araújo, & V. Fourcassié, Modelling ants behavior under

a variable environment, Lect. Not. Comp. Sci., v. 3172, p. 190 – 201, 2004.

[17] M. Dorigo, G. Di Caro, & L. M. Gambardella, Ant algorithms for discrete optimiza-

tion. Artif. Life, v. 5 (2), p. 137 – 172, 1999.

[18] J. Buhl, J. Gautrais, J. L. Deneubourg, P. Kuntz, & G. Theraulaz, The growth and

form of tunnelling networks in ants. J. Theor. Biol., v. 243, p. 287 – 298, 2006.

[19] S. Appleby & S. Steward, Mobile software agents for control in telecommunication

networks, Technology Journal of British Telecom, v. 12, p. 104 – 113, 1994.

[20] S. S. Dhillon & P. V. Mieghem, Performance analysis of the antnet algorithm„ Computer

Networks, p. doi:10.1016/j.comnet, 2006.

[21] A. Soltani, M. R. Akbarzadeh, & M. Naghibzadeh, Helping ants for adaptive network

routing, Journal of the Franklin Institute,, v. 343, p. 389 – 403, 2006.

[22] N. Bean & A. Costa, An analytic modelling approach for networkt routing algorithms

that use "ant-like"mobile agents, Computer Networks, v. 49, p. 243 – 268, 2005.

[23] E. B. Bandeira de Melo & A. F. R. Araújo, Modelling ant colony foraging in dynamic

and confined environment. Proc. Genetic and Evolutionary Computing Conference, ACM,

2008.

[24] D. Cassill, W. R. Tschinkel, & S. B. Vinson, Nest complexity, group size and brood

rearing in the fire ant, solenopsis invicta, Insectes Soc., v. 49, p. 158 – 162, 2002.

128


[25] W. Tschinkel, The nest architecture of the florida harvester ant, pogonomyrmex badius.

J. Insect Sci., v. 4, p. 1 – 19, 2004.

[26] G. J. Skinner, Territory, trail structure and activity patterns in the wood ant, f. rufa

(hymenoptera: Formicidae), in limestone woodland in north-west england, J. Anim.

Ecol., v. 49, p. 381 – 394, 1980.

[27] R. Beckers, J.-L. Deneubourg, & S. Goss, Trails and u-turns in the selection of a path

by the ant lasius niger. Journal of Theoretical Biology, v. 159, p. 397 – 415, 1992.

[28] J.-L. Deneubourg, S. Aron, S. Goss, & J. M. Pasteels, The self-organizing exploratory

pattern of the argentine ant, J. Insect Behav., v. 3(2), p. 158 – 168, 1990.

[29] V. V. Key & T. C. S. E. Baker, Observations on the trail deposition and recruitment

behavior of the argentine ant, iridomyrmex humilis (hymenoptera: Formicidae), Annals

of the Entomological Society of America,, v. 79, p. 283 – 288., 1986.

[30] H. Schöne, Spatial orientation, Princeton University Press., v. S. Princeton, NJ, 1984.

[31] M. Guo, Y. Liu, & J. Malec, A new q-learning algorithm based on the metropolis crite-

rion, IEEE Transactions on Systems, Man, and Cybernetics Part B : Cybernetics, v. 34, p. 2140

– 2143, 2004.

[32] E. O. Wilson & B. Hölldobler, The rise of the ants: A phylogenetic and ecological

explanation. Proc. Natl. Acad. Sci. USA, v. 102 (21), p. 7411 – 7414, 2005.

[33] D. R. Chialvo & M. M. Millonas, How swarms build cognitive maps, In Steels, L. (Ed.):

The Biology and Technology of Intelligent Autonomous Agents, NATO ASI Series, v. 144, p. 439

– 450, 1995.

[34] E. D. Jackson & F. L. W. Ratnieks, Communication in ants, Current Biology, v. 16, p. 570

– 574, 2003.

[35] B. Hölldobler & E. O. Wilson, Nest area exploration and recognition leafcutter ants,

atta cephalotes, J. Insect Physiol., v. 32, p. 143 – 150, 1986.

[36] D. Demolin, J.-L. Deneubourg, S. C. Nicolis, & C. Detrain, Optimality of collective

choices: A stochastic approach. Bulletin of Mathematical Biology, v. 65, p. 795 – 808.,

2003.

129


[37] J. A. Denny, W. J., & B. Grief, Foraging efficiency in the wood ant, formica rufa:is time

of the essence in trail following? Anim. Behav., v. 62, p. 139 – 146, 2001.

[38] D. J. T. Sumpter & M. Beekman, From non linearity to optimality:pheromone trail fo-

raging by ants, Anim. Behav., v. 66, p. 273 – 280, 2003.

[39] R. Jeanson & J.-L. Deneubourg, Path selection in cockroaches, The Journal of Experimen-

tal Biology, v. 209, p. 4768 – 4775, 2006.

[40] J. M. Ame, C. Rivault, & J.-L. Deneubourg, Cockroach aggregation based on strain

odour recognition, Anim. Behav., v. 68, p. 793 – 801, 2004.

[41] T. S. Collet, Insect navigation en route to the goal: Multiple strategies for the use of

landmarks. The Journal of Experimental Biology, v. 199, p. 227 – 235, 1996.

[42] M. Collett, T. S. Collett, & R. Wehner, Calibration of vector navigation in desert

ants, Current Biology, v. 9, p. 1031 – 1034, 1999.

[43] M. Collet & T. S. Collet, How do insects use path integration for their navigation?

Biological Cybernetics, v. 83, p. 245 – 259, 2000.

[44] M. Collett & T. S. Collett, How do insects represent familiar terrain? Journal of

Physiology, v. 98, p. 259 – 264, 2004.

[45] T. S. Collett, P. Graham, & V. Durier, Route learning by insects, Current Opinion in

Neurobiology, v. 13, p. 718 – 725, 2003.

[46] M. Collett & T. S. Collett, Insect navigation: No map at the end of the trail? Current

Biology, v. 16, p. 48 – 51, 2006.

[47] F. C. Dyer, Spatial memory and navigation by honeybees on the scale of foraging range,

The Journal of Experimental Biology, v. 199, p. 147 – 154, 1996.

[48] R. Wehner, Desert ant navigation: how miniature brains solve complex tasks, J. Comp.

Physiol. A, v. 189, p. 579 – 588, 2003.

[49] G. Grah, R. Wehner, & B. Ronacher, Path integration in a three-dimensional maze:

ground distance estimation keeps desert ants cataglyphis fortis on course, The Journal of

Experimental Biology, v. 208, p. 4005 – 4011, 2005.

130


[50] M. Knaden & R. Wehner, Ant navigation: resetting the path integrator, The Journal of

Experimental Biology, v. 209, p. 26 – 31, 2006.

[51] J. Watmough & L. Edelstein-Keshet, Modelling the formation of trail networks by

foraging ants, J. theor. Biol., v. 176, p. 357 – 371, 1995.

[52] A. D. Vincent & M. R. Myerscough, The effect of a non-uniform turning kernel on ant

trail morphology, J. Mathematical Biology, v. 49, p. 391 – 432, 2004.

[53] L. Edelstein-Keshet, J. Watmough, & G. B. Ermentrout, Trail following in ants: in-

dividual properties determine population behaviour, Behav Ecol Sociobiol, v. 36, p. 119 –

133, 1995.

[54] A.-C. Mailleux, J.-L. Deneubourg, & C. Detrain, How do ants assess food volume?

Anim. Behav., v. 59, p. 1061 – 1069, 2000.

[55] V. V. Key & T. C. Baker, Trail-following responses of the argentine ant, iridomyrmex

humilis (mayr), to a synthetic trail pheromone component and analogs. J. Chem. Ecol.,

v. 8, p. 1 – 14, 1982.

[56] Lesgreenberg & J. Klotz, Argentine ant (hymenoptera: Formicidae) trail pheromone

enhances consumption of liquid sucrose solution, Journal of Economy Entomology, v. 93,

p. 119 – 122, 2000.

[57] R. Jeanson, F. L.W. Ratnieks, & J.-L. Deneubourg, Pheromone trail decay rates on diffe-

rent substrates in the pharaoh?s ant, monomorium pharaonis, Physiological Entomology,

v. 28, p. 192 – 198, 2003.

[58] R. V. Solé, E. Bonabeau, J. Delgado, P. Fernández, & J. Marín, Pattern formation and

optimization in army ant raids, Santa Fé Institute, p. 1 – 11, 1999.

[59] J. Millor, J. M. Ame, J. Halloy, & J.-L. Deneubourg, Individual discrimination capa-

bility and collective decision-making, Journal of Theoretical Biology, v. 239, p. 313 – 323,

2006.

[60] K. E. Green, ’stop’ and ’go’ foraging signals in eusocial insects, Dissertação, APS 402

Dissertation - http://www.shef.ac.uk/, 2001.

[61] I. D. Couzin & N. R. Franks, Self-organized lane formation and optimized traffic flow

in army ants, Proc. Royal Soc. London B, v. DOI 10.1098 / rspb.2002.2210, p. 1 – 8, 2002.

131


[62] A. Dussutour, V. Fourcassie, D. Helbing, & J.-L. Deneubourg, Optimal traffic organi-

zation in ants under crowded conditions, Nature, v. 428, p. 70 – 73, 2004.

[63] H. F. Wedde & M. Farooq, A comprehensive review of nature inspired routing algo-

rithms for fixed telecommunication networks, Journal of Systems Architecture, v. 52, p. 461

– 484, 2006.

[64] A. Dussutour, J.-L. Deneubourg, & V. Fourcassié, Temporal organization of bi-

directional traffic in the ant lasius niger (l.), The Journal of Experimental Biology, v. 208, p.

2903 — 2912, 2005.

[65] D. E. Jackson, S. J. J. Martin, M. Holcombe, & F. L. W. Ratnieks, Longevity and detec-

tion of persistent foraging trails in pharaoh’s ants, monomorium pharaonis (l.), Anim.

Behav., v. 71, p. 351 – 359, 2006.

[66] J.-L. Deneubourg, A. Dussutour, & V. Fourcassié, Temporal organization of bi-

directional traffic in ant lasius niger, J. Exp. Biol., v. 208, p. 2903 – 2912, 2005.

[67] A. Dussutour, S. C. Nicolis, J.-L. Deneubourg, & V. Fourcassié, Collective decisions

in ants when foraging under crowded conditions. Behav. Ecol. Sociobiol., v. 61, p. 17 – 30,

2006.

[68] I. D. Couzin & N. R. Franks, Self-organized lane formation and optimized traffic flow

in army ants, Proc. Royal Soc. London – B, v. 606(02), p. 1 – 8, 2002.

[69] R. Jeanson & J. L. Deneubourg, Path selection in cockroaches, J. Exp. Biol., v. 209, p.

4768 – 4775, 2006.

[70] K. M. Sim & W.H. Sun, Ant colony optimization for routing and load-balancing: Survey

and new directions, IEEE Trans. Sys. Man Cyber., v. A, 33(5), p. 560 – 572, 2003.

[71] J. Watmough & L. Edelstein-Keshet, Modelling the formation of trail networks by

foraging ants. J. Theor. Biol., v. 176, p. 357 – 371, 1995.

[72] D. R. Chialvo & M. M. Millonas, How swarms build cognitive maps, Biol. Tech. Intel.

Auto. Agents, Nato ASI Series, Luc Steel, v. 144, p. 439 – 450, 1995.

[73] R. V. Solé, B. E., J. Delgado, P. Fernandez, & Marín, Pattern formation and optimiza-

tion in army ant raids, Artif. Life, v. 6(3), p. 219 – 226, 2000.

132


[74] G. Di Caro & M. Dorigo, Antnet: A mobile agents approach to adaptive routing,

IRIDIA 97-12, 317 – 365, Relatório Técnico, 1997.

[75] ——, Antnet: Distributed stigmergetic control for communications networks, Journal of

Artificial Intelligence Research, v. 9, p. 317 – 365, 1998.

[76] R. Schoonderwoerd, O. Holland, J. Bruten, & L. Rothkrantz, Ants for load balan-

cing in telecommunication networks, HP Labs, Bristol, Relatório Técnico, 1996.

[77] G. Di Caro, Two ant colony algorithms for best-effort routing in datagram networks,

In: Proceedings of the Tenth IASTED, 1998.

[78] ——, Ant colony optimization and its application to adaptive routing in telecommuni-

cation networks, Tese, Université de Bruxelles – Faculté de Sciences Appliquées, 2004.

[79] S. Liang, A. N. Zincir-Heywood, & M. I. Heywood, The effect of routing under local

information using a social insect metaphor, CEC’02: Proceedings of the Congress on Evoluti-

onary Computation, p. 1438 – 1443, 2002.

[80] G. Di Caro, F. Ducatelle, & L. M. Gambardella, Anthocnet: An ant-based hybrid

routing algorithm for mobile ad hoc networks, Lecture Notes in Computer Science, Springer

Berlin, v. 3242, p. 461 – 470, 2004.

[81] M. Saffarian & M. C. Morogan, A novel protocol to prevent malicious nodes from

misdirecting forward ants in antnet algorithm, ACM SAC’08, p. 1849 – 1853, 2008.

[82] K. M. Sim & W.H. Sun, Ant colony optimization for routing and load-balancing: Survey

and new directions, IEEE Transactions on Systems, Man, and Cybernetics - PART A: Systems

and Humans, v. 33, p. 5, 2003.

[83] O. Simonin, J. Ferber, & V. . Decugis, Performances analysis in collective systems, In:

Third International Conference on Multi Agent Systems (ICMAS’98), 1998, pp.469.

[84] K. Park & Y. Kim, Analysis of antnet routing scheme by using queueing model, Computer

Communications, v. 31, p. 2951 – 2958, 2008.

[85] J.-H. Yoo, R. J. La, & A. M. Makowski, Convergence results for ant routing, CISS, Prin-

ceton University, NJ., p. 1 – 6, 2004.

133


[86] W. Qu, H. Shen, & J. Sumb, New analysis on mobile agents based network routing,

Applied Soft Computing, v. 6, p. 108 – 118, 2005.

[87] M. Strobbe, V. Verstraete, E. Van Breusegem, J. Coppens, M. Pickavet, & P. Deme-

ester, Implementation and evaluation of antnet, a distributed shortest-path algorithm,

Proc. of the Adv. Ind. Conf. on Tel., 2005.

[88] Y. Yang, A. N. Zincir-Heywood, M. I. Heywood, & S. Srinivas, Agent-based routing

algorithms on a lan, Proceedings of the 2002 IEEE Canadian Conference on Electrical & Com-

puter Engineering, p. 1442 – 1447, 2002.

[89] F. Ducatelle, G. Di Caro, & L. M. Gambardella, Using ant agents to combine reactive

and proactive strategies for routing in mobile ad hoc networks,WSPC/157-IJCIA, v. 18(5),

p. 1 – 15, 2005.

[90] M. Abolhasan, T. Wysock, & E. Dutkiewicz, A review of routing protocols for mobile

ad hoc networks, Ad Hoc Networks, v. 2, p. 1 – 22, 2004.

[91] N. K. Cauvery & K. V. Viswanatha, Enhanced ant colony based algorithm for routing in

mobile ad hoc network, Proceedings of World Academy of Science, Engineering and Technology,

v. 36, p. 30 – 35, 2008.

[92] K. Oida & M. Sekido, Ars: an efficient agent-based routing system for qos guarantees,

Computer Communications, v. 23(14-15), p. 1437 – 1447, 2000.

[93] K. Fujita, A. Saito, T. Matsui, & H. Matsuo, An adaptive ant-based routing algorithm

used routing history in dynamic networks, In Proc. of the 4th Asia-Pacific Conf. on Simulated

Evolution and Learning, 2002.

[94] S. Marwaha, C. K. Tham, & D. Srinivasan, Mobile agents based routing protocol for

mobile ad hoc networks, Proceedings of IEEE Globecom, 2002.

[95] M. Günes, U. Sorges, & I. Bouazizi, Ara - the ant-colony based routing algorithm for

manets, ICPP Workshop on ad hoc networks (IWAHN), p. 79 – 85, 2002.

[96] J. S. Baras & H. Mehta, A probabilistic emergent routing algorithm for mobile ad hoc

networks, WiOpt03: Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks,

2003.

134


[97] M. Roth & S. Wicker, Termite: Emergent ad-hoc networking, Proceedings of the Second

Mediterranean Workshop on Ad-Hoc Networks, 2003.

[98] G. Di Caro, F. Ducatelle, & L. M. Gambardella, Anthocnet: An adaptive nature-

inspired algorithm for routing in mobile ad hoc networks – technical report no. idsia-

27-04-2004:, IDSIA / USI-SUPSI, Dalle Molle Institute for Artificial Intelligence, Galleria

2, 6928 Manno, Switzerland, Relatório Técnico, 2004.

[99] X. Zheng, W. Guo, & R. Liu, An ant-based distributed routing algorithm for ad-hoc

networks, International Conference on Communications, Circuits and Systems, ICCCAS., v. 1,

p. 412 – 417, 2004.

[100] B. Tatomir, J. Boehle, & L. Rothkrantz, Dynamic routing in traffic networks and ma-

nets using ant based algorithms, Proceedings of the 7th International Conference on Artificial

Evolution, 2005.

[101] S. Rajagopalan & C.-C. Shen, Ansi: A unicast routing protocol for mobile ad hoc

networks using swarm intelligence, Journal of Systems Architecture, v. 52(8-9), p. 485 –

504, 2006.

[102] S. S. Dhillon, X. Arbona, & P. Van Mieghem, Ant routing in mobile ad hoc networks,

Proceedings of the Third International Conference on Networking and Services, p. 67, 2007.

[103] V. Laxmi, L. Jain, & M. Gaur, Ant colony optimization based routing on ns-2, Proc. Int.

Conf. on Wireless Communication and Sensor Networks, WCSN, 2006.

[104] M. Heusse, D. Snyers, S. Guerin, & P. Kuntz, Adaptive agent-driven routing and load

balancing in communication networks technical report rr-98001-iasc. ENST de Bre-

tagne, Relatório Técnico, 1998.

[105] K. Fall & K. Varadhan, The NSManual. The VINT Project., A Collaboration between

researchers at UC Berkeley, LBL, USC/ISI, and Xerox PARC., 2008.

[106] M.M. Coutinho, NETWORK SIMULATOR, Guia Básico para Iniciantes, UFPA, 2003.

[107] S. Subing & L. Zemin, A qos routing algorithm based on ant algorithm, ICC 2001 - IEEE

International Conference on Communications, v. 5(1), p. 574 – 578, 2000.

135


[108] L. Carrillo, J. Marzo, L. Fàbrega, P. Vilà, & C. Guadall, Ant colony behaviour as rou-

ting mechanism to provide quality of service, Lecture Notes in Computer Science, Springer,

p. 418 – 419, 2004.

[109] H. Lee, G. Choi, H. Kim, & K. Lee, A nature-inspired qos routing algorithm for next ge-

neration networks, Fourth International Conference on Autonomic and Autonomous Systems,

IEEE Comp. Soc., v. 51, p. 226 – 232, 2008.

[110] D. Subramanian, P. Druschel, & J. Chen, Ants and reinforcement learning: a case study

in routing in dynamic networks, International Joint Conference on Artificial Intelligence, p.

832 – 839, 1998.

[111] V. der Put & Rothkrantz, Routing in packet switched networks using agents. simula-

tion practice and theory, in press, v. 9, p. 317 – 365, 1999.

[112] G. Di Caro & M. Dorigo, Ant Colonies for Adaptive Routing in Packet-Switched

Communications Networks, Springer, Ed. DiCaro Lecture Notes in Computer Sci-

ence, PPSN V, LNCS, 1998.

[113] T. White, B. Pagurek, & F. Oppacher, Asga: Improving the ant system by integration

with genetic algorithms, Proc. 3rd Genetic Programming Conf., p. 610 – 617, 1998.

[114] B. Baran & R. Sosa, Antnet: Routing algorithm for data networks based on mobile

agents, In: Argentine Symposium on Artificial Intelligence, 2000.

[115] I. Kassabalidis, M. El-Sharkawi, R. Marks II, P. Arabshahi, & A. Gray, Intelligent

routing and bandwidth allocation in wireless networks, In: ETC proceedigns, 2001.

[116] K. M. Sim & W. H. Sun, Multiple ant-colony optimization for network routing, Proc. of

the 1st Int. Symp.on Cyber Worlds, IEEE Comp. Soc., 2002.

[117] F. Tekiner, F. Z. Ghassemlooy, & S. Al-khayatt, The antnet routing algorithm - a modi-

fied version, Proc. 4th inter. Symposium on communication systems, networks and DSP, p. 428

– 432, 2004.

[118] ——, Improved antnet routing algorithm with link probability evaporation over the

given time window, SoftCom, v. 1, p. 134 – 137, 2004.

136


[119] K. A. Amin & A. R. Mikler, Agent-based distance vector routing: a resource effici-

ent and scalable approach to routing in large communication networks, The Journal of

Systems and Software, v. 71, p. 215 – 227, 2004.

[120] ——, Towards resource efficient and scalable routing: an agent-based approach, CSE

UNT, v. 1, 2002.

[121] S. Liang, A. N. Zincir-Heywood, & M. I. Heywood, The effect of routing under local

effect traffic using a social insect metaphor, IEEE International Congress on Evolutionary

Computation, p. 1438 – 1443, 2002.

[122] Y. Lü, G. Zhao, & F. Su, Adaptive ant-based dynamic routing algorithm, Proceedings of

the 5th World Congress on Intelligent Control and Automation, v. Hangzhou, P.R. China„

2004.

[123] S. Doi & M. Yamamura, Congestion detection and clearing history of trip time in antnet,

Evolutionary Computation, The 2005 IEEE Congress on, v. 2, p. 1621 – 1628, 2005.

[124] R. A. Arnous, H. A. Arafat, & M. M. Salem, Improving the load balancing within the

data network via modified antnet algorithm, IEEE, 2007.

[125] A. Pany, G. Kappel, & E. Michlmayr, Using taxonomies for content-based routing with

ants, Computer Networks, v. 51, p. 4514 – 4528, 2007.

[126] R. F. Vallejo, H-antnet: Hierarchical routing for improving ant colony optimization sys-

tems, Seminario de investigación II, Instituto Tecnológico y de Estudios Superiores de Monterrey,

México., v. CS 6002, p. 1 – 4, 2007.

137


Apêndice ITabela de ANTRALs

Na Tabela A.1, estão tabelados os principais ANTRALs (Ant Routing Algorithms), ordena-

dos pelo ano de publicação. Na terceira coluna é apontado o algoritmo no qual o ANTRAL

se baseia, na quarta coluna seus autores e em seguida uma breve descrição.

138

————

Refer

ências————

Tabela .1: ANTRALs e suas características.

Algoritmo Ano Base Autoria Descrição

Precursores dos

ANTRALs

1993 AS Appleby &

Steward [19]

Primeiras idéias de Ant System (AS) para a solução de roteamento

ABC 1996 AS Schoonderwoerd,

et al. [76]

O (Ant Based Control) foi projetado para roteamento e balanceamento

de carga. Destaca-se o fato de que, no ABC, as formigas armazenam

apenas o tempo de sua criação e depositam feromônio em cada trecho

de seu percurso origem-destino, estabelecendo trilhas para as formigas

que fazem o percurso inverso.

AntNet 1997 AS Di Caro et al.

[75], [80]

Serve de base para maioria dos algoritmos que se propõem a aplicar a

meta-heurística ACO ao problema de roteamento em redes de pacotes.

A robustez e o bom desempenho (próximo ao ótimo) do AntNet fazem

dele uma solução atrativa. Simulações indicam que o desempenho do

AntNet é comparável ao algoritmo Dijkstra para a busca de melhores

caminhos em um grafo, e apresenta vantagens em redes esparsas ou de

parâmetros variáveis, o que mostra sua robustez [20].

Continua . . .

139

————

Elto

nBer

nar

doBan

deir

adeMelo————


Formigas Regular

e Uniforme

1998 ABC Subramanian et

al. [110]

Introduz as formigas dos tipos regular e uniforme. A maior diferença

entre elas é no tocante ao comportamento exploratório. As formigas

uniformes escolhem seus próximos nós (next hop) uniformemente entre

os vizinhos ao invés de usar as informações disponíveis na tabela de

feromônio. As formigas regulares escolhem os próximos vizinhos com

base nas entradas da tabela de rotas e costumam avaliar e armazenar o

custo das rotas que percorrem para definirem a quantidade de feromô-

nio a ser depositada, elas apresentam um bom desempenho em redes de

custo simétrico e com muitas variações de topologia em relação ao (Link

State e Distance Vector). Isto ocorre devido à carga (overhead) que as for-

migas regulares introduzem na rede, que independe da quantidade de

mudanças na topologia da rede. Nos algoritmos convencionais o tráfego

cresce com o número de variações na topologia da rede.

ABC-backward 1998 AntNet Van der Put &

Rothkrantz [111]

Baseado no ABC, mas aplica conceitos do AntNet para a atualização das

tabelas de feromônio. No ABC-backward, as formigas forward armaze-

nam informações sobre suas viagens e as formigas backward refazem os

percurso origem-destino em sentido inverso, atualizando as tabelas de

feromônio de acordo com as condições de tráfego observadas. Resolve

problemas de exploração da rede, estimação de retardo e balanceamento

de carga.

Continua . . .

140

————

Refer

ências————


AntNet-FA 1998 AntNet DiCaro e Dorigo

[77], [112]

As formigas backward não compartilham as mesmas filas que os pacotes

de dados, ao invés disso, usam uma fila de alta prioridade na entrada

dos nós, i.e. são mais rápidas que os outros pacotes.

Smart Ants 1998 ABC Bonabeau, et

al.[58]

Baseado em conceitos de Programação Dinâmica, insere um novo tipo

de formigas, chamado de smart agents, que estão habilitadas a atualizar

toda a tabela de feromônio em cada nó por onde passam, e não apenas

as rotas associadas com sua origem. Apresenta desempenho significati-

vamente melhor, sobretudo para redes sujeitas a variações de tráfego.

Continua . . .

141

————

Elto

nBer

nar

doBan

deir

adeMelo————


CAF 1998 ABC Heusse et al. [104] Para roteamento e balanceamento de carga em redes de pacotes assimé-

tricas. No CAF (Cooperative Asymmetric Forwarding, as formigas carregam

estimativas de tráfego de todos os nós por onde passam e atualizam to-

das as entradas correspondentes, nas tabelas de feromônio dos nós onde

chegam. Utilizam estimativas feitas no caminho origem-destino para

atualizarem trilhas de feromônio relativas ao caminho inverso (destino-

origem). A principal idéia deste algoritmo é comutar pacote como se

estes estivessem percorrendo em sentido inverso o caminho percorrido

pelas formigas, como conseqüência, uma tabela reversa adicional pre-

cisa ser mantida em cada nó. Não funciona bem em cenários de baixo

tráfego, onde um pequeno número de pacotes de dados são enviados,

porque nestas condições, uma formiga carregará consigo valores desatu-

alizados, o que pode degradar o desempenho do algoritmo. Simulações

mostram que o CAF apresenta melhor desempenho que o AntNet em

termos de tempo de convergência e retardo médio, é simples e reage de

maneira apropriada a mudanças na rede, necessitando apenas do ajuste

dois ou três parâmetros.

Continua . . .

142

————

Refer

ências————


ASGA 1998 AS e AG White [113] Propõe a integração entre Algoritmos Genéticos (AG) e ANTRALs. O

Sistema ASGA integra o AS (Ant System) com um AG com o propósito

de controlar o processo de adaptação à rede. Permite a adaptação dos

parâmetros de ajuste do ANTRAL, considerando os custos dos enlaces

e as concentrações de feromônio percebidas. O ASGA foi aplicado a

três classes de problemas: i)achar o melhor caminho entre dois pontos

da rede; ii) buscar o melhor caminho que envolva um subconjunto de

nós da rede, e; iii)encontrar o menor laço entre dois pontos da rede. O

algoritmo resolveu com sucesso todos estes problemas, com um melhor

desempenho para redes que apresentam conexões razoavelmente dura-

douras, tais como as redes orientadas à conexão.

Continua . . .

143

————

Elto

nBer

nar

doBan

deir

adeMelo————


AntNet Modifi-

cado

2000 AntNet Barán & Sosa

[114]

Apresenta diversas melhorias ao AntNet: inicialização inteligente para

minimização do retardo inicial; atualização da tabela de roteamento de

modo a minimizar o tempo de recuperação no caso de falhas nos enla-

ces da rede; introdução de um fator aleatório e limites para os valores

das probabilidades, de modo a minimizar a estagnação da rede; auto-

destruição das formigas backward que não retornam às suas origens; mé-

todo dual para a seleção o próximo salto (next hop (aleatório conforme o

AntNet original ou hierárquico como no ABC), e; controle do número de

formigas dentro da rede, proporcionalmente ao número de nós. O de-

sempenho do AntNet modificado melhorou significativamente quando

comparado com o AntNet original ou com os algoritmos convencionais

LS e DV.

Continua . . .

144

————

Refer

ências————


AntNet adaptado

para QoS

1998 AntNet Subing & Zemin

[107]

Para o roteamento com vistas à Qualidade de Serviço (QoS), o algo-

ritmo utiliza múltiplas métricas de QoS, tais como retardo, jitter, largura

de banda e taxa de perdas, ao invés do algoritmos tradicionais de rotea-

mento, que utilizam uma única métrica, que pode ser o custo, o número

de saltos, o tamanho das filas, etc. Neste algoritmo, para cada Classe

de Serviço (CoS), com diferentes requisitos de QoS, foi associada uma

diferente formiga e um diferente feromônio. Para cada rota e CoS, o

algoritmo escolhe globalmente a melhor formiga que escolhe as rotas

de menor custo e satisfaz aos requisitos de QoS, para a atualização das

tabelas de feromônio ao longo do caminho. Simulações apontam um

desempenho superior do algoritmo;

SDR Adaptativo 2002 Kassabalidis, et al.

[115]

Não se baseia no ABC ou no AntNet e mostra melhores resultados que

o AntNet, LS e DV para redes muito grandes. O SDR-Adaptativo possui

atrativos tais como escalabilidade e alta utilização dos recursos da rede

e evita oscilações nas tabelas de roteamento.

Continua . . .

145

————

Elto

nBer

nar

doBan

deir

adeMelo————


MACO 2002 AntNet Sim & Sun [116] O paradigma de solução de problemas de roteamento MACO (Multiple

Ant Colony Optimization) propõe uma abordagem para mitigação da es-

tagnação do AntNet. No MACO, as formigas de uma determinada cor

respondem apenas aos feromônios de mesma cor, elas também possuem

um mecanismo de repulsão que evita formigas de diferentes cores (colô-

nias) de escolherem o mesmo caminho. A adoção de múltiplas colônias

de formigas na busca de melhores caminhos melhora a adaptabilidade e

reduz as chances de estagnação. Em uma rede dinâmica onde os enlaces e

nós podem mudar constantemente, o MACO aumenta as probabilidades

de que novos e melhores caminhos possam ser explorados.

AntNet-QoS 2004 AntNet Carrillo et al.

[108]

Para o roteamento com vistas à Qualidade de Serviço (QoS), levando

em consideração as melhorias sugeridas por Barán & Sosa [114]. O

AntNet-QoS é habilitado a prover o roteamento sob restrições de QoS

em uma rede DiffServ por meio do uso de múltiplos feromônios e classes

de formigas, de modo a encontrar os melhores caminhos para cada CoS

(Classe de Serviço). Quando uma formiga encontra um caminho que

satisfaz os requisitos de QoS para uma determinada CoS, uma formiga

backward retorna para informar da existência do caminho, atualizando

duas estruturas em cada nó ao longo do caminho de volta.

Continua . . .

146

————

Refer

ências————


AntNet Aperfei-

çoado

2004 AntNet Tekiner, et al.

[117? ]

Introduz novas ações ao AntNet: eliminação das formigas mais velhas,

limitação do efeito do parâmetro de reforço dos feromônios devido a

flutuações de tráfego, e limitação do número de formigas no sistema,

proporcionalmente ao número de pacotes enviados. Estas modificações

melhoraram o desempenho do AntNet em termos de vazão, retardo mé-

dio e carga. Em seguida, foi proposto um novo mecanismo de evapora-

ção, que reduz o retardo médio dos pacotes em condições de tráfego não

uniforme [118].

ADVR 2004 DV Amin & Mikler

[119], [120]

Propõe-se o roteamento de Vetor de Distância baseado em formigas

(ADVR - Agent-based Distance Vector Routing algorithm), onde os agentes

(formigas) carregam consigo, ao longo da rede, as tabelas de roteamento

dos seus nós de origem, ou um subconjunto destas tabelas. Em com-

paração com um algoritmo DV, o ADVR mostra uma baixa ocupação

de largura de banda (overhead) e melhor escalabilidade, sem perdas de

desempenho.

Continua . . .

147

————

Elto

nBer

nar

doBan

deir

adeMelo————


AntNet Modifi-

cado

2004 AntNet e AG Liang, et al. [121] Mostra que a remoção de informações globais compromete a habilidade

do AntNet de encontrar rotas adequadas. Propõe um novo algoritmo

também baseado em AG (Algoritmo Genético), adicionando inteligência

às formigas, mas com similaridades em relação ao AntNet. Os agentes-

AG mostram desempenho intermediário quando comparado com o Ant-

Net com e sem acesso às informações globais. Os agentes-AG, apesar

de incrementarem a carga (overhead) da rede, apresentam vantagens em

relação à segurança.

ASR 2004 AntNet Lü et al.[122] O Roteamento Adaptativo Baseado em Enxames, ASR (Adaptive Swarm-

based Routing algorithm), parte do AntNet aperfeiçoado por Barán & Sosa

[114], e aplica o princípio de Bellman de decomposição de um caminho

ótimo em sub-caminhos ótimos. No ASR, todo nó intermediário em um

caminho é tratado como um destino e associado a um retardo estimado,

que por sua vez é atualizado de acordo com o custo relativo até este nó

visitado. Foi usado um procedimento de atualização de roteamento dife-

rente, baseado na técnica do momentum para evitar oscilações e acelerar

a convergência. O ASR mostra retardos menores e vazão maior que o

AntNet;

AntNet-CHTT 2005 AntNet Doi & Yamamura

[123]

AntNet com limpeza do histórico de tempos de propagação.

Continua . . .

148

————

Refer

ências————


AntNet Modifi-

cado

2005 AntNet Bean & Costa

[22]

Desenvolvem o primeiro estudo analítico do AntNet e propõem algumas

modificações de modo a melhorar seu desempenho. As modificações es-

tão principalmente relacionadas ao desacoplamento das tarefas de explo-

ração, estimação de retardo e balanceamento de carga. Foi demonstrado

que a versão modificada do AntNet, após o estudo analítico, é mais apta

a atender políticas de roteamento que correspondem a uma forma de

otimização com base no usuário, chamado de Equilíbrio de Wardrop.

AntNet Modifi-

cado

2006 AntNet Soltani, et al. [21] Propõem um novo tipo de formigas, as helping ants, para representar me-

lhor o processo de propagação natural do feromônio, i.e. o mecanismo

de compartilhamento das informações entre as formigas mais próximas.

Quando uma formiga backward alcança seu nó de origem, é criada e

enviada uma helping ant a cada vizinho para informá-lo sobre o novo

caminho e atualizar as tabelas de vizinhos (similarmente a uma formiga

backward), depois disso, as helping ants não irão continuar a se propagar,

serão eliminadas. O AntNet assim modificado reduz significativamente

o retardo médio e a carga na rede sem incrementar as taxas de perdas

de pacotes ou o jitter e aceleram a convergência em caso de falhas nos

enlaces.

UnfNet 2006 AntNet Dhillon & Mi-

eghem [20]

AntNet simplificado para redes pequenas, quando o tráfego é reduzido e

a geração de formigas é relativamente alta.

Continua . . .

149

————

Elto

nBer

nar

doBan

deir

adeMelo————


AntNet Modifi-

cado

2007 AntNet Arnous et al. [124] Propõem modificações no AntNet para melhorar as características do

balanceamento de carga. As modificações consistem no controle e limite

do número total de formigas trafegando na rede. Modifica-se a taxa

de recrutamento das formigas de modo a alcançar uma melhor relação

custo-benefício entre a vazão e o retardo. Isto resulta em uma redução

no retado médio e num incremento na vazão.

SEMAnt 2007 AntNet Pany et al. [125] Um algoritmo proposto para redes peer-to-peer. O Algoritmo SEMAnt

usa taxonomia para o roteamento baseado no conteúdo, o destino das

formigas lançadas na rede é relacionado ao conteúdo desejado (meta-

data), ao invés de um endereço.

H-AntNet 2008 AntNet Vallejo [126] Propõe um algoritmo de roteamento hierárquico, o H-AntNet é uma

versão modificada do AntNet, inspirada no algoritmo BeeHive e na

RFC1195. O H-AntNet considera uma rede de telecomunicações hie-

rárquica, o que é plausível para redes de longa distâncias. O tratamento

hierárquico da rede mostra vantagens devido à manutenção de menores

tabelas de rotas, menor overhead, isolamento de falhas e maior escalabi-

lidade.

Continua . . .

150

————

Refer

ências————


NGN QoS AN-

TRAL

2008 AntNet Lee, et al. [109] Propõem um algoritmo de roteamento com QoS para redes NGN (Next

Generation Networks). Similarmente a Carrillo et al. [108] e Subing et al.

[107], há diferentes formigas para diferentes CoS (Classe de Serviço). As

formigas forwardmonitoram a rede e armazenam as informações necessá-

rias, como o tempo de percurso e o tamanho das filas para cada serviço.

A formiga backward usa filas de alta prioridade, modifica as tabelas de

roteamento e as estatísticas de QoS locais usando regras pré-definidas.

As rotas são classificadas pelas condições de tráfego, as CoS são alo-

cadas de acordo com suas necessidades. Os resultados das simulações

mostram que o algoritmo pode alocar eficientemente recursos baseado

no estado da rede.

151

Documents

Modelagem do Comportamento de Colônias de Formigas e Sua ... · das colônias para continuarem alimentando seus ninhos de modo eﬁciente. Neste trabalho é ... ao longo do tempo