Una propuesta para diversificar el campo de aplicación de un algoritmo Hill Climbing

Abstract

Cuando se habla de optimización, se busca obtener la mejor solución posible a un problema determinado, de la mejor manera, utilizando todos los recursos disponibles. Los métodos para encontrar la mejor solución varían de acuerdo a la complejidad del problema enfrentado. A medida que la complejidad de un problema aumenta, crece la necesidad de implementar métodos heurísticos para resolverlo. Por ejemplo, las metaheurísticas basadas en trayectoria (denominadas como Hill Climbing), se aplican a la resolución de problemas de optimización combinatoria, donde el conjunto de posibles soluciones es discreto, o al menos, se puede reducir a un conjunto discreto. Nosotros proponemos modificar el algoritmo Hill Climbing a los efectos de incrementar la diversidad de problemas a los cuales pueda aplicarse este algoritmo. En primer lugar, se analizan y comparan de forma incremental 6 (seis) propuestas de mejora: 5 (cinco) basadas en el algoritmo Hill Climbing y, 1 (una) basada en el algoritmo genético. Luego, desarrollamos nuestra propuesta como resultado del análisis de estas 6 (seis) propuestas de mejora y considerando algunas áreas en las que no se encontraron registros anteriores. En este trabajo, se presenta y describe una propuesta a los efectos de contribuir con nuevas ideas al campo de la optimización combinatoria. Nuestro algoritmo está basado en la hibridación de metaheurísticas poblacionales y en trayectoria. Esta propuesta es el resultado de la investigación desarrollada durante 2016 en la asignatura “Técnicas para la Elaboración de Documentos Científicos-Técnicos”, perteneciente a la carrera de grado “Ingeniería en Sistemas UNPA.”

Keywords

• metaheurísticas
• hill climbing
• optimización combinatoria