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

Artificial Intelligence Principles and Applications第第 9 章章 遗传算法及其应用遗传算法及其应用教材：教材：王万良王万良人工智能及其应用人工智能及其应用（第（第2版）版）高等教育出版社，高等教育出版社，2008.62第9章 遗传算法及其应用o 9.1 遗传算法的产生与发展遗传算法的产生与发展 o 9.2 遗传算法的基本算法遗传算法的基本算法 o 9.3 遗传算法的改进算法遗传算法的改进算法 o 9.4 基于遗传算法的生产调度方法基于遗传算法的生产调度方法3第9章 遗传算法及其应用9.1 遗传算法的产生与发展遗传算法的产生与发展 o 9.2 遗传算法的基本算法遗传算法的基本算法 o 9.3 遗传算法的改进算法遗传算法的改进算法 o 9.4 基于遗传算法的生产调度方法基于遗传算法的生产调度方法4 9.1 遗传算法的产生与发展 遗传算法遗传算法（genetic algorithms，GA）：一类借鉴生物界自然选择和自然遗传机制的随机搜索算法,非常适用于处理传统搜索方法难以解决的复杂和非线性优化问题。遗传算法可广泛应用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域。59.1 遗传算法的产生与发展o9.1.1 遗传算法的生物背景遗传算法的生物背景o9.1.2 遗产算法的基本思想遗产算法的基本思想o9.1.3 遗产算法的发展历史遗产算法的发展历史o9.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 遗传算法的发展历史o 1962年，Fraser提出了自然遗传算法。o 1965年，Holland首次提出了人工遗传操作的重要性。o 1967年，Bagley首次提出了遗传算法这一术语。o 1970年，Cavicchio把遗传算法应用于模式识别中。o 1971年，Hollstien在论文计算机控制系统中人工遗传自适应方法中阐述了遗传算法用于数字反馈控制的方法。o 1975年，美国J.Holland出版了自然系统和人工系统的适配；DeJong完成了重要论文遗传自适应系统的行为分析。o 20世纪80年代以后，遗传算法进入兴盛发展时期。109.1.4 设计遗传算法的基本原则与内容 o 设计的基本原则：设计的基本原则：适用性适用性：算法所能适用的问题种类。：算法所能适用的问题种类。可靠性可靠性：算法对于所设计的问题，以适当的精度求解算法对于所设计的问题，以适当的精度求解其中大多数问题的能力其中大多数问题的能力。收敛性收敛性：算法能否收敛到全局最优。：算法能否收敛到全局最优。稳定性稳定性：算法对其控制参数及问题数据的敏感度算法对其控制参数及问题数据的敏感度。生物类比生物类比：通过类比的方法引入在生物界被认为是有：通过类比的方法引入在生物界被认为是有效的方法及操作。效的方法及操作。11o 设计的基本内容：设计的基本内容：9.1.4 设计遗传算法的基本原则与内容 编码方案编码方案：编码表示方式。：编码表示方式。适应度函数适应度函数：目标函数。：目标函数。选择策略选择策略：优胜劣汰。：优胜劣汰。控制参数控制参数：种群的规模、算法执行的最大代数、执行：种群的规模、算法执行的最大代数、执行不同遗传操作的概率等。不同遗传操作的概率等。遗传算子遗传算子：选择：选择(selection)；交叉；交叉(crossover)；变异；变异(mutation)。算法的终止准则算法的终止准则：规定一个最大的演化代数，或算法：规定一个最大的演化代数，或算法在连续多少代以后解的适应值没有改进。在连续多少代以后解的适应值没有改进。12第9章 遗传算法及其应用o 9.1 遗传算法的产生与发展遗传算法的产生与发展 9.2 遗传算法的基本算法遗传算法的基本算法 o 9.3 遗传算法的改进算法遗传算法的改进算法 o 9.4 基于遗传算法基于遗传算法的生产调度方法的生产调度方法139.2 遗传算法的基本算法o 遗传算法的五个基本要素遗传算法的五个基本要素：n 参数编码n 初始群体的设定n 适应度函数的设计n 遗传操作设计n 控制参数设定149.2 遗传算法的基本算法o9.2.1 编码编码o9.2.2 群体设定群体设定o9.2.3 适应度函数适应度函数o9.2.4 选择选择o9.2.5 交叉交叉o9.2.6 变异变异o9.2.7 遗传算法遗传算法的一般步骤的一般步骤159.2.1 编码 o 位串编码位串编码一维染色体编码方法一维染色体编码方法：将问题空间的参数编码为一维排列的染色体的方法。二进制编码二进制编码：用若干二进制数表示一个个体，将原问题的解空间映射到位串空间 B=0，1上，然后在位串空间上进行遗传操作。（1）二进制编码二进制编码169.2.1 编码(1)二进制编码二进制编码（续）（续）优点优点：类似于生物染色体的组成，算法易于用生物遗传理论解释，遗传操作如交叉、变异等易实现；算法处理的模式数最多。缺点：缺点：相邻整数的二进制编码可能具有较大的Hamming距离，降低了遗传算子的搜索效率。15：01111 16：10000 要先给出求解的精度。求解高维优化问题的二进制编码串长，算法的搜索效率低。17 9.2.1 编码 o 位串编码位串编码（2）Gray 编码编码Gray编码:将二进制编码通过一个变换进行转换得到的编码。二进制串 n.21 Gray n.21二进制编码 Gray编码1111kkkkkGray编码 二进制编码)2(mod1kiik18 9.2.1 编码 2.实数编码实数编码 采用实数表达法不必进行数制转换不必进行数制转换，可直接在解的表现型上进行遗传操作。多参数映射编码的基本思想多参数映射编码的基本思想：把每个参数先进行二进制编码得到子串，再把这些子串连成一个完整的染色体。多参数映射编码中的每个子串对应各自的编码参数，所以，可以有不同的串长度和参数的取值范围有不同的串长度和参数的取值范围。19 9.2.1 编码 3.有序串编码有序串编码 有序问题有序问题：目标函数的值不仅与表示解的字符串的值有关，而且与其所在字符串的位置有关。4结构式编码结构式编码 Goldberg等提出MessyGA(mGA)的遗传算法编码方法。20初始种群的产生初始种群的产生 9.2.2 群体设定（1）根据问题固有知识，把握最优解所占空间在整个问题空间中的分布范围，然后，在此分布范围内设定初始群体。（2）随机产生一定数目的个体，从中挑选最好的个体加到初始群体中。这种过程不断迭代，直到初始群体中个体数目达到了预先确定的规模。212.种群规模的确定种群规模的确定 9.2.2 群体设定 模式定理模式定理表明：若群体规模为M，则遗传操作可从这M 个个体中生成和检测 个模式，并在此基础上能够不断形成和优化积木块，直到找到最优解。3M 群体规模太小，遗传算法的优化性能不太好，易陷入局部最优解。群体规模太大，计算复杂。22 将目标函数映射成适应度函数的方法将目标函数映射成适应度函数的方法 9.2.3 适应度函数 若目标函数为最大化最大化问题，则 若目标函数为最小化最小化问题，则)()(xfxfFit)(1)(xfxfFit将目标函数转换为求最大值的形式将目标函数转换为求最大值的形式,且保证函数值非负！且保证函数值非负！若目标函数为最大化最大化问题，则 若目标函数为最小化最小化问题，则minmin()()()0f xCf xCFit f x其他情况maxmax()()()0Cf xf xCFit f x其他情况23 将目标函数映射成适应度函数的方法将目标函数映射成适应度函数的方法(续）续）9.2.3 适应度函数 存在界限值预选估计困难或者不能精确估计的问题！存在界限值预选估计困难或者不能精确估计的问题！若目标函数为最大化最大化问题，则 若目标函数为最小化最小化问题，则 ：目标函数界限的保守估计值。1()0()01()Fit f xccf xcf x，1()0()01()Fit f xccf xcf x，c24适应度函数的尺度变换适应度函数的尺度变换 在遗传算法中，将所有妨碍适应度值高的个体产生，从而 影 响 遗 传 算 法 正 常 工 作 的 问 题 统 称 为 欺 骗 问 题欺 骗 问 题（deceptive problem）。9.2.3 适应度函数 过早收敛过早收敛：缩小这些个体的适应度，以降低这些超级个体的竞争力。停滞现象停滞现象：改变原始适应值的比例关系，以提高个体之间的竞争力。适应度函数的尺度变换（尺度变换（fitness scaling）或者定标定标：对适应度函数值域的某种映射变换。25适应度函数适应度函数的尺度变换的尺度变换(续）续）（1）线性变换：baff9.2.3 适应度函数 minfffaavgavgminminffffbavgavgavgavgmultfffCamax)1(avgavgavgmultffffCfbmaxmax)(,avgavgff avgmultfCfmax满足满足最小适应度值非负 26适应度函数适应度函数的尺度变换的尺度变换(续）续）（2）幂函数变换法：Kff affe9.2.3 适应度函数（3）指数变换法：279.2.4 选择 o 个体选择概率分配方法个体选择概率分配方法 选择操作也称为复制（reproduction）操作：从当前群体中按照一定概率选出优良的个体，使它们有机会作为父代繁殖下一代子孙。判断个体优良与否的准则是各个个体的适应度值：个体适应度越高，其被选择的机会就越多。289.2.4 选择 o 个体选择概率分配方法个体选择概率分配方法（1）适应度比例方法适应度比例方法（fitness proportional model）或蒙特卡或蒙特卡罗法罗法（Monte Carlo）Miiisiffp1 各个个体被选择的概率和其适应度值成比例。个体 被选择的概率为：i299.2.4 选择 1.个体选择概率分配方法个体选择概率分配方法（2）排序方法排序方法（rank-based model）线性排序：J.E.Baker 群体成员按适应值大小从好到坏依次排列：个体 按转盘式选择的方式选择父体Nxxx,21 iipx 分配选择概率)1(MMbiapi309.2.4 选择 1.个体选择概率分配方法个体选择概率分配方法（2）排序方法排序方法（rank-based model）非线性排序：Z.Michalewicz 将群体成员按适应值从好到坏依次排列，并按下式分配选择概率：MiMiqqqpMii1,2,1)1()1(11319.2.4 选择 1.1.个体选择概率分配方法个体选择概率分配方法（2）排序方法排序方法（rank-based model）可用其他非线性函数来分配选择概率，只要满足以下条件：Miip11 )2(满足则且若iMMpxfxfxfxxxP ),(.)()(,)1(212,1Mppp 21329.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）最佳个体保存方法 随机选取两个个体 ，若 则选择适应值好的作为胜者，否则计算概率 ，若 ，选择差解，否则选择好解。21,xx|21xfxf Txfxfp|exp21)1,0randomp 369.2.5 交叉 1.基本的交叉算子基本的交叉算子（1）一点交叉一点交叉（single-point crossover）一点交叉：在个体串中随机设定一个交叉点，实行交叉时，该点前或后的两个个体的部分结构进行互换，并生成两个新的个体。二点交叉：随机设置两个交叉点，将两个交叉点之间的码串相互交换。（2）二点交叉二点交叉（two-point crossover）379.2.5 交叉 o 基本的交叉算子（续）基本的交叉算子（续）均匀交叉：按照均匀概率抽取一些位，每一位是否被选取都是随机的，并且独立于其他位。然后将两个个体被抽取位互换组成两个新个体。（3）均匀交叉均匀交叉（uniform crossover）或一致交叉389.2.5 交叉 2.修正的交叉方法修正的交叉方法（1）部分匹配交叉）部分匹配交叉PMX：Goldberg D.E.和R.Lingle(1985)231765489A645932178B231932489A645765178B399.2.5 交叉 2.修正的交叉方法修正的交叉方法(续）续）（2）顺序交叉顺序交叉OX：Davis L.(1985)HHHA176548HHHB493218481765HHHA 184932HHHB 481932765 A184765932 B（3）循环交叉循环交叉CX：Smith D.(1985)409.2.5 交叉 3.实数编码的交叉方法实数编码的交叉方法（1）离散交叉）离散交叉（discrete crossover）部分离散交叉部分离散交叉：在父解向量中选择一部分分量，然后交换这些分量。二进制的点式交叉二进制的点式交叉 整体离散交叉整体离散交叉：以0.5的概率交换父体 的所有分量。二进制编码的均匀性交叉二进制编码的均匀性交叉 21ss 与419.2.5 交叉 3.实数编码的交叉方法（续）实数编码的交叉方法（续）（2）算术交叉算术交叉（arithmetical crossover）部分算术部分算术：先在父解向量中选择一部分分量，如第 个分量以后的所有分量，然后生成 个0，1区间的随机数，并将两个后代定义为：kkn)1(,.,1,.,()2()1()2(11)1(11)1()1(1vvvvvvnnnnkkkkkzaaaas)1(,.,1,.,()1()2()1(11)2(11)2()2(1vvvvvvnnnnkkkkkwaaaasnkaa.1429.2.5 交叉 3.实数编码的交叉方法（续）实数编码的交叉方法（续）（2）算术交叉算术交叉（arithmetical crossover）整体算术交叉整体算术交叉：先生成 n 个区间的随机数，则后代分别定义为：)()1()2()1()2()2()1(iiiiiiiiivvavvavaz)()1()1()2()1()1()2(iiiiiiiiivvavvavawnaaa.21439.2.6 变异 1.整数编码的变异方法整数编码的变异方法（1）位点变异位点变异：群体中的个体码串，随机挑选一个或多个基因座，并对这些基因座的基因值以变异概率作变动。（2）逆转变异逆转变异：在个体码串中随机选择两点（逆转点），然后将两点之间的基因值以逆向排序插入到原位置中。（3）插入变异插入变异：在个体码串中随机选择一个码，然后将此码插入随机选择的插入点中间。449.2.6 变异 1.整数编码的变异方法（续）整数编码的变异方法（续）（4）互换变异互换变异：随机选取染色体的两个基因进行简单互换。（5）移动变异移动变异：随机选取一个基因，向左或者向右移动一个随机位数。（6）自适应变异自适应变异：类似于位点变异，但变异概率随群体中个体的多样性程度而自适应调整。459.2.6 变异 2.实数编码的变异方法实数编码的变异方法（1）均匀性变异均匀性变异：父解),.,.,(21nkvvvvs：变异产生的后代),.,.,(21nkvvvvskivkivski,均匀性变异均匀性变异：在父解向量中随机地选择一个分量（第 个），然后在 中以均匀概率随机选择 代替 以得到 ，即 k,kkbakvkv s469.2.6 变异 2.实数编码的变异方法（续）实数编码的变异方法（续）（2）正态性变异正态性变异（normal distributed mutation）nvvvs,21 解向量n,21 摄动向量,s被选个体,s新个体,0expiiiNiiiNvv,0ni,2,1 479.2.6 变异 2.实数编码的变异方法（续）实数编码的变异方法（续）（3）非一致性变异非一致性变异 Z.Michalewicz首先提出将变异算子的结果与演化代数联系起来。在演化初期，变异范围相对较大，而随着演化的推进，变异范围越来越小，起着一种对演化系统的微调作用。489.2.6 变异 2.实数编码的变异方法（续）实数编码的变异方法（续）（3）非一致性变异非一致性变异：区间 ,kkba1)2(0)2(,rndrndabtvvbtvvkkkkkkkTtryyt11,：父解,.,21nkvvvvs ：变异后的解,121nkkvvvvvs 499.2.6 变异 2.实数编码的变异方法（续）实数编码的变异方法（续）（4）自适应变异自适应变异：解空间的一个向量,21nvvvs max1fsfT变异温度：自适应变异方式与非一致性变异算子相同，只是将其中的演化代数 改为 ，函数表达式变为：tTTryyT1,509.2.7 遗传算法的一般步骤问 题初 始 化 染 色 体 种 群计 算 每 个 个 体 的 适 应 值根 据 适 应 值 选 择串 进 行 复 制交 叉变 异确 定 表 示 问 题 解 答 的 染 色 体（编 码）输 出 最 优 解是否满 足 终 止 条 件519.2.7 遗传算法的一般步骤（1）使用随机方法或者其它方法，产生一个有N个染色体的初始群体 pop(1)，；1:t（2）对群体中的每一个染色体popi(t)，计算其适应值)(tpopfitnessfii（3）若满足停止条件，则算法停止；否则，以概率 从pop(t)中随机选择一些染色体构成一个新种群 Njjiiffp1/,.,2,1)()1(Njtpoptnewpopj529.2.7 遗传算法的一般步骤（4）以概率 进行交叉产生一些新的染色体，得到一个新的群体 cp)1(tcrosspop（5）以一个较小的概率 使染色体的一个基因发生变异，形成 ；，成为一个新的群体 返回（2）。mp)1(tmutpop1:tt)1()(tmutpoptpop539.2.8 遗传算法的特点 o可直接对结构对象进行操作。o利用随机技术指导对一个被编码的参数空间进行高效率搜索。o采用群体搜索策略，易于并行化。o仅用适应度函数值来评估个体，并在此基础上进行遗传操作，使种群中个体之间进行信息交换。54第9章 遗传算法及其应用o 9.1 遗传算法的产生与发展遗传算法的产生与发展 o 9.2 遗传算法的基本算法遗传算法的基本算法 9.3 遗传算法的改进算法遗传算法的改进算法 o 9.4 基于遗传算法的生产调度方法基于遗传算法的生产调度方法559.3 遗传算法的改进算法 o9.3.1 双倍体遗传算法双倍体遗传算法o9.3.2 双种群遗传算法双种群遗传算法o9.3.3 自适应遗传算法自适应遗传算法56 9.3.1 双倍体遗传算法1.基本思想基本思想o 双倍体遗传算法采用显性显性和隐性隐性两个染色体同时进行进化，提供了一种记忆以前有用的基因块的功能。双倍体遗传算法采用显性遗传显性遗传。双倍体遗传延长了有用基因块的寿命，提高了算法的收敛能力，在变异概率低的情况下能保持一定水平的多样性。57 9.3.1 双倍体遗传算法 2.双倍体遗传算法的设计双倍体遗传算法的设计（1）编码）编码/解码解码：两个染色体（显性、隐性）（2）复制算子）复制算子：计算显性染色体的适应度，按照显性染色体 的复制概率将个体复制到下一代群体中。（3）交叉算子）交叉算子：两个个体的显性染色体交叉、隐性染色体也同时交叉。（4）变异算子：）变异算子：个体的显性染色体按正常的变异概率变异；隐性染色体按较大的变异概率变异。（5）双倍体遗传算法显隐性重排算子：）双倍体遗传算法显隐性重排算子：个体中适应值较大的染色体设为显性染色体，适应值较小的染色体设为隐性染色体。58n=0不 同 的 随 机 方 法 产生 两 个 初 始 群 体是 否 满 足 停 止准 则？计 算 适 应 度两 个 种 群 分 别 执 行选 择 操 作两 个 种 群 分 别 执 行交 叉 操 作两 个 种 群 分 别 执 行变 异 操 作随 机 选 择 两 个 种 群中 的 个 体生 成 机 器 甘 特 图，计 算 目 标 值n=n+1输出结果，结束是否随 机 个 体 及 最 优 个 体分 别 交 换 双种群遗传算法程序流程图双种群遗传算法程序流程图 599.3.2 双种群遗传算法 o 基本思想基本思想o 在遗传算法中使用多种群同时进化，并交换种群之间优秀个体所携带的遗传信息，以打破种群内的平衡态达到更高的平衡态，有利于算法跳出局部最优。o 多种群遗传算法多种群遗传算法：建立两个遗传算法群体，分别独立地运行复制、交叉、变异操作，同时当每一代运行结束以后，选择两个种群中的随机个体及最优个体分别交换。609.3.2 双种群遗传算法 2.双种群双种群遗传算法的设计遗传算法的设计（1）编码/解码设计（2）交叉算子、变异算子（3）杂交算子杂交算子设种群A与种群B，当A与B种群都完成了选择、交叉、变异算子后，产生一个随机数num，随机选择A中num个个体与A中最优个体，随机选择B中num个个体与B中最优个体，交换两者，以打破平衡态。61n=0不同的随机方法产生两个初始群体是否满足停止准则？计算适应度两个种群分别执行选择操作两个种群分别执行交叉操作两个种群分别执行变异操作随机选择两个种群中的个体生成机器甘特图，计算目标值n=n+1输出结果，结束是否随机个体及最优个体分别交换 双种群遗传算法程序流程图双种群遗传算法程序流程图 629.3.3 自适应遗传算法 1.基本思想基本思想 Srinvivas M.，Patnaik L.M.等在1994年提出一种自适应遗传算法(adaptive genetic algorithms，AGA)：能随适应度自动改变。cmPP和 AGA：当种群各个体适应度趋于一致或者趋于局部最优时，使 增加，以跳出局部最优；而当群体适应度比较分散时，使 减少，以利于优良个体的生存。cmPP和cmPP和 同时，对于适应度高于群体平均适应值的个体，选择较低的 ，使得该解得以保护进入下一代；对低于平均适应值的个体，选择较高的 值，使该解被淘汰。cmPP和cmPP和639.3.3 自适应遗传算法 2.自适应自适应遗传算法的步骤遗传算法的步骤（1）编码/解码设计。（2）初始种群产生：N（N 是偶数）个候选解，组成初始解集。（3）定义适应度函数为 ，计算适应度 。（4）按轮盘赌规则选择N 个个体，计算 。（5）将群体中的各个个体随机搭配成对，共组成N/2对，对每一对个体，按照自适应公式计算自适应交叉概率 ，随机产生R(0,1)，如果 则对该对染色体进行交叉操作。1/fobifmaxavgff和cRPcp64 2.自适应遗传算法的步骤自适应遗传算法的步骤（续）（续）（6）对于群体中的所有个体，共N个，按照自适应变异公式计算自适应变异概率 ，随机产生 R(0,1)，如果 则对该染色体进行交叉操作。（7）计算由交叉和变异生成新个体的适应度，新个体与父代一起构成新群体。（8）判断是否达到预定的迭代次数，是则结束；否则转（4）。mRP9.3.3 自适应遗传算法 mP653.适应的适应的交叉概率与变异概率交叉概率与变异概率avg,2avgavgmaxmax1c,)(ffkffffffkPavg4avgavgmaxmax3m,)(ffkffffffkP9.3.3 自适应遗传算法 普通自适应算法中，当个体适应度值越接近最大适应度值时，交叉概率与变异概率就越小；当等于最大适应度值时，交叉概率和变异概率为零。改进的思想：当前代的最优个体不被破坏，仍然保留（最优保存策略）；但较优个体要对应于更高的交叉概率与变异概率。66 F自适应方法自适应方法：9.3.3 自适应遗传算法 3.自适应的交叉概率与变异概率（续）自适应的交叉概率与变异概率（续）max20ccffPP当，；max20mmffPP当，。avg,1cavgavgmaxavg2c1c1cc,)(ffPffffffPPPPavgm1avgavgmaxmax2m1m1mm,)(ffPffffffPPPP12120.9,0.6,0.1,0.001ccmmPPPP67avg,2avgavgmaxmax1c ),2sin(ffkffffffkPavg,4avgavgmaxmax3m ),2sin(ffkffffffkP9.3.3 自适应遗传算法 S自适应方法自适应方法：自适应的交叉概率与变异概率（续）自适应的交叉概率与变异概率（续）12341.0,1.0,0.5,0.5,kkkk68avg,2avgavgmaxmax1c ),2cos(1ffkffffffkPavg,4avgavgmaxmax3m ),2cos(1ffkffffffkP9.3.3 自适应遗传算法 自适应的交叉概率与变异概率（续）自适应的交叉概率与变异概率（续）C 自适应方法自适应方法：12341.0,1.0,0.5,0.5,kkkk69第9章 遗传算法及其应用o 9.1 遗传算法的产生与发展遗传算法的产生与发展 o 9.2 遗传算法的基本算法遗传算法的基本算法 o 9.3 遗传算法的改进算法遗传算法的改进算法 9.4 基于遗传算法的生产调度方法基于遗传算法的生产调度方法709.4 基于遗传算法的生产调度方法 o9.4.1 基于遗传算法的流水车间调度方法基于遗传算法的流水车间调度方法o9.4.2 基于遗传算法的混合流水车间调度方法基于遗传算法的混合流水车间调度方法711.流水车间调度问题流水车间调度问题),1;,1(mjnitij 问题描述：n 个工件要在 m 台机器上加工，每个工件需要经过 m 道工序，每道工序要求不同的机器，n 个工件在 m 台机器上的加工顺序相同。工件在机器上的加工时间是给定的，设为 问题的目标：确定 n 个工件在每台机器上的最优加工顺序，使最大流程时间达到最小。9.4.1 基于遗传算法的流水车间调度方法721.流水车间流水车间调度问题调度问题 假设假设：(1)每个工件在机器上的加工顺序是给定的。(2)每台机器同时只能加工一个工件。(3)一个工件不能同时在不同的机器上加工。(4)工序不能预定。(5)工序的准备时间与顺序无关，且包含在加工时间中。(6)工件在每台机器上的加工顺序相同，且是确定的。9.4.1 基于遗传算法的流水车间调度方法731.流水车间调度问题流水车间调度问题9.4.1 基于遗传算法的流水车间调度方法 问题的数学模型：问题的数学模型：个工件、台机器的流水车间调度问题的完工时间：，上的加工完工时间在机器：工序 ),(kjkjcii：工件的调度,21njjj111)1,(jtjcmktkjckjckj,.,2,)1,(),(111nitjcjcijii,.,2,)1,()1,(11mknitkjckjckjckjiiii,.,2;,.,2,)1,(),(max),(1),(maxmjccn最大流程时间：nm最小使得调度目标：确定max21,cjjjn74 2.求解流水车间调度求解流水车间调度问题的遗传算法设计问题的遗传算法设计（1）FSP的编码方法的编码方法 对于FSP，最自然的编码方式是用染色体表示工件的顺序。9.4.1 基于遗传算法的流水车间调度方法对于有四个工件的FSP，第 个染色体 ，表示工件的加工顺序为：。k4,3,2,1 kv43,21,jjjj75 2.求解流水车间调度问题求解流水车间调度问题的遗传算法设计的遗传算法设计（2）FSP的适应度函数的适应度函数 :个染色体 的最大流程时间，FSP的适应度函数：kcmaxkkvkkcvevalmax1)(9.4.1 基于遗传算法的流水车间调度方法76求解求解FSP的遗传算法实例的遗传算法实例 例例1 1 Ho 和 Chang(1991)给出的5个工件、4台机器问题。j1 jt2jt3jt4jt工件131412530219553343234227641322141353355719 加工时间表加工时间表 9.4.1 基于遗传算法的流水车间调度方法77用遗传算法求解。选择交叉概率 ，变异概 ,种群规模为20，迭代次数 。6.0cp1.0mp50N表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 假设加工 个工件，每个工件都要依次经过 个加工工序，每个工序的并行机器数为 ，。所有工序中至少有一个工序存在并行机，即至少有一个 大于1。NSiM),1(SiiMSNSSNNNSaaaaaaaaaA2122221112119.4.2 基于遗传算法的混合流水车间调度方法2.混合流混合流水车间调度问题的遗传算法编码方法水车间调度问题的遗传算法编码方法 HFSP的编码矩阵的编码矩阵 ：上的一个实数，表示 工件的第 个工序在第台并行机上加工。：多个工件在同一台机器上加工同一个工序 ija)1,1(iMji)(ijaIntkjaIntaIntikij,)()(83 ，按 的升序来加工工件。，根据每个工件的前一个工序的完成时间来确定其加工顺序，前一个工序先完成的先加工。假如完成时间相同，也按 的升序来加工。1i1ija1ija9.4.2 基于遗传算法的混合流水车间调度方法染色体的长度：。1NNS,0,0,0,2122111211SNSSNNkaaaaaaaaInd 染色体：染色体：84o 例如，对于有3个工件个工件、3道工序道工序、各工序的并行机器数并行机器数分别为3，2，2的混合流水车间调度问题。9.4.2 基于遗传算法的混合流水车间调度方法2.14.21.13.21.26.19.14.21.2A 染色体染色体：2.1，2.4，1.9，0，1.6，2.1，2.3，0，1.1，2.4，1.2 编码矩阵编码矩阵：工序1工序2工序3机器1机器2机器3机器4机器5机器6机器7 混合流水车间调度的机器编号 853.基于遗传算法的求解方法基于遗传算法的求解方法 9.4.2 基于遗传算法的混合流水车间调度方法种群成员按适应值从好到坏依次排列种群成员按适应值从好到坏依次排列 按下式分配复制概率：按下式分配复制概率：Nfff21NiNiaaapNii1,.,2,1)1()1(11（1）初始群体初始群体的产生的产生（2）适应度函数）适应度函数的选择的选择:最大流程时间的倒数最大流程时间的倒数（3）选择（）选择（非线性排名策略非线性排名策略）86（5）变异操作：分段变异操作：分段 （4）交叉操作交叉操作 (a)(b)若 ，则 ，否则 (c)1,1 Randd1d),0(ijiaMRandr),0(ijaRandr rdaaijij9.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代的进化，目标函数最小值随着种群的进化逐渐地减小，最后收敛于极值，目标函数平均值也随着群体的进化逐渐减少，最后趋近于最优值。acPmP90得到的最好的染色体是：机器 1：机器 2：5,1 1,1 机器 3：机器 4：机器 5：机器 6：机器 7：机器 8：机器 9：7,1 2,1 10,1 3,1 4,1 12,1 5,2 7,2 2,2 6,2 11,2 9,2 7,3 9,3 12,3 11,3 0 2 11 17 0 2 7 9 0 4 8 12 16 3 8 11 14 18 20 24 2 7 11 12 21 8 11 18 20 24 29 17 23 14 3 9 28 7 12 18 21 24 9,1 5 6,1 11,1 8,1 2 4 1,2 3,2 10,3 4,2 17 12,2 8,2 26 5,3 14 6,3 26 8,3 10,2 4,3 2,3 19 21 1,3 3,3 29 20(时间 t)混合流水车间调度结果甘特图混合流水车间调度结果甘特图 9.4.2 基于遗传算法的混合流水车间调度方法91Artificial Intelligence Principles and ApplicationsTHE END