Proceedings of the 2016 International Conference on Computer Engineering and Information Systems

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

Authors
Yue Zhang, Xing-Ye Dong, You-Fang Lin
Corresponding Author
Yue Zhang
Available Online November 2016.
DOI
https://doi.org/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.
Open Access
This is an open access article distributed under the CC BY-NC license.

Download article (PDF)

Proceedings
2016 International Conference on Computer Engineering and Information Systems
Part of series
Advances in Computer Science Research
Publication Date
November 2016
ISBN
978-94-6252-283-1
ISSN
2352-538X
DOI
https://doi.org/10.2991/ceis-16.2016.104How to use a DOI?
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  - 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  -