Ordenación por reversiones de permutaciones sin signo usando un enfoque de algoritmos genéticos

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.