车间调度的混合遗传算法的设计.doc

大学本科生毕业论文摘 要车间作业调度问题（Job Shop Scheduling Problem）是一个著名的NP难题，具有很强的条件约束，当问题规模较大时很难找到全局最优解。因此作业车间调度是一类求解困难的组合优化问题。近几年各种智能计算方法逐渐被引入到作业调度问题中，如遗传算法、模拟退火算法、启发式算法等。如何有效的安排各零件的加工顺序将直接关系到生产效率,也是本文所要解决的问题之一。本文提出了实现车间调度的混合遗传算法的设计方案，把遗传算法与模拟退火算法相结合，充分发挥遗传算法良好的全局搜索能力和模拟退火算法有效避免陷入局部极小的特性，通过实验验证了基于混合算法的作业车间调度方法显著提高了搜索效率，GASA改进了收敛性能。最后，本文分析了混合遗传算法的优越性。通过VC仿真程序的模拟仿真，对比单纯遗传算法和模拟退火算法，分析了混合算法的高搜索效率，以及改进了的收敛性能！系统的运行结果满足了调度要求，进一步证明了混合遗传算法的有效性和实用性。源代码请联系本人。关键词:遗传算法;模拟退火算法;车间调度; 仿真；ABSTRACTJob Shop Scheduling Problems are known as one of the most difficult NP hard problems, having strict constraints and very difficult to find the global optimum.so JSSP is NP hard combinational optim ization problem.Many intelligent computation methods such as simulated Anneal Algorithm, Genetic Algorithm, heuristic algorithm, are introduced into scheduling problem in recent years.This paper proposes a hybrid genetic algorithm to solve scheduling problem. To combine the genetic algorithm and simulated annealing, it is using GA excellent whole search ability and simulated annealing which is efficient to avoid getting into part minimum . The result of the test shows the efficiency of search is increased and the convergence is improved in shop scheduling with GASA hybrid algorithm.The scheudling reuslt satisfies the requirements，which shows the availabilities of GASA further.Key words:Job shop scheduling; Genetic algorithm; Simulated annealing;Simulation;目 录第一章 绪论1.1 概述1.2 课题研究的目的、背景及意义1.3 国内外研究现状1.4 课题研究方法及实验设计第二章 车间调度问题简述2.1 车间调度问题描述2.2 车间调度问题的特点及分类2.3 Job shop和Flow shop调度问题2.4 本章小结第三章 遗传算法和模拟退火算法理论及实现技术3.1 遗传算法简介3.2 遗传算法基本流程3.3 遗传算法参数设计3.4 模拟退火算法简介3.5 模拟退火算法基本思想和步骤3.6 模拟退火算法关键参数和操作的设计3.7 本章小结第四章 混合遗传算法理论4.1 混合遗传算法的构造出发点4.2 混合遗传算法的流程和特点第五章 方案设计5.1 输入设计5.2 输出设计5.3 关键程序介绍第六章 仿真结果输出及对比分析6.1 6.2 6.3结论参考文献致谢第一章 绪论1.1 概述 优化技术是一种以数学为基础，用于求解各种工程问题优化解的应用技术，作为一个重要的科学分支一直受到人们的广泛重视，并在诸多工程领域得到迅速推广和应用，如系统控制、人工智能、模式识别、生产电镀、VLSI技术、计算机工程等等。实现生产过程的最优化，对提高生产效率、节省资源具有重要的作用。同时，优化方法的理论研究对改进算法性能、拓宽算法应用领域、完善算法体系同样具有重要作用。因此，优化理论和算法的研究是一个同时具有理论意义和应用价值的重要课题。 柔性制造系统是一类复杂的人造系统，具有复杂性、递阶结构、不确定性的、多目标、多约束、多资源相互协调等特点。鉴于其重要的应用价值和理论意义，相关的分析与控制的研究方法已经受到工业界和控制界的广泛关注。研究控制策略的目的是提高系统的性能，二系统分析的目的则是更好的优化和控制系统。制造系统的分析和控制方法，从理论体系上可分为运筹学方法、马尔科夫链、排队论、极大极小代数、摄动分析法、Petri网、自动机/形式语言和仿真方法等。它们涉及系统的逻辑层次、时间层次和随机层次，进而形成离散事件动态系统的理论框架。生产调度是制造系统的一个研究热点，也是理论研究中最为困难的问题之一。调度的任务是根据生产目标和约束，为每一个加工对象确定具体的加工路径、时间、机器和操作等。优良的调度策略对于提高生产系统的最优性、提高经济效益，有着极大的作用。目前，对调度理论地研究已经受到广泛地关注，并取得了较大的进展，但还很不成熟。如今，人们鉴于调度问题的约束性、非线性、多极小性、不确定性、大规模性、多目标性等复杂性，正努力研究和发展统计式全局搜索技术和人工智能的方法，例如模拟退火、遗传算法、禁忌搜索、进化规划、进化策略、神经网络方法、Lagrangian松弛方法和混沌优化等，而遗传算法则是其中研究及应用最广的一类优化算法。提高车间生产效率已成为各生产企业的研究重点之一。本文着眼于如何有效的安排各工件的加工顺序，以达到该批工件的总加工时间最短，提高生产效率。采用混合遗传算法对加工顺序进行优化求解，并针对不同规模进行模拟仿真，对比基本遗传算法和模拟退火算法，说明混合遗传算法的有效性和优越性。采用VC+6.0软件进行仿真。1.2 课题研究的目的、背景及意义 进入90年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题。尤其是遗传算法的应用研究显得格外活跃，不但它的应用领域扩大，而且利用遗传算法进行优化和规则学习的能力也显著提高，同时产业应用方面的研究也在摸索之中。此外一些新的理论和方法在应用研究中亦得到了迅速的发展，这些无疑均给遗传算法增添了新的活力。遗传算法的应用研究已从初期的组合优化求解扩展到了许多更新、更工程化的应用方面。1.3 国内外研究现状1967年，Holland的学生J.D.Bagley在博士论文中首次提出“遗传算法（Genetic Algorithms）”一词。此后，Holland指导学生完成了多篇有关遗传算法研究的论文。1971年，R.B.Hollstien在他的博士论文中首次把遗传算法用于函数优化。1975年是遗传算法研究历史上十分重要的一年。这一年Holland出版了他的著名专著自然系统和人工系统的自适应（Adaptation in Natural and Artificial Systems），这是第一本系统论述遗传算法的专著，因此有人把1975年作为遗传算法的诞生年。Holland在该书中系统地阐述了遗传算法的基本理论和方法，并提出了对遗传算法的理论研究和发展极其重要的模式理论（schema theory）。该理论首次确认了结构重组遗传操作对于获得隐并行性的重要性。同年，K.A.De Jong完成了他的博士论文一类遗传自适应系统的行为分析（An Analysis of the Behavior of a Class of Genetic Adaptive System）。该论文所做的研究工作，可看作是遗传算法发展进程中的一个里程碑，这是因为，他把Holland的模式理论与他的计算实验结合起来。尽管De Jong和Hollstien 一样主要侧重于函数优化的应用研究，但他将选择、交叉和变异操作进一步完善和系统化，同时又提出了诸如代沟（generation gap）等新的遗传操作技术。可以认为，De Jong的研究工作为遗传算法及其应用打下了坚实的基础，他所得出的许多结论，迄今仍具有普遍的指导意义。进入八十年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题。1985年，在美国召开了第一届遗传算法国际会议（International Conference on Genetic Algorithms ，ICGA），并且成立国际遗传算法学会（International Society of Genetic Algorithms ，ISGA），以后每两年举行一次。1989年，Holland的学生D.E.Goldberg出版了专著搜索、优化和机器学习中的遗传算法（Genetic Algorithms in Search , Optimization, and Machine Learning）。该书总结了遗传算法研究的主要成果，对遗传算法及其应用作了全面而系统的论述。同年，美国斯坦福大学的Koza基于自然选择原则创造性地提出了用层次化的计算机程序来表达问题的遗传程序设计( genetic programming, GP)方法，成功地解决了许多问题。 在欧洲，从1990年开始每隔一年举办一次Parallel Problem Solving from Nature 学术会议，其中遗传算法是会议主要内容之一。此外，以遗传算法的理论基础为中心的学术会议还有Foundations of Genetic Algorithms，该会也是从1990年开始隔年召开一次。这些国际会议论文，集中反映了遗传算法近些年来的最新发展和动向。1991年，L.Davis编辑出版了遗传算法手册（Handbook of Genetic Algorithms），其中包括了遗传算法在工程技术和社会生活中的大量应用实例。1992年，Koza发表了他的专著遗传程序设计:基于自然选择法则的计算机程序设计”。1994年，他又出版了遗传程序设计，第二册:可重用程序的自动发现深化了遗传程序设计的研究，使程序设计自动化展现了新局面。有关遗传算法的学术论文也不断在Artificial Intelligence、Machine Learning、Information science、Parallel Computing、Genetic Programming and Evoluable MachinesIEEE Transactions on Neural Networks,IEEE Transactions on Signal Processing等杂志上发表。1993年，MIT出版社创刊了新杂志Evolutionary Computation。1997年，IEEE又创刊了Transactions on Evolutionary Computation。Advanced Computational Intelligence杂志即将发刊，由模糊集合创始人L.A.Zadeh教授为名誉主编。目前，关于遗传算法研究的热潮仍在持续，越来越多的从事不同领域的研究人员已经或正在置身于有关遗传算法的研究或应用之中。1.4 课题研究方法及实验设计第二章 车间调度问题简述生产调度，即对生产过程进行作业计划，作为一个关键模块，是整个先进生产制造系统实现管理技术、运筹技术、自动化与计算机技术发展的核心。有效的调度方法和优化技术的研究与应用，是实现先进制造和提高生产效益的基础和关键。改善生产调度方案，可大大提高生产效益和资源利用率，进而增强企业的竞争能力。生产调度的研究主要可分为建模和调度算法设计两方面，它是一个交叉性研究领域，涉及运筹学、数学、计算机工程、控制工程、工业工程等多个学科。其中，建模主要研究调度模型、调度规则、目标函数等内数；本章主要介绍调度问题的描述、调度指标、调度表示、调度分类和特调、车间调度研究方法等等基本概念，为后续章节遗传算法设计作基础。2.1 车间调度问题描述调度问题通常指对生产过程的作业计划，譬如工件在机器上的加工顺序、生产批量的划分等。就生产方式而言，调度问题可分为开环车间（open shop）型和闭环车间（closed shop）型。开环调度问题，也称加工排序问题，它本质上只研究工件的加工顺序，即订单所要求的产品在所有机器上的加工排序，其中订单均来源于顾客，不考虑库存的设立。闭环调度问题除研究工件的加工顺序外，还涉及各产品批量大小的设置，即在满足生产工艺约束条件下寻找一个调度策略，使得所确定的生产批量和相应的加工顺序下的生产性能指标最优，其中顾客需求的产品均有库存提供，生产任务一般只有产品存储策略来决定。显然，闭环调度问题较开环调度问题要复杂。鉴于批量大小与排序间的偶合性，寻求批量大小和排序的有效同时处理方案很困难，目前处理闭环问题的常用近似方法是，首先确定量大小，然后确定加工顺序。一般车间调度问题可以描述为n个工件在m台机器上加工，一个工件分为k道工序，每道可以在若干台机器上加工。每一台机器在每个时间只能加工某个工件的某道工序，只能在上道工序加工完成才能开始下一道工序的加工，前者称为占用约束，后者称为顺序约束。对于m台机器（machine）M1,.,Mm对n个工件(job)J1,Jn的加工过程，所谓调度就是分配个工件在各机器上的加工时间。调度通常用甘特图（Gantt chart）表示，图2.1为4个工件、3台机器的面向机器的甘特图，而图2.2则是相应的面向工件的甘特图。 图2.1 4个工件、3台机器的面向机器的甘特图 图2.2 4个工件、3台机器的面向工件的甘特图2.2 车间调度问题的特点及分类主要特点有： 1.复杂车间中机器、工件、缓存搬运系统之间关系复杂，建模、计算，相互影响，又相互作用。每个工件之间又要考虑它的加工时间、完成时间以及安装时间和操作顺序等，因而相当复杂，调度问题往往是通过等式或不等式等约束条件来计算的。随着问题规模的加大，计算量也急剧加大，所以调度问题往往没有精确的解，通常是在解答过程中寻求其最优解； 2.动态随机性调度中存在很多随机性和不确定性。如工件的交货期变更，工件的加工完成时间，工件到达时间。另外一些突发事件也增加的调度的难度和随机性。如机器故障、作业交货期的变更等； 3.多约束性调度中受到很多约束条件的限制。如缓存容量、资源数量、工件到期时间与操作顺序等。此外，还有人为的附加因素，如机器负荷平衡等等约束条件； 4.多目标性调度的目标很多，目标之间往往又相互冲突。如基于作业交货期的目标、基于作业完成时间的目标、基于生产成本的目标等。按照不同的分类标准，可分为6种类型：(1)开环车间和闭环车间；(2)单台处理机、多台并行机、Job shop和Flow shop； (3)基于调度费用和调度性能的指标；(4)确定性调度、随机性调度；(5)静态调度、动态实时调度；(6)有序加工，无序加工。现代车间调度类型往往是Job shop, Flow shop型。2.3 Job shop和Flow shop调度问题Job Shop和Flow Shop调度问题是具有特殊工件特性和加工环境的最典型和最重要的调度问题，通常是特殊的开环调度问题。Job Shop和Flow Shop调度问题研究n个工件在m台机器上的加工过程，Oij表示第i个工件在第j 台机器上的操作，相应的操作时间pij为已知，事先给定各个工件在各机器上的加工次序（称为技术约束条件），要求确定与技术约束条件相容的各机器上所有工件的加工次序，使加工性能指标达到最优。若各工件的技术约束条件相同，一个Job Shop调度问题就转化为较为简单的Flow Shop 调度问题。进而，若各机器上各工件的加工次序也相同，则问题可以进一步转化为置换Flow Shop调度问题。在典型的Job Shop调度问题中，除技术约束外，通常还假定以下条件：（1）各工件经过其准备时间后即可开始加工；（2）每一时刻每台机器只能加工一个工件，且每个工件只能被一台机器所加工，同时加工过程为不间断，整个加工过程中机器均有效。（3）整个加工过程中 ，每个工件不能在同一台机器上加工多次；（4）各工件必须按照工艺路线指定的次序在机器上加工。（5）不考虑工件加工的优先权；（6）操作允许等待，即前一个操作为完成，则后面的操作需要等待；（7）所有机器处理的加工类型均不同；（8）除非特殊说明，工件的加工时间事先给定，且在整个加工过程中保持不变；（9）除非特殊说明，工件加工时间内包含加工设置时间 ；（10）除非特殊说明，缓冲区容量无限大。2.4 本章小结本章首先介绍了调度问题的基本概念和特点分类。鉴于本设计的问题属于Flow Shop调度问题，本章对其作了重点介绍。这位后续的设计作充分的准备。第三章 遗传算法和模拟退火算法理论及实现技术3.1 遗传算法简介 遗传算法（GA）是J.Holland于1975年受生物进化论的启发而提出的，GA的提出一定程度上解决了传统的基于符号处理机制的人工智能方法在知识表示、信息处理和解决组合爆炸等方面所遇到的困难，其自组织、自适应、自学习和群体进化能力使其适合于大规模复杂优化问题。GA是一种通用的优化算法，其编码技术和遗传操作比较简单，优化不受限制性条件的约束，而其最大的显著特点则是隐含并行性和全局解空间搜索。目前，随着计算机技术的发展，GA越来越得到人们的重视，并在机器学习、模式识别、图像处理、神经网络、优化控制、组合优化、VLSI设计、遗传学等领域得到了成功运用，尤其在生产调度领域。3.2 遗传算法基本流程标准遗传算法的主要步骤可描述如下：步骤1：随机产生初始种群，并评价各个体的适配值（fitness value）.步骤2：判断算法收敛准则是否满足。若满足则输出搜索结果；否则执行一下步骤。步骤3：根据适配值大小以一定的方式执行复制操作来从种群中选取两个个体。步骤4：若交叉概率Pc，则对选中个体执行交叉操作来产生两个临时个体；否则将选中父代个体作为临时个体。步骤5：按变异概率Pm对临时个体执行变异操作产生两个新个体。步骤6：返回步骤2。标准遗传算法的流程图描述。如下图所示：算法终止条件是否满足？执行选择操作从父代种群中选取两个个体NY输出优化结果Y对选中个体执行交叉产生两个临时个体对种群各个体进行评价随机产生N个个体构成初始种群对两个临时个体以变异概率pm执行变异操作产生两个新个体将所选中父代个体作为临时个体N交叉概率pc0.1图3.1 标准遗传算法流程框图3.3 遗传算法参数设计通常，遗传算法的设计是按照以下步骤进行的：（1）确定问题的编码方案。由于遗传算法通常不直接作用于问题的解空间，而是利用解的某种编码表示来进行进化，因此选择合理的编码机制对算法质量和效率有很大的影响。（2）确定适应度函数。由于遗传算法通常基于适应度函数进行遗传操作，因此，合理的适应度值能够将各个体的优劣程度得以体现，并适应算法的进化过程。（3）算法参数的选取。通常包括种群数目、交叉概率、进化代数等。（4）遗传算子的设计。通常包括初始化、选择、交叉、变异和替换操作等。（5）确定算法的终止条件。根据所求问题的性质在优化质量和效率方面作合理均衡或侧重。车间调度问题必须考虑加工工艺方面的影响，以下对加工工艺方面的约束作简单介绍。（1）每道工序在固定的机床上加工。（2）对于某一个工件，其后序工序没开始加工之前，其前边的工序不能开始加工。（3）每道工序一旦开始就不能停止。（4）同一时刻，每台机床上只能加工一道工序。（5）对于一台机床上的第n道工序没开始加工或每加工完成之前，则该机床上的第n+1道工序不能开始加工。（6）每一道工序要有明确的机床加工。（7）每个工件的第一道工序在第一台机床上加工，第二道工序在第二台机床上加工，第三道工序在第三台机床上加工。这种约束符合现行的加工装配型车间的准用机床工序集中的原则，以及流水线操作的要求，可以在一定程度上提高生产效率。遗传算法基本操作设计 算法的基本操作是算法的主体，也是在算法寻找最优解过程中执行操作所要遵守的基本准则，在程序设计中也是主要的工作，基本操作设计的正确性是算法可以找到局部最优解或者全局最优解的基本前提和保证，基本操作设计的合理性是程序设计顺利实现和减轻调试工作的基础，所以对于基本操作的设计也是整体方案设计的主体。（一） 编码设计遗传算法的特点之一是不对求解问题的决策变量直接进行操作，而是通过对个体编码进行交叉与变异的进化运算过程，不断搜索出适应度较高的新个体，最终寻求出问题的最优解或近似最优解。遗传算法不能直接处理问题的空间参数，必须把他们转换成遗传算法空间的由基因一定结构组成的染色体或个体，这一转换操作称为编码。应用遗传算法计算时，遇到的首要问题就是编码，它也可以说是计算的一个关键步骤。编码方案除了决定个体的染色体排列形式，还决定了个体从搜索空间的基因型转换到解空间的表现型时的解码方法。编码方法也影响到交叉算子、变异算子等遗传算子的运算方法。由此可见，编码方法在很大程度上决定了如何进行群体的遗传进化运算以及遗传进化运算的效率。一个好的编码方法，有可能使遗传运算和操作过程简单的执行。而一个差的编码方法，一方面影响运算精度和储存量，另一方面可能使交叉及变异等运算难以实现。如果编码方法和交叉处理不当，在遗传算法中因交叉而生成的个体有可能成为无用解或无效解。编码时常考虑以下三个问题：（1）完备性。对问题空间的任何一点有表达空间的一个点与之对应，即问题空间的所有可能解都能表示为所设计的基因编码形式。（2）健全性。对于表达空间中的任何一个点都有问题空间中的一个点与之对应，即任何一个基因编码都对应于一个可行解。（3）非冗余性。问题空间和表达空间一一对应。编码时也要注意一定的原则，具体如下 ：编码原则一：有意义基因块编码规则。应使用能易于产生于所求问题相关的低阶、短定义长度模式的变码方案。该编码原则理解为应使用易于生成适应度较高的个体编码方案。编码原则二：最小字符集编码原则。所设计的编码方案应采用最小字符集，以使问题得到自然的表示或描述。常用的编码方法有二进制编码、十进制编码。以下简要介绍各种编码方法的优缺点，并选出一种符合本次设计的编码方法。1二进制编码所谓的二进制编码，就是将优化的个体一系列的二进制符号0，1，所组成的二进制的符号集合0，1，也就是说，把问题空间的参数表示为基于字符集合0，1构成的字符串。每个的个体的表示成若干个0，1。这样的好处是：（1）编码、解码操作简单易行；（2）交叉、变异等遗传操作简单易行；（3）符合最小字符集编码原则；（4）便于利用模式定理对算法进行理论分析。2十进制编码 相比于二进制编码。十进制的编码方式更接近人的思考方式，更加直观，对于优化的结果表达清楚，而且字符串的长度要小的多，对于其他的算法的操作更加易于寻址。这里我们选择十进制编码作为我们的编码方式，原因有： (1)十进制更加符合人的思维习惯，可以给程序的调试工作减少麻烦； (2)可以不用解码的工作。正因为十进制的编码方式符合人的思考习惯，就可以把由程序输出的优化结果不做任何的转化呈现在屏幕上，这样既增加了结果的可读性又可以很好对优化的结果进行理论分析； (3)在编码的过程中就可以解决工序互不相同的问题，可以减少程序的工作量。对于本论文的目标来说，操作的对象是由工序组成的字符串，而对于一组工件来说，其某个工件的某个工序是固定的，也是唯一的。也就是说这样的十进制的编码设计可以在编码设计的阶段就解决了一个实际的生产约束，这样就可以避免在进行剔除重复元素的程序段，给程序的设计带来了方便。选择了十进制编码后，还有结合本次设计的具体问题找到一种复合本次设计的编码。车间调度问题可归结为直接编码和间接编码两种。直接编码将各调度作为状态，通过状态演化达到寻址目的，主要包括基于操作的编码、基于工件的编码、基于工件对关系的编码、基于完成时间的编码等。间接编码将一组工件的分配处理规则作为状态，算法优化的结果是一组最佳的分配规则序列，再由分配规则序列构造调度，主要包括基于优先权规则的编码、基于先后表的编码基于机器的编码等。（二）适应度函数设计在遗传算法中用适应度评估个体或解的优劣，这个评估个体适应度的函数称为适应度函数。适应度高的个体遗传到下一代的概率较大；而适应度低的个体遗传到下一代的概率相对小一些。因此，适应度函数的选取很重要，直接影响到遗传算法的收敛速度以及能否找到最优解。一般而言，适应度函数是由目标函数变换而成的。适应度函数设计主要满足以下条件：(1)单值、连续、非负最大化； (2)合理、一致性。要求适应度函数反映对应解的优劣程度，该条件往往很难衡量；(3)计算量小。适应度函数设计应尽可能简单，这样可以减少计算时间和空间上的复杂性，降低计算成本；(4)通用性强。适应度的设计对于某类具体问题，应尽可能通用，最好无需使用者改变适应度函数中的参数。从目前而言，这个条件应该是不属于强要求。以下是由目标函数转换到适应度函数一种常用方法：若目标函数为最小化问题，适应度函数可表示为： C0, C + f(x) 0 （317）在上式中，f(x)为目标函数。若目标函数为最大化问题适应度函数可表示为： C0, C- f(x) 0 （318）在上式中，f(x)为目标函数。（三）遗传算子设计遗传算子中包括以下三个算子：选择算子、交叉算子和变异算子，它们构成了遗传算法具备强大搜索能力的核心。下面针对本次设计对这三种算子分别设计。1. 选择算子设计适应度比例方法是目前遗传算法中最为基本也是最常用的选择方法。它也叫赌盘轮或蒙特卡罗选择。在该方法中各个个体的选择概率和其适应度值成正比。其具体执行过程如下：(1)计算出群体中所有个体的适应度的总和；(2)计算出每个个体相应的适应度的大小，即计算出比值，它即为各个个体在选择操作中被选中的概率；(3)最后再使用模拟轮盘赌操作，即产生0到1之间的随机数，来确定各个个体被选中的次数。2. 交叉算子设计交叉是基本遗传算法重要的操作，它是由旧的个体产生新的个体的过程。交叉算子主要包括单点交叉和两点交叉两种情况，现分别阐述如下：(1)单点交叉 在个体串中随机设定一个交叉点，实行交叉时，该点前或后的两个个体的部分结构进行交换，并生成两个新的个体，例如下图3.4示(空格为交叉位置)。父体A 1001 111 1001 000 子体 父体B 0011 000 0011 111 子体 图3.2 单点交叉(2)两点交叉两点交叉的操作与单点交叉类似，只是设置了两个交叉点(依然是随机设定)两个交叉点之间的码串相互交换例如下图3.5示(空格为交叉位置)。父体A 10 011 11 1011011 子体 父体B 00 110 00 0001100 子体 图3.3 两点交叉 本次设计选用单点交叉。3.变异算子变异算子的基本内容是对群体中的个体串的某些基因座上的基因值作变动。交叉之后子代经历的变异，实际上是子代基因按小概率扰动产生的变化，依据个体编码表示方法的不同，可以有以下的算法： 基本变异算子是指对群体中的个体码串随机挑选一个或多个基因并对这些基因座的基因值作变动(依变异概率作变动)，二值码串中基本变异操作如图3.6所示。变异前1001111 1101011 变异后 图3.4 两点交叉（四）遗传算法运行参数设计1. 种群大小M群体大小M 表示群体中所含个体的数量。当M取值较小时，可提高遗传算法的运行速度，但降低了群体的多样性，有可能会引起遗传算法的早熟现象；而当M 取值较大时，又会使得遗传算法的运行效率降低。经过参考文献，本文的种群大小M取值范围是20100。2. 交叉概率Pc交叉概率Pc用于控制交叉操作的频度。较大的交叉概率可增强遗传算法开辟新的搜索区域的能力，但群体中优良模式的个体会遭到破坏；若交叉概率取值太小，交叉产生新个体的速度较慢，从而会使搜索停滞不前。经过参考文献，本文的交叉概率Pc取值范围是0.40.99之间。3变异概率Pm变异概率Pm直接影响到算法的收敛性和最终解的性能。若变异概率取较大的值，会使得算法能够不断地搜索新的解空间，增加模式的多样性，但较大的变异概率会影响算法的收敛性；若取值太小，则变异操作产生的新个体的能力和抑制早熟现象的能力就会很差。经过参考文献，本文中变异概率Pm的取值范围是0.00010.1。4算法的终止条件给定一个最大的遗传进化代数，当达到此值时，就停止运行，并将当前群体中的最佳个体作为所求问题的最优解输出。经过参考文献本文的取值为1001000。3.4 模拟退火算法简介模拟退火算法(simulated annealing,简称SA)的思想最早是由Metrepolis等(1953)提出的，1983年Kirkpatrick等将其用于组合优化。SA算法是基于Mente Carlo迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法在某一初温下，伴随温度参数的不断下降，结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部优解能概率性的跳出并最终趋于全局最优。模拟退火算法是一种通用的优化算法，目前已在工程中得到了广泛应用，诸如VLSI、生产调度、控制工程、机器学习、神经网络、图像处理等领域。模拟退火算法最早是针对组合优化提出的，它的基本思想是出于物理退火过程。其目的在于：(1)为具有NP复杂性的问题提供有效的近似求解算法；(2)克服优化过程陷入局部最小；(3)克服初始值依赖性。3.5 模拟退火算法基本思想和步骤1983年Kirkpatrick等意识到组合优化与物理退火的相似性，并受到Metropolis准则的启迪，提出了模拟退火算法。归纳而言，SA算法是基于Monte Carlo迭代求解策略的一种随机寻优算法，其出发点是基于物理退火过程与组合优化之间的相似性，SA由某一较高初温开始，利用具有概率突跳特性的Metropolis抽样策略在解空间中进行随机搜索，伴随温度的不断下降重复抽样过程，最终得到问题的全局最优解。模拟退火算法的一般步骤可描述如下：(1) 给定初温t=t0，随机产生初始状态s=s0，令k=0；(2) Repeat:(2.1)Repeat:(2.1.1)产生新状态sj=Genete(s);(2.1.2)if min1,exp-(C(sj)-C(s)/tkrandom0,1 s=sj;(2.1.3)Until抽样稳定准则满足；(2.2)退温tk+1=update(tk)并令k=k+1;(3)Until算法终止准则满足；(4)输出算法搜索结果。上述模拟退火算法可用流程框图(如图3.5所示)直观描述。3.6 模拟退火算法关键参数和操作的设计从算法流程上看，模拟退火算法包括三函数两准则，即状态产生函数、状态接受函数、温度更新函数、内循环终止准则和外循环终止准则，这些环节的设计将决定SA算法的优化性能。此外，初温的选择对SA算法性能也有很大影响。1.状态产生函数设计状态产生函数(领域函数)的出发点应该是尽可能保证产生的候选解遍布全部解空间。通常，状态产生函数由两部分组成，即产生候选解的方式和候选解产生的概率分布。前者决定由当前解产生候选解的方式，后者决定在当前解产生的候选解中选择不同状态的概率。候选解的产生方式由问题的性质决定，通常在当前状态的邻域结构内以一定概率方式产生，而邻域函数和概率方式可以多样化设计，其中概率分布可以是均匀分布、正态分布、指数分布、柯西分布等。2.状态分布函数状态接受函数一般以概率的方式给出，不同接受函数的差别主要在于接受概率的形式不同。设计状态接受概率，应该遵循以下原则：(1) 在固定温度下，接受使目标函数值下降的候选解的概率要大于使目标函数值上升的候选解的概率；(2) 随温度的下降，接受使目标函数值上升的解的概率要逐渐减小；(3) 当温度趋于零时，只能接受目标函数值下降的解。 状态接受函数的引入是SA算法实现全局搜索的最关键的因素，但试验证明状态接受函数的具体形式对算法性能的影响不显著。因