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:
- imitar los procesos adaptativos de los sistemas naturales, y
- diseñar sistemas artificiales (normalmente programas) que retengan los mecanismos importantes de los sistemas naturales.
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:- Evaluar la puntuación (fitness) de cada uno de los genes.
- Permitir a cada uno de los individuos reproducirse, de acuerdo con su puntuación.
- 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.
Un algoritmo genético tiene también una serie de parámetros que se tienen que fijar para cada ejecución, como los siguientes:
- Tamaño de la población: debe de ser suficiente para garantizar la diversidad de las soluciones, y, además, tiene que crecer más o menos con el número de bits del cromosoma, aunque nadie ha aclarado cómo tiene que hacerlo. Por supuesto, depende también del ordenador en el que se esté ejecutando.
- Condición de terminación: lo más habitual es que la condición de terminación sea la convergencia del algoritmo genético o un número prefijado de generaciones.
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:
- Usar el orden, o rango, y hacer depender la probabilidad de permanencia o evaluación de la posición en el orden.
- Aplicar una operación al fitness para
escalarlo; como por ejemplo el escalado
sigma. En este esquema el fitness se
escala
- En algunos casos, el fitness no es una sola cantidad, sino diversos números, que tienen diferente consideración. Basta con que tal fitness forme un orden parcial, es decir, que se puedan comparar dos individuos y decir cuál de ellos es mejor. Esto suele suceder cuando se necesitan optimizar varios objetivos.
- Basado en el rango: en este esquema se mantiene un porcentaje de la población, generalmente la mayoría, para la siguiente generación. Se coloca toda la población por orden de fitness, y los M menos dignos son eliminados y sustituidos por la descendencia de alguno de los M mejores con algún otro individuo de la población. A este esquema se le pueden aplicar otros criterios; por ejemplo, se crea la descendencia de uno de los paladines/amazonas, y esta sustituye al más parecido entre los perdedores. Esto se denomina crowding, y fue introducido por DeJong. En nuestro caso, se eliminaría el cromosoma número 3, y se sustituiría por un descendiente del cromosoma número 2 y otro aleatorio, escogido entre el 1 y el 4. En realidad, para este esquema se escoge un crowding factor, CF. Cuando nace una nueva criatura, se seleccionan CF individuos de la población, y se elimina al más parecido a la nueva criatura. Una variante de este es el muestreado estocástico universal, que trata de evitar que los individuos con más fitness copen la población; en vez de dar la vuelta a una ruleta con una ranura, da la vuelta a la ruleta con N ranuras, tantas como la población; de esta forma, la distribución estadística de descendientes en la nueva población es más parecida a la real.
- Rueda de ruleta: se crea un pool genético formado por cromosomas de la generación actual, en una cantidad proporcional a su fitness. Si la proporción hace que un individuo domine la población, se le aplica alguna operación de escalado. Dentro de este pool, se cogen parejas aleatorias de cromosomas y se emparejan, sin importar incluso que sean del mismo progenitor (para eso están otros operadores, como la mutación). Hay otras variantes: por ejemplo, en la nueva generación se puede incluir el mejor representante de la generación actual. En este caso, se denomina método elitista.
- Selección de torneo: se escogen aleatoriamente un número T de individuos de la población, y el que tiene puntuación mayor se reproduce, sustituyendo su descendencia al que tiene menor puntuación.
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
- Crossover n-puntos: los dos cromosomas se cortan por n puntos, y el material genético situado entre ellos se intercambia. Lo más habitual es un crossover de un punto o de dos puntos.
- Crossover uniforme: se genera un patrón aleatorio de 1s y 0s, y se intercambian los bits de los dos cromosomas que coincidan donde hay un 1 en el patrón. O bien se genera un número aleatorio para cada bit, y si supera una determinada probabilidad se intercambia ese bit entre los dos cromosomas.
- Crossover especializados: en algunos problemas, aplicar aleatoriamente el crossover da lugar a cromosomas que codifican soluciones inválidas; en este caso hay que aplicar el crossover de forma que genere siempre soluciones válidas. Un ejemplo de estos son los operadores de crossover usados en el problema del viajante.
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:
- Zap: en vez de cambiar un solo bit de un cromosoma, cambia un gen completo de un cromosoma.
- Creep: este operador aumenta o disminuye en 1 el valor de un gen; sirve para cambiar suavemente y de forma controlada los valores de los genes.
- Transposición: similar al crossover y a la recombinación genética, pero dentro de un solo cromosoma; dos genes intercambian sus valores, sin afectar al resto del cromosoma. Similar a este es el operador de eliminación-reinserción, en el que un gen cambia de posición con respecto a los demás.
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
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.
- 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.
- 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.
- 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.
- 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.
- 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:
- 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.
- 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.
- 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.
- 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.
6 Práctica 2: Algoritmo genético interactivo en Java
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
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.