Buscar en Google Scholar
Título: Ordenación por reversiones de permutaciones sin signo usando un enfoque de algoritmos genéticos
Otros títulos: Ordenação por reversões de permutações sem sinal usando uma abordagem de algoritmos genéticos
Asesor(es): Ayala Rincón, Mauricio
Campo OCDE: http://purl.org/pe-repo/ocde/ford#2.02.04
Fecha de publicación: 2013
Institución: Universidade de Brasília
Resumen: 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.
Disciplina académico-profesional: Ingeniería y tecnología
Institución que otorga el grado o título: Universidade de Brasília. Instituto de Ciências Exatas. Departamento de Ciência da Computação
Grado o título: Maestro en Informática
Fecha de registro: 29-nov-2017; 29-nov-2017

Ficheros en este ítem:
Fichero Descripción Tamaño Formato  
Soncco_Alvarez_Jose_Luis_M.pdf994.26 kBAdobe PDFVista previa
Visualizar/Abrir


IMPORTANTE
La información contenida en este registro es de entera responsabilidad de la universidad, institución o escuela de educación superior que administra el repositorio académico digital donde se encuentra el trabajo de investigación y/o proyecto, los cuales son conducentes a optar títulos profesionales y grados académicos. SUNEDU no se hace responsable por los contenidos accesibles a través del Registro Nacional de Trabajos de Investigación – RENATI.