Outros Links:

Algoritmos Genéticos y Computación Evolutiva
Uma tradução espanhola deste artigo.

Introdução
Topo

Os criacionistas ocasionalmente acusam que a evolução é inútil como teoria científica porque não produz benefícios práticos e não tem relevância para a vida diária. No entanto, apenas as evidências da biologia mostram que essa alegação é falsa. Existem numerosos fenômenos naturais para os quais a evolução nos fornece uma base teórica sólida. Para citar apenas um, o desenvolvimento observado de resistência - a inseticidas em pragas agrícolas, a antibióticos em bactérias, à quimioterapia em células cancerígenas e a drogas anti-retrovirais em vírus como o HIV - é uma consequência direta das leis de mutação e seleção, e o entendimento desses princípios nos ajudou a elaborar estratégias para lidar com esses organismos nocivos. O postulado evolutivo da descendência comum auxiliou o desenvolvimento de novos medicamentos e técnicas médicas ao dar aos pesquisadores uma boa ideia de quais organismos eles devem experimentar para obter resultados que sejam mais prováveis de serem relevantes para os humanos. Finalmente, o princípio da seleção artificial tem sido usado com grande efeito pelos humanos para criar organismos personalizados, nada encontrados na natureza, para seu próprio benefício. O exemplo canônico, é claro, são as muitas variedades de cães domésticos (raças tão diversas como bulldogs, chihuahuas e dachshunds foram produzidas a partir de lobos em apenas alguns milhares de anos), mas exemplos menos conhecidos incluem o milho cultivado (muito diferente de seus parentes selvagens, nenhum dos quais tem as famosas "espigas" do milho cultivado por humanos), peixes-órfãos (como os cães, criamos variedades que parecem dramaticamente diferentes do tipo selvagem) e vacas leiteiras (com tetas imensas muito maiores do que seriam necessárias apenas para nutrir a prole).

Críticos podem acusar que os criacionistas podem explicar essas coisas sem recorrer à evolução. Por exemplo, os criacionistas frequentemente explicam o desenvolvimento de resistência a agentes antibióticos em bactérias, ou as mudanças provocadas em animais domesticados pela seleção artificial, presumindo que Deus decidiu criar organismos em grupos fixos, chamados "espécies" ou baramin. Embora a microevolução natural ou a seleção artificial guiada pelo homem possam produzir diferentes variedades dentro da "espécie" originalmente criada de "cachorro", ou "vaca", ou "bactéria" (!), nenhuma quantidade de tempo ou mudança genética pode transformar uma "espécie" em outra. No entanto, exatamente como os criacionistas determinam o que é uma "espécie", ou qual mecanismo impede que os seres vivos evoluam além de suas fronteiras, é invariavelmente nunca explicado.

Porém, nas últimas décadas, o avanço contínuo da tecnologia moderna trouxe algo de novo. A evolução está agora produzindo benefícios práticos em um campo muito diferente, e desta vez, os criacionistas não podem alegar que sua explicação se ajusta aos fatos tão bem quanto antes. Este campo é a ciência da computação, e os benefícios provêm de uma estratégia de programação chamada algoritmos genéticos. Este ensaio explicará o que são os algoritmos genéticos e mostrará como eles são relevantes para o debate sobre evolução/criacionismo.

O que é um algoritmo genético?
Topo

Em termos concisos, um algoritmo genético (ou GA, por sigla) é uma técnica de programação que imita a evolução biológica como uma estratégia de resolução de problemas. Dado um problema específico a ser resolvido, a entrada para o GA é um conjunto de soluções potenciais para aquele problema, codificadas de alguma forma, e uma métrica chamada de função de aptidão que permite avaliar quantitativamente cada candidato. Esses candidatos podem ser soluções já conhecidas por funcionarem, com o objetivo do GA sendo melhorá-las, mas mais frequentemente são gerados aleatoriamente.

O GA avalia então cada candidato de acordo com a função de aptidão. Em um conjunto de candidatos gerados aleatoriamente, é claro, a maioria não funcionará de forma alguma, e estes serão eliminados. No entanto, puramente por acaso, alguns podem mostrar promessa - podem exibir atividade, mesmo que apenas fraca e imperfeita, em direção à resolução do problema.

Esses candidatos promissores são mantidos e permitidos para se reproduzir. São feitas múltiplas cópias deles, mas as cópias não são perfeitas; mudanças aleatórias são introduzidas durante o processo de cópia. Esses descendentes digitais então avançam para a próxima geração, formando um novo conjunto de soluções candidatas, e são submetidos a uma segunda rodada de avaliação de aptidão. Aqueles candidatos cujas soluções foram pioradas, ou não melhoradas, pelas alterações em seu código são novamente excluídos; mas, novamente, puramente por acaso, as variações aleatórias introduzidas na população podem ter melhorado alguns indivíduos, transformando-os em soluções melhores, mais completas ou mais eficientes para o problema em questão. Novamente, esses indivíduos vencedores são selecionados e copiados para a próxima geração com mudanças aleatórias, e o processo se repete. A expectativa é que a aptidão média da população aumente a cada rodada, e, portanto, ao repetir este processo por centenas ou milhares de rodadas, podem ser descobertas soluções muito boas para o problema.

Assim surpreendente e contra-intuitivo que possa parecer a alguns, os algoritmos genéticos provaram ser uma estratégia de resolução de problemas enormemente poderosa e bem-sucedida, demonstrando dramaticamente o poder dos princípios evolutivos. Os algoritmos genéticos têm sido utilizados em uma ampla variedade de campos para evoluir soluções para problemas tão difíceis ou mais difíceis do que aqueles enfrentados por designers humanos. Além disso, as soluções que eles produzem são frequentemente mais eficientes, mais elegantes ou mais complexas do que qualquer coisa comparável que um engenheiro humano produziria. Em alguns casos, os algoritmos genéticos chegaram a soluções que confundem os programadores que escreveram os algoritmos no primeiro lugar!

Métodos de representação

Antes de um algoritmo genético poder ser aplicado a qualquer problema, é necessário um método para codificar as soluções potenciais para aquele problema em uma forma que um computador possa processar. Uma abordagem comum é codificar as soluções como strings binárias: sequências de 1's e 0's, onde o dígito em cada posição representa o valor de algum aspecto da solução. Outra abordagem, semelhante, é codificar as soluções como arrays de inteiros ou números decimais, com cada posição novamente representando algum aspecto particular da solução. Essa abordagem permite maior precisão e complexidade do que o método comparativamente restritivo de usar apenas números binários e muitas vezes "é intuitivamente mais próximo do espaço do problema" (Fleming e Purshouse 2002, p. 1228).

Essa técnica foi utilizada, por exemplo, no trabalho de Steffen Schulze-Kremer, que escreveu um algoritmo genético para prever a estrutura tridimensional de uma proteína com base na sequência de aminoácidos que a compõem (Mitchell 1996, p. 62). O AG de Schulze-Kremer utilizou números de valor real para representar os chamados "ângulos de torção" entre as ligações peptídicas que conectam os aminoácidos. (Uma proteína é composta por uma sequência de blocos básicos chamados aminoácidos, que são unidos entre si como os elos de uma corrente. Uma vez que todos os aminoácidos estão ligados, a proteína dobra-se em uma forma tridimensional complexa com base em quais aminoácidos se atraem e quais se repelem entre si. A forma de uma proteína determina sua função.) Algoritmos genéticos para treinar redes neurais frequentemente utilizam também esse método de codificação.

Uma terceira abordagem é representar indivíduos em uma GA como strings de letras, onde cada letra novamente representa um aspecto específico da solução. Um exemplo dessa técnica é a abordagem de "codificação gramatical" de Hiroaki Kitano, onde uma GA foi colocada na tarefa de evoluir um conjunto simples de regras chamado gramática livre de contexto que, por sua vez, foi usada para gerar redes neurais para uma variedade de problemas (Mitchell 1996, p. 74).

A virtude de todos esses três métodos é que eles facilitam a definição de operadores que causam mudanças aleatórias nos candidatos selecionados: inverter um 0 para um 1 ou vice-versa, somar ou subtrair do valor de um número uma quantidade escolhida aleatoriamente, ou substituir uma letra por outra. (Veja a seção sobre Métodos de mudança para mais detalhes sobre os operadores genéticos.) Outra estratégia, desenvolvida principalmente por John Koza da Universidade de Stanford e chamada de programação genética, representa programas como estruturas de dados ramificadas chamadas árvores (Koza et al. 2003, p. 35). Nesta abordagem, mudanças aleatórias podem ser provocadas alterando o operador ou modificando o valor em um nó dado da árvore, ou substituindo uma subárvore por outra.

Genetic Programming Trees

Figura 1: Três árvores de programas simples do tipo normalmente usadas em programação genética. A expressão matemática que cada uma representa é dada abaixo.

É importante notar que os algoritmos evolutivos não precisam representar soluções candidatas como cadeias de dados de comprimento fixo. Alguns o fazem dessa maneira, mas outros não; por exemplo, a codificação gramatical de Kitano, discutida acima, pode ser escalada eficientemente para criar redes neurais grandes e complexas, e as árvores de programação genética de Koza podem crescer arbitrariamente grandes, conforme necessário, para resolver qualquer problema a que sejam aplicadas.

Métodos de seleção

Existem muitas técnicas diferentes que um algoritmo genético pode utilizar para selecionar os indivíduos a serem copiados para a próxima geração, mas listadas abaixo estão algumas das metodologias mais comuns. Alguns desses métodos são mutuamente exclusivos, enquanto outros podem e frequentemente são utilizados em combinação.

Seleção elitista: Os membros mais aptos de cada geração são garantidos para serem selecionados. (A maioria dos AGs não usa elitismo puro, mas sim uma forma modificada onde o melhor indivíduo, ou alguns dos melhores, de cada geração são copiados para a próxima geração, apenas no caso de nada melhor aparecer.)

Seleção proporcional à aptidão: Indivíduos mais aptos têm maior probabilidade, mas não certeza, de serem selecionados.

Seleção por roda da fortuna: Uma forma de seleção proporcional à aptidão na qual a probabilidade de um indivíduo ser selecionado é proporcional à medida em que sua aptidão é maior ou menor em relação à aptidão de seus competidores. (Conceitualmente, isso pode ser representado como um jogo de roleta - cada indivíduo recebe um pedaço da roda, mas os mais aptos recebem pedaços maiores do que os menos aptos. A roda é então girada, e o indivíduo que "possui" a seção em que ela cai a cada vez é escolhido.)

Escalonamento da seleção: À medida que a aptidão média da população aumenta, a intensidade da pressão seletiva também aumenta e a função de aptidão torna-se mais discriminatória. Este método pode ser útil para realizar a melhor seleção posteriormente, quando todos os indivíduos possuem aptidão relativamente alta e apenas pequenas diferenças em aptidão distinguem um do outro.

Seleção por torneio: Subgrupos de indivíduos são escolhidos da população maior, e os membros de cada subgrupo competem entre si. Apenas um indivíduo de cada subgrupo é escolhido para se reproduzir.

Seleção por classificação: Cada indivíduo na população recebe uma classificação numérica com base na aptidão, e a seleção é baseada nesta classificação em vez de diferenças absolutas na aptidão. A vantagem deste método é que ele pode evitar que indivíduos muito aptos ganhem dominância precocemente às custas de outros menos aptos, o que reduziria a diversidade genética da população e poderia dificultar a busca por uma solução aceitável.

Seleção geracional: A prole dos indivíduos selecionados de cada geração torna-se toda a geração seguinte. Nenhum indivíduo é mantido entre as gerações.

Seleção de estado estacionário: Os descendentes dos indivíduos selecionados de cada geração retornam ao pool gênico pré-existente, substituindo alguns dos membros menos aptos da geração anterior. Alguns indivíduos são mantidos entre as gerações.

Seleção hierárquica: Os indivíduos passam por múltiplas rodadas de seleção a cada geração. As avaliações de nível inferior são mais rápidas e menos discriminatórias, enquanto aqueles que sobrevivem até níveis superiores são avaliados com maior rigor. A vantagem deste método é que ele reduz o tempo total de computação ao utilizar avaliações mais rápidas e menos seletivas para eliminar a maioria dos indivíduos que mostram pouco ou nenhum potencial, submetendo apenas aqueles que sobrevivem a este teste inicial a uma avaliação de aptidão mais rigorosa e computacionalmente mais dispendiosa.

Métodos de mudança

Uma vez que a seleção escolheu indivíduos aptos, eles devem ser alterados aleatoriamente na esperança de melhorar sua aptidão para a próxima geração. Existem duas estratégias básicas para realizar isso. A primeira e mais simples é chamada de mutação. Assim como a mutação em seres vivos altera um gene em outro, a mutação em um algoritmo genético causa pequenas alterações em pontos únicos no código de um indivíduo.

O segundo método é chamado de crossover e envolve escolher dois indivíduos para trocar segmentos de seu código, produzindo "filhos" artificiais que são combinações de seus pais. Este processo tem como objetivo simular o processo análogo de recombinação que ocorre nos cromossomos durante a reprodução sexual. Formas comuns de crossover incluem crossover de ponto único, no qual um ponto de troca é definido em uma localização aleatória nos genomas dos dois indivíduos, e um indivíduo contribui com todo o seu código antes desse ponto e o outro contribui com todo o seu código após esse ponto para produzir um filho, e crossover uniforme, no qual o valor em qualquer localização dada no genoma do filho é ou o valor do genoma de um dos pais nessa localização ou o valor do genoma do outro pai nessa localização, escolhido com probabilidade de 50/50.

Crossover
Mutation

Figura 2: Cruzamento e mutação. Os diagramas acima ilustram o efeito de cada um desses operadores genéticos sobre indivíduos em uma população de strings de 8 bits. O diagrama superior mostra dois indivíduos sofrendo cruzamento de ponto único; o ponto de troca é definido entre a quinta e a sexta posições no genoma, produzindo um novo indivíduo que é um híbrido de seus progenitores. O segundo diagrama mostra um indivíduo sofrendo mutação na posição 4, alterando o 0 nessa posição em seu genoma para um 1.

Outras técnicas de resolução de problemas

Com o surgimento da computação de vida artificial e o desenvolvimento de métodos heurísticos, outras técnicas computacionais de resolução de problemas emergiram que, de certa forma, são semelhantes aos algoritmos genéticos. Esta seção explica algumas dessas técnicas, em que aspectos elas se assemelham aos AG e em que aspectos diferem.

  • Redes neurais
    Uma rede neural, ou rede neural para abreviar, é um método de resolução de problemas baseado em um modelo computacional de como os neurônios estão conectados no cérebro. Uma rede neural consiste em camadas de unidades de processamento chamadas nós, unidas por links direcionais: uma camada de entrada, uma camada de saída e zero ou mais camadas ocultas entre elas. Um padrão inicial de entrada é apresentado à camada de entrada da rede neural, e os nós que são estimulados então transmitem um sinal para os nós da próxima camada à qual estão conectados. Se a soma de todas as entradas que entram em um desses neurônios virtuais for maior que o chamado limiar de ativação desse neurônio, esse neurônio se ativa e passa seu próprio sinal para os neurônios da próxima camada. O padrão de ativação, portanto, espalha-se para frente até chegar à camada de saída e é ali retornado como uma solução para a entrada apresentada. Assim como no sistema nervoso de organismos biológicos, as redes neurais aprendem e ajustam seu desempenho ao longo do tempo por meio de rodadas repetidas de ajuste de seus limiares até que a saída real corresponda à saída desejada para qualquer entrada dada. Este processo pode ser supervisionado por um experimente humano ou pode rodar automaticamente usando um algoritmo de aprendizado (Mitchell 1996, p. 52). Algoritmos genéticos têm sido usados tanto para construir quanto para treinar redes neurais.

Uma Rede Neural Simples
Figura 3: Uma rede neural feedforward simples, com uma camada de entrada composta por quatro neurônios, uma camada oculta composta por três neurônios e uma camada de saída composta por quatro neurônios. O número em cada neurônio representa seu limiar de ativação: ele só dispara se receber pelo menos esse número de entradas. O diagrama mostra a rede neural sendo apresentada com uma string de entrada e mostra como a ativação se propaga para frente através da rede para produzir uma saída.

  • Subida de morro
    Semelhante aos algoritmos genéticos, embora mais sistemático e menos aleatório, um algoritmo de subida de morro começa com uma solução inicial para o problema em questão, geralmente escolhida aleatoriamente. A string é então mutada, e se a mutação resultar em maior aptidão para a nova solução do que para a anterior, a nova solução é mantida; caso contrário, a solução atual é retida. O algoritmo é então repetido até que não seja possível encontrar nenhuma mutação que cause um aumento na aptidão da solução atual, e esta solução é retornada como o resultado (Koza et al. 2003, p. 59). (Para entender de onde vem o nome desta técnica, imagine que o espaço de todas as soluções possíveis para um dado problema é representado como um relevo tridimensional. Um conjunto dado de coordenadas nesse relevo representa uma solução particular. Aquelas soluções que são melhores estão em maior altitude, formando morros e picos; aquelas que são piores estão em menor altitude, formando vales. Um "subidor de morro" é então um algoritmo que começa em um ponto dado no relevo e se move inexoravelmente para cima.) A subida de morro é o que se conhece como um algoritmo guloso, significando que ele sempre faz a melhor escolha disponível em cada etapa na esperança de que o melhor resultado geral possa ser alcançado dessa forma. Por contraste, métodos como os algoritmos genéticos e recozimento simulado, discutidos abaixo, não são gulosos; esses métodos às vezes fazem escolhas subótimas na esperança de que levem a melhores soluções posteriormente.

  • Recozimento simulado
    Outra técnica de otimização semelhante aos algoritmos evolutivos é conhecida como recozimento simulado. A ideia emprista seu nome do processo industrial de recozimento no qual um material é aquecido acima de um ponto crítico para amolecê-lo, e então gradualmente resfriado a fim de apagar defeitos em sua estrutura cristalina, produzindo uma arranjo de átomos mais estável e regular (Haupt e Haupt 1998, p. 16). Em recozimento simulado, como nos algoritmos genéticos, há uma função de aptidão que define um relevo de aptidão; no entanto, em vez de uma população de candidatos como nos AGs, há apenas uma solução candidata. O recozimento simulado também adiciona o conceito de "temperatura", uma grandeza numérica global que diminui gradualmente com o tempo. Em cada etapa do algoritmo, a solução sofre mutação (o que é equivalente a mover-se para um ponto adjacente do relevo de aptidão). A aptidão da nova solução é então comparada à aptidão da solução anterior; se for maior, a nova solução é mantida. Caso contrário, o algoritmo toma uma decisão sobre manter ou descartá-la com base na temperatura. Se a temperatura for alta, como é inicialmente, até mesmo mudanças que causam diminuições significativas na aptidão podem ser mantidas e usadas como base para a próxima rodada do algoritmo, mas à medida que a temperatura diminui, o algoritmo torna-se cada vez mais inclinado a aceitar apenas mudanças que aumentam a aptidão. Finalmente, a temperatura atinge zero e o sistema "congela"; qualquer configuração em que esteja naquele ponto torna-se a solução. O recozimento simulado é frequentemente usado para aplicações de projeto de engenharia, como determinar o layout físico de componentes em um chip de computador (Kirkpatrick, Gelatt e Vecchi 1983).

Uma breve história das AG
Topo

Os primeiros exemplos do que hoje poderíamos chamar de algoritmos genéticos apareceram no final dos anos 1950 e início dos anos 1960, programados em computadores por biólogos evolutivos que buscavam explicitamente modelar aspectos da evolução natural. Nenhum deles imaginou que essa estratégia poderia ser mais amplamente aplicável a problemas artificiais, mas esse reconhecimento não tardou a chegar: "A computação evolutiva estava definitivamente no ar nos dias formativos do computador eletrônico" (Mitchell 1996, p.2). Em 1962, pesquisadores como G.E.P. Box, G.J. Friedman, W.W. Bledsoe e H.J. Bremermann haviam desenvolvido independentemente algoritmos inspirados na evolução para otimização de funções e aprendizado de máquina, mas seu trabalho atraiu pouco acompanhamento. Um desenvolvimento mais bem-sucedido nessa área ocorreu em 1965, quando Ingo Rechenberg, então da Universidade Técnica de Berlim, introduziu uma técnica que chamou de estratégia evolutiva, embora fosse mais semelhante a subidas de morro do que a algoritmos genéticos. Nessa técnica, não havia população ou cruzamento; um progenitor era mutado para produzir um descendente, e o melhor dos dois era mantido e tornava-se o progenitor para a próxima rodada de mutação (Haupt e Haupt 1998, p.146). Versões posteriores introduziram a ideia de uma população. As estratégias evolutivas ainda são empregadas hoje por engenheiros e cientistas, especialmente na Alemanha.

O próximo desenvolvimento importante no campo ocorreu em 1966, quando L.J. Fogel, A.J. Owens e M.J. Walsh introduziram nos Estados Unidos uma técnica que chamaram de programação evolutiva. Neste método, soluções candidatas para problemas eram representadas como máquinas de estados finitos simples; como a estratégia evolutiva de Rechenberg, seu algoritmo funcionava por mutação aleatória de uma dessas máquinas simuladas e mantendo a melhor das duas (Mitchell 1996, p.2; Goldberg 1989, p.105). Assim como as estratégias evolutivas, uma formulação mais ampla da técnica de programação evolutiva continua sendo uma área de pesquisa em andamento hoje. No entanto, o que ainda faltava em ambas essas metodologias era o reconhecimento da importância do cruzamento.

Desde 1962, o trabalho de John Holland sobre sistemas adaptativos estabeleceu as bases para desenvolvimentos posteriores; notadamente, Holland foi também o primeiro a propor explicitamente o cruzamento e outros operadores de recombinação. No entanto, o trabalho seminal no campo dos algoritmos genéticos ocorreu em 1975, com a publicação do livro Adaptação em Sistemas Naturais e Artificiais. Baseando-se em pesquisas e artigos anteriores tanto de Holland quanto de colegas da Universidade do Michigan, este livro foi o primeiro a apresentar sistematicamente e rigorosamente o conceito de sistemas digitais adaptativos usando mutação, seleção e cruzamento, simulando processos de evolução biológica, como uma estratégia de resolução de problemas. O livro também tentou colocar os algoritmos genéticos em uma base teórica sólida introduzindo a noção de esquemas (Mitchell 1996, p.3; Haupt e Haupt 1998, p.147). No mesmo ano, a importante dissertação de Kenneth De Jong estabeleceu o potencial dos AGs ao demonstrar que eles poderiam performar bem em uma ampla variedade de funções de teste, incluindo paisagens de busca ruidosas, descontínuas e multimodais (Goldberg 1989, p.107).

