用SFLA算法解决NW调度问题

目录TOC\o"1-5"\h\z\o"CurrentDocument"绪论 1组合优化问题 11.2调度问题 21.3本文结构 3\o"CurrentDocument"生产调度问题 4生产调度问题 42.2流水车间调度问题 8\o"CurrentDocument"蛙跳算法 10蛙跳算法简介 103.2蛙跳算法国内外研究情况 11蛙跳算法原理 123.4蛙跳算法的相关研究 153.5蛙跳算法的优缺点 17\o"CurrentDocument"4零等待策略（NW）的Flowshop调度问题 184.1零等待策略（NW）的Flowshop调度问题数学模型 18仿真分析 19\o"CurrentDocument"小结 30\o"CurrentDocument"5总结与展望 315.1本文总结 31\o"CurrentDocument"展望 31\o"CurrentDocument"参考文献 32致谢 错误！未定义书签。1绪论1.1组合优化问题由于科学技术突飞猛进地发展，随着人们在生活和工作中碰到各种各样的问题，而解决这些问题的方案又有许多，其中组合优化问题日益得到了国内外的广泛重视。组合优化问题是一种离散最优化问题，就是在给定约束条件下，求出使目标函数极小（或极大）的变量组合问题。优化是个古老的课题，它所研究的问题是在众多方案中寻找最优方案。长期以来，人们对优化问题进行探讨和研究。早在17世纪，英国Newton和德国Leibnitz发明的微积分就蕴含了优化的内容。而法国数学家Cauchy则首次采用梯度下降法解决无约束优化问题，后来针对约束优化问题又提出了Lagrange乘数法。人们关于优化问题的研究工作，随着历史的发展不断深入。但是，任何科学的进步都受到历史条件的限制，直到二十世纪四十年代，计算机的应用被大量运用于这个问题，至此，优化问题的研究不仅成为一种迫切需要，而且有了求解的有力工具。因此，优化理论和算法迅速发展起来，形成一门新的学科。至今已出现线性规划、整数规划、非线性规划、几何规划、动态规划、随机规划、网络流等许多分支。这些优化技术在实际应用中正发挥越来越大的作用。不过随着人类生存空间的扩大，以及认识世界和改造世界范围的拓宽，常规优化方法已经无法处理人们所面对的复杂问题，因此高效的优化算法成为科学工作者的研究目标之一[1]。优化方法涉及的工程领域很广，问题种类与性质繁多。归纳而言，最优化问题可以分为无约束问题与约束优化问题两大类。若决策变量x的解空间为Rn，则该问题为无约束最优化问题；若决策变量x的解空间受到一些约束函数的限制，则该问题被称为约束优化问题。按对象是连续状态还是离散状态，最优化问题也可分为函数优化问题和组合优化问题两大类，其中函数优化问题的对象是一定区域内的连续变量，而组合优化问题是解空间中的离散状态[1]。1.1.1无约束最优化与约束优化最优化问题的一般形式为minf（x） （1-1）其中s,t,xGX其中xgRn是决策变量，f（x）为目标函数，XuRn为约束集或可行域。特别地，如果约束集X=Rn，则最优化问题(1-1)称为无约束最优化问题；minf(x) (1-2)其中xeRn约束最优化问题通常写为minf(x)s,t,c(x)=0,ieE (1-3)ic(x)>0,ieIi这里E和I分别是等式约束的指标集和不等式约束的指标集，c(x)是约束函数。i当目标函数和约束函数均为线性函数时，我们把问题称为线性规划。当目标函数和约束函数中至少有一个是变量x的非线性函数时，则问题称为非线性规划。此外，根据决策变量、目标函数和要求的不同，最优化还被分成了整数规划、动态规划、网络规划、非光滑规划、随机规划、几何规划、多目标规划等若干个分支［1］。函数优化与组合优化函数优化问题通常可描述为：令S为Rn上的有界子集(即变量的定义域)，f:STR为n维实值函数，所谓函数f在S域上全局最小化就是寻求X eS使得min在S域上全局最小。典型的组合优化问题有旅行商问题(TravelingSalesmanProblem，TSP)、时间表问题(TimetablingProblem，TTP)、加工调度问题(SchedulingProblem，如Flow-Shop,Job-Shop)、0-1背包问题(KnapsackProblem)、装箱问题(BinPackingProblem)、图着色问题(GraphColoringProblem)>聚类问题(ClusteringProblem)等⑵。1.2调度问题调度问题(Scheduling)是组合优化问题的一种，它是根据生产目标和约束条件为每个加工对象确定具体的加工路径、时间、机器和操作方式等，在一定的约束条件下，合理地分配资源(Resource)完成一批给定的任务(Task)或作业(Job),获得某些性能指标(PerformanceCriterion)如完成时间或生产成本等的最优化。这里的资源是一种泛指，如人员、金钱、机器、工具、材料和能源等，而任务也可以有不同的解释，从制造系统的机器分配到计算机系统的信息处理等。在有些文献中调度问题也被称为排序问题(Sequencing)。但“排序”与“调度”存在一定的区别，以生产车间的机器加工为例，“排序”主要考虑的是所有机器上一个工件序列的分配和置换问题。而“调度”不仅考虑次序问题（包括被加工对象“工件”的次序和提供加工对象“机器”的次序），而且更重要的是对时间的分配。因此，有些学者认为“排序”是一种特殊的调度，“调度”一词也被更广泛的使用。生产调度是在生产任务和产品产量需求给定的情况下，确定较合理的生产方案，即在满足单元设备的处理能力和生产工艺要求的前提下，对给定的单元装置进行任务的分配或重分配，包括对各产品在生产时间和空间（生产流程线）的规划，使生产任务得以完成［1］。优良的调度对于增强企业的竞争能力、提高经济效益有着极大的作用。调度问题中一个非常典型的问题是FlowShop问题。自从Johnson在2003年发表了第一篇关于流水车间调度问题的文章以来，流水车间调度问题引起了许多学者的关注，提出了许多解决的方法，整数规划和分枝定界法是寻求最优解的常用方法，但流水车间调度问题是NP完全问题，对于一些大规模甚至中等规模的问题，整数规划和分枝定界法仍不是很有效。因此又相继提出一些启发式算法，最近一些智能搜索算法也被应用于解决FlowShop调度问题，如禁忌搜索方法、模拟退火算法、遗传算法、蚁群算法等。其中无等待流水线（NWFlowshop）调度问题是一个具有广泛应用背景和重要理论价值的组合优化问题，是许多实际生产调度过程的简化模型，广泛存在于炼钢、食品加工、化工和制药等工业领域。随着当代科技的进步，研究方向逐渐转变到如何使效率最大化，这就要建立在有效的理论基础上。本文通过蛙跳算法（SFLA）来解决零等待调度问题［2］。1.3本文结构本文第二章从总到分的介绍生产调度问题，分为流水线调度问题及零等待流水线调度问题；第三章介绍蛙跳算法概念、基本原理及相关研究情况，并为零等待调度问题编程进行铺垫，第四章为进NW的调度问题的编程及其仿真，包括编程内容，仿真结果等；第五章为全文的总结，包括完成全文的过程及自我感觉的不足之处等。2生产调度问题2.1生产调度问题2.1.1生产调度问题简介生产调度是指在满足约束的条件下确定工件的加工顺序使得目标函数达到最优。其中FlowShop调度问题是一种典型的组合优化问题，它具有很强的工程应用背景，其特点是单个工件在各个机器阶段上的加工顺序是相同的。该调度问题是一种典型的NP完全问题，随着问题规模的增大，解的规模将成指数增长。因此，开发高效的优化算法具有极其重要的理论和应用价值。求解这一问题的传统方法仅能处理小规模问题，并且存在计算量太大的缺点。另有一些启发式算法虽能达到快速求解，但是存在求解质量不高、对向题的依赖性过强以及一旦完成决策就无法再修改等问题［2］。调度是在满足某些约束（作业的先后关系、预定的完成时间、最早开始时间和资源能力等）的条件下对操作（作业）的排序，按照排序的次序给它们分配资源和时间，并且使某个执行目标达到最优（如总的执行时间、拖期时间和生产费用等）。调度理论源于对制造车间生产计划与控制的研究，从诞生之日起它就引起了管理科学家和应用数学家等的重视，人们在这个领域发表了大量的文献著作，还有一些学者从不同的广度和深度考察了调度理论的发展状况。经过几十年的研究与探索，调度理论逐渐发展成为一个比较完整的科学理论，在企业的生产中得到了一定程度的应用。由于企业车间的生产计划与控制问题在所有调度问题中最具典型性，所以对车间调度问题的研究一直在调度理论中占据主导地位。特别是近几年，更多领域的研究人员都对车间调度问题产生了浓厚的兴趣，他们各自用不同的技术和方法对这个问题进行了更为广泛、深入、细致的研究，取得了丰硕的成果。生产调度，即对生产过程进行作业计划，作为一个关键模块，是整个先进生产制造系统实现管理技术、运筹技术、优化技术、自动化与计算机技术发展的核心。有效的调度方法和优化技术的研究与应用，是实现先进制造和提高生产效益的基础和关键。改善生产调度方案，可大大提高生产效益和资源利用率，进而增强企业的竞争能力。生产调度问题是在一定的时间内，进行可用共享资源的分配和生产任务的排序，以满足某些指定的性能指标。简单地说，生产调度问题就是按时间分配资源来完成任务的问题。生产调度问题一般可以描述为：针对某项可分解的工作，在一定约束条件下，如何安排其组成部分（操作）所占有的资源、加工时间、先后顺序，以获得产品制造时间或成本等最优。从数学规划的角度来说。生产调度问题可表述为等式或不等式约束下，对目标函数所进行的优化。生产调度问题主要集中在车间的计划与调度方面。制造系统的生产调度是针对一项可分解的工作（如产品制造），探讨在尽可能满足约束条件（如交货期、工艺路线、资源情况）的前提下，通过下达生产指令，安排其组成部分（操作）使用哪些资源、其加工时间及加工的先后顺序，以获得产品制造时间或成本的最优化。在理论研究中，生产调度问题常被称为排序问题或资源分配问题。生产调度中涉及的资源包括：原料、设备（加工、存贮、运输）、人力、资金、能源等。资源的详细分配受到产品的生产工艺的限制。调度问题受到工厂管理方法的影响，调度问题的优化目标、优化策略随不同的管理方法而变化，因而其优化数学模型也不同。可以这样说：很难用一个生产环境的调度方案，去解决另一个生产环境的生产调度，因为几乎每一个生产环境都是唯一的。由于生产环境的动态性，生产领域知识的多样性，调度问题的复杂性，必须将人、数学方法和信息技术结合起来研究生产领域的管理调度问题[3]。生产调度问题研究近况调度问题的研究始于20世纪50年代，S.MJohnson提出了解决n/2/F/c和部分特殊max的n/3/F/c问题的优化算法，这是调度理论的开始；直至五十年代末期，许多研究成max果主要是针对规模较小的单机和简单的流水车间问题，提出了解析优化方法，研究范围较窄，但是这些研究却成为经典调度理论的基石。六十年代，多是利用混合或纯整数规划、动态规划和分枝定界法解决一些有代表性的问题口Story的研究。同时也有人开始尝试用启发式算法研究此问题，如Gavett提出的方法。六十年代末期，经典调度理论体系初步形成。七十年代，人们开始了算法复杂性的研究，多数调度问题被证明属于NP-完全问题或NP-难问题，难以找到多项式算法，因此开始关注启发式算法。Panwalkar总结和归纳出了113条调度规则，并对其进行了分类。七十年代末期，经典调度理论趋向成熟。八十年代初期，Stephen等从三个方面对调度进行了重新考察，对未来发展做了分析和预测，认为理论与实际的结合将会成为研究热点。这个富有挑战性的课题吸引了机械、计算机、管理等诸多领域的学者，许多跨学科的方法被应用到研究中。其中最引人注目的就是以Carnegie-Mellon大学的M.Fox为代表的学者们开展的基于约束传播的ISIS研究，它标志了人工智能开始真正应用于调度问题。八十年代后期，Giffler等人总结了生产调度的理论和实践方面的最新研究进展，从七个方面论述了生产调度的技术和方法，认为生产调度无论在理论还是实践上都已突破了传统界限[3]。九十年代至今，各种方法在生产调度问题的研究中得到了充分的发挥，同时新的研究手段层出不穷。纵观目前国内外的研究成果，从总体趋势上来讲，经典调度理论依然是调度理论不可动摇的基石，但智能调度理论己崭露头角，逐渐趋于成熟，且二者的融合也将会成为一种趋势。2.1.3生产调度问题的分类及特点车间调度问题的分类，根据研究的侧重点不同有多种分类方式，如按照资源约束种类和数量划分，分为单资源车间调度、双资源车间调度、多资源车间调度，本文研究的零等待策略的流水车间调度问题则属于按照零件和车间的构成划分：流水车间调度(Flowshop):在这种车间中，每个零件都有相同的加工路径。这样，机床设备的布局如同流水线一样，零件一次从流水线的一端浸入，最后从另一端流出。作业车间调度(Jobshop):在这种车间中，机床设备的布局可以是任意的，因此零件的加工路径也是任意的，并且各零件的工序内容和数量也是任意的。这是一种最一般的车间调度形式。开放式车间调度(Openshop):每个零件的工序之间的加工次序是任意的。零件的加工可以从任何一道工序开始，在任何一道工序结束。单车间调度(Singleshop):在这种车间中，每个零件只能有一道工序⑶。其他的分类方法还有按照零件的加工特点划分，例如分为静态车间调度、动态车间调度等，这里不再赘述。车间调度问题的特点具有建模的复杂性，计算的复杂性，动态的随机性，多约束性，多目标性。复杂性:车间中工件、机器、缓存和搬运系统之间相互影响、相互作用。每个工件要考虑它的加工时间、安装时间和操作顺序等因素，因而相当复杂。调度问题是在等式或不等式约束下求指标的优化，在计算量上往往是具有NP特性，随着问题规模的增大，其计算量急剧增加，使得一些常规的方法无能为力，对于这一点已经证明。随机性:在实际的作业车间调度系统中存在很多随机的和不确定的因素，环境是不断变化的，在运行过程中会遇到多种随机干扰，比如工件到达时间的不确定性、作业的加工时间也有一定的随机性，而且生产系统中常出现一些突发偶然事件，如设备的损坏、修复、作业交货期的改变等，故作业车间调度过程是一个动态的随机过程。多约束性:车间调度问题中资源的数量、缓存的容量、工件加工时间以及工件的操作顺序等都是约束。此外还有一些人为的因素，如要求各机器上的负荷要平衡等。多目标性:实际的车间调度问题是多目标的，而且这些目标之间往往是发生冲突的。调度目标分为三类:基于作业交货期的目标、基于作业完成时间的目标和基于生产成本的目标［3］。2.1.4生产调度问题的调度策略由于车间调度问题的复杂性，各种不同的具体问题往往有很多不同的解决方法，因此需要从策略上去考虑调度问题，以支持生产调度高层次的决策部分。并行和分布策略一般调度问题很复杂，一旦问题规模加大就更难求解，因此不少研究者提出并行或分解的策略来解决调度问题。多智能体系统的研究是目前分布式人工智能领域的研究热点。大量的研究表明多智能体系统特别适用于解决复杂问题，尤其是那些经典方法无法解决的单元间有大量交互作用的问题。由于调度问题的复杂性和并发性等特点，最近多智能体已在调度上得到了较多的应用。多智能体系统不但速度快、可靠性高、可扩展性强、能处理带有空间分布的问题。对不确定性数据和知识有较好的容错性；而且由于是高度模块化系统，因而能澄清概念和简化设计。因此它必将得到更加广泛的应用。分解或成组策略利用分解和成组调度策略可以大大降低问题的计算复杂性和规模，求得调度问题的较优解。成组技术基本思想是根据工件、机器等之间的相似性将它们分组，利用组内的相似性降低问题的计算复杂性和规模，求得调度问题的较优解，同时优化系统的一些性能指标。动态重调度策略由于实际的加工系统具有随机性和不确定性，特别在动态环境下，调度本身就是不断地动态重调度的过程。基于目前的研究，动态调度的触发方式主要有：周期调度、事件驱动调度、连续调度、以及周期与事件调度相结合的混合调度等。滚动优化的思想很早就被应用于生产调度。与常规调度方法相比，滚动调度可避免生产的大幅度波动，在滚动调度中，对某一些区间内的工件(工件窗口)进行调度，但按时间只对此区间内的部分工件进行实际加工，然后再向工件窗口中加入新工件来形成滚动。滚动调度不仅可以应付刑S中的不确定性和突发偶然事件，而且每次只对工件窗口内的工件进行调度，可使问题求解规模大大减小。(4)多目标决策实际调度问题往往是多目标的，如最短生产期、最大生产利润，而且这些目标往往相互冲突。对多目标优化问题，数学规划中的处理方法有约束法、评价函数法、功效函数法、分层序列法等。人机交互策略为了取得好的调度结果，并考虑实际调度中存在的各种复杂因素，往往需要好的人机交互策略去启发和利用调度决策者的经验和知识。大量的研究成功表明在目前的知识条件下人机交互策略是解决困难问题的一条有效途径［3］。

