Este documento tiene como finalidad introducir el concepto de esta interesante herramienta de búsqueda y selección, proveniente de la inteligencia artificial, llamada algoritmos genéticos. Tal como lo sugiere su nombre, están basados en la teoría de la evolución de las especies. Se detallará el origen y definición de los algoritmos genéticos, así como sus aplicaciones, ventajas y desventajas.

Origen de los algoritmos genéticos

Antes de introducir el concepto de algoritmos genéticos, conviene enmarcar esta técnica dentro de un espectro más amplio; por ello, se definen en primer lugar los conceptos de inteligencia artificial y computación evolutiva.

Inteligencia artificial

La inteligencia artificial es un área multidisciplinaria, que a través de ciencias como la computación, la matemática, la lógica y la filosofía, estudia la creación y diseño de sistemas capaces de resolver problemas cotidianos por sí mismos, utilizando como paradigma la inteligencia humana. General y amplio como eso, reúne a amplios campos, los cuales tienen en común la creación de máquinas capaces de pensar. En ciencias de la computación, se denomina inteligencia artificial a la capacidad de razonar de un agente no vivo.

Computación evolutiva

La computación evolutiva es una rama de la inteligencia artificial que se aplica para la resolución de problemas de optimización combinatoria. Está inspirada en los mecanismos de evolución biológica Una gran variedad de algoritmos evolutivos han sido propuestos, pero principalmente pueden clasificarse en: algoritmos genéticos, programación evolutiva, estrategias evolutivas, sistemas clasificadores y programación genética. Esta clasificación se basa sobre todo en detalles de desarrollo histórico más que en el hecho de un funcionamiento realmente diferente; de hecho, las bases biológicas en las que se apoyan son esencialmente las mismas. Las diferencias entre ellos se centran en los operadores que se usan en cada caso y en general en la forma de implementar la selección, reproducción y sustitución de individuos en una población.

La computación evolutiva se fundamenta en la metáfora evolutiva, la cual se basa en los siguientes preceptos:

1. Una población de individuos coexiste en un determinado entorno con recursos limitados.
2. La competición por los recursos trae como consecuencia la selección de aquellos individuos que están mejor adaptados al entorno.
3. Estos individuos se convierten en los progenitores de nuevos individuos a través de procesos de mutación y recombinación.
4. Los nuevos individuos pasan a competir por su supervivencia.
5. Con el paso del tiempo, esta selección natural provoca el incremento en la “calidad” de los individuos de la población.

Gráfico 1 Metáfora evolutiva

Seguidamente, se hace una breve descripción de los algoritmos evolutivos mencionados:

1. Algoritmos genéticos: Resuelven los problemas generando poblaciones sucesivas a las que se aplican los operadores de mutación y cruce. Cada individuo representa una solución al problema y se trata de encontrar al individuo que represente a la mejor solución.
2. Programación genética: Funciona igual que los algoritmos genéticos pero se centra en el estudio de problemas cuya solución es un programa, de manera que los individuos de la población son programas que se acercan más o menos a realizar una tarea que es la solución.
3. Programación evolutiva: Es otro enfoque de los algoritmos genéticos, en este caso el estudio se centra en conseguir operadores genéticos que imiten lo mejor posible a la naturaleza, en cada caso, más que en la relación de los padres con su descendencia. En la programación evolutiva no se utiliza el operador de cruce, tomando la máxima importancia el operador de mutación.
4. Estrategias evolutivas: Se centran en el estudio de problemas de optimización e incluyen una visión del aprendizaje en dos niveles: a nivel de genotipo y a nivel de fenotipo.
5. Sistemas clasificadores: Engloban el estudio de problemas en los que la solución buscada se corresponde con toda una población.

¿Qué son los algoritmos genéticos?

El investigador de la Universidad de Michigan, John Holland, desarrolló una técnica a la cual se le llamó originalmente “planes reproductivos”. Sin embargo, sólo se hizo popular luego de 1975, como algoritmos genéticos. Cuando Holland desarrolló los algoritmos genéticos, lo hizo con un propósito diferente al que se les imputa hoy en día. Él quería lograr dos objetivos: El primero era abstraer y explicar el proceso de adaptación de la naturaleza y el segundo era diseñar un sistema artificial o programa informático que conservara los mecanismos de la selección natural. El propósito inicial de Holland estaba más ligado a la biología que a cualquier otra ciencia.

