Por favor, use este identificador para citar o enlazar este ítem:
http://cicese.repositorioinstitucional.mx/jspui/handle/1007/437| Problema de asignación de guardaespaldas multiclase Multiclass bodyguard allocation problem | |
| Lino Alberto Rodríguez Coayahuitl | |
| Jose Alberto Fernandez Zepeda | |
| Acceso Abierto | |
| Atribución | |
| Algoritmos | |
| En este trabajo se presenta el problema de asignación de guardaespaldas multiclase (PAGM). Este problema es una versión más general del problema de asignación de guardaespaldas (PAG). El PAG lo propuso Fajardo-Delgado et al. (2013), y consiste en construir un árbol de esparcimiento en grafos conectados donde se presentan tres tipos de vértices: blancos, negros y la raíz. Cada tipo de vértice tiene un objetivo distinto: los vértices blancos buscan minimizar su distancia a la raíz dentro del árbol de esparcimiento, mientras que los vértices negros, buscan maximizarla. Una de las limitaciones del PAG es que sólo contempla dos clases de vértices, por lo que el objetivo de este trabajo es extender el problema del PAG para que contemple más clases de vértices, no solo aquellos que buscan estar en los extremos del árbol de esparcimiento, sino también vértices que busquen estar a cualquier distancia especí?ca de la raíz. Una solución del PAGM es un árbol en el que se cumple una condición de equilibrio y se maximiza el bienestar social. El PAGM se estudia desde la teoría de juegos, y se propone un enfoque cooperativo y uno no cooperativo para encontrar soluciones al PAGM. Se propone un algoritmo centralizado, CBAPM, y un algoritmo distribuido, DBAPM, que utilizan uno de estos dos enfoques para resolver casos del PAGM. Se analiza de manera rigurosa la convergencia al equilibrio de estos algoritmos bajo cualquiera de los dos enfoques, así como su tiempo de ejecución, en función del tamaño del caso de entrada.Se propone un algoritmo denominado CBAPM mixto (M-CBAPM), que combina de manera secuencial los enfoques no cooperativo y cooperativo, con el objetivo de encontrar mejores soluciones de las que se pueden obtener si se utiliza cualquiera de los dos enfoques de manera individual. Se proponen tres variantes de este algoritmo: M-CBAPM, CBAPM mixto apartir del mejor bienestar social (M-CBAPM-BSW) y CBAPM mixto doble (DM-CBAPM).Por último, para llevar acabo pruebas experimentales de los algoritmos propuestos, se propuso un conjunto de casos especí?cos del PAGM. Se utilizó la metodología propuesta por Zatarain Aceves (2011) para el diseño de este conjunto de casos especí?cos. Se comparó el enfoque cooperativo contra el no cooperativo, para determinar bajo qué condiciones uno es mejor que el otro; y por último se compararon estos dos contra el enfoque del algoritmo M-CBAPM. In this thesis, we extended the bodyguard allocation problem (BAP) into the multiclass bodyguard allocation problem (MBAP). The BAP was originally proposed in (Fajardo- Delgado et al., 2013), and its objective is to build a spanning tree in a connected graph in which there are three types of vertices: white, black and the root. Each type of vertex has a different objective: the white vertices seek to minimize their distance to the root while black vertices seek to maximize it. A limitation of the BAP is that it only considers two classes of vertex, those that try to get as close as possible to the root, and those that try to get as far as possible from it. The objective of this work is to extend the model of the BAP, so it considers vertices that try to stay at speci?c distances from the root.We call this extended problem the MBAP.A solution to the MBAP is a spanning tree that satis?es a condition of equilibrium and maximizes the social welfare. We study the MBAP from a game theory perspective. We proposed a cooperative approach and a non-cooperative approach to solve the MBAP. We proposed the CBAPM, a centralized algorithm, and the DBAPM, a distributed algorithm, (both based on the algorithms originally proposed by Fajardo-Delgado et al. (2013) for the BAP), that use any of the two approaches to solve the MBAP. We analysed the conver- gence to a solution of the proposed algorithms under each approach. We also analysed the execution time of the algorithms according to the size of the input.We also proposed a mixed approach algorithm, M-CBAPM, that combines both non- cooperative and cooperative approaches in a sequential manner. The objetive of the M- CBAPM is to reach solutions with higher social welfare than those algorithms working independently. We proposed three variants of the mixed algorithm: M-CBAPM, M-CBAPM using best non-cooperative social welfare (M-BAPM-BSW), and double round M-CBAPM (DM-CBAPM).In order to carry experimental simulations of the proposed algorithms, we proposed a collection of MBAP instances. We used the methodology proposed by Zatarain Aceves (2011) for the design of such instances. We compared the performances of the coope- rative, non-cooperative and mixed approaches, to determine under what conditions each approach surpasses the others. | |
| CICESE | |
| 2014 | |
| Tesis de maestría | |
| Español | |
| Rodríguez Coayahuitl,L.A.2014.Problema de asignación de guardaespaldas multiclase.Tesis de Maestría en Ciencias. Centro de Investigación Científica y de Educación Superior de Ensenada, Baja California.xi, 88 pp. | |
| CIENCIA DE LOS ORDENADORES | |
| Aparece en las colecciones: | Tesis - Ciencias de la Computación |
Cargar archivos:
| Fichero | Descripción | Tamaño | Formato | |
|---|---|---|---|---|
| 236481.pdf | Versión completa de la tesis | 2.98 MB | Adobe PDF | Visualizar/Abrir |