×

Intelligent water drops algorithm: a new optimization method for solving the multiple knapsack problem. (English) Zbl 1163.90719

Summary: 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.
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.
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.
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.

MSC:

90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alaya, I., Solnon, C. and Ghedira, K. (2004), ”Ant algorithm for the multidimensional knapsack problem”, International Conference on Bioinspired Optimization Methods and their Applications, BIOMA 2004, pp. 63-72.
[2] DOI: 10.1023/A:1022452626305 · Zbl 1047.90045 · doi:10.1023/A:1022452626305
[3] DOI: 10.1023/A:1009642405419 · Zbl 0913.90218 · doi:10.1023/A:1009642405419
[4] DOI: 10.1016/0167-6377(89)90002-3 · Zbl 0675.90073 · doi:10.1016/0167-6377(89)90002-3
[5] DOI: 10.1007/BF01096763 · Zbl 0822.90110 · doi:10.1007/BF01096763
[6] DOI: 10.1016/S0377-2217(03)00274-1 · Zbl 1045.90050 · doi:10.1016/S0377-2217(03)00274-1
[7] DOI: 10.1007/BF02591863 · Zbl 0571.90065 · doi:10.1007/BF02591863
[8] DOI: 10.1287/opre.14.6.1045 · Zbl 0173.21502 · doi:10.1287/opre.14.6.1045
[9] DOI: 10.1111/j.1540-5915.1977.tb01074.x · doi:10.1111/j.1540-5915.1977.tb01074.x
[10] DOI: 10.1287/ijoc.1.3.190 · Zbl 0753.90054 · doi:10.1287/ijoc.1.3.190
[11] DOI: 10.1126/science.220.4598.671 · Zbl 1225.90162 · doi:10.1126/science.220.4598.671
[12] DOI: 10.1016/S0305-0548(97)00031-2 · Zbl 0889.90119 · doi:10.1016/S0305-0548(97)00031-2
[13] DOI: 10.1162/106365605774666886 · Zbl 05412958 · doi:10.1162/106365605774666886
[14] DOI: 10.1057/jors.1979.78 · doi:10.1057/jors.1979.78
[15] Vasquez, M. and Hao, J-K. (2001), ”A hybrid approach for the 0-1 multidimensional knapsack problem”, 17th International Conference on Artificial Intelligence, pp. 328-33. · Zbl 1015.90056
[16] DOI: 10.1016/j.ejor.2004.01.024 · Zbl 1112.90366 · doi:10.1016/j.ejor.2004.01.024
[17] DOI: 10.1287/mnsc.12.7.485 · doi:10.1287/mnsc.12.7.485
[18] DOI: 10.1287/opre.15.1.83 · doi:10.1287/opre.15.1.83
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.