Make your own free website on Tripod.com
Indice

Origenes

Definición

Tipos
- Generacional
- Fijo
- Paralelo
- Modelo de islas
- Modelo Celular

Operadores Genéticos
- Selección
- Cruce
- Mutación

Ciclo General

 
Algoritmos Genéticos
INTRODUCCION Y CONCEPTOS BASICOS

LOS ORIGENES

La evolución se produce como resultado de dos procesos primarios: la selección natural y la reproducción sexual. La primera determina que miembros de la población sobrevivirán hasta reproducirse, la segunda garantiza la mezcla y combinación de sus genes entre la descendencia. En la fusión del óvulo y el espermatozoide, los cromosomas homologados se estiran y adosan uno al otro, y luego se entrecruzan en zonas intermedias, intercambiando así material genético. [Holland 92]

En la naturaleza, los individuos compiten entre sí por recursos tales como comida, agua refugio. Adicionalmente, los animales de la misma especie normalmente antagonizan para obtener una pareja. [Martín 95]

Esta es la teoría de la evolución, especies naturales que van evolucionando para adaptarse al medio que las rodea y aquellos individuos que tenga más éxito en tal adaptación tendrán mejor probabilidad de sobrevivir hasta la edad adulta y probablemente un número mayor de descendientes, por lo tanto, mayores probabilidades de que sus genes sean propagados a los largo de sucesivas generaciones. La combinación de características de los padres bien adaptados, en un descendiente, puede producir muchas veces un nuevo individuo mucho mejor adaptado que cualquiera de sus padres a las características de su medio ambiente.

Este proceso no debe verse en ningún momento como un proceso determinista, sino como un proceso con la fuerte componente estocástica. Es decir, si un individuo se adapta al entorno, lo más que se puede afirmar es que ese individuo tendrá mayor probabilidad de conservar sus genes en la siguiente generación que sus congéneres. Pero solo es una probabilidad, no es un hecho absolutamente seguro. Siempre existirá la posibilidad de que a pesar de estar muy dotado por alguna razón no consiga reproducirse. Pero en cuanto a la especie como un conjunto o población, si puede afirmarse que ira adaptándose al medio. [Martín 95]

La idea surgió en la universidad de Michigan, Estados Unidos donde el profesor J. H. Holland quien, consciente de la importancia de la selección natural introdujo la idea de los Algoritmos Genéticos en los años sesenta y al final de esta década desarrollo una técnica que permitió incorporarla en un programa de computadora. Su principal objetivo era lograr que las computadoras aprendieran por sí mismas. A la técnica inventada por Holland se le llamo inicialmente Planes Reproductivos pero se hizo popular bajo el nombre de Algoritmos Genéticos, A.G.
Obviamente desde aquellos años sesenta hasta ahora, muchas otras personas han contribuido de modo notable al desarrollo de estas ideas, abriéndose muchos nuevos frentes de trabajo y subdividiéndose la idea original en múltiples disciplinas. [Martín 95] Estas técnicas se usan principalmente en países desarrollados como Japón Estados Unidos y en Europa.

QUE SON LOS ALGORTIMOS GENETICOS

Los organismos vivos poseen destreza consumada en la resolución de problemas y se manifiesta una versatilidad capaz de avergonzar a los problemas más refinados. Una definición bastante completa de un Algoritmo Genético es la propuesta por Jhon Kosa [Coello 95]: Es un Algoritmo matemático altamente paralelo que transforma un conjunto de objetos matemáticos con respecto al tiempo usando operaciones modeladas de acuerdo al principio Darwiniano de reproducción y supervivencia del mas apto, y tras haberse presentado de forma natural una serie de operaciones genéticas de entre las que destaca la recombinación sexual. Cada uno de estos objetos matemáticos suele ser una cadena de caracteres (letras o números) de longitud fija que se ajusta al modelo de las cadenas de cromosomas, y se asocian con una cierta función matemática que refleja su aptitud. Los Algoritmos Genéticos utilizan una analogía directa del fenómeno de evolución en la naturaleza. Trabajan con una población de individuos, cada uno representado una posible solución a un problema dado. A cada individuo se le asigna una puntuación de adaptación, dependiendo de que tan buena fue la respuesta al problema. A los más adaptados se les da la oportunidad de reproducirse mediante cruzamientos con otros individuos de la población, produciendo descendientes con características de ambos padres. Los miembros menos adaptados poseen pocas probabilidades de que sean seleccionados para la reproducción, y desaparecen. El evaluar esta adaptación no es sencillo de hacer, pues el entorno esta modificándose constantemente por lo que nunca se llegara al superindividuo perfecto, sino que la naturaleza tendera a optimizar los individuos de cada especie en las circunstancias actuales. Existen varios tipos de Algoritmos Genéticos, cada uno basado en una metáfora distinta de la naturaleza.

