Open AccessList-Based Simulated Annealing Algorithm With Hybrid Greedy Repair and Optimization Operator for 0–1 Knapsack Problem
Author(s) -
Shi-Hua Zhan,
Ze-Jun Zhang,
Li-Jin Wang,
Yi-Wen Zhong
Publication year - 2018
Publication title -
ieee access
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.587
H-Index - 127
ISSN - 2169-3536
DOI - 10.1109/access.2018.2872533
Subject(s) - aerospace , bioengineering , communication, networking and broadcast technologies , components, circuits, devices and systems , computing and processing , engineered materials, dielectrics and plasmas , engineering profession , fields, waves and electromagnetics , general topics for engineers , geoscience , nuclear engineering , photonics and electrooptics , power, energy and industry applications , robotics and control systems , signal processing and analysis , transportation
List-based simulated annealing (LBSA) algorithm, which uses list-based cooling scheme to control the change of parameter temperature, was first proposed for traveling salesman problem. This paper extends the application of LBSA algorithm for 0-1 knapsack problem (0-1 KP). A hybrid greedy repair and optimization operator, which combines density-based and value-based greedy repair and optimization operators, is designed to get better balance between intensification and diversification. Extensive experiments were performed to show the effectiveness and parameter robustness of a list-based cooling scheme and to verify the advantage of using hybrid greedy repair and optimization operator. Comparing experiments, which were conducted on small-scale, medium-scale, and large-scale 0-1 KP instances, have shown that LBSA algorithm is better than or competitive with other state-of-the-art metaheuristics.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom