Study on Ant System for the 0-1 Multiple Knapsack Problem with Knapsack Dependent Values

DOI

10.2991/ceis-16.2016.104How to use a DOI?

Keywords

multiple knapsack problem; knapsack dependent values; max-min ant system; greedy heuristic

Abstract

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.

Copyright

© 2017, the Authors. Published by Atlantis Press.

Open Access

This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)

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  - 10.2991/ceis-16.2016.104
ID  - Zhang2016/11
ER  -