Study on Ant System for the 0-1 Multiple Knapsack Problem with Knapsack Dependent Values
Yue Zhang, Xing-Ye Dong, You-Fang Lin
Available Online November 2016.
- https://doi.org/10.2991/ceis-16.2016.104How to use a DOI?
- multiple knapsack problem; knapsack dependent values; max-min ant system; greedy heuristic
- The values of items of the classic knapsack problems are independent of knapsacks. Inspired from some practical problems, a 0-1 multiple knapsack problems with knapsack dependent item values are proposed. A Greedy heuristic is proposed to provide a feasible solution and a basis for further comparison, and then three ant system algorithms are proposed. To relieve the stagnant phenomenon of the AS and MMAS, MMAS2 is developed with the newly proposed method by mapping the objective periodically for the purpose of adjusting the importance of the pheromone trails, in which the max-min pheromone limitation is also applied. And it has a more chance to find better solutions. Experimental results on randomly generated instances show that the proposed MMAS2 surpasses the MMAS significantly in performance.
- Open Access
- This is an open access article distributed under the CC BY-NC license.
Cite this article
TY - CONF AU - Yue Zhang AU - Xing-Ye Dong AU - You-Fang Lin PY - 2016/11 DA - 2016/11 TI - Study on Ant System for the 0-1 Multiple Knapsack Problem with Knapsack Dependent Values BT - Proceedings of the 2016 International Conference on Computer Engineering and Information Systems PB - Atlantis Press SP - 507 EP - 512 SN - 2352-538X UR - https://doi.org/10.2991/ceis-16.2016.104 DO - https://doi.org/10.2991/ceis-16.2016.104 ID - Zhang2016/11 ER -