Inteligencia Artificial y Algoritmos Genéticos – Parte 1

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

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


En una segunda parte de este artículo se expondrá, como ejemplo de aplicación de algoritmos genéticos, la construcción de una memoria visual para la navegación autónoma de robots.

Sobre el autor:

Alan es doctor en ciencias y coordinador del área dedicada a la investigación e implementación del Machine Learning y Ciencia de Datos en una empresa de TI. Le encanta aprender y enseñar sobre cómo lograr sistemas de aprendizaje de máquina prácticos y funcionales.

Blog personal: MachineLearningEnEspanol.com

 

En BI Geek, empresa tecnológica centrada en Business Intelligence, Big Data & IA, apostamos por un nuevo modelo de consultoría orientado a hacer accesibles las soluciones informacionales y de tratamiento de datos para cualquier tipo de empresa.

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

*
*

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.