¿Qué significan términos como inicialización, evaluación, selección, cruce, mutación en el contexto de algoritmos genéticos?

Toma un ejemplo simple.

Encuentre el valor mínimo de (x-8) * (x-8) para x entre 0 y 31 usando un algoritmo genético, cuya respuesta analítica es 0 para x es 8.

Pero antes de eso, revise mi respuesta para conocer los pasos del algoritmo genético. Los siguientes son los procesos paso a paso para comprender cómo funciona el algoritmo genético para el ejemplo anterior:

Fenotipo: el valor de x entre 0 y 31 se llama fenotipo.
Genotipo: representa el valor de x de 0 a 31 en un binario de, cuya longitud es cinco, como:

0: 00000
1: 00001
2: 00010
4: 00100
8: 01000
16: 10000
30: 11110
31: 11111

Inicialización: el algoritmo genético comienza con la población inicial. Considere cinco poblaciones iniciales 2, 7, 11, 30 y 31. Entonces, las representaciones de genotipo son 00010, 00111, 01011, 11110 y 11111 respectivamente.
Iteración: después de la representación del problema en el genotipo y el fenotipo y la creación de la población inicial, se realizan muchas iteraciones de cálculos en algoritmos genéticos para obtener la solución final. En cada iteración se crea un conjunto de descendientes mediante operaciones sucesivas como fenotipo, evaluación, aptitud, selección, cruce, mutación, elitismo, etc.
Fenotipo: Convertir la representación del genotipo en el fenotipo respectivo, que son 2, 7, 11, 30 y 31.
Evaluación: calcule el valor de la función (x-8) * (x-8) para cada individuo de la población. Entonces, los valores de las funciones para los valores x de 2, 7, 11, 30 y 31 son 36, 1, 9, 484 y 529 respectivamente.
Fitness: si el valor de la función es menor, el valor de fitness es mayor. Por lo tanto, 7 es el más apto.
Selección: los candidatos Fitter se seleccionan para la creación de la próxima generación estocásticamente. Por lo tanto, se seleccionan 7 y 11, cuyos genotipos son 00111 y 01011 para el primer conjunto de padres. Y 2 y 7 se seleccionan para el segundo conjunto de padres. Como 7 es el más apto, las posibilidades de ser seleccionado para el padre de la próxima generación son altas y, por lo tanto, seleccionadas para ambos conjuntos.
Crossover: Crossover divide la representación del genotipo e intercambia parte de la representación para crear una población de próxima generación.

Considere un punto de cruce en la segunda ubicación para el primer conjunto de padres 7 y 11. Entonces, después de dividir en el segundo punto 7 es 00 | 111 y 11 es 01 | 011 . Después del crossover, serán 00 | 011 y 01 | 111 , cuyos fenotipos son 3 y 15 respectivamente.
Considere un cruce de un punto en la tercera ubicación para el segundo conjunto de padres 2 y 7. Entonces, después de dividir en el tercer punto 2 es 000 | 10 y 7 es 001 | 11) Después del crossover serán 000 | 11 y 001 | 10 , cuyos fenotipos son 3 y 6 respectivamente.

Mutación: cada representación de genotipo de individuos en la nueva generación se cambiará con una cantidad muy pequeña de probabilidad, que se llama mutación y la probabilidad se llama probabilidad de mutación . Entonces, después de la mutación, los individuos de las próximas generaciones son:

3 = 0 0011 => 1 0011 = 19
15 = 01 1 11 => 01 0 11 = 11
3 = 00011 => 000 0 1 = 1
6 = 00110 => 001 0 0 = 4

Elitismo: en algún momento los padres más aptos son retenidos en la próxima generación, lo que se llama elitismo . Entonces 7 se retiene en la próxima generación.
Descendientes: la población de la próxima generación se llama descendencia. Por lo tanto, los descendientes son 10011, 01011, 00001, 00100 y 00111 cuyos fenotipos son 19, 11, 1, 4 y 7 respectivamente.
Generación: desde la conversión del fenotipo hasta la creación de descendencia se realiza iteración tras iteración para obtener el valor mínimo de la función. El número de tal iteración se llama Número de generación .

