¿Por qué el cruce es parte de algoritmos genéticos?

Algoritmos genéticos me han llamado la atención recientemente al tratar de corregir / mejorar a los oponentes de la computadora para los juegos de computadora de estrategia por turnos.

Implementé un algoritmo genético simple que no usaba ningún cruce, solo alguna mutación aleatoria. Parecía funcionar en este caso, así que comencé a pensar:

¿Por qué el cruce es parte de algoritmos genéticos? ¿No sería suficiente la mutación?

_{Esto es de un volcado de datos en un antiguo sitio de IA. El autor de la pregunta tenía el UID de 7.}

La mutación generalmente se define como un operador global , es decir, la mutación iterada es (eventualmente) capaz de alcanzar cada punto en el espacio vectorial definido por el genoma. En ese sentido, la mutación sola es ciertamente 'suficiente'.

Con respecto a la motivación para el crossover, de Essentials of Metaheuristics , p42:

Crossover se basó originalmente en la premisa de que las personas altamente en forma a menudo comparten ciertos rasgos, llamados bloques de construcción , en común. Por ejemplo, en el individuo booleano 10110101, quizás *** 101 * 1 podría ser un elemento fundamental

(donde * significa "0 o 1")

Entonces, la idea es que el crossover funcione mediante la distribución rápida de bloques de construcción entre la población.

Los métodos cruzados también suponen que existe un cierto grado de vinculación entre los genes en el cromosoma: es decir, la configuración de ciertos genes en grupos está fuertemente correlacionada con la mejora de la condición física. Por ejemplo, los genes A y B pueden contribuir a la aptitud física solo cuando ambos están configurados en 1: si uno está configurado en 0, entonces el hecho de que el otro esté configurado en 1 no hace nada.

También tenga en cuenta que el crossover no es un operador global . Si el único operador es cruzado entonces (también de p42):

Finalmente, la población convergerá, y a menudo (desafortunadamente) convergerá prematuramente, a copias del mismo individuo. En esta etapa no hay escapatoria: cuando un individuo cruza consigo mismo, no se genera nada nuevo.

Por esta razón, el crossover generalmente se usa junto con algún operador de mutación global.

Crossover permite combinar dos padres (frente a la mutación, que solo usa uno). En algunos casos, es útil (por ejemplo, si entrenas a un bot de FPS, si uno de los padres es bueno disparando y otro padre es bueno moviéndose, tiene sentido combinarlos). En algunos otros casos, no lo es.

Cuando se piensa en el crossover, es importante pensar en el panorama del fitness.

Considere un escenario hipotético en el que estamos aplicando un algoritmo genético para encontrar una solución que funcione bien en 2 tareas. Esto podría ser del ejemplo de Franck (moverse y disparar) para una IA, o tal vez podría predecirse 2 salidas en un escenario de aprendizaje automático genético, pero en realidad la mayoría de los escenarios en los que se aplican GA son sinónimos (incluso para resolver una sola tarea, puede haber ser diferentes aspectos de la tarea a abordar).

Supongamos que tenemos un individuo, 1, que se desempeña razonablemente bien en ambas tareas, y encontramos una serie de mutaciones que producen 2 nuevos individuos, 2 y 3, que se desempeñan mejor que el Individual 1 en las tareas 1 y 2 respectivamente. Ahora, si bien ambas son mejoras, idealmente queremos encontrar una solución generalmente buena, por lo que queremos combinar las características que nos han resultado beneficiosas.

Aquí es donde entra el crossover; Al combinar los genomas de los individuos 2 y 3, podemos encontrar un nuevo individuo que produce una mezcla de sus actuaciones. Si bien es posible que un individuo así pueda ser producido por una serie de mutaciones aplicadas al Individuo 2 o al Individual 3, el panorama puede simplemente no adaptarse a esto (puede que no haya mutaciones favorables en esa dirección, por ejemplo).

Tienes razón en parte, por lo tanto; A veces puede darse el caso de que los beneficios del crossover se puedan replicar con una serie de mutaciones. A veces, este puede no ser el caso y el crossover puede suavizar el panorama de la aptitud física de su GA, acelerando la optimización y ayudando a su GA a escapar de los óptimos locales.