Los algoritmos heurísticos son una clase de técnicas de resolución de problemas que se basan en la experiencia y la intuición para encontrar soluciones aproximadas en un tiempo razonable. A diferencia de los algoritmos exactos que buscan encontrar la solución óptima de manera garantizada, los algoritmos heurísticos ofrecen soluciones que son suficientemente buenas para muchos propósitos prácticos. Estos algoritmos son ampliamente utilizados en una variedad de aplicaciones, desde la optimización de recursos hasta la búsqueda de patrones en grandes cantidades de datos.

Los algoritmos heurísticos son especialmente útiles cuando se enfrentan a problemas complejos y de gran escala que son difíciles de resolver mediante técnicas exactas. Además, pueden ser altamente eficientes en términos de tiempo y recursos, lo que los hace una opción atractiva para muchos problemas reales.

A pesar de sus ventajas, los algoritmos heurísticos también tienen algunas limitaciones. En particular, no garantizan encontrar la solución óptima, y las soluciones que encuentran pueden no ser óptimas en todos los casos. Además, los algoritmos heurísticos pueden ser sensibles a los parámetros y la configuración, lo que puede afectar la calidad de las soluciones encontradas.

En resumen, los algoritmos heurísticos son una herramienta valiosa para resolver una amplia gama de problemas complejos, y su comprensión y aplicación continúan siendo un tema importante de investigación y desarrollo en la comunidad de inteligencia artificial y optimización.

Algoritmos heurísticos aplicados a problemas

Búsqueda Local

La búsqueda local es un algoritmo heurístico que se utiliza para encontrar soluciones óptimas o aproximadamente óptimas a problemas de optimización. Este algoritmo se basa en la idea de mejorar gradualmente una solución inicial explorando soluciones próximas y seleccionando aquellas que mejoran la solución actual.

El proceso de búsqueda local se inicia con una solución inicial, que puede ser generada de manera aleatoria o determinada por una heurística previa. A continuación, se evalúa la solución actual y se genera una lista de soluciones vecinas explorando soluciones cercanas a la solución actual. Finalmente, se selecciona la solución vecina que mejore la solución actual y se actualiza la solución actual. Este proceso se repite hasta que se alcance un criterio de parada, como un número máximo de iteraciones o una solución satisfactoria.

La búsqueda local es un enfoque eficiente y a menudo produce soluciones de buena calidad en un tiempo razonable. Sin embargo, es importante tener en cuenta que el algoritmo puede quedarse atrapado en un mínimo local y no encontrar la solución óptima global. Para mitigar este riesgo, se pueden utilizar técnicas como la exploración aleatoria o la utilización de múltiples soluciones iniciales.

En general, la búsqueda local es un enfoque popular y efectivo para resolver problemas de optimización y es ampliamente utilizado en una variedad de aplicaciones, incluyendo la inteligencia artificial, la optimización de recursos y la toma de decisiones. Al ser un algoritmo sencillo y fácil de comprender, es un buen punto de partida para aquellos que buscan soluciones a problemas de optimización.

Este código implementa una versión en español del algoritmo de búsqueda local para maximizar una función.

La función funcion_objetivo() es la función que se desea maximizar. En este caso, la función es -(x - 2) ** 2 + 5, que es una parábola con un máximo en x = 2.

La función busqueda_local implementa el algoritmo de búsqueda local. El proceso de búsqueda local comienza con una solución inicial, que en este caso se genera al azar usando la función random.uniform(-10, 10). La solución inicial se asigna a la variable x_actual.

Después, se realiza un bucle que se repite iteraciones_maximas veces. En cada iteración, se genera un aleatorio (perturbación) usando la función random.uniform(-1, 1) y se agrega a la solución actual (x_actual). Luego, se evalúa la función objetivo en la solución actual y se guarda el resultado en y_actual.

Si y_actual es mayor que y_optimo, se actualiza x_optimo con el valor de x_actual y y_optimo con el valor de y_actual, ya que esto significa que se encontró una solución mejor. Al final del bucle, se devuelve x_optimo, que representa la solución óptima encontrada.

Problema de la mochila

El problema de la mochila (también conocido como el problema de la mochila entera) es un problema de optimización combinatoria que consiste en seleccionar elementos de un conjunto finito de objetos, cada uno con su propio peso y valor, con el objetivo de maximizar el valor total mientras se mantiene el peso total dentro de una capacidad máxima de la mochila.

Este problema tiene una amplia variedad de aplicaciones en la vida real, como la planificación de la producción, la asignación de recursos, la gestión de inventarios y la planificación de rutas, entre otros.

Dado que el problema de la mochila es un problema NP-duro, es decir, que su resolución exacta para instancias grandes es costosa computacionalmente, se utilizan heurísticas para obtener soluciones subóptimas, pero de manera más eficiente.

Este algoritmo utiliza la heurística de búsqueda local, comenzando con una solución aleatoria. Se realizan un número fijo de iteraciones (100) y, para cada iteración, se genera una solución aleatoria. Luego se realiza una búsqueda local para mejorar esa solución.

La búsqueda local comienza eliminando elementos que violan la restricción de capacidad de la mochila. Se selecciona un objeto aleatorio y se elimina de la solución si su inclusión viola la restricción de capacidad. La búsqueda continúa hasta que se alcanza un máximo local o hasta que se ha agotado el número de iteraciones.

Este algoritmo devuelve la mejor solución encontrada y su valor total. El arreglo "pesos" contiene los pesos de cada objeto, el arreglo "valores" contiene los valores asociados a cada objeto y "capacidad" es la capacidad máxima de la mochila.

Conclusión

En resumen, los algoritmos heurísticos y la búsqueda local son herramientas valiosas para la resolución de problemas complejos y ofrecen soluciones eficientes en situaciones en las que la solución exacta es difícil o imposible de obtener en un tiempo razonable. El problema de la mochila es un ejemplo clásico de problema de optimización combinatoria en el que se pueden aplicar estos algoritmos con éxito.

Bibliografía 

Russell, S. J., & Norvig, P. (2018). Artificial Intelligence A Modern Approach (3rd ed.). Pearson.