List-Based Simulated Annealing Algorithm With Hybrid Greedy Repair and Optimization Operator for 0–1 Knapsack Problem

Abstract

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.

Keywords

• Greedy repair and optimization
• hybrid operator
• list-based cooling scheme
• list-based simulated annealing
• 0–1 knapsack problem