應用瀰母演算法於多目標排程問題之求解

Applying Memetic Algorithm for Multi-objective Scheduling Problems

劉育伶(Yu-Ling Liu)

指導教授 ： 張百棧

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

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

摘要

瀰母演算法（Memetic Algorithm, MA）是近年新興演算法，他不是制式的方法，而是一個通稱，舉凡具有演化並結合鄰近搜尋法（Evolutionary+Local search）都歸類為此方法。本研究所提出之方法稱為Sub-population with Memetic Algorithm（SPMA），應用於求解多目標流程型（Flowshop）之排程問題。
本研究主要分為四個主要部份，首先使用NEH作為建構解，在有限制搜尋時間下更有效找出較佳解，第二將母體賦予權重分群進行演化作更廣泛搜尋，第三結合鄰近搜尋法改變排序進行區域性搜尋，找出更多原先可能未搜尋到的有效解，最後在演化至一定世代時，導入具有機率矩陣所產生的人造解（Artificial Chromosome）注入個體中改善現有最佳解，此架構可具有快速收歛之成效。
在第一個測試問題上，SPMA與其他三個演算法比較，MGISPGA, NSGA-II 和 SPEA2，其衡量指標為D1r。在第二個測試問題上，SPMA與另一個演算法MOSA比較，其衡量指標為柏拉圖最佳解所佔比例。實驗結果顯示，SPMA在多目標流程型問題在測試案例上具有柏拉圖兩大特性－收斂性與擴散性。

關鍵字

瀰母演算法；鄰近搜尋法；人造染色體

並列摘要

Memetic Algorithm (MA) has been a new approach proposed for years; it is not a uniform method but is generally called as a philosophy. For those algorithms with neighboring search (Local Search) are classified to MA. The approach proposed in this paper is named as Sub-population with Memetic Algorithm (SPMA), which is applied for solving multi-objective Flowshop Scheduling Problems.
This paper consists of four phases which firstly apply NEH to be initial solution to search effectively better solution; the second phase is to apply weighted-approach to cluster solved problems for searching more widespread in time constraint; the third phase is to combine with neighboring search to shift the sequence for local search to find out the possible unsearchable feasible solutions; in the final phase, the Artificial Chromosome (AC) with probability matrix will be introduced when the algorithm evolves to certain iteration for injecting to individual to search better combination of chromosomes, this mechanism will make faster convergent time for evolving.
For the first test instance, SPMA compares with three algorithms which is MGISPGA, NSGA-II and SPEA2, the measuring index is D1r. In the second instance, the proportion of Pareto Optimal solutions is applied to be the index for evaluating SPMA and MOSA. The experiments result shows that SPMA has the two important characteristics of Pareto solutions simultaneously which is convergence and spread for solving multi-objective Flowshop Scheduling Problems in test instances.

並列關鍵字

Memetic Algorithm；Local search； Artificial Chromosome

參考文獻

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

61. 柯瓊惠，「基因演算法結合人造解在生產排程之應用」，碩士論文，元智大學， 2007。

57. 李家智，「順序性移動式精英政策之子群體基因演算法於多目標問題之應用」，碩士論文，元智大學， 2006。

63. 陳啟嘉，「基因結構探勘於承接式子群體基因演算法求解多目標組合性問題」，碩士論文，元智大學， 2006。

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