Cruces en los Algoritmos Geneticos

El Algoritmo Genético Canónico descrito anteriormente utiliza el cruce basado en un punto, en el cual los dos individuos seleccionados para jugar el papel de padres, son recombinados por medio de la selección de un punto de corte, para posteriormente intercambiar las secciones que se encuentran a la derecha de dicho punto.

Se han investigado otros operadores de cruce, habitualmente teniendo en cuenta más de un punto de cruce. De Jong investigó el comportamiento del operador de cruce basado en múltiples puntos, concluyendo que el cruce basado en dos puntos, representaba una mejora mientras que añadir más puntos de cruce no beneficiaba el comportamiento del algoritmo. La ventaja de tener más de un punto de cruce radica en que el espacio de búsqueda puede ser explorado más fácilmente, siendo la principal desventaja el hecho de aumentar la probabilidad de ruptura de buenos esquemas.

En el operador de cruce basado en dos puntos, los cromosomas (individuos) pueden contemplarse como un circuito en el cual se efectúa la selección aleatoria de dos puntos, tal y como se indica en la Figura 8.

Figura 8

Desde este punto de vista, el cruce basado en un punto, puede verse como un caso particular del cruce basado en dos puntos, en el cual uno de los puntos de corte se encuentra fijo al comienzo de la ristra que representa al individuo. Véase Figura,9.

En el denominado operador de cruce uniforme (Syswerda) cada gen, en la descendencia se crea copiando el correspondiente gen de uno de los dos padres, escogido de acuerdo ' a una "máscara de cruce" generada aleatoriamente. Cuando existe un l en la "máscara de cruce", el gen es copiado del primer padre, mientras que cuando exista un 0 en la

Figura 9

"máscara de cruce", el gen se copia del segundo padre, tal y como se muestra en la Figura 10. En la literatura, el término operador de cruce uniforme se relaciona con la obtención

Figura 10

de la "máscara de cruce" uniforme, en el sentido de que cualquiera de los elementos del alfabeto tenga asociada la misma probabilidad. Hablando en términos de la teoría de la probabilidad la máscara de cruce está compuesta por una muestra aleatoria de tamaño A extraída de una distribución de probabilidad de Bernouilli de parámetro l/2.

Si tuviésemos en cuenta el valor de la función de adaptación de cada padre en el momento de generar la "máscara de cruce", de tal manera que cuanto mayor sea la función de adaptación de un individuo, más probable sea heredar sus características, podríamos definir, véase Larrañaga y Poza [26], un operador de cruce basado en la función objetivo, en el cual la "máscara de cruce" se interpreta como una muestra aleatoria de tamaño l proveniente de una distribución de Bernouilli de parámetro

Función

donde (I super j sub t) y I(super i sub t) denotan los padres seleccionados para ser cruzados.

El concepto de "máscara de cruce" puede también servir para representar los cruces basados en un punto y basados en múltiples puntos, tal y como se muestra en Figura 11.

Sirag y Weiser, modifican el operador de cruce en el sentido del Simulated Annealing. De esta manera el operador de cruce se modifica definiendo un umbral de energía H. y una temperatura T, las cuales influencian la manera en la que se escogen los bits individuales. Según el operador propuesto el bit (i + 1)-ésimo se tomará del padre opuesto al que se ha tomado el bit i-ésimo, con probabilidad exp( . (tetha sub c)/T), donde T es el parámetro "temperatura" el cual, al igual que en Simulated Annealing, decrecerá lentamente por medio de un programa de enfriamiento. Con altas temperaturas el comportamiento se asemeja al del operador de cruce uniforme, es decir con probabilidad cercana a la unidad los bits se van escogiendo alternativamente de cada padre. Por otra parte cuando el valor

Figura 11

del parámetro temperatura se acerca a cero el hijo "resultante coincide prácticamente con uno de los padres.

Existen otros operadores de cruce específicos para un determinado problema como son, por ejemplo, los definidos para el problema del agente de comercio.

Por otra parte, la idea de que el cruce debería de ser más probable en algunas posiciones ha sido descrita por varios autores (Schaffer y Morishima, Holland, Davis, Levenick).

Mutaciones en los Algoritmos Geneticos

