Algoritmos Genéticos I: Resolución de problemas mediante computación evolutiva

1. Que son los Algoritmos Genéticos

    1.1 Algoritmos Evolutivos

Dentro de las líneas de la Inteligencia artificial y en contraposición a la búsqueda local, existen otras estrategias que llevan a cabo una búsqueda global mediante el uso de un conjunto de soluciones en lugar de una sola. Estos algoritmos se denominan Algoritmos Evolutivos.

Son llamados así por que se inspiran en la evolución biológica, basándose a su vez en la teoría de Darwin sobre la evolución natural. En este contexto, los Algoritmos evolutivos llevan a cabo una búsqueda mediante evolución de una población de individuos.

Este tipo de algoritmos se basan en los siguientes principios:

• Los individuos tienen capacidad para reproducirse.
• Existe una población de tales individuos.
• Existe variedad/diferencia entre dichos individuos.
• La adaptación al medio y la capacidad de supervivencia depende de dichas diferencias.
• Los individuos mejor adaptados obtienen mayor descendencia.
• La evolución es un proceso que opera sobre los cromosomas más que sobre las estructuras de la vida que están codificadas en ellos.

     1.2 Evolución artificial

Dentro de la evolución artificial se encuentran diferentes modelos de evolución basados en poblaciones, cuyos elementos representan soluciones potenciales al problema.

Es decir, una población sería una serie de soluciones, óptimas o no, de un problema concreto al que se quiere dar solución. Y cada una de esas soluciones representa un elemento de la población.

Desde un punto de vista computacional, la simulación de este proceso en un ordenador resulta ser una técnica de optimización probabilística, que con frecuencia mejora a otros métodos clásicos en problemas difíciles.

De este modo, se puede establecer la siguiente metáfora:

• Evolución natural vs Evolución artificial
• Individuo    - Solución candidata.
• Adaptación - Calidad.
• Entorno      - Problema

    1.3 Algoritmos Genéticos

Dentro de la computación evolutiva, se encuentra uno de los principales exponentes de este paradigma: Los Algoritmos Genéticos (AGs).

Dentro de estos algoritmos, la idea es mantener una población de cromosomas que codifican a los individuos y que permite a estos mejorar mediante un proceso evolutivo, de tal forma que se incluye un proceso de selección y de recombinación que hace que estos individuos sean cada vez mejores.

A continuación se puede observar la descripción de un AGs de forma gráfica y con todo detalle, donde el ciclo básico de un AG es el siguiente:

De este modo para definir un AG se deben especificar los siguientes componentes:

• Representación: definición de los individuos.
• Función de evaluación/fitness.
• Población: tamaño fijo o variable, cuantos individuos, como están formados...
• Mecanismo de selección.
• Operadores de variación: cruce y mutación.
• Mecanismo de sustitución de la población.

Una vez especificados los componentes, se debe estableces una representación del AG que establecerá como son representados cada uno de los individuos de la población y esta en su totalidad.

Sin duda la codificación más usada ha sido la representación binaria. Esta representación se ha usado no sólo para problemas cuya codificación natural es la binaria, sino también para problemas cuyos parámetros toman valores enteros o reales.

Por otro lado, la representación entera es mucho más natural que la binaria cuando tenemos un conjunto mayor que dos pero pequeño y finito para cada parámetro del problema.

Ejemplo: Los colores del grafo, el número de consecuentes para una regla, ...

Además puede representar el AG como una serie de permutaciones, la cual, es una representación muy utilizada en problemas relacionados con grafos.

Por último, también se podrá encontrar una Codificación real donde cada parámetro es representado por un número real, no siendo necesario sustituirlo.

    1.4 Función de Evaluación.

La función de evaluación mide el grado de adecuación o bondad de un individuo. Es decir, como de bueno es ese individuo o solución.

Aunque en ocasiones la función de evaluación es directa, por ejemplo, una expresión matemática,
también se puede encontrar que el individuo es decodificado en otra representación más o menos compleja y entonces podría ser evaluada según los criterios que se establezcan según el contexto de aplicación. (Ej: El caso de la optimización del movimiento en un robot).

• En los algoritmos genéticos interactivos la evaluación de un individuo es aportada por un experto humano (ejem: evaluación de pinturas, composiciones, etc).

