第9章-遗传算法及其应用.ppt

Artificial Intelligence Principles and Applications第第 9 章章   遗传算法及其应用遗传算法及其应用教材：教材： 王万良王万良《《人工智能及其应用人工智能及其应用》》（第（第2版）版）          高等教育出版社，高等教育出版社，2008. 62第9章  遗传算法及其应用o9.1  遗传算法的产生与发展遗传算法的产生与发展 o9.2  遗传算法的基本算法遗传算法的基本算法 o9.3  遗传算法的改进算法遗传算法的改进算法 o9.4  基于遗传算法的生产调度方法基于遗传算法的生产调度方法3第9章  遗传算法及其应用ü9.1  遗传算法的产生与发展遗传算法的产生与发展 o9.2  遗传算法的基本算法遗传算法的基本算法 o9.3  遗传算法的改进算法遗传算法的改进算法 o9.4  基于遗传算法的生产调度方法基于遗传算法的生产调度方法4 9.1  遗传算法的产生与发展   遗遗传传算算法法（genetic algorithms，GA）：一类借鉴生物界自然选择和自然遗传机制的随机搜索算法,非常适用于处理传统搜索方法难以解决的复杂和非线性优化问题。

  遗传算法可广泛应用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域59.1  遗传算法的产生与发展9.1.1  遗传算法的生物背景遗传算法的生物背景9.1.2  遗产算法的基本思想遗产算法的基本思想9.1.3  遗产算法的发展历史遗产算法的发展历史9.1.4  设计遗产算法设计遗产算法的基本原则与内容的基本原则与内容69.1.1  遗传算法的生物学背景o适适者者生生存存：：最最适适合合自自然然环环境境的的群群体体往往往往产产生生了了更更大大的的后后代代群群体 o生物进化的基本过程：生物进化的基本过程：染染色色体体(chromosome)：：生生物物的遗传物质的主要载体的遗传物质的主要载体基基因因(gene)：：扩扩展展生生物物性性状状的的遗遗传传物物质质的的功功能能单单元元和和结结构单位基基因因座座（（locus））：：染染色色体体中中基因的位置基因的位置等等位位基基因因（（alleles））：：基基因因所取的值所取的值79.1.2  遗传算法的基本思想生物遗传概念生物遗传概念遗产算法中的应用遗产算法中的应用适者生存适者生存目标值比较大的解被选择的可能性大目标值比较大的解被选择的可能性大个体（个体（Individual））解解染色体（染色体（Chromosome）） 解的编码（字符串、向量等）解的编码（字符串、向量等）基因（基因（Gene））解中每一分量的特征解中每一分量的特征适应性（适应性（Fitness））适应函数值适应函数值群体（群体（Population））根根据据适适应应函函数数值值选选定定的的一一组组解解（（解解的的个个数为群体的规模）数为群体的规模）婚配（婚配（Marry））交交叉叉（（Crossover））选选择择两两个个染染色色体体进进行行交叉产生一组新的染色体的过程交叉产生一组新的染色体的过程变异（变异（Mutation））编码的某一分量发生变化的过程编码的某一分量发生变化的过程89.1.2  遗传算法的基本思想 遗传算法的基本思想：遗传算法的基本思想： 在在求求解解问问题题时时从从多多个个解解开开始始，，然然后后通通过过一一定定的的法法则进行逐步迭代以产生新的解。

则进行逐步迭代以产生新的解99.1.3  遗传算法的发展历史o1962年，Fraser提出了自然遗传算法o1965年，Holland首次提出了人工遗传操作的重要性  o1967年，Bagley首次提出了遗传算法这一术语o1970年，Cavicchio把遗传算法应用于模式识别中 o1971年，Hollstien在论文《计算机控制系统中人工遗传自适应方法》中阐述了遗传算法用于数字反馈控制的方法 o1975年，美国J. Holland出版了《自然系统和人工系统的适配》；DeJong完成了重要论文《遗传自适应系统的行为分析》 o20世纪80年代以后，遗传算法进入兴盛发展时期109.1.4  设计遗传算法的基本原则与内容 设计的基本原则：设计的基本原则： 适用性适用性：算法所能适用的问题种类算法所能适用的问题种类 可靠性可靠性：：算法对于所设计的问题，以适当的精度求解算法对于所设计的问题，以适当的精度求解其中大多数问题的能力其中大多数问题的能力 收敛性收敛性：算法能否收敛到全局最优算法能否收敛到全局最优 稳定性稳定性：：算法对其控制参数及问题数据的敏感度算法对其控制参数及问题数据的敏感度 。

