Algoritmos Genéticos

Algoritmos Evolutivos.

Los algoritmos evolutivos son una técnica de resolución de problemas de búsqueda y optimización inspirada en la teoría de la evolución de las especies y de la selección natural[Araujo, 09]. Estos algoritmos reúnen características de búsqueda aleatoria con características de búsqueda dirigida que provienen del mecanismo de selección de los individuos mas adaptados. La unión de ambas características les permite abordar problemas de una manera muy particular, ya que tienen la capacidad para acceder a cualquier regióndel espacio de búsqueda, capacidad de la que carecen otros métodos de búsqueda exhaustiva, a la vez que exploran el espacio de soluciones de una manera mucho mas eficiente que los métodos puramente aleatorios. Indudablemente un algoritmo diseñado de forma especifica para la resolución de un problema concreto será más eficiente que un algoritmo evolutivo, que es una técnica general de resolución. Pero existen muchas situaciones en las que no es posible contar con tales algoritmos, como por ejemplo la complejidad computacional o el tamaño de los problemas que los hace inaccesibles para su solución.

Algoritmos Genéticos

Uno de los tipos de algoritmos evolutivos mas populares son los algoritmos genéticos propuestos por Holland [Holland,75]. Se caracterizar por representar las soluciones al problema que abordan en forma de cadena de bits. Entre las diversas razones que hacen que este tipo de algoritmo suela ser uno de los mas estudiados con mas detalle son su eficiencia y sencillez de implementación. Podemos estudiar a detalle la forma de implementar un algoritmo genético para resolver un problema especifico a partir de su esquema general que a continuación mostraremos.

La ejecución de un algoritmo genético requiere de una serie de parámetros de funcionamiento como por ejemplo el tamaño de la población con la que va a trabajar, que definen su comportamiento en promedio. Una vez que el algoritmo dispone de los valores para estos parámetros comienza generando una población de individuos donde cada uno de ellos es una posible solución del problema tratado.

Posteriormente esa población entra en un ciclo de evolución donde cada ciclo de evolución al que llamaremos generación constara de los siguientes operadores básicos:

• Selección que modifica la composición de la población, eliminando a ciertos individuos y reforzando la presencia de otros

• Reproducción que introduce nuevos individuos y una nueva evaluación que actualiza los datos de la evolución, tales como la adaptación media o la posición del mejor individuo de la población

Representación de los individuos

En un AG los individuos son cadenas binarias que denotaremos por b que representan a puntos x del espacio de búsqueda del problema. Tomando la nomenclatura de la biología a b se le denomina genotipo del individuo y a x se le denomina fenotipo. La nomenclatura biológica a veces se adopta también para otros datos del individuo .

Así se usa gen para referirse a la codificación de una determinada característica del individuo. En los AGs se suele identificar un gen con cada posición de la cadena binaria,aunque esto no tiene por que ser siempre así. Se usa alelo para los distintos valores que puede tomar un gen y locus para referirse a una determinada posición de la cadena binaria.

La sencillez de la representación binaria que utilizan los AGs les aporta características muy importantes de eficiencia. Pero su contrapartida es que requieren cierta lógica para poder codificar-decodificar a cada individuo y su complejidad va a variar dependiendo de l problema a tratar, este paso es necesario para poder evaluar la aptitud de cada individuo.

Es importante que cada posición de la cadena tenga un significado para el problema ya que de esta forma se favorece que los genes den alta calidad a un individuo sigan dando características de calidad en un nuevo individuo obtenido a partir de la la aplicación de un operador genético.

Generación de la población inicial

Los individuos de la población inicial de un AGs suelen ser cadenas de 1's y 0's generadas completamente en forma aleatoria, es decir se va generando un gen con cada función que devuelve un 0 o un 1 con igual probabilidad. En algunos problemas en los que se disponga de información adicional que nos permita saber de antemano que determinadas cadenas tienen mas probabilidades de de llegar a ser solución, podemos favorecer a su generación al crear la población inicial. Sin embargo es imprescindible para el buen funcionamiento del AG dotar a la población de suficiente variedad para poder explorar todas las zonas del espacio de búsqueda.

Grado de adaptación de los individuos

La evolución de la población depende de la calidad relativa de los individuos que compiten por aumentar su presencia en la población y por participar en las operaciones de reproducción. En un problema de búsqueda u optimización dicha calidad se mide por la adecuación o adaptación de cada individuo a se solución del problema. Es frecuente que los problemas se presenten como una función matemática explicita. En dichos casos la función adaptación coincide con la función a optimizar Sin embargo a veces se realizan algunas transformaciones a la función a optimizar o función de evaluación g(x) para transformarla en una función de adaptación adecuada f(x).

