Local search-based heuristics for the multiobjective multidimensional knapsack problem
Vianna, Dalessandro Soares; Vianna, Marcilene de Fátima D.
http://dx.doi.org/10.1590/S0103-65132012005000081
Prod, vol.23, n3, p.478-487, 2013
Abstract
In real optimization problems it is generally desirable to optimize more than one performance criterion (or objective) at the same time. The goal of the multiobjective combinatorial optimization (MOCO) is to optimize simultaneously r > 1 objectives. As in the single-objective case, the use of heuristic/metaheuristic techniques seems to be the most promising approach to MOCO problems because of their efficiency, generality and relative simplicity of implementation. In this work, we develop algorithms based on Greedy Randomized Adaptive Search Procedure (GRASP) and Iterated Local Search (ILS) metaheuristics for the multiobjective knapsack problem. Computational experiments on benchmark instances show that the proposed algorithms are very robust and outperform other heuristics in terms of solution quality and running times.
Keywords
Multiobjective multidimensional knapsack problem. Multiobjective combinatorial optimization. GRASP. ILS.
References
ALVES, M. J.; ALMEIDA, M. M. A multiobjective Tchebycheff based genetic algorithm for the multidimensional knapsack problem. Computers & Operations Research, v. 34, p. 3458-3470, 2007. http://dx.doi.org/10.1016/j.cor.2006.02.008
ARROYO, J. E. C.; VIEIRA, P. S.; VIANNA, D. S. A GRASP algorithm for the multi-criteria minimum spanning tree problem. Annals of Operations Research, v. 159, p. 125-133, 2008. http://dx.doi.org/10.1007/s10479-007-0263-4
COELLO, C. A. C. An updated survey of GA-based multiobjective optimization techniques. ACM Computing Surveys, v. 32, n. 2, p. 109-143, 2000. http://dx.doi.org/10.1145/358923.358929
CZYZAK, P.; JASZKIEWICZ, A. Pareto simulated annealing - a metaheuristic technique for multiple objective combinatorial optimization. Journal of Multi-Criteria Decision Analysis, v. 7, p. 34-47, 1998. http://dx.doi.org/10.1002/(SICI)1099-1360(199801)7:1<34::AID-MCDA161>3.0.CO;2-6
DEB, K. Multi-objective optimization using evolutionary algorithms. England: John Wiley & Sons Ltd., 2004.
EHRGOTT, M.; GANDIBLEUX, X. A survey and annotated bibliography of multiobjective combinatorial optimization. OR Spektrum, v. 22, p. 425-460, 2000. http://dx.doi.org/10.1007/s002910000046
EPPRECHT, E. K.; LEIRAS, A. Otimização conjunta de gráficos de X-barra-S ou X-barra-R: um procedimento de fácil implementação. Produção, v. 17, n. 3, p. 520-535, 2007.
FEO, T. A.; RESENDE, M. G. C. Greedy randomized adaptive search procedures. Journal of Global Optimization, v. 6, p. 109-133, 1995. http://dx.doi.org/10.1007/BF01096763
GANDIBLEUX, X.; FRÉVILLE, A. Tabu search based procedure for solving the 0-1 multiobjective knapsack problem: The two objectives case. Journal of Heuristics, v. 6, p. 361-383, 2000. http://dx.doi.org/10.1023/A:1009682532542
HANSEN, P. Tabu search for multiobjective optimization: MOTS. Technical Report. Technical University of Denmark. In: INTERNATIONAL CONFERENCE ON MULTIPLE CRITERIA DECISION MAKING, 13., 1997, Cape Town. Proceedings... Cape Town, 1997.
JASKIEWICZ, A. On the performance of multiple objective genetic local search on the 0/1 knapsack problem: A comparative experiment. IEEE Transaction on Evolutionary Computation, v. 6, n. 4, p. 402-412, 2002. http://dx.doi.org/10.1109/TEVC.2002.802873
JONES, D. F.; MIRRAZAVI, S. K.; TAMIZ, M. Multi-objective metaheuristics: An overview of the current state-of-art. European Journal of Operational Research, v. 137, p. 1-19, 2002. http://dx.doi.org/10.1016/S0377-2217(01)00123-0
LINS, I. D.; DROGUETT, E. L. Multiobjective optimization of availability and cost in repairable systems design via genetic algorithms and discrete event simulation. Pesquisa Operacional, v. 29, n. 1, p. 43-66, 2009. http://dx.doi.org/10.1590/S0101-74382009000100003
LOURENÇO, H. R.; MARTIN, O. C.; STÜTZLE, T. Iterated local search. In: GLOVER, F.; KOCHENBERGER, G. (Eds.). Handbook of Metaheuristics. Kluwer, 2002. p. 321-353.
MAURI, G. R.; LORENA, L. A. N. Uma nova abordagem para o problema dial-a-ride. Produção, v. 19, n. 1, p. 41-54, 2009. http://dx.doi.org/10.1590/S0103-65132009000100004
MURATA, T.; ISHIBUCHI, H.; GEN, M. Specification of genetic Search directions in cellular multi-objective genetic algorithms. In: INTERNATIONAL CONFERENCE ON EVOLUTIONARY MULTI-CRITERION OPTIMIZATION, 2001, Zurich. Proceedings... Zurich: Springer, 2001. v. 1, p. 82-95.
RESENDE, M. G. C.; RIBEIRO, C. C. Greedy randomized adaptive search procedures. In: GLOVER, F.; KOCHENBERGER, G. (Eds.). Handbook of Metaheuristics. Boston: Kluwer, 2003. p. 219-249.
RIBEIRO, C. C. et al. A hybrid heuristic for a multi-objective real-life car sequencing problem with painting and assembly line constraints. European Journal of Operational Research, v. 191, p. 981-992, 2008. http://dx.doi.org/10.1016/j.ejor.2007.04.034
ULUNGU, E. L.; TEGHEM, J. The two phases method: An efficient procedure to solve bi-objective combinatorial optimization problems. Foundations of Computing and Decision Sciences, v. 20, n. 2, p. 149-165, 1995.
ULUNGU, E. L.; TEGHEM, J.; OST, C. Efficiency of interactive multi-objective simulated annealing through a case study. Journal of the Operational Research Society, v. 49, p. 1044-1050, 1998.
VAN VELDHUIZEN D. A.; LAMONT, G. B. Multiobjective evolutionary algorithms: Analyzing the state-of art. Evolutionary Computation, v. 8, n. 2, p. 125-147, 2000. http://dx.doi.org/10.1162/106365600568158
VIANNA, D. S. et al. Parallel strategies for a multi-criteria GRASP algorithm. Produção, v. 17, p. 1-12, 2007. http://dx.doi.org/10.1590/S0103-65132007000100006
VISÉE, M. et al. Two-Phases Method and Branch and Bound Procedures to solve the Bi-objectives knapsack Problem. Journal of Global Optimization, v. 12, p. 139-155, 1998. http://dx.doi.org/10.1023/A:1008258310679
ZITZLER, E.; THIELE, L. Multiobjective evolutionary algorithms: A comparative case study and the strength pareto approach. IEEE Transactions on Evolutionary Computation, v. 3, n. 4, p. 257-271, 1999. http://dx.doi.org/10.1109/4235.797969
ZITZLER, E.; LAUMANNS, M.; THIELE, L. SPEA2: Improving the Strength Pareto Evolutionary Algorithm. In: GIANNAKOGLOU, K. et al. (Eds.). Evolutionary Methods for Design, Optimization and Control with Applications to Industrial Problems. Athens, 2002. p. 95-100.
Facebook
Google+
Twitter
LinkedIn
Mendeley
StumbleUpon
CiteULike
Reddit
Email