流水车间调度问题2.2.1流水车间调度问题的描述流水车间调度问题一般可以描述为n个工件要在m台机器上加工，每个工件需要经过m道工序，每道工序要求不同的机器。n个工件在m台机器上加工的顺序相同，工件i在机器m上的加工时间是给定的，设为t（i=1,2,...,n,j=1,2,...,m）。问题的目标是确定i,jn个工件在每台机器上的最优加工顺序，使最大流程时间达到最小。对该问题常常作如下假设：（1） 每个工件在机器上的加工顺序是给定的；（2） 每台机器同时只能加工一个工件；（3） 一个工件不能同时在不同机器上加工；（4） 工序不能预订；（5） 工序的准备时间与顺序无关，且包含在加工时间中；（6） 工件在每台机器上的加工顺序相同，且是确定的。令c（j,k）表示工件j在机器k上的加工完成时间，｛j,jj｝表示工件的调度，那i i 1 2n么，对于无限中间存储方式，n个工件、m台机器的流水车间调度问题的完工时间可表示为：c(j1,1)=tji1c(j,k)=c(j,k-1)+t11 jikik=2,...,mc(j,1)=1cc(j,1)=11-1 j.1ii=2,...,n+ti jikic(j,k)=max{c(+ti jikii i-12-1)2-2)2-3)最大流程时间为c=c2-1)2-2)2-3)最大流程时间为c=c（j,m），max n调度目标就是确定｛j,jj｝，1 2n使得c 最小［3］。max2.2.2流水车间调度问题的求解方法流水车间调度问题的求解方法很多，启发式算法比较常见。启发式算法（Heuristicalgorithm）是相对于最优算法提出的。一个问题的最优算法是求解该问题的最优解而启发式算法是在可接受费用内寻找最好的解，但不一定能保证所得解的可行性和最优性，甚至在多数情况下，无法阐述所得解同最优解的近似程度。事实上，在实际问题中，最优算法因问题的难度使其计算时问随问题规模的增加以指数速度增加，使人无法接受。这时只能通过启发式算法求得问题的一个可行解。启发式算法可定义为：一个基于直观或经验构造的算法，在可接受的花费（指计算时间、占用空间等）下，给出待解决组合优化问题每一个实例的一个可行解，该可行解与最优解的偏离程度不一定事先可以预料。33蛙跳算法3.1蛙跳算法简介蛙跳算法是新发展起来的一种启发式算法，它通过启发函数(某一数学函数)进行启发式搜索，从而找到问题的解。事实上，蛙跳算法结合了以遗传行为为基础的Memetic算法和以社会行为为基础的粒子群优化PSO算法的优点。Memetic算法Memetic算法是一种通过启发式搜索解决优化问题的群智能算法，受Dawkin提出的memeM念的启发而出现的。1989年，由Moscato第一次使用这种算法。"memetic"来自于单词"meme"，meme指的是寄存于人或动物的大脑中能指导他们的行为并能传播的信息。meme的内容，被称为memotype，类似于基因中的染色体。一个想法或信息直到它被重复或传播才能成为一个meme。所有可传播的知识都是memetic。这种算法和遗传算法相似，不同的是，在MAs中，组成染色体的元素被称为memes，而不是基因。Memetic算法的特征是所有的染色体和后代可以在进化之前通过局部搜索获得一些经验。这样，Memetic算法通常被描述为增加了局部搜索的遗传算法⑴。3.1.2粒子群算法粒子群优化(ParticleSwarmOptimize，PSO)算法由Kennedy和Eberhart于1995年提出的，是一种基于群智能(SwarmIntelligence)方法的演化计算技术。PSO算法通过模拟鸟群的捕食行为来实现优化问题的求解。首先在解空间内随机初始化乌群，鸟群中的每一只鸟称为“粒子”，这些“粒子”具有位置和速度两个特征，在解空间内以某种规律移动，经过若干次迭代后找到所求解问题的最优解。在每一次迭代中，粒子通过跟踪两个极值来更新自己的速度和位置。第一个是粒子本身的最优解p，另一个极值是整个粒子群best目前找到的最优解G。PSO的速度、位置算是表示如下:bestVk+1 Vk+1 k-1Vk+cRandii1()C—Xkii)+cRand2()Qk—Xki3-1)Xk+1=Xk+Vk+1

