¿Que es la Computación Evolutiva?

La computación evolutiva (en adelante CE) es una de las ramas de la Inteligencia Artificial que se aplica para la resolución de problemas de optimización combinatoria. La CE está inspirada en los mecanismos de evolución biológica propuestos por Darwin, Medel y Lamark. Sin entrar mucho en detalle sobre los estudios que hicieron estos científicos, solo vamos a mencionar brevemente lo que propusieron. Darwin propuso la "Selección natural de los más adaptados", Medel propuso la "Teoría corpuscular de la herencia" y Lamark propuso la "Herencia de caracteres adquiridos".

Como debéis saber muchos de vosotros, el principal problema de la inteligencia artificial es que no tiene una definición fácil o formal, pero para entendernos podemos decir que  la inteligencia artificial es una rama que trata de "imitar" a la inteligencia natural y por tanto la computación evolutiva se basa en imitar la evolución biológica tal y como la entendemos hoy en dia. Como podeis suponer la CE trata de resolver problemas de optimización combinatoria, con el fin de encontrar el mejor resultado al problema, es decir tal y como pasa en la naturaleza, ya que el gran problema que hay, sobre todo en el entorno animal; es la supervivencia y solo los más fuertes y mejor adaptados al entorno son capaces de sobrevivir y reproducirse; en otras palabras, son los mejores individuos posibles o la mejor solución al problema.

Aunque podemos "rizar mucho el rizo" la computación evolutiva se basa en la siguiente metáfora, denominada como metáfora evolutiva:

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

Dentro de lo que es la computación evolutiva, se engloban diferentes estrategias para la resolución de problemas de optimización. Estas estrategias son las siguientes:

1. Procesos de Búsqueda Evolutiva: Fue propuesta por Alan Turing en el año 1948.
2. Estrategias Evolutivas (EE): Propuesto por Rechenberg en 1964. Representan a los individuos con Vectores reales.
3. Programación Evolutiva (PE): Propuesto por Fogel en 1965. Utilizan máquinas de estado finito.
4. Algoritmos Genéticos (AG): Propuesto por Holland en 1975. Representan a los individuos como cadenas binarias.
5. Programación Genética (PG): Propuesto por Koza en 1992. Utilizan Arboles LISP.

Podemos decir que la diferencia que hay entre estos algoritmo evolutivos, es la forma en la que representan a los individuos. Hay que decir que la diferencia entre este tipo de algoritmos es irrelevante ya que conceptualmente hacen los mismo con distintas formas de representar a los individuos, por lo tanto lo mejor a la hora de utilizar los algoritmos evolutivos es elegir la representación más adecuada y los operadores de variación más adecuados para resolver el problema que tengamos que resolver.

El esquema general de un algoritmo evolutivo lo mostramos en la siguiente imagen:

A continuación mostramos el Pseudo-Código de un algoritmo evolutivo:

BEGIN
INICIALIZAR de forma aleatoria una población con soluciones candidatas EVALUAR cada candidato
REPEAT UNTIL ( CONDICIÓN DE TERMINACIÓN == true )
1. SELECCIONAR progenitores
2. RECOMBINAR progenitores seleccionados obteniendo descendencia 
3. MUTAR descendencia
4. EVALUAR nuevos candidatos
5. SELECCIONAR individuos para la próxima generación
END REPEAT 
END

Hasta ahora hemos visto a grandes rasgos en que se basa la CE y el Pseudocódigo de los algoritmos evolutivos, pero ¿Como representamos a los individuos?, ¿Como se reproducen y mutan los individuos? y ¿Que es eso de que un "individuo es suficientemente bueno"?. Pues vamos a responder a estas preguntas:

¿Como representamos a los individuos?

Basándonos en el conocimiento humano y haciendo una simplificación, diremos que cada persona tiene una información genetica única que se puede ver en el ADN de cada un@. Este ADN los forman 4 tipos de "elementos" que son la "Adenina" (A), "Timina" (T), "Citosina" (C) y "Guanina" (G), con lo que haciendo una gran simplificación podemos decir que las personas estamos representados por un "ARRAY" compuesto por alguno de estos 4 "elementos" con lo cual ya tenemos aqui una forma (o estructura de datos) para representar a los individuos. Esto, pasado a un problema de optimización combinatoria, significa que un posible resultado al problema lo podemos pasar a un array (por ejemplo un array binario de ceros y unos), al que le daremos un cierto significado. A este array que representa a un individuo del problema o una posible solución, se le denomina Cromosoma.

¿Como se reproducen y mutan los individuos?

Siguiendo con las simplificaciones, podemos decir que el proceso de reproducción no es mas que crear un nuevo individuo a partir de dos individuos dados, es decir combinando los dos arrays que representan a dos individuos. A continuación ponemos un ejemplo que como obtenemos un nuevo individuo a partir de dos:

A grandes rasgos es así como funciona la reproducción humana, ya que uno al nacer hereda unas características de la madre y otras del padre. Como se ve no se tiene porque heredar en partes iguales las características de los dos progenitores.

Por último en lo referente a la generación de nuevo individuos, existe la posibilidad de que "Mute" algún gen; es decir, que sin ninguna "lógica" (aunque supongo que biologicamente la tendrá) un determinado elemento del cromosoma cambie de valor, por ejemplo al valor complementario:

¿Que es eso de que un "individuo es suficientemente bueno"?

Como se ha comentado los Algoritmos Evolutivos sirven para resolver problemas de optimización combinatoria, pero tambien se ha de decir que no siempre alcanzan la mejor solución, por lo tanto hay que definir un umbral a partir del cual consideramos que la solución que buscamos es lo suficientemente buena. Este umbral se ha de obtener a partir de una "función de evaluación" que se ha de definir siempre que se utilicen algoritmos evolutivos. Esta función de evaluación es conocida como "Función de Fitness" aunque también se le suele denominar función de calidad, función de aptitud o función objetivo.

Como decía, esta función de fitness evaluará lo bueno o malo que es un individuo (o posible solución del problema) por lo tanto con esta función podemos utilizar dos estrategias para obtener la mejor solución al problema en función del conocimiento que tengamos del problema:

1. Sino tenemos mucha idea de la solución que nos dará el problema, pondremos el algoritmo evolutivo a ejecutarse hasta que complete 'N' generaciones y en la generación 'N' evaluaremos todos los individuos con la función de fitness y cogeremos como solución el individuo que mejor resultado nos haya dado con la función de fitness.
2. La segunda estrategia se utiliza cuando sabemos el umbral de calidad que queremos alcanzar para la solución del problema. En este caso se iran ejecutando generaciones (una por una) y tras cada generación se evaluaran todos los individuos con la función de fitness y si alguno cumple un determinado umbral de calidad, se parará de ejecutar el algoritmo, al haber alcanzado una buena solución.

Resumen y comentarios sobre la Computación Evolutiva

Hasta este punto hemos intentado explicar (a grandes rasgos) en que consiste la Computación Evolutiva a nivel teórico. Hay que decir que la CE es una rama de la inteligencia artificial muy interesante (sobre todo a los que nos gusta la inteligencia artificial) pero también se ha de dejar muy claro que no es "la panacea" y que no se ha de aplicar la CE para resolver cualquier problema ya que la CE no da los mejores resultados posibles a un problema aunque si puede dar un resultado bueno o "decente" a determinados problemas de los que no tenemos ni idea. Con esto quiero decir que a la hora de resolver un problema hay que analizarlo bien y ver como se pueden alcanzar las mejores soluciones. Existen algoritmos como el Backtracking (que mucho hemos sufrido 😉 ) que nos da la mejor solución para un problema de optimización combinatoria siempre que este problema tenga un espacio de búsqueda "tratable y finito" y para esos casos es mejor utilizar este algoritmo que no un algoritmo evolutivo. Si el problema tuviese una gran cantidad de datos que el Backtracking no pudiese darnos los resultados en un tiempo "prudencial" si que se podría utilizar los algoritmos evolutivos.

Otra de las aplicaciones erróneas que me he encontrado es la de utilizar algoritmos genéticos para encontrar el mínimo de una determinada función. Para resolver este problema es tan sencillo como derivar la función e igualarla a cero para obtener su mínimo. Este ejemplo lo digo porque en mucho sitios se ponen "ejemplos didácticos" de como obtener el mínimo de una función con algoritmos evolutivos, y precisamente la mejor forma de entender un algoritmo evolutivo es solucionando este tipo de problemas, que por algo son "ejemplos didácticos" pero no son ejemplo eficientes, así que cuidado con la utilización de estos algoritmos.

Mas adelante podremos un ejemplo de como resolver un determinado problema con algoritmos genéticos y ver detenidamente su ejecución.

Bibliografía

Parte de la información mostrada en esta entrada ha sido obtenida de los apuntes tomados en la asignatura de "Sistemas Inteligentes" impartida en el tercer curso de la carrera de Ingeniería Informática en la Escuela Universitaria de Informática de la UPM por el profesor Angel Arroyo y de la asignatura de "Inteligencia Artificial" impartida en segundo curso por los profesores Jesus Bernal y Jesus Bobadilla.