淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-0307200718292400
中文論文名稱 採用不可行解處理策略與逐步改良技術於不規則總合問題
英文論文名稱 Using Unfeasible Solution Processing Strategy and Incremental Improving Technology on Irregular Sum Problems
校院名稱 淡江大學
系所名稱(中) 資訊管理學系碩士班
系所名稱(英) Department of Information Management
學年度 95
學期 2
出版年 96
研究生中文姓名 余奕駿
研究生英文姓名 I-Jun Yu
學號 694521377
學位類別 碩士
語文別 中文
口試日期 2007-06-09
論文頁數 46頁
口試委員 指導教授-劉艾華
委員-陳彥良
委員-紀宗衡
委員-梁恩輝
中文關鍵字 基因演算法  圖形理論  不規則總和  遺傳修正  問題分割 
英文關鍵字 Genetic Algorithms  Graph Theory  Irregularity Sum  Evolution Refinement  Problem Decomposition. 
學科別分類 學科別社會科學管理學
學科別社會科學資訊科學
中文摘要 不規則總合問題(Irregular Sum Problem,ISP)是源自於數論及圖形理論的議題,此問題的特徵是當問題趨向龐大時,其搜尋空間也會隨之成長,因此,如何有效率的搜尋可行解則成為此問題的最主要目標,本研究考慮能夠以效能與自我逐漸改善區域解答為目標,提出一個新的基因演算法稱之為Incremental Improving Genetic Algorithm(IIGA),此演算法在初始解答部份能使用逐步滿足限制式的方式建構解答,在演化時期,IIGA為了加強其搜尋能力,允許部分比例的不可行解參與其中,並且針對這些不可行解產生的因素加以修正,經由實驗比較IIGA與SGA在各種不同類型的圖形之後,在效能上顯示IIGA確實比較優秀。
英文摘要 Irregular Sum Problem (ISP) is an issue resulted from mathematical problems and graph theories. It has the characteristic that when the problem size is getting bigger, the space of the solution is also become larger. Therefore, while searching for the feasible solution, the larger the question the harder the attempt to come up with an efficient search. We propose a new genetic algorithm, called the Incremental Improving Genetic Algorithm (IIGA), which is considered efficient and has the capability to incrementally improve itself from partial solutions. The initial solutions can be constructed by satisfying the constraints in stepwise fashion. The effectiveness of IIGA also comes from the allowing of suitable percentage of illegal solutions during the evolution for increasing the effectiveness of searching. The cut-point of the genetic coding for generating the descendants has carefully planned so that the algorithm can focus on the key factors for the contradiction and has the chances to fix it. After comparing the results of IIGA and usual genetic algorithm among different graphs, we found and shown that the performance of IIGA is truly better.
論文目次 第1章 緒論 1
1.1 研究動機 1
1.2 研究目的 3
1.3 研究範圍 5
1.4 研究架構 5
第2章 文獻探討 7
2.1 數學相關文獻探討 8
2.2 GA for ISP 11
第3章 Incremental Improving Genetic Algorithm 16
3.1 圖形資訊 17
3.2 可行解複雜度定義 19
3.3 建構階段之改進 20
3.4 容許不可行解參與演化 21
3.5 不可行解之運算子 23
3.6 挑選機制 26
第4章 案例測試 28
4.1 可行解比例 29
4.2 時間效能之分析 32
4.3 SGA vs. 逐步建構 34
4.4 演化時期之改善測試 37
4.4.1 存在不合法解對於演化之分析 37
4.4.2 IIGA容許不合法解比例測試 37
4.5 IIGA vs SGA 40
第5章 結論與未來研究方向 42
圖目錄

圖 2.1 SGA流程圖(文獻[1]所提出) 12
圖 2.2 編號網路圖 12
圖 2.3 染色體編碼圖 13
圖 2.4 網路圖 14
圖 3.1 IIGA流程圖 17
圖 3.2 群落示意圖 18
圖 3.3解空間示意圖 19
圖 3.4 建構改善圖 21
圖 3.5 搜尋解演化過程圖 23
圖 3.6 Cut-Point指派圖 25
圖 3.7交配後子代圖 26
圖 3.8挑選流程圖 27
圖 4.1 實驗流程圖 29
圖 4.2 逐步建構與SGA演化過程圖 36
圖 4.3 容許不同比例不可行解演化歷程圖 39
圖 4.4 IIGA與SGA演化歷程圖 41

表目錄

表 3.1 圖形資訊表 18
表4.1單群可行解比例表 30
表4.2 兩群可行解比例表 31
表4.3 多群可行解比例表 31
表4.4 群間密度相同可行解比例表 32
表4.5 逐步建構 vs. 隨機建構時間效能表 32
表4.6 逐步建構 vs. 隨機建構時間效能表 33
表4.7 逐步建構與SGA建構初始解效能表 33
表4.8 逐步建構 vs. SGA演化狀態表 35
表4.9 逐步建構 vs. SGA演化狀態表 36
表4.10 演化結果表 37
表4.11 演化結果分數表 38
表4.12 IIGA與SGA起始與結束分數表 40





