Sign In
Register
eISSN:2278-5299

International Journal of Latest Research in Science and Technology

DOI:10.29111/ijlrst   ISRA Impact Factor:3.35

A News Letter Sign UP!
A MEMORY-BASED GRASP HEURISTIC FOR THE MULTIOBJECTIVE MULTIDIMENSIONAL KNAPSACK PROBLEM

Research Paper Open Access

International Journal of Latest Research in Science and Technology Vol.3 Issue 4, pp 186-194,Year 2014

A MEMORY-BASED GRASP HEURISTIC FOR THE MULTIOBJECTIVE MULTIDIMENSIONAL KNAPSACK PROBLEM

Dalessandro Soares Vianna,Ferm?n Alfredo Tang Montan?,Edwin Benito Mitacc Meza, Carlos Bazilio Martins

Correspondence should be addressed to :

Received : 26 June 2014; Accepted : 01 July 2014 ; Published : 31 August 2014

Share
Download 125
View 179
Article No. 10375
Abstract

In real optimization problems is generally desirable to optimize more than one performance criterion (or objective) at the same time. The goal of the multi-objective combinatorial optimization (MOCO) is to optimize simultaneously r > 1 objectives. We developed a GRASP algorithm that incorporates a memory-based approach for solving the multiobjective multidimensional knapsack problem. There are, in the scientific literature, some memory-based GRASP algorithms for mono-objective problems, however it was not found any memory-based GRASP algorithm for multiobjective problems. Computational experiments on benchmark instances show that the proposed algorithm is very robust and outperforms other heuristics in terms of solution quality and running times.

Key Words   
multiobjective multidimensional knapsack problem; multiobjective combinatorial optimization; GRASP.

