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 |

Authors (5 rows)

Cited by (2 rows)

References (0 rows)

Name | Order | Citations | PageRank |
---|---|---|---|

Aizhen Liu | 1 | 7 | 1.29 |

Jiazhen Wang | 2 | 21 | 2.23 |

Guodong Han | 3 | 6 | 2.90 |

Su-zhen Wang | 4 | 11 | 3.67 |

Jiafu Wen | 5 | 2 | 0.45 |