Título
[pt] HEURÍSTICAS HÍBRIDAS PARA O PROBLEMA DA FILOGENIA
Título
[en] HYBRID HEURISTICS FOR THE PHYLOGENY PROBLEM
Autor
[pt] DALESSANDRO SOARES VIANNA
Vocabulário
[pt] ALGORITMO GENETICO
Vocabulário
[pt] HEURISTICAS HIBRIDAS
Vocabulário
[pt] PROBLEMA DA FILOGENIA
Vocabulário
[pt] RECONEXAO POR CAMINHOS
Vocabulário
[en] GENETIC ALGORITHM
Vocabulário
[en] HYBRID HEURISTICS
Vocabulário
[en] PHYLOGENY PROBLEM
Resumo
[pt] Uma filogenia é uma árvore que relaciona unidades
taxonômicas, baseada na similaridade de seus conjuntos de
características. O problema da filogenia consiste em
encontrar uma filogenia com o número mínimo de passos
evolutivos. O principal objetivo deste trabalho é
desenvolver heurísticas híbridas para este problema. Duas
estratégias são propostas. A primeira combina a
metaheurística GRASP baseada em uma nova estrutura de
vizinhança (k-SPR) proposta neste trabalho com um
procedimento VND de busca local. A segunda estratégia
híbrida combina algoritmos genéticos com uma estratégia de
cruzamento inovadora, a qual é uma extensão da técnica
de intensificação denominada reconexão por caminhos que foi
originalmente aplicada no contexto de outras
metaheurísticas, tais como busca tabu e GRASP. Os
experimentos computacionais realizados sobre instâncias
geradas aleatoriamente e instâncias da literatura
científica mostram que os novos algoritmos são bastante
robustos e que superaram os outros algoritmos existentes na
literatura em termos de qualidade de solução e tempos
computacionais obtidos.
Resumo
[en] A phylogeny is a tree that relates taxonomic units, based
on their similarities over a set of characters. The
phylogeny problem consists in finding a phylogeny with the
minimum number of evolutionary steps. The main goal
of this work is to develop hybrid heuristics for this
problem. Two strategies are proposed. The first combines
the GRASP metaheuristic using a new neighborhood structure
(k-SPR) proposed in this work with a VND local search
procedure. The second hybrid strategy combines genetic
algorithms with an innovative optimized crossover strategy
which is an extension of the path-relinking intensification
technique originally applied in the context of other
metaheuristics such as tabu search and GRASP. Computational
results on randomly generated and benchmark instances are
reported, showing that the new heuristics are quite robust
and outperform the others algorithms in the literature in
terms of solution quality and computational time.
Orientador(es)
CELSO DA CRUZ CARNEIRO RIBEIRO
Banca
EMMANUEL PISECES LOPES PASSOS
Banca
SERGIO LIFSCHITZ
Banca
CELSO DA CRUZ CARNEIRO RIBEIRO
Banca
LUIZ SATORU OCHI
Banca
NAIR MARIA MAIA DE ABREU
Banca
LUIZ FERNANDO BESSA SEIBEL
Banca
NALVO FRANCO ALMEIDA JUNIOR
Catalogação
2004-07-13
Apresentação
2004-02-27
Tipo
[pt] TEXTO
Formato
application/pdf
Formato
application/pdf
Formato
application/pdf
Formato
application/pdf
Formato
application/pdf
Formato
application/pdf
Formato
application/pdf
Idioma(s)
PORTUGUÊS
Referência [pt]
https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=5178@1
Referência [en]
https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=5178@2
Referência DOI
https://doi.org/10.17771/PUCRio.acad.5178
Arquivos do conteúdo
CAPA, AGRADECIMENTOS, RESUMO, ABSTRACT, SUMÁRIO E LISTAS PDF CAPÍTULO 1 PDF CAPÍTULO 2 PDF CAPÍTULO 3 PDF CAPÍTULO 4 PDF CAPÍTULO 5 PDF BIBLIOGRAFIA PDF