¿Cómo sabemos que la próxima generación será mejor?

Este artículo de MSDN me introdujo a los algoritmos genéticos recientemente , en el que los llama evolución combinatoria, pero parece ser lo mismo, y estoy luchando por comprender cómo combinar dos soluciones potenciales siempre producirá una nueva solución que sea al menos igual a bueno como sus padres.

¿Por qué esto es tan? Seguramente la combinación podría producir algo peor.

Según tengo entendido, el algoritmo se basa en el concepto de que cuando un macho y una hembra de una especie producen descendencia, esa descendencia tendrá características de ambos padres. Algunas combinaciones serán mejores, otras peores y otras igual de buenas. Los que son mejores (para cualquier definición de "mejor" que sea apropiada) tienen más posibilidades de sobrevivir y producir offpsring que tienen las características mejoradas. Sin embargo, habrá combinaciones que serán más débiles. ¿Por qué no es esto un problema con GA?

Un algoritmo genético intenta mejorar en cada generación sacrificando a la población. Cada miembro se evalúa de acuerdo con una función de aptitud física, y solo se permite la reproducción de una parte de alto puntaje.

Sin embargo, tienes razón: no hay garantía de que la próxima generación mejore en la puntuación de su predecesor.

Considere el programa de comadreja de Dawkins : "evolucionar" la cadena "Methinks it is like a weasel". A partir de una población de cadenas aleatorias, la función de aptitud evalúa la coincidencia textual más cercana, que se perturba para producir la próxima generación. Con una reproducción cruzada simple, dos cadenas de alto puntaje que se combinan podrían producir fácilmente una descendencia de menor puntaje. Incluso la mutación aleatoria "asexual" de una sola cuerda de alta aptitud podría disminuir la aptitud del niño.

Vale la pena señalar, creo, que esto no es necesariamente un defecto. Con este tipo de búsqueda, existe la idea de máximos locales . Un miembro de la población podría representar una solución que no es el resultado óptimo, pero es lo mejor que se puede lograr sin empeorar en el camino.

Imagine que la función de aptitud para el programa de comadrejas no solo encuentra la distancia de edición, sino que tiene una noción de "palabra" y prueba si la última palabra de la cadena es el nombre de un animal. Cualquier nombre de animal tiene buena puntuación, pero "weasel"recibe una gran bonificación.

Ahora, ¿qué pasa si "Methinks it is like a walrus"se evoluciona? Se puntúa bien. No tan bien como la cadena objetivo final, pero es mejor que "Methinks it is like a walrut"otras variaciones cercanas que podrían alcanzarse con un solo paso de mutación.

La cadena de morsa es un máximo local, y la búsqueda puede atascarse allí a menos que el programa permita que la puntuación de la próxima generación sea peor.

No sabemos que mejorará, sabemos que no empeorará.

En cada generación, no consiste solo en el ospring de los mejores elementos, sino que también incluye los mejores elementos en sí mismos: clones si lo desea. Como todavía están presentes, obtendrán el mismo puntaje que antes. Lo que significa que si ninguno de los descendientes es mejor, los ganadores de las generaciones anteriores volverán a ganar, y volverán a mutar / reproducirse.

Considere: con un individuo progenitor como una letra, por ejemplo, A un niño mutado se define mediante la adición de un número A1, por ejemplo , soluciones cruzadas que se escriben con corchetes alrededor del padre, por ejemplo, (A1B2) y el núcleo de aptitud de cualquier escrito individual después de él - mayor es mejor[12]

Para la demostración, considere un grupo de 5, donde guardamos los mejores 2. y llenamos con 1 mutación de cada uno, más un cruce.

Generación 1

• A [10]
• B [5]
• C [4]
• D [3]
• E [1]

Mantenga A, Bya que son los dos mejores, y rellene otros 3 espacios con sus descendientes

Generación 2

• A [10]
• B [5]
• (AB) [7]
• A1 [12]
• B1 [4]

Mantener Ay (AB), como son los mejores 2 - Esto significa que el abuelo Atodavía estará en la piscina ya que la mayoría de los niños trabajan más débiles

Generación 3

• A [10]
• (AB) [12]
• (A(AB)) [14]
• A2 [8]
• (AB)1 [13]

Keep (AB)1y (A(AB))esta vez no se mantuvieron abuelos, ya que dos de sus hijos los golpearon. Pero si (AB1)hubiera funcionado un poco peor, habríamos mantenido en su (AB)lugar.

Esto continúa hasta que el puntaje se estabilice. Lo que indica que ha alcanzado algún tipo de máximo local (potencialmente un máximo global). Una de las razones para detectar esto sería si los mismos individuos continúan siendo "clonados" en la próxima generación. (aunque para problemas de alta dimensión que pueden tomar demasiado tiempo, quizás sea mejor verificar la mejora <una tolerancia particular)

En general, los algoritmos genéticos funcionan creando una serie de variaciones (aleatorias) en los padres en cada generación. Luego se aplica alguna función de selección, y la descendencia que más se ajusta según esta función sobrevive. Por lo tanto, la descendencia no es necesariamente mejor ya que la variación es aleatoria, pero combinada con la selección se obtiene una mejora con el tiempo.

Cuando estudié algoritmos genéticos en la universidad, se explicó así:

Imagine que una solución es una combinación de "genes", donde cada gen afecta la calidad de la solución en su conjunto. Cuando se combinan dos soluciones, los genes se seleccionan aleatoriamente de cada padre.

Ahora, si el gen conduce, en general, a una buena solución, aumenta su frecuencia en el conjunto de genes. En casos extremos, el gen dominará a la población.

Entonces, cuando piensas en algoritmos genéticos (y evolución en general), no debes pensar en individuos. Debería pensar en los genes y las poblaciones en su conjunto. Incluso si se pierde una "mejor" solución, no significa que se pierdan los genes.

También hay una idea de elitismo en los algoritmos genéticos. Significa que las mejores soluciones siempre se mantienen a través de las generaciones. Esto podría acelerar la convergencia del algoritmo, pero es más fácil para el algoritmo quedarse atascado en los óptimos locales.

Los algoritmos de GA no son deterministas, no garantizan obtener una mejora en cada generación, y tampoco garantizan encontrar un óptimo total. Sin embargo, la fase de selección de una AG, usando una función de aptitud, hace más probable que "buenas soluciones" sobrevivan.