• En ocasiones, la función de evaluación real es tan costosa que es necesario usar una función sucedánea (surrogate).

    1.5 Población de individuos.

Una población es un conjunto de individuos o soluciones potenciales. Debemos considerar los siguientes aspectos relativos a la población de un AG:

• Tamaño de la población.
• Pequeño: tendremos poca diversidad y un alto riesgo de convergencia prematura (a un óptimo local).
• Grande: gran diversidad pero proceso de convergencia más lento y mayor coste en número de evaluaciones.
• ¿Variable o fijo?.
• Normalmente se usan poblaciones fijas.
• Variables: empezar con población grande (diversidad) e ir acotando el tamaño conforme la búsqueda avanza (intensificación).

• ¿Informada o aleatoria?.
• Una población aleatoria tiene la ventaja de distribuir soluciones por todo el espacio de búsqueda.
• Una población informada aporta buenas configuraciones al principio que pueden acelerar la convergencia.
• • Una población muy informada nos puede llevar rápidamente a una convergencia prematura a óptimos locales.

    1.6 Mecanismos de Selección de individuos

El mecanismo de selección juega un papel muy importante puesto que se encarga de decidir qué individuos van a pasar directamente a la generación siguiente o serán padres de los futuros descendientes, es decir, decide que individuos son los mejores.

A continuación se presentan algunos métodos de selección:

 1.- Selección proporcional a la función de evaluación (fitness). En este caso, cada individuo tiene la probabilidad directamente proporcional al fitness de ser seleccionado.

Por ejemplo: Si se ha declarado una función de evaluación como la que se puede ver a continuación:

• fitness( i ) = 40, 25, 12, 9, 4, 3, 3, 2, 1, 1.

El mecanismo de selección puede seleccionar el siguiente individuo:

• Proceso de Selección -->; ps( i ) = 4, 25, 12, 09, 04, 03, 03, 02, 01, 01.

Se ha de mencionar que el principal peligro es que un "SuperIndividuo" rápidamente cope la población y no se encuentren individuos mejores.

 2.- Selección basada en rango. Se trata de de atenuar la presión selectiva del modelo anterior. Para ello, si la población tiene tamaño N, asignaremos N puntos al mejor individuo, N − 1 al segundo, etc. De este modo, se finalizará calculando la probabilidad de selección proporcional a dichos puntos.

En nuestro ejemplo:

• fitness( i ) = 40, 25, 12, 9, 4, 3, 3, 2, 1, 1.
• ps(i) = 18, 16, 15, 13, 11, 09, 07, 05, 04, 02.

Nótese que si N = 100 el mejor individuo (por bueno que sea) obtendría ps() = 0,02.

 3.- Selección por torneo. Intenta disminuir todavía más la presión selectiva. Cada individuo se selecciona usando el siguiente procedimiento:

• Sea k (3, 4, 5, ..) el tamaño de torneo.
• Escoger aleatoriamente k individuos.
• Seleccionar el mejor individuo de los k escogidos.
• Nótese que cada individuo intervendrá (en media) en k torneos.

    1.7 Operador de Variación.

Dentro de los Algoritmos genéticos, se pueden encontrar dos operadores genéticos: cruce y mutación. Estos nos permiten crear nuevos individuos que nos permitan aproximarnos a la mejor solución posible.

De este modo, el operador de cruce o recombinación consiste en combinar la información de dos padres para crear (habitualmente) dos descendientes (que pueden ser mejores o peores).

Es importante tener en cuenta que el cruce es explorativo, por lo que probablemente nos va a conducir a zonas entre los dos padres. En este sentido es muy importante saber que no introduce nuevo material genético (diversidad).

Por otro lado el operador de mutación consiste en cambiar levemente el genotipo de un individuo (p.e. invirtiendo el valor de un bit). Por tanto, la probabilidad de mutación (pm) se aplica (normalmente) a nivel de gen y suele ser muy pequeña (0.01, 0.0001, ...).

Este operador, a diferencia de los operadores de cruce, es de carácter explotativo puesto que implica que pequeños cambios exploten la vecindad próxima de un individuo.

De este modo, la mutación es el único operador que introduce nuevo material genético (diversidad).

    1.8 Operadores de cruce: Representación Binaria / Entera.

Algunos de los más típicos son:

