1 |
[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.
|
2 |
[en] AN EXPERIMENTAL INVESTIGATION OF PROBABILITY DISTRIBUTION OF SOLUTION TIME IN GRASP AND ITS APPLICATION ON THE ANALYSIS OF PARALLEL IMPLEMENTATIONS / [pt] UMA INVESTIGAÇÃO EXPERIMENTAL DA DISTRIBUIÇÃO DE PROBABILIDADE DO TEMPO DE SOLUCAO EM HEURISTICAS GRASP E SUA APLICAÇÃO NA ANALISE DE IMPLEMENTAÇÕES PARALELASRENATA MACHADO AIEX 13 June 2003 (has links)
[pt] GRASP (Greedy Randomized Adaptive Search Procedure)é uma
metaeurística de partidas múltiplas usada para obter
soluções para problemas de otimização combinatória.
Nesse
trabalho. A metaheurística GRASP tem sido usada para
obter
soluções de qualidade para muitos problemas de
otimização
combinatória. Nesse trabalho é proposta uma metodologia
para análise do comportamento da metaheurística GRASP.
Também são propostas estratégias de hibridização com o
religamento de caminhos. Essas estratégias foram
desenvolvidas para o problema de atribuição de três
índices
(AP3) e para o problema de escalonamento de tarefas
conhecido na literatura como job-shop schedulling
problem
(JSP) e são analisadas de acordo com a metodologia
proposta. A metodologia para análise do comportamento do
método GRASP pode ser usada para prever a partir da
versão
seqüencial do algoritmo, como a qualidade da solução do
algoritmo implementado em paralelo irá variar. Os
algoritmos GRASPs desenvolvidos para AP3 e para JSP
foram
paralelizados e os resultados são comparados aos
resultados
obtidos usando a metodologia proposta. / [en] GRASP (Greedy Randomized Adaptive Search Procedure) is a
multi-start metaheuristic for combinatorial optimization
problems. GRASP has been used to find quality solutions of
several combinatorial optimization problems. In this work
we describe a methodology for analysis of GRASP. Hybrid
strategies of GRASP with path relinking are also proposed.
These strategies are studied for the 3-index assignment
problem (AP3) and for the job-shop schedulling problem
(JSP) and are analyzed according to the methodology
proposed. The methodology for analysis of GRASP is used to
predict qualitatively how the quality of the solution
varies in a parallel independent GRASP, using the data of
the GRASP sequential version as input. The GRASPs for the
AP3 and for the JSP are parallelized and the computational
results are compared to the results obtained using the
methodology proposed.
|
Page generated in 0.0464 seconds