Procedimientos metaheurísticos en optimización combinatoria

Metaheuristic methods in combinatorial optimization

Los métodos descritos en este artículo reciben el nombre de algoritmos heurísticos, metaheurísticos o sencillamente heurísticos. Este término deriva de la palabra griega heuriskein, que significa encontrar o descubrir y se usa en el ámbito de la optimización para describir una clase de algoritmos de resolución de problemas.

En contraposición a los métodos exactos que proporcionan una solución óptima del problema, los métodos heurísticos se limitan a proporcionar una buena solución no necesariamente óptima. Lógicamente, el tiempo invertido por un método exacto para encontrar la solución óptima de un problema difícil, si es que existe tal método, es de un orden de magnitud muy superior al del heurístico (pudiendo llegar a ser tan grande en muchos casos que sea inaplicable).

En este texto se consideran los llamados problemas de optimización combinatoria. En estos, el objetivo es encontrar el máximo (o el mínimo) de una determinada función sobre un conjunto finito de soluciones que se denota por S. No se exige ninguna condición o propiedad sobre la función objetivo o la definición del conjunto S. Es importante notar que, dada la finitud de S, las variables han de ser discretas, restringiendo su dominio a una serie finita de valores.

Recent Advances on Meta-Heuristics and Their Application to Real Scenarios

Avances recientes sobre metaheurística y su aplicación a escenarios reales

Este documento pretende atraer el interés de los investigadores y los profesionales hacia la aplicabilidad de algoritmos metaheurísticos a escenarios prácticos que provienen de diversas disciplinas del conocimiento. Se hace énfasis en algoritmos evolutivos e inteligencia de enjambre (swarm intelligence) como medios computacionales para balancear de modo efectivo la compensación entre optimalidad de las soluciones producidas y la complejidad derivada de su estimación. En síntesis, el escrito sirve como un buen punto de partida —con base en una revisión rigurosa de la literatura y la orientación práctica de sus contenidos— para investigadores novatos en las primeras etapas de sus estudios en metaheurística.

El documento está dividido en cinco capítulos:

• Using Multiobjective Genetic Algorithm and Multicriteria Analysis for the Production Scheduling of a Brazilian Garment Company
• Grasp and Path Relinking to Solve the Problem of Selecting Efficient Work Teams
• Meta-Heuristic Optimization Techniques and Its Applications in Robotics
• A Comparative Study on Meta Heuristic Algorithms for Solving Multilevel Lot-Sizing Problems
• A Two-Step Optimisation Method for Dynamic Weapon Target Assignment Problem