一种改进的进化算法在生产计划中的应用

1、种改进的进化算法在生产计划中的应用摘要：简要介绍了目前生产计划的研究状况，建立了一个该问题的数学模型，在此基础上,应用遗传算法，并在计算机上得以仿真实现。关键词：多目标进化算法；擂台赛法则；聚集密度；生产计划0引言ERP是当今国际上先进的企业管理模式，其核心是计划体系，包括主生产计划、采购计划、车间作业计划等。车间作业计划的管理目标是按物料需求计划的要求，按时、按质、按量和低成本地完成加工制造任务。该文探讨了遗传算法在车间作业计划安排中的应用。在当今市场经济的条件下，客户的订货量决定了企业的生产品种和产量。企业在做决定时已没有可供选择的余地，生产的技术与工艺已经决定了生产的成本和原材料的消耗，

2、在这个方面，计划已经不能做过多的贡献性决定。因此，生产计划只能从其他方面着手优化生产，也就是说，制定准时化的生产计划，保证能够按期交货，并减少存储费用。进化算法(EvolutionaryAlgorithms,EAs)是近年发展起来的一种崭新的全局优化算法，与大自然的生态环境一样，进化的物种也需要平衡发展，因此设计者必须制定合适生存规则来维持种群的多样性和分布性。越来越多的证据显示EAs非常适合求解多目标优化问题，其机理在于进化群体可并行搜寻多个目标，逐渐找到问题的满意解。越来越多的证据显示EAs非常适合求解多目标优化问题其机理在于进化群体可并行搜寻多个目标，逐渐找到问题的满意解。1基于擂台赛法

3、则和聚集密度的多目标进化算法遗传算法就是一定数目的个体组成的群体的抽象进化模型，各个体由一定长度“基因”串来表示。新的群体通过与父本优劣度成正比的概率选择父本，并由交叉和变异算子产生“类似遗传”的突变进化而来。基因的突变和交叉增加了群体基因材料的多样性，有利变异在长期时间推移中适应环境从而得到遗传与保留，有害变异则因生存困难被淘汰。从优胜劣汰的原则看，新的一代群体对环境的平均适应程度总是比双亲的一代要高。1.1擂台赛法则在基于Pareto的优化中，多目标进化群体的最优解集是通过构造当前进化群体的非支配集来实现的。采用擂台赛法则（arenasprinciple，简称AP）构造非支配的基本思路是，

4、在每一轮比较时，从构造集中选出一个个体出任擂主（一般为当前构造集的第1个个体），由擂主与构造集中其他个体进行比较，败者被淘汰出局，胜者成为新的擂主，并继续该轮比较，一轮比较后，最后的擂主个体即为非支配个体。按照这种方法进行下一轮比较，直至构造集为空。1.2用聚集密度方法保持进化群体的分布性群体中个体的聚集密度能够刻画群体的多样性，如果个体之间的聚集距离越大，则个体的聚集密度就越小。这种方法，既能从宏观上刻画群体的多样性与分布性，同时也比较好的刻画了个体之间的内在关系，可以用于进化过程中对群体的调控。三种方法求聚集密度：一是通过直接计算个体之间的相似度来计算一个个体的聚集密度；二是通过计算个体之

5、间的影响因子来计算个体的聚集密度；三是通过计算个体之间的聚集距离来计算个体之间的聚集密度。1.3遗传算法的全过程事先设计问题的编码方案；选择条件较好的初始染色体群；建立判断染色体优劣的适应度函数；合理的设计遗传算子；确定客观的算法运行参数；确定算法的终止条件。1.4遗传算法的基本运算过程(1) 选择：从当前种群中选出优良的个体作为父代个体。对各染色体vk计算适合度eval(vk)；k=1,2,3,，m对各染色体vk，计算选择概率：P=eval(vk)/Eeval(vk)(2) 交叉：对群体中的个体进行两两随即配对对每一对相互配对的个体，随机设置某一基因之后的位置为交叉点对每一对相互配对的个体，

6、依设定的交叉概率在其交叉点处相互交换两个个体的染色体，从而产生出两个新的个体。变异：遗传算法中的所谓变异运算，是将个体染色体编码串中的某些位置上的基因值用其他等位基因替换，从而形成一个新的个体。2生产计划问题的描述生产调度就是组织执行生产进度计划的工作，是实现生产进度计划的主要手段。生产调度以生产进度计划为依据，生产进度计划要通过生产调度来实现。在生产调度的事业上，生产调度有管理和工作之分，也就是生产调度管理和生产调度工作，是两个互为联系有有区别的概念。生产调度的作用是职能作用，生产调度工作的作用是职责作用。具体来说，生产调度管理，是指生产调度的计划、实施、检查、总结的期量循环活动的管理，是指