3-1)式中，Vk为粒子i在第k次迭代中的速度；Xk为粒子i在第k次迭代中的位置；Pki i i为粒子i的个体极值；Gk为在第k次迭代中的全局极值；Rand()为在区间［0,1］上的随机数;-为惯性权重；S是认知系数，调节向的飞行步长；c2是社会系数，调节向Gk的飞行步长。迭代过程中，粒子的速度和位置都限制在特定的范围内，同时Pk和Gk不i断更新，最后输出Gk就是全局最优解⑴。蛙跳算法国内外研究情况目前仅有很少的关于蛙跳算法的研究，相关的成果如下：2003年Eusuff和Lansey首次将这种算法用来解决管道网络扩充中的管道尺寸最小化问题，在SFLA基础上提出了一个计算模型SFLANET，并且为了评价该模型的性能在一些实例上进行了测试［4］。2005年Elbeltagi等在连续优化和离散优化方面将遗传算法、Memetic算法、微粒群算法、蚁群算法和蛙跳算法五种进化算法的模型和结果进行了比较［5］。实验结果表明：蛙跳算法在解决某些连续函数问题时成功率和收敛速度优于遗传算法，近似于粒子群算法［5］。2006年Eusuff等将发展了的蛙跳算法用于解决组合优化问题，通过具体应用得出：蛙跳算法是一种解决组合优化问题的有效工具，在收敛效果和速度上优于遗传算法［4］。2007年，AlirezaRahimi,Vahed等提出了混合多目标蛙跳算法HMOSFLA用于解决多目标的混合型装配线排序问题，且HMOSFLA的性能优于MOGA，这一优势在求解大型问题时尤为突出［4］。国内学者直到2007年才开始对蛙跳算法予以关注，相关成果更是很少，主要成果包括：2007年，王辉，钱锋讨论了四种群体智能优化算法一蚁群算法、微粒群算法、人工鱼群算法和混合蛙跳算法，对其算法的原理、发展及应用进行了综述。提出了群体智能优化算法统一框架模式，并对群体智能优化算法进一步发展进行了讨论［6］。2007年，李英海等针对蛙跳算法局部更新策略引起的更新操作前后个体空间位置变化较大，容易降低收敛速度这一问题，提出了一种基于阈值选择策略的改进混合蛙跳算法。通过不满足阈值条件的个体分量不予更新的策略，减少了个体空间差异，从而改善算法性能［7］。蛙跳算法是一种新兴的群智能算法，对于该算法的研究还处于非常初步的阶段，仅有极少的文献，不过已经显示出较大的潜力，存在很大的发展空间。适用范围。SFLA的应用仅在函数优化、聚类、组合优化、多目标优化方面有较少的应用，并且其应用大多数还和具体问题相关，仅停留在研究阶段，其它的很多应用还尚未开始。显然，SFLA不会仅仅局限于目前的这些领域。如果将SFLA引入机器学习、自动控制等领域，将大大地促进算法的研究和发展。数学基础。SFLA的有效性在一些实例和数值实验中得到证明，但并没有给出收敛性、收敛速度估计、分布性、多样性等方面的数学证明。虽然有些文献对收敛性等根据实验数据做了一些研究，但是目前其理论和数学基础的研究还很不够。算法收敛性以及算法本身的研究都需要在理论上进行更加深入的探索，仅仅依靠实验方法是不够的。参数的设计与选择。SFLA中的参数选择依赖于具体问题，设计合适的参数需要经过多次实验。研究如何选择和设计参数，使其减少对具体问题的依赖，也将大大促进SFLA的发展和应用。算法性能的改进。应该致力于补充和扩展SFLA与其他算法或技术的结合，克服SFLA相关的缺点。可以预见，随着SFLA和一些相关领域学科的发展，SFLA在不久的将来一定会大显身手，并有新的突破［1］。3.3蛙跳算法原理蛙跳算法基本概念青蛙(frog):又称为个体。等同于GA中的染色体，是生物遗传物质的主要载体。可以使用一组二进制0，1代码或实数表示。基因(Gene):基本的遗传物质的结构单位，若干个基因组成一个青蛙。种群(population)：—定数量的个体(frog)组成了种群。种群中数量的大小称之为种群规模。生物进化算法的基本思想是模拟生物由一个种群进化到一个新的种群的过程。⑷族群：由种群划分得到的一组个体(frog)。类似于一个国家中的民族，所有族群组成种群。适应度(fitness):用来描述个体(frog)对当前环境的适应程度。通常由数值表示的个体优劣程度。适应度一般就是要优化的目标函数，这个函数的设定决定了算法最终寻优结果的优劣。⑹分组(group):把种群以一定方式划分为族群。可以采用随机分组、循环分组等多种形式。选择：和GA不同，SFLA算法只考虑当前族群中适应度值最优的个体对族群中最差个体的更新，更新体现青蛙活动的方向性。更新:SFLA算法有特定的更新公式，替代了GA中的交叉、变异的工作。更新是SFLA算法的核心［8］。蛙跳算法原理描述图3-1是蛙跳算法的原理示意图［1］。