Essas obras fundamentais estabeleceram um interesse mais amplo na computação evolutiva. No início ao meio dos anos 1980, os algoritmos genéticos estavam sendo aplicados a uma ampla gama de temas, desde problemas matemáticos abstratos como empacotamento de bin e coloração de grafos até questões de engenharia tangíveis como controle de fluxo em tubulações, reconhecimento e classificação de padrões, e otimização estrutural (Goldberg 1989, p. 128).

Inicialmente, essas aplicações eram principalmente teóricas. No entanto, conforme a pesquisa continuou a se proliferar, os algoritmos genéticos migraram para o setor comercial, com seu crescimento impulsionado pelo crescimento exponencial do poder de computação e pelo desenvolvimento da Internet. Hoje, a computação evolutiva é um campo próspero, e os algoritmos genéticos estão "resolvendo problemas de interesse cotidiano" (Haupt e Haupt 1998, p.147) em áreas de estudo tão diversas quanto previsão de mercado de ações e planejamento de carteiras, engenharia aeroespacial, design de microchips, bioquímica e biologia molecular, e programação em aeroportos e linhas de montagem. O poder da evolução tocou virtualmente qualquer campo que se queira nomear, moldando o mundo ao nosso redor de inúmeras formas invisíveis, e novos usos continuam a ser descobertos conforme a pesquisa prossegue. E no centro de tudo não há nada mais do que a simples e poderosa intuição de Charles Darwin: que a chance aleatória da variação, combinada com a lei da seleção, é uma técnica de resolução de problemas de imenso poder e aplicação quase ilimitada.

Quais são as vantagens das AGs?
Topo
  • O primeiro e mais importante ponto é que os algoritmos genéticos são intrinsecamente paralelos. A maioria dos outros algoritmos é serial e pode explorar apenas o espaço de soluções de um problema em uma direção de cada vez; e se a solução que descobrem se revelar subótima, não há nada a fazer senão abandonar todo o trabalho anteriormente concluído e começar do zero. No entanto, como os AGs têm múltiplos descendentes, eles podem explorar o espaço de soluções em múltiplas direções ao mesmo tempo. Se um caminho se revelar um beco sem saída, eles podem facilmente eliminá-lo e continuar o trabalho em caminhos mais promissores, dando-lhes uma maior chance a cada execução de encontrar a solução ótima.

    No entanto, a vantagem do paralelismo vai além disso. Considere o seguinte: Todas as strings binárias de 8 dígitos (strings de 0s e 1s) formam um espaço de busca, que pode ser representado como ******** (onde o * representa "ou 0 ou 1"). A string 01101010 é um membro desse espaço. No entanto, ela é também um membro do espaço 0*******, do espaço 01******, do espaço 0******0, do espaço 0*1*1*1*, do espaço 01*01**0, e assim por diante. Ao avaliar a aptidão dessa string particular, um algoritmo genético estaria amostrando cada um desses muitos espaços aos quais ela pertence. Ao longo de muitas tais avaliações, ele construiria um valor cada vez mais preciso para a média de aptidão de cada um desses espaços, cada um dos quais tem muitos membros. Portanto, um AG que explicitamente avalia um pequeno número de indivíduos está implicitamente avaliando um grupo muito maior de indivíduos - assim como um pesquisador de opinião que faz perguntas a um certo membro de um grupo étnico, religioso ou social espera aprender algo sobre as opiniões de todos os membros desse grupo e, portanto, pode prever confiavelmente a opinião nacional enquanto amostra apenas uma pequena porcentagem da população. Da mesma forma, o AG pode "focar" no espaço com os indivíduos de maior aptidão e encontrar o melhor geral desse grupo. No contexto de algoritmos evolutivos, isso é conhecido como Teorema do Esquema, e é a "vantagem central" de um AG sobre outros métodos de resolução de problemas (Holland 1992, p. 68; Mitchell 1996, p.28-29; Goldberg 1989, p.20).

  • Devido ao paralelismo que permite avaliar implicitamente muitos esquemas de uma vez, os algoritmos genéticos são particularmente adequados para resolver problemas em que o espaço de todas as soluções potenciais é verdadeiramente enorme — tão vasto que não pode ser pesquisado exaustivamente em qualquer quantidade razoável de tempo. A maioria dos problemas que se enquadram nesta categoria é conhecida como "não linear". Em um problema linear, a aptidão de cada componente é independente, de modo que qualquer melhoria em qualquer parte resultará em uma melhoria do sistema como um todo. Não é preciso dizer que poucos problemas do mundo real são assim. A não linearidade é a norma, onde alterar um componente pode ter efeitos em cascata em todo o sistema, e onde múltiplas alterações que individualmente são prejudiciais podem levar a muito maiores melhorias na aptidão quando combinadas. A não linearidade resulta em uma explosão combinatória: o espaço de cadeias binárias de 1.000 dígitos pode ser pesquisado exaustivamente avaliando apenas 2.000 possibilidades se o problema for linear, enquanto, se for não linear, uma pesquisa exaustiva requer avaliar 21000 possibilidades — um número que levaria mais de 300 dígitos para ser escrito por completo.

    Felizmente, o paralelismo implícito de um AG permite que ele supere mesmo esse enorme número de possibilidades, encontrando com sucesso resultados ótimos ou muito bons em um curto período de tempo após amostrar diretamente apenas pequenas regiões da vasta paisagem de aptidão (Forrest 1993, p. 877). Por exemplo, um algoritmo genético desenvolvido conjuntamente por engenheiros da General Electric e do Instituto Politécnico de Rensselaer produziu um projeto de turbina de motor a jato de alto desempenho que foi três vezes melhor do que uma configuração projetada por humanos e 50% melhor do que uma configuração projetada por um sistema especialista, navegando com sucesso em um espaço de soluções contendo mais de 10387 possibilidades. Métodos convencionais para projetar tais turbinas são parte central de projetos de engenharia que podem levar até cinco anos e custar mais de 2 bilhões de dólares; o algoritmo genético descobriu essa solução após dois dias em uma estação de trabalho de engenharia de desktop típica (Holland 1992, p. 72).

  • Outra notável vantagem dos algoritmos genéticos é que eles funcionam bem em problemas para os quais a paisagem de aptidão é complexa — aqueles em que a função de aptidão é descontínua, ruidosa, muda ao longo do tempo ou possui muitos ótimos locais. A maioria dos problemas práticos possui um vasto espaço de soluções, impossível de ser explorado exaustivamente; o desafio torna-se então como evitar os ótimos locais — soluções que são melhores do que todas as outras semelhantes a elas, mas que não são tão boas quanto outras em diferentes partes do espaço de soluções. Muitos algoritmos de busca podem ficar presos em ótimos locais: se alcançarem o topo de uma colina na paisagem de aptidão, descobrirão que não existem soluções melhores nas proximidades e concluirão que encontraram a melhor, mesmo que picos mais altos existam em outras partes do mapa.

    Os algoritmos evolutivos, por outro lado, provaram ser eficazes na fuga de ótimos locais e na descoberta do ótimo global, mesmo em paisagens de aptidão muito acidentadas e complexas. (Deve-se notar que, na realidade, geralmente não há como saber se uma determinada solução para um problema é o ótimo global ou apenas um ótimo local muito alto. No entanto, mesmo que um AG não entregue sempre uma solução perfeitamente provada para um problema, ele quase sempre consegue fornecer pelo menos uma solução muito boa.) Os quatro componentes principais de um AG — paralelismo, seleção, mutação e cruzamento — trabalham juntos para realizar isso. No início, o AG gera uma população inicial diversa, lançando uma "rede" sobre a paisagem de aptidão. (Koza (2003, p. 506) compara isso a um exército de paraquedistas caindo sobre a paisagem do espaço de busca de um problema, com cada um recebendo ordens para encontrar o pico mais alto.) Pequenas mutações permitem que cada indivíduo explore sua vizinhança imediata, enquanto a seleção foca o progresso, guiando a prole do algoritmo para cima, em direção a partes mais promissoras do espaço de soluções (Holland 1992, p. 68).

    No entanto, o cruzamento é o elemento chave que distingue os algoritmos genéticos de outros métodos, como os escaladores de colinas e o recozimento simulado. Sem o cruzamento, cada solução individual está sozinha, explorando o espaço de busca em sua vizinhança imediata sem referência ao que outros indivíduos podem ter descoberto. Com o cruzamento em vigor, há uma transferência de informação entre candidatos bem-sucedidos — os indivíduos podem se beneficiar do que outros aprenderam, e esquemas podem ser misturados e combinados, com o potencial de produzir uma prole que tenha as forças de ambos os pais e as fraquezas de nenhum. Este ponto é ilustrado em Koza et al. 1999, p. 486, onde os autores discutem um problema de síntese de um filtro passa-baixa usando programação genética. Em uma geração, dois circuitos pais foram selecionados para sofrer cruzamento; um pai tinha boa topologia (componentes como indutores e capacitores nos lugares certos), mas mau dimensionamento (valores de indutância e capacitância para seus componentes muito baixos). O outro pai tinha má topologia, mas bom dimensionamento. O resultado do acasalamento dos dois através do cruzamento foi uma prole com a boa topologia de um pai e o bom dimensionamento do outro, resultando em uma melhoria substancial na aptidão em relação a ambos os pais.

    O problema de encontrar o ótimo global em um espaço com muitos ótimos locais também é conhecido como o dilema da exploração vs. exploração, "um problema clássico para todos os sistemas que podem se adaptar e aprender" (Holland 1992, p. 69). Uma vez que um algoritmo (ou um projetista humano) tenha encontrado uma estratégia de resolução de problemas que parece funcionar satisfatoriamente, ele deve concentrar-se em fazer o melhor uso dessa estratégia ou deve buscar outras? Abandonar uma estratégia comprovada para procurar novas é quase garantido a envolver perdas e degradação de desempenho, pelo menos no curto prazo. Mas se se apegar a uma estratégia particular à exclusão de todas as outras, corre-se o risco de não descobrir estratégias melhores que existem, mas ainda não foram encontradas. Novamente, os algoritmos genéticos mostraram-se muito bons em encontrar esse equilíbrio e descobrir boas soluções com uma quantidade razoável de tempo e esforço computacional.

  • Outra área em que os algoritmos genéticos se destacam é sua capacidade de manipular muitos parâmetros simultaneamente (Forrest 1993, p. 874). Muitos problemas do mundo real não podem ser enunciados em termos de um único valor a ser minimizado ou maximizado, mas devem ser expressos em termos de múltiplos objetivos, geralmente envolvendo compromissos: um só pode ser melhorado às custas de outro. Os AGs são muito bons para resolver tais problemas: em particular, seu uso de paralelismo permite que eles produzam múltiplas soluções igualmente boas para o mesmo problema, possivelmente com uma solução candidata otimizando um parâmetro e outra solução candidata otimizando um diferente (Haupt e Haupt 1998, p.17), e um supervisor humano pode então selecionar um desses candidatos para uso. Se uma solução particular para um problema multiobjetivo otimiza um parâmetro a um grau tal que esse parâmetro não pode ser mais melhorado sem causar uma diminuição correspondente na qualidade de algum outro parâmetro, essa solução é chamada de ótima de Pareto ou não dominada (Coello 2000, p. 112).

  • Finalmente, uma das qualidades dos algoritmos genéticos que, à primeira vista, pode parecer uma desvantagem, revela-se ser uma de suas forças: a saber, os AGs não sabem nada sobre os problemas para os quais são aplicados. Em vez de usar informações específicas do domínio previamente conhecidas para guiar cada passo e realizar alterações com um olhar específico voltado para a melhoria, como fazem os designers humanos, eles são "relógios cegos" (Dawkins 1996); eles realizam alterações aleatórias em suas soluções candidatas e, em seguida, usam a função de aptidão para determinar se essas alterações produzem uma melhoria.

    A virtude dessa técnica é que ela permite que os algoritmos genéticos comecem com uma mente aberta, assim dizer. Como suas decisões são baseadas na aleatoriedade, todos os caminhos de busca possíveis são teoricamente abertos a um AG; em contraste, qualquer estratégia de resolução de problemas que se baseie em conhecimento prévio deve inevitavelmente começar descartando muitos caminhos a priori, portanto, perdendo soluções inovadoras que possam existir lá (Koza et al. 1999, p. 547). Carecendo de preconceitos baseados em crenças estabelecidas de "como as coisas devem ser feitas" ou do que "não poderia funcionar de jeito nenhum", os AGs não têm esse problema. Da mesma forma, qualquer técnica que se baseie em conhecimento prévio entrará em colapso quando tal conhecimento não estiver disponível, mas, novamente, os AGs não são afetados negativamente pela ignorância (Goldberg 1989, p. 23). Através de seus componentes de paralelismo, cruzamento e mutação, eles podem variar amplamente sobre a paisagem de aptidão, explorando regiões que algoritmos produzidos de forma inteligente poderiam ter ignorado e, potencialmente, descobrindo soluções de criatividade surpreendente e inesperada que nunca teriam ocorrido aos designers humanos. Uma ilustração vívida disso é a redescoberta, por meio de programação genética, do conceito de realimentação negativa - um princípio crucial para muitos componentes eletrônicos importantes hoje, mas que, quando foi descoberto pela primeira vez, teve sua patente negada por nove anos porque o conceito era tão contrário às crenças estabelecidas (Koza et al. 2003, p. 413). Os algoritmos evolutivos, é claro, não estão nem cientes nem preocupados se uma solução vai contra crenças estabelecidas - apenas se ela funciona.

Quais são as limitações das AGs?
Topo

Embora os algoritmos genéticos tenham se provado uma estratégia de resolução de problemas eficiente e poderosa, eles não são uma panaceia. Os AGs possuem certas limitações; no entanto, será demonstrado que todas elas podem ser superadas e nenhuma delas afeta a validade da evolução biológica.

  • O primeiro, e mais importante, aspecto a considerar ao criar um algoritmo genético é definir uma representação para o problema. A linguagem usada para especificar soluções candidatas deve ser robusta; ou seja, ela deve ser capaz de tolerar mudanças aleatórias de modo que erros fatais ou nonsensos não resultem consistentemente.

    Existem duas maneiras principais de alcançar isso. A primeira, que é usada pela maioria dos algoritmos genéticos, é definir indivíduos como listas de números - binários, inteiros ou reais - onde cada número representa algum aspecto de uma solução candidata. Se os indivíduos forem strings binárias, 0 ou 1 podem representar a ausência ou presença de um dado traço. Se forem listas de números, esses números podem representar muitas coisas diferentes: os pesos dos links em uma rede neural, a ordem das cidades visitadas em um determinado tour, a colocação espacial de componentes eletrônicos, os valores alimentados em um controlador, os ângulos de torção de ligações peptídicas em uma proteína, e assim por diante. A mutação, neste caso, envolve alterar esses números, inverter bits ou adicionar ou subtrair valores aleatórios. Neste caso, o código do programa real não muda; o código é o que gerencia a simulação e mantém o rastro dos indivíduos, avaliando sua aptidão e, talvez, garantindo que apenas valores realistas e possíveis para o problema dado resultem.

    Em outro método, programação genética, o código do programa real sim muda. Como discutido na seção Métodos de representação, a PG representa indivíduos como árvores de código executáveis que podem ser mutadas alterando ou trocando subárvores. Ambos esses métodos produzem representações que são robustas contra mutação e podem representar muitos tipos diferentes de problemas, e como discutido na seção Alguns exemplos específicos, ambos tiveram considerável sucesso.

    Esta questão de representar soluções candidatas de uma maneira robusta não surge na natureza, porque o método de representação usado pela evolução, a saber, o código genético, é inerentemente robusto: com apenas algumas exceções muito poucas, como uma string de códons de parada, não existe tal coisa como uma sequência de bases de DNA que não possa ser traduzida em uma proteína. Portanto, virtualmente qualquer mudança nas genes de um indivíduo ainda produzirá um resultado inteligível, e assim as mutações na evolução têm uma chance maior de produzir uma melhoria. Isto é em contraste com linguagens criadas por humanos, como o inglês, onde o número de palavras significativas é pequeno comparado ao número total de maneiras de se combinar letras do alfabeto, e, portanto, mudanças aleatórias em uma frase em inglês são prováveis de produzir nonsensos.

  • O problema de como escrever a função de aptidão deve ser cuidadosamente considerado para que uma maior aptidão seja alcançável e realmente corresponda a uma melhor solução para o problema em questão. Se a função de aptidão for escolhida mal ou definida com imprecisão, o algoritmo genético pode ser incapaz de encontrar uma solução para o problema, ou pode acabar resolvendo o problema errado. (Esta última situação é às vezes descrita como a tendência de um AG de "trapacear", embora na realidade o que está acontecendo é que o AG está fazendo o que lhe foi ordenado fazer, e não o que seus criadores pretendiam que ele fizesse.) Um exemplo disso pode ser encontrado em Graham-Rowe 2002, no qual pesquisadores usaram um algoritmo evolutivo em conjunto com um array de hardware reprogramável, configurando a função de aptidão para recompensar o circuito em evolução por produzir um sinal oscilante. No final do experimento, um sinal oscilante estava de fato sendo produzido - mas, em vez do próprio circuito atuar como um oscilador, como os pesquisadores pretendiam, descobriram que ele havia se tornado um receptor de rádio que estava captando e retransmitindo um sinal oscilante de um equipamento eletrônico próximo!

    Este não é um problema na natureza, no entanto. No laboratório da evolução biológica, existe apenas uma função de aptidão, que é a mesma para todos os seres vivos - o impulso de sobreviver e se reproduzir, não importa quais adaptações tornem isso possível. Aquelas organismos que se reproduzem com mais abundância em comparação com seus competidores são mais aptos; aqueles que falham em se reproduzir são inadequados.

  • Além de fazer uma boa escolha da função de aptidão, os outros parâmetros de um GA — o tamanho da população, a taxa de mutação e cruzamento, o tipo e a força da seleção — também devem ser escolhidos com cuidado. Se o tamanho da população for muito pequeno, o algoritmo genético pode não explorar o espaço de soluções o suficiente para encontrar consistentemente boas soluções. Se a taxa de mudança genética for muito alta ou o esquema de seleção for escolhido mal, esquemas benéficos podem ser interrompidos e a população pode entrar em catástrofe de erro, mudando tão rápido que a seleção nunca consiga trazer convergência.

    Os seres vivos de fato enfrentam dificuldades semelhantes, e a evolução lidou com elas. É verdade que se o tamanho da população cair muito baixo, as taxas de mutação forem muito altas, ou a pressão de seleção for muito forte (tal situação pode ser causada por mudanças ambientais drásticas), então a espécie pode se extinguir. A solução tem sido "a evolução da evolvibilidade" — adaptações que alteram a capacidade de uma espécie de se adaptar. Por exemplo, a maioria dos seres vivos evoluiu maquinário molecular elaborado que verifica e corrige erros durante o processo de replicação do DNA, mantendo sua taxa de mutação em níveis aceitavelmente baixos; inversamente, em tempos de estresse ambiental severo, algumas espécies bacterianas entram em um estado de hipermutação onde a taxa de erros de replicação do DNA aumenta acentuadamente, aumentando a chance de que uma mutação compensatória seja descoberta. Claro, nem todas as catástrofes podem ser evitadas, mas a enorme diversidade e as adaptações altamente complexas dos seres vivos hoje mostram que, em geral, a evolução é uma estratégia bem-sucedida. Da mesma forma, as diversas aplicações e os resultados impressionantes produzidos por algoritmos genéticos mostram que eles são um campo de estudo poderoso e digno.

  • Um tipo de problema com o qual os algoritmos genéticos têm dificuldade é lidar com problemas de funções de aptidão "enganosas" (Mitchell 1996, p.125), aquelas em que as localizações de pontos melhorados fornecem informações enganosas sobre onde é provável que o ótimo global seja encontrado. Por exemplo, imagine um problema em que o espaço de busca consistisse em todas as cadeias binárias de oito caracteres, e a aptidão de um indivíduo fosse diretamente proporcional ao número de 1s nele - ou seja, 00000001 seria menos apto que 00000011, que seria menos apto que 00000111, e assim por diante - com duas exceções: a cadeia 11111111 acabou por ter aptidão muito baixa, e a cadeia 00000000 acabou por ter aptidão muito alta. Em um problema como esse, um AG (assim como a maioria dos outros algoritmos) não seria mais propenso a encontrar o ótimo global do que uma busca aleatória.

    A resolução para este problema é a mesma tanto para algoritmos genéticos quanto para a evolução biológica: a evolução não é um processo que precisa encontrar o único ótimo global toda vez. Ela pode fazer quase tão bem ao alcançar o topo de um ótimo local alto, e para a maioria das situações, isso será suficiente, mesmo que o ótimo global não possa ser facilmente alcançado a partir desse ponto. A evolução é muito mais um "satisfizer" - um algoritmo que entrega uma solução "suficientemente boa", embora não necessariamente a melhor solução possível, dado um tempo e esforço razoáveis investidos na busca. O FAQ Evidence for Jury-Rigged Design in Nature fornece exemplos desse resultado muito aparecendo na natureza. (Também vale notar que poucos, se houver, problemas do mundo real são tão enganosos quanto o exemplo um pouco artificial dado acima. Geralmente, a localização de melhorias locais fornece pelo menos alguma informação sobre a localização do ótimo global.)

  • Um problema bem conhecido que pode ocorrer com uma GA é conhecido como convergência prematura. Se um indivíduo que é mais apto do que a maioria de seus competidores emerge cedo no curso da execução, ele pode se reproduzir tão abundantemente que reduz a diversidade da população muito cedo, levando o algoritmo a convergir para o ótimo local que aquele indivíduo representa, em vez de pesquisar a paisagem de aptidão o suficiente para encontrar o ótimo global (Forrest 1993, p. 876; Mitchell 1996, p. 167). Este é um problema especialmente comum em populações pequenas, onde até variações de chance na taxa de reprodução podem fazer com que um genótipo se torne dominante sobre os outros.

    Os métodos mais comuns implementados por pesquisadores de GA para lidar com este problema envolvem todos o controle da força da seleção, a fim de não dar a indivíduos excessivamente aptos uma vantagem excessiva. Seleção por classificação, escalonamento e torneio, discutidos anteriormente, são três meios principais para realizar isso; alguns métodos de escalonamento da seleção incluem escalonamento sigma, no qual a reprodução é baseada em uma comparação estatística com a aptidão média da população, e seleção de Boltzmann, na qual a força da seleção aumenta ao longo do curso de uma execução de uma maneira semelhante à variável "temperatura" no recozimento simulado (Mitchell 1996, p. 168).

    A convergência prematura ocorre na natureza (onde é chamada de deriva genética pelos biólogos). Isso não deve ser surpreendente; como discutido acima, a evolução como estratégia de resolução de problemas não tem obrigação de encontrar a única melhor solução, meramente uma que seja boa o suficiente. No entanto, a convergência prematura na natureza é menos comum, já que a maioria das mutações benéficas em seres vivos produz apenas pequenos melhoramentos incrementais de aptidão; mutações que produzem um ganho tão grande de aptidão a ponto de dar aos seus detentores uma vantagem reprodutiva dramática são raras.

  • Finalmente, vários pesquisadores (Holland 1992, p.72; Forrest 1993, p.875; Haupt e Haupt 1998, p.18) aconselham contra o uso de algoritmos genéticos em problemas analiticamente solúveis. Não é que os algoritmos genéticos não possam encontrar boas soluções para tais problemas; é apenas que os métodos analíticos tradicionais levam muito menos tempo e esforço computacional do que os AG e, ao contrário dos AG, são matematicamente garantidos para entregar a única solução exata. Claro, já que não existe tal coisa como uma solução matematicamente perfeita para qualquer problema de adaptação biológica, essa questão não surge na natureza.

