[pt] O seqüenciamento por hibridação é uma alternativa
interessante para a tarefa
de seqüenciamento de DNA. Este método ainda está sendo
aperfeiçoado
e pode superar as técnicas utilizadas em termos de tempo e
custo. Uma
etapa crucial do método consiste em resolver um problema
combinatório
que pode ser formulado como um caso especial do problema do
caixeiro viajante
com coleta de prêmios. Neste trabalho, propõe-se uma nova
heurística
construtiva multi-partida para resolver este problema. Uma
estratégia de
aprendizado baseada em uma memória adaptativa e um
procedimento de
construção de vocabulário são utilizados para melhorar o
desempenho da
heurística multi-partida. A memória adaptativa é utilizada
para intensificar as construções de novas soluções com os
elementos que aparecem com
uma freqüência maior nas melhores soluções encontradas
anteriormente pela
heurística multi-partida. O procedimento de construção de
vocabulário consiste
em construir novas soluções através da combinação de partes
comuns a
boas soluções. Testes computacionais mostraram que estas
duas estratégias
aumentam significativamente o desempenho da heurística
multi-partida e
são particularmente indicadas para problemas de
escalonamento nos quais
as melhores soluções são na maioria dos casos formadas por
blocos de elementos
que aparecem juntos com muita freqüência. A heurística
proposta
supera os resultados dos melhores algoritmos encontrados na
literatura,
tanto em termos da qualidade das soluções encontradas, como
do tempo
de computação. / [en] Sequencing by hybridization is an attractive alternative
for DNA sequencing.
This novel method can be less time and cost consuming than
the techniques
applied nowadays. A very important step of this method is
to solve
a combinatorial problem formulated as a special case of the
prize-collecting
traveling salesman problem. In this work, we propose a new
multistart construtive
heuristic to solve this problem. A learning strategy based
on adaptive
memory and a vocabulary building procedure are used to
improve the
performance of the multistart heuristic. The adaptive
memory is used to
intensify the construction of new solutions with the
elements that appear
frequently in the best solutions previously found by the
multistart heuristic.
The objective of the vocabulary building procedure is to
construct new
solutions combining parts of good solutions. Computational
experiments
have shown that these two methods significantly improves
the performance
of the multistart heuristic and are particularly suitable
for scheduling problems
whose best solutions are in most cases built by blocks of
elements that
appear together very often. The proposed heuristic obtains
systematically
better solutions and is less time consuming than the best
algorithms found
in the literature.
| Identifer | oai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:6412 |
| Date | 04 May 2005 |
| Creators | ERALDO LUIS REZENDE FERNANDES |
| 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.0026 seconds