Relatório de Iniciação Tecnológica
Vida Artificial e Transporte Coletivo
Lucas Freitas Teixeira, aluno
Pedro de Souza Asad, aluno
Eduardo Bezerra da Silva, orientador
17 de agosto de 2009
,_
_,
’.__.’
’-,
(__)
,-’
’._ .::. _.’
_’(^^)’_
_,‘ ‘>\/<‘ ‘,_
‘ ,-‘ )( ‘-, ‘
| /==\ |
,-’ |=-| ’-,
)-=(
\__/
1
Resumo
Este presente projeto de pesquisa envolve investigação em Vida Artificial. Em particular, esse estudo tem o objetivo de analisar o comportamento
de transporte de presas por criaturas simples (e.g., formigas) e como esse
comportamento pode ser simulado computacionalmente. Com esse objetivo, estamos desenvolvendo uma ferramenta computacional de simulação
de transporte coletivo. Essa ferramenta deve possibilitar a simulação em
computador de comportamentos de transporte coletivo de objetos por grupos de criaturas. Essa ferramenta se destina ao uso em ambiente de sala
de aula (por alunos de Biologia em variados nı́veis de ensino). Também
pode ser utilizada para complementar e auxiliar experimentos de pesquisa
desenvolvidos por biólogos e engenheiros, que estudam o comportamento de
transporte coletivo.
Palavras-chave: vida artificial, sistemas emergentes, simulação e modelagem computacional, desenvolvimento de software, transporte coletivo
1
Sumário
1 Introdução
3
2 Metodologia
2.1 Aplicativo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Linguagens, ferramentas e padrões utilizados . . . . . . . . . . . . .
4
4
4
3 Ambiente
6
4 Formiga
7
4.1 Comportamentos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
4.2 Trilhas de feromônio . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4.3 Volta ao ninho . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
5 Variáveis do programa
14
6 Formatos de arquivos
6.1 Entrada da simulação . . . . . . . . . . . .
6.1.1 <simulation> . . . . . . . . . . . .
6.1.2 <variables> . . . . . . . . . . . . .
6.1.3 <environment> . . . . . . . . . . .
6.1.4 <animation> . . . . . . . . . . . .
6.2 Saı́da da simulação . . . . . . . . . . . . .
6.3 Transformando a saı́da em outros formatos
6.3.1 <report> . . . . . . . . . . . . . .
16
16
16
16
19
20
21
22
22
.
.
.
.
.
.
e
.
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
gráficos
. . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
7 Experimentos
26
Referências
47
2
1
Introdução
A Vida Artificial é uma sub-área da Computação Bioinspirada e é a abordagem
que utilizamos para reproduzir o comportamento de transporte coletivo em formigas. “A Computação Bioinspirada estuda técnicas de computação inspiradas na
Biologia. [. . . ] A computação Bioinspirada tem por objetivo construir sistemas
computacionais semelhantes a seres vivos (utilizando conhecimento das ciências
biológicas) e utilizar tais sistemas para melhorar nosso entendimento da Biologia
e da Natureza.” [?]
Outra área da Computação Bioinspirada, a Inteligência Coletiva, se utiliza
constantemente do termo emergente para descrever como a atuação de um grupo
de agentes autônomos, que se comportam com base em regras simples, resulta
num comportamento coletivo complexo e capaz de se adaptar às circunstâncias
ambientais. Isso é particularmente útil na resolução de problemas NP-completo1 ,
como:
• Problema do caixeiro viajante (traveling salesman problem): dada uma lista
de cidades e as distâncias entre elas, achar o menor circuito possı́vel que
visite cada cidade uma única vez, sendo um circuito uma rota que comece e
termine na mesma cidade. [?]
• Roteamento multicast com variação de atraso limitada (multicast routing for
delay variation bound ): transmitir, da melhor maneira possı́vel, dados por
uma rede para diversos destinatários diferentes, de forma que a diferença
entre os atrasos para quaisquer dois destinatários não ultrapasse um limite.
Esse limite de variação de atraso é necessário, por exemplo, em transmissões
de vı́deo para vários destinatários onde é vantajoso para um usuário receber
informações contidas no vı́deo antes dos outros. [?]
1
Classe de problemas computacionais que não podem ser resolvidos em tempo polinomial.
Estes problemas geralmente apresentam tempo de solução exponencial ou fatorial em função
de suas entradas, dificultando a aplicação das soluções conhecidas a conjuntos de dados muito
extensos.
3
2
Metodologia
2.1
Aplicativo
A tela do programa é constituı́da de um painel onde a simulação é exibida, à
esquerda, uma fila de arquivos de simulação a serem executados, botões de controle
da execução (pausar, cancelar a simulação atual e cancelar todas as simulações da
fila) e mostradores onde são exibido o número da rodada da simulação atual, o
tempo passado desde o inı́cio dessa rodada e o tempo máximo permitido para cada
rodada dessa simulação.
Para iniciar uma simulação, o usuário deve adicionar pelo menos um arquivo
de simulação através do botão “Adicionar arquivo”. Arquivos indesejados podem
ser removidos pelo botão “Remover arquivo”. O botão “Processar em lote” pode
ser ativado ou desativado, e quanto ativo, faz com que ao terminar uma simulação,
o programa inicie a próxima simulação da fila.
Ao longo dessa seção (e do relatório), quando certa variável for descrita como
“um certo número” ou similar, isso é feito pois esses números podem estar definidos no arquivo de simulação (quando não estão, o aplicativo designa números
padrões). Além disso, a maioria desses números não são definidos exatamente;
são definidos parâmetros para uma certa distribuição estatı́stica, sendo o número
calculado durante a simulação. Para mais informações sobre as variáveis, consulte
a seção “Variáveis do programa”.
Quando a simulação começa, um certo número de formigas sai do ninho a procura de alimento. São desenhados as formigas, o ninho (um cı́rculo branco), uma
folha (um cı́rculo verde preenchido) e os blocos de feromônio no chão (quadrados
brancos que são preenchidos de tons de amarelo quando há feromônio neles).
2.2
Linguagens, ferramentas e padrões utilizados
Inicialmente, pensamos em fazer um modelo simples na linguagem NetLogo2 , por
ser de fácil aprendizado, já ter a parte gráfica pronta (tanto a tela mostrando as for2
O NetLogo é uma linguagem de programação simples e adaptada à modelação / simulação
de fenômenos naturais e/ou sociais
4
migas se movimentando, quanto a tela para alterar as configurações do ambiente),
e porque a linguagem é orientada a agentes. As ”turtles”, os agentes do NetLogo,
rodam concorrentemente, e isso facilitaria a implementação das formigas.
Posteriormente descobrimos que o NetLogo, entre seus vários modelos de exemplo, possui uma simulação de formigas buscando alimento. Estudamos o modelo,
bem simples, em que as formigas saem do ninho e se guiam por feromônio. [?]
Acabamos desistindo do NetLogo, pois a linguagem é muito limitada.
Trocamos para Java, pois era uma linguagem de conhecimento dos três – orientador e orientados –, utilizada no projeto de Iniciação Tecnológica anterior. Além
disso, Java possui uma enorme variedade de APIs 3 de qualidade disponı́veis –
uma boa parte delas, de licença livre ou gratuita para uso acadêmico. De fato, a
versão presente do programa utiliza as bibliotecas:
• Colt: desenvolvido pelo CERN (European Organization for Nuclear Research), é um conjunto de bibliotecas para realizar computação cientı́fica e
técnica de alta performance, em Java. Possui uma vasta quantidade de
funções, além da utilizada no nosso programa: gerar números aleatórios utilizando distribuições de probabilidade. [?]
• Processing: utilizado para desenhar as o ambiente e as formigas na tela. [?]
• Apache Xerces: conjunto de ferramentas para analisar arquivos XML. Utilizado no nosso programa para ler os arquivos de configuração das simulações.
[?]
Utilizamos o IDE4 Netbeans, escolhido por familiaridade de ambos os alunos e
por ter um construtor de interfaces gráficas simples de usar, o Swing GUI Builder.
A configuração dos parâmetros de simulação é feita através de arquivos XML5 ,
segundo a sintaxe definida no arquivo input.dtd. Arquivos (Document Type Definition, ou Definição de Tipo de Documento) definem regras de formação de arquivos
XML, especificando quais entidades são opcionais, quais são obrigatórias, o que
podem e devem conter e também a ordem em que devem aparecer.
Desenhamos a tela utilizando o Swing, biblioteca padrão do Java para construir interfaces gráficas. Construir interfaces não-triviais com o Swing torna-se
rapidamente trabalhoso e demorado, então utilizamos a ferramenta presente no
NetBeans que permite construir interfaces movendo os elementos (botões, caixas
de texto etc) na tela até o local desejado.
Para desenhar o ambiente (formigas, ninho, folha, feromônios) na tela, utilizamos a API do Processing, por sua simplicidade e novamente por termos, os
três, domı́nio sobre a ferramenta, utilizada em aulas do curso técnico ministradas pelo professor orientador. O Processing permite desenhar facilmente formas
3
Application Programming Interface é um nome comumente empregado para designar bibliotecas de programação, que são pacotes de rotinas computacionais dedicados a mascarar os
detalhes de operações complexas, oferecendo uma interface simples para acessar os serviços.
4
Integrated Development Environment, ou Ambiente de Desenvolvimento Integrado, é um
programa que fornece ferramentas para apoiar o desenvolvimento de software, tornando este
mais rápido do que seria utilizando ferramentas separadas. Possui editor de texto, compilador,
depurador, entre outras ferramentas, integradas em um mesmo programa.
5
XML, do inglês eXtensible Markup Language, é uma linguagem de marcação recomendada
pela W3C (World Wide Web Consortium, a principal organização de padronização da Internet)
para a criação de documentos com dados organizados hierarquicamente, tais como textos, banco
de dados ou desenhos vetoriais. A linguagem XML é classificada como extensı́vel porque permite
definir os elementos de marcação, criando-se uma linguagem de marcação para fins especı́ficos.
5
geométricas na tela, e torna as operações de nı́vel mais baixo (desenhar cada pixel,
limpar a tela etc) transparentes ao programador.
Uma vez que simulações tenham sido rodadas, seus dados são gravados em
arquivos properties, no diretório output. Como o formato dos arquivos só é comumente usado em aplicações Java, fizemos o programa auxiliar Ants-Report.jar,
que pode ser utilizado para coletar dados relevantes e gravá-los em formatos mais
úteis. Na versão atual, há duas maneiras de processar os dados: arquivos CSV6 e
gráficos gerados pelo gnuplot, uma ferramenta para geração de gráficos de funções
e dados interativa e orientada a linha de comando [?].
3
Ambiente
Folhas são o único tipo de presa implementado. Embora o simulador tenha sido
projetado para suportar múltiplas folhas, os módulos de coleta e processamento
de dados só suportam uma presa por ecossistema.
Um dos maiores problemas que enfrentamos no projeto foi simular um ambiente contı́nuo (a realidade) em um sistema discreto (pixels, números de ponto
flutuante). Dentro desse problema, está o de simular os processos fı́sicos. Procuramos em vão uma API pronta para lidar com o nosso caso especı́fico: fı́sica
em duas dimensões, vista de cima. A grande maioria das APIs que encontramos
estava em uma dessas duas categorias: ou era 2D, mas vista de lado como um
videogame de plataforma, ou era 3D, e para adaptá-la à nossa situação terı́amos
que simplesmente ignorar uma das dimensões, mas as curvas de aprendizado eram
impraticáveis para a duração do projeto.
A fı́sica, então, é toda feita por nós. É extremamente difı́cil simular colisões
(entre formigas, folhas e outros objetos) e contato com aplicação de força (quando
a formiga empurra/puxa uma folha). Os problemas foram encarados, respectivamente, permitindo somente uma folha por simulação e “prendendo” as formigas
à folha quando estas estão empurrando/puxando. Cada folha possui uma lista de
formigas que estão “agarradas” nela. A folha então calcula a força aplicada pelas
formigas e se move de acordo com ela, movendo também as formigas.
As folhas, que são sempre circulares, podem possuir ganchos. Os ganchos são
uma resistência à força aplicada pelas formigas em certas direções.
6
CSV é um formato simples para armazenar dados tabelares em arquivos texto. É suportado pela maioria das aplicações de planilha, como OpenOffice Calc e Microsoft Excel. Em
arquivos CSV, os dados em uma linha são separados por vı́rgulas. Todas as linhas devem ter o
mesmo número de elementos, como em uma tabela. Tudo entre um par de vı́rgulas, incluindo
espaçamento, faz parte do campo. Embora existam diferentes implementações deste formato,
cada uma com certas regras, o IETF – Internet Engineering Task Force – possui um documento,
o RFC4180[?], que descreve o formato para uso em correio eletrônico e este é o padrão utilizado
pelo programa.
6
Um gancho tem três parâmetros: um vetor principal, um ângulo de influência
e um valor limite do módulo de influência no extremo do arco.
Quando a força aplicada pelas formigas tem a mesma direção e sentido do vetor
principal, a força de resistência do gancho tem módulo igual ao do vetor principal.
Quando a força aplicada pelas formigas se encontra dentro do arco de influência, a
força de resistência é proporcional ao ângulo formado pela força aplicada e o vetor
principal, até o limite, quando esse ângulo é igual ao ângulo de influência.
A implementação dos feromônios foi feita dividindo o solo em blocos quadrados
de mesmo tamanho. Cada bloco desses é considerado um “átomo”, no sentido que
é definida uma quantidade de feromônio presente no bloco inteiro, e o decaimento
de feromônio é feito em todo o bloco também, bem como as formigas decidem para
qual bloco devem caminhar de acordo com o nı́vel de feromônio do bloco.
O solo, cujas dimensões são dadas em centı́metros, é segmentado em vértices
de acordo com o parâmetro Ecosystem.gridDensity. Esta variável de entrada,
que pode assumir os valores 1, 2 ou 3, determina quantas divisões um centı́metro
causa na matriz de vértices. Assim, quando Ecosystem.gridDensity assume o valor
1, cada centı́metro quadrado equivale a um vértice, quando assume o valor 2, cada
centı́metro quadrado contém 4 vértices e com o valor 3, 9 vértices por centı́metro
quadrado.
Quando uma formiga deposita feromônio em um bloco, a parte do programa
que controla o solo (classe Ground ) adiciona a quantidade de feromônio depositada
a uma matriz NxM, correspondente aos NxM blocos de feromônio. Com o tempo,
esse feromônio vai decaindo (a quantidade de feromônio é decrescida por uma
porcentagem definida por uma constante de decaimento), até chegar a um limite
no qual a quantidade de feromônio é considerada zero (isso foi feito para impedir
que resı́duos desprezı́veis como 0,0000000023 fossem levados em conta na hora dos
cálculos).
4
Formiga
Cada formiga é um agente, no sentido em que ela recebe entradas do ambiente
e como resposta, executa ações. Achamos adequado então procurar alguma API
para o Java que abstraisse a implementação interna dos agentes, e nos economizasse
tempo.
Depois de alguma busca na Internet, achamos o JADE, uma biblioteca de
programação em Java que possibilita a aplicação da Programação Orientada a
Agentes. Seguiu-se um grande aprendizado da utilização do JADE. Analisamos o
trabalho de conclusão de curso de um aluno do CEFET, Fabiano, que consistia
7
em um sistema de gerenciamento de sinais de trânsito, e utilizava JADE. Fizemos
uma versão inicial do nosso simulador de formigas, pra testar as capacidades do
JADE, mas tivemos muitos problemas. O JADE possui um mecanismo de troca
de mensagens entre os agentes muito complexo, e é extremamente difı́cil trabalhar
com os agentes sem ser por troca de mensagens. Isso não nos era útil, pois a
comunicação entre formigas é baseada somente em estigmergia7 .
Decidimos então que implementarı́amos nossos agentes do zero. Depois de
alguns modelos malsucedidos, implementamos nossos agentes como Máquinas de
Estado Finito, que executam comportamentos como “vagar”, “tentar puxar presa”,
“chamar ajuda” etc. Fizemos essa escolha por tornar o código-fonte mais claro e
fácil de manter, uma vez que os comportamentos são como módulos independentes entre si. Também se torna mais fácil mostrar como a formiga se comporta,
através de uma ilustração descrevendo visualmente a máquina de estado finito e
as transições entre os estados.
4.1
Comportamentos
• Seeking - Comportamento inicial. É neste estado que as formigas deixam o
ninho inicialmente e partem em busca de presas. Se a formiga fareja uma
trilha de feromônios, ela possivelmente segue essa trilha inteira, segue por
apenas um trecho ou a ignora completamente. Formigas com altos valores
de independência tendem a ignorar trilhas completamente e formigas com
valores baixos tendem a segui-las. É esperado que uma boa distribuição dos
valores de independência em um formigueiro gere uma população equilibrada,
que consiga eventualmente achar caminhos alternativos cada vez mais curtos
para uma presa. Ao avistar uma presa, a formiga passa imediatamente para
o comportamento Approching. A formiga busca presas até uma distância
máxima, sua audácia. Após essa distância, se a formiga não tiver encontrado presa alguma, ela vai para Returning. Para mais informações sobre
7
Estigmergia é uma comunicação não-verbal auto-ajustável e indireta realizada através do
meio ambiente. Vestı́gios ou estı́mulos fı́sicos ou quı́micos são gerados por um agente como
consequência de suas ações e são percebidos pelo mesmo agente ou por terceiros, influenciando
em suas ações.
8
o algoritmo utilizado na busca para seguir trilhas de feromônio, consulte a
seção “Formiga” → “Trilhas de feromônio”.
Variáveis utilizadas no comportamento:
– Ant.sight
– Ant.topSpeed
– Ant.initiative
– Seeking.audacity
• Returning - A formiga retorna ao ninho por um caminho melhorado em
relação ao caminho percorrido até o ponto em que ela decide retornar. Esse
caminho de retorno tende a ser menor que o caminho original invertido e o
quanto ele é melhorado depende da inteligência da formiga. Quanto maior o
valor da inteligência, mais aprimorado é o caminho de retorno.
Variáveis utilizadas no comportamento:
– Ant.sight
– Ant.intelligence
• Approaching - Neste comportamento, a formiga simplesmente se aproxima
da presa avistada e passa imediatamente para o estado Circumventing.
• Circumenventing - Este comportamento faz com que a formiga procure uma
posição “confortável”, isto é, a uma certa distância de outras formigas. Se
as formigas imediatamente à esquerda e à direita estiverem a uma distância
mı́nima ideal, ela passa prontamente para o comportamento Aligning, caso
contrário, contorna a presa até achar um posição que satisfaça essa condição.
Após certo tempo contornando a presa, se a formiga não encontrar posição
agradável, ela simplesmente pára no meio de duas formigas e passa para
Aligning.
Variáveis utilizadas no comportamento:
– Circumventing.insistance
– Circumventing.sociability
• Aligning - A formiga exerce força cresecente sobre a presa na direção do
ninho durante um certo intervalo de tempo. Após esse tempo, ela muda o
sentido de aplicação desta força e torna a aplicá-la com intensidade crescente.
Quando múltiplas formigas exercem esse comportamento simultaneamente,
a força alicada pode, eventualmente, ser suficiente para mover a folha em
direção ao ninho. Esta mudança de direção aumenta o tempo necessário
para que um grande número de formigas consiga mover uma presa, mas
torna o transporte eficaz na presença de obstáculos. Se a presa for movida a
formiga passa prontamente para o estado Carrying, se não, após certo tempo
de inércia, ela vai para o comportamento Redocking.
Variáveis utilizadas no comportamento:
– Aligning.angleTurn
– Aligning.chargeRate
9
– Aligning.exhaustion
– Aligning.firstCharge
– Aligning.tries
– Aligning.insistance
• Redocking - Semelhante a Circumventing, com a diferença que a condição
de exaustão não é o tempo e sim o comprimento do perı́metro da presa que
é contornado. Em pressas geometricamente complexas, posições diferentes
podem fornecer melhores resultados na movimentação, o que não é o caso
nesta implementação. De toda forma, esse comportamento dá tempo para
que outras formigas se unam ao transporte antes que ocorra desistência,
aumentando as chances de que um deslocamento em grupo seja conseguido.
O número de vezes que a formiga se reposiciona é limitado. Se este número
de reposicionamentos é esgotado, a formiga passa para Recruiting.
Variáveis utilizadas no comportamento:
– Circumventing.sociability
– Redocking.offset
• Carrying - Comportamento de transporte da presa. Neste estado a formiga
mantém a força que aplicava inicialmente sobre a presa. Há uma tolerância
em relação ao desvio de rota, pois o objetivo das formigas é levar a presa
na direção do ninho, mas se a tolerância em relação a desvios na direção
for zero, será virtualmente impossı́vel mover a presa. Por isso, cada formiga
tem uma certa tolerância e uma certa iniciativa em tentar corrigir a rota
através da mudança da aplicação de sua força, a partir de uma intensidade
menor que cresce gradativamente. Como os valores de tolerância e iniciativa
diferem, a rota é corrigida com relativa suavidade, implicando em raras vezes,
na parada do transporte devido à redução da força aplicada. E nos casos
em que isso acontece, é possı́vel que novas formigas se juntem ao grupo,
aumentando a estabilidade do transporte. Quando uma presa é entregada, a
simulação termina. Se o transporte for interrompido, passa-se prontamente
para o estado Aligning novamente.
Variáveis utilizadas no comportamento:
– Aligning.angleTurn
– Aligning.chargeRate
– Aligning.exhaustion
– Carrying.firstCharge
– Carrying.tolerance
• Recruiting - A formiga retorna ao ninho deixando um rastro de feromônios
pelo chão. A concentração do feromônio deixado depende da relação entre a
audácia da formiga e a distância percorrida até chegar à presa. O retorno até
o ninho é feito da mesma maneira que em Returning. Chegando ao ninho,
ela sinaliza para que novas formigas deixem o ninho e sigam sua trilha e
retorna a Seeking.
Variáveis utilizadas no comportamento:
10
– Ant.intelligence
– Seeking.audacity
4.2
Trilhas de feromônio
As formigas deixam o ninho em busca de presas (folhas). Um algoritmo de caminhada é aplicado sucessivas vezes até que uma presa seja encontrada ou a formiga
tenha se afastado uma distância máxima do ninho, dada por sua audácia. No primeiro caso ela agarra a presa e aplica força sobre a mesma na tentativa de movê-la
e no último caso ela retorna ao ninho.
A etapa de busca é baseada no algoritmo Ant System[?], originalmente aplicado
ao problema do caixeiro viajante[?]. Cada vértice percorrido pela formiga passa
a integrar uma lista de vértices denominada trajetória. A cada vértice atingido,
uma regra probabilı́stica de decisão é aplicada para escolher o próximo vértice. A
regra de decisão depende do feromônio presente nas redondezas e da orientação da
caminhada. Esta etapa de decisão é uma adaptação do modelo de construção de
solução do Ant System.
O caminho sk – também conhecido como solução parcial – percorrido pela
formiga k determina qual o conjunto N (sk ) de vértices que podem ser escolhidos
para compor a próxima etapa da caminhada. A probabilidade de que um certo
vértice em N (sk ) seja escolhido, dada por p(v, sk ), depende da atratividade deste
vértice em comparação aos demais vértice dos conjunto N (sk ). Essa probabilidade
p(v, sk ) é dada formalmente por:
p(v, sk ) =
τ (v, k)α · η(v, sk )β
X
[τ (u, k)α · η(u, sk )β ]
u∈N (sk )
Onde:
• sk é a solução parcial ou simplesmente o caminho já percorrido pela formiga
k;
• N (sk ) é o conjunto de vértices candidatos. Esse conjunto é formado por
todos os vértices adjacentes que não façam parte de sk .
• τ (v, k) é a soma da iniciativa da formiga k com a quantidade de feromônio
presente no vértice v no instante da decisão;
• η(u, sk ) é uma função heurı́stica de avaliação do vértice;
• α é o expoente que controla a importância do feromônio na escolha;
• β é o expoente que controla a importância da informação heurı́stica de um
vértice.
A função heurı́stica η utilizada aqui foi escolhida para tornar o padrão de
busca mais realista e eficaz, isto é, minimizar as mudanças súbitas de direção,
mas ainda assim permitir desvios. A função escolhida produz valores entre 0 e 1,
inclusive. Quando o único vértice presente em sk é o vértice de partida do ninho,
a função assume valor 1, pois todos os vértices ao redor são equiprováveis – isto
é, sem levar em consideração o feromônio depositados nestes vértices. A partir da
segunda escolha, dois ângulos passam a ser levados em consideração:
11
O ângulo θ entre o vetor deslocamento do vértice anterior ao vértice atual e o
vetor deslocamento do vértice atual ao vértice candidato. Se este ângulo for maior
que 90◦ , a função assume valor 0. Isso serve para eliminar a possibilidade de se
andar para trás e faz com que, a cada etapa, existam cinco escolhas possı́veis de
vértices: o vértice imediatamente à frente, dois a 45◦ e dois a 90◦ do deslocamento
anterior.
O ângulo φ entre o vetor deslocamento do ninho até o vértice atual e o vetor
deslocamento do ninho até o vértice candidato. À medida que a formiga se afasta
do ninho, as diferenças entre os diferentes φ de cada vértice candidato se tornam
menores, fazendo com que num primeiro momento haja maior tendência a deslocarse radialmente a partir do ninho, mas posteriormente, seja mais provável que curvas
mais abertas sejam realizadas.
A função η(v, sk ) é finalmente definida como:

π
π
1
 [(θ+1)·(φ+1)] se sk > 1 e θ ≤ 2 e φ ≤ 2 ;
η(v, sk ) =
0
se sk > 1;

1
if sk ≤ 1.
A implementação do algoritmo de caminhada do simulador difere do Ant System em alguns pontos chave:
τ (v, k) em Ant System é apenas a quantidade de feromônio associada ao vértice
v. Aqui, a adição da constante de iniciativa visa contornar os seguintes problemas:
no estado inicial do ecossistema não há feromônio qualquer depositado, por isso,
na ausência da constante de iniciativa, todos os vértices teriam probabilidade zero
de serem escolhidos e as formigas não se moveriam; além disso, se uma formiga
encontra uma presa e retorna ao ninho deixando um rastro de feromônio, todas as
formigas que retornam ao ninho percebem esta trilha; se esta constante não fizesse
parte do cálculo de probabilidades, todos os vértices que fizessem parte do conjunto
N (sk ) e não contivessem feromônio algum teriam probabilidade zero de serem escolhidos, o que impossibilitaria a descoberta de trilhas alternativas e faria com
que todas as formigas tivessem um comportamento previsı́vel. Adicionalmente, a
adição dessa constante traz alguns efeitos desejáveis ao comportamento das formigas: valores altos de iniciativa, sobrepujam o feromônio depositado, aumentando a
possibilidade de que vértices alternativos sejam escolhidos e novos caminhos sejam
trilhados; na ausência total de feromônios, o valor de τ (v, k) é idêntico para todos
os vértices, sendo assim, a informação heurı́stica η(v, sk ) é o único fator relevante
na escolha de um vértice, o que é desejável nas primeiras etapas de simulação.
η(u, sk ) em Ant System é o inverso da distância do vértice atual ao vértice v,
o que não faz sentido no contexto deste simulador já que praticamente todos os
vértices levados em consideração estão à mesma distância do vértice atual.
Outra etapa do Ant System é a atualização dos valores de feromônios, que
envolve duas ações:
• deposição de feromônio pelas formigas que já completaram o circuito.
• evaporação do feromônio previamente depositado.
Ambos foram também implementados neste simulador, com adaptações. A
taxa de evaporação, indicada pela variável ρ, representa a taxa de evaporação de
feromônio em unidades por segundo - em contraste com o Ant System, no qual ρ
é a taxa de evaporação em unidades por rodada – e é atualizada constantemente
12
pela thread (unidade de execução independente) que gerencia o ecossistema. A
deposição de feromônio também se processa de maneira bem diferente, visto que
ela é feita gradualmente à medida que a formiga retorna ao ninho e não de uma
única vez como no Ant System. Uma consequência disso é que o feromônio vai
evaporando à medida que é depositado e o feromônio tende a estar mais concentrado próximo ao ninho e menos concentrado próximo à presa. Isso aumenta a
possibilidade que a iniciativa sobrepuje o feromônio quando se chega mais perto da
presa, aumentando a quantidade de caminhos alternativos próximo à folha. Uma
quantidade de feromônio igual para todos os vértices do caminho até uma certa
folha é depositada por uma determinada formiga. A quantidade de feromônio depositada é dada por uma função de avaliação F (sk ) – também chamada de função
de adaptação – que julga o quão bom é o caminho. A função F (sk ) visa aumentar a atratividade de caminhos mais curtos, além de levar em consideração uma
estimativa do tamanho da presa encontrada. Ela é definida da seguinte maneira:
F (sk ) = 1 −
1
d(sk )
·
ak
δ · ik
Onde:
• d(sk ) é o comprimento do caminho sk .
• ak é a audácia da formiga k.
• δ é o diâmetro da folha encontrada.
• ik é a inteligência da formiga k.
A razão d(sk )/ak é tão maior quanto maior for a distância percorrida em relação
à distância máxima que a formiga está disposta a percorrer para encontrar uma
presa. Assim, para uma presa relativamente próxima, 1 – d(sk )/ak é um número
mais próximo de 1 do que de 0. Mas ainda assim, devido às configurações ideiais
e à natureza do caminhar, os valores se concentram mais próximos de 0 do que
de 1. Para contrabalançar este fato, introduz-se a razão 1/(δ · ik ), que constitui
uma estimativa do diâmetro da folha tão mais precisa quanto mais inteligente é
a formiga. O valor de feromônio calculado é, então, despejado sobre cada vértice
sobre o qual a formiga passa ao regressar ao ninho.
4.3
Volta ao ninho
Para calcular o caminho de retorno, nos comportamentos Recruiting e Returning,
dado o caminho original sk , percorre-se o caminho sk no sentido contrário ao de
construção do caminho. A cada vértice em que a formiga está posicionada, traçase um vetor v0 do vértice atual para um vértice de sk que seja o mais próximo
do vértice atual na ordem contrária da lista – o caminho seguro – e um vetor v1
do vértice atual para o ninho – o caminho perfeito. Então toma-se v2 , o vetor
diferença v1 − v0 . Multiplica-se v2 pela inteligência da formiga e soma-se v2 a v1 .
se a inteligência da formiga for máxima (1), o resultado será o caminho perfeito
e a formiga terá estimado um caminho de retorno otimizado ao máximo. Se a
inteligência for mı́nima (0), ela seguirá exatamente o mesmo caminho pelo qual
ela veio.
13
5
Variáveis do programa
Uma simulação possui diversos parâmetros / variáveis de entrada e alguns de
saı́da. Muitas das variáveis de entrada dizem respeito ao comportamento das
formigas, algumas dizem respeito ao ecossistema e outras ainda, à disposição da
presa. As variáveis de saı́da refletem, basicamente, tempos que foram necessários
para realizar uma tarefa e quantas formigas foram necessárias para fazê-lo.
Cada variável um nome único no sistema. Esse nome é hierárquico, no sentido de agrupar variáveis correlatas através de nomes semelhantes. No caso das
variáveis comportamentais, o nome é composto pelo nome da classe comportamental adicionado de um “.” e do nome especı́fico da variável. No caso das variáveis
da formiga, o “.” é precedido por “Ant”.
Variáveis de entrada:
• Ant.initiative – [0, 1]: Representa a iniciativa da formiga em tomar certas
atitudes. Essa variavél afeta dois comportamentos: Seeking e Carrying.
O padrão é uma distribuição normal com média 0.2 e desvio padrão 0.03,
delimitada entre 0 e 0.2.
• Ant.intellingence – [0, 1]: Precisão de estimativas e memória. Afeta três comportamentos: Aligning, Returning e Recruiting. O padrão é uma distribuição
normal com média 0,5 e desvio padrão 0.16.
• Ant.sight – ]0, +∞[: Raio de visão da formiga, em centı́metros. Afeta tão e
somente Seeking. Uma distribuição normal com média 2,5 e desvio padrão
0,2 é o padrão.
• Ant.topForce – ]0, +∞[: Força máxima que a formiga é capaz de exercer.
Afeta Aligning e Carrying. Uma distribuição normal com média 0.6 e desvio
padrão 0.1 é o padrão.
• Ant.topSpeed – ]0, +∞[: Velocidade máxima com a qual a formiga caminha.
Afeta Redocking, Seeking, Approaching, Routing e Circumventing. O padrão
é uma distribuição normal com média 1,7 e desvio padrão 0.2.
• Aligning.angleTurn – ] − ∞, +∞[: Ângulo de rotação da força (em sentido
aleatório) utilizado toda vez que a formiga resolve trocar a orientação da
mesma. O padrão é uma distribuição normal com média π/12 e desvio
padrão 0,5.
• Aligning.chargeRate – ]0, 1]: Taxa de aumento da força em unidades por
segundo. Toda vez que a formiga aplica a porcentagem de sua força inicial
dada por Aligning.firstCharge, essa é a taxa com que ela aumenta sua força
nos próximos segundos. O padrão é uma distribuição normal com média 0,3
e desvio padrão 0,1.
• Aligning.exhaustion – Z>0 : Número máximo de vezes que a formiga troca a
orientação da força antes de desistir ou trocar para Redocking. O Padrão é
uma distribuição poisson com média 3.
• Aligning.firstCharge – ]0, +∞]: Porcentagem da força máxima que a formiga
aplica na primeira tentativa e em cada uma das vezes subsequentes em que
muda a orientação da força. O padrão é uma distribuição normal com média
0,14 e desvio padrão 0,13.
14
• Aligning.tries – Z>0 : Número máximo de vezes que a formiga vai para um
comportamento de Redocking e volta para Aligning antes de passar para
Recruiting. O padrão é uma distribuição poisson com média 4.
• Aligning.insistance – ]0, +∞[: Tempo máximo durante o qual a formiga permance aplicando força na mesma direção. O Padrão é uma distribuição
normal com média 3 e desvio padrão 1.
• Carrying.firstCharge – ]0, +∞]: Porcentagem da força máxima que a formiga
aplica em cada uma das vezes em que muda a orientação da força para tentar
uma correção de rota. O padrão é uma distribuição normal com média 0,95
e desvio padrão 0,2. Esta variável é semelhante a Aligning.firstCharge, mas
deve ter média mais elevada, ou então as tentativas de correção de rota
resultarão em frequentes paradas do transporte.
• Carrrying.tolerance – ]0, +∞[: Ângulo máximo entre a trajetória em linha
reta até o ninho e a orientação da velocidade de transporte atual que a
formiga tolera sem tentar realizar uma correção. O padrão é uma distribuição
normal com média π/24 e desvio padrão 0,04.
• Circumventing.insistance – ]0, +∞[: Tempo máximo durante o qual a formiga circunda a presa em busca de uma posição confortável. O padrão é
uma distribuição normal com média 4 e desvio padrão 1.
• Circumventing.sociability – ]0, +∞[: Medida da distância mı́nima, em centı́metros,
das companheiras mais próximas para que a formiga se sinta confortável. O
padrão é uma distribuição normal com média 1,5 e desvio padrão 0,5.
• Redocking.offset – ]0, +∞[: Medida da distância mı́nima, em centı́metros,
que a formiga circunda a folha buscando uma nova posição. O padrão é uma
distribuição normal com média 1,5 e desvio padrão 0,5.
• Seeking.audacity – ]0, +∞[: Audácia da formiga. Medida da distância máxima
que ela se afasta do ninho em busca de presas. O padrão é uma distribuição
normal com média igual à diagonal do ecossistema e desvio padrão igual a
trigésima parte desta.
Variáveis de saı́da:
• Leaf.finding: Tempo necessário para encontrar a folha.
• Leaf.movement: Tempo necessário para mover a folha.
• Leaf.transporting: Tempo desde o achado da folha até a sua entrega.
• Leaf.delivery: Tempo necessário para entregar a folha desde o começo da
simulação (duração da simulação).
• Workers.delivery: Trabalhadores atuantes ao final do transporte da folha.
• Workers.movement: Trabalhadores necessários para causar a primeira movimentação na folha.
Leaf.delivery, Leaf.finding, Leaf.movement, Leaf.transporting, Workers.delivery
ou Workers.movement.
15
6
Formatos de arquivos
6.1
6.1.1
Entrada da simulação
<simulation>
Todo arquivo de configuração deve conter, obrigatoriamente a entidade simulation:
<s i m u l a t i o n>
[...]
</ s i m u l a t i o n>
Ela delimita o conteúdo de uma simulação e deve ser única em um arquivo.
Esta entidade possui quatro atributos possı́veis, sendo que apenas um deles é
obrigatório. Os demais, se não especificados, farão com que valores padrão sejam
adotados.
Atributos:
• threadInterval (opcional): intervalo de execução de threads em milissegundos (número inteiro). Partes do código que devem ser repetidas diversas
vezes em alta velocidade, devem sofrer uma pausa entre execuções sucessivas, para permitir que outros trechos de código também sejam executados.
Durante o desenvolvimento, indı́cios apontaram para a possibilidade de que
diferentes valores possam se adequar a diferentes processadores, no entanto a
hipótese não foi confirmada. Se as simulações tiverem um baixo desempenho,
recomenda-se testar valores diferentes aqui. O valor padrão é 10.
• timeout (opcional): tempo máximo (em segundos) para a execução da simulação. A simulação é encerrada após este perı́odo de tempo, caso não tenha terminado da maneira correta anteriormente. O valor padrão, 0, indica
que não há limite de tempo, a simulação rodará até que encerre normalmente.
O valor padrão é 0.
• rounds (opcional): número de vezes que a simulação será repetida, com
sucesso ou não. O valor padrão é 100.
• output (obrigatório): arquivo em que serão coletados os resultados da simulação
Exemplo:
<s i m u l a t i o n t h r e a d I n t e r v a l=” 20 ” timeout=” 300 ” rounds=” 250 ”
output=” . / output / 0 0 0 0 0 . t p f ”>
[...]
</ s i m u l a t i o n>
Essa entidade pode conter, nesta ordem, as entidade <variables>, <environment>
e <animation>. A primeira é opcional e as outras duas obrigatórias.
6.1.2
<variables>
A entidade <variables> perimite alterar os parâmetros comportamentais das formigas da simulação. Se não especificada, todas as variáveis comportamentais
assumem valores padrão. Ela não contém atributos, apenas sub-entidades. A
16
sub-entidade <aco> pode aparecer uma única vez; as sub-entidades <boundednormal>, <normal>, <poisson> e <uniform> podem aparecer diversas vezes e
em qualquer ordem, após <aco>.
Sub-entidades:
• <aco>
Altera os parâmetros do algoritmo utilizado no comportamento de busca
(Seeking). Todos os atributos são opcionais, então, a não ser que um deles
seja alterado, não faz sentido utilizar essa entidade, embora seu uso com
valores padrão não gere erro algum. Para mais informações sobre o algoritmo,
consulte a seção “Formiga” → “Trilhas de feromônio”.
Atributos:
– alpha (opcional): expoente alfa. O valor padrão é 1.0.
– beta (opcional): expoente beta. O valor padrão é 1.0.
• <normal>
Descreve uma variável aleatória gerada dentro de uma distribuição estatı́stica
normal.
Atributos:
– name (obrigatório): nome da variável. Pode conter um dos valores a
seguir: angleTurn, audacity, chargeRate, exhaustion, firstCharge, initiative, intellingence, insistance, offset, sight, sociability, topForce, tries,
topSpeed, tolerance.
– class (obrigatório): nome do comportamento. Pode conter um dos valores a seguir: Aligning, Ant, Carrying, Circumventing, Redocking, Seeking.
– mean (obrigatório): valor médio.
– deviation (opcional): desvio padrão. Se não especificado, o valor 1.0,
correspondente à distribuição normal padrão, é utilizado.
• <bounded-normal>
É utilizado para descrever uma variável de distribuição normal restrita a um
certo intervalo. Um conhecido resultado da estatı́stica, conhecido por “Regra
Empı́rica”, atesta que 99.7% dos valores em uma distribuição normal padrão
concentram-se entre menos três vezes o desvio padrão e três vezes o desvio
padrão, significando que todos os valores dentro de uma dirtibuição normal
estão dentro desta faixa, para fins práticos. Em alguns casos, na aplicação,
foi interessante que certas variáveis estivessem limitadas a intervalos, como
entre 0 e 1. É possı́vel utilizar <bounded-normal> com este fim. Se o
intervalo especificado for [a, b], então a média será o meio do intervalo, ou
seja, (a + b)/2 e o desvio padrão será a sexta parte deste intervalo, ou seja,
(b − a)/6. Valores produzidos aleatoriamente que caiam fora do intervalo
especificado serão ignorados.
Atributos:
17
– name (obrigatório): nome da variável. Pode conter um dos valores a
seguir: angleTurn, audacity, chargeRate, exhaustion, firstCharge, initiative, intellingence, insistance, offset, sight, sociability, topForce, tries,
topSpeed, tolerance.
– class (obrigatório): nome do comportamento. Pode conter um dos valores a seguir: Aligning, Ant, Carrying, Circumventing, Redocking, Seeking.
– min (obrigatório): limite inferior do intervalo.
– max (obrigatório): limite superior do intervalo.
• <uniform>
Descreve uma variável aleatória gerada dentro de uma distribuição estatı́stica
uniforme.
Atributos:
– name (obrigatório): nome da variável. Pode conter um dos valores a
seguir: angleTurn, audacity, chargeRate, exhaustion, firstCharge, initiative, intellingence, insistance, offset, sight, sociability, topForce, tries,
topSpeed, tolerance.
– class (obrigatório): nome do comportamento. Pode conter um dos valores a seguir: Aligning, Ant, Carrying, Circumventing, Redocking, Seeking
– min (obrigatório): limite inferior do intervalo.
– max (obrigatório): limite superior do intervalo.
• <poisson>
Descreve uma variável aleatória gerada dentro de uma distribuição estatı́stica
de Poisson. Ao contrário das anteriores, esta distribuição é discreta, ou seja,
gera números inteiros e não reais.
Atributos:
– name (obrigatório): nome da variável. Pode conter um dos valores a
seguir: angleTurn, audacity, chargeRate, exhaustion, firstCharge, initiative, intellingence, insistance, offset, sight, sociability, topForce, tries,
topSpeed, tolerance.
– class (obrigatório): nome do comportamento. Pode conter um dos valores a seguir: Aligning, Ant, Carrying, Circumventing, Redocking, Seeking.
– mean (obrigatório): valor médio. Pode ser um número real.
Exemplo:
<v a r i a b l e s>
<aco alpha=”2” beta=” 0 . 5 ”/>
<bounded−normal name=” i n i t i a t i v e ” c l a s s=”Ant” min=”0”
max=”1”/>
<uniform name=” i n t e l l i n g e n c e ” c l a s s=”Ant” min=”0”
max=”1”/>
18
<normal name=” angleTurn ” c l a s s=” A l i g n i n g ” mean=” 0 . 6 2 ”/>
<p o i s s o n name=” e x h a u s t i o n ” c l a s s=” A l i g n i n g ” mean=”3”/>
<normal name=” a u d a c i t y ” c l a s s=” S e e k i n g ” mean=” 6 7 . 7 5 ”
d e v i a t i o n=” 0 . 3 ”/>
<p o i s s o n name=” t r i e s ” c l a s s=” A l i g n i n g ” mean=”3”/>
</ v a r i a b l e s>
6.1.3
<environment>
A entidade <enviroment> contém informações sobre o tamanho do ecossistema,
a disposição de presas, a taxa de evaporação de feromônios e sobre o ninho. Suas
sub-entidades são <ecosystem>, <colony> e <leaves>, todas obrigatórias.
Sub-entidades:
• <ecosystem>
Agrupa as propriedade fı́sicas do ecossistema.
Atributos:
– rho (opcional): taxa de evaporação de feromônio. Recebe este nome
nada intuitivo devido à terminologia utilizada no algoritmo ACO, do
qual faz parte. O valor padrão é 2.5e − 3.
– threshold (opcional): valor mı́nimo de feromônio. Quando atinge estes
valor, o feromônio terá evaporado totalmente. O valor padrão é 0.01.
– gridDensity (opcional): valor de subdivisões da grade por centı́metro.
Pode ser 1, 2 ou 3, sendo 2 o valor padrão. Os valores de feromônio são
depositados em uma matriz bidimensional de dimensões iguais à largura
e altura do ecossistema em centı́metros. Com esta opção, é possı́vel
multiplicar ambas as dimensões desta matriz por 2 ou 3. Quanto mais
subdividido o ecossistema, mais discretas serão as trilhas de feromônios
e mais caminhos possı́veis as formigas serão capazes de escolher.
– width (obrigatório): largura do ecossistema, em centı́metros.
– height (obrigatório): altura do ecossistema, em centı́metros.
• <colony>
Contém informações sobre o ninho de formigas.
Atributos:
– ants (obrigatório): número de formigas desbravadoras que deixam o
ninho, inicialmente.
– reinforcements (opcional): número de formigas recrutadas por vez. O
valor padrão é 2.
• <leaves>
Como a aplicação foi originalmente concebida para suportar múltiplas presas, <leaves> permite alterar parâmetros qua afetam todas elas da mesma
maneira. Deve conter uma única entidade <leaf>.
Atributos:
– friction (opcional): coeficiente de atrito. O valor padrão é 0.3.
19
– areaDensity (opcional): densidade superficial da folha. o peso das folhas
depende desta densidade e do raio das folhas. O valor padrão é 0.0025.
– topSpeed (opcional): velocidade máxima com que as folhas podem ser
carregadas. O valor padrão é 0.55.
• <leaf>
Uma única folha. Pode conter múltiplas (ou nenhuma) sub-entidades <hook>.
Atributos:
– location (obrigatório): localização da folha segundo o sistema de coordenadas do ecossistema. Deve ser especificada no formato “(a, b)” ou
“a, b”, onde a e b são números reais. O espaço após a vı́rgula é opcional.
– radius (obrigatório): raio da folha, em centı́metros.
A entidade <hook> Adiciona um gancho à folha.
Atributos:
– pointer: Vetor da direção principal do gancho no sistema de coordenadas do ecossistema.
– threshold: valor mı́nimo de atuação do gancho, em centı́metros.
– arc: valor do arco de abertura do gancho, em radianos.
Exemplo:
<environment>
<e co sy s te m g r i d D e n s i t y=”2” width=” 45 ” h e i g h t=” 45 ”
rho=” 0 . 5 e−3” t h r e s h o l d=” 0 . 0 1 ”/>
<c o l o n y a n t s=”5” d e l i v e r i n g D i s t a n c e=”2”
l o c a t i o n=” 2 2 . 5 , 2 2 . 5 ” r a d i u s=”2”
r e i n f o r c e m e n t s=”3”/>
<l e a v e s a r e a D e n s i t y=” 0 . 0 0 0 7 5 ” f r i c t i o n=” 0 . 4 ”
topSpeed=” 0 . 7 ”>
< l e a f l o c a t i o n=” 1 2 . 5 , 3 2 . 5 ” r a d i u s=”5”/>
</ l e a v e s>
</ environment>
6.1.4
<animation>
Permite configurar um pequeno número de opções básicas da visualização da simulação. Pode conter as entidades <leaf-anim> e <ant-anim> nesta ordem, mas
não necessariamente as duas. Todos os atributos desta entidade e daquelas são
opcionais.
Atributos:
• scale (opcional): define quantos pixels são utilizados por centı́metro no desenho da simulação. O valor padrão é 20.
• drawGrid (opcional): se “true”, desenha a grade de vértices do ecossistema,
se “false”, não desenha a grade. O valor padrão é “true”.
Sub-entidades:
20
• <ant-anim>
Contém opções quanto ao desenho das formigas.
Atributos:
– size (opcional): raio das formigas, que são representadas através de
cı́rculos. O valor padrão é 0.3.
– fill (opcional): se verdadeiro, preenche as formigas com a vor de contorno, caso contrário, desenha apenas o contorno. O valor padrão é
“true”.
– drawVectors (opcional): se verdadeiro, habilita o desenho dos vetores
de força aplicada e velocidade. O valor padrão é “true”.
– drawForce (opcional): se verdadeiro, habilita o desenho do vetore de
força aplicada. O valor padrão é “false”.
– drawVelocity (opcional): se verdadeiro, habilita o desenho do vetore de
velocidade. O valor padrão é “false”.
• <leaf-anim>
Contém opções quanto ao desenho das folhas
Atributos:
– drawForces (opcional): se “true”, habilita o desenho dos vetores de
forças e de ganchos. O valor padrão é “true”.
– drawHooks (opcional): se “true”, habilita o desenho dos ganchos atuantes. O valor padrão é “false”.
– drawResultant (opcional): se “true”, habilita o desenho do vetores de
força resultante; se “false”, desenha a força aplicada total. O valor
padrão é “false”.
Exemplo:
<animation s c a l e=” 15 ” drawGrid=” f a l s e ”>
<l e a f −anim drawForces=” t r u e ” drawHooks=” t r u e ”
drawResultant=” f a l s e ”/>
<ant−anim drawVectors=” t r u e ” d r a w V e l o c i t y=” f a l s e ”
drawForce=” t r u e ” f i l l =” t r u e ” s i z e=” 0 . 3 ”/>
</ animation>
6.2
Saı́da da simulação
No final da simulação, os dados são inseridos no arquivo definido na entrada da
simulação (atributo “output” da entidade “<simulation>”).
A primeira linha do arquivo informa o horário do final da primeira rodada da
simulação, e as outras informam os valores das variáveis durante a rodada (quer
elas variem entre uma rodada e outra, quer não).
As variáveis de entrada só estarão presentes na saı́da se forem explicitadas
como entradas no arquivo de entrada. Os valores impressos na saı́da para variáveis
estatı́sticas são as médias destas variáveis, seja qual for a distribuição.
Exemplo:
21
#Wed Aug 05 19 : 3 9 : 0 9 BRT 2009
Colony . a n t s =15 ,15 ,15 ,15
Ecosystem . s u r f a c e =2025 ,2025 ,2025 ,2025
Ecosystem . rho =5.0E−4 ,5.0E−4 ,5.0E−4 ,5.0E−4
Ecosystem . g r i d D e n s i t y =2 ,2 ,2 ,2
Colony . r e i n f o r c e m e n t s =9 ,9 ,9 ,9
Workers . movement =76 ,66 ,73 ,63
L e a f . a r e a D e n s i t y =7.5E−4 ,7.5E−4 ,7.5E−4 ,7.5E−4
L e a f . topSpeed = 0 . 7 , 0 . 7 , 0 . 7 , 0 . 7
Leaf . d i s t a n c e =42.169907 ,42.169907 ,42.169907 ,42.169907
Leaf . d e l i v e r y =151.03514378 ,161.50254692 ,164.08383385 ,154.75300962
Leaf . f i n d i n g =13.116619583 ,8.249502757 ,7.290980041 ,11.188247748
Leaf . radius = 5 . 0 , 5 . 0 , 5 . 0 , 5 . 0
Leaf . f r i c t i o n = 0 . 4 , 0 . 4 , 0 . 4 , 0 . 4
L e a f . movement = 1 1 3 . 9 1 0 6 , 1 2 8 . 9 7 4 4 7 3 2 3 6 , 1 3 2 . 6 1 6 0 , 1 1 9 . 2 6 8 8 7 6 3 8 8
Leaf . t r a n s p o r t i n g =24.0079031 ,24.2785709 ,24.17677560 ,24.29588548
Workers . d e l i v e r y =113 ,104 ,127 ,99
Ecosystem . t h r e s h o l d = 0 . 0 0 9 8 2 5 8 2 , 0 . 0 0 9 8 2 5 8 2 , 0 . 0 0 9 8 2 5 8 2 , 0 . 0 0 9 8 2 5 8 2
6.3
Transformando a saı́da em outros formatos e gráficos
Uma vez que simulações tenham sido rodadas e seus dados tenham sido gravados
em arquivos properties, o programa auxiliar Ants-Report.jar pode ser utilizado
para coletar dados relevantes e gravá-los em formatos mais úteis. Na versão atual,
há duas maneiras de processar os dados: arquivos CSV e gráficos gerados pelo gnuplot, ambos mencionados na seção “Linguagens, ferramentas e padrões utilizados”
deste documento. O programa recebe um arquivo XML com os dados necessários
para fazer a conversão de formatos. A seguir, uma descrição do formato do arquivo
XML:
6.3.1
<report>
Esta etidade deve estar presete em todo e qualquer relatório e deve ser única. Deve
conter apenas uma entre as entidades <plot-2d>, <plot-3d>, <csv> e <csv-all>
e deve conter uma ou mais entidades <input>.
Atributos:
• file (obrigatório): contém o arquivo em que será gravada a saı́da, exceto no
caso em que ela for direcionada para o terminal interativo. No último caso,
o valor do campo será ignorado, mas ainda assim, deve ser especificado.
Sub-entidades:
• <plot-2d>
Indica que um gráfico em duas dimensões deve ser gerado. Contém as subentidades <x> e <y>, nesta ordem. Atributos:
– title (opcional): permite mudar o tı́tulo padrão adicionado ao topo do
gráfico. O valor padrão é o nome do arquivo de entrada.
– type (opcional): escolhe o tipo de saı́da da imagem. Pode possuir os
seguintes valores: PNG, GIF, BMP, JPG, SVG, EPS, DEFAULT. O
22
último direciona a saı́da para o terminal interativo e os demais constituem formatos de imagem, sendo recomendado colocar a extensão de
arquivo correspondente ao tipo escolhido aqui. Assim, por exemplo, se
o tipo escolhido for “GIF”, o arquivo deve ter um nome semelhante a
“arquivo.GIF” ou “arquivo.gif”. O valor padrão é “PNG”.
– average (opcional): se “true”, indica que as médias aritméticas dos
valores referentes a cada simulação serão gravadas. Se “false”, cada
valor será registrado. O valor padrão é “false”.
– style (opcional) - determina o estilo de desenho dos pontos do gráfico.
O gnuplot suporta muitos estilos diferentes, mas somente os estilos
“POINTS” e “LINES” são suportados nesta versão da aplicação. “POINTS”
desenha os pontos como cruzes vermelhas e “LINES” traça linhas entre
pontos consecutivos do gráfico. O valor padrão é “POINTS”.
– margin (opcional): indica a porcentagem de margem q deve ser deixada
em relação aos limites do gráfico, para evitar que os pontos fiquem
colados nos cantos do gráfico. O valor padrão é 0,1.
Sub-entidades:
– <x> e <y>
Escolhe a variável de simulação utilizada no eixo x, y e permite escolher
algumas outras opções de gráfico relacionadas a cada eixo.
Atributos:
∗ range (opcional): escolhe os limites inferior e superior do eixo. Se
não especificado, os limites serão automaticamente escolhidos para
se ajustar aos menores e maiores valores, respectivamente. Deve
ser especificado na forma “a:b”, onde a é o limite inferior e b é o
limite superior, a e b números reais.
∗ label (opcional): especifica o nome do eixo, que será apresentado no
gráfico. Se não especificado, assume o valor do atributo “variable”.
∗ variable (obrigatória): escolhe a variável correspondente ao eixo,
pode ter um dos seguintes valores, dependendo da entidade (todas
essas variáveis são descritas na seção “Variáveis do programa”):
· Para a entidade <x>: Aco.alpha, Aco.beta, Colony.ants, Aligning.angleTurn, Aligning.chargeRate, Aligning.exhaustion, Aligning.firstCharge, Aligning.insistance, Aligning.tries, Ant.initiative,
Ant.intelligence, Ant.sight, Ant.topForce, Ant.topSpeed, Carrying.firstCharge, Carrying.tolerance, Circumventing.insistance,
Circumventing.sociability, Colony.reinforcements, Leaf.areaDensity,
Leaf.distance, Leaf.friction, Leaf.radius, Leaf.topSpeed, Hook.modulus,
Hook.arc, Redocking.offset ou Seeking.audacity.
· Para a entidade <y>: Leaf.delivery, Leaf.finding, Leaf.movement,
Leaf.transporting, Workers.delivery ou Workers.movement.
• <plot-3d>
Indica que um gráfico em três dimensões deve ser gerado. Contém as subentidades <x>, <y> e <z> nesta ordem. Atributos:
– title (opcional): permite mudar o tı́tulo padrão adicionado ao topo do
gráfico. O valor padrão é o nome do arquivo de entrada.
23
– type (opcional): escolhe o tipo de saı́da da imagem. Pode possuir os
seguintes valores: PNG, GIF, BMP, JPG, SVG, EPS, DEFAULT. O
último direciona a saı́da para o terminal interativo e os demais constituem formatos de imagem, sendo recomendado colocar a extensão de
arquivo correspondente ao tipo escolhido aqui. Assim, por exemplo, se
o tipo escolhido for “GIF”, o arquivo deve ter um nome semelhante a
“arquivo.GIF” ou “arquivo.gif”. O valor padrão é “PNG”.
– average (opcional): se “true”, indica que as médias aritméticas dos
valores referentes a cada simulação serão gravadas. Se “false”, cada
valor será registrado. O valor padrão é “false”.
– style (opcional) - determina o estilo de desenho dos pontos do gráfico.
O gnuplot suporta muitos estilos diferentes, mas somente os estilos
“POINTS” e “LINES” são suportados nesta versão da aplicação. “POINTS”
desenha os pontos como cruzes vermelhas e “LINES” traça linhas entre
pontos consecutivos do gráfico. O estilo “LINES” funciona melhor em
gráficos bidimensionais. O valor padrão é “POINTS”.
– margin (opcional): indica a porcentagem de margem q deve ser deixada
em relação aos limites do gráfico, para evitar que os pontos fiquem
colados nos cantos do gráfico. O valor padrão é 0,1.
Sub-entidades:
– <x>, <y> e <z>
Escolhe a variável de simulação utilizada no eixo x, y ou z e permite
escolher algumas outras opções de gráfico relacionadas a cada eixo.
Atributos:
∗ range (opcional): escolhe os limites inferior e superior do eixo. Se
não especificado, os limites serão automaticamente escolhidos para
se ajustar aos menores e maiores valores, respectivamente. Deve
ser especificado na forma “a:b”, onde a é o limite inferior e b é o
limite superior, a e b números reais.
∗ label (opcional): especifica o nome do eixo, que será apresentado no
gráfico. Se não especificado, assume o valor do atributo “variable”.
∗ variable (obrigatória): escolhe a variável correspondente ao eixo,
pode ter um dos seguintes valores, dependendo da entidade (todas
essas variáveis são descritas na seção “Variáveis do programa”):
· Para a entidade <x>: Aco.alpha, Aco.beta, Colony.ants, Aligning.angleTurn, Aligning.chargeRate, Aligning.exhaustion, Aligning.firstCharge, Aligning.insistance, Aligning.tries, Ant.initiative,
Ant.intelligence, Ant.sight, Ant.topForce, Ant.topSpeed, Carrying.firstCharge, Carrying.tolerance, Circumventing.insistance,
Circumventing.sociability, Colony.reinforcements, Leaf.areaDensity,
Leaf.distance, Leaf.friction, Leaf.radius, Leaf.topSpeed, Hook.modulus,
Hook.arc, Redocking.offset ou Seeking.audacity.
· Para a entidade <y>: Aco.alpha, Aco.beta, Colony.ants, Aligning.angleTurn, Aligning.chargeRate, Aligning.exhaustion, Aligning.firstCharge, Aligning.insistance, Aligning.tries, Ant.initiative,
Ant.intelligence, Ant.sight, Ant.topForce, Ant.topSpeed, Carrying.firstCharge, Carrying.tolerance, Circumventing.insistance,
24
Circumventing.sociability, Colony.reinforcements, Leaf.areaDensity,
Leaf.delivery, Leaf.distance, Leaf.finding, Leaf.friction, Leaf.radius,
Leaf.movement, Leaf.topSpeed, Leaf.transporting, Hook.modulus,
Hook.arc, Redocking.offset, Seeking.audacity, Workers.delivery
ou Workers.movement.
· Para a entidade <z>: Leaf.delivery, Leaf.finding, Leaf.movement,
Leaf.transporting, Workers.delivery ou Workers.movement.
• <csv>
Determina a geração de um arquivo CSV ao invés de um gráfico. Pode conter
uma ou mais sub-entidades <col>, cada uma sendo uma coluna da tabela.
Atributos:
– header (opcional): caso seja “true”, a primeira linha da tabela conterá
o tı́tulo das colunas, correspondente ao tı́tulo dos eixos especificado nas
entidades <x>, <y> e <z>. O valor padrão é “true”.
Sub-entidades:
– <col>
Representa uma coluna na tabela.
Atributos:
∗ label (opcional): especifica o nome da coluna da tabela. Se não
especificado, assume o valor do atributo “variable”.
∗ variable (obrigatória): escolhe a variável correspondente ao eixo,
pode ter um dos seguintes valores (todas essas variáveis são descritas na seção “Variáveis do programa”): Aco.alpha, Aco.beta, Colony.ants, Aligning.angleTurn, Aligning.chargeRate, Aligning.exhaustion,
Aligning.firstCharge, Aligning.insistance, Aligning.tries, Ant.initiative,
Ant.intelligence, Ant.sight, Ant.topForce, Ant.topSpeed, Carrying.firstCharge,
Carrying.tolerance, Circumventing.insistance, Circumventing.sociability,
Colony.reinforcements, Leaf.areaDensity, Leaf.distance, Leaf.friction,
Leaf.radius, Leaf.topSpeed, Hook.modulus, Hook.arc, Redocking.offset
ou Seeking.audacity, Aco.alpha, Aco.beta, Colony.ants, Aligning.angleTurn,
Aligning.chargeRate, Aligning.exhaustion, Aligning.firstCharge, Aligning.insistance, Aligning.tries, Ant.initiative, Ant.intelligence, Ant.sight,
Ant.topForce, Ant.topSpeed, Carrying.firstCharge, Carrying.tolerance,
Circumventing.insistance, Circumventing.sociability, Colony.reinforcements,
Leaf.areaDensity, Leaf.delivery, Leaf.distance, Leaf.finding, Leaf.friction,
Leaf.radius, Leaf.movement, Leaf.topSpeed, Leaf.transporting, Hook.modulus,
Hook.arc, Redocking.offset, Seeking.audacity, Workers.delivery ou
Workers.movement, Leaf.delivery, Leaf.finding, Leaf.movement, Leaf.transporting,
Workers.delivery ou Workers.movement.
• <csv-all>
Determina a geração de um arquivo CSV ao invés de um gráfico, mas ao
contrário da entidade <cvs>, insere no arquivo CSV todas as variáveis disponı́veis para os arquivos indicados pelas entidades <input>.
Atributos:
25
– header (opcional): caso seja “true”, a primeira linha da tabela conterá
o tı́tulo das colunas, correspondente ao nome das variáveis. O valor
padrão é “true”.
• <input>
Adiciona um arquivo de saı́da de simulação como entrada para geração do
relatório.
Atributos:
– file (obrigatório): nome do arquivo de saı́da de simulação.
7
Experimentos
Realizamos alguns experimentos com a aplicação, e fizemos gráficos com os dados
recolhidos.
Os arquivos de simulação foram nomeados segundo a convenção input-xyz.xml,
onde:
x se refere ao número de formigas desbravadoras que deixam o ninho, inicialmente.
• x = 0 =⇒ Colony.ants = 5
• x = 1 =⇒ Colony.ants = 15
• x = 2 =⇒ Colony.ants = 25
y se refere ao número de formigas que saem do ninho quando uma formiga
retorna para recrutar apoio.
• y = 0 =⇒ Colony.reinforcements = 3
• y = 1 =⇒ Colony.reinforcements = 6
• y = 2 =⇒ Colony.reinforcements = 9
z se refere à distância da folha ao ninho.
• z = 0 =⇒ Leaf.distance = metade da distância do raio do cı́rculo inscrito na
tela da simulação.
• z = 1 =⇒ Leaf.distance = distância do raio do cı́rculo inscrito na tela da
simulação.
Exemplo: input-201.xml é a simulação na qual 25 formigas deixam o ninho a
princı́pio, os reforços são de 3 em 3 formigas e a folha está a uma distância do
ninho equivalente ao raio do cı́rculo inscrito na tela da simulação.
Os arquivos dos gráficos foram nomeados segundo a convenção report-###?.xml, onde:
? indica qual variável está no eixo y, sendo:
• a −→ Leaf.finding
• b −→ Leaf.delivery
26
• c −→ Leaf.movement
• d −→ Leaf.transporting
Dois dos #’s são números que indicam os valores dos parâmetros, segundo a
convenção anterior, e um # é um X, indicando qual parâmetro está variando.
Exemplo: report-20X-b.xml é o gráfico no qual 15 formigas saem da colônia e
o tamanho do reforço é 3 em todas as simulações. O que varia é a distância da
folha ao ninho (que é a variável do eixo x) e a variável do eixo y é Leaf.delivery.
Isso significa que este é um gráfico das simulações input-200.xml e input-201.xml.
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47