Algoritmos Genéticos y Memoria Visual

Los algoritmos genéticos forman parte de la llamada computación evolutiva, que a su vez suele clasificarse dentro de las técnicas de Inteligencia Artificial. ¿Qué aplicaciones tienen los algoritmos genéticos? En este artículo aprenderás dos cosas: 1. Cómo se construye un algoritmo genético simple, y 2. Cómo aplicar un algoritmo genético en la creación de un mapa visual para la navegación de robots.

Computación Evolutiva y Algoritmos Genéticos

La Computación Evolutiva (CE) engloba diversos algoritmos que están inspirados en la teoría Neo-Darwiniana de la evolución natural. Ésta es vista como un proceso de optimización, en el cual los individuos de una población mejoran gradualmente adaptándose a su ambiente. En los algoritmos pertenecientes a la CE, un individuo es una solución potencial a un problema de optimización y el ambiente al que pertenece es la función(es) objetivo y sus restricciones. Este ambiente determinará la capacidad de supervivencia del individuo. Más adelante veremos un ejemplo simple para dejar esto más claro. Antes veamos algunos conceptos básicos para seguir avanzando.

Un algoritmo genético es una clase de algoritmo perteneciente a la Computación Evolutiva [David E. G.,1998]. Es un algoritmo de búsqueda basado en la mecánica de la selección natural. Estos algoritmos hacen evolucionar una población de individuos a través de acciones aleatorias semejantes a las que actúan según la teoría de la evolución biológica como mutaciones y recombinaciones genéticas. Además, hacen una selección de acuerdo con alguna función de aptitud que decide cuáles son los individuos más aptos que sobreviven, y cuáles los menos aptos que son descartados.

En un algoritmo genético, los individuos pueden ser codificados como cadenas binarias, que representan el cromosoma o genotipo del individuo. Por otra parte, el valor real al que codifica el genotipo es llamado fenotipo. Por ejemplo la cadena binaria 1010 sería el genotipo, mientras que el fenotipo sería 10.

En este artículo usaremos la codificación binaria, aunque no es la única forma de representar a un individuo. Existe también la codificación real, que implica que el fenotipo y genotipo coincide. En otras palabras, la codificación real del individuo con fenotipo 10, sería 10 también.

Son las cadenas binarias las que pasan por operaciones de recombinación genética y mutaciones. De forma más particular, un algoritmo genético simple ejecuta tres operaciones básicas:

1. Reproducción 
2. Cruza
3. Mutación

Reproducción

La reproducción es un proceso de selección de cromosomas para el posterior apareamiento e intercambio de genes, con base en el valor de su función de aptitud (la que indica qué tan apto es un individuo). Idealmente, se seleccionan con mayor probabilidad los individuos con una función de aptitud alta, logrando así una mayor probabilidad de contribuir con descendencia a la próxima generación. La función de aptitud determina entonces la supervivencia o muerte de algún individuo.

Uno de los métodos más usado para la selección de individuos es la llamada rueda de ruleta. Este método asigna un porcentaje de la ruleta, es decir una probabilidad, a cada individuo según su aptitud; donde el 100% de la ruleta es la suma de las aptitudes. Como ejemplo, observa la ruleta que se construye para una población de cuatro individuos con aptitudes: 25, 784, 441 y 961.

Cruza

La cruza es un operador que lleva a cabo el intercambio de información genética de dos individuos de la población, a los que llamaremos padres, en el cual se combinan sus genes, que son los bits de las cadenas binarias, para generar descendencia o hijos. Toma por ejemplo la cruza de estas dos cadenas binarias.

1 0 | 1 0

  ⇒   1 0 0 0

1 1 | 0 0  

Mutación

La mutación modifica bits de la cadena binaria de forma aleatoria con cierta probabilidad. Una mutación se vería así:

1 0 0 0   ⇒   1 0 0 1

El objetivo de la mutación es generar nuevos individuos o hijos que formarán parte de la nueva población. Este operador permite la variabilidad en la población, con la finalidad de no quedar estancado en un máximo o mínimo local. Eso contribuye a la exploración de todo el espacio de búsqueda evitando así la convergencia prematura.