De manera muy general, los algoritmos genéticos consisten en una rutina de software que toma como entradas a los ejemplares y retorna como salidas cuáles de ellos deben generar descendencia para la nueva generación. Los algoritmos genéticos son métodos adaptativos que pueden usarse para resolver problemas de búsqueda y optimización. Están basados en el proceso genético de los organismos vivos. A lo largo de las generaciones, las poblaciones evolucionan en la naturaleza de acorde con los principios de la selección natural y la supervivencia de los más fuertes, postulados por Darwin. Por imitación de este proceso, los algoritmos genéticos son capaces de ir creando soluciones para problemas del mundo real.

Los algoritmos genéticos usan una analogía directa con el comportamiento natural. Trabajan con una población de individuos, cada uno de los cuales representa una solución factible a un problema dado. A cada individuo se le asigna un valor o puntuación, relacionado con la bondad de dicha solución. En la naturaleza, esto equivaldría al grado de efectividad de un organismo para competir por unos determinados recursos. Cuanto mayor sea la adaptación de un individuo al problema, mayor será la probabilidad de que el mismo sea seleccionado para reproducirse, cruzando su material genético con otro individuo seleccionado de igual forma. Este cruce producirá nuevos individuos, descendientes de los anteriores, los cuales comparten algunas de las características de sus padres. Cuanto menor sea la adaptación de un individuo, menor será la probabilidad de que dicho individuo sea seleccionado para la reproducción, y por tanto de que su material genético se propague en sucesivas generaciones.

De esta manera, se produce una nueva población de posibles soluciones, la cual reemplaza a la anterior y verifica la interesante propiedad de que contiene una mayor proporción de buenas características en comparación con la población anterior. Así, a lo largo de las generaciones, las buenas características se propagan a través de la población. Favoreciendo el cruce de los individuos mejor adaptados, van siendo exploradas las áreas más prometedoras del espacio de búsqueda. Si el algoritmo genético ha sido bien diseñado, la, población convergerá hacia una solución óptima del problema. En el Gráfico 2 se muestra el esquema general de un algoritmo genético:

Gráfico 2 Esquema general de un algoritmo genético

A partir de una población inicial de individuos, se procede a evaluar la bondad de cada uno. Luego se asigna un valor asociado a esa bondad, mediante una función de aptitud. Consecutivamente, se evalúa si la alternativa es suficientemente buena para dar una solución definitiva al problema; de ser así, el proceso iterativo se detiene. En caso contrario, deberá continuar. Posteriormente ocurre el proceso de reproducción, compuesto por la selección, la recombinación y la mutación. En el proceso de selección, se escogen los mejores individuos según el valor de aptitud que se les ha asignado, luego en la recombinación se intercambia la información genética de unos y otros y finalmente en algunos casos se emplea la mutación, que consiste en cambiar de alguna forma la información de uno o más genes dentro del individuo.

Ventajas de los algoritmos genéticos

Una clara ventaja de los algoritmos genéticos es que operan de forma simultánea con varias soluciones, en vez de trabajar de forma secuencial como las técnicas tradicionales. Esto significa que mientras otras técnicas solamente pueden explorar el espacio de soluciones hacia una solución en una dirección al mismo tiempo, y si la solución que descubren resulta no óptima, no se puede hacer otra cosa que abandonar todo el trabajo hecho y empezar de nuevo. Sin embargo, los algoritmos genéticos simplemente desechan esta solución no óptima y siguen por otros caminos.

Cuando se usan para problemas de optimización, resultan menos afectados por los máximos locales (falsas soluciones) que las técnicas tradicionales. Muchos algoritmos de búsqueda pueden quedar atrapados en los óptimos locales: si llegan a lo alto de una colina del paisaje adaptativo, descubrirán que no existen soluciones mejores en las cercanías y concluirán que han alcanzado la mejor de todas, aunque existan picos más altos en algún otro lugar del mapa.

Entre otras ventajas de los algoritmos genéticos está la habilidad que poseen para manipular muchos parámetros simultáneamente. No necesitan conocimientos específicos sobre el problema que intentan resolver y su ejecución en las modernas arquitecturas masivas en paralelo está relativamente exenta de complicaciones.

