2022年遗传算法的作业调度优化分析研究 .pdf

《2022年遗传算法的作业调度优化分析研究 .pdf》由会员分享，可在线阅读，更多相关《2022年遗传算法的作业调度优化分析研究 .pdf（39页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1 / 39 摘要在现今的经济全球化制造时代，客户化的产品需求要求更短的产品生命周期。现代制造业与服务业呈现融合的状态。车间作业调度技术是生产管理技术的核心技术，直接关系到企业产品以及服务的质量。有效的车间作业调度技术，可以增强车间资源优、化配置能力、提高企业的生产效率、减少生产损耗，使企业在经济全球化的竞争中处于领先地位。现代制造业的生产特点是品种多、批量小( 甚至是单件生产 ，而车间资源的有限性制约着能否有效利用车间现有资源完成任务，以最快的速度响应市场需求。调度的任务是根据生产目标和约束，为每个加工对象确定具体的加工路线、时间、机器和操作等。优良的调度策略对于提高生产系统的最优性、提高经

2、济效益都有着极大的作用。作业车间调度问题是一个典型的NP hard问题，是最困难的组合优化问题之一。本文主要研究了制造车间作业调度问题。本文系统地介绍了车间作业调度理论及其发展状况、用于作业车间调度理论的优化算法及其特点；针对生产过程的作业调度，描述了调度的分类以及常规调度方法；建立了制造车间调度模型；利用染色体编码方法和遗传算子，用遗传算法解决该调度问题。此外，用Matlab 强大的数值计算能力和众多库函数来编写算法，通过仿真实例对算法的求解效果进行了测试。实例证明，该程序算法结果较好，能充分利用设备资源组织生产，对于车间的实际生产具有较强的指导意义。关键词：作业调度，遗传算法，MATLAB

3、精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 39 页1 / 39 Job Scheduling OptimizationBased on Genetic AlgorithmABSTRACT In the manufacturing era of economic globalization, demand for our products of customer requires shorter product life cycle. Modern manufacturing and service rendered to the

4、state of integration. The job-shop scheduling technology is the core technology of the production and management technology, is directly related to the quality of enterprise products and services. Effective job shop scheduling techniques can enhance the workshop resources, optimal allocation of capa

5、city, improve production efficiency, reduce production losses, so that enterprises can locate in the central positionin the competition of economic globalization. The feature ofmodern manufacturing sector is variety, small batch (or even a single piece production. The limited resources of the worksh

6、op restricting the effective use of existing workshop resources to complete the task to meet market demand in the fastest pace. The scheduling task is to determine the specific processing route, time, machinery and operation according to production goals and constraints for each processing object. G

7、ood scheduling strategy has a great role for the optimal production system, improve economic efficiency. The job shop scheduling problem is a typical NP-hard problem,and is the most difficult combinatorial optimization problems. In this paper, we study manufacturing job shop scheduling problem. The

8、paper systematically introduces the job shop scheduling theory and its development, optimization algorithm for job shop scheduling theory and its characteristics。contrary to job scheduling of the production process, we describes the classification of scheduling and conventional scheduling methods 。

9、we have established a manufacturing shop scheduling model。 we use chromosome coding, genetic operators and genetic algorithm to solve the scheduling problem. In addition, using the Matlab numerical computing power and number of library functions to write the algorithm to test the effects of algorith

10、m by simulation examples. Examples show that The program algorithm is better, equipment of organizing production resource utilization, The algorithm has a strong guiding significance for the actual production of the workshop. 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 39 页2 / 39 Keywords:

11、Job Scheduling, Genetic Algorithm, MATLAB精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 39 页I / 39 目录1 绪论 11.1 课题研究背景及意义11.1.1 问题的提出 11.1.2 课题的现实与理论意义11.2 国内外研究现状综述31.3 本文的研究内容 42 车间作业调度算法52.1 调度问题特点与分类52.2 车间作业调度问题描述52.3 调度问题优化算法 63 求解调度问题的遗传算法103.1 遗传算法求解调度问题的优越性103.2 遗传算法简介 113.2.1 遗传算法概述 1

12、13.2.2 遗传算法基本过程123.2.3 遗传算法执行策略154 车间作业调度的建模174.1 车间作业调度问题描述174.2 遗传算法设计思想 184.2.1 编码 184.2.2 生成初始种群 194.2.3 适应度函数 194.2.4 选择算子 194.2.5 交叉算子 194.2.6 变异算子 194.3 遗传算法流程 195 用 Matlab 实现模拟作业调度225.1 程序设计思想及伪代码22精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 39 页II / 39 5.2 分析结果的可行性、运行时间以及目标函数值265.2

13、.1 仿真输出结果 265.2.2 分析结果 276 结论与展望 30参考文献 32致谢 34精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 39 页1 / 39 1 绪论1.1 课题研究背景及意义1.1.1 问题的提出随着科学技术、经济全球化和信息技术的迅猛发展，生产企业面临着多变的商业环境1。现代科学技术的快速发展和客户对产品的个性化需求越来越高，这给传统制造加工业带来了巨大的挑战和机遇。原来简单的、局部的、常规的计划和仅凭经验的管理已经不能满足现代化的要求。当前的机械制造企业采用多元化、多品种、小批量、高柔性生产方式来适应激烈的市

14、场竞争。制造业的经营重心已从企业规模和产品成本转移到用户需求和上市时间、产品质量、制造成本和售后服务。制造过程中的生产管理与调度是保证生产质量和生产效率的关键，先进的生产管理与调度技术能够快速响应顾客需求变化的多样性。为了保证生产的高效稳定运行，以获得最大的经济效益，企业管理者必须能根据市场上原料供应和产品需求的变化进行经营决策和组织生产，能利用现有的资源做出最有效的调度方案，使企业生产获得最大的综合经济效益。21世纪企业的先进制造模式是完全面向顾客，敏捷制造是综合了JIT的求解目标是寻求某种最优策略，找到的调度方案能将加工作业安排到车间制造机器上，并且使加工作业能够精选学习资料 - - -

15、- - - - - - 名师归纳总结 - - - - - - -第 6 页，共 39 页2 / 39 最高效的完成。每个作业都由一些工序组成，而每个工序则必须由指定的机器加工处理。一个调度方案就是按照作业内在逻辑的先后顺序条件将所有工序安排到机器上的一种方案。以前大部分企业主要依靠经验丰富的工人手工安排调度计划，在调度问题比较简单的情况下还是可行的。然而，当前的产品的加工工艺复杂度相当高，在调度任务规模较大且动态多变的环境中，手工调度表现的非常低效甚至无法实现调度。1973年harrington博士提出计算机制造集成制造CIM 的概念， CIM是一种组织、管理与运行企业生产的新哲理，它借助计算

16、机软件、硬件，综合运用现代管理技术、制造技术、信息技术、自动化技术、系统工程技术，将企业生产过程中有关人、技术、经营管理三要素及其信息流与物质流有机地集成并优化运行34。计算机集成制造系统 (CIMS能给企业带来巨大的综合经济效益，因此国内、外各大中型企业都研究与实施计算机集成制造系统。作为实施 CIMS工程中的一个重要组成部分，生产计划与调度系统是计算机集成制造系统功能结构模型中不可缺少的一个层次。当前在自动化程度较高的生产系统中，使生产过程合理、高效运行的调度问题变得非常复杂，需要建立有效的计算机调度控制策略、因此调度问题的研究具有重要的现实意义。由于大量的调度问题是NP完全问题13，近几

17、年各种智能计算方法逐渐被引入到调度问题中，如遗传算法、模拟退火算法等，但是目前尚无有效的求解策略，因此调度问题的研究也具有重要的理论意义5。车间作业调度是一个交叉的研究领域，以数学为基础，涉及运筹学、计算机、控制工程和工业设计等多门学科。具体就是针对一项可分析的工作如产品制造），探讨尽可能满足约束条件 如交货期、工艺路线、资源情况）的前提下，通过下达生产指令，安排其组成部分 操作哪些资源）、其加工时间及加工的先后顺序，以达到合理利用产品制造资源，获得产品制造时间和成本的最优化14，提高企业经济效益的目的。制造系统生产管理的核心就是车间生产调度，生产管理任务顺利实施与完成，最终要靠合理的生产调度

18、来保证。它研究的是如何合理地配置加工过程的各种资源，减少零件在加工过程中的各种浪费，从而提高设备利用率和生产率，降低生产成本。因此，合理的生产调度是生产系统的高效运行的前提，生产调度可以保证:生产计划的有效实施；高效低耗地使用生产资源；均衡生产，减少在制品的资金占用；缩短产品生产周期、确保产品交货期、降低生产成本，以适应多变的市场需求。生产调度对企业来说精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 39 页3 / 39 是至关重要的，在品种多、中小批量生产环境下的主生产调度问题更加复杂和重要12。1.2 国内外研究现状综述车间作业调度

19、问题是一个经典而又传统的问题，对于它的研究始于20世纪50年代。1954年，Johnson 对两台机床 Flow-Shop型调度问题进行了研究后，提出了解决车间调度部分特殊问题的优化算法，代表理论研究的开始。60-70年代都是利用混合或纯整数规划、动态规划和分枝定界法解决一些有代表性的问题，并开始重视调度复杂性的研究。由于车间调度问题的复杂性，各种不同的具体问题往往有不同的解决方法。大量的研究促使车间调度领域取得了丰硕的成果，产生了很多重要的调度方法。随着70年代后期调度理论研究的深入及各种交叉学科的发展，又涌现出了许多新的车间调度理论与方法，如：基于运筹学OR）方法6、基于控制的方法、基于

20、DEDS的概念， Koza成功地将他提出的遗传编程方法应用到了人工智能、机器学习、符号处理等方面，进一步证明了遗传算法在解决NP问题方面的有效性11。国内对于车间调度问题的研究起步比较晚，基本上是靠调度人员的经验进行车间作业分配和调度。随着遗传算法在作业调度方面的应用，国内也掀起了一股应用遗传算法研究车间作业调度问题的热潮。目前,研究工作主要集中在清华大学等CIMS(Computer Integrated Manufacturing System 国家重点实验室，这些实验室的系统精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 39 页4

21、 / 39 开发基本上还处于试用阶段，距离开发出成熟的软件系统还有很长一段距离，因此还需要投入大量的人力物力进行该方面的研究。1.3 本文的研究内容本文针对先进制造环境下车间管理与调度的特点，分析了车间作业调度的特点，给出了遗传算法求解车间作业调度的过程。通过研究与分析车间作业调度系统，给出了调度的数学模型，运用Matlab遗传算法工具箱进行了仿真调度，并分析了结果。本文主要分五章，具体安排如下：第一章说明了课题的提出背景和研究意义，讨论了车间调度的国内外研究现状，最后给出了本文的研究内容和文章的结构安排。第二章详细阐述了车间作业调度问题，分析了调度模型及模型描述，总结了车间调度的求解方法。第

22、三章简要说明了遗传算法的产生、发展、特点及操作流程。重点研究了遗传算法在车间作业调度优化中的操作过程，包括了编码方式、种群大小、交叉方式与概率、变异方法与概率等参数的选择。第四章将实际的车间作业问题抽象成数学模型，并且设计遗传算法的基本算子以及操作。第五章运用 Matlab遗传算法工具箱，通过编码实现模拟作业调度。并且分析结果的可行性，运行时间以及目标值。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 39 页5 / 39 2 车间作业调度算法2.1 调度问题特点与分类调度问题的主要特点有 : (1建模、计算复杂性。车间中工件、机器、操

23、作人员和搬运系统之间相互影响、相互制约。每个工件又要考虑它的加工时间、安装时间和操作顺序等因素，因而相当复杂，调度问题往往是通过等式或不等式等约束条件来计算的，属于典型的NP-hard问题。随着问题规模的加大，计算量也急剧加工，所以调度问题往往没有精确的解，通常是在解答过程中寻求其最优解。在现有计算条件下，一般优化方法对于车间调度问题是低效甚至是无能为力的。(2动态随机性调度中存在很多随机性和不确定性。如机器故障、作业交货期的变更，如工件到达时间的不确定性，实际工件的加工时间也有一定的随机性。如机器故障、紧急任务插入、作业交货期的变更等一些突发事件也增加了调度的难度和随机性。(3多约束性调度中

24、受到很多约束条件的限制。车间的生产能力不仅会受到机床的制约，还会受到工人和辅助工具的制约，各道工序的先后关系不能颠倒，如缓存容量、资源数量、工件到期时间与操作顺序等也是制约因素。此外，还有人为的附加因素，如机器负荷平衡等等约束条件。(4多目标性调度的目标很多，目标之间往往又相互冲突。如基于作业交货期的目标、基于作业完成时间的目标、基于生产成本的目标等。按照不同的分类标准，可分为6 种类型 :(l开环车间和闭环车间。(2单台处理机、多台并行机、 Jobshop 和 Flowshop。(3基于调度费用和调度性能的指标。(4确定性调度、随机性调度。(5静态调度、动态事实调度。(6 有序加工，无序加工

25、。现代车间调度类型往往是Job-shop 、Flow-shop型。2.2 车间作业调度问题描述一般车间调度问题可以描述为:n 个工件在 m 台机器上加工，每个工件分为k 道工序，每道工序可在不同的机器上加工。每一台机器在每个时间只能加工某个工件的精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页，共 39 页6 / 39 某道工序，只能在上道工序加工完成才能开始下一道工序的加工，前者称为占用约束，后者称为顺序约束。调度的结果就是确定决策方案，决策内容包括分配决策(工件的加工顺序 和时间决策 (工件各工序的加工时间以及路径决策 (工件工序的加工

26、设备的分配 。生产车间出现调度问题主要原因是生产资源受到了制约。车间调度的问题是多个工件在有限的机器上加工，每台机器在切换不同的工件加工时又需要一定的生产加工准备时间。切换加工的次数越多越有利于减少工件的库存，但导致生产率的下降。如果车间有足够多的机床设备和其它生产资源分配给每个工件或每条工艺加工路线，那么一切都会井然有序，也就不存在调度问题。但是，对于企业主来说，这样必定会造成资源浪费和制造成本的增加，于是出现了工件和相应的工序数量多于生产资源的情况，也就出现了车间调度问题。因此，需要在库存成本与切换加工次数频率之间寻求一个动态的平衡。生产的柔性体现在设备的使用和设备的安排两个方面，设备使用

27、的柔性是指设备可用于多个零件的多道工序加工，设备安排的柔性是指工件的设备加工路径，而不是固定或预先确定的。具有可选的路径，可以通过将若干设备组作为一条或者多条生产线加工一种工件，使得该工件的生产率最大。典型的车间调度问题包括一个要完成的作业集(工件集 ，每个作业由一个操作集(工序集 组成，各操作的加工需要生产资源(机器、人员、刀具和辅助资源，并且必须按一些可行的工艺次序进行加工。车间调度就是对一个可用的加工机床集在时间和空间上进行加工任务集分配，以达到生产性能指标最优化。每台机床可加工工件的若干操作，并且在不同的机床上能加工的操作集可以不同。调度的目标是将作业合理地安排到各机床以及合理地使用其

28、它生产资源，并合理安排作业的加工次序和加工时间，使约束条件被满足，同时优化其中的一些生产性能指标。2.3 调度问题优化算法目前的车间调度问题的算法研究有很多，归纳起来主要有: 1）确定性最优化方法该方法主要通过对车间调度问题建立一个数学模型，采用基于枚举思想的分枝定界或动态规划法进行求解，分枝定界法有很多，其主要不同点在于分枝规则、定界机制和上界的产生等三个方面的差异。这类方法从理论上来说是能求得最优解，但通常精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 39 页7 / 39 由于计算复杂性原因，不能获得真正的实用。采用数学规划的方

29、法，表达清晰，易于在计算机上求解，但生产环境具有很多不确定的因素，存在建模不确定性和求解空间太大，造成计算困难，特别是不能反映特定调度领域的自然结构，所以很难应用经验知识去处理调度问题。采用数学规划的方法大致可以分为三类：简单规则、复合规则、启发式规则。，其本质是给每一个生产任务和操作，并赋予优先级，优先级高的生产任务和操作优先考虑。这类方法因调度规则易于实现，计算复杂度低，能够用于动态实时调度系统中，许多年来一直受到广泛关注和研究，并不断涌现许多新的调度规则。如作业的平均等待时间、机床的平均利用率、作业总加工时间等。，根据系统当时所处的属性转台，决定采取何种规则(策略，确定或选择活动发生的顺

30、序和时间，即所谓的状态指导的智能调度方法。缺乏理论意义。b应用仿真进行生产调度的费用很高。c仿真的准确性很大程度受编程人员的判断和技巧的限制。5）基于 DEDS 的解读模型方法现实中的制造系统往往是离散事件系统，因此可以用研究离散事件系统解读模型和方法探讨车间调度问题，诸如排队论、极大极小代数模型、Petri 网等，。比如，精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共 39 页8 / 39 Petri 网作为一种图形建模工具可以形象地表示和分析FMS节点语义的单义性，使得所携带的系统信息量不够丰富。 2重用性差。 Petri 网是基

31、于 FMS 中作业的加工流程建模，当作业需求或工艺稍微变动，必须改模型结构。3很难对高级的调度规则建模。6）启发式图搜索法在人工智能中启发式图搜索法是图搜索的重要策略之一，在启发式图搜索法中最引人注目的 A* 算法，在图搜索过程中A* 算法能够通过选择合适的评价函数寻找达到目标结点的最佳路径。在调度问题的离散图模型基础上，启发式图搜索法在调度领域得到应用。对于表述为整数规划的调度问题，最初采用分枝界定法，而后其他的启发式图搜索法也被应用于解决调度问题。该方法主要需要解决搜索效率和降低内存使用问题，对大规模的问题需进一步探讨。7）模拟退火模拟退火法 最优解。模拟退火法的改进算法有加温退火法、记忆

32、退火法。模拟退火法可以用于具有最小MakesPan指标的 FlowShop 排序问题。由于模拟退火法能以一定的概率接受差的能量值，因而有可能跳出局部极小，但它的收敛速度较慢，很难用于实时动态调度环境。8）禁忌搜索法对于复杂的组合优化问题，禁忌搜索也是一种通过领域搜索以获取最优解的方法，Gfover 首次叙述了它的基本原理。该方法已经用于解决now-shop调度问题。 是一种模拟人脑神经系统的结构和功能，运用大量的处理部件，经广泛互连而组成的网络系统。搜索网络Hopfield）模型可以求解各种有约束的优化问题，随机Hopfield 也可以用于解决 job-shop的调度问题。松弛算法LR 算法由

33、于其在可行的时间里能对复杂的规划问题提供较好的次优解，并能对解的次优性进行定量评估，近年来已成为解决复杂生产调度问题的一种重要方法。但精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 13 页，共 39 页9 / 39 同时 LR 算法的对偶问题存在搜索效率低，可行调度的构造有待于进一步研究等问题。由于调度问题的复杂性，其研究策略主要形成了以下几种：分解与成组策略：利用分解生产计划或GT 的调度策略可以大大降低问题的计算复杂性和规模，求得调度问题的较优解，同时优化系统的一些性能指标。实时或动态重调度策略：车间制造过程的随机性、不确定性需要不断地进行重

34、调度，以处理突发的事件。基于目前的研究，对于动态调度的具体策略有:周期调度，连续调度，事件驱动调度，周期与事件驱动混合调度，周期与连续调度混合的策略等。生产计划与调度集成策略：生产计划、调度的集成研究具有全局优化的特征，也符合先进制造模式的思想。多目标权衡调度策略：实际调度问题往往是多目标的，而这些目标往往相互冲突。对此类多目标优化问题，常用数学规划中的约束法、评价函数法、分层序列法、功效函数法等。随着各种特殊调度问题的攻克和新方法、新设备的出现，作业车间调度研究正在向 动 态 、 敏 捷 、 多 重 入 、 多 资 源 、 智 能 化 的 方 向 发 展 。精选学习资料 - - - - -

35、- - - - 名师归纳总结 - - - - - - -第 14 页，共 39 页10 / 39 3 求解调度问题的遗传算法3.1 遗传算法求解调度问题的优越性遗传算法 搜索过程不直接作用在变量上，而是在参数集进行了编码的个体。(2搜索过程是从一组解迭代到另一组解，采用同时处理群体中多个个体的方法，降低了陷入局部最优解的可能性，并易于并行化。这使的遗传算法能以较少的计精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 15 页，共 39 页11 / 39 算获得较大的收益。(3遗传算法属于一种自适应概率搜索技术，其选择、交叉、变异等运算都是以一种概率的

36、方式来进行的，从而增加了其搜索过程的灵活性。采用概率的变迁规则来指导搜索方向，而不采用确定性搜索规则。(4对搜索空间没有任何特殊要求(如连通性、凸性等，只利用适应性信息，不需要导数等其他辅助信息，适应范围更广。遗传算法的自组织、自适应和自学习性(智能性 决定遗传算法可求解复杂问题。(5黑箱式结构。应用遗传算法时，根据具体问题的特性，进行编码与适应度设计之后，其余操作按常规算子自动运行即可，只等最后输出最优解个体，而不必关心求解的实际过程，所以遗传算法非常便于处理那些输入输出之间因果关系复杂的问题。基于遗传算法以上的特点，本文选用遗传算法作为求解优化问题的有效方法。3.2 遗传算法简介3.2.1

37、 遗传算法概述遗传算法是基于自然选择，在计算机上模拟生物进化机制的寻优搜索算法。由于遗传算法是自然遗传学与计算机科学相互结合渗透的产物，因此在遗传算法中借用了许多自然进化的概念。这些概念如下所示：1. 串String）：串是个体 Individual）的形式，在算法中为字符串，并且对应于遗传学中的染色体 Chromosome）。2. 群体Population）：一定数量的个体组成了群体，或叫种群。串是群体中的元素。3. 群体规模 Population Size）：群体中个体的数目成为群体个数，也称为群体规模或群体大小。4. 基因Gene）：基因是串中的元素，基因用于表示个体的特征。例如，有一个

38、串 S = 1001，则其中的元素1，0，0，1 分别称为基因。它们的值称为等位基因Alleles）。5. 串结构空间SS：在串中，基因任意组合所构成的串的集合。基因操作是在串结构空间中进行的。串结构空间对应于遗传学中的基因型Genotype）的集合。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 16 页，共 39 页12 / 39 6. 参数空间 SP：这是串空间在物理系统中的映射，它对应于遗传学中的表现型Phenotype ）的集合。7. 适应度 ：以一定的概率从种群中选择若干个体的操作。10.交叉 (crossover ：有性生殖生物在繁殖

39、下一代时两个同源染色体之间通过交叉而重组，即在两个染色体的某一相同位置处DNA 被切断，其前后两串分别交叉组合形成两个新的染色体。在遗传算法中为通过交配原则产生一组新解的过程。11.变异(Mutation：在细胞进行复制时可能以很小的概率产生某些复制差错，从而使 DNA 发生某种变异，产生新的染色体，这些新的染色体表现出新的性状。3.2.2 遗传算法基本过程遗传进化开始于随机选择遗传种群，然后通过应用遗传算子，即繁殖算子，交叉算子和变异算子朝着优化的方向进化。下面对关键参数与操作的设计做简单介绍。编码将问题的潜在解用一些参数表示，这些参数(基因排列在一起形成一个特定的编码(染色体 ，代表一个个

40、体，从而将问题的状态空间与遗传算法的码空间相对应，这很大程度上依赖于问题的性质，并将影响遗传操作的设计。针对优化问题的编码技术主要有二进制编码、十进制编码、实数编码等。二进制编码将问题的解用一个二进制0 和 1 字符串来表示，十进制编码将问题的解用一个十进制串来表示。实数编码将问题的解用一个实数来表示。实数编码解决了二进制和十进制编码对算法精度和存储量的影响，同时便于优化中引入问题的相关信息，譬如梯度信息。实数编码直接在解的表现型上进行遗传操作，目前在高维复杂优化问题中得到广泛应用，并取得了较好效果。鉴于组合优化问题本身的性质，其编码方式需要特殊设计。适值函数精选学习资料 - - - - -

41、- - - - 名师归纳总结 - - - - - - -第 17 页，共 39 页13 / 39 即个体空间 S到正实数空间的映射，适值函数f 为f:S R+遗传算法在搜索进化过程中一般不需要其它外部信息，仅用适应度函数值来评估个体或解的优劣，并作为以后遗传操作的依据。根据求解问题特性来定义反应个体对问题环境适应能力和优劣程度的测定函数。选择选择即是在一个种群中选择一个个体，它是随机映射Ts:SNS选择操作的目的是为了避免当前群体中有效基因的损失，使高性能的个体得以更大的概率生存，从而提高全局收敛性和计算效率。选择操作按照个体的适值进行，适值高的个体拥有更多的被选中机会，因而有更大的存活概率，

42、并将其优良特性传递给后代。通常有以下的算法可供选择: 轮盘赌选择 (roulette wheel selection 记种群规模为 n，个体 Vi 的适值为 (fvi，则个体 Vi 被选择的概率为然后，根据这些概率构造一个转轮，旋转转轮n 次，每次选一个染色体加入新的种群。随机遍历抽样 (stoehastic universal sampling 。局部选择 (local selection。截断选择 (truncation selection。锦标赛选择 (tournament selection 。交叉交叉算子是母体空间到个体空间的映射，记作Tc:S2S交叉是最主要的遗传运算，它同时对两个

43、染色体操作，交叉操作用于结合来自父染色体和母染色体的特征来产生新的子个体，在解空间中进行有效搜索，同时降低对有效模式的破坏概率。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 18 页，共 39 页14 / 39 点式交叉算子分为单点交叉和多点交叉。单点交叉即首先在双亲的染色体上随机地选一个交叉位置，将交换位置的右段互相交换，从而形成两个新的后代。实数编码遗传算法的交叉操作类似于二进制编码遗传算法。以下以离散交叉为例介绍实数编码的交叉方式。为了便于解释，下面设解向量s1= (v1，vm和 s1=( v12），v22），vm是两个父解向量， sz=

44、s1s2，sm和 sw=( s1，s2，sn是通过杂交获得的两个后代。与二进制编码单点交叉不同在于交换的对象的差异，前者是二进制串，后者是实空间的向量。如若选择交换第k 个分量以后的所有分量，则两个后代为sz =( v1，vk1），vk+12），vm sw =( v1，vk2），vk+11），vm 组合优化中的置换编码遗传算法通常采用部分映射交叉、次序交叉、循环交叉、基于位置的交叉，群交叉等操作。变异变异是一种基本运算，它在染色体上自发地产生随机的变化。一种简单的变异方法是替换一个或多个基因。在遗传算法中，变异可以提供初始种群中不含有的基因，或找回选择过程中丢失的基因，为种群提供新的内容。Vl

45、=l0010011在给定点变异后变为 :V1*=10011011 在遗传操作中需注意的几点问题: 1. 参数及其选取种群规模记为Pop_Size ，即种群中个体 (染色体 的个数。种群规模选择较大时，可以同时处理更多的解，因而容易找到全局最优解，其缺点是增加了每次迭代所需要的时间。迭代代数，即算法进化代数，代数的大小直接关系到解的质量和计算速度。叉率 (记为 Pc定义为各代中交叉产生的后代数与种群中的个体数(Pop_Size的比。较高的交叉率可达到更大的解空间，但会因搜索不必要的解空间而耗费大量的计算时间，从而降低停在非最优解上的机会。变异率 (记为 Pm定义为种群中变异基因数中的百分比。变异

46、率控制了新基因导入种群的比例。若变异率太低，一些有用的基因就不能进入选择，若太高，既随机的精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 19 页，共 39 页15 / 39 变化太多，那么后代就可能失去双亲继承下来的好特性，这样算法就会失去从过去的搜索中学习的能力。2. 终止规则遗传算法的终止准则通常有三种，一种是将某一个固定的最大代数作为停止算法的标准。另一种是把算法的运行时间作为停止准则。第三种准则有一定的自适应性，例如根据算法的评价的一些规则。当由此监控得到算法再进化己无法改进解的性能，此时停止计算。3.2.3 遗传算法执行策略遗传算法在执

47、行策略方面的下面几方面工作值得注意: 1.遗传算法与模拟退火算法的结合模拟退火 是一种基于热力学理论的优化方法，并有着完善的全局收敛理论。在遗传算法中以各种形式融入模拟退火思想，从而使得遗传算法在理论上具有全局收敛性，是一个有意义的研究方向。2.遗传算法与局部优化方法的结合把遗传算法与局部搜索方法有机结合起来，是改进遗传算法性能的一个卓有成效的方法。这种混合型遗传算法不但模拟了生物种群的学习过程，而且事实上还模拟了种群的个体在其生命周期内具有学习行为这一生物现象。这在生物学中被称为为Lamarckian evolution 和 Baldwin effect。3.并行遗传算法 (Parallel

48、 Genetic Algorithm 并行遗传算法是在遗传算法的实施中加入自然生物种群中的空间结构因素，它的目的是可以在大规模并行机上运行，即使是序列式实施并行遗传算法，也可克服经典遗传算法性能上的不足，从而提高算法的效率。并行遗传算法大致分为两种，一种是岛模型 (Island Model，称为粗粒并行遗传算法(Coarse Grained PGA 。岛模型的实施方法是 在几 个独 立按 经典遗 传算 法方 式运 行的种 群 (称为 子种 群中加 入迁移(Migration 因素。而细胞模型的实施则是在一个单一种群中，通过对经典整体性选择与杂交机制的局部化来达到并行化目的。岛模型考虑的是种群的

49、空间结构，而细胞模型考虑的是一种群中个体的空间结构。4.混乱遗传算法 (Messy Genetic Algorithm 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 20 页，共 39 页16 / 39 混乱遗传算法是由Goldberg提出的，它的目的是解决经典遗传算法中所谓的连接问题，即经典遗传算法很容易破坏定义位置较远的模式问题。在混乱遗传算法中，个体由其每个分量的位置与取值共同表示，位置可以不按次序排列，也并不是所有分量都在个体的表示中出现。事实上，混乱遗传算法直接操作的对象既有个体，也有空间结构，这自然使它丧失了只操作个体的经典遗传算法所

50、具有的隐含并行性。混乱遗传算 法 的 理 论 基 础 、 算 法 设 计 及 实 验 比 较 ， 均 是 有 待 探 讨 的 课 题 。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 21 页，共 39 页17 / 39 4 车间作业调度的建模4.1 车间作业调度问题描述不失一般性，设n 个作业 m 台机器的车间作业调度问题表示为： n/m JSP）满足以下约束条件：1）每个工件包含若干道工序；2）各工件必须按工艺路线以指定的次序在机器上加工； 不考虑工件加工的优先权，不考虑加工准备时间。(6 一个工件同一时间只能在一台机器上加工，一台机器同一时间