簡易檢索 / 詳目顯示

回結果列表
研究生： 簡逸倫
Yi-Lun Chien
論文名稱： 背包問題之再探討
Knapsack Problems Revisited
指導教授： 水谷英二
Eiji Mizutani
口試委員: 王孔政
Kung-Jeng Wang
黃安橋
An-Chyau Huang
學位類別： 碩士
Master
系所名稱： 管理學院 - 工業管理系
Department of Industrial Management
論文出版年： 2011
畢業學年度： 99
語文別： 英文
論文頁數： 63
中文關鍵詞： 背包問題 、動態規劃 、基因演算法
外文關鍵詞： knapsack problem, dynamic programming, genetic algorithm
相關次數： 點閱：243  下載：2 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 見英文摘要

    The Knapsack Problems family is one of the most important problems in Optimization fields.It was classified into NP-hard problem.Unbounded Knapsack Problem is one variant that has special properties can be efficiently exploited.In this thesis, we first give a quick scan of Knapsack Problems family, and describe these properties in details.
    Further, the conventional optimization method - Dynamic Programming- is conscientiously reviewed from the basic to the advance versions of this problem.Although the problem-specified Genetic Algorithm for UKP received few attentions previously, we capture the main features among the literatures and provide a simplified scheme of GA for the faster running time.
    According to the series of experiments, we point out the limitation of data sets which were widely applied in the literatures (especially in papers which solving UKP by GA), and discuss the trade-off between the exact algorithm DP and the approximate approach GA.
    Due to the powerful properties of UKP, we find out that the GA does not take many advantages comparing with DP in the problems which are usually considered large-size in UKP.

    1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Problem De nition . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Why the Knapsack Problems are Important . . . . . . . . . . . . . . .. 3 1.2.1 Multiobjective Evolutionary Algorithm . . . . . . . . . . . . . . .. 3 1.2.2 Real World Applications . . . . . . . . . . . . . . . . . . . . .. . 5 1.3 Special Properties of UKP . . . . . . . . . . . . . . . . . . . . . . 5 1.3.1 Periodicity . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3.2 Dominance . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 6 2 Dynamic Programming Approach . . . . . . . . . . . . . . . . . . . . . 10 2.1 Complexity of DP for the Knapsack Problem . . . . . . . . . . . . . . 10 2.2 Basic Dynamic Programming . . . . . . . . . . . . . . . . . . . . . . 11 2.2.1 General Resource Allocation Formulation . . . . . . . . . . . . . . 11 2.2.2 Exploiting Linearity of Basic Dynamic Programming . . . . . . . .. 13 2.3 Early Stopping and Symmetry of Solution . . . . . . . . . . . . . . . 16 2.4 Breakpoints in Optimal Value Function . . . . . . . . . . . . . . . . 19 2.5 E cient Dynamic Programming for the UKP . . . . . . . . . . . . . . . 21 3 Genetic Algorithm Approach . . . . . . . . . . . . . . . . . . . . . . 25 3.1 Introduction of GA . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.2 Li's GA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.3 Adaptive GA with Elitism Strategy . . . . . . . . . . . . . . . . . . 28 3.4 Center of Mass Selection Operator Based GA . . . . . . . . . . . .. . 29 3.5 The GA Scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 4 Experiment Results . . . . . . . . . . . . . . . . . . . . . . . . .. . 32 4.1 Data Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 4.1.1 Random Data Set . . . . . . . . . . . . . . . . . . . . . . . . . . 32 4.1.2 Arti cial Data Set . . . . . . . . . . . . . . . . . . . . . . .. . 34 4.2 Computational E ciency of Two Basic DPs . . . . . . . . . . . . . . . 35 4.3 Periodicity-Based DPs . . . . . . . . . . . . . . . . . . . . . . . . 37 4.4 Trade-o Between Exact Algorithm and GA . . . . . . . . . . . . . . . 37 4.5 Performance of Exact Hybrid Algorithm . . . . . . . . . . . . . . . . 39 5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 Appendix A : The NP-Completeness of Knapsack Problem . . . . . . . . . . 46 Appendix B : The Script Files of Matlab . . . . . . . . . . . . . . . . . 48

    見本文

    無法下載圖示 全文公開日期 2016/01/17 (校內網路)
    全文公開日期 2041/01/17 (校外網路)
    全文公開日期 2041/01/17 (國家圖書館：臺灣博碩士論文系統)
    QR CODE