¿Es necesario mapear enteros a bits en un algoritmo genético?

8

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.

itzy
fuente
1
No tengo conocimiento del dominio del problema en el que se encuentra, pero intuitivamente parece útil y potencialmente beneficioso en este contexto tratar directamente en el lenguaje de la computadora, en lugar de proxies numéricos como valores enteros. Pero si tratar con números enteros es más conveniente, hágalo de todas maneras. Las redes neuronales a menudo operan en números de coma flotante, a pesar de que existen ventajas significativas para su arquitectura en forma binaria.
Robert Harvey
Dado que el ADN utiliza fragmentos de 2 bits, creo que la respuesta no puede ser "no", al menos en la medida en que los algoritmos genéticos modelen la evolución biológica.
Gort the Robot

Respuestas:

9

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):

chromosome 1: 0xA3 0xB2
chromosome 2: 0x12 0x34

El cruce entre estos dos cromosomas solo puede ocurrir en lugares limitados. Terminarás con:

chromosome 1': 0x12 0xB2
chromosome 2': 0xA3 0x34

Si esto se hizo como bits en su lugar:

chromosome 1: 1010001110110010
chromosome 2: 0001001000110100
                    ^   ^     

Ahora puede seleccionar los ^sitios para dar crossover:

chromosome 1': 1010001000110010
chromosome 2': 0001001110110100
                     ^   ^     

Esto proporciona un modelo más rico con más variaciones posibles entre dos cromosomas.


fuente
Gracias. Esto es lo que quise decir al decir que el problema era "más grueso", pero ha dado una respuesta clara y agradable.
Itzy
3

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.

Robar
fuente
0

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.

AlexSC
fuente
0

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).

Esquema para generar vectores de parámetros de prueba

De la evolución diferencial: un enfoque práctico para la optimización global

manlio
fuente