Registro:
| Documento: | Tesis de Grado |
| Título: | Biased random key genetic algorithm con búsqueda local para el Team Orienteering Problem |
| Autor: | Lix-Klett, Alejandro Federico |
| Editor: | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales |
| Publicación en la web: | 2025-06-12 |
| Fecha de defensa: | 2018 |
| Fecha en portada: | 2018 |
| Grado Obtenido: | Grado |
| Título Obtenido: | Licenciado en Ciencias de la Computación |
| Departamento Docente: | Departamento de Computación |
| Director: | Loiseau, Irene |
| Jurado: | Feuerstein, Esteban Zindel; Lin, Min Chih |
| Idioma: | Español |
| Palabras clave: | TEAM ORIENTEERING PROBLEM; BIASED RANDOM KEY GENETIC ALGORITHM; ROUTING PROBLEM; BUSQUEDA LOCAL; DECODIFICADORTEAM ORIENTEERING PROBLEM; BIASED RANDOM KEY GENETIC ALGORITHM; ROUTING PROBLEM; LOCAL SEARCH HEURISTIC; ROUTING PROBLEMS; DECODER |
| Formato: | PDF |
| Handle: |
http://hdl.handle.net/20.500.12110/seminario_nCOM000631_LixKlett |
| PDF: | https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000631_LixKlett.pdf |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/seminario/document/seminario_nCOM000631_LixKlett |
| Ubicación: | Dep.COM 000631 |
| Derechos de Acceso: | Esta obra puede ser leída, grabada y utilizada con fines de estudio, investigación y docencia. Es necesario el reconocimiento de autoría mediante la cita correspondiente. Lix-Klett, Alejandro Federico. (2018). Biased random key genetic algorithm con búsqueda local para el Team Orienteering Problem. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de http://hdl.handle.net/20.500.12110/seminario_nCOM000631_LixKlett |
Resumen:
En el Orienteering Problem (OP) [25], se da un conjunto de nodos, cada uno con un beneficio determinado. El objetivo es determinar una ruta, limitada en su longitud, que visite a algunos nodos maximizando la suma de los beneficios obtenidos. El OP se puede formular de la siguiente manera: dado n nodos en el plano euclidiano cada uno con un beneficio, donde benef icio(nodoi) > 0 si 0 < i < n y beneficio(nodo1) = bene ficio(nodoi) = 0, se debe encontrar una ruta de beneficio máximo a través de estos nodos, iniciando en el nodo1 y finalizando en el nodo1, de longitud no mayor que dmax. Tsiligirides [25] fue el primero en presentar este problema y lo llamó Score Orienteering Event (SOE). El Team Orienteering Problem (TOP) [9] es la generalización al caso de múltiples rutas del Orienteering Problem. Resolver el TOP implica encontrar un conjunto de rutas desde el nodo de inicio hasta el nodo final de forma tal que se maximice la sumatoria de los beneficios recolectados, la distancia de todas las rutas no supere a dmax y ningún nodo sea visitado más de una vez. El OP pertenece a la clase problemas NP-Completo ya que contiene al problema Traveling Salesman Problem como caso especial (ver Garey y Johnson [13]). De la misma manera, el TOP pertenece a la clase de problemas NP-Completo porque contiene al OP como un caso especial donde solo hay una ruta. Resolver el TOP requiere determinar qué subconjunto de nodos se visitarán, a que ruta serán asignados y el orden en que serán visitados. En este trabajo, propongo una combinación del Biased Random Key Genetic Algorithm (BRKGA) [4] y de búsquedas locales para resolver el TOP. El BRKGA es una clase de algoritmos genéticos cuya población inicial es generada utilizando un decodificador que convierte un conjunto de vectores de números enteros aleatorios, en un conjunto de soluciones válidas del problema. El BRKGA es una variante del Random Key Genetic Algorithm (RKGA). Estos algoritmos se diferencian en el proceso de apareamiento (crossover ), mientras que en el RKGA los padres son elegidos al azar entre todos los individuos de la población, en la mayoría de las implementaciones del BRKGA uno de los padres siempre pertenece al subconjunto de los mejores individuos de la población y este padre tiene mayor probabilidad de transmitir sus genes al individuo resultante del proceso de apareamiento. En mi algoritmo, en cada nueva generación, la mejor solución se mejora con algunas búsquedas locales. Dada una solución s, un algoritmo de búsqueda local básicamente busca mejores soluciones en la vecindad de s. La solución s 0 en la vecindad de s, es mejor que s si el beneficio total recolectado por s 0 es mayor al de s o si sus beneficios recolectados son iguales y la distancia recorrida por las rutas de s 0 es menor a la de s. En este trabajo implementé los algoritmos de búsqueda local: Insert, Swap, 2-Opt, Simple Replace y Mutiple Replace. Los experimentos computacionales los realicé en instancias estándar de la literatura. Las instancias se dividen en siete conjuntos. Los primeros tres conjuntos de instancias son los de Tsiligirides [25] y los siguientes cuatro conjuntos son los de Chao et al. [9]. Todas las instancias pueden encontrarse en [18]. Mis resultados fueron comparados con los i resultados obtenidos por los siguientes autores: Chao, Golden y Wasil 1996 [9] (CGW), Tang y Miller-Hooks 2005 [24] (TMH), Archetti, Hertz, Speranza 2007 [1] (AHS), Ke, Archetti y Feng 2008 [19] (KAF) y Bouly, Dang y Moukrim 2010 [5] (BDM). Los resultados de mi algoritmo son muy buenos dado que en el 70 % de las instancias del benchmark mi implementación obtuvo la mejor solución conocida y para el 30 % restante obtuvo valores competitivos con los trabajos previamente mencionados.
Abstract:
In the Orienteering Problem (OP) [25], a set of nodes is given, each with a certain benefit. The objective is to determine a path, limited in length, that visits some nodes in order that maximizes the sum of the collected benefits. The OP can be formulated in the following way: given n nodes in the euclidean plane each with a benefit, where benefit(nodei) > 0 if 0 < i < n and benefit (node1) = benefit (noden) = 0, find a route of maximum benefit through these nodes beginning at node1 and ending at noden of length no greater than dmax. Tsiligirides [25] was the first one to present this problem and called it Score Orienteering Event (SEO). The Team Orienteering Problem (TOP) [9] is the generalization to the case of multiple tours of the Orienteering Problem. Solving TOP involves finding a set of paths from the starting node to the ending node such that the total collected benefit received from visiting a subset of nodes is maximized, the length of each path is restricted by dmax and no node is visited more than once. The OP belongs to the class of NP-Hard problems, as it contains the well known Travelling Salesman Problem as a special case (see Garey y Johnson [13]). In the same way, TOP belongs to the NP-Hard problems as it contains the OP as a special case when there is only one path. Solving TOP requires not only determining a calling order on each tour, but also selecting which subset of nodes in the graph to visit. In this dissertation, I propose a combination of the Biased Random Key Genetic Algorithm (BRKGA) [4] and local searches to solve the TOP. The BRKGA is a class of genetic algorithms that initializes its population using a decoder that converts a set of random integer vectors into a set of valid solutions of the problem. The BRKGA is a variant of the Random Key Genetic Algorithm (RKGA). These algorithms differ in the mating process (crossover ), while in the RKGA the parents are chosen randomly between all individuals of the population, in most of the BRKGA implementations one of the parents always belongs to the subset of best individuals of the population and this parent has better chances of transmitting his gens to the individual resulting from the mating process. In my algorithm, in every new generation, the best solution is enhanced with some local searches. Given a solution s, a local search algorithm searches for better solutions in the neighborhood of s. The solution s 0 in the neighborhood of s, is better than s if the total collected benefit from s 0 is greater than the one from s or their total collected benefit are equal and the distance traveled by the routes of s 0 is less than the distance traveled by the routes of s. In this work, I implemented the following local search algorithms: Insert, Swap, 2-Opt, Simple Replace y Mutiple Replace. I performed the computational experiments in standard instances of the literature. The instances are divided in seven sets. The first three sets of instances are those of Tsiligirides [25] and the other four sets are those of Chao et al. [9]. All instances can be found in [18]. My results were compared with the results obtained by the following authors: Chao, Golden and Wasil 1996 [9] (CGW), Tang and Miller-Hooks 2005 [24] (TMH), Archetti, Hertz and iii Speranza 2007 [1] (AHS), Ke, Archetti and Feng 2008 [19] (KAF) and Bouly, Dang and Moukrim 2010 [5] (BDM). The results of my algorithm are very good given that in 70 % of the instances of the benchmark my implementation obtained the best known solution and for the remaining 30 % it obtained competitive values with the previously mentioned works.
Citación:
---------- APA ----------
Lix-Klett, Alejandro Federico. (2018). Biased random key genetic algorithm con búsqueda local para el Team Orienteering Problem. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/seminario_nCOM000631_LixKlett
---------- CHICAGO ----------
Lix-Klett, Alejandro Federico. "Biased random key genetic algorithm con búsqueda local para el Team Orienteering Problem". Tesis de Grado, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2018.https://hdl.handle.net/20.500.12110/seminario_nCOM000631_LixKlett
Estadísticas:
Descargas mensuales
Total de descargas desde :
https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000631_LixKlett.pdf
Distrubución geográfica
