(c) Marek Obitko, 1998
Como vimos em Esboço Básico de Algoritmos Genéticos, o cruzamento e a mutação são as partes mais importantes do algoritmo genético. O desempenho é influenciado principalmente por esses dois operadores. Antes de detalharmos mais cruzamento e mutação, vejamos mais alguma informação sobre cromossomas.
Um cromossoma deve de alguma maneira conter a informação da solução que ele representa. A forma mais comum de codificar é uma série (string) binária. Um cromossoma pode então se parecer como isto:
| Cromossoma 1 | 1101100100110110 |
| Cromossoma 2 | 1101111000011110 |
Cada cromossoma é representado por uma série binária. Cada bit da série representa alguma característica da solução. Outra possibilidade é que a série toda possa representar um número - isso foi feito basicamente no applet AG.
É claro, há muitas outras formas de codificar. A codificação dependerá principalmente do problema a ser solucionado. Por exemplo, um pode codificar diretamente números inteiros ou reais, algumas vezes é útil codificar algumas permutações, e assim por diante.
Depois de decidirmos que codificação usaremos, podemos proceder a operação de cruzamento. O cruzamento opera em determinados genes dos cromossomas dos pais e cria novas descendências. A maneira mais simples de fazer isso é escolher aleatóriamente alguns pontos de cruzamento e copiar tudo o que vem antes desse ponto de um dos pais e então copiar tudo o que vem depois desse ponto do outro pai.
O Cruzamento pode ser ilustrado da seguinte maneira: ( | é o ponto de cruzamento):
| Cromossoma 1 | 11011 | 00100110110 |
| Cromossoma 2 | 11011 | 11000011110 |
| Descendência 1 | 11011 | 11000011110 |
| Descendência 2 | 11011 | 00100110110 |
Há outras maneiras de fazer cruzamento. Por exemplo, nós podemos escolher mais pontos de cruzamento. O cruzamento pode ser um pouco complicado e depender principalmente da codificação dos cromossomas. Cruzamentos especificos feitos para problemas específicos podem melhorar o desempenho dos algoritmos genéticos.
Depois que um cruzamento é realizado, acontece a mutação. A mutação tem a intenção de prevenir que todas as soluções do problema dessa população caiam em um ponto ótimo local. A operação de mutação muda aleatóriamente a descendência criada pelo cruzamento. No caso de uma codificação binária, podemos mudar aleatóriamente alguns bits escolhidos de 1 para 0, ou de 0 para 1. A mutação pode então ser ilustrada como a seguir:
| Descendência Original 1 | 1101111000011110 |
| Descendência Original 2 | 1101100100110110 |
| Descendência Mutada 1 | 1100111000011110 |
| Descendência Mutada 2 | 1101101100110110 |
A técnica da mutação (da mesma forma que a do cruzamento) depende muito da codificação dos cromossomas. Por exemplo, quando codificamos permutações, mutações podem ser realizadas como uma troca de dois genes.