Técnicas Heurísticas De Resolución De Problemas: Computación Evolutiva Y Redes Neuronales

Introducción: problemas de búsqueda y técnicas tradicionales

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)? [Imagen TSP pirateada de

www.sscnet.ucla.edu/geog/ gessler/borland/wip.htm] 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.

1.1 Modelización de un problema

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.

1.2 Metiéndonos en complicaciones: variación temporal, restricciones

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

...