La mutación se considera un operador básico, que proporciona un pequeño elemento de aleatoriedad en la vecindad (entorno) de los individuos de la población. Si bien se admite que el operador de cruce es el responsable de efectuar la búsqueda a lo largo del espacio de posibles soluciones, también parece desprenderse de los experimentos efectuados por varios investigadores que el operador de mutación va ganando en importancia a medida que la población de individuos va convergiendo (Davis).

Schaffer y col. encuentran que el efecto del cruce en la búsqueda es inferior al que previamente se esperaba. Utilizan la denominada evolución primitiva, en la cual, el proceso evolutivo consta tan sólo de selección y mutación. Encuentran que dicha evolución primitiva supera con creces a una evolución basada exclusivamente en la selección y el cruce. Otra conclusión de su trabajo es que la determinación del valor óptimo de la probabilidad de mutación es mucho más crucial que el relativo a la probabilidad de cruce.

La búsqueda del valor óptimo para la probabilidad de mutación, es una cuestión que ha sido motivo de varios trabajos. Así, De Jong recomienda la utilización de una probabilidad de mutación del bit de (l super -1), siendo l la longitud del string. Schaffer y col. utilizan resultados experimentales para estimar la tasa óptima proporcional a l /(lambda super 0.9318),(l super 0.4535), donde lambda denota el número de individuos en la población.

Si bien en la mayoría de las implementaciones de Algoritmos Genéticos se asume que tanto la probabilidad de cruce como la de mutación permanecen constantes, algunos autores han obtenido mejores resultados experimentales modificando la probabilidad de mutación a medida que aumenta el número de iteraciones. Pueden consultarse los trabajos de Ackley, Bramlette, Fogarty y Michalewicz y Janikow.

Caracteristicas de los Algoritmos Geneticos

Un algoritmo genético puede presentar diversas variaciones, dependiendo de cómo se aplican los operadores genéticos (cruzamiento,mutación), de cómo se realiza la selección y de cómo se decide el reemplazo de los individuos para formar la nueva población. En general, el pseudocódigo consiste de los siguientes pasos:

Algoritmo genético i: inicialización, f(X): evaluación, ?: condición de término, Se: selección, Cr: cruzamiento, Mu: mutación, Re: reemplazo, X*: mejor solución.

• Inicialización: Se genera aleatoriamente la población inicial, que está constituida por un conjunto de cromosomas los cuales representan las posibles soluciones del problema. En caso de no hacerlo aleatoriamente, es importante garantizar que dentro de la población inicial, se tenga la diversidad estructural de estas soluciones para tener una representación de la mayor parte de la población posible o al menos evitar la convergencia prematura.
• Evaluación: A cada uno de los cromosomas de esta población se aplicará la función de aptitud para saber qué tan "buena" es la solución que se está codificando.
• Condición de término El AG se deberá detener cuando se alcance la solución óptima, pero ésta generalmente se desconoce, por lo que se deben utilizar otros criterios de detención. Normalmente se usan dos criterios: correr el AG un número máximo de iteraciones (generaciones) o detenerlo cuando no haya cambios en la población. Mientras no se cumpla la condición de término se hace lo siguiente:
  • Selección Después de saber la aptitud de cada cromosoma se procede a elegir los cromosomas que serán cruzados en la siguiente generación. Los cromosomas con mejor aptitud tienen mayor probabilidad de ser seleccionados.
  • Recombinación o Cruzamiento La recombinación es el principal operador genético, representa la reproducción sexual, opera sobre dos cromosomas a la vez para generar dos descendientes donde se combinan las características de ambos cromosomas padres.
  • Mutación modifica al azar parte del cromosoma de los individuos, y permite alcanzar zonas del espacio de búsqueda que no estaban cubiertas por los individuos de la población actual.
  • Reemplazo una vez aplicados los operadores genéticos, se seleccionan los mejores individuos para conformar la población de la generación siguiente

Evolución de los Algoritmos Geneticos

El origen de lo que se conoce como computación evolutiva hay que buscarlo en su razón de ser: los conocimientos sobre evolución se pueden aplicar en la resolución de problemas de optimización. Fue en las décadas de 1950 y 1960 cuando varios científicos, de modo independiente, comenzaron a estudiar los sistemas evolutivos, guiados por la intuición de que se podrían emplear como herramienta en problemas de optimización en ingeniería. La idea era “evolucionar” una población de candidatos a ser solución de un problema conocido, utilizando operadores inspirados en la selección natural y la variación genética natural.

