A programação evolutiva converte o darwinismo em algoritmos

A evolução é, sem dúvida, a “teoria” de maior alcance para enfeitar a revolução científica. De uma só vez, explica a biodiversidade, a forma em que evoluíram todos os seres vivos; como se reproduzir seletivamente para quase qualquer característica – de cães que matam ratos a vacas pesadas e abundantes – e mesmo por que há vida no universo. No entanto, agora que a era do computador está sobre nós, os algoritmos evolutivos tornaram-se uma maneira de resolver problemas usando mutação algorítmica e recombinação em simulações.

Quando aplicado à biologia, as mutações dos planos de um organismo (como os raios cósmicos colidem com o seu ácido-ácido desoxirribonucleico) ou a recombinação deliberada do seu DNA (por exemplo, por engenheiros genéticos em um segmento de outro organismo) podem causar resultados aleatórios ou previsíveis , respectivamente. Da mesma forma, a programação evolutiva usa as mesmas técnicas para introduzir mudanças aleatórias ou previsíveis em uma simulação, que é então executada repetidamente usando diferentes mudanças para produzir uma “nuvem” de soluções que podem então ser comparadas para determinar qual é otimizado.

“A computação evolutiva é um campo grande e variado que existe há cerca de 50 anos”, disse Robert Heckendorn, professor associado de ciência da computação na Universidade de Idaho.

As estratégias de computação evolutiva avançaram para incluir uma infinidade de algoritmos de inspiração biológica para otimizar problemas, geralmente aqueles com muitas variáveis ​​para comparar todos os cenários possíveis; assim, a necessidade de evoluir apenas o melhor. Essas técnicas, algumas vezes chamadas de soft computing , incluem teste e erro , metaheurísticas , otimização estocástica , programação genética , neuroevolução , sistemas de classificação de aprendizado baseados em aprendizagem de reforço ou aprendizagem supervisionada e dezenas de outras variações. O que todos eles têm em comum é que eles resolvem problemas com tantas variáveis ​​que o espaço de busca é muito grande para atravessar, enumerar e comparar em sua totalidade.

Você pode pensar que essas áreas problemáticas se concentrarão em ajudar os biólogos a entender a evolução e a genética, ou mesmo ajudar os agricultores a aumentar os touros do prêmio, mas você estaria errado, porque as técnicas de programação evolutiva são usadas principalmente para quebrar problemas em áreas completamente diferentes da biologia, genética e A própria evolução.

Um artigo apresentado neste verão na Conferência de Computação Genética e Evolutiva 2014 da ACM ( GECCO 2017, 15 a 19 de julho, em Berlim, Alemanha) é um bom exemplo. Intitulado Evolução de uma Evacuação em tempo real para a Gestão de Desastres Urbanos , o documento tomou como variáveis ​​todas as rotas diferentes que uma evacuação poderia usar, tendo em conta todos os danos causados ​​por um desastre urbano que poderia impedir os motoristas e pedestres tentando escapar e surgiu um conjunto de planos de evacuação que poderiam sobreviver à ditadura do presidente dos EUA, Eisenhower, de que “nenhum plano sobrevive ao primeiro contato com o inimigo”, apresentando uma nuvem de planos intercambiáveis ​​que podem ser trocados em tempo real à medida que os eventos se desenrolam.

Disse Heckendorn, um co-autor do artigo: “Estamos prontos com uma população de soluções potenciais para se adaptar de forma rápida e robusta às mudanças nas condições do desastre. Nada acontece como planejado”. Em vez disso, observa o resumo do papel, “usamos estratégias evolutivas e um modelo de probabilidade para encaminhar a população otimizando sua segurança. O algoritmo é projetado para usar os pontos fortes da computação evolutiva para otimizar repetidamente uma evacuação sob a dinâmica de um desastre, como acidentes que bloqueiam estradas críticas, colapsos de ponte, fechamentos de detritos, mudanças de segurança e pessoas que não seguem instruções de evacuação “.

Os algoritmos evolutivos, segundo Heckendorn, exigem “uma população, uma representação, métodos de reprodução / variação, e técnicas de seleção semelhantes às que a evolução natural usa. Nossa representação particular é uma nuvem de probabilidades que se centrou nas interseções rodoviárias, a saber, a maneira de sair a interseção. Isso faz um vetor que avaliamosexecutando uma simulação da cidade para avaliar cada um para fitness. Desenvolvemos uma população de vetores para resolver o problema usando nossas estratégias de evolução, então deixamos que o desastre se desdobre e re-otimize contra cada novo estado da cidade. As pontes podem entrar em colapso, o gás venenoso pode mudar de direção com o vento, as pessoas podem ignorar as instruções, e assim por diante. Para cada novo fator, re-otimizamos o melhor turno a ser feito em relação a cada novo cenário de desastres “.

Outro documento apresentado no GECCO 2017 incluiu um tutorial sobre como escrever algoritmos evolutivos que, simultaneamente, otimizem múltiplos objetivos. Tutorial Titulado sobre Otimização Multiobjetiva Evolutiva , o artigo explica como esta técnica vai contra o grão da maioria dos programas evolutivos, que geralmente possuem como principal objetivo individual para o qual várias variáveis ​​precisam ser ajustadas para alcançar uma solução ótima.

“Há muitos problemas algorítmicos difíceis na otimização multi-objetivo”, disse Heckendorn.

No entanto, de acordo com o autor do último papel, Dimo ​​Brockhoff, no Instituto Nacional de Pesquisa Déditio ao Numérico (inria, Instituto Francês de Pesquisa em Ciência da Computação e Automação), é possível otimizar múltiplos objetivos simultaneamente, embora nenhuma das soluções seja completamente otimizado para cada objetivo; Em vez disso, deve haver algum comprometimento de cada objetivo, a fim de alcançar uma solução global mais próxima do melhor possível para cada objetivo.

Ainda outro papel não modifica apenas a evolução, mas os comportamentos coordenados em tempo real evoluíram para “animais enxugados”, desde a construção de cúpulas por termitas até a comunicação entre abelhas e comportamentos de ant-trail para o forrageamento de escolas de peixes e comportamentos migratórios de bandos de aves. A vantagem dos algoritmos de escrita que imitam esses comportamentos de enxames, de acordo com Dirk Sudholt na Universidade de Sheffield (Reino Unido), em seu artigo Theory of Swarm Intelligence , é que aproveitam milhões de anos de táticas de otimização que podem ser diretamente lançadas em algoritmos.

De acordo com Sudholt, “os algoritmos Swarm são potentes otimistas de propósito geral que imitam e exploram a inteligência coletiva de um enxame de animais. Eles são fáceis de aplicar, mesmo quando o problema não é bem compreendido ou quando as técnicas padrão falham, e eles geralmente entregam soluções surpreendentemente boas “.

R. Colin Johnson é um membro do Prêmio de Kyoto que trabalhou como jornalista de tecnologia por duas décadas.

Haga clic aquí para más información