臺灣博碩士論文加值系統

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

見本文