7、生产调度的计划理论、方法、法规等方面的管理。生产调度工作，则有狭义和广义之分，从狭义上说，生产调度工作是指生产调度的业务工作，也就是生产经营管理方面的技术性工作，其内容是生产调度对生产经营动态的了解、掌握、预防、处理，对关键岗位如主机岗位实行控制，对跨车间和跨部门的电、水、风，产、供、销、运等进行协调平衡，对产量、质量、安全、效益等重点环节实行衔接一致的保证；从广义上说，生产调度部门的行政管理方面的具体事项，如业务上，科技上的研讨活动，在岗人员道德和专业知识的教育，业务能量的具体发挥等，可见广义的生产调度工作，其具体活动事项要比生产调度管理大得多，将生产调度管理等同生产调度工作是不准确的。可以

8、概括的说，生产调度工作是生产调度管理的具体表现，生产调度工作的完成是生产调度管理在实际上完成的具体表现。由于现代工业企业，具有生产环节多，协作关系复杂，生产连续性强，情况变化快等特点，因此某一局部发生故障，或某一措施没有按期实现，往往会波及整个生产系统的运行。这些因素促使我们不得不加强生产调度工作，以便及时了解、掌握生产进度，研究分析影响生产的各种因素，根据不同情况采取相应对策，使差距缩小或恢复正常。一般计划人员在没有接到用户订单时就应该做好了后期安排工作，只有这样才能应对市场需求，从而获得利润。计划人员从销售人员提供的预测中提取有用信息，并且按已有的标准产品或产品系列安排生产。生产的直接目的

9、是补充成品库存，通过维持一定量成品库存来满足用户的需求，其生产和需求具有相对的稳定性。此类企业的生产计划是基于库存管理，通过建立满足最小库存量、最小成本、最小成本、最小机会损失和最大利润之一为目标函数的先行规划模型，确定某种产品在某个时间段的生产量。但这种方法存在两个缺陷：a、无法同时兼顾多个目标，使得确定的生产量不尽合理；b、通过线性规划模型只能求得唯一的解，给管理者的决策带来极大的限制。针对上述问题，本文提出了能够同时兼顾多个目标的随机规划模型。基于储货型生产的特点，可以采用MonteCarlo方法，根据历史数据预测未来的需求量，它体现了一定的随机性。遗传算法在解决多目标问题上，有比较好的

10、效果，因此用它解决生产计划问题是合适的。于是，我们一次可以同时得到多个Pareto解。这也有利于管理者根据市场和企业的现状选出一个最“合适”的生产组合。为了制定出生产计划，生产企业需要确定各个阶段，各种产品的数量。假设生产周期分为T个阶段，共有I种产品需要生产。d-ti,p-ti和q-ti分别表示在第t个阶段，第i种产品的需求量，生产量和成品库存量。则销售量s-ti和机会损失矢量l-ti可表示为：S-ti=min(d-ti•p-ti+q-ti)JY(1)l-ti=d-ti-S-tiJY(2)于是，下一阶段的成品库存量即为：q-(t+1)i二p-i+q-i-s-iJY(3)设

11、u-ti,v-ti和w-ti分别表示在第t个阶段，第i种产品的销售价格，生产成本价格和成本库存价格。则产品的利润和成本表示如卜：G=刀DD(Tt-1DD)刀DD(ii=1DD)(s-tiu-ti-p-iv-i-q-iw-i)JY(4)C=刀DD(Tt-1DD)刀DD(ii=1DD)(p-iv-i+q-iw-i)JY(5)若企业可供给的最小于市场的需求量，就产生了机会损失：L=刀DD(Tt-1DD)刀DD(Ii=1DD)l-tiu-tiJY(6)于是，生产计划问题的目标就被确定下来：JB(maxGminCminLJB)JY(7)当然企业的生产是依赖于其有限的资源，令企业拥有J种资源，r-ij表示

