Informática evolutiva:

Algoritmos genéticos

Juan Julián Merelo Guervós

http://geneura.ugr.es/~jmerelo

4 Algoritmo genético simple.

4.1 Introducción

John Holland desde pequeño, se preguntaba cómo logra la naturaleza, crear seres cada vez más perfectos (aunque, como se ha visto, esto no es totalmente cierto, o en todo caso depende de qué entienda uno por perfecto). Lo curioso era que todo se lleva a cabo a base de interacciones locales entre individuos, y entre estos y lo que les rodea. 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. De hecho, ya de pequeño hacía simulaciones de batallas célebres con todos sus elementos: copiaba mapas y los cubría luego de pequeños ejércitos que se enfrentaban entre sí.

En los años 50 entró en contacto con los primeros ordenadores, donde pudo llevar a cabo algunas de sus ideas, aunque no se encontró con un ambiente intelectual fértil para propagarlas. 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 algoritmos genéticos.

Por tanto, cuando Holland se enfrentó a los algoritmos genéticos, los objetivos de su investigación fueron dos:

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

4.2 Anatomía de un algoritmo genético simple

Los algoritmos genéticos son métodos sistemáticos para la resolución de problemas de búsqueda y optimización que aplican a estos los mismos métodos de la evolución biológica: selección basada en la población, reproducción sexual y mutación.

Los algoritmos genéticos son métodos de optimización, que tratan de resolver el mismo conjunto de problemas que se ha contemplado anteriormente, es decir, hallar (xi,...,xn) tales que F(xi,...,xn) sea máximo. En un algoritmo genético, tras parametrizar el problema en una serie de variables, (xi,...,xn) se codifican en un cromosoma. Todas los operadores utilizados por un algoritmo genético se aplicarán sobre estos cromosomas, o sobre poblaciones de ellos. En el algoritmo genético va implícito el método para resolver el problema; son solo parámetros de tal método los que están codificados, a diferencia de otros algoritmos evolutivos como la programación genética. Hay que tener en cuenta que un algoritmo genético es independiente del problema, lo cual lo hace un algoritmo robusto, por ser útil para cualquier problema, pero a la vez débil, pues no está especializado en ninguno.

Las soluciones codificadas en un cromosoma compiten para ver cuál constituye la mejor solución (aunque no necesariamente la mejor de todas las soluciones posibles). El ambiente, constituido por las otras camaradas soluciones, ejercerá una presión selectiva sobre la población, de forma que sólo los mejor adaptados (aquellos que resuelvan mejor el problema) sobrevivan o leguen su material genético a las siguientes generaciones, igual que en la evolución de las especies. La diversidad genética se introduce mediante mutaciones y reproducción sexual.

En la Naturaleza lo único que hay que optimizar es la supervivencia, y eso significa a su vez maximizar diversos factores y minimizar otros. Un algoritmo genético, sin embargo, se usará habitualmente para optimizar sólo una función, no diversas funciones relacionadas entre sí simultáneamente. La optimización que busca diferentes objetivos simultáneamente, denominada multimodal o multiobjetivo, también se suele abordar con un algoritmo genético especializado.

Por lo tanto, un algoritmo genético consiste en lo siguiente: hallar de qué parámetros depende el problema, codificarlos en un cromosoma, y se aplican los métodos de la evolución: selección y reproducción sexual con intercambio de información y alteraciones que generan diversidad. En las siguientes secciones se verán cada uno de los aspectos de un algoritmo genético.

4.3 Codificación de las variables

Los algoritmos genéticos requieren que el conjunto se codifique en un cromosoma. Cada cromosoma tiene varios genes, que corresponden a sendos parámetros del problema. Para poder trabajar con estos genes en el ordenador, es necesario codificarlos en una cadena, es decir, una ristra de símbolos (números o letras) que generalmente va a estar compuesta de 0s y 1s.

Por ejemplo, en esta cadena de bits, el valor del parámetro p1 ocupará las posiciones 0 a 2, el p2 las 3 a 5, etcétera, como aparece en la tabla 2. El número de bits usado para cada parámetro dependerá de la precisión que se quiera en el mismo o del número de opciones posibles (alelos) que tenga ese parámetro. Por ejemplo, si se codifica una combinación del Mastermind, cada gen tendrá tantas opciones como colores halla, el número de bits elegido será el log2(número de colores).

