跳到主要內容

臺灣博碩士論文加值系統

(18.205.192.201) 您好!臺灣時間:2021/08/05 10:46
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:張維哲
研究生(外文):Wei-Je Chang
論文名稱:結合外部自我演化機制改善基因演算法求解組合性最佳化問題
論文名稱(外文):Combined Varietal Genetic Algorithm with External Self-evolving Mechanism for Combinatorial Optimization Problems
指導教授:張百棧張百棧引用關係
學位類別:碩士
校院名稱:元智大學
系所名稱:資訊管理學系
學門:電算機學門
學類:電算機一般學類
論文種類:學術論文
論文出版年:2009
畢業學年度:97
語文別:中文
論文頁數:88
中文關鍵詞:多樣性組合性最佳化問題基因演算法自我演化分群多階段突變策略
外文關鍵詞:DiversityCombinatorial ProblemGenetic AlgorithmSelf-evolvingClusteringMultiple-phases Mutation Strategy
相關次數:
  • 被引用被引用:0
  • 點閱點閱:296
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
基因演算法(Genetic Algorithm)是最常用於求解組合性問題的演化式演算法,該方法在組合問題中具有不錯的求解效果。但隨著組合性問題(Combinatorial Problem)的維度(Dimension)漸漸變大,該方法易因演化運算後喪失族群多樣性(Diversity)而產生過早收斂或稱過早成熟的問題,使求得的解落於局部最佳解(Local Optimal)之中並且難以跳脫。為了解決此問題,大多數的學者均以改變演化的運算子或其機率,試圖藉由演化運算子之機率的不同改善過早收斂並跳脫出區域最佳解。
本研究提出以衡量族群多樣性,及利用分群(Clustering)的概念,將族群依照多樣性分為多個不同的群體,在演化時從不同的群體中挑選出個體加以演化,以增加演化時染色體容易喪失多樣性而過早收斂的情況並擴大演化的搜尋空間,其後透過多階段突變(Multiple-Phases Mutation)策略演化法則,以不同突變方法探究搜尋空間,並於其中所產生出的基因資訊擁有較好基因片段的染色體加以保留,透過染色體多樣性的計算,將其放置於各群組之中,藉由此方式,一方面可以將在演化過程中出現過的較好基因片段加以保留,另一方面亦可藉由萃取出較好的染色體資訊增加收斂的速度。透過收集較佳的染色體資訊藉由排序多樣性評估後放入至適合的群組,可避免僅單方面增加收斂速度,而陷入區域最佳解的問題,藉此達到不失多樣性又兼具收斂速度的方法。
本研究以旅行推銷員問題(Traveling Salesman Problem)來進行驗證,其結果証明本研究具有較為快速的收斂速度,並且仍能夠保持族群的多樣性另其不易陷入區域最佳解,而能夠獲得更好的求解品質。
In this paper, a bionic algorithm based on Genetic Algorithms is proposed as a varietal GA, named External Self-evolving Multiple-archives (ESMA). The main idea of ESMA adopts clustering approach to cluster chromosomes with elitist chromosomes and high diversities. ESMA focuses on improving the efficiency of applying diversity for enhancing the solution quality via searching unexplored searching space. Therefore, this paper proposes three mechanisms for self-evolving Multiple-archives, which are Clustering Strategy, Switchable Mutation and Elitist Propagation. These mechanisms are designed based on the idea of increasing dynamic diversity for searching better solution space. Moreover, the proposed algorithm can effectively search satisfactory solution than several well-known algorithms with benchmark problems such as Simple Genetic Algorithm (SGA), Ant Colony Optimization (ACO) and Simulated Annealing (SA). The experimental results using Traveling Salesman Problem (TSP) instances which are KroA100, KroA150 and KroA200 for small problems to show the efficiency of convergence speed. Instance PR299 and PCB442 are applied to test the general complexity of problem. And the final instance, PR1002, PR2392, PCB1173 and PCB3038 show the robust of the proposed approach. The experimental results show that the proposed approach is more effective when searches global solution and it can prevent the solution trapped in local optimal when compared with the earlier approaches.
結合外部自我演化機制改善基因演算法求解組合性最佳化問題 i
論文口試委員審定書授權書 ii
授權書 iii
中文摘要 iv
英文摘要 v
誌謝 vii
目錄 viii
表目錄 x
圖目錄 xii
第一章 緒論 1
1.1研究背景與動機 1
1.2研究目的 2
1.3研究方法 3
1.4研究架構與流程 4
第二章 文獻探討 7
2.1組合性問題 7
2.2旅行銷售員問題 8
2.2.1旅行銷售員問題之求解方法 10
2.3 啟發式演算法(Heuristics Algorithms) 14
2.3.1 基因演算法(Genetic Algorithms, GAs) 14
2.3.2 具機率模式之基因演算法 16
2.3.3 其他基因演算法之相關研究 17
2.3.4 基因結構探勘運算子(Mining Gene Structures Operator) 19
2.3.5模擬退火法 (Simulated Annealing) 20
2.3.6蟻群最佳化 (Ant Colony Optimization) 21
2.4 多樣性設計及量測(Diversity Design and Measure) 25
2.4.1 相關多樣性應用之研究 27
2.4.2個體多樣性以及母體多樣性的計算 27
2.4.3個體多樣性之計算: 28
2.4.4 母體多樣性的計算: 30
第三章 問題定義與介紹 31
3.1 TSPLIB旅行推銷員測試資料 33
第四章 研究方法 39
4.1 ESMA第一階段(First Stage of ESMA) 43
4.2 ESMA第二階段(Second Stage of ESMA) 44
4.3 ESMA第三階段(Third Stage of ESMA) 46
4.4 ESMA第四階段(Forth Stage of ESMA) 49
第五章 實驗結果與分析 53
5.1 各演算法之參數設定 53
5.2 ESMA四階段之階段轉換世代參數實驗設計 55
5.3 ESMA二階段之Multiple_Swap突變參數實驗設計 57
5.4 各方法於旅行推銷員問題之結果比較 61
5.5 透過平均絕對值誤差率分析各方法於旅行推銷員問題之結果比較 71
5.6 分析與討論 74
第六章 結論與未來展望 77
6.1結論 77
6.2 未來展望 79
參考文獻 82
附錄 87
A.基因演算法於TSP問題KroA100之實驗設計 87
1.A.Ekárt, and S.Z. Németh. “Maintaining the Diversity of Genetic Programs," Genetic Programming: 5th European Conference, EuroGP 2002, Kinsale, Ireland, vol.3-5, 2002. Proceedings.
2.Affenzeller, M., “New Variants of Genetic Algorithms Applied to Problems of Combinatorial Optimization,” Proceedings of the EMCSR 2002, vol.1, pp.75-80, 2002.
3.Backer, K. R.,” Introduction to Sequencing and Scheduling. John Wiley,” NY. 1974.
4.Baluja, S. and S. Davies, “Fast Probabilistic Modeling for Combinatorial Optimization,”American Association for Artificial Intelligence, pp.469-476, 1998.
5.Bodin, L. D., Golden, B. L., Assas, A., and Ball, M.,”Routing and scheduling of vehicles and crews: the state of art,” Computer and Operations Research, vol.10, pp.63-211, 1983.
6.Boxer L, Miwa T, Gustafson T, Kedes L, “Identification and characterization of a factor that binds to two human sarcomeric actin promoters”. J Biol Chem 264, pp.1284–1292, 1989.
7.Bingul, Z., “Adaptive genetic algorithms applied to dynamic multiobjective problems,” vol.7, pp.791-799, Applied Soft Computing, 2006.
8.Brucker, P., B. Jurisch., and A. Kramer, “The job-shop problem and immediate selection,” Annals of Operations Research, Vol. 50, pp. 73-114, 1994.
9.Chan, D., “Precedence constrained TSP applied to circuit board assembly and no wait flowshop,” International Journal of Production Research, vol.31, pp.2171-2177, 1993.
10.Chan, F. T. S., S. H. Chung and P. L. Y. Chan, “Application of genetic algorithms with dominant genes in a distributed scheduling problem in flexible manufacturing systems,” International Journal of Production Research, vol.44, pp.523-543, 2006.
11.Chang, P. C., Y. W. Wang and C. H. Liu, “New Operators for Faster Convergence and Better Solution Quality in Modified Genetic Algorithm,” Lecture Notes in Computer Science, vol.3611, pp.983-991, 2005.
12.Clarke, G., & Wright, W.,”Scheduling of Vehicles from a Central Depot to a Number of Delivery Points,” Operation Research, vol.12, pp.568-581, 1964.
13.D. E. Goldberg and J. Richardson,”Genetic Algorithms with Sharing for Multimodal Function Optimization,”In Genetic Algorithms and their Applications (ICGA''87), pp. 41-49, 1987.
14.Dorigo, M., Gambardella, L. M.,”Ant colony system: A cooperative learning approach to the tavelling salesman problem.” IEEE, pp.53-66, 1997.
15.E. H. L. Aarts, F. M. J. De Bont, E. H. A. Haberts and P. J. M. VanLaarhoven, “Statistical Cooling: A General Approach to Combinatorial Optimizations”, Philips Journal of Research, vol.4, pp.193-226, 1985.
16.E.K. Burke, S. Gustafson, and G. Kendall.,”Diversity in genetic programming: an analysis of measures and correlation with fitness. Evolutionary Computation, “IEEE Transactions, vol.8, pp.47-62, 2004.
17.Fishetti, M., Salazar, J. J., & Toth, P.,”A Branch and Cut Algorithm for the symmetric Generalised Travelling Salesman. Problem,” Working paper, University of Bologna, 1993.
18.Flood, M. M.”The traveling salesman problem.Operations Research,” vol.4, pp.61-75, 1956.
19.Garey, M. R., and Johnson, D. S.,”Computers and Intractability: A Guide to the Theory of NP-Completeness,” W. H., 1956.
20.Gibson, D. R. and Sharp, G. P., “Order batching procedures,” European Journal of Operational Research, vol. 58, no.1, pp.57-67, 1992.
21.H. Shimodaira., “DCGA: a diversity control oriented genetic algorithm.” in Tools with Artificial Intelligence, Proceedings, Ninth IEEE International Conference, 1997.
22.Harik, G.R., F. G. Lobo and D. E. Goldberg, ”The compact genetic algorithm ,” IEEE Transactions on Evolutionary Computation, vol.3, No. 4, pp.287-297, November, 1999.
23.Hoffman, K. L. and M. Padberg, Combinatorial and Integer Optimization, in S. I. Gass and C. M. Harris, editors, Encyclopedia of Operations Research and Management Science, Centennial Edition, Kluwer Academic Publishers, Boston, 2001.
24.Hwang, H., Bake, W., and Lee, M. K., “Clustering algorithms for order picking in an automated storage and retrieval systems,” International Journal of Production Research, vol. 26, no. 2, pp. 189-201, 1988.
25.K. Ting, and H. Shu-Yuen.,”Using Disruptive Selection to Maintain Diversity in GeneticAlgorithms,” Kluwer Academic Publishers, 1997.
26.K.U.Rasmus.,”Diversity-Guided Evolutionary Algorithms,” Proceedings of the 7th International Conference on Parallel Problem Solving from Nature, Springer-Verlag, 2002.
27.Kureichick, V. M., V. V. Miagkikh and A. P. Topchy, “Genetic Algorithm for Solution of the Traveling Salesman Problem with New Features against Premature Convergence,” Russia: Taganrog State University of Radio-Engineering, 1995.
28.Kashi N., Singh, Dirk L. “A branch and bound algorithm for the traveling purchaser problem,” European Journal of Operational Research, pp.571-579, 1997.
29.Kirkpatrick, A.,”Optimization by simulated annealing: quantitative studies,” Journal of statistical Physics, vol.34, pp.978-986, 1984.
30.Knox, J.”Tabu search performance on the symmetric TSP. Computers & Operations Research”, vol.21 (8), pp.786-802, 1994.
31.Kubiak, M., “Distance Metrics and Fitness –Distance Analysis for the Capacitated Vehicle Routing Problem,” Presented at The 6th Metaheuristics International Conference, Vienna, Austria, 2005.
32.Kubiak, M., A. Jaszkiewicz and P. Kominek, “Fitness-distance analysis of a car sequencing problem,” Technical Report RA-009/06, 2006.
33.Kubota, N., K. Shimojima and T. Fukuda, “The Role of Virus Infection in Virus-Evolutionary Genetic Algorithm,” Evolutionary Computation, Proceedings of IEEE International Conference, pp.182-187, 1996.
34.K.Q. Zhu, and Z. Liu.,”Empirical Study of Population Diversity in Permutation-Based Genetic Algorithm,”Genetic and Evolutionary Computation – GECCO 2004", 2004.
35.L. Yee, G. Yong, and X. Zong-Ben.,”Degree of population diversity - a perspective on premature convergence in genetic algorithms and its Markov chain analysis,” Neural Networks, IEEE Transactions, vol.8, pp.1165-1176, 1994.
36.Laporte, G.,”The vehicle routing problem: An overview of exact and approximate algorithms,” European Journal of Operational Research, vol.59 (3), pp.345−358, 1992.
37.Lawler, J., Derick, L. H., Connolly, J. E., Chen, J. H., and Chao, F. C. J. Biol. Chem. vol.260, pp.3762-3772, 1985.
38.Lenstra, J. K., and K.G. Rinnooy,”Some Simple Applications of the Traveling Salesman Problem,” Research Report, Stichting Mathematisch Centrum, Amsterdam, 1974.
39.Li H, Zhang QF.,”A multi-objective differential evolution based on decomposition for multiobjective optimization with variable linkages,” Runarsson TP, Beyer HG, Burke E, Merelo-Guervós JJ, Whitley LD, Yao X, eds. Parallel Problem Solving from Nature, PPSN IX. LNCS, Berlin: Springer-Verlag (2006), pp.583−592, 2006.
40.M. Mauldin.,” Maintaining Diversity in Genetic Search,” AAAI, 1984.
41.M.R. Garey and D.S. Johnson.,”Computers and Intractability: A Guide to the Theory of NP-Completeness,” W. H. Freeman, 1979.
42.Metropolis, N., Rosenbluth, A., Rosenbluth M. and Teller, A., “Equation of State Calculations by Fast Computing Machines,” Journal of Chemical Physics, 1953, Vol. 21, pp.1087-1092, 1953.
43.N.Sangkawelert and N.Chaiyaratana.”Diversity control in a multi-objective genetic algorithm,”Evolutionary Computation, 2003. CEC ''03. The 2003 Congress on, 2003.
44.Otten, R. H. J. M.,”Automatic floorplan design.Proceedings of the 19th ACM/IEEE Design Automation Conference”, Miami Beach, FL, 1982.
45.P.-j. Wang,”The Investigation of Dynamic Scheduling Problem Using Genetic Algorithm with Simulation,” Department of Industrial Engineering, Chung Yuan, 1995.
46.Pe a, J. M. et al, “GA-EDA: Hybrid Evolutionary Algorithm Using Genetic and Estimation of Distribution Algorithms,” Computer Science, vol.3029, pp.361-371, April 22, 2004.
47. , A. and E. Costa, “Using biological inspiration to deal with dynamic environments,” In the Proceedings of the Seventh International Conference on Soft Computing (MENDEL''01), Brno, Czech Republic, pp.6-8, 2001.
48.Steven A. Melnyk and Gary L. Ragatz,"Order review/release: research issues and perspectives,”International journal of production research, vol 27, pp. 1081~1096, 1989.
49.S. Paul, D.d.J. Edwin, B. Bart de, and W. Franjo.,”Multi-objective diversity maintenance,”Proceedings of the 8th annual conference on Genetic and evolutionary computation 1-59593-186-4, ACM Press, Seattle, Washington, USA, 2006.
50.Volgenant, T., & Jonker, R.,”A branch and bound algorithm for the symmetric traveling salesman problem based on the 1-tree relaxation,” European Journal of Operational research, vol.9, pp.83-89, 1982.
51.Wang, C. X. et al, “A Novel Genetic Algorithm Based on Cure Mechanism of Traditional Chinese Medicine,” ICNC, pp.86-92, 2005.
52.Wang, C. X. et al, “A novel genetic algorithm based on gene therapy theory,” Transactions of the Institute of Measurement and Control, vol.28, pp.253-262, 2006.
53.W. Bossert, P.K. Pattanaik, and Y. Xu.,”The Measurement of Diversity, Universite de Montreal,” Departement de sciences economiques, 2001.
54.W. Bossert, P.K. Pattanaik, and Y. Xu.,”Similarity of Options and the Measurement of Diversity, Universite de Montreal, Departement de sciences economiques”, 2002.
55.Y. Tsujimura, and M. Gen.,”Entropy-based genetic algorithm for solving TSP Entropy-based genetic algorithm for solving TSP,”Knowledge-Based Intelligent Electronic Systems, 1998. Proceedings KES ''98. 1998 Second International Conference, M. Gen, Ed, 1998.
56.Zhang, J. and K. Y. Szeto, “Mutation Matrix in Evolutionary Computation:An Application to Resource Allocation Problem,” Springer Berlin, 3612, pp.112-119, 2005.
57.吳泰熙、張欽智,「以禁忌搜尋法則求解推銷員行問題」,大葉學報,卷(6)1,1997。
58.陳佑誠,「基因演算法之動態基因多樣性改善以延伸組合性問題之求解空間」,碩士論文,元智大學,2007。
59.陳啟嘉,「基因結構探勘於承接式子群體基因演算法求解多目標組合性問題」,碩士論文,元智大學,2006。
60.陳隆熙,「一個解決TSP 問題最佳解的穩定方法—以TA 演算法為例」,大葉大學工業工程研究所,碩士論文,2002。
61.韓復華、楊智凱,「門檻接受法在TSP問題上之應用」,運輸計劃季刊,卷25(2),163-188,1996。
62.羅中育,「田口品質工程應用於模擬退火法參數組合—以旅行推銷員問題(TSP)為例」,雲林科技大學工業工程與管理研究所碩士論文,2000。
電子全文 電子全文(本篇電子全文限研究生所屬學校校內系統及IP範圍內開放)
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top