A new discrete electromagnetism-based meta-heuristic for solving the multidimensional knapsack problem using genetic operators

Bonyadi, Mohammad Reza and Li, Xiaodong (2012) A new discrete electromagnetism-based meta-heuristic for solving the multidimensional knapsack problem using genetic operators. Operational Research, 12 2: 229-252. doi:10.1007/s12351-010-0084-0


Author Bonyadi, Mohammad Reza
Li, Xiaodong
Title A new discrete electromagnetism-based meta-heuristic for solving the multidimensional knapsack problem using genetic operators
Journal name Operational Research   Check publisher's open access policy
ISSN 1109-2858
1866-1505
Publication date 2012-08
Year available 2010
Sub-type Article (original research)
DOI 10.1007/s12351-010-0084-0
Open Access Status Not yet assessed
Volume 12
Issue 2
Start page 229
End page 252
Total pages 24
Place of publication Heidelberg, Germany
Publisher Springer
Language eng
Formatted abstract
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).
Keyword Electromagnetism-Like meta-heuristic
Multidimensional knapsack problem
Population-based optimization
Swarm intelligence
Q-Index Code C1
Q-Index Status Provisional Code
Institutional Status Non-UQ

Document type: Journal Article
Sub-type: Article (original research)
Collection: School of Information Technology and Electrical Engineering Publications
 
Versions
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 2 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 4 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Tue, 12 Jul 2016, 14:48:38 EST by System User on behalf of Learning and Research Services (UQ Library)