Hay otras codificaciones posibles, usando alfabetos de diferente cardinalidad; sin embargo, uno de los resultados fundamentales en la teoría de algoritmos genéticos, el teorema de los esquemas, afirma que la codificación óptima, es decir, aquella sobre la que los algoritmos genéticos funcionan mejor, es aquella que tiene un alfabeto de cardinalidad 2.

Aquí se está codificando cada parámetro como un número entero de n bits. En realidad, se puede utilizar cualquier otra representación interna: bcd, código Gray y codificación en forma de números reales, por ejemplo.

La mayoría de las veces, una codificación correcta es la clave de una buena resolución del problema. Generalmente, la regla heurística que se utiliza es la llamada regla de los bloques de construcción, es decir, parámetros relacionados entre sí deben de estar cercanos en el cromosoma. Por ejemplo, si queremos codificar los pesos de una red neuronal, una buena elección será poner juntos todos los pesos que salgan de la misma neurona de la capa oculta (también llamada codificación fregona), como se indica en la figura. En esta, todos los pesos señalados con trazo doble se codifican mediante grupos de bits o bytes sucesivos en el cromosoma.

En todo caso, se puede ser bastante creativo con la codificación del problema, teniendo siempre en cuenta la regla anterior. Esto puede llevar a usar cromosomas bidimensionales, o tridimensionales, o con relaciones entre genes que no sean puramente lineales de vecindad. En algunos casos, cuando no se conoce de antemano el número de variables del problema, caben dos opciones: codificar también el número de variables, fijando un número máximo, o bien, lo cual es mucho más natural, crear un cromosoma que pueda variar de longitud. Para ello, claro está, se necesitan operadores genéticos que alteren la longitud.

Normalmente, la codificación es estática, pero en casos de optimización numérica, el número de bits dedicados a codificar un parámetro puede variar, o incluso lo que representen los bits dedicados a codificar cada parámetro. Algunos paquetes de algoritmos genéticos adaptan automáticamente la codificación según van convergiendo los bits menos significativos de una solución.

4.4 Algoritmo genético propiamente dicho

Para comenzar la competición, se generan aleatoriamente una serie de cromosomas. El algoritmo genético procede de la forma siguiente:

Algoritmo genético

  1. Evaluar la puntuación (fitness) de cada uno de los genes.
  2. Permitir a cada uno de los individuos reproducirse, de acuerdo con su puntuación.
  3. Emparejar los individuos de la nueva población, haciendo que intercambien material genético, y que alguno de los bits de un gen se vea alterado debido a una mutación espontánea.

Cada uno de los pasos consiste en una actuación sobre las cadenas de bits, es decir, la aplicación de un operador a una cadena binaria. Se les denominan, por razones obvias, operadores genéticos, y hay tres principales: selección, crossover o recombinación y mutación; aparte de otros operadores genéticos no tan comunes, todos ellos se verán a continuación.

Un algoritmo genético tiene también una serie de parámetros que se tienen que fijar para cada ejecución, como los siguientes:

4.5 Evaluación y selección

Durante la evaluación, se decodifica el gen, convirtiéndose en una serie de parámetros de un problema, se halla la solución del problema a partir de esos parámetros, y se le da una puntuación a esa solución en función de lo cerca que esté de la mejor solución. A esta puntuación se le llama fitness.

Por ejemplo, supongamos que queremos hallar el máximo de la función , una parábola invertida con el máximo en x=1. En este caso, el único parámetro del problema es la variable x. La optimización consiste en hallar un x tal que F(x) sea máximo. Crearemos, pues, una población de cromosomas, cada uno de los cuales contiene una codificación binaria del parámetro x. Lo haremos de la forma siguiente: cada byte, cuyo valor está comprendido entre 0 y 255, se transformará para ajustarse al intervalo [-1,1], donde queremos hallar el máximo de la función.

Valor binario

Decodificación Evaluación f(x)
10010100 21 0,9559
10010001 19 0,9639
101001 -86 0,2604
1000101 -58 0,6636

El fitness determina siempre los cromosomas que se van a reproducir, y aquellos que se van a eliminar, pero hay varias formas de considerarlo para seleccionar la población de la siguiente generación:

Una vez evaluado el fitness, se tiene que crear la nueva población teniendo en cuenta que los buenos rasgos de los mejores se transmitan a esta. Para ello, hay que seleccionar a una serie de individuos encargados de tan ardua tarea. Y esta selección, y la consiguiente reproducción, se puede hacer de dos formas principales:

