Los algoritmos genéticos (AG) son algoritmos de búsqueda heurística adaptativa que pertenecen a la mayor parte de los algoritmos evolutivos. En cada generación, los cromosomas (nuestra solución candidata) sufren mutación y cruce y luego selección para producir una mejor población cuyos candidatos estén más cerca de nuestra solución deseada. El operador de mutación es un operador unario y solo necesita un padre para trabajar. Lo hace seleccionando unos pocos genes de nuestro cromosoma seleccionado y aplicando el algoritmo deseado.
En este artículo, hablaré de cinco algoritmos de mutación para la manipulación de strings:
1) Mutación de cambio de bit
2) Mutación de reinicio aleatorio
3) Mutación de intercambio
4) Mutación de codificación
5) Mutación de inversión
Bit Flip Mutation se usa principalmente para la manipulación de strings de bits, mientras que otros se pueden usar para cualquier
tipo de strings. Aquí nuestro cromosoma se representará como una array y cada índice representará un gen. Las strings se pueden representar como una array de caracteres que, a su vez, es una array de valores ASCII o numéricos.
Mutación de cambio de bit —
En la mutación bit flip, seleccionamos uno o más genes (índices de array) y cambiamos sus valores, es decir, cambiamos 1 a 0 y viceversa. Se explica mejor usando el diagrama dado.
Mutación de restablecimiento aleatorio —
En la mutación de restablecimiento aleatorio, seleccionamos uno o más genes (índices de array) y reemplazamos sus valores con otro valor aleatorio de sus rangos dados. Digamos que a[i] (un índice de array / gen) varía de [1, 6], luego la mutación de reinicio aleatorio seleccionará un valor de [1, 6] y reemplazará el valor de a[i] con él.
Mutación de intercambio —
En Swap Mutation seleccionamos dos genes de nuestro cromosoma e intercambiamos sus valores.
Mutación Scramble —
En Scramble Mutation seleccionamos un subconjunto de nuestros genes y codificamos su valor. Los genes seleccionados pueden no ser contiguos (ver el segundo diagrama).
Mutación de inversión —
En Inversion Mutation seleccionamos un subconjunto de nuestros genes e invertimos su orden. Los genes tienen que ser contiguos en este caso (ver el diagrama).
Referencias:
1.
http://ijcsit.com/docs/Volume%205/vol5issue03/ijcsit20140503404.pdf
2. https://www.youtube.com/watch?v=FKhgrb2zaMA