Nuevos criterios de parada en algoritmos de optimización

Abstract

Como es de sobra conocido, las metodologías asociadas a los conjuntos difusos se han apoyado prácticamente siempre en las que previamente existían (clásicas), siendo poco frecuente el que los modelos convencionales se traten de resolver a partir de métodos originales del campo difuso. Sin embargo esto no se ha dado con los Sistemas Basados en Reglas, que si han aportado una metodología propia proveniente de los conjuntos y los sistemas difusos. Dentro del campo de la Inteligencia Artificial, y también en otros campos, una de las áreas más provechosas, en diferentes sentidos, es la de los modelos de programación matemática, y dentro de estos, uno de los problemas más relevantes, tanto por sus aplicaciones como por ser un auténtico banco de pruebas teórico, son los problemas de programación lineal. Desde este doble punto de vista, el ámbito en el que se desarrolla este trabajo, que lleva por título Nuevos Criterios de Parada para Algoritmos de Optimización, es el del interfaz entre los Sistemas Basados en Reglas y los Algoritmos de Optimización, concentrado en los criterios de parada de estos algoritmos. Clásicamente los criterios de parada fijan las condiciones de finalización del procedimiento iterativo de un algoritmo, estableciéndose dichos criterios a partir de las características teóricas del problema, del tipo de solución que se busca y del tipo del algoritmo que se utilice, que en definitiva determina un conjunto de referencia, y se detiene cuando se verifica el criterio de parada. La flexibilización de los algoritmos exactos con la introducción de criterios de parada basados en reglas difusas, supone considerar que el conjunto de referencia es un conjunto difuso, y los criterios de parada difusa se fijan en función del grado de pertenencia de los elementos. Estos criterios de parada difusos se aplican en esta Tesis a diferentes algoritmos de problemas clásicos, para lo que el trabajo se desarrolla del siguiente modo. En el primer capítulo se hace un repaso de problemas, métodos y técnicas propios del campo de la Programación Matemática Difusa. En el segundo se introducen los criterios de parada que se van a emplear en lo sucesivo en este contexto, y se aplican al caso lineal, concretando en los algoritmos de punto interior y de Karmarkar. En el tercer capítulo, se desarrollan y aplican criterios de parada basados en reglas difusas a los problemas de la mochila y del viajante de comercio. La memoria termina con la presentación de conclusiones, la exposición de líneas de investigación a desarrollar en el futuro, y la recopilación de las referencias bibliográficas más importantes, empleadas para su confección