Condiciones de Paro

Es necesario especificar las condiciones en las que el algoritmo deja de evolucionar y se presenta la mejor solución encontrada. La condición de terminación mas sencilla es alcanzar determinado numero de generaciones de evolución. Otras condiciones que a veces se utilizan en forma combinada, son alcanzar una determinada calidad o detectar que mayor parte de la población a convergido a una forma similar careciendo de la suficiente diversidad para que tenga sentido continuar con la evolución.

La Selección: Procesos de Muestreo

La población del algoritmo genético se somete a un proceso de selección que debe tender a favorecer la calidad de copias de los individuos mas adaptados. Este proceso se puede realizar de formas muy diferentes en este caso mostraremos solamente 2 de ellas incluyendo la que se utilizara en la implementación informática de LAYAGEN-G

Selección por Ruleta

La probabilidad de selección pi de un individuo i con este método es proporcional a su adaptación relativa

siendo f la adaptación media de la población.

Necesitamos generar un numero aleatorio de acuerdo a la distribución de probabilidad dada por los pi. Si contamos con un generador de números aleatorios que genera números de forma uniformemente distribuida a lo largo de un intervalo como [0,1] podemos seguir el siguiente procedimiento [Perez 96]

Selección por torneo

En la selección por torneo se elige aleatoriamente una pequeña muestra de la población y de ella se selecciona el individuo de mejor valor de adaptación. Normalmente se utiliza un tamaño pequeño para la muestra, de 2 o 3 individuos. El proceso se repite hasta tener el numero de individuos que se desee seleccionar. Esta puede realizarse en forma probabilística o determinista

• En la selección por torneo determinista se selecciona aleatoriamente un numero p de individuos. Habitualmente p toma el valor de 2. Después de entre los individuos seleccionados se elije el mejor, es decir es decir el de mayor valor de adaptación.

• El caso probabilístico es similar, excepto porque una vez seleccionados los p individuos en lugar de escoger siempre el mejor, la selección se realiza con una cierta probabilidad. Si un numero, que se genera aleatoriamente entre 0 y 1, es mayor que un cierto umbral especificado como parámetro del algoritmo, entonces se elige al mejor, en otro caso al peor.

Como se había mencionado anteriormente uno de estos métodos sera implementado en el algoritmo LAYAGEN-G[Diego-Mas 06], El autor nos propone usar el método de ruleta sencillo aunque también da alternativas de mejoramiento del procedimiento pero en nuestro caso solo implementaremos la ruleta sencilla.

Operadores genéticos: Reproducción y Mutación

En cada nueva generación se crean algunos individuos que no estaban presentes en la población anterior. De esta forma el algoritmo genético va accediendo a nuevas regiones del espacio de búsqueda. Los nuevos individuos se crean aplicando ciertos operadores genéticos a individuos de la población anterior. Los operadores suelen estar presentes en todo el algoritmo genético son los operadores de cruce y mutación. El operador cruce combina las propiedades de 2 individuos de la población anterior para crear nuevos individuos. El operador de mutación crea un nuevo individuo realizando algún tipo de alteración usualmente pequeña en algún individuo de la población anterior veamos a continuación la forma mas simple de implementarlos que sera un tanto similar a la que usaremos.

Cruce Monopunto

La forma mas simple del operador de cruce en los algoritmos genéticos es el cruce monopunto. Este consiste en seleccionar al azar una única posición en la cadena de ambos padres e intercambiar las partes de los padres divididas por dicha posición, como muestra la siguiente figura.

Este operador produce 2 hijos que combinan propiedades de ambos padres lo que puede llevar a una mejora de adaptación de los hijos con respecto a los padres.

La forma mas sencilla de mutación que se puede aplicar a un individuo de un algoritmo genético consiste en cambiar el valor de una de las posiciones de la cadena: si es 0 pasa a 1 y si es 1 pasa a 0 como en la siguiente figura.

En muchos casos la mutación produce individuos con peor adaptación que los originales, ya que la mutación puede romper las posibles correlaciones entre genes que se hayan formado con la evolución de la población. Sin embargo contribuyen a mantener la diversidad de la población que es fundamental para el buen funcionamiento de un algoritmo genético..