生物类比生物类比：通过类比的方法引入在生物界被认为是有：通过类比的方法引入在生物界被认为是有效的方法及操作效的方法及操作 11设计的基本内容：设计的基本内容： 9.1.4  设计遗传算法的基本原则与内容 编码方案编码方案：编码表示方式编码表示方式适应度函数适应度函数：目标函数目标函数选择策略选择策略：优胜劣汰优胜劣汰控控制制参参数数：：种种群群的的规规模模、、算算法法执执行行的的最最大大代代数数、、执执行行不同遗传操作的概率等不同遗传操作的概率等遗遗传传算算子子：：选选择择(selection)；；交交叉叉(crossover)；；变变异异(mutation)算算法法的的终终止止准准则则：：规规定定一一个个最最大大的的演演化化代代数数，，或或算算法法在连续多少代以后解的适应值没有改进在连续多少代以后解的适应值没有改进12第9章  遗传算法及其应用o9.1  遗传算法的产生与发展遗传算法的产生与发展 ü9.2  遗传算法的基本算法遗传算法的基本算法 o9.3  遗传算法的改进算法遗传算法的改进算法 o9.4  基于遗传算法基于遗传算法的生产调度方法的生产调度方法139.2  遗传算法的基本算法o遗传算法的五个基本要素遗传算法的五个基本要素：n参数编码n初始群体的设定n适应度函数的设计n遗传操作设计n控制参数设定149.2  遗传算法的基本算法9.2.1  编码编码9.2.2  群体设定群体设定9.2.3  适应度函数适应度函数9.2.4  选择选择9.2.5  交叉交叉9.2.6  变异变异9.2.7  遗传算法遗传算法的一般步骤的一般步骤159.2.1  编码 1.  位串编码位串编码一一维维染染色色体体编编码码方方法法：将问题空间的参数编码为一维排列的染色体的方法。

二二进进制制编编码码：用若干二进制数表示一个个体，将原问题的解空间映射到位串空间 B={0，1}上，然后在位串空间上进行遗传操作 （（1）） 二进制编码二进制编码169.2.1  编码 (1) 二进制编码二进制编码（续）（续）优点优点：类似于生物染色体的组成，算法易于用生物遗传理论解释，遗传操作如交叉、变异等易实现；算法处理的模式数最多 缺点：缺点：① 相邻整数的二进制编码可能具有较大的Hamming距离，降低了遗传算子的搜索效率                  15：01111            16： 10000② 要先给出求解的精度③ 求解高维优化问题的二进制编码串长，算法的搜索效率低17 9.2.1  编码 1.  位串编码位串编码（（2））  Gray 编码编码Gray编码:将二进制编码通过一个变换进行转换得到的编码 二进制串   Gray 二进制编码  Gray编码Gray编码  二进制编码 18 9.2.1  编码 2.  实数编码实数编码 采用实数表达法不不必必进进行行数数制制转转换换，可直接在解的表现型上进行遗传操作 多多参参数数映映射射编编码码的的基基本本思思想想：把每个参数先进行二进制编码得到子串，再把这些子串连成一个完整的染色体。

