Codificación en algoritmos genéticos
1. Introducción
Los Algoritmos Genéticos (AG) son algoritmos de búsqueda estocástica inspirados en los principios de evolución biológica y emulan el proceso por medio de operadores genéticos de recombinación, mutación y selección en una población [1].
Este tipo de algoritmos se han utilizado para analizar una gran variedad de problemas complejos entre los que se encuentran: knapsack [2], calendarización de procesos, vendedor viajero [3], búsqueda de funciones para regresión simbólica [4], funciones de kernel gaussiano para análisis de sentimientos [5], entre otros.
Los AG constituyen una estrategia de optimización potente y adaptable que puede utilizarse para competir con otros métodos de optimización de manera eficiente. Lo anterior se ha reflejado en el interés de la comunidad científica en ellos. Diferentes trabajos exploran aspectos relativos a su complejidad, optimización, explotación y exploración del espacio de búsqueda entre otros.
Algunos ejemplos del uso de AG se pueden consultar en donde se utiliza un algoritmo de evolución diferencial [6] para estimar los pesos de una red neuronal pulsante. Otro ejemplo interesante es el presentado por Viana et. al [1] en donde se usa un AG para la generación de contextos en sistemas de reconocimiento del habla, y el de Orozco et al. [7] en donde usan AG para la generación de filtros de imágenes sísmicas para la detección de yacimientos de sal.
Los ejemplos anteriores nos ayudan a entender la flexibilidad de dominios en donde los AG y sus variantes pueden aplicarse.
2. Codificación en AG
Los AG representan las posibles soluciones en el espacio de búsqueda como individuos representados por un único cromosoma con ciertos valores (alelos). La cadena completa es el genotipo del cromosoma y la función que mapea el cromosoma a una solución para ser evaluada en la función de fitness, define su fenotipo. La codificación de los algoritmos genéticos se refiere al tipo de valores que puede tomar cada una de las posiciones del genotipo. Cuando estos valores son tomados del alfabeto binario, se trata de una codificación binaria. Si los valores pueden tomar números enteros, es una codificación entera. Cuando los valores del cromosoma pueden ser números reales, tenemos una codificación real. Cada tipo de codificación tiene diferentes ventajas y desventajas por lo que es necesario conocerlas para poder tomar las mejores decisiones de acuerdo al problema que se está resolviendo.
3. Diseño de AG
Plantear el problema a resolver en términos de un AG, es una tarea crucial para el éxito de la optimización y a menudo demanda experiencia y creatividad por parte del investigador. Entre los retos principales al diseñar un AG se tienen que resolver dos cuestiones importantes:
- ¿Cuál es la representación óptima de un individuo como una solución del problema que se intenta resolver?
- ¿Cómo se debe definir la función de fitness para generar un problema optimizado?
Responder estas preguntas en la etapa de diseño resulta de gran importancia y una parte importante para la resolución del problema es escoger el tipo de codificación óptima. Es importante tomar en cuenta varios aspectos al escoger una codificación para nuestro AG:
- Explicabilidad
- Complejidad del espacio de búsqueda
- Tiempo de convergencia
- Mapeo del fenotipo al genotipo
- Espacio requerido para la representación de la solución
La elección de la codificación adecuada para el problema, contribuirá notoriamente a la resolución óptima del problema que estamos explorando.
4. Características de la codificación binaria
La codificación binaria es flexible y permite crear cromosomas capaces de representar soluciones en un basto conjunto de dominios. Este tipo de codificación se expresa en términos de la unidad mínima de información: el bit. Con esta codificación podemos expresar soluciones arbitrariamente grandes y complejas incrementando el tamaño del cromosoma. Un ejemplo de cómo la representación binaria puede usarse para almacenar información compleja, es el funcionamiento de los discos duros magnéticos, en donde cada dirección de memoria se encuentra magnetizada (1) o no (0).
Al ser una representación que contiene un alfabeto simple (binario), la mutación y los posibles alelos son restringidos, permitiendo que las estrategias de explotación y exploración sean estables.
Dadas las ventajas de la codificación binaria surge la pregunta: ¿Es la codificación binaria lo suficientemente robusta para poder representar cualquier dominio de aplicación?
5. Limitaciones de la codificación binaria
Pese a la diversidad de interpretación que se puede generar a partir de la codificación binaria, también existen limitaciones importantes al utilizar esta representación.
- Complejidad del mapeo del fenotipo al genotipo: Cuando los problemas son complejos, la función de mapeo para convertir la representación binaria del cromosoma de cada individuo a las soluciones del problema, puede crecer mucho, en particular es claro que resulta impráctico codificar cromosomas demasiado grandes para problemas en donde se tienen múltiples individuos interactuando y mutando entre ellos. Esto requeriría escribir programas complejos y caros computacionalmente, solo para traducir un individuo a la forma que necesitamos para evaluar la función de fitness.
- Dificultad de convergencia en problemas con múltiples variables: Cuando el problema que resolvemos tiene múltiples parámetros a menudo necesitamos establecer puntos de corte en la representación binaria que representan cada una de las variables que estamos explorando. En un escenario donde los puntos de corte para el cruce son tomados de forma aleatoria se puede traducir en pérdida de información valiosa del individuo, por lo que necesitaríamos aplicar restricciones de cruce o introducir variantes de cruce más complejas, aumentando el tiempo de ejecución y la complejidad de nuestro algoritmo genético.
- Dificultad de ajuste para problemas con decimales: Si el problema requiere ajustar parámetros que son sensible al uso de decimales, necesitaríamos codificar representaciones flotantes en nuestras soluciones, lo cual ocasionaría que el cromosoma creciera y dificultaría el esquema de mutación, ya que la variación de un dígito binario representando la tercera cifra de decimal, no introduce la misma variabilidad que la primera cifra de la parte de entera, por lo que necesitaríamos utilizar complejas estrategias de mutación para poder superar este problema.
6. Comparación con otros tipos de codificación
Si bien la codificación binaria es flexible y expresiva, a menudo puede añadir complejidades en su manejo. Para problemas de optimización combinatoria por ejemplo una codificación entera pudiera generar un problema más sencillo y con soluciones de mejor calidad de convergencia que una codificación binaria. Por ejemplo, si tomamos el problema de las 8 reinas, numeramos cada una de las casillas del tablero, denotando cada posición del gen como un número de fila, el alelo del gen representará la columna donde se debe ubicar la reina en dicha fila. Generando una representación compacta y de fácil evaluación a un problema que crecería en complejidad si se representa utilizando la codificación binaria.
La codificación real resulta de utilidad cuando estamos trabajando con problemas que son sensibles a los decimales. En particular esta codificación tiene la ventaja de poder representar múltiples variables reales. Además no se necesita un mapeo complejo entre el fenotipo y el genotipo. La desventaja principal es que al tener un dominio de búsqueda sumamente grande, es necesario utilizar estrategias de mutación y cruce más complejas para permitir un buen balance entre la explotación y la exploración. Un ejemplo en donde puede resultar útil es en problemas de calibración de sensores.
7. Conclusiones
La codificación binaria es expresiva y es capaz de adaptarse a varios dominios de aplicación, sin embargo puede introducir problemas importantes que se necesitan resolver cuando se optimizan problemas complejos.
Conocer diferentes estrategias de codificación permite a investigadores tener una gama de herramientas para poder diseñar representaciones y funciones fitness más convenientes de acuerdo al problema estudiado.
Es importante escoger la representación y la función correcta para acelerar la convergencia y obtener buenos resultados, por lo que es recomendable dedicar un tiempo al análisis de nuestro problema para tomar las decisiones adecuadas.
8. Referencias
[1] Viana-Cámara, R., Campos-Sobrino, D., Campos-Soberanis, M.: Optimización evolutiva de contextos para la corrección fonética en sistemas de reconocimiento del habla. Research in Computing Science 148(8), 293–306 (2019)
[2] Shah, S.: Genetic algorithm for a class of knapsack problems. CoRRabs/1903.03494 (2019), http://arxiv.org/abs/1903.03494
[3] Luo, J., Baz, D.E.: A survey on parallel genetic algorithms for shop scheduling problems. CoRR abs/1904.04031 (2019), http://arxiv.org/abs/1904.04031
[4] Anjum, A., Sun, F., Wang, L., Orchard, J.: A novel continuous representation of genetic programmings using recurrent neural networks for symbolic regression. CoRR abs/1904.03368 (2019), http://arxiv.org/abs/1904.03368
[5] Roman, I., Mendiburu, A., Santana, R., Lozano, J.A.: Sentiment analysis with genetically evolved gaussian kernels. CoRR abs/1904.00977 (2019), http://arxiv.org/abs/1904.00977
[6] Hernández-Becerra C., Mejía-Lavalle M.: Clasificación de patrones mediante el uso de una red neuronal pulsante. Research in Computing Science 116, 81–91 (2016)
[7] Orozco‐del‐Castillo M., Ortiz‐Alemán C., Urrutia‐Fucugauchi J., Martin R., Rodriguez‐Castellanos A., Villaseñor‐Rojas P.: A genetic algorithm for filter design to enhance features in seismic images. Geophysical Prospecting 62(2) 210–222 (2014)
