[pt] HEURÍSTICAS HÍBRIDAS PARA O PROBLEMA DA FILOGENIA
[en] HYBRID HEURISTICS FOR THE PHYLOGENY PROBLEM
| dc.contributor | CELSO DA CRUZ CARNEIRO RIBEIRO | |
| dc.contributor | CELSO DA CRUZ CARNEIRO RIBEIRO | |
| dc.creator | DALESSANDRO SOARES VIANNA | |
| dc.date | 2004-07-13 | |
| dc.date.accessioned | 2022-09-21T21:43:56Z | |
| dc.date.available | 2022-09-21T21:43:56Z | |
| dc.identifier | https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=5178@1 | |
| dc.identifier | https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=5178@2 | |
| dc.identifier | http://doi.org/10.17771/PUCRio.acad.5178 | |
| dc.identifier.uri | https://hdl.handle.net/20.500.12032/42764 | |
| dc.description | [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. | |
| dc.description | [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. | |
| dc.language | pt | |
| dc.publisher | MAXWELL | |
| dc.subject | [pt] ALGORITMO GENETICO | |
| dc.subject | [pt] HEURISTICAS HIBRIDAS | |
| dc.subject | [pt] PROBLEMA DA FILOGENIA | |
| dc.subject | [pt] RECONEXAO POR CAMINHOS | |
| dc.subject | [en] GENETIC ALGORITHM | |
| dc.subject | [en] HYBRID HEURISTICS | |
| dc.subject | [en] PHYLOGENY PROBLEM | |
| dc.title | [pt] HEURÍSTICAS HÍBRIDAS PARA O PROBLEMA DA FILOGENIA | |
| dc.title | [en] HYBRID HEURISTICS FOR THE PHYLOGENY PROBLEM | |
| dc.type | TEXTO |
Files in this item
| Files | Size | Format | View |
|---|---|---|---|
|
There are no files associated with this item. |
|||