基于遗传算法的柔性车间作业调度 - 毕业设计正文.doc

华北电力大学本科毕业设计（论文）基于遗传算法的柔性车间作业调度摘要车间生产调度问题是当今工程领域研究的热点。近十几年来，面向用户个性化需求的定制生产模式开始成为制造的主流，对市场需求的快速反应能力开始成为企业能否在激烈的市场竞争中占得一席之地的重要标志，因此，柔性快速的生产调度就显得格外重要。柔性作业车间调度是古典作业调度问题的扩展，柔性作业车间调度问题由于减少了机器的约束，所以比传统作业车间调度问题的复杂性更高。因此，寻找有效的方法对柔性作业车间调度问题进行求解具有重要的理论价值和应用意义。本文首先介绍国内外车间调度研究的方法和发展现状，然后阐述遗传算法的基本概念、原理和方法。其次对所研究的作业车间调度进行了详细的数学分析，并对数学描述进行了简化，为下一步的算法设计建立数学模型。针对柔性作业车间调度问题的特点，提出了一种改进的遗传算法，采用双子串的方式来进行编码，并且基于此给出了独特的交叉和变异法则，从而取消了运用遗传算法求解作业车间问题时为使基因合法化而进行的基因修复和重建过程。 最后给出了一个46 调度问题的测试例子，并且绘制出了作业调度的甘特图。仿真实例证明了此算法的有效性。关键词：柔性车间作业调度；遗传算法 ；双子串编码Flexible Job-Shop Scheduling Problem Based on Genetic AlgorithmABSTRACTJob-shop scheduling problem is the scientific research hotspot , in the past dozens of years, User-oriented personalized needs customization product mode starts to become the mainstream of manufacturing, the capability of rapid response in market demands come to be an important symbol that whether the enterprise can occupy a room in the fierce market competitionThe flexible job shop scheduling problem is a generalization of the classical job shop scheduling problem. Due to machine constraint, flexible job shop scheduling is much more complex than traditional job shop scheduling. Thus, seeking the effective methods used to solve flexible job shop scheduling has important theoretical and applied significance.This paper firstly introduces the methods and developments about workshop scheduling inside and outside country; secondly expatiates the basic conception and principle about genetic algorithm; then analyses the job shop scheduling problem，and also predigests the mathematic depiction so as to convenience further program design. According to the characteristics of flexible job shop scheduling problem , an improved genetic algorithm has been adopted. It uses two multistage-based model to code. Based on that a special crossover operators and mutation operators are designed for genetic algorithm, By doing that, the repairing process to validate the schedule gene is successfully cancelled. In this paper, Finally , a example of 8 6 scheduling showed that the genetic algorithm was efficient .At the same time ,give the arithmetic examples of job shop，and show their schedule Gantt picturesKey words: flexible job shop scheduling problem ；genetic algorithm; two multistage-based model to code.II华北电力大学本科毕业设计（论文）目录摘要IABSTRACT II绪论11车间作业调度21.1车间调度问题的研究意义 21.2车间调度问题研究现状 21.3车间调度问题的分类 31.4实际车间调度问题的特点 31.5车间调度问题的研究方法 41.6实际车间生产调度研究中存在的主要问题 51.7柔性车间作业调度问题 51.7.1问题描述 51.7.2数学描述 61.8 Gantt图72遗传算法82.1遗传算法的基本思想 82.2遗传算法的特点 82.3遗传算法的基本概念 92.4遗传算法基本流程102.5遗传算法的参数及基本操作 112.5.1算法参数112.5.2遗传算法的编码和解码122.5.3适应度函数 132.5.4遗传操作142.5.4.1初始种群的产生142.5.4.2选择算子 152.5.4.3交叉算子 152.5.4.4变异算子163遗传算法求解柔性作业车间调度问题 173.1遗传算法求解柔性作业车间调度问题的步骤 173.2遗传操作设计173.2.1编码173.2.2适应度函数18II3.2.3遗传算法的主要操作步骤184仿真实例及结论 215总结与展望 235.1总结 235.2展望 23参考文献 24致谢 26绪论有效的调度方法与优化技术的研究和应用，对于制造企业提高生产效率、降低生产成本等方面起着重要作用，因而越来越受到学者们的关注。如何进行组织管理，包括如何组织动态联盟、如何重构车间和单元、如何安排生产计划、如何进行调度都是我们面临的主要问题。其中车间作业调度与控制技术是实现生产高效率、高柔性和高可靠性的关键，有关资料表明，制造过程中95的消耗是在非切削过程中2。因此，有效的调度方法与优化技术的研究和应用，已成为先进制造技术实践的基础和关键。车间作业调度(Job Shop Scheduling，简称JSS)的启发式算法3，是用某一调度优先级规则在当前可调度工序中选择一个工序进行加工，最终形成一个由所有被加工零件各工序组成的序列，即所谓调度结果由于调度规则通常只针对特定问题和特定环境，它存在着难以克服的缺点，如计算规模不可能较大，寻优具有局部性等而基于遗传算法的车间作业调度的基本思想是，预先排列出若干个由工序组成的序列，然后对这些序列进行遗传进化操作，从而达到优化调度结果性能指标的目的由于遗传算法只利用适应性信息，它不要求目标函数可微、连通和凸性，因而它是一种高效率的随机搜索与优化的方法，具有搜索面广、算法速度快等优点然而遗传算法中交叉概率和变异概率的选择是影响遗传算法行为和性能的关键，直接影响算法收敛性，并且编码与解码的问题也对遗传算法的应用有较大的限制作用。同时遗传算法易于早熟和陷入局部最优解的缺点，也使人们不断对遗传算法进行改进。研究车间生产调度问题，对促进企业生产管理的现代化，建立现代企业制度，提高我国企业的竞争力，迅速打开走向世界的局面都具有重要的意义。1车间作业调度车间调度主要是针对一项可分解的工作(如产品制造)，探讨在尽可能满足约束条件(如交货期、工艺路线、资源情况)的前提下，通过下达生产指令，安排其组成部分(操作)使用哪些资源、其加工时间及加工的先后顺序，以获得产品制造时间或成本的最优化4。在理论研究中，车间作业调度问题常被称为排序问题或资源分配问题或组合优化问题。1.1车间调度问题的研究意义车间生产过程的调度问题，是制造系统运筹技术、管理技术与优化技术发展的核心。有效的调度方法与优化技术的研究和应用，已经成为先进制造技术实践的基础和关键，优良的调度策略对于提高生产系统的最优性、提高经济效益，有着极大的作用。在理论研究中，车间作业调度问题常被称为排序问题或资源分配问题或组合优化问题。随着产品制造界的市场的竞争性在不断提高，好的生产调度能提高资源的利用率和操作管理水平，生产出具有竞争力的产品。车间的调度优化工作，因其在提高生产效率，降低生产成本等方面所起的重要作用，正越来越受到学者们的关注，也是本课题的研究意义所在。车间作业调度问题的研究不仅具有较大的实用价值，而且还有相当大的理论意义。研究生产调度问题推动了遗传算法、模拟退火算法、启发式方法等优化方法的发展与融合，也为其他领域类似问题的解决提供了条件与手段。通过将优化算法与调度方法相结合，使制造系统提高运行效率，满足客户的要求，增强企业在市场上的竞争力。1.2车间调度问题研究现状由于调度问题是制造系统中最基本、最重要的问题之一，是生产管理的核心问题和关键技术，因此国内外大量的学者对其进行了广泛的探讨和研究。调度问题的研究始于20世纪50年代，Johnson提出了解决n/2/F/Cmax和部分特殊的n/3/F/Cmax问题的优化算法，代表调度理论研究的开始：60-70年代建立了调度理论的主体(经典调度理论)并重视调度复杂性的研究。随着70年代后期调度理论研究的深入及各种交叉学科的发展，又涌现出了许多新的车间调度理论与方法，如神经网络、模拟退火法、遗传算法等5。由于各种车间作业调度的算法都存在着不同程度的优缺点6，所以，近年来，人们开始将各种算法组合起来进行研究7，以扬长避短，达到优化调度的目的。比如：使用将遗传算法和禁忌搜索算法结合起来的混合策略，求解车间调度问题8。通过结合启发式算法和遗传算法的混合方法，求解多资源约束的车间调度问题9。1.3 车间调度问题的分类车间生产调度系统的分类方法很多，主要有以下几种：(1) 根据加工系统的复杂度，生产调度可分为单机调度、作业车间调度(Job Shop)、流水车间(Flow Shop)调度、多机器并行加工调度。(2) 根据优化准则，可以分为基于代价和性能的调度两大类。(3) 根据生产环境的特点，可将调度问题分为确定性调度问题和随机性调度问题。(4) 根据作业的加工特点，可将调度问题分为静态调度和动态调度。1.4实际车间调度问题的特点：车间生产调度问题有以下特点10：(1) 复杂性由于装卸作业、装卸设备、库场、搬运系统之间相互影响、相互作用、每个作业又要考虑它的到达时间、装卸时间、准备时问、操作顺序、交货期等，因而相当复杂。而且调度问题是在等式或不等式约束下求性能指标的优化，在计算量上往往是NP难问题，即随着问题规模的增大，对于求解最优化的计算量呈指数增长，使得一些常规的最优化方法往往无能为力。(2) 动态随机性在实际的生产调度系统中存在很多随机的和不确定的因素，比如作业到达时间的不确定性、作业的加工时间也有一定的随机性，而且生产系统中常出现一些突发偶然事件，如设备的损坏或修复、作业交货期的改变等。(3) 多目标性。实际的计划调度往往是多目标的，并且这些目标间可能发生冲突。Kiran等人将调度目标分三类：基于作业交货期的目标、基于作业完成时间的目标、基于生产成本的目标11。这种多目标性导致调度的复杂性和计算量急剧增加。1.5车间调度问题的研究方法现有调度问题的研究方法大体上可以分为以下几种类别：(1) 解析方法。只针对简单小规模调度问题的解析求解方法。(2) 枚举方法（enumerative methods）该类方法对小规模问题比较有效，但对于大规模问题计算量和存储量难以承受。 分支定界（bound and branch）数学方法（mathematical method）。譬如整数规划、混合整数规划、分解方法、代理对偶方法、Lagrangian松弛方法等。(3) 构造性方法（constructive method）。该类方法能够快速建立问题的解，但通常解质量较差，否则需要建立复杂的启发式规则。 优先分配规则（priority dispatch rule）。譬如SPT，LRM，MWR等。 基于瓶颈的启发式方法（bottleneck based heuristics）。如移动瓶颈过程，beam搜索等。 插入方法（insertion algorithm）。如CDS，NEH法等。(4) 领域搜索算法（local search method）。该类方法从若干解出发，对其领域的不断搜索和当前解的替换来实现优化。 迭代改进法（iterative improvement）。 模拟退火法（simulated annealing，SA）。 进化算法（evolutionary computation，EC）。它包括遗传算法（genetic algorithm，GA）、进化规划、进化策略和遗传编程。 禁忌搜索（tabu search，TS）。 巢分区（nested parition，NP）。 变邻域搜索（variable neighborhood search，VNS）。 噪声方法（noising method，NM）。 阈值接受法（threshold accepting，TA）。 可变深度搜索（variable deep search，VDS）。(5) 人工智能方法（artificial intelligence）。该类方法利用人工智能的原理和技术进行搜索，譬如将优化过程转化成智能系统动态的演化过程，基于系统动态的演化来实现优化。 神经网络（neural network，NN）。 专家系统（expert system，ES）。 蚁群系统（ant system，AS）。 混沌搜索（chaotic search，CS）。 免疫算法（immunity algorithm）。另外，还有上述各算法的混合方法。1.6实际车间生产调度研究中存在的主要问题调度领域中的大部分问题都具有NP难问题，虽然对它的研究已经有几十年的历史，但至今尚未形成一套系统的方法和理论。一些理论上的最优化方法能提供最优调度，但由于其计算的复杂性，并且忽略了很多实际因素，离实际运用还有很大距离。由于大多数调度问题属于一类NP难组合问题，因此寻找具有多项式复杂性的最优算法几乎是不可能的。传统的启发式算法，智能模拟退火算法，禁忌算法，神经网络法等算法其共性是对生产线优化问题寻求满足实际需要的近似解或满意解，而非精确最优解。在调度问题的理论研究中，大多数还是集中在针对经典的调度问题设计优化算法，在实际车间调度中，车间计划与车间调度往往是分层进行的，这可能造成计划在实际调度中的不可行问题。另外，还有很多待进一步研究的问题，比如实际车间调度的多目标性、动态随机性等。1.7柔性车间作业调度问题1.7.1问题描述一般的车间调度问题都是对于具体生产环境中复杂动态、多目标、多约束调度的一种抽象和简化，其首要问题是对调度问题进行建模。Job Shop是一类最具一般性的生产加工环境，该类调度问题已得到广泛的关注和研究。在传统的Job Shop调度问题研究中，仅考虑各工序在唯一确定的机床上加工的情况，即先有确定的加工计划，再进行作业调度，缺乏一定的柔性。随着FMS的出现，这一传统限制已被突破，各工序可以在多台可选的机床上加工，即路径柔性已成为生产的实际需求。研究具有路径柔性的车间调度(Flexible Job Shop Scheduling，简称FJSS)问题具有重要的理论和应用意义。从“系统工程方法论”的角度来看，建模是在选定目标、约束条件及研究环境等工作基础上进行的。因此在建立FJSS模型之前，首先要对FJSS问题有个清楚的描述，明确问题的特点、目标、约束及输入输出。FJSS问题的描述如下：假定一个加工系统有m台机器和n个工件，每个工件包含一道或多道工序，工件的工序顺序是预先确定的，每道工序可以在多台不同的机床上加工，工序的加工时间随机床的性能不同而变化。调度目标是为每道工序选择最合适的机器，以及确定每台机器上各工件工序的最佳加工顺序及开工时间，使系统的某些性能指标达到最优。下面是针对该调度问题的假设：(1) 整个加工过程中，一个工件不能在同一台机器上加工多次；(2) 任何一个工件的前一道工序加工完成后，方能进行后一道工序的加工，在同一台机器上一个加工任务完成之后，方能开始另一个加工任务；(3) 各工件必须按工艺路线以指定的次序在机器上加工；(4) 不考虑工件加工的优先权；(5) 每个工件的工序一旦进行就不能中断；(6) 一个工件同一时间只能在一台机器上加工，一台机器同一时间只能加工一个工件，加工的开始时间为0。1.7.2数学描述：目标函数： min (1-1)St (1-2) (1-3) (1-4)其中： (1-5) (1-6) i,j = 1,2,n；h,k = 1,2,m；其中，分别为工件i在机器k上的完成时间和加工时间；M是一个足够大的正数；分别为指示系数和指示变量。式(1-1)表示目标函数，即调度的目标为最大完成时间最小化；式(1-2)表示顺序约束条件，即各个工件各操作的先后加工顺序，保证每个工件的加工顺序满足预先的要求；式(1-3)表示资源约束条件，即机器加工各个工件的先后顺序，保证每台机器一次只能加工一个工件。1.8 Gantt图对于m台机器(Machine)(M1，M2，Mm)，n个工件(Job)(J1，J2，Jn)的加工过程，调度通常用Gantt图表示。Gantt图是在1917年由Henry Laurence Gantt开发的。它基本上是一种线条图，横轴表示时间，纵轴表示要安排的活动，线条表示在整个期间计划的和实际的活动完成情况。Gantt图直观地表明任务计划在什么时候进行，以及实际进展与计划要求的对比。Gantt图使车间的计划安排情况一目了然，成为管理人员了解全局，安排车间进度的有效工具。表1.1 一个33的车间调度问题Job(机器，时间)J1（3,1）（1,2）（2,2）J2（3,1）（2,4）（1,1）J3（2,2）（3,3）（1,1）以一个3个工件3台机器的JSP为例说明，表1.1中每个括弧中第一个数据表示工件在哪台机器上加工，第二个数据表示加工时间。以Gantt图表示的该实例的一个可行调度，如图1.1所示。 图1.1 表1.1中JSP的Gantt图2 遗传算法遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。它最早由美国密执安大学的Holland教授提出，起源于60年代对自然和人工自适应系统的研究1270年代De Gong基于GA的思想在计算机上进行大量的纯数值函数优化计算实验13。在一系列研究工作的基础上，80年代由Goldberg进行归纳总结，形成了GA的基本框架14。近几年来，GA主要在复杂优化问题求解和工业工程领域应用，取得了一些令人信服的结果。GA成功的应用包括：作业调度与排序、可靠性设计、车辆路径选择与调度、成组技术、设备布置与分配、交通问题等等。2.1遗传算法的基本思想遗传算法(Genetic Algorithms)的基本思想来源于分子遗传学和生物进化论，其基本原理是，产生若干代表问题候选解的成员，并组成一个群体，按照某一评价函数或算法对群体中的每个成员进行评估，评估结果代表解的良好性。按照适者生存、优胜劣汰的原则，群体中的某一成员愈适合，则愈有可能产生后代。利用遗传操作对群体中的成员进行遗传操作，产生新的后代，这种后代能继承双亲的特征。对后代进行评估，并将其放入群体，代替上一代中较弱的成员(非良好解)。此过程反复执行，这构成一代代的群体。随着遗传过程的不断进行，越来越良好的解就可以得到。2.2遗传算法的特点遗传算法是解决搜索问题的一种通用算法，对于大部分搜索问题都能够使用，首先在此先阐述一下搜索算法的共同特征14：(1)首先生成一组候选解，即构造算法的初始解集；(2)依据设定的适应性条件计算这些解的适应度；(3)依据适应度，选择保留适应度高的个体，去除适应度低的个体；(4)对筛选出的新个体进行新的操作，生成新的适应度个体。这是大部分搜索算法所具有的特征，但是遗传算法作为一种新型的算法，必然有它的特殊之处，它基于染色体群的并行搜索，带有猜测性质的选择操作、交换操作和突变操作。这种特殊的组合方式将遗传算法与其它搜索算法区别开来。遗传算法独具的特点如下：(1) 遗传算法是对问题参数的编码(染色体)群进行进化，而不是参数本身。这是遗传算法与传统优化算法的较大区别。传统优化算法是从单个初始值迭代求最优解的；容易误入局部最优解。遗传算法从串集开始搜索，覆盖面大，利于全局择优，克服了早熟的缺点。(2) 遗传算法的搜索是从问题解的串集开始搜索，而不是从单个解开始。遗传算法同时处理群体中的多个个体，即对搜索空间中的多个解进行评估，减少了陷入局部最优解的风险，同时算法本身易于实现并行化。(3) 遗传算法使用适应度这一信息进行搜索，而不需导数等其它信息。适应度函数不仅不受连续可微的约束，而且其定义域可以任意设定。这一特点使得遗传算法的应用范围大大扩展。 (4) 遗传算法使用的选择、交叉、变异这三个算子都是随机操作，而不是确定性规则。遗传算法是采用概率的变迁规则来指导他的搜索方向。(5) 遗传算法最善于搜索复杂地区，从中找出期望值高的区域和个体。(6) 遗传算法具有可扩展性，易于同别的算法技术混合。综上所述，GA算法较之传统优化方法，具有良好的全局搜索能力，是一种全局优化算法。但是，实际应用遗传算法时，往往出现早熟收敛、收敛性能差、局部最优解等缺点。因为遗传算法是一类基于“产生+测试”方式的迭代搜索算法，尽管算法在一定条件具有全局收敛性，但算法的交叉、变异、选择等操作一般都是在概率意义下随机进行的，虽然保证了种群的群体进化性，但一定程度上不可避免退化现象的出现。2.3遗传算法的基本概念遗传算法是由进化理论和遗传学机理而产生的，基于概率的搜索优化方法，因而，在遗传算法中要用到进化和遗传学相关的概念。这些概念如下：(1) 串(String)：它是个体(Individual)的形式，在算法中为表现为字符串，并对应于遗传学中的染色体(Chromosome)。(2) 群体(Population)：个体的集合，串是群体中的元素。(3) 群体的大小(Population Size)：在群体中个体的数量为群体的大小。(4) 基因(Gene)：基因是串中的元素，基因用于表示个体的特征。(5) 适应度(Fitness)：表示某个体对于环境的适应程度。2.4遗传算法基本流程遗传算法是一类随机优化算法，但它不是简单的随机比较搜索，而是通过对染色体的评价和对染色体中基因的作用，有效地利用已有信息来指导搜索有希望改善优化质量的状态。标准遗传算法的主要步骤如描述下：(1) 确定问题的编码方案。编码的目的主要是使优化问题解的表现形式适合于遗传算法中的遗传运算，由于GA通常不直接作用于问题的解空间，而是利用解的某种编码表示来进行进化，因此选择合理的编码机制对算法的质量和效果有很大的影响。(2) 适应度函数的构造和应用。由于GA通常是基于适应度函数进行遗传操作的，因此合理的适应度函数能够将个体的优劣程度得以体现。适应度函数基本上依据优化问题的目标函数而定，当适应度函数确定以后，自然选择规律是以适应度函数值的大小决定的概率分布来确定哪些染色体适应生存，哪些被淘汰，生存下来的染色体组成种群，形成一个可以繁殖下一代的群体。(3) 算法参数的选取。通常包括；种群大小、交叉概率、变异概率、进化代数等。(4) 遗传算子的设计。通常包括：初始化、选择、交叉、变异和替换操作等。父代的遗传基因结合是通过父代染色体之间的交叉并到达下一代个体的。新产生个体中可能发生基因变异，变异使解有更大的遍历性。(5) 确定算法的终止条件。终止准则应根据所求解问题的性质，在优化质量和效率方面作合理均衡或侧重。图2.1遗传算法具体设计实施过程2.5遗传算法的参数及基本操作2.5.1算法参数标准的GA有6个关键参数，包括种群数目、交叉概率、变异概率、代沟、尺度窗口和选择策略。因此如何确定GA的最优参数仍然是一个热点问题，也是研究GA的重点课题之一。(1)种群数目(Generation Size)种群数目是影响算法最终优化性能和效率的因素之一。当种群数目设得过小时，不能提供足够的采样点来搜索整个解空间，以致算法性能很差；当种群数目设得过大时，尽管可增加优化信息以阻止早熟收敛的发生，但无疑会增加计算量，从而使收敛时间太长，算法效率偏低。一般建议取值范围是20-100。(2)交叉概率(Crossover Rate)交叉概率用于控制交叉操作发生的频率。交叉概率过大时，种群中个体的更新很快，会使高适应度的个体很快被破坏掉；概率过小时，交叉操作发生的频率过低，使搜索停滞不前。一般建议的取值范围是0.40-0.99。另外，也可使用自适应的思想来确定交叉概率，如Davis15提出，随着GA在线性能的提高，可以增大交叉概率的取值。(3)变异概率(Mutation Rate)变异概率是保证种群多样性的重要因素。通常，一个较低的变异率足以防止整个群体中任一位置的基因一直保持不变。但是，变异概率太小则不会产生新个体，概率太大则使GA成为随机搜索。一般建议的取值范围是0.0001-0.1000。另外，也可使用自适应的思想来确定变异概率。可减小变异概率的取值。(4)代沟(G)代沟用于控制每代中种群被替换的比例。当G=100时，种群中所有个体将被替换；G=50时，一半种群将被替换。在标准GA中，G=100，而有些替换策略中G值与新旧个体的适应度好坏有关而且是变化的。(5)尺度窗口(W)该参数用于由目标值到适应度的调整。对于最大化函数优化问题，个体x的适应度可以定义为：u(x)=f(X)一fmin (2-1)其中f(x)为其目标值，fmin为问题的最小目标值。然而，fmin通常是未知的。许多方法用算法当前进程发现的最小目标值fmin作为替代。显然，定义不同的fmin将影响优良个体的选择压力。(6)选择策略(S)通常有两种选择策略：其一为纯选择，即种群中每一个体根据其适应度作比例选择；其二为保优策略，即先用纯选择作选择，然后将最优个体加入下一代种群，该策略可防止最优解的遗失。2.5.2遗传算法的编码和解码在遗传算法中如何描述问题的可行解，即把一个问题的可行解从其解空间转化到遗传算法所能处理的搜索空间的转换方法称为编码。编码是应用GA时要解决的首要问题，也是设计GA时的一个关键步骤。由于GA的优化过程不是直接作用于问题参数本身，而是在一定编码机制对应的码空间上进行的，因此编码的选择是影响其算法性能与效率的重要因数。GA的一个显著特点是它交替地在编码空间和解空间中工作，它在编码空间对染色体进行遗传操作，而在解空间对解进行评估和选择。对于实数编码，染色体和解之间的编码与解码(基因性与表现性之间的相互映射)有三个主要问题：(1)染色体的可行性为染色体解码成为解之后是否在给定问题的可行域内的性质。(2)染色体的合法性是指编码空间中的编码是否可以映射到解空间中的一个解。凡是可以映射到解空间的编码都是合法的，否则就是非法的。(3)映射的唯一性从编码空间到解空间的映射可以是1对1映射、X对1映射或1对X映射，显然，1对1映射是最好的，而1对X映射是最不值得提倡的。编码(encoding)是问题的解空间到GA表达空间的一种映射。而解码(decoding)是GA表达空间到问题的解空间的一种映射，如图2.2所示。图2.2 GA表达空间和问题解空问GA表达空间中的所有染色体并非全部对应于实际问题的。有效调度，如图2.3所示。可能存在着对应不合法调度和不可行调度的染色体。图2.3 调度的可行性和合法性注：不可行指的是某个染色体解码出来的解在给定问题的可行区域之外的现象；而非法性指的是某个染色体不能代表给定问题的解的现象针对函数优化的编码技术主要有二进制编码、十进制编码、Gray编码、实数编码等。(1) 二进制编码是用若干二进制数表示一个个体，将原问题的解空间映射到位串空间B=0，l上，然后在位串空间上进行遗传操作。二进制编码类似生物染色体的组成，从而使算法易于用生物遗传理论来解释。并使得遗传操作如交叉、变异等很容易实现。另外，采用二进制编码算法的处理模式很多，但是可能使相邻整数具有较大的Hamming16距离。例如15和16的二进制表示为01111和10000，因此算法要从15变为16则必须改变所有的位。这种缺陷造成了Hamming悬崖将降低遗传算子的搜索效率。在求解高维优化问题时，二进制编码串将非常长，从而使得算法的搜索效率很低。由于很多数值与非数值优化问题都可以用二进制编码来应用遗传算法，同时表达的模式最多，所以二进制编码方法是遗传算法中最常用的一种编码方法，它具有以下优点：1) 编码、解码操作简单易行。2) 交叉、变异等遗传操作便于实现。3) 符合最小字符集编码原则。4) 便于用模式定理进行分析，因为模式定理就是以二进制为基础的。(2) 格雷码编码方法作为一种新的编码方法具有自己独特的优势，但本质上还是和二进制编码方法有相似之处。格雷码能够克服二进制编码在结构特征，以及一些连续函数的优化问题中显现出局部搜索能力差的缺陷，增强了算法的局部搜索能力。格雷码是将二进制编码通过一个转换而得到的编码。转化公式17如下：设有二进制编码串为B =bmbm-1bm-2b2b1 ,其中对应的格雷码为 G=gm gm-1gm-2g2g1。则将二进制转化为格雷码的公式为： (2-2)其中为异或运算符，而格雷码转化为二进制的运算公式为: (2-3)(3) 实数编码为了克服二进制编码的缺点，对问题的变量是实向量的情形，可以直接采用实数编码。采用实数表达法不必进行数制转换，可直接在解的表现型上进行遗传操作，从而可引入与问题领域相关的启发式信息来增加算法的搜索能力。遗传算法在求高维、复杂优化问题时通常采用实数编码18。2.5.3适应度函数遗传算法遵循自然界优胜劣汰的原则，在进行搜索中基本上不用外部信息，而用适应度表示个体的优劣，作为遗传算法操作的依据。适应度函数表明个体对环境适应能力的强弱，是区分群体中个体好坏的标准，也是进行自然选择的唯一依据。对于简单的最小化问题，通常可以直接将目标函数变换成适应度函数，例如将个体X的适应度值f(X)定义为M-c(X)或e-ac(X),其中M为一足够大的正数。c(X)为个体的目标值，a0。对于复杂优化问题，往往需要构造合适的评价函数，使其适应GA进化优化。对于适应度和目标函数值，有多种设计方法。它影响遗传选择的方向，最终影响遗传运算结果。采用妥协方法19的基本思想是：通过最大完成时间来确定后悔值r，进而求得相应染色体的适应度。妥协方法根据某种距离度量方式来确定与理想解最近的解20。加权Lp范数21被用作距离度量方式来确定后悔值r即其中(z1*，z2*，zq*)是判据空间Z中的正理想点，权重(w1，w2，wq)被分配给目标并用来强调其不同的重要程度。其中，z用每代种群中染色体的Tmax表示，z*即理想的最小化时间0+。理想解实际上无法达到，然而它可以成为评价可达到的非支配解的标准。后悔值r越小个体越好，因此将后悔值转换为适应值从而确保优秀个体具有较大的适应值。设r(x)表示个体x的后悔值，rmax表示当前代中的最大后悔值，rmin表示当前代中的最小后悔值，求取染色体X的适应度e(x)其中是正实数，通常被限制在(0，1)中。该系数有两个作用：避免式(2-5)产生被零除错误；可以将选择方式从适应值比例选择调整到纯粹随机选择()。值得一提的是，GA的优化过程是一种搜索评价过程，如果评价过程占有的时间过多，则势必影响算法的整体优化性能。因此，对于评价过程复杂的问题，如仿真优化问题，如何提出有效的评价机制来加速或简化评价过程，将有利于提高GA的优化效率。2.5.4遗传操作2.5.4.1初始种群的产生遗传算法是群体型操作算法，在对解空间变量进行编码后，紧接着就要随机产生N个染色体，构造遗传算法的初始群体。但考虑到搜索效率和质量，最好采用如下策略设定21：1) 根据问题固有知识，设法把握最优解所占空间在整个问题空间中的分布范围，然后，在此范围内设定初始种群。2) 先随机产生一定数目的个体，然后从中挑选最好的个体加到初始群体中，这种过程不断迭代，直到初始种群中个体数目达到了预定规模。2.5.4.2选择算子遗传算法中的选择操作就是用来确定如何从父代群体中按某种方法选取哪些个体遗传到下一代群体中的一种遗传运算。目的是为了避免有效基因的损失，从当前群体中选出生命力强的染色体，使它有机会保留用以繁殖后代，从而提高全局收敛性和计算效率。最常用的选择方法是适应度比例选择、最优个体保存选择和锦标赛选择。(1) 比例选择(也称轮盘赌)。比例选择的基本思想是：根据染色体的适应度值的大小，分配繁殖机会，适应度相对低的个体则产生的后代数目将减少。该方法的染色体新个体是概率性地从老群体中选择的，其操作是随机的。设群体大小为M，个体i的适应度为Fi，则个体i被选中的概率Pi，为Pi = (2 - 6)由上式可见，适应度越高的个体被选中的概率越大；反之，适应度越低的个体被选中的概率越小。(2) 基于排名的选择。首先将种群中所有个体由好到坏进行排列，然后以一定方式分配给各个体一定的选择概率，具体分配方式不限，如线性方式、非线性方式，但要要求越好的个体分配的概率越大，且所有个体所分配的概率之和为l。(3) 锦标赛选择。首先在父代种群中随机选取k个个体，然后令其中适配值或目标值最好的个体为被选中的个体。显然k的大小影响选择性能。2.5.4.3交叉算子遗传算法中起核心作用的是交叉算子，也称为基因重组(recombination)。采用的方法应能够使父代的特征遗传给子代。子代应能够部分或者全部地继承父代的结构特征和有效的基因。在遗传算法中，交叉运算之前还必须先对群体中的个体进行配对，它通常分为三步：第一步，对父代中的个体进行随机配对；第二步，对所选择的配对个体随机产生一个交叉位置：第三步，将交叉位置后面的部分进行交换，产生两个新的个体。下面我们来介绍在遗传算法中主要应用的两种交叉方法：(1) 单点交叉 首先在相互配对的染色体中随机确定一个交叉位置，然后对换交叉点后的子串。例如父串为P1、P2，若单点交叉位置为4,则生成的子串为C1、C2。P1(1100100) C1(1100011)P2(0011011) C2(0011100)(2) 多点交叉 首先在相互配对的染色体中随机确定多个交叉位置，然后对换相应的子串。若两点交叉，位置选择为2、5，父代个体同上，则经过交叉后的子代个体为：C1(1111000) C2(0000111)2.5.4.4变异算子GA中的变异运算，是指以很小的概率随机地改变染色体串上的某些位，从而形成一个新的个体。如二进制编码的个体，就是将个体在变异点上的基因值取反，即0变1，1变0。从遗传运算过程中产生新个体的能力方面来说，交叉运算是产生新个体的主要方法，它决定了GA的全局搜索能力；而变异运算是产生新个体的辅助方法，决定了GA的局部搜索能力。交叉算子与变异算子的相互配合，共同完成对搜索空间的全局搜索和局部搜索，从而使得GA能够以良好的搜索性能完成最优化问题的寻优过程。下面介绍几种常用的变异操作方法。它们适用于二进制编码和实数编码的个体。(1) 基本位变异对群体中的个体的染色体串中，随机的选择一个或几个基因位。，若需要进行变异操作则将基因座上的原有基因值（假设为）0，则变异操作将该基因值变为1；反之，若原有基因值为1，则变异操作将该基因值变为0。变异前：100111 选择基因位3和5进行变异，变异后：101101 此操作仅限于二进制编码的染色体串，对于实数编码的串不适用。(2) 逆转基因位变异在个体的染色体串中随机的选择两个逆转点，然后将两个逆转点之间的基因逆向排序，从而达到产生新个体的目的。变异前：101011001 选择两个逆转点为2和7，变异后：101101001变异前：132456779 选择两个逆转点为2和7，变异后：136542779 操作对于染色体串的编码方式没有过多的要求，因此是比较常用的变异方法，但通过观察我们应该发现此操作会产生与父代差异很大的染色体串，在应用中予以重视。(3) 互换变异在染色体串中随机的选择两个基因位，然后互换基因位上的值，完成变异操作。 变异前：101101 选择变异位置为3和5，变异后：100111 变异前：125673 选择变异位置为3和5，变异后：127653 3遗传算法求解柔性作业车间调度问题3.1 遗传算法求解柔性作业车间调度问题的步骤遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的领域和种类。FJSS问题的优化，可按图3.1来构造求解该问题的遗传算法22。在图3.1中，对于求解FJSS模型的基于活动