¿Qué es un simple ejemplo de un algoritmo genético?

Planteamiento del problema : dada una función que toma cadenas de bits como entradas y produce una puntuación, encuentre la cadena de bits con la puntuación máxima / mínima.

Tenga en cuenta que usted necesita cadenas de bits como entradas, debido a que las operaciones genéticas se definen en las cadenas de bits. (Es posible que pueda definir las operaciones de mutación de otro tipo de entradas, pero el marco original sólo permite cadenas de bits).

Ahora, esto es un problema NP-duro, es decir, no hay manera eficiente para resolver este problema exactamente. Así se recurre a métodos aproximados, que buscar el espacio de todas las cadenas de bits. Debido a que no podemos buscar en todo el espacio de manera eficiente, utilizamos la heurística para navegar por el espacio, para maximizar la probabilidad de encontrar una buena solución.

• ¿Cuál es la mejor manera de obtener experiencia con el aprendizaje automático y la ciencia de datos?
• ¿En qué se diferencia la IA de la coincidencia de patrones básicamente?
• ¿Puede la inteligencia artificial mejorar la compresión de datos?
• ¿Qué pasaría realmente si una IA oye una paradoja?
• ¿Por qué hacerse cargo de la inteligencia artificial retratada como negativa?

Los algoritmos genéticos es una de esas clase de heurísticas.

Veamos un ejemplo. Digamos que quiere resolver Traveling Salesman Problem (TSP) en un gráfico dado con 16 vértices. Así que hay 16! posibilidades. Este problema puede ser modelado utilizando cadenas de bits – representar cada vértice usando 4 bits, de 0000 a 1111. Por lo tanto una trayectoria en la gráfica se puede representar como una cadena de 64 bits mediante la concatenación de las representaciones de bits de vértices consecutivos en el tour. En consecuencia, cada cadena de 64 bits se puede asignar una puntuación – si el viaje es válido, la puntuación es igual a la longitud del camino, si no es válido (vértices repetidos), entonces la puntuación es [matemáticas] \ infty [/ matemáticas] . Usted quiere encontrar el mínimo de esta función.

El marco básico de algoritmos genéticos tiene el siguiente aspecto:

1. Comience con algunas cadenas de bits generados de forma aleatoria, llamados población.
2. Elija cadenas de 2 bits del conjunto actual de cadenas de bits y realice operaciones genéticas (cruce, mutación, etc.) para generar nuevas cadenas de bits.
3. Evaluar cadenas de bits recién generadas, y actualización de la mejor cadena de bits encontrado hasta ahora.
4. Actualización de la población actual.
5. Vaya al paso 2.

Repite los pasos hasta la convergencia, o durante un tiempo fijo.

Ahora viene lo más importante: porque este es un algoritmo heurístico, no hay una “forma correcta” de hacer las cosas. Solo necesita asegurarse de realizar el paso 3 correctamente, y tiene la libertad de modificar los pasos 1, 2 y 4. Esto da como resultado diferentes versiones de algoritmos genéticos. Algunas posibles modificaciones son:

• En el paso 1, en lugar de una generación completamente aleatoria, puede generar más de la cantidad requerida de cadenas de bits y luego filtrar según las puntuaciones.
• En el paso 1, se puede elegir el número de cadenas de bits que desea generar.
• En el paso 2, puede elegir las cadenas de 2 bits uniformemente al azar, o asignar una probabilidad más alta de cadenas de bits con las puntuaciones más altas.
• En el paso 2, puede definir las operaciones genéticas de su cuenta, o elegir entre los más populares.
• En el paso 2, si tiene varias CPU o GPU, se pueden realizar muchas operaciones genéticas en muchas parejas en paralelo.
• En el paso 4, se puede incluir la nueva cadena de bits en la población siempre, o incluir sólo si es mejor que la mayoría de los otros.
• En el paso 4, puede conservar todas las cadenas de bits antiguas o eliminar las cadenas de bits antiguas de la población, si son peores que la mayoría de las demás.
• Puede ejecutar todo este proceso de forma independiente en varias máquinas, y luego encontrar el mejor entre las mejores marcas de todas las máquinas.
• Aquí está un ejemplo extremo de la libertad que tiene – suponga que está en un entorno de múltiples hilos (múltiples CPU o GPU), y la población se almacena en una matriz fija. Sobrescribe cuerdas viejas bits con los recién generados, en esa matriz fija. Ahora, mientras un hilo está realizando operaciones genéticas en cadenas de 2 bits B1 y B2, otro hilo puede aparecer y sobrescribir B1 con B3, en el medio de la operación . Así, el resultado que se obtiene de la operación genética no es correcta, en el sentido de que no se genera a partir de las operaciones en B1 y B2. Sin embargo, el resultado es, sin embargo, una cadena de bits válido! Lo que sólo puede seguir adelante como si nada inusual sucedió. Rara vez hay un escenario en informática en la que no necesita preocuparse por las dependencias y condiciones de carrera en entornos multi-hilo. ¡Los algoritmos genéticos son uno de ellos!