12、单位数量第i种产品所消耗第j种资源的数量，a-ij表小在第t个阶段可获得的第j种资源。实际上，资源的消耗量一定不会超过其可以获得的数量，而且生产量也不能为负值。因此，得到了生产计划问题的约束：EDD(lt-1DD)r-ijp-i<a-ij(t=1,T,j=1,J)J丫(8)p-ti>0(t=1,T,j=1,J)JY(9)3结束语任何一门新技术的产生与发展都源于它的应用，否则这门新技术将是没有生命力的。多目标进化算法(MOEA)正是因为它具有广泛的应用前景而发展起来的。近年来，生产计划问题引起了广大学者的重视，越来越多的学者对这一领域进行研究，并得出结论：遗传算法是迄今为止用来解决车

13、间调度问题有效的、合理的、常用的进化算法。Schaffer为了解决及其学习中的多模式分类判别(Multiclasspatterndiscrimination)问题，在LS-1的基础上采用向量评估遗传算法(VEGA)设计并实现了LS-2。我们开发的算法和实际的调度状况还有一定的差距。实际的生产调度含有传统的设备约束条件、其他的如人力的制约、突发情况产生时的处理方法等，因此在解决实际问题时，仍然有许多工作要做1990年后，遗传算法在各行各业中得到了广泛应用。如环境与资源配置，电子与电气工程，通信与网络，机器人，交通运输，机械设计与制造，管理工程，金融，航空航天，市政建设，以及科学研究等。同时遗传算

14、法也在求解生产计划问题中取得卓越的成就。本文综合研究基于擂台赛和聚集密度的多目标进化算法及实际生产情况，提出新的解决生产调度问题的方法。保留遗传算法的一系列优点，还具有收敛快、不容易陷入局部最优等独特的优点，因此可以将其有效的应用于求解生产调度问题。参考文献：1 郑金华，蒋浩用擂台赛法则构造多目标Pareto最优解集的方法J.软件学报,2007(6).2 郑金华多目标进化算法及其应用M.科学出版社,2007(2).3 崔逊学,李淼.多目标协调进化算法研究J.计算机学报,2001(9).蔡天鸣遗传算法在储货型生产企业制定生产计划中的应用J.科技天地,2008.4 陈国良，王煦法,庄镇泉,等.遗传

15、算法及其应用M.北京:人民邮电出版社,1996(3).金毅.生产计划的模糊方法与应用M.西安:陕西人民出版社,1997.孙棣华.解佳.赵敏求解生产批量计划问题的改进量子进化算法J.计算机集成制造系统2010(8).5 玄光男，程润伟.遗传算法与工程优化M.北京:清华大学出版社,2004.6 唐恒永赵传立.排序引论M.北京:科学出版社,2002.7 季宝慧，唐明.改进的蜜蜂进化型遗传算法在生产调度中的研究与应用M.大连:大连交通大学出版社,2010.李明.遗传算法的改进及其在优化问题中的应用研究D.吉林大学,2004.8 陈振同.基于改进遗传算法的车间调度问题研究与应用D.大连理工大学,2007

16、.9 BALLINGRICHARDJ.Paretosetsindecision-baseddesignJ.JournalofEngineeringValuationandCostAnalysis,2001(3).10 COELLOCOELLOCARLOSA,etal.ApplicationofMulti-ObjectiveEvolutionaryAlgorithms(AdvaneeInNaturalComputation,Vol.1)M.WorldScientificPublishingCo.PteLtd,2004.11 COELLOCOELLOCARLOSA,ALANDCHRISTIANSE

17、N.TwonewGA-basedmethodsformulti-objectiveoptimizationJ.CivilEngineeringSystems,2008(3).12 KURSAWEF.AVariantofEvolutionStrategiesforVectorOptimizationC.In:SchwefelHP,MannerR.ParallelProblemSolvingfromNature-PPSNI.Berlin:Springer-Verlag,2009.13 SCHAFFERJD.Multipleobjectiveoptimizationwithvectorevaluat

18、edgeneticalgorithmsA.Proceedingsof1stInternationalCongressonGeneticAlgorithmsC.Hillsdale,LawreneeErlbaum,NewYork,1985.14 GOLDBERGDE.GeneticAlgorithms:InSearch,OptimizationandMachineLearningM.NewYork:Addison2Wesley,1989.ApplicationofImprovedGeneticAlgorithmtoProductionPlanningAbstract:Thispaperputsthecrowding-densitytechnologyintothemulti-objectiveevolutionaryalgorithmbasedonarenaprinciple.Experiment