Original Article: Simulation of Ant's Emergent Behavior Using StarLogo

Author: thepangburns.com

Simulação do comportamento emergente da Ant usando StarLogo

Esta página é sobre um pequeno projeto pessoal meu para investigar o comportamento emergente. Para esse fim, criei uma colônia de ants virtual usando um pedaço de software chamado StarLogo feito por algumas pessoas no MIT. A idéia é que cada ant sozinha é próxima a inútil para reunir alimentos de forma eficiente, mas um monte de ants cada uma agindo em seu próprio conjunto simples de regras juntas são capazes de reunir comida de forma muito mais eficiente. Este fenômeno em que a capacidade do grupo é maior do que a soma de cada indivíduo atuando sozinho, pode ser uma forma de comportamento emergente. Um excelente livro sobre o comportamento emergente é "EMERGÊNCIA A vida conectada de ants, cérebros, cidades e software" por Steven Johnson. Este livro foi recomendado por um amigo e me inspirou a fazer este projeto. Vou citar sua definição de emergência aqui, da aba interna da capa do livro:

O surgimento é o que acontece quando um sistema interconectado de elementos relativamente simples se auto-organiza para formar um comportamento de nível superior mais inteligente e mais adaptável. É um modelo de baixo para cima; em vez de ser projetado por um planejador geral ou mestre, a emergência começa no nível do solo. Os sistemas que, a primeira vista, parecem muito diferentes - colônias de ants, cérebros humanos, cidades, sistemas imunológicos - todos seguem as regras de emergência. Em cada um desses sistemas, os agentes que residem em uma escala começam a produzir um comportamento que situa uma escala acima deles: as ants criam colônias, os habitantes urbanos criam bairros.

A seguir, uma captura de tela das minhas ants virtuais reunindo comida e trazendo de volta ao ninho.:

Isso pode parecer complicado no início, mas na verdade é bastante simples.  Se você quiser ver isso executando em seu próprio computador, basta seguir estas simples etapas:

1. baixe e instale o software StarLogo do MIT.  NOTA: Meu software foi escrito na versão 1.2.2 do StarLogo e a versão atual é 2.0.  Minha fonte original não era compatível e algumas pessoas gentis me disseram que estavam recebendo uma mensagem de erro, então eu atualizei o link de origem abaixo para fornecer uma versão compatível com 2.0.  Não tenho certeza se isso funcionará com a versão 1.2.2, então, se você tiver essa versão e tiver problemas, peço desculpas, tente a versão 2.0.
2. baixe o meu código fonte.  Se este arquivo abrir no seu navegador, basta fazer o backup desta página, clique com o botão direito do mouse e "Save Target As..." para salvá-lo em seu disco rígido como "ant_simulation.slogo"
3. execute StarLogo e abra o meu arquivo de código-fonte que você acabou de baixar.  
4. Para a demonstração mais simples, clique no botão "setup" uma vez e, em seguida, clique no botão "execute turn".  Então as ants agora começarão a correr e logo formarão uma trilha para a comida.
5. Em troca de usar meu código-fonte, eu simplesmente pergunto algumas coisas.  Primeiro, sinta-se livre para se divertir e fazer mudanças no software.  Em segundo lugar, se você fizer melhoras que você achar interessantes, me mande um email!

Então, de volta ao que está acontecendo na foto: 

• Ant indivíduos - os pontos vermelho e azul são as ants individuais.  As ants coloridas vermelhas vieram do ninho e estão procurando comida.  As ants azuis têm comida e estão procurando o ninho para depositar a comida.
• Trilhas de perfume - as ants que deixam o ninho deixam uma trilha decadente de "aroma de ninho", estas são as linhas vermelhas.  Quando uma ant que procura o ninho aparece em uma trilha como essa, ela (as trabalhadoras de ants são do sexo feminino, você não sabe?) Sabe que, se ela seguir, ela acabará por acabar no ninho.  O mesmo vale para as trilhas de comida azul.
• O ninho - o centro das trilhas de perfume de ninho vermelho é o ninho.  As ants vêm do ninho e retornam lá para depositar os alimentos que coletaram.
• A comida - os pontos amarelados / verdes são itens alimentares.  Cada ponto tem uma determinada quantidade de "pontos de comida", ou peças que uma ant pode romper com isso.  É meio difícil ver, mas os diferentes pontos de comida são na verdade um pouco diferentes em cores.  Quanto mais verde é o ponto, mais pontos de comida são deixados naquele pedaço de comida.
• The Great Food Trail - a estrada que as ants criaram entre o seu ninho e a comida, note que é bastante liso.

