跳到主要內容

臺灣博碩士論文加值系統

(34.204.169.230) 您好!臺灣時間:2024/02/26 13:01
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:林明賢
研究生(外文):Ming-Hsien Lin
論文名稱:以量子基因演算法解無界限背包問題之研究
論文名稱(外文):A Study on Solving Unbounded Knapsack Problem Base on Quantum Genetic Algorithm
指導教授:陳榮靜陳榮靜引用關係
指導教授(外文):Rung-Ching Chen
學位類別:碩士
校院名稱:朝陽科技大學
系所名稱:資訊管理系碩士班
學門:電算機學門
學類:電算機一般學類
論文種類:學術論文
論文出版年:2009
畢業學年度:97
語文別:英文
論文頁數:47
中文關鍵詞:最佳化問題量子基因演算法背包問題
外文關鍵詞:Quantum genetic algorithmsKnapsack problemsOptimization problems
相關次數:
  • 被引用被引用:0
  • 點閱點閱:636
  • 評分評分:
  • 下載下載:66
  • 收藏至我的研究室書目清單書目收藏:0
資源分配、資金預算、投資決策、裝載物品等日常問題,均可建為背包問題的模組。背包問題(Knapsack Problem)是一個NP-Complete問題,而無界限背包問題更趨複雜,其困難度更甚一般的背包問題。在本文論文中,我們運用量子基因演算法(Quantum Genetic Algorithms, QGAs)求解無界限背包問題(Unbounded Knapsack Problem)。首先將問題轉換成量子基因演算法的模式,再尋求其相對的基因表示方式與適應函數,接著找到可符合限制與求得最大利益的組合,最後經由調整旋轉角度更新量子位元的機率,找出問題的最佳解。另外我們使用貪婪策略以調整染色體的序列來加強執行的效率。初步實驗證明我們的系統是有效的,並與自調式基因演算法(Adaptive Genetic Algorithms, AGAs)比較及評估效能。
Resource distribution, capital budgeting, investment decision and transportation question could form as knapsack question models. Knapsack problem is one kind of NP-Complete problem and Unbounded Knapsack problems (UKP) are more complex and harder than general Knapsack problems. In this paper, we apply QGAs (Quantum Genetic Algorithms) to solve Unbounded Knapsack Problem. First, present the problem into the mode of QGAs and figure out the corresponding genes types and their fitness functions. Then, find the perfect combination of limitation and largest benefit. Finally, quant bit is updated by adjusting rotation angle and the best solution is found. In addition, we use the strategy of greedy method to arrange the sequence of chromosomes to enhance the effect of executing. Preliminary experiments prove our system is effective. The system also compare with AGAs (Adaptive Genetic Algorithms) to estimate their performances.
Table of Contents
中文摘要 ................................................................................................ I
Abstract ................................................................................................II
誌謝 ...................................................................................................... III
Chapter 1 Introduction ..........................................................................1
1.1 The motivation .................................................................................. 1
1.2 The literature review ......................................................................... 4
1.3 The research framework ................................................................... 6
Chapter 2 The system overview.............................................................7
2.1 Representation ....................................................................................7
2.2 QGA ...................................................................................................9
2.3 Classical genetic method...................................................................12
2.4 Arrangement the chromosome sequences ........................................12
Chapter 3 Quantum Genetic algorithm using greedy methods........14
3.1 Gene coding.......................................................................................14
3.2 Unsuitable solutions revising ............................................................17
3.3 Fitness function calculation...............................................................20
3.4 The probability of Q (t) update..........................................................20
Chapter 4 Experimental results and analysis......................................24
4.1 Search spaces are less than 109..........................................................25
4.2 experimental results and discussion.................................................. 27
4.3 Data Distributions............................................................................. 34
Chapter 5 Conclusions and future work..............................................43
References...............................................................................................44

List of Tables
Table 2-1 The unbounded knapsack problem with twenty items..............7
Table 2-2 Arrangement the item’s sequences of chromosomes..............13
Table 3-1 Possible combinations of each item........................................15
Table 3-2 The Setting of rotation angle ...............................................21
Table 4-1 Unbounded knapsack problem with twenty items ..................25

