實驗室成員‎ > ‎

陳萌智

陳萌智 Min-Chih Chen

博士論文 (2012)

分佈估計演算法解決排程問題之有效指引原則
Guidelines for Developing Effective Estimation of Distribution Algorithms in Solving Scheduling Problems

關鍵字 Keywords

分佈估計演算法, 啟發式演算法, 排程問題
Estimation of Distribution Algorithms, Heuristic Algorithms, Scheduling Problems

摘要

本研究的目的是提出設計分佈估計演算法(Estimation of Distribution Algorithms)有效指引原則。分佈估計演算法由於使用機率模式產生可行解,因此具有不會拆解可行解良好結構的特色,然而卻可能造成分佈估計演算法過早趨於收斂的問題,本研究的第一個指引原則是控制群體的多樣性(diversity),使其能在多樣性與收斂性之間取得平衡,因此提出二個策略:逐步增加群體多樣性與結合超啟發式演算法(meta-heuristic)。分佈估計演算法的另一個問題是機率模式(probabilistic model)可能無法真正描述群體的資訊,本研究第二個指引原則是加強全域搜尋的資訊模式,為此提出二個策略,其一是加入變數之間互動的資訊,其二是在演化初始時加入特定領域的知識。分佈估計演算法另一個問題是缺乏探究(exploitation)最佳解的能力,本研究第三個指引原則是加入局部搜尋演算法,為此提出的策略是在演化過程中將有希望的可行解改良成局部最佳解,再持續演化使其最後能趨近於全域最佳解。為了進一步說明與驗證這些指引原則,本研究將二個有名的分佈估計演算法(EA/G、ACGA)分別加以改良成Adaptive EA/G、EA/G-GA、eACGA、eACGAHYBRID,並分別運用在解決單機、單機具整備時間與流線型機台的排程問題,實驗結果指出改良的演算法在求解品質上比原本的演算法較佳且具有顯著差異,因此這些原則將能提供分佈估計演算法的研究者進一步提升演算法效率的參考,同時證明本研究對於改良分佈估計演算法的效率有重要的貢獻。

Abstract

The goal of this research is to deduce important guidelines for designing effective Estimation of Distribution Algorithms (EDAs). Most EDAs have the advantage of incorporating probabilistic models which can generate chromosomes with non-disruption of salient genes. This advantage, however, may result in premature convergence of EDAs. In order to enhance the design of algorithms in balancing the intensification and diversification effects of EDAs, we propose two strategies to control the diversity of population: by increasing the population diversity gradually and by hybridizing EDAs with other meta-heuristics. There is still a second EDAs question that remains: simple probabilistic models may not be truly representative of the population. To address this concern, two strategies are presented to enhance the information model in global search: by combining ordinal probabilistic model with dependent probabilistic model to represent information model of the population and by embedding domain specific knowledge. Having tackled the problems of diversity and representation, the only item left to discuss is that a promising solution needs a refining method to approach the local optimal solution in evolution. In order to improve the solution quality, exploitative behavior is hybridized into the searching process. For illustrating and validating these guidelines, we employ two well known EDAs as improvements, EA/G and ACGA. The enhanced algorithms based on these guidelines are named as Adaptive EA/G, EA/G-GA, eACGA and eACGAHYBRID respectively. These algorithms are applied in a just-in-time single objective scheduling environment to solve single machine scheduling problems, single machine scheduling problems with setup time, and permutation flowshop scheduling problems. Overview of the experimental results shows that, in terms of solution quality, all of our improved algorithms outperformed original EDAs as well as some algorithms in the literature. Thus, these guidelines can provide references for researchers to improve their EDAs performance in the future, and this study is important for the same reason.

Comments