Los distintos algoritmos genéticos que se pueden formular responden a un esquema básico común, y comparten una serie de propiedades: 

• Procesan simultáneamente, no una solución al problema, sino todo un conjunto de ellas. Estos algoritmos trabajan con una codificación de soluciones potenciales al problema, que se denominan individuos o cromosomas. El conjunto de todos ellos forman la población con la que trabaja el algoritmo.
• La composición de la población se va modificando a lo largo de las iteraciones del algoritmo que se denominan generaciones. De generación en generación, además de variar el número de copias de un mismo individuo en la población, también pueden aparecer nuevos individuos generados mediante operaciones de transformación sobre individuos de la población anterior. Dichas operaciones se conocen como operadores genéticos, que ya han sido descritos.
• Cada generación incluye un proceso de selección, que da mayor probabilidad de permanecer en la población y participar en las operaciones de reproducción a los mejores individuos. Los mejores individuos son aquellos que dan lugar a los mejores valores de la función de aptitud.

Es fundamental para el funcionamiento de un algoritmo genético que este proceso de selección tenga una componente aleatoria, de forma que individuos con bajo valor de aptitud también tengan oportunidades de sobrevivir, aunque la probabilidad asociada a éstos sea menor. Es esta componente aleatoria la que dota a los algoritmos genéticos de capacidad para escapar de óptimos locales y de explorar distintas zonas del espacio de búsqueda.

Requisitos para resolver un problema usando Algoritmos Genéticos

Para resolver un problema con algoritmos genéticos, el problema debe poder plantearse como un problema de optimización. Esto es, dada una función matemática se deben encontrar el o los parámetros que hagan que la función tenga su máximo (o mínimo) valor.

Observa la gráfica para la función f(x) = x^3 + 10x^2 – 37x + 26. En este caso, x es el único parámetro. El problema consiste en encontrar el valor de x que optimice (maximice) la función.

La gráfica representa los distintos valores de la función de aptitud también llamada función objetivo. Como puedes observar, de los tres valores señalados, el punto rojo tiene mejor función de aptitud.

Ejemplo de un Algoritmo Genético Simple

Consideremos el problema de maximizar la función f(x) = x^2 , donde x tiene la restricción de variar entre 0 y 31. Se codifican los individuos con una cadena de 5 elementos (bits) siendo 00000 = 0 y 11111 = 31. Para empezar se elige aleatoriamente una población de 4 individuos.

El algoritmo elige de forma aleatoria una población inicial con individuos: 15, 31, 3 y 12, cuya codificación, valor de aptitud y porcentaje en la ruleta se muestran en la siguiente tabla.

Observa una simulación de 4 iteraciones o generaciones.

En la primera iteración del algoritmo se encuentra una nueva población con individuos: 15, 31, 31 y 31. Se observa que la aptitud máxima se mantuvo y que los mejores individuos fueron seleccionados para la cruza. La gráfica anterior muestra la evolución de la población, en cada iteración de los algoritmos de reproducción y cruza la función de aptitud mejoró en términos generales. Sin embargo, al tratarse de un algoritmo basado en la probabilidad, la población no siempre converge al máximo en la tercera iteración. Es posible que sean necesarias más iteraciones para ciertas funciones objetivo.

Aplicación de Algoritmos Genéticos: Construcción de una Memoria Visual para la navegación autónoma de robots

El problema de navegación de robots consiste en el desplazamiento seguro de éstos dentro de un ambiente, sea éste estructurado o no. Para lograr la navegación autónoma tres problemas diferentes debes ser resueltos:

1. Mapeo. Determinación de una representación eficiente y adecuada del ambiente a navegar. Esto a través de un mapa que describa correctamente el espacio de navegación.
2. Auto-localización. Es necesario que el robot logre localizarse eficientemente en el mapa.
3. Navegación. Diseño de leyes de control. Debe ser posible el desplazamiento del robot de un punto A a un punto B con leyes de control adecuadas.