Copyright
References
  1. Alves M.J., Almeida M. 2007. MOTGA: A multiobjective Tchebycheff based genetic algorithm for the multidimensional knapsack problem. Computers & Operations Research, 34: 3458–3470.
  2. Ahmadi S., Osman I.H. 2005. Greedy random adaptive memory programming search for the capacitated clustering problem. European Journal of Operational Research, 162: 30-44.
  3. Aiex R.M., Resende M.G.C., Ribeiro C.C. 2002. Probability distribution of solution time in GRASP: An experimental investigation. Journal of Heuristics, 8: 343-373.
  4. Aiex R.M., Resende M.G.C., Ribeiro C.C. 2007. TTTPLOTS: A perl program to create time-to-target plots. Optimization Letters, 1: 355-366.
  5. Albuquerque, L.L., Almeida, A.T., Cavalcante, C.A.V. 2009. Aplicabilidade da programação matemática multiobjetivo no planejamento da expansão de longo prazo da geração no Brasil (in Portuguese). Pesquisa Operacional, 29(1): 153-177.
  6. Armentano V.A., França Filho M.F. 2007. Minimizing total tardiness in parallel machine scheduling with setup times: An adaptive memory-based GRASP approach. European Journal of Operational Research, 183: 100-114.
  7. Coello C.A.C. 2000. An updated survey of GA-based multiobjective optimization techniques. ACM Computing Surveys, 32(2): 109–143.
  8. Czyzak P., Jaszkiewicz A. 1998. Pareto simulated annealing – a metaheuristic technique for multiple objective combinatorial optimization. Journal of Multi-Criteria Decision Analysis, 7: 34–47.
  9. Deb K. 2004. Multi-objective optimization using evolutionary algorithms. England: John Wiley & Sons Ltd.
  10. Ehrgott M., Gandibleux X. 2000. A survey and annotated bibliography of multiobjective combinatorial optimization. OR Spektrum, 22: 425–460.
  11. Fernandes E.R., Ribeiro C.C. 2005. A multistart constructive heuristic for sequencing by hybridization using adaptive memory. Electronic Notes in Discrete Mathematics, 19: 41-47.
  12. Feo T.A., Resende M.G.C. 1995. Greedy randomized adaptive search procedures. Journal of Global Optimization, 6: 109–133.
  13. Feo T.A., Resende M.G.C, Smith S.H. 1994. A greedy randomized adaptive search procedure for maximum independent set. Operations Research, 42: 860-878.
  14. Fiehler, K., Bannert, M.M., Bischoff, M., Blecker, C., Stark, R., Vaitl, D., Franz, V.H. & Rösler, F. 2010. Working memory maintenance of grasp-target information in the human posterior parietal cortex. NeuroImage, 1: 1–11.
  15. Fleurent C., Glover F. 1999. Improved constructive multistart strategies for the quadratic assignment problem. INFORMS Journal on Computing, 11: 198-204.
  16. Gandibleux X., Fréville A. 2000. Tabu search based procedure for solving the 0-1 multiobjective knapsack problem: The two objectives case. Journal of Heuristics, 6: 361–383.
  17. Gandibleux X., Ehrgott M. 2005. 1984–2004 – 20 Years of Multiobjective Metaheuristics. But What About the Solution of Combinatorial Problems with Multiple Objectives?. In: Coello AA, Aguirre AH, Zitzler E (Eds.). Evolutionary Multi-Criterion Optimization. Berlin, Springer: 33–46.
  18. Hansen P. 1997. Tabu search for multiobjective optimization: MOTS. Technical Report. Technical University of Denmark. Paper presented at The 13th International Conference on Multiple Criteria Decision Making. Cape Town, South Africa, 1997.
  19. Hoos H.H., Stützle T. On the empirical evaluation of Las Vegas algorithms â-Position paper. Technical report, Computer Science Department, University of British Columbia, 1998.
  20. Hoss H.H., Stützle T. 1998. Evaluation Las Vegas algorithms - Pitfalls and remedies. In: Proceedings of the 14th Conference on Uncertainty in Artificial Intelligence, p.238-245.
  21. Jaskiewicz A. 2002. On the performance of multiple objective genetic local search on the 0/1 knapsack problem: A comparative experiment. IEEE Transaction on Evolutionary Computation, 6(4): 402–412.
  22. Jones D.F., Mirrazavi S.K., Tamiz M. 2002. Multi-objective metaheuristics: An overview of the current state-of-art. European Journal of Operational Research, 137: 1–19.
  23. Lourenço H.R., Pinto J., Portugal R. 1998. Metaheuristics for The Bus-Driver Scheduling Problem. Economics Working Papers 304, Department of Economics and Business, Universitat Pompeu Fabra.
  24. Lins I.D., Droguett E.L. 2009. Multiobjective optimization of availability and cost in repairable systems design via genetic algorithms and discrete event simulation. Pesquisa Operacional, 29(1): 43-66.
  25. Murata T., Ishibuchi H., Gen M. 2001. Specification of genetic Search directions in cellular multi-objective genetic algorithms. In: Zitzler E, Deb K, Thiele L, Coello CAC, Corne D (eds.). Evolutionary Multi-Criterion optimization, First International Conference, EMO. Lecture Notes in Computer Science. Zurich: Springer, 1: 82–95.
  26. Murphey R., Pardalos P.M., Resende M. 2000. Frequency Assignment Problems. Handbook of Combinatorial Optimization. Kluwer: 295–377.
  27. Resende M.G.C., Ribeiro C.C. 2003. Greedy randomized adaptive search procedures. In: Glover F, Kochenberger G (eds.). Handbook of Metaheuristics. Boston, Kluwer: 219–249.
  28. Resende M.G.C., Ribeiro C.C. 2005. GRASP with path-relinking: Recent advances and applications. In: Ibaraki T, Nonobe K, Yagiura M (eds.). Metaheuristics: Progress as Real Problem Solvers. Boston, Kluwer: 29-63.
  29. [29] Ribeiro C.C., Rosseti I. 2007. Efficient parallel cooperative implementations of GRASP heuristics. Parallel Computing, 33: 21-35.
  30. Ulungu E.L., Teghem J. 1995. The two phases method: An efficient procedure to solve bi-objective combinatorial optimization problems. Foundations of Computing and Decision Sciences, 20(2): 149–165.
  31. Ulungu E.L., Teghem J., Ost C. 1998. Efficiency of interactive multi-objective simulated annealing through a case study. Journal of the Operational Research Society, bf 49: 1044–1050.
  32. Van Veldhuizen D.A., Lamont G.B. 2000. Multiobjective evolutionary algorithms: Analyzing the state-of art. Evolutionary Computation, 8(2): 125–147.
  33. Vianna D.S., Arroyo J.E.C. 2004. A GRASP algorithm for the multi-objective knapsack problem. In: XXIV International Conference of the Chilean Computer Science Society (XXIV SCCC). Washington: IEEE Computer Society: 69–75.
  34. Vianna D.S., Dianin, M.F.V. 2013. Local search-based heuristics for the multiobjective multidimensional knapsack problem. Production Journal, 23(3): 478-487.
  35. Visée M., Teghem J., Pirlot M., Ulungu E.L. 1998. Two-Phases Method and Branch and Bound Procedures to solve the Bi-objectives knapsack Problem. Journal of Global Optimization, 12: 139–155.
  36. Zitzler E., Thiele L. 1999. Multiobjective evolutionary algorithms: A comparative case study and the strength pareto approach. IEEE Transactions on Evolutionary Computation, 3(4): 257–271.
  37. Zitzler E., Laumanns M., Thiele L. 2002. SPEA2: Improving the Strength Pareto Evolutionary Algorithm. In: Giannakoglou K, Tsahalis D, Periaux J, Papailou P, Fogarty T (eds.). EUROGEN 2001, Evolutionary Methods for Design, Optimization and Control with Applications to Industrial Problems. Athens, Greece: 95–100.
To cite this article

Dalessandro Soares Vianna,Ferm?n Alfredo Tang Montan?,Edwin Benito Mitacc Meza, Carlos Bazilio Martins , " A Memory-based Grasp Heuristic For The Multiobjective Multidimensional Knapsack Problem ", International Journal of Latest Research in Science and Technology . Vol. 3, Issue 4, pp 186-194 , 2014

Responsive image

MNK Publication was founded in 2012 to upholder revolutionary ideas that would advance the research and practice of business and management. Today, we comply with to advance fresh thinking in latest scientific fields where we think we can make a real difference and growth now also including medical and social care, education,management and engineering.

Responsive image

We offers several opportunities for partnership and tie-up with individual, corporate and organizational level. We are working on the open access platform. Editors, authors, readers, librarians and conference organizer can work together. We are giving open opportunities to all. Our team is always willing to work and collaborate to promote open access publication.

Responsive image

Our Journals provide one of the strongest International open access platform for research communities. Our conference proceeding services provide conference organizers a privileged platform for publishing extended conference papers as journal publications. It is deliberated to disseminate scientific research and to establish long term International collaborations and partnerships with academic communities and conference organizers.