A Self-guided Genetic Algorithm for permutation flowshop scheduling problems

被引:57
作者
Chen, Shih-Hsin [2 ]
Chang, Pei-Chann [1 ]
Cheng, T. C. E. [3 ]
Zhang, Qingfu [4 ]
机构
[1] Yuan Ze Univ, Dept Informat Management, Tao Yuan, Taiwan
[2] Nanhua Univ, Dept Elect Commerce Management, Chiayi, Taiwan
[3] Hong Kong Polytech Univ, Dept Logist & Maritime Studies, Kowloon, Hong Kong, Peoples R China
[4] Univ Essex, Sch Comp Sci & Elect Engn, Colchester CO4 3SQ, Essex, England
关键词
Estimation of Distribution Algorithms; Permutation flowshop scheduling; Self-guided crossover; Self-guided mutation; PARTICLE SWARM OPTIMIZATION; EVOLUTIONARY ALGORITHM; ARTIFICIAL CHROMOSOMES; HEURISTIC ALGORITHM; TOTAL FLOWTIME; MAKESPAN; MACHINE;
D O I
10.1016/j.cor.2011.08.016
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
In this paper we develop a Self-guided Genetic Algorithm (Self-guided GA), which belongs to the category of Estimation of Distribution Algorithms (EDAs). Most EDAs explicitly use the probabilistic model to sample new solutions without using traditional genetic operators. EDAs make good use of the global statistical information collected from previous searches but they do not efficiently use the location information about individual solutions. It is recently realized that global statistical information and location information should complement each other during the evolution process. In view of this, we design the Self-guided GA based on a novel strategy to combine these two kinds of information. The Self-guided GA does not sample new solutions from the probabilistic model. Instead, it estimates the quality of a candidate offspring based on the probabilistic model used in its crossover and mutation operations. In such a way, the mutation and crossover operations are able to generate fitter solutions, thus improving the performance of the algorithm. We tested the proposed algorithm by applying it to deal with the NP-complete flowshop scheduling problem to minimize the makespan. The experimental results show that the Self-guided GA is very promising. We also demonstrate that the Self-guided GA can be easily extended to treat other intractable combinatorial problems. (C) 2011 Elsevier Ltd. All rights reserved.
引用
收藏
页码:1450 / 1457
页数:8
相关论文
共 44 条
[1]   An estimation of distribution algorithm with intelligent local search for rule-based nurse rostering [J].
Aickelin, U. ;
Burke, E. K. ;
Li, J. .
JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2007, 58 (12) :1574-1585
[2]  
[Anonymous], 1994, POPULATION BASED INC, DOI 10.1007/978-3-540-70706-6_21
[3]  
[Anonymous], 2011, Pei. data mining concepts and techniques
[4]  
Baker K. R., 1974, Introduction to Sequencing and Scheduling"
[5]  
Baluja S, 1998, FIFTEENTH NATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE (AAAI-98) AND TENTH CONFERENCE ON INNOVATIVE APPLICATIONS OF ARTIFICAL INTELLIGENCE (IAAI-98) - PROCEEDINGS, P469
[6]  
Baluja S., 1997, ICML '97: Proceedings of the Fourteenth International Conference on Machine Learning, P30
[7]  
Baluja S, 1995, CMUCS95193 CARN MELL
[8]   A hybrid heuristic for the traveling salesman problem [J].
Baraglia, R ;
Hidalgo, JI ;
Perego, R .
IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 2001, 5 (06) :613-622
[9]   Approaches to Selection and their Effect on Fitness Modelling in an Estimation of Distribution Algorithm [J].
Brownlee, Alexander E. I. ;
McCall, John A. W. ;
Zhang, Qingfu ;
Brown, Deryck F. .
2008 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION, VOLS 1-8, 2008, :2621-+
[10]  
Cestnik B., 1990, ECAI 90. Proceedings of the 9th European Conference on Artificial Intelligence, P147