Look-up in Google Scholar
Title: Ordenación por reversiones de permutaciones sin signo usando un enfoque de algoritmos genéticos
Other Titles: Ordenação por reversões de permutações sem sinal usando uma abordagem de algoritmos genéticos
Advisor(s): Ayala Rincón, Mauricio
OCDE field: http://purl.org/pe-repo/ocde/ford#2.02.04
Issue Date: 2013
Institution: Universidade de Brasília
Abstract: Ordenación de permutaciones por reversiones es uno de los problemas más desafiantes relacionados con el análisis de la distancia evolutiva entre organismos. En el caso de permutaciones con signo, el problema puede ser resuelto en tiempo lineal, sin embargo en el caso de permutaciones sin signo el problema fue demostrado que es NP-Hard. En este trabajo se ha propuesto un algoritmo genético (AG) para resolver el problema de ordenación de permutaciones sin signo. Este enfoque está basado en el método propuesto por Auyeung y Abraham que usa soluciones exactas para el caso de permutaciones con signo para resolver la versión del problema sin signo. Además, fue propuesto un AG mejorado que usa una heurística de eliminación de puntos de quiebra antes de la primera generación. Diversos experimentos fueron realizados tomando como entrada permutaciones generadas aleatoriamente. Ya que muchos enfoques de AG usaron mecanismos de control imprecisos para validad la precisión de sus respuestas, fue necesario implementar y corregir el algoritmo de radio de aproximación 1.5 (Aprox 1.5) propuesto por Christie. Resultados de los experimentos mostraron que ambos AG’s dan respuestas que son mejores que aquellas dadas por métodos relacionados de la literatura, tanto como aquellas respuestas dadas por el algoritmo Aprox 1.5.
Discipline: Ingeniería y tecnología
Grade or title grantor: Universidade de Brasília. Instituto de Ciências Exatas. Departamento de Ciência da Computação
Grade or title: Maestro en Informática
Register date: 29-Nov-2017; 29-Nov-2017

Files in This Item:
File Description SizeFormat 
Soncco_Alvarez_Jose_Luis_M.pdf994.26 kBAdobe PDFThumbnail
View/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.