Introducción a la Computación Evolutiva

 

Los algoritmos genéticos se encuadran dentro de la clase de algoritmos que presentan ciertas analogías con los procesos biológicos de la naturaleza. Están incluidos, por tanto, en el marco de la Bioinformática, área de especialización encargada de estudiar modelos y técnicas basándose en patrones biológicos y aprovechando las metodologías y técnicas informáticas. La bioinformática, trata de dar solución a una gran variedad de problemas de un amplio domino científico.

 

Dentro de este campo, nos encontramos con la Computación Evolutiva, que es un enfoque alternativo para abordar problemas complejos de búsqueda y aprendizaje a través de modelos computacionales de procesos evolutivos. Las implementaciones concretas de tales modelos se conocen como algoritmos evolutivos. El propósito genérico de los algoritmos evolutivos consiste en guiar una búsqueda estocástica haciendo evolucionar a un conjunto de estructuras y seleccionando de modo iterativo las más adecuadas.

 

La computación evolutiva parte de un hecho observado en la naturaleza: los organismos vivos poseen una destreza consumada en la resolución de los problemas que se les presentan, y obtienen sus habilidades, casi sin proponérselo, a través del mecanismo de la evolución natural. La evolución se produce, en casi todos los organismos, como consecuencia de dos procesos primarios: la selección natural y la reproducción sexual. La primera determina qué miembros de la población sobrevivirán hasta reproducirse (es un proceso sencillo: cuando un organismo falla una prueba de idoneidad, muere). La reproducción sexual garantiza la mezcla y recombinación de genes en la descendencia de un organismo.

 

Las condiciones que determinan un proceso evolutivo en la naturaleza son:

 

 

En los siguientes apartados nos centraremos en el grupo más importante de la computación evolutiva: los algoritmos genéticos, donde explicaremos los conceptos básicos de los mismos.

 

 

Algoritmos Genéticos

 

Como ya hemos mencionado anteriormente, los algoritmos genéticos ocupan el lugar central dentro de la computación evolutiva. Las razones de esta preeminencia son tanto teóricas como prácticas, siendo las más importantes:

 

 

 

 

 

 

 

 

 

Después de enumerar estas características podríamos definir los algoritmos genéticos, de forma general, como "métodos estocásticos de búsqueda ciega de soluciones cuasi-óptimas. En ellos se mantiene una población que representa un conjunto de posibles soluciones, la cual es sometida a ciertas transformaciones con las que se trata de obtener nuevos candidatos, y un proceso de selección sesgado en favor de los mejores candidatos".

 

Decimos que la búsqueda es ciega porque no se dispone de ningún conocimiento específico del problema, de manera que la búsqueda se basa exclusivamente en los valores de la función objetivo. Es también una búsqueda codificada, ya que no se trabaja directamente sobre el dominio del problema, sino con representaciones de sus elementos; múltiple, porque busca simultáneamente entre un conjunto de candidatos; y estocástica, referida tanto a las fases de selección como a las de transformación, con lo que se obtiene control sobre el factor de penetración de la búsqueda.

 

 

Todo esto hace que los algoritmos genéticos proporcionen una mayor robustez a la búsqueda, esto es, más eficiencia sin perder generalidad.

 

 

Goldberg justifica esta afirmación del siguiente modo:

 

"Los algoritmos genéticos manejan variables de decisión o de control representadas como cadenas con el fin de explotar similitudes entre cadenas de altas prestaciones. Otros métodos tratan habitualmente con las funciones y sus variables de control directamente. Dado que los algoritmos genéticos operan en el nivel de códigos, son difíciles de engañar aun cuando la función sea difícil para los enfoques tradicionales.

 

Los algoritmos genéticos trabajan con una población; muchos otros métodos trabajan con un único punto. De este modo, los algoritmos genéticos encuentran seguridad en la cantidad. Al mantener una población de puntos bien adaptados se reduce la probabilidad de alcanzar un falso óptimo.

 

Los algoritmos genéticos consiguen gran parte de su amplitud ignorando la información que sea la del objetivo. Otros métodos se basan fuertemente en tal información, y en problemas donde la información no está disponible o es difícil de conseguir, estos otros métodos fallan. Los algoritmos genéticos son generales porque explotan la información disponible en cualquier problema de búsqueda. Los algoritmos genéticos procesan similitudes en el código subyacente junto con información proveniente de la ordenación de las estructuras de acuerdo con sus capacidades de supervivencia en el entorno actual. Al explotar una información tan fácilmente disponible, los algoritmos genéticos se pueden aplicar en prácticamente cualquier problema.

 

