PDF de programación - Algoritmos de búsqueda con retroceso para problemas multicriterio

Algoritmos de búsqueda con retroceso

para problemas multicriterio

TESIS DOCTORAL

Javier Coego Botana
Universidad de Málaga

23 de Octubre de 2015

Documento maquetado con TEXiS v.1.0.

Este documento está preparado para ser imprimido a doble cara.

Algoritmos de búsqueda con retroceso

para problemas multicriterio

Memoria que presenta el doctorando

Javier Coego Botana

para optar al grado académico de Doctor Ingeniero en Informática

Dirigida por el Doctor

Lorenzo Mandow Andaluz

Tribunal de la tesis

Rafael Morales Bueno - Universidad de Málaga

María Victoria Belmonte Martínez - Universidad de Málaga

Camino Rodríguez Vela - Universidad de Oviedo

Eva Onaindía de la Rivaherrera - Universidad Politécnica de Valencia

Raquel Fuentetaja Pizán - Universidad Carlos III de Madrid

Universidad de Málaga

23 de Octubre de 2015

Copyright c(cid:13) Javier Coego Botana

E-MAIL: [email protected]

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivs

License: http://creativecommons.org/licenses/by-nc-nd/3.0/

Este trabajo está financiado por:

Consejería de Economía, Innovación, Ciencia y Empresa.
Junta de Andalucía (España)
Referencia: P07-TIC-03018

El Dr. D. Lawrence Mandow Andaluz, Profesor Titular de Universidad, del Área
de Ciencias de la Computación e Inteligencia Artificial de la Escuela Técnica Superior
de Ingeniería Informática de la Universidad de Málaga ,

Certifica que,

D. Javier Coego Botana, Licenciado en Informática, ha realizado en el Departa-
mento de Lenguajes y Ciencias de la Computación de la Universidad de Málaga , bajo
su dirección, el trabajo de investigación correspondiente a su Tesis Doctoral titulada:

Algoritmos de búsqueda con retroceso para problemas multicriterio

Revisado el presente trabajo, estima que puede ser presentado al tribunal que ha
de juzgarlo, y autoriza la presentación de esta Tesis Doctoral en la Universidad de
Málaga .

Fdo.: Dr. Lawrence Mandow Andaluz

Málaga, 23 de Octubre de 2015

A Nieves y a nuestros hijos, Dani y Javi.

Agradecimientos

Finalmente, muchos años después de zarpar, este barco llega ya a puerto. Unas
veces ha sido un crucero, otras el barco del holandés errante y en ocasiones un viaje
en galeras. Pero siempre he tenido gente a mi lado que se merece un reconocimiento
por haber remado altruistamente conmigo, compartiendo esta singladura.

En primer lugar y por encima de todo, gracias a Lawrence Mandow, capitán, brú-
jula y director, por haberme regalado esta tesis, pues es más suya que mía. Gracias
por haber recogido a este náufrago del proceloso mar del Doctorado; por ser maestro y
compañero antes que director; por su luz cuando recorríamos caminos de investigación
un tanto oscuros; por ser el timonel que ha corregido la derrota del barco cuando iba
camino de ser pecio; por haber tirado del carro cuando yo me empeñaba en procrasti-
nar; por sus buenos consejos; por su buen humor y paciencia. Y por un millón de cosas
más, GRACIAS.

Gracias a José Luis Pérez de la Cruz, teórico, analítico, pragmático, matemático,
catedrático y británico. Ha ejercido de padrino de esta criatura, velando por su buen
rumbo y aportando esa flema y capacidad de resolución que tantas veces me han dejado
con la boca abierta.

Gracias a mis contemporáneos de tesis, los doctores Enrique Machuca y Francisco
Javier Pulido, por su ayuda desinteresada siempre que me ha hecho falta, compartiendo
información y trucos, y regalándome la luna cuando se la he pedido. Gracias y buena
suerte en vuestros viajes.

Gracias a mis compañeros de trabajo de estos últimos años en la Junta de Andalucía
y en la UMA, que han sabido tolerar, y muchas veces fomentar, mis cada vez más
frecuentes distracciones doctorales, sobre todo en este tramo final.

Gracias a mis grandes amigos en las tres grandes etapas de mi vida: Coruña, Madrid
y Málaga. En especial a Darío, Justo, Mari Cruz, Álvaro, Chelo e Isa, todos ellos
condiciones necesarias y suficientes para que yo haya llegado donde estoy ahora. En
mayor o menor medida habéis sido testigos de esta deriva y el apoyo y ánimo que me
habéis brindado han hecho más llevadero este largo camino.

Gracias a mi familia de Málaga, por haber sido mi Norte en este Sur. En especial
a José y Nieves, por haberme acogido y tratado todos estos años como si fuera un hijo
más.

Gracias infinitas a mis padres, por tantos esfuerzos durante tanto tiempo, por darlo

ix

x

Agradecimientos

todo, por privarse ellos para que tuviera yo y por haberme inculcado valores a los cuales
espero haber sido fiel. Y como no, a mi hermano Jose, mi Gran Hermano, por ser el
espejo de honestidad, trabajo y humanidad en el que me quiero ver reflejado.

