採用不可行解處理策略與逐步改良技術於不規則總合問題

Using Unfeasible Solution Processing Strategy and Incremental Improving Technology on Irregular Sum Problems

余奕駿(I-Jun Yu)

指導教授 ： 劉艾華

淡江大學/管理學院/資訊管理學系碩士班/碩士(2007年)

https://doi.org/10.6846/TKU.2007.00097

摘要

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

並列關鍵字

Genetic Algorithms ； Graph Theory ； Irregularity Sum ； Evolution Refinement ； Problem Decomposition.

參考文獻

2.Aiger, M. and E. Triesch, “Irregular assignments of trees and forests,” SIAM Journal of Discrete Mathematics, vol. 3, 1990, pp. 439-449.

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.

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.