Por lo que he leído, los algoritmos genéticos generalmente se aplican (¿siempre?) A los cromosomas de bits. Entonces, si un problema implica maximizar una función que toma valores enteros, los enteros se codifican primero como bits.
¿Es necesario este mapeo? Parece que podría tomar cromosomas de enteros y aplicar crossover y mutación directamente. Entonces, si tengo una función que toma 35 entradas enteras, simplemente puedo aplicar los operadores genéticos a esos enteros, en lugar de en los bits de 35xB (donde B es el número de bits necesarios para codificar un entero). ¿Hay alguna razón para que esto no se haga?
Quizás el algoritmo sufriría porque el problema se define de manera más gruesa (es decir, un problema se puede definir con cromosomas más cortos si no estamos usando bits), pero tengo curiosidad si alguien tiene una mejor respuesta.
fuente
Respuestas:
No es necesario codificar los valores como bits. Mire el 2d box car (no pierda demasiado tiempo en él) para ver un ejemplo donde el crossover se realiza en valores enteros (flotantes). Se cruzan 'ensamblajes' enteros, esto se suma a la capacidad de reconocimiento de la fuente (parte de la estética del juego), pero hace que las variaciones entre un cromosoma dado y sus padres sean más limitadas.
La razón para considerar el uso de bits en lugar de enteros tiene que ver con el rango de datos con el que se siembra el grupo. Tener 35 enteros significa que el cruce solo puede ocurrir en 35 valores que se toman como valores enteros. tener 1120 bits (enteros de 35 * 32 bits) proporciona una granularidad más fina (considere el trabajo tradicional de 'algoritmos genéticos' en ATCG, no 'valores' completos de aminoácidos o proteínas).
Tener bits te permite tener mutaciones 'más limpias' (voltear un poco) y un crossover que toma la parte superior de un entero y la parte inferior de otro. Ambas cosas ayudan a aumentar la variedad potencial de descendencia.
Considere el cromosoma de solo dos bytes (estamos haciendo bytes en lugar de enteros para que sea más fácil de ver):
El cruce entre estos dos cromosomas solo puede ocurrir en lugares limitados. Terminarás con:
Si esto se hizo como bits en su lugar:
Ahora puede seleccionar los
^sitios para dar crossover:Esto proporciona un modelo más rico con más variaciones posibles entre dos cromosomas.
fuente
Mientras tenga un crossover y una mutación, estará en el negocio. El tipo subyacente no importa. He visto GAs en estructuras de gráficos donde el crossover y la mutación operan en gráficos directamente, agregando o combinando nodos.
En realidad, generalmente codifico todo en caracteres y luego proporciono cruce y mutación a nivel de byte, en lugar de bits. Agregar una máscara de bits para llevarlo al nivel de bits no es difícil, pero la vida es demasiado corta.
fuente
En GA, todos los cromosomas generalmente se representan como cadenas de bits. Puedes tener excepciones, pero olvidemoslas por ahora.
Un cromosoma es una posible solución a su problema, por lo que si su solución es un número entero, debe tener una representación binaria para que funcione con las operaciones genéticas. Afortunadamente, los números enteros ya tienen esta representación binaria (de hecho, * son cadenas de bits nativas), por lo que no tiene que hacer nada, solo aplique los operadores sobre los individuos de su población a lo largo del proceso de evolución.
fuente
El mapeo no es necesario.
La evolución diferencial (DE) es un "subconjunto" muy exitoso del espacio más amplio de algoritmos genéticos.
El primer gran cambio es que DE está utilizando números reales / enteros reales en lugar de cadenas de bits (generalmente números reales para optimización numérica, enteros en otros campos).
De todos modos, es bueno poder representar las cosas como números reales.
Es una forma de usar los recursos de la computadora de manera eficiente y también hace que la entrada y la salida sean transparentes para el usuario: los parámetros pueden ingresarse, manipularse y emitirse como números ordinarios sin tener que formatearse como genes con una representación binaria diferente.
Para el problema de ser "definido más groseramente" , DE adopta operadores modificados de mutación / cruce que hacen uso de la diferencia entre dos o más vectores enteros / reales en la población para crear un nuevo vector (por ejemplo, agregando alguna proporción aleatoria de la diferencia a uno de los vectores existentes, más una pequeña cantidad de ruido aleatorio).
De la evolución diferencial: un enfoque práctico para la optimización global
fuente