Por favor, use este identificador para citar o enlazar este ítem:
http://cicese.repositorioinstitucional.mx/jspui/handle/1007/2455| Resolviendo el problema de asignación de guardaespaldas utilizando algoritmos genéticos Solving the bodyguard allocation problem using genetic algorithms tehniques | |
| Héctor Zatarain Aceves | |
| Jose Alberto Fernandez Zepeda Carlos Alberto Brizuela Rodriguez | |
| Acceso Abierto | |
| Atribución | |
| Cómputo evolutivo,Sistemas distribuidos,Algotirmos genéticos,Modelos de grafos aleatorios | |
| La cooperación entre distintos procesadores en un sistema distribuido permite cumplir un objetivo global. En sistemas distribuidos grandes, los procesadores pueden tener un objetivo individual, por lo cual su comportamiento puede ser egoísta al intentar lograr dicho objetivo. La decisión de un procesador de mejorar su función de utilidad puede entrar en conflicto con el cumplimiento del objetivo global del sistema, especialmente cuando uno o más procesadores buscan de forma egoísta incrementar unilateralmente su propia utilidad. En este documento se presenta un problema que se puede ver como un juego en un sistema distribuido. Se supone que existen dos clases de procesadores y cada clase tiene un objetivo individual opuesto entre ellos, pero todos los procesadores en el sistema deben cooperar para alcanzar un objetivo común global. En esta tesis se estudia esta problemática, siendo la distancia entre procesos el parámetro en conflicto en el sistema distribuido, y se le llama “Problema de Asignación de Guardaespaldas”. Existe un algoritmo determinístico que genera soluciones aproximadas a este problema. Los algoritmos genéticos tienen muy buenos resultados para una gran variedad de problemas en donde no se conocen algoritmos determinísticos exactos y eficientes, debido a que el espacio de soluciones es muy extenso y por lo tanto, realizar una búsqueda exhaustiva determinística genera tiempos de ejecución muy grandes. En esta tesis se propone el uso de algoritmos genéticos para resolver el Problema de Asignación de Guardaespaldas. Se determina la configuración del algoritmo genético y la representación de soluciones con las que se obtiene el valor más alto al evaluar la función objetivo. Además, se proponen distintas variantes de algoritmos híbridos que combinan el algoritmo determinístico existente con el algoritmo genético propuesto. Se realizan comparaciones entre el algoritmo híbrido, el algoritmo genético y el algoritmo determinístico existente ante una gran variedad de casos de prueba. Se concluye que el algoritmo híbrido es el que obtiene mejores resultados ante cualquier tipo de caso de prueba, no obstante el algoritmo determinístico necesita un menor tiempo de ejecución. Cooperation between different processors in a distributed system allows the fulfillment of a global objective. Distributed algorithms that provide the required coordination make possible such cooperation; however, in large distributed systems, processors can also have an individual objective, so their behavior can be selfish when they attempt to improve their individual objective. The decision of a processor for improving its individual utility function may conflict with the global objective of the system, especially when one or more processors increase their individual utility in a selfish way. This document studies a computational problem that can be viewed as a game in a distributed system. It assumes the existence of two types of processors and each type has an individual objective that is opposite to the objective of the other. Also, all the processors in the system have to cooperate to achieve a common global objective. In this thesis we study this issue considering that the parameter in conflict is the distance between processors in the distributed system. This problem is the “bodyguard allocation problem”. There exists a deterministic algorithm that generates approximate solutions to this problem. Genetic algorithms have been successfully used for a wide variety of problems where there are no exact deterministic algorithms. In these problems, the searching space is very large and performing an exhaustive search is not feasible. This thesis proposes the use of genetic algorithms to generate solutions for the bodyguard allocation problem. The work presents an experimental study comparing different representations of solutions to the problem for an implementation with genetic algorithms. We determined the best configuration and the best representation for this problem. In addition to the genetic algorithm, we proposed different variants of hybrid algorithms that combine the existing deterministic algorithm with our proposed genetic algorithm. We made comparisons among the proposed genetic algorithm, the proposed hybrid algorithms and the existing deterministic algorithm, with a variety of instances, to determine the best algorithm. The hybrid algorithm generates the highest global utility; however, the existing deterministic algorithm is faster than the hybrid and than all other genetic variants. | |
| CICESE | |
| 2011 | |
| Tesis de maestría | |
| Español | |
| Zatarain Aceves, H.2011.Resolviendo el problema de asignación de guardaespaldas utilizando algoritmos genéticos.Tesis de Maestría en Ciencias.Centro de Investigación Científica y de Educación Superior de Ensenada, Baja California.142 pp. | |
| TECNOLOGÍA DE LOS ORDENADORES | |
| Aparece en las colecciones: | Tesis - Ciencias de la Computación |
Cargar archivos:
| Fichero | Tamaño | Formato | |
|---|---|---|---|
| 187781.pdf | 4.97 MB | Adobe PDF | Visualizar/Abrir |