Algoritmos evolucionários (AEs) são uma classe de técnicas metaheurísticas de otimização baseadas em população, inspiradas nos mecanismos da evolução biológica, como reprodução, mutação, recombinação e seleção. Eles são usados para encontrar soluções aproximadas para problemas de otimização difíceis, onde métodos exatos ou satisfatórios são desconhecidos. Como parte da computação evolucionária e da inteligência computacional, os AEs operam sobre uma população de soluções candidatas, avaliando sua qualidade por meio de uma função de aptidão e aplicando iterativamente operadores evolucionários para melhorar a população ao longo das gerações. Sua principal vantagem é que eles fazem poucas suposições sobre a paisagem de aptidão subjacente, permitindo-lhes lidar com uma ampla variedade de problemas, embora sua complexidade computacional muitas vezes decorra dos custos de avaliação da aptidão.
Algoritmo Genérico
O algoritmo evolucionário típico segue um processo iterativo:
- Gerar aleatoriamente uma população inicial de indivíduos (a primeira geração).
- Avaliar a aptidão de cada indivíduo na população.
- Verificar se o objetivo foi alcançado; se sim, terminar.
- Selecionar indivíduos como pais, preferencialmente aqueles com maior aptidão.
- Produzir descendentes por meio de cruzamento (imitando a reprodução) e, opcionalmente, mutação.
- Aplicar operações de mutação aos descendentes.
- Selecionar indivíduos para substituição, preferencialmente aqueles com menor aptidão, para formar a próxima geração.
- Retornar ao passo 2 e repetir até a terminação.
Este quadro genérico é adaptado em vários tipos de AE, cada um com representações e operadores específicos.
Tipos de Algoritmos Evolucionários
Existem várias variantes de AE, que diferem na representação genética e nos detalhes de implementação:
- Algoritmo Genético (AG): O tipo mais popular, onde as soluções são representadas como cadeias de números (frequentemente binários). Operadores como recombinação e mutação são aplicados. Os AGs são amplamente utilizados em problemas de otimização.
- Programação Genética (PG): As soluções são programas de computador, e a aptidão é determinada pela sua capacidade de resolver problemas computacionais. As variantes incluem programação genética cartesiana, expressão gênica, evolução gramatical, programação genética linear e programação de múltiplas expressões.
- Estratégia Evolucionária (EE): Desenvolvida nas décadas de 1960 e 1970 por Ingo Rechenberg, Hans-Paul Schwefel e colegas, a EE foca na otimização numérica e de engenharia. Opera em vetores de valores reais, usando mutação, recombinação e seleção determinística. Uma característica distintiva é a auto-adaptação da distribuição de mutação, com formas como (1+1)-EE, (μ, λ)-EE e (μ+λ)-EE. Desenvolvimentos posteriores incluem a adaptação da matriz de covariância (CMA-ES) e estratégias evolucionárias naturais.
- Evolução Diferencial (ED): Baseada em diferenças de vetores, adequada principalmente para otimização numérica.
- Otimização Evolucionária Multiobjetivo: Estende os AEs para problemas com múltiplos objetivos conflitantes, mantendo uma população que aproxima soluções de trade-off na fronteira de Pareto.
- Algoritmo Coevolucionário: As soluções são avaliadas com base em interações com outras soluções, que podem competir ou cooperar. Útil para paisagens de aptidão dinâmicas ou competitivas.
- Neuroevolução: Os genomas representam redes neurais artificiais, codificando estrutura e pesos de conexão, de forma direta ou indireta.
- Sistema Classificador de Aprendizado (SCA): As soluções são conjuntos de classificadores (regras). O Michigan-SCA evolui classificadores individuais, enquanto o Pittsburgh-SCA evolui populações de conjuntos de classificadores. A aptidão é determinada por meio de aprendizado por reforço ou aprendizado supervisionado.
- Algoritmos de Qualidade-Diversidade (QD): Visam simultaneamente soluções de alta qualidade e diversidade, explorando uma ampla variedade de soluções no espaço do problema.
Fundamentação Teórica
Teorema do Almoço Grátis
O teorema do almoço grátis da otimização afirma que, ao considerar todos os problemas de otimização possíveis, todas as estratégias de otimização são igualmente eficazes. Isso implica que nenhum algoritmo evolucionário é fundamentalmente superior a outro em todos os problemas. No entanto, na prática, o conjunto de problemas é restrito, e os AEs podem ser melhorados explorando conhecimento específico do problema, como escolher representações e operadores apropriados.
Complexidade Computacional
Na maioria das aplicações reais, a complexidade computacional dos AEs é um fator significativo, principalmente devido ao custo da avaliação da função de aptidão. Técnicas de aproximação da aptidão podem mitigar esse problema. Curiosamente, AEs simples podem frequentemente resolver problemas complexos, sugerindo que não há uma ligação direta entre a complexidade do algoritmo e a complexidade do problema.
Aplicações e Limitações
Os algoritmos evolucionários são aplicados em diversos domínios, incluindo projeto de engenharia, agendamento, aprendizado de máquina (por exemplo, neuroevolução) e otimização multiobjetivo. Eles são particularmente valiosos quando o espaço de busca é grande, não linear ou pouco compreendido. No entanto, seu desempenho depende do ajuste de parâmetros e da representação do problema. Técnicas de AEs também são usadas na modelagem da microevolução biológica e de processos celulares, embora com limitações.