二元變量估計分配演算法應用於流程型排程問題

Bi-Variate Estimation of Distribution Algorithm for Flow Shop Problem

蕭鴻錦(Hung-Ching Hsiao)

指導教授 ： 張百棧

元智大學/資訊學院/資訊管理學系/碩士(2013年)

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

摘要

近年來，估計分配演算法(Estimation of Distribution Algorithms, EDAs)被廣泛應用於求解各類組合性問題，但隨著問題的複雜度提升，估計分配演算法容易產生過早收斂而陷入局部最佳化的問題。因此，本研究針對估計分配演算法進行優化，提出一種混合型演算法稱為二元變量估計分配演算法(Bi-Variate Estimation of Distribution Algorithm, BVEDA)。BVEDA以估計分配演算法為架構，使用二元變量機率模型作為演化依據，期望獲得更豐富的演化訊息，根據機率模型挖掘出具有優勢訊息的區塊，並利用區塊組成具競爭優勢的人造解注入母體演化，並結合具高收斂性的區域搜尋方法，增加找尋最佳解的機會。本研究透過排列式流程型排程問題(Permutation Flow Shop Problem, PFSP)來驗證BVEDA的求解能力，實驗結果顯示，BVEDA能有效提升EDAs之收斂能力，避免過早陷入局部最佳化，求解能力優於其他知名的演化式演算法。我們提出的BVEDA兼具效率與效果，是一個具備高度競爭力之演化式演算法。

關鍵字

排程問題 ； 二元變量機率模型 ； 優勢區塊 ； 人造解

並列摘要

Recently, Estimation of Distribution Algorithms (EDAs) is adapted to solve the combinatorial problems. Nevertheless many of these approaches failed to solve the problems efficiently because the intractability of computational cost when the problem size increases. Therefore, we propose a new evolutionary algorithm called Bi-Variate Estimation of Distribution Algorithm (BVEDA), which is based on EDAs. A set of blocks which have advantage of information is generated using bivariate probability model, and these blocks combining with rest of genes to form an effective artificial chromosome. Then, artificial chromosome is injected into population to enhance the efficiency of evolution. In addition, we employ a local search approach to improve efficiency of convergence and the opportunity to find the optimal solution. In order to confirm the effectiveness of BVEDA, we apply BVEDA on permutation flow shop problem. According to the experimental results, BVEDA can effectively enhance the convergence of EDAs, and outperforms others evolutionary algorithms. The BVEDA is an evolution algorithm which has better performance.

並列關鍵字

Scheduling problems ； Bivariate probability model ； Blocks ； Artificial chromosome

參考文獻

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

[2] Flood, M. M. “The Traveling Salesman Problem. Operations Research,” vol.4, pp.64-75,1956.

[3] Chu, P.C., Beasley, J. E. “A Genetic Algorithm for the Multidimensional Knapsack Problem,” Journal of Heuristics, pp. 63-86, 1998.

[5] Garey, M. R., Johnson, D.S. “Some simplified NP-complete graph problems,” Theoretical Computer Science, Vol. 1, pp. 237–267, 1976.

[7] Brucker, P., Sceduling algorithms, Springer, Berlin, 1998.