Resolvamos el primer problema relacionado con el mapeo del ambiente de navegación. Este trabajo fue publicado en The International Symposium on Optomechatronic Technology (ISOT) [López-Martínez, A., 2019].

En la teoría, los tipos de mapas pueden ser divididos en dos familias: las geométricas y las topológicas.

En las geométricas, el espacio de navegación se representa en un marco de referencia euclidiano; se tiene información de las medidas métricas del ambiente de navegación.

En las representaciones topológicas, por otra parte, el ambiente es descrito de forma cualitativa, es decir, un mapa sin información métrica del ambiente. En esta parte del artículo, te mostraré la construcción de un mapa topológico en la forma de una memoria visual.

Memoria Visual

Una memoria visual es un mapa topológico que usa solamente información visual [Delfin, J., 2018]. El sensor es una cámara proyectiva a bordo del robot, y las trayectorias por las cuales el robot tiene permitido navegar se describen con un conjunto de imágenes (imágenes clave) que caracterizan o describen el ambiente. A esta colección de imágenes la llamamos memoria visual.

¿Por qué una Memoria Visual?

La motivación es simular la forma en que humanos y animales guardamos la información de lugares nuevos [Van Veen H., 1998]. Pongamos un ejemplo: Imagina que exploras un espacio nuevo. ¿Cómo guardas la información? De ninguna manera lo haces de forma métrica. Es decir, no sabes exactamente la distancia en metros de la puerta A a la puerta B, ¿cierto? Más bien, guardas información topológica o cualitativa. En otras palabras, guardas la relación de la posición de cada elemento de interés; la puerta A está antes de la puerta B.

Un ejemplo común de mapa topológico son los mapas de las estaciones de metro. Cuando ves el mapa, no observas información métrica con la distancia entre estaciones. Más bien, obtienes información sobre la posición relativa entre estaciones. Sin embargo, esta información parcial no te impide navegar ya sea dentro del espacio nuevo que has explorado o dentro del sistema del metro.

Comparemos el mapa de metro con la memoria visual. En la memoria visual cada imagen clave es como una estación de metro. En la siguiente imagen, cada círculo representa distintos frames del video capturado por la cámara del robot. Un círculo azul indica una imagen clave dentro de la memoria visual.

Una ventaja de este tipo de mapas topológicos está en la cantidad de información necesaria para navegar. Es mucho menos que la información de mapas 3D por ejemplo. Entre menos datos para procesar, mejor eficiencia de procesamiento, y de almacenamiento de información. Existen desventajas claro está ¿puedes pensar en algunas? Comenta este artículo.

¿Cómo construir una memoria visual?

La metodología para la construcción de la memoria visual se divide en tres etapas: la primera etapa inicia con una fase de aprendizaje, en ésta el robot es conducido por un humano a través del entorno, mientras el robot captura imágenes de entrenamiento.

Después, este conjunto de imágenes se procesa en la etapa dos, que busca reducir el número de imágenes que conformarán la MV. Para lograr tal reducción, se seleccionan sólo algunas de las imágenes del conjunto, que son llamadas imágenes clave (Los círculos azules que viste en la imagen anterior). Para ello se analiza la similitud entre imágenes, o su traslape, y se desechan las imágenes que no cumplen ciertos criterios. Tal selección también toma en cuenta el cumplimiento de algunas hipótesis necesarias para el control del robot durante la navegación. Es en esta etapa donde usaremos el algoritmo genético.

Una vez que se tiene un conjunto de imágenes clave, el cual denominamos conjunto M1, se organizan la imágenes pertenecientes a éste para formar una representación topológica del ambiente de navegación. Esto último ocurre en la etapa tres de la construcción de la memoria visual. La siguiente imagen ilustra estos pasos.

Construcción de una Memoria Visual con Algoritmos Genéticos

En esta sección nos concentraremos en la selección de imágenes clave. Queremos que en el mapa visual tengamos únicamente información relevante. Entonces, no debería haber imágenes similares. Para lograr esto, seleccionamos los frames del video que tengan solo un porcentaje de similitud o empalme. Cuando el robot haya avanzado cierta distancia, la cámara capturará información nueva. Seleccionamos una imagen clave nueva cuando tengamos un porcentaje previamente definido de información nueva. ¿Cómo logramos hacer esto con un algoritmo genético?

