Algoritmos metaheurísticos para optimización y aplicación a problemas NP completos

Abstract

En la actualidad las empresas deben enfrentar un conjunto de problemas logístico-operativos, de alta complejidad, conocidos en la comunidad científica como problemas de optimización combinatoria. Actualmente, en esta comunidad se observa una importante tendencia a resolver dichos problemas con la utilización de algoritmos heurísticos y metaheurísticos. Nuestro grupo está abocado al diseño y desarrollo de algoritmos heurísticos y metaheurísticos que resuelvan problemas de optimización. En particular se ha puesto especial énfasis en: el problema de corte y empaquetado, y en el de planificación y programación de recursos y en el ensamblado de fragmentos de ADN. Tanto la optimización de la planificación de recursos como la de generación de patrones de cortes, reducen significativamente los costos de los distintos recursos involucrados. Esto se debe a la mejor utilización que se hace de los mismos, lograda por medio de la aplicación de metaheurísticas. Por otro lado, las metaheurísticas también permiten resolver problemas de optimización en el área de la bioinformática; la cual se beneficia con la capacidad de hacer búsquedas en el espacio de problemas realmente grandes, en un tiempo razonable sin necesidad del uso de información extra. Estas son ventajas que no ofrecen los algoritmos específicos de esta área. Ya sea en el contexto industrial como en el bioinformático, las metaheurísticas han sido juzgadas o evaluadas como beneficiosas, ya que con un esfuerzo limitado se pueden alcanzar buenos resultados con gran versatilidad. Actualmente dos de las ramas con más éxito para diseñar metaheurísticas eficientes, y dar solución a estos problemas, son la hibridación y el paralelismo.