::: acronym :::

::: IEEEkeywords MinSA, Grafos con signo, Embebido de grafos, Heurísticas, Metaheurísticas :::

Datos de la Tesis Doctoral

• Nombre: Marcos Robles Rodríguez.

• Universidad: Universidad Rey Juan Carlos.

• Departamento: Departamento de Informática y Estadística.

• Directores: Sergio Cavero Díaz y Eduardo García Pardo.

• Programa: Programa de Doctorado en Tecnologías de la Información y las Comunicaciones.

• Línea de investigación: Inteligencia Artificial.

• Fecha de inicio: 18 de octubre de 2023.

Introducción

El proyecto de Tesis Doctoral presentado en este documento pertenece a la disciplina de la optimización heurística. La optimización constituye un campo de estudio que se dedica a la búsqueda de la solución óptima para problemas modelados matemáticamente. Para describir un problema se define una función (función objetivo), que evalúa la calidad de una solución dada y un conjunto de restricciones que dicha solución debe cumplir. Las soluciones que satisfacen estas restricciones se denominan soluciones factibles.

Para abordar los problemas de optimización es posible utilizar técnicas exactas y aproximadas. Las técnicas exactas son procesos que garantizan encontrar la solución óptima, es decir, la mejor solución posible, pero suelen ser procesos que requieren mucho tiempo para obtenerla. Esto es debido a que su complejidad algorítmica suele ser muy elevada, incrementando exponencialmente el tiempo de cómputo a medida que crece el tamaño de la entrada del problema, por lo que se vuelven inviables para problemas de gran tamaño, como suele ser el caso de los problemas reales. Por otro lado, las técnicas aproximadas no garantizan obtener la solución óptima, pero generalmente tienen un tiempo de ejecución mucho menor que el de las técnicas exactas. Entre las técnicas aproximadas se incluyen las técnicas heurísticas, basadas en ideas sencillas y específicas del problema tratado [@gigerenzer2008heuristics; @michalewicz2013solve; @duarte:hal-03674503]. En [@zanakis1981heuristic] se presentan las bases para identificar en qué situaciones utilizar técnicas heurísticas para abordar un problema de optimización. Concretamente, se enumeran los siguientes casos comunes:

• No existe un algoritmo exacto.

• Existe un algoritmo exacto, pero no es viable debido a su lentitud.

• Se quiere obtener una cota.

• Es suficiente con una solución aproximada.

• Se quiere estudiar algún aspecto del problema.

Es por estas razones que las técnicas heurísticas son de gran interés para abordar problemas de optimización complejos, especialmente aquellos clasificados como pertenecientes a la familia de complejidad NP-Difícil [@garey1979computers]. Además, este tipo de técnicas son comúnmente combinadas con unas estrategias más avanzadas denotadas como metaheurísticas. El objetivo principal de las metaheurísticas es guiar a las heurísticas en el espacio de soluciones, diversificando la búsqueda para explorarlo eficientemente, pero a su vez, tratando de encontrar soluciones de calidad en tiempos de cómputo reducidos. En concreto, una de sus habilidades principales es evitar que los procedimientos heurísticos queden atrapados en los óptimos locales.

Para que a un problema se le puedan aplicar estas técnicas es necesario modelarlo matemáticamente. En este sentido, los problemas con los que se trabaja en esta Tesis Doctoral son representados por medio de grafos. Un grafo es una estructura de datos que se compone de una serie de nodos o vértices que representan los elementos de un sistema, y de aristas, que representan las diferentes conexiones o relaciones entre los elementos. Los grafos se han utilizado satisfactoriamente para representar problemas complejos con gran interés práctico en la sociedad actual como, los problemas de rutas y transporte [@wren1998heuristics; @ralphs2003capacitated], la localización de instalaciones [@shen2011reliable], la planificación de tareas [@rajendran1995heuristics; @emmons2012flow], o las redes de comunicaciones [@frei1999bandwidth].

