Algoritmo genético

O que é isso?

A evolução natural pode ser modelada como um jogo, no qual as recompensas para um organismo que joga um bom jogo da vida são a transmissão de seu material genético para seus sucessores e sua sobrevivência contínua. ^[2] Na evolução natural, o desempenho de um indivíduo depende de com quem ele trabalha e com quem compete, bem como do meio ambiente. Os algoritmos genéticos são uma simulação de seleção natural sobre uma população de candidatos a soluções para um problema de otimização (cromossomos, indivíduos, criaturas, ou fenótipos).

Os candidatos são avaliados e cruzados na tentativa de encontrar boas soluções. Tais soluções podem levar muito tempo e não são óbvias para um humano. Uma fase evolucionária é iniciada com uma população de seres gerados aleatoriamente. Em cada geração, é avaliada a aptidão de cada indivíduo da população. Alguns são selecionados aleatoriamente a partir da população atual (com base em sua aptidão) e modificados (recombinados e possivelmente mutantes aleatórios) para formar uma nova população. O ciclo se repete com esta nova população. O algoritmo termina ou após um determinado número de gerações ter passado, ou após um bom nível de aptidão física ter sido alcançado para a população. Se o algoritmo terminou devido a ter alcançado um número máximo de gerações, isso não significa necessariamente que um bom nível de aptidão física tenha sido obtido.

Programando isto em um computador

O pseudo-código é:

1. Inicialização: Algumas soluções possíveis são criadas; muitas vezes estas terão valores aleatórios
2. Avaliação: Uma função de condicionamento físico pontua cada solução; a pontuação será um número que diz o quão bem esta solução resolve o problema.
3. Os passos seguintes são executados até que a exigência de parar seja atendida:
1. Seleção: Escolha as soluções/indivíduos para a próxima iteração
2. Recombinação: Combinar as soluções escolhidas
3. Mutação: Mudar aleatoriamente as soluções recém-criadas
4. Avaliação: Aplicar a função fitness, ver passo 2.
5. Se a exigência de parar não for atendida, reinicie com a etapa de seleção.

Exemplo

A descrição acima é abstrata. Um exemplo concreto ajuda.

Aplicações

Em geral

Algoritmos genéticos são bons para resolver problemas que incluem a calendarização e o agendamento. Eles também têm sido aplicados à engenharia. Eles são freqüentemente usados para resolver problemas de otimização global.

Como regra geral, os algoritmos genéticos podem ser úteis em domínios problemáticos que têm uma paisagem de aptidão complexa, pois a mistura é projetada para afastar a população da optima local na qual um algoritmo tradicional de escalada de colinas pode ficar preso. Os operadores de crossover comumente usados não podem mudar nenhuma população uniforme. Só a mutação pode proporcionar ergodicidade do processo geral do algoritmo genético (visto como uma cadeia de Markov).

Exemplos de problemas resolvidos por algoritmos genéticos incluem: espelhos projetados para canalizar a luz solar para um coletor solar, antenas projetadas para captar sinais de rádio no espaço, métodos de caminhada para figuras de computador, projeto ideal de corpos aerodinâmicos em campos de fluxo complexos

Em seu Algorithm Design Manual, Skiena aconselha contra algoritmos genéticos para qualquer tarefa: "Não é natural modelar aplicações em termos de operadores genéticos como mutação e crossover em cadeias de bits". A pseudobiologia acrescenta outro nível de complexidade entre você e seu problema". Em segundo lugar, os algoritmos genéticos levam muito tempo para resolver problemas não triviais. [...] A analogia com a evolução - onde um progresso significativo requer [sic] milhões de anos - pode ser bastante apropriada. [...] Nunca encontrei nenhum problema em que os algoritmos genéticos me parecessem a maneira correta de atacá-lo. Além disso, nunca vi nenhum resultado computacional relatado usando algoritmos genéticos que me tenham impressionado favoravelmente. Limite-se a simular um recozimento para suas necessidades de vodu de busca heurística".

Jogos de tabuleiro

Os jogos de tabuleiro são uma parte muito relevante da área de algoritmos genéticos como aplicados a problemas de teoria de jogos. Muito do trabalho inicial sobre inteligência computacional e jogos foi direcionado para jogos de tabuleiro clássicos, tais como tic-tac-toe,^[3] xadrez, e damas. ^[4] Os jogos de tabuleiro podem agora, na maioria dos casos, ser jogados por um computador a um nível superior ao dos melhores humanos, mesmo com técnicas cegas de busca exaustiva. Go é uma notável exceção a esta tendência, e até agora tem resistido a ataques de máquinas. Os melhores jogadores de computador Go agora jogam no nível de um bom novato. ^[5][6] Diz-se que a estratégia Go depende muito do reconhecimento de padrões, e não apenas da análise lógica, como no xadrez e em outros jogos mais independentes de peças. O enorme fator de ramificação eficaz necessário para encontrar soluções de alta qualidade restringe fortemente a aparência que pode ser usada dentro de uma busca de sequência de movimentos.

