應用約略集合於基因演算法之交配機制－以0/1背包問題為例

勤益科大機構典藏 > 管理學院 > 工業工程與管理系(所) > 【工業工程與管理系所】博碩士論文 > Item 987654321/1322

請使用永久網址來引用或連結此文件: http://ir.lib.ncut.edu.tw/handle/987654321/1322

題名:	應用約略集合於基因演算法之交配機制－以0/1背包問題為例 Applying Rough Sets to Crossover Operations in Genetic Algorithms–a Case of 0/1 Knapsack Problem
作者:	王世文 Wang, Shih-Wen
貢獻者:	工業工程與管理系
關鍵詞:	基因演算法;約略集合;屬性化簡;背包問題 Genetic algorithms;Rough sets;Reduct;Knapsack problem
日期:	2008
上傳時間:	2008-10-06 13:32:28 (UTC+8)
摘要:	基因演算法 (Genetic Algorithms; GA) 透過複製、交配及突變等機制，不斷地改變母體使母體演化成適應性更高的下一代以搜尋最佳解。但是在自然界中突變較少發生，因為發生突變時往往也會帶來毀滅性的破壞，所以基因演算法的設計會以較高的比率執行交配機制。而為了防止母體的染色體過於一致而落入局部最佳解，會以較低的比率執行突變使母體多樣化。約略集合 (Rough Sets; RS) 理論適合處理不完全或不精確的資料，進行資料刪減、知識擷取與分類，並輔助決策分析，常用於資料探勘之研究。約略集合理論具有屬性化簡的功能，經過屬性化簡的資訊系統，不僅可減少屬性項目以降低計算的複雜度，並仍以較少的屬性項目維持相同之決策。背包問題 (Knapsack Problem) 屬於NP-hard 問題，若以一般的數學規劃方法求解，不僅耗費運算時間，而且不易求得最佳解。因基因演算法的設計為全域搜尋，較不易於運算過程早期即落入局部最佳解，故背包問題適合以基因演算法求解。本研究是以0/1 背包問題為例，結合約略集合之屬性化簡功能於基因演算法之交配機制。聚焦於交配機制是由於基因演算法的交配機制執行比率較高。一般而言常使用的交配方式有單點交配及雙點交配，這兩種交配方式都是隨機選取交配點，因此本研究應用約略集合理論中屬性化簡的功能將背包物件視為屬性進行化簡，由屬性化簡找出染色體中重要的基因點作為交配點。藉由屬性化簡，有系統的找出交配點以刪除交配的隨機性達到控制基因交配。本研究提出兩種導入方法：混合型約略集合之基因演算法 (Mix Rough Sets in Genetic Algorithms; MRSGA)，以及單一型約略集合之基因演算法 (Unique Rough Sets in Genetic Algorithms; URSGA)。MRSGA考慮母體是否能進行屬性化簡，尋找染色體中重要的基因，若能屬性化簡則以此屬性化簡所找到的基因作為交配點，若不能進行屬性化簡則以單點交配進行交配。MRSGA仍保留了部份單點交配的隨機方式尋找交配點。URSGA則是完全刪除基因演算法隨機尋找交配點的方式，採用較嚴謹的方式進行交配，能找到重要的基因點才進行交配。若能屬性化簡則以此屬性化簡所找到的基因作為交配點，若未能屬性化簡則不進行交配。迥異於以往基因演算法相關研究，本研究主要導入約略集合的屬性化簡功能於交配機制中，期望以屬性化簡找出背包問題中重要的基因，並以此基因作為交配的依據，以加強基因演算法的效能。根據實驗結果顯示，導入約略集合屬性化簡於基因演算法交配機制，在限制條件較嚴格的情況下，MRSGA以及URSGA演算法能夠提供比傳統基因演算法更好更集中的解。而在限制條件寬鬆的條件下，該兩種演算法也能夠提供比基因演算法更集中的解。
顯示於類別:	[工業工程與管理系(所)] 【工業工程與管理系所】博碩士論文

文件中的檔案:

檔案	大小	格式	瀏覽次數
	0Kb	Unknown	1327	檢視/開啟

在NCUTIR中所有的資料項目都受到原著作權保護.

資料載入中.....