Resolución del problema militar de búsqueda de camino óptimo multiobjetivo mediante el uso de algoritmos de optimización basados en colonias de hormigas
- Juan Julián Merelo Guervós Zuzendaria
- Pedro Ángel Castillo Valdivieso Zuzendaria
Defentsa unibertsitatea: Universidad de Granada
Fecha de defensa: 2009(e)ko maiatza-(a)k 05
- Julio Ortega Lopera Presidentea
- Jorge Casillas Barranquero Idazkaria
- Óscar Cordón García Kidea
- José Ignacio Hidalgo Pérez Kidea
- Anna Isabel Esparcia Alcázar Kidea
Mota: Tesia
Laburpena
En este trabajo se presentan una serie de algoritmos desarrollados para la resolución de un problema de búsqueda de camino óptimo atendiendo a varios criterios, y dentro de un entorno que modela un campo de batalla militar (en el que puede haber enemigos) recorrido por una compañía, Estos han sido planteados como algoritmos de Optimización basada en Colonias de Hormigas para la resolución de problemas MultiObjetivo (OCHMO), es decir, estarán enfocados a la búsqueda de soluciones en problemas con distinto número de objetivos a optimizar. Los algoritmos propuestos han sido diseñados para trabajar con uno, dos o cuatro objetivos y se ha postulado un algoritmo para tratar cualquier número de objetivos, como generalización de los mismos. Todos han sido bautizados a partir de las siglas CHAC (Compañía de Hormigas ACorazadas), para relacionar los algoritmos de OCH con el entorno militar y con la unidad que se considera. Además de estos algoritmos, también han sido estudiados y adaptados a la resolución del problema una serie de métodos propuestos en la bibliografía para resolver otros problemas multiobjetivo, así como una heurística clásica (enfoque voraz o greedy) adaptada también para afrontar el mismo problema. Estos métodos han servido como base comparativa con respecto a los algoritmos originales propuestos en la tesis. Se han modelado para su resolución varios escenarios, partiendo de campos de batalla del videojuego Panzer GeneralTM, y definiendo las propiedades y restricciones necesarias para hacerlos fieles a la realidad. Dichos escenarios han sido resueltos aplicando tanto los algoritmos propuestos, como los adaptados. Previa y posteriormente a la resolución de dichos mapas, también se han hecho varios estudios, tanto de tipo estadístico, como puramente experimentales, en relación con los parámetros que utilizan los algoritmos y con las posibilidades de mejora de soluciones. Los resultados obtenidos demuestran que los algoritmos propuestos ofrecen muy buenas soluciones, mejores en la mayoría de casos que las obtenidas con los métodos rediseñados y adaptados. Lo que significa que se han definido satisfactoriamente varios métodos para solucionar problemas de este tipo en base a su número de objetivos.