Por favor, use este identificador para citar o enlazar este ítem:
http://cicese.repositorioinstitucional.mx/jspui/handle/1007/3354| Algoritmos genéticos para el problema de localización de radio bases | |
| Everardo Gutiérrez López | |
| Carlos Alberto Brizuela Rodriguez | |
| Acceso Abierto | |
| Atribución | |
| Algoritmos genéticos, Optimización combinatoria | |
| En la actualidad existe un conjunto de problemas para los cuales no se conoce ningún método eficiente para resolverlos computacionalmente. Este conjunto de problemas pertenece a la clase NP-completa. La mayoría de estos problemas han sido tratados utilizando meta-heurísticas, obteniendo resultados alentadores en muchos de los casos. Entre las meta-heurísticas más utilizadas se encuentran los Algoritmos Genéticos, que son parte de la Computación Evolutiva, los cuales están inspirados en los mecanismos de evolución natural. El problema del Conjunto Mínimo Dominante pertenece a la clase NP-completa y es un problema de grafos que tiene diversas aplicaciones en el mundo real. Una de ellas es el problema de Localización de Radio Bases (LRB), que es parte de la planificación de redes móviles celulares. Este problema consiste en seleccionar los sitios más adecuados, de un conjunto de sitios candidatos, donde instalar radio bases de tal forma que se de la mayor cobertura posible. En este trabajo de tesis, se propone un algoritmo genético para tratar el problema de LRB. Se propone una representación para el problema así como los operadores necesarios para esa representación. Se compara el desempeño del algoritmo propuesto con el utilizado en trabajos anteriores, utilizando dos modelos del problema. Se analiza además la calidad de la solución generada por el algoritmo propuesto, en un caso que considera las características de la tecnología CDMA (Code Division Multiple Access). Se presenta también un análisis del comportamiento del algoritmo utilizando el concepto de vecindades. Los resultados obtenidos en este trabajo indican, por un lado, que el algoritmo propuesto es superior a los utilizados anteriormente en la literatura, y que las soluciones que genera son aceptables en un entorno CDMA. Por último, el análisis de vecindades nos muestra que las vecindades generadas sobre la representación entera mejoran a las generadas sobre la representación binaria.
There are many problems for which it is not known algorithms that can solve any given instance efficiently. These problems belong to a special class denominated the NP-complete class. Search techniques such as Meta-Heuristics have been deal with sorne of these problems giving good results. Genetic Algorithms are one of the most successful ones, they are a part of Evolutionary Computation, and are inspired in the mechanisms of natural evolution. The Minimum Dominating Set problem belongs to NP-complete class, it is a graph problem which has severa! applications in the real world. One of them is the Base Station Location (BSL) problem, which is part of the cell planning process in cellular networks. This problem consists of the appropriate selection of sites where to install base stations, such that the serviced area is optimized. In this thesis, we propase a genetic algorithm for the BSL problem. We propase a representation for the problem, and its corresponding operators. We compare the performance of the proposed algorithm with algorithms used befare in the literature. The comparison is over a set of instances generated by two models of the problem. We analyze the quality of a solution generated by the proposed algorithm, in an scenario where the CDMA (Code Division Multiple Access) technology is considered. We present an analysis of the algorithm behavior based on neighborhood concepts. The results obtained in this work show that the proposed algorithm improves others previously proposed in the literature, and that the solutions are acceptable from the system capacity point of view, for a given scenario. Finally, the neighborhood analysis shows that the neighborhoods over the integer representation improve the neighborhoods over the binary representation. | |
| CICESE | |
| 2003 | |
| Tesis de maestría | |
| Español | |
| Gutiérrez López, E. 2003.Algoritmos genéticos para el problema de localización de radio bases. Tesis de Maestría en Ciencias. Centro de Investigación Científica y de Educación Superior de Ensenada, Baja California. 89 pp. | |
| TECNOLOGÍA DE LOS ORDENADORES | |
| Aparece en las colecciones: | Tesis - Ciencias de la Computación |
Cargar archivos:
| Fichero | Tamaño | Formato | |
|---|---|---|---|
| 158191.pdf | 7.61 MB | Adobe PDF | Visualizar/Abrir |