• Cruce por 1 punto. Se elige una posición como punto de cruce. Hasta ella se copia la información de los padres en los hijos, pero a partir de ella se copia del otro padre.

• Cruce por varios puntos. Es una extensión del anterior.

• Cruce uniforme. Se crea un máscara y se va copiando gen a gen en uno u otro padre en función de la máscara.

    1.9 Operadores de cruce: Codificación Real.

Cuando los individuos se representan por vectores de números reales (codificación real) los operadores anteriores pierden mucho valor. Los siguientes pueden ser buenos sustitutos:

• Cruce aritmético simple. Se elige un punto de cruce (k) y hasta él se copia la información de los padres en los hijos. A partir de él, el valor de la posición i-ésima se calcula

como:

• hijo1[i] = _padre1[i] + (1 − α)padre2[i]
• hijo2[i] = _padre2[i] + (1 − α)padre1[i]

• Cruce aritmético completo. La expresión anterior se aplica a todas las posiciones.

  1.0 Operadores de cruce para permutaciones.

Cuando se van a realizar permutaciones los cruces anteriores no tienen ningún sentido y dan en la mayoría de los casos soluciones no válidas.

Hay muchas propuestas específicas pero en este caso, vamos a centrarnos en una de ellas a modo de curiosidad.

Cruce 2PCX (Two-points center crossover):

1. Elegir dos posiciones (puntos de cruce) aleatoriamente: l y r.
2. Copiar las posiciones hasta l − 1 de padre1 en hijo1 y de padre2 en hijo2.
3. Copiar las posiciones desde r + 1 de padre1 en hijo1 y de padre2 en hijo2.
4. Rellenar el segmento [l,r] de padre1 con los valores que contiene pero usando el orden de dichos valores en padre2.
5. Rellenar el segmento [l,r] de padre2 con los valores que contiene pero usando el orden de dichos valores en padre1.

A continuación se puede observar en un ejemplo:

Sea Padre1 = (531264) y Padre2 = (216534)

- Elegimos las posiciones 3 y 5 como puntos de cruce:

• Padre 1 = (53 | 126 | 4). 
• Padre 2 = (21 | 653 | 4).

- Copiamos las posiciones que no están entre los puntos de cruce:

• Hijo 1 -- h1 = (53 | — | 4).
• Hijo 1 -- h2 = (21 | — | 4).

- Vemos que los valores 126 en Padre2 se encuentran en el orden: 216, por tanto:

• h1 = (53 | 216 | 4).

- Vemos que los valores 653 en Padre1 se encuentran en el orden: 536, por tanto:

• h2 = (21 | 536 | 4).

De este modo tenemos dos nuevos hijos:

• h1 = (53 | 216 | 4).
• h2 = (21 | 536 | 4).

    1.11 Operadores de mutación.

La mutación se encarga de introducir nuevo material genético, es decir, se cambia o altera la forma de un individuo en sí, veamos algunos ejemplos:

• Codificación binaria o entera. Cambiar (aleatoriamente) el valor de una posición por otro de los posibles para ese gen.

• Codificación real. En este tipo de mutaciones podemos cambiar el valor de un gen por otro creado de forma aleatoria en el intervalo en que dicho gen toma valores o por otro lado realizar permutaciones de Intercambio e inserción. (Véase a continuación de forma gráfica)

    1.12 Criterios de Parada.

Cuando se lanza un algoritmo genético para la resolución de un problema es importante establecer "Criterios de parada" que determinen cuando se ha encontrado la solución o cuando se está lo suficientemente cerca de encontrarla. En este contexto podemos ver diferentes criterios de parada, aunque pueden darse múltiples interpretaciones.

• Hasta que la población converja:
• (Casi) todos los individuos de la población son el mismo.
• (Casi) todos los individuos tienen el mismo valor para cada gen.
• número fijo de generaciones.
• número fijo de evaluaciones de fitness.
• número fijo de generaciones sin mejorar el mejor (o la media)
• .......

2. Ejemplo práctico.

Como el movimiento se demuestra andando, desde mi punto de vista, es una buena idea crear una entrada con un ejemplo práctico que permita asimilar de una forma correcta la teoría aquí expuesta.

De este modo, crearé un ejemplo práctico y publicaré el enlace a continuación, aunque de momento...