Source: http://docplayer.es/4155844-Computacion-evolutiva-algoritmos-geneticos.html
Timestamp: 2018-12-11 20:44:48+00:00

Document:
Computación Evolutiva: Algoritmos Genéticos - PDF
Download "Computación Evolutiva: Algoritmos Genéticos"
José Ángel Belmonte Correa
1 Computación Evolutiva: Apuntes de la asignatura: Inteligencia Artificial Razonamiento Aproximado (Máster) Daniel Manrique Gamo Profesor Titular de Universidad
3 Índice 1. Introducción Bases de la computación evolutiva Características de la computación evolutiva 9 2. Algoritmos genéticos Historia de los algoritmos genéticos Características y funcionamiento de los algoritmos genéticos Codificación del problema Codificaciones binarias Codificaciones no binarias La función de evaluación Convergencia Medidas de convergencia Operadores genéticos Operadores de reproducción Operadores de mutación Operadores de cruce con alfabeto finito Operadores de cruce con codificación real Reemplazo de individuos 51 Daniel Manrique Gamo Página 3
5 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
6 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
7 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 Bases de la computación evolutiva La más comúnmente aceptada base de teorías sobre la evolución es el paradigma neo- Darwiniano. 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
8 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
9 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 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
10 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
11 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
12 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 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
13 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
14 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 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
15 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
16 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
17 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 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 m l 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 A l de todas las posibles l-uplas de elementos de A, con la condición de que m l 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 Ω(A l ), y se entiende que cada elemento (a 1, a 2,..., a l ) de A l es la codificación de su imagen mediante Ω. Ahora bien, el número de puntos codificados es m l. Por tanto, sólo será posible la búsqueda del óptimo entre estos puntos. Con la Daniel Manrique Gamo Página 17
18 notación anterior, se puede definir el espacio de búsqueda como el subconjunto Ω(A l ) 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 m l, 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 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
19 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 (p 1, p 2,..., p l ) donde cada p i {0,1,*}. Un patrón p 1 p 2...p l representa un conjunto de cadenas o elementos de {0,1} l. Para ello, se distinguen dos casos: Si p i es un carácter del alfabeto original, toda cadena del conjunto toma el valor p i en la posición i. En caso contrario, si p i =*, 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 2 k 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
20 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 I 1,..., 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 (I i ), siendo f(i i ) el valor de la función objetivo del individuo I i 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 E sel,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 p c y p m 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 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
21 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 2 l 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 2 l 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
22 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 = c 1 c 2... c l, c i 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 I i, en posiciones i de la cadena de la forma I i = [a i,b i ] N, con a i y b i N. Se denomina esquema intervalo a todo elemento de la forma c =c 1 c 2... c l, c i {I i } 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 = I i, entonces las cadenas del conjunto pueden tomar cualquiera de los valores del intervalo [a i,b i ] 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 k 1 y k 2 [0,n-1] con k 1 < k 2, tienen (k 1 +1) (n-k 2 ) 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

References: resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución