Paper Info
Title
Improved Simulated Annealing Algorithm Solving for 0/1 Knapsack Problem
Abstract
0/1 knapsack problem belongs to combination optimization problem. Its optimal solution exists in the problem space including substantially large useless solutions besides optimal solutions. Differing with other SA (simulated annealing) algorithms that getting the approximate optimization solution from the whole problem space often need much computation time, this improved SA algorithm proposed in this paper avoided this disadvantage by extracting two kinds of solution spaces, i.e. all optimal solutions space and the most possible part optimal solutions space, from the whole space. Then to improve approximate solution quality some variables were introduced to record the maximum solution, which produced during annealing process but was possibly deserted because of Metropolis rule in SA. We applied this SA algorithm, general SA and greedy-based SA algorithm to knapsack problem. And experimental results showed that this algorithm only searching the two optimal spaces obtained better approximate results and largely decreased the time overhead compared with the other two algorithms searching whole space
Year
DOI
Venue
2006
10.1109/ISDA.2006.253776
ISDA (2)
Keywords
Field
DocType
knapsack problem,optimal solution,improved simulated annealing algorithm,problem space,combination optimization,sa algorithm,solution space,greedy-based simulated annealing,combinatorial mathematics,0/1 knapsack problem,optimal space,improved sa algorithm,optimal solutions space,knapsack problems,general sa,simulated annealing,greedy-based sa algorithm,whole space,simulated annealing algorithm,optimization problem
Simulated annealing,Mathematical optimization,Computer science,Combinatorial mathematics,Continuous knapsack problem,Artificial intelligence,Knapsack problem,Approximate solution,Optimization problem,Machine learning,Problem space,Computation
Conference
Volume
ISBN
Citations 
2
0-7695-2528-8
2
PageRank 
References 
Authors
0.45
0
5
Name
Order
Citations
PageRank
Aizhen Liu171.29
Jiazhen Wang2212.23
Guodong Han362.90
Su-zhen Wang4113.67
Jiafu Wen520.45