Las reglas de transición de los algoritmos genéticos son estocásticas; otros muchos métodos tienen reglas de transición deterministas. Hay una diferencia, no obstante, entre los operadores estocásticos de los algoritmos genéticos y otros métodos que no son más que paseos aleatorios. Los algoritmos genéticos usan el azar para guiar una búsqueda fuertemente explotadora. Esto puede parecer inusual, usar el azar para conseguir resultados concretos (los mejores puntos), pero hay gran cantidad de precedentes en la naturaleza."

 

 

Estructura y componentes básicos

 

El siguiente gráfico muestra la estructura genérica de del bucle básico de un algoritmo genético:

 

 

El proceso se describe como sigue: una población Pop, que consta de n miembros se somete a un proceso de selección para constituir una población intermedia AuxPop de n criadores. De dicha población intermedia se extrae un grupo reducido de individuos llamados progenitores que son los que efectivamente se van a reproducir. Sirviéndose de los operadores genéticos, los progenitores son sometidos a ciertas transformaciones de alteración y recombinación en la fase de reproducción, en virtud de las cuales se generan s nuevos individuos que constituyen la Descendencia. Para formar la nueva Pop[t+1], se deben seleccionar n supervivientes de entre los n+s de la población auxiliar y la descendencia, lo que ocurre en la fase de reemplazo. El cuadrado rayado hace referencia a la selección, la cual se realiza en dos etapas con la idea de emular las dos vertientes del Principio de Selección Natural: selección de craidores o selección a secas, y selección de supervivientes para la próxima generación o reemplazo.

 

El proceso descrito, puede ser expresado de forma algorítmica del siguiente modo:

 

t = 0

Inicializar Población(t)

Evaluar Población(t)

Mientras (nos se verifique la condición de parada) hacer

t = t +1

Seleccionar Población(t) a partir de Población(t-1)

Recombinar Población(t)

Evaluar Población(t)

FinMientras

 

Terminología:

 

Generalmente cada individuo de la población se representa por medio de una cadena binaria de longitud fija, que suele denominarse ‘ejemplar’, ‘muestra’, ‘punto’ o ‘cromosoma’, la cual codifica los valores de las variables que intervienen en el problema. Representaremos un individuo por medio de x.

 

El tamaño de la población permanece fijo entre generación y generación, siendo la población inicial totalmente aleatoria.

 

Durante la iteración t, representamos por Población(t) el conjunto de posibles soluciones que mantiene el sistema. Cada solución será de la siguiente forma, xti. Así:

 

Población (t) = {xt1, . . . , xtn}

 

siendo n el tamaño de la población.

 

En el proceso de evaluación, lo que se hace es evaluar cada solución mediante una función f que nos da una medida de la adecuación o fitness de la misma. Así f(xti) es una medida de la bondad de la solución xi en la iteración t. Cada individuo contribuye al proceso de reproducción en proporción a su correspondiente fitness. De esta forma, individuos bien adaptados, contribuyen con múltiples copias e individuos mal adaptados contribuyen con pocas o incluso ninguna copia.

 

Definimos como genotipo, a las estructuras que representan los individuos. Los caracteres o rasgos por los que están formados los individuos, se les denomina genes. Cada una de las posiciones de la cadena, es lo que se llama loci. Cada carácter o gen puede manifestarse de forma diferente, es decir, puede tomar distintos valores que son denominados alelos. Una estructura decodificada es un fenotipo.

 

 

 

Mecanismos de muestreo de poblaciones

 

Un mecanismo auxiliar pero fundamental para los algoritmos genéticos es le muestreo de poblaciones, esto es, la elección según unos criterios de un subconjunto de k individuos de una población especificada. Los mecanismos de muestreo son muy variados, distinguiéndose tres grupos fundamentales según el grado de intervención del azar en el proceso:

 

  1. Muestreo directo: se toma un subconjunto de individuos de las población siguiendo un criterio fijo, del estilo "los k mejores", "los k peores", "a dedo", etc...
  2.  

     

  3. Muestreo aleatorio simple o equiprobable: se asignan a todos los elementos de la población base las mismas probabilidades de formar parte de la muestra y se constituye ésta mediante ensayos de Bernoulli simples.
  4.  

     

  5. Muestreos estocásticos: se asignan probabilidades de selección o puntuaciones a los elementos de la población base en función (directa o indirecta) de su aptitud. Por defecto, la puntuación pi, asociada al individuo xi de la población P={x1,...,xn}, se calcula como la aptitud relativa de dicho individuo: esto es, siendo u1, . . ., un las respectivas aptitudes se tiene que

 

 