Desventajas de los algoritmos genéticos

Pueden tardar mucho en converger, o no converger en absoluto, dependiendo en cierta medida de los parámetros que se utilicen: Tamaño de la población, número de generaciones, etc. También pueden converger prematuramente debido a una serie de problemas de diversa índole; si un individuo que es más apto que la mayoría de sus competidores emerge muy pronto en el curso de la ejecución, se puede reproducir tan abundantemente que merme la diversidad de la población demasiado pronto, provocando que el algoritmo converja hacia el óptimo local que representa ese individuo, en lugar de rastrear el paisaje adaptativo lo bastante a fondo para encontrar el óptimo global. Esto es un problema especialmente común en las poblaciones pequeñas, donde incluso una variación aleatoria en el ritmo de reproducción puede provocar que un genotipo se haga dominante sobre los otros.

La representación o codificación del individuo para generar la población

Los individuos se representan mediante un arreglo de caracteres, que contienen toda la información que permite dar solución al problema a resolver. El individuo puede estar codificadoen forma binaria o en parámetros reales, es decir, que en el individuo está codificado el número como tal o puede estar la representación binaria del número.

La codificación de los individuos tiene un gran impacto en el funcionamiento del algoritmo genético. La optimización es función de la representación de los datos; una codificación errada puede conducir incluso a la necesidad de abortarla pues las soluciones obtenidas pueden no cumplir con las restricciones del problema. Por el contrario, si se escoge acertadamente, puede conducir a una convergencia rápida y además facilita la programación del algoritmo. Entre los tipos (binario y parámetros reales) de codificación no existe uno absolutamente mejor que el otro. Cuando se emplea la codificación con parámetros reales, ocurre un acercamiento entre la optimización clásica y los algoritmos genéticos, pero no existe una gran cantidad de estudios sobre esta forma de representación de los individuos.

Evaluación y asignación de aptitud

La categorización de los individuos se hace a partir de su aptitud hacia el problema. Cuando se tiene una población muy grande de individuos, es necesario saber qué tan bueno es cada uno de ellos para proceder a seleccionar su información y transmitirla a nuevas generaciones. Para ello se asigna una función de aptitud y se evalúa para cada individuo. La función arroja un valor numérico, el cual permite conocer qué tan bueno es cada uno de los individuos.

La “bondad” de cada individuo se evalúa a partir de la función objetivo y las restricciones, con una función de aptitud. Cuando los problemas tienen restricciones es necesario implementar “penalizaciones”. Las restricciones deben plantearse en forma de inecuaciones y el incumplimiento de las restricciones debe penalizarse en la función de aptitud. Es decir que el incumplimiento de una o alguna de las restricciones le resta aptitud al individuo y por consiguiente se hace menos probable que su información sea transmitida.

Es necesario aclarar la diferencia que existe entre la función objetivo y la función de aptitud. La función objetivo sólo define la ecuación que se busca optimizar, mientras que la función de aptitud tiene en cuenta el valor de la función objetivo y también el cumplimiento o incumplimiento de las restricciones, Los individuos se seleccionan según su aptitud y a partir de dicho valor se hace la categorización sobre cuáles individuos y en qué proporción, van a contribuir con su información en las nuevas generaciones, La selección de los individuos tiene que estar entonces precedida por la asignación de aptitud.

Selección

La selección de los individuos que van a transmitir información genética a las siguientes generaciones se hace con base en su aptitud. El objetivo primordial de esta operación es escoger las buenas soluciones y eliminar las malas. Existen varios tipos de selección entre los cuales se encuentran: La selección por torneo, la selección proporcional y la selección por ranking.

La selección por torneo opera haciendo torneos entre pares de individuos y haciendo copia de los individuos que ganen cada torneo. Con las copias de los individuos ganadores se conforma una nueva población. Se deben realizar tantos torneos como individuos se desean obtener luego de la selección. La selección por torneo opera mediante la comparación entre pares de individuos. De esa forma, se espera que los individuos más aptos sean seleccionados y los menos aptos sean descartados.

