不規則總合問題(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.