Sesuhspace：雪⑺gy切perfbiminglocai豳◎then\they口朗聽irfonratflnwi(h)othergroups.图3-1蛙跳算法的图解如图所示，在SFLA中，种群由很多青蛙组成，每只青蛙代表一个解。种群被分成了多个子群，每个子群包括一定数量的青蛙，称为一个memeplex。不同的memeplex可以看作是具有不同文化的青蛙群，分别执行局部搜索。在每个memeplex中，每只青蛙都有自己的想法，并且还受其它青蛙想法的影响，通过Memetic算法来进化发展。这样，经过一定的Memetic进化以及跳跃过程，这些想法思路就在各个memeplex中传播开来。然后，继续局部搜索和跳跃，直到收敛标准满足为止［1］。蛙跳算法（shuffledfrogleapingalgorithm,SFLA）是Eusuff等受生物模仿启发提出的一种基于群体协同搜索的模因算法。模因是一种通过感染人或动物的思想，进行传播、复制和交流的信息体。模因算法最显著特征是群体在进行传统进化过程之前，通过某种局部搜索方式，模因之间或内部可进行经验、知识和信息的共享和交流。因此，模因算法对传统遗传算法模型中的个体赋予了智能水平。SFLA的群体由互相能够交流的青蛙构成，每个青蛙可看作一个模因的载体，通过青蛙个体之间的交流可使算法执行模因进化。目前该算法已经在比例-积分-微分控制器控制等工程问题以及一些经典组合优化问题上取得成功应用［8］。算法首先初始化随机一组群体，然后计算每一个frog的适应度值，然后根据适应度值进行排序，排序后，根据它们的排列序号进行分组，分组采用余数相同原则进行分组，如共分三组，第一个放入一组，第二个放入第二组，第三个放入第三组，第四个放入第一组，以此类推。分组进行完成之后，每一组内进行更新，更新使用适应度值最高的frog通过更新公式对适应度值最低的frog进行更新，如果更新成功，则替换原有frog，迭代执行，否则随机生成一个新的frog。混合所有frog，重新分组，直到所有满足终止条件。蛙跳算法的核心步骤：（1） 局部搜索：局部搜索是在每个族群内部进行信息交互（更新公式），每次主要是两个青蛙个体不断的迭代进行信息交互（族群内最优个体和族群内最劣个体），使整个族群向着最优解的方向跳转，从而达到局部深度搜索（局部内考虑更多的可能解）的目的。（2） 全局信息交互：当局部搜索完成后，每一个青蛙个体会被重新计算适应度值，进而进行重新排序、分组。再次分组后每个族群中的个体均会发生改变，因此局部搜索中族群间可以进行信息交互，加快求解速度。局部搜索能够快速有效地在一个特定区域找寻极值，加快搜索进程；全局交互避免陷入局部最优解的问题［8］。混合蛙跳算法工作过程描述如下：随机生成含有f个青蛙的群体P={X,XX}，对于解为t维的问题，第i个青蛙的位置X=［x,x，…,x］•生成群12 F i i1i2 it体之后，计算每个青蛙位置的适应度值f（X），将其从大到小进行排序。将排序后的青i蛙按式（3-2）平均分配到m个族群，每个族群有n个青蛙，因此有F=mn.M={X ePII<l<n},1<i<m （3-2）i i+m（l—1）其中，m为第i个族群。族群中适应度函数值最小的青蛙位置用x表示，按（3-3）iw和式（3-4）更新。TOC\o"1-5"\h\zD=r（X—X） （3-3）swX=X+D,D<D<D （3-4）ww min max其中，X为当前族群适应度最佳的青蛙位置；r为（0,l］内的随机数；D为青蛙移动s距离；D和D分别为青蛙位置所允许移动距离的最大值和最小值。更新后若适应度maxmin值优于原适应度值，则用X'取代X；否则，用式（3-5）代替式（3-3）wwD=r（X—X） （3-5）bw其中，X为当前整个群体适应度最佳的青蛙位置，若更新后仍无改进，则随机生成一b行解代替X，在族群内重复此操作，知道设定的迭代次数。随后对所有族群的青蛙重w新混合并排序，更新群体最佳青蛙位置X，然后重新划分族群，进行局部深度搜索，b如此循环直到满足终止条件［4］。图3-2为蛙跳算法流程图。

