Como implementar permuta gênica em algoritmos evolutivos — e onde ela falha
Eu implementei permuta gênica em um algoritmo genético há cerca de cinco anos para um problema de otimização logística, e foi mais complicado do que o esperado. Não porque o conceito em si seja difícil, mas porque os detalhes de implementação fazem toda a diferença entre um crossover que funciona e um que destrói a diversidade da população antes dos 50 gêneros. Vou explicar como eu fiz e o que aprendi com isso. Permuta gênica, ou recombinação por crossover, é o operador que combina partes do genoma de dois progenitores para gerar descendentes. Em algoritmos genéticos clássicos, isso significa selecionar dois indivíduos da população, escolher um ou mais pontos de corte no vetor de genes, e trocar os segmentos entre eles. A ideia é simples na teoria, mas na prática existem armadilhas que você só encontra depois de ver a população convergir prematuramente.
O que é permuta gênica na prática
Em termos práticos, permuta gênica funciona assim: você tem dois vetores, digamos A = [3, 7, 1, 8, 4, 2, 9, 5] e B = [6, 2, 9, 1, 7, 3, 4, 8]. Você escolhe um ponto de corte aleatório, digamos na posição 3, e cruza os segmentos para gerar dois filhos: filho1 = [3, 7, 1, 1, 7, 3, 4, 8] e filho2 = [6, 2, 9, 8, 4, 2, 9, 5]. Isso é crossover de ponto único. Existem variações — dois pontos, uniform crossover, crossover aritmético para genes contínuos — e a escolha do tipo impacta diretamente o desempenho do algoritmo. O que a maioria dos tutoriais não menciona é que a taxa de crossover e a forma como você escolhe os pontos de corte precisam ser ajustadas juntas. Taxa alta demais com crossover de ponto único gera fragments de solução muito pequenos que não conseguem carregar padrões úteis. Taxa baixa demais faz o algoritmo depender excessivamente da mutação, que por si só não explora o espaço de busca eficientemente. Na minha experiência, uma taxa entre 0,6 e 0,9 funciona para a maioria dos problemas combinatoriais, mas isso varia conforme a dimensionalidade do problema.
O problema que eu enfrentei — e o workaround
Meu problema específico era de roteirização de entregas com restrições de capacidade e janelas de tempo. Os cromossomos representavam sequências de visitas, então tecnicamente era um problema de permutação, não de binário ou real. O crossover padrão de ponto único gerava filhos inválidos — cidades repetidas ou ausentes — porque simplesmente trocar segmentos de duas permutações não preserva a propriedade de permutação. A solução que eu encontrei foi usar Order Crossover (OX1). O processo é: selecionar um segmento subsequencial do primeiro progenitor, copiar esses genes para o filho na mesma posição, e preencher os slots restantes com os genes faltantes do segundo progenitor na ordem em que aparecem nele. Funciona assim na prática — se o segmento escolhido for [7, 1, 8] da posição 2 a 4, você copia esses valores, e então preenche o resto com [3, 9, 2, 5, 6, 4] na ordem que aparecem no segundo progenitor. O resultado é sempre uma permutação válida.
Eu também testei Partially Mapped Crossover (PMX) e Cycle Crossover (CX). PMX funcionou bem mas era mais complexo de implementar e não houve ganho significativo em relação ao OX1 no meu caso. CX foi interessante teoricamente mas produziu resultados inferiores na minha implementação. Fiquei com OX1 e não mudei mais.
👉 Clique no botão abaixo para saber mais sobre o assunto!
Insights contraintuitivos que ninguém conta
Primeiro insight: permuta gênica não é sobre explorar mais espaço, é sobre combinar construtos bons que já existem. Muita gente trata o crossover como um operador de exploração pura, mas o valor real dele é a recombinção — pegar soluções parciais promissoras de diferentes indivíduos e juntá-las. Se sua função de aptidão não construtiva, o crossover perde muito do efeito. Em problemas onde genes individuais têm significado fraco mas combinações específicas são importantes (como No-Intro ou scheduling), crossover mal configurado pode destruir blocos bons tão rápido quanto a mutação. Segundo insight: diversidade populacional não é garantida pelo crossover. Pelo contrário, com taxa alta e população pequena, o crossover tende a homogeneizar rapidamente porque os melhores indivíduos se parecem cada vez mais. Eu vi populações perderem diversidade genética significativa nos primeiros 20 gêneros em problemas de 30 variáveis, mesmo com taxa de mutação de 5%. O workaround foi implementar crowding determinístico — substituir os pais pelos filhos mais similares em vez dos menos aptos — o que ajudou a manter variabilidade sem aumentar o custo computacional.
Limitações e onde permuta gênica simplesmente não funciona
Permuta gênica por ponto não funciona para problemas com restrições de ordem estrita onde qualquer troca de segmento gera soluções inviáveis. Se o seu espaço de busca tem restrições duras que invalidam grande parte das combinações, crossover estrutural vai gerar uma taxa alta de indivíduos descartados e o algoritmo vai ficar preso. Nesses casos, use operadores especializados ou crossover repair — onde o filho é gerado primeiro e depois reparado para satisfazer as restrições. Também não funciona bem em problemas com epistasia forte, onde o efeito de um gene depende do contexto de outros genes distantes no cromossomo. Se a representação codifica variáveis correlacionas em posições adjacentes, crossover de ponto único quebra esses blocos de forma sistemática. A solução aqui é mudar a representação, usar crossover de pontos adaptativos, ou recorrer a algoritmos de programação genética em vez de genéticos simples.
Outro ponto importante: permuta gênica sozinha nunca resolve problemas difíceis. Ela precisa estar acoplada a seleção adequada, esquema de sobrevivência que preserve diversidade, e taxa de mutação balanceada. Eu vi muitos tutoriais apresentarem crossover como o coração do algoritmo genético quando na verdade ele é apenas um operador dentro de um ecossistema inteiro. O que diferencia um GA que converge e outro que não converge quase nunca é o crossover — é a combinação de todos os parâmetros e operadores trabalhando juntos.
Código — exemplo prático em Python
Aqui está uma implementação simples de Order Crossover que usei no meu projeto: def order_crossover(parent1, parent2): size = len(parent1) start, end = sorted(random.sample(range(size), 2)) child = [None] * size child[start:end+1] = parent1[start:end+1] remaining = [g for g in parent2 if g not in child] fill_pos = (end + 1) % size for gene in remaining: while child[fill_pos] is not None: fill_pos = (fill_pos + 1) % size child[fill_pos] = gene fill_pos = (fill_pos + 1) % size return child
Essa função roda em O(n) e preserva a permutação. Para populações de alguns milhares de indivíduos e problemas com até 200 cidades, o overhead é desprezível. Se você estiver trabalhando com problemas maiores, considere usar numpy para vectorizar a operação. Se você estiver começando agora com permuta gênica, o erro mais comum é escolher o tipo de crossover errado para a representação do problema. Para vetores binários, simples crossover de ponto funciona. Para permutações, use OX1 ou PMX. Para reais, considere BLX- ou Simulated Crossover. Usar crossover binário em uma representação de permutação é garantia de problemas. Adapte o operador ao problema, não o problema ao operador.
