Mutació (algorisme genètic)
En els algorismes genètics, una mutació és un operador genètic utilitzat per mantenir la diversitat genètica d'una generació d'una població de cromosomes a la següent. És anàleg a la mutació en biologia.
El propòsit de la mutació en els algorismes genètics és evitar que la població de cromosomes sigui massa similar entre si, cosa que podria provocar una solució no prou acurada. Aquest raonament també explica el fet que la majoria de sistemes d'algorismes genètics eviten escollir només el cromosoma amb l'adequació més alta de la població per generar la següent, i en el seu lloc utilitzen una selecció aleatòria (o semi aleatòria) ponderant segons l'adequació dels cromosomes.
Es dona amb molt poca freqüència d'ocurrència (fenomen rar) i pot, fins i tot, no ser emprat.
Si en la generació actual va a produir-se una mutació fem els següents passos:
- Seleccionar a l'atzar un individu qualsevol.
- Triar un punt de mutació a l'atzar en la seva cadena genètica.
- Canviar el valor del bit afectat.
- Retornar el nou individu a la població.
Individu original: 0 0 0 1 1 0 1 0 1 0 1 0 1 1 0 1
Individu mutat: 0 0 0 1 1 0 1 0 1 0 1 1 1 1 0 1
La mutació serveix com a mecanisme de control del procés.
- taxa mutació alta: ajuda a evitar mínims locals/màxims locals.
- taxa mutació baixa: facilita la convergència.
Tipus de mutació
[modifica]Els principals tipus de mutació existents són:
- Inversió de bit: es realitza una inversió bit a bit de l'individu.
- Canvi d'ordre: se seleccionen dos valors i s'intercanvien de posició.
- Suma d'un valor: per codificació amb valor, un determinat valor s'afegeix (o es resta) als valors seleccionats.