开始构造下一彳弋的新种群停止条件满足确定种群大小Ftmemqitex的数量用，开始构造下一彳弋的新种群停止条件满足确定种群大小Ftmemqitex的数量用，毎组memeplex中最大迭代次数%,每组m询即T中青蛙的个数«青蛙在不同memeplex中跳跃：重新汇合、排序将尸只青蛙分别放■在m组iDiineplex中将所有奇睡袪适配值降序排列円箏每只育蛙的适配值用Memetic算法局部搜索＜A)初始化种群输出最优解片图3-2蛙跳算法流程图蛙跳算法的相关研究鉴于SFLA的优越性，SFLA已经广泛应用于许多自然科学与工程科学领域，显示出强大的优势和潜力。关于SFLA的相关研究已经涉及资源网络优化问题、连续优化问题、离散优化问题、聚类问题、流水车间调度问题、装配线排序问题、TSP问题以及参数调节问题等。3.4.1资源网络优化问题在资源网络优化方面，2003年Eusuff和Lanseyr将SFLA用于求解水资源网络的管径选择和管网扩张问题中。在该文中，解向量南表示管径类型的一串整数值构成。算法作为优化工具，采用成熟软件EPANET作为约束检验工具。通过与其他文献的求解结果相比较，作者展示了SFLA的优越性，给出了SFLA算法在求解这类问题时的适用参数组合［6］。连续优化问题2005年，Elbeltagi等人对SFLA算法、元算法(MA)、粒子群算法(PSO)、蚁群算法(AntColonyOptimization，ACA)及遗传算法(GA)进行了比较，详细描述了各种算法，给出了各个算法的简单实现过程的伪码及合理化的参数组合。采用F8和F10这两个具有连续变量的函数，评价了SFLA算法的计算性能，结果显示SFLA在F10函数的求解方面性能不够理想，在F8函数的求解上性能优于GA算法，与PSO算法的性能相近［9］。离散优化问题2005年，Elbeltagi等人对SFLA算法、元算法(MA)、粒子群算法(PSO)、蚁群算法(AntColonyOptimization，AC0)及遗传算法(GA)采用建筑业的项目管理问题对5种算法的求解结果进行了比较，结果显示SFLA求解效果不够理想，仅优于GA算法。2006年，Eusuff等人采用5个标准离散函数测试了SFLA算法的求解效果，系统地测试并给出了算法的最佳参数组合。之后，他们将SFLA算法用于求解地表水模型标定问题.并通过与GA相比较来说明SFLA算法的有效性。2007年。李英海等人对SFLA算法进行了改进，通过概率的方式来决定是否改进最差蛙的位置。通过F7等4个参数的计算结果，表明改进后的算法在求解效果方面得到了改善和提高［6］。聚类问题2008年，Yang等采用SFLA与GA的混合算法求解了基于聚类的基因选择问题，取得了较好的结果。2009年，Amili等人采用SFLA求解了K均值聚类问题。通过多组数据集对算法的求解效果进行了测试，并与其他4种算法进行了比较.结果显示SFLA算法的目标函数值(距离矩阵中所有数值和的最小值)明显优于其他算法的目标值。此外，他们还系统地测试了算法参数组合，给出了算法的最佳参数组合［8］。其他优化问题2006年，Elbehairy等人求解了桥面修复决策问题，比较了SFLA算法和GA算法在该问题上的求解性能。结果表明，在各自的合理化参数组合下，SFLA和GA都能达到令人满意的求解效果，但总体看来，SFLA效果略好于GA算法。2007年。Rahimi，Vahed等人采用SFLA求解了多目标混合模型装配线排序问题。通过将产品类型与数字进行对应，从而将解向量按整数串形式进行编码。通过将算法与其他3种不同的GA算法进行比较，表明SFLA算法得到了更多的Pareto解。错误率比其他3个GA算法更小，并且Pareto解集的多样性更好。2008年,Luo等人采用SFLA求解了TSP问题,通过与TSPLIB中的标准测试问题的结果进行比较，证明了SFLA算法的优越性.得到了新的6组改进解。2008年，Huynh采用混合SFLA算法求解了多变量PID控制器参数调节问题.结果证明混合SFLA算法的控制能力更强，控制效果比GA等算法更好。2009年，Rahimi,Vahed等人求解了具有双准则的带缓冲区流水车间调度问题。采用Pareto解的数和错误率作为评价标准，将混合SFLA与2个GA算法进行了比较，结果表明SFLA算法在多目标问题求解上有优越性［8］。蛙跳算法的优缺点蛙跳算法的优点：较少的参数。相对于其它进化算法，参数较少。计算速度快。由于在SFLA算法中采用了分组策略，每一组frog可以搜寻一个方向，并由一直带头frog指引方向(更新策略)，使得算法执行过程中能在局部快速找到最优解。全局搜索。由于SFLA算法执行中会采用分组策略，每组进行局部深度搜索，多组并行进行全局搜索，并在执行一定次数的局部搜索后，进行全局性的个体融合，然后再次分组，实现不同组间的信息交互，达到快速全局搜索的目的。每次迭代过程中，所有的frog均可以通过融合操作达到多次选择参与进化的目的。蛙跳算法的缺点：作为进化算法，蛙跳算法也存在着诸多进化算法的缺点，即算法的执行过程中含有参数，算法时间复杂度较高，最优解不唯一等。综上所述，蛙跳算法是一种寻优能力很强的算法，能够快速求解优化问题，避免了传统进化算法易陷入局部最优解的问题［8］。4零等待策略（NW）的Flowshop调度问题4.1零等待策略（NW）的Flowshop调度问题数学模型在间歇过程中，有些化学反应经常要求中间产物在某个设备处理完毕后，立即转移到下一个加工设备中，不能延误或者中间存储，这时需要采用零等待存储策略。在典型的间歇过程中，如染料生产中，一些活性染料和还原染料的生产过程会生成不稳定的中间产物，为了保证中间产物的反应活性和操作安全，反应通常在氮气保护或低温下进行，而设立中间储罐会使生产的保持变得相当困难，因而每一步操作完成后，都要立刻转移到下游设备中进行下一步操作；又如许多生化制品的生产需要在无菌、无氧的条件下进行，中间存储对于保持适宜的生产条件是很不利的；在钢铁加工过程中，加热过的金属在降温前需要经过一系列不间断的操作过程，以防止其成品的组分中存在缺陷；在塑料加工行业也存在同样的过程，它在不同的加工单元中加工必须是连续的，从而防止其老化。生产过程中采用零等待ZW存储策略的另一个原因是中间储罐会增加设备的投资，增加过程控制的难度，因此这种操作方式在生产中被广泛应用。Flowshop调度问题可以这样描述:有n个产品需要加工；可供选用的设备单元有m个，第i个被加工的产品在第j个设备上需要的加工时间为T，它包括装配时间、传输ij时间、卸载时间、加工时间以及清洗时间等；每个产品的加工工序都相同，并且以相同的次序在各设备上加工；过程按零等待方式进行，即一批产品在设备j加工完毕之后，必须立即转移到下一个加工设备j+1中去；定义S和C分别表示产品i在设备j上的开ij ij始加工时间和完工时间，S.和T分别是产品i的最后一道工序的开始加工时间和处理时ieie间，以最小化总加工周期为调度目标。首先作如下假设:（1） 所有产品在每个加工单元上的操作次序相同，即为排序；（2） 产品之间没有优先性；（3） 一个设备不能同时处理多种产品，一种产品不能同时为多个设备处理；（4） 对最终的产品有足够的存储容量；（5） 产品的加工过程中不允许中断。上面的定义和假设可以用下面的数学模型表示min Z=max （S+T）}（4-1）ie ies.t. S=S +T（4-2）ij i（j-1） i（j-1）S>S、+T,、 iGN,jGMij （i-1）j （i-1）j（4-3）S>0（4-4）ij