CLASES DE ALGORITMOS GENÉTICOS

Algoritmos Genéticos Generacionales
Se asemejan a la forma de reproducción de los insectos, donde una generación pone huevos, se aleja geográficamente o muere y es substituida por una nueva. En este momento se realizan cruces en una piscina de individuos, los descendientes son puestos en otra, al final de la fase reproductiva se elimina la generación anterior y se pasa a utilizar la nueva. Este modelo también es conocido como Algoritmo Genético Canónico.

Algoritmos Genéticos de estado Fijo.
Utilizan el esquema generacional de los mamíferos y otros animales de vida larga, donde coexisten padres y sus descendientes, permitiendo que los hijos sean educados por sus progenitores, pero también que a la larga se genere competencia entre ellos.
En este modelo, no solo se deben seleccionar los dos individuos a ser padres, si no también cuales de la población anterior serán eliminados, para dar espacio a los descendientes.
La diferencia esencial entre el reemplazo generacional y el modelo de estado fijo es que las estadísticas de la población son recalculadas luego de cada cruce y los nuevos descendientes están disponibles inmediatamente para la reproducción. Esto permite al modelo utilizar las características de un individuo prometedor tan pronto como es creado.
Algunos autores dicen que este modelo tiende a evolucionar mucho más rápido que el modelo generacional, sin embargo investigaciones de Goldberg y deb [GOLDBERG 93], encontraron que las ventajas parecen estar relacionadas con la alta tasa de crecimiento inicial, ellos dicen que los mismos efectos pueden ser obtenidos en rangos de adaptación exponencial o selección por competencia. No encontraron evidencia que este modelo sea mejor que el Generacional.

Algoritmos Genéticos Paralelos.
Parte de la metáfora biológica que motivo a utilizar la búsqueda genética consiste en que es inherentemente paralela, donde al evolucionar se recorren simultáneamente muchas soluciones, cada una representada por un individuo de la población. Sin embargo, es muy común en la naturaleza que no solo sea una población evolucionando, si no varias poblaciones, normalmente aisladas geográficamente, que originan respuestas diferentes a la presión evolutiva. Esto origina dos modelos que toman es cuenta esta variación, y utilizan no una población como los anteriores si no múltiples concurrentemente.

Modelos de Islas.
Si se tiene una población de individuos, esta se divide en subpoblaciones que evolucionan independientemente como un Algoritmo Genético normal. Ocasionalmente, se producen migraciones entre ellas, permitiéndoles intercambiar material genético.
Con la utilización de la migración, este modelo puede explotar las diferencias en las subpoblaciones; esta variación representa una fuente de diversidad genética. Sin embargo, si un número de individuos emigran en cada generación, ocurre una mezcla global y se eliminan las diferencias locales, y si la migración es infrecuente, es probable que se produzca convergencia prematura en las subpoblaciones.

