- Objetivo
general - Panorama histórico de la
computación evolutiva - Conceptos básicos. Los
orígenes - Programación
evolutiva - Estrategias evolutivas
(EE) - Algoritmos
genéticos - Clases de algoritmos
genéticos - Elementos de un algoritmo
genético - Operadores
genéticos. - Ciclo general de un algoritmo
genético estándar - Software
- Conclusión
- Bibliografía
En este tema se verá la forma en que los
científicos han tomado a la evolución a través de la selección
natural determinando que miembros de la población sobrevivirán hasta
reproducirse y la reproducción sexual garantizando la mezcla
y combinación de sus genes entre la
descendencia.
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.
Veremos conceptos básicos de las técnicas
más importantes de computación evolutiva. Luego comenzaremos a
hablar de la computación evolutiva en particular.
Iniciaremos con un recorrido histórico en el que se
resumirán los logros más importantes en torno a la
simulación de los procesos
evolutivos como una herramienta para el aprendizaje y
la optimización.
Posteriormente se analizarán de manera general
los 3 paradigmas
principales que se utilizan hoy en día en la
computación evolutiva: las estrategias
evolutivas, la programación evolutiva y los algoritmos
genéticos. En cada caso se abordará su
inspiración biológica, su motivación, su funcionamiento y algunas de
sus aplicaciones. Finalmente se estudiará el
funcionamiento, fundamentos teóricos,
implementación de los algoritmos genéticos, que es
actualmente el paradigma
evolutivo más utilizado por los investigadores que
trabajan en esta disciplina.
Comprender el concepto de la
computación evolutiva, su importancia en el mundo actual
así como su historia, sus conceptos
básicos y sus diferentes aplicaciones.
Computación Evolutiva
La Computación Evolutiva interpreta la naturaleza
como una inmensa máquina de resolver problemas y
trata de encontrar el origen de dicha potencialidad para
utilizarla en nuestros programas.
Definición :Con el término de
Computación Evolutiva se engloba al conjunto de
técnicas que basándose en la simulación de
los procesos naturales y la genética
se utilizan para resolver problemas complejos de búsqueda
y aprendizaje.
Panorama
histórico de la computación
evolutiva
Cannon 1932, visualizó la evolución
natural como un proceso de
aprendizaje. Alan Turing reconoció, en 1950, que
debe haber una conexión obvia entre el aprendizaje de
máquina y la evolución, y señaló que
se podrían desarrollar programas para jugar ajedrez usando
esta técnica.
Campbell conjeturó en 1960 que en todos
los procesos que llevan a la expansión del conocimiento,
se involucra un proceso ciego de variación y supervivencia
selectiva.
Los primeros intentos de aplicar de manera formal la
teoría
de la evolución, apareció en las áreas de
control de
procesos estadísticos, aprendizaje de máquina y
optimización de funciones. Tal
vez el primer intento serio de este tipo se dio en el trabajo que
realizaron Box y sus colegas en 1957, en el desarrollo de
una técnica que denominaron operación evolutiva, la
cual se aplicó a una planta de manufactura
para manejarla.
Friedberg intentó, en 1958, hacer que un
programa en
lenguaje
máquina se mejorara a sí mismo, seleccionando
instrucciones que se asociaran más frecuentemente con un
resultado exitoso.
Barricelli ofreció, en 1954, una de las
primeras simulaciones que usaba principios
evolutivos, utilizando los mismos procedimientos
generales que se usan hoy en día en la disciplina conocida
como vida artificial.
Fogel el que introdujo la primera técnica
evolutiva que realmente funcionó más o menos dentro
de los lineamientos actuales de la computación evolutiva.
Su programación evolutiva consistía en hacer
evolucionar autómatas de estados finitos por medio de
mutaciones artificial.
Rechenberg y Schwefel 1965. desarrollaron una
técnica, llamada estrategia
evolutiva, se utilizó inicialmente para resolver problemas
ingenieriles que desafiaban a los métodos de
optimización tradicionales.
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.
En la naturaleza todos los seres vivos se enfrentan a
problemas que deben resolver con éxito, como conseguir
más luz del sol, o
cazar una mosca. La Computación Evolutiva interpreta la
naturaleza como una inmensa máquina de resolver problemas
y trata de encontrar el origen de dicha potencialidad para
utilizarla en nuestros programas.
Los Algoritmos Genéticos son una de las
más conocidas y originales técnicas de
resolución de problemas dentro de lo que se ha definido
como "Computación Evolutiva" (o "Algoritmos Evolutivos"),
término que agrupa a los Algoritmos Genéticos,
las Estrategias Evolutivas y la Programación
Evolutiva. En realidad todas estas técnicas son muy
parecidas y comparten muchos aspectos.
Un Algoritmo
Evolutivo es una técnica de resolución de
problemas inspirada en la evolución de los seres
vivos.
En un Algoritmo Evolutivo se define una estructura de
datos que admita todas las posibles soluciones a
un problema.
Cada uno de los posibles conjuntos de
datos
admitidos por esa estructura
será una solución al problema. Unas soluciones
serán mejores, otras peores.
Solucionar el problema consistirá en encontrar la
solución óptima, y por tanto, los Algoritmos
Evolutivos son en realidad un método de
búsqueda.
Pero un método de búsqueda muy especial,
en el que las soluciones al problema son capaces de reproducirse
entre sí, combinando sus características y
generando nuevas soluciones.
En cada ciclo se seleccionan las soluciones que
más se acercan al objetivo buscado, eliminando el resto de
soluciones. Las soluciones seleccionadas se reproducirán
entre sí, permitiendo de vez en cuando alguna
mutación o modificación al azar durante la
reproducción.
Algoritmo Evolutivo
- Es una técnica de resolución de
problemas inspirada en la evolución de los seres
vivos. - Programas computacionales cuyo fin es imitar el
proceso de "selección natural" que según la
teoría de Darwin rige el
curso de la evolución
Esquema de la computación
evolutiva
- Inteligencia artificial.
- Enfoque simbólico o
`top-down'. - Enfoque subsimbólico o
`botton-up'. - Redes neuronales
artificiales. - Computación evolutiva o algoritmos
evolutivos. - Solidificación o recocido
simulado (simulated annealing). - Algoritmos
genéticos. - Estrategias evolutivas.
- Clasificadores
genéticos. - Programación
genética.
- Solidificación o recocido
- Redes neuronales
- Enfoque simbólico o
Fases de un Algoritmo Evolutivo
- Opciones Generales.
- Número de entidades.
- Número de elementos (genes, reglas) por
cada agente.
- Método de Evaluación: Asignar un
peso. - Desordenar las entidades antes de
evaluarlas. - Diferentes formas de modificación de los
pesos después de la evaluación. Por
ejemplo, el peso de una entidad se puede calcular
independientemente de las demás entidades, o se
puede modificar posteriormente este valor,
disminuyendo el peso si existe otra entidad muy parecida,
analizando para ello un cierto subconjunto de la
población vecina.
- Desordenar las entidades antes de
- Método de Selección:
¿Quién muere? ¿Quién se
reproduce? - Con o sin reemplazamiento.
- Método de la ruleta.
- Método de los torneos.
- Seleccionar el n% mejor y el m%
peor.
- Método de Reproducción: Generar
y mutar nuevos hijos. - Los padres pueden tomarse por parejas o en
grupos
más numerosos, elegidos al azar o en orden de
pesos. - En el caso de detectar que los progenitores son
muy parecidos, se puede realizar una acción
especial, como incrementar la probabilidad de
mutación. - Las entidades pueden comunicar a otras su
conocimiento, ya sea a toda o a una parte de la
población, directamente o a través de una
pizarra, (una especie de tablón de
anuncios). - Método de recombinación de genes:
se puede tomar genes de uno u otro progenitor al azar, en
un cierto orden, con uno, dos o más puntos de
corte, etc. - Tasa de mutación variable.
- Fijar una tasa de mutación diferente
para cada individuo o incluso para cada gen. - Hacer que sea más probable que se
produzca una mutación en un gen si en su vecino ya
se ha producido. - Sustituir por mutaciones, genes sin utilidad, como reglas incorrectas o
repetidas. - Tipos de mutaciones
- Los padres pueden tomarse por parejas o en
Algoritmo
El algoritmo básico de la programación
evolutiva es el siguiente:
- Generar aleatoriamente una población
inicial. - Se aplica mutación.
- Se calcula la aptitud de cada hijo y se usa un
proceso de selección mediante torneo (normalmente
estocástico) para determinar cuales serán las
soluciones que se retendrán.
El termino computación evolutiva o
algoritmos evolutivos, realmente engloba
una serie de técnicas inspiradas
biológicamente. En términos generales, para simular
el proceso evolutivo en una computadora se requiere:
- Codificar las estructuras
que se replicaran. - Operaciones que afecten a los
"individuos". - Una función
de aptitud. - Un mecanismo de selección.
Aunque hoy en día es cada vez mas difícil
distinguir las diferencias entre los distintos tipos de
algoritmos evolutivos existentes, suele hablarse de tres
paradigmas principales:
_Estrategias Evolutivas
_Algoritmos Genéticos.
Programas Evolutivos (PE)
Son una estrategia de optimización
estocástica similar a los Ags, pero hacen un
énfasis específico en los operadores
genéticos tal y como se observan en la naturaleza y en la
estructura de datos que utilizan adaptada al problema. Por esto,
a diferencia de los AGs, los PEs no son restrictivos en cuanto a
la representación del problema. Mientras en los AGs se
hace necesario una codificación de las soluciones del
problema; en los PEs, tal representación se hace de forma
directa.
Historia
Los programas evolutivos fueron presentados en 1994 por
Michalewicz, cuando propuso incorporar conocimiento
específico del problema a resolver en las estructuras de
datos. Así, los PEs son métodos que incorporan
directamente conocimiento específico a los AGs, puesto que
permiten la utilización de estructuras de datos naturales.
Esto permite, a su vez, la utilización de operadores
genéticos sensibles al contexto, con el fin de mejorar la
eficiencia del
algoritmo de búsqueda sin perder gran parte de la propiedad de
generalización. Además, de perder un poco de
generalización, con la incorporación de
conocimiento específico, también se pierde el
paralelismo implícito (basado en alfabetos de
símbolos mínimos). Sin embargo, esta pérdida
se compensa con el procesamiento de información mas útil.
Veamos el ejemplo del funcionamiento de la
programación evolutiva que se indica en la figura 3.2. La
tabla de transiciones de este autómata es la
siguiente:
En este autómata pueden ahora aplicarse
cinco diferentes tipos de mutaciones:
cambiar un símbolo de salida, cambiar una
transición, agregar un estado, borrar
un estado y cambiar el estado
inicial. El objetivo es hacer que el autómata reconozca un
cierto conjunto de entradas (o sea, una cierta expresión
regular) sin equivocarse ni una sola vez.
Aplicaciones
Predicción
Generalización
Juegos
Control automático
Problema del viajero
Planeación de rutas
Diseño y entrenamiento de
redes
neuronales
Reconocimiento de patrones.
Esta técnica esta básicamente enfocada
hacia la optimización paramétrica. En esencia son
métodos estocásticos con paso adaptativo, que
permiten resolver problemas de optimización
paramétrica. A este método se le han agregado
procedimientos propios de la computación evolutiva, que lo
han convertido en un paradigma más de dicha metodología. Con tal mezcla, las EEs pueden
definirse como algoritmos evolutivos enfocados hacia la
optimización paramétrica, teniendo como
características principales que utilizan una
representación a través de vectores reales,
una selección determinística y operadores
genéticos específicos de cruce y mutación.
Además, su objetivo fundamental consiste en encontrar el
valor real de un vector de N dimensiones.
Las EEs pueden dividirse en dos tipos: Estrategias
Evolutivas Simples y Estrategias Evolutivas
Múltiples.
- EEs Simples
Son consideradas como procedimientos estocásticos
de optimización paramétrica con paso adaptativo,
esta característica las hace similares al temple simulado.
En este caso, se hace evolucionar un solo individuo usando
únicamente a la mutación como operador
genético. Son relativamente sencillas, y se denominan
también EEs de dos miembros. Debido a que evoluciona un
solo individuo a la vez, no son consideradas estrictamente como
métodos evolutivos. A pesar de ser muy sencillas, son de
gran utilidad práctica y han sido utilizadas, con algunas
mejoras, para resolver problemas reales en diversas
áreas.
- EEs Múltiples:
Surgen como respuesta a las debilidades de las EEs
simples, las cuales tienden a converger hacia subóptimos.
En las EEs múltiples existen múltiples individuos
(población), y se producen en cada generación
varios nuevos individuos, usando tanto mutación como cruce
(también puede usarse cualquier otro operador). Se usa
normalmente e cruce promedio, el cual genera un único
descendiente de dos padres, promediando los valores de
estos. En cuanto a los criterios de reemplazo, siempre se usa un
esquema determinístico pudiéndose utilizar una
estrategia de inserción o de inclusión.
Algunas aplicaciones de las estrategias evolutivas
son
Problemas de ruteo y redes
Bioquímica
Óptica
Diseño en ingeniería
Magnetismo
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 súper individuo 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.
Los algoritmos genéticos parten de una
población inicial donde cada individuo se representa con
un código
genético (típicamente una secuencia de bits) en la
que se encuentra codificada su información. Sobre esta
población se realiza una serie de operaciones, en primer
lugar se seleccionan parejas de soluciones para que se
reproduzcan (a este proceso se le llama cruce), siendo los hijos
una mezcla del código genético de los padres. A
continuación se producen una serie de mutaciones que
alteran los genes de los recién nacidos y por
último de entre toda la población se eligen
aquellos que van a sobrevivir desechándose el resto (la
población en un algoritmo genético típico
permanece constante en todas las iteraciones). Tanto a la hora de
la reproducción, como en el momento de elegir las
soluciones supervivientes en cada iteración, se favorece a
aquellos individuos que según la función de
evaluación sean más fuertes. El algoritmo
terminará cuando se llegue a un número de
iteraciones seleccionado previamente, o cuando se observe tras
una serie de iteraciones no se ha detectado ninguna mejora en la
población. El pseudo código sería el
siguiente:
Algoritmo
Crear población inicial
Evaluar la población
Mientras No(condición salida)
Seleccionar a los padres
Combinar los genes de los padres para crear a los
descendientes
Mutar a los descendientes
Evaluar la nueva población
Elegir los individuos que sobrevivirán
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 si4 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.
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.
Para ver la fórmula seleccione la
opción "Descargar" del menú superior
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 selecc
Para ver el gráfico seleccione la
opción "Descargar" del menú superiorión
Ps.
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.
Para ver el gráfico seleccione la
opción "Descargar" del menú superior
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.
Para ver el gráfico seleccione la
opción "Descargar" del menú superior
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
Algunas aplicaciones de los AGs son las
siguientes
- Optimización (estructural, de topologías, numérica,
combinatoria, etc.) - Aprendizaje de maquina (sistemas
clasificadores) - Bases de datos (optimización de
consultas) - Reconocimiento de patrones (por ejemplo, imágenes)
- Generación de gramáticas (regulares,
libres de contexto, etc.) - Planeación de movimientos de
robots - Predicción.
Estrategias Evolutivas vs Programación
Evolutiva
La Programación Evolutiva usa normalmente
selección estocástica, mientras que
las estrategias evolutivas usan selección
deterministica.
Ambas técnicas operan a nivel fenotipico (es
decir, no requieren codificación
de las variables del
problema).
La programación evolutiva es una
abstracción de la evolución al nivel de
las
especies, por lo que no se requiere el uso de un
operador de recombinación (diferentes especies no se
pueden cruzar entre si). En contraste, las estrategias evolutivas
son una abstracción de la evolución al nivel de un
individuo, por lo que la recombinación es
posible.
Tendencias futuras
Las limitaciones de la representación binaria en
algunas aplicaciones ha hecho de esta una ruta interesante de
investigación, sobre todo en el contexto de
problemas de manufactura y definición de rutas, en los
cuales la respuesta se expresa en forma de permutaciones.
Idealmente, debiera existir un tipo de representación
suficientemente flexible como para permitir su utilización
en una amplia gama de problemas de forma sencilla y
natural.
Filho [77] desarrollo un sistema llamado
GAME (Genetic Algorithms Manipu-lation Environment), que
constituye un paso importante en esta dirección. GAME usa una codificación
de árbol en la que las hojas pueden ser enteros,
caracteres,números reales o cadenas binarias.
Gibson [101] también propuso una
codificación híbrida similar a la de
Filho.
Su propuesta se basa en el uso de componentes de
diferentes tipos en el contexto de modelado de procesos
industriales.
Existe amplia evidencia en la literatura especializada
[159, 155, 190, 100, 115] de que el usar una
representación adecuada puede simplificar tremendamente el
proceso de búsqueda de un algoritmo genético, pero
a pesar de eso, muchos investigadores suelen pasar por alto este
importante hecho. Por lo tanto, es vital no únicamente
reconocer que se requieren codificaciones mas poderosas,
sino
En general, podemos clasificar el software para
computación evolutiva en 3 grandes grupos:
_Orientado a las aplicaciones: Son "cajas negras"
diseñadas para ocultar
detalles de los AGs y ayudar al usuario a desarrollar
aplicaciones para dominios
específicos tales como las finanzas, la
programación de horarios, etc.
_Orientado a los algoritmos: Se basan en modelos
de AGs específicos y
pueden subdividirse en 2 grupos:
1. Sistemas Específicos: Contienen un solo
algoritmo.
2. Bibliotecas:
Contienen una gama de algoritmos y operadores
genéticos
que pueden estar disponibles solo de manera
precompilada.
Cajas de herramientas
(tool kits): Sistemas de programación que
proporcionan
muchas utilerías, algoritmos y operadores
genéticos que pueden
usarse para cualquier tipo de aplicación y que
normalmente se proporcionan
en forma de código fuente (al menos de manera
parcial).
A su vez, las cajas de herramientas se pueden subdividir
en 2 grupos:
1.Sistemas Educativos:
2. Sistemas de propósito general:
- Los algoritmos genéticos son un proceso de
prueba y error. - Una de las partes mas importantes del algoritmo es la
función de "adaptación". Sin ella la
mutación se pueden "contaminar", y no hay
evolución. - Solucionar el problema consistirá en encontrar
la solución óptima, y por tanto, los Algoritmos
Evolutivos son en realidad un método de
búsqueda. - La Computación Evolutiva, en resumen, es
la ciencia
computacional cuyos algoritmos imitan el proceso evolutivo de
la naturaleza.
1. http://www.redcientifica.com/doc/doc199904260012.html
2.
http://www.redcientifica.com/gaia/ce/ce_c.htm
3.http://www.lania.mx/spanish/actividades/newsletters/1997-otono-invierno/evolutiv.html
4.http://www.lania.mx/spanish/actividades/newsletters/1997-otono-invierno/evolutiv.html
5.
http://www.cimat.mx/talleres/pasados/2003/evolutiva/
6.
http://www.dccia.ua.es/ria/artics/sceta97.pdf
7.http://www.lania.mx/spanish/actividades/newsletters/1999-primavera-verano/tendencias.html
8. http://cursos.itam.mx/akuri/Semestre2/RNS/0123Pres/0.pdf
9. http://pitagoras.usach.cl/~msanchez/ce/
10.
http://delta.cs.cinvestav.mx/~ccoello/talks.html
11.
http://www.psicologiacientifica.com/articulos/ar-h_gascon01.htm
12.http://chue.ing.ula.ve/DOCENCIA/POSTGRADO/CURSOS/MSS05/ComputacionEvolutiva.html#PE
13.
http://www.elrinconcito.com/articulos/Genetico/Geneticos.htm
14.
http://delta.cs.cinvestav.mx/~ccoello/genetic.html
15.
http://delta.cs.cinvestav.mx/~ccoello/compevol/apuntes.pdf.gz
16. http://kal-el.ugr.es/VidArt/VidaArti.html
17. http://pitagoras.usach.cl/~msanchez/ce/
18.
http://members.tripod.com/jesus_alfonso_lopez/AgIntro.html
19. http://www.iieh.com/comunidad/mherran.html
José Madrigal García
Mateo Luna Luna
CUNDUACÁN TABASCO