Intelligent water drops algorithm
Author:
- 6 June 2008
- journal article
- Published by Emerald Publishing in International Journal of Intelligent Computing and Cybernetics
- Vol. 1 (2) , 193-212
Abstract
Purpose – The purpose of this paper is to test the capability of a new population-based optimization algorithm for solving an NP-hard problem, called “Multiple Knapsack Problem”, or MKP. Design/methodology/approach – Here, the intelligent water drops (IWD) algorithm, which is a population-based optimization algorithm, is modified to include a suitable local heuristic for the MKP. Then, the proposed algorithm is used to solve the MKP. Findings – The proposed IWD algorithm for the MKP is tested by standard problems and the results demonstrate that the proposed IWD-MKP algorithm is trustable and promising in finding the optimal or near-optimal solutions. It is proved that the IWD algorithm has the property of the convergence in value. Originality/value – This paper introduces the new optimization algorithm, IWD, to be used for the first time for the MKP and shows that the IWD is applicable for this NP-hard problem. This research paves the way to modify the IWD for other optimization problems. Moreover, it opens the way to get possibly better results by modifying the proposed IWD-MKP algorithm.Keywords
This publication has 27 references indexed in Scilit:
- Empirical Analysis of Locality, Heritability and Heuristic Bias in Evolutionary Algorithms: A Case Study for the Multidimensional Knapsack ProblemEvolutionary Computation, 2005
- Improved results on the 0–1 multidimensional knapsack problemEuropean Journal of Operational Research, 2005
- Iterated Local SearchSSRN Electronic Journal, 2001
- Variable neighborhood searchComputers & Operations Research, 1997
- Greedy Randomized Adaptive Search ProceduresJournal of Global Optimization, 1995
- Knapsack Problems: Algorithms and Computer ImplementationsJournal of the Operational Research Society, 1991
- Optimization by Simulated AnnealingScience, 1983
- A Branch and Bound Method for the Multiconstraint Zero-One Knapsack ProblemJournal of the Operational Research Society, 1979
- A Branch and Bound Method for the Multiconstraint Zero-One Knapsack ProblemJournal of the Operational Research Society, 1979
- HEURISTICS FOR INTEGER PROGRAMMING USING SURROGATE CONSTRAINTSDecision Sciences, 1977