×

A new discrete electromagnetism-based meta-heuristic for solving the multidimensional knapsack problem using genetic operators. (English) Zbl 1256.90039

Summary: The standard electromagnetism-like mechanism (SEM) is one of the swarm-based optimization methods which is examined in this paper. The SEM works based on the charges in electrons and hence its operators have been especially designed for continuous space problems. Although the SEM was successfully applied to the standard optimization problems, it was not that notable when it came to tackling discrete space problems. This shortcoming was obvious when the SEM was applied to some standard discrete problems such as Travelling Salesman Problem, Nurse Scheduling Problem, etc. In this paper, a modified SEM, called discrete electromagnetism-like mechanism, is proposed which utilizes genetic algorithm (GA) operators to work in discrete spaces. In fact, the vector calculations (which are at the heart of the SEM) in the SEM are replaced by specific types of GA operators to determine the effects that particles have on one another. Also, a new operator based on the principles of quantum mechanics is proposed which further improves the performance of the method. In our experiments, the proposed algorithm is applied to a well-studied discrete space problem, called multidimensional knapsack problem (MKP). All tests are done on standard problems of the MKP and the results are reported and compared with several stochastic population-based optimization methods. Experiments showed that the proposed algorithm not only found comparable (and even better in some cases) solutions for the standard problems of the MKP, but also took much less computational time (75% improvement in average in comparison to other methods).

MSC:

90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming

Software:

