7 Mutar
Herramientas: mutation-ga, accesible desde el portal.
Al terminar el recorrido básico de este capítulo podrás:
- explicar para qué sirve la mutación y qué tres condiciones debe cumplir: poder llegar a cualquier solución, cambiar poco y de forma controlada, y producir soluciones válidas;
- aplicar a mano la inversión de bits con unos números aleatorios dados y calcular cuántos bits cambian en promedio;
- elegir entre el reinicio aleatorio y el deslizamiento según lo que signifiquen los genes enteros, y aplicarlos;
- calcular un mutante gaussiano y explicar el papel de σ;
- explicar con un contraejemplo por qué las permutaciones necesitan mutaciones propias, y aplicar el intercambio, la inserción y la inversión;
- razonar qué ocurre si la probabilidad de mutación es demasiado baja o demasiado alta.
7.1 ¿Para qué mutar? BásicoB
El cruce combina lo que ya tienen los padres. ¿De dónde salen los valores que no tiene nadie en la población?
En el capítulo de cruce vimos que, en los cruces binarios que intercambian partes de los cromosomas, donde los dos padres coinciden, los hijos también coinciden (ejemplo 6.2). Con estos cruces, cada hijo recibe en cada posición alguno de los valores que tenían allí sus padres. Si un valor desaparece de una posición en toda la población, ningún cruce de este tipo lo puede recuperar, y la selección, que solo copia individuos, tampoco. Con otras representaciones, el cruce sí puede dar valores que no tenía ningún padre: el cruce aritmético, de dos padres con un 2 y un 6 en la misma posición, puede dar un 4 (sección 6.4), y los cruces de permutaciones recolocan los genes. Pero lo que alcanzan depende de lo que ya hay en la población: el aritmético, por ejemplo, nunca sale del intervalo que forman los padres. Además, la selección reduce la diversidad de la población generación tras generación, como vimos en el capítulo de selección.
La mutación es un operador que actúa sobre un solo individuo y le hace un cambio pequeño y aleatorio en el cromosoma (Talbi, 2009, p. 208). Introduce valores nuevos y recupera los que se habían perdido, de modo que ningún punto del espacio de búsqueda quede fuera de alcance (Herrera et al., 1998; Whitley, 1994).
En los algoritmos genéticos de Holland, con cadenas de bits, la mutación tiene un papel secundario. El cruce es la principal fuente de combinaciones nuevas, y la mutación garantiza que ningún valor desaparezca para siempre de la población; si se pierde, el cruce no tiene forma de recuperarlo (Holland, 1975/1992, pp. 110–111). Goldberg (1989, p. 14) la compara con una póliza de seguro contra la pérdida prematura de material genético útil. En otros métodos evolutivos, como la programación evolutiva y las primeras estrategias evolutivas, la mutación era la única fuente de variación (Mitchell, 1996/1998, apartado 5.5). Volveremos sobre este debate en la sección 7.10.
La mutación se aplica después del cruce, a todos los individuos de la nueva población: a los hijos de las parejas que se han cruzado y también a las copias de las que no se han cruzado. A cada uno se le da una probabilidad baja de cambiar. Si una mutación empeora un individuo, lo más probable es que la selección lo descarte; si lo mejora, la selección tenderá a extender ese cambio por la población.
Una buena mutación debe cumplir tres condiciones (Talbi, 2009, p. 209):
- Poder llegar a cualquier solución. Encadenando mutaciones, desde cualquier individuo debe poder alcanzarse cualquier otro, aunque sea con una probabilidad muy baja.
- Cambiar poco, y de forma controlada. El mutante debe parecerse al individuo del que procede, y el tamaño del cambio debe poder ajustarse. Si se muta demasiado, se destruye lo que habían conseguido la selección y el cruce; si se muta demasiado poco, no se aporta diversidad.
- Validez. El mutante debe seguir siendo una solución del problema.
Como el cruce, la mutación actúa sobre el genotipo, así que cada representación tiene sus propios operadores.
Notación. Seguimos la de la herramienta: el individuo que se muta es el Padre y el resultado, el Mutante. Las posiciones se numeran desde 1. La probabilidad de mutación es pm.
En una población de 50 cadenas de bits, todos los individuos tienen un 0 en la posición 3. Si solo se aplican selección y cruce, ¿puede algún descendiente tener un 1 en esa posición? ¿Y si además se aplica una mutación que invierta bits al azar? Anota tu predicción: la comprobarás en la sección 7.2.
7.2 Binaria: inversión de bits BásicoB
¿Cómo se cambia un poco una cadena de bits?
La mutación clásica de la representación binaria es la inversión de bits (bit-flip) (Goldberg, 1989, p. 14; Mitchell, 1996/1998, apartado 1.5; Talbi, 2009, p. 209). Cada posición se trata por separado:
- Se sortea un número aleatorio r \in [0, 1).
- Si r < \mathit{pm}, el bit de esa posición se invierte: el 0 pasa a 1 y el 1, a 0.
- Si no, el bit se queda como está.
El número de bits que cambian no es fijo. En promedio cambian \mathit{pm} \times n, donde n es la longitud del cromosoma, pero unas veces cambian más, otras menos y otras ninguno.
Datos. El padre 1 1 0 1 0 0 1 0 y \mathit{pm} = 0{,}15. Números aleatorios de las posiciones 1 a 8:
| Posición | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| Padre | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 0 |
| r | 0,28 | 0,07 | 0,58 | 0,94 | 0,15 | 0,01 | 0,69 | 0,64 |
Predice. ¿Qué posiciones mutan? ¿Muta la posición 5? ¿Cuál es el mutante? ¿Cuántos bits esperabas que cambiaran?
Ver el resultado
Mutan las posiciones 2 y 6, las únicas con r < 0{,}15. La posición 5 no muta: r = 0{,}15 no es menor que pm.
| Posición | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| Mutante | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 0 |
Mostrar aquí la herramienta (inversión de bits)
Con 0 < \mathit{pm} < 1, cada bit puede cambiar o quedarse igual, así que cualquier cadena puede salir, aunque sea con una probabilidad muy pequeña: una cadena que difiere del padre en d de sus n bits sale con probabilidad \mathit{pm}^d \, (1 - \mathit{pm})^{n-d}. Hacen falta los dos límites. Con \mathit{pm} = 0 no cambia nada. Con \mathit{pm} = 1 cambian todos los bits a la vez: desde 000 solo se llega a 111 y, al mutar otra vez, se vuelve a 000. Esto responde al ejercicio 7.1: sin mutación, el 0 de la posición 3 no puede cambiar nunca; con ella, sí.
Un cromosoma tiene 8 bits y se muta con \mathit{pm} = 1/8. ¿Cuántos bits cambian en promedio? ¿Con qué probabilidad no cambia ninguno? ¿Y exactamente uno?
Ver la solución
En promedio cambia 8 \times 1/8 = 1 bit. Cada bit se queda igual con probabilidad 7/8, y los sorteos son independientes, así que ninguno cambia con probabilidad (7/8)^8 \approx 0{,}34. Exactamente uno cambia con probabilidad 8 \times (1/8) \times (7/8)^7 = (7/8)^7 \approx 0{,}39. Aunque en promedio cambie un bit, en una de cada tres mutaciones el mutante es una copia del padre.- Avanza paso a paso y fíjate en la fila de números r: la posición muta cuando su número es menor que pm.
- Pulsa Sortear de nuevo varias veces y cuenta los bits que cambian. ¿Cuántas veces sale una copia del padre?
- Mueve la Probabilidad de mutación pm entre 0,01 y 0,5 y observa cuántas posiciones mutan.
- Pulsa Practicar: la herramienta te da los números sorteados y tú escribes el mutante.
7.3 Enteros: reinicio aleatorio y deslizamiento BásicoB
Si cada gen es un número entero, ¿da igual cambiarlo por cualquier otro valor?
En la representación entera, cada gen es un entero dentro de un rango. En mutation-ga, el rango es de 0 a 9. Hay dos mutaciones básicas, y en las dos cada posición muta con probabilidad pm, como en la inversión de bits:
- Reinicio aleatorio (random resetting). Si la posición muta, el gen toma un valor cualquiera del rango, todos con la misma probabilidad. Es la mutación tal como la definió Holland (1975/1992, pp. 109–110) para cualquier alfabeto: el valor nuevo se elige al azar entre todos los posibles, con la misma probabilidad. Talbi (2009, p. 209) la describe como cambiar el valor del gen por otro del alfabeto. En la herramienta se sortea un segundo número s y el valor nuevo es \lfloor 10\, s \rfloor, la parte entera de 10\,s. Puede coincidir con el que había.
- Deslizamiento (creep). Si la posición muta, al gen se le suma un paso pequeño, positivo o negativo, de como mucho s unidades (el paso máximo). Con s = 1 se sortea un segundo número u: si u < 0{,}5, el gen baja una unidad; si no, sube una. Si el valor se sale del rango, se queda en el extremo. La idea de deslizar un gen hacia arriba o hacia abajo una cantidad pequeña, con un deslizamiento máximo fijado por el usuario, procede de los números reales (Herrera et al., 1998, apartado 4.4).
Cuál conviene depende de lo que signifique cada gen (Eiben y Smith, 2015). Si los valores son categorías sin orden, como la máquina que hace cada tarea o el proveedor que atiende cada pedido, la máquina 3 no se parece más a la 4 que a la 9, y cualquier valor es un cambio tan razonable como otro: conviene el reinicio aleatorio. Si los valores son cantidades ordenadas, como las unidades de un lote o los operarios de un turno, un valor próximo suele dar una solución parecida, y el deslizamiento cambia poco, como pide la sección 7.1.
Datos. El padre 3 7 1 4 9 0 6 2, con genes de 0 a 9. Los números se sortean por orden y, cuando una posición muta, el siguiente número es el de la mutación. Por eso, con el mismo sorteo, los r de las dos mutaciones dejan de coincidir después de la primera posición que muta.
Reinicio aleatorio con \mathit{pm} = 0{,}2:
| Posición | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| Padre | 3 | 7 | 1 | 4 | 9 | 0 | 6 | 2 |
| r | 0,92 | 0,33 | 0,22 | 0,08 | 0,50 | 0,07 | 0,62 | 0,69 |
| s | 0,23 | 0,97 |
Deslizamiento con \mathit{pm} = 0{,}3 y paso máximo s = 1:
| Posición | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| Padre | 3 | 7 | 1 | 4 | 9 | 0 | 6 | 2 |
| r | 0,92 | 0,33 | 0,22 | 0,23 | 0,07 | 0,62 | 0,69 | 0,76 |
| u | 0,08 | 0,50 | 0,97 |
Predice. ¿Cuál es el mutante de cada operador? ¿Cuál es el mayor salto de cada uno? ¿Qué le pasa al 9 de la posición 5 en el deslizamiento?
Abrir: reinicio aleatorio Abrir: deslizamiento
Ver el resultado
En el reinicio aleatorio mutan las posiciones 4 y 6. La 4 toma el valor \lfloor 10 \times 0{,}23 \rfloor = 2 y la 6, \lfloor 10 \times 0{,}97 \rfloor = 9. En el deslizamiento mutan la 3, la 4 y la 5: la 3 baja (u = 0{,}08 < 0{,}5), la 4 sube y la 5 también, pero 9 + 1 = 10 se sale del rango y el gen se queda en 9.
| Posición | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| Reinicio: Mutante | 3 | 7 | 1 | 2 | 9 | 9 | 6 | 2 |
| Deslizamiento: Mutante | 3 | 7 | 0 | 5 | 9 | 0 | 6 | 2 |
Mostrar aquí la herramienta (deslizamiento)
- Con el reinicio aleatorio, \mathit{pm} = 0{,}2 y genes de 0 a 9, ¿con qué probabilidad cambia el valor de un gen?
- Una empresa asigna cada pedido a uno de sus diez proveedores, numerados del 0 al 9. ¿Qué mutación usarías? ¿Y si cada gen fuera el número de camiones, de 0 a 9, que se envían cada día?
Ver la solución
- El gen muta con probabilidad 0,2, pero el valor nuevo coincide con el que había una vez de cada diez. Cambia con probabilidad 0{,}2 \times 9/10 = 0{,}18.
- Los proveedores son categorías sin orden: el reinicio aleatorio. El deslizamiento haría más probable pasar del proveedor 4 al 5 que al 9, sin ningún motivo. El número de camiones es una cantidad ordenada: el deslizamiento, que cambia la cantidad poco a poco.
- Sube el Paso máximo s de 1 a 3 y observa cuánto se alejan los genes que mutan.
- Escribe en Introducir el padre a mano un padre con varios 0 y 9 y fíjate en lo que pasa en los extremos del rango.
- Pasa a Reinicio aleatorio con el mismo padre (el selector de operadores de la parte superior lo conserva) y compara el tamaño de los saltos.
7.4 Reales: mutación gaussiana BásicoB
Con números reales, ¿cómo damos pasos pequeños casi siempre y, de vez en cuando, uno grande?
En la representación real, la mutación más usada suma al gen un ruido aleatorio. En la mutación gaussiana, ese ruido sigue una distribución normal de media 0 y desviación típica σ:
v' = v + \sigma\, z, \qquad z \sim N(0, 1).
Cada posición muta con probabilidad pm. Los saltos pequeños son los más probables: unos 68 de cada 100 son menores que σ y unos 95, menores que 2σ. Los grandes son raros, pero posibles. Es la mutación propia de las estrategias evolutivas (Herrera et al., 1998, apartado 4.1), y σ, el tamaño del paso, hay que elegirlo bien (Talbi, 2009, pp. 211–212). Si el mutante se sale del intervalo permitido, hay que repararlo. En mutation-ga los genes van de 0 a 10, y un valor que se sale se recorta al extremo.
La herramienta obtiene z a partir de dos números aleatorios (lo veremos en la sección 7.8). En el ejemplo te damos z directamente.
Datos. El padre 2,0 8,5 4,0 1,5 6,0, con genes entre 0 y 10, y \mathit{pm} = 0{,}25. Con este sorteo mutan las posiciones 2 y 3, con z = 1{,}2288 y z = -0{,}0551. Lo aplicamos con σ = 1 y con σ = 2, con los mismos números.
Predice. ¿Cuál es el mutante con cada σ? ¿Se sale algún gen del intervalo [0, 10]?
Abrir: mutación gaussiana con σ = 1 Abrir: mutación gaussiana con σ = 2
Ver el resultado
| Posición | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| Padre | 2,0 | 8,5 | 4,0 | 1,5 | 6,0 |
| σ = 1: Mutante | 2,0 | 9,73 | 3,94 | 1,5 | 6,0 |
| σ = 2: Mutante | 2,0 | 10,0 | 3,89 | 1,5 | 6,0 |
Mostrar aquí la herramienta (mutación gaussiana)
Un gen vale 5,0 y muta con la mutación gaussiana. ¿Entre qué valores caerán unos 95 de cada 100 mutantes si σ = 0,5? ¿Y si σ = 2? ¿Con cuál afinarías mejor una solución que ya es casi óptima?
Ver la solución
Unos 95 de cada 100 saltos son menores que 2σ. Con σ = 0,5, los mutantes caerán casi siempre entre 4 y 6; con σ = 2, entre 1 y 9. Para afinar una solución casi óptima conviene σ = 0,5, porque da pasos pequeños; σ = 2 explora más, pero cuesta acercarse con precisión al óptimo.- Mira el panel «Distribución del valor mutado»: muestra los valores que puede tomar el gen si muta. Mueve la Desviación típica σ entre 0,1 y 3 y observa cómo se estrecha o se ensancha la campana.
- Escribe en Introducir el padre a mano un gen cercano a 10, por ejemplo 9,8, y busca en el panel el pico que aparece en el extremo por el recorte.
- Pulsa Sortear de nuevo varias veces y compara los saltos con σ.
7.5 Permutaciones: por qué no sirve el reinicio aleatorio BásicoB
En una ruta del viajante, ¿podemos mutar cambiando una ciudad por otra elegida al azar?
En la representación de permutación, cada número es una ciudad (o una tarea) y debe aparecer exactamente una vez. Probemos con el reinicio aleatorio de la sección 7.3: cada posición muta con probabilidad pm y, si muta, toma un valor al azar entre 1 y n.
Datos. El padre 1 2 3 4 5 6 7 8 9 y \mathit{pm} = 0{,}25. Si una posición muta, su valor nuevo es 1 + \lfloor 9\, s \rfloor.
| Posición | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| r | 0,67 | 0,19 | 0,16 | 0,76 | 0,28 | 0,54 | 0,25 | 0,68 | 0,79 |
| s | 0,53 | 0,08 |
Predice. ¿Cuál es el mutante? ¿Es una ruta válida?
Abrir: contraejemplo con el reinicio aleatorio
Ver el resultado
Mutan las posiciones 2 y 3 (la 7 no, porque r = 0{,}25 no es menor que pm). La 2 toma el valor 1 + \lfloor 9 \times 0{,}53 \rfloor = 5 y la 3, 1 + \lfloor 9 \times 0{,}08 \rfloor = 1.
| Posición | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| Mutante | 1 | 5 | 1 | 4 | 5 | 6 | 7 | 8 | 9 |
Con permutaciones no se pueden cambiar los valores de los genes uno a uno: casi siempre aparecen repetidos (Eiben y Smith, 2015). Se podría reparar el mutante o castigarlo en la función de evaluación, pero lo natural es usar mutaciones que solo recoloquen los genes, sin cambiar ningún valor, para que se cumpla la condición de validez de la sección 7.1. Con el cruce pasaba lo mismo (sección 6.5).
- Pulsa Ver como rutas y observa qué ciudades quedan sin visitar.
- Pulsa Sortear de nuevo varias veces. ¿Cuántas veces sale una permutación válida? ¿Qué tiene que pasar para que salga?
7.6 Intercambio, inserción e inversión BásicoB
¿Cómo se cambia un poco una permutación sin repetir ninguna ciudad?
Las mutaciones más usadas para permutaciones se basan en tres operaciones (Talbi, 2009, p. 209):
- Intercambio (swap): se eligen al azar dos posiciones, i y j, y se intercambian sus genes.
- Inserción: el gen de la posición i se saca de su sitio y se coloca de modo que quede en la posición j. Los genes que había entre las dos posiciones se desplazan un lugar para hacerle hueco.
- Inversión: se elige al azar un tramo del cromosoma y se invierte el orden de sus genes.
Las tres solo recolocan genes, así que el mutante es siempre una permutación válida. Y encadenando intercambios se puede llegar a cualquier ordenación.
En una permutación los genes no se pueden mutar uno a uno, por eso pm se interpreta como la probabilidad de que el individuo mute, no cada gen (Eiben y Smith, 2015). En la herramienta, cada operador se aplica una vez, con las posiciones elegidas al azar o arrastradas a mano.
Datos. El padre 1 2 3 4 5 6 7 8 9.
- Intercambio de las posiciones 3 y 7.
- Inserción del gen de la posición 3 para que quede en la posición 7.
- Inversión del tramo de las posiciones 3–7.
Predice. ¿Cuál es el mutante de cada operador? ¿Cuántos genes siguen en la misma posición que en el padre?
Abrir: intercambio Abrir: inserción Abrir: inversión
Ver el resultado
| Posición | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| Intercambio: Mutante | 1 | 2 | 7 | 4 | 5 | 6 | 3 | 8 | 9 |
| Inserción: Mutante | 1 | 2 | 4 | 5 | 6 | 7 | 3 | 8 | 9 |
| Inversión: Mutante | 1 | 2 | 7 | 6 | 5 | 4 | 3 | 8 | 9 |
Mostrar aquí la herramienta (inversión)
Aplica las tres mutaciones al padre 9 4 5 2 6 3 8 1 7: el intercambio de las posiciones 2 y 6, la inserción del gen de la posición 2 en la posición 6 y la inversión del tramo de las posiciones 2–6.
Ver la solución
- Intercambio: el 4 y el 3 cambian de sitio: 9 3 5 2 6 4 8 1 7.
- Inserción: se saca el 4, el 5, el 2, el 6 y el 3 se desplazan a la izquierda y el 4 queda en la posición 6: 9 5 2 6 3 4 8 1 7.
- Inversión: el tramo 4 5 2 6 3 queda como 3 6 2 5 4: 9 3 6 2 5 4 8 1 7.
- Abre Mutación por intercambio, Mutación por inserción y Mutación por inversión, y arrastra los marcadores ◆ para elegir otras posiciones o tramos.
- Pulsa Ver como rutas: cada cromosoma se dibuja como una ruta del viajante. Cuenta los tramos nuevos del mutante con cada operador. ¿Cuál cambia menos la ruta?
- Usa Practicar con Padre aleatorio hasta acertar los mutantes a la primera.
7.7 ¿Cuánto mutar? BásicoB
Si la mutación aporta diversidad, ¿por qué no mutar mucho?
Normalmente pm es pequeña. Goldberg (1989, p. 14) habla de una mutación por cada mil bits copiados, Whitley (1994) de probabilidades por bit menores del 1 % y Talbi (2009, p. 208) de valores por gen entre 0,001 y 0,01, o de \mathit{pm} = 1/k, donde k es el número de variables, para que en promedio mute una sola. Los primeros estudios sistemáticos de parámetros llegaron a valores parecidos: 0,001 por bit en los experimentos de De Jong y entre 0,005 y 0,01 en los de Grefenstette y en los de Schaffer y sus colaboradores. Pero estos valores se obtuvieron con conjuntos concretos de problemas, y nada garantiza que sean los mejores para otro (Mitchell, 1996/1998, apartado 5.6). Con muy poca mutación, la población pierde diversidad y converge enseguida. Con demasiada, el mutante apenas se parece al padre: se pierde lo que habían conseguido la selección y el cruce y, en el caso extremo, la búsqueda se convierte en una búsqueda al azar (Talbi, 2009, p. 209). Por sí sola, la mutación es un paseo aleatorio por el espacio de soluciones (Goldberg, 1989, p. 14; Holland, 1975/1992, p. 110).
En la inversión de bits, el caso extremo es \mathit{pm} = 0{,}5: cada bit del mutante es un 0 o un 1 con la misma probabilidad, sea cual sea el del padre. En las otras representaciones, el tamaño del cambio depende también de otros parámetros, como el paso máximo s del deslizamiento o σ en la mutación gaussiana.
Datos. La pantalla «Comparar operadores» de mutation-ga aplica todas las mutaciones de una representación y resume cuánto cambia cada una. Con «Media con: padres al azar» promedia sobre 1000 padres de la misma longitud, con 10 mutaciones de cada uno. Usamos cadenas de 10 bits y la inversión de bits con \mathit{pm} = 0{,}1 y con \mathit{pm} = 0{,}5.
Predice. ¿En cuántos bits difiere en promedio el mutante del padre con cada pm? ¿Qué porcentaje de mutantes son copias del padre?
Abrir: comparar con pm = 0,1 Abrir: comparar con pm = 0,5
La media con padres al azar tarda unos segundos en calcularse.
Ver el resultado
| Inversión de bits | Distancia de Hamming | Copia del padre |
|---|---|---|
| \mathit{pm} = 0{,}1 | 1,01 | 34 % |
| \mathit{pm} = 0{,}5 | 5,00 | 0 % |
Una población tiene 100 individuos de 10 bits. Tras el cruce, se aplica la inversión de bits a todos. ¿Cuántos individuos quedan sin ningún cambio, en promedio, con \mathit{pm} = 0{,}01? ¿Y con \mathit{pm} = 0{,}1?
Ver la solución
Un individuo queda igual si no muta ninguno de sus 10 bits. Con \mathit{pm} = 0{,}01 ocurre con probabilidad 0{,}99^{10} \approx 0{,}90: unos 90 de los 100 individuos no cambian. Con \mathit{pm} = 0{,}1, 0{,}9^{10} \approx 0{,}35: unos 35. Con pm pequeña, la mayoría de los individuos no cambia, aunque todos, se hayan cruzado o no, tengan la oportunidad de mutar.- Desde la página de un operador, ajusta sus parámetros y pulsa Comparar operadores: la comparación conserva tus ajustes para ese operador.
- Cambia Media con entre «este padre» y «padres al azar».
- Despliega «Qué mide cada columna» para ver la definición exacta de cada medida.
7.8 Otras mutaciones AvanzadoA
Esta sección amplía el recorrido básico. Requiere las mutaciones de las secciones 7.2 a 7.6.
Mutación de un bit. Se elige una sola posición al azar y se invierte su bit. El mutante difiere siempre del padre en exactamente un bit, y nunca es una copia, como se ve en el ejemplo 7.7. Es el cambio más pequeño posible en una cadena de bits, el mismo que define los vecinos en una búsqueda local binaria (Talbi, 2009, p. 209).
Alelo aleatorio. Algunos textos describen la mutación binaria como «sustituir el bit por uno elegido al azar», no como «invertirlo». La definición original de Holland (1975/1992, pp. 109–110) es de este tipo. No es lo mismo: el bit sorteado coincide con el que había la mitad de las veces, así que cada bit cambia solo con probabilidad pm/2. Como señala Whitley (1994), la diferencia es solo de escala, siempre que se sepa cuál de las dos se está usando. Es la variante «Alelo aleatorio» de la inversión de bits, y corresponde al reinicio aleatorio con dos valores (en el ejercicio 7.3, con diez valores, el gen cambiaba con probabilidad \mathit{pm} \times 9/10).
Deslizamiento circular. La variante «Dar la vuelta» del deslizamiento trata el rango como un círculo: después del 9 viene el 0. Con los datos del ejemplo 7.3, el gen 5 pasa de 9 a 0, y el mutante es 3 7 0 5 0 0 6 2: un salto de 9 unidades con un paso máximo de 1. Solo tiene sentido si la variable es cíclica, como la hora del día o el día de la semana.
Mutación uniforme. Con probabilidad pm, el gen real se sustituye por un valor sorteado de manera uniforme en todo su intervalo, sin tener en cuenta el que tenía (Herrera et al., 1998; Michalewicz, 1996). Es el equivalente real del reinicio aleatorio: puede llegar a cualquier valor, pero no cambia poco. Ojo con el nombre: Talbi (2009, p. 211) llama «uniforme» a sumar al gen un número uniforme entre −b y b, que sí es una perturbación local.
Mutación no uniforme. Michalewicz (1996) propuso que los saltos se estrechen a medida que avanza la búsqueda. Si el gen muta, se sortea con un número τ si sube (τ < 0,5) o baja, y el gen recorre una fracción del hueco y que le queda hasta el límite en ese sentido:
\Delta(t, y) = y \left(1 - u^{(1 - t/T)^{b}}\right),
donde u es un número aleatorio, t la generación actual, T el número máximo de generaciones y b un parámetro que decide lo deprisa que se estrecha el salto. Al principio la búsqueda es uniforme en todo el hueco y, al final, muy local (Herrera et al., 1998). Como Δ nunca supera el hueco, el mutante nunca se sale del intervalo.
Datos. El padre 2,0 8,5 4,0 1,5 6,0 del ejemplo 7.4, con el mismo sorteo: mutan las posiciones 2 y 3. Sus números son τ = 0,5801 y u = 0,9413 en la posición 2, y τ = 0,0136 y u = 0,696 en la 3. Con b = 5, comparamos el principio de la búsqueda (t/T = 0) con la mitad (t/T = 0,5).
Predice. ¿Hacia dónde se mueve cada gen? ¿Cuál es el mutante en cada momento de la búsqueda?
Abrir: no uniforme con t/T = 0 Abrir: no uniforme con t/T = 0,5
Ver el resultado
El gen 2 baja (τ ≥ 0,5): su hueco hasta 0 es y = 8,5. El gen 3 sube (τ < 0,5): su hueco hasta 10 es y = 6.
- Con t/T = 0, el exponente es 1^5 = 1: \Delta = 8{,}5 \times (1 - 0{,}9413) = 0{,}50 y \Delta = 6 \times (1 - 0{,}696) = 1{,}82. El mutante es 2,0 8,0 5,82 1,5 6,0.
- Con t/T = 0,5, el exponente es 0{,}5^5 = 0{,}03125, y u^{0{,}03125} queda muy cerca de 1: \Delta = 0{,}016 y \Delta = 0{,}068. El mutante es 2,0 8,48 4,07 1,5 6,0.
Mutación polinómica. La mutación polinómica de Deb y Goyal (1996) suele acompañar al cruce SBX de la sección 6.9. El gen se perturba con v' = v + \delta\,(U - L), donde L y U son los límites del intervalo y δ, entre −1 y 1, sale de una distribución polinómica centrada en 0. El índice de distribución η controla su forma: cuanto mayor es η, más se concentra δ cerca de 0 y más se parece el mutante al padre. Se suele usar η ≈ 20 (Talbi, 2009, p. 212).
Cómo se obtiene z. En la mutación gaussiana, mutation-ga calcula el número normal z a partir de dos números uniformes, u_1 y u_2, con la transformación de Box-Muller: z = \sqrt{-2 \ln(1 - u_1)}\, \cos(2\pi u_2).
Mutación por mezcla (scramble). Se elige un tramo y sus genes se reordenan al azar, de modo que todas las ordenaciones sean igual de probables. Es la más disruptiva de las cuatro mutaciones de permutación: dentro del tramo se pierden a la vez las posiciones, el orden y las vecindades. A veces, sobre todo con tramos cortos, el tramo queda como estaba. Davis (1985, p. 163) ya usó mutaciones que desordenan un segmento de una lista en un problema de empaquetado.
- Abre Mutación de un bit y arrastra el marcador ◆ para elegir la posición.
- En Inversión de bits, con la Variante «Alelo aleatorio», busca una posición que mute sin cambiar.
- En Mutación por deslizamiento, con los datos del ejemplo 7.3, cambia la Variante entre «Recortar en los límites» y «Dar la vuelta».
- Compara el panel «Distribución del valor mutado» en Mutación uniforme, Mutación no uniforme (mueve Avance de la búsqueda t/T) y Mutación polinómica (mueve el Índice de distribución η).
- En Mutación por mezcla, deja un tramo de dos genes y pulsa Sortear de nuevo varias veces. ¿Cuántas veces queda igual?
7.9 Qué cambia y qué conserva cada operador AvanzadoA
Esta sección requiere las mutaciones de permutación de las secciones 7.6 y 7.8.
La condición de cambiar poco de la sección 7.1 se puede medir. Con bits, por la distancia de Hamming. Con enteros y reales, por el porcentaje de genes que cambian y el tamaño de los saltos. Con permutaciones, «cambiar poco» depende de lo que importe en el problema, como pasaba con la herencia en el cruce (sección 6.10):
- Posición: el gen sigue en la misma posición. El intercambio solo mueve dos genes.
- Orden relativo: los genes se recorren en el mismo orden. La inserción solo cambia la colocación del gen que se mueve respecto a los que salta.
- Adyacencias: los genes vecinos del mutante ya eran vecinos en el padre. La inversión conserva todas las adyacencias salvo las dos de los extremos del tramo.
En los problemas de secuenciación importa sobre todo el orden relativo, y en el viajante, las adyacencias (Talbi, 2009, p. 92).
Datos. La pantalla «Comparar operadores» de permutación, con «Media con: padres al azar»: 1000 padres de longitud 9, con 10 mutaciones de cada operador por padre, en posiciones y tramos al azar. Las adyacencias y el orden relativo se miden leyendo el cromosoma como una ruta circular.
Predice. ¿Qué operador conserva más posiciones? ¿Cuál, más orden relativo? ¿Y más adyacencias?
Abrir: comparar las mutaciones de permutación
La media con padres al azar tarda unos segundos en calcularse.
Ver el resultado
| Operador | Posición | Adyacencias | Orden relativo | Copia del padre | Mutantes válidos |
|---|---|---|---|---|---|
| Contraejemplo: reinicio aleatorio | 78 % | 66 % | 47 % | 10 % | 11 % |
| Intercambio | 78 % | 67 % | 75 % | 0 % | 100 % |
| Inserción | 52 % | 71 % | 86 % | 0 % | 100 % |
| Inversión | 63 % | 79 % | 64 % | 0 % | 100 % |
| Mezcla | 69 % | 70 % | 82 % | 21 % | 100 % |
Lee como rutas circulares el padre y los mutantes del ejemplo 7.6: el último gen es vecino del primero, y el padre tiene las 9 adyacencias 1–2, 2–3, …, 8–9 y 9–1. ¿Cuántas adyacencias del padre conserva cada mutante?
Ver la solución
- Intercambio (1 2 7 4 5 6 3 8 9): conserva 5. Las nuevas son 2–7, 7–4, 6–3 y 3–8: cada gen movido rompe sus dos adyacencias.
- Inserción (1 2 4 5 6 7 3 8 9): conserva 6. Las nuevas son 2–4, 7–3 y 3–8.
- Inversión (1 2 7 6 5 4 3 8 9): conserva 7. Solo son nuevas 2–7 y 3–8, las de los extremos del tramo.
- Cambia Media con entre «este padre» y «padres al azar». ¿Qué columnas dependen más del padre concreto?
- Haz la misma comparación con las mutaciones enteras y las reales, y fíjate en las columnas «Salto medio» y «Saltos pequeños». ¿Qué mutación real da los saltos más grandes?
7.10 Ampliaciones Para saber más+
Las tres propiedades, con su nombre. Talbi (2009, p. 209) llama a las tres condiciones de la sección 7.1 ergodicidad (poder llegar a cualquier solución), validez y localidad. La localidad se mide en la solución, no en el cromosoma: una mutación es muy local si un cambio pequeño en el genotipo produce un cambio pequeño en el fenotipo. Si no es así, la búsqueda se acerca a una búsqueda aleatoria. Talbi pone un ejemplo con problemas de agrupamiento: si cada gen indica el grupo de un elemento, cambiar un solo gen de AAACCC da AAABCC, que tiene un grupo de un solo elemento. Es un cambio mínimo en el cromosoma, pero puede convertir una buena solución en una muy mala. Por eso, como en la sección 7.3, la mutación adecuada depende de lo que signifiquen los genes.
Mutación y búsqueda local. La mutación está emparentada con los vecindarios de las metaheurísticas que trabajan con una sola solución, como el recocido simulado: los operadores de vecindario de una representación sirven como mutaciones (Talbi, 2009, p. 209). El intercambio, la inserción y la inversión son vecindarios clásicos de las permutaciones (Talbi, 2009, pp. 91–93). La inversión de un tramo es el movimiento 2-opt del viajante (Croes, 1958): quita dos aristas de la ruta y vuelve a unir los dos trozos en el otro sentido. En el viajante produce un cambio pequeño, pero en un problema de secuenciación, donde importa el orden, el mismo movimiento produce un cambio grande (Talbi, 2009, p. 92).
Datos. El padre 1 2 3 4 5 6 7 8 9, visto como una ruta del viajante. Se invierte el tramo de las posiciones 2–9.
Predice. ¿Cuántos genes siguen en su posición? ¿Cuántos tramos nuevos tiene la ruta del mutante? ¿Cambia su longitud?
Abrir: inversión, vista como rutas
Ver el resultado
El mutante es 1 9 8 7 6 5 4 3 2. Solo el 1 sigue en su posición, pero la ruta es la misma recorrida al revés: no tiene ningún tramo nuevo y su longitud no cambia. Medido por posiciones, el cambio es enorme; para el viajante, no hay cambio.¿Un operador secundario? La visión de Holland, con la mutación como operador de fondo, se ha matizado. Según Mitchell (1996/1998, apartado 5.5), Spears mostró que mutación y cruce rompen esquemas por igual, aunque el cruce es más eficaz construyendo otros nuevos, y Mühlenbein defendió que el poder de la mutación se había subestimado. Whitley (1994) recuerda que la mutación también actúa como un mecanismo de ascenso de colinas, y que una búsqueda genética con mutación y sin cruce suele ser bastante robusta. Lo importante es el equilibrio entre selección, cruce y mutación, que depende de la función de aptitud y de la representación, y que cambia a lo largo de una ejecución (Mitchell, 1996/1998, apartado 5.5).
Un tamaño de paso que se adapta. Por eso se han propuesto algoritmos que ajustan sus propias probabilidades de mutación y de cruce durante la búsqueda (Mitchell, 1996/1998, apartado 5.6). En la mutación gaussiana, σ puede mantenerse fija durante toda la búsqueda o ajustarse según lo que va ocurriendo (Talbi, 2009, p. 212). En las estrategias evolutivas, cada individuo lleva junto a sus genes sus propios valores de σ, que también mutan: es la autoadaptación (Herrera et al., 1998, apartado 4.1). Así, los pasos que funcionan bien se transmiten junto con las soluciones que los producen (Talbi, 2009, pp. 212–213).
Resumen
- La mutación cambia al azar una pequeña parte de un individuo. Aporta valores que la selección y el cruce no pueden crear ni recuperar por sí solos (en binaria, un bit que se ha perdido en toda la población), y debe poder llegar a cualquier solución, cambiar poco y dar soluciones válidas.
- En binaria, cada bit se invierte con probabilidad pm. En entera, el reinicio aleatorio sirve para categorías y el deslizamiento, para cantidades ordenadas. En real, la mutación gaussiana suma un ruido de tamaño σ.
- Las permutaciones necesitan mutaciones que solo recoloquen genes: intercambio, inserción e inversión.
- Ni poca ni mucha: con pm pequeña la mayoría de los individuos no cambia; con pm demasiado alta, la búsqueda se vuelve aleatoria.