順序性移動式精英政策之子群體基因演算法於多目標問題之應用

Shifting Sequential Archive of Sub-Population Genetic Algorithm in Solving Multi-Objective Problem

李家智(Chia-Chih Li)

指導教授 ： 張百棧 ； 謝日章

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

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

摘要

本研究將以子群體基因演算法為主要架構，從收斂性和擴散性二個方向著手，在收斂性方面提出新的演化式演算法─順序性移動式精英政策之子群體基因演算法(SSA-SPGA)，以改善原始子群體基因演算法的求解效率和品質。在擴散性方面主要是將順序性移動式精英政策之子群體基因演算法再加上調適性的交配率及突變率(ASSA-SPGA)，使得適合度值大的個體得到較高的機率改變其搜尋方向，增加擴散性。二個方法皆以流程型排程問題、完全平行機台多目標排程問題及連續性問題等，多目標最佳化問題來驗證新演算法的適用性，並與NSGA2及SPEA2進行比較。所比較的衡量方法為 、R-metric及C-metric。測試的結果發現，SSA-SPGA及ASSA-SPGA雖然在收斂性及穩定性較差，但在擴散性方面表現得的較佳，可以在二側搜尋到較多的的解。

關鍵字

基因演算法、收斂性、擴散性、多目標最佳化問題

並列摘要

A modified Sub-Population genetic Algorithm (SPGA) is proposed in the research. It’s developed from two properties: convergence and diversity. As for convergence, a new evolutionary algorithm - Shifting Sequential Archive of Sub-Population Genetic Algorithm (SSA-SPGA) is created to improve the effectiveness and quality of solution searching by the original SPGA. And the diversity is enhanced by combining the SSA-SPGA with adaptive crossover rate and mutation rate to enable the individuals with high fitness value have higher probability to change their searching direction. The appropriateness of these two proposed methods are verified by solving multi-objectives problems such as flowshop scheduling problems, multi-objective parallel machine scheduling problems and continuous problems, etc. The measurement methods are , R-metric and C-metric. The result finds that although SSA-SPGA and ASSA-SPGA do not perform so well in convergence and stability, they are better in diversity, and can find more solutions on two sides.

並列關鍵字

Genetic Algorithm ； Convergence ； Diversity ； Multi-Objectives Scheduling

參考文獻

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

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

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

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

59. 阮永漢，「系統模擬與基因演算法於完全相同機台排程之應用」，元智大學，碩士論文， 2002。