基因結構探勘於承接式子群體基因演算法求解多目標組合性問題

Mining Gene Structures with Inheritance Sub-Population Genetic Algorithm in Solving Combinatorial Problem

陳啟嘉(Chi-Chia Chen)

指導教授 ： 張百棧

元智大學/工程學院/工業工程與管理學系/碩士(2006年)

https://doi.org/10.6838/YZU.2006.00117

摘要

在本研究中，將以所提出的方法解決組合性問題，主要目的是希望求得一組兼具收斂性及擴散性的柏拉圖解。本研究提出一個基因結構探勘於承接式子群體基因演算法（MGISPGA）的啟發式演算法，用以求解多目標流程型排程問題、多目標平行機台排程問題與多目標背包問題。MGISPGA中所使用的基因結構探勘法又可分為簡單的基因結構探勘（SMGS）、加權式基因結構探勘（WMGS）與門檻式基因結構探勘（TWMGS）。本研究所提出的方法MGISPGA將與SPGA、NSGA-II及SPEA-II等三個演化式演算法進行比較，並以 、R metric與C metric三種衡量指標來討論其求解表現。實驗結果顯示，MGISPGA的求解結果在收斂性與擴散性上都有不錯的表現，而三種基因結構探勘的方法中，TWMGS所得到的求解效果最好。藉由實驗的結果也證實，MGISPGA為一有效求解組合性問題之方法。

關鍵字

組合性問題 ； 多目標基因演算法 ； 基因結構探勘 ； 最佳化

並列摘要

This study presents a new algorithm to solve combination problems. The main purpose of this research is to find a set of pareto solutions with both natures of convergence and diversity. The heuristic proposed in this research uses Mining Gene Structures with Inheritance Sub-Population Genetic Algorithm (MGISPGA) to solve multi-objective flowshop scheduling problems, multi-objective parallel machine scheduling problems and multiple knapsack problems. The mining gene structure used in MGISPGA can be divided into three categories: the simple mining gene structure (SMGS), weighted mining gene structure (WMGS ) ,and the threshold mining gene structure（TWMGS）. The experimental results of MGISPGA used in this research will be compared with three evolving algorithms, SPGA, NSGA-II and SPEA2, and three kinds of performance metrics: , R metric ,and C metric are utilized as the measurement tools. The finding shows that overall speaking, MGISPGA has better solution in convergence and diversity. Besides, among these three kinds of gene structure methods, TWMGS has the best performance. Through the experiments, MGISPGA coucld be an effective approach for solving combination problems.

並列關鍵字

Combinatorial Problems ； Multiple-objective Genetic Algorithms ； Ming Gene Sructures ； Optimization

參考文獻

104. 湯璟聖，「動態彈性平行機群排程的探討」，碩士論文，中原大學， 2003。

101. 林昆霖，「子群體基因演算法於多目標排程之應用─以PCB鑽孔作業為例」，碩士論文，元智大學， 2005。

99. 林水耕，「應用混合式基因演算法求解流程型工廠之多目標排程問題」，碩士論文，元智大學， 2001。

95. 王治元，「智慧型基因演算法於多目標排程之發展與應用—以PCB鑽孔作業為例」，碩士論文，元智大學， 2004。

107. 謝日章，「柔性計算於生產管理之應用」，博士論文，元智大學， 2002。