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

32

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?

Avrohom Yisroel
fuente
12
However, there will be combinations that are weaker. Why isn't this an issue with GA?- Porque las combinaciones más débiles se descartan.
Robert Harvey
66
Sabemos que la próxima generación no será peor porque no desechamos los buenos, pero desechamos los malos. Y existe una posibilidad razonable de que combinar algunos de los buenos sea aún mejor, pero no está garantizado.
user253751
77
Why isn't this an issue with GA?Bueno, lo es, o más exactamente, podría ser. Uno de los muchos (muchos) parámetros para optimizar el uso de GA es el tamaño de la población: si es demasiado bajo, es posible que solo produzca individuos más débiles, pero si es demasiado alto, el tiempo de cálculo asociado con la función de condición física puede ser demasiado alto.
Loufylouf
3
Es una diferencia entre la reproducción y la eliminación de malezas : la etapa de reproducción puede (producirá) una descendencia peor, pero la etapa de eliminación de malezas (debería) eliminará el peor desempeño antes de la siguiente etapa de reproducción.
TripeHound
Gracias a todos ustedes. Si entiendo correctamente, fue la forma en que lo expresó en el artículo lo que me sacó del camino. Él dijo: " El nuevo, presumiblemente muy bueno, Organismo infantil reemplaza a un Organismo pobre ", lo que provocó mi pregunta. Parece que estaba mal :)
Avrohom Yisroel

Respuestas:

43

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.

Josh Caswell
fuente
1
Relevante: youtube.com/watch?v=YT1vXXMsYak : la demostración del programa de computadora de Dawkin es de aproximadamente 12 minutos, aunque vale la pena ver toda la conferencia, ya que describe la base teórica básica sobre la que se desarrolla la evolución (ya sea biológica o simulada) conectado a tierra.
Periata Breatta
24
De hecho, algunas veces permitirás que un cierto porcentaje de miembros con puntajes más débiles sobrevivan para aumentar la "diversidad genética", así como también introducir mutaciones completamente aleatorias que no se basan en ningún miembro existente.
Jörg W Mittag
@JoshCaswell Gracias por esto. Aunque todas las respuestas fueron excelentes, voy a marcar esto como el aceptado ya que cubre todo lo que pregunté, ¡y un par de cosas que aún no había pedido!
Avrohom Yisroel
Me alegro de poder ayudar, @AvrohomYisroel
Josh Caswell
6

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)

Lyndon White
fuente
1
"En cada generación, no consiste solo en la fuente de los mejores elementos, sino que también incluye los mejores elementos en sí mismos" Esto depende de la implementación. Algunas implementaciones no hacen esto. Hacerlo a veces se llama "elitismo".
jpmc26
4

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.

JacquesB
fuente
44
Ah, parece que el artículo fue un poco engañoso. Él dijo: " El nuevo, presumiblemente muy bueno, Organismo infantil reemplaza a un Organismo pobre ", que es lo que me confundió. Supongo que si está combinando una gran cantidad de organismos, entonces, en general , esperaríamos un aumento, a pesar de que los nuevos organismos individuales podrían ser más débiles que los anteriores. ¿Está bien? Gracias
Avrohom Yisroel
@AvrohomYisroel: Exactamente.
JacquesB
1
@AvrohomYisroel: Tenga cuidado con la comprensión aproximada de los no especialistas. (Además, tenga cuidado con la precisión "muro de jerga" de especialistas.)
Eric Towers
@EricTowers Sí, ¡veo el problema! Pensé que era un experto, a juzgar por los artículos anteriores que escribió, pero claramente parece haber cometido algunos errores importantes en este artículo.
Avrohom Yisroel
4

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.

Eufórico
fuente
2

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.

Doc Brown
fuente