Um algoritmo genético é uma técnica de busca e otimização inspirada nos princípios da seleção natural, na qual uma população de soluções candidatas é evoluída iterativamente por meio de operações análogas à mutação, ao cruzamento (recombinação) e à seleção, para melhorar a aptidão em direção a um objetivo definido ao longo de gerações sucessivas. Algoritmos genéticos pertencem à família mais ampla de métodos de computação evolucionária dentro de inteligência artificial e aprendizado de máquina.
Mecanismo
Um algoritmo genético começa com uma população gerada aleatoriamente de soluções candidatas, cada uma tipicamente codificada como uma string ou vetor análogo a um cromossomo. Cada candidato é avaliado usando uma função de aptidão que pontua o quão bem ele resolve o problema alvo. Candidatos com pontuações mais altas têm maior probabilidade de serem selecionados como "pais", cujas codificações são combinadas por meio de cruzamento para produzir descendentes, com mutações aleatórias ocasionalmente introduzidas para manter a diversidade e evitar convergência prematura para uma solução subótima. Esse ciclo de avaliação, seleção e recombinação se repete ao longo de muitas gerações, com a população como um todo tendendo a melhorar sua aptidão média ao longo do tempo, embora não haja garantia de encontrar um ótimo global.
História
Os fundamentos matemáticos do campo foram formalizados por John Holland, cujo livro de 1975 "Adaptation in Natural and Artificial Systems" introduziu algoritmos genéticos como uma estrutura geral para busca adaptativa, com base em experimentos anteriores de computação evolucionária das décadas de 1950 e 1960. Alunos e colaboradores de Holland, incluindo David Goldberg, estenderam a base teórica da estrutura e popularizaram aplicações práticas ao longo das décadas de 1980 e 1990.
Aplicações
Algoritmos genéticos têm sido aplicados a problemas de agendamento e roteamento, otimização de design em engenharia, incluindo formas de antenas e aerodinâmicas avaliadas pela NASA e outros, síntese automatizada de programas no campo relacionado de programação genética, e busca de hiperparâmetros para sistemas de aprendizado de máquina. Eles são particularmente favorecidos para problemas com espaços de busca grandes, complexos e não diferenciáveis, onde métodos baseados em gradiente não estão disponíveis ou são ineficazes, já que algoritmos genéticos exigem apenas a capacidade de avaliar a aptidão de um candidato, não de calcular uma derivada do objetivo.
Neuroevolução
Uma área de aplicação notável, a neuroevolução, usa métodos evolucionários para projetar ou treinar arquiteturas e pesos de redes neurais, às vezes combinados com aprendizado por reforço para tarefas de controle e jogos. A neuroevolução tem sido explorada como uma alternativa ou complemento a redes treinadas por retropropagação em pesquisas de robótica e IA incorporada, onde o sinal de recompensa é escasso ou a topologia da rede em si, não apenas seus pesos, é uma variável de design.
Limitações e relevância moderna
Algoritmos genéticos escalam mal para os espaços de parâmetros de altíssima dimensionalidade das redes profundas modernas em comparação com a otimização baseada em descida de gradiente, como a retropropagação, e recuaram amplamente da pesquisa mainstream à medida que arquiteturas de aprendizado profundo treinadas por retropropagação passaram a dominar após o início dos anos 2010. Eles permanecem ativamente usados, no entanto, em domínios de otimização fora do treinamento supervisionado padrão, em nichos de neuroevolução, e como um ponto de referência conceitual para pesquisas sobre abordagens evolucionárias e de final aberto para gerar soluções diversas e novas, em vez de otimizar um único objetivo fixo.