Com este entendimento, vou tentar explicar o que as regras seguem as ants, então, como essas regras simples levam a esse belo exemplo de comportamento emergente (a boa trilha alimentar direta que permite que as ants coletem mais eficientemente). Se ainda não o fez, deixe-me recomendar que você instale e execute o software antes de continuar. Embora seja uma boa captura de tela, se eu mesmo disser isso, não é um substituto para ver as ants correndo e construir a trilha - é absolutamente fascinante assistir (talvez apenas para mim?) E isso fará com que essa explicação seja muito mais fácil Compreendo.

Uma vez que não sei por onde começar a explicar isso, o que vou fazer é começar no topo da janela do aplicativo e explicar o que significam os diferentes botões, slides e caixas de informações. Quando eu chegar ao fundo, deve ser bastante claro o que está acontecendo (também, tenha em mente as descrições acima do que a exibição gráfica significa).

• o botão"setup" - este botão inicializa o aplicativo, limpando qualquer coisa restante de uma execução anterior do aplicativo e criando uma nova pilha de alimentos. O alimento é desembolsado em um determinado local com uma propagação gaussiana. No caso de "propagação gaussiana" é grego para você, imagine o que aconteceria se você deixasse um punhado de BBs no chão. Eles estariam centrados em torno do local onde você os abandonou, mas alguns ficariam mais longe desse centro do que outros por chance aleatória. É assim que o alimento é desembolsado. Este botão também cria um novo ninho, limpa as variáveis da última execução e, em seguida, começa a fazer uma ant sair do ninho cada segundo até a quantidade definida de ants
• botão "execute turn" - este botão diz a cada ant que tome uma "turn".  Este botão passa e continua dizendo às ants que tomem outra volta até você clicar novamente e pará-las.  Um turno pode consistir em mover um passo, pegar comida, deixar comida, etc.
• botão "debug turn" - não importa este botão, eu esqueci o que faz de qualquer maneira, e não importa o suficiente para incomodar tentar lembrar ou olhar através do código  :-)
• "NumWorkers" slider - isto é simplesmente o número de ants que você quer correr.  Você deve definir isso antes de pressionar o botão "setup", ou seja, quando a simulação estiver em ação, você não pode adicionar mais ants.
• slider "NumFood" - este é o número de bocados de comida que você deseja que haja.  Isso também deve ser definido antes de atingir o botão "setup".
• caixa de informações "FoodGathered" - esta é uma exibição da variável FoodGathered.  Isto obviamente controla a quantidade de pontos de comida que as ants trouxeram de volta ao ninho.  Esta é a métrica de desempenho que uso para avaliar a qualidade/"genetic fitness" de uma determinada população de ants.  A "HeadingConsistency" controle deslizante e baixo são as configurações que fazem de forma exclusiva uma população de ants adequadamente.  Se essas configurações não são boas, então a população não tem um bom "genetic fitness" uma vez que não conseguem reunir muita comida.
• "FoodPointsPerItem" slider - isso define o número de pontos de comida que cada peça de comida tem.  O objetivo disso é simular ants agarrando um pequeno pedaço de pedaço de comida.  Para colocá-lo em termos de um verdadeiro pedaço de comida, ele descreve o quão grande é cada pedaço de comida e quantos pedaços podem ser usados antes que ele tenha desaparecido.
• "HeadingConsistency" slider - se você já viu uma ant andando por aí, a menos que eles seguissem uma trilha que eles meandro.  Você pode ver o que quero dizer ao olhar para algumas trilhas na captura de tela acima.  Para obter esse caminho errante, cada vez que uma ant vai dar um passo, há uma chance percentual de que a ant altere seu ângulo de partida.  Esta variável é a porcentagem de chance de que a ant NÃO altere o título em uma determinada curva.
• "HeadingDegreeRandomizer" slider - depois que a ant usa o controle deslizante "HeadingConsistency" acima e determinou que quer fazer uma mudança de título, ele usa esse controle deslizante para ajudar a determinar a quantidade de mudanças a serem feitas.  Basicamente, ele gera um grau aleatório de -"HeadingDegreeRandomizer" para +"HeadingDegreeRandomizer" fora do curso atual.  Só pode girar 1 ou 2 graus para a esquerda ou para a direita, ou pode virar para a esquerda ou para a direita para a quantidade total do controle deslizante.
• "ScentStrengthDecay" slider - quando uma ant está deixando o ninho (ou simplesmente pegou um pedaço de comida), ele cai perfume indicando que ele acabou de sair do ninho (ou um pedaço de comida).  À medida que continua em movimento, a força do cheiro que está caindo deve se deteriorar para que outra ant que venha sobre a trilha possa dizer em que direção o ninho está.  Isso é mais fácil de ver na captura de tela com as trilhas azuis, você pode ver que eles são mais brilhantes perto da comida.  Isso faz sentido em termos do comportamento real das ants, é bom que a força do cheiro caiu para indicar a proximidade de algo.
• "GroundScentDecay" trilhos deslizantes no chão na vida real são lentamente lavados pelos elementos do vento e da água.  Isso é realmente útil para as ants, uma vez que não querem seguir velhas trilhas para comida que já passou.  Então, esse controle deslizante determina quão rápidas trilhas no chão virtual se deterioram.  Quanto menor for o número, mais rápido a decadência.  Este número deve ser maior do que o valor "ScentStrengthDecay" para que as trilhas sejam mais fortes perto do objeto que estão marcando.
• "SearchDistance" slider - cada vez que uma ant dá um passo, parece em frente a si mesmo por coisas de interesse.  Este controle deslizante determina o raio à frente de si, a ant pode ver.  Ele varre através deste raio por -45 a +45 graus de seu título atual.  Dependendo se a ant está procurando comida ou o ninho é o que determina o tipo de coisas que está procurando.  Se está à procura de alimentos, a sua primeira prioridade a procurar é um pedaço real de alimentos dentro do seu alcance de varredura, se não vê nenhum alimento lá, então procura uma trilha de aromas de comida.  Se está procurando o ninho, então sua primeira prioridade é olhar e ver se o ninho está bem na frente dele, então, se ele não vê o ninho, ele procura uma trilha de ninho.
• "FollowProbability" slider - quando uma ant vê uma trilha que pode estar interessada, então esse controle deslizante entra em jogo.  Isso determina a chance de a ant seguir a trilha.  Isso traz um ponto: a ant nem sempre segue uma trilha do tipo que eles estão procurando.  Novamente, se você já viu ants, às vezes uma ant que não carrega comida vai caminhar através de uma trilha que leva a algum alimento.  Eu não sabia por que isso era, mas depois de programá-lo, tornou-se óbvio por que era benéfico para as ants.  Dois bons motivos, primeiro dos quais é que às vezes um rastro existente para a comida ou o ninho não é o caminho mais curto.  Então, se uma ant nem sempre segue uma trilha e, às vezes, deixa uma trilha, e então eles seguem a trilha novamente - então sua trilha pode ser a mais curta!  É assim que as ants construíram essa linda trilha direta do ninho para a comida!  No início, o caminho era muito curvilíneo, mas com o efeito deste deslizador, as ants que deixaram a trilha e voltaram mais tarde encontraram um caminho mais curto.  Devido à decadência das trilhas de perfume, caminhos mais curtos são reforçados melhor e têm um perfume mais forte do que um longo caminho.  Isso traz o fator adicional na sequência de uma trilha: a probabilidade de seguir uma determinada trilha é baseada neste controle deslizante e quão forte é a trilha.  Se é uma trilha fraca, então a ant tem menos probabilidade de segui-la, e se é uma trilha forte, então a ant é mais provável que a siga, o que contribui para a construção de caminhos mais curtos.  A segunda boa razão para não seguir sempre uma trilha é que pode haver comida em outro lugar (além da peça atual de que eles estão agarrando) e, portanto, algumas ants precisam estar procurando outra fonte de alimento.  Atualmente, não há como descartar novos pedaços de comida, mas essa é uma característica que eu gostaria de adicionar.
• botão "evolve" - este botão é a última coisa que adicionei.  Como acabei de definir o valor dos controles deslizantes com base em alguma experimentação para descobrir algumas configurações que permitiriam que as ants coletissem alimentos de forma razoavelmente eficiente, é claro que as configurações que usei provavelmente não são ótimas.  O que esse botão faz é executar a simulação um par de vezes por cerca de dois minutos cada, em seguida, pegue a média do valor FoodGathered para determinar o desempenho dessa população de ants.  Em seguida, muda o controle deslizante "FollowProbability" por uma pequena quantidade aleatória, depois executa a simulação duas vezes mais.  Se o "FoodGathered" for maior do que a população anterior, ele armazena esta nova "FollowProbability" como a melhor e depois faz outra pequena mudança aleatória e repete.  Isso permite que o "FollowProbability" evolua para o melhor valor.  Infelizmente, o StarLogo não é um bom programa para ler e escrever dados, o que torna muito difícil escrever um bom algoritmo genético para modificar todos os controles deslizantes.  Daí a tentativa patética de evolução que só modifica esse deslize e está, naturalmente, sujeita a erros máximos locais.  

