1 |
[en] HYBRID HEURISTICS FOR THE PHYLOGENY PROBLEM / [pt] HEURÍSTICAS HÍBRIDAS PARA O PROBLEMA DA FILOGENIADALESSANDRO SOARES VIANNA 13 July 2004 (has links)
[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.
|
2 |
[en] SEQUENTIAL AND PARALLEL STRATEGIES OF GRASP WITH PATH-RELINKING FOR THE 2-PATH NETWORK DESIGN PROBLEM / [pt] ESTRATÉGIAS SEQÜENCIAIS E PARALELAS DE GRASP COM RECONEXÃO POR CAMINHOS PARA O PROBLEMA DE SÍNTESE DE REDES A 2-CAMINHOSISABEL CRISTINA MELLO ROSSETI 09 January 2004 (has links)
[pt] Seja G= (V, E) um grafo não-orientado com custos não-
negativos em suas arestas e D um conjunto de pares
origem -
destino. Um 2-caminho entre nós (s,t)é um caminho de s a
t
formado por , no máximo, 2 arestas. O problema de síntese
de redes com 2-caminhos (2PNDP) consiste em encontrar um
subconjunto de arestas com custo mínimo que contenha um 2-
caminho entre as extremidades dea cada para origem-
destino
pertencente a D. Apicações deste problema encontram-se no
projeto de redes de comunicação, onde caminhos com poucas
arestas são desejáveis para garantir alta confiabilidade
e
pequenos atrasos. A metaheurística GRASP é um processo
multipartida para resolver problemas combinatórios, cujas
iterações consistem de duas fases, uma fase de construção
e
outra de busca local. O algoritmo retorna a melhor
solução
encontrada depois de um número determinado de
iterações.Aplica-se a técnica de reconexão por caminhos
ao
final de cada iteração GRASP para melhorar a qualidade
das
soluções. Implementações paralelas de metaheurística são
muito robustas. A maior parte das implementações
paralelas
da metaheurística GRASP segue uma estratégia do tipo
independente , baseada na distribuição balanceada das
iterações pelos processadores. No caso de estratégias
colaboradtivas, os processadores trocam e compartilham
informações coletadas ao longo da trajetória que cada um
deles investiga. Neta tese são desenvolvidas heurísticas
seqüenciais e paralelas para 2PNDP. São analisadas
variantes e combinações de GRASP e reconexão por
caminhos , comparando-se os resultados obtidos pelos
algoritmos descritos na literatura. Heurísticas GRASP
paralelas com reconexão por caminhos são avaliadas e
comparadas para verificar qual o papel que a colaboração
entre os processadores desempenha na qualidade das
soluções
e nos tempos de processamento. Procura-se também estudar
a
melhor maneira de desenvolver implementações paralelas ,
para se utilizar da melhor forma possível os recursos
computacionais e reduzir conflitos de memória e
comunicação. / [en] Let G = ( V, E) be a connected undirected graph , where V
is the set of nodes and E denotes the set of edges. A 2-
path between nodes (s,t)is a sequence of a most two edges
connecting them. Given a non-negative weight function
associated with edges of G and a set D of origin-
destination pairs of nodes, the 2-path network design
problem (2PNDP) consists in finding a minimum weighted
subset of edges containing a 2-path between the extremities
of every origin-destination pair in D. Applications can be
found in the design of communication networks , in which
paths with few edges are sought to enforce high reliability
and small delays. The GRASP metaheuristic is a multistart
process , in which each iteration consists of two phases :
construction and local search. The best solution found
after a fixed number of iterations is returned. Path-
relinking is applied as an attempt to improve the solutions
found at the of each GRASP iteration. Parallel
implementations of metaheuistics ara very robust. Typical
parallelizations of GRASP correspond to multiple-walk
independent-thread strategies, based on the balanced
distribuiton of the iterations over the processors. In the
case of multiple-walk cooperative-thread strategies, the
processors exchange and share information collected along
the trajectories that they investigate. In this thesis,
sequential and parallel heuristics are developed for 2PNDP.
Variants and combinations of GRASP with path-relinking are
analysed by comparing the results of the proposed
algorithms with those obtained by others algoritms
described in the literature. Parallel GRASP with
pathrelinking heuristcs are compared to investigate the
influence of the cooperation among processors in terms of
solution quality and processing time. We also explore
different strategies to optimize the parallel
implementations, to make better use of the computational
resources and to reduce communication and memory
conflicts.
|
Page generated in 0.0396 seconds