ui

Pi = -----------------

u1+u2+...+un

 

Existen muchos mecanismos de muestreo estocático según para lo que se apliquen. En concreto, al implementar algoritmos genéticos se usan fundamentalmente cuatro tipos de muestreo estocástico:

 

  1. Por sorteo: se consideran las puntuaciones estrictamente como probabilidades de elección para formar la muestra, y se contituye ésta realizando k ensayos de una variable aleatoria con dicha distribución de probabilidades
  2.  

     

  3. Por restos: A cada individuo xi, se le asignan directamente pi·k puestos en la muestra. Seguidamente los individuos se reparten los puestos vacantes en función de sus puntuaciones. El reparto suele ser por sorteo.
  4.  

     

  5. Universal o por ruleta: es análogo al muestreo por sorteo sólo que ahora se genera un único número aleatorio simple r y con él se asignan todas las muestras de modo parecido a como se haría girar una ruleta.
  6.  

     

  7. Por torneos: cada elemento de la muestra se toma eligiendo el mejor de los individuosde un conjunto de z elementos tomados al azar de la población base; esto se repite k veces hasta completar la muestra. El parámetro z suele ser un entero pequeño comparado con el tamaño de la población base, normalmente 2 o 3. Nótese que en este caso no es necesario hacer la asignación de puntuacines.

 

 

A su vez, todos estos mecanismos admiten algunas variantes no necesariamente excluyentes; las más empleadas al trabajar con algortimos genéticos son estas tres:

 

  1. Muestreo diferenciado: cada elemento de la población base se puede tomar para formar la muestra a lo sumo una sola vez
  2.  

     

  3. Muestreo conservador: todos los elementos de la población base tienen alguna oportunidad (probabilidad no nula) de ser elegidos. También se conoce como "muestreo duro".
  4.  

     

  5. Muestreo excluyente: se excluyen a priori algunos individuos del proceso de muestreo. También se llama "muestreo extintivo"

 

De esta manera se habla, por ejemplo, de que el proceso de selección de criadores de cierto algoritmo genético se ha implementado a través de un "muestreo estocástico por torneos de tamaño 2 en la variedad conservsdora".

 

 

 

Procedimientos básicos de un algortimo genético

 

Una vez vistos los principales mecanismos de muestreo, se pueden describir los tres procedimientos básicos de que consta un algoritmo genético: selección (de criadores), reproducción (o transformación) y reemplazo (o selección de supervivientes). Nótese que para implementar un algoritmo genético se requiere un mínimo de dos parámetros: el tamaño de la población n y el tamaño de la descendencia s.

 

Proceso de selección: consiste en muestrear, a partir de la población inical, los n elementos de la población de criadores. El criterio concreto de muestreo depende del problema y del buen juicio del programador. Los más usados en la práctica son los muestreos por sorteo, universal y pot torneos, en sus variedades conservadoras. Los muestreos deterministas se usan muy poco, entre otros motivos porque van en contra de la filosofñia del método.

 

Proceso de reproducción: aplicando los operadores de transformación (cruce, mutación, inversión...), sobre ciertos miembros de la población de criadores se obtiene una descendencia de s nuevos miembros. Cuanto más grande sea el valor de s más variará la población de una generación a otra. Salvo indicación en contra, lo más común es trabajar con valores de s no mayores del 60% de n.

 

Existen dos grupos de operadores que nunca faltan en un algoritmo genético: el cruce y la mutación. Los operadores de cruce son el arquetipo de los operadores de recombinación: actúan sobre parejas de individuos y normalmente originan otro par de individuos que combinan características de los progenitores. Dado que en los algoritmos genéticos los individuos están representados a través de cadenas, el cruce se lleva a cabo por intercambio de segmentos.

 

Los operadores de mutación, por su parte, son el arquetipo de operadores de alteración, dado que actúan sobre individuos en particular, realizando una pequeña modificación en alguno de sus genes o en el conjunto.

 

El motivo de hacer esta separación es el siguiente: entendiendo que la búsqueda propiamente dicha se lleva a cabo en la fase de reproducción, resulta conveniente diferenciar los operadores de búsqueda en profundidad de los de búsqueda en anchura: los primeros se encargarán de explotar las mejores características de que disponga la población actual, los otros se encargarán de explorar nuevos dominios en busca de mejores soluciones. Desde esta perspectiva, los operadores de cruce son los que principalmente se encargan de la búsqueda en profundidad y los de mutación de la búsqueda en anchura. Así, dando mayor importancia a unos o a otros se puede ajustar el tipo de búsqueda a las necesidades del problema.

 