Neste ponto, você deve ter uma boa idéia de como este programa funciona.  Se você chegou tão longe, espero que você esteja interessado em jogar com ele por conta própria.  Eu recomendo encorajá-lo e jogar com os controles deslizantes para ver como ele afeta as ants, observe que muitas combinações de configurações irão completamente incapacitar sua capacidade de reunir comida de forma razoavelmente eficiente, então, se você deseja salvar suas mudanças, você deve fazê-lo com um novo nome de arquivo para que você sempre possa reiniciar com minhas configurações se você não conseguir as ants funcionando novamente novamente.

Coisas que eu gostaria de melhorar

Principalmente, eu gostaria de melhorar a evolução das ants a partir do método de hack pouco bobo que usei acima para evoluir o "FollowProbability". Eu estava esperando que eu pudesse de alguma forma ter uma interface de programa C (ou qualquer linguagem de programação com boa capacidade de manipulação de dados) com o StarLogo. Isso permitiria ao programa C fazer coisas como criar árvores genéticas das configurações do controle deslizante, pois eu suspeito que a ramificação dos caminhos genéticos seria necessária para encontrar combinações ótimas de configurações, uma vez que as configurações estão relacionadas e, portanto, pode haver mínimos e máximos locais para uma determinada configuração em relação a outra. O que quero dizer com isso é que se você simplesmente mover uma configuração por vez, você encontrará um ponto em que essa configuração é melhor, mas se você alterar algumas outras configurações, a primeira configuração pode não ser mais otimizada. É por isso que eu suspeito que ter vários ramos na cadeia de evolução pode ajudar a descobrir as configurações mais eficientes. O programa AC poderia gerenciar esses dados e fazer as mudanças evolutivas e chamar o programa StarLogo para executar uma determinada população de ants algumas vezes para medir sua capacidade de coletar alimentos, o programa C, então, pode ler os resultados e determinar se a nova população era um melhoria ou um passo na direção errada.

Entrei em contato com as pessoas que escreveram o StarLogo para perguntar se eles tinham escrito uma interface oculta como essa, mas eles disseram que não tinham, mas que tinham pensado nisso. Estava de volta em outubro, e eu estava esperando que eles saíssem com uma nova versão, incluindo esse recurso até agora, mas até agora não lançaram novas atualizações para o StarLogo desde a versão 1.2.2 que recebi então. Eu suspeito que os principais autores (se não todos os envolvidos) estão trabalhando em outras coisas agora.

Atualização: talvez o StarLogo 2.0 tenha alguma disposição para se comunicar com um idioma mais adequado para lidar com os conjuntos de dados para executar um bom algoritmo de evolução.  Eu ainda não tive tempo para examinar isso, mas se alguém souber a resposta, eu apreciaria uma dica. :-)