Ordenação por reversões de permutações sem sinal usando uma abordagem de algoritmos genéticos
Autor(a)
Soncco Álvarez, José Luis
Orientador(a) Coorientador(a)
Ayala-Rincón, Mauricio
Data de aceite
2013-08-02
Data de disponibilizacao
2013-08-02
Data de publicacao
2013-08-02
Data de defesa submissao
2013-02-25
Citacao
SONCCO ÁLVAREZ, José Luis. Ordenação por reversões de permutações sem sinal usando uma abordagem de algoritmos genéticos. 2013. 57 f., il. Dissertação (Mestrado em Informática)—Universidade de Brasília, Brasília, 2013.
Dissertação (mestrado)—Universidade de Brasília, Departamento de Ciência da Computação, 2013.
Resumo Portugues
Ordenação de permutações por reversões é um dos problemas mais desafiantes relacionados com a análise da distância evolutiva entre organis- mos, cujos resultados podem ser usados na construção de árvores filogenéticas baseadas nesta distância. No caso de permutações com sinal, o problema pode ser resolvido em tempo linear, porém, no caso de permutações sem sinal o problema é mais complexo, já que foi demonstrado ser NP-difícil e com uma questão ainda em aberto: se é ou não NP completo; este foi o motivo pelo qual foram propostos diversos algoritmos de
aproximação e de computação evolucionária. Neste trabalho, é proposto um algoritmo genético(AG) padrão para resolver o problema de ordenação de permutações sem sinal. Este enfoque está baseado no método proposto por Auyeung e Abraham, que usa soluções exatas para o caso de permutações com sinal, para resolver a versão do problema com permutações sem sinal. Adicionalmente, foi proposto um algoritmo genético melhorado (hibrido), que usa uma heurística de eliminação de pontos de quebra em gerações iniciais. Diversos experimentos foram feitos tomando como entrada permutações gera- das aleatoriamente, escolhendo um elemento aleatório sobre um conjunto de números, ou aplicando reversões aleatórias sobre uma permutação ordenada. Ademais, foram usadas permutações de Gollan as quais sabemos que podem ser ordenadas usando n — 1 reversões, onde n é o comprimento da permutação. Desde que muitos enfoques de AG's usaram mecanismos de controle impreci- sos para validar a precisão das suas respostas, foi necessário um grande esforço para desenvolver uma algoritmo de aproximação confiável. Dando origem a um desenvolvimento teórico baseado no algoritmo de raio de aproximação 1.5 proposto por Christie, e sua posterior implementação. Os experimentos mostraram que ambos AG fornecem respostas que
são melhores do que aquelas fornecidas por métodos relacionados prévios, tanto como os que são fornecidos pelo algoritmo de raio de aproximação 1.5 corrigido. ______________________________________________________________________________ ABSTRACT
Resumo Ingles
Sorting permutations by reversals is one of the most challenging problems related to
the analysis of the evolutionary distance between organisms, whose results can be used in the construction of phylogenetic trees bases on this distance. In the case of signed permutations, the problem can be solved in linear time, however in the case of unsigned permutations the problem is more complex, since it was shown to be NP-hard and it is unknown whether it is NP-complete or not; this fact motivated the proposal of several approximation, and evolutionary computing algorithms. In this work, we propose genetic algorithms (GA) to solve the problem of sorting unsigned permutations. Initially, we propose a standard GA approach based on the method proposed by Auyeung and Abraham, which uses exact polynomial solutions for
the case of signed permutations, for solving the problem with unsigned permutations.
Further, we propose an improved genetic algorithm, which uses the heuristic of elimination of break points in early generations and then the standard approach.
Several experiments were made using as inputs permutations generated randomly by
choosing a random element over a set of numbers, and by applying random reversals over an sorted permutation. Also, was used Gollan permutations that it's well-known that can be sorted by n 1 reversals, where n is the length of the permutation. Since previous GA approaches have used imprecise control mechanisms for checking the accuracy of their answers, a great deal of e ort was necessary in order to develop a reliable approximate algorithm. This gave rise to a theoretical development based on the well-known Christie's 1.5 ratio approximation algorithm and its further implementation. Experiments showed that both AG approaches compute answers that are better than the ones computed by previous approaches as well as than the ones computed with the adjusted correct 1.5 approximation algorithm.
Departamento
Departamento de Ciência da Computação
Idioma
Português
Tipo de documento
Dissertação
Formato
application/pdf
Direitos de acesso
Acesso Aberto
Termo de licenca
A concessão da licença deste item refere-se ao termo de autorização impresso assinado pelo autor com as seguintes condições: Na qualidade de titular dos direitos de autor da publicação, autorizo a Universidade de Brasília e o IBICT a disponibilizar por meio dos sites www.bce.unb.br,www.ibict.br,http://hercules.vtls.com/cgi-bin/ndltd/chameleon?lng=pt&skin=ndltd sem ressarcimento dos direitos autorais, de acordo com a Lei nº 9610/98, o texto integral da obra disponibilizada, conforme permissões assinaladas, para fins de leitura, impressão e/ou download, a título de divulgação da produção científica brasileira, a partir desta data.
