¿Qué es la heurística y cuándo hay que utilizarla?

En Ciencias de la Computación y Optimización Matemática, solemos buscar un procedimiento que produzca una solución exacta a un problema. En el contexto general, eso significa devolver siempre la respuesta correcta y, en el caso de optimización, la respuesta correcta es la mejor! Pero como vimos en P vs. NP: el problema de un millón de dólares, no todos los problemas se pueden resolver de forma óptima en un tiempo factible. Eso es precisamente lo que motiva un creciente campo de investigación que estudia los métodos para encontrar la mejor solución posible en el tiempo que se tiene. Estos métodos son conocidos como Heurística.

Para ilustrar la utilidad de los métodos heurísticos, tomemos el ejemplo de Gambito de Reina y la complejidad e imaginemos una partida de ajedrez. Más concretamente, consideremos una partida de ajedrez práctica en la que los jugadores tienen un límite de tiempo. Podemos construir un algoritmo para jugar al ajedrez que considere todas las jugadas posibles y elija la mejor. Pero a pesar de haber demostrado ser óptimo, este algoritmo siempre perdería en un juego de la vida real. Incluso con nuestros modernos superordenadores, tardaría una cantidad de tiempo absurda en decidir su movimiento de apertura. Entonces, ¿cómo pudo un ordenador vencer al campeón del mundo, Garry Kasparov, en 1997? Con una heurística, ¡por supuesto!

La principal diferencia entre los métodos exactos y los heurísticos está en el enfoque. Los métodos exactos se centran en encontrar la solución óptima en el menor tiempo posible, lo que, en muchos casos, supone un equilibrio entre intentar encontrar una solución mejor e intentar demostrar que la mejor solución actual es la óptima. Por otro lado, los métodos heurísticos se centran en comprender lo que constituye una "buena" solución y desarrollar un método de búsqueda que aproveche ese conocimiento. Un punto de partida habitual para desarrollar la heurística es replicar la lógica de un profesional. En el ejemplo del ajedrez, una heurística comúnmente utilizada es crear, con la ayuda de ajedrecistas expertos, una función que pueda puntuar una configuración del tablero basada en las posiciones de las piezas. Esta función evita tener que simular todas las partidas posibles hasta el final.

Entonces, ¿debo elegir siempre la heurística? ¡Claro que no! Muchos problemas prácticos se pueden resolver de forma óptima, y si este es el caso, hay que optar por la respuesta óptima. Pero en los casos en que la solución óptima no es posible, hay que conocer los inconvenientes de la heurística y cómo superarlos: 

¿Cuándo es "suficientemente bueno"?

Cuando usted tiene una solución óptima, sabe que no podría haberlo hecho mejor. Pero si usted está utilizando una heurística, nunca sabe si podría tener una mejora del 50% si se esforzara un poco más. Afortunadamente, en la mayoría de los casos, un estudio basado en instancias generadas de su problema puede indicar cuándo un determinado método de búsqueda comienza a estancarse. Con esto, un profesional experto en optimización puede definir unos buenos criterios de parada que, en función de sus necesidades, le proporcionen la mejor compensación entre tiempo y calidad de la solución.

Los humanos no siempre son buenos para resolver problemas

Como ya hemos comentado, una estrategia común para la heurística es utilizar la intuición humana como punto de partida. Eso es fantástico en muchas situaciones, pero a veces las limitaciones y los prejuicios humanos pueden dar lugar a una mala toma de decisiones. Diseñar una buena heurística no es simplemente codificar la intuición profesional en una solución. Un método de búsqueda eficiente que aproveche la velocidad del ordenador es también muy importante para explorar soluciones diferentes e inusuales.

Son difíciles de comparar

Comparar dos heurísticas no es una tarea trivial. Casi siempre se obtiene un resultado mixto en el que el método A da mejores resultados en algunos casos y, en otros, el método B es superior. Un análisis estadístico cuidadosamente construido y un buen modelo informático del problema son muy importantes para identificar un método sólido que dé buenas soluciones en una gran variedad de contextos. Otra buena práctica es utilizar métodos con parámetros libres que se puedan ajustar a diferentes escenarios.  

Autor: Vinícius Mello - Consultor en Cassotis Consulting

  Coautor: Fabio Silva - Gerente Senior en Cassotis Consulting