(44.192.112.123) 您好!臺灣時間:2021/02/28 06:06
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:謝坤憲
研究生(外文):Kun-Sian Sie
論文名稱:以生命力與競爭強化為基礎之模擬草履蟲演化演算法
論文名稱(外文):Sim-paramecium Evolution Algorithm based on Enhanced Livability and Competition
指導教授:李宗南李宗南引用關係
指導教授(外文):Chungnan Lee
學位類別:碩士
校院名稱:國立中山大學
系所名稱:資訊工程學系研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2007
畢業學年度:95
語文別:英文
論文頁數:47
中文關鍵詞:基因演算法競爭無性繁殖
外文關鍵詞:genetic algorithmcompetitionasexual reproduction
相關次數:
  • 被引用被引用:0
  • 點閱點閱:84
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
此篇論文提出了一種藉由改變基因演算法的流程來加速基因演算法演化速度的方法。這個方法增加了無性繁殖、競爭以及生命上限幾個機制在基因演算法的存活機制之前。這幾個新增的機制會加速基因演算法的收斂速度。實驗結果顯示這個方法在旅人問題會得到47%的收斂速度提升,並且在著色問題上也有10%的提升。除此之外,因為這個方法是藉由新增加的機制來改善基因演算法的效能,所以相關研究於改進基因演算法內部機制的方法依然可以跟這個方法整合。
This thesis proposes an algorithm to enhance the convergence speed of genetic algorithm by modifying the function flow of a simple GA. Additional operators, such as asexual reproduction, competition, and livability, are added before the survival operation. After adding these three operators to the genetic algorithm, the convergence speed can be increased. Experiments indicate that simulations with the proposed algorithm have a 47% improvement in convergence speed on the traveling salesman problem. As for the graph coloring problem, the proposed algorithm also has a 10% improvement. Also, since these operators are additional parts to the original GA, the algorithm can be further improved by enhancing the operators, such as selection, crossover, and mutation.
Chapter 1 Introduction………………………………………………………1
Chapter 2 Related Work………………………………………………………3
2-1 Genetic Algorithms………………………………………………………3
2-1-1 Representation…………………………………………………………5
2-1-1-1 Representation of the Traveling Salesman Problem…………5
2-1-1-2 Representation of the Graph Coloring Problem………………5
2-1-2 Selection………………………………………………………………6
2-1-2-1 Roulette Wheel Approach…………………………………………6
2-1-2-2 Tournament Approach………………………………………………7
2-1-3 Crossover………………………………………………………………8
2-1-3-1 Partially Mapped Crossover………………………………………8
2-1-3-2 Uniform Crossover…………………………………………………9
2-1-3-3 Greedy Partition Crossover………………………………………11
2-1-4 Mutation…………………………………………………………………13
2-1-4-1 Reciprocal Exchange Mutation……………………………………13
2-1-4-2 Inversion Mutation…………………………………………………13
2-2 Researches on Genetic Algorithm……………………………………14
Chapter 3 The Proposed Algorithm…………………………………………16
3-1 Aging………………………………………………………………………19
3-2 Competition………………………………………………………………20
3-3 Reproduction………………………………………………………………23
3-4 The Parameters Setting Method………………………………………24
3-5 The Complexity Analysis………………………………………………25
Chapter 4 Performance Evaluation…………………………………………26
4-1 Traveling Salesman Problem……………………………………………26
4-2 Graph Coloring Problem…………………………………………………31
Chapter 5 Conclusion…………………………………………………………35

References………………………………………………………………………36
[1]J. H. Holland, Adaptation in Natural and Artificial Systems, First Published by University of Michigan Press, 1992.
[2]M. L. Mauldin, Maintaining Diversity in Genetic Search, Proceedings of the National Conference on Artificial Intelligence AAAI-84, pp.247-250, 1984.
[3]L. A. Rendell, A Doubly Layered Genetic Penetrance Learning System, Proceedings of the Third National Conference on Artificial Intelligence AAAI-83, pp.343-347, 1983.
[4]M. Kavian and R. G. McLenaghan, Application of Genetic Algorithms to the Algebraic Simplification of Tensor Polynomials, Proceedings of the 1997 international symposium on Symbolic and algebraic computation, pp.93-100, 1997.
[5]D. Whitley, The GENITOR algorithm and selection pressure: Why Rank-Based Allocation of Reproductive Trials Is Best, Proceedings of 3rd International Conference on Genetic Algorithms, pp.116-121, 1989.
[6]C. K. Ting, S. T. Li, and C. N. Lee, On the harmonious mating strategy through tabu search, Information Sciences, pp.189-214, 2003.
[7]C. H. Su and C. N. Lee, A Multi-Parent Crossover for Combinatorial Optimization Problems, Master Thesis of National Sun Yat-Sen University, Kaohsiung, Taiwan, 2006.
[8]S. Tsutusi, Multi-Parent Recombination in Genetic Algorithm with Search Space Boundary Extension by Mirroring, Proceedings of the 5th International Conference on Parallel Problem Solving from Nature, pp.428-437, 1998.
[9] A. E. Eiben, Multiparent Recombination in Evolutionary Computing, Advances in Evolutionary Computing: theory and applications, Springer-Verlag New York, 2003.
[10]W. Rand, R. Riolo and J. H. Holland, The Effect of Crossover on the Behavior of the GA in Dynamic Environments, Proceedings of the 8th annual conference on Genetic and evolutionary computation, pp.1289-1296, 2006.
[11]Y. Hong, Q. Ren, and J. Zeng, Adaptive Population Size for Univariate Marginal Distribution Algorithm, Proceedings of the Evolutionary Computation, pp.1396-1402, 2005.
[12] D. E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley, 1989.
[13] C. R. Houck, J. A. Joines, and Michael G. Kay, A Genetic Algorithm for Function Optimization: A Matlab Implementation, North Carolina State University, Raleigh, NC, Technical Report, 1995.
[14]D. E. Goldberg and R. Lingle, Alleles, Loci and the Traveling Salesman Problem, Proceedings of the First International Conference on Genetic Algorithms, pp.154-159, 1985.
[15] E. Falkenauer, The Worth of the Uniform, Proceedings of the Evolutionary Computation, pp. -782 Vol. 1, 1999.
[16] P. Galinier and J. K. Hao, Hybrid Evolutionary Algorithms for Graph Coloring, Journal of Combinatorial Optimization, pp.379-397, 1998.
[17]B. Freisleben and P. Merz, New Genetic Local Search Operators for the Traveling Salesman Problem, pp.890-899, Proceedings of the Fourth International Conference on Parallel Problem Solving from Nature, 1996.
[18]J. T. David and P. Sampat, Mathematical Programming in a Hybrid Genetic Algorithm for Steiner Point Problems, Proceedings of the ACM symposium on Applied computing, pp.357-363,, 1995.
[19]S. Tsutusi, Multi-Parent Recombination in Genetic Algorithm with Search Space Boundary Extension by Mirroring, Proceedings of the 5th International Conference on Parallel Problem Solving from Nature, pp. 428-437, 1998.
[20] S. V. Jose and A. B. John, Sexual Selection with Competitive/co-operative Operators for Genetic Algorithms, Proceedings of the IASTED International Conference on Neural Networks and Computational Intelligence, pp.191-196, 2003.
[21] http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsplib.html
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關論文
 
1. 16、 崔延紘、張志清、吳志桐,電子載貨證券之證據力及其舉證問題之研究,國立臺灣海洋大學海運學報,第12期,2003年10月。
2. 12、 徐仁慈,貨物唯一追蹤號碼(UCR)簡介,今日海關,第40期,2006年4月。
3. 11、 孫漢欽,以提單號面查詢通關流程可行性研究報告,今日海關,第44期,2007年4月。
4. 10、 周東鳳、羅素珍、陳慧娟、洪碧涓,RFID在物流運輸上之應用,電工通訊,2007年3月。
5. 4、 柯澤東,新海商法溯源-實體統一國際公約對我國海商法之影響,月旦法學雜誌,第60期,2000年5月。
6. 9、 何尚先,『條約對於非諦約國之效力』,社會科學論叢,第11輯,民國50年6月。
7. 22、 張志清、陳岳宏,論電子載貨證券之憑證機構作業方式,國立臺灣海洋大學海運學報,第10期,2002年6月。
8. 23、 張天駿,從美國司法判決看台灣的兩國論-從明台產險案談起,全國律師,89年4月。
9. 24、 傅廷中;盛茜,提單轉讓過程中的訴權問題研究,月旦民商法雜誌,第10期,2005年12月。
10. 25、 楊鴻基,空運提單的性質及押匯銀行對提單的權利—兼論空運法律適用問題,法令月刊,第29卷第7期,民國67年7月。
11. 27、 蔡絢麗,空運貨損索賠案例探討空運分提單為中心,中國海事商業專科學校學報,第1卷第3期,2007年3月。
12. 31、 譚湘龍,從國際航空法的觀點論代碼共用,民航季刊第一卷第3期,民國88年9月。
 
系統版面圖檔 系統版面圖檔