[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. / [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.
| Identifer | oai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:5178 |
| Date | 13 July 2004 |
| Creators | DALESSANDRO SOARES VIANNA |
| Contributors | CELSO DA CRUZ CARNEIRO RIBEIRO, CELSO DA CRUZ CARNEIRO RIBEIRO |
| Publisher | MAXWELL |
| Source Sets | PUC Rio |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | TEXTO |
Page generated in 0.002 seconds