Algoritmos genéticos

Question

Estoy tratando de implementar un algoritmo genético que calculará el mínimo de Rastrigin functon y estoy teniendo algunos problemas.
Necesito representar el cromosoma como una cadena binaria y como la función de Rastrigin toma una lista de números como parámetro, ¿cómo se puede decodificar el cromosoma a una lista de números?
También el Rastrigin quiere que los elementos en la lista sean -5.12 < = x (i) < = 5.12 ¿Qué sucede si cuando genero el cromosoma producirá un número que no está en ese intervalo?

Answer 1

Está buscando implementar un Algoritmo Genético. Su implementación debe ser tal que funcione para cualquier problema genérico de minimización (o maximización) y no solo la función Rastrigin. Puede decidir implementar un GA binario codificado o un GA codificado real. Ambos tienen sus propios usos y aplicaciones de nicho. Pero para usted, sugeriría implementar un GA codificado Real. Según su pregunta con respecto a qué hacer, si los valores de las variables generadas están fuera de [-5.12: 5.12], un GA con código real y un código binario GA lo manejarán de manera diferente.

Tener un código de referencia siempre es bueno antes de comenzar a implementar su propia versión. Si está buscando una implementación C, el source section de lab tiene una implementación de GA codificado real, que nosotros y otros utilizamos ampliamente para nuestro trabajo de investigación. Te sugiero que juegues con él y pruebes algunos de los problemas simples de optimización que se ofrecen allí.

Pyevolve es una biblioteca de Python para Algoritmos Genéticos y Programación Genética.

Ahora que hemos hablado sobre la implementación, ¿está claro su entendimiento de GA? De lo contrario, consulte este tutorial, que presenta GA desde un punto de vista de optimización. Tenga en cuenta que la explicación del cruce y la mutación para una GA codificada en binario no se transfiere automágicamente a una GA con código real. La GA codificada real tiene sus propias complejidades, por lo que necesitará tiempo para leer algunos documentos y comprenderlos.No hay prisa, pero con un esfuerzo de tiempo completo deberías poder ponerte en marcha fácilmente.

Answer 2

Supongo que está programando en C. Los enteros (int para el lenguaje C) se pueden empaquetar como una matriz de 4 bytes/char (32 bits). por lo que si la matriz es

char* chrom_as_bytes=(...) 

su puede obtener el valor i-ésimo de fundición a int *

int ith=3; 
value=((int*)chrom_as_bytes)[ith]; 

si un valor no está en el rango de -5,12 < x 5,12 < que, a su La función de fidelidad debería devolver un valor muy malo y este paso en la evolución debería descartarse en la próxima generación.

Consulte también el artículo en Wikipedia.

Answer 3

¿Por qué necesita representar el cromosoma como una cadena binaria? Puede escribir algoritmos evolutivos que usan otros tipos. Podría usar una lista de números.

En cuanto a la restricción de los valores, cuando genere los miembros iniciales de la población, asegúrese de que los números aleatorios estén dentro del rango que necesita. Restringir el operador de su mutación para evitar producir valores fuera de este rango (puede truncar valores que están fuera de este rango, o puede tenerlos ajustados).

Si realmente tiene que usar una cadena binaria, eche un vistazo a Gray Code, que es una forma de codificar valores numéricos en binario haciéndolos más susceptibles a mutaciones.

Answer 4

Si le interesa, he hecho una implementación usando Pyevolve: http://pyevolve.sourceforge.net/examples.html#example-7-the-rastringin-function Lo siento por el error tipográfico en el nombre.

Answer 5

La codificación de soluciones de problemas reales como una cadena de bits no es realmente el camino a seguir. Cuando tienes números como cadenas de bits, estás usando números de punto fijo para representar los números. Una vez que su algoritmo se acerque al óptimo, hasta la precisión de su codificación de punto fijo, no progresará más. Puede usar más bits, pero luego tendrá una convergencia más lenta. En la práctica, en problemas serios, tal enfoque es de varias órdenes de magnitud más lenta que un algoritmo competente que trabaja en valores de coma flotante.

Usar números en coma flotante le permitiría acercarse mucho más al óptimo, digamos 1e-10, mientras utiliza los números típicos de 64 bits. Además, el algoritmo evolutivo moderno usa un esquema adaptativo para ajustar el paso de la mutación durante la optimización. Tal mecanismo permite una mayor velocidad de convergencia, en comparación con un paso de mutación fija. Verifique esto para ver qué optimizadores evolutivos típicos logran en la función Rastrigin: http://coco.gforge.inria.fr/doku.php?id=bbob-2010