Análisis experimental de heurísticas para el problema del viajante de comercio

Grado en Matemáticas TRABAJO FIN DE GRADO Análisis Experimental de heurísticas para el Problema del Viajante de Comercio José María Verde López Sevilla, junio de 2018 Dedicado a mi familia y amigos. Agradecimientos Para empezar quiero mostrar mi agradecimiento a quien más me ha ayudado en este camino (que no ciclo, porque no acabo donde empecé), mi tutor Álvaro. Al comienzo del curso pensaba que mi tutor del Trabajo de Fin de Grado sería un profesor al que consultar ocasionalmente alguna duda. Me ha quedado claro que nada más lejos de la realidad, pues él estaba siempre al pie del cañón dispuesto a ayudarme con cualquier problema que tuviera (además de haber demostrado una paciencia innita con mi ordenador). Profesionales como él hacen que esta universidad crezca día a día. Quiero agradecer también a mis padres y a mi hermano todo su apoyo en el día a día y su interés por conocer un poco esta ciencia que es uno de los pilares de mi vida, a pesar de que no siempre sea comprensible para ellos. Igualmente debo mencionar también a mis amigos, quienes están ahí siempre y hacen que los momentos más difíciles queden en simples baches. Por último he de agradecer a todos mis profesores y, en general, a todo aquel que me ha enseñado algo en la vida, porque gracias a ellos he llegado hasta aquí. III IV Resumen El Problema del Viajante de Comercio es un problema de optimización de tipo NP - duro cuyo objetivo es, dado un conjunto de puntos y la distancia entre cada par de ellos, encontrar el camino más corto que pase por todos ellos y empiece y acabe en el mismo punto. Este problema aparentemente tan sencillo esconde una gran complejidad a la hora de afrontarlo, pues a medida que va aumentando el número de puntos nos damos cuenta de que resolverlo por fuerza bruta es en vano. Debido a esto y a la importancia de sus aplicaciones se han realizado numerosos estudios acerca del problema, centrados normalmente en el diseño de heurísticas con el n de reducir el tiempo de cálculo de soluciones. En este Trabajo de Fin de Grado se ha llevado a cabo la implementación en el lenguaje de programación Haskell de varias de esas heurísticas y de un algoritmo de fuerza bruta con el objetivo de hacer al nal de la presente memoria un análisis experimental comparativo de la eciencia de cada uno de estos algoritmos. V VI RESUMEN Abstract The Travelling Salesman Problem is an NP -hard optimization problem whose aim is to nd the shortest way through all of them that starts and ends at the same point given a set of points and the distance between each of them. This apparently naive problem hides a huge complexity when being faced since one can easily realize that solving it by a brute-force algorithm does not help once the number of points starts rising. Due to this and to the importance of its applications, numerous studies about the problem have been carried out, usually centred on the design of heuristics, whose aim is to reduce the computing time of solutions. We have carried out an implementation of some of those heuristics during this Final Degree Project using the programming language Haskell , as well as the implementation of a brute-force algorithm in order to check the hardness of the problem. The aim of all this is to experimentally make a comparative analysis of the eciency of each of these algorithms. VII XIV ÍNDICE DE CUADROS Capítulo 1 Introducción El Problema del Viajante de Comercio (en inglés Travelling Salesman Problem , TSP ) es un problema NP -duro que ha sido ampliamente estudiado por ramas de las matemáticas tales como la Investigación Operativa y las Ciencias de la Computación. Informalmente, el problema consiste en, dada una lista de ciudades y las distancias entre cada par de ellas, encontrar la ruta más corta posible que visita cada ciudad exactamente una vez y al nalizar regresa a la ciudad origen. 1.1. Evolución del TSP a lo largo de la historia El origen del nombre Problema del Viajante de Comercio es un misterio. Aparentemente no hay ningún documento ocial que esclarezca el nombre del autor y no tenemos verdaderos indicios de cuándo se empezó a usar. Uno de los investigadores más inuyentes y prolícos en los primeros avances del TSP fue Merrill Flood, de la Universidad de Princeton y de la RAND Corporation ( Research and Development Corporation ), el cual comentó en una entrevista: Mientras trataba de resolver un problema de rutas de autobuses escolares para el Estado de West Virginia me topé con el Problema de los 48 Estados ( 48 States Problem ) de Hassler Whitney, el cual fue el primero al que se le adjudicó el nombre de Problema del Viajante de Comercio. Al nal, el nombre ha calado bastante hondo y el problema ha resultado ser de gran importancia. A excepción de pequeñas variaciones en su pronunciación y en la forma de escribirlo, el nombre de TSP se había expandido completamente por la comunidad cientíca en la década de 1950. 1 2 CAPÍTULO 1. INTRODUCCIÓN El Manual de 1832 para viajantes de comercio Los viajantes de comercio estaban muy interesados en el diseño de rutas comerciales que atravesaran los principales puntos de venta. Un importante aporte en este contexto es el manual alemán de 1832 Der Handlungsreisende  wie er sein soll und was er zu tun hat, um Aufträge zu erhalten und eines glücklichen Erfolgs in seinen Geschäften gewiÿ zu sein  von einem alten Commis-Voyageur , que llegó a manos de la comunidad investigadora del TSP en 1983. El libro incluye cinco rutas a través de regiones de Alemania y Suiza, cuatro de las cuales vuelven al punto de partida. Pero este no es el único ejemplo de la presencia del TSP en esa época, podemos encontrar también libros como Commercial Traveller's Guide Book (L.P. Brockett, 1880) e incluso un juego de mesa de 1890 llamado Commercial Traveller que consistía en diseñar rutas a través de una red de ferrocarriles. Llegada del TSP a la comunidad matemática La primera aparición del TSP en la literatura matemática corresponde a Karl Menger, quien describió una variante del problema en un coloquio en Viena en 1930. A partir de ese momento empezamos a ver numerosos ejemplos de estudios sobre rutas óptimas en diversos ámbitos, como por ejemplo conexiones entre campos de cultivo en India (Eli S. Marks, 1940), autobuses escolares en EE. UU. (Merrill Flood, 1937) o rutas de vigilancia policiales (Gerald Thompson, principios de los años 60). Estos son ejemplos de estudios sobre instancias concretas. No obstante, posteriormente fueron desarrollándose los distintos algoritmos que se utilizan hoy en día para la resolución computacional del problema, así como teoremas acerca del TSP que han ido ayudando a renar dichos algoritmos. 1.2. Formalización del TSP El problema TSP puede formalizarse matemáticamente como un problema de grafos. Problema del Viajante de Comercio. Sea V={v1, . . . , vn} un conjunto de n puntos en un espacio X dotado de una distancia d y sea pi,j =d(vi, vj) la distancia entre los puntos vi y vj . Sea G= (V, A) el grafo completo ponderado sobre V , con pi,j el peso de la arista ai,j . El TSP para G consiste en encontrar el ciclo hamiltoniano de mínimo coste, es decir, una secuencia de vértices {vπ(1), . . . , vπ(n), vπ(1)} (donde π es una permutación de los subíndices 1 a n ) que minimiza la suma Pn−1 i=1 pπ(i),π(i+1) +pπ(n),π(1) . La complejidad de este problema reside en que la cantidad de ciclos posibles para n ciudades es de n! , es decir, crece de forma más que exponencial a medida que aumenta la 1.3. APLICACIONES 3 cantidad de puntos. Esto implica que resolverlo por un algoritmo de fuerza bruta (evaluando todos los posibles trayectos) es inviable. Por ello, el estudio de formas alternativas de resolución se basa en gran medida en el diseño de heurísticas que proporcionen un cierto equilibrio entre el tiempo de ejecución y la calidad de la solución obtenida. Antes de continuar, cabe mencionar la existencia de dos principales versiones del TSP , dependiendo de si el grafo es no dirigido (Problema del Viajante de Comercio simétrico, STSP ) o es dirigido (Problema del Viajante de Comercio asimétrico, ATSP ). En este trabajo nos centraremos únicamente en el estudio del primero, por lo que de ahora en adelante todos los TSP s que tratemos serán simétricos. 1.3. Aplicaciones Es fácil darse cuenta (y de ahí el interés que suscita) de que los vértices del grafo de una instancia del TSP pueden interpretarse como cualquier tipo de objeto que encaje debidamente en el planteamiento, por lo que la cantidad de problemas que pueden plantearse como un TSP para facilitar su resolución es muy grande. Algunos ejemplos de aplicaciones son: Diseño de rutas: se trata de la aplicación más inmediata que se nos puede ocurrir al pensar en el problema, pues es la más presente en la vida diaria. Ejemplos de estas rutas pueden ser desde repartos de correos o recogidas de residuos hasta la ruta seguida por un autobús escolar para recoger a todos sus pasajeros. Orientación de telescopios: en este caso el recorrido por los puntos no se hace físicamente, sino que el problema consiste en diseñar el recorrido de un telescopio que debe inspeccionar distintos puntos del espacio. La distancia total de este problema es el tiempo que tomaría observar los puntos en ese orden concreto. Cristalografía de Rayos X: el TSP aparece en este contexto al tratar de minimizar el tiempo empleado en cambiar un cristal por otro y un equipo de rayos X por el siguiente (debido a que cada cristal requiere de un equipo distinto). Secuenciación del genoma: al realizar estudios sobre secuenciación genómica en el ADN se obtienen distintos fragmentos (series de nucleótidos) que han de ser ensamblados entre sí como si de un puzzle se tratara, lo que implica la resolución de instancias del TSP . Producción de chips: cada chip cuenta con una serie de puntos cuyo circuito integrado debe conectar entre sí, de manera que la calidad del chip depende en gran medida de la distancia total del circuito. Aunque pueda parecer que las distancias dentro del chip son muy cortas, la inmensa cantidad de veces que debe recorrerse el 4 CAPÍTULO 1. INTRODUCCIÓN circuito hace que sea de vital importancia optimizar el diseño del chip lo máximo posible. Perforado de circuitos impresos: para montar distintas capas de los chips mencionados en el apartado anterior se necesitan unas placas especiales en las que se realizan multitud de agujeros para ensamblar los chips. Esto lleva a un problema de tipo TSP a la hora de automatizar el orden de realización de dichos agujeros en la placa. 1.4. Variantes del TSP Existen multitud de problemas de grafos similares al TSP que pueden ser fácilmente traducibles a un TSP propiamente dicho: MaxTSP : este problema consiste en encontrar el ciclo hamiltoniano de máxima distancia. Podemos convertirlo en un TSP cambiando el signo de los pesos de las aristas (y añadiendo una constante grande a cada uno en caso de que la forma de resolverlo pida explícitamente que estos sean positivos). TSP con visitas múltiples: en esta variante se debe visitar cada vértice al menos (en lugar de exactamente) una vez. BottleneckTSP : este problema consiste en encontrar un ciclo hamiltoniano que minimice el valor de la arista con mayor peso del ciclo. Puede ser reinterpretado como un TSP con aristas con un peso exponencialmente grande. ClusterTSP : en este caso los puntos se agrupan en conjuntos disjuntos y se añade la restricción de que los puntos de un mismo conjunto deben ser visitados de forma consecutiva. La reinterpretación en forma de TSP se hace aumentando considerablemente el peso de aristas entre puntos de distintos conjuntos. Problema de los m -Viajeros de Comercio: dado un vértice v de G= (V, A) se trata de encontrar una partición X1, . . . , Xm del conjunto V\{v} que minimice la suma de las distancias de las soluciones del TSP para cada Xi∪ {v} , siendo siempre v la ciudad de partida y de llegada. Problema del Cartero Chino: problema análogo al TSP , pero cuyo objetivo es buscar el ciclo euleriano de mínimo coste dentro del grafo. Capítulo 2 Algoritmos para la resolución del TSP Vamos a proceder ahora a describir el funcionamiento de cada uno de los algoritmos implementados durante la realización de este Trabajo de Fin de Grado, así como mostrar una parte del código utilizado para ello y los resultados de eciencia obtenidos para cada algoritmo, con el n de realizar un estudio comparativo de todos ellos. 2.1. Algoritmo de Fuerza Bruta Los algoritmos de fuerza bruta son una primera aproximación trivial al proceso de resolución computacional de un problema. Destacan por su simpleza, ya que consisten en generar todas las soluciones candidatas para luego evaluar cada una de ellas, comprobando si se ajustan o no a los requisitos que debe cumplir una solución correcta del problema. El inconveniente que tienen es el enorme coste computacional que conllevan, pues en muchos casos la cantidad de posibles soluciones a generar crece de forma exponencial o factorial al aumentar el tamaño del problema (en el caso del TSP , como ya hemos mencionado anteriormente, el número de soluciones candidatas es del orden O(n!) ). 2.1.1. Planteamiento Denición 1. Dado un conjunto V={v1, . . . , vn} , denimos la familia de conjuntos VSn={vπ(1), . . . , vπ(n)} | π∈Sn , donde Sn es el conjunto de todas las permutaciones de {1, . . . , n} . Dada una instancia G= (V, A) del TSP , el algoritmo de fuerza bruta consiste en generar el conjunto VSn de todas las posibles permutaciones de V , para después evaluar la distancia total de cada permutación. La distancia asociada a cada permutación π será la longitud total de la ruta que recorre los puntos en el orden indicado y volviendo nalmente al punto inicial, es decir, 5 6 CAPÍTULO 2. ALGORITMOS PARA LA RESOLUCIÓN DEL TSP la suma Pn−1 i=1 d(vπ(i), vπ(i+1)) + d(vπ(n), vπ(1)) (siendo d una distancia dada). La solución nal del problema mediante este algoritmo será la permutación que minimice la suma anterior. 2.1.2. Implementación Se ha implementado el algoritmo de fuerza bruta de dos maneras ligeramente diferentes. La primera de ellas utiliza la función permutations , ya denida en el preludio de Haskell , para generar todas las posibles permutaciones de las ciudades. Las instancias del TSP consideradas asumen ciudades numeradas de 1 a n , siendo la ciudad 1 la de partida y llegada. Los datos de entrada en ambas implementaciones deben ser una lista de aristas ponderadas y el número de ciudades. Cada arista debe indicarse en formato ((ciudad de origen, ciudad de destino), peso de la arista) . Se proporciona como resultado un par de la forma (ciclo óptimo de ciudades, distancia total del ciclo) en la primera implementación y de la forma (ciclo óptimo de ciudades, distancia total del ciclo) en la segunda. Fuerza bruta (con permutations ) -- | Calcula el ciclo de menor longitud a partir de la lista -- de aristas g. El número de ciudades n se da para no tener -- que recorrer g para conocerlo. menorCamino :: [((Int,Int),Float)] -> Int -> (Float,[Int]) menorCamino gn= minimum (zip (map (fn g) w) w) where v=permutations [2..n] w=anhade1 v -- | Añade el vértice 1 a cada una de las rutas. anhade1 :: [[Int]] -> [[Int]] anhade1 [] =[] anhade1 (x:xs) =(1:x) :(anhade1 xs) fn :: [((Int,Int),Float)] -> [Int]-> Float fn g (x:xs) =pesoDeCamino (x:xs) 0g -- | Calcula la distancia total de un ciclo. pesoDeCamino :: [Int]-> Float -> [((Int,Int),Float)] -> Float pesoDeCamino (x:y:xs) p g |null xs =p+(pesoArista (x,y) g) +(pesoArista (y,1) g) 2.1. ALGORITMO DE FUERZA BRUTA 7 |otherwise =pesoDeCamino (y:xs) (p +(pesoArista (x,y) g)) g -- | Devuelve el peso de la arista (x,y). pesoArista :: (Int,Int)-> [((Int,Int),Float)] -> Float pesoArista (x,y) (g:gs) |((x,y) == fst g) || ((y,x) == fst g) =snd g |otherwise =pesoArista (x,y) gs La optimización de la segunda implementación consiste en que, en lugar de calcular todos los ciclos desde el principio y luego evaluarlos, la distancia del ciclo se va actualizando a medida que se añaden vértices nuevos (como podemos ver en la función rutasPosibles ), por lo que no es necesario recorrer las listas nuevamente. Fuerza bruta (propia) -- | Calcula el ciclo de menor longitud a partir de la lista -- de aristas g. El número de ciudades n se da para no tener -- que recorrer g para conocerlo. menorCamino :: [((Int,Int),Float)] -> Int -> ([Int],Float) menorCamino gn=search (tail sig) (head sig) where sig =rutasPosibles (([1],[2..n]),0) g -- | Devuelve el ciclo de menor longitud de la lista (r:rs). search :: [([Int],Float)] -> ([Int],Float)-> ([Int],Float) search [] k=k search (r:rs) k |snd r <snd k =search rs r |otherwise =search rs k rutasPosibles :: (([Int],[Int]),Float)-> [((Int,Int),Float)] -> [([Int],Float)] rutasPosibles ((xs,[]),p) g = [(xs,p +peso (head xs) (last xs) g)] rutasPosibles (((x:xs),ys),p) g = concat [rutasPosibles (((y :x:xs), elimina y ys),p +(peso x y g)) g |y<- ys] -- | Encuentra la arista (x,y) en la lista de aristas y 8 CAPÍTULO 2. ALGORITMOS PARA LA RESOLUCIÓN DEL TSP -- devuelve su peso. peso :: Int -> Int -> [((Int,Int),Float)] -> Float peso x y (g:gs) |((x,y) == fst g) || ((y,x) == fst g) =snd g |otherwise =peso x y gs -- | Devuelve la lista (y:ys) sin el elemento x. elimina :: Int -> [Int]-> [Int] elimina x[] =[] elimina x (y:ys) |x== y=ys |otherwise =y:(elimina x ys) 2.2. Heurística Strip La heurística Strip se aplica a instancias geométricas del TSP, es decir, aquellas en las que los vértices del grafo son puntos del plano y la distancia entre ellos es la distancia euclídea. El objetivo de esta heurística es obtener una solución rápidamente, evidentemente a costa de la calidad de la misma. 2.2.1. Planteamiento Denición 2. Dado un conjunto de n puntos A={(ai, bi):1≤i≤n} ⊂ R2 , denimos el mínimo rectángulo recubridor de A como M={(x, y) : m´ın1≤i≤nai≤x≤ m´ax1≤i≤nai,m´ın1≤i≤nbi≤y≤m´ax1≤i≤nbi} . Dado el conjunto A={(ai, bi) : 1 ≤i≤n} , el algoritmo Strip comienza dividiendo M en franjas verticales de anchura pn 3 . Llamamos Mj , 1≤j≤k , a la j-ésima franja formada de esta manera, siendo M1 la situada más a la izquierda y Mk la de más a la derecha. El siguiente paso es, para cada Mj , formar una ruta que recorra sus puntos en orden creciente o decreciente de la variable y , según sea j impar o par respectivamente. Uniendo el último vértice de la ruta de Mj con el primero de la ruta de Mj+1 , 1≤j≤k−1 , y el último de Mk con el primero de M1 , obtenemos un ciclo hamiltoniano. Se puede demostrar que las rutas construidas por la heurística Strip tienen en el caso peor una longitud a lo sumo Ω(√n) veces la longitud de una ruta óptima. Las guras 2.1, 2.2 y 2.3 muestran un ejemplo de funcionamiento de la heurística. 2.2. HEURÍSTICA STRIP 9 Figura 2.1: 11 puntos generados aleatoriamente Figura 2.2: Mínimo rectángulo recubridor y su división en franjas 16 CAPÍTULO 2. ALGORITMOS PARA LA RESOLUCIÓN DEL TSP hacia el otro lado. Asumiendo únicamente que la distancia considerada satisface la desigualdad triangular (como es el caso de la distancia euclídea), garantiza que la longitud de la solución proporcionada será a lo sumo una vez y media la longitud óptima. Este es a día de hoy el mejor resultado de aproximación conocido para el TSP en espacios métricos generales. 2.4.1. Planteamiento Sea un conjunto de puntos V={v1, . . . , vn} ⊂ R2 , construimos el grafo completo inducido por V , G= (V, A) , asignando como peso a cada arista ai,j ∈A la distancia euclídea entre vi y vj . Los distintos pasos del algoritmo sobre el grafo G son: 1. Obtener el árbol de expansión mínimo T de G . 2. Sea O el conjunto de vértices de grado impar en T , hallar un emparejamiento perfecto M de mínimo peso en el grafo completo sobre los vértices de O . 3. Combinar las aristas de M y T para crear el multigrafo H . 4. Obtener un ciclo euleriano en H . 5. Obtener un ciclo hamiltoniano a partir del ciclo euleriano anterior, descartando los vértices ya visitados. Este ciclo hamiltoniano será el argumento de salida del algoritmo. En las guras 2.8, 2.9 y 2.10 puede verse un ejemplo del algoritmo de Christodes sobre el grafo de la gura 2.7. A B C D17 4 510 3 1 Figura 2.7: Grafo G 2.4. ALGORITMO DE CHRISTOFIDES 17 A B C D 4 3 1 Figura 2.8: Árbol de expansión mínimo T sobre el grafo G A B C D17 Figura 2.9: Vértices de grado impar en T y emparejamiento perfecto de mínimo coste sobre ellos A B C D17 4 3 1 Figura 2.10: Multigrafo H obtenido combinando las aristas de M y T . Coincide con los ciclos euleriano y hamiltoniano construidos sobre el propio H . 18 CAPÍTULO 2. ALGORITMOS PARA LA RESOLUCIÓN DEL TSP 2.4.2. Implementación El código de la implementación de la heurística NN viene en el CD adjunto. Puntos a destacar: El tipo con el que escribiremos los grafos será: Tipo de dato de los grafos type Node =String -- La cadena es el nombre del vértice en cuestión. type Edge =([Node], Float) -- El primer elemento es la lista de los vértices que une -- la arista y el segundo el peso de esta. Esta lista -- tendrá siempre dos elementos únicamente. type Graph =([Node], [Edge]) -- El primer elemento es la lista de vértices y el segundo -- la de aristas. El cálculo del árbol de expansión mínimo se realiza mediante el algoritmo de Kruskal, cuya implementación se ha obtenido de https://github.com/ddrake/haskellkruskal/blob/master/Kruskal.hs. El cálculo del emparejamiento perfecto de mínimo peso es la parte más complicada de implementar. El algoritmo más eciente a día de hoy se llama Blossom V y es una versión mejorada del llamado algoritmo Blossom , desarrollado por el matemático Jack Edmonds. Debido a la complejidad de esta implementación se ha recurrido a una heurística que devuelve otro emparejamiento perfecto (no de mínimo coste necesariamente), ya que se ha comprobado que en la práctica basta con obtener una buena aproximación. Esta heurística es conocida como voraz y funciona de la siguiente manera:  Tenemos un grafo ponderado G= (V, A) y una lista M de las aristas que forman el emparejamiento perfecto, inicialmente vacía.  En cada iteración se busca la arista a= ((vi, vj), p)∈A de mínimo peso y se añade a M . Se borran los vértices vi y vj de V y todas las aristas incidentes en ellos (incluyendo a ) de A . Si V es vacío termina el algoritmo y se obtiene el grafo (V, M) como argumento de salida. En caso contrario se repite este paso. 2.5. ALGORITMO GENÉTICO 19 Para el cálculo del ciclo euleriano en H se utiliza una técnica conocida como el Hilo de Ariadna para llevar la cuenta de en qué vértices ha habido una encrucijada de caminos (necesidad de elegir una de entre varias aristas para continuar construyendo el ciclo). Esto lo hacemos actualizando a medida que avanzamos una lista con ternas de la forma (vértice v visitado en este paso, 1 o 0 dependiendo de si ha habido una encrucijada en v o no, aristas incidentes en v que ya hemos probado y cuyas posibilidades dan todas a callejones sin salida). Estas ternas nos son útiles porque, aparte de llevar la cuenta del ciclo, nos dan información sobre qué hacer en cada paso dependiendo de lo que encontremos. El argumento de entrada del algoritmo es un grafo proporcionado en la forma descrita arriba (cada vértice representa a un punto y los pesos de las aristas son las distancias entre los distintos puntos), y el de salida un par de la forma (Float,[Node]) , siendo el primer elemento la longitud de la ruta construida por la heurística y el segundo la ruta propiamente dicha. La función que ejecuta el algoritmo es christofides . 2.5. Algoritmo genético Los algoritmos genéticos son una de las técnicas más usadas por la inteligencia arti- cial. Están inspirados en la evolución biológica y su base genético-molecular y se utilizan en problemas de optimización. Los algoritmos genéticos trabajan con una población de individuos, cada uno de los cuáles posee unas características determinadas que vienen codicadas en sus genes. Esta población va evolucionando a lo largo del tiempo igual que una población real de seres vivos, de forma que aquellos individuos cuyas características los hacen estar mejor adaptados tendrán más probabilidades de sobrevivir. Además del factor de supervivencia existe otro muy importante en este tipo de algoritmos, que es la capacidad de los individuos de reproducirse entre sí para dar lugar a otros cuyos genes son una combinación de los de sus progenitores. Estos genes pueden, además, sufrir mutaciones en el proceso (modicaciones aleatorias de la secuencia genómica) para dar lugar a individuos completamente distintos de los ya existentes en la población. El rendimiento del algoritmo depende en gran medida de la capacidad para expresar las características a optimizar en los individuos, es decir la capacidad de modelizar bien el problema. Esta tarea puede ser sencilla en algunos casos (como el del problema del TSP ) o muy compleja (en casos de optimización de diseños industriales, por ejemplo). 20 CAPÍTULO 2. ALGORITMOS PARA LA RESOLUCIÓN DEL TSP 2.5.1. Planteamiento Denición 4. Sea P un problema de optimización con unas restricciones dadas, x es una solución de P ( sol(P, x) ) si satisface sus restricciones. Denimos también el conjunto XP={x:sol(P, x)} de las soluciones del problema P . En el caso del problema del TSP , las soluciones son todas las permutaciones posibles de las ciudades dadas como argumento de entrada del problema, por lo que una nosolución del problema sería, por ejemplo, una lista con ciudades repetidas o donde falta alguna de ellas. Denición 5. Dado un problema de optimización P , denimos la función fP:XP→R de aptitud de P , que mide lo buena que es una solución del problema P . Para el TSP la función de aptitud es la que asigna a cada solución su distancia total. Denición 6. Sea P un problema y fP su función de aptitud, ˆx∈XP es la solución óptima de P si fP(ˆ (x)) ≥fP(x) (resp., fP(ˆ (x)) ≤fP(x) ) ∀x∈XP . La medida de la aptitud de las soluciones por parte de f es relativa, pues es posible que aunque para un problema P se tenga k=fP(ˆx) , para otro problema P0 las soluciones del conjunto f−1(k)⊂XP0 estén muy alejadas en calidad de la óptima para P0 . Así, en una instancia del TSP con 2.000 ciudades, la longitud de la solución óptima podría ser mucho mayor que la distancia de cualquiera de las soluciones de otra instancia con 10 ciudades. Un algoritmo genético para un problema de optimización P consta de los siguientes pasos: 1. Generamos aleatoriamente una población inicial de individuos llamada POB . POB es un conjunto de soluciones del problema (pudiendo haber soluciones repetidas), de forma que POB ⊂XP . 2. Aplicamos la función de aptitud fP a cada uno de los individuos de la población anterior. 3. Como en muchos casos desconocemos cuánto vale f(ˆx) para P , se utilizan otros métodos de parada. Los dos principales son: Detenerse después de un número prejado de generaciones Detenerse cuando, al producir una nueva generación, la mejor solución de esta es muy parecida a la de la generación anterior (o directamente no cambia). Estas condiciones de parada se pueden utilizar alternativa o simultáneamente. En caso de no cumplirse la condición (o las condiciones) de parada se realizan las siguientes operaciones sobre el conjunto POB : 2.5. ALGORITMO GENÉTICO 21 a ) Selección de los mejores: Tomamos un subconjunto SEL ⊂P OB de los individuos con mayor aptitud. Esta selección puede realizarse de forma completamente determinista o semialeatoria. En nuestro caso lo haremos utilizando un sistema llamado de torneo. Consiste en tomar dos individuos de POB , x e y , de forma aleatoria y calcular el valor absoluto de la diferencia f(x)−f(y) . Si esta es mayor que un parámetro, que llamaremos α , se selecciona el individuo de mayor aptitud, en caso contrario se hace aleatoriamente. Este proceso se realiza repetidas veces hasta que el conjunto SEL es lo sucientemente grande (el tamaño considerado suciente dependerá de cómo enfoquemos el problema). b ) Cruzamiento: Representa la reproducción sexual biológica y consiste en la combinación de los genes de dos individuos del conjunto SEL para dar un nuevo individuo x∈XP . Para completar la población de la siguiente generación repetiremos este proceso de cruzamiento de individuos hasta que sea necesario, obteniendo un conjunto de individuos descendientes del conjunto SEL . Este nuevo conjunto se denominará DES . Para aplicar el cruzamiento al TSP tomamos dos individuos, x e y , que serán ciclos de ciudades. Escogemos dos puntos aleatorios del ciclo de x y nos quedamos con las ciudades situadas entre estos dos puntos, obteniendo así una subsecuencia x0 donde algunos huecos han quedado vacíos. Dichos huecos serán rellenados con las ciudades que no estén en x0 colocadas en el mismo orden en el que están en y . Este proceso queda ilustrado en la gura 2.11: c ) Mutación: Este proceso se realiza sobre el conjunto DES . En cada individuo de DES se lleva a cabo una ligera modicación con una cierta probabilidad. El conjunto formado por los individuos de DES tras pasar la etapa de la mutación se denomina MUT . Aplicado al TSP , este proceso elige en cada individuo dos ciudades de su ciclo e intercambia sus posiciones (también con una cierta probabilidad). Podemos ver un ejemplo en la gura 2.12 Tras aplicar estos operadores genéticos formamos una nueva generación de individuos juntando los conjuntos SEL y MUT (que representen a los progenitores que han sobrevivido y su descendencia ya mutada). Esta nueva generación vuelve al paso 2 del algoritmo en el lugar de POB . Puede verse un esquema del funcionamiento del algoritmo en la gura 2.13. 22 CAPÍTULO 2. ALGORITMOS PARA LA RESOLUCIÓN DEL TSP 123456789 245836197 Progenitor 1 Progenitor 2 Subsecuencia del progenitor 1 4567 4567283 19 Descendiente Figura 2.11: Cruzamiento de dos individuos en una instancia del TSP con 9 ciudades. 1 345 7892 6 1 345 7896 2 Individuo original Individuo mutado Figura 2.12: Mutación de un individuo en una instancia del TSP con 9 ciudades. 2.5. ALGORITMO GENÉTICO 23 POB P OB evaluada SEL DES MUT Individuo más apto de la población Figura 2.13: Esquema del algoritmo genético 2.5.2. Implementación El código de la implementación del algoritmo genético aplicado al TSP viene en el CD adjunto. Cabe destacar varias cosas: La función que ejecuta el algoritmo es algoritmoGenetico . El argumento de entrada del algoritmo es la lista de puntos en formato (Float,Float) . No es necesario proporcionar el peso de las aristas porque se calculará como la distancia euclídea entre los puntos que conectan. La salida es un par formado por la ruta construida por el algoritmo y su longitud. El algoritmo tiene varios parámetros que se pueden modicar para obtener distintos resultados, según nos queramos centrar más en la calidad de la ruta obtenida o en acortar el tiempo de ejecución.Dichos parámetros son:  Probabilidad de mutación: es la probabilidad de que un individuo mute.  Tamaño de la población: es el número de individuos que tiene la población. Se mantiene constante al pasar de una generación a la siguiente.  Índice de superioridad: inuye a la hora de seleccionar los mejores individuos de la población. Cuando tomamos dos individuos al azar para compararlos, si la diferencia relativa entre sus aptitudes es menor que el índice superioridad entonces se elige uno de ellos al azar. En caso contrario se elige al más apto. 24 CAPÍTULO 2. ALGORITMOS PARA LA RESOLUCIÓN DEL TSP  Número de generaciones: es el número de generaciones que calcularemos antes de detener el algoritmo. Estos parámetros también inuyen a la hora de obtener soluciones que sean óptimos locales o el óptimo global. Por ejemplo, cuanto mayor sea la probabilidad de mutación mayor diversidad habrá en la población. Capítulo 3 Batería de pruebas La batería de pruebas utilizada para probar la eciencia de los algoritmos estudiados en el trabajo consta de 20 instancias del TSP obtenidas de la página http://elib.zib.de/pub/mptestdata/tsp/tsplib/tsplib.html, la cual es una biblioteca de instancias reales para el TSP y otros problemas relacionados. Todas las instancias que hemos seleccionado son conjuntos de puntos del plano (por lo que se corresponden con problemas STSP ) de distintos tamaños. El hecho de que estén contenidos en el plano facilita la implementación de los algoritmos, ya que la distancia entre estos puntos es la euclídea. Estos puntos se han guardado en cheros de texto separados para poder leerlos fácilmente con un chero de Haskell llamado intcheros. Junto con estos puntos también se ha guardado la longitud del ciclo óptimo de cada instancia para poder comprobar a posteriori la calidad de la solución obtenida por cada algoritmo. Para testear los algoritmos se ha escrito otro chero de Haskell llamado testeador que toma los puntos de cada una de esas 20 instancias y escribe un chero de texto con la longitud del ciclo construido por el algoritmo y el tiempo empleado para ello. En caso de que se sobrepase un límite de tiempo previamente establecido se pasa a la siguiente instancia automáticamente (para ello se utiliza la función timeout denida en la biblioteca System.Timeout). En la tabla 3 se pueden ver los tiempos de ejecución del algoritmo Strip para cada una de de las instancias de la batería de pruebas, así como la longitud de la ruta obtenida y la longitud de la solución óptima. Para la heurística del vecino más cercano se ha usado la batería de pruebas con un tiempo máximo de 10 minutos por instancia, obteniéndose unos resultados sorprendentemente buenos. Los resultados pueden verse en la tabla 3 (para las instancias que no se encuentran en la tabla la heurística tardó más tiempo del estipulado). Para el algoritmo genético hemos establecido un límite de tiempo de 35 minutos para cada instancia. Solamente tenemos datos de las 12 primeras (aunque la 1 y la 11 superaron el tiempo límite) porque a partir de ella se agotó la memoria del ordenador. 25 32 APÉNDICE A. DEFINICIONES DE TEORÍA DE LA COMPLEJIDAD Apéndice B Deniciones de Teoría de Grafos A continuación vamos a denir una serie de conceptos de Teoría de Grafos que hemos utilizado a lo largo de la memoria: Denición 18. Un Grafo Dirigido G consiste de dos conjuntos: V(G) : un conjunto no vacío cuyos elementos son llamados Vértices de G. E(G) : un conjunto de pares ordenados de vértices llamados Aristas de G. Nótese que por la denición se tiene que la arista (u, v) no es equivalente a la arista (v, u) . Es decir, el orden en que son listados los vértices indica la Dirección de la arista. Denición 19. Un grafo G para el cual se tiene que las aristas (u, v) y (v, u) son equivalentes es llamado Grafo No Dirigido . Ello implica que en estos grafos es válido moverse del vértice u al vértice v así como del vértice v al u pasando por la arista (u, v) . Denición 20. Un grafo G es llamado Multigrafo si posee aristas repetidas (también conocidas como Aristas Múltiples o Aristas Paralelas ). Denición 21. Sea G un grafo. Los vértices u , v∈V(G) se denominan Adyacentes si existe una arista e∈E(G) tal que e= (u, v) . En tal caso, u y v son llamados Puntos Finales o Extremos de e , y además se dice que e conecta u y v . Además, la arista e se dice que es Incidente a cada uno de sus puntos nales u y v . Denición 22. El Grado de un Vértice v en un grafo G , denotado como deg(v) , es igual al número de aristas en G que contienen a v , es decir, aquellas que son incidentes a v . Denición 23. Se dice que un vértice es Par o Impar de acuerdo a si su grado es un número par o impar, respectivamente. 33 34 APÉNDICE B. DEFINICIONES DE TEORÍA DE GRAFOS Denición 24. Considérese un grafo G con sus conjuntos V(G) y E(G) . Un grafo H con sus conjuntos V(H) y E(H) es llamado un Subgrafo de G si los vértices y aristas de H están contenidas en los conjuntos de vértices y aristas de G . Denición 25. Sea U un conjunto de vértices tal que U⊂V(G) . G{U} denota el subgrafo de G cuyas aristas son aristas de G y sus vértices están en U . A G{U} se le llama el Subgrafo Inducido por el Conjunto de Vértices U . Denición 26. Si v es un vértice en G , entonces G\v es el subgrafo de G obtenido al eliminar a v de G y al eliminar a todas las aristas en G que contienen a v . Denición 27. Si e es una arista en G , entonces G\e es el subgrafo obtenido al eliminar la arista e de G . Denición 28. Una Ruta en un grafo G consiste de una secuencia alternante de vértices y aristas de la forma (v0, e1, v1, e2, v2, . . . , en−1, vn−1, en, vn) . En donde cada arista ei contiene los vértices vi−1 y vi (los cuales aparecen antes y después de ei en la secuencia. Al número n de aristas se le denomina la Longitud de la Ruta . Por simplicidad, se denota a una ruta solo por la secuencia de sus vértices, asumiendo que efectivamente existen las aristas que conectan a dos vértices consecutivos dentro de la misma. Denición 29. Se dice que una ruta es Cerrada si v0=vn . Una Ruta Simple es aquella en la cual todos sus vértices son distintos. Una ruta en la cual todas las aristas son distintas es llamada una Vía . Un Circuito es una ruta cerrada de longitud mayor o igual que 3 en la cual todos los vértices son distintos excepto v0=vn . Denición 30. Se dice que un grafo G es Completo si para cualquier par de vértices u , v en V(G) , u6=v , existe en E(G) la arista (u, v) que los conecta. Denición 31. Un grafo G es llamado Grafo Pesado o Grafo Ponderado si a cada arista e de G le es asignado un número no negativo w(e) llamado el Peso de e . Denición 32. El Peso de una Ruta en un grafo pesado de G es denido como la suma de los pesos de las aristas en la ruta. Denición 33. Un grafo G es Conectado si existe una ruta entre cualesquiera dos de sus vértices. Denición 34. Una Ruta Euleriana en un grafo conectado G es una ruta que pasa por cada arista de G exactamente una vez, aunque puede visitar a un vértice en más de una ocasión. Si un grafo tiene una ruta Euleriana y además ésta es una ruta cerrada entonces se tiene que tal ruta de hecho es un Circuito Euleriano y el grafo es caracterizado como Grafo Euleriano . 35 Teorema 35. Un grafo conectado es Euleriano si y solo si cada uno de sus vértices tiene grado par. Denición 36. Un Circuito Hamiltoniano en un grafo conectado G es un circuito que contiene a todos los vértices de G . Si G admite un circuito Hamiltoniano entonces G es llamado Grafo Hamiltoniano . Denición 37. A un grafo T se le llama Árbol si es conectado y además T no tiene circuitos. Denición 38. Un subgrafo T de un grafo conectado G es llamado un Árbol de Expansión de G si T es un árbol y además T incluye a todos los vértices de G , es decir, V(T) = V(G) . En el caso de que G sea ponderado, un árbol de expansión T de G es el Árbol de Expansión Mínimo de G si la suma de los pesos de sus aristas es el mínimo de todos los árboles de expansión de G . Denición 39. Un Emparejamiento Perfecto de G es un subconjunto M de las aristas de G tal que cada vértice de G es incidente exactamente con una de las aristas de M . En el caso de que G sea ponderado, un emparejamiento perfecto M de G es el Emparejamiento Perfecto de Mínimo Coste si el peso total de M , es decir, la suma de los pesos de las aristas de M es la menor de todos los emparejamientos perfectos de G . 36 APÉNDICE B. DEFINICIONES DE TEORÍA DE GRAFOS Bibliografía [1] Aguila, R.P. Una introduccion a las matematicas discretas y teoria de grafos . El Cid Editor, 2013. [2] Applegate, D.L., Bixby, R.E., Cook, W.J., and Chvatal, V. The Traveling Salesman Problem: A Computational Study . Princeton University Press, 2007. [3] Avis, D. A survey of heuristics for the weighted matching problem. Networks (1983). [4] Bentley, J.L. Multidimensional binary search trees used for associative searching. Communications of the ACM (1975). [5] Bentley, J.L. Fast algorithms for geometric traveling salesman problems. ORSA Journal on Computing (1990). [6] Friedman, J.H., Bentley, J.L., and Finkel, R.A. An algorithm for nding best matches in logarithmic expected time. ACM Transactions on Mathematical Software (1977). [7] Gutin, G., and Punnen, A. The Traveling Salesman Problem and its Variations . Kluwer Academic Publishers, 2002. [8] Kao, M.Y. Encyclopedia of Algorithms . Springer, 2008. [9] Sipser, M. Introduction to the Theory of Computation . PWS Publishing, 1997. 37