4.6 Crossover

Consiste en el intercambio de material genético entre dos cromosomas (a veces más, como el operador orgía propuesto por Eiben et al.). El crossover es el principal operador genético, hasta el punto que se puede decir que no es un algoritmo genético si no tiene crossover, y, sin embargo, puede serlo perfectamente sin mutación, según descubrió Holland. El teorema de los esquemas confía en él para hallar la mejor solución a un problema, combinando soluciones parciales.

Para aplicar el crossover, entrecruzamiento o recombinación, se escogen aleatoriamente dos miembros de la población. No pasa nada si se emparejan dos descendiente de los mismos padres; ello garantiza la perpetuación de un individuo con buena puntuación (y, además, algo parecido ocurre en la realidad; es una práctica utilizada, por ejemplo, en la cría de ganado, llamada inbreeding, y destinada a potenciar ciertas características frente a otras). Sin embargo, si esto sucede demasiado a menudo, puede crear problemas: toda la población puede aparecer dominada por los descendientes de algún gen, que, además, puede tener caracteres no deseados. Esto se suele denominar en otros métodos de optimización atranque en un mínimo local, y es uno de los principales problemas con los que se enfrentan los que aplican algoritmos genéticos.

En cuanto al teorema de los esquemas, se basa en la noción de bloques de construcción. Una buena solución a un problema está constituida por unos buenos bloques, igual que una buena máquina está hecha por buenas piezas. El crossover es el encargado de mezclar bloques buenos que se encuentren en los diversos progenitores, y que serán los que den a los mismos una buena puntuación. La presión selectiva se encarga de que sólo los buenos bloques se perpetúen, y poco a poco vayan formando una buena solución. El teorema de los esquemas viene a decir que la cantidad de buenos bloques se va incrementando con el tiempo de ejecución de un algoritmo genético, y es el resultado teórico más importante en algoritmos genéticos.

El intercambio genético se puede llevar a cabo de muchas formas, pero hay dos grupos principales

4.7 Mutación

En la Evolución, una mutación es un suceso bastante poco común (sucede aproximadamente una de cada mil replicaciones), como ya se ha visto anteriormente. En la mayoría de los casos las mutaciones son letales, pero en promedio, contribuyen a la diversidad genética de la especie. En un algoritmo genético tendrán el mismo papel, y la misma frecuencia (es decir, muy baja).

Una vez establecida la frecuencia de mutación, por ejemplo, uno por mil, se examina cada bit de cada cadena cuando se vaya a crear la nueva criatura a partir de sus padres (normalmente se hace de forma simultánea al crossover). Si un número generado aleatoriamente está por debajo de esa probabilidad, se cambiará el bit (es decir, de 0 a 1 o de 1 a 0). Si no, se dejará como está. Dependiendo del número de individuos que haya y del número de bits por individuo, puede resultar que las mutaciones sean extremadamente raras en una sola generación.

No hace falta decir que no conviene abusar de la mutación. Es cierto que es un mecanismo generador de diversidad, y, por tanto, la solución cuando un algoritmo genético está estancado, pero también es cierto que reduce el algoritmo genético a una búsqueda aleatoria. Siempre es más conveniente usar otros mecanismos de generación de diversidad, como aumentar el tamaño de la población, o garantizar la aleatoriedad de la población inicial.

Este operador, junto con la anterior y el método de selección de ruleta, constituyen un algoritmo genético simple, sga, introducido por Goldberg en su libro.

4.8 Otros operadores

No se usan en todos los problemas, sino sólo en algunos, y en principio su variedad es infinita. Generalmente son operadores que exploran el espacio de soluciones de una forma más ordenada, y que actúan más en las últimas fases de la búsqueda, en la cual se pasa de soluciones "casi buenas" a "buenas" soluciones.

4.8.1 Cromosomas de longitud variable

Hasta ahora se han descrito cromosomas de longitud fija, donde se conoce de antemano el número de parámetros de un problema. Pero hay problemas en los que esto no sucede. Por ejemplo, en un problema de clasificación, donde dado un vector de entrada, queremos agruparlo en una serie de clases, podemos no saber siguiera cuantas clases hay. O en diseño de redes neuronales, puede que no se sepa (de hecho, nunca se sabe) cuántas neuronas se van a necesitar. Por ejemplo, en un perceptrón hay reglas que dicen cuantas neuronas se deben de utilizar en la capa oculta; pero en un problema determinado puede que no haya ninguna regla heurística aplicable; tendremos que utilizar los algoritmos genéticos para hallar el número óptimo de neuronas. En este caso, si utilizamos una codificación fregona, necesitaremos un locus para cada neurona de la capa oculta, y el número de locus variará dependiendo del número de neuronas de la capa oculta.