Dentro del ámbito de los problemas de optimización que se modelan a través de grafos, existe una subfamilia conocida como problemas de embebido o etiquetado de grafos (GLP, por sus siglas en inglés, Graph Layout Problems) [@chung1988labelings; @diaz_survey_2002]. Estos problemas han sido objeto de estudio en la literatura debido a la amplia variedad de aplicaciones prácticas que presentan [@diaz_survey_2002; @fischer2013virtual; @pardo2018; @dujmovic2004linear]. El propósito principal de los GLP es optimizar una función objetivo específica durante la proyección de un grafo candidato en un grafo huésped. El grafo candidato se denota como $G_C=(V_C, E_C)$, donde $V_C$ simboliza el conjunto de vértices y $E_C$ representa el conjunto de aristas del grafo $G_C$. De manera similar, el grafo huésped se denota como $G_H=(V_H, E_H)$, donde $V_H$ y $E_H$ representan el conjunto de vértices y el conjunto de aristas del grafo $G_H$, respectivamente. Este proceso de proyección, también conocido como embebido o etiquetado, consiste formalmente en la definición de una función biyectiva que establece una correspondencia entre los vértices del conjunto $V_G$ y los vértices del conjunto $V_H$. Los GLP que suelen despertar mayor interés son aquellos en los que el grafo huésped $G_H$ posee una estructura definida. En particular, los grafos huésped más estudiados en las últimas décadas son el camino [@garcia2006variable], el ciclo [@robles2022bvns], el árbol [@becerra2019sitting] y la rejilla [@cavero2023efficient]. En la Figura 1{reference-type=“ref” reference=“fig:regular”} se proporciona una representación gráfica de cada una de estas estructuras.