La clave está en la geometría epipolar [Zisserman, R. H. A., 2004]. Esta geometría describe la rotación y traslación de la cámara. Se pueden conocer estos movimientos cuando una imagen observa un punto, y después se mueve (rotación o traslación) un poco sin dejar de observar el mismo punto.

Para usar un algoritmo genético haremos lo siguiente. Cada individuo codificará una rotación y traslación candidata.

Ind = [φ, θ, ψ, tx, ty],

donde

• φ ∈ [0, 2π]
• θ ∈ [0, 2π]
• ψ ∈ [0, 2π]
• tx ∈ [−5, 5]
• ty ∈ [−5, 5]

Para calcular la aptitud de cada individuo se calcula qué tan bien describe la rotación y traslación real. ¿Cómo sabemos cuál fue el movimiento real? Se deduce indirectamente con puntos emparejados entre imágenes. Si la rotación y traslación codificada por el individuo explica correctamente la posición de cada punto en la imagen, entonces tendrá una buena aptitud. Desde luego que necesitamos un valor numérico para representar la aptitud, entonces se contará la cantidad de puntos que concuerdan con la rotación y traslación propuesta por el individuo.

Todos los individuos pasarán un número determinado de generaciones, y serán modificados con los operadores de selección, cruza y mutación. Al final, se escoge al mejor individuo como la solución final. Conocer cuál fue la rotación y traslación de la cámara permite saber indirectamente la cantidad de puntos nuevos en cada frame, y en consecuencia decidir qué imágenes aportan más información para la memoria visual.

Cuando te mostré el ejemplo simple con la función f(x) = x^2 o la función f(x) = x^3 + 10x^2 – 37x + 26, tal vez pensaste ¿para qué usar un algoritmo genético? Bueno para estos ejemplos sí que era innecesario. Sin embargo, para el problema de la selección de imágenes clave, ni siquiera podemos graficar la función de aptitud. En este caso, los algoritmos genéticos son de ayuda.

La anterior es una explicación de muy alto nivel de cómo usar un algoritmo genético para la construcción de un mapa visual topológico.

Sobre el autor

Otros artículos del autor

• Cómo es trabajar de Científico de Datos: Ejercicios Prácticos de Machine Learning
• Cómo empezar en Machine Learning y Encontrar Trabajo este 2021
• Cómo elegir un curso de Machine Learning con Python en Español en 2021

Referencias

1. López-Martínez, A., Cuevas, F. J., & Sosa-Balderas, J. V. (2019). Visual Memory Construction for Autonomous Humanoid Robot Navigation. In Progress in Optomechatronic Technologies (pp. 103-109). Springer, Singapore. Este artículo describe lo presentado en este post.
2. David E. G. (1998). Genetic Algorithms in search, optimization and machine learning. pp 1-25. Este libro fue escrito por el inventor de los algoritmos genéticos, ilustra a mayor detalle cómo funcionan.
3. Van Veen H., Distler H., Braun S., and Bulthoff H. (1998). Navigating through a virtual city: Using virtual reality technology to study human action and perception. Journal, Future Generation Computer Systems. Vol. 14. No. 3-4, pp 231-242. El artículo muestra cómo navegamos por un ambiente nuevo los humanos.
4. Delfin, J., Becerra, H. M., & Arechavaleta, G. (2018). Humanoid navigation using a visual memory with obstacle avoidance. Robotics and Autonomous Systems, 109, 109-124. En este artículo se explica cómo generar las leyes de control adecuadas para permitir la navegación autónoma dentro de una memoria visual con un robot humanoide Nao.
5. Zisserman, R. H. A. (2004). Multiple view geometry in computer vision. Este libro muestra cómo usar información visual (a partir de imágenes) para diversas aplicaciones como structure from motion, reconstrucción 3D o entendimiento de la escena.