跳到主要內容

臺灣博碩士論文加值系統

(44.212.99.248) 您好!臺灣時間:2023/01/28 12:55
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:蘇建豪
研究生(外文):Chien-hao Su
論文名稱:利用多親代交叉解決組合最佳化問題
論文名稱(外文):A Multi-Parent Crossover for Combinatorial Optimization Problems
指導教授:李宗南李宗南引用關係丁川康丁川康引用關係
指導教授(外文):Chung-Nan LeeChuan-Kang Ting
學位類別:碩士
校院名稱:國立中山大學
系所名稱:資訊工程學系研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2006
畢業學年度:94
語文別:英文
論文頁數:108
中文關鍵詞:多親代交叉組合最佳化問題基因演算法
外文關鍵詞:Multi-Parent CrossoverCombinatorial Optimization ProblemsGenetic Algorithms
相關次數:
  • 被引用被引用:1
  • 點閱點閱:202
  • 評分評分:
  • 下載下載:26
  • 收藏至我的研究室書目清單書目收藏:1
最佳化問題可以區分為數值最佳化問題與組合最佳化問題,基因演算法(Genetic algorithms, GAs)已經被廣泛的應用在解最佳化問題上面,基因演算法搭配多親代交叉方法(multi-parent crossover)常被用來解數值最佳化問題。然而,在解組合最佳化問題方面,還沒有一個有效的多親代交叉方法。Partially mapped crossover (PMX)演算法是解組合最佳化問題方面最常用的交叉方法。在本篇論文中,我們提出了multi-parent partially mapped crossover (MPPMX)。大量的實驗結果顯示出MPPMX改進PMX的比率最高到達38.63 %。而t-test的 p-value在PMX與MPPMX的差異上的值是介於10-6 到10-14之間,也指出MPPMX針對PMX有顯著性的改進。
Optimization problems are divided into numerical optimization problems and combinatorial optimization problems. Genetic algorithms (GAs) are applied to solve optimization problems widely. GAs with multi-parent crossover are often used to solve numerical optimization problems. However, no effective multi-parent crossover is used for combinatorial optimization problems. Partially mapped crossover (PMX) is the most popular crossover for combinatorial optimization problems. In this thesis, we propose multi-parent partially mapped crossover (MPPMX). A large amount of experimental results show that the improvement ratio of MPPMX reaches 38.63 % over PMX. The p-values of t-test on the difference between MPPMX and PMX range from 10-6 to 10-14, which indicates the significant improvement of MPPMX over PMX.
1.INTRODUCTION
1.1 GENETIC ALGORITHMS
1.2 MULTI-PARENT CROSSOVERS
1.3 COMBINATORIAL OPTIMIZATION PROBLEMS
1.3.1 Traveling Salesman Problem
1.3.2 Job Shop Scheduling Problem
1.4 ORGANIZATION
2.GENETIC ALGORITHMS FOR COMBINATORIAL OPTIMIZATION PROBLEMS
2.1 REPRESENTATION
2.1.1 Permutation Representation for the TSP
2.1.2 Representations for the JSP
2.2 SELECTION
2.3 CROSSOVER
2.3.1 Two-Parent Crossover
Partially Mapped Crossover (PMX)
2.3.2 Multi-Parent Crossover
Diagonal Crossover
Uniform Scanning Crossover (U-Scan)
Occurrence Based Adjacency Based Crossover (OB-ABC)
2.4 MUTATION
2.4.1 Insertion Mutation
2.4.2 Reciprocal Exchange Mutation
3.THE PROPOSED METHOD - MPPMX
3.1 MULTI-PARENT PARTIALLY MAPPED CROSSOVER (MPPMX)
3.1.1 Algorithm
3.1.2 Substrings Selection
3.1.3 Substrings Exchange
3.1.4 Mapping List Determination
3.1.5 Offspring Legalization
3.1.6 Complexity analysis of MPPMX
3.2 MPPMX FOR COMBINATORIAL OPTIMIZATION PROBLEMS
3.2.1 MPPMX for the TSP
3.2.2 MPPMX for the JSP
4.PERFORMANCE EVALUATION
4.1 EMPIRICAL ANALYSIS
4.2 EXPERIMENTAL RESULTS ON THE TSP
4.3 EXPERIMENTAL RESULTS ON THE JSP
5.CONCLUSIONS AND FUTURE WORK
APPENDIX A.SETTING AND DATA OF THE EXPERIMENTAL RESULTS
A.1 DATA ON THE TSP
A.1.1 The solution quality
A.1.2 The convergence
A.1.3 The data
A.2 DATA ON THE JSP
A.2.1 The solution quality
A.2.2 The data
REFERENCES
[1]H. J. Bremermann, M. Rogson, and S. Salaff, “Global properties of evolution processes,” In H.H. Pattee, E.A. Edlsack, L. Fein, and A.B. Callahan, editors, Natural Automata and Useful Simulations, pp. 3-41, Spartan Books, Washington DC, 1966.
[2]L. J. Fogel, A. J. Owens, and M. J. Walsh, Artificial Intelligence through Simulated Evolution, John Wiley, 1966.
[3]H. Kaufman, “An Experimental Investigation of Process Identification by Competitive Evolution,” IEEE Transactions on Systems Science and Cybernetics, vol. 3, No. 1, pp. 11-16, 1967.
[4]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.
[5]A. E. Eiben, “Multiparent Recombination in Evolutionary Computing,” In A. Ghosh and S. Tsutsui, editors, Advances in Evolutionary Computing, Natural Computing Series, Springer, pp. 175-192, 2002.
[6]J. H. Holland, Adaptation in Natural and Artificial System, University of Michigan Press, 1975.
[7]C. Darwin, The Origin of Species, John Murray, London, 1859.
[8]C. K. Ting, “Design and Analysis of Multi-Parent Genetic Algorithms,” Dissertation of University of Paderborn, Germany, 2005.
[9]C. K. Ting and H. K. Büning, “A Mating Strategy for Multi-Parent Genetic Algorithms by Integrating Tabu Search,” Proceedings of the 2003 Congress on Evolutionary Computation CEC2003, Canberra, Australia, IEEE Press, pp. 1259-1266, 2003.
[10]A. E. Eiben, P-E. Raué, and Zs. Ruttkay, “Genetic Algorithms with Multi-Parent Recombination,” Proceedings of the 3rd Conference on Parallel Problem Solving from Nature, vol. 866 of LNCS, pp. 78-87, 1994.
[11]A. E. Eiben, C. H. M. van Kemenade, and J. N. Kok, “Orgy in the Computer: Multi-Parent Reproduction in Genetic Algorithms,” Proceedings of the 3rd European Conference on Artificial Life, vol. 929, pp. 934-945, 1995.
[12]A. E. Eiben, C. H. M. van Kemenade, and J. N. Kolk, “Diagonal Crossover in Genetic Algorithms for Numerical Optimization,” Journal of Control and Cybernetics, vol. 26, No. 3, pp. 447-465, 1997.
[13]H.-M. Voigt, and H. Mühlenbein, “Gene Pool Recombination and Utilization of Covariances for the Breeder Genetic Algorithm,” Proceedings of the 2nd IEEE International Conference on Evolutionary Computation, pp. 172-177, 1995.
[14]H. Mühlenbein and H.-M. Voigt, “Gene Pool Recombination in Genetic Algorithms,” Proceedings of the 6th International Conference on Genetic Algorithms, pp. 104-113, 1995.
[15]I. Ono and S. Kobayashi, “A Real-coded Genetic Algorithm for Function Optimization Using Unimodal Normal Distribution Crossover,” Proceedings of the Seventh International Conference on Genetic Algorithms, pp. 246-253, 1997.
[16]S. Tsutusi and A. Ghosh, “A Study on the Effect of Multi-Parent Recombination in Real Coded Genetic Algorithms,” Proceedings of the 1998 IEEE International Conference on Evolutionary Computation, pp. 828-833, 1998.
[17]S. Tsutsui, M. Yamamura, and T. Higuchi, “Multi-Parent Recombination with Simplex Crossover in Real Coded Genetic Algorithms,” Proceedings of the 1999 Genetic and Evolutionary Computation Conference, pp. 657-664, 1999.
[18]D. Gong and X. Ruan, “A New Multi-Parent Recombination Genetic Algorithm,” Proceedings of the 5th World Congress on Intelligent Control and Automation, vol. 3, pp. 2099-2103, 2004.
[19]C. K. Ting, “An Analysis of the Effectiveness of Multi-parent Crossover,” In Parallel Problem Solving from Nature VIII, vol. 3242 of LNCS, pp 131-140, Springer-Verlag, 2004.
[20]J.P. Caldeira, F. Melicio, and A. Rosa, “Using a Hybrid Evolutionary-Taboo Algorithm to Solve Job Shop Problem,” Proceedings of the 2004 ACM Symposium on Applied Computing, pp. 1446-1451, 2004.
[21]M. Garey, D. Johnson, and R. Sethi, “The Complexity of Flowshop and Jobshop Scheduling,” Mathematics of Operations Research, vol. 1, pp. 117-129, 1976.
[22]M. Gen and R. Cheng, Genetic Algorithms and Engineering Design, John Wiley and Sons, New York, 1997.
[23]M. Gen, Y. Tsujimura, and E. Kubota, “Solving Job-Shop Scheduling Problem Using Genetic Algorithms,” Proceedings of the 16th International Conference on Computers and Industrial Engineering, pp. 576-579, 1994.
[24]L. Davis, “Job Shop Scheduling with Genetic Algorithms,” Proceedings of the First International Conference on Genetic Algorithms, pp. 136-140, 1985.
[25]F. Croce, R. Tadei, and G. Vlota, “A Genetic Algorithm for the Job Shop Problem,” Computers and Operations Research, vol. 22, pp. 15-24, 1995.
[26]U. Dorndorf and E. Pesch, “Evolution Based Learning in A Job Shop Scheduling Environment,” Computers and Operations Research, vol. 22, pp. 25-40, 1995.
[27]D. E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley, New York, 1989.
[28]D. Goldberg and R. Lingle, “Alleles, Loci and the Traveling Salesman Problem,” Proceedings of the First International Conference on Genetic Algorithms, pp. 154-159, 1985.
[29]C. H. M. van Kemenade, J. N. Kok, and A. E. Eiben, “Raising GA Performance by Simultaneous Tuning of Selective Pressure and Recombination Disruptiveness,” Proceedings of the 1995 IEEE International Conference on Evolutionary Computation, pp. 346-351, 1995.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
1. 張錯,〈文學獎的爭議性〉,《文訊》,一三六期,一九九七年二月。
2. 張健,〈六十年代的散文|民國五十年到五十九年〉,《文訊月刊》,一三期,一九八四年八月。
3. 張堂錡,〈跨越邊界|現代散文的裂變與演化〉,《文訊》,一六七期,一九九九年九月。
4. 孫治本,〈全球地方化、民族認同與文明衝突〉,《思與言》,三八卷一期,二○○○年三月。
5. 胡錦媛,〈遠離非洲,遠離女性:「黑暗之心」中的旅行敘事〉,《中外文學》,二七卷一二期,一九九九年五月。
6. 胡錦媛,〈繞著地球跑(下)|當代台灣旅行文學〉,《幼獅文藝》,五一六期,一九九六年十二月。
7. 胡錦媛,〈繞著地球跑(上)|當代台灣旅行文學〉,《幼獅文藝》,五一五期,一九九六年十一月。
8. 胡衍南,〈心靈逍遙遊|國內中文旅遊書現況〉,《出版情報》,九八期,一九九六年六月。
9. 林麗如,〈用生命揮灑大地|專訪梁丹丰女士〉,《文訊月刊》,一八八期,二○○一年六月。
10. 林怡君,〈愛麗絲的旅行:兒童文學中的女遊典範〉,《中外文學》,二七卷一二期,一九九五年五月。
11. 林央敏,〈散文出位〉,《文訊》,一四期,一九八四年十月。
12. 孟樊,〈風起雲湧的九○年代台灣文壇〉,《文訊雜誌》,二○○○年十二月。
13. 李鴻瓊,〈空間.旅行.後現代:波西亞與海德格〉,《中外文學》,二六卷四期,一九九七年九月。
14. 李有成,〈理論旅行與文學史〉,《中外文學》,二五卷三期,一九九六年八月。
15. 宋美璍,〈自我主體、階級認同與國族建構:論狄福、菲爾定和包士威爾的旅行書〉,《中外文學》,二六卷四期,一九九七年九月。