Fenotipo (generación-2): los fenotipos son 19, 11, 1, 4 y 7.
Evaluación (generación-2): el valor de la función con un valor x de 19, 11, 1, 4 y 7 son 121, 9, 49, 16 y 1 respectivamente.
Aptitud física (generación 2): 7, 11, 4, 1 y 19 son orden ascendente de aptitud física.
Selección (generación-2): el conjunto de padres seleccionados para las próximas generaciones son (7,11) y (7,4) y sus representaciones de genotipo son (00111, 01011) y (00111, 00100) respectivamente.
Crossover (generación-2): después del crossover ( 00111 , 01011 ) y ( 00111 , 00100 ) se convierten como ( 00 011 , 01 111 ) y ( 001 00 , 001 11 )
Mutación (generación-2): después de la mutación (000 1 1, 01 1 11) y (0 0 100, 001 1 1) se convierten como (000 0 1, 01 0 11) y (0 1 100, 001 0 1)
Elitismo (generación-2): 7 se retiene en la próxima generación.
Descendientes (generación-2): los descendientes después de las segundas generaciones son 00001, 01011, 01100, 00101 y 00111.
Fenotipo (generación-3): los fenotipos son 1, 11, 12, 5 y 7.
Evaluación (generación-3): los valores de función son 49, 9, 16, 9 y 1 respectivamente.
Aptitud física (generación 3): 7, 11, 5, 12 y 1 son orden ascendente de aptitud física.
Selección (generación-3): el conjunto de padres seleccionados para las próximas generaciones son (7,11) y (12,1) y sus representaciones de genotipo son (00111, 01011) y (01100, 00001) respectivamente.
Crossover (generación-3): después del crossover ( 00111 , 01011 ) y ( 01100 , 00001 ) se convierten como ( 00 011 , 01 111 ) y ( 0110 1 , 0000 0 )
Mutación (generación-3): después de la mutación (000 1 1, 01 1 11) y (011 0 1, 0 0 000) se convierten como (000 0 1, 01 0 11) y (011 1 1, 0 1 000)
Elitismo (generación-3): 7 se retiene en la próxima generación.
Descendientes (generación-3): los descendientes después de la tercera generación son 00001, 01011, 01111, 01000 y 00111.
Fenotipo (generación-4): los fenotipos son 1, 11, 15, 8 y 7.
Evaluación (generación-4): los valores de la función son 49, 9, 49, 0 y 1 respectivamente.

Criterios de terminación: Hay muchos criterios de terminación disponibles en la literatura para detener la iteración.

Número de generación: cuando el número de iteraciones para la generación de descendencia alcanzó un cierto valor predeterminado.
Valor de la función: cuando se alcanza el mejor valor de la función en un valor predeterminado.
Progreso detenido: cuando se detiene el progreso del valor de función mejor o promedio sobre alguna iteración.
Tiempo, memoria o cálculo: cuando el cálculo se alcanza en un valor predeterminado de tiempo, memoria o cálculo.

Solución: La mejor solución o algunas de las mejores soluciones se toman de la población final. Aquí la mejor solución es x = 8; o dos mejores soluciones son 8 y 7.

¿Cuál es el algoritmo de aprendizaje automático más útil para Google?

Cómo comenzar a aprender algoritmos de reconocimiento de voz

¿Los algoritmos de aprendizaje y las estructuras de datos son muy importantes para la informática y la programación?

¿Cómo resolver la pregunta 1 de ZIO2015? ¿Es un enfoque de programación dinámica?

¿Cuál es el propósito de la red de área local?

¿Cuál es la importancia del algoritmo en informática?

Suponga que desea generar una cadena binaria como esta 010100. Tenga en cuenta que el equivalente decimal de esto es 20.

Esto se puede lograr usando GA siguiendo el procedimiento.

Inicialización : aquí tenemos que dar cuáles son todas las posibles soluciones para obtener esta cadena.

Diferentes combinaciones de 6 bits de 0s y 1s es la posible solución para esto.

Así, la población inicial es: 001101, 001100, 010001, 010011.

Nota :

Aquí solo se consideran 4 soluciones posibles, pero puede tomar tantas como desee.

Evaluación : esto se utiliza para determinar la idoneidad de cada posible solución. Aquí el puntaje de aptitud es: (equivalente decimal de la cadena requerida – equivalente decimal de cada posible cadena de solución). Aquí el que tiene menos valor de diferencia está más en forma. Puntuación de condición física:

001101: 7 (20-13)

001100: 8 (20-12)

010001: 3 (20-17)

010011: 1 (20-19)

Selección : se seleccionará el más apto. En lo anterior, la puntuación de fitnes con 1 (cadena 010011: 19) está mucho más cerca de la requerida (cadena 010100: 20). Se seleccionarán dos a la vez de la población inicial para formar padres. Este es un proceso aleatorio, los más aptos tendrán más posibilidades de ser seleccionados.

Las posibles selecciones (pares de padres) son:

(p1: 010011 p2: 010001),

(P3: 010011 p4: 001101),

(P5: 010001 p6: 001101)

Nota : hay muchas técnicas de selección, por ejemplo: ruleta, selección de torneos, etc.

Crossover : para generar descendientes. El crossover más simple es el crossover de un solo punto. Arregle un punto e intercambie el bit de los padres restantes. Aquí los primeros 3 bits se copian tal como están y se intercambian.

Del primer par de padres obtendremos dos hijos como: (c1: 010001, c2: 010011)

Del segundo par: (c3: 001011 (primeros 3 bits de p4 y siguientes 3 bits de p3), c4: 010101 primeros 3 bits de p3 y siguientes 3 bits de p4)

Desde el tercer par: (c5: 010001, c6: 001101)

Así tenemos 6 niños de este paso.

Mutación : la modificación de la cadena de niños es mutación. Aquí la posible mutación está cambiando un poco 1 a 0 o 0 a 1 en cada niño. Ese bit a voltear se puede elegir al azar. Aquí voy a mutar cada sexto bit de niños.

Entonces los niños mutados son:

c1: 010000, c2: 010010

c3: 001010, c4: 010100

c5: 010000, c6: 001100

Ahora nuevamente calcule la aptitud de cada niño. Aquí el equivalente decimal de c4 es 20 y es exactamente la misma cadena que necesitamos.

Aplicando así GA obtuvimos la cadena requerida en c4.

Nota : si la cadena requerida no se obtiene en la mutación, tome la población infantil obtenida después de la mutación como la próxima generación y repita los pasos de selección a mutación hasta que obtengamos la cadena requerida.

Balaji Venkatesan

Inicialización
Los algoritmos genéticos funcionan con una población, por lo que la inicialización podría referirse a dos cosas: inicializar una solución o inicializar la población.

El primero, una solución se crea al azar, dijimos que la solución se ha inicializado. En el segundo, la población se crea con N soluciones aleatorias, dijimos que la población se ha inicializado.

Recordando, en algoritmos genéticos la solución se puede representar con una matriz de valores booleanos.

Solución no inicializada: [- – – – – -]

Solución inicializada: [0 1 0 0 1 0]

Población de 4 soluciones inicializadas:

S1: [0 1 0 0 1 0]

S2: [1 1 0 1 1 0]

S3: [0 0 1 0 1 1]

S4: [1 0 0 1 1 1]

Evaluación

La evaluación se refiere a una función de evaluación que asigna un valor de aptitud a una solución, en optimización se conoce como valor objetivo. Este valor representa la calidad de la solución.

Entonces, básicamente es una función que recibe una solución y asigna un valor a la solución. Continuando con el ejemplo:

Si cada solución de la población se pasa a la función, supongamos que obtenemos:
S1: [1 1 0 1 1 0] Aptitud: 10

S2: [1 0 0 1 1 0] Aptitud: 5

S3: [0 0 1 0 1 1] Aptitud: 8

S4: [1 0 0 1 1 1] Aptitud: 6

Selección

El operador de selección es una técnica estadística que se utiliza para elegir las soluciones que serán los padres. Esta técnica tiende a elegir a los mejores individuos de la población y, gracias a la probabilidad de que algunas veces se elijan soluciones con baja aptitud física, esto se hace con el objetivo de mantener la diversidad en la población. Las técnicas que siempre eligen la mejor forma física se denominan elitistas. Algunas técnicas son: ruleta, torneo binario, etc.

Ahora supongamos que tenemos S1 y S6 como el choo.

Crossover