參考文獻 中文文獻
1.劉艾華、紀宗衡、余奕駿,基因演算法-應用於具有群聚特性之不規則總和問題,第三屆演化式計算應用研討會暨 2005機會探索國際工作坊,2005年12月,台北。
英文文獻
2.Aiger, M. and E. Triesch, “Irregular assignments of trees and forests,” SIAM Journal of Discrete Mathematics, vol. 3, 1990, pp. 439-449.
3.Alavi, Y., G. Chartrand, F. R. K. Chung, P. Erdos, R. L. Graham and O. R. Oellermann, “Highly irregular graphs,” J. Graph Theory, vol. 11, 1987, pp. 235-249.
4.Amar, D., “Irregularity strength of regular graphs of large degree,” Discrete Mathematics, vol. 114, 1993, pp. 9-17.
5.Bohman, T. and D. Kravitz, “On the irregularity strength of trees,” Journal of Graph Theory, vol. 45, 2004, pp. 241-254.
6.Burris, A. C., “The irregular coloring number of trees,” Discrete Mathematics, vol. 141, 1995, pp. 279-283.
7.Chartrand, G., M. S. Jacobsen, J. Lehel, O. R. Oellermann, S. Ruiz and F. Saba, “Irregular Networks,” Congressus Numerantium, vol. 64, 1988, pp. 187-192.
8.Chen, S. and S. Smith, “Improving Genetic Algorithms by Search Space Reductions,” Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 1999), 1999, pp. 13-17.
9.Christopher, P. R., “Highly irregular asymmetric graphs,” Congressus Numerantium, vol. 91, 1992, pp. 93-97.
10.Davis, L., “Order-based genetic algorithms and the graph coloring problem,” In Handbook of Genetic Algorithms, Van Nostrand Reinhold, New York, 1991, pp. 72-90.
11.Dorigo, M. and V. Maniezzo, “Parallel Genetic Algorithms: Introduction and Overview of Current Research,” Parallel Genetic Algorithms: Theory and Applications, J.Stenders (Ed.), IOS Press, Amsterdam, 1992, pp. 5-42.
12.Ebert, G., J. Hemmeter, F. Lazebnik and A. Woldar, “On the number of irregular assignments on a graph,” Discrete Mathematics, vol. 93, 1991, pp. 131-142.
13.Faudree, R., M. Jacobson, J. Lehel and R. Schlp, “Irregular networks, regular graphs and integer matrices with distinct row and column sums,” Discrete Mathematics, vol. 76, 1989, pp. 223-240.
14.Fleurent, C. and J. A. Ferland “Genetic and hybrid algorithms for graph coloring,” Annals of Operations Research, Vol 63, No. 3 , 1996, pp. 437-461
15.Fogel, D. B., Evolutionary computation: toward a new philosophy of machine intelligence. Piscataway, N J: Institute of Electrical and Electronics Engineers, 1995.
16.Frieze, A., R. J. Gould, M. Karoński and F. Pfender, “On graph irregularity strength,” Journal of Graph Theory, vol. 41, 2002, pp. 120-137.
17.Goldberg, D. E., Genetic algorithm in search, optimization and machine learning., Reading MA: Addison-Wesley Publishing Co; 1989.
18.Gyarfas, A., “The irregularity strength of Km,m is 4 for m odd,” Discrete Mathematics, vol. 71, 1988, pp. 273-274.
19.Holland, J., Adaptation in natural and artificial systems, University of Michigan Press, Ann Arbor, MI, 1975.
20.Jacobson, M. S., E. Kubicka and G. Kubicki, “Irregularity Sum for graphs,” Vishwa International Journal of Graph Theory, vol. 1, no. 2, 1992, pp. 159-175.
21.Kravitz, D., “Investigation of the Irregularity Strength of Trees,” Undergraduate thesis, University of Delaware, 2000.
22.Majcher, Z., J. Michael, J. Górska and Z. Skupień, “The minimum size of fully irregular oriented graphs,” Discrete Mathematics, vol. 236, 2001,pp. 263-272
23.Michalewicz, Z., D. Dasgupta, R. G. Le, M. Schoenauer, “Evolutionary algorithms for constrained engineering problems,” Computers and Industrial Engineering, Vol. 30 , Issue 4, 2006, pp. 851 – 870.
24.Miettinen, K., M. M. Mäkelä, J. Toivanen, “Numerical Comparison of Some Penalty-Based Constraint Handling Techniques in Genetic Algorithms,” Journal of Global Optimization, Vol. 27, No. 4, 2003, pp. 427 – 446.
25.Mezura-Montes, E. , C.A.C. Coello, “A simple multimembered evolution strategy to solve constrained optimization problems,” Evolutionary Computation, IEEE Transactions on, Vol. 9, Issue 1, 2005, pp. 1- 17.
26.Naudts, B. and L. Schiifs, “GA performance distributions and randomly generated binary constraint satisfaction problems,” Theoretical Computer Science, Vol. 287 , Issue 1, 2002, pp. 167-185.
27.Petersen, J., “Die Theorie der regulären Graphen,” Acta Math., vol. 15, 1891, pp. 193-220.
28.Sannomiya, N., H. Iima, K. Ashizawa, Y. Kobayashi, “Application of genetic algorithm to a large-scale scheduling problem for a metal mold assembly process,” Proceedings of the 38th IEEE Conference on Decision and Control, 1999, pp. 2288 - 2293.
29.Whitley, D., “An overview of evolutionary algorithms: practical issues and common pitfalls,” Information & Software Technology, Vol. 43, Issue 14, 2001, pp. 817 - 831.
30.Yuchi, M. and J. H. Kim, “Grouping-based evolutionary algorithm: seeking balance between feasible and infeasible individuals of constrained optimization problems,” Evolutionary Computation, Vol. 1, 2004, pp. 280- 287.
31.Zhao, Y. and N. Sannomiya, “An improvement of genetic algorithms by search space reductions in solving large-scale flowshop problems,” Transactions of IEE of Japan, Vol. 121-C, No. 6, 2001, pp. 1010 - 1015.
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2007-07-12公開。
  • 同意授權瀏覽/列印電子全文服務,於2007-07-12起公開。


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2281 或 來信