MOTGA; OR-Library
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alaya I, Solnon G, Ghedira K (2004) Ant algorithm for the multidimensional knapsack problem. International conference on bio-inspired optimization methods and their applications. BIOMA 2004, pp 63–72
[2] Alves M, Almeida M (2008) MOTGA: a multiobjective Tchebycheff based genetic algorithm for the multidimensional knapsack problem. Comput Oper Res 34(11):3458–3470 · Zbl 1127.90059
[3] Angelelli E, Mansini R, Speranza MG (2010) Kernel search: a general heuristic for the multi-dimensional knapsack problem. Comput Oper Res 37:2017–2026 · Zbl 1188.90207 · doi:10.1016/j.cor.2010.02.002
[4] Beasley JE (1990) OR-Library: distributing test problems by electronic mail. J Oper Res Soc 41(11):1069–1072
[5] Birbil S, Fang SH (2003) An electromagnetism-like mechanism for global optimization. J Glob Optim, Kluwer, vol 25, pp 263–282 · Zbl 1047.90045
[6] Boussier S, Vasquez M, Vimont Y, Hanafi S, Michelon P (2010) A multi-level search strategy for the 01 Multidimensional Knapsack. Discret Appl Math 158(2):97–109 · Zbl 1185.90170 · doi:10.1016/j.dam.2009.08.007
[7] Chang PC, Chen SH, Fan CY (2009) A hybrid electromagnetism-like algorithm for single machine scheduling problem. Expert Syst Appl 36:1259–1267 · doi:10.1016/j.eswa.2007.11.050
[8] Chu P, Beasley JE (1998) A genetic algorithm for the multidimensional knapsack problem. J Heur 4:63–86 · Zbl 0913.90218 · doi:10.1023/A:1009642405419
[9] Cotta C, Troya JM (1998) ”A hybrid genetic algorithm for the 0-1 Multidimensional knapsack problem”, Artificial Neural Nets and Genetic Algorithms, Springer, New York, pp 250–254
[10] Debels D, Vanhoucke M (2004) An electromagnetism meta-heuristic for the resource-constrained project scheduling problem. Published in Lecture notes on Computer Science, vol 3871, pp 259–270
[11] Debels D, Vanhoucke M (2006) ”The electromagnetism meta-heuristic applied to the resource-constrained project scheduling problem”, Lecture notes in Computer Science, ISSN: 0302-9743, pp 259–270
[12] Fidanova S (2002) Evolutionary algorithm for multidimensional knapsack problem. PPSNVII-Workshop
[13] Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W.H.Freeman and company, New York
[14] Gilmore PC, Gomory RE (1966) The theory and computation of knapsack functions. Oper Res 14:1045–1075 · Zbl 0173.21502 · doi:10.1287/opre.14.6.1045
[15] Hanafi S, Fréville A (1998) An efficient tabu search approach for the 0-1 multidimensional Knapsack Problem. Eur J Oper Res 106(2–3):659–675 · Zbl 0991.90089 · doi:10.1016/S0377-2217(97)00296-8
[16] Hanafi S, Wilbaut C (2008) Scatter search for the 0-1 multidimensional knapsack problem. J Math Model Algor 7:143–159. doi: 10.1007/s10852-008-9078-9 · Zbl 1140.68063 · doi:10.1007/s10852-008-9078-9
[17] Ke L, Feng Z, Ren Z, Wei X (2010) An ant colony optimization approach for the multidimensional knapsack problem. J Heur 16(1):65–83. doi 10.1007/s10732-008-9087-x · Zbl 1184.90141
[18] Khuri S, Back T, Heitkotter J (1994) The zero/one multidimensional knapsack problem and genetic algorithms. In: Proceedings of the 1994 ACM symposium on applied computing, pp 188–193
[19] Kong M, Tian P (2007) Application of the particle swarm optimization to the multidimensional knapsack problem. Artificial Intelligence and Soft Computing. In: 8th international conference. Proceedings, pp 1140–1149
[20] Kong M, Tian P, Kao Y (2008) A new ant colony optimization algorithm for the multidimensional Knapsack problem. Comput Oper Res 35(8):2672–2683 · Zbl 1169.90435 · doi:10.1016/j.cor.2006.12.029
[21] Leguizamon G, Michalewicz Z (1999) A new version of ant system for subset problems. In: Proceedings of the congress on evolutionary computation, pp 1459–1464
[22] Maenhout B, Vanhoucke M (2007) An electromagnetic meta-heuristic for the nurse scheduling problem. J Heur, Springer, Netherlands, vol 13, no 4, pp 359–385
[23] Martello S, Toth P (1990) Knapsack problems: algorithms and computer implementations. Wiley, New York · Zbl 0708.68002
[24] Naderi B, Tavakkoli-Moghaddam R, Khalili M (2010) Electromagnetism-like mechanism and simulated annealing algorithms for flowshop scheduling problems minimizing the total weighted tardiness and makespan. Knowl Based Syst 23(2):77–85
[25] Pirkul H (1987) A heuristic solution procedure for the multiconstraint zero-one knapsack problem. Naval Res Logist 34(1):61–72 · Zbl 0609.90092
[26] Rafael PH, Nikitas D (2003) On the performance of the ant colony system for solving the multidimensional Knapsack problem. In: Proceedings of the IEEE pacific rim conference on communications, computers and signal processing, pp 338–341
[27] Shih W (1979) A branch and bound method for the multiconstraint zero-one knapsack problem. J Oper Res Soc 30:369–378 · Zbl 0411.90050
[28] Solnon C, Fenet S (2006) A study of ACO capabilities for solving the maximum clique problem. J Heur 12:155–180 · Zbl 1163.90817 · doi:10.1007/s10732-006-4295-8
[29] Stenholm S, Suominen KA (2005) Quantum approach to informatics. Wiley, New York · Zbl 1123.81015
[30] Vasquez M, Vimont Y (2005) Improved results on the 0-1 multidimensional knapsack problem. Eur J Oper Res 165(1):70–81 · Zbl 1112.90366 · doi:10.1016/j.ejor.2004.01.024
[31] Wu P, Yang K, Fang H (2006) A revised EM-like algorithm + K-OPT method for solving the traveling salesman problem. In: Proceedings of the first international conference on innovative computing, information and control. ISBN 0-7695-2616-0/06
[32] Yurtkuran A, Emel E (2010) A new hybrid electromagnetism-like algorithm for capacitated vehicle routing problems. Expert Syst Appl 37:3427–3433 · doi:10.1016/j.eswa.2009.10.005
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.