Fue Rechenberg quien, en la década de 1960 (1965, 1973) introdujo las “estrategias evolutivas”, método que empleó para optimizar parámetros reales para ciertos dispositivos.

La misma idea fue desarrollada posteriormente por Schwefel (1975, 1977). El campo de las estrategias evolutivas ha permanecido como un área de investigación activa, cuyo desarrollo se produce, en su mayor parte,  de modo independiente al de los algoritmos genéticos (aunque recientemente se ha visto como las dos comunidades han comenzado ha colaborar). Fogel, Owens y  Walsh (1966), fueron los creadores de la “programación evolutiva”, una técnica en la cual las candidatas a soluciones a tareas determinadas, eran representadas por máquinas de estados finitos, cuyos diagramas de estados de transición se evolucionaban mediante mutación aleatoria, seleccionándose el que mejor aproximara. Una formulación más amplia de la programación evolutiva, es un campo de investigación que también continúa en activo (ver, por ejemplo, a Fogel y Altman 1993). Estas tres áreas, estrategias evolutivas, algoritmos genéticos, y programación evolutiva, son las que forman la columna vertebral de la Computación Evolutiva, y de ellas parten los caminos hacia  todos los campos de investigación inspirados en nuestros conocimientos sobre Evolución.

Pero muchos otros investigadores desarrollaron su trabajo en los algoritmos para la optimización y el aprendizaje inspirados en la evolución. Cabe resaltar nombres como los de Box (1957), Friedman (1959), Bledsoe (1961), Bremermann (1962), y Reed, Toombs y Baricelli (1967). Sin embargo, su trabajo no ha tenido, ni con mucho, la atención que han recibido las estrategias evolutivas, programación evolutiva, y los algoritmos genéticos.

Hay que recordar además a los biólogos evolucionistas que han utilizado el ordenador para simular la evolución para realizar experimentos controlados (Baricelli 1957, 1962; Fraser 1957 a,b; Martin y Coreman 1960). Pero habría que esperar hasta que la computación electrónica se desarrollara, para poder apreciar la consolidación definitiva de la computación evolutiva.

Centrémonos en los Algoritmos Genéticos. La primera mención del término, y la primera publicación sobre una aplicación del mismo, se deben a Bagley (1967), que diseñó algoritmos genéticos para buscar conjuntos de parámetros en funciones de evaluación de juegos, y los comparó con los algoritmos de  correlación, procedimientos de aprendizaje modelizados después de los algoritmos de pesos variantes de ese periodo. Pero es otro científico el considerado creador de los Algoritmos Genéticos: John Holland, que los desarrolló, junto a sus alumnos y colegas, durante las décadas de 1960 y 1970. En contraste con las estrategias evolutivas y la programación evolutiva, el propósito original de Holland no era diseñar algoritmos para resolver problemas concretos, sino estudiar, de un modo formal, el fenómeno de la adaptación tal y como ocurre en la naturaleza, y desarrollar vías de extrapolar esos mecanismos de adaptación  natural a los sistemas computacionales.

El libro que Holland escribió en 1975  Adaptación en Sistemas Naturales y Artificiales presentaba el algoritmo genético como una abstracción de la evolución biológica, y proporcionaba el entramado teórico para la  adaptación bajo el algoritmo genético. El Algoritmo Genético de Holland era un método para desplazarse, de una población de cromosomas (bits) a una nueva población,  utilizando un sistema similar a la “selección natural” junto con los operadores de  cruces, mutaciones e  inversión inspirados en la genética. En este primitivo algoritmo, cada cromosoma consta de genes (bits), y cada uno de ellos es una muestra de un alelo particular (0 o 1). El operador de selección escoge, entre los cromosomas de la población, aquellos con capacidad de reproducción, y entre éstos, los que sean más “compatibles”, producirán más descendencia que el resto. El de cruce extrae partes de dos cromosomas, imitando la combinación biológica de dos cromosomas aislados (gametos). La mutación se encarga de cambiar, de modo aleatorio, los valores del alelo en algunas localizaciones del cromosoma; y, por último, la inversión, invierte el orden de una sección contigua del cromosoma , recolocando por tanto el orden en el que se almacenan los genes.