Gracias a Nieves, la mujer del millón de sonrisas, Doctora en Paciencia y Cate-
drática en Psicología de Tercer Ciclo: por haber estado siempre a mi lado, no sólo en
este camino académico, sino en otro aún más largo y difícil que es la vida, soportán-
dome, quitando piedras del camino y echándose a la espalda cualquier distracción. Mil
párrafos no le harían justicia.

Gracias a mis hijos, Dani y Javi, por aguantar tantos “ahora no puedo“ o “estoy
muy liado“, e incluso gruñidos, con su inagotable alegría, su resignación y sus muchos
besos. Aunque vuestras respectivas felicidades me hayan salido como funciones a ma-
ximizar, tened por seguro que resolveré este problema biobjetivo. En esta vida os ha
tocado un padre NP-hard de aguantar, pero prometo compensaros con tiempo de juego
exponencial en plazo polinómico.

Resumen

La búsqueda en grafos, con multitud de aplicaciones en el mundo real, ha propiciado
el diseño de una gran cantidad de algoritmos centrados en el procesamiento de un
único objetivo, magnitud representativa del coste. Sin embargo, un tratamiento realista
de estos problemas requiere en muchas ocasiones contemplar diferentes objetivos de
modo simultáneo. Además, es habitual que estos objetivos sean antagónicos, de tal
modo que la optimización de uno de ellos se traduzca en el empeoramiento de uno o
varios de los objetivos restantes. Esto hace que el coste óptimo no sea único, sino que
generalmente existe un conjunto de soluciones óptimas cuyas componentes de coste
están compensadas entre sí.

Esta naturaleza multiobjetivo de los problemas provoca que el rendimiento de los
algoritmos empeore de modo considerable, ya que al procesamiento habitual de los
nodos generados durante el proceso de búsqueda hay que añadir el tratamiento de
vectores de coste (de dimensión igual al número de objetivos considerado) y el manejo
de un conjunto de soluciones óptimas (cuyo tamaño en el peor de los casos será ex-
ponencial), siendo este tipo de operaciones muy costosas desde el punto de vista de
tiempo y memoria.

De las dos principales clases de algoritmos exactos multiobjetivo, la correspondien-
te a un enfoque best-first ha sido ampliamente estudiada, dando lugar a una gran
cantidad de algoritmos que persiguen reducir la complejidad espacial y temporal del
proceso de búsqueda. Asimismo existen numerosas y detalladas comparativas de ren-
dimiento entre estos algoritmos. Sin embargo la clase de algoritmos depth-first, aún
siendo de gran utilidad en la resolución de problemas con grafo de búsqueda en forma
de árbol, presentaba un reducido número de propuestas, careciendo además de análisis
comparativos entre las mismas.

Esta tesis pretende cubrir dicho hueco, realizando un estudio sistemático de al-
goritmos exactos multiobjetivo de tipo depth-first. Para ello, por un lado se realiza
una caracterización detallada de dichos algoritmos, contribuyendo con nuevos diseños
multiobjetivo, variantes de algoritmos para un objetivo que aplican los conceptos de
Frontera de Pareto y Punto Ideal a la cota de expansión empleada en la búsqueda

xi

xii

Resumen

depth-first. De todos estos nuevos algoritmos se aporta su correspondiente análisis for-
mal. Asimismo se realizan adaptaciones de algoritmos multiobjetivo ya existentes, de
tal modo que sean aplicables a árboles infinitos, el principal tipo de problemas usado
en el análisis de rendimiento realizado en este trabajo.

Por otro lado, en esta tesis se realiza un análisis empírico detallado de los algorit-
mos mencionados. Para ello en primer lugar se determinan los principales parámetros
de rendimiento a tener en cuenta en función de la naturaleza multiobjetivo de los pro-
blemas considerados. Concretamente el tiempo de ejecución, en combinación con el
tamaño de la cota de expansión, se perfilan como los factores clave de rendimiento.
Los resultados obtenidos en las pruebas realizadas presentan a la variante multiob-
jetivo del algoritmo Branch & Bound como la opción más eficiente para árboles de
búsqueda tanto finitos como infinitos, precisando de una cota adicional en este último
caso.

Índice

Agradecimientos

Resumen

I Alcance y fundamentos

1. Introducción

1.1. Motivación y relevancia . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2. Alcance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3. Objetivos de la investigación . . . . . . . . . . . . . . . . . . . . . . . .
1.4. Contribuciones de la tesis
. . . . . . . . . . . . . . . . . . . . . . . . . .
1.5. Publicaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.6. Estructura de la tesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

IX

XI

1

3
3
5
6
7
8
9

2. Búsqueda con un objetivo

11
2.1. Formalización de problemas . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2. Algoritmo general de búsqueda para un único objetivo . . . . . . . . . . 15
2.3. Propiedades de los algoritmos de búsqueda . . . . . . . . . . . . . . . . 16
2.4. Clasificación de algoritmos de búsqueda para un único objetivo . . . . . 17
2.5. La heurística aplicada a la búsqueda . . . . . . . . . . . . . . . . . . . . 18
2.6. Algoritmos de búsqueda heurística best-first con un único objetivo . . . 20
2.7. Algoritmos de búsqueda heurística depth-first con un único objetivo . . 21
2.7.1.