多参数映射编码中的每个子串对应各自的编码参数，所以，可以有不同的串长度和参数的取值范围有不同的串长度和参数的取值范围 19 9.2.1  编码 3.  有序串编码有序串编码 有有序序问问题题：目标函数的值不仅与表示解的字符串的值有关，而且与其所在字符串的位置有关 4．结构式编码．结构式编码 Goldberg等提出MessyGA(mGA)的遗传算法编码方法 201.初始种群的产生初始种群的产生 9.2.2  群体设定 （1）根据问题固有知识，把握最优解所占空间在整个问题空间中的分布范围，然后，在此分布范围内设定初始群体2）随机产生一定数目的个体，从中挑选最好的个体加到初始群体中这种过程不断迭代，直到初始群体中个体数目达到了预先确定的规模 212.  种群规模的确定种群规模的确定 9.2.2   群体设定  模模式式定定理理表明：若群体规模为M，则遗传操作可从这M 个个体中生成和检测 个模式，并在此基础上能够不断形成和优化积木块，直到找到最优解 群体规模太小，遗传算法的优化性能不太好，易陷入局部最优解 群体规模太大，计算复杂 221.1.将目标函数映射成适应度函数的方法将目标函数映射成适应度函数的方法 9.2.3  适应度函数 § 若目标函数为最大化最大化问题，则§ 若目标函数为最小化最小化问题，则将目标函数转换为求最大值的形式将目标函数转换为求最大值的形式, ,且保证函数值非负！且保证函数值非负！ § 若目标函数为最大化最大化问题，则§ 若目标函数为最小化最小化问题，则231.1.将目标函数映射成适应度函数的方法将目标函数映射成适应度函数的方法( (续）续） 9.2.3   适应度函数 存在界限值预选估计困难或者不能精确估计的问题！存在界限值预选估计困难或者不能精确估计的问题！ § 若目标函数为最大化最大化问题，则§ 若目标函数为最小化最小化问题，则§ ：目标函数界限的保守估计值。

242.适应度函数的尺度变换适应度函数的尺度变换 § 在遗传算法中，将所有妨碍适应度值高的个体产生，从而 影 响 遗 传 算 法 正 常 工 作 的 问 题 统 称 为 欺欺 骗骗 问问 题题（deceptive problem） 9.2.3   适应度函数 § 过过早早收收敛敛：缩小这些个体的适应度，以降低这些超级个体的竞争力§ 停停滞滞现现象象：改变原始适应值的比例关系，以提高个体之间的竞争力§ 适应度函数的尺尺度度变变换换（（fitness scaling））或者定定标标：对适应度函数值域的某种映射变换 252.适应度函数适应度函数的尺度变换的尺度变换( (续）续） （1）线性变换：9.2.3  适应度函数 满足满足最小适应度值非负 262.适应度函数适应度函数的尺度变换的尺度变换( (续）续） （2）幂函数变换法： 9.2.3  适应度函数 （3）指数变换法：279.2.4  选择 1. 个体选择概率分配方法个体选择概率分配方法§ 选择操作也称为复制（reproduction）操作：从当前群体中按照一定概率选出优良的个体，使它们有机会作为父代繁殖下一代子孙§ 判断个体优良与否的准则是各个个体的适应度值：个体适应度越高，其被选择的机会就越多。

289.2.4  选择 1. 个体选择概率分配方法个体选择概率分配方法（（1））适适应应度度比比例例方方法法（（fitness proportional model））或或蒙蒙特特卡卡罗法罗法（（Monte Carlo）） § 各个个体被选择的概率和其适应度值成比例§ 个体 被选择的概率为： 299.2.4  选择   1. 个体选择概率分配方法个体选择概率分配方法（（2）） 排序方法排序方法 （（rank-based model））① 线性排序：J. E. BakerØ 群体成员按适应值大小从好到坏依次排列：Ø 个体Ø 按转盘式选择的方式选择父体309.2.4  选择   1. 个体选择概率分配方法个体选择概率分配方法（（2）） 排序方法排序方法 （（rank-based model））② 非线性排序： Z. Michalewicz § 将群体成员按适应值从好到坏依次排列，并按下式分配选择概率：319.2.4  选择 1. 1.个体选择概率分配方法个体选择概率分配方法（（2）） 排序方法排序方法 （（rank-based model）） § 可用其他非线性函数来分配选择概率，只要满足以下条件： 329.2.4  选择   2. 选择个体方法选择个体方法（1）转盘赌选择转盘赌选择（roulette wheel selection） Ø 按个体的选择概率产生一个轮盘，轮盘每个区的角度与个体的选择概率成比例。

Ø 产生一个随机数，它落入转盘的哪个区域就选择相应的个体交叉 第1轮产生一个随机数：0.81 第2轮产生一个随机数：0.32 339.2.4  选择   2. 选择个体方法选择个体方法（2）锦标赛选择方法锦标赛选择方法（（tournament selection model）） § 锦锦标标赛赛选选择择方方法法：从群体中随机选择个个体，将其中适应度最高的个体保存到下一代这一过程反复执行，直到保存到下一代的个体数达到预先设定的数量为止 § 随随机机竞竞争争方方法法（stochastic tournament）：每次按赌轮选择方法选取一对个体，然后让这两个个体进行竞争，适应度高者获胜如此反复，直到选满为止 349.2.4  选择   2. 选择个体方法选择个体方法（3）        和         选择      Ø 从规模为 的群体中随机选取个体通过重组和变异生成 个后代，Ø 再选取 个最优的后代作为新一代种群 § 从 个后代与其父体共 中选取 个最优的后代 359.2.4  选择   2. 选择个体方法选择个体方法（4）Boltzmann锦标赛选择§ 最最佳佳个个体体（（elitist model））保保存存方方法法：把群体中适应度最高的个体不进行交叉而直接复制到下一代中，保证遗传算法终止时得到的最后结果一定是历代出现过的最高适应度的个体。

（5）最佳个体保存方法 § 随机选取两个个体 ，若 则选择适应值好的作为胜者，否则计算概率 ，若 ，选择差解，否则选择好解 369.2.5  交叉   1. 基本的交叉算子基本的交叉算子（1）一点交叉一点交叉（single-point crossover）§ 一点交叉：在个体串中随机设定一个交叉点，实行交叉时，该点前或后的两个个体的部分结构进行互换，并生成两个新的个体 § 二点交叉：随机设置两个交叉点，将两个交叉点之间的码串相互交换 （2）二点交叉二点交叉 （two-point crossover）379.2.5  交叉 1. 基本的交叉算子（续）基本的交叉算子（续）§ 均匀交叉：按照均匀概率抽取一些位，每一位是否被选取都是随机的，并且独立于其他位然后将两个个体被抽取位互换组成两个新个体3）均匀交叉均匀交叉（uniform crossover）或一致交叉389.2.5  交叉   2. 修正的交叉方法修正的交叉方法（（ 1）） 部部 分分 匹匹 配配 交交 叉叉 PMX： Goldberg  D.  E.和 R.   Lingle(1985)  399.2.5  交叉 2.  修正的交叉方法修正的交叉方法(续）续）（2）顺序交叉顺序交叉OX：Davis L. (1985) （3） 循环交叉循环交叉CX：Smith D. (1985) 409.2.5  交叉   3. 实数编码的交叉方法实数编码的交叉方法（（1）离散交叉）离散交叉（discrete crossover） § 部部分分离离散散交交叉叉：在父解向量中选择一部分分量，然后交换这些分量。

—— 二进制的点式交叉二进制的点式交叉 § 整整体体离离散散交交叉叉：以0.5的概率交换父体      的所有分量    ——— 二进制编码的均匀性交叉二进制编码的均匀性交叉  21ss 与419.2.5  交叉   3. 实数编码的交叉方法（续）实数编码的交叉方法（续）（2）算术交叉算术交叉（arithmetical crossover） § 部部分分算算术术：先在父解向量中选择一部分分量，如第 个分量以后的所有分量，然后生成 个[0，1]区间的随机数，并将两个后代定义为：429.2.5  交叉   3. 实数编码的交叉方法（续）实数编码的交叉方法（续）（2）算术交叉算术交叉（arithmetical crossover）  § 整整体体算算术术交交叉叉：先生成 n 个区间的随机数，则后代分别定义为：439.2.6  变异  1. 整数编码的变异方法整数编码的变异方法（1）位位点点变变异异：群体中的个体码串，随机挑选一个或多个基因座，并对这些基因座的基因值以变异概率作变动2）逆逆转转变变异异：在个体码串中随机选择两点（逆转点），然后将两点之间的基因值以逆向排序插入到原位置中。

（3）插插入入变变异异：在个体码串中随机选择一个码，然后将此码插入随机选择的插入点中间 449.2.6  变异  1. 整数编码的变异方法（续）整数编码的变异方法（续）（4）互互换换变变异异：随机选取染色体的两个基因进行简单互换5）移移动动变变异异：随机选取一个基因，向左或者向右移动一个随机位数6）自自适适应应变变异异：类似于位点变异，但变异概率随群体中个体的多样性程度而自适应调整459.2.6  变异  2. 实数编码的变异方法实数编码的变异方法（（1））均匀性变异均匀性变异 § 均匀性变异均匀性变异：在父解向量中随机地选择一个分量（第 个），然后在 中以均匀概率随机选择 代替 以得到 ，即 469.2.6  变异   2. 实数编码的变异方法（续）实数编码的变异方法（续）（2）正态性变异正态性变异（（normal distributed mutation）） 479.2.6  变异   2. 实数编码的变异方法（续）实数编码的变异方法（续）（3）非一致性变异非一致性变异§  Z. Michalewicz首先提出将变异算子的结果与演化代数联系起来。

§ 在演化初期，变异范围相对较大，而随着演化的推进，变异范围越来越小，起着一种对演化系统的微调作用 489.2.6  变异   2. 实数编码的变异方法（续）实数编码的变异方法（续）（3）非一致性变异非一致性变异499.2.6  变异   2. 实数编码的变异方法（续）实数编码的变异方法（续）（4）自适应变异自适应变异 §自适应变异方式与非一致性变异算子相同，只是将其中的演化代数 改为 ，函数表达式变为： 509.2.7  遗传算法的一般步骤519.2.7  遗传算法的一般步骤（1）使用随机方法或者其它方法，产生一个有N个染色体的初始群体  pop(1)，          ； （2）对群体中的每一个染色体popi(t)，计算其适应值（3）若满足停止条件，则算法停止；否则，以概率         从pop(t)中随机选择一些染色体构成一个新种群 529.2.7  遗传算法的一般步骤（4）以概率 进行交叉产生一些新的染色体，得到一个新的群体  （5）以一个较小的概率   使染色体的一个基因发生变异，形成                         ；              ，成为一个新的群体         返回 （2）。

 539.2.8  遗传算法的特点 可直接对结构对象进行操作利用随机技术指导对一个被编码的参数空间进行高效率搜索采用群体搜索策略，易于并行化仅用适应度函数值来评估个体，并在此基础上进行遗传操作，使种群中个体之间进行信息交换54第9章  遗传算法及其应用o9.1  遗传算法的产生与发展遗传算法的产生与发展 o9.2  遗传算法的基本算法遗传算法的基本算法 ü9.3  遗传算法的改进算法遗传算法的改进算法 o9.4  基于遗传算法的生产调度方法基于遗传算法的生产调度方法559.3  遗传算法的改进算法 9.3.1  双倍体遗传算法双倍体遗传算法9.3.2  双种群遗传算法双种群遗传算法9.3.3  自适应遗传算法自适应遗传算法56 9.3.1  双倍体遗传算法1. 基本思想基本思想 双倍体遗传算法采用显显性性和隐隐性性两个染色体同时进行进化，提供了一种记忆以前有用的基因块的功能 双倍体遗传算法采用显性遗传显性遗传 双倍体遗传延长了有用基因块的寿命，提高了算法的收敛能力，在变异概率低的情况下能保持一定水平的多样性57 9.3.1  双倍体遗传算法 2. 双倍体双倍体遗传算法的算法的设计（（1）编码）编码/解码解码：两个染色体（显性、隐性）   （（2））复复制制算算子子：计算显性染色体的适应度，按照显性染色体   的复制概率将个体复制到下一代群体中。

  （（3））交交叉叉算算子子：两个个体的显性染色体交叉、隐性染色体也同时交叉             （（4））变变异异算算子子：：个体的显性染色体按正常的变异概率变异；隐性染色体按较大的变异概率变异    （（5））双双倍倍体体遗遗传传算算法法显显隐隐性性重重排排算算子子：：个体中适应值较大的染色体设为显性染色体，适应值较小的染色体设为隐性染色体58 双种群遗传算法程序流程图双种群遗传算法程序流程图 599.3.2  双种群遗传算法 1.1. 基本思想基本思想 在遗传算法中使用多种群同时进化，并交换种群之间优秀个体所携带的遗传信息，以打破种群内的平衡态达到更高的平衡态，有利于算法跳出局部最优 多多种种群群遗遗传传算算法法：建立两个遗传算法群体，分别独立地运行复制、交叉、变异操作，同时当每一代运行结束以后，选择两个种群中的随机个体及最优个体分别交换 609.3.2  双种群遗传算法  2. 双种群双种群遗传算法的设计遗传算法的设计（1）编码/解码设计（2）交叉算子、变异算子（3）杂交算子杂交算子设种群A与种群B，当A与B种群都完成了选择、交叉、变异算子后，产生一个随机数num，随机选择A中num个个体与A中最优个体，随机选择B中num个个体与B中最优个体，交换两者，以打破平衡态。

61 双种群遗传算法程序流程图双种群遗传算法程序流程图 629.3.3  自适应遗传算法 1. 基本思想基本思想 Srinvivas M.，Patnaik L. M.等在1994年提出一种自适应遗传算法(adaptive genetic algorithms，AGA)：         能随适应度自动改变 AGA：当种群各个体适应度趋于一致或者趋于局部最优时，使          增加，以跳出局部最优；而当群体适应度比较分散时，使          减少，以利于优良个体的生存 同时，对于适应度高于群体平均适应值的个体，选择较低的 ，使得该解得以保护进入下一代；对低于平均适应值的个体，选择较高的 值，使该解被淘汰 639.3.3  自适应遗传算法 2. 自适应自适应遗传算法的步骤遗传算法的步骤（1） 编码/解码设计2） 初始种群产生：N（N 是偶数）个候选解，组成初始解集3） 定义适应度函数为              ，计算适应度     4） 按轮盘赌规则选择N 个个体，计算              5）将群体中的各个个体随机搭配成对，共组成N/2对， 对每一对个体，按照自适应公式计算自适应交叉概率   ，随机产生R(0,1)，如果          则对该对染色体进行交叉操作。

64  2. 自适应遗传算法的步骤自适应遗传算法的步骤（续）（续）（6）对于群体中的所有个体，共N个，按照自适应变异公式计算自适应变异概率     ，随机产生 R(0,1)，如果                则对该染色体进行交叉操作 （7）计算由交叉和变异生成新个体的适应度，新个体与父代一起构成新群体8）判断是否达到预定的迭代次数，是则结束；否则转 （4） 9.3.3  自适应遗传算法 653. 适应的适应的交叉概率与变异概率交叉概率与变异概率9.3.3  自适应遗传算法 普通自适应算法中，当个体适应度值越接近最大适应度值时，交叉概率与变异概率就越小；当等于最大适应度值时，交叉概率和变异概率为零 改进的思想：当前代的最优个体不被破坏，仍然保留（最优保存策略）；但较优个体要对应于更高的交叉概率与变异概率 66 F－自适应方法－自适应方法： 9.3.3  自适应遗传算法 3. 自适应的交叉概率与变异概率（续）自适应的交叉概率与变异概率（续）679.3.3  自适应遗传算法  S－自适应方法－自适应方法： 3.自适应的交叉概率与变异概率（续）自适应的交叉概率与变异概率（续）689.3.3  自适应遗传算法 3.自适应的交叉概率与变异概率（续）自适应的交叉概率与变异概率（续） C －－自适应方法自适应方法： 69第9章  遗传算法及其应用o9.1  遗传算法的产生与发展遗传算法的产生与发展 o9.2  遗传算法的基本算法遗传算法的基本算法 o9.3  遗传算法的改进算法遗传算法的改进算法 ü9.4  基于遗传算法的生产调度方法基于遗传算法的生产调度方法709.4  基于遗传算法的生产调度方法 9.4.1  基于遗传算法的流水车间调度方法基于遗传算法的流水车间调度方法9.4.2  基于遗传算法的混合流水车间调度方法基于遗传算法的混合流水车间调度方法711. 流水车间调度问题流水车间调度问题  问题描述：n 个工件要在 m 台机器上加工，每个工件需要经过 m 道工序，每道工序要求不同的机器，n 个工件在 m 台机器上的加工顺序相同。

工件在机器上的加工时间是给定的，设为        问题的目标：确定 n 个工件在每台机器上的最优加工顺序，使最大流程时间达到最小9.4.1  基于遗传算法的流水车间调度方法721. 流水车间流水车间调度问题调度问题 假设假设：  (1) 每个工件在机器上的加工顺序是给定的 (2) 每台机器同时只能加工一个工件 (3) 一个工件不能同时在不同的机器上加工 (4) 工序不能预定 (5) 工序的准备时间与顺序无关，且包含在加工时间中 (6) 工件在每台机器上的加工顺序相同，且是确定的 9.4.1  基于遗传算法的流水车间调度方法731. 流水车间调度问题流水车间调度问题9.4.1  基于遗传算法的流水车间调度方法 问题的数学模型：问题的数学模型： 个工件、 台机器的流水车间调度问题的完工时间： 74 2. 求解流水车间调度求解流水车间调度问题的遗传算法设计问题的遗传算法设计 （（1）） FSP的编码方法的编码方法 对于FSP，最自然的编码方式是用染色体表示工件的顺序9.4.1  基于遗传算法的流水车间调度方法对于有四个工件的FSP，第 个染色体 ，表示工件的加工顺序为： 。

75 2. 求解流水车间调度问题求解流水车间调度问题的遗传算法设计的遗传算法设计 （（2））FSP的适应度函数的适应度函数  : 个染色体 的最大流程时间，FSP的适应度函数： 9.4.1  基于遗传算法的流水车间调度方法763.求解求解FSP的遗传算法实例的遗传算法实例 例例1 1 Ho 和 Chang(1991) 给出的5个工件、4台机器问题 工件131412530219553343234227641322141353355719 加工时间表加工时间表 9.4.1  基于遗传算法的流水车间调度方法77用遗传算法求解选择交叉概率 ，变异概 ,种群规模为20，迭代次数 表9.3  遗传算法运行的结果 总运行次数最好解最坏解平均最好解的频率最好解的平均代数20213221213.950.85129.4.1  基于遗传算法的流水车间调度方法用穷举法求得最优解：4-2-5-1-3，加工时间：213；最劣解：1-4-2-3-5，加工时间：294；平均解的加工时间：265   遗传算法运行的结果遗传算法运行的结果 78表9.3  遗传算法运行的结果 最优解收敛图最优解收敛图 9.4.1  基于遗传算法的流水车间调度方法79平均值收敛图平均值收敛图 9.4.1  基于遗传算法的流水车间调度方法80机器甘特图机器甘特图 9.4.1  基于遗传算法的流水车间调度方法819.4.2  基于遗传算法的混合流水车间调度方法1. 混合流水混合流水车间调度问题车间调度问题 问题的特征问题的特征：在某些工序上存在并行机器并行机器。

问问题题的的描描述述：需要加工多个工件，所有工件的加工路线都相同，都需要依次通过几道工序，在所有工序中至少有一个工序存在着多台并行机器 需需要要解解决决的的问问题题：确确定定并并行行机机器器的的分分配配情情况况以及同同一台机器上工件的加工排序一台机器上工件的加工排序 目标目标：最小化最大流程时间 82 假设加工 个工件，每个工件都要依次经过 个加工工序，每个工序的并行机器数为 ， 所有工序中至少有一个工序存在并行机，即至少有一个 大于19.4.2  基于遗传算法的混合流水车间调度方法2. 混合流混合流水车间调度问题的遗传算法编码方法水车间调度问题的遗传算法编码方法  HFSP的编码矩阵的编码矩阵 ： 上的一个实数，表示 工件的第 个工序在第台并行机上加工 ：多个工件在同一台机器上加工同一个工序 83§ ，按 的升序来加工工件§ ，根据每个工件的前一个工序的完成时间来确定其加工顺序，前一个工序先完成的先加工§ 假如完成时间相同，也按 的升序来加工  9.4.2  基于遗传算法的混合流水车间调度方法染色体的长度： 。

  染色体：染色体：84o例如，对于有3个个工工件件、3道道工工序序、各工序的并并行行机机器器数数分别为3，，2，，2的混合流水车间调度问题 9.4.2  基于遗传算法的混合流水车间调度方法 染色体染色体：[2.1，2.4，1.9，0，1.6，2.1，2.3，0，1.1，2.4，1.2] 编码矩阵编码矩阵：   混合流水车间调度的机器编号 853. 基于遗传算法的求解方法基于遗传算法的求解方法 9.4.2  基于遗传算法的混合流水车间调度方法种群成员按适应值从好到坏依次排列种群成员按适应值从好到坏依次排列 按下式分配复制概率：按下式分配复制概率： （（1）） 初始群体初始群体的产生的产生（（2）适应度函数）适应度函数的选择的选择: : 最大流程时间的倒数最大流程时间的倒数（（3）选择（）选择（非线性排名策略非线性排名策略））86（（5）） 变异操作：分段变异操作：分段 （（4）） 交叉操作交叉操作  (a)                               (b) 若          ，则                                  ，否则  (c)            9.4.2  基于遗传算法的混合流水车间调度方法分段交叉分段交叉：在两个父体的各段中随机选取一部分基因，然后交换，得到子代个体。

874.  调度实例调度实例 某汽车发动机厂金加工车间要加工12个工件，每个工件都有车、刨、磨 3个工序，现有3台车床，2台刨床，4台磨床，每台机床的加工能力不同9.4.2  基于遗传算法的混合流水车间调度方法88 工件工件工序工序1工序工序2工序工序3机器机器1机器机器2机器机器3机器机器4机器机器5机器机器6机器机器7机器机器8 8机器机器9 9122345232324543434543654423425443465365854533134656654234395752446343583547533649254127865103643448671152435676512654543475工件在每个机器上的加工时间工件在每个机器上的加工时间 9.4.2  基于遗传算法的混合流水车间调度方法89得到的最好的染色体是： 最好的染色体：[2.77，3.51，1.74，3.52，2.42，1.36，3.28，3.94，1.09，   1.22，2.24，3.64，0，1.60，1.13，1.24，2.97，1.73，1.88，1.08，2.68，1.16，2.69，2.51，2.96，0，4.99，3.29，4.95，2.35，1.10，1.01，1.73，1.35，3.06，1.20，4.13，3.67 ] 9.4.2  基于遗传算法的混合流水车间调度方法算法中使用的参数为   =0.07，  =0.80，  =0.01，种群规模为30，种群经过100代的进化，目标函数最小值随着种群的进化逐渐地减小，最后收敛于极值，目标函数平均值也随着群体的进化逐渐减少，最后趋近于最优值。

90得到的最好的染色体是： 混合流水车间调度结果甘特图混合流水车间调度结果甘特图 9.4.2  基于遗传算法的混合流水车间调度方法91Artificial Intelligence Principles and ApplicationsTHE END。