Es un operador que combina dos soluciones para generar dos nuevas soluciones. El operador más básico es el punto de cruce del punto medio.

En este ejemplo, las fuentes en negrita (X) se combinan en una nueva solución (C1) y las fuentes normales (Y) se combinan en otra solución (C2). Aquí generamos dos hijos.

S0: [XXXYYY]

S1: [ 1 1 0 1 1 0] C1: [ 1 1 0 0 1 1 ]

S3: [0 0 1 0 1 1 ] C2: [0 0 1 1 1 0]

Mutación

La mutación es un operador que modifica los genes de una solución. La mutación más simple es la mutación de cambio de bit donde se cambia un gen. Comúnmente, el 10% de la solución está mutada. En nuestro caso, solo modificamos una generación de la solución (la fuente en negrita), por ejemplo, si mutamos las dos nuevas soluciones que obtenemos:

C1: [1 1 0 0 1 1] -> S5: [1 0 0 0 1 1]

C2: [0 0 1 1 1 0] -> S6: [0 0 1 1 0 0]

Luego combinamos a los niños con los padres y tenemos nuestra nueva población y a veces llamada la primera generación:

S1: [1 1 0 1 1 0] Aptitud: 10

S3: [0 0 1 0 1 1] Aptitud: 8

S5: [1 0 0 0 1 1] Aptitud: 9

S6: [0 0 1 1 0 0] Aptitud 4

Este proceso se repite hasta alcanzar el número deseado de generaciones.

Styne John

Dado que los términos provienen originalmente de la reproducción sexual, serán más fáciles de entender con el contexto relevante.

Las personas tienen un código genético, principalmente como ADN. Cuando nuestras células se dividen para formar dos nuevas células, el ADN se replica. Durante esta replicación, existe la posibilidad de algún error, ya que todos son procesos químicos y se basan en la probabilidad. Este error es lo que se llama mutación. El ADN reside en los cromosomas, y durante la replicación, existe la posibilidad de intercambio de partes de un cromosoma con otro. Esto se llama crossover. (Hay otra variación de división, donde el ADN no se replica pero no vamos a la biología ahora).

El crossover junto con la mutación es responsable de la mayor parte de la variación genética que vemos. Esta variación genética es responsable de muchos rasgos “nuevos”, algunos favorables y otros no. Los rasgos favorables son responsables de impulsar la selección natural y, por lo tanto, la evolución. La reproducción sexual tiene claramente una mayor probabilidad de crear nuevas combinaciones y, por lo tanto, se considera “mejor” con la selección natural en perspectiva.

Esta es la idea básica detrás de los algoritmos genéticos. Primero inicializamos una población, con alguna formulación de un código de ADN. En cada iteración, evaluamos a cada individuo y seleccionamos los que son favorables. Les permitimos tener [palabra sucia] y combinar su ADN para formar un nuevo ADN. Mientras combinamos, también hacemos algunos cruces y algunas mutaciones al azar.

Espero que la explicación sea autosuficiente.

Styne John

More Interesting

En el juego de conkers, ¿cómo diseñarías un experimento para identificar qué conkers son mejores?

¿Cuál es el código más elegante que puede escribir en su lenguaje de programación favorito que imprima los números del 100 al 200?

¿Cuáles son los algoritmos de geometría computacional que aparecen en los concursos de programación? ¿Cuál de ellos es más frecuente que los demás? ¿Qué estructuras de datos geométricos aparecen en los concursos de programación?

Si existen múltiples rutas más cortas entre 2 nodos en un gráfico no dirigido, ¿es posible imprimirlas todas utilizando el algoritmo de Dijkstra?

¿Qué estructuras de datos y algoritmos deben conocer todos los estudiantes de ciencias de la computación / ingeniería?

¿Cómo puedo implementar algoritmos de aprendizaje automático en una aplicación web?

¿Cuáles son las ventajas de los algoritmos SVM?

¿Cómo es que la mayoría de las empresas solicitan específicamente estructuras de datos y algoritmos? ¿Qué sucede cuando un adicto a los algoritmos con solo conocimiento de C ++ o Java es aceptado en una empresa que utiliza tecnologías web, aprende el marco utilizado desde cero?

¿Qué depara el futuro para los algoritmos genéticos y qué tan relevantes serán en 20 años?