Jogos de computador

O algoritmo genético pode ser usado em jogos de computador para criar inteligência artificial (o computador joga contra você). Isto permite uma experiência de jogo mais realista; se um jogador humano pode encontrar uma seqüência de passos que sempre leva ao sucesso mesmo quando repetido em jogos diferentes, não pode restar nenhum desafio. Por outro lado, se uma técnica de aprendizagem como um algoritmo genético para um estrategista puder evitar a repetição de erros passados, o jogo terá mais jogabilidade.

Os algoritmos genéticos exigem as seguintes partes:

• Um método para representar o desafio em termos da solução (por exemplo, rotear soldados em um ataque em um jogo de estratégia)
• Uma função de adequação ou avaliação a fim de determinar a qualidade de uma instância (por exemplo, uma medida do dano causado a um oponente em tal ataque).

A função de aptidão aceita uma instanciação mutante de uma entidade e mede sua qualidade. Esta função é personalizada para o domínio do problema. Em muitos casos, particularmente aqueles que envolvem otimização de código, a função de adequação pode ser simplesmente uma função de temporização do sistema. Uma vez definida uma representação genética e função de adequação, um algoritmo genético instanciará os candidatos iniciais como descrito anteriormente, e então melhorará através da aplicação repetitiva de operadores de mutação, cruzamento, inversão e seleção (conforme definido de acordo com o domínio do problema).

Limitações

Há limitações no uso de um algoritmo genético em comparação com algoritmos alternativos de otimização:

• A avaliação da função de aptidão repetida para problemas complexos é freqüentemente o segmento mais limitante dos algoritmos evolutivos artificiais. Encontrar a solução ótima para problemas complexos muitas vezes requer avaliações muito caras da função de aptidão física. Em problemas do mundo real, tais como problemas de otimização estrutural, uma única avaliação de função pode requerer de várias horas a vários dias de simulação completa. Os métodos típicos de otimização não podem lidar com tais tipos de problemas. Muitas vezes é necessário usar aproximação, pois o cálculo da solução exata leva muito tempo. Os algoritmos genéticos às vezes combinam diferentes modelos de aproximação para resolver problemas complexos da vida real.
• Os algoritmos genéticos não escalam bem. Ou seja, onde o número de elementos que estão expostos à mutação é grande, muitas vezes há um aumento exponencial no tamanho do espaço de busca. Isto torna extremamente difícil o uso da técnica em problemas como o projeto de um motor, de uma casa ou de um avião. Para usar algoritmos genéticos com tais problemas, eles devem ser decompostos na representação mais simples possível. Por esta razão, vemos algoritmos evolutivos codificando projetos de pás de ventoinha em vez de motores, construindo formas em vez de planos de construção detalhados, e aerofólios em vez de projetos de aeronaves inteiras. O segundo problema de complexidade é a questão de como proteger as peças que evoluíram para representar boas soluções contra novas mutações destrutivas, particularmente quando sua avaliação de aptidão requer que elas se combinem bem com outras peças.
• A solução "melhor" é apenas em comparação com outras soluções. Como resultado, o critério de parada não é claro em todos os problemas.
• Em muitos problemas, os algoritmos genéticos têm uma tendência a convergir em direção à ótica local ou mesmo a pontos arbitrários, em vez do ideal global do problema. Isto significa que o algoritmo não "sabe como" sacrificar a aptidão a curto prazo para ganhar aptidão a longo prazo. A probabilidade de isso ocorrer depende da forma da função de adequação: certos problemas facilitam a busca do ótimo global, outros podem facilitar a busca da ótima local pela função. Este problema pode ser atenuado pelo uso de uma função de aptidão diferente, aumentando a taxa de mutação, ou pelo uso de técnicas de seleção que mantêm uma população diversificada de soluções. Uma técnica comum para manter a diversidade é usar uma "penalidade de nicho": qualquer grupo de indivíduos de similaridade suficiente (raio de nicho) tem uma penalidade adicionada, que reduzirá a representação desse grupo nas gerações seguintes, permitindo que outros indivíduos (menos similares) sejam mantidos na população. Este truque, entretanto, pode não ser eficaz, dependendo da paisagem do problema. Outra técnica possível seria simplesmente substituir parte da população por indivíduos gerados aleatoriamente, quando a maioria da população é muito parecida entre si. A diversidade é importante nos algoritmos genéticos (e na programação genética) porque o cruzamento sobre uma população homogênea não produz novas soluções. Em estratégias de evolução e programação evolutiva, a diversidade não é essencial por causa de uma maior dependência da mutação.
• A operação em conjuntos de dados dinâmicos é difícil, pois os genomas começam a convergir cedo para soluções que podem não ser mais válidas para dados posteriores. Vários métodos foram propostos para corrigir isso, aumentando de alguma forma a diversidade genética e evitando a convergência precoce, seja aumentando a probabilidade de mutação quando a qualidade da solução cai (chamada de hipermutação desencadeada), ou introduzindo ocasionalmente elementos inteiramente novos, gerados aleatoriamente no pool genético (chamados de imigrantes aleatórios). Novamente, estratégias de evolução e programação evolutiva podem ser implementadas com uma chamada "estratégia de vírgula" na qual os pais não são mantidos e os novos pais são selecionados apenas da descendência. Isto pode ser mais eficaz em problemas dinâmicos.
• Os algoritmos genéticos não podem efetivamente resolver problemas nos quais a única medida de aptidão física é uma única medida certa/ errada (como os problemas de decisão), pois não há como convergir para a solução (nenhuma colina para subir). Nesses casos, uma busca aleatória pode encontrar uma solução tão rapidamente quanto uma AG. Entretanto, se a situação permitir que o julgamento de sucesso/falha seja repetido dando (possivelmente) resultados diferentes, então a proporção de sucessos e fracassos fornece uma medida de aptidão adequada.
• Para problemas específicos de otimização e instâncias de problemas, outros algoritmos de otimização podem ser mais eficientes do que os algoritmos genéticos em termos de velocidade de convergência. Algoritmos alternativos e complementares incluem estratégias de evolução, programação evolutiva, recozimento simulado, adaptação gaussiana, escalada de colinas e inteligência de enxame (por exemplo: otimização de colônia de formigas, otimização de enxame de partículas) e métodos baseados em programação linear inteira. A adequação dos algoritmos genéticos depende da quantidade de conhecimento do problema; problemas bem conhecidos muitas vezes têm abordagens melhores e mais especializadas.

