Por favor, use este identificador para citar o enlazar este ítem: http://repositorio.espam.edu.ec/handle/42000/1105
metadata.dc.type: bachelorThesis
Título : Representaciones cromosómicas del algoritmo NSGA-II para el problema de árbol de expansión mínima multiobjetivo (MST-MO)
Autor : Guamán Bravo, Paola Victoria
metadata.dc.contributor.advisor: Párraga Álava, Jorge Antonio
Palabras clave : NSGA-II;Árbol de expansión mínima multiobjetivo;Representaciones para algoritmos genéticos;Prüfer number
Fecha de publicación : dic-2019
Editorial : Calceta: ESPAM MFL
metadata.dc.rights: openAccess
Atribución-NoComercial-SinDerivadas 3.0 Ecuador
metadata.dc.format.extent: 80 p.
Resumen : La finalidad de este trabajo de titulación consistió en identificar la mejor alternativa de representación cromosómica que lograse mejorar el rendimiento en términos multiobjetivo de un algoritmo genético conocido como NSGA-II, el cual fue utilizado a la vez para abordar el problema del árbol de expansión mínima en su versión multiobjetivo. Esta identificación se logró a través de la evaluación exhaustiva de tres distintos tipos de representación cromosómica: Prüfer number, link and node biased encoding (LNB), y edge-set encoding. En unión a ello, se emplearon métodos de investigación científica (bibliográfico y analítico) para la búsqueda, interpretación y análisis de la información y de los resultados obtenidos en cada ejecución. Se empleó el software RStudio para la codificación y posterior ejecución de las representaciones, mismas que fueron aplicadas al NSGA-II junto con sus operadores evolutivos respectivos. En la realización de los experimentos computacionales se utilizaron datos de expresión génica, los cuales corresponden a cuatro bases de datos distintas disponibles en la web: arabidopsis, cell cycle, sporulation y serum. Una vez realizados dichos experimentos, se evaluó el rendimiento de las representaciones utilizando la métrica de desempeño multiobjetivo hipervolumen, con el fin de identificar las mejores fronteras de Pareto de cada representación. Luego del cálculo del hipervolumen se aplicaron pruebas estadísticas a sus datos por medio de los tests de Friedman y Nemenyi. Dichos cálculos de hipervolumen y test estadísticos permitieron determinar que la representación LNB fue la mejor alternativa para el mejoramiento del NSGA-II.
Descripción : The purpose of this titration work was to identify the best alternative of chromosome representation that could improve the performance in multiobjective terms of a genetic algorithm known as NSGA-II, which was used at the same time to address the problem of the minimum spanning tree in its multiobjective version. This identification was achieved through the thorough evaluation of three different types of chromosome representation: Prüfer number, link and node biased encoding (LNB), and edge-set encoding. In conjunction with this, scientific research methods (bibliographic and analytical) were used to search, interpret and analyze the information and the results obtained in each execution. RStudio software was used for the coding and subsequent execution of the representations, which were applied to the NSGA-II together with their respective evolutionary operators. In the realization of the computational experiments, gene expression data were used, which correspond to four different databases available on the web: arabidopsis, cell cycle, sporulation and serum. Once these experiments were performed, the performance of the representations was evaluated using the hypervolume multiobjective performance metric, in order to identify the best Pareto boundaries of each representation. After the calculation of the hypervolume, statistical tests were applied to their data by means of the Friedman and Nemenyi tests. These hypervolume calculations and statistical tests allowed us to determine that the LNB representation was the best alternative for the improvement of NSGA-II.
URI : http://repositorio.espam.edu.ec/handle/42000/1105
Aparece en las colecciones: Trabajo de Titulación

Ficheros en este ítem:
Fichero Descripción Tamaño Formato  
TTC22.pdf4,73 MBAdobe PDFVista previa
Visualizar/Abrir


Este ítem está sujeto a una licencia Creative Commons Licencia Creative Commons Creative Commons