List of Figures
Figure 1-1 Unbounded Knapsack problem................................................3
Figure 2-1 The workflow of the quantum genetic algorithms..................11
Figure 3-1 The workflow of gene coding.................................................17
Figure 3-2 The workflow of unsuitable solutions revising......................19
Figure 3-3 Polar plot of the rotation gate for Q-bit individuals...............21
Figure 3-4 The workflow of Q (t) probability update..............................23
Figure 4-1 Description of the system parameter and the outline of program....................................................................................................24
Figure 4-2 The result of QGAs program................................................. 24
Figure 4-3 Relation between weight constraint and options....................26
Figure 4-4 The plot of optimum values appearances in 200kg................26
Figure 4-5 The experimental results of generations’ changes..................28
Figure 4-6 The experimental results of groups’ changes.........................29
Figure 4-7 The experimental results of rotation angles’ changes.............30
Figure 4-8 The comparison of QGAs and QGAs with Greedy method......................................................................................................32
Figure 4-9 The work flow of QGAs with Greedy method.......................33
Figure 4-10 The relation between benefit and weight..............................37
Figure 4-11(a) The distribution of 100 items...........................................38
Figure 4-11(b) The process time under 100 items....................................39
Figure 4-11(c) The outline of program under 100 items..........................39
Figure 4-12(a) The comparison of the process time.................................40
Figure 4-12(b) The outline of AGA program under 100 items.................40
Figure 4-13(a) The comparison of QGAs and AGAs under 10 items......41
Figure 4-13(b) The comparison of average profits..................................42
[1] P. Benioff (1980), “The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines,” J. Statist. Phys., Vol. 22, pp. 563–591.
[2] N. Chaiyaratana and A.M.S. Zalzala (1999), “Hybridization of Neural Networks and Genetic Algorithms for Time-Optimal Control,” Evolutionary Computation, Vol.1, pp.389-396.
[3] B. Chakrabort(2002), “Genetic Algorithm with Fuzzy Fitness Function for Feature Selection,” Proc. of the IEEE Int.Sym. On Industrial Electronics, pp.315-319.
[4] R.C Chen and C.H. Jian (2007), “Solving Unbounded Knapsack Problem Using an Adaptive Genetic Algorithm with Elitism strategy,” The Fifth International Symposium on Parallel and Distributed Processing and Applications (ISPA07), International Workshop on Intelligent Systems and Smart Home, Springer''s Lecture Notes in Computer Science.
[5] D.E. Goldberg (1989), “Genetic Algorithms in Search, Optimization and Machine Learning”, Addison-Wesley.
[6] L. K. Grover (1996), “A fast quantum mechanical algorithm for database search,” in Proc. 28th ACM Symp. Theory of Computing, pp. 212–219.
[7] K.H. Han and J.H. Kim (2000), “Genetic quantum algorithm and its application to combinatorial optimization problems,” IEEE Conference on Evolutionary Computation, IEEE Press, pp. 1354-1360.
[8] K.H. Han and J.H. Kim (2002), “Quantum-Inspired Evolutionary Algorithm for a Class of Combinatorial Optimization,” IEEE Transactions on Evolutionary Computation, Vol.6, No.6, pp.580-593.
[9] J.H. Holland (1975),” Adaptation in Natural and Asrtificial System,” Ann Arbor: The University of Michigan Press.
[10] K.L. Li, G.M. Dai and Q.H. Li (2003), “A Genetic algorithm for the Unbounded Knapsack Problem”, IEEE Conference on Machine Learning and Cybernetics, Vol.3, pp1586-1590.
[11] P.C. Li and S.Y. Li (2007), “Optimal Design of Normalized Fuzzy Neural Network Controller Based on Quantum Genetic Algorithm,” Journal of System Simulation, Vol.19, No.16, pp. 3710-3730.
[12] S.Y. Li, P.C. Li and L.Y. Yuan (2007), “Quantum genetic algorithm with application in fuzzy controller parameter optimization,” System Engineering and Electronics, Val. 29, No.7, pp. 1134-1138.
[13] S. Martello and P. Toth (1990),”Knapsack Problems: Algorithms and Computer Implementations,” John Wiley &Sons Ltd., ISBN 0-471-92420-2.
[14] A. Narayanan and M. Moore (1996), “Quantum-inspired genetic algorithms,” IEEE Int. Conf. Evolutionary Computation. Piscataway, NJ: IEEE Press, pp. 61–66.
[15] A. Narayanan(1999), “Quantum computing for beginners,” in Proc. 1999 Congress on Evolutionary Computation. Piscataway, NJ: IEEE Press, Vol. 3, pp. 2231–2238.
[16] I.H. Osman and G. Laporte (1996), “Metaheuristics: A bibliography,” Ann. Oper. Res. 63,513–623.
[17] D. Pisinger(2005), “Where are the hard knapsack problems?,” Computers and Operations Research, Vol. 32, Issue 9, pp. 2271-2284.
[18] P. W. Shor(1998), “Quantum computing,” Doc. Mathematica, Vol. Extra Volume ICM, pp. 467–486.
[19] L. Spector, H. Barnum, H. J. Bernstein, and N. Swamy(1999), “Finding a better-than-classical quantum AND/OR algorithm using genetic programming,” in Proc. Congress on Evolutionary Computation. Piscataway, NJ: IEEE Press, Vol. 3, pp. 2239–2246.
[20] H. Teng, B. Yang and B. Zhao (2008), “A New Mutative Scale Chaos Optimization Quantum Genetic Algorithm,” on Chinese Control and Decision Conference (CCDC), pp.1547-1551
[21] J. G. Vlachogiannis and J. Ostergaard (2009), “Reactive power and voltage control based on general quantum genetic algorithms,” Expert Systems with Applications, Vol. 36, Issue 3, pp. 6118-6126.
[22] L.Wang and D.Z. Zheng (2002), “A Modified Genetic Algorithm for Job Shop Scheduling”, International Journal of Advanced Manufacturing Technology, Vol.20, No.6, pp.72-76.
[23] Wikipedia,”Knapsack problem”, [Online]. Available:
http://en.wikipedia.org/wiki/Knapsack_problem
[24] C. Zhao and W. Zhang (2005),“Using genetic algorithm optimizing stack filters based on MMSE criterion,” image and vision Computing, College of Information and Communication Engineering, pp. 853–860.
[25] X.R. Zhu and X.H. Zhang (2007), “A quantum genetic algorithm with repair function and its application Knapsack question,” The Computer Applications, Vol. 27, No.5, pp. 1187-1190.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top