Resolviendo problemas con heurísticas y metaheurísticas

Seamos sinceros, el discurso de que la inteligencia artificial es para lograr crear una mente artificial que imite la inteligencia humana suena muy bonito e inspirador, pero uno de los principales motivos para los que queremos la inteligencia artificial es que nos solucione problemas. Y a ser posible problemas que nosotros no seamos capaces de resolver fácilmente. Hay problemas que son irresolubles matemáticamente e inabordables por la fuerza bruta con la potencia de cálculo actual. Una de las herramientas que tenemos para resolver estos problemas son las heurísticas y metaheurísticas. Estos algoritmos exploran el espacio de soluciones (el conjunto de todas las posibles soluciones para un problema) usando información sobre la calidad de cada solución para guiarse en la búsqueda de la mejor solución. Estos algoritmos permiten resolver en un tiempo aceptable problemas demasiado costosos como para ser abordados de manera exhaustiva (comprobando todas las posibles soluciones). Pero nada es gratis en esta vida, a cambio
Su principal diferencia es que las heurísticas suelen estar orientadas a un tipo de problema mientras que las metaheurísticas son más genéricas y se pueden aplicar a multitud de problemas.

El origen de estos algoritmos es diverso, desde reglas descubiertas empíricamente, desarrollos matemáticos, prueba y error o claras inspiraciones en fenómenos de la naturaleza. Rara vez estos algoritmos son únicos. Generalmente existen familias basadas en variaciones del mismo algoritmo para mejorar su rendimiento con distintos tipos de problemas.

Pese a una descripción tan genérica estos algoritmos tienen ciertas características en común:

Fitness/distancia:

Todas poseen una función que evalúa una solución y le indica “lo buena que es”.  Aunque hablare casi todo el rato de función de fitness realmente esta función puede adoptar dos formas:

Una función de fitness o bondad que indica lo correcta que es una solución. Su valor, aumenta cuanto más cerca se está del valor deseado.

Una función distancia que indica a qué distancia del valor buscado estamos. Esta función decrece según nos acercamos a la solución ideal.

Aunque nos pueda parecer que son muy distintas realmente hay dos maneras muy simples de convertir un tipo de función en la otra.

Dividir un numero K mayor de 0 por el valor de la función.  K/f(x)

Restarle a un valor K mayor que 0 el valor de la función. en este caso hay que asegurarse de el valor de la función nunca es mayor que K.  K-f(x) 

Esta función ha de ser una representación apropiada del problema real ya que es la aporta información sobre la solución al algoritmo y de su corrección dependerá que se puede encontrar una solución adecuada.

Máximo/mínimo:

Intenta maximizar o minimizar el valor la función de fitness. El punto deseado debe de ser siempre un máximo o un mínimo y hay que crear la función de fitnes para que cumpla ese requisito.

Una función no tiene porque tener un único punto máximo/mínimo de hecho puede tener máximos/mínimos locales que son puntos que son máximos/mínimos en su entorno pero no son el punto máximo/mínimo de la función. Hay que tener cuidado de no quedarse atascado en uno de estos puntos.

Exploración:

Como ya se ha comentado estos algoritmos basan su funcionamiento en explorar el espacio de soluciones guiándose por la función de fitness buscando sus valores máximos (o mínimos).

Podemos imaginarnos el espacio de soluciones como una amplia pradera llena de lomas, cada punto de este terreno es una solución y la altura de cada punto viene determinada por la función fitness.

Ejemplo de espacio de busqueda

Ejemplo de espacio de búsqueda – Imagen obtenida Wikipedia

Estos algoritmos al ver un punto alto se lanzan hacia él cual montañista o cabra que siempre tira al monte y en cuanto llegan a ese máximo puede quedarse “atrapados” en él negándose a seguir explorando el terreno. Para evitar esto se tiene que permitir que exploren soluciones que sean peores que las ya encontradas, sin embargo tampoco han de ser tan “exploradores” que ignoren los máximos o se convertirán en un algoritmo que se mueve aleatoriamente por el espacio de soluciones. Gran parte de la dificultad de hacer funcionar estos algoritmos es lograr el equilibrio entre ambas situaciones.

