Problemas de otimização
Em um algoritmo genético, uma população de soluções candidatas (chamadas de indivíduos, criaturas ou fenótipos) para um problema de otimização evolui em direção a melhores soluções. Cada solução candidata possui um conjunto de propriedades (seus cromossomos ou genótipos) que podem sofrer mutação e alterações. Tradicionalmente, as soluções são representadas em binário como sequências de zeros e uns, mas outras codificações também são possíveis.
A evolução geralmente começa a partir de uma população de indivíduos gerados aleatoriamente e é um processo iterativo, sendo a população em cada iteração chamada de geração. Em cada geração, é avaliada a aptidão de cada indivíduo da população. Fitness é geralmente o valor da função objetivo no problema de otimização que está sendo resolvido. Os indivíduos mais aptos são selecionados estocasticamente da população atual, e o genoma de cada indivíduo é modificado (recombinado "Recombinação (computação evolutiva)") e possivelmente mutado aleatoriamente) para formar uma nova geração. A nova geração de soluções candidatas é então usada na próxima iteração do algoritmo. Normalmente, o algoritmo termina quando ocorre um número máximo de gerações ou quando um nível de aptidão satisfatório para a população é alcançado.
Um algoritmo genético típico requer:
Uma representação padrão de cada solução candidata é como uma matriz "Matriz (matemática)") de bits. Matrizes de outros tipos e estruturas podem ser usadas essencialmente da mesma maneira. A principal propriedade que torna essas representações genéticas convenientes é que suas partes são facilmente alinhadas devido ao seu tamanho fixo, o que facilita operações simples de cruzamento. Representações de comprimento variável também podem ser usadas, mas a implementação do cruzamento cromossômico é mais complexa neste caso. As representações de árvores são exploradas na programação genética e as representações semelhantes a gráficos são exploradas na programação evolutiva. Uma mistura de cromossomos lineares e árvores é explorada na programação de expressão gênica.
Uma vez definidas a representação genética e a função de aptidão, um AG prossegue para inicializar uma população de soluções e então melhorá-la aplicando repetidamente os operadores de mutação, cruzamento, inversão e seleção.
O tamanho da população depende da natureza do problema, mas normalmente contém centenas ou milhares de soluções possíveis. Freqüentemente, a população inicial é gerada aleatoriamente, permitindo toda a gama de soluções possíveis (o espaço de busca). Ocasionalmente, as soluções podem ser “semeadas” em áreas onde é provável que sejam encontradas soluções óptimas.
Durante cada geração sucessiva, uma parte da população existente é selecionada para criar uma nova geração. As soluções individuais são selecionadas através de um processo baseado na aptidão, onde as soluções de aptidão (medidas por uma função de aptidão) têm normalmente maior probabilidade de serem selecionadas. Certos métodos de seleção avaliam a adequação de cada solução e selecionam preferencialmente as melhores soluções. Outros métodos pontuam apenas uma amostra aleatória da população, pois o processo acima pode ser demorado.
A função de aptidão é definida na representação genética e mede a qualidade da solução representada. A função de fitness sempre depende do problema. Por exemplo, no problema da mochila queremos maximizar o valor total dos objetos que podem ser colocados em uma mochila com alguma capacidade fixa. Uma representação de uma solução pode ser uma matriz de bits, onde cada bit representa um objeto diferente e o valor do bit (0 ou 1) representa se o objeto está ou não na mochila. Nem todas as representações são válidas, pois o tamanho dos objetos pode ultrapassar a capacidade da mochila. A adequação da solução é a soma dos valores de todos os objetos da mochila se a representação for válida, ou 0 caso contrário.
Em alguns problemas é difícil ou mesmo impossível definir a expressão da condição física. Nestes casos, a simulação pode ser usada para determinar o valor da função de aptidão de um fenótipo (por exemplo, a dinâmica de fluidos computacional é usada para determinar a resistência do ar de um veículo cuja forma é codificada como o fenótipo) ou mesmo algoritmos genéticos interativos.
O próximo passo é gerar uma população de segunda geração, a partir de soluções selecionadas através de uma combinação de operadores genéticos: cruzamento cromossômico (também chamado de crossover ou recombinação) e mutação.
Para cada nova solução produzida, um par de soluções "pais" foi selecionado para reprodução a partir do conjunto previamente selecionado. Ao produzir uma solução de "reprodução" usando os métodos de cruzamento e mutação cromossômicos mencionados acima, é criada uma nova solução que normalmente compartilha muitas das características de seus "pais". Novos pais são selecionados para cada nova ninhada e o processo continua até que uma nova população de soluções de tamanho apropriado seja gerada. Embora os métodos de melhoramento que dependem do uso de dois pais sejam mais “inspirados na biologia”, algumas pesquisas sugerem que mais de dois “pais” podem gerar cromossomos de maior qualidade.
Em última análise, esses processos resultam na próxima geração de população cromossômica, que é diferente da geração inicial. Em geral, a aptidão média foi aumentada por este procedimento para a população, uma vez que apenas os melhores organismos da primeira geração são selecionados para reprodução, juntamente com uma pequena proporção de soluções menos adequadas. Estas soluções menos adequadas garantem a diversidade genética dentro do património genético dos pais e, portanto, asseguram a diversidade genética da próxima geração de crianças.
As opiniões estão divididas sobre a importância do cruzamento versus mutação. Existem muitas referências em Fogel (2006) que apoiam a importância da pesquisa baseada em mutações.
Embora cruzamento e mutação sejam conhecidos como os principais operadores genéticos, é possível utilizar outros operadores como rearranjo, extinção de colonização ou migração em algoritmos genéticos.
Vale a pena ajustar parâmetros como probabilidade de mutação, probabilidade de cruzamento e tamanho da população para encontrar ajustes razoáveis para o tipo de problema em que você está trabalhando. Uma taxa de mutação muito pequena pode levar à deriva genética (que é de natureza não ergódica). Uma taxa de recombinação muito alta pode levar à convergência prematura do algoritmo genético. Uma taxa de mutação muito alta pode levar à perda de boas soluções, a menos que seja usada a seleção de elite.
Este processo geracional é repetido até que uma condição de término seja alcançada. As condições de rescisão comuns são:.