在本研究中,將以所提出的方法解決組合性問題,主要目的是希望求得一組兼具收斂性及擴散性的柏拉圖解。本研究提出一個基因結構探勘於承接式子群體基因演算法(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.