História

Em 1950, Alan Turing propôs uma "máquina de aprendizagem" que paralelasse os princípios da evolução. A simulação computadorizada da evolução começou já em 1954 com o trabalho de Nils Aall Barricelli, que estava usando o computador no Instituto de Estudos Avançados em Princeton, Nova Jersey. Sua publicação de 1954 não foi amplamente notada. A partir de 1957, o geneticista quantitativo australiano Alex Fraser publicou uma série de artigos sobre simulação de seleção artificial de organismos com múltiplos loci controlando um traço mensurável. A partir destes inícios, a simulação computadorizada da evolução por biólogos tornou-se mais comum no início dos anos 60, e os métodos foram descritos em livros de Fraser e Burnell (1970) e Crosby (1973). As simulações de Fraser incluíram todos os elementos essenciais dos algoritmos genéticos modernos. Além disso, Hans-Joachim Bremermann publicou uma série de artigos nos anos 60 que também adotaram uma população de solução para problemas de otimização, passando por recombinação, mutação e seleção. A pesquisa de Bremermann também incluiu os elementos dos modernos algoritmos genéticos. Outros pioneiros notáveis incluem Richard Friedberg, George Friedman, e Michael Conrad. Muitos dos primeiros trabalhos são reimpressos por Fogel (1998).

Embora Barricelli, no trabalho que relatou em 1963, tivesse simulado a evolução da capacidade de jogar um jogo simples, a evolução artificial tornou-se um método de otimização amplamente reconhecido como resultado do trabalho de Ingo Rechenberg e Hans-Paul Schwefel nos anos 60 e início dos anos 70 - o grupo de Rechenberg foi capaz de resolver problemas complexos de engenharia através de estratégias de evolução. Outra abordagem foi a técnica de programação evolucionária de Lawrence J. Fogel, que foi proposta para gerar inteligência artificial. A programação evolutiva usava originalmente máquinas de estado finito para prever ambientes, e usava variação e seleção para otimizar a lógica de previsão. Algoritmos genéticos em particular se tornaram populares através do trabalho de John Holland no início dos anos 70, e particularmente de seu livro Adaptação em Sistemas Naturais e Artificiais (1975). Seu trabalho teve origem nos estudos de autômatos celulares, realizados pela Holanda e seus alunos na Universidade de Michigan. A Holanda introduziu uma estrutura formalizada para prever a qualidade da próxima geração, conhecida como o teorema do esquemaholandês. As pesquisas em AG permaneceram em grande parte teóricas até meados dos anos 80, quando foi realizada a Primeira Conferência Internacional sobre Algoritmos Genéticos em Pittsburgh, Pennsylvania.