式（4-2）表示加工产品的顺序约束，产品i的第j道工序必须在第j-1道工序完成后才能开始，即任何一道工序的加工开始时间必须大于等于该产品前一道工序的结束时间；式（4-3）表示加工产品的资源约束，一批产品的生产必须在前一批产品在某一处理单元处理完毕后才能进入该处理单元，即任一时刻该处理单元不能同时处理两个产品；式（4-4）说明产品的开始加工时间大于或等于零。由于产品的加工方式是零等待，在第一个加工单元上的产品的开始操作时间需要适当的延迟。令加工顺序中产品s和产品t相邻，k为加工单元上处理产品的排序号，贝U两个产品的延迟时间为：d=max<m-11d=max<m-110,乙T—乙T4-5)stm-2,Mstst)=)=min(Z)。min（makespan4.2仿真分析基于蛙跳算法解决零等待Flowshop问题，算法用Matlab语言进行编程，仿真7个工件在7台机床上进行加工的Flowshop调度问题。进行三次基于不同蛙跳算法设定值的仿真。表4.1是产品的加工时间。表4.1产品的加工时间JobUnit12345671692310832630258147255258158214214147753806347547578557885226994231966962145863568775158325530785325565412679687421423689689830275422055789633258001204.2.1示例1基于上述工件与机床设定并采用上述算法并基于模型使用Matlab软件进行第一次仿真，取种群分组数M_pop=30，每组青蛙包含的个数N_frog=30，组内迭代数Ni_MAX=20,最大步长S_max=5,种群总进化代数MAXGEN=100,进行寻求最优解仿真，结果如图4-1。7600 1 1 1 1 1 1 1 1 1 0 10 20 30 40 50 60 70 80 90 100Generation图4-1最优解遗传演化曲线1图4-1为最优解的遗传演化曲线，横轴为演化代数，即演化时间，纵轴为目标函数值，优化目标为minZ=maX5+I"。图中有曲线折线两条线，上方曲线为种群内的平均值曲线，下方红线为种群的最优值曲线，每代中子群最优化后种群最优化，随着代数的不断增加，目标函数收敛，并达到最优质且稳定，证明了算法的收敛及有效性。该图的设定值所仿真出的最优排序为(2,4,5,3,7,6,1)，所对应的甘特图如图4-2，所模拟问题为零等待的加工序列，所以由图看出，同一编号的工件在不同机床上加工时，每道工序的结束时间和下一道工序的开始时间一定是一样的，就做到了零等待加工，所以在同一机床上看，加工完一件工件后，会有一定的时间间隔，那么这个时间间隔的大小就是通过蛙跳算法的模拟计算出来的一个最优解。005①ELLmugOESOL冲r~—r--609566ZS6舄T-S9二图4-2最优调度结果Gantt图示寸 0 3euii|oe[A|BuisseooJd66ZS0蜀G0品S0IN吕EUJO窗吕H-西r--UJL昼壬g9SMOS00匚INong±±ns(D」6u亏p£oso£示例2基于上述工件与机床设定并采用上述算法并基于模型使用Matlab软件进行第二次仿真，取种群分组数M_pop=40,每组青蛙包含的个数N_frog=30,组内迭代数Ni_MAX=20,最大步长S_max=5,种群总进化代数MAXGEN=100,进行寻求最优解仿真，结果如图4-3。图4-3最优解遗传演化曲线2该图所对应的最优排序为(4,2,7,6,3,5,1),由图看出,同一编号的工件在不同机床上加工时,每道工序的结束时间和下一道工序的开始时间一定是一样的,做到零等待加工,所以在同一机床上看,加工完一件工件后,有一定的时间间隔,通过蛙跳算法则体现在族群内优化与族群间优化的先后过程,并得出最终优化结果中。按照本示例的参数设定,可以看出,在第30代左右时达到了最小时间并趋于稳定,所求目标时间函数大概在7800左右。示例2与示例1的不同之处在于,示例2的红色最优值曲线较为稳定,优化过程有效性很高。按照此顺序进行加工,其模拟的甘特图如图4-4：茗幕冨爲asgCN色ucmgEMEgmssgoesOS窗9£S*995旳S気ZZZOE9£S#6尊LG韶gsissfc比£2专EoezLS2S0O0gLssc?□0oogo