En estos casos, necesitamos dos operadores más: añadir y eliminar. Estos operadores se utilizan para añadir un gen, o eliminar un gen del cromosoma. La forma más habitual de añadir un locus es duplicar uno ya existente, el cual sufre mutación y se añade al lado del anterior. En este caso, los operadores del algoritmo genético simple (selección, mutación, crossover) funcionarán de la forma habitual, salvo, claro está, que sólo se hará crossover en la zona del cromosoma de menor longitud.

Estos operadores permiten, además, crear un algoritmo genético de dos niveles: a nivel de cromosoma y a nivel de gen. Supongamos que, en un problema de clasificación, hay un gen por clase. Se puede asignar una puntuación a cada gen en función del número de muestras que haya clasificado correctamente. Al aplicar estos operadores, se duplicarán los alelos con mayor puntuación, y se eliminarán aquellos que hayan obtenido menor puntuación, o cuya puntuación sea nula.

Por ejemplo, en un problema de clasificación en el que hay que clasificar los puntos del cuadrado [0,10]x[0,10] en dos clases, 1 y 2, que no son linealmente separables. Inicialmente se desconoce cuantos vectores son necesarios para clasificar estas clases. El algoritmo genético es capaz de hallar un número óptimo de vectores, a cada uno de los cuales se asigna una etiqueta de clase, tales que el error se hace mínimo, en este caso 4 vectores para la primera clase y 5 para la 2ª. Cada cromosoma estará compuesto por un diccionario o conjunto de vectores, cada uno de los cuales tiene asignada una etiqueta de clase.

4.8.2 Operadores de nicho (ecológico)

Otros operadores importantes son los operadores de nicho. Estos operadores están encaminados a mantener la diversidad genética de la población, de forma que cromosomas similares sustituyan sólo a cromosomas similares, y son especialmente útiles en problemas con muchas soluciones; un algoritmo genético con estos operadores es capaz de hallar todos los máximos, dedicándose cada especie a un máximo. Más que operadores genéticos, son formas de enfocar la selección y la evaluación de la población.

Uno de las formas de llevar esto a cabo ya ha sido nombrada, la introducción del crowding (apiñamiento). Otra forma es introducir una función de compartición o sharing, que indica cuán similar es un cromosoma al resto de la población. La puntuación de cada individuo se dividirá por esta función de compartición, de forma que se facilita la diversidad genética y la aparición de individuos diferentes.

También se pueden restringir los emparejamientos, por ejemplo, a aquellos cromosomas que sean similares. Para evitar las malas consecuencias del inbreeding que suele aparecer en poblaciones pequeñas, estos periodos se intercalan con otros periodos en los cuales el emparejamiento es libre.

4.8.3 Operadores especializados

En una serie de problemas hay que restringir las nuevas soluciones generadas por los operadores genéticos, pues no todas las soluciones generadas van a ser válidas, sobre todo en los problemas con restricciones. Por ello, se aplican operadores que mantengan la estructura del problema. Otros operadores son simplemente generadores de diversidad, pero la generan de una forma determinada:

4.8.4 Aplicando operadores genéticos

En toda ejecución de un algoritmo genético hay que decidir con qué frecuencia se va a aplicar cada uno de los algoritmos genéticos; en algunos casos, como en la mutación o el crossover uniforme, se debe de añadir algún parámetro adicional, que indique con qué frecuencia se va a aplicar dentro de cada gen del cromosoma. La frecuencia de aplicación de cada operador estará en función del problema; teniendo en cuenta los efectos de cada operador, tendrá que aplicarse con cierta frecuencia o no. Generalmente, la mutación y otros operadores que generen diversidad se suele aplicar con poca frecuencia; la recombinación se suele aplicar con frecuencia alta.