Coste vs mejor solución:

Generalmente estos algoritmos devuelven aproximaciones de cual es la mejor solución. Para mejorar estas aproximaciones es necesario realizar más iteraciones lo que supone mayor consumo de recursos y coste en tiempo. Hay que buscar un equilibrio entre la exactitud del resultado y el coste en tiempo y recursos del mismo.

Solución aproximada:

No hay seguridad de que lo que se vaya a obtener sea la mejor solución, posiblemente solo se obtenga una aproximación. Pero afortunadamente en el mundo real una buena aproximación puede ser tan validad como la solución ideal. Ademas que en muchos casos se necesita solo una buena solución, sin necesidad que sea la solución óptima.

Dada su variedad también es difícil clarificarlas. Pero vamos a ver algunas características por las que agruparlas:

Una única solución o múltiples soluciones: 

Algunas heurísticas/metaheurísticas usan varias soluciones las cuales van modificando, a veces combinándolas,  para obtener nuevas soluciones. En el caso de una única solución simplemente tiene una solución que van mejorando.

Búsqueda global o búsqueda local:

La búsqueda global busca en todo el espacio de soluciones mientras que la local busca solamente en el espacio cercano a una solución propuesta. Lo mayoría de las heurísticas o metaheurísticas tratan de equilibrar ambos aspectos, sin embargo depende del problema a resolver necesitaremos decantarnos por uno de estos dos lados.

Deterministas o estocásticos:

En el primer caso si ejecutamos la heurística/metaheurística varias veces con los mismos parámetros iniciales e iteramos el mismo número de veces obtendremos siempre el mismo resultado. Mientras que en el segundo caso al entran en juego partes aleatorias la respuesta puede ser diferente, pese a que las condiciones iniciales sean idénticas. Eso significa también que puede ser necesario ejecutar el algoritmo varias veces para asegurarse de que la respuesta obtenida es la más adecuada.

Paralelizables:

Algunas heurística/metaheurística son fácilmente paralelizables. Esta característica puede ser importante si necesitamos resolver un problema con gran consumo de recursos ya que podríamos distribuir su calculo entre varias maquinas.

Inspiradas en la naturaleza:

Muchas metaheurísticas han aparecido de fijarse como en la naturaleza se soluciona el mismo problema. Los insectos, bandadas o los genes han sido inspiradores de varias de ellas. El problema es que este método puede llevar a encontrar metaheurísticas que funcionan sin saber muy bien el porque. sin embargo ha dado muy buenos resultados. Aunque últimamente da la sensación de que el proceso de creación de estas metaheurísticas ha dado la vuelta y parece en algunos casos primero se crea el algoritmo y luego se busca a que se parece ya que este tipo de algoritmos siempre despiertan interés independientemente de que no sean tan buenos o aporten nada a los ya existentes.

Podemos pensar que ya tenemos una solución mágica para todos nuestros problemas. Desgraciadamente no es tan sencillo. Suelen funcionar bien con problemas de optimización matemáticaoptimización combinatoria o satisfación de restricciones. Ejemplos hay muchos, el problema del viajante, el problema de la mochila, el problema de la ocho/n reinas, …

Sin embargo en casos cuando el espacio de soluciones no es fácil de explorar ya sea porque es enorme, hay muchas discontinuidades, muchos máximos locales o una combinación de todas.

Personalmente estos algoritmos me gustan, ya no solo por el interés que tiene de resolver este problemas, si no por fácil que puede resultar resolver alguno problemas irresolubles cambiando la forma de afrontar el problema. La mayoría de estas soluciones adoptan estrategias, que al menos a mi, me resultan curiosas.