Download Computación Evolutiva: Algoritmos Genéticos

Computación Evolutiva:
Algoritmos Genéticos
Apuntes de la asignatura:
Inteligencia Artificial
Razonamiento Aproximado (Máster)
Daniel Manrique Gamo
Profesor Titular de Universidad
Computación Evolutiva: Algoritmos Genéticos
Índice
────────────────────────────────────────────────────────────────────────────────────────────
1. Introducción
5 1.1. Bases de la computación evolutiva
7 1.2. Características de la computación evolutiva
9 2. Algoritmos genéticos
11 2.1. Historia de los algoritmos genéticos
12 2.2. Características y funcionamiento de los algoritmos genéticos
14 2.3. Codificación del problema
17 2.3.1. Codificaciones binarias
18 2.3.2. Codificaciones no binarias
20 2.4. La función de evaluación
23 2.5. Convergencia
25 2.5.1. Medidas de convergencia
2.6. Operadores genéticos
25 27 2.6.1. Operadores de reproducción
27 2.6.2. Operadores de mutación
31 2.6.3. Operadores de cruce con alfabeto finito
32 2.6.4. Operadores de cruce con codificación real
38 2.6.5. Reemplazo de individuos
51
Daniel Manrique Gamo
Página 3
Computación Evolutiva: Algoritmos Genéticos
Introducción
────────────────────────────────────────────────────────────────────────────────────────────
1.
Introducción
Desde mediados de los años cincuenta, existen evidencias del uso de ordenadores para,
entre otras tareas, avanzar en la comprensión del proceso de la evolución natural
[Neum, 56], [Neum, 58]. Uno de los primeros trabajos que utilizan un proceso evolutivo
para la resolución de problemas en computadores es el de Friedberg [Frie, 58], [Frie,
59]. Estos artículos representan los primeros resultados en aprendizaje automático y
describen la utilización de un algoritmo evolutivo para programación automática. El
objetivo era encontrar un programa que calculara una función de entrada-salida.
También el artículo de Fraser [Fras, 57] sirvió de influencia en los primeros trabajos en
esta área.
En esta misma época se presentaron los primeros intentos de aplicar evolución simulada
a problemas de optimización numérica [Brem, 62]. Posteriormente, también comenzó el
desarrollo de la teoría de los algoritmos evolutivos, demostrando que la relación óptima
de mutación para problemas linealmente separables debería tener el valor 1/m, donde m
representa el número de bits que codifica cada individuo [Brem, 65].
Durante este periodo se desarrollaron las ideas de la operación evolutiva (evolutionary
operation EVOP) que utilizaba una técnica evolutiva para el diseño y el análisis de
experimentos industriales [Box, 57], [Box, 69]. Estas ideas no fueron nunca
implementadas en un computador, aunque fueron usadas para el desarrollo del método
denominado diseño símplex [Spen, 62].
Como suele suceder con el comienzo de cualquier nuevo campo de estudio, estos inicios
se veían con un alto grado de escepticismo. Sin embargo, a mediados de los sesenta ya
están establecidas las bases de lo que hoy son las tres ramas principales de la
computación evolutiva (CE). Así los trabajos de Fogel [Foge, 66] en San Diego,
California, se desarrollaron en el campo de la Programación Genética (PG).
Por otra parte, se desarrollan los algoritmos genéticos por Holland [Holl, 69] en la
Universidad de Michigan, y las estrategias evolutivas (EE) en la Universidad de Berlín
[Rech, 65].
Durante los siguientes veinticinco años, cada una de estas ramas se desarrolló de una
forma bastante independiente, pero con rutas paralelas. Fue en el año 1991 cuando se
hizo un esfuerzo por acercar a los distintos investigadores que trabajaban en CE. Para
ello tuvo lugar la celebración del Workshop on Paralell Problem Solving from Nature
en Dortmund, donde realmente se acuñó el nombre de Computación Evolutiva [Schw,
91] para englobar las tres técnicas empleadas para simular los distintos aspectos de la
evolución: los algoritmos genéticos, las estrategias evolutivas y la programación
genética. Todas ellas tienen en común que utilizan la reproducción, el azar, la
competición y la selección de los individuos de la población. Así, en cualquiera de estas
técnicas evolutivas están presentes las ideas de la esencia de la evolución y al menos
Daniel Manrique Gamo
Página 5
Computación Evolutiva: Algoritmos Genéticos
Introducción
────────────────────────────────────────────────────────────────────────────────────────────
uno de estos cuatro procesos, presuponiendo que, tanto en la naturaleza como en la
informática, la evolución es la mejor herramienta de optimización [Atma, 76].
Desde un primer momento, las ideas de la CE se orientan hacia cuatro objetivos:
1. Optimización. La evolución en sí es un proceso de optimización [Mayr, 88] en el
que se busca adaptar, lo mejor posible, los individuos al entorno en el que habitan.
Darwin [Darw, 59] estudió, sorprendido, la extrema perfección que ciertos órganos
habían alcanzado mediante la evolución, como por ejemplo, los ojos. Sin embargo,
optimización no significa perfección. La evolución descubre soluciones funcionales
altamente precisas para problemas concretos que se dan en el medio ambiente de un
determinado individuo. Debido a esto, ya desde un primer momento, se pensó en su
utilización para resolver problemas de optimización en ingeniería. Las técnicas
clásicas utilizadas en esta área, como el descenso del gradiente, técnicas de escalada,
o las puramente aleatorias habían sido claramente inadecuadas al enfrentarse a
problemas de optimización no lineales, especialmente aquellos que contenían una
componente estocástica, temporal o de caos. Todas estas ideas fueron claves para el
desarrollo de las EE [Rech, 94], [Schw, 95].
2. Sistemas robustos. Los problemas del mundo real casi nunca son estáticos y los
problemas de optimización temporal son cada vez más comunes. Estas
circunstancias requieren un cambio en la estrategia que se aplica para resolver el
problema. En estos casos, la realimentación sobre el éxito o el fracaso de la
estrategia actual es fundamental. Holland [Holl, 75], utilizando AAGG, describe un
procedimiento que puede hacer evolucionar estrategias, tanto como cadenas
codificadas de números o como bases de reglas llamadas sistemas clasificadores. El
resultado es un procedimiento robusto que tiene la capacidad de ajustar el
rendimiento basándose en la realimentación de la salida del sistema.
3. Inteligencia artificial. Como se puede comprobar, la evolución ha creado especies
con una inteligencia cada vez más desarrollada. Por tanto, la forma de conseguir
inteligencia artificial, además de las alternativas clásicas que persiguen la emulación
de la inteligencia humana, ya sea mediante la emulación de las estructuras
biológicas del sistema nervioso o mediante la emulación del comportamiento, tiene
una nueva posibilidad: simular la evolución para construir algoritmos predictivos.
Esta es la base de las investigaciones en CE [Foge, 62], [Foge, 66].
4. Vida artificial. En el campo de la biología, más que utilizar la evolución como una
herramienta, se intenta capturar la esencia de la propia evolución en una simulación
por computador y usar entonces esta simulación para conseguir una nueva
información sobre la física de los procesos de la evolución natural [Ray, 91]. El
éxito en este campo abre la posibilidad de estudiar sistemas biológicos alternativos
de cómo puede ser la vida en otros lugares y averiguar qué características pueden
tener en común con la de La Tierra [Lang, 87]. Aunque cada modelo es incompleto
y las características que tiene la vida en otros lugares del universo es pura
Daniel Manrique Gamo
Página 6
Computación Evolutiva: Algoritmos Genéticos
Introducción
────────────────────────────────────────────────────────────────────────────────────────────
especulación, las simulaciones de vida por ordenador, denominadas genéricamente
vida artificial, ya han conseguido generar algunos patrones que se corresponden con
fenómenos que normalmente ocurren en la vida en La Tierra.
Una vez vistas las distintas ramas de aplicación de la CE, la cuestión fundamental que
se plantea ahora es por qué simular los procesos de la evolución. Una respuesta podría
ser que en estos momentos no se dispone de mejores alternativas. Normalmente, no se
pueden utilizar eficientemente las técnicas clásicas de optimización para encontrar un
máximo global en una función si está rodeado de máximos locales. Las técnicas
desarrolladas hasta ahora para emular la inteligencia humana no son suficientemente
adaptables a los dominios cambiantes, ya que no son suficientemente capaces de
predecir ni de anticipar sus acciones. Tampoco se puede visitar un nuevo mundo,
enviarle los compuestos químicos primigenios que dan lugar a la vida y esperar
millones de años para ver qué tipo de vida se desarrolla allí. En contraste, los métodos
de computación evolutiva ofrecen posibles soluciones a estos problemas basándose en
la utilización dirigida del azar y la incertidumbre.
De acuerdo con el teorema “no-free-lunch” (NFL) [Wolp, 96], no puede existir ningún
algoritmo que resuelva todos los problemas (por ejemplo de optimización) que sea, en
general, superior a cualquier otro. Por tanto, en principio, la cuestión de si los
algoritmos evolutivos son superiores o inferiores a cualquier otra aproximación no tiene
sentido. Sin embargo, es posible afirmar que los algoritmos evolutivos se comportan
mejor que otros métodos con respecto a problemas específicos y, como consecuencia, se
comportarán peor con respecto a otras clases de problemas.
El teorema NFL puede corroborar que, en el caso de los algoritmos evolutivos frente a
otros métodos clásicos de optimización, son más eficientes resolviendo problemas
discontinuos, no diferenciables, multimodales, con ruido y cualquier tipo de superficies
de búsqueda no convencionales. Por el contrario, su efectividad disminuye al afrontar
problemas más simples para los que se han desarrollado algoritmos específicos en su
resolución.
Por tanto, en principio, y mientras no se desarrolle un método específico de resolución
del problema que tenga en cuenta ciertas propiedades del mismo que lo haga más
eficiente, parecen claras las ventajas de la utilización de algoritmos no especializados y
robustos como los algoritmos evolutivos.
1.1.
Bases de la computación evolutiva
La más comúnmente aceptada base de teorías sobre la evolución es el paradigma neoDarwiniano. En esta teoría se afirma que la mayor parte de la historia de la vida puede
ser completamente justificada mediante procesos físicos y mediante poblaciones y
especies [Hoff, 89]. Estos procesos son: la reproducción, la mutación, la competición y
la selección. La reproducción es una propiedad común de las especies. Hay que tener en
cuenta que, normalmente, la capacidad reproductiva de las especies es enorme y el
Daniel Manrique Gamo
Página 7
Computación Evolutiva: Algoritmos Genéticos
Introducción
────────────────────────────────────────────────────────────────────────────────────────────
número de individuos se incrementaría exponencialmente si todos sus individuos se
pudieran reproducir con éxito simultáneamente. La reproducción supone la transferencia
del código genético de cada individuo a su descendencia. La mutación sucede debido a
que los errores en la replicación durante el proceso de transferencia de información
genética son inevitables, además de ser necesario incluir variabilidad en las especies. La
competición es una consecuencia del crecimiento de la población dentro de un espacio
físico finito donde no hay espacio o energía para todos. La selección es el resultado de
la reproducción de las especies en un medio de competencia. Gracias a ella, sobrevivían
los mejores individuos, esto es, los más adaptados al medio.
Los individuos y las especies pueden ser vistos como una dualidad de su código
genético, el genotipo, y su forma de plasmarse con respecto al mundo, el fenotipo. El
genotipo ofrece la posibilidad de almacenar la experiencia acumulada, adquirida de la
información histórica. Desgraciadamente, el resultado de la variación genética es
impredecible debido a los efectos combinados de la pleitropía y la poligénesis, [Mayr,
88]. La pleitropía implica que un único gen afecta simultáneamente a varias
características del fenotipo, mientras que la poligénesis significa que cada característica
del fenotipo viene determinada por la interacción de varios genes. No se conoce ninguna
relación, uno a uno, entre genes y características en los sistemas evolutivos naturales.
Debido a esto, el fenotipo cambia siguiendo una función compleja, no lineal, de la
interacción entre las estructuras genéticas y las condiciones medioambientales. De esta
forma, códigos genéticos muy distintos pueden tener comportamientos equivalentes,
igual que programas diferentes pueden conseguir resultados similares.
Dentro del proceso de evolución, hay que tener en cuenta que la selección actúa sólo
sobre los comportamientos externos de los individuos y las especies [Mayr, 88] y no
sobre el genotipo que representan. La selección viene dada por la adaptación de los
individuos al entorno, y esta adaptación se puede ver como un espacio con una
topografía adaptativa dependiente de las condiciones del entorno. Una población de
genotipos genera sus respectivos fenotipos que, por sus características de adaptación al
medio, están situados en un cierto lugar del mapa de adaptación. Cada pico de este
mapa se corresponde con una zona de fenotipos optimizados. De una forma
probabilística, la evolución acerca a los individuos a estos picos, mientras que la
selección elimina las variantes fenotípicamente peores.
Visto de esta forma, la evolución es claramente un proceso de optimización en
resolución de problemas. La selección conduce los fenotipos tan cerca como es posible
del óptimo para la supervivencia con respecto a unas condiciones iniciales y unas
restricciones del entorno. Sin embargo, el entorno está continuamente cambiando y, por
tanto, las diferentes especies constantemente evolucionan hacia nuevos óptimos. Debido
a esto, no se puede decir que ningún organismo esté perfectamente adaptado a su
entorno.
Daniel Manrique Gamo
Página 8
Computación Evolutiva: Algoritmos Genéticos
Introducción
────────────────────────────────────────────────────────────────────────────────────────────
Según todo lo visto anteriormente, se resumen a continuación las características más
importantes del paradigma neo-Darwiniano:
•
El individuo es el principal objetivo de la evolución.
•
La variación genética es un fenómeno de probabilidad. Los fenómenos estocásticos
juegan un papel importante en la evolución.
•
La variabilidad de genotipo se basa, en su mayor parte, en un proceso de
recombinación y, sólo en menor medida, en la mutación.
•
La evolución gradual puede incluir discontinuidades en el fenotipo.
•
No todos los cambios en el fenotipo tienen que ser consecuencia de la selección
natural.
•
La evolución es un cambio en la adaptación y la diversidad, no solamente un cambio
en la frecuencia de los genes.
•
La selección es probabilística, no determinística.
1.2.
Características de la computación evolutiva
Todas las técnicas de la CE se basan en el modelo de la evolución natural, por lo que
todos comparten un conjunto de características comunes. A continuación se reseñan las
más importantes:
•
Se utiliza una estrategia de aprendizaje colaborativo a partir de un conjunto de
individuos. Normalmente, cada individuo representa o codifica un punto del espacio
de búsqueda de soluciones en un problema dado. Cada individuo incorpora
información adicional que permite llegar a la solución final del problema.
•
La descendencia, obtenida a partir de los individuos de la población, se genera de
forma pseudo-aleatoria mediante procesos de cruce y recombinación donde se
intercambia información entre dos o más individuos actualmente existentes. La
mutación es un proceso de auto-replicación errónea de los individuos que produce
pequeños cambios en los mismos.
•
Mediante la evaluación de los individuos, se consigue una medida de la adaptación
de cada uno de ellos a su entorno. De acuerdo con esta medida de adaptación, el
proceso de selección favorece más a los individuos mejor adaptados, que serán por
tanto los que se reproduzcan más frecuentemente.
Estas son las características generales que comparten todas las ramas de la CE. Sin
embargo, existen diferencias de implementación de estos principios que caracterizan y
diferencian a los algoritmos genéticos, las estrategias evolutivas y la programación
genética. A continuación se muestra, de forma resumida, las principales características
diferenciadoras de cada una de estas ramas [Foge, 95], [Back, 96]:
Daniel Manrique Gamo
Página 9
Computación Evolutiva: Algoritmos Genéticos
Introducción
────────────────────────────────────────────────────────────────────────────────────────────
•
Las estrategias evolutivas normalmente usan la mutación para modificar vectores de
números reales, empleando la recombinación (cruce) como operador principal de
búsqueda. El operador de selección es determinístico y, normalmente, el tamaño de
la población de los padres y el de la descendencia es distinto. Dado que este tipo de
algoritmos se apoyan principalmente en el operador de mutación, realizan
búsquedas muy exploratorias del espacio de búsqueda, lo cual resulta interesante en
las primeras iteraciones del proceso de evolución; sobre todo en la resolución de
problemas paramétricos de los que apenas se conoce nada. Sin embargo, esta misma
capacidad exploratoria de las estrategias evolutivas impide alcanzar la convergencia
hacia el óptimo resultando, por tanto, ineficientes en las etapas más tardías del
proceso evolutivo.
•
Los algoritmos genéticos se basan en el cruce como el operador de búsqueda más
importante. A diferencia de las estrategias evolutivas, el operador de mutación se
aplica con una probabilidad muy pequeña, y no es considerado un operador
fundamental. Se usa la selección probabilística y, generalmente, se emplea la
codificación de los individuos mediante cadenas binarias, aunque también se pueden
emplear otras codificaciones tales como las basadas en números reales [Eshe, 93].
•
La programación genética es una extensión de los algoritmos genéticos. Busca
construir programas de computador sin que ellos sean diseñados y programados
expresamente por un humano. Puede decirse que es una técnica de optimización
cuyo espacio de búsqueda son los posibles programas de computador que
solucionan un problema determinado. Al igual que ocurre con los algoritmos
genéticos, la creación de los individuos es completamente aleatoria, es decir, el
computador no ha sido explícitamente programado para encontrar una solución
predeterminada. Se parte de una situación sujeto de la investigación (estado inicial)
obtenida de forma aleatoria, a la que se aplican sucesivamente los operadores
genéticos (selección, cruce, mutación y reemplazamiento de individuos) hasta llegar
a una solución del problema (estado final).
Daniel Manrique Gamo
Página 10
Computación Evolutiva: Algoritmos Genéticos
Algoritmos Genéticos
────────────────────────────────────────────────────────────────────────────────────────────
2.
Algoritmos genéticos
Como se ha descrito anteriormente, los algoritmos genéticos (en adelante AAGG) son
una clase de algoritmos evolutivos que se usan para resolver problemas de búsqueda y
optimización. Los AAGG son capaces de hacer evolucionar los individuos de una
población hacia soluciones del mundo real, siempre que se encuentre una codificación
adecuada del problema, siendo ésta una de las claves principales de éxito cuando se
aplica este tipo de técnicas.
Los AAGG simulan mediante poblaciones de individuos la evolución sufrida a través de
diferentes operadores. En la naturaleza, los individuos de una población compiten entre
ellos por diferentes recursos necesarios para la supervivencia como el agua y la comida,
y los miembros de una misma especie también compiten por aparearse. De todos ellos,
los que tienen más éxito en sobrevivir y aparearse conseguirán un mayor número de
descendientes. Los individuos con peores aptitudes producirán muy poca o ninguna
descendencia. Esto significa que los genes de los individuos de mayor adaptación al
medio serán heredados por un número creciente de individuos en cada generación. La
combinación de buenas características de diferentes antepasados puede generar una
descendencia altamente adaptada al medio. De la misma forma, es posible también que
la combinación de genes de individuos bien adaptados generen otros con peores
características, con lo que estos individuos tenderán a desaparecer. Es posible, además,
que se produzcan cambios en el propio medio de vida, por lo que las especies
evolucionarán hacia las nuevas condiciones de vida.
Los AAGG presentan una analogía directa a este comportamiento natural. A cada
individuo se le asigna un valor dependiendo de lo buena que sea la solución que aporta
al problema. A los individuos con mayor adaptación, esto es, a los que mejores
soluciones representan, se les da mayor oportunidad de reproducirse, cruzándolos con
otros individuos de la población que probablemente representan también buenas
soluciones al problema. Así se produce la descendencia cuyos individuos comparten
características de cada uno de los padres. Se van produciendo por tanto, nuevas
generaciones con una proporción mayor de individuos mejor adaptados. De esta forma,
con el paso de las generaciones, las poblaciones constan de individuos que aportan
mejores soluciones al problema, mezclándose entre sí en busca de la solución óptima.
Al favorecer el cruce entre los individuos mejor adaptados, se exploran las áreas más
prometedoras del espacio de soluciones del problema, sin dejar de lado tampoco
soluciones que, a priori, pueden considerarse como peores, pero que al recombinarse
pueden dar lugar a individuos muy bien adaptados. Si el AG ha sido bien diseñado, la
población convergerá hacia la solución óptima del problema.
La potencia de los AAGG viene de que la técnica que usan es robusta y puede tratar con
éxito un gran número de tipos de problemas, incluyendo y destacando aquellos que son
Daniel Manrique Gamo
Página 11
Computación Evolutiva: Algoritmos Genéticos
Algoritmos Genéticos
────────────────────────────────────────────────────────────────────────────────────────────
difícilmente solucionables utilizando otro tipo de métodos clásicos. Los AAGG no
garantizan la localización exacta de la solución óptima del problema, pero proporcionan
una solución alternativa aceptablemente buena en un tiempo corto. Este hecho es
especialmente interesante en el caso de resolución de problemas donde todavía no se ha
desarrollado una técnica específica.
2.1.
Historia de los algoritmos genéticos
Las primeras ideas en las que se basan los AAGG se pueden encontrar en los artículos
de Holland de principios de los años 60 [Holl, 62]. En ellos se establecen los aspectos
básicos para la comprensión y el establecimiento de los principios básicos de los
sistemas adaptativos. Estos sistemas son capaces de automodificarse en respuesta a su
interacción con el medio en el que están funcionando. Las teorías sobre los sistemas
adaptativos están orientadas a facilitar, por un lado, la comprensión de las formas
complejas de adaptación que aparecen en los sistemas naturales y, por otro, la habilidad
para diseñar sistemas adaptativos robustos.
Según Holland, la característica fundamental de los sistemas adaptativos naturales es el
éxito en el uso de la competición y la innovación que les proporciona la habilidad de
responder dinámicamente a sucesos nuevos y a cambios en el medio. Para llegar a estas
ideas, Holland se basó en modelos simples de evolución biológica, a través de la
superviviencia del más adaptado y la producción continua de nueva descendencia.
A mediados de los años 60, las ideas de Holland empezaron a plasmarse en modelos
implementados en ordenador. En cada uno de estos sistemas se representaban elementos
por medio del uso de genomas en los que los mecanismos de evolución y herencia eran
abstracciones de operadores genéticos como la mutación, el cruce o la inversión.
Estos estudios experimentales desembocaron en el tratamiento de problemas de
búsqueda más complejos, como el reconocimiento de patrones. Asimismo, se realizaron
los primeros estudios con operadores de selección de tipo elitista y las ideas básicas
para el empleo de probabilidades adaptativas de mutación y cruce. También en esta
época se estudió detalladamente, por primera vez, las diferentes posibilidades de
reproducción y cruce. Usando dos espacios de soluciones diferentes, se experimentó con
una amplia variedad de operadores de cruce. También resultó interesante la utilización
de la codificación binaria del genoma y las ventajas de la codificación Gray [Hols, 71].
En paralelo con estos estudios experimentales, Holland continuó trabajando en una
teoría general de los sistemas adaptativos [Holl, 67]. Durante este periodo, desarrolló la
teoría de los patrones en los sistemas adaptativos [Holl, 69] y utilizó estas ideas para
completar el análisis teórico de sus planes reproductivos [Holl, 71], [Holl, 73].
Posteriormente, Holland compiló todas estas ideas en su libro “Adaptation in Natural
and Artificial Systems” [Holl, 75].
Es interesante destacar que muchas de las propiedades de los AAGG identificadas por
Holland de forma teórica no pudieron ser observadas experimentalmente debido a la
Daniel Manrique Gamo
Página 12
Computación Evolutiva: Algoritmos Genéticos
Algoritmos Genéticos
────────────────────────────────────────────────────────────────────────────────────────────
falta de recursos computacionales. Esto obligaba a trabajar con un número limitado de
generaciones y con un número muy pequeño de individuos, habitualmente menos de 20.
En estos casos, las desviaciones en el comportamiento esperado de los AAGG se debía
al fenómeno de la pérdida de diversidad genética debido a los fenómenos estadísticos
que se producen en la selección y reproducción en poblaciones pequeñas.
A principios de los setenta ya había un gran interés en entender mejor el
comportamiento de los AAGG. En concreto, se sabía que la elección del tamaño de la
población, la representación de los individuos y la elección de los operadores y sus
probabilidades de actuación tenían efectos relevantes en el funcionamiento de los
AAGG. Así se realizaron estudios en detalle sobre la influencia del cruce y la mutación,
y se empezaron a utilizar los operadores de cruce basados en múltiples puntos [Fran,
72].
Estos estudios fueron ampliados posteriormente de forma teórico-práctica con el
análisis de los efectos cruzados de la modificación del tamaño de la población, cruce y
mutación en el comportamiento de una familia de AAGG utilizados para optimizar un
conjunto fijo de funciones de prueba [Dejo, 75]. A partir de estos estudios se empezó a
vislumbrar el enorme potencial de los AAGG para resolver problemas de optimización.
En esta misma época, se empieza a generalizar la investigación sobre los AAGG al
iniciarse trabajos en diversas universidades. Esta generalización fue muy lenta en un
principio debido a cierto escepticismo creado por los malos resultados que habían
obtenido las técnicas basadas en sistemas auto-organizativos y las redes de neuronas
artificiales con los perceptrones que no cubrieron las expectativas creadas. A pesar del
ambiente de pesimismo que se creó en torno a estas técnicas, se celebró en la
Universidad de Michigan el congreso “An interdisciplinary Workshop in Adaptive
Systems” [Samp, 81], lo cual impulsó su estudio, consiguiendo que se establecieran
diversos grupos de trabajo. Así, se empezaron a estudiar los sistemas clasificadores
propuestos por Holland [Beth, 81], [Book, 82], [Gold, 83], nuevas mejoras de los
AAGG como la regla de ponderación para aprendizaje de reglas [Smit, 80], [Wetz, 83],
o también, el estudio de nuevas aplicaciones de optimización [Brin, 91].
Dado el creciente interés en los AAGG, se organizó en 1985 el primer “International
Congress on Genetic Algorithms” donde se presentaron los últimos avances tanto
teóricos como prácticos en el empleo de estas técnicas [Gref, 85]. El éxito de esta
edición del congreso consiguió que se instaurara su celebración cada dos años. A partir
de 1989, las actividades en el campo de los AAGG habían crecido mucho, por lo que se
fundó la “International Society for Genetic Algorithms (ISGA)”.
A partir de 1990, la tendencia ha sido la de un tremendo crecimiento y diversificación
del área de investigación de los AAGG, como se refleja en el éxito de las distintas
conferencias y la proliferación de libros y publicaciones periódicas. La interacción de
los AAGG con otras técnicas de la Computación Evolutiva se ha traducido en un muy
productivo intercambio de ideas y la aparición de nuevas aplicaciones híbridas.
Daniel Manrique Gamo
Página 13
Computación Evolutiva: Algoritmos Genéticos
Algoritmos Genéticos
────────────────────────────────────────────────────────────────────────────────────────────
Actualmente, las aplicaciones basadas en AAGG continúan desarrollándose abarcando
un amplio abanico de campos como la ingeniería, la investigación operativa y la
programación automática.
2.2.
Características y funcionamiento de los algoritmos genéticos
Los AAGG comienzan con una muestra aleatoriamente elegida en el espacio de
búsqueda, para ir transformándola paso a paso hasta llegar a un estado estacionario, en
el cual la muestra, también llamada población, está constituida por las soluciones del
problema. Un AG no actúa, en general, directamente sobre el espacio de búsqueda, sino
sobre una codificación de éste, haciendo interaccionar entre sí y operando sobre las
cadenas resultantes de dicha codificación. Esta acción tiene como consecuencia la
progresiva transformación del conjunto de elementos evaluados, hasta llegar al estado
final. Para ello, los algoritmos genéticos se valen de la acción de los llamados
operadores genéticos, tales como reproducción, cruce y mutación, a la que es sometida
la población. Cada operador juega un papel diferente en la evolución de la población.
Así, la reproducción puede ser entendida como una competición, mientras que los otros
operadores, tales como el cruce y la mutación son capaces de crear nuevos individuos a
partir de los existentes en la población. La figura 3.1 muestra el funcionamiento
genérico de los AAGG.
Figura 3.1. Esquema general de funcionamiento de los algoritmos genéticos.
El operador de reproducción obtiene un mejoramiento de la población, mediante un
proceso en el cual se obtienen individuos para la población mejorada de acuerdo con
cierta ley de probabilidad. Para cada individuo, la probabilidad de ser elegido por este
operador, para formar parte de la siguiente generación, depende de su proximidad al
óptimo buscado. De este modo, este operador causa la desaparición de los individuos
más débiles, a costa de la permanencia de los más fuertes.
La reproducción sólo selecciona individuos de entre la población existente. Para llegar
de este modo a las proximidades del óptimo buscado, se necesitaría una gran cantidad
de individuos en la población, ya que la solución proporcionada por la única aplicación
de este operador sería un individuo de la población inicial. En el caso extremo de que la
población estuviera constituida por la totalidad de los individuos entre los que se busca
el óptimo, un algoritmo aceptable consistiría en la sucesiva aplicación de este operador
Daniel Manrique Gamo
Página 14
Computación Evolutiva: Algoritmos Genéticos
Algoritmos Genéticos
────────────────────────────────────────────────────────────────────────────────────────────
sobre dichos individuos hasta obtener una única muestra formada por un único
individuo repetido en toda la población. Precisamente, una de las ventajas de los
algoritmos genéticos consiste en su eficacia para obtener buenos resultados partiendo de
muestras con cardinal relativamente pequeño con respecto al cardinal del conjunto en el
cual se busca la solución.
La introducción del operador de cruce permite renovar la población, supliendo el
inconveniente presentado por la reproducción. Es en este operador donde juega un papel
muy importante la codificación. Se trabaja ahora con códigos de individuos, de forma
que cada punto del espacio de búsqueda se transforma en un vector o cadena, cuyos
elementos están formados por caracteres pertenecientes a un determinado alfabeto. El
cruce actúa según cierta probabilidad, obteniendo nuevos individuos, denominados
descendencia, con ciertas características “heredadas” de aquellos de los cuales se partió.
Generalmente se suelen emplean dos individuos padres, para generar una descendencia
nueva de otros dos individuos.
Podría pensarse que el efecto de este operador es negativo, ya que pueden resultar
destruidas, de un modo aparentemente arbitrario, cadenas correspondientes a puntos
obtenidos mediante reproducción. Por ello, si bien es cierto que existe una probabilidad
de que estas cadenas se pierdan, también es posible que los nuevos elementos que van
apareciendo mejoren la población, tanto por su proximidad al óptimo buscado, como
por los posibles descendientes a los que pudiera dar lugar posteriormente. Este
enriquecimiento de la población es el objetivo del operador de cruce.
Cuando se cruzan cadenas, existe cierta relación entre los progenitores y los
descendientes. Es por ello por lo que se puede hablar de herencia transmitida por los
primeros a los segundos. Hay ocasiones, con fines experimentales, donde únicamente se
emplean estos dos operadores descritos con el fin de observar más claramente el
comportamiento de los mismos y poder obtener conclusiones. Sin embargo, los
resultados que se obtienen son mejores cuando el algoritmo utilizado se completa con el
operador de mutación. Dicho operador actúa, con cierta probabilidad, directamente
sobre las cadenas, cambiando de forma aleatoria alguno de sus valores. El efecto de este
cambio, en una cadena afectada por el operador, es imprevisible, en el sentido de que
puede obtenerse, a partir del elemento del que se parte, cualquier otro del espacio de
búsqueda. De este modo, se obtienen nuevos individuos para ser evaluados. Esto
produce un enriquecimiento de los individuos de la población, objetivo común de los
operadores de cruce y mutación. Pero con la mutación, desaparece el concepto de
herencia transmitida de los padres a la descendencia que existía en el operador anterior.
Se puede decir que la mutación provoca la búsqueda en nuevas regiones del espacio,
que de otro modo serían inaccesibles. Sin este operador, la búsqueda quedaría limitada,
tras cierto número de pasos, a determinadas zonas de dicho espacio. Con esto, existe el
peligro que el algoritmo converja a soluciones subóptimas [Sced, 89].
Daniel Manrique Gamo
Página 15
Computación Evolutiva: Algoritmos Genéticos
Algoritmos Genéticos
────────────────────────────────────────────────────────────────────────────────────────────
Con relación al tema de que la solución obtenida por el algoritmo esté más o menos
próxima al óptimo buscado, se necesita una base teórica que proporcione un método
para el estudio de dicha proximidad. Según se decía anteriormente, una de las
características de los AAGG es que la solución se presenta en forma de un conjunto de
puntos, y no de un único punto. Partiendo de un estado inicial, la población evoluciona
para aproximarse a la solución del problema. En cada nuevo estado, se aproxima más a
la solución. Finalmente, si el problema converge a un único punto, la población estará
formada por el mismo elemento, repetido tantas veces como indique su cardinal.
También se puede hablar de convergencia cuando una población está formada por
puntos que, aunque no sean todos iguales entre sí, están muy cercanos a la solución.
Para el estudio de la evolución de la población se ha utilizado la teoría de patrones
[Holl, 81] para el caso de individuos codificados con un alfabeto finito. Dicha teoría
proporciona algunas bases teóricas para el conocimiento de la evolución de la población
cuando se aplica un AG. También se han realizado estudios de convergencia mediante
series de Walsh [Barr, 94] que permitan decidir si se puede producir la convergencia
hacia el óptimo en un problema dado según su función objetivo y las condiciones
necesarias que permiten dicha convergencia en el menor tiempo posible [Barr, 98].
Cuando se trabaja con AAGG con individuos codificados con números reales o, en
general, cuando el cardinal del alfabeto utilizado es muy grande, el problema de la
convergencia se ha abordado también mediante la teoría de patrones, esta vez definidos
mediante intervalos de números reales [Eshe, 93].
Los AAGG proporcionan un método de optimización con características que lo hacen
particularmente interesante con respecto a determinadas aplicaciones. Un AG trabaja
con una población de puntos, actuando sobre ellos en paralelo, comparando los valores
obtenidos de la función que se desea optimizar en dichos puntos y obteniendo nuevos
puntos a partir de los que ya se tienen valorados. De este modo, puede interpretarse que
un AG efectúa una búsqueda en un dominio en un sentido global. Por el contrario, otros
métodos de optimización, tanto deterministas como aleatorios, utilizan un conocimiento
local de los puntos del conjunto de búsqueda, teniendo únicamente información de un
entorno de un punto. En este sentido, los AAGG usan la información aportada por todo
un conjunto de puntos de manera simultánea, por lo que, aún en el caso de búsqueda de
puntos óptimos en funciones que no presenten problemas de regularidad, el método
proporcionado por los AAGG presenta ciertas ventajas frente a los tradicionales, ya que
esta “visión global” de la función objetivo es la que evita el peligro de la caída en
óptimos locales comentada anteriormente. Asimismo, el paralelismo implícito de este
tipo de algoritmos tiene como consecuencia una mayor rapidez en la búsqueda.
El método proporcionado por los AAGG, si bien no puede ser clasificado como
determinista, tampoco puede serlo como aleatorio estrictamente hablando. No es posible
conocer, a partir de un conjunto de puntos dado, cuáles serán los siguientes puntos que
se obtengan en la búsqueda como ocurre en el caso de los algoritmos deterministas. Sin
embargo, se introducen técnicas que orientan la búsqueda hacia zonas del dominio
Daniel Manrique Gamo
Página 16
Computación Evolutiva: Algoritmos Genéticos
Algoritmos Genéticos
────────────────────────────────────────────────────────────────────────────────────────────
donde es más probable encontrar los puntos deseados, por lo que tampoco es un
algoritmo de tipo aleatorio. Como se verá más adelante, los AAGG utilizan cierta
información sobre la proximidad de los puntos elegidos al óptimo, por lo que la
búsqueda se centra más en aquellas zonas del dominio de la función en donde hay
mayor probabilidad de encontrar puntos próximos al óptimo.
La mayoría de las implementaciones de los AAGG mantienen una población de tamaño
fijo, de tal forma que, partiendo de una población de tamaño λ, se aplican los
operadores genéticos sobre la población antigua, hasta completar una nueva población
de λ individuos que reemplaza por completo a la anterior.
Para aplicar un AG a la resolución de un problema concreto, se necesita la
configuración de distintas fases. En primer lugar, se debe diseñar una codificación del
problema que determine un espacio de búsqueda. Después, hay que pensar cómo
evaluar los individuos con respecto al problema que se quiere resolver, cómo aplicar los
operadores genéticos de reproducción, cruce y mutación, cuáles de los existentes son los
más adecuados para el problema en concreto y, por último, cómo realizar la sustitución
de individuos de generaciones anteriores. Las distintas opciones disponibles para
realizar estas tareas se muestran en los siguientes puntos.
2.3.
Codificación del problema
Cuando se trabaja con AAGG, se precisa algún método de codificación de los puntos
del espacio de búsqueda de la función con la que se está trabajando. Esta es una de las
características más interesantes y peculiares del método, ya que con ello cada punto se
puede tratar como una cadena, en función de la codificación utilizada. Por tanto, una
vez aplicada la codificación, el dominio de la función a optimizar queda transformado
en un conjunto acotado de valores representados por cadenas, independientemente de su
origen.
Habitualmente, la codificación utilizada suele ser completa. Es decir, si se utiliza un
alfabeto A de cardinal finito m, y cadenas de longitud l, cualquiera de las ml posibles
cadenas corresponde a la codificación de un único punto del dominio de la función
[Barr, 91]. Sin embargo, dada la discretización establecida por la codificación, la
correspondencia anterior no es biunívoca entre el dominio de la función objetivo y las
diferentes cadenas. En otras palabras, si se considera el conjunto Al de todas las posibles
l-uplas de elementos de A, con la condición de que ml no sea mayor que el cardinal del
dominio de la función que se quiere optimizar, existe al menos una aplicación inyectiva
Ω entre dicho conjunto y el dominio. La terna formada por A, l y una de tales
aplicaciones Ω, determina una codificación de un subconjunto del dominio. Dicho
subconjunto es Ω(Al), y se entiende que cada elemento (a1, a2, ..., al) de Al es la
codificación de su imagen mediante Ω. Ahora bien, el número de puntos codificados es
ml. Por tanto, sólo será posible la búsqueda del óptimo entre estos puntos. Con la
Daniel Manrique Gamo
Página 17
Computación Evolutiva: Algoritmos Genéticos
Algoritmos Genéticos
────────────────────────────────────────────────────────────────────────────────────────────
notación anterior, se puede definir el espacio de búsqueda como el subconjunto Ω(Al)
del dominio de la función objetivo.
Cuando se utiliza codificación completa, el espacio de búsqueda depende del cardinal
del alfabeto utilizado y de la longitud de las cadenas. De este modo, con un alfabeto de
cardinal m, y una longitud l para las cadenas, el cardinal del espacio de búsqueda es ml,
y será necesario aumentar la longitud de las cadenas, o bien elegir un alfabeto de mayor
cardinal, cuando se desee obtener mayor cantidad de puntos.
En general, al conjunto de puntos del espacio de búsqueda o individuos (posibles
soluciones al problema) con los que trabaja un AG en un momento dado del proceso de
evolución se denomina población. Los individuos que forman una población se
representan a su vez, como un conjunto de parámetros denominados genes. Cada gen
representa una posición en la cadena. A cada uno de los posibles valores que puede
tomar un determinado gen, se denomina alelo. Por tanto, el número de alelos posibles
de un gen coincide con el cardinal del alfabeto utilizado: m. Si la codificación es binaria
entonces existen dos posibles alelos por cada gen que son el valor cero y el valor uno.
Por último, los genes a su vez se agrupan para formar cromosomas. En la literatura
existente, se suele identificar individuo con cromosoma aunque, en general, en la
naturaleza, un individuo consta de varios cromosomas. La figura 3.2 muestra de forma
esquemática estos conceptos.
Figura 3.2. Estructura de los datos manejados por un algoritmo genético.
2.3.1.
Codificaciones binarias
Inicialmente se empezó a trabajar con codificaciones binarias de las cadenas que forman
la población. Es decir, el alfabeto habitualmente utilizado en los algoritmos genéticos
era {0,1}. En este sentido, es necesario escoger el tipo de codificación binaria que se va
emplear. Algunos trabajos experimentales indican que la codificación Gray supera a la
codificación binaria estándar [Caru, 88], al menos en los casos de prueba más
Daniel Manrique Gamo
Página 18
Computación Evolutiva: Algoritmos Genéticos
Algoritmos Genéticos
────────────────────────────────────────────────────────────────────────────────────────────
comúnmente utilizados. La razón de esta superioridad es que en la codificación Gray,
dos números enteros adyacentes sólo varían su representación binaria en un único bit.
Esto supone que un pequeño cambio en el valor del número codificado repercute muy
poco en la codificación.
Dada la importancia de la codificación de los individuos, se han llevado a cabo diversas
investigaciones para permitir que un AG adapte su propia codificación. Así Holland
propuso desde sus primeros trabajos el operador de inversión para reacomodar la
localización de los genes en las cadenas de los individuos. Posteriormente se desarrolló
el sistema ARGOT [Shae, 87], en el que existe una traducción adaptativa de los
parámetros de números reales a cadenas binarias. La resolución con que la cadena
binaria representa al número real se puede incrementar o decrementar dependiendo de
un cierto número de reglas heurísticas. También se han desarrollado métodos en los
cuales se incrementa la resolución cuando la población comienza a converger [Schr,
92]. Posteriormente se propuso una codificación denominada codificación delta en la
que, cuando la población empieza a converger, la representación de los parámetros se
modifica de forma que el intervalo de codificación esté centrado en el mejor valor
conseguido por el AG hasta el momento y, entonces, se reinicia el algoritmo [Math, 94].
En cualquiera de los casos, para el estudio de las consecuencias de la aplicación de
cualquiera de los operadores, así como la posibilidad de obtener o no la solución o
soluciones esperadas, se introduce el concepto de esquema o patrón [Holl, 81]. Para
ello, se añade al alfabeto binario un tercer carácter, denominado carácter añadido,
obteniendo el alfabeto {0,1,*}. Se denomina entonces patrón o esquema y se representa
por H a todo elemento del conjunto {0,1,*}l.
De este modo, un patrón o esquema se puede representar mediante una l-upla (p1, p2, ...,
pl) donde cada pi∈{0,1,*}. Un patrón p1p2...pl representa un conjunto de cadenas o
elementos de {0,1}l. Para ello, se distinguen dos casos: Si pi es un carácter del alfabeto
original, toda cadena del conjunto toma el valor pi en la posición i. En caso contrario, si
pi=*, entonces las cadenas del conjunto pueden tomar cualquiera de los valores del
alfabeto original en la posición i. Se dice que las cadenas contenidas en un esquema H,
como elementos del conjunto H, son ejemplos o representantes de dicho esquema. La
cantidad de caracteres añadidos de cada patrón determina sus grados de libertad, de
modo que aquellos patrones con más caracteres añadidos tienen, como conjuntos, mayor
cardinal. Concretamente, si en el patrón H aparece el carácter añadido k veces, dicho
patrón es un conjunto formado por 2k cadenas.
Se denomina orden del esquema H, denotado por O(H), a la cantidad de posiciones que
no están ocupadas, en su representación en cadena, por caracteres añadidos. Se trata por
tanto del número de posiciones fijas en el esquema. De este modo, la cantidad de grados
de libertad se obtiene como la diferencia entre la longitud de cadena y el orden.
Daniel Manrique Gamo
Página 19
Computación Evolutiva: Algoritmos Genéticos
Algoritmos Genéticos
────────────────────────────────────────────────────────────────────────────────────────────
Se denomina longitud de un patrón a la distancia máxima entre dos posiciones de dicho
patrón no ocupadas por el carácter añadido. La longitud del patrón H se representa por
l(H).
Por otra parte, ξ(H,t) denota el número de cadenas que en una determinada población en
el tiempo t, se asocian con el esquema H. Se denomina adaptación de un esquema H en
el tiempo t, denotada por eval(H,t), a la media de la función objetivo de todas las
cadenas de la población que pertenecen al esquema H.
Dada una población en el instante t compuesta por λ individuos I1, ..., Iλ, se denota por
F(t) a la media de la función objetivo extendida a toda la población en el tiempo t. Por
tanto, se tiene:
F(t) =
f (Ii),
siendo f(Ii) el valor de la función objetivo del individuo Ii de la población en el instante
t.
Con todos estos conceptos y notación introducida hasta el momento, es posible enunciar
el teorema de los esquemas de la siguiente manera [Larr, 96]:
Sea Esel,cru,mut (ξ(H,t)), el número esperado de individuos que se asocian con el esquema
H, en el tiempo t+1. Después de efectuar la reproducción, el cruce y la mutación en un
algoritmo genético con alfabeto binario, se tiene que:
siendo pc y pm la probabilidad de cruce y mutación respectivamente.
De la fórmula anterior, se desprende como conclusión que esquemas cortos, de bajo
orden y longitud y con una adaptación al problema superior a la adaptación media, se
espera que a medida que evoluciona el AG, obtengan un rápido incremento en el
número de individuos que se asocian con los mismos. La importancia de este teorema
queda de manifiesto cuando se trata de predecir la convergencia de un algoritmo, en
cierto problema. La solución o soluciones obtenidas en cada generación se ajustarán a
los patrones que sobrevivan, hasta ese momento, a la acción de los operadores
genéticos.
2.3.2.
Codificaciones no binarias
Como se ha dicho anteriormente, el tipo de codificación más comúnmente utilizada ha
sido la binaria [Gold, 89b]; sin embargo, desde que se han empezado a utilizar alfabetos
de mayor cardinal [Davi, 91], [Wrig, 91], [Ange, 92], [Anto, 92], se ha observado que
éstos poseen ciertas ventajas [Jani, 91]. La forma más común de codificar un problema
empleando un alfabeto de alta cardinalidad es mediante la codificación con números
enteros [Bram, 91], o mediante números reales [Mich, 91], [Manr, 01].
Daniel Manrique Gamo
Página 20
Computación Evolutiva: Algoritmos Genéticos
Algoritmos Genéticos
────────────────────────────────────────────────────────────────────────────────────────────
En general, no se puede hablar de que la codificación binaria sea siempre superior, en
términos de velocidad de convergencia, a la codificación con números reales o
viceversa. Las ventajas que puede presentar el uso de un tipo u otro de codificación
depende del problema que se esté tratando [Eshe, 93]. La codificación real tiene las
siguientes ventajas frente a la binaria:
•
La propia representación de un problema con un alfabeto de cardinal elevado como
los números reales supone ya una ventaja en sí misma. En cierto tipo de problemas
la interpretación resulta ser mucho más directa que la codificación del problema con
números binarios. En este último caso se requiere de un proceso de descodificación
para pasar los individuos de una población al espacio definido por la función
objetivo y conocer las soluciones proporcionadas por el algoritmo y el grado de
adecuación de las mismas.
•
La codificación con números reales resulta muy adecuada cuando el dominio de la
función objetivo es continuo. Trabajar en este caso con un espacio de búsqueda
codificado con números binarios implica utilizar una precisión suficiente para que
haya alguna solución codificada dentro del error permitido. Puesto que, en general,
no se conoce a priori cual es el grado de precisión requerido sería necesaria la
utilización de una gran cantidad de bits (más que los realmente necesarios puesto
que no se conoce la localización del óptimo) que permitieran alcanzar la solución,
con la consiguiente pérdida de rendimiento.
•
Mediante la codificación con números reales, ya no se hace necesario exigir que el
cardinal del espacio de búsqueda sea una potencia de dos. Efectivamente, si se
utilizan cadenas binarias de longitud l, existen exactamente 2l puntos en el espacio
de búsqueda. El problema aquí se produce cuando el dominio de la función objetivo
es de tipo discreto y contiene menos de 2l puntos. En este caso existen puntos dentro
del espacio de búsqueda que no pertenecen al dominio de la función. Una forma de
tratar estos puntos consiste en darles a este tipo de soluciones un grado de
adecuación muy bajo, pero esta solución generalmente complica mucho el
problema, y lo cierto es que no existe una forma adecuada de tratarlos.
•
Los algoritmos genéticos codificados con números reales tienen la capacidad de
explorar las funciones de variables reales de forma gradual: pequeños cambios
introducidos en las variables producen pequeños cambios en los valores dados por la
función. Esta característica permite explorar el dominio de la función objetivo con
gran precisión.
Daniel Manrique Gamo
Página 21
Computación Evolutiva: Algoritmos Genéticos
Algoritmos Genéticos
────────────────────────────────────────────────────────────────────────────────────────────
Al igual que se había desarrollado el concepto de patrón para codificaciones binarias, se
desarrolló posteriormente el concepto de patrón intervalo o esquema intervalo, similar
al dado por Wright de esquemas o patrones conectados [Wrig, 91]. Estos conceptos
permiten demostrar teóricamente que la codificación con números reales, enteros o, en
general, elevada cardinalidad, resulta más eficiente que la codificación realizada con
alfabetos de baja cardinalidad en ciertos tipos de problemas [Eshe, 93].
Supóngase, por ejemplo, que se está trabajando con cadenas de números naturales N de
longitud l de la forma c = c1 c2 ... cl, ci ∈ N. El concepto de esquema intervalo añade a la
codificación empleada la posibilidad de que aparezcan intervalos de números naturales,
denotados por Ii, en posiciones i de la cadena de la forma Ii = [ai,bi]∩N, con ai y bi ∈ N.
Se denomina esquema intervalo a todo elemento de la forma c’=c’1c’2... c’l, c’i∈{Ii}∪N.
El patrón intervalo c’ representa un conjunto de cadenas, existiendo dos casos: Si c’i ∈N
entonces todas las cadenas del conjunto toman el valor c’i en la posición i. En caso
contrario, si c’i = Ii, entonces las cadenas del conjunto pueden tomar cualquiera de los
valores del intervalo [ai,bi]∩N.
Supóngase ahora que se trabaja con cadenas c de números naturales formadas por un
único gen. En este caso los patrones intervalo serán de la forma c’ = [a,b]. Si la longitud
del intervalo es n (n = b – a +1), entonces el número de esquemas intervalo (incluyendo
todos los posibles subintervalos) que pueden ser definidos es:
Por tanto, para el caso concreto de que el gen de c tome valores concretos dentro del
intervalo [0,7], existen un total de 36 esquemas intervalo a los que podría pertenecer la
cadena c. Como ejemplos de esquemas intervalo más anchos existe uno de longitud 8:
[0,7], hay dos de longitud 7: [0,6] y [1,7]. En el extremo opuesto, tenemos que existen
ocho esquemas intervalo de longitud 1: [0,0], [1,1], ..., [7,7]. Cada uno de los valores
que pueda tomar el gen de la cadena c es miembro de como mínimo n esquemas
intervalo y pertenece como máximo a E[(n+1)2/4] esquemas intervalo (E[x] es la
función parte entera). Para el caso particular de que dicho gen pueda tomar valores
k∈[0,n-1], este valor pertenecerá a (k+1)·(n-k) esquemas intervalo. Es fácil ver también
que, dados dos valores k1 y k2 ∈ [0,n-1] con k1 < k2, tienen (k1+1)·(n-k2) esquemas
intervalo en común.
La cantidad de intervalos de cada patrón intervalo determina sus grados de libertad.
Desde un punto de vista geométrico, un esquema intervalo en el que haya dos intervalos
define un conjunto rectangular de cadenas, mientras que si existen l intervalos, el
conjunto definido tiene una forma hiperprismática de dimensión l.
El empleo del concepto de patrones intervalo cuando se trabaja con AAGG codificados
con alfabetos de alta cardinalidad permite, al igual que los esquemas definidos sobre
alfabetos de baja cardinalidad, realizar estudios sobre el comportamiento del AG a lo
Daniel Manrique Gamo
Página 22
Computación Evolutiva: Algoritmos Genéticos
Algoritmos Genéticos
────────────────────────────────────────────────────────────────────────────────────────────
largo de su evolución así como de los operadores que actúan dentro de él. Es fácil
observar que cualquier método de selección que elige con una mayor probabilidad
aquellos individuos mejor adaptados, también elegirá con mayor probabilidad aquellos
esquemas intervalo que contienen a los elementos mejor adaptados, por lo que no se
pierden los mejores esquemas intervalo. La cuestión fundamental a la hora de diseñar un
operador de cruce para individuos codificados con números reales o enteros es, por
tanto, que sea capaz de explorar y preservar los mejores patrones intervalo, aunque sin
descuidar la posibilidad de alcanzar otras zonas del espacio de búsqueda [Radc, 90],
[Mich, 96], [Ono, 97] .
2.4.
La función de evaluación
La función de evaluación, también denominada función objetivo, tiene que ser diseñada
para cada problema que se quiere resolver [Dora, 99]. Dado un cromosoma concreto, la
función de evaluación devuelve un valor de ajuste o adaptación, que es proporcional a la
habilidad del individuo que representa el cromosoma.
A la hora de optimizar una función mediante algoritmos genéticos, ésta puede ser
utilizada directamente como función de evaluación, aunque en ciertos casos es posible
obtener mejores resultados cuando se emplea una transformación o una aproximación
de la misma. La elección de una adecuada función objetivo, junto con la codificación
utilizada, son dos aspectos que resultan cruciales en el comportamiento de los AAGG.
Idealmente, interesaría construir funciones objetivo con ciertas regularidades, es decir,
funciones objetivo que verifiquen que para dos individuos que se encuentren cercanos
en el espacio de búsqueda (recordemos que el espacio de búsqueda es un subconjunto
del dominio de la función objetivo definido por la función Ω(Al)), sus respectivos
valores en la función objetivo sean también parecidos. Además, la existencia de gran
cantidad de óptimos locales en la función objetivo, o el hecho de que el óptimo global
se encuentre muy aislado suponen dificultades añadidas en el comportamiento de los
AAGG.
En muchos problemas de optimización combinatoria, donde existen gran cantidad de
restricciones, buena parte de los puntos del espacio de búsqueda representan individuos
no válidos, para los cuales no hay un valor definido de adaptación. Este hecho supone
dificultades a la hora de emplear los AAGG por lo que se han propuesto varias
soluciones [Larr, 96].
La primera es la absolutista, donde aquellos individuos que no verifican las condiciones
necesarias para ser válidos no son considerados como tales, y se siguen efectuado cruces
y mutaciones sobre ellos hasta conseguir que se les pueda asignar un valor por la
función objetivo. Una posible variante consiste en dar un valor fijo a los individuos no
válidos que represente poca adaptación, con el fin de que no sean elegidos para
reproducción, cruce o mutación, y desaparezcan en la siguiente generación. Asimismo,
existe la posibilidad de reconstruir aquellos individuos que no verifican las restricciones
mediante la aplicación de un operador denominado reparador. Otra solución es
Daniel Manrique Gamo
Página 23
Computación Evolutiva: Algoritmos Genéticos
Algoritmos Genéticos
────────────────────────────────────────────────────────────────────────────────────────────
establecer un criterio de penalizaciones en la función objetivo. La idea general consiste
en dividir la función objetivo por una cantidad (la penalización) que guarda relación con
aquellas características del individuo que le hacen no ser válido. Dicha cantidad puede
tener en cuenta el número de características violadas, o bien el denominado costo
esperado de reconstrucción, es decir, un coste asociado a la conversión de dicho
individuo en otro que sea válido.
Hay ocasiones en las que se emplea una evaluación aproximada de la función objetivo,
sobre todo cuando la computación de la misma es muy costosa. La obtención de una
aproximación al valor de adaptación para un determinado individuo puede resultar
mejor que su evaluación exacta siempre y cuando se obtenga una gran velocidad de
cálculo como contrapartida.
En la elección de una adecuada función objetivo, es necesario, además, que el intervalo
de posibles valores de adaptación que proporciona sea el adecuado. Si este intervalo es
demasiado amplio, es posible que se dé el caso de que unos pocos individuos dominen
sobre todo el resto de la población. Si, por el contrario, dicho intervalo es demasiado
estrecho, se produce una convergencia muy lenta hacia el valor óptimo.
Por último, hay que resaltar que existe la posibilidad de modificar el valor de la función
objetivo en cada individuo de tal manera que individuos que estén muy cercanos entre
sí, se devalúen con objeto de que la población gane en diversidad [Gold, 87]. Dada una
codificación binaria del problema, si se denota por d(Ij,Ii) la distancia Hamming entre
los individuos Ij y Ii en un instante t, y por K un valor real positivo fijo, se puede definir
la siguiente función:
h [d (Ij,Ii)] =
K – d (Ij,Ii), si d (Ij,Ii) < K
0,
si d (Ij,Ii) ≥ K
A partir de la función h se define, para cada individuo Ij de la población, el valor de
devaluación σj de la función objetivo de la siguiente manera:
σj =
h [d (Ij,Ii)]
Por tanto utilizando este método, cualquier función objetivo f que hace corresponder a
todo individuo Ij de la población un valor de medida de su adaptación al problema f(Ij),
queda modificada de la siguiente forma:
f*(Ij) = f(Ij) / σj
De esta manera, aquellos individuos cuyas codificaciones sean parecidas (dependiendo
del parámetro K) verán devaluadas sus adaptaciones y, por tanto, se reducirá la
probabilidad de ser seleccionados como padres, promoviendo la existencia de
individuos que se encuentren más aislados, por lo que se produce un aumento de la
diversidad genética.
Daniel Manrique Gamo
Página 24
Computación Evolutiva: Algoritmos Genéticos
Algoritmos Genéticos
────────────────────────────────────────────────────────────────────────────────────────────
El mecanismo de devaluación de la función objetivo descrito, puede ser también
aplicado a otro tipo de codificaciones simplemente definiendo una distancia d(Ij,Ii) entre
dos individuos que dé una medida de su parecido.
2.5.
Convergencia
Una vez conocido y planteado el problema de optimización con algoritmos genéticos, la
pregunta inmediata es hasta qué punto puede esperarse la obtención de la solución
buscada. La respuesta a esta pregunta es un claro indicador de la bondad del método. En
aquellos casos en los que se pueda esperar convergencia del algoritmo hacia el óptimo u
óptimos de la función objetivo, se puede comenzar a plantear otras cuestiones, tales
como la velocidad de convergencia, o el error cometido por el método.
Si el algoritmo genético ha sido implementado correctamente, la población evolucionará
a través de las generaciones de tal forma que la adaptación del mejor y la media de
todos los individuos en cada generación se incrementará hacia el óptimo global. Este
proceso de incremento uniforme del valor de adaptación es lo que se denomina
convergencia. Se dice que un gen converge cuando el 95% de la población comparte el
mismo valor para ese determinado gen [Dejo, 75], o bien que todos los valores que toma
ese gen en todos los individuos de la población sufren variaciones de no más del 5%
para el caso de alfabetos infinitos. Asimismo, se dice que la población converge cuando
todos los genes han convergido.
Hay que tener en cuenta que tanto la convergencia de los AAGG, como su velocidad de
convergencia y error cometido depende en gran medida de ciertos parámetros como el
tamaño de la población, frecuencia de aplicación de los diferentes operadores, además
de la elección de los diferentes operadores.
2.5.1.
Medidas de convergencia
Como ejemplo de la preocupación de algunos investigadores respecto al tema de la
buena convergencia de los AAGG, cabe destacar los estudios de De Jong [Dejo, 75], el
cual definió dos medidas de convergencia que aún hoy siguen vigentes: la medida fuera
de línea (offline) y la medida en línea (online).
La medida fuera de línea mide la capacidad de convergencia del algoritmo. En cada
generación T, se mide la media entre todos los mejores individuos de las generaciones
anteriores, incluida la actual:
m* (T) =
f (I* (t))
donde f (I* (t)) es el valor de la función objetivo para el individuo más cercano al óptimo
en la generación t. En cada generación t, la medida fuera de línea se puede interpretar
como un indicador del progreso del algoritmo. Cuando transcurre cierto número de
generaciones, el resultado de dicha medida puede aproximarse o no al óptimo buscado.
La velocidad con que esto ocurre indica la capacidad del algoritmo para estabilizarse en
Daniel Manrique Gamo
Página 25
Computación Evolutiva: Algoritmos Genéticos
Algoritmos Genéticos
────────────────────────────────────────────────────────────────────────────────────────────
la solución. De este modo, la medida puede ser utilizada para establecer algún criterio
de parada. Por ejemplo, cuando la diferencia entre resultados obtenidos para
generaciones consecutivas es suficientemente próximo a cero, según cotas establecidas
a priori.
La medida en línea se define como la media, para la función objetivo, obtenida por el
algoritmo hasta el momento de la evaluación:
m (T) =
F(t)
donde F(t) es la media de los valores de la función objetivo de todos los individuos
existentes en la generación t.
Para ambas medidas, la diferencia entre los valores obtenidos en generaciones
consecutivas proporciona información sobre la última de éstas. La comparación entre la
medida en línea y la medida fuera de línea para cada generación, puede considerarse
como un indicador del estado en el cual se encuentra el algoritmo. En efecto, al
comienzo existe una mayor diversidad genética en la población, y la media puede diferir
considerablemente del individuo mejor adaptado. Pero, cuando el algoritmo avanza
hacia la solución, los individuos de la población empiezan a aproximarse al mejor valor
obtenido, sea o no la solución óptima. Entonces, la media y el óptimo obtenidos en cada
generación se aproximan entre sí.
La utilización de estas medidas a lo largo del proceso de evolución del algoritmo
permite advertir problemas de convergencia. Si se tiene poco cambio en línea entre
generaciones consecutivas, se puede intuir la poca renovación de la población entre dos
instantes de tiempo, ya que la media alcanzada es parecida. Por tanto, si ese valor está
muy alejado de la solución final, se está dando un problema de convergencia hacia un
subóptimo. Si, por otro lado, la variación de esta medida con respecto a la medida fuera
de línea es grande, y no mejora significativamente con el paso del tiempo, ello indica
que la media alcanzada en cada generación dista mucho del mejor individuo que se tiene
hasta el momento. Por tanto se puede deducir que el algoritmo actúa muy lentamente
sobre el problema que se está tratando, dando lugar a un proceso de convergencia muy
lento.
Estudios posteriores tratan de obtener una medida de la diversidad genética de la
población en un instante determinado con el fin de conocer el proceso de evolución
actual. Si la medida de la diversidad genética indica un valor muy bajo, significa que la
población está convergiendo, al contrario que si la diversidad genética es alta. En este
sentido, se ha utilizado la desviación típica de cada uno de los genes de los individuos
medidos en toda la población. Una desviación típica elevada indica mucha diversidad
genética. Por el contrario, si la desviación típica es muy baja, significa que la población
está convergiendo [Roch, 99].
Daniel Manrique Gamo
Página 26
Computación Evolutiva: Algoritmos Genéticos
Algoritmos Genéticos
────────────────────────────────────────────────────────────────────────────────────────────
Otros trabajos utilizan una medida de la diversidad genética incluida dentro del
operador de cruce con el fin de variar su comportamiento de acuerdo a ésta. Esto es lo
que ocurre en el caso del operador de cruce gaussiano [Ono, 97]. Aquí la medida de la
diversidad genética se obtiene a partir de una definición de la distancia existente entre
los tres padres que se van a cruzar elegidos mediante algún mecanismo de selección. A
partir de esta medida se construye una distribución normal de donde se obtienen los dos
hijos.
2.6.
Operadores genéticos
Entre los operadores genéticos, los considerados fundamentales por la mayoría de los
estudiosos del tema [Holl, 75], [Gold, 89], son los de reproducción, mutación y cruce.
Cada uno de ellos desarrolla una labor específica, bien diferenciada de las de los demás,
como se verá seguidamente.
2.6.1.
Operadores de reproducción
Este operador selecciona, entre los diferentes puntos de la población, aquellos que van a
tener descendencia, para lo cual se copian primero a un lugar intermedio denominado
lugar de apareamiento (matting pool). Los individuos más adaptados tienen más
probabilidades de ser seleccionados, incluso varias veces si esto se permite. Por el
contrario, los individuos menos adaptados tendrán una probabilidad muy baja de poder
producir descendencia.
El comportamiento de los AAGG depende mucho de cómo se seleccionen los
individuos para producir la descendencia. Existe una gran variedad de métodos de
selección, entre los que se destacan los siguientes por ser los más comúnmente
empleados:
1. La función de selección más utilizada, que es la denominada función de selección
proporcional a la función objetivo, en la cual cada individuo tiene una probabilidad
de ser seleccionado que es proporcional a su valor en la función objetivo [Barr, 91].
Denotando por pjprop la probabilidad de que el individuo Ij sea seleccionado de entre
una población de λ individuos y por f(Ij) el valor de la función objetivo, se tiene
que:
pjprop = f (Ij)
f (Ij)
Esta función de selección es invariante ante un cambio de escala, pero no ante una
traslación. El problema que se plantea con la aplicación de este método de selección
es que la existencia de un individuo super-adaptado provoca que únicamente él
mismo sea seleccionado, ya que tendría un valor de pjprop muy elevado, mientras que
el resto de individuos lo tendrían muy bajo. Este hecho provocaría la convergencia
del algoritmo genético hacia un óptimo local.
Daniel Manrique Gamo
Página 27
Computación Evolutiva: Algoritmos Genéticos
Algoritmos Genéticos
────────────────────────────────────────────────────────────────────────────────────────────
Una de las maneras de solucionar este problema es mediante la utilización del
mecanismo de selección proporcional al orden del individuo [Davi, 89], con lo cual
se consigue un reparto más uniforme de la probabilidad de selección, tal y como se
ilustra en la figura 3.3. Este método utiliza el concepto de orden de un individuo Ij,
denotado por Orden[f(Ij)], según el cual, una vez ordenados los λ individuos de la
población de menor a mayor adaptación, asigna un valor de 1 a λ según la posición
del individuo Ij en la lista ordenada. Así, el orden del peor individuo es el valor 1,
mientras que el orden del mejor individuo es λ. Para la selección de los individuos,
se calcula la probabilidad de que el individuo Ij sea seleccionado cuando la selección
se efectúa proporcionalmente a la posición que ocupa el individuo en la lista
ordenada. Esta probabilidad se denota por pjorden y se calcula según la siguiente
fórmula:
pjorden = Orden [f (Ij) ]
λ (λ+1) / 2
El factor λ(λ+1)/2 constituye la constante de normalización. La propiedad
fundamental de la selección basada en el orden es invariante no sólo a cambios de
escala, sino también a traslaciones.
Figura 3.3. Esquemas de selección de individuos proporcional a la función objetivo (izquierda)
y proporcional al orden de los individuos (derecha).
Otro posible refinamiento del modelo de selección proporcional, es el modelo de
selección del valor esperado, el cual actúa de la manera siguiente: para cada
individuo Ij, se introduce un contador, inicializado en f (Ij) / F(t), donde F(t) denota
la media de la función objetivo en la generación t. Cada vez que el individuo Ij es
seleccionado, dicho contador decrece en una cantidad c, con c∈(0.5,1). El individuo
en cuestión dejará de poder ser seleccionado cuando su contador sea negativo.
2. El muestreo estocástico con reemplazamiento del resto [Brin, 91], que
empíricamente ha proporcionado muy buenos resultados. Según este método de
selección, cada individuo es seleccionado un número de veces que coincide con la
parte entera del número esperado de ocurrencias de dicho individuo, compitiendo el
Daniel Manrique Gamo
Página 28
Computación Evolutiva: Algoritmos Genéticos
Algoritmos Genéticos
────────────────────────────────────────────────────────────────────────────────────────────
resto de individuos por los restos de esta división. Si se nota por n(Ij) el número de
veces que el individuo Ij es seleccionado, se tiene que:
n(Ij) = n1(Ij) + n2(Ij)
donde n1(Ij) = E[f (Ij) / F(t)], y n2(Ij) corresponde a la componente aleatoria que
resulta de muestrear sobre los λ -
E[f (Ij) / F(t)] restantes individuos, siendo el
muestreo proporcional a la función objetivo de cada individuo.
3. El muestreo universal estocástico o método de la ruleta [Bake, 87] emplea un
círculo (la ruleta) dividido en sectores circulares que son proporcionales a la función
objetivo. De esta forma, los sectores correspondientes a individuos mejor adaptados
ocupan un área mayor dentro de la ruleta, mientras que los peor adaptados se
corresponden con sectores circulares con una superficie muy pequeña. Los
individuos son seleccionados a partir de marcadores igualmente espaciados, siendo
la colocación del primero de ellos aleatoria. La figura 3.4 representa un ejemplo de
este tipo de métodos en el que el individuo I1 (el más adaptado) se escoge dos veces,
los individuos I3 e I4 se escogen una vez cada uno, mientras que el individuo I2 (el
menos adaptado) no es seleccionado.
Figura 3.4: Método de la ruleta para la selección de individuos.
4. La selección por torneo [Brin, 91], constituye un procedimiento de selección muy
extendido y en el cual, la idea consiste en escoger al azar tantos individuos de la
población como se haya prefijado el tamaño del torneo (con o sin reemplazamiento),
se selecciona el mejor individuo de los que constituyen el grupo de torneo, y se
repite el proceso hasta alcanzar el número de individuos seleccionados deseado.
Habitualmente, el tamaño del torneo es de dos, y generalmente se utiliza una versión
Daniel Manrique Gamo
Página 29
Computación Evolutiva: Algoritmos Genéticos
Algoritmos Genéticos
────────────────────────────────────────────────────────────────────────────────────────────
probabilística en la cual se permite la selección de individuos sin que
necesariamente sean los mejores de los diferentes torneos que tienen lugar.
5. El método de ponderación explícita de la adaptación (explicit fitness remapping)
toma el valor dado por la función objetivo para cada individuo como estimador del
número de veces que puede ser seleccionado. Más concretamente, el número de
veces n(Ij) que un individuo Ij puede ser seleccionado es n(Ij) = f (Ij) / F(t) . Por ello,
la media del número de veces que cada individuo de la población puede ser
seleccionado es uno. Este tipo de selección reparte las posibilidades de selección de
acuerdo al grado de adaptación de cada individuo, y se corresponde con la versión
original de las teorías de Holland. Sin embargo, este mecanismo de selección tiene
el peligro de que el algoritmo genético caiga en mínimos locales, debido a que
únicamente se le da la oportunidad de producir descendencia a los individuos mejor
adaptados, produciéndose una pérdida de la diversidad genética. Para evitar este
problema existen algunas variantes de este método [Bake, 87] como el método de
cambio de escala de la adaptación y el método de cambio de escala mediante
ventanas.
Con el método de cambio de escala de la adaptación, el número máximo de veces
que un individuo puede ser seleccionado se fija a un determinado valor que
típicamente suele ser dos. El método funciona de manera similar al anterior. Sin
embargo, en este caso se aplica una escala a los valores de adaptación de los
individuos de la población. Esta escala se calcula restando al valor de la adaptación
del mejor individuo el número máximo de selecciones repetidas permitido, y
dividiendo el resultado por la adaptación media de la población. Este procedimiento
tiende a comprimir el intervalo de valores de la función objetivo, por lo que se da el
problema de una convergencia muy lenta.
El método de cambio de escala mediante ventanas es también muy parecido al
anterior, pero en este caso la cantidad que se resta es el valor mínimo de la
adaptación de los individuos aparecidos en las últimas n generaciones, siendo n
típicamente diez. Este método se encuentra implementado en [Gref, 84].
Estas dos últimas técnicas, cambio de escala de la adaptación y cambio de escala
mediante ventanas, tienen el problema de que el grado de compresión del intervalo
de valores de la función objetivo depende de un único individuo, el más adaptado, o
el peor. El rendimiento de estas técnicas sufrirá mucho si estos individuos son muy
diferentes al resto de la población.
Una vez vistos los procedimientos de selección más frecuentemente utilizados, se
podría realizar una clasificación de los mismos atendiendo a diferentes criterios.
Daniel Manrique Gamo
Página 30
Computación Evolutiva: Algoritmos Genéticos
Algoritmos Genéticos
────────────────────────────────────────────────────────────────────────────────────────────
Atendiendo a si se modifican o no las probabilidades de selección de los individuos de
una generación a otra, se podría realizar una primera clasificación en métodos de
selección dinámica y métodos de selección estática. En los métodos de selección
dinámica, las probabilidades de selección varían de generación en generación como, por
ejemplo, la selección proporcional a la función objetivo. Los métodos de selección
estática mantienen las probabilidades de selección constantes como, por ejemplo, en el
método de selección basada en el orden de los individuos.
Por otro lado, si se asegura que todos los individuos tienen asignada una probabilidad de
selección distinta de cero, el método de selección se engloba dentro de los métodos
preservativos. En caso contrario, se denominan métodos extintivos.
En [Gold, 91b] se comparan algunos de los diferentes métodos de selección expuestos
en este apartado, concluyendo que todos ellos (excepto la selección proporcional a la
función objetivo) ofrecen un rendimiento similar si se utilizan los parámetros
adecuados, por lo que no existe un método definitivo a utilizar en todos los casos.
Como se ha podido comprobar, todas las diferentes formas de selección tienen en
común que tratan de elegir con mayor probabilidad aquellos individuos más adaptados,
es decir, aquellos puntos que se encuentren más cerca del valor óptimo buscado, para lo
cual, de una u otra manera, se emplea el valor dado por la función objetivo f(Ij). De este
modo, se conforma el hecho de que la actuación del operador de reproducción está
inspirada en los procesos de selección natural, de forma que los individuos más fuertes
son los que tienen más posibilidades para sobrevivir.
2.6.2.
Operadores de mutación
El operador de mutación, también actúa según cierta probabilidad pm, característica de
cada problema concreto. Cuando una cadena resulta afectada por el operador, se
selecciona aleatoriamente un lugar de mutación. Para ello, todos los lugares posibles de
la cadena son equiprobables. El valor correspondiente a dicho lugar cambia por otro de
los posibles, eligiendo éste, también aleatoriamente, entre todos los del alfabeto que se
esté utilizando. La mutación se considera, por ello, un operador genético básico, que
proporciona un pequeño elemento de aleatoriedad en los individuos de la población.
En este caso, sólo se puede hablar de un progenitor y un descendiente. Elegida una
cadena, correspondiente a un punto en el espacio de búsqueda, el producto de aplicar
este operador será otra cadena, no necesariamente perteneciente a la población actual.
De este modo el operador de mutación ayuda a renovar la población, aunque lo hace de
forma aparentemente arbitraria ya que el resultado, la cadena descendiente, nada tiene
que ver con su progenitora.
Como ilustración del resultado de aplicar este operador, supóngase código binario,
donde cada cadena se obtiene como la expresión en binario del correspondiente punto
del espacio de búsqueda de los números naturales positivos. Suponiendo, además,
longitudes de cadena igual a cinco, el individuo 01101 es la codificación de 13. Si esta
Daniel Manrique Gamo
Página 31
Computación Evolutiva: Algoritmos Genéticos
Algoritmos Genéticos
────────────────────────────────────────────────────────────────────────────────────────────
cadena resultara afectada por la mutación, y el lugar de mutación fuese 3, entonces se
obtendría el descendiente 01001, codificación de 9. Sin embargo, si el lugar de
mutación es 1, la cadena descendiente es 11101, codificación de 29. Por tanto, según el
lugar de mutación, se obtienen puntos muy diferentes del espacio de búsqueda. En este
sentido, el operador de mutación encuentra su más amplia justificación como método
para obtener nuevos puntos en los que recomenzar la búsqueda, evitando de esta forma
la pérdida de diversidad genética en la población, lo cual, como se verá más adelante,
tiene implicaciones directas en el proceso de convergencia del algoritmo genético.
Tanto es así que, según ciertos estudios, el operador de mutación va ganando en
importancia a medida que la población de individuos va convergiendo [Davi, 91].
Según lo expuesto anteriormente se observa que la elección de una adecuada
probabilidad de mutación es un elemento crucial. Si la probabilidad de mutación es muy
elevada, el algoritmo genético se convierte en una búsqueda aleatoria; mientras que si se
elige una probabilidad de mutación muy pequeña, entonces la pérdida de diversidad
genética producida cuando los individuos de la población están convergiendo, puede
llevar al algoritmo a un subóptimo. La determinación de la probabilidad de mutación es,
de hecho, mucho más crucial que la probabilidad de cruce [Scha, 89].
La búsqueda del valor óptimo para la probabilidad de mutación, es una cuestión que ha
sido motivo de muchos trabajos de investigación. Así, una de las recomendaciones es la
utilización de una probabilidad de mutación de 1/l (l es la longitud de la cadena)
[JONG75]. Otros estudios, a partir de ciertos resultados experimentales, obtuvieron que
la mejor probabilidad de mutación era proporcional al tamaño y a la longitud según la
fórmula
[Scha, 89].
Si bien en la mayoría de las implementaciones de algoritmos genéticos se asume que la
probabilidad de mutación permanece constante, algunos estudios realizados revelan que
se obtienen mejores resultados modificando esta probabilidad a lo largo del proceso de
convergencia del algoritmo [Ackl, 87], [Bram, 91], [Foga, 89], [Mich, 91], lo cual ha
sido corroborado en algunos estudios realizados más recientemente [Roch, 99], donde a
intervalos regulares en el tiempo, se obtiene la diversidad genética existente en la
población a través del cálculo de la desviación típica. Si el valor obtenido es menor que
un cierto límite predefinido, lo cual significa que la población está convergiendo,
entonces se incrementa la probabilidad de mutación. Si, por el contrario, el valor
calculado de la desviación típica como medida de la diversidad genética de la población
es mayor que este límite, entonces se reduce la probabilidad de mutación.
2.6.3.
Operadores de cruce con alfabeto finito
El trabajo con algoritmos genéticos cuya codificación de los puntos de la función a
optimizar se realiza empleando un alfabeto finito se puede modelizar, como ya se ha
indicado anteriormente, suponiendo que se emplea un alfabeto A de cardinal m.
Asimismo, se supone que la cadena c1, c2, ..., cl corresponde a la codificación de un
Daniel Manrique Gamo
Página 32
Computación Evolutiva: Algoritmos Genéticos
Algoritmos Genéticos
────────────────────────────────────────────────────────────────────────────────────────────
punto del espacio de búsqueda, donde ck∈A, para cada k∈{1,2,...,l}, utilizando cadenas
de longitud l. El operador de cruce actúa sobre cadenas correspondientes a la población
actual, generalmente dos, denominadas cadenas progenitoras o padres. Actuando sobre
las cadenas progenitoras, un operador de cruce produce generalmente otras dos cadenas
que corresponden a nuevos puntos del espacio de búsqueda, denominadas cadenas
descendientes. Este operador afecta a cada par de puntos de la población con
probabilidad pc, siendo el valor de pc característico de cada problema concreto.
A continuación se describen algunos de los operadores de cruce más importantes:
1. Operador de cruce ordinario u operador basado en un punto [Larr, 96]. Toma dos
padres seleccionados y corta sus cadenas en un punto elegido al azar, denominado
lugar de cruce, de entre los l posibles. Con esto se determinan dos subcadenas en
cada una de las cadenas del par. Si el lugar de cruce resulta ser k, y las cadenas que
se cruzan son a1, a2, ..., ak, ak+1, ..., al y b1, b2, ..., bk, bk+1, ..., bl, las subcadenas
determinas por el cruce tienen longitud k y l-k respectivamente, y están constituidas
por los caracteres correspondientes a las k primeras y l-k últimas posiciones en
ambos casos. Estas cuatro subcadenas serán utilizadas para formar las dos nuevas
cadenas que forman la descendencia. El primer descendiente se forma concatenando
la subcadena de longitud k de uno de los padres con la cadena de longitud l-k del
otro padre, y las otras dos subcadenas conducen al segundo descendiente. Por tanto,
el resultado del aplicar este operador de cruce está dado por las cadenas a1, a2, ..., ak,
bk+1, ..., bl y b1, b2, ..., bk, ak+1, ..., al. De esta forma ambos descendientes heredan
genes de cada uno de los padres.
2. Operador de cruce basado en dos puntos. Se han realizado diferentes
investigaciones en cuanto al comportamiento del operador de cruce basado en
múltiples puntos, concluyéndose que el basado en dos puntos representa una mejora
respecto al operador basado en uno solo. Sin embargo, el añadir más puntos de
cruce no beneficia al comportamiento del algoritmo [Dejo, 75]. Este operador actúa
de la siguiente forma: dadas dos cadenas a cruzar a1, a2, ..., ak, ak+1, ..., ak’, ak’+1, ..., al
y b1, b2, ..., bk, bk+1, ..., bk’, bk’+1, ..., bl, se determinan aleatoriamente, de entre los l
posibles, los dos lugares de cruce k y k’, y se intercambian las subcadenas ak+1, ...,
ak’ y bk+1, ..., bk’, quedando las cadenas descendientes a1, a2, ..., ak, bk+1, ..., bk’, ak’+1,
..., al y b1, b2, ..., bk, ak+1, ..., ak’, bk’+1, ..., bl.
3. Operador de cruce uniforme. Se basa en la definición de una máscara de cruce
consistente en una cadena de bits aleatoria de longitud l. El operador genera dos
descendientes para cada par de padres de la siguiente forma: dadas dos cadenas
padres a1, a2, ..., ai, ..., al y b1, b2, ...,bi, ..., bl, la posición i de la cadena del primer
descendiente será ai si existe el valor 0 en la posición i de la máscara de cruce; y
será bi en caso contrario. Para el caso del segundo descendiente se aplica la máscara
de forma inversa [Sysw, 91]. El término de cruce uniforme viene del hecho de que
Daniel Manrique Gamo
Página 33
Computación Evolutiva: Algoritmos Genéticos
Algoritmos Genéticos
────────────────────────────────────────────────────────────────────────────────────────────
la obtención de la máscara de cruce se realiza de forma aleatoria dando la misma
probabilidad a que en cada una de las posiciones de la máscara haya un 1 ó un 0.
El operador de cruce uniforme puede emular el comportamiento de los operadores
de cruce basados en uno o en dos puntos. Así, elegido el lugar de cruce en la
posición k para el cruce de un solo punto, se podría utilizar una máscara formada por
la concatenación de una cadena de k ceros con otra de l-k unos. En el caso del cruce
basado en dos puntos, elegidos k y k’ como lugares de cruce, la máscara se compone
de la concatenación de una cadena de k ceros, seguida de una cadena de k’-k unos y
finalmente, una cadena de l-k’ ceros.
4. Operador de cruce basado en la función objetivo. Este operador es una
modificación del cruce uniforme. El valor de la función de adaptación de cada padre
es tenido en cuenta a la hora de generar la máscara de cruce, de tal manera que
cuanto mayor sea la adaptación de un individuo, sea más probable heredar sus
características [Larr, 96]. En este caso, la máscara de cruce se interpreta como una
muestra aleatoria de ceros y unos de tamaño l que sigue una distribución de
Bernouilli de parámetro:
p = f (Ii)
f (Ii) + f (Ij),
donde Ii e Ij son los padres seleccionados para el cruce y f es la función objetivo.
5. Operador de cruce basado en el enfriamiento simulado. Se basa en la definición de
un umbral de energía θc y una temperatura T, las cuales influencian la manera en la
que se escogen los caracteres dentro de la cadena que va a pasar a formar parte de la
descendencia [Sira, 87]. Según este operador, el bit (i+1)-ésimo se tomará del padre
opuesto del bit i-ésimo, con probabilidad e-θc/T, donde el parámetro de temperatura T
irá decreciendo lentamente por medio de un programa de enfriamiento. Con altas
temperaturas, e-θc/T toma valores próximos a 1, y el comportamiento se asemeja al
operador de cruce uniforme. Por tanto, los bits se van cogiendo alternativamente de
cada padre. Por otra parte, cuando el valor de temperatura se acerca a cero, el hijo
resultante coincide prácticamente con alguno de los padres, pues la probabilidad de
cambiar de progenitor en cada posición i es e-θc/ T, valor muy próximo a cero.
6. Operador de cruce generalizado. Parte de dos cadenas padres codificadas con un
alfabeto binario para obtener dos nuevas cadenas descendientes de las anteriores
[Barr, 91]. Sea S = {0,1}l el conjunto de todas las posibles cadenas de longitud l.
Sea g: S → {0, 1, ..., 2l-1} la función de transformación que permite, a partir de una
cadena binaria, obtener su decodificación usual como número entero. Puesto que g
es una función biyectiva, se puede definir el conjunto entero equivalente como el
conjunto g(S). De esta forma es posible trabajar con el espacio de búsqueda o el
conjunto entero equivalente indistintamente.
Daniel Manrique Gamo
Página 34
Computación Evolutiva: Algoritmos Genéticos
Algoritmos Genéticos
────────────────────────────────────────────────────────────────────────────────────────────
Dadas dos cadenas binarias a y b ∈ S, los descendientes mediante el operador de
cruce generalizado serán los puntos a’ y b’ tales que:
a’∈ g-1 ( [g(a∧b) , g (a∨b)] )
;
b’ = g-1 ( g(a) + g(b) – g(a’) )
siendo ∧ el operador lógico and bit a bit, y ∨ el operador lógico or bit a bit.
A la cadena a∧b se la denomina cadena mínima, mientras que a la cadena a∨b se la
denomina cadena máxima ya que siempre se cumple que si g(a)≤g(b) entonces
g(a∧b) ≤ g(a) ≤ g(b) ≤ g(a∨b). Al intervalo [g(a∧b),g(a∨b)] se le denomina intervalo
de cruce ya que siempre se cumple que g(a’) y g(b’)∈ [g(a∧b),g(a∨b)]. La figura 3.5
localiza de forma esquemática los progenitores y descendientes dentro del intervalo
de cruce.
Figura 3.5: Progenitores y descendientes en el intervalo de cruce.
En otras investigaciones se han realizado modificaciones al operador de cruce
específicas para resolver, por ejemplo, el problema del viajante que se basan en el
orden de los genes. En este problema, no se cruzan los valores de los genes, sino su
orden dentro de la cadena, ya que cada gen representaría una ciudad, y el
cromosoma completo, el recorrido que se ha de llevar a cabo [Sysw, 91], [Davi, 91],
[Star, 91], [Muhl, 91].
Convergencia con codificación binaria
El modelo que Holland estableció para los algoritmos genéticos, y que debía resolver
los problemas de convergencia [Holl, 75], presenta ciertos problemas en la práctica, ya
que estableció las siguientes simplificaciones: la población debería ser infinita, la
función de evaluación debe reflejar exactamente el grado de utilidad de una solución y
que los genes dentro de un cromosoma no deben interactuar entre sí significativamente
[Dora, 99].
Si bien es posible satisfacer las dos últimas premisas, aunque no suele ser así cuando se
tratan problemas del mundo real, sí que es cierto que una población nunca puede ser
infinita, ni siquiera se puede disponer de un gran número de individuos en la población
para que sea computacionalmente abordable. Debido a esta causa, el rendimiento de un
AG siempre está sujeto a errores estocásticos. Los miembros de una población siempre
convergirán a algún punto del espacio de soluciones debido a la acumulación de errores
estocásticos. Si la presencia de un determinado gen en una población finita se
incrementa a lo largo de sucesivas generaciones, entonces se puede extender a todos sus
Daniel Manrique Gamo
Página 35
Computación Evolutiva: Algoritmos Genéticos
Algoritmos Genéticos
────────────────────────────────────────────────────────────────────────────────────────────
individuos. En tal caso, el valor de dicho gen queda fijo (salvo mutaciones), ya que el
cruce no puede producir nuevos valores.
Se ha puesto de manifiesto, al menos de forma empírica, que el tamaño de la población
afecta directamente en el comportamiento del AG [Gold, 91b]. En general, los
problemas de convergencia de los AAGG suelen verse atenuados, utilizando tamaños de
población mayores. Esto es debido a que la renovación de la población es mayor, y se
tiene acceso a un mayor número de puntos dentro del intervalo de búsqueda. Por tanto,
la selección se efectúa entre una mayor cantidad de individuos a la vez. Cuando, por el
contrario, el tamaño de la población es excesivamente pequeño, el algoritmo puede
conducirse rápidamente hacia puntos más distantes de las soluciones buscadas. Se
observa también, sin embargo, que existe un cierto tamaño de la población, a partir del
cual el rendimiento baja considerablemente. Efectivamente, si el tamaño de la población
es excesivamente grande, el número de generaciones necesarias para seguir avanzando
hacia el óptimo es muy elevado, por lo que el proceso de convergencia se hace muy
lento [Barr, 91].
Retomando de nuevo los trabajos de Holland, El teorema de Holland predice los
patrones con mayor probabilidad de sobrevivir son aquellos de menor orden y longitud.
Esto supone un inconveniente, ya que es posible que el óptimo se adapte a un patrón de
orden o longitud elevados y que, por tanto, no sería deseable que se destruyese.
A la vista de tales resultados, se han realizado numerosos estudios acerca de qué
operadores de cruce (ver la sección titulada operadores de cruce con alfabeto finito)
pueden paliar estas dificultades. Inicialmente se apostó principalmente por el operador
de cruce uniforme porque los patrones de un cierto orden tienen la misma probabilidad
de ser divididos, independientemente de su longitud [Sysw, 89]. Otra ventaja del cruce
uniforme es que el ordenamiento de los genes es irrelevante, lo cual significa que las
operaciones de reordenamiento, como la inversión, son innecesarias y no hay que
preocuparse de colocar los genes de forma que se puedan desarrollar buenos bloques
constructivos, al contrario que en otros operadores de cruce como el basado en dos
puntos [Beas, 93].
Eshelman [Eshe, 89] realizó una comparación en profundidad de los operadores de
cruce ordinario, basado en dos puntos y uniforme. Estos operadores fueron analizados
desde un punto de vista empírico aplicándolos a diferentes tipos de problemas diseñados
a tal fin. De estas pruebas, no se obtuvo ningún ganador claro, obteniendo unas
diferencias máximas del 20% en rendimiento. Las conclusiones de este trabajo fueron
que no se debe de tener una excesiva preocupación a la hora de elegir el método de
cruce.
Existen otros trabajos muy críticos con el operador de cruce uniforme [Spea, 91]. Sus
análisis teóricos dieron como resultado que, en general, el cruce con uno o dos puntos
son los operadores óptimos. Sin embargo comentan que el cruce basado en dos puntos
funciona peor cuando el algoritmo está convergiendo casi completamente.
Daniel Manrique Gamo
Página 36
Computación Evolutiva: Algoritmos Genéticos
Algoritmos Genéticos
────────────────────────────────────────────────────────────────────────────────────────────
A la vista de todas las conclusiones anteriores que se basan en el orden y longitud de los
patrones que van apareciendo en el proceso de evolución de un AG, cabe preguntarse si
es posible la existencia de problemas donde el óptimo buscado no se ajuste a los
mejores patrones, entendiendo que éstos son los que tienen mayor probabilidad de
sobrevivir tras cada generación. La respuesta a tal pregunta es afirmativa: los problemas
paradójicos. Por tanto, ante uno de tales problemas se puede esperar que el algoritmo se
desvíe de la solución buscada.
Para el análisis de los problemas paradójicos, se introdujo el concepto de funciones de
Walsh [Gold, 89c], [Gold, 89d], [Gold, 89e]. Las funciones de Walsh permiten
aproximar cualquier función como combinación de una base de funciones denominada
monomios de Walsh. La transformada inversa de Walsh, para cada aproximación, indica
el tipo de problema con el que se enfrenta el algoritmo, pudiendo predecirse, de este
modo, la posibilidad de llegar a obtener los resultados deseados tras su aplicación. Los
estudios teóricos posteriores, confirmados mediante simulaciones realizadas con
funciones de prueba, revelan que cuando todos los coeficientes de la transformada de
Walsh de orden mayor que uno son nulos, entonces el problema es no paradójico [Barr,
94].
Estos resultados permiten conocer a priori la dificultad del problema de optimización al
que se enfrenta el AG, así como determinar las dos deficiencias encontradas en los
operadores de cruce clásicos como el ordinario, el basado en múltiples puntos de corte y
el uniforme, que impiden la resolución de este tipo de problemas:
1. Dadas dos cadenas binarias a y b pertenecientes a una determinada población que
han resultado seleccionadas para el cruce, los operadores de cruce clásicos son
incapaces de acceder a puntos del espacio de búsqueda comprendidos entre las
cadenas máxima y mínima, entre las cuales podría encontrarse el óptimo. Como se
indicó en el estudio realizado del operador de cruce generalizado, la cadena máxima
se define como a∨b y la cadena mínima como a∧b, siendo ∧ el operador lógico and
bit a bit, y ∨ el operador lógico or bit a bit. Así por ejemplo, si a = 101101001 y b =
011101011, entonces se tiene que en ningún caso podría obtenerse como
descendiente de un operador de cruce clásico la cadena 011111001, aún estando
comprendida dentro del intervalo de cruce definido las cadenas mínima y máxima.
2. El grave inconveniente que supone la preferencia que posee este tipo de operadores
por ciertos patrones en función de su longitud o su orden, sin tener en cuenta si éstos
se encuentran o no próximos al óptimo buscado.
Daniel Manrique Gamo
Página 37
Computación Evolutiva: Algoritmos Genéticos
Algoritmos Genéticos
────────────────────────────────────────────────────────────────────────────────────────────
2.6.4.
Operadores de cruce con codificación real
El principal problema que surge a la hora de utilizar el operador de cruce cuando se
trabaja con cadenas de números reales para codificar un problema de optimización
consiste en que no es posible utilizar operadores de cruce basados en la recombinación
de los genes procedentes de los padres para generar la descendencia. Supongamos dos
cadenas de números reales a = a1,a2, ..., al y b = b1, b2, ..., bl con ai, bi∈ℜ, ∀ i∈{1, ..., l}.
Recombinando de cualquier forma los genes procedentes de los padres, se obtendrán
como descendientes cadenas de longitud l del tipo c = c1, c2, ..., cl donde ci∈{a1, ..., al,
b1, ..., bl}, ∀ i∈{1, ..., l}. Es decir, se manejarán constantemente los mismos genes
(números reales) que aparecieron en la población inicial, aunque en posiciones
diferentes a lo largo de todo el proceso de evolución. En este contexto, el único
operador capaz de generar nuevos genes sería el operador de mutación por lo que, dada
su poca probabilidad de actuación en general, no se produciría la convergencia del
algoritmo.
Uno de los primeros operadores de cruce para cadenas codificadas con números reales
es el operador de cruce plano de Radcliffe [Radc, 90]. Este operador toma dos cadenas
de números reales a = a1,a2, ..., al y b = b1, b2, ..., bl y genera dos descendientes c = c1,c2,
..., cl y d = d1, d2, ..., dl donde cada uno de los genes descendientes ci y di se obtiene de
forma aleatoria del intervalo de cruce Ci obtenido como Ci=[min(ai,bi),max(ai,bi)], para
cada i∈{1, ..., l}.
El operador de cruce lineal de Wright [Wrig, 91] toma dos cadenas a y b como
progenitores para generar tres descendientes c, d y e, donde para el caso del gen ci se
calcula como el punto medio de ai y bi, es decir, ci = ai + bi
2. Por otro lado el gen di
se calcula como di = 1.5·ai – 0.5·bi, mientras que ei = –0.5·ai + 1.5·bi.
Una generalización del operador de cruce plano es el operador de cruce combinado
[Eshe, 93]. Este operador toma dos progenitores a y b para generar dos nuevos
descendientes c y d. Para cada par de genes ai y bi procedentes de las cadenas padres, y
suponiendo ai≤bi, se crea el intervalo de cruce Ci calculado como Ci = [ai-αI , bi+αI],
donde I = bi-ai y α∈[0,1] es un parámetro predeterminado de antemano. La figura 3.6
muestra de forma esquemática el intervalo de cruce formado por los genes ai y bi de los
progenitores. El descendiente ci se toma de forma aleatoria de este intervalo de cruce,
siendo di = ai + bi - ci. A partir de la figura 4.6 se puede observar que este operador de
cruce guarda un cierto paralelismo en su funcionamiento con el operador de cruce
generalizado definido para cadenas binarias. Por otro lado se puede ver que el valor del
parámetro α determina cuánto se ensancha el intervalo de cruce con respecto al
intervalo [ai,bi] determinado por los genes de las cadenas de los padres. Si α = 0,
entonces el funcionamiento de este operador es el mismo que en el caso del operador de
cruce plano. Por el contrario, si α = 1, la longitud del intervalo de cruce es la máxima
posible, siendo de tres veces la longitud del intervalo determinado por los genes padres.
Daniel Manrique Gamo
Página 38
Computación Evolutiva: Algoritmos Genéticos
Algoritmos Genéticos
────────────────────────────────────────────────────────────────────────────────────────────
Figura 3.6: Operador de cruce combinado.
Otro operador de cruce importante es el operador de cruce gaussiano [Ono, 97]. Éste
trata a los individuos de la población como vectores de números reales de dimensión l,
generando, a partir de tres cadenas progenitoras
la siguiente forma:
=
+ z1· +
=
– z1·
–
+
) / 2,
=(
zk ·
zk ·
,
y
, dos descendientes,
y
, de
,
,
z1 ∼ N (0, σ1), zk ∼ N (0, σ2) (k = 2, ..., l).
Siendo N (0, σ1) y N (0, σ2) dos distribuciones normales de media cero y desviaciones
típicas σ1 y σ2 respectivamente. σ1 se calcula como un valor proporcional a la distancia
euclídea existente entre los padres
y
proporcional a la distancia euclídea entre
. Los vectores { , ...,
. Mientras que σ2 se calcula como un valor
y el segmento que une los extremos de
y
} forman una base de ℜl.
Este operador de cruce genera hijos que se encuentran muy alejados entre sí, en
distancia euclídea, si la distancia entre los padres también es muy grande, mientras que
se mantienen próximos en caso contrario. Este hecho permite explorar todo el espacio
de búsqueda en las primeras iteraciones del algoritmo, mientras que posteriormente se
centra más en aquellas zonas donde parece estar el óptimo buscado.
Otras características del operador de cruce gaussiano es su independencia respecto a los
ejes del sistema de coordenadas y que es independiente a transformaciones ortogonales.
El operador de cruce morfológico [Barr, 00], [Barr, 03] (denominado MMX) es un
operador de propósito general para la resolución de problemas con algoritmos genéticos
codificados con números reales. Se basa en la utilización de la morfología matemática,
la cual apareció gracias a los trabajos de Matheron y Serra [Math, 65], [Math, 75], [Serr,
82], [Serr, 83], [Serr, 86], [Serr, 88]. Se basa en la aplicación de la teoría de conjuntos al
procesamiento de señales [Cres, 93]. En concreto, puesto que una imagen digitalizada
puede ser interpretada como una señal bidimensional [Dalo, 98], es muy común utilizar
los conceptos derivados de la morfología matemática al análisis de imágenes con el fin
Daniel Manrique Gamo
Página 39
Computación Evolutiva: Algoritmos Genéticos
Algoritmos Genéticos
────────────────────────────────────────────────────────────────────────────────────────────
de extraer aquellos componentes que serán útiles para describirla, tales como forma o
contornos [Giar, 88], [Gonz, 93], [Cres, 93].
El operador de cruce morfológico incluye una nueva medida de la diversidad genética
basada en el gradiente morfológico, usado generalmente en imágenes digitalizadas. Para
ello, se ha adaptado su funcionamiento y la interpretación de sus resultados con el fin de
aplicar capacidades de exploración y explotación de forma equilibrada.
El cruce morfológico opera con poblaciones de λ individuos formados por cadenas de
números reales de longitud l de la siguiente forma. Partiendo de un número n impar de
cadenas progenitoras (n ≤ λ), obtenidas sin repetición de la población actual, se obtiene
un conjunto de l intervalos, denominados intervalos de cruce C0, ..., Cl-1, a partir de los
cuales se generan las cadenas descendientes del operador, denotadas por o = (o0, ..., ol-1)
y o’ = (o0’, ..., ol-1’).
Para cada i = 0, ..., l-1, oi es un valor aleatorio perteneciente al intervalo de cruce Ci,
mientras que oi’ se obtiene como:
oi’ = ( ai + bi ) – oi
siendo ai y bi los extremos del intervalo de cruce Ci.
Puesto que se trabaja con cadenas de números reales, cada punto del espacio de
búsqueda está codificado mediante un vector definido como:
s=
, con
∈ ℜ, i = 0, 1, ..., l-1
Al conjunto de todas las cadenas que codifican el espacio de búsqueda de un
determinado problema se denota por Dlℜ. Se va a suponer de aquí en adelante que se
trabaja siempre con cadenas de números reales acotados. Es decir, cualquier gen
perteneciente a cualquier cadena s que representa un punto del espacio de búsqueda,
será un valor comprendido dentro de un intervalo real acotado:
∀ s ∈ Dlℜ, con s =
se tiene que
∈[αi, ωi], αi, ωi ∈ ℜ, ∀ i = 0, ..., l-1
Por tanto, para que un AG que trabaje con este tipo de cadenas encuentre la solución a
un problema de optimización, ésta debe poder ser codificada mediante una cadena de
genes cuyos valores se encuentren dentro de las cotas establecidas.
Con estas premisas es posible definir la función de normalización N, como una función
biyectiva l-dimensional de la forma:
N: Dlℜ → [0,1]l.
N (s) =
que transforma cada uno de los genes
, con
∈ [0,1], i = 0, 1, ..., l-1
de una determinada cadena en un número real
del intervalo [0,1]. Analíticamente, se describe la función de normalización como:
Daniel Manrique Gamo
Página 40
Computación Evolutiva: Algoritmos Genéticos
Algoritmos Genéticos
────────────────────────────────────────────────────────────────────────────────────────────
Puesto que la función de normalización es biyectiva, es equivalente trabajar con cadenas
s pertenecientes al espacio Dlℜ, o bien con las correspondientes cadenas normalizadas
N(s), pertenecientes al espacio [0,1]l. Por tanto, se supone desde este momento que se
trabaja siempre con cadenas normalizadas según la función N.
Recordando que el cruce morfológico opera con un número n impar de cadenas
progenitoras de dimensión l, obtenidas mediante un mecanismo de selección sin
repetición de la población actual, se denomina matriz progenitora, y se denota por G, a
la matriz que representa todos los valores de los genes de las cadenas padre:
donde si =
(3.1)
, i = 1 ,.., n
Para cada una de las l columnas de G se define el vector unidimensional fi como:
fi =
con i = 0 ,.., l-1
Partiendo de estos l vectores columna: f0, ..., fl-1, el cruce morfológico lleva a cabo los
siguientes tres pasos: cálculo de la medida de la diversidad genética, cálculo de los
intervalos de cruce y obtención de la descendencia.
1. Cálculo de la medida de la diversidad genética.
El primer paso del operador de cruce morfológico es el cálculo de un valor que
proporcione una medida de la diversidad genética de la población. De esta forma, será
posible poder decidir de forma dinámica, según se evoluciona en el proceso de
convergencia hacia el óptimo global, si es más interesante aplicar técnicas de
explotación sobre los esquemas intervalo actualmente existentes, o si, por el contrario,
se está en peligro de convergencia subóptima. En este último caso, hay que tomar
medidas más intensas de exploración, provocando la ruptura de patrones intervalo.
La obtención de la medida de la diversidad genética se realiza gen a gen a partir de los n
individuos tomados como progenitores, es decir, se toma una medida gi para cada vector
columna fi de la matriz progenitora. Puesto que se trabaja con cada uno de los genes que
forman los individuos independientemente, es posible conocer cómo evoluciona cada
uno de ellos por separado, lo cual proporciona una mayor información, y es posible
actuar de forma distinta (explorando o explotando) según cada caso.
Sea el retículo completo ℱ, cualquier transformación ε: ℱ → ℱ que cumple la
propiedad conmutativa con respecto al ínfimo se denomina erosión. Es decir, si la
trasformación ε es una erosión, ∀ {fi} ⊆ ℱ se tiene que ε (∧ifi) = ∧i ε (fi).
Daniel Manrique Gamo
Página 41
Computación Evolutiva: Algoritmos Genéticos
Algoritmos Genéticos
────────────────────────────────────────────────────────────────────────────────────────────
De forma similar, cualquier transformación δ:ℱ → ℱ que cumple la propiedad
conmutativa con respecto al supremo se la denomina dilatación. Es decir, si la
trasformación δ es una dilatación, ∀ {fi} ⊆ ℱ, se tiene que δ (∨ifi) = ∨i δ (fi).
Estos dos operadores morfológicos pueden ser aplicados sobre funciones pertenecientes
al retículo completo ℱ, las cuales son del tipo:
f: E → T,
siendo E un conjunto cualquiera y T un retículo completamente ordenado.
Supóngase ahora que se desean aplicar las operaciones de dilatación y erosión de la
morfología matemática, pero esta vez sobre cada uno de los l vectores columna f0, ..., fl-1
de la matriz progenitora. Con este fin, se interpreta fi como la función:
fi: Dfi → [0,1], siendo Dfi = {1, 2, ..., n}
fi (j) = aj,i, con aj,i ∈ G
Puesto que [0,1] es un retículo completamente ordenado, se cumplen todas las premisas
para la aplicación de estos operadores.
Dadas una imagen f y una función b: Z x Z → Z, denominada elemento estructurante,
la operación dilatación morfológica más usual de dicha imagen con el elemento
estructurante b sobre el punto (s,t) es de la forma [GIAR88], [GONZ93]:
(f ⊕ b) (s,t) = max {f (s-x , t-y) + b (x,y) : (s-x, t-y)∈Df ; (x,y) ∈ Db}
(3.2)
donde Db es el dominio del elemento estructurante.
La ecuación 3.2 define la operación dilatación que se aplica sobre imágenes digitales.
Se trata ahora de modificar esta expresión con el fin de aplicarla sobre los vectores
columna fi de G. Para ello, hay que tener en cuenta que la única diferencia importante
entre una imagen y fi es que ésta es una función de una variable, mientras que aquella es
una función de dos variables.
Se toma en primer lugar el elemento estructurante b que, por lo dicho anteriormente,
debe tratarse de una función de una variable:
b: Db → ℜ, siendo Db = {-E (n/2), -E (n/2) + 1 , …, E (n/2)}.
E (x) es la función parte entera de x.
Al igual que suele ocurrir en el caso de imágenes digitalizadas, se supone el elemento
estructurante nulo:
b (x) = 0, ∀ x∈ Db
Con estas premisas, y partiendo de la ecuación 3.2 se define la operación dilatación
morfológica sobre los vectores fi de G, empleando el elemento estructurante b definido
anteriormente de la forma:
Daniel Manrique Gamo
Página 42
Computación Evolutiva: Algoritmos Genéticos
Algoritmos Genéticos
────────────────────────────────────────────────────────────────────────────────────────────
(fi ⊕ b) (s) = max {fi (s-x) + b (x) : s-x ∈ Dfi ; x ∈ Db}
Dado que se emplea el elemento estructurante nulo, resulta:
(fi ⊕ b) (s) = max {fi (s-x) : s-x ∈ Dfi ; x ∈ Db}
(3.3)
La operación erosión morfológica usual de una imagen f sobre un punto (s,t) de la
misma mediante el elemento estructurante b, es de la forma [GIAR88], [GONZ93]:
(f ⊖ b) (s,t) = min {f (s+x , t+y) - b (x,y) : (s+x, t+y)∈Df ; (x,y) ∈ Db}
(3.4)
Utilizando el mismo razonamiento, es posible aplicar esta operación de erosión
morfológica sobre cada uno de los l vectores f0, ..., fl-1 de la matriz progenitora,
empleando el mismo elemento estructurante nulo b. Para ello, partiendo de la ecuación
3.4, se define:
(fi ⊖ b) (s) = min {fi (s+x) - b (x) : s+x∈Dfi ; x ∈ Db}
Puesto que, de nuevo, se trabaja con el elemento estructurante nulo, resulta finalmente:
(fi ⊖ b) (s) = min {fi (s+x) : s+x∈Dfi ; x ∈ Db}
(3.5)
La transformación gradiente morfológico sobre una imagen consiste en la resta entre la
imagen dilatada y la imagen erosionada, obteniendo una nueva imagen denotada por la
función g. Su expresión es la siguiente:
g = (f ⊕ b) - (f ⊖ b)
Con muy pocas modificaciones se obtiene que la operación gradiente morfológico,
aplicada sobre un vector fi de la matriz progenitora con el elemento estructurante usual
nulo b, es la siguiente:
g (s) = (fi ⊕ b) (s) - (fi ⊖ b) (s)
El funcionamiento interno de esta operación aplicada sobre la componente situada en la
posición media del vector fi, es decir, el cálculo de g (E (n/2)+1) se realiza en tres pasos:
1. En primer lugar, se aplica una operación de dilatación del vector fi sobre el punto
E(n/2)+1, con el elemento estructurante b. De la ecuación 3.3 se deduce que el
resultado de esta operación es el valor máximo de las componentes del vector,
puesto que el elemento estructurante recorre a fi desde la componente
E(n/2)+1−E(n/2) = 1; hasta E (n/2) +1 + E (n/2) = 2· E (n/2) +1 = n (ya que n es
impar).
2. Posteriormente se calcula, de la misma forma, la erosión del vector fi sobre el punto
E (n/2)+1. A partir de la ecuación 3.5, se tiene que esta operación consiste en el
cálculo del valor mínimo de las componentes del vector fi.
Daniel Manrique Gamo
Página 43
Computación Evolutiva: Algoritmos Genéticos
Algoritmos Genéticos
────────────────────────────────────────────────────────────────────────────────────────────
3. Finalmente, se realiza la resta entre los valores máximo y mínimo de las
componentes de fi obtenidos en los dos pasos anteriores.
Definición: Sea G la matriz progenitora de dimensión (n x l) de la ecuación 3.1, y sean
f0, ..., fi, ..., fl-1 sus l vectores columna, fi = (a1,i, a2,i, ..., an,i) que contienen los n valores
de los n progenitores para el gen i. Se define como medida de la diversidad genética del
gen i en la población, el valor gi∈[0,1] calculado como:
gi = g (E (n/2)+1) = (fi ⊕ b) (E (n/2)+1) - (fi ⊖ b) (E (n/2)+1)
(3.6)
Es decir, se toma como medida de la diversidad genética del gen número i al valor del
gradiente morfológico aplicado sobre la componente situada en la posición media del
vector columna fi de la matriz progenitora.
La operación gradiente morfológico aplicada sobre una imagen digitalizada en niveles
de gris produce el realce de las zonas donde se producen cambios de nivel de gris, sin
importar la dirección del borde, dejando el resto de la imagen en tonos oscuros (valores
próximos a cero). Esto es precisamente lo que se quiere detectar en el vector fi: si las n
componentes de fi son todas parecidas, entonces el valor máximo de todas ellas será un
valor similar al valor mínimo, y por tanto, la resta entre ellos, un valor próximo a cero.
Si por el contrario, hay divergencias y, por tanto, diversidad genética para ese gen, el
valor máximo y el mínimo de las componentes de fi serán diferentes, y la operación
gradiente morfológico devolverá un valor tanto más alejado de cero (y más cercano a
uno) cuanto mayor sea la diversidad. Puesto que los genes contenidos en fi están
normalizados entre cero y uno, el caso límite de máxima diversidad es que exista un gen
con valor cero y otro con valor uno, lo que da como resultado del gradiente el valor uno.
En el extremo opuesto, si todos los genes son iguales, el resultado del gradiente es el
valor cero.
Lo dicho anteriormente supone una nueva interpretación de la operación gradiente
morfológico cuando se aplica de esta manera en AAGG reales. A este hecho, hay que
resaltar además, como característica muy importante de esta medida definida en la
ecuación 3.6, su bajo coste computacional al constar únicamente del cálculo del valor
máximo y mínimo de un vector y, posteriormente, la resta entre ambos. Al contrario que
el resto de medidas existentes hasta el momento, no hay que aplicar ni una sola
multiplicación o división, que es lo computacionalmente costoso cuando se trabaja con
números reales.
2. Cálculo de los intervalos de cruce.
Como se ha dicho anteriormente, el cruce morfológico toma un número impar de
progenitores sin repetición de la población actual para generar dos nuevos descendientes
o = (o0, ..., ol-1) y o’ = (o’0, ..., o’l-1). Cada uno de los pares de genes oi y oi’ de la
descendencia se obtienen como dos valores pertenecientes al intervalo de cruce Ci.
Daniel Manrique Gamo
Página 44
Computación Evolutiva: Algoritmos Genéticos
Algoritmos Genéticos
────────────────────────────────────────────────────────────────────────────────────────────
El cálculo de cada uno de los l intervalos de cruce Ci depende de una función ϕ: ℜ → ℜ
denominada función de exploración / explotación. La elección de ϕ se discutirá en la
siguiente sección por sus importantes repercusiones en el funcionamiento del cruce
morfológico.
Sea gimax el gen máximo, definido como la resta entre la dilatación del vector fi en el
punto medio y el valor de la función ϕ en el punto gi (valor de la diversidad genética del
gen número i):
gimax = (fi ⊕ b) (E (n/2)+1) - ϕ (gi)
Es decir, según lo comentado en el apartado anterior:
gimax = máx (fi) - ϕ (gi)
(3.7)
Asimismo, se define el gen mínimo i, y se denota por gimin, como la suma entre la
erosión del vector fi en el punto medio, y el valor de la función ϕ en el punto gi:
gimin = (fi ⊖ b) (E (n/2)+1) + ϕ (gi)
lo cual es equivalente a:
gimin = mín (fi) + ϕ (gi)
(3.8)
El gen máximo y el gen mínimo son los valores que determinan finalmente los bordes
de los intervalos de cruce, de tal forma que Ci = [gimin, gimax], con i = 0, ..., l-1.
La función ϕ de exploración / explotación, FEE, es crucial en el funcionamiento del
cruce morfológico, ya que determina cómo van a ser los intervalos de cruce.
Supóngase que ϕ (gi) = 0, ∀gi. En este caso se tiene que los intervalos de cruce son de
la forma Ci = [mín (fi), máx (fi)]. A este intervalo se le denomina intervalo de cruce
definido por los padres o intervalo de referencia. Visto desde el punto de vista de los
patrones intervalo, se podría interpretar en este caso a C0, ..., Cl-1 como el patrón
intervalo mínimo que contiene a todos los progenitores s1, ..., sn. En este caso, se
cumple también que las cadenas descendientes o y o’ también pertenecen al patrón
intervalo definido por los l intervalos de referencia. Un operador de cruce de este tipo
actuaría exactamente igual que el cruce plano de Radcliffe, o el cruce combinado
tomando α=0. Estos operadores de cruce mantienen siempre los patrones intervalo,
aplicando únicamente técnicas de explotación al generar únicamente individuos dentro
del intervalo de cruce definido por los padres. Este hecho puede llevar al algoritmo a la
convergencia prematura. La figura 3.7 muestra esta situación para el caso de un gen
cualquiera i.
Daniel Manrique Gamo
Página 45
Computación Evolutiva: Algoritmos Genéticos
Algoritmos Genéticos
────────────────────────────────────────────────────────────────────────────────────────────
Figura 3.7: La descendencia se obtiene siempre dentro del intervalo de referencia.
Mediante la inclusión de la FEE en el cruce morfológico es posible controlar la
construcción de los intervalos de cruce, para que éstos no sean siempre iguales a los
intervalos definidos por los padres. Puesto que depende de la variable gi, es decir, de la
diversidad genética de la población actual, la FEE debe de proporcionar una regla que
permita, de forma dinámica según el estado del proceso de convergencia, localizar la
búsqueda dentro del intervalo [mín (fi), máx (fi)] (explotación), o bien por el contrario,
tratar de buscar nuevos puntos dentro del espacio de búsqueda (exploración).
Cuando los valores que toma algún determinado gen i en los individuos de la población
son muy similares entre sí, éste está convergiendo hacia algún punto. En estos casos, el
valor obtenido de gi será muy cercano a cero y por tanto, la FEE debe expandir el
intervalo [mín (fi), máx (fi)], para permitir la exploración de nuevos puntos dentro del
espacio de búsqueda, con el fin de evitar la convergencia hacia un punto que no sea el
óptimo. A partir de las ecuaciones 3.7 y 3.8, se deduce que en este caso, la FEE debe
proporcionar valores negativos para valores pequeños de gi, con lo que [mín (fi), máx
(fi)] ⊆ [gimin, gimax]. La figura 3.8 ilustra este caso.
Figura 3.8: Posibilidad de obtener descendencia fuera del intervalo de referencia.
Existe también la posibilidad de que los valores de un determinado gen sean muy
diferentes unos de otros en las cadenas que forman la población actual. O bien, el caso
general de que los individuos de la población estén muy dispersos dentro de todo el
espacio de búsqueda. Este hecho se produce, por ejemplo, en la población inicial o en
las primeras etapas del proceso de convergencia del AG. En estos casos, el valor de gi
será muy elevado (más cercano al valor 1) y, por tanto, la FEE debe estrechar el
intervalo de referencia, hecho importante y novedoso. Para ello, la FEE debe
proporcionar valores positivos, por lo que según las ecuaciones 3.7 y 3.8 se tiene que
[gimin, gimax] ⊆ [mín (fi), máx (fi)]. La figura 3.9 ilustra este hecho.
Daniel Manrique Gamo
Página 46
Computación Evolutiva: Algoritmos Genéticos
Algoritmos Genéticos
────────────────────────────────────────────────────────────────────────────────────────────
Figura 3.9: El intervalo de cruce es más estrecho que el intervalo de referencia.
De esta forma, se evita el problema de la no convergencia por la continua exploración
de nuevos puntos cuando la población está muy dispersa, consiguiendo, por el contrario,
una convergencia muy rápida hacia algún punto. Si resultara ser el óptimo global, el AG
finalizaría en muy pocas iteraciones. Si, por el contrario, este proceso no conduce hacia
la solución, sería entonces cuando se volverían a aplicar técnicas de exploración
ensanchando el intervalo de cruce con respecto al de referencia, para explorar nuevas
regiones del espacio de búsqueda.
A continuación se describen las condiciones que debe de cumplir la función ϕ (gi) para
conseguir el comportamiento descrito anteriormente:
1. La función ϕ debe proporcionar valores positivos para valores elevados de gi. De
esta forma se estrecha el intervalo de cruce. Por el contrario, debe proporcionar
valores negativos cuando gi esté próximo a cero, ya que el gen i está convergiendo e
interesa explorar nuevas regiones ensanchando el intervalo.
2. La función ϕ debe de tener un coste computacional bajo, ya que en cada aplicación
del cruce morfológico, se calcula tantas veces como genes tengan los individuos, es
decir, se calcula l veces: ϕ (g0), ϕ (g1), ..., ϕ (gl-1).
3. El dominio de la función debe de ser el intervalo real [0,1], que contiene los valores
que puede tomar gi.
4. Puesto que la función ϕ (gi) se utiliza para el cálculo del intervalo de cruce Ci =
[gimin, gimax], se debe de cumplir siempre que gimin ≤ gimax, con lo que a partir de las
ecuaciones 3.7 y 3.8 se tiene que:
mín (fi) + ϕ (gi) ≤ máx (fi) - ϕ (gi)
Despejando ϕ (gi):
ϕ (gi) ≤ ½·[máx (fi) - mín (fi)]
(3.9)
A partir de las ecuaciones 3.3, 3.5 y 3.6, con el elemento estructurante usualmente
utilizado, b (x) = 0, ∀ x∈Db = {-E (n/2), …, 0, …, E (n/2)}, se tiene que:
Daniel Manrique Gamo
Página 47
Computación Evolutiva: Algoritmos Genéticos
Algoritmos Genéticos
────────────────────────────────────────────────────────────────────────────────────────────
gi = máx (fi) - mín (fi)
(3.10)
Luego,
ϕ (gi) ≤ ½ gi
Finalmente, se obtiene la condición que debe de satisfacer ϕ para asegurar que
gimin≤gimax:
ϕ (x) ≤
, ∀ x ∈ Dϕ
(3.11)
5. En el caso particular de que gi = 0, entonces todos los valores de los genes i de los n
individuos que se cruzan son iguales:
gi = 0 ⇒ g (E (n/2)+1) = 0 ⇒ fi(j) = k, ∀ j ∈ Dfi, k ∈ ℜ
La función ϕ (gi) debe de ser tal que cumpla la condición: ϕ (0) ≠ 0. En caso de que
esta premisa no se satisfaga, ocurre que tanto gimax como gimin son iguales a un valor
k:
gimax = máx (fi) - ϕ (0) = k
gimin = mín (fi) + ϕ (0) = k
Por lo tanto, el intervalo de cruce es Ci = [k , k]. Puesto que, como se verá en el
siguiente apartado, los valores para el gen i de la descendencia, oi y o’i, pertenecen a
Ci, entonces oi = o’i = k. Si el valor k no es el óptimo para el gen i, el AG quedará
atrapado en ese valor, no alcanzando nunca la solución óptima.
La figura 3.10 muestra la función ϕ (gi) que mejores resultados ha proporcionado en las
pruebas realizadas, cuya forma final depende de cuatro parámetros: a, b, c y d, donde
ϕ(0) = a; ϕ (c-) = b; ϕ (c) = ϕ (c+) = 0 y ϕ (1) = d.
Figura 3.10. Función ϕ empleada en las pruebas realizadas.
Para satisfacer los cinco requisitos descritos anteriormente, se debe de cumplir que:
•
La función ϕ sea como mucho de orden lineal, para no incrementar el coste
computacional del algoritmo.
Daniel Manrique Gamo
Página 48
Computación Evolutiva: Algoritmos Genéticos
Algoritmos Genéticos
────────────────────────────────────────────────────────────────────────────────────────────
•
a<0, con lo que se evita el problema de que ϕ (0) = 0, y además, por ser negativo,
ensancha el intervalo para valores pequeños de gi.
•
b ≤ a. Así, los puntos (0,a) y (c,b) determinan una recta de pendiente negativa, de tal
forma que cuanto menor sea gi, menor sea el ensanchamiento que se produce del
intervalo definido por los padres. Esto es así, debido a que si [gimin, gimax] es muy
grande comparado con [mín (fi), máx (fi)], entonces no se tiene en cuenta para nada
los valores de los genes de los padres, convirtiendo el proceso en una búsqueda
aleatoria. Este último razonamiento lleva a la conclusión de que el parámetro a tenga
que tener un valor negativo y muy próximo a cero.
•
El parámetro c puede ser cualquier valor entre cero y uno. Este parámetro es el que
decide cuándo se considera que la población está dispersa y cuándo la población
está convergiendo. Valores de gi mayores de c, indican que el gen i está disperso, lo
cual proporciona un valor positivo de ϕ (gi) que, a su vez, provoca el estrechamiento
del intervalo definido por los padres. Por el contrario, valores de gi menores que c,
indican que este gen está convergiendo, con lo que ϕ (gi) es negativo, y el intervalo
de cruce será más ancho que el definido por los padres.
•
d∈[0, 0.5]. Los puntos (c,0) y (1,d) determinan una recta de pendiente positiva de tal
forma que cuanto mayor sea gi, más disperso está el gen i, y por tanto, mayor será el
estrechamiento que se produce del intervalo definido por los padres. Si d = 0,
entonces el cruce morfológico no estrecha nunca este intervalo. Por otro lado, d
nunca puede ser mayor de 0.5 para que se cumpla la condición definida por la
ecuación 3.11.
3. Cálculo de la descendencia.
Una vez obtenidos los l intervalos de cruce C0, C1, ..., Ci, ..., Cl-1, a partir del intervalo
definido por los padres y el valor proporcionado por la FEE. El tercer y último paso del
cruce morfológico es el cálculo de la descendencia o = (o0, ..., ol-1) y o’ = (o’0, ..., o’l-1),
resultado final del operador. Como ya se comentó anteriormente, para cada i = 0, ..., l-1,
este paso se realiza en dos etapas:
1. oi es un valor aleatorio escogido del intervalo de cruce Ci.
2. oi’ se obtiene a partir del valor de oi según la expresión:
oi’ = ( mín (fi) + máx (fi) ) – oi, con i = 0, 1, ..., l-1
(3.12)
Esta forma de calcular oi’ provoca que los genes elegidos para la descendencia
cumplan:
oi + oi’ = mín (fi) + máx (fi) = gimin + gimax,
(3.13)
lo cual significa que son equidistantes al centro del intervalo de cruce.
Además, como cabría esperar, se asegura que oi y oi’ pertenecen al intervalo de
cruce Ci = [gimin , gimax]. En efecto, de la ecuación 3.12 se tiene que:
Daniel Manrique Gamo
Página 49
Computación Evolutiva: Algoritmos Genéticos
Algoritmos Genéticos
────────────────────────────────────────────────────────────────────────────────────────────
oi = ( mín (fi) + máx (fi) ) – oi’
(3.14)
Puesto que oi se elige aleatoriamente de Ci, también se tiene que:
gimin ≤ oi ≤ gimax
Reemplazando en la ecuación anterior oi por su valor de la expresión 3.14:
gimin ≤ ( mín (fi) + máx (fi) ) – oi’ ≤ gimax
Despejando oi’:
( mín (fi) + máx (fi) ) - gimax ≤ oi’ ≤ ( mín (fi) + máx (fi) ) - gimin
Finalmente, empleando 3.13:
gimin ≤ oi’ ≤ gimax
Coste computacional del operador de cruce morfológico
Se realiza a continuación un recuento de las operaciones en coma flotante que se llevan
a cabo en cada uno de los pasos del algoritmo, suponiendo cadenas de un único gen, ya
que, en el caso de existir l genes, el proceso es exactamente igual, repetido l veces:
1. Para el cálculo de g, se parte del vector f, de dimensión n, y se realiza la operación
g= máx (f) – mín (f). Se considera que el cálculo de los valores máximo y mínimo
implica la realización de n sumas / restas. Por tanto, en este primer paso se realizan
2·n + 1 sumas / restas.
2. El intervalo de cruce C = [gmin, gmax] se calcula como se describe en las ecuaciones
3.7 y 3.8 teniendo en cuenta que máx (f) y mín (f) ya están calculados del paso
anterior. Si se emplea la función ϕ propuesta en la figura 3.10, el cálculo de ϕ (g)
implica una suma y una multiplicación. Luego en total en este paso se realizan 3
sumas / restas y una multiplicación.
3. Por último, el cálculo del descendiente o’ implica una suma y una resta.
Resumiendo todo lo anterior, se tiene que para cada gen, la ejecución del operador de
cruce emplea únicamente una multiplicación y 2·n + 6 sumas / restas.
De aquí en adelante se denominará FLOPS al número total de operaciones en coma
flotante (números reales) necesarias para realizar una tarea. Asimismo, se denominará
FLOMS al número de multiplicaciones y S al número de sumas. Según lo dicho
anteriormente, se tiene que: FLOPS=FLOMS+S.
Puesto que el operador de cruce morfológico trabaja con cadenas de longitud l, una
operación de cruce emplea l FLOMS, esto es, tantas multiplicaciones en coma flotante
como genes tengan los individuos de la población, más SMMX sumas en coma flotante:
Daniel Manrique Gamo
Página 50
Computación Evolutiva: Algoritmos Genéticos
Algoritmos Genéticos
────────────────────────────────────────────────────────────────────────────────────────────
FLOPSMMX = l + l·(2n+6) = l + SMMX
(3.15)
Se observa claramente, después de este recuento, que el operador de cruce morfológico
emplea muy pocas operaciones en coma flotante, lo cual lo hace especialmente indicado
para su utilización con números reales dentro de un AG, donde se realizan gran cantidad
de operaciones de cruce a lo largo del proceso de evolución.
Además, para todos los genes se actúa de igual forma, e independientemente (los
valores de unos genes no interactúan con los otros), luego este proceso es muy
fácilmente paralelizable empleando l procesadores, con lo que la velocidad de ejecución
del cruce morfológico quedaría, en este caso, multiplicada por l.
2.6.5.
Reemplazo de individuos
Una vez obtenidos los individuos descendientes de una determinada población tras la
aplicación de los diferentes operadores, es necesario formar una nueva población (la
nueva generación) de λ individuos a partir de las λ cadenas existentes en la población
de partida y los nuevos individuos obtenidos. El concepto de reemplazo suele ir ligado
con el de tasa de reemplazamiento generacional ttg que es el porcentaje de hijos
generados con respecto al tamaño de la población inicial.
Inicialmente, el proceso de reemplazamiento se efectuaba de uno en uno, ttg=λ-1, por lo
que se generaba un único individuo descendiente que sustituía a otro de la población
inicial [Holl, 75].
De Jong aplicó el concepto de tasa de reemplazamiento generacional con el objetivo de
efectuar un solapamiento controlado entre padres e hijos [Dejo, 75]. En este trabajo, una
proporción ttg de la población es seleccionada para ser cruzada. Los hijos resultantes
reemplazarán a los miembros de la población anterior que peor adaptados se encuentren.
Este tipo de algoritmos genéticos, donde únicamente se sustituyen unos pocos
individuos, se conocen bajo el nombre de SSGA (Steady-State Replacement Genetic
Algorithms), llegando en algunas implementaciones a sustituir únicamente dos. Un
ejemplo de este tipo de reemplazamiento se aplica en el sistema GENITOR [Whit, 88],
[Whit, 89], [Whit, 90].
Es posible también realizar el reemplazamiento de individuos en bloque, es decir ttg = 1
[Gref, 86]. Según este estudio, habiendo obtenido λ individuos por aplicación de los
operadores genéticos sobre una población inicial también de λ individuos, se aplica lo
que se denomina un proceso de reducción simple, consistente en un reemplazo
generacional completo donde los nuevos λ individuos sustituyen a todos los de la
población inicial.
Otra posibilidad es la de, a partir de los λ individuos iniciales, más otros λ individuos
descendientes, obtener los λ individuos más adaptados al problema en lo que se
denomina reducción elitista de grado λ.
Daniel Manrique Gamo
Página 51
Computación Evolutiva: Algoritmos Genéticos
Algoritmos Genéticos
────────────────────────────────────────────────────────────────────────────────────────────
Los algoritmos genéticos modificados llevan a cabo el reemplazo generacional
seleccionando al azar r1 individuos por la reproducción, así como otros r2 individuos
distintos a los anteriores destinados a morir. Estas selecciones aleatorias tienen en
consideración el valor de la función objetivo para cada individuo, de tal manera que
cuanto mayor es la adaptación del individuo, mayor es la probabilidad de que sea
seleccionado por la reproducción, y menor es la probabilidad de que dicho individuo
fallezca. El resto de los λ - (r1+r2) individuos son considerados como neutros y pasan
directamente a formar parte de la población en la siguiente generación [Mich, 96].
Existen, además, otros operadores relacionados con los métodos de selección de los
individuos, denominados catastróficos [Kure, 96]. Dichos operadores realizan una
evaluación cada cierto tiempo sobre el grado de convergencia del algoritmo. Si la
población está convergiendo hacia un determinado óptimo, el cual podría ser un óptimo
local y, por tanto, no es la solución al problema, se aplica alguno de estos operadores,
reemplazando una serie de individuos de la población actual por otros generados
aleatoriamente. Estos operadores nunca destruyen a los mejores individuos generados
hasta el momento, ya que éstos podrían estar muy cerca del óptimo buscado,
permitiendo la aparición de nuevos individuos de forma aleatoria con el fin de explorar
nuevas regiones dentro del espacio de búsqueda por si existieran puntos mejores que los
encontrados hasta ahora. Los principales operadores catastróficos son dos:
•
Operador de empaquetado: Todos los individuos que tienen el mismo valor en la
función objetivo son destruidos excepto uno de ellos. El resto son reemplazados en
la población por individuos generados aleatoriamente. Este operador impide la
repetición de individuos en la población, facilitando la diversidad de la misma.
•
El día del juicio final: Este operador destruye a todos los individuos de la población
excepto al más adaptado. La población se vuelve a rellenar con individuos
generados aleatoriamente.
Daniel Manrique Gamo
Página 52