Modelo Celular
Coloca cada individuo en una matriz, donde cada uno sólo podrá buscar reproducirse con los individuos que tenga a su alrededor (mas cerca de casa) escogiendo al azar o al mejor adaptado. El descendiente pasara a ocupar una posición cercana.
No hay islas en este modelo, pero hay efectos potenciales similares. Asumiendo que el cruce esta restringido a individuos adyacentes, dos individuos separados por 20 espacios están tan aislados como si estuvieran en dos islas, este tipo de separación es conocido como aislamiento por distancia.
Luego de la primera evaluación, los individuos están todavia distribuidos al azar sobre la matriz. Posteriormente, empiezan a emerger zonas como cromosomas y adaptaciones semejantes. La reproducción y selección local crea tendencias evolutivas aisladas, luego de varias generaciones, la competencia local resultara en grupos mas grandes de individuos semejantes.


ELEMENTOS DE UN ALGORITMO GENETICO

Como los Algoritmos Genéticos se encuentra basados en los procesos de evolución de los seres vivos, casi todos sus conceptos se basan en conceptos de biología y genética que son fáciles de comprender.

Individuo
Un individuo es un ser que caracteriza su propia especie. El individuo es un cromosoma y es el codigo de información sobre el cual opera el algoritmo. Cada solución parcial del problema a optimizar está codificada en forma de cadena o String en un alfabeto determinado, que puede ser binario. Una cadena representa a un cormosoma, por lo tanto tambien a un individuo y cada posición de la cadena representa a un gen. Esto significa que el algoritmo trabaja con una codificación de los parametros y no con los parametros en si mismos.
El genotipo, es el conjunto de genes ordenados y representa las caracteristicas del individuo. Cada individuo tinen una medida de su adecuación como solución al problema.

Población
A un conjunto de individuos (Cromosomas) se le denomina población. El método de A.G´s consiste en ir obteniendo de forma sucesiva distintas poblaciones. Por otra parte un Algoritmo Genético trabaja con un conjunto de puntos representativos de diferentes zonas del espacio de búsqueda y no con un solo punto (como lo hace Hillclimbing).

Función Fitness.
La única restricción para usar un algoritmo genético es que exista una función llamada fitness, que le informe de cuan bueno es un individuo dado en la solución de un problema. Esta función fitness o de evaluación es el principal enlace entre el Algoritmo Genético a un problema real, es la efectividad y eficiencia de la función fitness que se tome, por lo tanto debe procurarse que la función fitness sea similar, si no igual a la función objetivo que se quiere optimizar. Esta medida se utiliza como parámetro de los operadores y guía la obtención de nuevas poblaciones.

OPERADORES GENETICOS.

Son los diferentes métodos u operaciones que se pueden ejercer sobre una población y que nos permite obtener poblaciones nuevas. Una vez que se ha evaluado cada individuo sobre una función fitness, se aplican los operadores genéticos. En Algoritmos Genéticos se destacan los siguientes operadores.

Operador de Selección.
El paso siguiente a la evaluación es escoger los miembros de la población que serán utilizados para la reproducción. Su meta es dar mas oportunidades de selección a los miembros más aptos de la población. Así funciona: se calcula el cociente entre el valor fitness de un individuo y la suma total de los valores fitness de todos los individuos de la población. Este resultado mide la probabilidad de selección Ps (i) de cada individuo.

Ecuación
Ecuación No. 1 Probabilidad de selección.

Empezando desde la población P (t) de N individuos se obtiene una nueva población P(t+1) aplicando N veces el operador de selección. Los individuos se seleccionan de una especie de rueda de ruleta (como se muestra en la figura 1) donde cada uno tiene asignado un trozo en proporción a su probabilidad selección Ps.

Ecuación
Figura No.1 Operador de Selección

Este mecanismo puede causar problemas de convergencia prematura, causada por la aparición de un individuo que es mucho mejor que los otros de la población aunque esta lejos de optimo; las copias de este individuo pueden dominar rápidamente a la población, sin poder escapar de este mínimo local.


Operador de Cruce