Proceso de reemplazo: a partir de los n miembros de la población de criadores y de los s miembros de la población de descendientes se debe obtener una nueva población de n miembros. Para hacerlo existen diferentes criterios:

  1. Reemplazo inmediato ( o al vuelo): los s descendientes sustituyen a sus respectivos progenitores
  2.  

     

  3. Reemplazo con factor de llenado: los s descendientes sustituyen a aquellos miembros de la población de criadores que más se les parezcan.
  4.  

  5. Reemplazo por inserción (o de tipo "coma"): según el tamaño relativo de la descendencia respecto de la población se distinguen dos casos:

 

    1. s £ n: se muestrean para ser eliminados s miembros de la población de criadores (normalmente los perores). Esos miembros serán sustituidos por los descendientes
    2. s > n: se muestrean n miembros de la población de descendientes y se constituye con ellos la nueva población. Nótese que con este modo cualquier individuo sólo puede sobrevivir a lo sumo una generación.

 

 

  1. Reemplazo por inclusión (o de tipo "más"): se juntan los s descendientes con los n progenitores en una sola población, y en ella se muestrean n miembros (normalmente los mejores).

 

Elitismo

El método más utilizado para mejorar la convergencia de los algoritmos genéticos es el elitismo. Consiste básicamente en realizar la etapa de selección en dos partes:

 

  1. Se muestrea una élite de r miembros de entre los mejores de la población inicial y se incorporan directamente a la población final, sin pasar por la población intermedia.
  2. La población auxiliar de criadores se muestrea de entre los n – r restantes miembros de la población inicial.

 

Comúnmente, el tamaño de la élite r es bastante pequeño (1 ó 2 para n=50), y el tipo de muestreo es bien directo o bien por sorteo, ambos en la variedad diversa.

 

El esquema básico de un algoritmo genérico elitista puede ser como sigue:

 

 

 

 

Bajo ciertas condiciones muy generales, la introducción del elitismo garantiza la convergencia teórica al óptimo global; en la práctica, mejora la velocidad de convergencia de los algoritmos genéticos cuando la función de evaluación es unidmodal (no hay subóptimos), sin embargo la velocidad de convergencia empeora con funciones fuertemente multimodales.

 

Con tamaños de población pequeños se consiguen efectos similares a los del elitismo introduciendo reinicializaciones periódicas en los algoritmos genéticos: cada vez que el algoritmo genético converge se salvan los mejores individuos, se reinicializan los demás y se vuelve a comenzar. La reinicialización tiene efectos beneficiosos sobre las prestaciones del método debido a que introduce diversidad, requisito especialmente crítico en los algoritmos genéticos con poblaciones pequeñas.

 

 

Fundamentos teóricos de los algoritmos genéticos

 

Como Liepins [Lie89], cualquier algoritmo que limite su procesamiento de información al grado de adaptación de uno o dos puntos, está virtualmente condenado al fracaso cuando trabaje en un espacio con suficiente cardinalidad. Afortunadamente, los algoritmos genéticos se pueden ver como algoritmos que orientan su búsqueda de forma global dentro del espacio de búsqueda.

 

El concepto global que se necesita para describir esta orientación global es el esquema. Un esquema es un patrón de similitud que describe un subconjunto de cadenas con similitudes en ciertas posiciones de las cadenas. Se define un símbolo "*" que indica que no está determinado el alelo. Si usamos in alfabeto binario, el conjunto de caracteres sobre los que está definido un esquema H = 1*11*10 representa a los individuos { (1 0 1 1 0 1 0 ),

(1 0 1 1 1 1 0), (1 1 1 1 0 1 0), (1 1 1 1 1 1 0) }.

 

Se puede ver que mediante el concepto de esquema, se están definiendo regiones del espacio total de soluciones. Así en una representación binaria de longitud L, cada individuo de la población pertenece a 2L esquemas o regiones del espacio de búsqueda.

 

Desde el punto de vista matemático, para describir la orientación global de la búsqueda de los algoritmos genéticos, se ha desarrollado la Teoría de los esquemas. Para ello se utilizan los conceptos de longitud y orden de un esquema.

 

Se considera una alfabeto de codificación binario V = {0, 1}. Se trabaja con una población de cadenas A(t), formada por cadenas de longitud L.

A(t) = { Ai }, Ai = a1 a2 . . . aL i Î {1, . . ., n}

 

 