QC3

寸G6LF30INSLt.CM寸匚窝C50On对 m eeuiqoeiAiGuisseooJd示例3基于上述工件与机床设定并采用上述算法并基于模型使用Matlab软件进行第二次仿真，取种群分组数M_pop=30,每组青蛙包含的个数N_frog=30,组内迭代数Ni_MAX=20,最大步长S_max=3,种群总进化代数MAXGEN=100,进行寻求最优解仿真，结果如图4-5。图4-5最优解遗传演化曲线3该图所对应的最优排序为(4,5,3,7,6,1,2),同样的,按照示例参数设定,仿真出的零等待机床为前一工件的加工完成时间一定等于同一工件的下一步骤开始时间,满足零等待加工的要求,那么由示例3的设定仿真看出,同样在第30代左右求出最优解,即30代左右达到最小加工时间,最小加工时间大约为7900左右。精确的时间则由甘特图可以看出,最小加工时间为7895,最后完成工件为2号。按照此顺序进行加工,其模拟的甘特图如图4-6：rd

uJ京心」g-npo-IZos心£6S3窝石OOZST-S9OLis卜烹9L6Z6CD£nrtLi』E06ZSZOE盟4-6最优调度结果Gantt图示63L 寸M06Z雷胃吕刘SE00S0009002①一U___L口匚一留山30」丄0SP000E00009;Jon cmauiqoeiAjGuissaoojd000L示例4基于上述工件与机床设定并采用上述算法并基于模型使用Matlab软件进行第二次仿真，取种群分组数M_pop=40,每组青蛙包含的个数N_frog=40,组内迭代数Ni_MAX=20,最大步长S_max=3,种群总进化代数MAXGEN=100,进行寻求最优解仿真，结果如图4-7。9009000008600840082008000托肚 1 1 1 1 1 1 1 1 1 0 10 20 30 40 50 60 70 80 90 100Generation图4-7最优解遗传演化曲线4该图所对应的最优排序为(2,4,5,6,7,3,1)，同样的，按照示例参数设定，仿真出的零等待机床为前一工件的加工完成时间一定等于同一工件的下一步骤开始时间，满足零等待加工的要求，那么看到示例4的改变参数将族群分组数增加到了40，每组青蛙包含的个数同时增加到40，经过优化得到的最优曲线却在40代左右趋于平稳，于预期的分组数越多达到稳定越快不符合，下面将继续研究。精确的时间则由甘特图可以看出，最小加工时间为7705，最后完成工件为1号。按照此顺序进行加工，其模拟的甘特图如图4-8：

