跳到主要內容

臺灣博碩士論文加值系統

(44.201.99.222) 您好!臺灣時間:2022/12/03 23:23
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:簡程輝
研究生(外文):Cheng-Huei Jian
論文名稱:以自調式基因演算法解無界限背包問題之研究
論文名稱(外文):A study on Solving Unbounded Knapsack Problem Based on Adaptive Genetic Algorithm
指導教授:陳榮靜陳榮靜引用關係
指導教授(外文):Rung-Ching Chen
學位類別:碩士
校院名稱:朝陽科技大學
系所名稱:資訊管理系碩士班
學門:電算機學門
學類:電算機一般學類
論文種類:學術論文
論文出版年:2007
畢業學年度:95
語文別:英文
論文頁數:45
中文關鍵詞:演化式演算法菁英策略自調式基因演算法背包問題基因演算法
外文關鍵詞:adaptive Genetic algorithmEvolutionary algorithmGenetic algorithmKnapsack problemElitism strategy
相關次數:
  • 被引用被引用:2
  • 點閱點閱:533
  • 評分評分:
  • 下載下載:60
  • 收藏至我的研究室書目清單書目收藏:1
背包問題(Knapsack problem)在作業研究尋求最佳化中是極著名的課題,它隸屬於NP-Complete問題的一種,而無界限背包問題(Unbounded Knapsack problem)的複雜度與困難度更甚於一般的背包問題。在本研究中,我們運用自調式機制的基因演算法以解無界限背包問題,其中包括使用自動基因序列重排方式以及自動調整執行次數的機制。在基因演算法的重製程序中我們使用菁英策略(elitism strategy)來選取新的子代,使用菁英策略是用來克服基因演算法收斂較慢的情形,菁英策略保留了較好的染色體,且保證它們經過交配與突變的機制後,其子代至少與母代一樣好。本系統自動調整基因演算法中的初始執行次數與初值母體數;它在每一次的基因演算法結束後將最好的值保留在菁英群中,當整個執行次數執行完畢後再從菁英群中取出最佳者當實際解。另外我們使用貪婪法策略以調整染色體的序列以加強執行的效率,實驗證明我們提出的方法能求得最佳解,而且染色體重排的方式大大的提昇了執行的效率,以達到快速求得最佳解的目的。
The Knapsack problem is an NP-Complete problem. Unbounded Knapsack problems are more complex and harder to solve than the general Knapsack problem. In this thesis, we apply the genetic algorithm using adaptive mechanism which includes greedy method to arrange the chromosomes and automatically adapt the runs to solve the unbounded Knapsack problem. In reproduction procedure, we use elitism strategy to select new offspring. The elitism strategy is utilized to overcome the defect of the slow convergence rate of the general genetic algorithm. The elitism strategy retains good chromosomes and ensures that they are not eliminated through the mechanism of crossover and mutation, while ensuring that the features of the offspring chromosomes are at least as good as their parents. The system automatically adapts the number of the initial population of chromosomes and the number of runs of the genetic algorithm. It will obtain the best value from the chromosomes of each run and retain the best values into an elitism set. The best value is then taken from the elitism set and adapted as the real solution. In addition, we use the strategy of greedy method to arrange the sequence of chromosomes to enhance the effect of executing. Experimental results showed that our method could find the best solution of the problem in evidence space.
Table of Contents
中文摘要..................................................I
Abstract................................................ II
誌謝.....................................................IV
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
Chapter 3 Genetic algorithm and Adaptive Genetic Setting.11
3.1 Basic genetic method.................................11
3.2 Arrangement of the chromosome sequence...............12
3.3 Adaptive genetic setting.............................13
Chapter 4 Genetic Algorithm using Elitism Strategy.......17
4.1 Gene coding with reducing bits ......................17
4.2 Crossover and mutation mechanism.....................20
4.3 The definition of the fitness function ..............22
4.4 The elitism selection strategy ......................23
Chapter 5 Experimental results and analysis..............24
5.1 Search spaces are less than 1000000000...............26
5.2 Data distributions...................................35
5.3 The result which rearrange the sequence of chromosomes
5.4 Expand the ranges....................................39
Chapter 6 Conclusion and future work.....................43
Reference................................................44
[1] A.A. Javadi, R. Farmani, T.P. Tan. (2005),” A hybrid intelligent genetic algorithm,” Advanced Engineering Informatics,Vol.19, pp.255–262.
[2] C. Zhao, 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.
[3] D. Pisinger. (2005),” Where are the hard Knapsack problem s?” Computers and Operations Research, Vol. 32,Issue 9,pp. 2271-2284.
[4] Hans Kellerer,Ulrich Pferschy, and David Pisinger.(2004),” Knapsack Problems,” Springer, Berlin, ISBN 3-540-40286-1
[5] Holland, J. H. (1975), “Adaptive in Natural and Artificial Systems,” Ann Arbor, MI: Univ. Michigan Press.
[6] J. Costa, R. Tavares, A.C. Rosa, (1999), “An experimental study on dynamic random variation of population size,” IEEE SMC Conference Proceedings. IEEE International Conference on Systems, Man, and Cybernetics, pp. 607–612
[7] Ken-Li Li, Guang-Mingdai, Qing-HuaA Li1. (2003), “A genetic algorithm for the unbounded Knapsack Problem,” Proceedings of the International Conference on Machine Learning and Cybernetics, pp1586 - 1590 Vol.3
[8] Lan Zhou, Sun Shi-Xin . (2006),” A Self-Adaptive Genetic Algorithm for Tasks Scheduling in Multiprocessor System,” Communications, Circuits and Systems Proceedings, International Conference ,pp. 2098-2101
[9] Mark Last, Shay Eyal. (2005), “A fuzzy-based lifetime extension of genetic algorithms,” Fuzzy Sets and Systems. Vol.149 ,pp. 131–147
[10] M. Negnevitsky. (2004), Artificial Intelligence: A Guide to Intelligent Systems, 2nd ed. Essex: Addison Wesley.
[11] Randy L. Haupt. (2000),” Optimum Population Size and Mutation Rate for a Simple Real Genetic Algorithm that Optimizes Array Factors,” Proceedings of the International Symposium, IEEE on Antennas and Propagation Society, pp. 1034-1037
[12] Silvano Martello , Paolo Toth. (1990), ”Knapsack Problems:Algorithms and Computer Implementations”. John Wiley &Sons Ltd., ISBN 0-471-92420-2`
[13] W. P. Su. (1995), “Simulated annealing as a tool for Ab initio phasing in X-ray crystallography,” Acta Cryst. A51 ,pp. 845-849
[14] WiKipedia . Knapsack problem. http://en.wikipedia.org/wiki/Knapsack problem
[15] Young Su Yun, Minoru Mukuda, Mitsuo Gen. (2004), “Reliability Optimization Problems Using Adaptive Hybrid Genetic Algorithms,” Advanced Computational Intelligence and Intelligent Informatics.Vol.8, No.4 pp. 437-441
[16] Zhiming Liu. (2003),” New adaptive genetic algorithm based on ranking,” Proceedings of the Second International Conference on Machine Learning and Cybernetics, pp. 1841-1844
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top