La longitud de un esquema es la distancia entre la primera y la última posición especificadas del esquema. Se nota como d (H), y define cómo de concisa o compacta es la información contenida en el esquema. Ejemplo:

d (1 0 * * * 1 * *) = 5

 

La noción de longitud de un esquema es útil para calcular las probabilidades de supervivencia de los esquemas para los cruces.

 

El orden de un esquema es le número de posiciones (no comodines *) fijas en el patrón. Se nota como o(h) y define la especifidad del esquema. En ejemplo anterior la cadena es de orden 3. Esta noción es útil para calcular las probabilidades de supervivencia del esquema para las mutaciones.

 

Estas dos propiedades permiten considerar el efecto individual y combinado de las operaciones que se realizan en los algoritmos genéticos (cruce, mutación,...), consideradas sobre los esquemas contenidos dentro de la población de cadenas.

 

Sea H un esquema. Sea L la longitud de los individuos. f(H) representa el valor de adaptación estimado para el esquema H y se calcula como la media del grado de adecuación de los individuos de la población asociados al esquema. f es la media de la función de evaluación sobre la población (en una determinada iteración). m(H,t) representa el número de ejemplares de un esquema H en la población durante la iteración t. Con igual criterio, el número de representantes esperados del esquema H en el instante t+1 en la población P(t+1) se representa por m(H,t+1). Dicho de otra forma, m(H,t+1) es el número de individuos correspondientes al esquema H en la generación anterior, que sobreviven en las operaciones de cruce y mutación. Su valor viene dado por la siguiente expresión:

 

m(H, t+1) £ m(H, t) · f(H)/f’ · (1- pc · d (H)/(L-1) ) · (1-pm)o(H)

 

con f’ = S fi / n

 

Este teorema de los esquemas se comprende más fácilmente si se consideran cada uno de los términos aisladamente (se puede hacer el supuesto de que las tres operaciones – reproducción, cruce y mutación- son independientes):

 

 

 

 

 

Estos dos últimos operadores son necesarios porque la reproducción no introduce nuevos esquemas. Es por esto por lo que se usan el operador de cruce, que crea nuevos esquemas intercambiando información de forma aleatoria, y el operador de mutación que introduce variedad dentro de la población.

 

En resumen, la consecuencia que se extrae de la expresión al completo, es que esquemas cortos, de bajo orden, con adaptación por encima de la media incrementran su número de representantes de forma exponencial en las siguientes generaciones. Esta afirmación constituye el enunciado del Teorema de los Esquemas.

 

TEOREMA DE LOS ESQUEMAS

El esquema es el concepto central de la Hipótesis de construcción de bloques: en algún sentido se puede considerar que un esquema representa la dirección de la búsqueda genética (el hecho de que la selección determine copias de individuos en proporción directa a su fitness o grado de adaptación, inclina la siguiente en la dirección del esquema que se estima más favorable. Así, en las primeras generaciones, están representados una amplia variedad de esquemas y la búsqueda lo que hace en principio es una criba de los esquemas de menor orden. Generaciones posteriores muestran una mayor concurrencia en posiciones individuales de bits, y la búsqueda procede a través de esquemas de mayor orden. En definitiva, se ve qeu el algoritmo genético, explota las regiones de más alto rendimiento del espacio de soluciones, porque las sucesivas generaciones de reproducción y cruce, generan un número creciente de ellas. De hecho, el número de cadenas de un región o esquema dado, aumenta de forma proporcional a la estimación que se ha hecho del grado de adaptación de esa región.

 

Los fundamentos subyacentes en la búsqueda genética son: en una representación binaria de longitud L, cada individuo de la población pertenece a 2L esquemas, pertenece a todos los esquemas en los cuales aparece uno cualquiera de sus bits. Cada población de N individuos permite estimar el grado de adaptación de entre 2L y N·2L esquemas. Se sabe que no todos ellos son procesados ya que, dependiendo de la longitud y el orden, unos tendrán una mayor probabilidad de supervivencia a los operadores de cruce y de mutación. Se ha estimado que en una generación de N estructuras se procesan del orden de O(N3) esquemas. Esta es una importante propiedad a la que J. Holland dio el nombre de Paralelismo Implícito. El Paralelismo Implícito es el que hace que un algoritmo genético que manipule una población de unos cuantos millares de cadenas, realmente esté tomando muestras de un número de regiones o esquemas enormemente mayor. Tal paralelismo implícito (en el sentido de procesamiento paralelo), proporciona al algoritmo genérico su ventaja principal sobre otros métodos de resolución de problemas.