±±nsal6u=npollos£1寸曇F=留UJUJv.r'-xBUJL茁1g■y■J①E±±nsal6u=npollos£1寸曇F=留UJUJv.r'-xBUJL茁1g■y■J①E匚b匚一ssOJlJEdSS吕导吕届Z g M7) 寸 n CMeumoeiA]BuissesoJd图4-8最优调度结果Gantt图示

示例5基于上述工件与机床设定并采用上述算法并基于模型使用Matlab软件进行第二次仿真，取种群分组数M_pop=20,每组青蛙包含的个数N_frog=20,组内迭代数Ni_MAX=20,最大步长S_max=3,种群总进化代数MAXGEN=150,进行寻求最优解仿真，结果如图4-9。图4-9最优解遗传演化曲线5该图所对应的最优排序同样为(2,4,5,6,7,3,1),同样的,按照示例参数设定,仿真出的零等待机床为前一工件的加工完成时间一定等于同一工件的下一步骤开始时间,满足零等待加工的要求,那么看到示例4的改变参数将族群分组数恢复20,每组青蛙包含的个数同样恢复20,经过优化得到的最优曲线却在25代左右趋于平稳,由此和前面的示例进行对比,发现种群进化代数越大,得到优化成功的速度越快,此结论符合理论,证实了算法的有效性,正确性。精确的时间则由甘特图可以看出,最小加工时间为7705,最后完成工件为1号。按照此顺序进行加工,其模拟的甘特图如图4-10：

giY■jSS①giY■jSS①6wcrlsclJ30」d§s§seuiL|3e|/\|Buissesojd图4-9最优解遗传演化曲线5从以上的所有仿真中可以看出，当我们确定了一套机床去解决一系列工件的加工问题后，如果需要做到零等待的加工，采用蛙跳算法来解决，我们的目的是让工作时间最小化。由三次仿真看出，当示例1和示例2分别设定了较大的种群分组数和较大的最大步长时，目标函数时间较短，结果较精确，而示例3将种群分组和最大步长减小时，模拟出的结果不是很精确。结果在30代左右趋于最优，所耗时间最短，当种群分组数和种群总进化代数增加时，会明显提高搜索的效率，使趋于稳定的代数提前，但同时，如果增大了每组青蛙的数量时，由于搜索的可能性加多，效率会减低，但不同的参数和设定值的组合还是会对排序结果造成更多的影响。4.3小结本章为解决NW调度问题提供了具体仿真研究，首先建立了零等待调度问题的数学模型，并用Matlab对蛙跳算法及NW调度问题进行编程，考虑到零等待调度的特点，建立模型后以最小化生产周期为目标函数进行优化，从而模拟出用于实际生产的甘特图，得出了较满意的结果，验证了编程与所建模型的可操作行和有效性。5总结与展望5.1本文总结本文研究运用蛙跳算法解决实际操作中的零等待流水线调度问题，本文分别介绍了调度问题和蛙跳算法，并将两者结合进行仿真实验解决问题。零等待流水线调度问题属于组合优化问题的一种，本文在介绍组合优化问题的基础上，介绍调度问题的类型，特点，研究近况等，并分层详细引出零等待调度问题。对蛙跳算法的介绍注重概念和原理的介绍，探讨了在零等待流水车间问题的应用，设计出该问题的算法，过程较易于实现。通过仿真实验的过程，基本证明了编程的正确性和有效性，仿真的结果也证明了所建模型的正确性和算法的有效性。蛙跳算法在处理一类组合优化问题上参数较少，采用了分组策略，使得计算速度较快，而且在分组局部深度搜索的基础上进行全局搜索，实现了不同组之间的信息交互，具有准确快速的特点，较适合解决此类问题，但也存在待改进的地方，比如在仿真过程中含有参数，对参数的修改导致最优解不唯一等问题。在完成论文的过程中我自身也存在很多不足之处，在建模与编程方面依然存在相当的不足，对整个调度问题的研究方向了解很不全面，在今后的生活中希望能弥补这方面的不足。5.2展望随着科学技术水平的飞速发展，人们已将视线逐渐关注于如何提高生产效率、如何将理论最优化的应用在实际生产中，Flowshop问题渐渐得到相当的重视。实际问题往往相当复杂，未来的研究定将在实际的应用中建立更加精确的模型，对工件加工的零等待调度问题和如何最大化的缩小工时，提高工作效率，将会是未来研究的一大方向。同时，在理论方面，蛙跳算法作为一种最优化算法，其自身也将不断优化，并有可能衍生出更加适合具体操作问题的算法，理论将对具体问题有具体的分析，匹配度更高，从而更有效率的解决生产生活中的具体问题，为生产的运转提供更多的支持，带来更多的便利。参考文献⑴王亚敏.蛙跳算法的研究与应用.[D]北京工业大学，硕士论文⑵徐震浩，顾幸生.不确定条件下具有零等待的流水车间免疫调度算法.J]计算机集成制造系统，2004，10-13⑶张松艳，基于遗传算法的FlowShop调度的研究与应用.[D]浙江工业大学,2008.M．M．Eusuff，K．E．Lansey．Optimizationofwaterdistributionnetworkdesignusingtheshuffledfrogleapingalgorithm．WaterResourPlanManage，2003，129(3)：210-225，Rippin，D.W.T.，1993，Batchprocesssystemengineeringretrospectiveandprospectivereview，ComputChemEng，17:S1E．Elbeltagi，T．Hegazy，D．Grierson．Comparisonamongfiveevolutionary_basedoptimizationalgorithm.AdvancedEngineeringInformatics，2005，19(1):43-53⑹王辉，钱锋.群体智能优化算法.[J]化工自动化及仪表，2007,34(5):7-13.⑺李英海，周建中•一种基于选择策略的改进混合蛙跳算法 .[J]计算机工程与应用.2007，43(35):19-21．⑻骆剑平，李霞.求解TSP的改进混合蛙跳算法.[J]深圳大学学报理工版,2010:27-28肖力.改进免疫算法在Flowshop调度上的应用.[J]计算机仿真,2008,03:13-17昊华丽,汪玉春，陈坤明,等•基于混合蛙跳算法的成品油管网优化设计.[J]石油工程建设,2008(1):14-16高尚，杨静字.群智能算法及其应用.[D]中国水利水电出版社,2006:2-4王亚敏,冀俊忠,潘全科.基于离散蛙跳算法的零空闲流水线调度问题求解.北京工业大学学报,2010,36:124-130常俊林,邵慧鹤.两机零等待流水车间调度问题的启发式算法.2005,07:13-16ALLAHVERDIT,GUPTAJ,