Diseño e implementación de un algoritmo paralelo de enjambre para el problema de la mochila 0-1

Esta tesis de investigación aborda el conflicto de resolver eficientemente instancias difíciles del problema de la mochila 0-1 mediante una metaheurística de inteligencia de enjambre utilizando un enfoque paralelo. Los enfoques tradicionales para la solución de las instancias fuertemente correlacionadas son métodos exactos con la limitante de resolver instancias de pequeña dimensión, otros autores han utilizado métodos aproximados. Sin embargo, estos métodos siguen un procesamiento lineal en donde el tiempo de ejecución puede llegar a ser excesivo. A través de la propuesta de solución de una variante metaheurística de inteligencia de enjambre con enfoque paralelo se contribuye para resolver las instancias difíciles que representan situaciones de la vida cotidiana, logrando obtener soluciones en tiempos de computo de ejecución razonable en comparación con los métodos de solución exacta y metaheurísticas secuenciales, consiguiendo mejorar la calidad de la solución de forma eficiente y eficaz. La propuesta se validó mediante la solución de un conjunto de instancias de prueba utilizando diferentes instancias de la literatura, así como de las instancias fuertemente correlacionada, no correlacionada y débilmente correlacionada, utilizando diferentes restricciones de capacidad de .25, .50 y 75 de la suma de los pesos de los elementos de la mochila. El número de elementos de las instancias probadas fue desde 50 hasta 10,000. Los resultados obtenidos se compararon con los obtenidos con los algoritmos exactos y aproximados citados en la literatura, donde la solución de nuestra metaheurística paralela es buena y con un buen desempeño. Los resultados son satisfactorios porque muestran que la variante del algoritmo propuesto obtiene buenos porcentajes de calidad y cercanía a la solución óptima con diferentes capacidades de la mochila. Finalmente, se considera que el enfoque de solución puede ser utilizado para resolver problemas reales de la vida cotidiana que caen dentro de la clasificación de instancias fuertemente correlacionadas.