求解置换流水车间调度问题的改进遗传算法

《求解置换流水车间调度问题的改进遗传算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、502009，45（36）ComputerEngineeringandApplications计算机工程与应用求解置换流水车间调度问题的改进遗传算法涂雪平，施灿涛，李铁克TUXue-ping，SHICan-tao，LITie-ke北京科技大学经济管理学院，北京100083SchoolofEconomyandManagement，UniversityofScienceandTechnologyBeijing，Beijing100083，ChinaE-mail：tuxueping1@126.comTUXue-ping，SHICan-tao，LITie-ke.Impro

2、vedgeneticalgorithmforpermutationflow-shopproblem.ComputerEngineeringandApplications，2009，45（36）：50-53.Abstract：Accordingtothefeaturesofpermutationflow-shopproblemandtheprematuredefectofGA，animprovedGAforthisproblemisproposed.IntheprocessofproposedGA，theNEHandthePalmerheuristicsareuse

3、dtoinitializethepopulationtoimprovethequalityoftheinitialsolutions，theMetropolisruleisemployedinchromosomeselectionforavoidingfallintolocaloptimum，andthetabu-searchalgorithmisembeddedtogetawayfromcircuitoussearch.Inordertosavethegeneticinformationofexcellentchromosomes，an“elitemechani

4、sm”ispresentedtoremembergoodgenes，andthebestsolutionswillbesavedineachrun.Theauto-adaptiveterminationruleissuggestedtofurtherimprovesolutionquality.Atlast，theeffectivenessoftheimprovedGAisverifiedbasedonsomebenchmarkproblems.Theresultsshowthatthesolutionqualityandtheconvergencespeedar

5、ebet－terthantheNEHandoriginalGAinitializedbyheuristicalgorithm.Keywords：permutationflow-shopproblem；GeneticAlgorithm（GA）；Metropolisrule；tabusearch；elitemechanism摘要：针对置换流水车间调度问题的基本特征和传统遗传算法易早熟的缺陷，设计了改进遗传算法来求解此问题。采用NEH和Palmer启发式算法进行种群初始化，以提高初始解的质量；根据Metropolis准则对染色体进行选择操作，避免陷入局部最优；在变异过程

6、中引入禁忌算法，避免迂回搜索；在算法迭代过程中引入了保优机制，避免丢失优秀染色体的基因信息；采用自适应终止准则，以保证解的质量。基于典型Benchmark算例的仿真实验结果表明，算法在求解质量和收敛速度方面明显优于NEH算法和种群经过初始优化的传统遗传算法。关键词：置换流水车间调度；遗传算法；Metropolis准则；禁忌搜索；保优机制DOI：10.3778/j.issn.1002-8331.2009.36.016文章编号：1002－8331（2009）36-0050-04文献标识码：A中图分类号：TP181引言在现有研究中，文献[5]将NEH算法和蚁群算法结合起

7、来进行置换流水车间调度问题广泛存在于生产系统和服务系统求解，使用插入型局部搜索策略；文献[6]介绍了一种基于分支中，是典型的组合优化问题，也是典型的NP难问题[1]，工件加界定法的算法，这种算法采用逐对比较的形式来获得较优解；工顺序的多样性和每道工序开工时间的差异性都将大大增加文献[7]介绍了微粒群优化算法来求解此问题，该算法引入交换求解此问题的难度[2]。当只有2台机器时，可以用一个多项式解子和交换序的概念，利用实数进行编码；文献[8]采用了基于回决此问题；但是当机器数达到3台时，其调度问题就属于强NP溯策略和关键工序邻域搜索的并行禁忌搜索算法来进行求解，难题[

8、3]。鉴于