Addressing the advantages of using ensemble probabilistic models in Estimation of Distribution Algorithms for scheduling problems

被引:23
作者
Chen, Shih-Hsin [1 ]
Chen, Min-Chih [2 ]
机构
[1] Nanhua Univ, Dept Elect Commerce Management, Dalin 62248, Taiwan
[2] WuFeng Univ, Dept Informat Management, Wufeng 62153, Taiwan
关键词
Estimation of Distribution Algorithms; Single machine scheduling problem; Permutation flowshop scheduling problem; Self-Guided Genetic Algorithm; GENETIC ALGORITHM; ARTIFICIAL CHROMOSOMES; LOCAL SEARCH; MACHINE; OPTIMIZATION; HEURISTICS; EARLINESS;
D O I
10.1016/j.ijpe.2012.05.010
中图分类号
T [工业技术];
学科分类号
08 ;
摘要
Estimation of Distribution Algorithms (EDAs) have recently been recognized as a prominent alternative to traditional evolutionary algorithms due to their increasing popularity. The core of EDAs is a probabilistic model which directly impacts performance of the algorithm. Previous EDAs have used a univariate, bi-variate, or multi-variable probabilistic model each time. However, application of only one probabilistic model may not represent the parental distribution well. This paper advocates the importance of using ensemble probabilistic models in EDAs. We combine the univariate probabilistic model with the bi-variate probabilistic model which learns different population characteristics. To explain how to employ the two probabilistic models, we proposed the Ensemble Self-Guided Genetic Algorithm (eSGGA). The extensive computation results on two NP-hard scheduling problems indicate the advantages of adopting two probabilistic models. Most important of all, eSGGA can avoid the computation effort overhead when compared with other EDAs employing two models. As a result, this paper might point out a next generation approach for EDAs. (c) 2012 Elsevier B.V. All rights reserved.
引用
收藏
页码:24 / 33
页数:10
相关论文
共 51 条
[41]  
Shapiro JL, 2006, LECT NOTES COMPUT SC, V4193, P92
[42]   The one-machine problem with earliness and tardiness penalties [J].
Sourd, F ;
Kedad-Sidhoum, S .
JOURNAL OF SCHEDULING, 2003, 6 (06) :533-549
[43]  
TSUTSUI S, 2002, P 4 AS PAC C SIM EV
[44]   Effect of Using Partial Solutions in Edge Histogram Sampling Algorithms with Different Local Searches [J].
Tsutsui, Shigeyoshi .
2009 IEEE INTERNATIONAL CONFERENCE ON SYSTEMS, MAN AND CYBERNETICS (SMC 2009), VOLS 1-9, 2009, :2137-2142
[45]   A comparative study of sampling methods in node histogram models with Probabilistic model-building genetic algorithms [J].
Tsutsui, Shigeyoshi .
2006 IEEE INTERNATIONAL CONFERENCE ON SYSTEMS, MAN, AND CYBERNETICS, VOLS 1-6, PROCEEDINGS, 2006, :3132-3137
[46]   Discrete particle swarm optimization based on estimation of distribution for terminal assignment problems [J].
Wang, Jiahai ;
Cai, Yiqiao ;
Zhou, Yalan ;
Wang, Ronglong ;
Li, Caiwei .
COMPUTERS & INDUSTRIAL ENGINEERING, 2011, 60 (04) :566-575
[47]   A hybrid estimation of distribution algorithm for solving the resource-constrained project scheduling problem [J].
Wang, Ling ;
Fang, Chen .
EXPERT SYSTEMS WITH APPLICATIONS, 2012, 39 (03) :2451-2460
[48]   An effective estimation of distribution algorithm for the multi-mode resource-constrained project scheduling problem [J].
Wang, Ling ;
Fang, Chen .
COMPUTERS & OPERATIONS RESEARCH, 2012, 39 (02) :449-460
[49]   ONE-MACHINE RESCHEDULING HEURISTICS WITH EFFICIENCY AND STABILITY AS CRITERIA [J].
WU, SD ;
STORER, RH ;
CHANG, PC .
COMPUTERS & OPERATIONS RESEARCH, 1993, 20 (01) :1-14
[50]   An evolutionary algorithm with guided mutation for the maximum clique problem [J].
Zhang, QF ;
Sun, JY ;
Tsang, E .
IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 2005, 9 (02) :192-200