Alguns exemplos específicos de AGs
Topo

À medida que o poder da evolução ganha reconhecimento cada vez mais generalizado, algoritmos genéticos têm sido utilizados para enfrentar uma ampla variedade de problemas em uma gama extremamente diversa de campos, demonstrando claramente seu poder e seu potencial. Esta seção discutirá alguns dos usos mais notáveis aos quais eles têm sido aplicados.

  • Acústica
    Sato et al. 2002 utilizaram algoritmos genéticos para projetar uma sala de concerto com propriedades acústicas ótimas, maximizando a qualidade sonora para o público, para o maestro e para os músicos no palco. Esta tarefa envolve a otimização simultânea de múltiplas variáveis. Começando com uma sala em formato de caixa de sapatos, o GA dos autores produziu duas soluções não dominadas, ambas descritas como "em forma de folha" (p.526). Os autores afirmam que essas soluções possuem proporções semelhantes à do Grosser Musikvereinsaal de Viena, que é amplamente considerado um dos melhores – se não o melhor – salões de concerto do mundo em termos de propriedades acústicas.

    Porto, Fogel e Fogel 1995 utilizaram programação evolutiva para treinar redes neurais a distinguir entre reflexões de sonar de diferentes tipos de objetos: esferas metálicas artificiais, montes submarinos, peixes e vida vegetal, e ruído de fundo aleatório. Após 500 gerações, a melhor rede neural evoluída apresentou uma probabilidade de classificação correta variando entre 94% e 98% e uma probabilidade de classificação incorreta entre 7,4% e 1,5%, o que são "probabilidades razoáveis de detecção e alarme falso" (p.21). A rede evoluída igualou o desempenho de outra rede desenvolvida por recozimento simulado e consistentemente superou redes treinadas por retropropagação, que "repetidamente travavam em conjuntos de pesos subótimos que não produziam resultados satisfatórios" (p.21). Em contraste, ambos os métodos estocásticos mostraram-se capazes de superar esses ótimos locais e produzir redes menores, eficazes e mais robustas; no entanto, os autores sugerem que o algoritmo evolutivo, ao contrário do recozimento simulado, opera sobre uma população e, portanto, aproveita informações globais sobre o espaço de busca, potencialmente levando a um melhor desempenho a longo prazo.

    Tang et al. 1996 revisam os usos de algoritmos genéticos no campo da acústica e processamento de sinais. Uma área de particular interesse envolve o uso de GAs para projetar sistemas de Controle Ativo de Ruído (ANC), que cancelam o som indesejado produzindo ondas sonoras que interferem destrutivamente com o ruído indesejado. Este é um problema de múltiplos objetivos que requer a colocação precisa e o controle de múltiplos alto-falantes; GAs têm sido utilizados tanto para projetar os controladores quanto para encontrar a colocação ótima dos alto-falantes para tais sistemas, resultando na "atenuação eficaz do ruído" (p.33) em testes experimentais.

  • Engenharia aeroespacial
    Obayashi et al. 2000 used a multiple-objective genetic algorithm to design the wing shape for a supersonic aircraft. Three major considerations govern the wing's configuration - minimizing aerodynamic drag at supersonic cruising speeds, minimizing drag at subsonic speeds, and minimizing aerodynamic load (the bending force on the wing). These objectives are mutually exclusive, and optimizing them all simultaneously requires tradeoffs to be made.

    The chromosome in this problem is a string of 66 real-valued numbers, each of which corresponds to a specific aspect of the wing: its shape, its thickness, its twist, and so on. Evolution with elitist rank selection was simulated for 70 generations, with a population size of 64 individuals. At the termination of this process, there were several Pareto-optimal individuals, each one representing a single non-dominated solution to the problem. The paper notes that these best-of-run individuals have "physically reasonable" characteristics, indicating the validity of the optimization technique (p.186). To further evaluate the quality of the solutions, six of the best were compared to a supersonic wing design produced by the SST Design Team of Japan's National Aerospace Laboratory. All six were competitive, having drag and load values approximately equal to or less than the human-designed wing; one of the evolved solutions in particular outperformed the NAL's design in all three objectives. The authors note that the GA's solutions are similar to a design called the "arrow wing" which was first suggested in the late 1950s, but ultimately abandoned in favor of the more conventional delta-wing design.

    In a follow-up paper (Sasaki et al. 2001), the authors repeat their experiment while adding a quarto objective, namely minimizing the twisting moment of the wing (a known potential problem for arrow-wing SST designs). Additional control points for thickness are also added to the array of design variables. After 75 generations of evolution, two of the best Pareto-optimal solutions were again compared to the Japanese National Aerospace Laboratory's wing design for the NEXST-1 experimental supersonic airplane. It was found that both of these designs (as well as one optimal design from the previous simulation, discussed above) were physically reasonable and superior to the NAL's design in all four objectives.

    Williams, Crossley e Lang 2001 applied genetic algorithms to the task of spacing satellite orbits to minimize coverage blackouts. As telecommunications technology continues to improve, humans are increasingly dependent on Earth-orbiting satellites to perform many vital functions, and one of the problems engineers face is designing their orbital trajectories. Satellites in high Earth orbit, around 22,000 miles up, can see large sections of the planet at once and be in constant contact with ground stations, but these are far more expensive to launch and more vulnerable to cosmic radiation. It is more economical to put satellites in low orbits, as low as a few hundred miles in some cases, but because of the curvature of the Earth it is inevitable that these satellites will at times lose line-of-sight access to surface receivers and thus be useless. Even constellations of several satellites experience unavoidable blackouts and losses of coverage for this reason. The challenge is to arrange the satellites' orbits to minimize this downtime. This is a multi-objective problem, involving the minimization of both the average blackout time for all locations and the maximum blackout time for any one location; in practice, these goals turn out to be mutually exclusive.

    When the GA was applied to this problem, the evolved results for three, four and five-satellite constellations were unusual, highly asymmetric orbit configurations, with the satellites spaced by alternating large and small gaps rather than equal-sized gaps as conventional techniques would produce. However, this solution significantly reduced both average and maximum revisit times, in some cases by up to 90 minutes. In a news article about the results, Dr. William Crossley noted that "engineers with years of aerospace experience were surprised by the higher performance offered by the unconventional design".

    Keane e Brown 1996 utilizaram uma GA para evoluir um novo design para uma treliça ou braço de sustentação de carga que pudesse ser montado em órbita e utilizado para satélites, estações espaciais e outros projetos de construção aeroespacial. O resultado, uma estrutura torcida e com aparência orgânica que tem sido comparada a um osso da perna humana, utiliza não mais material do que o design de treliça padrão, mas é leve, forte e muito superior na amortização de vibrações danosas, conforme confirmado por testes no mundo real do produto final. E ainda "Nenhuma inteligência fez os designs. Eles apenas evoluíram" (Petit 1998). Os autores do artigo além disso observam que sua GA rodou apenas por 10 gerações devido à natureza computacionalmente intensiva da simulação, e a população não havia se tornado estagnada. Continuar a execução por mais gerações sem dúvida teria produzido melhorias adicionais no desempenho. Uma Treliça Otimizada Geneticamente
    Figura 4: Uma treliça tridimensional otimizada geneticamente com resposta de frequência melhorada. (Adaptado de [1].)


    Finally, as reported in Gibbs 1996, Lockheed Martin has used a genetic algorithm to evolve a series of maneuvers to shift a spacecraft from one orientation to another within 2% of the theoretical minimum time for such maneuvers. The evolved solution was 10% faster than a solution hand-crafted by an expert for the same problem.

  • Astronomia e astrofísica
    Charbonneau 1995 sugere a utilidade de Algoritmos Genéticos (AGs) para problemas em astrofísica ao aplicá-los a três exemplos de problemas: ajustar a curva de rotação de uma galáxia com base nas velocidades rotacionais observadas de seus componentes, determinar o período de pulsação de uma estrela variável com base em dados de séries temporais e resolver os parâmetros críticos em um modelo magnetohidrodinâmico do vento solar. Todos esses são problemas não lineares multidimensionais difíceis.

    O algoritmo genético de Charbonneau, PIKAIA, utiliza seleção por classificação proporcional à aptidão por gerações, acoplada com elitismo, garantindo que o único melhor indivíduo seja copiado uma vez para a próxima geração sem modificação. O PIKAIA tem uma taxa de cruzamento de 0,65 e uma taxa de mutação variável que é definida inicialmente em 0,003 e aumenta gradualmente posteriormente, à medida que a população se aproxima da convergência, para manter a variabilidade no pool gênico.

    No problema da curva de rotação galáctica, o AG produziu duas curvas, ambas com ajustes muito bons aos dados (um resultado comum neste tipo de problema, em que há pouco contraste entre as cristas vizinhas); observações adicionais podem então distinguir qual delas deve ser preferida. No problema de séries temporais, o AG foi impressionantemente bem-sucedido ao gerar autonomamente um ajuste de alta qualidade para os dados, mas problemas mais difíceis não foram ajustados tão bem (embora, Charbonneau aponte, esses problemas sejam igualmente difíceis de resolver com técnicas convencionais). O artigo sugere que um AG híbrido que empregue tanto evolução artificial quanto técnicas analíticas padrão pode ter um desempenho melhor. Finalmente, ao resolver os seis parâmetros críticos do vento solar, o AG determinou com sucesso o valor de três deles com uma precisão de até 0,1% e os três restantes com precisões de até 1 a 10%. (Embora um erro experimental menor para esses três sempre fosse preferível, Charbonneau observa que não existem outros métodos robustos e eficientes para resolver experimentalmente um problema não linear de seis dimensões deste tipo; um método de gradiente conjugado funciona "desde que uma muito boa estimativa inicial possa ser fornecida" (p.323). Em contraste, os AGs não requerem tal conhecimento específico do domínio finamente ajustado.)

    Com base nos resultados obtidos até agora, Charbonneau sugere que os AGs podem e devem encontrar uso em outros problemas difíceis em astrofísica, em particular problemas inversos como imageamento Doppler e inversões heliosísmicas. Ao encerrar, Charbonneau argumenta que os AGs são um "forte e promissor concorrente" (p.324) neste campo, um que pode ser esperado para complementar, em vez de substituir, técnicas tradicionais de otimização, e conclui que "a linha de fundo, se houver uma, é que os algoritmos genéticos funcionam, e muitas vezes de forma assustadoramente bem" (p.325).

  • Química
    Pulsos de alta potência e ultracurtos de energia laser podem separar moléculas complexas em moléculas mais simples, um processo com importantes aplicações na química orgânica e na microeletrônica. Os produtos finais específicos de tal reação podem ser controlados modulando a fase do pulso laser. No entanto, para moléculas grandes, resolver analiticamente a forma de pulso desejada é demasiado difícil: os cálculos são demasiado complexos e as características relevantes (as superfícies de energia potencial das moléculas) não são conhecidas com precisão suficiente.

    Assion et al. 1998 resolveram este problema utilizando um algoritmo evolutivo para projetar a forma do pulso. Em vez de inserir conhecimento complexo e específico do problema sobre as características quânticas das moléculas de entrada para projetar o pulso conforme as especificações, o AE (algoritmo evolutivo) dispara um pulso, mede as proporções das moléculas de produto resultantes, muta aleatoriamente as características do feixe na esperança de obter essas proporções mais próximas da saída desejada e o processo repete-se. (Em vez de ajustar finamente qualquer característica do feixe de laser diretamente, o GA dos autores representa os indivíduos como um conjunto de 128 números, cada um dos quais é um valor de tensão que controla o índice de refração de um dos pixels no modulador de luz laser. Novamente, não é necessário nenhum conhecimento específico do problema sobre as propriedades do laser ou dos produtos da reação.) Os autores afirmam que o seu algoritmo, quando aplicado a duas substâncias de amostra, "encontra automaticamente a melhor configuração... não importa quão complicada possa ser a resposta molecular" (p.920), demonstrando "controle coerente automatizado em produtos que são quimicamente diferentes entre si e da molécula progenitora" (p.921).

    No início ao meio dos anos 1990, a ampla adoção de uma técnica inovadora de design de fármacos chamada química combinatória revolucionou a indústria farmacêutica. Neste método, em vez da síntese penosa e precisa de um único composto de cada vez, os bioquímicos misturam deliberadamente uma grande variedade de reagentes para produzir uma variedade ainda maior de produtos - centenas, milhares ou milhões de compostos diferentes por lote - que podem então ser rapidamente triados para atividade bioquímica. Ao projetar bibliotecas de reagentes para esta técnica, existem duas abordagens principais: design baseado em reagentes, que escolhe grupos otimizados de reagentes sem considerar quais produtos resultarão, e design baseado em produtos, que seleciona reagentes mais propensos a produzir produtos com as propriedades desejadas. O design baseado em produtos é mais difícil e complexo, mas mostrou-se resultar em bibliotecas combinatórias melhores e mais diversas e uma maior probabilidade de obter um resultado utilizável.

    Num artigo financiado pelo departamento de pesquisa e desenvolvimento da GlaxoSmithKline, Gillet 2002 discute o uso de um algoritmo genético multiobjetivo para o design baseado em produtos de bibliotecas combinatórias. Ao escolher os compostos que entram numa biblioteca particular, devem ser consideradas qualidades como diversidade molecular e peso, custo dos suprimentos, toxicidade, absorção, distribuição e metabolismo. Se o objetivo for encontrar moléculas semelhantes a uma molécula existente de função conhecida (um método comum de design de novos fármacos), a similaridade estrutural também pode ser tida em conta. Este artigo apresenta uma abordagem multiobjetivo onde pode ser desenvolvido um conjunto de resultados Pareto-ótimos que maximizam ou minimizam cada um destes objetivos. O autor conclui que o GA foi capaz de satisfazer simultaneamente os critérios de diversidade molecular e máxima eficiência sintética, e foi capaz de encontrar moléculas que eram semelhantes a fármacos bem como "muito semelhantes a moléculas-alvo dadas após explorar uma fração muito pequena do espaço total de busca" (p.378).

    Num artigo relacionado, Glen e Payne 1995 discutem o uso de algoritmos genéticos para projetar automaticamente novas moléculas do zero para se adequar a um conjunto dado de especificações. Dada uma população inicial gerada aleatoriamente ou usando a molécula simples etano como semente, o GA adiciona, remove e altera aleatoriamente átomos e fragmentos moleculares com o objetivo de gerar moléculas que se adequam às restrições dadas. O GA pode otimizar simultaneamente um grande número de objetivos, incluindo peso molecular, volume molecular, número de ligações, número de centros quirais, número de átomos, número de ligações rotacionáveis, polarizabilidade, momento dipolar e mais, a fim de produzir moléculas candidatas com as propriedades desejadas. Com base em testes experimentais, incluindo um problema de otimização difícil que envolvia gerar moléculas com propriedades semelhantes à ribose (um composto de açúcar frequentemente mimetizado em fármacos antivirais), os autores concluem que o GA é um "excelente gerador de ideias" (p.199) que oferece "propriedades de otimização rápidas e poderosas" e pode gerar "um conjunto diverso de estruturas possíveis" (p.182). Eles prosseguem afirmando: "De particular nota é a poderosa capacidade de otimização do algoritmo genético, mesmo com tamanhos de população relativamente pequenos" (p.200). Num sinal de que estes resultados não são meramente teóricos, Lemley 2001 relata que a corporação Unilever utilizou algoritmos genéticos para projetar novos compostos antimicrobianos para uso em limpadores, que patenteou.

  • Engenharia elétrica
    Um array de portas programáveis por campo, ou FPGA, por sigla, é um tipo especial de placa de circuito com um array de células lógicas, cada uma das quais pode atuar como qualquer tipo de porta lógica, conectadas por interligações flexíveis que podem conectar células. Ambas essas funções são controladas por software, de modo que, simplesmente carregando um programa especial na placa, ela pode ser alterada em tempo real para realizar as funções de qualquer um de uma vasta variedade de dispositivos de hardware.

    O Dr. Adrian Thompson explorou este dispositivo, em conjunto com os princípios da evolução, para produzir um circuito protótipo de reconhecimento de voz que pode distinguir entre e responder a comandos falados usando apenas 37 portas lógicas – uma tarefa que teria sido considerada impossível para qualquer engenheiro humano. Ele gerou strings de bits aleatórios de 0s e 1s e usou-os como configurações para o FPGA, selecionando os indivíduos mais aptos de cada geração, reproduzindo e mutando-os aleatoriamente, trocando seções de seu código e passando-os para outra rodada de seleção. Seu objetivo era evoluir um dispositivo que, inicialmente, pudesse discriminar entre tons de frequências diferentes (1 e 10 quilohertz), e depois distinguir entre as palavras faladas "go" (vá) e "stop" (pare).

    Este objetivo foi alcançado dentro de 3000 gerações, mas o sucesso foi ainda maior do que havia sido antecipado. O sistema evoluído usa muito menos células do que qualquer engenheiro humano poderia ter projetado, e ele nem mesmo precisa do componente mais crítico dos sistemas construídos por humanos – um relógio. Como funciona? Thompson não tem ideia, embora ele tenha rastreado o sinal de entrada através de um arranjo complexo de loops de realimentação dentro do circuito evoluído. De fato, dos 37 portões lógicos que o produto final usa, cinco deles nem sequer estão conectados ao resto do circuito de qualquer forma – ainda que, se sua fonte de energia for removida, o circuito pare de funcionar. Parece que a evolução explorou algum efeito eletromagnético sutil dessas células para chegar à sua solução, mas o funcionamento exato da estrutura evoluída complexa e intrincada permanece um mistério (Davidson 1997).

    Altshuler e Linden 1997 usaram um algoritmo genético para evoluir antenas de fio com propriedades pré-especificadas. Os autores observam que o projeto de tais antenas é um processo impreciso, começando com as propriedades desejadas e depois determinando a forma da antena através de "palpites... intuição, experiência, equações aproximadas ou estudos empíricos" (p.50). Esta técnica é demorada, frequentemente não produz resultados ótimos e tende a funcionar bem apenas para projetos relativamente simples e simétricos. Em contraste, na abordagem do algoritmo genético, o engenheiro especifica as propriedades eletromagnéticas da antena, e o AG sintetiza automaticamente uma configuração correspondente.

    A Crooked-Wire Genetic Antenna
    Figura 5: Uma antena genética de fio torto
    (após Altshuler e Linden 1997, figura 1).    		 Altshuler e Linden usaram seu AG para projetar uma antena de sete segmentos com polarização circular e cobertura hemisférica; o resultado é mostrado à esquerda. Cada indivíduo no AG consistia em um cromossomo binário especificando as coordenadas tridimensionais de cada extremidade de cada fio. A aptidão foi avaliada simulando cada candidato de acordo com um código de fiação eletromagnética, e o indivíduo melhor da corrida foi então construído e testado. Os autores descrevem a forma desta antena, que não se assemelha a antenas tradicionais e não tem simetria óbvia, como "inusitadamente estranha" e "contraintuitiva" (p.52), mas ela tinha um padrão de radiação quase uniforme com alta largura de banda tanto na simulação quanto nos testes experimentais, correspondendo excelentemente à especificação anterior. Os autores concluem que um método baseado em algoritmo genético para projeto de antenas mostra "promessa notável". "...este novo procedimento de projeto é capaz de encontrar antenas genéticas capazes de resolver efetivamente problemas difíceis de antena, e será particularmente útil em situações onde os projetos existentes não são adequados" (p.52).
  • Mercados financeiros
    Mahfoud e Mani 1996 utilizaram um algoritmo genético para prever o desempenho futuro de 1600 ações negociadas publicamente. Especificamente, o AG foi encarregado de prever o retorno relativo de cada ação, definido como o retorno da ação menos a média de retorno de todas as 1600 ações ao longo do período de tempo em questão, 12 semanas (um trimestre calendário) no futuro. Como entrada, o AG recebeu dados históricos sobre cada ação na forma de uma lista de 15 atributos, como razão preço-lucro e taxa de crescimento, medidos em vários pontos no passado; o AG foi solicitado a evoluir um conjunto de regras se/para classificar cada ação e a fornecer, como saída, tanto uma recomendação sobre o que fazer em relação a essa ação (comprar, vender ou nenhuma previsão) quanto uma previsão numérica do retorno relativo. Os resultados do AG foram comparados aos de um sistema estabelecido baseado em redes neurais que os autores estavam utilizando para prever preços de ações e gerenciar carteiras há três anos anteriormente. É claro que o mercado de ações é um sistema extremamente ruidoso e não linear, e nenhum mecanismo preditivo pode estar correto 100% do tempo; o desafio é encontrar um preditor que seja preciso mais frequentemente do que não.

    No experimento, o AG e a rede neural fizeram previsões no final de cada semana para cada uma das 1600 ações, por doze semanas consecutivas. Doze semanas após cada previsão, o desempenho real foi comparado com o retorno relativo previsto. No geral, o AG superou significativamente a rede neural: em uma execução de teste, o AG previu corretamente a direção de uma ação 47,6% das vezes, não fez nenhuma previsão 45,8% das vezes e fez uma previsão incorreta apenas 6,6% das vezes, resultando em uma precisão preditiva geral de 87,8%. Embora a rede neural fizesse previsões definitivas com mais frequência, também estava errada em suas previsões com mais frequência (de fato, os autores especulam que a maior capacidade do AG de não fazer uma previsão quando os dados eram incertos foi um fator em seu sucesso; a rede neural sempre produz uma previsão a menos que seja explicitamente restringida pelo programador). No experimento de 1600 ações, o AG produziu um retorno relativo de +5,47%, versus +4,40% para a rede neural - uma diferença estatisticamente significativa. De fato, o AG também superou significativamente três principais índices de mercado de ações - o S&P 500, o S&P 400 e o Russell 2000 - durante este período; a chance foi excluída como causa deste resultado no nível de confiança de 95%. Os autores atribuem este sucesso convincente à capacidade do algoritmo genético de aprender relações não lineares não facilmente aparentes para observadores humanos, bem como ao fato de que ele carece do "viés a priori de um especialista humano contra regras contra-intuitivas ou contrárias" (p.562).

    Sucesso similar foi alcançado por Andreou, Georgopoulos e Likothanassis 2002, que utilizaram algoritmos genéticos híbridos para evoluir redes neurais que previam as taxas de câmbio de moedas estrangeiras até um mês à frente. Em oposição ao último exemplo, onde AGs e redes neurais estavam em competição, aqui os dois trabalharam em conjunto, com o AG evoluindo a arquitetura (número de unidades de entrada, número de unidades ocultas e o arranjo dos links entre elas) da rede que foi então treinada por um algoritmo de filtro.

    Como informação histórica, o algoritmo recebeu 1300 valores brutos diários anteriores de cinco moedas - o dólar americano, a marca alemã, o franco francês, a libra britânica e a dracma grega - e foi solicitado a prever seus valores futuros 1, 2, 5 e 20 dias à frente. O desempenho do AG híbrido, em geral, mostrou um "nível notável de precisão" (p.200) em todos os casos testados, superando vários outros métodos incluindo redes neurais sozinhas. As correlações para o caso de um dia variaram de 92 a 99%, e embora a precisão diminuisse com intervalos de tempo cada vez maiores, o AG continuou a ser "bastante bem-sucedido" (p.206) e claramente superou os outros métodos. Os autores concluem que "um notável sucesso preditivo foi alcançado tanto em um horizonte de previsão de um passo quanto em um horizonte multistep" (p.208) - de fato, eles afirmam que seus resultados são muito melhores do que qualquer estratégia preditiva relacionada tentada nesta série de dados ou outras moedas.

    Os usos de AGs nos mercados financeiros começaram a se espalhar para firmas de corretagem do mundo real. Naik 1996 relata que a LBS Capital Management, uma firma americana sediada na Flórida, utiliza algoritmos genéticos para escolher ações para um fundo de pensão que gerencia. Coale 1997 e Begley e Beals 1995 relatam que a First Quadrant, uma firma de investimentos na Califórnia que gerencia mais de $2,2 bilhões, utiliza AGs para tomar decisões de investimento para todos os seus serviços financeiros. Seu modelo evoluído ganha, em média, $255 para cada $100 investidos ao longo de seis anos, em oposição a $205 para outros tipos de sistemas de modelagem.

  • Jogar jogos
    One of the most novel and compelling demonstrations of the power of genetic algorithms was presented by Chellapilla e Fogel 2001, who used a GA to evolve neural networks that could play the game of checkers. The authors state that one of the major difficulties in these sorts of strategy-related problems is the problema de atribuição de crédito - in other words, how does one write a fitness function? It has been widely believed that the mere criterion of win, lose or draw does not provide sufficient information for an evolutionary algorithm to figure out what constitutes good play.

    In this paper, Chellapilla and Fogel overturn that assumption. Given only the spatial positions of pieces on the checkerboard and the total number of pieces possessed by each side, they were able to evolve a checkers program that plays at a level competitive with human experts, without any intelligent input as to what constitutes good play - indeed, the individuals in the evolutionary algorithm were not even told what the criteria for a win were, nor were they told the result of any one game.

    In Chellapilla and Fogel's representation, the game state was represented by a numeric list of 32 elements, with each position in the list corresponding to an available position on the board. The value at each position was either 0 for an unoccupied square, -1 if that square was occupied by an enemy checker, +1 if that square was occupied by one of the program's checkers, and -K or +K for a square occupied by an enemy or friendly king. (The value of K was not pre-specified, but again was determined by evolution over the course of the algorithm.) Accompanying this was a neural network with multiple processing layers and one input layer with a node for each of the possible 4x4, 5x5, 6x6, 7x7 and 8x8 squares on the board. The output of the neural net for any given arrangement of pieces was a value from -1 to +1 indicating how good it felt that position was for it. For each move, the neural network was presented with a game tree listing all possible moves up to four turns into the future, and a move decision was made based on which branch of the tree produced the best results for it.

    The evolutionary algorithm began with a population of 15 neural networks with randomly generated weights and biases assigned to each node and link; each individual then reproduced once, generating an offspring with variations in the values of the network. These 30 individuals then competed for survival by playing against each other, with each individual competing against 5 randomly chosen opponents per turn. 1 point was awarded for each win and 2 points were deducted for each loss. The 15 best performers, based on total score, were selected to produce offspring for the next generation, and the process repeated. Evolution was continued for 840 generations (approximately six months of computer time).

    Classe Classificação
    Senior Master 2400+
    Master 2200-2399
    Expert 2000-2199
    Class A 1800-1999
    Class B 1600-1799
    Class C 1400-1599
    Class J < 200
    		O único indivíduo melhor que emergiu dessa seleção foi inscrito como concorrente no site de jogos www.zone.com. Ao longo de um período de dois meses, ele jogou contra 165 oponentes humanos que abrangiam uma variedade de níveis de habilidade, da classe C ao master, de acordo com o sistema de classificação da Federação de Xadrez dos Estados Unidos (mostrado à esquerda, algumas classificações omitidas para clareza). Desses jogos, a rede neural venceu 94, perdeu 39 e empatou 32; com base nas classificações dos oponentes nesses jogos, a rede neural evoluída era equivalente a um jogador com uma classificação média de 2045,85, colocando-a no nível de expert – uma classificação superior à de 99,61% dos mais de 80.000 jogadores registrados no site. Uma das vitórias mais significativas da rede neural foi quando derrotou um jogador classificado 98º entre todos os jogadores registrados, cuja classificação estava apenas 27 pontos abaixo do nível de master.


    Tests conducted with a simple piece-differential program (which bases moves solely on the difference between the number of checkers remaining to each side) with an eight-move look-ahead showed the neural net to be significantly superior, with a rating over 400 points higher. "A program that relies only on the piece count and an eight-ply search will defeat a lot of people, but it is not an expert. The best evolved neural network is" (p.425). Even when it was searching positions two further moves ahead than the neural net, the piece-differential program lost decisively in eight out of ten games. This conclusively demonstrates that the evolved neural net is not merely counting pieces, but is somehow processing spatial characteristics of the board to decide its moves. The authors point out that opponents on zone.com often commented that the neural net's moves were "strange", but its overall level of play was described as "very tough" or with similar complimentary terms.

    To further test the evolved neural network (which the authors named "Anaconda" since it often won by restricting its opponents' mobility), it was played against a commercial checkers program, Hoyle's Classic Games, distributed by Sierra Online (Chellapilla e Fogel 2000). This program comes with a variety of built-in characters, each of whom plays at a different skill level. Anaconda was tested against three characters ("Beatrice", "Natasha" and "Leopold") designated as expert-level players, playing one game as red and one game as white against each of them with a six-ply look-ahead. Though the authors doubted that this depth of look-ahead would give Anaconda the ability to play at the expert skill level it had previously shown, it won six straight victories out of all six games played. Based on this outcome, the authors expressed skepticism over whether the Hoyle software played at the skill level advertised, though it should be noted that they reached this conclusion based exclusivamente on the ease with which Anaconda defeated it!

    The ultimate test of Anaconda was given in Chellapilla e Fogel 2002, where the evolved neural net was matched against the best checkers player in the world: Chinook, a program designed principally by Dr. Jonathan Schaeffer of the University of Alberta. Rated at 2814 in 1996 (with its closest human competitors rated in the 2600s), Chinook incorporates a book of opening moves provided by human grandmasters, a sophisticated set of middle-game algorithms, and a complete database of all possible moves with ten pieces on the board or less, so it never makes a mistake in the endgame. An enormous amount of human intelligence and expertise went into the design of this program.

    Chellapilla and Fogel pitted Anaconda against Chinook in a 10-game tournament, with Chinook playing at a 5-ply skill level, making it roughly approximate to master level. Chinook won this contest, four wins to two with four draws. (Interestingly, the authors note, in two of the games that ended as draws, Anaconda held the lead with four kings to Chinook's three. Furthermore, one of Chinook's wins came from a 10-ply series of movies drawn from its endgame database, which Anaconda with an 8-ply look-ahead could not have anticipated. If Anaconda had had access to an endgame database of the same quality as Chinook's, the outcome of the tournament might well have been a victory for Anaconda, four wins to three.) These results "provide good support for the expert-level rating that Anaconda earned on www.zone.com" (p.76), with an overall rating of 2030-2055, comparable to the 2045 rating it earned by playing against humans. While Anaconda is not an invulnerable player, it is able to play competitively at the expert level and hold its own against a variety of extremely skilled human checkers players. When one considers the very simple fitness criterion under which these results were obtained, the emergence of Anaconda provides dramatic corroboration of the power of evolution.

  • Geofísica
    Sambridge e Gallagher 1993 usaram um algoritmo genético para localizar hipocentros de terremotos com base em dados sismológicos. (O hipocentro é o ponto abaixo da superfície da Terra em que um terremoto começa. O epicentro é o ponto na superfície diretamente acima do hipocentro.) Esta é uma tarefa extremamente complexa, já que as propriedades das ondas sísmicas dependem das propriedades das camadas de rocha pelas quais elas viajam. O método tradicional para localizar o hipocentro baseia-se no que é conhecido como um algoritmo de inversão sísmica, que começa com uma melhor estimativa da localização, calcula as derivadas do tempo de viagem das ondas em relação à posição da fonte, e realiza uma operação de matriz para fornecer uma localização atualizada. Este processo é repetido até que uma solução aceitável seja alcançada. (Este Post do Mês, de novembro de 2003, fornece mais informações.) No entanto, este método requer informações de derivada e é propenso a ficar preso em ótimos locais.

    Um algoritmo de localização que não depende de informações de derivada ou modelos de velocidade pode evitar essas limitações calculando apenas o problema direto - a diferença entre os tempos de chegada das ondas observados e previstos para diferentes locais de hipocentro. No entanto, uma busca exaustiva baseada neste método seria muito cara computacionalmente. Isto, naturalmente, é precisamente o tipo de problema de otimização no qual os algoritmos genéticos se destacam. Como todos os AGs, o proposto pelo artigo citado é de natureza paralela - em vez de perturbar progressivamente um único hipocentro cada vez mais próximo da solução, ele começa com uma nuvem de hipocentros potenciais que diminui com o tempo para convergir em uma única solução. Os autores afirmam que sua abordagem "pode localizar rapidamente soluções quase ótimas sem uma busca exaustiva do espaço de parâmetros" (p.1467), exibe "comportamento altamente organizado resultando em busca eficiente" e é "um compromisso entre a eficiência de métodos baseados em derivadas e a robustez de uma busca exaustiva totalmente não linear" (p.1469). Os autores concluem que seu algoritmo genético é "eficiente para otimização global verdadeiramente" (p.1488) e "uma nova ferramenta poderosa para realizar localização robusta de hipocentros" (p.1489).

  • Engenharia de materiais
    Giro, Cyrillo e Galvão 2002 utilizaram algoritmos genéticos para projetar polímeros baseados em carbono condutores eletricamente conhecidos como polianilinas. Estes polímeros, uma classe recentemente inventada de materiais sintéticos, têm "grandes aplicações de potencial tecnológico" e podem abrir janelas para "novos fenômenos físicos fundamentais" (p.170). No entanto, devido à sua alta reatividade, os átomos de carbono podem formar um número virtualmente infinito de estruturas, tornando uma busca sistemática por novas moléculas com propriedades interessantes praticamente impossível. Neste artigo, os autores aplicam uma abordagem baseada em AG à tarefa de projetar novas moléculas com propriedades pré-especificadas, começando com uma população de candidatos iniciais gerada aleatoriamente. Eles concluem que sua metodologia pode ser uma "ferramenta muito eficaz" (p.174) para orientar experimentalistas na busca por novos compostos e é geral o suficiente para ser estendida ao projeto de novos materiais pertencentes a praticamente qualquer classe de moléculas.

    Weismann, Hammel e Bäck 1998 aplicaram algoritmos evolutivos a um problema industrial "não trivial" (p.162): o projeto de revestimentos ópticos multicamada usados em filtros que refletem, transmitem ou absorvem luz de frequências especificadas. Estes revestimentos são usados na fabricação de óculos de sol, por exemplo, ou discos compactos. Sua fabricação é uma tarefa precisa: as camadas devem ser depositas em uma sequência particular e espessuras específicas para produzir o resultado desejado, e variações ambientais não controláveis no ambiente de fabricação, como temperatura, poluição e umidade, podem afetar o desempenho do produto final. Muitos ótimos locais não são robustos contra tais variações, significando que a máxima qualidade do produto deve ser paga com taxas mais altas de desvio indesejável. O problema particular considerado neste artigo também tinha múltiplos critérios: além da refletância, a composição espectral (cor) da luz refletida também foi considerada.

    O AE operou variando o número de camadas de revestimento e a espessura de cada uma, e produziu projetos que foram "substancialmente mais robustos à variação de parâmetros" (p.166) e tiveram desempenho médio superior aos métodos tradicionais. Os autores concluem que "algoritmos evolutivos podem competir com ou até superar os métodos tradicionais" (p.167) de projeto de revestimentos ópticos multicamada, sem precisar incorporar conhecimento específico do domínio na função de busca e sem precisar semear a população com bons projetos iniciais.

    Mais um uso de AGs no campo da engenharia de materiais merece menção: Robin et al. 2003 usaram AGs para projetar padrões de exposição para um feixe de litografia eletrônica, usado para gravar estruturas em escala submicrométrica em circuitos integrados. Projetar estes padrões é uma tarefa altamente difícil; é trabalhoso e desperdiçador determiná-los experimentalmente, mas a alta dimensionalidade do espaço de busca derrota a maioria dos algoritmos de busca. Até 100 parâmetros devem ser otimizados simultaneamente para controlar o feixe de elétrons e prevenir espalhamento e efeitos de proximidade que, de outra forma, arruinariam as estruturas finas sendo esculpidas. O problema direto - determinar a estrutura resultante como função da dose de elétrons - é direto e fácil de simular, mas o problema inverso de determinar a dose de elétrons para produzir uma estrutura dada, que é o que está sendo resolvido aqui, é muito mais difícil e não existe uma solução determinística.

    Algoritmos genéticos, que são "conhecidos por serem capazes de encontrar boas soluções para problemas muito complexos de alta dimensionalidade" (p.75) sem precisar ser fornecidos com informações específicas do domínio sobre a topologia da paisagem de busca, foram aplicados com sucesso a este problema. Os autores do artigo empregaram um AG de estado estacionário com seleção por roda da roleta em uma simulação computacional, o que resultou em "padrões de exposição muito bem otimizados" (p.77). Por contraste, um tipo de escalador de colina conhecido como algoritmo simplex-descida foi aplicado ao mesmo problema, sem sucesso; o método SD rapidamente ficou preso em ótimos locais dos quais não conseguia escapar, produzindo soluções de baixa qualidade. Uma abordagem híbrida dos métodos AG e SD também não conseguiu melhorar os resultados entregues pelo AG sozinho.

  • Matemática e algoritmia
    Embora algumas das aplicações mais promissoras e demonstrações convincentes do poder das AGs estejam no campo do projeto de engenharia, elas também são relevantes para problemas matemáticos "puros". Haupt e Haupt 1998 (p.140) discutem o uso de AGs para resolver equações diferenciais parciais não lineares de alta ordem, tipicamente encontrando os valores para os quais as equações são iguais a zero, e dão como exemplo uma solução quase perfeita de AG para os coeficientes da equação de Super Korteweg-de Vries de quinta ordem.

    Ordenar uma lista de itens em ordem é uma tarefa importante em ciência da computação, e uma rede de ordenação é uma forma eficiente de realizar isso. Uma rede de ordenação é uma lista fixa de comparações realizadas em um conjunto de tamanho dado; em cada comparação, dois elementos são comparados e trocados se não estiverem em ordem. Koza et al. 1999, p. 952, usaram programação genética para evoluir redes de ordenação mínimas para conjuntos de 7 itens (16 comparações), conjuntos de 8 itens (19 comparações) e conjuntos de 9 itens (25 comparações). Mitchell 1996, p.21, discute o uso de algoritmos genéticos por W. Daniel Hillis para encontrar uma rede de ordenação de 61 comparações para um conjunto de 16 itens, apenas um passo a mais do que a menor conhecida. Este último exemplo é particularmente interessante por duas inovações que utilizou: cromossomos diplóides e, mais notavelmente, coevolução hospedeiro-parasita. Tanto as redes de ordenação quanto os casos de teste evoluíram lado a lado; as redes de ordenação receberam maior aptidão com base em quantos casos de teste ordenaram corretamente, enquanto os casos de teste receberam maior aptidão com base em quantas redes de ordenação conseguiam "enganar" para ordenar incorretamente. A AG com coevolução performou significativamente melhor do que a mesma AG sem ela.

    Um último exemplo notável de AGs no campo da algoritmia pode ser encontrado em Koza et al. 1999, que usaram programação genética para descobrir uma regra para o problema de classificação de maioria em autômatos celulares unidimensionais que é melhor do que todas as regras conhecidas escritas por humanos. Um autômata celular unidimensional pode ser pensado como uma fita finita com um número dado de posições (células) nela, cada uma das quais pode conter o estado 0 ou o estado 1. O autômata roda por um número dado de passos de tempo; em cada passo, cada célula adquire um novo valor com base em seu valor anterior e o valor de seus vizinhos mais próximos. (O Jogo da Vida é um autômata celular bidimensional.) O problema de classificação de maioria envolve encontrar uma tabela de regras de tal forma que, se mais da metade das células na fita forem 1 inicialmente, todas as células vão para 1; caso contrário, todas as células vão para 0. O desafio reside no fato de que qualquer célula individual pode acessar apenas informações sobre seus vizinhos mais próximos; portanto, bons conjuntos de regras devem de alguma forma encontrar uma maneira de transmitir informações sobre regiões distantes da fita.

    Sabe-se que uma solução perfeita para este problema não existe - nenhum conjunto de regras pode classificar com precisão todas as configurações iniciais possíveis - mas ao longo dos últimos vinte anos, houve uma longa sucessão de soluções cada vez melhores. Em 1978, três pesquisadores desenvolveram a chamada regra GKL, que classifica corretamente 81,6% dos estados iniciais possíveis. Em 1993, uma regra melhor com uma precisão de 81,8% foi descoberta; em 1995, outra regra com precisão de 82,178% foi encontrada. Todas essas regras requeriram trabalho significativo por parte de humanos inteligentes e criativos para serem desenvolvidas. Em contraste, a melhor regra descoberta por uma execução de programação genética, apresentada em Koza et al. 1999, p.973, tem uma precisão geral de 82,326% - melhor do que qualquer uma das soluções criadas por humanos que foram desenvolvidas ao longo das últimas duas décadas. Os autores notam que suas novas regras são qualitativamente diferentes das regras anteriormente publicadas, empregando representações internas finas da densidade de estado e conjuntos intrincados de sinais para comunicar informações a longas distâncias.

  • Militares e aplicação da lei
    Kewley e Embrechts 2002 utilizaram algoritmos genéticos para evoluir planos táticos para batalhas militares. Os autores observam que "[p]lanificar uma batalha militar tática é uma tarefa complexa e de alta dimensão que frequentemente confunde profissionais experientes" (p.163), não apenas porque tais decisões são geralmente tomadas sob condições de alto estresse, mas também porque mesmo planos simples exigem que se levem em conta um grande número de variáveis e resultados conflitantes: minimizar baixas entre as próprias forças, maximizar baixas entre o inimigo, controlar o terreno desejado, conservar recursos, e assim por diante. Os planejadores humanos têm dificuldade em lidar com as complexidades desta tarefa e frequentemente precisam recorrer a abordagens "rápidas e sujas", como fazer o que funcionou da última vez.

    Para superar essas dificuldades, os autores do artigo citado desenvolveram um algoritmo genético para automatizar a criação de planos de batalha, em conjunto com um programa de simulador de batalha gráfico. O comandante insere o resultado preferido, e o AG automaticamente evolui um plano de batalha; na simulação utilizada, fatores como a topografia do terreno, cobertura vegetal, velocidade de movimento das tropas e precisão de tiro foram levados em conta. Neste experimento, também foi utilizada co-evolução para melhorar a qualidade das soluções: planos de batalha para as forças inimigas evoluíram simultaneamente com os planos das próprias forças, forçando o AG a corrigir quaisquer fraquezas em seu próprio plano que um inimigo pudesse explorar. Para medir a qualidade das soluções produzidas pelo AG, elas foram comparadas a planos de batalha para o mesmo cenário produzidos por um grupo de "especialistas militares experientes... considerados muito capazes de desenvolver cursos de ação táticos para o tamanho das forças utilizadas neste experimento" (p.166). Esses especialistas experientes desenvolveram seu próprio plano e, quando a solução do AG estava completa, tiveram a chance de examiná-la e modificá-la conforme achassem adequado. Finalmente, todos os conjuntos de planos foram executados várias vezes no simulador para determinar sua qualidade média.

    Os resultados falam por si mesmos: a solução evoluída superou tanto o plano próprio dos especialistas militares quanto o plano produzido por suas modificações à solução do AG. "...[T]os planos produzidos por algoritmos automatizados tiveram um desempenho médio significativamente superior aos gerados por especialistas militares experientes" (p.161). Além disso, os autores observam que o plano do AG fazia bom sentido tático. (Envolveu um ataque em duas frentes à posição inimiga por pelotões de infantaria mecanizada apoiados por helicópteros de ataque e escoteiros terrestres, em conjunto com veículos aéreos não tripulados realizando reconhecimento para direcionar fogo de artilharia.) Além disso, o plano evoluído incluía unidades amigas individuais executando missões doutrinárias - uma propriedade emergente que apareceu durante o curso da execução, em vez de ser especificada pelo experimenter. Em campos de batalha modernos cada vez mais interconectados, o potencial atraente de um algoritmo evolutivo que pode automatizar a produção de planos táticos de alta qualidade deve ser óbvio.

    Um uso interessante de AGs na aplicação da lei foi relatado em Naik 1996, que descreveu o software "FacePrints", um projeto para ajudar testemunhas a identificar e descrever suspeitos criminosos. A imagem clichê do artista de esboços policiais desenhando o rosto do suspeito em resposta aos indícios das testemunhas é um método difícil e ineficiente: a maioria das pessoas não é boa em descrever aspectos individuais do rosto de uma pessoa, como o tamanho do nariz ou a forma da mandíbula, mas é melhor em reconhecer rostos inteiros. O FacePrints aproveita isso utilizando um algoritmo genético que evolui imagens de rostos com base em bancos de dados de centenas de características individuais que podem ser combinadas de um vasto número de maneiras. O programa mostra imagens de rostos geradas aleatoriamente às testemunhas, que escolhem as que mais se assemelham à pessoa que viram; os rostos selecionados são então mutados e cruzados para gerar novas combinações de características, e o processo se repete até que um retrato preciso do rosto do suspeito emerge. Em um caso real de roubo, os retratos finais criados pelas três testemunhas foram surpreendentemente semelhantes, e a imagem resultante foi impressa no jornal local.

  • Biologia molecular
    Em seres vivos, as proteínas transmembranares são proteínas que atravessam uma membrana celular. As proteínas transmembranares frequentemente desempenham funções importantes, como detectar a presença de certas substâncias fora da célula ou transportá-las para dentro da célula. Compreender o comportamento de uma proteína transmembrana requer identificar o segmento dessa proteína que está realmente incorporado na membrana, o que é chamado de domínio transmembrana. Ao longo das últimas duas décadas, biólogos moleculares publicaram uma sucessão de algoritmos cada vez mais precisos para esse fim.

    Todas as proteínas utilizadas por seres vivos são compostas pelos mesmos 20 aminoácidos. Alguns desses aminoácidos são hidrofóbicos, o que significa que são repelidos pela água, e outros são hidrofílicos, o que significa que são atraídos pela água. Sequências de aminoácidos que fazem parte de um domínio transmembrana são mais propensas a serem hidrofóbicas. No entanto, a hidrofobicidade não é uma característica precisamente definida, e não existe uma escala universalmente aceita para medi-la.

    Koza et al. 1999, capítulo 16, utilizou programação genética para projetar um algoritmo capaz de identificar domínios transmembranares de uma proteína. A programação genética foi fornecida com um conjunto de operadores matemáticos padrão para trabalhar, bem como um conjunto de funções booleanas de detecção de aminoácidos que retornam +1 se o aminoácido em uma posição dada for o aminoácido que elas detectam e, caso contrário, retornam -1. (Por exemplo, a função A? recebe como argumento um número correspondente a uma posição dentro da proteína e retorna +1 se o aminoácido nessa posição for alanina, denotada pela letra A; caso contrário, retorna -1). Uma variável de memória compartilhada mantinha uma contagem em tempo real da soma total, e quando o algoritmo completava, o segmento da proteína era identificado como um domínio transmembrana se seu valor fosse positivo. Dadas apenas essas ferramentas, seria necessário que um projetista humano criasse nova informação para produzir uma solução eficiente para este problema?

    As soluções produzidas pela programação genética foram avaliadas quanto à aptidão testando-as em 246 segmentos de proteína cujo status transmembrana era conhecido. O indivíduo melhor da execução foi então avaliado em 250 casos de teste adicionais, fora da amostra, e comparado ao desempenho dos quatro melhores algoritmos escritos por humanos conhecidos para o mesmo propósito. O resultado: a programação genética produziu um algoritmo de identificação de segmentos transmembranares com uma taxa de erro geral de 1,6% - significativamente menor do que todos os quatro algoritmos escritos por humanos, o melhor dos quais tinha uma taxa de erro de 2,5%. O algoritmo projetado geneticamente, que os autores apelidaram de regra 0-2-4, opera da seguinte maneira:

    • Aumente a soma em execução em 4 para cada instância de ácido glutâmico (um aminoácido eletricamente carregado e altamente hidrofílico) no segmento da proteína.
    • Aumente a soma em execução em 0 para cada instância de alanina, fenilalanina, isoleucina, leucina, metionina ou valina (todos aminoácidos altamente hidrofóbicos) no segmento da proteína.
    • Aumente a soma em execução em 2 para cada instância de todos os outros aminoácidos.
    • Se [(SOMA - 3,1544)/0,9357] for menor que o comprimento do segmento da proteína, classifique esse segmento como um domínio transmembrana; caso contrário, classifique-o como um domínio não transmembrana.

  • Reconhecimento de padrões e mineração de dados
    Competition in the telecommunications industry today is fierce, and a new term - "churn" - has been coined to describe the rapid rate at which subscribers switch from one service provider to another. Churn costs telecom carriers a large amount of money each year, and reducing churn is an important factor in increasing profitability. If carriers can contact customers who are likely to switch and offer them special incentives to stay, churn rates can be reduced; but no carrier has the resources to contact more than a small percent of its customers. The problem is therefore how to identify customers who are more likely to churn. All carriers have extensive databases of customer information that can theoretically be used for this purpose; but what method works best for sifting through this vast amount of data to identify the subtle patterns and trends that signify a customer's likelihood of churning?

    Au, Chan e Yao 2003 applied genetic algorithms to this problem to generate a set of if-then rules that predict the churning probability of different groups of customers. In their GA, the first generation of rules, all of which had one condition, was generated using a probabilistic induction technique. Subsequent generations then refine these, combining simple, single-condition rules into more complex, multi-condition rules. The fitness measure used an objective "interestingness" measure of correlation which requires no subjective input. The evolutionary data-mining algorithm was tested on a real-world database of 100,000 subscribers provided by a Malaysian carrier, and its performance was compared against two alternative methods: a multilayer neural network and a widely used decision-tree-based algorithm, C4.5. The authors state that their EA was able to discover hidden regularities in the database and was "able to make accurate churn prediction under different churn rates" (p.542), outperforming C4.5 under all circumstances, outperforming the neural network under low monthly churn rates and matching the neural network under larger churn rates, and reaching conclusions more quickly in both cases. Some further advantages of the evolutionary approach are that it can operate efficiently even when some data fields are missing and that it can express its findings in easily understood rule sets, unlike the neural net.

    Among some of the more interesting rules discovered by the EA are as follows: subscribers are more likely to churn if they are personally subscribed to the service plan and have not been admitted to any bonus scheme (a potential solution is to admit all such subscribers to bonus schemes); subscribers are more likely to churn if they live in Kuala Lumpur, are between 36 and 44 in age, and pay their bills with cash (presumably because it is easier for subscribers who pay cash, rather than those whose accounts are automatically debited, to switch providers); and subscribers living in Penang who signed up through a certain dealer are more likely to churn (this dealer may be providing poor customer service and should be investigated).

    Rizki, Zmuda e Tamburino 2002 used evolutionary algorithms to evolve a complex pattern recognition system with a wide variety of potential uses. The authors note that the task of pattern recognition is increasingly being performed by machine learning algorithms, evolutionary algorithms in particular. Most such approaches begin with a pool of predefined features, from which an EA can select appropriate combinations for the task at hand; by contrast, this approach began from the ground up, first evolving individual feature detectors in the form of expression trees, then evolving cooperative combinations of those detectors to produce a complete pattern recognition system. The evolutionary process automatically selects the number of feature detectors, the complexity of the detectors, and the specific aspects of the data each detector responds to.

    To test their system, the authors gave it the task of classifying aircraft based on their radar reflections. The same kind of aircraft can return quite different signals depending on the angle and elevation at which it is viewed, and different kinds of aircraft can return very similar signals, so this is a non-trivial task. The evolved pattern recognition system correctly classified 97.2% of the targets, a higher net percentage than any of the three other techniques - a perceptron neural network, a nearest-neighbor classifier algorithm, and a radial basis algorithm - against which it was tested. (The radial basis network's accuracy was only 0.5% less than the evolved classifier, which is not a statistically significant difference, but the radial basis network required 256 feature detectors while the evolved recognition system used only 17.) As the authors state, "The recognition systems that evolve use fewer features than systems formed using conventional techniques, yet achieve comparable or superior recognition accuracy" (p.607). Various aspects of their system have also been applied to problems including optical character recognition, industrial inspection and medical image analysis.

    Hughes e Leyland 2000 also applied multiple-objective GAs to the task of classifying targets based on their radar reflections. High-resolution radar cross section data requires massive amounts of disk storage space, and it is very computationally intensive to produce an actual model of the source from the data. By contrast, the authors' GA-based approach proved very successful, producing a model as good as the traditional iterative approach while reducing the computational overhead and storage requirements to the point where it was feasible to generate good models on a desktop computer. By contrast, the traditional iterative approach requires ten times the resolution and 560,000 times as many accesses of image data to produce models of similar quality. The authors conclude that their results "clearly demonstrate" (p.160) the ability of the GA to process both two- and three-dimensional radar data of any level of resolution with far fewer calculations than traditional methods, while retaining acceptably high accuracy.

  • Robótica
    O torneio internacional RoboCup é um projeto para promover avanços em robótica, inteligência artificial e áreas relacionadas, fornecendo um problema padrão onde novas tecnologias podem ser testadas — especificamente, trata-se de um torneio anual de futebol entre equipes de robôs autônomos. (O objetivo declarado é desenvolver uma equipe de robôs humanoides que possa vencer a equipe de futebol humana campeã mundial até 2050; no momento presente, a maioria das equipes de robôs concorrentes é baseada em rodas.) Os programas que controlam os membros da equipe robótica devem exibir comportamento complexo, decidindo quando bloquear, quando chutar, como se mover, quando passar a bola para os companheiros de equipe, como coordenar defesa e ataque, e assim por diante. Na liga de simuladores do campeonato de 1997, David Andre e Astro Teller inscreveram uma equipe chamada Darwin United, cujos programas de controle foram desenvolvidos automaticamente do zero até o fim por meio de programação genética, um desafio à sabedoria convencional de que "esse problema é simplesmente muito difícil para tal técnica" (Andre e Teller 1999, p. 346).

    Para resolver esse problema difícil, Andre e Teller forneceram ao algoritmo de programação genética um conjunto de funções de controle primitivas, como girar, mover, chutar e assim por diante. (Essas funções também estavam sujeitas a mudanças e refinamentos durante o curso da evolução.) Sua função de aptidão, escrita para recompensar um bom jogo em geral e não especificamente para marcar gols, forneceu uma lista de objetivos cada vez mais importantes: chegar perto da bola, chutar a bola, manter a bola no lado do campo do oponente, mover-se na direção correta, marcar gols e vencer o jogo. Deve-se notar que nenhum código foi fornecido para ensinar à equipe especificamente como alcançar esses objetivos complexos. Os programas evoluídos foram então avaliados usando um modelo de seleção hierárquico: primeiro, as equipes candidatas foram testadas em um campo vazio e rejeitadas se não marcassem um gol em 30 segundos. Em seguida, foram avaliadas contra uma equipe de "pólos de chute" estacionários que chutam a bola para o lado oposto do campo. Em terceiro lugar, a equipe jogou um jogo contra a equipe vencedora do campeonato RoboCup de 1997. Finalmente, as equipes que marcaram pelo menos um gol contra essa equipe foram eliminadas entre si para determinar qual era a melhor.

    Das 34 equipes em sua divisão, a Darwin United acabou ficando em 17º lugar, posicionando-se exatamente no meio do campo e superando metade das entradas escritas por humanos. Embora uma vitória no torneio sem dúvida teria sido mais impressionante, esse resultado é competitivo e significativo por si só, e parece ainda mais assim à luz da história. Há cerca de 25 anos, os programas de computador para jogar xadrez estavam em seus primórdios; um computador havia entrado apenas recentemente em uma competição regional pela primeira vez, embora não tivesse vencido (Sagan 1979, p. 286). Mas "[u]ma máquina que joga xadrez no nível médio de habilidade humana é uma máquina muito capaz" (ibid.), e pode-se dizer que o mesmo é verdadeiro para o futebol robótico. Assim como as máquinas de jogar xadrez competem hoje em níveis de grande mestre mundial, que tipos de sistemas a programação genética estará produzindo em 20 ou 30 anos?

  • Roteamento e agendamento
    Burke e Newall 1999 used genetic algorithms to schedule exams among university students. The timetable problem in general is known to be NP-complete, meaning that no method is known to find a guaranteed-optimal solution in a reasonable amount of time. In such a problem, there are both hard constraints - two exams may not be assigned to the same room at the same time - and soft constraints - students should not be assigned to multiple exams in succession, if possible, to minimize fatigue. Hard constraints must be satisfied, while soft constraints should be satisfied as far as possible. The authors dub their hybrid approach for solving this problem a "memetic algorithm": an evolutionary algorithm with rank-based, fitness-proportionate selection, combined with a local hill-climber to optimize solutions found by the EA. The EA was applied to data sets from four real universities (the smallest of which had an enrollment of 25,000 students), and its results were compared to results produced by a heuristic backtracking method, a well-established algorithm that is among the best known for this problem and that is used at several real universities. Compared to this method, the EA produced a result with a quite uniform 40% reduction in penalty.

    He e Mort 2000 applied genetic algorithms to the problem of finding optimal routing paths in telecommunications networks (such as phone networks and the Internet) which are used to relay data from senders to recipients. This is an NP-hard optimization problem, a type of problem for which GAs are "extremely well suited... and have found an enormous range of successful applications in such areas" (p.42). It is also a multiobjective problem, balancing conflicting objectives such as maximizing data throughput, minimizing transmission delay and data loss, finding low-cost paths, and distributing the load evenly among routers or switches in the network. Any successful real-world algorithm must also be able to re-route around primary paths that fail or become congested.

    In the authors' hybrid GA, a shortest-path-first algorithm, which minimizes the number of "hops" a given data packet must pass through, is used to generate the seed for the initial population. However, this solution does not take into account link congestion or failure, which are inevitable conditions in real networks, and so the GA takes over, swapping and exchanging sections of paths. When tested on a data set derived from a real Oracle network database, the GA was found to be able to efficiently route around broken or congested links, balancing traffic load and maximizing the total network throughput. The authors state that these results demonstrate the "effectiveness and scalability" of the GA and show that "optimal or near-optimal solutions can be achieved" (p.49).

    This technique has found real-world applications for similar purposes, as reported in Begley e Beals 1995. The telecommunications company U.S. West (now merged with Qwest) was faced with the task of laying a network of fiber-optic cable. Until recently, the problem of designing the network to minimize the total length of cable laid was solved by an experienced engineer; now the company uses a genetic algorithm to perform the task automatically. The results: "Design time for new networks has fallen from two months to two days and saves US West $1 million to $10 million each" (p.70).

    Jensen 2003 and Chryssolouris e Subramaniam 2001 applied genetic algorithms to the task of generating schedules for job shops. This is an NP-hard optimization problem with multiple criteria: factors such as cost, tardiness, and throughput must all be taken into account, and job schedules may have to be rearranged on the fly due to machine breakdowns, employee absences, delays in delivery of parts, and other complications, making robustness in a schedule an important consideration. Both papers concluded that GAs are significantly superior to commonly used dispatching rules, producing efficient schedules that can more easily handle delays and breakdowns. These results are not merely theoretical, but have been applied to real-world situations:

    As reported in Naik 1996, organizers of the 1992 Paralympic Games used a GA to schedule events. As reported in Petzinger 1995, John Deere & Co. has used GAs to generate schedules for a Moline, Illinois plant that manufactures planters and other heavy agricultural equipment. Like luxury cars, these can be built in a wide variety of configurations with many different parts and options, and the vast number of possible ways to build them made efficient scheduling a seemingly intractable problem. Productivity was hampered by scheduling bottlenecks, worker teams were bickering, and money was being lost. Finally, in 1993, Deere turned to Bill Fulkerson, a staff analyst and engineer who conceived of using a genetic algorithm to produce schedules for the plant. Overcoming initial skepticism, the GA quickly proved itself: monthly output has risen by 50 percent, overtime has nearly vanished, and other Deere plants are incorporating GAs into their own scheduling.

    As reported in Rao 1998, Volvo has used an evolutionary program called OptiFlex to schedule its million-square-foot factory in Dublin, Virginia, a task that requires handling hundreds of constraints and millions of possible permutations for each vehicle. Like all genetic algorithms, OptiFlex works by randomly combining different scheduling possibilities and variables, determines their fitness by ranking them according to costs, benefits and constraints, then causes the best solutions to swap genes and sends them back into the population for another trial. Until recently, this daunting task was handled by a human engineer who took up to four days to produce the schedule for each week; now, thanks to GAs, this task can be completed in one day with minimal human intervention.

    As reported in Lemley 2001, United Distillers and Vintners, a Scottish company that is the largest and most profitable spirits distributor in the world and accounts for over one-third of global grain whiskey production, uses a genetic algorithm to manage its inventory and supply. This is a daunting task, requiring the efficient storage and distribution of over 7 million barrels containing 60 distinct recipes among a vast system of warehouses and distilleries, depending on a multitude of factors such as age, malt number, wood type and market conditions. Previously, coordinating this complex flow of supply and demand required five full-time employees. Today, a few keystrokes on a computer instruct a genetic algorithm to generate a new schedule each week, and warehouse efficiency has nearly doubled.

    Beasley, Sonander e Havelock 2001 used a GA to schedule airport landings at London Heathrow, the United Kingdom's busiest airport. This is a multiobjective problem that involves, among other things, minimizing delays and maximizing number of flights while maintaining adequate separation distances between planes (air vortices that form in a plane's wake can be dangerous to another flying too closely behind). When compared to actual schedules from a busy period at the airport, the GA was able to reduce average wait time by 2-5%, equating to one to three extra flights taking off and landing per hour - a significant improvement. However, even greater improvements have been achieved: as reported in Wired 2002, major international airports and airlines such as Heathrow, Toronto, Sydney, Las Vegas, San Francisco, America West Airlines, AeroMexico, and Delta Airlines are using genetic algorithms to schedule takeoffs, landings, maintenance and other tasks, in the form of Ascent Technology's SmartAirport Operations Center software (see http://www.ascent.com/faq.html). Breeding and mutating solutions in the form of schedules that incorporate thousands of variables, "Ascent beats humans hands-down, raising productivity by up to 30 percent at every airport where it's been implemented."

  • Engenharia de sistemas
    Benini e Toffolo 2002 applied a genetic algorithm to the multi-objective task of designing wind turbines used to generate electric power. This design "is a complex procedure characterized by several trade-off decisions... The decision-making process is very difficult and the design trends are not uniquely established" (p.357); as a result, there are a number of different turbine types in existence today and no agreement on which, if any, is optimal. Mutually exclusive objectives such as maximum annual energy production and minimal cost of energy must be taken into account. In this paper, a multi-objective evolutionary algorithm was used to find the best trade-offs between these goals, constructing turbine blades with the optimal configuration of characteristics such as tip speed, hub/tip ratio, and chord and twist distribution. In the end, the GA was able to find solutions competitive with commercial designs, as well as more clearly elucidate the margins by which annual energy production can be improved without producing overly expensive designs.

    Haas, Burnham e Mills 1997 used a multiobjective genetic algorithm to optimize the beam shape, orientation and intensity of X-ray emitters used in targeted radiotherapy to destroy cancerous tumors while sparing healthy tissue. (X-ray photons aimed at a tumor tend to be partially scattered by structures within the body, unintentionally damaging internal organs. The challenge is to minimize this effect while maximizing the radiation dose delivered to the tumor.) Using a rank-based fitness model, the researchers began with the solution produced by the conventional method, an iterative least-squares approach, and then used the GA to modify and improve it. By constructing a model of a human body and exposing it to the beam configuration evolved by the GA, they found good agreement between the predicted and actual distributions of radiation. The authors conclude that their results "show a sparing of [healthy organs] that could not be achieved using conventional techniques" (p.1745).

    Lee e Zak 2002 used a genetic algorithm to evolve a set of rules to control an automotive anti-lock braking system. While the ability of antilock brake systems to reduce stopping distance and improve maneuverability has saved many lives, the performance of an ABS is dependent on road surface conditions: for example, an ABS controller that is optimized for dry asphalt will not work as well on wet or icy roads, and vice versa. In this paper, the authors propose a GA to fine-tune an ABS controller that can identify the road surface properties (by monitoring wheel slip and acceleration) and respond accordingly, delivering the appropriate amount of braking force to maximize the wheels' traction. In testing, the genetically tuned ABS "exhibits excellent tracking properties" (p.206) and was "far superior" (p.209) to two other methods of braking maneuvers, quickly finding new optimal values for wheel slip when the type of terrain changes beneath a moving car and reducing total stopping distance. "The lesson we learned from our experiment... is that a GA can help to fine-tune even a well-designed controller. In our case, we already had a good solution to the problem; yet, with the help of a GA, we were able to improve the control strategy significantly. In summary, it seems that it is worthwhile to try to apply a GA, even to a well-designed controller, because there is a good chance that one can find a better set of the controller settings using GAs" (p.211).

    As cited in Schechter 2000, Dr. Peter Senecal of the University of Wisconsin used small-population genetic algorithms to improve the efficiency of diesel engines. These engines work by injecting fuel into a combustion chamber which is filled with extremely compressed and therefore extremely hot air, hot enough to cause the fuel to explode and drive a piston that produces the vehicle's motive force. This basic design has changed little since it was invented by Rudolf Diesel in 1893; although vast amounts of effort have been put into making improvements, this is a very difficult task to perform analytically because it requires precise knowledge of the turbulent behavior displayed by the fuel-air mixture and simultaneous variation of many interdependent parameters. Senecal's approach, however, eschewed the use of such problem-specific knowledge and instead worked by evolving parameters such as the pressure of the combustion chamber, the timing of the fuel injections and the amount of fuel in each injection. The result: the simulation produced an improved engine that consumed 15% less fuel than a normal diesel engine and produced one-third as much nitric oxide exhaust and half as much soot. Senecal's team then built a real diesel engine according to the specifications of the evolved solution and got the same results. Senecal is now moving on to evolving the geometry of the engine itself, hopefully producing even greater improvements.

    As cited in Begley e Beals 1995, Texas Instruments used a genetic algorithm to optimize the layout of components on a computer chip, placing structures so as to minimize the overall area and create the smallest chip possible. Using a connection strategy that no human had thought of, the GA came up with a design that took 18% less space.

    Finally, as cited in Ashley 1992, a proprietary software system known as Engineous that employs genetic algorithms is being used by companies in the aerospace, automotive, manufacturing, turbomachinery and electronics industries to design and improve engines, motors, turbines and other industrial devices. In the words of its creator, Dr. Siu Shing Tong, Engineous is "a master 'tweaker,' tirelessly trying out scores of 'what-if' scenarios until the best possible design emerges" (p.49). In one trial of the system, Engineous was able to produce a 0.92 percent increase in the efficiency of an experimental turbine in only one week, while ten weeks of work by a human designer produced only a 0.5 percent improvement.

    Granted, Engineous does not rely solely on genetic algorithms; it also employs numerical optimization techniques and expert systems which use logical if-then rules to mimic the decision-making process of a human engineer. However, these techniques are heavily dependent on domain-specific knowledge, lack general applicability, and are prone to becoming trapped on local optima. By contrast, the use of genetic algorithms allows Engineous to explore regions of the search space that other methods miss.

    Engineous has found widespread use in a variety of industries and problems. Most famously, it was used to improve the turbine power plant of the Boeing 777 airliner; as reported in Begley e Beals 1995, the genetically optimized design was almost 1% more fuel-efficient than previous engines, which in a field such as this is "a windfall". Engineous has also been used to optimize the configuration of industrial DC motors, hydroelectric generators and steam turbines, to plan out power grids, and to design superconducting generators and nuclear power plants for orbiting satellites. Rao 1998 also reports that NASA has used Engineous to optimize the design of a high-altitude airplane for sampling ozone depletion, which must be both light and efficient.

Argumentos criacionistas
Topo

Como se poderia esperar, a demonstração prática no mundo real do poder da evolução que os Algoritmos Genéticos (AG) representam provou ser surpreendente e desconcertante para os criacionistas, que sempre alegaram que apenas o design inteligente, e não a variação aleatória e a seleção, poderiam ter produzido o conteúdo de informação e a complexidade dos seres vivos. Eles, portanto, argumentaram que o sucesso dos algoritmos genéticos não nos permite inferir nada sobre a evolução biológica. Serão abordadas as críticas de dois anti-evolucionistas, representando dois pontos de vista diferentes: o criacionista da Terra jovem Dr. Don Batten, da Answers in Genesis, que escreveu um artigo intitulado "Algoritmos genéticos -- eles mostram que a evolução funciona?", e o criacionista da Terra antiga e defensor do design inteligente Dr. William Dembski, cujo livro recente No Free Lunch (Dembski 2002) discute este tópico.

Don Batten

  • Algumas características em seres vivos são qualitativas, enquanto as AGs são sempre quantitativas
    Batten afirma que as AGs devem ser quantitativas, de modo que qualquer melhoria possa ser selecionada. Isso é verdade. Em seguida, ele diz: "Muitas características biológicas são qualitativas – ou funcionam ou não funcionam, por isso não há meio passo a passo de ir da não função à função." Esta afirmação, no entanto, não foi demonstrada e não é apoiada por evidências. Batten nem sequer tenta dar um exemplo de uma característica biológica que "funciona ou não funciona" e, portanto, não pode ser construída de forma passo a passo.

    Mas mesmo que ele oferecesse tal característica, como ele poderia provar que não há nenhuma via passo a passo para ela? Mesmo que não conheçamos tal via, segue-se que não há nenhuma? Claro que não. Batten está efetivamente afirmando que se não entendemos como certas características evoluíram, então é impossível que essas características tenham evoluído – um exemplo clássico da falácia lógica elementar de argumento da ignorância. O espaço de busca de todas as variantes possíveis de qualquer característica biológica dada é enorme, e na maioria dos casos nosso conhecimento abrange apenas uma fração infinitesimal das possibilidades. Pode haver inúmeros caminhos para uma estrutura que ainda não conhecemos; não há razão alguma para acreditar que nossa ignorância atual limita nosso progresso futuro. De fato, a história nos dá motivos para sermos confiantes: os cientistas fizeram enormes progressos na explicação da evolução de muitas estruturas e sistemas biológicos complexos, tanto macroscópicos quanto microscópicos (por exemplo, veja estas páginas sobre a evolução de sistemas moleculares complexos, genes "relógio", a língua do pica-pau ou o besouro-bombardier). Temos justificativa para acreditar que é provável que aqueles que até agora nos eludiram também sejam esclarecidos no futuro.

    De fato, as próprias AGs nos dão um excelente motivo para acreditar nisso. Muitos dos problemas aos quais elas foram aplicadas são questões complexas de engenharia e design onde a solução não era conhecida com antecedência e, portanto, o problema não podia ser "ajustado" para auxiliar o sucesso do algoritmo. Se os criacionistas estivessem corretos, seria inteiramente razoável esperar que os algoritmos genéticos falhassem miseravelmente tempo após tempo quando aplicados a esses problemas, mas, pelo contrário, ocorreu exatamente o oposto: as AGs descobriram soluções poderosas e de alta qualidade para problemas difíceis em uma variedade diversa de campos. Isso levanta sérias dúvidas sobre se existem mesmo problemas como os descritos por Batten, cujas soluções são inacessíveis a um processo evolutivo.

  • Os algoritmos genéticos selecionam uma característica de cada vez, enquanto os seres vivos são multidimensionais
    Batten afirma que nos algoritmos genéticos, "uma única característica é selecionada, enquanto qualquer ser vivo é multidimensional", e sustenta que em seres vivos com centenas de características, "a seleção tem que operar sobre todas as características que afetam a sobrevivência", enquanto "[u]m algoritmo genético não funcionará com três ou quatro objetivos diferentes, ou ousaria dizer, nem mesmo apenas dois."

    Este argumento revela o profundo desconhecimento de Batten sobre a literatura relevante. Mesmo uma revisão superficial do trabalho realizado sobre algoritmos evolutivos (ou uma olhada em uma seção anterior deste ensaio) teria revelado que os algoritmos genéticos multiobjetivo são uma área de pesquisa majoritária e próspera dentro do campo mais amplo da computação evolutiva e o impediria de fazer uma afirmação tão vergonhosamente incorreta. Existem artigos de revistas, números inteiros de revistas proeminentes sobre computação evolutiva, conferências inteiras e livros inteiros sobre o tema dos algoritmos genéticos multiobjetivo. Coello 2000 fornece uma revisão muito extensa, com cinco páginas de referências a artigos sobre o uso de algoritmos genéticos multiobjetivo em uma ampla gama de campos; veja também Fleming e Purshouse 2002; Hanne 2000; Zitzler e Thiele 1999; Fonseca e Fleming 1995; Srinivas e Deb 1994; Goldberg 1989, p.197. Para alguns livros e artigos que discutem o uso de algoritmos genéticos multiobjetivo para resolver problemas específicos, veja: Obayashi et al. 2000; Sasaki et al. 2001; Benini e Toffolo 2002; Haas, Burnham e Mills 1997; Chryssolouris e Subramaniam 2001; Hughes e Leyland 2000; He e Mort 2000; Kewley e Embrechts 2002; Beasley, Sonander e Havelock 2001; Sato et al. 2002; Tang et al. 1996; Williams, Crossley e Lang 2001; Koza et al. 1999; Koza et al. 2003. Para um repositório abrangente de citações sobre algoritmos genéticos multiobjetivo, veja http://www.lania.mx/~ccoello/EMOO/.

  • Os AGs não permitem a possibilidade de extinção ou catástrofe de erro
    Batten afirma que, nos AGs, "algo sempre sobrevive para continuar o processo", enquanto isso não é necessariamente verdade no mundo real - em suma, os AGs não permitem a possibilidade de extinção.

    No entanto, isso não é verdade; a extinção pode ocorrer. Por exemplo, alguns AGs utilizam um modelo de seleção chamado thresholding (limiar), no qual os indivíduos devem ter uma aptidão superior a um nível predeterminado para sobreviver e se reproduzir (Haupt e Haupt 1998, p. 37). Se nenhum indivíduo atender a esse padrão em tal AG, a população pode, de fato, extinguir-se. Mas mesmo em AGs que não utilizam thresholding, estados análogos à extinção podem ocorrer. Se as taxas de mutação forem muito altas ou as pressões seletivas muito fortes, então um AG nunca encontrará uma solução viável. A população pode tornar-se completamente desordenada à medida que mutações deletérias se acumulam mais rápido do que a seleção pode removê-las, perturbando candidatos mais aptos (catástrofe de erro), ou pode agitarse sem sucesso, incapaz de alcançar qualquer ganho em aptidão grande o suficiente para ser selecionado. Assim como na natureza, deve haver um equilíbrio ou uma solução nunca será alcançada. A única vantagem que um programador tem neste respeito é que, se isso acontecer, ele pode recarregar o programa com diferentes valores - para o tamanho da população, para a taxa de mutação, para a pressão de seleção - e começar de novo. Obviamente, isso não é uma opção para seres vivos. Batten diz: "Não há regra na evolução que diga que algum(s) organismo(s) na população em evolução permanecerão viáveis, não importa quais mutações ocorram", mas não há tal regra em algoritmos genéticos também.

    Batten também afirma que "os AGs que examinei artificialmente preservam o melhor da geração anterior e o protegem de mutações ou recombinação caso nada melhor seja produzido na próxima iteração". Esta crítica será abordada no próximo ponto.

  • Os AGs ignoram o custo da substituição
    A próxima alegação de Batten é que os AGs negligenciam o "Dilema de Haldane", o qual afirma que um alelo que contribui menos para a aptidão de um organismo levará um tempo correspondentemente mais longo para se fixar em uma população. Obviamente, a que ele se refere é a técnica de seleção elitista, que automaticamente seleciona o melhor candidato em cada geração, independentemente de quão pequena seja sua vantagem sobre seus competidores. Ele está correto ao sugerir que, na natureza, vantagens competitivas muito sutis podem levar muito mais tempo para se propagar. Os algoritmos genéticos não são um modelo exato da evolução biológica neste aspecto.

    No entanto, isso é irrelevante. A seleção elitista é uma idealização da evolução biológica – um modelo do que aconteceria na natureza se a sorte não interferisse de vez em quando. Como Batten reconhece, o dilema de Haldane não afirma que uma mutação ligeiramente vantajosa nunca se tornará fixa em uma população; ele afirma que levará mais tempo para que isso ocorra. No entanto, quando o tempo de computação é escasso ou um pesquisador de AGs deseja obter uma solução mais rapidamente, pode ser desejável pular esse processo implementando a elitismo. Um ponto importante é que o elitismo não afeta quais mutações surgem, apenas garante a seleção das melhores que de fato surgem. Não importaria a força da seleção se as mutações que aumentam a informação não ocorressem. Em outras palavras, o elitismo acelera a convergência uma vez que uma boa solução foi descoberta – ele não traz à tona um resultado que não ocorreria de outra forma. Portanto, se algoritmos genéticos com elitismo podem produzir nova informação, então a evolução na natureza também pode.

    Além disso, nem todos os AGs usam seleção elitista. Muitos não usam, dependendo apenas da seleção por roda da roleta e outras técnicas de amostragem estocástica, e ainda assim esses têm sido igualmente bem-sucedidos. Por exemplo, Koza et al. 2003, p.8-9, fornece exemplos de 36 casos em que a programação genética produziu resultados competitivos com humanos, incluindo a recriação automatizada de 21 invenções anteriormente patenteadas (seis das quais foram patenteadas durante ou após 2000), 10 das quais duplicam a funcionalidade do patente de uma nova maneira, e também incluindo duas novas invenções patentáveis e cinco novos algoritmos que superam qualquer algoritmo escrito por humanos para o mesmo propósito. Como o Dr. Koza afirma em uma referência anterior ao mesmo trabalho (1999, p.1070): "A estratégia elitista não é usada." Alguns outros artigos citados neste ensaio nos quais o elitismo não é usado incluem: Robin et al. 2003; Rizki, Zmuda e Tamburino 2002; Chryssolouris e Subramaniam 2001; Burke e Newall 1999; Glen e Payne 1995; Au, Chan e Yao 2003; Jensen 2003; Kewley e Embrechts 2002; Williams, Crossley e Lang 2001; Mahfoud e Mani 1996. Em cada um desses casos, sem nenhum mecanismo para garantir que os melhores indivíduos fossem selecionados em cada geração, sem isentar esses indivíduos de mudanças aleatórias potencialmente prejudiciais, os algoritmos genéticos ainda produzem resultados poderosos, eficientes e competitivos com humanos. Este fato pode ser surpreendente para criacionistas como Batten, mas é totalmente esperado pelos defensores da evolução.

  • As GAs ignoram as restrições de tempo de geração
    Esta crítica é confusa. Batten afirma que uma única geração em uma GA pode levar microssegundos, enquanto uma única geração em qualquer organismo vivo pode levar de minutos a anos. Isso é verdade, mas não é explicado como isso se relaciona com a validade das GAs como evidência para a evolução. Se uma GA pode gerar nova informação, independentemente do tempo que leva, então certamente a evolução na natureza também pode fazê-lo; que as GAs de fato possam fazê-lo é tudo o que este ensaio pretende demonstrar. A única questão restante seria se a evolução biológica realmente teve tempo suficiente para causar mudanças significativas, e a resposta a esta questão seria uma para biólogos, geólogos e físicos, não para programadores de computador.

    A resposta que esses cientistas forneceram está totalmente de acordo com as escalas de tempo evolutivas, no entanto. Várias linhas de evidência independente, incluindo datação por isócronas radiométricas, as taxas de resfriamento de anãs brancas, a inexistência de isótopos com meia-vida curta na natureza, as taxas de recessão de galáxias distantes e a análise da radiação cósmica de fundo todas convergem para a mesma conclusão: uma Terra e um universo com muitos bilhões de anos de idade, facilmente tempo suficiente para a evolução produzir toda a diversidade de vida que vemos hoje, segundo todas as estimativas razoáveis.

  • Os AGs empregam taxas de mutação e reprodução irrealistas
    Batten afirma, sem fornecer qualquer evidência ou citação de apoio, que os AGs "produzem comumente centenas ou milhares de 'filhos' por geração", uma taxa que nem mesmo bactérias, os organismos biológicos de reprodução mais rápida, conseguem igualar.

    Esta crítica falha em vários aspectos. Primeiro, se a métrica utilizada for (como deveria ser) o número de filhos por geração, em vez do número de filhos por unidade de tempo absoluto, então claramente existem organismos biológicos que podem se reproduzir a taxas mais rápidas do que as das bactérias e aproximadamente iguais às taxas que Batten afirma serem irrealistas. Por exemplo, um único sapo pode botar milhares de ovos de uma vez, cada um dos quais tem o potencial de se desenvolver em um adulto. Concedido, a maioria desses geralmente não sobreviverá devido a limitações de recursos e predação, mas então a maioria dos "filhos" em cada geração de um AG também não prosseguirá.

    Em segundo lugar, e mais importante, um algoritmo genético trabalhando para resolver um problema não é destinado a representar um único organismo. Em vez disso, um algoritmo genético é mais análogo a uma população inteira de organismos - afinal, são as populações, não os indivíduos, que evoluem. Claro, é perfeitamente plausível que uma população inteira tenha coletivamente centenas ou milhares de filhos por geração. (O criacionista Walter ReMine comete o mesmo erro em relação ao programa "gato" do Dr. Richard Dawkins. Veja este Post do Mês para mais informações.)

    Além disso, Batten diz que a taxa de mutação é artificialmente alta nos AGs, enquanto os organismos vivos possuem maquinaria de verificação de erros projetada para limitar a taxa de mutação a cerca de 1 em 10 bilhões de pares de bases (embora isso seja muito pequeno - o valor real está mais próximo de 1 em 1 bilhão. Veja Dawkins 1996, p.124). Agora, é claro que isso é verdade. Se os AGs mutassem nessa taxa, levariam muito tempo demais para resolver problemas do mundo real. Claramente, o que deve ser considerado relevante é a taxa de mutação relativa ao tamanho do genoma. A taxa de mutação deve ser alta o suficiente para promover uma quantidade suficiente de diversidade na população sem sobrecarregar os indivíduos. Um humano médio possuirá entre uma e cinco mutações; isso não é nada irrealista para os filhos de um AG.

  • As GAs possuem genomas artificialmente pequenos
    O argumento de Batten de que o genoma de um algoritmo genético "é artificialmente pequeno e apenas faz uma coisa" é mal fundamentado. Em primeiro lugar, como já vimos, não é verdade que um GA apenas faz uma coisa; existem muitos exemplos de algoritmos genéticos especificamente projetados para otimizar muitos parâmetros simultaneamente, frequentemente muito mais parâmetros simultaneamente do que um designer humano jamais poderia.

    E como exatamente Batten quantifica "artificialmente pequeno"? Muitos algoritmos evolutivos, como o programação genética de John Koza, usam codificações de comprimento variável onde o tamanho das soluções candidatas pode crescer arbitrariamente. Batten afirma que até mesmo o organismo vivo mais simples possui muito mais informações em seu genoma do que um GA já produziu, mas enquanto os organismos vivos hoje podem ter genomas relativamente grandes, isso ocorre porque muita complexidade foi adquirida ao longo de bilhões de anos de evolução. Como o artigo Probabilidade de Abiogênese aponta, há bons motivos para acreditar que os primeiros organismos vivos eram muito mais simples do que qualquer espécie atualmente existente — moléculas autorreplicantes provavelmente não mais longas que 30 ou 40 subunidades, que poderiam facilmente ser especificadas pelos 1800 bits de informação que Batten aparentemente admite que pelo menos um GA gerou. Algoritmos genéticos são igualmente uma técnica muito nova cujo potencial pleno ainda não foi explorado; os computadores digitais em si têm apenas algumas décadas de existência, e como Koza (2003, p. 25) aponta, as técnicas de computação evolutiva têm gerado resultados cada vez mais substanciais e complexos nos últimos 15 anos, em sincronia com o aumento rápido contínuo no poder de computação frequentemente referido como "Lei de Moore". Assim como a vida primitiva era muito simples em comparação com o que veio depois, os algoritmos genéticos de hoje, apesar dos resultados impressionantes que já produziram, provavelmente darão origem a coisas muito maiores no futuro.

  • Os AG ignoram a possibilidade de mutação ocorrer em todo o genoma
    Batten aparentemente não entende como os algoritmos genéticos funcionam, e ele demonstra isso fazendo este argumento. Ele afirma que na vida real, "as mutações ocorrem em todo o genoma, não apenas em um gene ou seção que especifica uma dada característica". Isso é verdade, mas quando ele diz que o mesmo não é verdade para os AG, ele está errado. Exatamente como em organismos vivos, os AG permitem que mutação e recombinação ocorram em qualquer lugar nos genomas de suas soluções candidatas; exatamente como em organismos vivos, os AG devem eliminar as mudanças deletérias enquanto selecionam simultaneamente as benéficas.

    Batten continua alegando que "o próprio programa é protegido contra mutações; apenas as sequências-alvo são mutadas", e se o próprio programa fosse mutado, ele entraria em colapso rapidamente. Esta crítica, no entanto, é irrelevante. Não há razão para que o programa governante de um AG deva ser mutado. O programa não faz parte do algoritmo genético; o programa é o que supervisiona o algoritmo genético e muta as soluções candidatas, que é o que o programador busca melhorar. O programa que executa o AG não é análogo à maquinaria reprodutiva de um organismo, uma comparação que Batten tenta fazer. Pelo contrário, é análogo às leis naturais invariantes que governam os ambientes em que os organismos vivos vivem e se reproduzem, e estas não são esperadas para mudar nem precisam ser "protegidas" contra isso.

  • Os AG ignoram os problemas da complexidade irredutível
    Usando o argumento de "complexidade irredutível" do criacionista da Terra antiga Michael Behe, Batten argumenta que "muitas características biológicas exigem que muitos componentes diferentes estejam presentes, funcionando juntos, para que a característica exista de alguma forma", enquanto isso não acontece nos Algoritmos Genéticos (AG).

    No entanto, é trivial demonstrar que tal alegação é falsa, pois os algoritmos genéticos produziram sistemas complexos irredutivelmente. Por exemplo, o circuito de reconhecimento de voz evoluído pelo Dr. Adrian Thompson (Davidson 1997) é composto por 37 portas lógicas principais. Cinco delas nem sequer estão conectadas ao resto do circuito, contudo todas as 37 são necessárias para que o circuito funcione; se qualquer uma delas for desconectada de sua fonte de alimentação, o sistema inteiro cessa de funcionar. Isso se encaixa na definição de Behe de um sistema complexo irredutivelmente e mostra que um processo evolutivo pode produzir tais coisas.

    Deve-se notar que este é o mesmo argumento que o primeiro, apenas apresentado em linguagem diferente, e, portanto, a refutação é a mesma. A complexidade irredutível não é um problema para a evolução, seja essa evolução ocorrendo em seres vivos na natureza ou em silício no chip de processador de um computador.

  • Os AG ignoram a poligenia, pleiotropia e outras complexidades genéticas
    Batten argumenta que os AG ignoram questões de poligenia (a determinação de uma característica por múltiplos genes), pleiotropia (um gene afetando múltiplas características) e genes dominantes e recessivos.

    No entanto, nenhuma dessas alegações é verdadeira. Os AG não ignoram a poligenia e a pleiotropia: essas propriedades são meramente permitidas para surgir naturalmente, em vez de serem codificadas deliberadamente. É óbvio que em qualquer sistema complexo e interdependente (ou seja, um sistema não linear), a alteração ou remoção de uma parte causará um efeito cascata de mudanças em toda a estrutura; portanto, os AG incorporam naturalmente a poligenia e a pleiotropia. "Na literatura de algoritmos genéticos, a interação de parâmetros é chamada de epistasia (um termo biológico para interação de genes). Quando há pouca ou nenhuma epistasia, os algoritmos de busca de mínimo [ou seja, escaladores de colinas --A.M.] performam melhor. Os algoritmos genéticos brilham quando a epistasia é média a alta..." (Haupt e Haupt 1998, p. 31, ênfase original).

    Da mesma forma, existem algumas implementações de algoritmos genéticos que possuem cromossomos diplóides e genes dominantes e recessivos (Goldberg 1989, p.150; Mitchell 1996, p.22). No entanto, aqueles que não possuem são simplesmente mais semelhantes a organismos haplóides, como bactérias, do que a organismos diplóides, como seres humanos. Como (por certas medidas) as bactérias estão entre os organismos mais bem-sucedidos neste planeta, tais AG permanecem um bom modelo de evolução.

  • As AGs não possuem múltiplos quadros de leitura
    Batten discute a existência de múltiplos quadros de leitura nos genomas de alguns seres vivos, nos quais as sequências de DNA codificam diferentes proteínas funcionais quando lidas em direções diferentes ou com deslocamentos de início diferentes. Ele afirma que "Criar uma AG para gerar tal codificação densa em informações pareceria ser impossível".

    Tal desafio exige uma resposta, e aqui está ela: Soule e Ball 2001. Neste artigo, os autores apresentam um algoritmo genético com múltiplos quadros de leitura e codificação densa, permitindo que ele armazene mais informações do que o comprimento total de seu genoma. Assim como os códons de três nucleotídeos que especificam aminoácidos nos genomas de organismos vivos, os códons desta AG eram strings binárias de cinco dígitos. Como os códons tinham cinco dígitos de comprimento, havia cinco quadros de leitura possíveis. A sequência 11111 serve como códon de "início" e 00000 como códon de "fim"; como os códons de início e fim poderiam ocorrer em qualquer lugar do genoma, o comprimento de cada indivíduo era variável. As regiões do cromossomo que não caíam entre pares início-fim eram ignoradas.

    A AG foi testada em quatro problemas clássicos de maximização de função. "Inicialmente, a maioria dos bits não participa de nenhum gene, ou seja, a maior parte de um cromossomo é não codificante. Novamente, isso ocorre porque nos indivíduos iniciais aleatórios há relativamente poucos pares de códons início-fim. No entanto, o número de bits que não participam diminui extremamente rapidamente." Durante o curso da execução, a AG pode aumentar o comprimento efetivo de seu genoma introduzindo novos códons de início em diferentes quadros de leitura. Ao final da execução, "a quantidade de sobreposição é bastante alta. Muitos bits estão participando de vários (e frequentemente todos os cinco) genes." Em todos os problemas de teste, a AG começou, em média, com 5 variáveis especificadas; ao final da execução, esse número havia aumentado para uma média de cerca de 25.

    Nos problemas de teste, a AG com múltiplos quadros de leitura produziu soluções significativamente melhores do que uma AG padrão em dois dos quatro problemas e melhores soluções médias nos dois restantes. Em um problema, a AG comprimiu com sucesso 625 bits totais de informações em um cromossomo de apenas 250 bits de comprimento, usando quadros de leitura alternativos. Os autores rotulam esse comportamento como "extremamente sofisticado" e concluem que "Esses dados mostram que uma AG pode usar quadros de leitura com sucesso apesar da complexidade adicional" e "É claro que uma AG pode introduzir novos 'genes' conforme necessário para resolver um problema dado, mesmo com as dificuldades impostas pelo uso de códons de início e fim e genes sobrepostos".

  • Os AGs têm objetivos preestabelecidos
    Como vários outros, essa objeção mostra que Batten não entende completamente o que é um algoritmo genético e como ele funciona. Ele argumenta que os AGs, ao contrário da evolução, têm objetivos predeterminados e especificados desde o início, e como exemplo disso, oferece o programa "gato" do Dr. Richard Dawkins.

    No entanto, o programa do gato não é um verdadeiro algoritmo genético e não é típico dos algoritmos genéticos, precisamente por essa razão. Não foi destinado a demonstrar o poder de resolução de problemas da evolução. Em vez disso, sua única intenção era mostrar a diferença entre seleção de um único passo (o infame "tornado soprando por um cemitério de lixo produzindo um 747") e seleção cumulativa, de múltiplos passos. Ele tinha sim um objetivo específico predeterminado desde o início. Verdadeiros algoritmos genéticos, no entanto, não têm.

    Em um sentido amplamente geral, os AGs têm sim um objetivo: nomeadamente, encontrar uma solução aceitável para um problema dado. Nesse mesmo sentido, a evolução também tem um objetivo: produzir organismos que estejam melhor adaptados ao seu ambiente e, portanto, experimentem maior sucesso reprodutivo. Mas assim como a evolução é um processo sem objetivos específicos, os AGs não especificam desde o início como um problema dado deve ser resolvido. A função de aptidão é meramente configurada para avaliar o quão bem uma solução candidata se comporta, sem especificar nenhuma maneira particular de como ela deve funcionar e sem emitir juízo sobre qualquer maneira que ela invente. A solução em si então emerge através de um processo de mutação e seleção.

    A próxima afirmação de Batten mostra claramente que ele não entende o que é um algoritmo genético. Ele afirma que "Talvez se o programador pudesse criar um programa que permitisse que qualquer coisa acontecesse e depois medisse a sobrevivabilidade dos 'organismos', isso poderia estar se aproximando do que a evolução é suposta fazer" - mas isso é exatamente como os algoritmos genéticos funcionam. Eles geram aleatoriamente soluções candidatas e as mutam aleatoriamente ao longo de muitas gerações. Nenhuma configuração é especificada com antecedência; como Batten diz, qualquer coisa é permitida que aconteça. Como John Koza (2003, p. 37) escreve, ecoando estranhamente as palavras de Batten: "Uma característica importante... é que a seleção [no programação genética] não é gananciosa. Indivíduos que são conhecidos por serem inferiores serão selecionados em certa medida. O melhor indivíduo na população não é garantido para ser selecionado. Além disso, o pior indivíduo na população não será necessariamente excluído. Qualquer coisa pode acontecer e nada é garantido." (Uma seção anterior discutiu esse ponto exatamente como uma das forças de um AG.) E, no entanto, ao aplicar um filtro seletivo a esses candidatos que mutam aleatoriamente, surgem soluções eficientes, complexas e poderosas para problemas difíceis, soluções que não foram projetadas por nenhuma inteligência e que muitas vezes podem igualar ou superar soluções que foram projetadas por humanos. A afirmação despreocupada de Batten de que "É claro que isso é impossível" é contradita frontalmente pela realidade.

  • GAs não geram realmente nova informação
    A crítica final de Batten é: "Com um GA particular, precisamos perguntar quanto da 'informação' gerada pelo programa está realmente especificada no programa, em vez de ser gerada de novo." Ele acusa os GAs de muitas vezes não fazerem mais do que encontrar a melhor maneira para certos módulos interagirem quando tanto os próprios módulos quanto as maneiras como podem interagir são especificados com antecedência.

    É difícil saber o que fazer com este argumento. Qualquer problema imaginável - termos em uma equação de cálculo, moléculas em uma célula, componentes de um motor, ações em um mercado financeiro - pode ser expresso em termos de módulos que interagem de maneiras dadas. Se tudo o que se tem são módulos não especificados que interagem de maneiras não especificadas, não há problema a ser resolvido. Isso significa que a solução para nenhum problema requer a geração de nova informação?

    Em relação à crítica de Batten sobre a informação contida na solução estar pré-especificada no problema, a melhor maneira de aliviar suas preocupações é apontar os muitos exemplos em que os GAs começam com populações iniciais geradas aleatoriamente que não são de forma alguma projetadas para ajudar o GA a resolver o problema. Alguns desses exemplos incluem: Graham-Rowe 2004; Davidson 1997; Assion et al. 1998; Giro, Cyrillo e Galvão 2002; Glen e Payne 1995; Chryssolouris e Subramaniam 2001; Williams, Crossley e Lang 2001; Robin et al. 2003; Andreou, Georgopoulos e Likothanassis 2002; Kewley e Embrechts 2002; Rizki, Zmuda e Tamburino 2002; e especialmente Koza et al. 1999 e Koza et al. 2003, que discutem o uso de programação genética para gerar 36 invenções competitivas com humanos em projeto de circuitos analógicos, biologia molecular, algoritmia, projeto de controladores industriais e outros campos, todos começando a partir de populações de candidatos iniciais gerados aleatoriamente.

    Concedido, alguns GAs começam com soluções geradas inteligentemente, que eles então buscam melhorar, mas isso é irrelevante: nesses casos, o objetivo não é apenas retornar a solução inicialmente inserida, mas melhorá-la pela produção de nova informação. De qualquer forma, mesmo que a situação inicial seja como Batten descreve, encontrar a maneira mais eficiente de vários módulos interagirem sob um conjunto dado de restrições pode ser uma tarefa longe de trivial, e cuja solução envolve uma quantidade considerável de nova informação: programação em aeroportos internacionais, por exemplo, ou linhas de montagem de fábricas, ou distribuição de barris entre armazéns e destilarias. Novamente, os GAs provaram ser eficazes na resolução de problemas cuja complexidade submergiria qualquer humano. À luz das múltiplas inovações e soluções inesperadamente eficazes surgidas dos GAs em muitos campos, a afirmação de Batten de que "A quantidade de nova informação gerada (por um GA) é geralmente bastante trivial" soa realmente vazia.

William Dembski

O recente livro do criacionista da Terra antiga, Dr. William Dembski, No Free Lunch: Why Specified Complexity Cannot Be Purchased Without Intelligence, é em grande parte dedicado ao tema de algoritmos evolutivos e como eles se relacionam com a evolução biológica. Em particular, o livro de Dembski trata de uma qualidade elusiva que ele chama de "complexidade especificada", a qual ele afirma estar presente em abundância em seres vivos, e que ele ainda afirma que os processos evolutivos são incapazes de gerar, deixando o "design" através de mecanismos não especificados por um "designer inteligente" não identificado como a única alternativa. Para reforçar seu caso, Dembski apela a uma classe de teoremas matemáticos conhecidos como os teoremas No Free Lunch, os quais ele afirma provar que os algoritmos evolutivos, em média, não fazem melhor do que uma busca cega.

Richard Wein escreveu uma refutação excelente e abrangente a Dembski, intitulada Não é um Almoço Grátis, mas uma Caixa de Chocolates, e seus pontos não serão reproduzidos aqui. Em vez disso, focarei no capítulo 4 do livro de Dembski, que trata em detalhes de algoritmos genéticos.

Dembski tem um argumento principal contra os Algoritmos Genéticos (AGs), que é desenvolvido em detalhes ao longo deste capítulo. Embora ele não negue que eles possam produzir resultados impressionantes — de fato, ele diz que há algo "estranhamente convincente e quase mágico" (p.221) na maneira como os AGs podem encontrar soluções que são diferentes de qualquer coisa projetada por seres humanos — ele argumenta que seu sucesso deve-se à complexidade especificada que é "contrabandeada" para eles por seus designers humanos e posteriormente incorporada nas soluções que produzem. "Em outras palavras, toda a complexidade especificada que obtemos de um algoritmo evolutivo primeiro tem de ser colocada em sua construção e na informação que guia o algoritmo. Portanto, os algoritmos evolutivos não geram ou criam complexidade especificada, mas apenas aproveitam a complexidade especificada já existente" (p.207).

O primeiro problema evidente no argumento de Dembski é este. Embora seu capítulo sobre algoritmos evolutivos tenha aproximadamente 50 páginas, as primeiras 30 delas discutem apenas o algoritmo do "gambá" do Dr. Richard Dawkins, que, como já discutido, não é uma verdadeira rede genética e não representa as redes genéticas. Os outros dois exemplos de Dembski - as antenas genéticas de fio torto de Edward Altshuler e Derek Linden e as redes neurais de xadrez de Kumar Chellapilla e David Fogel - são apresentados apenas nas últimas 10 páginas do capítulo e são discutidas por três páginas, combinadas. Esta é uma deficiência séria, considerando que o programa do "gambá" não representa a maioria dos trabalhos realizados no campo da computação evolutiva; no entanto, os argumentos de Dembski relacionados a ele serão analisados.

No que diz respeito ao programa da mangusta, Dembski afirma que "Dawkins e outros darwinistas usam este exemplo para ilustrar o poder dos algoritmos evolutivos" (p.182), e, novamente, "Darwinistas... estão bastante fascinados pelo exemplo METHINKS IT IS LIKE A WEASEL e o veem como ilustrando o poder dos algoritmos evolutivos para gerar complexidade especificada" (p.183). Isso é um homem de palha da criação de Dembski (não menos porque o livro de Dawkins foi escrito muito antes de Dembski ter cunhado aquele termo!). Eis o que Dawkins realmente diz sobre o propósito de seu programa:

"O que importa é a diferença entre o tempo gasto pela seleção acumulativa e o tempo que o mesmo computador, trabalhando no máximo à mesma taxa, levaria para alcançar a frase-alvo se fosse forçado a usar o outro procedimento de seleção de um único passo: cerca de um milhão de milhão de milhão de milhão de milhão de anos." (Dawkins 1996, p.49, ênfase original)

Em outras palavras, o programa da comadreja tinha como objetivo demonstrar a diferença entre dois tipos diferentes de seleção: seleção de um único passo, onde um resultado complexo é produzido por pura sorte em um único salto, e acumulativa seleção, onde um resultado complexo é construído pouco a pouco por meio de um processo de filtragem que preserva preferencialmente as melhorias. Nunca foi intendido ser uma simulação da evolução como um todo.

A seleção de um único passo é o processo absurdamente improvável frequentemente atacado na literatura criacionista ao compará-lo a um tornado varrendo um depósito de sucata e produzindo um avião 747, ou uma explosão em uma gráfica produzindo um dicionário. A seleção cumulativa é o que a evolução realmente utiliza. Usando a seleção de um único passo para alcançar um resultado funcional de qualquer complexidade significativa, seria necessário esperar, em média, muitas vezes a idade atual do universo. Usando a seleção cumulativa, no entanto, o mesmo resultado pode ser alcançado em um período de tempo relativamente muito curto. Demonstrar essa diferença foi o objetivo do programa da raposa de Dawkins, e esse foi o único objetivo desse programa. Em uma nota de rodapé deste capítulo, Dembski escreve: "É notável como o exemplo de Dawkins é reciclado sem qualquer indicação das dificuldades fundamentais que o acompanham" (p.230), mas são apenas os equívocos nas mentes de criacionistas como Dembski e Batten, que atacam o programa da raposa por não demonstrar algo para o qual nunca foi destinado, que dão origem a essas "dificuldades".

Diferentemente de todos os exemplos de algoritmos evolutivos discutidos neste ensaio, o programa da raposa realmente tem um único resultado prespecificado, e a qualidade das soluções que ele gera é julgada comparando-as explicitamente com esse resultado prespecificado. Portanto, Dembski está bastante correto ao afirmar que o programa da raposa não gera nova informação. No entanto, ele então faz um salto gigantesco e completamente injustificado ao extrapolar essa conclusão para todos os algoritmos evolutivos: "Como a única possibilidade que o algoritmo evolutivo de Dawkins pode alcançar, a sequência alvo na verdade tem complexidade mínima.... Algoritmos evolutivos são, portanto, incapazes de gerar verdadeira complexidade" (p.182). Mesmo Dembski parece reconhecer isso quando escreve: "...a maioria dos algoritmos evolutivos na literatura é programada para procurar um espaço de soluções possíveis para um problema até encontrar uma resposta - não, como Dawkins faz aqui, programando explicitamente a resposta neles com antecedência" (p.182). Mas então, após dar uma razão perfeitamente válida para que o programa da raposa não seja representativo dos AGs como um todo, ele inexplicavelmente prossegue para fazer precisamente essa generalização falaciosa!

Na realidade, o programa das comadreiras é significativamente diferente da maioria dos algoritmos genéticos e, portanto, o argumento por analogia de Dembski não se sustenta. Verdadeiros algoritmos evolutivos, como os exemplos discutidos neste ensaio, não simplesmente encontram seu caminho de volta para soluções já descobertas por outros métodos; em vez disso, são apresentados com problemas onde a solução ótima não é conhecida com antecedência e são convidados a descobrir essa solução por conta própria. De fato, se os algoritmos genéticos não pudessem fazer nada mais do que redescobrir soluções já programadas neles, qual seria o ponto de usá-los? Seria um exercício de redundância fazê-lo. No entanto, o amplo interesse científico (e comercial) em AGs mostra que há muito mais substância neles do que o exemplo bastante trivial que Dembski tenta reduzir todo esse campo.

Após ter estabelecido e depois derrubado este homem de palha, Dembski passa para sua próxima linha de argumento: que a complexidade especificada exibida pelos resultados de algoritmos evolutivos mais representativos tem sido, como o programa do texugo, "contrabandeada" pelos designers do algoritmo. "Mas invariavelmente encontramos que, quando a complexidade especificada parece ser gerada de graça, ela na verdade foi pré-carregada, contrabandeada ou escondida da vista" (p.204). Dembski sugere que o local de "esconderijo" mais comum da complexidade especificada está na função de aptidão do GA. "O que o [algoritmo evolutivo] fez foi aproveitar a complexidade especificada inerente à função de aptidão e usá-la na busca e, em seguida, na localização do alvo..." (p.194). Dembski prossegue argumentando que, antes que um AE possa buscar uma paisagem de aptidão dada por uma solução, algum mecanismo deve primeiro ser empregado para selecionar aquela paisagem de aptidão do que ele chama de espaço de fases de todas as paisagens de aptidão possíveis, e se aquele mecanismo for igualmente evolutivo, algum outro mecanismo deve primeiro ser empregado para selecionar sua função de aptidão de um espaço de fases ainda maior, e assim por diante. Dembski conclui que a única maneira de parar essa regressão infinita é através da inteligência, que ele sustenta ter alguma capacidade irredutível e misteriosa de selecionar uma função de aptidão de um espaço de fases dado sem recurso a espaços de fases de ordem superior. "Existe apenas um gerador conhecido de complexidade especificada, e esse é a inteligência" (p.207).

Dembski está correto ao escrever que a função de aptidão "orienta um algoritmo evolutivo para o alvo" (p.192). No entanto, ele está incorreto ao afirmar que selecionar a função de aptidão correta é um processo que requer a geração de ainda mais complexidade especificada do que o próprio AE produz. Como Koza (1999, p. 39) escreve, a função de aptidão diz a um algoritmo evolutivo "o que precisa ser feito", não "como fazê-lo". Diferentemente do exemplo não representativo do programa do texugo, a função de aptidão de um AE tipicamente não especifica qualquer forma particular que a solução deve assumir, e, portanto, não pode ser dito que ela contribui "complexidade especificada" para a solução evoluída em qualquer sentido significativo.

Um exemplo ilustrará o ponto com maior detalhe. Dembski afirma que, no experimento de damas de Chellapilla e Fogel, a sua escolha de manter o critério de vitória constante de jogo para jogo "introduziu uma enorme quantidade de complexidade especificada" (p.223). É certamente verdade que o produto final deste processo exibiu uma grande quantidade de complexidade especificada (seja como se definir esse termo). Mas é verdade que a medida de aptidão escolhida continha tanta complexidade especificada? Eis o que Chellapilla e Fogel dizem na verdade:

"Para apreciar o nível de jogo que foi alcançado, pode ser útil considerar o seguinte experimento mental. Suponha que você seja convidado a jogar um jogo em um tabuleiro de oito por oito casas com cores alternadas. Há 12 peças em cada lado dispostas de uma maneira específica para começar o jogo. Você é informado das regras de como as peças se movem (ou seja, diagonalmente, saltos forçados, reis) e de que a diferença de peças está disponível como um recurso. Você não é, no entanto, informado se essa diferença é favorável ou desfavorável (existe uma versão de damas chamada 'damas suicidas', onde o objetivo é 'perder' o mais rápido possível) ou se é até mesmo uma informação valiosa. Mais importante, você não é informado do objetivo do jogo. Você simplesmente faz movimentos e, em algum momento, um observador externo declara o jogo encerrado. Eles não fornecem, no entanto, feedback sobre se você ganhou, perdeu ou empatou. Os únicos dados que você recebe vêm após um mínimo de cinco jogos semelhantes e são oferecidos na forma de uma pontuação geral. Assim, você não pode saber com certeza quais jogos contribuíram para o resultado geral ou em que grau. Seu desafio é induzir os movimentos apropriados em cada jogo baseado apenas neste nível grosseiro de feedback." (Chellapilla e Fogel 2001, p.427)

Excede os limites do absurdo que Dembski afirme que esta medida de aptidão inseriu uma "imensa" quantidade de complexidade especificada. Se uma pessoa que nunca ouviu falar de damas fosse dada a mesma informação e, meses depois, descobríssemos que ela se tornara uma especialista internacionalmente classificada em damas, deveríamos concluir que a complexidade especificada foi gerada?

Dembski afirma que para refutar seu argumento, "é necessário demonstrar que encontrar a informação que guia um algoritmo evolutivo até um alvo é substancialmente mais fácil do que encontrar o alvo diretamente por meio de uma busca cega" (p.204). Eu sustento que este é exatamente o caso. Intuitivamente, não deve ser surpreendente que a função de aptidão contenha menos informação do que a solução evoluída. Esta é precisamente a razão pela qual os AGs (algoritmos genéticos) encontraram tão ampla aplicação: é mais fácil (requer menos informação) escrever uma função de aptidão que meça o quão boa é uma solução, do que projetar uma boa solução do zero.

Em termos mais informais, considere os dois exemplos de Dembski: a antena genética de fio torto e a rede neural evoluída para jogar damas chamada Anaconda. É necessário um grande volume de informações detalhadas sobre o jogo de damas para desenvolver uma estratégia vencedora (considere o Chinook e sua enorme biblioteca de finais de jogo). No entanto, não é necessário igualmente detalhado para reconhecer tal estratégia quando se a observa: tudo o que precisamos observar é que essa estratégia consistentemente derrota seus oponentes. Da mesma forma, uma pessoa que nada soubesse sobre como projetar uma antena que irradie uniformemente sobre uma região hemisférica em uma faixa de frequência dada ainda poderia testar tal antena e verificar que ela funciona conforme o previsto. Em ambos os casos, determinar o que constitui alta aptidão é muito mais fácil (requer menos informações) do que descobrir como alcançar alta aptidão.

Admitindo, mesmo que escolher uma função de aptidão para um problema específico exija menos informações do que resolver o problema definido por essa função de aptidão, ainda é necessário alguma informação para especificar a função de aptidão em primeiro lugar, e é uma questão legítima perguntar de onde vem essa informação inicial. Dembski pode ainda perguntar sobre a origem da inteligência humana que nos permite decidir resolver um problema em vez de outro, ou sobre a origem das leis naturais do cosmos que tornam possível a existência e o florescimento da vida e a ocorrência da evolução. São questões válidas, e Dembski tem o direito de se questionar sobre elas. No entanto, até este ponto - aparentemente não percebido por Dembski mesmo - ele já se afastou de seu argumento inicial. Ele não está mais afirmando que a evolução não pode acontecer; em vez disso, ele está essencialmente perguntando por que vivemos em um universo onde a evolução pode acontecer. Em outras palavras, o que Dembski não parece perceber é que a conclusão lógica de seu argumento é evolução teísta. É totalmente compatível com um Deus que (como muitos cristãos, incluindo o biólogo evolutivo Kenneth Miller, acreditam) usou a evolução como sua ferramenta criativa e estabeleceu o universo de tal forma a torná-lo não apenas provável, mas certo.

Concluirei esclarecendo algumas concepções errôneas adicionais e menores no capítulo 4 de No Free Lunch. Para começar, embora Dembski, ao contrário de Batten, esteja claramente ciente do campo da otimização multiobjetivo, ele afirma erroneamente que "até que alguma forma de unicidade seja alcançada, a otimização não pode começar" (p.186). A discussão deste ensaio sobre algoritmos genéticos de múltiplos objetivos demonstra o erro disso. Talvez outras técnicas de design tenham essa restrição, mas uma das virtudes dos AGs é precisamente que eles podem fazer concessões e otimizar vários objetivos mutuamente exclusivos simultaneamente, e os supervisores humanos podem então escolher qual solução melhor atende aos seus objetivos do grupo final de soluções Pareto-ótimas. Nenhum método de combinar múltiplos critérios em um é necessário.

Dembski também afirma que as AG "parecem menos aptas a construir sistemas integrados que exigem múltiplas partes para alcançar funções novas" (p.237). Os muitos exemplos detalhados neste ensaio (particularmente o uso de John Koza da programação genética para projetar circuitos analógicos complexos) mostram que essa alegação também é falsa.

Finalmente, Dembski menciona que a INFORMS, a organização profissional da comunidade de pesquisa operacional, presta pouca atenção às GA, e isso "é motivo para ceticismo quanto ao escopo e poder gerais da técnica" (p.237). No entanto, apenas porque uma sociedade científica específica não está fazendo uso generalizado de GA não significa que tais usos não sejam generalizados em outros lugares ou em geral, e este ensaio buscou mostrar que este é de fato o caso. Técnicas evolutivas encontraram uma grande variedade de usos em praticamente qualquer campo da ciência que se queira nomear, bem como entre muitas empresas no setor comercial. Aqui está uma lista parcial:

Em contraste, dada a escassez de descobertas científicas e pesquisas estimuladas pelo design inteligente, Dembski está em uma posição precária para reclamar sobre a falta de aplicação prática. O design inteligente é uma hipótese vazia, que não nos diz nada além de "Algo designer fez algo, de alguma forma, em algum momento, para causar este resultado." Em contraste, este ensaio demonstrou esperançosamente que a evolução é uma estratégia de resolução de problemas rica em aplicações práticas.

Conclusão
Topo

Até mesmo os criacionistas acham impossível negar que a combinação de mutação e seleção natural pode produzir adaptação. No entanto, eles ainda tentam justificar sua rejeição da evolução dividindo o processo evolutivo em duas categorias - "microevolução" e "macroevolução" - e argumentando que apenas a segunda é controversa, e que qualquer mudança evolutiva que observamos é apenas um exemplo da primeira.

Agora, microevolução e macroevolução são termos que têm significado para biólogos; são definidos, respectivamente, como evolução abaixo do nível de espécie e evolução no ou acima do nível de espécie. Mas a diferença crucial entre a forma como criacionistas usam esses termos e a forma como cientistas os usam é que cientistas reconhecem que esses dois são fundamentalmente o mesmo processo com os mesmos mecanismos, operando apenas em escalas diferentes. Criacionistas, no entanto, são forçados a postular algum tipo de lacuna intransponível que separe os dois, a fim de poderem negar que os processos de mudança e adaptação que vemos operando no presente podem ser extrapolados para produzir toda a diversidade observada no mundo vivo.

No entanto, os algoritmos genéticos tornam essa visão insustentável ao demonstrar a fundamental continuidade do processo evolutivo. Tome, por exemplo, um problema que consiste em programar um circuito para discriminar entre um tom de 1 quilohertz e um de 10 quilohertz, e responder respectivamente com saídas constantes de 0 e 5 volts. Digamos que temos uma solução candidata que pode discriminar com precisão entre os dois tons, mas suas saídas não são totalmente constantes como exigido; elas produzem pequenas formas de onda em vez da voltagem invariável necessária. Presumivelmente, de acordo com a visão criacionista, mudar esse circuito de seu estado atual para a solução perfeita seria "microevolução", uma pequena mudança dentro da capacidade da mutação e da seleção para produzir. Mas certamente, um criacionista argumentaria, chegar a esse mesmo estado final a partir de uma disposição inicial completamente aleatória de componentes seria "macroevolução" e além do alcance de um processo evolutivo. No entanto, os algoritmos genéticos foram capazes de realizar ambos, evoluindo o sistema de uma disposição aleatória para a solução quase perfeita e finalmente para a solução perfeita e ótima. Em nenhum passo do caminho surgiu uma dificuldade insolúvel ou uma lacuna que não pudesse ser transponida. Em nenhum ponto foi necessária intervenção humana para montar um núcleo de componentes complexidade irredutível (apesar de o produto final conter tal coisa) ou para "guiar" o sistema em evolução sobre um pico difícil. O circuito evoluiu, sem qualquer orientação inteligente, de um estado completamente aleatório e não funcional para um estado altamente complexo, eficiente e ótimo. Como isso não pode ser uma demonstração experimental convincente do poder da evolução?

Diz-se que a evolução cultural humana superou a biológica - que, como espécie, chegamos a um ponto em que somos capazes de controlar conscientemente nossa sociedade, nosso ambiente e até mesmo nossos genes em grau suficiente para tornar o processo evolutivo irrelevante. Diz-se que os caprichos culturais de nossa sociedade em rápida mudança, e não o ritmo comparativamente lento como o da glaciação da mutação genética e da seleção natural, é o que determina a aptidão hoje. Num certo sentido, isso pode ser bem verdade.

Porém, em outro sentido, nada poderia estar mais longe da verdade. A evolução é um processo de resolução de problemas cujo poder estamos apenas começando a compreender e explorar; apesar disso, já está em ação ao nosso redor, moldando nossa tecnologia e melhorando nossas vidas, e no futuro, esses usos apenas se multiplicarão. Sem um entendimento detalhado do processo evolutivo, nenhum dos inúmeros avanços que devemos às algoritmos genéticos teria sido possível. Há uma lição aqui para aqueles que negam o poder da evolução, bem como para aqueles que negam que o conhecimento dela tenha qualquer benefício prático. Por incrível que pareça, a evolução funciona. Como disse o poeta Lord Byron: "'É estranho, mas verdadeiro; pois a verdade é sempre estranha, mais estranha que a ficção."

Referências e recursos
Topo

"Aprendizagem Adaptativa: Voando pelos Céus Inteligentes." Wired, vol.10, no.3 (março de 2002). Disponível online em http://www.wired.com/wired/archive/10.03/everywhere.html?pg=2.

Altshuler, Edward e Derek Linden. "Projeto de uma antena de fio usando um algoritmo genético." Journal of Electronic Defense, vol.20, no.7, p.50-52 (julho 1997).

Andre, David and Astro Teller. "Evolving team Darwin United." In RoboCup-98: Copa do Mundo de Futebol Robô II, Minoru Asada and Hiroaki Kitano (eds). Lecture Notes in Computer Science, vol.1604, p.346-352. Springer-Verlag, 1999.

Andreou, Andreas, Efstratios Georgopoulos e Spiridon Likothanassis. "Previsão de taxas de câmbio: um algoritmo híbrido baseado em redes neurais adaptativas otimizadas geneticamente." Economia Computacional, vol.20, no.3, p.191-210 (dezembro de 2002).

Ashley, Steven. "Engineous explora o espaço de projeto." Engenharia Mecânica, fevereiro de 1992, p.49-52.

Assion, A., T. Baumert, M. Bergt, T. Brixner, B. Kiefer, V. Seyfried, M. Strehle e G. Gerber. "Controle de reações químicas por pulsos de laser femtossegundo de fase moldada otimizados por feedback." Science, vol.282, p.919-922 (30 de outubro de 1998).

Au, Wai-Ho, Keith Chan, e Xin Yao. "Um novo algoritmo de mineração de dados evolutivo com aplicações à previsão de churn." IEEE Transactions on Evolutionary Computation, vol.7, no.6, p.532-545 (dezembro 2003).

Beasley, J.E., J. Sonander e P. Havelock. "Agendamento de aterrissagens de aeronaves em Heathrow, Londres usando uma heurística de população." Journal of the Operational Research Society, vol.52, no.5, p.483-493 (maio 2001).

Begley, Sharon e Gregory Beals. "Software au naturel." Newsweek, 8 de maio de 1995, p.70.

Benini, Ernesto e Andrea Toffolo. "Projeto ótimo de turbinas eólicas de eixo horizontal usando teoria de elementos de pá e computação evolutiva." Journal of Solar Energy Engineering, vol.124, no.4, p.357-363 (novembro 2002).

Burke, E.K. e J.P. Newall. "Um algoritmo evolutivo multietapas para o problema de horários." IEEE Transactions on Evolutionary Computation, vol.3, no.1, p.63-74 (abril 1999).

Charbonneau, Paul. "Algoritmos genéticos em astronomia e astrofísica." The Astrophysical Journal Supplement Series, vol.101, p.309-334 (dezembro de 1995).

Chellapilla, Kumar e David Fogel. "Desenvolvendo um programa de xadrez especialista sem utilizar conhecimento humano." IEEE Transactions on Evolutionary Computation, vol.5, no.4, p.422-428 (agosto de 2001). Disponível online em http://www.natural-selection.com/NSIPublicationsOnline.htm.

Chellapilla, Kumar e David Fogel. "Anaconda derrota Hoyle 6-0: um estudo de caso competindo um programa de damas evoluído contra software comercialmente disponível." Em Proceedings of the 2000 Congress on Evolutionary Computation, p.857-863. IEEE Press, 2000. Disponível online em http://www.natural-selection.com/NSIPublicationsOnline.htm.

Chellapilla, Kumar e David Fogel. "Verificando a classificação de especialista do Anaconda competindo contra o Chinook: experimentos em co-evolução de um jogador de damas neural." Neurocomputing, vol.42, no.1-4, p.69-86 (janeiro 2002).

Chryssolouris, George e Velusamy Subramaniam. "Agendamento dinâmico de oficinas de manufatura usando algoritmos genéticos." Journal of Intelligent Manufacturing, vol.12, no.3, p.281-293 (junho de 2001).

Coale, Kristi. "Darwin em uma caixa." Wired News, 14 de julho de 1997. Disponível online em http://www.wired.com/news/technology/0,1282,5152,00.html.

Coello, Carlos. "Uma revisão atualizada de técnicas de otimização multiobjetivo baseadas em GA." ACM Computing Surveys, vol.32, no.2, p.109-143 (junho 2000).

Davidson, Clive. "Criaturas de silício primordial." New Scientist, vol.156, no.2108, p.30-35 (15 de novembro de 1997). Disponível online em http://www.newscientist.com/hottopics/ai/primordial.jsp.

Dawkins, Richard. O Relógio Cego: Por que as Evidências da Evolução Revelam um Universo Sem Design. W.W. Norton, 1996.

Dembski, William. No Free Lunch: Por que a Complexidade Especificada Não Pode Ser Adquirida Sem Inteligência. Rowman & Littlefield, 2002.

Fleming, Peter e R.C. Purshouse. "Algoritmos evolutivos em engenharia de sistemas de controle: uma revisão." Control Engineering Practice, vol.10, p.1223-1241 (2002).

Fonseca, Carlos and Peter Fleming. "An overview of evolutionary algorithms in multiobjective optimization." Computação Evolutiva, vol.3, no.1, p.1-16 (1995).

Forrest, Stephanie. "Algoritmos genéticos: princípios da seleção natural aplicados à computação." Science, vol.261, p.872-878 (1993).

Gibbs, W. Wayt. "Programando com o caldo primordial." Scientific American, outubro de 1996, p.48-50.

Gillet, Valerie. "Abordagens baseadas em reagentes e produtos para o desenho de bibliotecas combinatórias." Journal of Computer-Aided Molecular Design, vol.16, p.371-380 (2002).

Giro, R., M. Cyrillo e D.S. Galvão. "Desenvolvendo polímeros condutores usando algoritmos genéticos." Chemical Physics Letters, vol.366, no.1-2, p.170-175 (25 de novembro de 2002).

Glen, R.C. e A.W.R. Payne. "Um algoritmo genético para a geração automatizada de moléculas dentro de restrições." Journal of Computer-Aided Molecular Design, vol.9, p.181-202 (1995).

Goldberg, David. Algoritmos Genéticos em Busca, Otimização e Aprendizado de Máquina. Addison-Wesley, 1989.

Graham-Rowe, Duncan. "O rádio emerge da sopa eletrônica." New Scientist, vol.175, no.2358, p.19 (31 de agosto de 2002). Disponível online em http://www.newscientist.com/news/news.jsp?id=ns99992732.

  • Veja também: Bird, Jon e Paul Layzell. "O rádio evoluído e suas implicações para a modelagem da evolução de sensores novos." Em Proceedings of the 2002 Congress on Evolutionary Computation, p.1836-1841.

Graham-Rowe, Duncan. "Circuito eletrônico 'evolui' a partir de cristais líquidos." New Scientist, vol.181, no.2440, p.21 (27 de março de 2004).

Haas, O.C.L., K.J. Burnham e J.A. Mills. "On improving physical selectivity in the treatment of cancer: A systems modelling and optimisation approach." Control Engineering Practice, vol.5, no.12, p.1739-1745 (December 1997).

Hanne, Thomas. "Otimização multiobjetivo global usando algoritmos evolutivos." Journal of Heuristics, vol.6, no.3, p.347-360 (Agosto 2000).

Haupt, Randy e Sue Ellen Haupt. Algoritmos Genéticos Práticos. John Wiley & Sons, 1998.

He, L. e N. Mort. "Algoritmos genéticos híbridos para roteamento de rotas de backup em redes de telecomunicações." BT Technology Journal, vol.18, no.4, p. 42-50 (Out 2000).

Holland, John. "Algoritmos genéticos." Scientific American, julho de 1992, p. 66-72.

Hughes, Evan e Maurice Leyland. "Usando múltiplos algoritmos genéticos para gerar modelos de espalhadores de radar." IEEE Transactions on Evolutionary Computation, vol.4, no.2, p.147-163 (julho 2000).

Jensen, Mikkel. "Gerando agendas flexíveis e robustas para oficinas de produção usando algoritmos genéticos." IEEE Transactions on Evolutionary Computation, vol.7, no.3, p.275-288 (junho 2003).

Kewley, Robert e Mark Embrechts. "Sistema de planejamento tático militar computacional." IEEE Transactions on Systems, Man and Cybernetics, Parte C - Aplicações e Revisões, vol.32, no.2, p.161-171 (maio 2002).

Kirkpatrick, S., C.D. Gelatt e M.P. Vecchi. "Otimização por recozimento simulado." Science, vol.220, p.671-678 (1983).

Koza, John, Forest Bennett, David Andre e Martin Keane. Programação Genética III: Invenção Darwiniana e Resolução de Problemas. Morgan Kaufmann Publishers, 1999.

Koza, John, Martin Keane, Matthew Streeter, William Mydlowec, Jessen Yu and Guido Lanza. Programação Genética IV: Inteligência de Máquina Competitiva com Humanos. Kluwer Academic Publishers, 2003.
  • Veja também: Koza, John, Martin Keane e Matthew Streeter. "Invenções evolutivas." Scientific American, fevereiro de 2003, p. 52-59.

Keane, A.J. e S.M. Brown. "O design de um boom de satélite com desempenho de vibração aprimorado usando técnicas de algoritmos genéticos." Em Computação Adaptativa no Design de Engenharia e Controle '96 - Atas da Segunda Conferência Internacional, I.C. Parmee (ed), p.107-113. Universidade de Plymouth, 1996.

Lee, Yonggon e Stanislaw H. Zak. "Designing a genetic neural fuzzy antilock-brake-system controller." IEEE Transactions on Evolutionary Computation, vol.6, no.2, p.198-211 (abril 2002).

Lemley, Brad. "Máquinas que pensam." Discover, Janeiro 2001, p.75-79.

Mahfoud, Sam e Ganesh Mani. "Previsão financeira usando algoritmos genéticos." Inteligência Artificial Aplicada, vol.10, no.6, p.543-565 (1996).

Mitchell, Melanie. Uma Introdução a Algoritmos Genéticos. MIT Press, 1996.

Naik, Gautam. "De volta a Darwin: sob a luz do sol e nas células, a ciência busca respostas para quebra-cabeças de alta tecnologia." The Wall Street Journal, 16 de janeiro de 1996, p. A1.

Obayashi, Shigeru, Daisuke Sasaki, Yukihiro Takeguchi, e Naoki Hirose. "Computação evolutiva multiobjetivo para otimização da forma de asas supersônicas." IEEE Transactions on Evolutionary Computation, vol.4, no.2, p.182-187 (julho 2000).

Petzinger, Thomas. "Na Deere sabem que um cientista louco pode ser o maior ativo de uma empresa." The Wall Street Journal, 14 de julho de 1995, p.B1.

Porto, Vincent, David Fogel e Lawrence Fogel. "Métodos alternativos de treinamento de redes neurais." IEEE Expert, vol.10, no.3, p.16-22 (junho de 1995).

Rao, Srikumar. "Evolução à velocidade da luz." Forbes, vol.161, no.1, p.82-83 (12 de janeiro de 1998).

Rizki, Mateen, Michael Zmuda e Louis Tamburino. "Sistemas de reconhecimento de padrões em evolução." IEEE Transactions on Evolutionary Computation, vol.6, no.6, p.594-609 (dezembro de 2002).

Robin, Franck, Andrea Orzati, Esteban Moreno, Otte Homan, e Werner Bachtold. "Simulação e otimização evolutiva da litografia por feixe de elétrons com algoritmos genéticos e simplex-downhill." IEEE Transactions on Evolutionary Computation, vol.7, no.1, p.69-82 (fevereiro de 2003).

Sagan, Carl. O Cérebro de Broca: Reflexões sobre o Romance da Ciência. Ballantine, 1979.

Sambridge, Malcolm e Kerry Gallagher. "Localização do hipocentro de terremotos usando algoritmos genéticos." Bulletin da Sociedade Sismológica da América, vol.83, no.5, p.1467-1491 (outubro de 1993).

Sasaki, Daisuke, Masashi Morikawa, Shigeru Obayashi e Kazuhiro Nakahashi. "Otimização aerodinâmica de formas de asas supersônicas por meio de algoritmos genéticos multiobjetivo com intervalo adaptativo." Em Otimização Evolutiva Multi-Critério: Primeira Conferência Internacional, EMO 2001, Zurique, Suíça, março de 2001: Atas, K. Deb, L. Theile, C. Coello, D. Corne e E. Zitler (orgs). Lecture Notes in Computer Science, vol.1993, p.639-652. Springer-Verlag, 2001.

Sato, S., K. Otori, A. Takizawa, H. Sakai, Y. Ando e H. Kawamura. "Aplicando algoritmos genéticos ao projeto ótimo de uma sala de concertos." Journal of Sound and Vibration, vol.258, no.3, p. 517-526 (2002).

Schechter, Bruce. "Colocar uma visão darwiniana no motor a diesel." The New York Times, 19 de setembro de 2000, p. F3.

Srinivas, N. e Kalyanmoy Deb. "Otimização multiobjetivo usando ordenamento não dominado em algoritmos genéticos." Computação Evolutiva, vol.2, no.3, p.221-248 (Outono 1994).

Soule, Terrence e Amy Ball. "Um algoritmo genético com múltiplos quadros de leitura." Em GECCO-2001: Proceedings of the Genetic and Evolutionary Computation Conference, Lee Spector e Eric Goodman (eds). Morgan Kaufmann, 2001. Disponível online em http://www.cs.uidaho.edu/~tsoule/research/papers.html.

Tang, K.S., K.F. Man, S. Kwong e Q. He. "Algoritmos genéticos e suas aplicações." IEEE Signal Processing Magazine, vol.13, no.6, p.22-37 (novembro de 1996).

Weismann, Dirk, Ulrich Hammel, e Thomas Bäck. "Projeto robusto de revestimentos ópticos multicamada por meio de algoritmos evolutivos." IEEE Transactions on Computação Evolutiva, vol.2, no.4, p.162-167 (Novembro 1998).

Williams, Edwin, William Crossley e Thomas Lang. "Estudos de comércio de tempo médio e máximo de retorno para constelações de satélites usando um algoritmo genético multiobjetivo." Journal of the Astronautical Sciences, vol.49, no.3, p.385-400 (julho-setembro 2001).

Zitzler, Eckart e Lothar Thiele. "Algoritmos evolutivos multiobjetivo: um estudo de caso comparativo e a abordagem Strength Pareto." IEEE Transactions on Evolutionary Computation, vol.3, no.4, p.257-271 (novembro de 1999).