La selección proporcional puede ser asociada con una ruleta ya que funciona bajo el mismo principio. Se conforma una circunferencia y a cada individuo se le asigna una porción proporcional a la magnitud de su valor de aptitud. Si dicha ruleta se pone a girar y existe un indicador fijo, hay más probabilidad de que el indicador apunte a la porción de mayor magnitud cuando ésta se detenga. La técnica de selección proporcional es más exigente al momento de programarse debido a que es necesario simular todo el proceso de la ruleta. Además, este tipo de selección presenta problemas cuando los valores de aptitud entre los individuos son o muy parejos o muy disparejos.

La selección por ranking opera mediante la organización de los individuos según su valor de aptitud. Se enumeran en una lista de peor a mejor y se les asigna un nuevo valor de aptitud igual al puesto en el cual quedaron. Finalmente, se hace el proceso de selección proporcional sobre los individuos a partir del nuevo valor de aptitud.

Recombinación o cruce

La reproducción se ha iniciado ya con el proceso de selección. Tal proceso es anterior a la recombinación ya que se busca que a ésta instancia lleguen solo los individuos dentro de la población que mejor información genética contengan. En la recombinación se mezcla la información genética de los individuos seleccionados para generar nuevos individuos presumiblemente mejores.

La recombinación o cruce consiste en intercambiar la información contenida en los cromosomas escogiendo uno o más puntos de cruce. Trata de recrear la reproducción hembra-macho, en la cual la información del padre se mezcla con la de la madre para producir un nuevo individuo. El hijo, ese nuevo individuo que resulta de la recombinación, puede ser mejor que sus padres pues podría heredar lo mejor del uno y del otro. Aunque existen diversos métodos de recombinación, se describirán solamente los dos métodos utilizados por el software usado para este trabajo de investigación: Cruce de un punto y cruce de dos puntos.

En el cruce de un punto (ver Gráfico 3), los individuos que se recombinarán son divididos en dos partes, en algún punto aleatorio. La primera parte del padre1 se intercambia con la primera parte 2, dando como resultado dos hijos, 1 y 2. El cruce de dos puntos (ver Gráfico 4) es similar al cruce de un punto, con la diferencia de que cada individuo es dividido en dos puntos aleatorios en vez de uno, y se intercambian las porciones medias de cada individuo. La diferencia práctica entre los dos métodos es que el método de cruce doble usualmente genera individuos con menor cambio con respecto a sus padres.

Gráfico 3 Cruce de un punto

Gráfico 4 Cruce de dos puntos

Mutación

Tras la recombinación, tiene lugar la mutación. En términos de evolución, la mutación se manifiesta de forma extraordinaria. Las mutaciones suelen en promedio ser beneficiosas ya que contribuyen a la diversidad genética de la especie. Además, previenen a las soluciones de la población de verse limitadas por un óptimo local. La mutación consiste en modificar ciertos genes de forma aleatoria atendiendo a la probabilidad de ocurrencia establecida con anterioridad. La mutación depende de la codificación y de la reproducción. Si se abusa de la mutación se puede caer en el uso del algoritmo genético como una simple búsqueda aleatoria. Por consiguiente, antes de aumentar las mutaciones, conviene estudiar otras soluciones que aporten diversidad a la población como podría ser el aumento el tamaño de la población o garantizar la aleatoriedad de la población inicial.

Para el caso de una codificación binaria, la mutación consiste simplemente en la inversión del gen mutado que corresponderá con un bit. En el caso de una codificación numérica, la mutación podría consistir en sustituir un número por otro o intercambiar un número por otro que está en otra posición del cromosoma.

Bibliografía

1. Moya, R. (2.013, mayo). ¿Qué es la Computación Evolutiva? Extraído el 6 de julio de 2.016 desde http://www.jarroba.com/computacion-evolutiva-ejemplo-con-un-algoritmo-genetico/
2. Alfaro, E. (n.d). Algoritmos genéticos. Extraído el 6 de julio de 2.016 desde http://www.eddyalfaro.galeon.com/geneticos.html
3. Arranz de la Peña, J. ParraTruyol, A. (n.d). Algoritmos genéticos. España. Extraído el 6 de julio de 2.016 desde http://www.it.uc3m.es/jvillena/irc/practicas/06-07/05.pdf.
4. Wikipedia.org. (n.d). Inteligencia artificial. Extraído el 6 de julio de 2.016 desde https://es.wikipedia.org/wiki/inteligencia_artificial.