Redes neuronales recurrentes para optimización combinatoria
- Galán Marín, Gloria
- José Muñoz Pérez Director/a
Universitat de defensa: Universidad de Málaga
Fecha de defensa: 08 de de maig de 2000
- Rafael Infante Macías President/a
- Gonzalo Joya Caparrós Secretari/ària
- José María Troya Linero Vocal
- Inmaculada Pérez de Guzmán Molina Vocal
- Ignacio Requena Ramos Vocal
Tipus: Tesi
Resum
Esta tesis doctoral se dedica al estudio y desarrollo de redes neuronales para la resolución de problemas de optimizacion combinatoria, un campo de gran interes en numerosas areas tales como Matematicas y Computacion, En el trabajo se analizan las principales redes existentes para optimización, proporcionando nuevos puntos de vista sobre algunas de ellas, en particular sobre las redes de Hopfield discreta y continua, y sobre las redes de Takefuji y Lee. Se realiza una primera aportación en el campo de las redes secuenciales, presentando una generalización de la red de Hopfield binaria que como novedad garantiza la convergencia hacia minimos locales para valores cualesquiera de las autoconexiones. Es destacable que en los problemas inplementados de las n reinas y de los cuatro colores los algoritmos neuronales propuestos permiten alcanzar mínimos globales, mientras que otras redes presentadas anteriormente para dichos problemas se estancan fácilmente en minimos locales, por lo que requieren técnicas heurísticas adicionales. Otra aportación destacada es la de una nueva red binaria n-paralela competitiva, que se demuestra converge siempre hacia mínimos locales o globales. La implementación de esta red competitiva en los problemas de las n reinas, bipartición de grafos y clique máximo, muestra unos excelentes resultados computacionales. De este modo, tanto enel tiempo de computación como en la calidad de las soluciones, los resultados son superiores a los de la principal red neuronal competitiva existente, la red maximum de Takefuji y Lee, que a su vez ha demostrado a través de diversas publicaciones internacionales su superioridad sobre los mejores métodos existentes para la resolución de dichos problemas. Destacar por último que las simulaciones realizadas en los problemas NP-Completos resueltos indican que hasta los tamaños implementados el tiempo utilizado en las simulaciones crece polinomialmente con el tamaño