{#fig:regular width=“45%”}

La definición de un GLP, por lo tanto, consiste en la definición, a su vez, de un grafo candidato, un grafo huésped, una función objetivo para evaluar las soluciones generadas, es decir, los embebidos, y un conjunto de restricciones. La formalización de cada uno de estos elementos dará como resultado un problema de optimización concreto dentro de la familia de los GLP.

De todos los GLP presentes en la literatura, esta Tesis Doctoral se centra en aquellos problemas cuyo grafo candidato es un grafo con signos. El aspecto que diferencia a estos grafos es que sus aristas están etiquetadas con los pesos +1 y –1 [@zaslavsky1982signed]. Esta representación permite establecer relaciones positivas y negativas entre los vértices.

Uno de los problemas más estudiados de este tipo es el [MinSA]{acronym-label=“MinSA” acronym-form=“singular+short”}. Este problema se define para un grafo candidato con signos, y para un grafo huésped de tipo camino. El objetivo es encontrar un embebido en el que se minimice la suma total de casos en los que para un vértice hay vértices adyacentes conectados con aristas negativas, situados más cerca que otros vértices adyacentes con aristas positivas.

En la Figura 2{reference-type=“ref” reference=“fig:minsa”} se muestra un ejemplo de embebido de un grafo con signos en un grafo camino. En este caso se tiene que el grafo candidato tiene cinco vértices (A, B, C, D y E) y cinco aristas, de las cuales dos tienen un peso de +1 ((B, C), (C, D)) y tres un peso de -1 ((A, B), (A, D), (D, E)). El embebido resultante tiene una etiqueta asignada a cada uno de los vértices del grafo candidato, teniendo, por ejemplo, el vértice A la etiqueta 1, el vértice B la etiqueta 2… Para evaluar la función objetivo del embebido hay que evaluar cada vértice de forma individual, contando el número de casos en los que un vértice tiene un adyacente con un peso negativo más cercano que otro con un peso positivo. Por ejemplo, en este embebido no se da ningún caso de este tipo, ya que los pares de vértices (B, C) y (C, D) no tienen adyacentes negativos entre ninguno de ellos, y, por lo tanto, la solución es óptima.

En esta Tesis Doctoral, en primer lugar se estudia el estado del arte del [MinSA]{acronym-label=“MinSA” acronym-form=“singular+short”}. A partir de este problema surgen otros con variaciones en el tipo grafo huésped (de tipo ciclo o tipo R-Tree). Estas variaciones dan lugar a esta Tesis Doctoral que se enfoca en estudiar estos nuevos problemas que modifican aspectos como el tipo de grafo huésped o la función objetivo. En concreto, esta Tesis Doctoral se centra en la variación del grafo huésped ciclo. Además, también se plantea estudiar nuevas funciones objetivo para el [MinSA]{acronym-label=“MinSA” acronym-form=“singular+short”} con el grafo huésped ciclo.

{#fig:minsa width=“35%”}

Investigaciones previas

El problema de [SA]{acronym-label=“SA” acronym-form=“singular+short”} fue introducido por primera vez en la literatura en el año 2011 por Kermarrec y Thraves [@kermarrec2011can]. En dicho estudio, se planteó el problema consistente en el embebido de un grafo no dirigido, con aristas etiquetadas como positivas o negativas, en un espacio R. El objetivo era que cada vértice se ubicara más cerca de todos sus vértices adyacentes con aristas positivas (denominados “amigos”) que de aquellos con aristas negativas (denominados “enemigos”). Cada uno de estos casos se considera un fallo en el embebido, y se denomina como “error”. Además, en el mismo trabajo, los autores propusieron un algoritmo para espacios R unidimensionales, equivalente a un grafo huésped de tipo camino.

En el año 2012, se demostró que es posible embeber un grafo candidato de tipo intervalo en un grafo huésped con estructura de camino, de tal manera que el error total sea cero [@cygan2012sitting]. Este resultado es particularmente relevante, ya que demostró que es posible encontrar una solución óptima para ciertos tipos de grafos candidato y permitió el desarrollo de métodos heurísticos efectivos para el [MinSA]{acronym-label=“MinSA” acronym-form=“singular+short”}.

En el año 2015, se formuló el problema de [SA]{acronym-label=“SA” acronym-form=“singular+short”} como un problema de minimización ([MinSA]{acronym-label=“MinSA” acronym-form=“singular+short”}) [@pardo2015embedding]. En este trabajo también se presentaba un algoritmo voraz y un algoritmo [GRASP]{acronym-label=“GRASP” acronym-form=“singular+short”} para abordar el [MinSA]{acronym-label=“MinSA” acronym-form=“singular+short”} en el grafo huésped camino. Se comprobó de forma práctica que el método [GRASP]{acronym-label=“GRASP” acronym-form=“singular+short”} obtenía mejores resultados que el algoritmo voraz. Sin embargo, el método voraz obtenía mejores soluciones en el caso particular de los grafos de tipo intervalo.

En el año 2018, se examinó el [SA]{acronym-label=“SA” acronym-form=“singular+short”} desde una perspectiva teórica para un grafo huésped con estructura de ciclo [@benitez2018sitting]. En este estudio, se explica que si las aristas positivas del grafo candidato forman un “Grafo de Arco Circular” (Circular-Arc Graph), existe un embebido en el grafo ciclo, para la cual el error total es cero. Se define un “Grafo de Arco Circular” como un subgrafo en el que, dado un vértice perteneciente a ese subgrafo, todos los demás vértices del subgrafo son adyacentes a este. Este trabajo es equivalente al de 2012 [@cygan2012sitting] para el grafo huésped ciclo.

En el año 2019, se propuso la estructura de R-Tree para el grafo huésped [@becerra2019sitting]. En este trabajo, los autores demostraron teóricamente que si el subgrafo compuesto por todas las aristas positivas de un grafo candidato es fuertemente cordal, entonces existe un embebido en un grafo huésped R-Tree con un error total de cero.

En el año 2020, se presentó un algoritmo heurístico para el problema de [CMinSA]{acronym-label=“CMinSA” acronym-form=“singular+short”}, la variante del [MinSA]{acronym-label=“MinSA” acronym-form=“singular+short”} en la que el grafo huésped tiene una estructura de ciclo [@pardo_basic_2020]. Este algoritmo fundamentaba su método de construcción en los cliqués del subgrafo formado por las aristas positivas del grafo candidato, utilizando la demostración de [@cygan2012sitting]. Con este enfoque, el algoritmo demostró ser altamente eficiente para grafos candidato de tipo intervalo, aunque no tanto como el algoritmo voraz propuesto en [@pardo2015embedding]. Por otro lado, el método de búsqueda de la propuesta de ese artículo fue un [BVNS]{acronym-label=“BVNS” acronym-form=“singular+short”} que utiliza una búsqueda local basada en movimientos de intercambio. Para la experimentación, los autores utilizaron tres conjuntos de instancias compuestos por grafos completos, grafos de intervalo y grafos generados aleatoriamente. El resultado de este trabajo fue un algoritmo heurístico capaz de mejorar los resultados del mejor algoritmo previamente conocido para este problema [@pardo2015embedding]. En consecuencia, este algoritmo se considera el estado del arte actual para el problema de MinSA en un grafo camino.

Finalmente, en el año 2022, se utilizó el algoritmo del estado del arte del [MinSA]{acronym-label=“MinSA” acronym-form=“singular+short”} en el [CMinSA]{acronym-label=“CMinSA” acronym-form=“singular+short”} [@robles2022bvns]. Se demostró en ese trabajo que era una propuesta efectiva, y se estableció ese método como el estado del arte del [CMinSA]{acronym-label=“CMinSA” acronym-form=“singular+short”} en cuanto a métodos heurísticos. De forma complementaria, los autores efectuaron un estudio de la correlación entre las funciones objetivo del [MinSA]{acronym-label=“MinSA” acronym-form=“singular+short”} y el [CMinSA]{acronym-label=“CMinSA” acronym-form=“singular+short”}, demostrando también que existe una relación entre ambas. Se comprobó de forma práctica que, para la misma solución, el valor de la función objetivo era mayor al evaluarse en un grafo de tipo ciclo que en un grafo camino.

En la Figura 3{reference-type=“ref” reference=“fig:sota”} se muestran estos trabajos de forma gráfica para cada grafo huésped. Como se puede ver, la variante del grafo huésped camino está muy trabajada, mientras que para los grafos huésped de tipo ciclo y R-Tree no existen casi trabajos. Por otro lado, el grafo huésped rejilla ni siquiera se ha propuesto aún.

{#fig:sota width=“45%”}

Hipótesis

El desarrollo de la Tesis Doctoral se basa en el método científico. El primer paso es identificar el problema, se comprueba su interés y los trabajos relacionados, obteniendo elementos como instancias, códigos y ficheros ejecutables. A continuación, se debe plantear una hipótesis de partida, que dará como resultado el desarrollo de uno o varios algoritmos. Estos algoritmos se comparan experimentalmente con los ya existentes en la literatura. Si estos dan resultados positivos, entonces se valida la hipótesis de partida.

En esta Tesis Doctoral se trabaja con el problema de [MinSA]{acronym-label=“MinSA” acronym-form=“singular+short”} y sus variantes. Los trabajos existentes en la literatura demuestran que el [MinSA]{acronym-label=“MinSA” acronym-form=“singular+short”} es un problema con un interés científico. Además, también poseen un interés científico sus variantes, para las que no existen aún casi propuestas algorítmicas. Para suplir esta falta de propuestas se plantea la búsqueda de algoritmos efectivos para esta familia de problemas. Debido a los trabajos observados en la literatura, se ha comprobado que el uso de algoritmos aproximados es esencial para estos problemas, consecuentemente, las propuestas se centraran en los algoritmos heurísticos y metaheurísticos. En conclusión, la hipótesis de esta Tesis Doctoral se define como:

“Los algoritmos heurísticos y metaheurísticos son una aproximación efectiva para el problema de [MinSA]{acronym-label=“MinSA” acronym-form=“singular+short”} y sus derivados.”

Objetivos

Identificada las hipótesis de esta tesis es necesario definir una serie de objetivos con el fin de contrastarla. El objetivo de esta Tesis Doctoral se puede enunciar como:

“Diseñar e implementar algoritmos heurísticos, utilizados junto con técnicas metaheurísticas, para abordar problemas de optimización derivados del MinSA.”

Este objetivo se puede descomponer en una serie de objetivos específicos. En primer lugar, se tienen unos objetivos iniciales (Obj.I) con el fin de arrancar el desarrollo de la investigación:

• Obj.I.1: Llevar a cabo un estudio del estado del arte del problema original.

• Obj.I.2: Estudiar de manera exhaustiva las características estructurales de cada variante (camino, ciclo y R-Tree).

• Obj.I.3: Modelar las distintas variantes para poder abordarlo computacionalmente.

• Obj.I.4: Implementar los algoritmos propuestos para las distintas variantes.

Una vez cumplidos los objetivos iniciales se tendrá un contexto que permite iniciar el estudio nuevas propuestas. Una vez se completen los objetivos iniciales y se seleccione una variante de [MinSA]{acronym-label=“MinSA” acronym-form=“singular+short”}, se tienen unos objetivos específicos (Obj.E), que se enuncian como:

• Obj.E.0: Elegir una variante del [MinSA]{acronym-label=“MinSA” acronym-form=“singular+short”}, que modifica elementos como la estructura del grafo huésped o la función objetivo.

• Obj.E.1: Llevar a cabo un estudio del estado del arte de la variante si existe.

• Obj.E.2: Estudiar de manera exhaustiva las características estructurales de la variante.

• Obj.E.3: Modelar la variante para abordarla computacionalmente.

• Obj.E.4: Probar la eficacia de algoritmos ya empleados anteriormente en otras variantes del [MinSA]{acronym-label=“MinSA” acronym-form=“singular+short”}.

• Obj.E.5: Proponer, diseñar e implementar algoritmos heurísticos para esa variante.

• Obj.E.6: Escoger, parametrizar e implementar la técnica metaheurística más adecuada, que permita mejorar las soluciones encontradas por métodos previos.

• Obj.E.7: Comparar los resultados obtenidos por los algoritmos propuestos, con los algoritmos previos del estado del arte, sobre conjuntos de datos comunes.

• Obj.E.8: Elaborar un documento que recoja el trabajo realizado, conclusiones y posibles mejoras.

• Obj.E.9: Guardar la nueva variante y su propuesta algorítmica con el fin de formar parte de las comparaciones en investigaciones futuras.

Todos los objetivos anteriores tienen el fin de contrastar la hipótesis inicial. Los resultados y el conocimiento que resulte de esta investigación se publicarán en revistas de impacto y en congresos internacionales y nacionales del área. Por lo tanto, el aporte final estará compuesto por los resultados obtenidos, a modo de documentos, y por el código e instancias utilizadas.

Metodología

En esta Tesis Doctoral se sigue un proceso iterativo e incremental, basado en el método científico. En concreto, cada iteración se centra en el estudio de un problema específico. Se considera un proceso incremental porque se espera que los conocimientos de estudiar unas variantes se puedan aplicar posteriormente a otras. Dentro de cada iteración se aplicará el método científico como tal con el fin de crear nuevo conocimiento. Basándose en la observación y en los resultados prácticos, se formularán hipótesis específicas para cada variante del [MinSA]{acronym-label=“MinSA” acronym-form=“singular+short”}, utilizando, por tanto, los resultados como guía para contrastar y formular futuras hipótesis.

Este proceso seguirá el orden indicado en los objetivos, especificando la variante seleccionada y cumpliendo los objetivos indicados. Este proceso se representa en la Figura 4{reference-type=“ref” reference=“fig:iter”}. El Obj.E.5 será el punto en el que se propondrá una hipótesis sobre qué algoritmo puede ser efectivo para tratar el problema. En el Obj.E.7 se contrastará la hipótesis, si esta es cierta se pasará al Obj.E.8, si no, el algoritmo no será efectivo, y, por lo tanto, se tendrá que volver al Obj.E.5, formulando una nueva hipótesis, esta vez con más información que antes. Este proceso se repetirá hasta contar con la suficiente información para formular una hipótesis que dé como resultado un algoritmo efectivo, y, por lo tanto, una contribución científica significativa.

{#fig:iter width=“45%”}

Relevancia

Esta Tesis Doctoral contribuye significativamente al avance del conocimiento en diversas áreas. En primer lugar, en esta Tesis Doctoral se van a estudiar las variantes del MinSA, que aún se encuentran en sus primeras etapas. Esto presenta una gran oportunidad para llevar a cabo investigaciones innovadoras y de alto impacto. Como resultado, se obtendrán soluciones de mayor calidad para estos problemas, se desarrollarán métodos eficientes y se extraerán propiedades de los problemas que podrán ser útiles en futuras investigaciones.

En segundo lugar, en el ámbito de la optimización, y específicamente en lo que respecta a los métodos heurísticos y metaheurísticos, se propondrán y compararán métodos innovadores, que podrían ser de interés en otros campos también.

En tercer lugar, el desarrollo de esta Tesis Doctoral es interesante de cara a aplicaciones reales. Los problemas asociados al [MinSA]{acronym-label=“MinSA” acronym-form=“singular+short”} se han formulado para casos prácticos reales, como la distribución de personas e instalaciones, situaciones donde se desea modelar relaciones positivas y negativas. Por lo tanto, estos problemas tienen relevancia práctica en áreas como la planificación urbana o la organización de eventos.

En el tiempo que se lleva trabajando en esta Tesis Doctoral el desarrollo de la propuesta heurística ha demostrado ser una línea de investigación de gran relevancia, con un potencial considerable para contribuir al campo de estudio. La aceptación de los resultados parciales en foros académicos de prestigio confirma la importancia de este trabajo y su impacto en la comunidad científica. Concretamente, los resultados parciales han sido difundidos por medio de la publicación de un artículo en una revista indexada en el índice SJR [@robles2022bvns], se ha presentado una publicación en un congreso internacional [@RoblesCP22] y en un congreso nacional [@roblesSEIO].

Adicionalmente, al momento de redactar este documento, se está elaborando un artículo científico, el cual presenta un enfoque innovador en el campo de los GLP. Este artículo aborda el problema del [CMinSA]{acronym-label=“CMinSA” acronym-form=“singular+short”} y logra resultados mejores que los del método anterior. El objetivo es publicar este artículo en una revista indexada en el índice JCR.