Consiste en unir en alguna forma los cromosomas de los padres que han sido previamente selecciónados de la generación anterior para formar dos descendientes. Existen diversas variaciones, dependiendo del número de puntos de división a emplear y la forma de ver el cromosoma. El operador cruce se aplica en dos pasos: en el primero los individuos se aparean (se seleccionan de dos a dos) aleatoriamente con una determinada probabilidad, llamada probabilidad de cruce Pc; en el segundo paso a cada par de individuos seleccionados anteriormente se le aplica un intercambio en su contenido desde una posición aleatoria K hasta el final, con K Î [1, m-1], donde m es la longitud de individuo. K es el denominado punto de cruce y determina la subdivisión de cada padre en dos partes que se intercambian para formar dos nuevos hijos, según podemos ver en la figura 2 Esto se conoce como cruce ordinario o cruce de un punto. El objetivo del operador de cruce es recombinar subcadenas de forma eficiente; esta gestión recibe el nombre de construcción de bloques.

Ecuación
Figura No. 2 Operador de Cruce

Mutación.

El operador de mutación consiste en la alteración aleatoria de cada uno de los genes del individuo con una probabilidad de mutación PM, como se puede ver en la figura 3.
El objetivo de la mutación es producir diversidad en la población. Si al generar aleatoriamente la población inicial o después de varias generaciones, en la misma posición de todos los cromosomas sólo aparece un único elemento del alfabeto utilizado, esto supondrá que con los operadores de reproducción y cruce, nunca cambiara dicho elemento, por lo que puede ocurrir que jamas se alcance la solución más optima a nuestro problema. La probabilidad de aparición del operador de mutación no debe ser grande para no perjudicar la correcta construcción de bloques. El operador de mutación origina variaciones elementales en la población y garantiza que cualquier punto del espacio de búsqueda pueda ser alcanzado.

Ecuación
Figura No. 3 Operador de Mutación

CICLO GENERAL DE UN ALGORITMO GENETICO ESTANDAR

El AG estándar se puede expresar en pseudocodigo con el siguiente ciclo. [Coello 95]:
1. Generar aleatoriamente la población inicial de individuos P(0). Generación = 0:
2. Mientras ( numero _ generaciones <= máximo _ números _ generaciones)

  Hacer  
        {
		Evaluación;
		Selección;
		Reproducción;
		Generación ++;
	}

3.Mostrar resultados;
Fin de la generación

Estas características de los AG, a su vez, describen las diferencias entre ellos, y otros métodos normales de optimización.
1. Un Algoritmo Genético trabaja con codificación de los parámetros que busca optimizar y no con los parámetros en sí mismo.
2. Un Algoritmo Genético trabaja con un conjunto de puntos representativos de diferentes zonas del espacio y no con un solo punto. Por el contrario necesita considerables recursos de computación.
3. La aplicación de AG no depende de ninguna propiedad de la función a optimizar (derivable, continua, ni siquiera conocida), o de que el conjunto de posibles soluciones sea finito o no lo sea.
4. Un AG utiliza reglas de transición probabilisticas, no deterministas, lo cual hace que dos aplicaciones consecutivas de un AG a un mismo problema puedan producir dos soluciones distintas.
EL ejemplo siguiente nos da una pequeña ilustración de un Pseudocódigo de Algoritmo Genético.

BEGIN /* Algoritmo Genético  */
   Generar una población inicial.
   Computar la función de evaluación de cada individuo.
   WHILE NOT  Terminado  DO
   BEGIN /* Producir nueva Generación */
	FOR Tamaño Población /2 DO
	BEGIN /* Ciclo Reproductivo */
	   Seleccionar dos individuos de la anterior generación
	   El cruce (probabilidad de selección proporcional a la 
	   Función de evaluación de individuo).
 	   Cruzar con cierta probabilidad los dos individuos
	   obtenida dos descendientes
	   Mutar los dos descendientes con cierta probabilidad.
	   Computar la función de evaluación de los dos 
	   descendientes Mutados.
	   Insertar los dos descendientes mutados en la nueva 
	   generación.
	END
	
	IF La población ha convergido THEN 
	Terminado =TRUE
	
   END
END

Arriba

Comentarios
jes_alf_lopez@yahoo.com


[Redes Neuronales] [Computación Evolutiva] [Lógica Difusa] [Principal]


Ultima modificación Agosto/03/2000