Parallel strategies for a multi-criteria GRASP algorithm
Estratégias de paralelização para um algoritmo GRASP multicritério
Vianna, Dalessandro Soares; Arroyo, José Elias C.; Vieira, Pedro Sampaio; Azaredo, Thiago Ribeiro de
http://dx.doi.org/10.1590/S0103-65132007000100006
Prod, vol.17, n1, p.84-93, 2007
Resumo
This paper proposes different strategies of parallelizing a multi-criteria GRASP (Greedy Randomized Adaptive Search Problem) algorithm. The parallel GRASP algorithm is applied to the multi-criteria minimum spanning tree problem, which is NP-hard. In this problem, a vector of costs is defined for each edge of the graph and the goal is to find all the efficient or Pareto optimal spanning trees (Pareto-optimal solutions). Each process finds a subset of efficient solutions. These subsets are joined using different strategies to obtain the final set of efficient solutions.
The multi-criteria GRASP algorithm with the different parallel strategies are tested on complete graphs with n = 20, 30 and 50 nodes and r = 2 and 3 criteria. The computational results show that the proposed parallel algorithms reduce the execution time and the results obtained by the sequential version were improved.
Palavras-chave
Parallel GRASP algorithm, multi-criteria combinatorial optimization, minimum spanning tree
Abstract
Este artigo propõe diferentes estratégias de paralelização de um algoritmo GRASP (Greedy Randomized Adaptive Search Procedure) multicritério. O algoritmo paralelo proposto é aplicado ao problema da árvore geradora mínima multicritério, que é NP-difícil. Neste problema, um vetor de custos é definido para cada aresta do grafo e o objetivo é encontrar as árvores geradoras eficientes (soluções Pareto-ótimas). Cada processo encontra um subconjunto de soluções eficientes. Estes subconjuntos são reunidos usando diferentes estratégias para obter o conjunto final de soluções eficientes.
O algoritmo proposto é testado em grafos completos com n = 20, 30 e 50 nós e r = 2 e 3 critérios. Os resultados computacionais mostram que a proposta de se paralelizar o algoritmo reduz o tempo de execução e os resultados obtidos pela versão seqüencial foram melhorados.
Keywords
Algoritmo GRASP paralelo, otimização combinatória multicritério, árvore geradora mínima
References
ARROYO, J. E. C., VIEIRA, P. S. & VIANNA, D. S. (2005). A GRASP algorithm for the multi-criteria minimum spanning tree problem. In: Second Multidisciplinary Conference on Scheduling: Theory and Applications, Nova York, p. 1-11.
DRUMMOND, L. M. A., OCHI, L. S. & VIANNA, D. S. (2001). An asynchronous parallel metaheuristic for the period vehicle routing problem. Future generation computer systems, 17, p. 79-386.
EHRGOTT, M. & KLAMROTH, K. (1997). Connectedness of efficient solutions in multiple criteria combinatorial optimization. European Journal Operations Research, v. 97, p. 159-166.
EHRGOTT, M. & GANDIBLEUX, X. (2000). A survey and annotated bibliography of multiobjective combinatorial optimization. OR Spektrum, 22, p. 25-460.
FEO, T. A. & RESENDE, M. G. C. (1995). GREedy randomized adaptive search procedures. Global Optimization, 6, p. 109-133.
GLOVER, F. & LAGUNA, M. (1997). Tabu search. Kluwer Academic Publishers.
HAMACHER, H. W. & RUHE, G. (1994). On spanning tree problems with multiple objectives. Annals of Operations Research, 52, p. 209-230.
HOLLAND, J. H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press.
JONES, D. F., MIRRAZAVI, S. K. & TAMIZ, M. (2002). Multi-objective metaheuristics: An overview of the current state-of-art. European Journal Operations Research, 137, p. 1-19.
KIRKPATRICK, S., GELLAT JR., C.D. & VECCHI, M. P. (1983). Optimization by Simulated Annealing. Science, 220, p. 671-680.
KRISHNAMOORTH, M., ERNST, A. T. & SHARAIHA, Y. M. Comparison of Algorithms for the Degree Constrained Minimum Spanning Tree. Journal of Heuristics, v. 7, p. 587-611, 2001.
KRUSKAL, J. B. On the shortest spanning tree of graph and the traveling salesman problem. Proceedings of the American Mathematical Society, v. 7, p. 48-50, 1956.
KNOWLES, J. D. Local search and hybrid evolutionary algorithms for Pareto optimization. Thesis of Doctorate, University of Reading, UK, 2002.
MOON, J. W. Various Proofs of Cayley's Formula for Counting Trees. In: A Seminar on Graph Theory [edited by F. Harary], New York: Holt, Rinehart and Winston, p. 70-78, 1967.
MURATA, T., ISHIBUCHI, H. & GEN, M. (2001). Specification of genetic Search directions in cellular multi-objective genetic algorithms. Evolutionary Multi-Criterion optimization, EMO. LNCS, 1993, p. 82-95.
OCHI, L. S., VIANNA, D. S., DRUMMOND, L. M. A. & VICTOR, A. O. A parallel evolutionary algorithm for the vehicle routing problem with heterogeneous fleet. Future Generation Computer Systems, 14, p. 285-292, 1999.
RAMOS, R. M., ALONSO, S., SICÍLIA, J. & GONZÁLES, C. (1998). The problem of the optimal biobjective spanning tree problem. European Journal Operations Research, v. 111, p. 617-628.
VIANNA, D. S., OCHI, L. S. & DRUMMOND L. M. A. A parallel hybrid evolutionary metaheuristic for the period vehicle routing problem. Lecture notes in computer science, 1586, p. 183-191, 1999.
VIANNA, D. S. & ARROYO, J. E. C. A GRASP algorithm for the multi-objective knapsack problem. In: XIV International Conference of the Chilean Computer Science Society, Arica, IEEE CS Press, p. 69-75, 2004.
Zhou, G. & Gen, M. GEnetic algorithm approach on Multi-criteria minimum spanning tree problem. European Journal Operations Research, v. 114, p. 141-152, 1999.
Facebook
Google+
Twitter
LinkedIn
Mendeley
StumbleUpon
CiteULike
Reddit
Email