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

機構典藏 > College of Business and Management > Graduate Institute & Department of Information Management > Thesis > Item 987654321/34116

Please use this identifier to cite or link to this item: https://tkuir.lib.tku.edu.tw/dspace/handle/987654321/34116

Title:	採用不可行解處理策略與逐步改良技術於不規則總合問題
Other Titles:	Using unfeasible solution processing strategy and incremental improving technology on irregular sum problems
Authors:	余奕駿;Yu, I-jun
Contributors:	淡江大學資訊管理學系碩士班劉艾華;Liou, Ay-hwa Andy
Keywords:	基因演算法;圖形理論;不規則總和;遺傳修正;問題分割;Genetic Algorithms;Graph Theory;Irregularity Sum;Evolution Refinement;Problem Decomposition.
Date:	2007
Issue Date:	2010-01-11 04:56:07 (UTC+8)
Abstract:	不規則總合問題(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.
Appears in Collections:	[Graduate Institute & Department of Information Management] Thesis

Files in This Item:

File	Size	Format
	0Kb	Unknown	308	View/Open

Loading...