A Self-guided Genetic Algorithm for Permutation Flowshop Scheduling Problems
學年 100
學期 2
出版(發表)日期 2012-07-01
作品名稱 A Self-guided Genetic Algorithm for Permutation Flowshop Scheduling Problems
著者 Chen, S. H.; P. C. Chang; T. C. Edwin Cheng; Q. Zhang
著錄名稱、卷期、頁數 Computers & Operations Research 39(7), p.1450–1457
摘要 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.
關鍵字 Estimation of Distribution Algorithms;Permutation flowshop scheduling;Self-guided crossover;Self-guided mutation
語言 en
ISSN 1873-765X
期刊性質 國外
收錄於 SCI
國別 GBR
出版型式 ,電子版,紙本

機構典藏連結 ( http://tkuir.lib.tku.edu.tw:8080/dspace/handle/987654321/121396 )