En general, la frecuencia de los operadores no varía durante la ejecución del algoritmo, pero hay que tener en cuenta que cada operador es más efectivo en un momento de la ejecución. Por ejemplo, al principio, en la fase denominada de exploración, los más eficaces son la mutación y la recombinación; posteriormente, cuando la población ha convergido en parte, la recombinación no es útil, pues se está trabajando con individuos bastante similares, y es poca la información que se intercambia. Sin embargo, si se produce un estancamiento, la mutación tampoco es útil, pues está reduciendo el algoritmo genético a una búsqueda aleatoria; y hay que aplicar otros operadores. En todo caso, se pueden usar operadores especializados.

Por ejemplo, en el algoritmo genético para jugar al MasterMind (http://kal-el.ugr.es/mastermind), se usan varios operadores genéticos: transposición, mutación y entrecruzamiento. Sin embargo, la mutación y el crossover dejan de ser efectivos en el momento que la combinación que se ha jugado tiene los colores correctos, y en cualquier caso la tasa de mutación tendrá que ser mayor cuantos menos colores haya averiguados; por eso las tasas varían durante la ejecución, convirtiéndose eventualmente en 0.

4.9 El zen y los algoritmos genéticos

Este es el título de un artículo que publicó Goldberg en la conferencia sobre algoritmos genéticos celebrada en el año 89 (icga 89), en donde da una serie de consejos para que se apliquen los algoritmos genéticos debidamente, y avisa a aquellos que se quieren apartar de la ortodoxia. Estos consejos son los siguientes

Deja que la Naturaleza sea tu guía: dado que la mayoría de los problemas a los que se van a aplicar los algoritmos genéticos son de naturaleza no lineal, es mejor actuar como lo hace la naturaleza, aunque intuitivamente pueda parecer la forma menos acertada. Si queremos desarrollar sistemas no lineales que busquen y aprendan, mejor que comencemos (como mínimo) imitando a sistemas que funcionan (Goldberg). Y estos sistemas se hallan en la naturaleza.

Cuidado con el asalto frontal: a veces se plantea el problema de pérdida de diversidad genética en una población de cromosomas. Hay dos formas de resolver este problema: aumentar el ritmo de mutación, lo cual equivale a convertir un algoritmo genético en un algoritmo de búsqueda aleatoria, o bien introducir mecanismos como el sharing, por el cual el fitness de un individuo se divide por el número de individuos similares a él. Este segundo método, más parecido al funcionamiento de la naturaleza, en la cual cada individuo, por bueno que sea, tiene que compartir recursos con aquellos que hayan resuelto el problema de la misma forma, funciona mucho mejor. Otro caso que surge a menudo en los grupos de discusión de Usenet es el tratar de optimizar AGs mediante AGs; es mucho mejor tratar de entender el problema que acercarse a él de esta manera.

Respeta la criba de esquemas: para ello, lo ideal es utilizar alfabetos con baja cardinalidad (es decir, con pocas letras) como el binario.

No te fíes de la autoridad central: la Naturaleza actúa de forma distribuida, por tanto, se debe de minimizar la necesidad de operadores que "vean" a da la población. Ello permite, además, una fácil paralelización del algoritmo genético. Por ejemplo, en vez de comparar el fitness de un individuo con todos los demás, se puede comparar sólo con los vecinos, es decir, aquellos que estén, de alguna forma, situados cerca de él.

5 Práctica 1: Algoritmos genéticos con el programa gwin2

Gwin2, que aparece en casi todos sitios como WinGA, es un programa que permite ejecutar algoritmos genéticos simples, cambiar sus parámetros, y que incluso admite ampliaciones mediante la programación de nuevas funciones en Pascal. Fue realizado por I.R. Munro, de la Universidad de Hertfordshire. Está disponible en la página web Zooland, y en el sitio de ftp del autor.

WinGA es un programa que funciona en Windows 3.1 y Windows 95; según el autor necesita como mínimo 4 megas para funcionar. La práctica consistirá en ver los efectos de los diferentes parámetros en la ejecución de un algoritmo genético simple; en este caso, los únicos operadores admitidos son mutación y crossover, y dos tipos de selección diferentes. Existen unas 10 funciones ya programadas, pero, en el manual indica como se pueden programar más.

  1. En el primer paso, se carga un fichero .dll usando la opción FunctionsLoad DLL. Cada .dll que contiene el código que evalúa las funciones; hay dos: example1.dll, y master1.dll, se puee escoger el segundo, que contiene más funciones. De ellas, se puede escoger Sphere Model, por ejemplo, que maximiza el cuadrado de una suma de parámetros; el número de parámetros es el que pide en el cuadro de diálogo.
  2. Añadir views, diferentes ventanas que contienen información sobre el algoritmo genético que se está ejecutando. Para ello, se elige la opción Views del menú y sucesivamente se van abriendo las cuatro ventanas.
  3. Seleccionar los parámetros genéticos, y comprobar posteriormente el estado de lo seleccionado. Esto se hace desde el menú Setup. Se puede elegir, por ejemplo, SelectionRemainder Stochastic, CombinationsOne point crossover, con la misma tasa, que indica la cantidad de la población a la que afecta esa operación, y Normal Mutation con la misma tasa.

Eligiendo SetupStatus aparece un cuadro que indica los parámetros elegidos.

  1. Establecer el fichero de registro, en el cual se guardarán los datos de la ejecución actual, usando la opción ReportsLog file. En este fichero se puede guardar, por ejemplo, el mejor cromosoma, en formato binario, y darle un nombre cualquiera, como primero.log.
  2. En este momento ya se puede ejecutar el algoritmo genético, eligiendo la opción Run, y se pueden ver el efecto de los diferentes parámetros sobre la ejecución del algoritmo. Probar, por ejemplo, lo siguiente:
  3. Cambiar la mutación, y ver el efecto sobre la diversidad, es decir, el número de cromosomas diferentes que aparece en el gráfico de Current Distribution.
  4. Reducir el crossover, y comprobar su efecto sobre la velocidad de convergencia. Probar también a cambiar el tipo de crossover, que en este tipo de problema no tendrá mucho efecto sobre el resultado.
  5. Cambiar el tamaño de la población, hasta encontrar el mínimo necesario para que el algoritmo converja en un número de generaciones razonable; cambiar también el número de generaciones.
  6. Cambiar el tipo de selección; en la selección de Tournament o torneo siempre se seleccionan los mejores, sin embargo, en la estocástica pueden desaparecer de la población.

Ejercicio: Encontrar la combinación de parámetros que halla el mínimo de la función anterior, y de alguna otra función del ejemplo, en un mínimo de tiempo. Tener en cuenta que, hasta cierto punto, se pueden intercambiar número de generaciones por el tamaño de la población.

6 Práctica 2: Algoritmo genético interactivo en Java

En esta página Web, situada en el sitio denominado Evolvica (universidad de Erlangen), al cual se puede acceder desde la página de aplicaciones evolutivas en Java, http://www.systemtechnik.tu-ilmenau.de/~pohlheim/EA_Java/ea_java.html, se ejecuta un algoritmo genético interactivo. Para ello, es necesario acceder a la dirección Web -- mediante un browser que admita Java, como el Netscape Navigator 2 o el Internet Explorer 3.

En esta página, se hacen evolucionar formas bajo control del usuario; el usuario elige primero una forma hacia la cual tiende la evolución, y luego, en cada generación elige las formas que mutarán para dar finalmente, con un poco de suerte, la que se ha elegido inicialmente.

Se pueden modificar los parámetros, como por ejemplo, la tasa de mutación y el radio de mutación, y ver como varían las formas generadas.

Ejercicio: Por supuesto, conseguir generar la forma inicial en un mínimo de generaciones.

7 Práctica 3: Algoritmos genéticos simples en Java

En este applet, programado por Ramsey et al. de la Universidad de Arizona, que se halla en la dirección Web http://ai.bpa.arizona.edu/~mramsey/ga.html, se muestra un algoritmo genético simple que trata de hallar el máximo global de una función con muchos máximos y una sola variable. El valor de esa variable para los diferentes elementos de la población aparece como líneas verticales de color. Se puede variar, por ejemplo, la tasa de mutación; en problemas tan pequeños el crossover no tiene tanta importancia.

8 Práctica 4: Programación de un algoritmo genético simple

En esta práctica, se trata de programar un algoritmo genético simple, que incluya selección de tipo rueda de ruleta, mutación y entrecruzamiento de dos puntos. Utilizar cualquier lenguaje de programación (PERL, Java, Pascal, C, C++, Tcl/Tk), y usar como función de evaluación alguna función simple, como la suma total de los componentes del cromosoma. Comparar la representación binaria con la representación de números reales, y comprobar la eficiencia de cada uno de ellos.

Ver el resto del tutorial:

Juan Julian Merelo Guervos