La mayor innovación de Holland fue la  de introducir un algoritmo basado en poblaciones con cruces, mutaciones e inversiones. Es más, Holland fue el primero en intentar colocar la computación evolutiva sobre una base teórica firme (Holland, 1975).

Hasta hace poco, esta base teórica, fundamentada en la noción de “esquemas”, fue la estructura sobre la que se edificaron la mayoría de los trabajos teóricos sobre algoritmos genéticos en las décadas siguientes.

En estos últimos años se ha generado una amplia interacción entre los investigadores de varios métodos de computación evolutiva, rompiéndose las fronteras entre algoritmos genéticos, estrategias evolutivas y programación evolutiva. Como consecuencia, en la actualidad, el término “algoritmo genético” se utiliza para designar un concepto mucho más amplio del que concibió Holland.

Origenes de los Algoritmos Geneticos

Los algoritmos genéticos (AG), fueron inventados en 1975 por John Holland, de la Universidad de Michigan. Los AG son, simplificando, algoritmos de optimización, es decir, tratan de encontrar la mejor solución a un problema dado entre un conjunto de soluciones posibles. Los mecanismos de los que se valen los AG para llevar a cabo esa búsqueda pueden verse como una metáfora de los procesos de evolución biológica.

John Holland desde pequeño, se preguntaba cómo logra la naturaleza, crear seres cada vez más perfectos. No sabía la respuesta, pero tenía una cierta idea de como hallarla: tratando de hacer pequeños modelos de la naturaleza, que tuvieran alguna de sus características, y ver cómo funcionaban, para luego extrapolar sus conclusiones a la totalidad.

Fue a principios de los 60, en la Universidad de Michigan en Ann Arbor, donde, dentro del grupo Logic of Computers, sus ideas comenzaron a desarrollarse y a dar frutos. Y fue, además, leyendo un libro escrito por un biólogo evolucionista, R. A. Fisher, titulado La teoría genética de la selección natural, como comenzó a descubrir los medios de llevar a cabo sus propósitos de comprensión de la naturaleza. De ese libro aprendió que la evolución era una forma de adaptación más potente que el simple aprendizaje, y tomó la decisión de aplicar estas ideas para desarrollar programas bien adaptados para un fin determinado.

En esa universidad, Holland impartía un curso titulado Teoría de sistemas adaptativos. Dentro de este curso, y con una participación activa por parte de sus estudiantes, fue donde se crearon las ideas que más tarde se convertirían en los AG. Por tanto, cuando Holland se enfrentó a los AG, los objetivos de su investigación fueron dos: imitar los procesos adaptativos de los sistemas naturales, y diseñar sistemas artificiales (normalmente programas) que retengan los mecanismos importantes de los sistemas naturales.

Unos 15 años más adelante, David Goldberg, actual delfín de los AG, conoció a Holland, y se convirtió en su estudiante. Goldberg era un ingeniero industrial trabajando en diseño de pipelines, y fue uno de los primeros que trató de aplicar los AG a problemas industriales. Aunque Holland trató de disuadirle, porque pensaba que el problema era excesivamente complicado como para aplicarle AG, Goldberg consiguió lo que quería, escribiendo un AG en un ordenador personal Apple II. Estas y otras aplicaciones creadas por estudiantes de Holland convirtieron a los AG en un campo con bases suficientemente aceptables como para celebrar la primera conferencia en 1985, ICGA´85.

Programación Evolutiva

La programación evolutiva (PE) es una rama de la computación evolutiva. La programación evolutiva es prácticamente una variación de los algoritmos genéticos, donde lo que cambia es la representación de los individuos. En el caso de la PE los individuos son ternas(tripletas) cuyos valores representan estados de un autómata finito. Cada terna está formada por:

§                    El valor del estado actual

§                    un símbolo del alfabeto utilizado

§                    el valor del nuevo estado.

Estos valores se utilizan, como en un autómata finito, de la siguiente manera: Teniendo el valor del estado actual en el que nos encontramos, tomamos el valor del símbolo actual y si es el símbolo de nuestra terna, nos debemos mover al nuevo estado.

Básicamente así funciona y así se representan los individuos en la PE. Evidentemente las funciones de selección, Cruce (crossover) y mutación deben variar para adaptarse y funcionar con una población de individuos de este tipo.