Design and application of novel harmony search multi-objective algorithms to practical problems

Resumen

La mayoría de los problemas de optimización en el mundo real están definidos por varias métricas objetivo en conflicto que se deben cumplir simultáneamente. En la formulación de estos problemas, comúnmente etiquetados como multi-objetivo, la noción de óptimo debe ser redefinida de tal manera que, en lugar de buscar una solución única, se persigue un conjunto de ellas que balancee o compense diferentemente las métricas del problema, entre las que se selecciona la solución según las especificaciones del escenario en cuestión. Pese al considerable aumento de nuevos algoritmos meta-heurísticos para la resolución de problemas de optimización mono-objetivo surgidos en las últimas décadas, dichas técnicas no han sido extrapoladas a formulaciones multi-objetivo al mismo ritmo, ya que la comunidad investigadora ha dedicado menos esfuerzos hacia esta vertiente. En consecuencia, de cara a cubrir los exigentes requisitos computacionales de los problemas de optimización del mundo real se consideran cruciales tanto la adaptación de algoritmos de optimización mono-objetivo existentes para hacer frente simultáneamente a varios objetivos, como el desarrollo de nuevas técnicas específicamente orientadas a formulaciones multi-objetivo. En este sentido, ha sido ampliamente demostrado en la literatura relacionada que el algoritmo llamado búsqueda por armonía (del anglosajón ``Harmony Search'', HS) obtiene excelentes resultados en el campo de la optimización combinatoria. Sus propiedades innovadoras y las características de los operadores probabilísticos que lo controlan hacen que HS supere otros algoritmos meta-heurísticos de la literatura, motivando así su utilización en campos de aplicación pertenecientes a diversas áreas del conocimiento como la construcción, las telecomunicaciones y la economía, entre otras. Esta Tesis doctoral tiene como objetivo la adaptación de la búsqueda por armonía a paradigmas de optimización multi-objetivo, así como la aplicabilidad del algoritmo multi-objetivo resultante (acuñado como NSHS-II, del anglosajón ``Non Dominated Sorting HS'') a diferentes problemas multi-objetivo de elevada complejidad. En concreto, NSHS-II se aplica a cuatro escenarios: 1) localización en redes de sensores inalámbricos; 2) reconfiguración de redes de transporte urbano; 3) diseño de redes de acceso WiFi; y 4) planificación de centros de salud. A tal efecto, la definición de la mejor estrategia de codificación para cada problema resulta de suma importancia para representar de manera unívoca cada solución encontrada. Es por ello que esta Tesis doctoral también investiga la llamada estrategia de codificación por agrupaciones con el propósito de evitar representaciones redundantes del espacio solución y reducir así la complejidad computacional del proceso de búsqueda. El desempeño del método propuesto es validado y contrastado con el rendimiento de técnicas presentes en el estado del arte por medio de estudios experimentales. De los resultados obtenidos se concluye que el algoritmo NSHS-II es un método robusto capaz de superar otras técnicas multi-objetivo al resolver problemas emergentes en diferentes disciplinas del conocimiento.