Source: http://kal-el.ugr.es/~jmerelo/tutoriales/heuristics101/
Timestamp: 2018-01-16 17:24:25+00:00

Document:
Si un problema está formulado de forma unívoca, y el espacio de todas las soluciones posibles es conocido, un método de búsqueda trata de encontrar las soluciones o soluciones que satisfagan el enunciado del problema. Dicho así parece una tautología, pero no todos los problemas son problemas de búsqueda, ni todos los espacios de búsqueda se pueden definir también de forma unívoca.
El libro que sirve de referencia para este capítulo es Modern Heuristics, de Zbigniew Michalewicz, David B. Fogel . Tiene un enfoque moderno, como su título indica, a la resolución de problemas, incluyendo todo tipo de técnicas subsimbólicas, y usando una serie de problemas de referencia (recorrido del viajante, satisfiabilidad máxima y problema multimodal de optimización numérica) para aplicarle esas técnicas y ver su funcionamiento.
Pero si resulta que efectivamente, un problema se puede efectuar como problema de búsqueda, en muchos casos se puede reducir a un problema de hallar un máximo o mínimo, o sea, un óptimo. Sólo va a funcionar esto en el caso de que se pueda calcular la bondad de una solución: la solución del problema será aquella, o aquellas, que optimicen una función de bondad, ajuste, evaluación o fitness; en muchos casos, por lo tanto, un problema de búsqueda se puede reducir a un problema de optimización (maximización o minimización). No siempre es así, pero cuando sucede hay que congratularse y celebrarlo adecuadamente. La mayor parte de los problemas con los que trataremos en este tutorial serán problemas de optimización.
El lector sería capaz de enumerar algún problema de búsquda que no sea optimización? Por ejemplo, los problemas de búsqueda interativos, en los cuales se busca algo a base de las pistas que da un usuario; o incluso el ajedrez, que se puede formular como problema de búsqueda, pero en cada paso es difícil asignar una función de bondad, sin tener en cuenta posibles soluciones posteriores.
¿Quién, a estas alturas de la película, no conoce el recorrido del viajante de comercio, también llamado TSP (travelling salesman problem)? Este problema, explicado aquí, por ejemplo, consiste en hallar un recorrido por n ciudades, sin pasar dos veces por la misma ciudad, que minimice la distancia total recorrida. En este caso, el problema de búsqueda consiste en encontrar el recorrido óptimo, por lo que, desde el principio, está formulado como un problema de optimización.
Dado que cada ciudad se puede visitar una sola vez, se trata de un problema de optimización combinatoria; las soluciones posibles están situadas en el espacio de todas las permutaciones del conjunto de ciudades. Si denominamos a las ciudades con letras mayúsculas, A, B, ....; una solución posible podría ser ABDEFC, y otra BDFECA. Cada una de estas soluciones tiene una puntuación, que sería la cantidad total de kilómetros recorridos; evidentemente habrá una cuyo kilometraje sea menor o igual que todas las otras soluciones.
Claro está, hay que encontrar esa solución. Para 6 ciudades es fácil, pero para 200 no lo es. La razón es, simplemente, que el tamaño del espacio de búsqueda aumenta con el número de ciudades, de hecho, su tamaño es (n-1)!/2, donde n es el número de ciudades. Eso lo hace un problema NP-difícil: no pueden ser resueltos por una máquina de Turing no determinística en tiempo polinómico.
En muchos casos, los problemas a los que se va a enfrentar uno se comportan de esta forma: cuando aumenta el tamaño del mismo, el tamaño del espacio de búsqueda aumenta mucho más rápidamente, y por tanto, el tiempo de solución del problema (o el espacio en memoria necesario para solucionarlo), teóricamente, aumenta más o menos de la misma forma.
Otros problemas de búsqueda son los siguientes:
8-puzzle, en el cual, como se muestra en la ilustración, a partir de una configuración inicial donde hay 8 cuadros desordenados, hay que llegar a otra configuración donde estén ordenados, usando para el intercambio cualquier posición que se halle vacía. El problema de búsqueda en este caso consiste en encontrar un camino que vaya desde la configuración inicial hasta la final. Hay un problem equivalente, o al menos similar, en el libro de Michalewicz, denominado el problema de los cuatro caballos: dos caballos blancos y dos negros situados en un tablero de 3x3, tienen que moverse de forma que los caballos negros intercambien sus posiciones con los caballos blancos.
Problema de la mochila: dados una serie de objetos, generalmente rectangulares, maximizar la cantidad de objetos que se pueden empaquetar dentro de una superficie finita, también rectangular. También se le conoce como el bin-packing problem.
Problemas de optimización númerica: se trata de encontrar el punto o puntos en una función multidimensional que den el máximo, o mínimo, valor para esa función. En algunos casos, tal función puede estar definida en todo el dominio, y ser diferenciable hasta dos veces, pero en otros casos, puede haber zonas del espacio en las cuales no esté definida, o puede que no tenga derivadas en algún punto, o puede que esté definida, con toda la mala leche del mundo, a trozos. Nunca te puedes fiar de que una función a optimizar esté definida decentemente.
Mastermind: En este juego, que se muestra en la figura, un jugador debe de averiguar una combinación de chinchetas de colores oculta por el otro jugador haciendo suposiciones sobre la combinación, y siendo contestado con una chincheta pequeña y blanca por cada acierto de color, y una negra por cada acierto de color y posición. Sólo una solución (entre 64) es la correcta, pero el jugador que ha puesto la combinación oculta va orientando la búsqueda mediante las chinchetas blancas o negras. El problema se hace exponencialmente más difícil cuando se aumenta el número de colores, y la longitud de la combinación. Este es un ejemplo particular de una gama más general de problemas denominados problema oráculo: un usuario tiene que averiguar una combinación secreta guiado por las respuestas de un oráculo, que concede pistas a partir de las posibles soluciones apuntadas por el usuario. Este tipo de problemas tiene aplicación en criptoanálisis diferencial tests de circuitos VLSI, y juegos tales como el que se está tratando.
Generalmente, para resolver un problema del mundo real, no se trabaja directamente con el mundo real. Para resolver el problema del viajante no se compra uno una Kangoo y se lía a hacerse kilómetros, sino que se hace un modelo del problema. En ese modelo, se extraen las características fundamentales del mismo (como por ejemplo, la conocida simetría esférica del caballo), y se eliminan todas las que son accesorias, o que no tienen tanta importancia en el desarrollo del problema (o simplemente que nos estorban). Cuando hemos tratado de resolver el problema del viajante de comercio, hemos tenido en cuenta exclusivamente la distancia entre ciudades, sin considerar, por ejemplo, que para ir de una ciudad a otra puede ser obligatorio pasar por una tercera, el estado de las carreteras, los diferentes consumos de gasolina según el tráfico; más o menos, viene a ser un problema de bruja con escoba viajante de comercio, que recorre los espacios entre ciudades usando pasillos aéreos de escoba.
En otros casos, sobre todo si se trata de problemas puramente computacionales, el modelo se acerca bastante más al problema real. En un problema de colocación de clases en un Instituto de enseñanza media, por ejemplo, todos o casi todos los factores pueden ser tenidos en cuenta: distancia entre las clases, disponibilidad de los profesores, máximo número de horas por profesor, y el modelo se acercará bastante a la realidad.
En todo caso, sólo se puede resolver un problema si se tiene un modelo del mismo; la solución al problema real será tanto más adecuada cuanto más cercano sea el modelo al problema real, pero, en todo caso, la solución a un problema lo es sólo en el sentido que es una solución al modelo del problema.
En algunos casos, modelar el problema supone, de alguna forma, simplificarlo; incluso en casos en el que el problema esté formulado computacionalmente de forma completa, hace falta hacer aproximaciones para hacer su resolución más simple usando un método determinado. Una función no diferenciable (como la función escalón de Heavyside) puede ser aproximada, por ejemplo, por una función diferenciable con el objeto de aplicarle soluciones (como las que vamos o ver más adelante) que necesiten esa precondición.
Siempre hay que tener en cuenta, sin embargo, que modelos diferentes del problema darán soluciones diferentes del mismo. Pero siempre encontrar una solución aproximada a un modelo exacto será mejor que encontrar una solución exacta a un modelo aproximado. O casi siempre.
No siempre las condiciones del problema permanecen estáticas durante la duración del mismo; puede ser que el espacio de búsqueda aumente o disminuya, que la valoración de una solución cambie, o simplemente que la forma más simple de resolver un problema consista en resolver previamente una serie de subproblemas, que vayan acotando la solución cada vez más.
En el caso del Mastermind, la búsqueda de la solución puede descomponerse a su vez en búsqueda de una serie de subsoluciones. Por ejemplo, una forma de enfocarlo es jugar, en cada momento, una combinación de colores que no haya sido eliminada de antemano como inválida. Supongamos que, como se ha visto en el caso anterior, se ha jugado una ficha roja y tres amarillas, a lo que el jugador oráculo ha contestado con una tachuela negra y otra blanca. Si se sigue la estrategia anterior, se tendrá que jugar una combinación que coincida, como máximo, en una posición y color, y en un color.
De esta forma, se va acotando el espacio de búsqueda, pero a la vez, el problema de búsqueda inicial se convierte en el subproblema de encontrar, a cada paso, una combinación que cumpla las condiciones. La función que expresa la bondad de una solución va variando con el tiempo: por ejemplo, una solución válida en un momento determinado, en el momento que se juega, deja de ser válida, porque el espacio de búsqueda ha cambiado
Los problemas cuya solución varía con el tiempo son un ejemplo de problemas difíciles de solucionar usando técnicas tradicionales; sin embargo, los problemas con restricciones tienen una larga tradición. Una restricción es simplemente una condición que tiene que cumplir la solución, habitualmente formulada como una función sobre una combinación de las variables del espacio de búsqueda. En el caso del problema TSP, una restricción consistía en que no se podía pasar por una ciudad dos veces. En otros casos, se expresan como una desigualdad; por ejemplo, la suma de las variables debe ser 0. En un problema de colocación de clases, una restricción puede ser que ningún profesor imparta menos ni más de un número de horas determinadas el mismo día. En un problema de asignación de trabajos a revisores en un congreso, por ejemplo, ningún revisor deberá revisar más de 6 trabajos, y preferentemente, más de 5. En este caso se trata de una restricción suave, que se puede incumplir; en el caso de las restricciones fuertes, la solución será inválida en el caso de que se incumplan.
Las restricciones fuertes se pueden manejar de múltiples maneras válidas; en algunos casos, el problema puede ser manejar las restricciones suaves. Se puede optar simplemente por pasar de ellas; pero si no se pasa, hay que asignarles un peso, o una prioridad, con lo cual, el manejo de las restricciones suaves se convierte, en sí, en un problema. Se verá a lo largo de este tutorial cómo se manejan en diferentes sitios.
El concepto de multimodalidad se usa en diferentes contextos: estrictamente, un problema multimodal es un problema que tiene varios máximos, todos ellos de la misma jerarquía, pero también se aplica a aquellos problemas que tienen varias soluciones posibles. En general, casi todo problema de búsqueda, formulado como un problema de optimización, suele tener varios máximos, pero uno de ellos es mejor que el resto, y se denomina máximo global. El resto son máximos locales; es decir, se puede definir una vecindad alrededor de ellos en la cual son máximos globales. Sin embargo, en muchos casos, todos los máximos globales tienen la misma jerarquía, bien por tener el mismo valor numérico, o bien porque se establezca un criterio de mejor que tal que no se pueda decidir cuál de ellos es mejor que otro.
Esto suele suceder en los problemas denominados de optimización multiobjetivo: en este caso, las soluciones se califican con respecto a varias variables o criterios, y ningún criterio tiene preferencia sobre otro. Por ejemplo, imaginemos un problema del viajante más real en el cual se trate de minimizar el tiempo necesario, y, simultáneamente, el combustible gastado. No se puede cambiar más tiempo por menos combustible, ni al revés, los dos tienen la misma importancia. Habrá soluciones mejores que otras (90 minutos y 13 litros será mejor que 100 minutos y 14 litros), pero en algunos casos, no se podrán comparar (¿es mejor 90 minutos y 13 litros que 100 minutos y 12 litros?). En este caso, un problema tiene muchas soluciones posibles, el llamado frente de Pareto, constituido por todas las soluciones no dominadas, es decir, tales que no hay otra solución mejor que ellas. Estos problemas de optimización de multiobjetivo se están abordando también usando técnicas heurísticas y metaheurísticas.
Como ya se sabe que se va a trabajar con un modelo de la solución del problema, no con la solución en sí, y generalmente con ese modelo se va a trabajar dentro del ordenador, hay que dar con la representación del problema más adecuada, es decir, la estructura de datos que mejor se adapte a ese modelo. Esto es tanto un problema de diseño como un problema de implementación: se escogerá la estructura de datos más adecuada para el método de solución del problema, y la estructura de datos más adecuada para el lenguaje y entorno sobre el que se esté trabajando. Aunque inicialmente pueda parecer que el paso de modelo a representación es directo, no siempre es así. La representación representa, casi siempre, una simplificación del modelo; por ejemplo, en el momento que se trabaje con números de coma flotante en el ordenador para representar números reales ya estamos limitando la posible precisión de la solución; en la práctica, la precisión se adapta al problema, pero, en algunos casos, esta falta de precisión puede introducir artefactos en la posible solución.
En la mayor parte de los casos, la solución al TSP se representa como una permutación de una serie de símbolos únicos, tantos como ciudades. Por ejemplo, si hay suertecilla y trabajamos con menos de veintitantas ciudades, se puede usar el alfabeto, y podemos usar una cadena de caracteres ASCII para representar la solución (también se puede subir un punto en la escala de geekidad y usar una cadena de caracteres UNICODE, que necesitan un par de bytes cada uno y se pueden usar más ciudades). Si hay más, tendremos que usar algún otro tipo de estructura, como un vector o una lista de enteros. Se trata, mayormente, de una decisión de implementación, pero, en algunos casos, usar una representación inadecuada puede hacer ineficiente la resolución de un problema.
Algunos métodos de resolución pueden exigir un tipo de representación determinada, allá ellos. En general, un buen método de resolución debería ser capaz de manejar cualquier tipo de representación.
Sobre esta representación del problema, se calcula la función de evaluación; lo que se pretende habitualmente con la función de evaluación es que su valor sea máximo (o mínimo) cuando se haya alcanzado el objetivo del problema, a veces es denomina, por eso, función objetivo, de adecuación, o, también, usando el término en inglés, fitness. Y aunque la función de evaluación viene dada por el objetivo del problema, en muchos casos la función se modifica para tener en cuenta restricciones, multimodalidad, o bien simplemente una serie de artefactos introducidos por el método de resolución del problema.
Puede suceder también que la función objetivo no esté definida en todo el espacio de búsqueda del problema: en problemas con restricciones, combinaciones de valores de las variables del problema o bien valores de estas variables dan lugar a un valor inválido de la función de evaluación. Estos casos se manejan de muchas formas diferentes: sustituyendo la función objetivo por otra función en la que estas regiones "no alcanzables" sean alcanzables, o asignando un valor numérico al incumplimiento de la restricción. Dependerá del método de resolución del problema, y, en todo caso, cada técnica tiene un grado de éxito diferente.
A partir de esta función de objetivo, se define el problema de búsqueda de la forma siguiente:
Un problema de búsqueda (y, equivalentemente, un problema de optimización), consiste en, dado un espacio de búsqueda S junto con su parte alcanzable F ⊆ S, encontrar un x ∈ F, tal que eval(x) ≤ eval(y) para todo y ∈ F.
Puesto así, parece fácil, ¿no? Se parte de una solución o soluciones iniciales, y se van cambiando esas soluciones o generando otras nuevas hasta que se encuentre la solución deseada. La cosa no es tan fácil, pero, en todo caso, cabe llamar la atención sobre el hecho de que todos los métodos de resolución de problemas necesitan una factoría de soluciones (una forma de generar soluciones nuevas) y un taller de soluciones, que genere soluciones nuevas a partir de las existentes. Las primeras se suelen llamar generadores de soluciones, y las segundas, operadores de variación. No todos los métodos usan las segundas, en todo caso. Pero si se usan, es conveniente tener presente una definición de la vecindad de cada punto del espacio de búsqueda; los operadores de variación convierten un punto del espacio de búsqueda en otro de forma aleatoria o siguiendo algún criterio (por ejemplo, tomando sólo los puntos que sean mejores objetivamente que los anteriores). Este concepto de vecindad es necesario para que los operadores actúen de forma más o menos local, usando en cierto modo la información ya existente en la solución para generar otra nueva; si un operador convierte una solución en otra lejos de la primera, equivale, en la práctica, a generar una solución aleatoria.
Las factorías y talleres representan dos formas diferentes de moverse por el espacio de búsqueda: una factoría explora, puesto que genera puntos en zonas del espacio que previamente no tienen porqué haber sido visitadas; los talleres también exploran, porque generan soluciones nuevas, pero al hacerlo en la cercanía de soluciones ya existentes, explotan estas soluciones, sacándoles todo el partido posible, para obtener una solución mejor. La mayor parte de los algoritmos de búsqueda tratan de establecer un equilibrio entre explotación y exploración, aunque muchos de ellos se inclinan hacia una mayor exploración (aleatoriedad) o explotación (determinismo).
No es que sea el espacio más apropiado para describir un mogollón de técnicas un subapartado de un capítulo; cada una de estas técnicas tienen una larga historia, y han servido durante mucho tiempo para resolver muchos problemas de optimización. Desgraciadamente, este no es el tema de este tutorial, así que le dedicaremos un poco a cada una de ellas. En general, todos los métodos de búsqueda se dividen, a grandes rasgos, en métodos globales y locales. Los métodos globales tratan de encontrar el máximo global de un problema, mientras que los locales se concentran en la vecindad de la solución generada inicialmente, y, por tanto, necesitan alguna técnica adicional, como comienzos múltiples, para acercarse al máximo global. En general, los métodos locales no tienen ninguna garantía de que el máximo encontrado sea global, ni una medida del error en que se incurre dando como bueno el máximo encontrado; los globales sí suelen tener una de las dos cosas, o las dos (o ninguna, pero los venden así). Algunos métodos híbridos combinan algoritmos de los dos tipos; los métodos exhaustivos, sin embargo, no degan que se les escape la solución fácilmente.
Los métodos se dividen también en aquellos que trabajan, a cada paso, sobre soluciones completas, y aquellos que no tienen una solución completa hasta que han terminado. En el primer caso, normalmente se procede de forma iterativa a mejorar una solución; mientras que en el segundo, se puede ir acotando la solución, o bien asignándole valores a cada una de las variables de la solución hasta que se asigna la solución final.
En algunos problemas donde el espacio de búsqueda es suficientemente pequeño y enumerable, se pueden usar métodos de búsqueda exhaustiva o enumerativas: se examinan una por una todas las soluciones posibles, y se da por buena aquella que tenga el máximo valor de la funcion objetivo.
En el caso del juego del mastermind, se enumeran una por una todas las combinaciones posibles de colores para una longitud determinada, y se van tachando todas ellas que no cumplan las condiciones puestas por el "oráculo"; en cada caso, se juega aleatoriamente una de las soluciones que sea factible, y se tachan las no factibles, con la ventaja de que no tienen porqué volver a aparecer en la búsqueda, y se acota cada vez más el espacio.
El problema con la búsqueda exhaustiva no sólo es que no siempre sea factible, sino que su mal comportamiento con respecto al aumento de tamaño del espacio de búsqueda, y el hecho de que necesite una cantidad de memoria de ordenador proporcional al tamaño del problema, hace que no se pueda aplicar en la mayor parte de los casos. Sin embargo, en algunos casos puede ser útil; por ejemplo, en la fase final de la resolución del problema cuando el subespacio de búsqueda esté suficientemente acotado.
En todo caso, son problemas simples con relativamente pocos prerrequisitos: sólo que el tamaño del espacio de búsqueda quepa en la memoria del ordenaodr; otros algoritmos, además, tales como el branch&bound o el A*, que elaboran una solución completa a partir de una solución parcial, necesitan también una búsqueda exhaustiva. Y, con un poco de suerte, podemos usar técnicas tales como el backtracking para descartar partes del espacio de búsqueda que se van a recorrer.
Los algoritmos de búsqueda local parten de una solución inicial, y, aplicándole operadores de variación, la van alterando; si la solución alterada es mejor que la original, se acepta, si no lo es, se vuelve a la inicial. El procedimiento se repite hasta que no se consigue mejora en la solución.
Los procedimientos de búsqueda local más usados son los basados en el gradiente: en este caso, el operador de variación selecciona una nueva solución teniendo en cuenta la derivada de la función que se quiere optimizar en el punto, tratando de ascender o descender usando el gradiente hasta llegar a un punto de inflexión donde no se puede obtener ninguna mejora adicional.
Estos procedimientos se suelen llamar de hillclimbing, o de escalado de colinas; el mayor truco en ellos consiste en escoger correctamente el tamaño de paso para ascender y el punto de inicio. Pero se trata de algoritmos de búsqueda locales, y, como tales, sólo van a encontrar el máximo local más cercano al punto de inicio. Esto se puede resolver usando una estrategia de multicomienzo, pero, en todo caso, no te garantizan que se encuentre, o incluso de acerque uno, al máximo global. En todo caso, tiene la ventaja de que, en cada iteración del algoritmo, se tiene una solución válida, aunque no tiene porqué ser la mejor.
En el caso del TSP, un procedimiento de búsqueca local se denomina 2-opt. Consiste en escoger una permutación inicial aleatoria, e ir probando con todas las posibles soluciones en la vecindad de esta, entendiendo como vecindad el conjunto de todos los recorridos que pueden ser alcanzados intercambiando dos caminos no adyacentes en el recorrido original. Un recorrido reemplaza al original si es mejor; una vez que no se puede mejorar un recorrido, se considera óptimo y se da como solución.
El mejor algoritmo de búsqueda local conocido para el recorrido del viajante es el llamado Lin-Kernighan. Es una variación del anterior, permitiendo el número de caminos a intercambiar en cada iteración variar; además, en vez de tomar cualquier mejora, prueba varias y se queda con la mejora de más valor.
Estos métodos van construyendo soluciones variable a variable, no obteniendo una solución completa al problema hasta que todas las variables han sido asignadas. Uno de los métodos más conocidos son los algoritmos voraces o greedy, que funcionan de la forma siguiente: para cada variable, se asigna aquél valor que maximice alguna función de utilidad.
En el caso del TSP, un algoritmo voraz comenzaría con una ciudad elegida aleatoriamente, y elegiría la ciudad más cercana a ésta. Para esta segunda ciudad, elegiría la más cercana, y así sucesivamente. En este caso, el problema estaría simplemente parametrizado con la ciudad inicial elegida.
Los algoritmos voraces sustituyen un criterio de optimalidad global por un criterio en cada paso; no siempre los dos se corresponden, y por tanto, no tienen porqué hallar el máximo global del problema.
Otros métodos consisten en dividir el problema general en problemas más simples, y hallar la solución a estos problemas más simples; el método se denomina divide y vencerás; en algunos casos, la solución a un problema de orden n puede venir resolver a otro problema de orden n-1, tal como sucede, por ejemplo en el conocido problema de las torres de Hanoi.
Algunos métodos consisten en ir descartando partes del espacio de búsqueda, con el objeto de acotar cada vez más la solución al problema. El branch and bound. Este método imagina el espacio de búsqueda como un árbol de decisión; en cada paso del algoritmo, se toma la decisión de podar las ramas del árbol que parezcan menos prometedoras.
Este método procede de la forma siguiente: se establece una cota inferior a la posible solución (o superior, si se trata de minimizar). Se va siguiendo una rama del árbol, hasta que se encuentra que la solución parcial es menor que esa cuota; en ese caso, se descarta la rama completa.
En el caso del recorrido del viajante, supongamos que hemos establecido que la cota superior es 200 kms. Se establece un árbol de la forma siguiente: tomando una ruta entre dos ciudades, pongamos AB, se establecen dos ramas para una posible solución con y sin esa ruta; a partir de ahí, se hace lo mismo con el resto de las rutas. Se van recorriendo las ramas, y si se encuentra que la suma parcial de las rutas supera los 200 kms, se elimina esa rama y ya no se sigue recorriendo.
Si se ha organizado el espacio de búsqueda en forma de árbol, puede resultar importante la ordenación de las ramas, porque si se consigue colocar las ramas "mejores" antes, el algoritmo será capaz de encontrar la solución con más rapidez. Algoritmos como el A* toman este tipo de enfoque. En este algoritmo, se usa un método mejor-primero para recorrer las ramas, y un método heurístico para estimar el coste de las ramas que quedan por recorrer. La principal diferencia con el método anterior es que se usan heurísticas para estimar valores de las ramas restantes, en vez de valores exactos.
Estos métodos se pueden extender también a problemas de optimización numérica, en cuyo caso darían cotas entre las cuales se moverían las soluciones. Pero si el espacio de búsqueda no se puede enumerar bien, o si existe un número de variables excesivo, este tipo de algoritmos no suelen funcionar bien.
Los métodos de búsqueda global tratan de escaparse de los máximos locales, explorando com más eficiencia el espacio de búsqueda. Generalmente, añaden algún componente aleatorio a la búsqueda, de forma que, si se encuentra un mínimo local, se salte a otro punto del espacio de búsqueda, donde pueda haber otro máximo, posiblemente global.
Uno de los más conocidos es el recocimiento simulado, o simulated annealing. A grandes rasgos, consiste en un procedimiento de ascenso de gradiente, pero tal que no siempre se escoge la mejor solución; dependiendo de una temperatura, la probabilidad de escoger una solución peor que la actual va descenciendo con el tiempo, hasta que al final del algoritmo, cuando la temperatura es 0, se escoge de forma determinista siempre la mejor solución. Puesto en forma de algoritmo:
Inicial el procedimiento en un punto del espacio de búsqueda
Mientras no se cumpla la condición de terminación, mejorar la solución actual, dependiendo de la temperatura.
Actualizar la temperatura
Volver al paso segundo
La probabilidad de aceptar una nueva solución xt+1 en vez de la antigua xt se suele expresar con la fórmula p(x,y,T)=1/(1+eeval(xt+1) - eval(xt)/T).
Al método que se sigue para actualizar la temperatura se le suele denominar procedimiento de enfriado o cooling schedule. Dependiendo de la temperatura, puede ser que se escojan soluciones peores, pero la probabilidad de que suceda desciende con el tiempo y con la diferencia entre la evaluación de las dos soluciones. El truco, claro está, consiste en elegir una buena temperatura inicial y un procedimiento de enfriado correcto.
El término annealing procede de la metalurgia, y en concreto de la fabricación de espadas. En esta página se describe el procedimiento de fabricación de espadas antiguas, y cómo se usaba el recocimiento para conseguir espadas flexibles que no se rompieran. En concreto, lo que consigue este procedimiento es un cristal con pocas irregularidades, y con un bajo nivel de energía atrapada.
El recocimiento simulado es un método de optimización bastante popular, simple de implementar, y que funciona bien para muchos problemas. Ha sido aplicado, por ejemplo, para la optimización de la disposición de una página web o para resolver el juego del Mastermind. Si embargo, es una mala elección de punto inicial o del esquema de enfriamiento puede dar al traste con su exploración del espacio global.
Otros métodos, como el Greedy Randomized Adaptive Search Procedure o GRASP, se basan en la combinación de fases de explotación, en los cuales se siguen algoritmos de búsqueda local, con fases de exploración, en los cuales se usan procedimientos aleatorios para expandir el espacio de búsqueda recorrido.
El algoritmo GRASP mantiene una lista de posibles soluciones a un problema, que se genera aleatoriamente. Se escoge una de las soluciones, y se mejora hasta que no se pueda mejorar más; si es mejor que la mejor almacenada, se actualiza la lista de soluciones almacenadas. Viene a equivaler a un algoritmo de ascenso/descenso de gradiente con multicomienzo; mejora los resultados con respecto a una aplicación simple del mismo, pero no es tan eficiente como algoritmos que incluyen componentes estocásticos.
Un algoritmo similar, denominado búsqueda tabú, incluye una memoria que almacena los últimos movimientos realizados, y que se usa para no volver a caer en los mismos máximos locales, a esta memoria se le denomina lista tabú. Pero también tiene un método que permite escapar de los máximos locales, que se denomina nivel de aspiración; consiste en un criterio para aceptar movimientos incluidos en la lista tabú. Aparte de esa memoria, que se podría llamar a corto plazo, diversas variantes de la búsqueda tabú incluyen memorias a medio plazo, registrando los atributos más comunes de un conjunto de soluciones, para poder explotar esa zona del espacio de búsqueda, y a largo plazo, que diversifica la búsqueda sobre regiones que no se han explorado con anterioridad.
La búsqueda tabú ha sido usada en diferentes aplicaciones, y tiene diferentes variantes: por ejemplo, en la denominada búsqueda tabú con umbral se sigue un procedimiento similar al GRASP: una fase de intensificación (que correspondería a lo que hemos denominado explotación), en la que solo se aceptan soluciones que aumentan el valor de la solución objetivo, seguida por una fase de diversificación (exploración), en la que se acepttan cualquier tipo de movimientos con el objetivo de escapar de máximos locales.
1. Tomar un problema clásico, tal como el problema de la mochila, abordarlo usando varios algoritmos de los descritos anteriormente. Para ello, elegir un lenguaje de programación determinado, como Java, C++ o Perl, localizar en Internet diferentes librerías que implementen los algoritmos descritos, y resolver el problema.
Un algoritmo que aborda los algoritmos bioinspirados con un enfoque divulgativo es Digital Biology de Peter J. Bentley . Mirando a diferentes aspectos de la naturaleza, desde el universo al crecimiento pasando por los sistemas inmunes, describe cómo se pueden imitar tales procesos dentro del ordenador para resolver problemas reales..
El término algoritmos bioinspirados agrupa una serie de algoritmos que, de una forma o de otra, están inspirados en algún comportamiento de los seres vivos, o simplemente grupos grandes de elementos regidos por las leyes de la física. Entre ellos están tanto los algoritmos de cristales de spin, como las redes neuronales, y los algoritmos de sistema inmune. A algunos de ellos se le dedicará algún espacio más dentro de este tutorial, así que nos referiremos brevemente solo a los menos populares, incidiendo en aquellos que se puedan aplicar a problemas de búsqueda.
Los algoritmos de colonia de hormigas son, sin ninguna duda, los más populares de todos, sobre todo en los últimos años. Parten principalmente del estudio del comportamiento de las hormigas sociales, realizado principalmente por los mirmecólogos Pierre-Paul Grassé y Edward O. Wilson, que vienen a entender la colonia de hormigas como un solo organismo, cuyos componentes u órganos son las hormigas en sí. Los componentes de una colonia se comportan de tal forma que el comportamiento de la misma es mucho más que lo que cabría deducir de la suma de sus partes, o incluso de la inteligencia de cada una de las partes. Para explicar esto Pierre Paul Grassé introdujo el concepto de stigmergia, que consiste en la sinergia por la comunicación que se realiza entre los miembros de la colonia a través del ambiente en el que se mueven. De esta forma se puede explicar la realización de obras colectivas sin necesidad de la intervención de una autoridad central. Estas ideas fueron usadas por investigadores como Jean-Louis Deneaubourg y Marco Dorigo.
En general, la comunicación entre las hormigas es bastante escasa, y su entendimiento limitado; la mayor parte de la comunicación se realiza a través de los actos que otras hormigas han realizado, o bien a través de la acumulación de feromonas en el suelo. Por ejemplo, si la colonia se dedica a acumular las larvas en un sitio determinado, no hay ninguna hormiga que decida de antemano en qué sitio se van a acumular: simplemente se cogen larvas de un lado, y se sueltan donde ya se detecte que hay otras larvas.
Uno de los primeros libros que introducen los algoritmos de colonias de hormigas es Swarm Intelligence: From Natural to Artificial Systems de Eric Bonabeau, Marco Dorigo, y Guy Theraulaz . Un libro que parte de diferentes comportamientos de las hormigas, para aprovecharlos en algoritmos de búsqueda y simulación. Escrito, además, por algunas de las grandes autoridades del género.
Casi todos los comportamientos de una colonia de hormigas, desde la construcción de estructuras, hasta la localización de comida, se pueden usar para algún tipo de problema de búsqueda; toda esta familia de algoritmos se denomina ant colony optimization u optimización por colonia de hormigas, un resumen se encuentra en esta dirección. En general, tienen en común las hormigas, las feromonas, y un entorno en el cual se desarrolla la labor de la colonia.
El problema del viajante ha sido paradigmático en su solución por parte de colonias de hormigas. Para resolverlo, se toma una serie de hormigas, y se las suelta en el grafo con el cual se representan las diferentes ciudades a visitar. Las hormigas situarán en cada arco del grafo (que une dos ciudades) una cantidad de feromonas inversamente proporcional a la distancia entre esas dos ciudades; la hormiga, en cada ciudad, se irá con una probabilidad mayor por aquél camino que tenga más acumulación de feromonas. Si deja uno a las hormigas el tiempo suficiente, se irán yendo por los caminos más cortos, porque serán los que tienen más feromonas; a su vez, irán dejando feromonas, con lo cual estarán haciendo más probable que se siga ese camino. Al final, se destacará el camino con más feromonas y/o hormigas, que será la solución al problema.
Habrá que hacer provisiones adicionales de que las hormigas no visiten dos veces las mismas ciudades, o no sigan dos veces el mismo camino, pero la idea, en principio, es esa. En este artículo se muestra la solución del problema del viajante usando hormigas.. Un trabajo que aborda éste problema usando el denominado ant-system lo hizo Dorigo en el 1996.
Tanto las colonias de hormigas como los algoritmos que las imitan, se basan en tres principios: retroalimentación positiva, junto con retroalimentación negativa, lo cual lleva a una amplificación de las fluctuaciones, y el hecho de que sucedan fluctuaciones múltiples. Debe haber un equilibrio entre los dos tipos de retroalimentaciones; si no, se llegaría a una situación de caos, y las dos juntas hace que las fluctuaciones (por ejemplo, el que unas pocas hormigas elijan un camino en vez de otro) se amplifiquen. Por otro lado, estos comportamientos sólo pueden tener lugar si hay múltiples individuos e interacciones; en el caso de que haya solo unos pocos, los comportamientos serán más predecibles a corto plazo, y menos sorpresivos. Curiosamente, estos principios son comunes a la mayoría de los algoritmos bioinspirados.
Los algoritmos de hormigas se pueden usar también para clasificación de documentos, como se hace en esta aplicación, donde se aplica un algoritmo de clustering de hormigas mejorado a la clasificación de documentos tomados de la prensa española.
Distribución espacial de 931 elementos (tomados de un artículo en un periódico nacional) en una rejilla toroidal 61x61; usando 91 hormigas (tomado de Self-Organized Stigmergic Document Maps: Environment as a Mechanism for Context Learning Ejemplos de algunos clusters independientes: (A) anunció, bilbao, embargo, titulos, entre, hacer, necesídad, tras, vida, lider, cualquier, derechos, medida.(B) dirigentes, prensa, ciu. (C) discos, amigos, grandes. (D) hechos, piloto, miedo, tipo, cd, informes. (E) dificil, gobierno, justicia, crisis, voluntad, creó, elección, horas, frente, técnica, unas, tarde, familia, sargento, necesídad, red, obra. (F) voz, puenlo, papel, asseguró. (G) nuestro, europea, china, ahora, poder, hasta, mucho, compañía, nacionalistas, cambio, asesinado, autor, nuevo.(H) rodríguez, vez, tramitación, gran. (I) se, declara, junto, administración.(J) final, visita, cataluña, puerta, final, jurisprudencia, todas.(K) fallo, ejército, bajo, real, situación, mission, liga, teatro, decision, queda, nacionalismo, pasado, director, plan, manos. (L) unica, blancos, ibarra, intensidad, nuevas, las, persona, parlamento, españoles, tarde, seis, otros, euro, elecciones, servicios, podría, otra, tiene, nada, posibilidad, hablar, porque, música, puntos, compromiso, dentro, doctrina, fiscal, abc, derecho, atentado, sistema, carrera, razón, televisión, semanas, mundo, natural, mitad. (M) mayo, parís, ciento, consejo, reconoció, me, pero, lo, ocasión. (N) incluso, pnv, luis, momentos, miembros, regimen, ee.(O) cabeza, ex.(P) oea, municipals, mujer, ayuntamiento, cosas, toda, novedades, debate, firmado. (Q) domingo, estado, otro, primeros, estamos, no.
Los automátas celulares son tremendamente populares como juguetito computacional, aunque su utilidad para resolver problemas reales está todavía por probar. Tampoco está muy claro que estén inspirados en la naturaleza, aunque es cierto que se pueden imitar, usando autómatas celulares, muchos fenómenos naturales, tales como la coloración de algunas piles de animales, o incluso la situación de madrigueras de animales. Sin embargo, son populares porque son uno de los sistemas más simples que pueden reflejar comportamientos "naturales": autoorganización, autorreplicación, caos... también producen bonitos dibujos, y gente como Stephen Wolfram han llegado a postular que el universo todo se puede explicar usando autómatas celulares. No es que mucha gente lo crea, pero lo dice.En todo caso, tienen una utilidad limitada para resolución de problemas de búsqueda, por eso no merece la pena dedicarle mucho más espacio.
Hay algunos algoritmos que no sólo están inspirados en la Naturaleza, sino que necesitan de algo "natural", "húmedo", para ejecutarse. Se trata de la llamada computación ADN o DNA computing. Como su propio nombre indica, se usa el ADN como base para calcular, en vez de los ordenadores de toda la vida. Aquí el truco es lograr usar como representación de un problema una cadena de ADN. Una vez que lo logres, lo único que tienes que hacer es soltar todos los posibles candidatos en una cuba PCR (que usa la ADN polimerasa, una enzima, para replicar cadenas de ADN), y dejar que emerjan los más aptos. Este sistema lo ha aplicado Adleman, como no, al recorrido del viajante, resolviéndolo mucho más rápidamente que cualquier ordenador. Tratándose de un problema de optimización combinatoria, es posible que esta técnica tenga aplicación a ese tipo de problemas, al menos; y quizás con el tiempo, empecemos a ver los Pentium VII con coprocesador ADN. Por lo pronto, parece poco más que un entretenimiento académico.
Puede que tenga un éxito mayor como algoritmo de búsqueda los denominados algoritmos de sistema inmune: el problema que tiene que resolver el sistema inmune es diferenciar lo propio de lo ajeno. Evidentemente, no tienen una lista completa de qué es lo que puede ser ajeno y qué no lo es; menos aún, es posible que esta lista esté codificada en el código genético de los seres humanos (y mamíferos superiores, que son los que tienen un sistema inmune). Pero lo cierto es que lo consiguen, y lo hacen a través de una serie de mecanismos: diversidad, manteniendo librerías de posibles componentes de antígenos, y que usan para reconocerlos, especifidad, porque se puede crear un antícuerpo específico para cada antígeno, memoria, o guardar las respuestas inmunes llevadas a cabo anteriormente, y tolerancia, porque no se ataca al propio organismo, sólo a lo que se considera "extraño".
Un modelo evolutivo del sistema inmune fue descrito por Forrest y otros hace cierto tiempo, y últimamente, se piensa que puede ser aplicado a la identificación y eliminación de virus, otra serie de aplicaciones de diferentes métodos basados en el sistema inmune se puede encontrar en este artículo.
Entre los dos enfoques se encuentran la denominada computación de membrana o sistemas P (membrane computing), una técnica introducida por Gheorghe Paun y que cuenta hoy en día con un grupo de seguidores bastante activo. Los sistemas P se inspiran en la célula para un nuevo concepto de computación, basado en el procesamiento sucesivo de la información siguiendo una jerarquía, y aplicando transformaciones en cada uno de los nodos de esa jerarquía. Este concepto está inspirado en la célula, cuya membrana procesa los productos químicos en el exterior, dejando pasar algunos y protegiéndose de otros, y, a su vez, cambiando de estado y produciendo nuevos productos químicos dependiendo de las entradas que reciba. En la práctica un p-sistema se comporta de forma más o menos similar a un automáta celular: hay diferentes "estados" o nodos, y los estados una vez recibida una entrada, cambian de estado y envían información en forma de cadenas o átomos a otros estados. Por ejemplo, una célula con una membrana (llamada piel), y una segunda vesícula dentro, puede comportarse de la forma siguiente. Inicialmente, tiene dos unidades de "a" dentro de la "piel"; a cada paso, cada una de las unidades produce dos unidades de "c" y una de "b", que emite hacia la membrana interior. No es que este sistema haga nada útil, pero produce dos átomos, uno de ellos en doble proporción que el otro. En ese sentido, se puede entender un sistema p como un híbrido entre un autómata de estados finitos y una red neuronal; cada nodo tiene un estado (los productos que tiene en ese momento), y además, realiza una operación determinada.
Otra técnica que está inspirada en las reglas que siguen las manadas de animales, o las bandadas de pájaros es la llamada particle swarm optimization, u optimización por enjambres de partículas.
Las tres reglas que rigen una bandada (de izquierda a derecha): separación (evitar los sitios donde haya muchos individuos), cohesión (tratar de ir hacia el centro percibido de la bandada), y alineación (tratar de ir en la dirección general de la bandada). Tomado de de la página "Boids", de Craig Reynolds.
Se trata de representar las diferentes soluciones a un problema mediante "individuos" de una manada. Como se indica en esta página central, cada individuo tiene unas coordenadas en el espacio problema, así como un valor de evaluación. Las partículas, tomando diferentes caminos, tratan de dirigirse hacia la mejor partícula del grupo, teniendo también en cuenta el mejor valor obtenido por las partículas en la vecindad de cada una. El movimiento se realiza según una aceleración, que es un parámetro del método. Un tutorial más completo se puede encontrar en esta dirección. Desde nuestro punto de vista, parece una técnica interesante para abordar entornos que varíen en el tiempo, dado que la bandada puede adaptarse con facilidad a condiciones de entorno cambiantes (igual que, por ejemplo, una bandada se adapta a un obstáculo que encuentre por el camino).
1. Realizar una tabla con entradas para cada uno de los paradigmas naturales mencionados anteriormente, sus parecidos y diferencias, y explicar para qué tipo de problemas pueden ser útiles, incidiendo especialmente en problemas de búsqueda.
Cambiemos totalmente de tercio, y después de ver una panorámica general de los algoritmos algoritmos de búsqueda y los algoritmos bioinspirados, vamos a fijarnos qué es lo que inspira dichos algoritmos, la Naturaleza, ese fenómeno natural denominado evolución, y si optimiza o no.
La teoría de la evolución (que no es tal teoría, sino una serie de hechos probados), fue descrita por Charles Darwin 20 años después de su viaje por las islas Galápagos en el Beagle, en el libro Sobre el Origen de las Especies por medio de la Selección Natural. Este libro fue bastante polémico en su tiempo, y en cualquier caso es una descripción incompleta de la evolución. La hipótesis de Darwin, presentada junto con Wallace, que llegó a las mismas conclusiones independientemente, es que pequeños cambios heredables en los seres vivos y la selección son los dos hechos que provocan el cambio en la Naturaleza y la generación de nuevas especies. Pero Darwin desconocía cual es la base de la herencia, pensaba que los rasgos de un ser vivo eran como un fluido, y que los "fluidos" de los dos padres se mezclaban en la descendencia; esta hipótesis tenía el problema de que al cabo de cierto tiempo, una población tendría los mismos rasgos intermedios.
Fue Mendel quien descubrió que los caracteres se heredaban de forma discreta, y que se tomaban del padre o de la madre, dependiendo de su carácter dominante o recesivo. A estos caracteres que podían tomar diferentes valores se les llamaron genes, y a los valores que podían tomar, alelos. En realidad, las teorías de Lendel, que trabajó en total aislamiento, se olvidaron y no se volvieron a redes cubrir hasta principios del siglo XX. Además, hasta 1930 el geneticista inglés Robert Aylmer no relacionó ambas teorías, demostrando que los genes mendelianos eran los que proporcionaban el mecanismo necesario para la evolución.
Más o menos por la misma época, el biólogo alemán Walther Flemming describió los cromosomas, como ciertos filamentos en los que se agregaba la cromatina del núcleo celular durante la división; poco más adelante se descubrió que las células de cada especie viviente tenían un número fíjo y característico de cromosomas.
En resumen, la selección natural actúa sobre el fenotipo y suele disminuir la diversidad, haciendo que sobrevivan solo los individuos más aptos (aunque esta frase, bien mirada, es una redundancia: ¿Sobreviven los mejores o son los mejores porque sobreviven?); los mecanismos que generan diversidad y que combinan características actúan habitualmente sobre el genotipo.
Hay quien aboga, como Fogel, por no hacer demasiado caso a lo que ocurre en la naturaleza, sino seguir un camino propio para resolver problemas de búsqueda, igual que no se han imitado las alas para volar. Sin embargo, muchas veces conocer los mecanismos activos en la Naturaleza nos sirve para mejorar nuestros propios algoritmos, o nos puede inspirar para depurar un programa, cuando todo va mal.
Más o menos a mediados de los años 60, Rechenberg y Schwefel describieron las estrategias de evolución. Las estrategias de evolución son métodos de optimización paramétricos, que trabajan sobre poblaciones de cromosomas compuestos por números reales. Hay diversos tipos de estrategias de evolución, que se verán más adelante, pero en la más común, se crean nuevos individuos de la población añadiendo un vector mutación a los cromosomas existentes en la población; en cada generación, se elimina un porcentaje de la población (especificado por los parámetros y µ), y los restantes generan la población total, mediante mutación y crossover. La magnitud del vector mutación se calcula adaptativamente.
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.
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.
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á para optimizar habitualmente para optimizar sólo una función, no diversas funciones relacionadas entre sí simultáneamente. Este tipo de optimización, denominada optimización multimodal, 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.
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.
Los algoritmos evolutivos son, en general, independientes de la codificación; usando siempre ún código genético quizás nos estamos dejando llevar demasiado lejos por la metáfora de la Naturaleza. Cualquier estructura de datos que cumpla las condiciones de evaluabilidad, combinabilidad y mutabilidad, puede usarse para le evolución.
Hoy en día, la tendencia en algoritmos evolutivos es usar la estructura de datos más adecuada al problema que se esté resolviendo. En algunos casos resultará conveniente usar matrices bidimensionales, en otros estructuras de datos complejas tales como las usadas para representar redes neuronales. El único problema con las estructuras de datos específicas es que no se pueden usar los operadores genéricos, tales como el crossover binario y la mutación binaria; pero, por otro lado, se pueden usar operadores que estén más adaptados al dominio del problema.
El usar una codificación binaria en el TSP lo único que va a conseguir es dar por saco más de lo estrictamente necesario. Puede llegarse hasta el punto de que esta codificación, al ser alterada por un operador de variación, dé lugar a una solución no factible: una que incluya una ciudad dos veces, por ejemplo. Sin embargo, usar una codificación más adecuada al problema, como por ejemplo una permutación, con operadores que trabajen con ella como tal permutación, puede evitar trabajar con soluciones no factibles.
Este hecho, que parece de puro sentido común, no ha evitado que mucha gente use este tipo de codificaciones para resolver el recorrido del viajante (y que lo publique).
Siguiendo con esta tendencia, lo normal es que las estructuras a evolucionar sean objetos en el sentido de la programación diriga a objetos: una estructura de datos con variables de instancia encapsuladas, cuyo acceso está regulado por una serie de métodos que están en su interfaz público. Un cromosoma binario, por ejemplo, permitirá que se realicen sobre él variaciones tal como la mutación y el crossover, pero, por ejemplo, no se permitirá que se cambie la longitud, porque no hay una función en el interfaz que lo permita o porque se produzca un error en tiempo de ejecución.
De la misma forma, la evolución de esas estructuras de datos no plantea más restricciones que las que da el interfaz: por ejemplo, se pueden usar estructuras de datos no uniformes o de tamaño variable, o incluso partes de la estructura de datos que no contribuyan al fitness de la solución. Cabe hablar en estos casos de intrones: partes del cromosoma que no condifican; y se dan en muchos tipos de problemas diferentes. Por ejemplo, en el caso de que se codifique un sistema basado en reglas, puede haber reglas que no se "disparen" durante la evaluación del individuo: en ese caso, actuarían como intrones.
Se plantea un problema adicional que es eliminar o no esos intrones: en general, algunos estudios dan como resultado que los intrones se deben eliminar probabilísticamente, pero no de forma voraz, porque de alguna forma codifican la memoria genética del individuo correspondiente.
Quizás por razones históricas, hay una serie de estructuras de datos que son populares a la hora de resolver problemas usando algoritmos evolutivos: los cromosomas binarios, los vectores de números reales (usados en la programación evolutiva y las estrategias deevolución) y los árboles, que son las estructuras de datos que se usan en la denominada programación genética.
La programación genética, de John Koza (aunque su autoría original es algo disputado), inicialmente se propuso como un método para hacer evolucionar programas de ordenador, con el objeto de generar automáticamente programas que llevaran a cabo una función determinada. Para ello eligieron un lenguaje, el LISP, que se puede representar de forma unívoca como un árbol; la raíz es el resultado de la evaluación, y las ramas contienen como símbolos terminales las variables del problema. Por esto mismo, precisamente, la programación genética no hace evolucionar, en realidad, programas, sino funciones multivariadas, pero con una sola salida, lo cual no se acerca ni por el forro, a la gama de todos los programas posibles. Eso no significa, por supuesto, que no sea útil, pudiéndose usar para generar, por ejemplo, circuitos, o para realizar regresiones simbólicas, es decir, generar una función de formato libre que aproxime los datos obtenidos en un experimento o modelo.
En estas representaciones no es aplicable ya el teorema de los esquemas, el cual, de todas formas, ya no goza del predicamento que gozaba (con las correcciones propuestas por algunos autores, y la crítica de otros tales como Michael Vose). Sin embargo, es aplicable el denominado teorema de las formas, que trabaja no sobre esquemas, sino sobre clases de equivalencia definidas sobre el conjunto de las soluciones posibles. En realidad, tampoco esta teoría ha tenido mucha continuación, por lo cual, casi lo único que se le pide a una representación hoy en día en los algoritmos evolutivos es que respete la teoría de los bloques de construcción: partes de las estructuras de datos que estén juntas en el dominio del problema deben de permanecer juntas, con una cierta probabilidad, a la hora de la aplicación de ciertos operadores.
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.
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:
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.
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 f(x)=x2, 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 entre 0 y 1.
En algunos casos, el fitness no es una sola cantidad, sino diversos números, que tienen diferente consideración. Estos problemas se tratan de otra forma, como se verá más adelante.
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:
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 factor de crowding, 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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
A pesar de que, teóricamente, los algoritmos evolutivos tienen un cierto paralelismo implícito, debido al procesamiento simultáneo de los diferentes esquemas a los que pertenece un componente del cromosoma, en la práctica, se han realizado multitud de versiones paralelas de los algoritmos evolutivos. Eso se debe, principalmente, a dos razones: primero, normalmente la función de evaluación es un componente crítico, y suele consumir gran parte del tiempo, y, por la naturaleza del algoritmo, hay que evaluarla multitud de veces; y, segundo, la estructura del algoritmo se presta fácilmente a la paralelización, ya que cada elemento de la población, salvo en algunos casos, se puede evaluar de forma independiente de los demás, y la mayor parte de los operadores actúan sobre uno, una pareja o unos pocos individuos. En general, los algoritmos evolutivos están descentralizados, una característica que proviene de su inspiración natural, lo cual favorece su paralelización.
En general, cualquier tipo de algoritmo evolutivo se puede paralelizar, independientemente de la representación, y de los operadores que se usen. Sin embargo, es más normal encontrar implementaciones paralelas en algoritmos genéticos y en programación genética; en estos casos, además, presenta ventajas adicionales, hasta el punto que se pueden conseguir aceleraciones superlineales.
Generalmente, los multicomputadores o multiprocesadores se suelen clasificar según la multiplicidad de instrucciones y datos que tengan: pueden tener una o múltiples instrucciones, o uno y múltiples datos. Sin embargo, lo más habitual hoy en día es trabajar en un entorno de ordenadores heterogéneos, unido por redes con diferente ámbito, y con sistemas operativos y modos de representación de las instrucciones y datos muy diferente. Por eso, desde el punto de vista del usuario, hay diferentes formas de considerar este multicomputador heterogéneo: como un sólo ordenador virtual, que ejecuta los programas de forma transparente sin que uno se entere muy bien dónde están físicamente, que es el enfoque que, inicialmente, se propuso la librería PVM . Otro enfoque es considerar los diferentes sistemas como una serie de procesos unidos por intercambio de mensajes, como hace la librería MPI, y algunos lenguajes como el Java a través de su interfaz RMI (Remote Method Invocation). En este trabajo, se pareliza una librería de algoritmos evolutivos usando MPI. Otra librería, basada en la misma EO y llamada ParadisEO, también usa MPI para distribución de algoritmos evolutivos.
Este último método es el más popular, por lo que la mayor parte de los algoritmos, especialmente basados en poblaciones, actuales, consisten en enviar o recibir diferentes mensajes que incluyan o no miembros de la población y/o estadísticas, tratando de hacer el mínimo cambio posible a los algoritmos tradicionales.
Últimamente están surgiendo una serie de ideas en computación distribuida, que se escapan a los paradigmas tradicionales. La mayor parte de ellas intentan trabajar con un entorno heterogéneo, cambiante, y en el cual la CPU es un recurso relativamente abundante. Una idea interesante es la denominada computación en rejilla, o grid computing. La computación en rejilla trata de aprovecharse de los recursos computacionales (CPU, almacenamiento, transmisión) de cantidades ingentes de ordenadores, proveyendo un interfaz que sea independiente de la realidad física de la red y de los ordenadores, de forma que el usuario sólo tenga que preocuparse por ejecutar su problema a través de, por ejemplo, una página web. La infraestructura de la rejilla se encarga de distribuir su problema, los métodos y los datos, por la rejilla, de forma que se aprovechen al máximo los recursos. Hay muchos productos comerciales de computación rejilla, así como algún esfuerzo de fuentes abiertas, tal como OpenGRID.
También es interesante tener en cuenta una tecnología que se usa habitualmente para pirateo de todo tipo de contenido: las redes entre iguales, o P2P, redes sin una topología fija y sin un número de elementos fijos, ni un servidor central, que permiten distribuir datos y servicios. Este tipo de tecnologías están empezando a ser usadas para cálculo paralelo, usando, por ejemplo, los denominados algoritmos epidémicos. Este enfoque es el que se toma en el proyecto DREAM (Distributed resource evolutionary algorithm machine), un software para programar algoritmos evolutivos usando una infraestructura P2P.
Por último, los servicios web, que ofrecen un interfaz con una sintaxis y semántica conocida para usar los servicios existentes en un ordenador, se pueden usar también para computación distribuida; pueden ser una implementación posible para un sistema en rejilla, o para una red P2P, o simplemente un interfaz para acceder a cualquier tipo de servicio. Los servicios web están basados en el metalenguaje XML. Por ejemplo, en en este artículo, se paraleliza un algoritmo genético usando un protocolo llamado SOAP (Simple Object Access Protocol), que permite intercambiar mensajes codificados en XML entre diferentes procesos. En esta página se ofrece un servicio web para la ejecución de algoritmos evolutivos que usa también SOAP.
En resumen, el panorama actual de la computación evolutiva presenta muchos tipos de entornos diferentes en los cuales implementar algoritmos de búsqueda, y especialmente algoritmos evolutivos.
Para evaluar un algoritmo paralelo habitualmente se tienen en cuenta sus propiedades de escalado, es decir, cómo se comporta según se van añadiendo nuevos procesadores al grupo; habitualmente el procesador más lento suele ser el primero que interviene. Un escalado lineal se daría si la aceleración SP, definido como el tiempo que tarda el algoritmo en ejecutarse en P procesadores o speedup del proceso es directamente proporcional al número de procesadores añadidos; sin embargo, lo más normal es que llegue un momento en el que añadir nuevos procesadores no mejora en absoluto las prestaciones. La eficiencia EP se define como SP/P, y está relacionada con el aprovechamiento que se hace del añadido de nuevas máquinas . En algunos (contados) casos puede suceder que se dé un escalado superlineal, es decir, que la aceleración crezca más rapidamente que el número de procesadores añadidos, o la eficiencia es mayor que 1; suele suceder cuando la división en diferentes procesadores interacciona positivamente con el algoritmo, ofreciendo una mejora superior a la que se daría si se ejecutara en una sola máquina.
Los algoritmos evolutivos paralelos tienen forzosamente que aprovecharse de las tecnologías existentes. Un AE puede paralelizarse de diferentes formas, como está bastante bien expuesto en este tutorial de Tomassini y en este artículo de Alba y Tomassini (necesitas tener acceso a IEEExplore).
Para empezar, hay que considerar qué se paraleliza. La forma más simple de hacerlo es paralelizar simplemente la evaluación de cada uno de los individuos, en lo que se suele denominar farming o bien paralelización amo/esclavo. Uno de los ordenadores o procesadores actúa como amo, enviando individuos para evaluar a los otros procesadores, que devuelven su valor. La población se mantiene dentro de un solo procesador, y, conceptualmente, no tiene ninguna diferencia con un algoritmo evolutivo tradicional. Este método también se suele llamar paralelización global, o estrategia panmíctica, porque no hay ninguna restricción a la reproducción.
Sin embargo, el escalado de este tipo de métodos es bastante deficiente; dado que están basados en un solo servidor, llega un punto en el que la red de ese servidor se satura. Por eso, históricamente se llegó a otro tipo de estrategias, basadas en dividir la población. En realidad, tampoco hay que ser neurocientífico para, con una población de n individuos y P procesadores, crear P subpoblaciones de tamaño n/P, y dejarlas evolucionar de forma independiente. A cada una de estas subpoblaciones se les suele llamar islas o demes, y, en principio, pueden funcionar como algoritmos independientes. Lo que ocurre es que es mejor dejarles intercambiar de vez en cuando algún miembro de la población, en lo que se suele llamar migración. La migración puede ser síncrona: todos los procesadores se sincronizan en un momento dado, por ejemplo, cada T generaciones, e intercambian miembros de la población; o asíncrona, cada procesador envía o recibe individuos cuando buenamente puede o le viene en gana.
Una vez que la población se ha dividido en diferentes islas, hay que considerar y ser selectivo en qué isla puede enviarnos inmigrantes, y a qué islas enviamos nosotros los emigrantes. Se habla entonces de topología; es decir, de una forma de la red que se superpone a la red física donde se ejecutan los algoritmos. Por ejemplo, se puede usar una topología en anillo: cada procesador está conectado a otros dos, y añadir nuevos procesadores no añade nuevas conexiones a los procesadores existentes. Tiene la ventaja de presentar buenas propiedades de escalado, pero la desventaja de que la difusión de las buenas soluciones es bastante lenta. Otra topología popular es la de rejilla, también llamada algoritmos evolutivos paralelos celulares: los procesadores se sitúan en una rejilla, de forma que cada procesador intercambia individuos sólo con sus 4 u 8 vecinos. Se pueden imaginar también otro tipo de topologías mixtas, que mezclen anillo con rejilla, por ejemplo.
Pero lo más normal es que se use la topología de aquí te pillo, aquí te mato, usando los procesadores que haya, de diferentes tipos, cuando se pueda; por eso, los algoritmos evolutivos paralelos actuales suelen ser asíncronos, y sin una topología fija, tal como se propugna en el proyecto DREAM: usando una red P2P, cada nodo nuevo se conecta a algún nodo conocido de la red, y puede recibir o enviar código para ejecutarse.
También es normal que se gorroneen ciclos de CPU, al estilo del SETI@home; bajándote un cliente o un simple applet Java estás ejecutando el experimento de alguien; el applet en Java se conecta con el servidor usando sockets o RMI, y recibe información del mismo, que procesa y devuelve. Por el modelo de seguridad de Java, se trata forzosamente de una arquitectura cliente-servidor. Esto se ha presentado, por ejemplo, en este trabajo, denominado JavaGenes.
La optimización multiobjetivo (u optimización multicriterio, multiprestaciones o optimización vectorial) (de la que hay un excelente tutorial de Carlos Coello se define como el problema de encontrar un vector de variables de decisión que satisfacen unas restricciones y optimizan una función vectorial cuyos elementos representan a la función objetivo. Estas funciones forman una descripción matemática de criterios de evaluación que generalmente están en conflicto unos con otros. Por tanto, el término "optimizar" implica encontrar una solución que daría los valores de todas las funciones objetivo aceptables para el diseñador.
Es raro que exista un solo punto que satisfaga todas las funciones objetivo; normalmente se busca un equilibrio al tratar con problemas de optimización multiobjetivo; por lo tanto, el concepto de óptimo es diferente. El concepto más normal de óptimo fue propuesto originalmente por Edgeworth, y más adelante por Pareto, y se suele denominar óptimo Pareto u óptimo tipo Pareto; un vector es óptimo pareto si no existe ninguno cuyos valores sean mejores para cada uno de los componentes (estrictamente, si son menores o iguales para todos, y al menos menor estricto para uno de ellos). Lo más habitual es que no exista un solo óptimo Pareto, sino un conjunto de ellos; a este conjunto de solucione se le suele denominar conjunto no dominado, y a su gráfico se le suele llamar frente Pareto.
Históricamente, ha habido muchas formas de resolver problemas de optimización multiobjetivo usando algoritmos genéticos. El más inocente es la utilización de funciones agregativas, es decir, una combinación lineal de las diferentes funciones que se tienen que optimizar, asignándole a cada una un peso. Se crea así una función de evaluación que se puede usar directamente en cualquier método de selección de los algoritmos evolutivos. Sin embargo, no siempre funciona bien, es difícil establecer los pesos, y es incapaz de generar todos los miembros de un frente de Pareto si da la casualidad de que es cóncavo.
Otro enfoque, denominado VEGA (vector evaluated genetic algorithm, dividía la población en tantas subpoblaciones como objetivos diferentes, y hacía evolucionar cada población por separado, fijándose sólo en uno de los objetivos. Cada cierto tiempo, las poblaciones se volvían a mezclar y a dividir; de esa forma, se esperaba que se obtuviera el frente de Pareto al cabo de cierto tiempo. Sin embargo, no funciona demasiado bien; funciona para obtener soluciones de compromiso, pero no se puede obtener el conjunto de Pareto.
La mayoría de los algoritmos posteriores tienen en cuenta el concepto de dominancia para usarlo como evaluación de una solución, y además se centran en obtener el frente de Pareto de forma explícita. Por ejemplo, el MOGA (multiobjective genetic algorithm) considera como fitness de un individuo la inversa del número de individuos en la población por los cuales es dominado; el fitness obtenido se linealiza por interpolación, de forma que todos los individuos con un rango determinado tengan el mismo fitness. Para que se produzca un reparto uniforme en el frente de Pareto, se usa la técnica denominada sharing, aplicada sobre los valores reales de la función de evaluación. Sin embargo, el problema principal es que su funcionamiento depende de la técnica de sharing que se use, y el factor de sharing usado. En general, sin embargo, funciona bien y es una técnica relativamente popular.
Otros algoritmos en uso hoy en día son NSGA (nondominated sorting genetic algorithm), de Deb y Srinivas, que usan una división de la población en "capas" dependiendo de su dominancia, y sharing para mantener la diversidad; cada capa recibe un fitness que es proporcional al tamaño a la población. Sin embargo, este algoritmo es menos eficiente que el MOGA, por lo que se creó una segunda versión, NSGA II, que usa elitismo, y una comparación mediante crowding, en vez de sharing. También hay un NPGA (niched Pareto genetic algorithm), que usa un sistema de selección mediante torneo basado en la dominancia Pareto, pero en vez de tener sólo dos invididuos para comparar, usa hasta el 10% de la población en cada comparación. Cuando hay un empate, se usa sharing para resolverlo.
Finalmente, una de las técnicas más recientes, SPEA (Strength Pareto Evolutionary Algorithm, de Zitzler & Thiele), trata de integrar diferentes técnicas: usa un archivo de soluciones no dominadas, y para cada uno de ellos, se calcula una fuerza, que es similar al ranking en MOGA, porque es proporcional al número de soluciones que domina; usa una técnica de clustering para mantener la diversidad.
Los mapas autoorganizativos de Kohonen son un algoritmo, a veces agrupado dentro de las redes neuronales, que a partir de un proceso de entrenamiento agrupa los datos según una serie de características. El Mapa de Kohonen, o SOM (self-organizing map) se usa para diferentes aplicacaciones:
Clustering: se pueden agrupar datos del conjunto de entrada, atendiendo a diferentes criterios.
Visualización: este agrupamiento, como se realiza de una forma ordenada, permite visualizarlo y descubrir características nuevas, o relaciones que no se habían previsto de antemano.
Clasificación: una vez calibrado el mapa, o asignada algún tipo de etiqueta a cada clusters, se puede usar para clasificar sobre datos desconocidos.
Interpolación de una función: asignando valores numéricos a cada uno de los nodos de la red de Kohonen, se pueden asignar esos valores numéricos a los vectores de entrada.
Cuantización vectorial, es decir, aplicación de una entrada continua a una salida que está discretizada
Los SOMs son algoritmos no-supervisados; eso quiere decir que no usan la etiqueta de los datos para el entrenamiento; sin embargo, en la mayor parte de los casos se usa algún tipo de etiqueta para visualizar los datos correctamente. Se denominan también algoritmos competitivos porque en el entrenamiento sólo se entrena una sola "neurona" de cada vez, lo cual significa que la representación de cada zona del espacio de entrada está concentrada por neuronas, no distribuida.
Hasta el momento, ha habido cientos de aplicaciones de los mapas autoorganizativos de Kohonen, muchas de ellas en Biocomputación. En este tutorial se tratará de dar un enfoque práctico al uso de los mapas de Kohonen en biocomputación, aplicándolo a problemas comunes en el área y usando herramientas habituales en la misma
Los algoritmos de clasificación no supervisados son aquellos que no requieren un etiquetado de cada uno de los vectores de entrada; se suelen llamar también algoritmos auto-asociativos, porque asocian entradas a ellas mismas. Una buena explicación de estos algoritmos se halla en la FAQ de redes neuronales.
El tipo más común de algoritmos de aprendizaje o clasificación no supervisada son los algoritmos de análisis de grupos o clustering; estos algoritmos tratan de dividir las muestras del conjunto de entrada en una serie de grupos con características comunes. Un algoritmo debe descubrir cuáles son estos clusters, pero también cuáles son las características que define ese cluster y cuántos clusters hay; pero éste último es un problema que no tiene solución fácil. También se denominan algoritmos de cuantización vectorial o VQ (vector quantization), pues se pueden usar para sustituir un elemento perteneciente a un grupo por un representante de ese grupo, habitualmente llamado vector código o centro del grupo. La cuantización vectorial pretende reducir la cantidad de bits a transmitir en una línea de comunicaciones, al sustituir un vector por un código que indica qué representante se está transmitiendo; la técnica, además, suprime el ruido.
Dentro de las redes neuronales, el algoritmo no supervisado más común es el mapa autoorganizativo de Kohonen (SOM), pero hay otro método denominado aprendizaje hebbiano que consiste en aumentar el valor de los pesos que unen a dos neuronas si se activan a la vez, y disminuir el valor si se activan de forma diferencial. Una red hebbiana se puede disponer en una sola capa o varias: las entradas se propagan a la capa interna, y a la salida, y tras la propagación, se cambian los pesos de la forma indicada. El aprendizaje hebbiano equivale a un análisis de componentes principales de las entradas.
Una red neuronal supervisada tal como el perceptrón multicapa se puede convertir en no supervisada usando las entradas como salidas; de esta forma, la capa interna extraerá los componentes principales de las entradas, y se podrá usar, por ejemplo, como memoria asociativa; o bien, analizando las activaciones de la capa interna, se pueden asignar diferentes grupos a las entradas.
Los métodos no supervisados se suelen usar en lo denominado análisis de datos exploratorio, es decir, en una fase del análisis de los datos, cuando no se sabe de antemano cuáles son los grupos naturales que se forman, y se quiere visualizar la abundancia y la relación que hay entre los grupos "naturales"; se puede decir que una de sus principales aplicaciones es la visualización de datos multidimensionales, porque un algoritmo no supervisado actúa como una proyección de un espacio multidimensional a otro de dimensiones visualizables. También se pueden usar como fase inicial de algoritmos de aprendizaje supervisados: un algoritmo como el k-medias o el mismo SOM se pueden usar para inicializar algoritmos de aprendizaje supervisado tales como el LVQ (Learning Vector Quantization).
Los algoritmos de clustering agrupan, de forma no supervisada, las muestras de entrada en una serie de grupos, extrayendo, a la vez, unos representantes de la muestra de entrada; a este grupo se le llama habitualmente diccionario.
Hay dos grupos de algoritmos de clustering: los jerárquicos, que van creando clusters de pequeño tamaño, incluso incialmente con un solo componente, y los van fusionando hasta obtener clusters de tamaño superior; diferentes versiones de algoritmos se diferencian por las reglas que usan para unir clusters o separarlos; el resultado final es un árbol de clusters denominado dendrograma, que muestra como los clusters se relacionan unos con otros. El clustering jerárquico se ha usado, por ejemplo, para clasificación de documentos, o incluso para clasificación en biocomputación.
Por el contrario, el clustering no jerárquico calcula los clusters directamente; los algoritmos más populares, tales como el k-medias y el ISODATA. K-medias, también llamado a veces c-medias, funciona de la forma siguiente: se escoge inicialmente un número de clusters (se puede haber hallado ese número usando alguna técnica de análisis exploratorio, o, la mayor parte de las veces, a ojo de buen cuberoTM) Se escogen aleatoriamente el mismo número de vectores de referencia, usando alguna provisión adicional, por ejemplo, una distancia mínima entre ellos; a continuación, se asigna cada elemento de la muestra de entrada al vector de referencia más cercano. Una vez asignados todos los vectores de la muestra, se actualizan los vectores de referencia como la media de todos los vectores en un clusters. El algoritmo se repite hasta que en dos iteraciones no varíen los vectores de referencia, o, lo que es lo mismo, la distancia media de los vectores de la muestra a los vectores de referencia más cercanos o ganadores.
El algoritmo ISODATA es similar, pero el número de clusters no está fijo de antemano. Un cluster se divide si su desviación estándar excede un valor determinado, o el número de elementos de un cluster es dos veces un valor predeterminado; dos clusters se fusionan si su distancia es inferior a un umbral, o bien si el número de elementos que contienen es inferior a otro umbral establecido.
Ambos algoritmos tienen el problema de la inicialización de los vectores de referencia, y del valor inicial (también final, en el caso del k-medias) del número de clústers. la existencia de diferentes parámetros en el caso del ISODATA lo hace también complicado de manejar.
En todo caso, ambos son algoritmos de búsqueda, o de optimizazión: consiste en minimizar la distancia cuadrática media de los vectores muestra a los de referencia. ¿A alguien de los que ha seguido este tutorial se le ocurriría una manera mejor de hacerlo?
Como al mapa de Kohonen no le falta más que el volante forrado de leopardo, también puede usarse para proyección multidimensional, como hemos visto que sucede con los algoritmos de aprendizaje no supervisado. En realidad, es un método de proyección no lineal. Los métodos de proyección lineales, tales como el análisis de componentes principales, tratan de hayar un subespacio de pocas dimensiones que contenga la máxima varianza de la muestra de entrada; una vez hayado, se pueden proyectar las muestras sobre ese espacio, y usarlas para clasificación supervisada. Sin embargo, no siempre se puede proyectar linealmente a unas pocas dimensiones, y hay que usar sistemad de proyección no lineal. Uno de ellos es el denominado escalado multidimensioal (Multidimensional scaling, MDS), que usa las distancias entre los diferentes elementos de la muestra y trata de proyectarlos a un espacio de dimensión inferior, habitualmente dos. Este algoritmo trata de mantener las relaciones topológicas, igual que lo hace el mapa de Sammon. Últimamente han surgido algoritmos más potentes, como el análisis de componentes curvilíneos, desarrollado a partir del mapa de Kohonen, y que mejora el mapa de Sammon en el sentido que favorece la reproducción de distancias cortas en la proyección con respecto a las distancias largas.
Un mapa de Kohonen es un conjunto de vectores de dimensión n distribuidos habitualmente en una retícula bidimensional (aunque nada impide que se distribuyan en 3 o más dimensiones). Para cada vector (al que a veces llamaremos nodo o neurona) se define un vecindario: cada vector puede tener 8 vecinos (es decir, una retícula rectangular) o 6 (retícula hexagonal). Hay razones teóricas para preferir una u otra; mientras que la más popular es la rectangular, la hexagonal tiene una base teórica más sólida.
La vecindad tiene otro parámetro: la forma de la función por la que se cambian los valores de los vectores que hay en ella: una forma tipo gaussiana (gaussian) hara que el cambio de valores disminuya con la distancia, mientras que una forma tipo burbuja (bubble) cambiará de la misma forma todos los vectores que pertenezcan a la vecindad.
Para entrenar un mapa de Kohonen, primero hay que tener un conjunto de datos, que se dividirá en tres conjuntos: entrenamiento, prueba y validación. El de entrenamiento servirá precisamente para eso, el de prueba para seleccionar un mapa entre varios, y el de de validación, posteriormente, para establecer el error final, que es el que vale.
Rara vez los conjuntos sirven tal como los dan; suelen tener la mala costumbre de tener valores en escalas muy diferentes, variabilidades muy diferentes, e incluso algunos tienen la mala costumbre de ser categóricos. Por eso, normalmente, previamente al entrenamiento, hay que realizar algún tipo de preprocesamiento, para que todas las variables tengan aproximadamente el mismo rango y la misma desviación estándar. La forma más segura es hacer lo siguiente:
Convertir variables categóricas de n categorías en n variables. Los valores de estas variables dependerán de cómo hayamos preprocesado el resto del fichero: normalmente se pondrá al valor máximo en caso de que la variable corresponda a esa categoría y en el valor mínimo en el caso de que no. Por ejemplo, en una variable categórica con 3 categorías, la segunda categoría se codificaría como [ min, max, min], que podría ser [-1, 1, -1].
Normalizar el resto de las columnas, restando la media y dividiento por la desviación estándar. Así todas las variables tendrán un rango entre -1 y 1.
Otros preprocesos posibles son aplicar logaritmos, en caso de que el rango de variación pase por varios órdenes de magnitud, o restar el mínimo y dividir por el rango de variación, para dar diferentes variables en el rango [0,1]. Aún así, cuando se trata de variables muy diferentes, sobre todo en el caso de que la distribución de las variables sea muy diferente, los modelos que se van a hallar no son excesivamente buenos, y habría que someterlos a algún preproceso adicional.
1. Crear en Perl un conjunto aleatorio, con 10 variables, una de las cuales es categórica con 3 categorías, otra son números reales entre 0 y 10000, y el resto son números aleatorios entre -10 y 10. Crear un programa para preprocesar este conjunto. 2. Uso de alguno de los sitios on-line que aplican el mapa de Kohonen: GEPAS o SOMCD. En el primero, usar el conjunto de datos creado anteriormente para ver resultados de clustering. En el segundo, usar el ejemplo para calcular los valores de estructura secundaria de una proteina a partir de los datos de dicroismo circular ejemplo u obtenidos de otro sitio.
Una vez el conjunto está bien preprocesadito, en un formato que sea el adecuado para pasárselo al programa correspondiente, viene el entrenamiento en sí, y la arquitectura de la red elegida (hexagonal o cuadrada). En dos palabras, consiste en lo siguiente:
Inicialización de los vectores del mapa de Kohonen.. Se puede hacer de muchas formas diferentes: aleatoriamente dentro del rango de variación de cada variable, y con una distribución determinada: uniforme, gaussiana, o bien aleatoriamente con valores pequeños, mucho menores que ese rango de variación; usando vectores del conjunto de entrenamiento, lo cual hace que no tenga uno que preocuparse por el rango de variación, o bien usando algún algorimo tal como el k-medias, que permite tener ya inicialmente una población de vectores que cubre más o menos el espacio de entrada.
se escoge aleatoriamente un vector del conjunto.
se calcula el vector más cercano de entre los del mapa, y se le denomina ganador;
se cambia el valor de ese vector y de otros vectores en su vecindad de forma que se acerquen más al vector de entrada. El tamaño de la vecindad disminuirá a lo largo del entremamiento; esa es la clave de la autoorganización.
Normalmente el entrenamiento se divide en dos fases: una primera en la que la vecindad disminuye, y cuya longitud viene a ser unas 10 veces el tamaño del conjunto de entrenamiento, y una segunda en la que la vecindad permanece fija (a veces llamada fase de autoorganización), que suele durar 100 veces el tamaño del conjunto de entrenamiento.
La tasa de cambio de los vectores ganadores y su vecindad también cambia durante el entrenamiento; tiene al principio un valor, y va disminuyendo hasta ser cero al final de la fase. Normalmente, para la primera fase se suele usar una tasa del orden de 0.1, y para la segunda, valores bastante menores.
El entrenamiento consiste, evidentemente, en un procedimiento iterativo de minimización del error cuadrático medio; por lo tanto, cuanto menor sea este error, mejor. Sin embargo, tampoco conviene que sea demasiado pequeño, porque se trataría de sobreentrenamiento. Como regla para evitar el sobreentrenamiento, el modelo (en este caso el mapa de Kohonen) no debe tener más de 0.1 veces el número de parámetros en el conjunto de entrenamiento, es decir, no superar el 10% de su tamaño. En algunas aplicaciones, sin embargo, el mapa de Kohonen puede ser incluso mayor que el conjunto de entrenamiento.
1. Usar SOM_PAK sobre el conjunto de entrenamiento aleatorio creado anteriormente. Inicialmente usar el comando vfind, que va preguntando los diferentes valores. Posteriormente, crear un fichero de parámetros, y usadlo de la forma siguiente: vfind < fichero.param. 2. Tomando alguno de los conjuntos de datos de GEPAS, aplicadle el mapa de Kohonen usando SOM_PAK. Estimad cuál es la mejor mezcla de parámetros usando como medida el error cuadrático medio.
Calibrando mapas
Una vez entrenado el mapa, ¿qué se puede hacer con él? Pues usarlo para algo, se supone. A pesar de que el algoritmo de Kohonen es no supervisado, en la mayor parte de los casos se usan etiquetas para identificar de alguna forma cada uno de los datos que se le ha pasado. Esas etiquetas las vamos a visualizar sobre el mapa, para ver qué se ha hecho con ellas. Lo primero es calibrar el mapa, asignando a cada vector la etiqueta del más cercano de entre los que hay en el conjunto de entrenamiento.
Luego, dependiendo de la aplicación, se hacen más análisis sobre los resultados. Uno de ellos se denomina mapa de Sammon, una herramienta de proyección bidimensional que permite proyectar un conjunto de muchas dimensiones en dos dimensiones. La proyección permite descubrir agrupamientos "naturales" del conjunto de datos; es una alternativa al mapa de Kohonen. También se suele usar para proyectar el mapa de Kohonen en sí, dándote una idea de cuáles son los clusters que forman los vectores que a su vez forman el mapa de Kohonen. En el paquete SOM_PAK se incluye sammon, un programa que permite calcular el mapa de Sammon. Con lo que hay que tener más cuidado es con el runlength, el número de iteraciones del algoritmo. Si se pasa uno quedará un mapilla bastante mísero. El número correcto dependerá del problema, pero un número adecuado puede ser 10. Uno de los principales problemas del mapa de Sammon es que es muy sensible a los datos que trillan fuera de parva, así que habrá que eliminarlos uno por uno antes de tener algo decente.
1. Aplicar el mapa de Sammon a los datos del Diauxic shift, tratando los outliers adecuadamente. Describir qué estructura tienen los datos. Aplicar posteriormente el mapa de Kohonen, y ver qué grupos se forman.
Otra herramienta que permite apreciar el agrupamiento de los datos es el algoritmo UMatrix, que se usa sobre el mapa ya calibrado, y da una medida de la distancia entre dos elementos del mapa, y la distancia media de cada elemento a los que lo rodean. Esto permite apreciar los clusters: son zonas "claras" separadas por "zonas oscuras". Es una forma un tanto visual de verlo, pero es tan objetivo como asignar un umbral determinado, y decir que toda distancia por encima de ese umbral hace que se separen los clusters.
UMatrix se aplica en SOM_PAK usando el programa umat, y, aplicándolo sobre un mapa entrenado con los datos del Diauxic Shift usados anteriormente, da un resultado como el que se muestra en la imagen
En la imagen se ve, por ejemplo, que hay dos clusters, que se reparten más o menos a partes iguales el espacio en el mapa de Kohonen; están separados por una banda central donde la distancia entre vectores es mayor. En este caso, el mapa de Kohonen refleja la misma estructura de dos clusters que se veían en el mapa de Sammon; aunque no siempre están las cosas tan claritas.
1. Comparar los resultados obtenidos observando el UMatrix con los resultados de los algoritmos SOTA y SOMTree tal como aparecen en el GEPAS. ¿Cuántos clusters hay? ¿Cuántos se aprecian?
La última fase de análisis de datos usando el mapa de Kohonen consiste en el análisis de planos, es decir, ver cómo se distribuyen los valores de cada uno de los componentes de los vectores del mapa a lo largo y ancho del mismo. Esta distribución permite dar reglillas sobre cuáles son los componentes más representativos en cada uno de los clusters, y qué valores de cada componente son los que los caracterizan. Los valores de los componentes se suelen representar sobre el propio mapa, con un tono oscuro indicando valores altos y un tono claro valores bajos, todo ello relativamente a los valores máximos y mínimos para cada componente.
En este caso, por ejemplo, se puede ver que el cluster a la izquierda del mapa corresonde a valores bajos de los tres primeros componentes, y altos de los tres últimos, y el cluster a la derecha justo al contrario.
1. Sobre los datos de esporulación del GEPAS aplicar el mapa de Kohonen, extraer clusters usando el algoritmo UMatrix y finalmente, hacer un análisis por planos para caracterizar cada uno de los clusters.
Perl: Módulos Bio
Módulos AI::Kohonen
Para integrar el mapa de Kohonen en una aplicación, se puede usar SOM_PAK como programa externo, pero siempre es más fácil disponer de un módulo accesible desde un lenguaje de programación tal como Perl. Perl, además, tiene una serie de módulos, agrupados dentro del espacio de nombres Bio, que sirven para manejar datos relacionados con biocomputación y acceder a bases de datos relacionadas con la misma. Estos módulos están accesibles desde CPAN, el sitio de los módulos en Perl, o bien desde el sitio de BioPerl.
La serie de módulos Bio::DB sirve, por ejemplo, para acceder a bases de datos biológicas tales como GeneBank o SwissProt:
Estas secuencias se pueden manejar en una variedad de formatos diferentes, o realizarse una serie de operaciones sobre ellas: invertir, transformar de aminoácidos a proteinas y viceversa, o enviarse a una serie de sitios web tales como BLAST.
Finalmente, se pueden emplear para tratarlos con el mapa autoorganizativo de Kohonen, usando el módulo AI::NeuralNet::Kohonen:
$_ = AI::NeuralNet::Kohonen->new( map_dim_x => 39, map_dim_y => 19, epochs => 100, table => "R G B 1 0 0 0 1 0 0 0 1 1 1 0 1 0 1 0 1 1 1 1 1 "); $_->train; $_->save_file('mydata.txt'); exit;
Para tratar con secuencias biológicas, habría primero que tratarla para poderla meter en el argumento table de la red de Kohonen. El formato de salida es compatible con el mapa autoorganizativo de Kohonen; y se puede usar también para aplicar los resultados una vez entrenada la red.
Una de las posibles aplicaciones del mapa de Kohonen es a la clasificación de conjuntos de documentos. Genéricamente, a esta aplicación se le llama WEBSOM. Lo que se persigue con esta aplicación no es solo la clasificación de documentos, sino también el crear un mapa de un corpus de documentos, de forma que se pueda navegar por él entre documentos similares, y, además, ver la estructura a gran escala del grupod de documentos, con el objeto de detectar grupos naturales (clusters).
El algoritmo funciona de la forma siguiente: primero, se crea un mapa de palabras; el objetivo es desambiguar los significados de las palabras, detectando sinónimos y otras relaciones semánticas (hiperónimos, por ejemplo). Para ello, se entrena un mapa de Kohonen con cada palabra representada por su contexto promediado: se toma cada palabra y se le asigna un vector n- dimensional aleatorio. Una vez hecho eso, se calcula para cada palabra la que le antecede y sucede, teniendo en cuenta finales de frase y principios como si fuera otra palabra. Una vez tomadas todos los antecesores y sucesores, se promedian; la representación de la palabra que se usará será los vectores antecesores y sucesores promedio yuxtapuestos.
Cualquier otro método que sirva para asignar un vector único dependiente del contexto a cada palabra sirve también. Por ejemplo, si tenemos los textos categorizados (por ejemplo, secciones de un periódico), se pueden usar para cada palabra un vector de las frecuencias con las que aparece en cada sección. También se pueden considerar contextos más extensos: de 4 palabras, en vez de dos palabras. O se puede representar cada palabra con un vector que represente co-ocurrencia de una palabra en un documento determinado; esta codificación se usa para el análisis semántico latente. Dependiendo de la aplicación, será necesario uno u otro.
El resultado de entrenar un mapa de Kohonen con este conjunto de palabras es un mapa de palabras, que se supone que van a estar organizadas por significado (en realidad, por contexto): palabras similares, incluso sinónimos, irán a parar al mismo nodo de la red de Kohonen, y palabras que se usen en el mismo dominio irán a parar al mismo nodo o a nodos cercanos.
Este mapa se usará como base para la codificación de cada documento: un documento será un histograma formado por el número de veces que se "activa" cada nodo del mapa de palabras; es decir, cada documento irá representado por un vector que contendrá como componentes la cantidad de veces que se haya activado cada nodo del mapa de palabras de Kohonen. A su vez, estos vectores se usarán para entrenar un nuevo mapa de Kohonen, que será, en este caso, un mapa de documentos. Los resultados son subjetivamente buenos, permitiendo, además, navegar sobre colecciones de documentos por similaridad entre los mismos, algo que no permiten otras técnicas de codificación de los mismos. Hay una demo online de los resultados usando grupos de noticias de Usenet.
La principal referencia en este tutorial, y además, el libro que contiene el enfoque y todos los temas tratados en el mismo, es Modern Heuristics, de Zbigniew Michalewicz, David B. Fogel . El libro intercala descripciones de algoritmos de búsqueda con problemas de ingenio, con un enfoque destinado a la resolución general de problemas. Aparte de los algoritmos clásicos, dedica varios capítulos a los métodos adaptativos, como algoritmos genéticos, redes neuronales, y otros como lógica borrosa. Aunque no trata ninguno de los temas en profundidad, cubre todos los algoritmos y es un excelente punto de partida para introducirse en otros algoritmos.
Dictionary of algorithms and data structures, con información breve, pero exhaustiva, de todos los algoritmos que se le puedan ocurrir a uno.
La red de Kohonen viene bien explicada en su propio libro, Self-Organizing Maps, de Teuvo Kohonen, aunque hace mucho énfasis en aspectos teóricos y poco en los prácticos. Visual Explorations in Finance: With Self-Organizing Maps (Springer Finance) by Guido J. Deboeck (Editor), Teuvo Kohonen (Editor) tiene un enfoque mucho más práctico, aunque está principalmente enfocado a información financiera.
Por último, un tutorial en castellano sobre uso de la red de Kohonen: uno en la Universidad de Cádiz, parte de una presentación.

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