第6章进化算法及其应用AI应用3版

《第6章进化算法及其应用AI应用3版》由会员分享，可在线阅读，更多相关《第6章进化算法及其应用AI应用3版（142页珍藏版）》请在装配图网上搜索。

1、Artificial Intelligence Principles and Applications第第6章章进化算法及其应用进化算法及其应用教材：教材：王万良王万良人工智能及其应用人工智能及其应用（第（第3版）版）高等教育出版社，高等教育出版社，2016.22第6章进化算法及其应用o6.1进化算法的产生与发展进化算法的产生与发展o6.2基本遗传算法基本遗传算法o6.3遗传算法的改进算法遗传算法的改进算法o6.4基于遗传算法的生产调度方法基于遗传算法的生产调度方法o6.5差分进化算法及其应用差分进化算法及其应用o6.6量子进化算法及其应用量子进化算法及其应用3第6章进化算法及其应用o6.1进

2、化算法的产生与发展进化算法的产生与发展o6.2基本遗传算法基本遗传算法o6.3遗传算法的改进算法遗传算法的改进算法o6.4基于遗传算法的生产调度方法基于遗传算法的生产调度方法o6.5差分进化算法及其应用差分进化算法及其应用o6.6量子进化算法及其应用量子进化算法及其应用46.1进化算法的产生与发展6.1.1进化算法的概念进化算法的概念6.1.2进化算法的生物背景进化算法的生物背景6.1.2遗产算法的基本思想遗产算法的基本思想6.1.3遗产算法的发展历史遗产算法的发展历史6.1.4设计遗产算法设计遗产算法的基本原则与内容的基本原则与内容56.1.1进化算法的概念进进化化算算法法(evolutio

3、naryalgorithms，EA)是基于自然选择和自然遗传等生物进化机制的一种搜索算法。生物进化是通过繁殖、变异、竞争和选择实现的；而进化算法则主要通过选择、重组和变异这三种操作实现优化问题的求解。进化算法是一个“算法簇”，包括遗传算法(GA)、遗传规划、进化策略和进化规划等。进化算法的基本框架是遗传算法所描述的框架。进化算法可广泛应用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域。66.1.2进化算法的生物学背景o适适者者生生存存：最最适适合合自自然然环环境境的的群群体体往往往往产产生生了了更更大大的的后后代代群群体。体。o生物进化的基本过程：生物进化的基本过程：染染色色体体(

4、chromosome)：生生物物的遗传物质的主要载体。的遗传物质的主要载体。基基因因(gene)：扩扩展展生生物物性性状状的的遗遗传传物物质质的的功功能能单单元元和和结结构单位。构单位。基基因因座座（locus）：染染色色体体中中基因的位置。基因的位置。等等位位基基因因（alleles）：基基因因所取的值。所取的值。7第6章进化算法及其应用o6.1进化算法的产生与发展进化算法的产生与发展o6.2基本遗传算法基本遗传算法o6.3遗传算法的改进算法遗传算法的改进算法o6.4基于遗传算法的生产调度方法基于遗传算法的生产调度方法o6.5差分进化算法及其应用差分进化算法及其应用o6.6量子进化算法及其应

5、用量子进化算法及其应用86.2.1遗传算法的基本思想生物遗传概念生物遗传概念遗产算法中的应用遗产算法中的应用适者生存适者生存目标值比较大的解被选择的可能性大目标值比较大的解被选择的可能性大个体（个体（Individual）解解染色体（染色体（Chromosome）解的编码（字符串、向量等）解的编码（字符串、向量等）基因（基因（Gene）解的编码中每一分量解的编码中每一分量适应性（适应性（Fitness）适应度函数值适应度函数值群体（群体（Population）根根据据适适应应度度值值选选定定的的一一组组解解（解解的的个个数数为群体的规模）为群体的规模）婚配（婚配（Marry）交交叉叉（Cros

6、sover）选选择择两两个个染染色色体体进进行行交叉产生一组新的染色体的过程交叉产生一组新的染色体的过程变异（变异（Mutation）编码的某一分量发生变化的过程编码的某一分量发生变化的过程96.2.1遗传算法的基本思想 遗传算法的基本思想：遗传算法的基本思想：在在求求解解问问题题时时从从多多个个解解开开始始，然然后后通通过过一一定定的的法法则进行逐步迭代以产生新的解。则进行逐步迭代以产生新的解。106.2.2遗传算法的发展历史o1962年，Fraser提出了自然遗传算法。o1965年，Holland首次提出了人工遗传操作的重要性。o1967年，Bagley首次提出了遗传算法这一术语。o197

7、0年，Cavicchio把遗传算法应用于模式识别中。o1971年，Hollstien在论文计算机控制系统中人工遗传自适应方法中阐述了遗传算法用于数字反馈控制的方法。o1975年，美国J.Holland出版了自然系统和人工系统的适配；DeJong完成了重要论文遗传自适应系统的行为分析。o20世纪80年代以后，遗传算法进入兴盛发展时期。11遗传算法设计的基本内容 编码方案编码方案：怎样把优化问题的解进行编码。：怎样把优化问题的解进行编码。适应度函数适应度函数：怎样根据目标函数构建适应度函数。：怎样根据目标函数构建适应度函数。选择策略选择策略：优胜劣汰。：优胜劣汰。控控制制参参数数：种种群群的的规规

8、模模、算算法法执执行行的的最最大大代代数数、执行不同遗传操作的概率等。执行不同遗传操作的概率等。遗传算子遗传算子：选择、交叉、变异：选择、交叉、变异。算算法法终终止止准准则则：规规定定一一个个最最大大的的演演化化代代数数，或或算算法在连续多少代以后解的适应值没有改进。法在连续多少代以后解的适应值没有改进。12遗传算法的基本算法o遗传算法的五个基本要素遗传算法的五个基本要素：n参数编码n初始群体的设定n适应度函数的设计n遗传操作设计n控制参数设定136.2遗传算法的基本算法6.2.1编码编码6.2.2群体设定群体设定6.2.3适应度函数适应度函数6.2.4选择选择6.2.5交叉交叉6.2.6变异

9、变异6.2.7遗传算法遗传算法的一般步骤的一般步骤146.2.3编码 1.位串编码位串编码一一维维染染色色体体编编码码方方法法：将问题空间的参数编码为一维排列的染色体的方法。二二进进制制编编码码：用若干二进制数表示一个个体，将原问题的解空间映射到位串空间B=0，1上，然后在位串空间上进行遗传操作。（1）二进制编码二进制编码156.2.3编码(1)二进制编码二进制编码（续）（续）优点优点：类似于生物染色体的组成，算法易于用生物遗传理论解释，遗传操作如交叉、变异等易实现；算法处理的模式数最多。缺点：缺点：相邻整数的二进制编码可能具有较大的Hamming距离，降低了遗传算子的搜索效率。15：0111

10、116：10000要先给出求解的精度。求解高维优化问题的二进制编码串长，算法的搜索效率低。166.2.3编码 1.位串编码位串编码（2）Gray编码编码Gray编码:将二进制编码通过一个变换进行转换得到的编码。二进制串 Gray 二进制编码 Gray编码Gray编码 二进制编码 176.2.3编码 2.实数编码实数编码 采用实数表达法不不必必进进行行数数制制转转换换，可直接在解的表现型上进行遗传操作。多多参参数数映映射射编编码码的的基基本本思思想想：把每个参数先进行二进制编码得到子串，再把这些子串连成一个完整的染色体。多参数映射编码中的每个子串对应各自的编码参数，所以，可以有不同的串长度和参数

11、的取值范围有不同的串长度和参数的取值范围。181.初始种群的产生初始种群的产生6.2.4群体设定（1）根据问题固有知识，把握最优解所占空间在整个问题空间中的分布范围，然后，在此分布范围内设定初始群体。（2）随机产生一定数目的个体，从中挑选最好的个体加到初始群体中。这种过程不断迭代，直到初始群体中个体数目达到了预先确定的规模。192.种群规模的确定种群规模的确定6.2.4群体设定 模模式式定定理理表明：若群体规模为M，则遗传操作可从这M 个个体中生成和检测 个模式，并在此基础上能够不断形成和优化积木块，直到找到最优解。群体规模太小，遗传算法的优化性能不太好，易陷入局部最优解。群体规模太大，计算复

12、杂。201.1.将目标函数映射成适应度函数的方法将目标函数映射成适应度函数的方法6.2.5适应度函数 若目标函数为最大化最大化问题，则 若目标函数为最小化最小化问题，则将目标函数转换为求最大值的形式将目标函数转换为求最大值的形式,且保证函数值非负！且保证函数值非负！若目标函数为最大化最大化问题，则 若目标函数为最小化最小化问题，则211.1.将目标函数映射成适应度函数的方法将目标函数映射成适应度函数的方法(续）续）6.2.5适应度函数存在界限值预选估计困难或者不能精确估计的问题！存在界限值预选估计困难或者不能精确估计的问题！若目标函数为最大化最大化问题，则 若目标函数为最小化最小化问题，则 ：

13、目标函数界限的保守估计值。222.适应度函数的尺度变换适应度函数的尺度变换 在遗传算法中，将所有妨碍适应度值高的个体产生，从而 影 响 遗 传 算 法 正 常 工 作 的 问 题 统 称 为 欺欺 骗骗 问问 题题（deceptiveproblem）。6.2.5适应度函数 过过早早收收敛敛：缩小这些个体的适应度，以降低这些超级个体的竞争力。停停滞滞现现象象：改变原始适应值的比例关系，以提高个体之间的竞争力。适应度函数的尺尺度度变变换换（fitnessscaling）或者定定标标：对适应度函数值域的某种映射变换。232.适应度函数适应度函数的尺度变换的尺度变换(续）续）（1）线性变换：6.2.5

14、适应度函数满足满足最小适应度值非负 242.适应度函数适应度函数的尺度变换的尺度变换(续）续）（2）幂函数变换法：6.2.5适应度函数（3）指数变换法：256.2.6选择 1.个体选择概率分配方法个体选择概率分配方法选择操作也称为复制（reproduction）操作：从当前群体中按照一定概率选出优良的个体，使它们有机会作为父代繁殖下一代子孙。判断个体优良与否的准则是各个个体的适应度值：个体适应度越高，其被选择的机会就越多。266.2.6选择 1.个体选择概率分配方法个体选择概率分配方法（1）适适应应度度比比例例方方法法（fitnessproportionalmodel）或蒙特卡罗法或蒙特卡罗法

15、（MonteCarlo）各个个体被选择的概率和其适应度值成比例。个体 被选择的概率为：276.2.6选择 1.个体选择概率分配方法个体选择概率分配方法（2）排序方法排序方法（rank-basedmodel）线性排序：J.E.Baker 群体成员按适应值大小从好到坏依次排列：个体 按转盘式选择的方式选择父体286.2.6选择 1.个体选择概率分配方法个体选择概率分配方法（2）排序方法排序方法（rank-basedmodel）非线性排序：Z.Michalewicz 将群体成员按适应值从好到坏依次排列，并按下式分配选择概率：296.2.6选择 1.1.个体选择概率分配方法个体选择概率分配方法（2）排

16、序方法排序方法（rank-basedmodel）可用其他非线性函数来分配选择概率，只要满足以下条件：306.2.6选择 2.选择个体方法选择个体方法（1）转盘赌选择转盘赌选择（roulettewheelselection）按个体的选择概率产生一个轮盘，轮盘每个区的角度与个体的选择概率成比例。产生一个随机数，它落入转盘的哪个区域就选择相应的个体交叉。第1轮产生一个随机数：0.81 第2轮产生一个随机数：0.32 316.2.6选择 2.选择个体方法选择个体方法（2）锦标赛选择方法锦标赛选择方法（tournamentselectionmodel）锦锦标标赛赛选选择择方方法法：从群体中随机选择个个体

17、，将其中适应度最高的个体保存到下一代。这一过程反复执行，直到保存到下一代的个体数达到预先设定的数量为止。随随机机竞竞争争方方法法（stochastictournament）：每次按赌轮选择方法选取一对个体，然后让这两个个体进行竞争，适应度高者获胜。如此反复，直到选满为止。326.2.6选择 2.选择个体方法选择个体方法（3）和选择 从规模为 的群体中随机选取个体通过重组和变异生成 个后代，再选取 个最优的后代作为新一代种群。从 个后代与其父体共 中选取 个最优的后代。336.2.6选择 2.选择个体方法选择个体方法（4）Boltzmann锦标赛选择 最最佳佳个个体体（elitistmodel）

18、保保存存方方法法：把群体中适应度最高的个体不进行交叉而直接复制到下一代中，保证遗传算法终止时得到的最后结果一定是历代出现过的最高适应度的个体。（5）最佳个体保存方法 随机选取两个个体 ，若 则选择适应值好的作为胜者，否则计算概率 ，若 ，选择差解，否则选择好解。346.2.7交叉 1.基本的交叉算子基本的交叉算子（1）一点交叉一点交叉（single-pointcrossover）一点交叉：在个体串中随机设定一个交叉点，实行交叉时，该点前或后的两个个体的部分结构进行互换，并生成两个新的个体。二点交叉：随机设置两个交叉点，将两个交叉点之间的码串相互交换。（2）二点交叉二点交叉（two-pointc

19、rossover）356.2.7交叉 1.基本的交叉算子（续）基本的交叉算子（续）均匀交叉：按照均匀概率抽取一些位，每一位是否被选取都是随机的，并且独立于其他位。然后将两个个体被抽取位互换组成两个新个体。（3）均匀交叉均匀交叉（uniformcrossover）或一致交叉366.2.7交叉 2.修正的交叉方法修正的交叉方法（1）部部 分分 匹匹 配配 交交 叉叉 PMX：Goldberg D.E.和 R.Lingle(1985)376.2.7交叉 2.修正的交叉方法修正的交叉方法(续）续）（2）顺序交叉顺序交叉OX：DavisL.(1985)（3）循环交叉循环交叉CX：SmithD.(1985

20、)386.2.7交叉 3.实数编码的交叉方法实数编码的交叉方法（1）离散交叉）离散交叉（discretecrossover）部部分分离离散散交交叉叉：在父解向量中选择一部分分量，然后交换这些分量。二进制的点式交叉二进制的点式交叉 整整体体离离散散交交叉叉：以0.5的概率交换父体的所有分量。二进制编码的均匀性交叉二进制编码的均匀性交叉21ss 与396.2.7交叉 3.实数编码的交叉方法（续）实数编码的交叉方法（续）（2）算术交叉算术交叉（arithmeticalcrossover）部部分分算算术术：先在父解向量中选择一部分分量，如第 个分量以后的所有分量，然后生成 个0，1区间的随机数，并将两

21、个后代定义为：406.2.7交叉3.实数编码的交叉方法（续）实数编码的交叉方法（续）（2）算术交叉算术交叉（arithmeticalcrossover）整整体体算算术术交交叉叉：先生成n 个区间的随机数，则后代分别定义为：416.2.8变异 1.整数编码的变异方法整数编码的变异方法（1）位位点点变变异异：群体中的个体码串，随机挑选一个或多个基因座，并对这些基因座的基因值以变异概率作变动。（2）逆逆转转变变异异：在个体码串中随机选择两点（逆转点），然后将两点之间的基因值以逆向排序插入到原位置中。（3）插插入入变变异异：在个体码串中随机选择一个码，然后将此码插入随机选择的插入点中间。426.2.8

22、变异 1.整数编码的变异方法（续）整数编码的变异方法（续）（4）互互换换变变异异：随机选取染色体的两个基因进行简单互换。（5）移移动动变变异异：随机选取一个基因，向左或者向右移动一个随机位数。（6）自自适适应应变变异异：类似于位点变异，但变异概率随群体中个体的多样性程度而自适应调整。436.2.8变异 2.实数编码的变异方法实数编码的变异方法（1）均匀性变异均匀性变异 均匀性变异均匀性变异：在父解向量中随机地选择一个分量（第 个），然后在 中以均匀概率随机选择 代替 以得到 ，即 446.2.8变异 2.实数编码的变异方法（续）实数编码的变异方法（续）（2）正态性变异正态性变异（normald

23、istributedmutation）456.2.8变异 2.实数编码的变异方法（续）实数编码的变异方法（续）（3）非一致性变异非一致性变异Z.Michalewicz首先提出将变异算子的结果与演化代数联系起来。在演化初期，变异范围相对较大，而随着演化的推进，变异范围越来越小，起着一种对演化系统的微调作用。466.2.8变异 2.实数编码的变异方法（续）实数编码的变异方法（续）（3）非一致性变异非一致性变异476.2.8变异 2.实数编码的变异方法（续）实数编码的变异方法（续）（4）自适应变异自适应变异自适应变异方式与非一致性变异算子相同，只是将其中的演化代数 改为 ，函数表达式变为：486.2

24、.10遗传算法的一般步骤496.2.10遗传算法的一般步骤（1）使用随机方法或者其它方法，产生一个有N个染色体的初始群体pop(1)，；（2）对群体中的每一个染色体popi(t)，计算其适应值（3）若满足停止条件，则算法停止；否则，以概率从pop(t)中随机选择一些染色体构成一个新种群 506.2.10遗传算法的一般步骤（4）以概率 进行交叉产生一些新的染色体，得到一个新的群体 （5）以一个较小的概率使染色体的一个基因发生变异，形成；，成为一个新的群体返回（2）。516.2.11遗传算法的特点 可直接对结构对象进行操作。利用随机技术指导对一个被编码的参数空间进行高效率搜索。采用群体搜索策略，易

25、于并行化。仅用适应度函数值来评估个体，并在此基础上进行遗传操作，使种群中个体之间进行信息交换。52第6章遗传算法及其应用o6.1遗传算法的产生与发展遗传算法的产生与发展o6.2遗传算法的基本算法遗传算法的基本算法6.3遗传算法的改进算法遗传算法的改进算法o6.4基于遗传算法的生产调度方法基于遗传算法的生产调度方法536.3遗传算法的改进算法 6.3.1双倍体遗传算法双倍体遗传算法6.3.2双种群遗传算法双种群遗传算法6.3.3自适应遗传算法自适应遗传算法546.3.1双倍体遗传算法1.基本思想基本思想 双倍体遗传算法采用显显性性和隐隐性性两个染色体同时进行进化，提供了一种记忆以前有用的基因块的

26、功能。双倍体遗传算法采用显性遗传显性遗传。双倍体遗传延长了有用基因块的寿命，提高了算法的收敛能力，在变异概率低的情况下能保持一定水平的多样性。556.3.1双倍体遗传算法2.双倍体双倍体遗传遗传算法的算法的设计设计（1）编码）编码/解码解码：两个染色体（显性、隐性）（2）复复制制算算子子：计算显性染色体的适应度，按照显性染色体的复制概率将个体复制到下一代群体中。（3）交交叉叉算算子子：两个个体的显性染色体交叉、隐性染色体也同时交叉。（4）变变异异算算子子：个体的显性染色体按正常的变异概率变异；隐性染色体按较大的变异概率变异。（5）双双倍倍体体遗遗传传算算法法显显隐隐性性重重排排算算子子：个体中

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

28、叉、变异算子后，产生一个随机数num，随机选择A中num个个体与A中最优个体，随机选择B中num个个体与B中最优个体，交换两者，以打破平衡态。58 双种群遗传算法程序流程图双种群遗传算法程序流程图 596.3.3自适应遗传算法 1.基本思想基本思想SrinvivasM.，PatnaikL.M.等在1994年提出一种自适应遗传算法(adaptivegeneticalgorithms，AGA)：能随适应度自动改变。AGA：当种群各个体适应度趋于一致或者趋于局部最优时，使增加，以跳出局部最优；而当群体适应度比较分散时，使减少，以利于优良个体的生存。同时，对于适应度高于群体平均适应值的个体，选择较低的

29、 ，使得该解得以保护进入下一代；对低于平均适应值的个体，选择较高的 值，使该解被淘汰。606.3.3自适应遗传算法 2.自适应自适应遗传算法的步骤遗传算法的步骤（1）编码/解码设计。（2）初始种群产生：N（N 是偶数）个候选解，组成初始解集。（3）定义适应度函数为，计算适应度。（4）按轮盘赌规则选择N 个个体，计算。（5）将群体中的各个个体随机搭配成对，共组成N/2对，对每一对个体，按照自适应公式计算自适应交叉概率，随机产生R(0,1)，如果则对该对染色体进行交叉操作。612.自适应遗传算法的步骤自适应遗传算法的步骤（续）（续）（6）对于群体中的所有个体，共N个，按照自适应变异公式计算自适应变

30、异概率，随机产生R(0,1)，如果则对该染色体进行交叉操作。（7）计算由交叉和变异生成新个体的适应度，新个体与父代一起构成新群体。（8）判断是否达到预定的迭代次数，是则结束；否则转（4）。6.3.3自适应遗传算法623.适应的适应的交叉概率与变异概率交叉概率与变异概率6.3.3自适应遗传算法 普通自适应算法中，当个体适应度值越接近最大适应度值时，交叉概率与变异概率就越小；当等于最大适应度值时，交叉概率和变异概率为零。改进的思想：当前代的最优个体不被破坏，仍然保留（最优保存策略）；但较优个体要对应于更高的交叉概率与变异概率。63F自适应方法自适应方法：6.3.3自适应遗传算法 3.自适应的交叉概

31、率与变异概率（续）自适应的交叉概率与变异概率（续）646.3.3自适应遗传算法S自适应方法自适应方法：3.自适应的交叉概率与变异概率（续）自适应的交叉概率与变异概率（续）656.3.3自适应遗传算法3.自适应的交叉概率与变异概率（续）自适应的交叉概率与变异概率（续）C自适应方法自适应方法：66第6章遗传算法及其应用o6.1遗传算法的产生与发展遗传算法的产生与发展o6.2遗传算法的基本算法遗传算法的基本算法o6.3遗传算法的改进算法遗传算法的改进算法6.4基于遗传算法的生产调度方法基于遗传算法的生产调度方法676.4基于遗传算法的生产调度方法 6.4.1基于遗传算法的流水车间调度方法基于遗传算法

32、的流水车间调度方法6.4.2基于遗传算法的混合流水车间调度方法基于遗传算法的混合流水车间调度方法681.流水车间调度问题流水车间调度问题问题描述：n 个工件要在m 台机器上加工，每个工件需要经过m 道工序，每道工序要求不同的机器，n 个工件在m 台机器上的加工顺序相同。工件在机器上的加工时间是给定的，设为问题的目标：确定n 个工件在每台机器上的最优加工顺序，使最大流程时间达到最小。6.4.1基于遗传算法的流水车间调度方法691.流水车间流水车间调度问题调度问题 假设假设：(1)每个工件在机器上的加工顺序是给定的。(2)每台机器同时只能加工一个工件。(3)一个工件不能同时在不同的机器上加工。(4

33、)工序不能预定。(5)工序的准备时间与顺序无关，且包含在加工时间中。(6)工件在每台机器上的加工顺序相同，且是确定的。6.4.1基于遗传算法的流水车间调度方法701.流水车间调度问题流水车间调度问题6.4.1基于遗传算法的流水车间调度方法 问题的数学模型：问题的数学模型：个工件、台机器的流水车间调度问题的完工时间：712.求解流水车间调度求解流水车间调度问题的遗传算法设计问题的遗传算法设计（1）FSP的编码方法的编码方法 对于FSP，最自然的编码方式是用染色体表示工件的顺序。6.4.1基于遗传算法的流水车间调度方法对于有四个工件的FSP，第 个染色体 ，表示工件的加工顺序为：。722.求解流水

34、车间调度问题求解流水车间调度问题的遗传算法设计的遗传算法设计（2）FSP的适应度函数的适应度函数 :个染色体 的最大流程时间，FSP的适应度函数：6.4.1基于遗传算法的流水车间调度方法733.求解求解FSP的遗传算法实例的遗传算法实例例例1 1 Ho和Chang(1991)给出的5个工件、4台机器问题。工件131412530219553343234227641322141353355719 加工时间表加工时间表6.4.1基于遗传算法的流水车间调度方法74用遗传算法求解。选择交叉概率 ，变异概 ,种群规模为20，迭代次数 。表9.3遗传算法运行的结果总运行次数最好解最坏解平均最好解的频率最好解

35、的平均代数20213221213.950.85126.4.1基于遗传算法的流水车间调度方法用穷举法求得最优解：4-2-5-1-3，加工时间：213；最劣解：1-4-2-3-5，加工时间：294；平均解的加工时间：265。遗传算法运行的结果遗传算法运行的结果 75表9.3遗传算法运行的结果最优解收敛图最优解收敛图6.4.1基于遗传算法的流水车间调度方法76平均值收敛图平均值收敛图6.4.1基于遗传算法的流水车间调度方法77机器甘特图机器甘特图6.4.1基于遗传算法的流水车间调度方法786.4.2基于遗传算法的混合流水车间调度方法1.混合流水混合流水车间调度问题车间调度问题 问题的特征问题的特征：

36、在某些工序上存在并行机器并行机器。问问题题的的描描述述：需要加工多个工件，所有工件的加工路线都相同，都需要依次通过几道工序，在所有工序中至少有一个工序存在着多台并行机器。需需要要解解决决的的问问题题：确确定定并并行行机机器器的的分分配配情情况况以及同同一台机器上工件的加工排序一台机器上工件的加工排序。目标目标：最小化最大流程时间。79 假设加工 个工件，每个工件都要依次经过 个加工工序，每个工序的并行机器数为 ，。所有工序中至少有一个工序存在并行机，即至少有一个 大于1。6.4.2基于遗传算法的混合流水车间调度方法2.混合流混合流水车间调度问题的遗传算法编码方法水车间调度问题的遗传算法编码方法

37、HFSP的编码矩阵的编码矩阵 ：上的一个实数，表示 工件的第 个工序在第台并行机上加工。：多个工件在同一台机器上加工同一个工序 80 ，按 的升序来加工工件。，根据每个工件的前一个工序的完成时间来确定其加工顺序，前一个工序先完成的先加工。假如完成时间相同，也按 的升序来加工。6.4.2基于遗传算法的混合流水车间调度方法染色体的长度：。染色体：染色体：81o例如，对于有3个个工工件件、3道道工工序序、各工序的并并行行机机器器数数分别为3，2，2的混合流水车间调度问题。6.4.2基于遗传算法的混合流水车间调度方法 染色体染色体：2.1，2.4，1.9，0，1.6，2.1，2.3，0，1.1，2.4

38、，1.2 编码矩阵编码矩阵：混合流水车间调度的机器编号 823.基于遗传算法的求解方法基于遗传算法的求解方法9.4.2基于遗传算法的混合流水车间调度方法种群成员按适应值从好到坏依次排列种群成员按适应值从好到坏依次排列 按下式分配复制概率：按下式分配复制概率：（1）初始群体初始群体的产生的产生（2）适应度函数）适应度函数的选择的选择:最大流程时间的倒数最大流程时间的倒数（3）选择（）选择（非线性排名策略非线性排名策略）83（5）变异操作：分段变异操作：分段 （4）交叉操作交叉操作(a)(b)若，则，否则(c)6.4.2基于遗传算法的混合流水车间调度方法分段交叉分段交叉：在两个父体的各段中随机选取

39、一部分基因，然后交换，得到子代个体。844.调度实例调度实例 某汽车发动机厂金加工车间要加工12个工件，每个工件都有车、刨、磨3个工序，现有3台车床，2台刨床，4台磨床，每台机床的加工能力不同。6.4.2基于遗传算法的混合流水车间调度方法85工件工件工序工序1工序工序2工序工序3机器机器1机器机器2机器机器3机器机器4机器机器5机器机器6机器机器7机器机器8 8机器机器9 9122345232324543434543654423425443465365854533134656654234395752446343583547533649254127865103643448671152435676

40、512654543475工件在每个机器上的加工时间工件在每个机器上的加工时间6.4.2基于遗传算法的混合流水车间调度方法86得到的最好的染色体是：最好的染色体：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.676.4.2基于遗传算法的混合流水车间调度方法算法中使用的参数为=0.07，

41、=0.80，=0.01，种群规模为30，种群经过100代的进化，目标函数最小值随着种群的进化逐渐地减小，最后收敛于极值，目标函数平均值也随着群体的进化逐渐减少，最后趋近于最优值。87得到的最好的染色体是：混合流水车间调度结果甘特图混合流水车间调度结果甘特图 6.4.2基于遗传算法的混合流水车间调度方法8888第6章进化算法及其应用o6.1进化算法的产生与发展进化算法的产生与发展o6.2基本遗传算法基本遗传算法o6.3遗传算法的改进算法遗传算法的改进算法o6.4基于遗传算法的生产调度方法基于遗传算法的生产调度方法o6.5差分进化算法及其应用差分进化算法及其应用o6.6量子进化算法及其应用量子进化

42、算法及其应用896.5差分进化算法及其应用差分进化算法及其应用o差分进化算法的概念：差分进化算法的概念：n差分进化算法（差分进化算法（DEDE）或称为差分演化算法、）或称为差分演化算法、微微分进化算法分进化算法、微分演化算法、差异演化算法。、微分演化算法、差异演化算法。n19951995年由年由Rainer StornRainer Storn和和Kenneth PriceKenneth Price提出。提出。nDEDE是一种采用实数矢量编码在连续空间中进行是一种采用实数矢量编码在连续空间中进行随机搜索的优化算法。随机搜索的优化算法。n差分进化算法是一种基于实数编码的具有保优差分进化算法是一种基

43、于实数编码的具有保优思想的贪婪思想的贪婪遗传算法遗传算法。906.5差分进化算法及其应用差分进化算法及其应用 6.5.1差分进化算法差分进化算法6.5.2差分进化算法的流程差分进化算法的流程6.5.3差分进化算法的改进差分进化算法的改进916.5.1差分进化算法差分进化算法o差分进化算法的基本要素差分进化算法的基本要素：n参数编码n初始群体的产生n适应度函数的设计n差分操作设计n控制参数设置926.5.1差分进化算法差分进化算法 参数编码参数编码DE采用实数编码方式。DE中的个体i表示为：。D表示问题空间维数，t 表示进化代数。为实数。不不必必进进行行数数制制转转换换，可直接在解的表现型上进行

44、进化操作。93初始种群的产生初始种群的产生根据问题固有知识，把握解参数变量 的取值范围，然后，在此范围内设定初始群体。通常寻找初始种群的一个方法是从给定边界约束内的值中随机选择。设参数变量的界限为 ，则：NP表示种群规模，表示在0,1之间产生的均匀随机数。6.5.1差分进化算法差分进化算法 94适应度函数的设计适应度函数的设计在差分进化算法中，差分操作主要通过适应度函数的导向来实现的，它是用来评估个体相对于整个群体的优劣的相对值的大小。通常根据具体问题定义适应度函数，最直观的方法是直接将待求解优化问题的目标函数作为适应度函数。具体设计方法与遗传算法相似。具体设计方法与遗传算法相似。6.5.1差

45、分进化算法差分进化算法 95差分操作设计差分操作设计变异变异对每个目标个体 ，它的变异个体 的产生方式根据差向量的个数以及父代基向量的选取方式的不同分如下几种：（1）（2）（3）6.5.1差分进化算法差分进化算法 96差分操作设计差分操作设计变异（续）变异（续）（4）（5）其中，、和 表示随机产生的 之间互异且不等于目标个体序号 的自然数。表示缩放比例因子，是一个实常数因数，控制偏差变量的放大作用。6.5.1差分进化算法差分进化算法 97差分操作设计差分操作设计变异（续）变异（续）将不符合边界约束的参数用在可行域中随机产生的参数代替。将不符合边界约束的参数映射到可行域内。若若变变异异产产生生的

46、的新新个个体体参参数数值值不不符符合合边边界界约约束束条条件件，如如何处理？何处理？边界条件的处理边界条件的处理例如：参数，那么若变异得到的超出该范围，可通过函数来映射到0,1范围。6.5.1差分进化算法差分进化算法 98差分操作设计差分操作设计交叉交叉二项式（bin）交叉：其中，为第个0,1之间的随机数；为之间的随机自然数，它确保了至少从获得一个参数；为交叉概率，取值范围为0,1。对目标个体和变异个体实施交叉操作生成试验个体的过程称为交叉，。DE交叉操作分二项式（bin）交叉和指数（exp）交叉两种交叉方式。6.5.1差分进化算法差分进化算法 99差分操作设计差分操作设计二项式交叉（例）二项

47、式交叉（例）6.5.1差分进化算法差分进化算法 100差分操作设计差分操作设计指数交叉指数交叉指数（exp）交叉。对第位参数：若：取目标个体上的第位参数作为试验个体上的第位参数；若：取变异个体上的第位参数作为试验个体上的第位参数；若：随机产生0,1之间的随机实数，若，取变异个体上的第位参数作为试验个体上的第位参数，否则，试验个体上剩下的所有参数都从目标个体继承。6.5.1差分进化算法差分进化算法 101差分操作设计差分操作设计指数交叉（例）指数交叉（例）6.5.1差分进化算法差分进化算法 102差分操作设计差分操作设计选择选择DE采用贪婪准则在和之间进行选择，产生下一代个体：表示适应度函数。上

48、式是针对最大化问题而言，若是最小化问题，那么选择试验个体作为子代个体的条件是。6.5.1差分进化算法差分进化算法 103控制参数设置控制参数设置DE的搜索性能取决于算法全局探索和局部开发能力的平衡，而这在很大程度上依赖于算法的控制参数的选取。种群规模。种群规模NP必须满足以确保DE具有足够的不同的变异向量，根据经验，NP的合理选择在5D10D（D为问题空间的维数）之间。缩放比例因子。缩放比例因子是一个实常数，它决定偏差向量的放大比例。F越大，算法更容易逃出局部极小点，更容易收敛到全局最优点。一般取0.7。6.5.1差分进化算法差分进化算法 104控制参数设置（续）控制参数设置（续）交叉概率。交

49、叉概率CR是一个范围在0,1的实数，它控制着一个试验个体参数来自于变异个体的概率。CR越大，算法更容易收敛，但易发生早熟现象。CR的一个较好的选择是0.3。最大迭代代数。一般而言，最大迭代次数越大，最优解越精确，但计算时间越长，要根据具体问题设定。终止条件。除最大进化代数可作为DE的终止条件外，有时还需要其它判定准则，一般当目标函数值小于阈值时程序终止，阈值常选为10-6。6.5.1差分进化算法差分进化算法 105控制参数设置（续）控制参数设置（续）F，CR与NP一样，在搜索过程中是常数，一般F和CR影响搜索过程的收敛速度和鲁棒性，它们的优化值不仅依赖于目标函数的特性，还与NP有关。通常可通过

50、在对不同值做一些试验之后利用试验和结果误差找到F，CR和NP的合适值。6.5.1差分进化算法差分进化算法 106开始初始化种群、DE算法参数；设置进化代数t0计算群体中每个个体适应值变异操作交叉操作选择操作tt1是否满足终止条件最优结果YN6.5.2差分进化算法的流程差分进化算法的流程 107差分进化算法的特点差分进化算法的特点 算法原理简单，容易实现；算法通用，不依赖于问题信息。分散搜索，能在整个解空间进行全局搜索。保优搜索，具有记忆个体最优解的能力。协同搜索，具有利用个体局部信息和群体全局信息指导算法进一步搜索的能力。直接对结构对象进行操作，不存在对目标函数的限定（如要求函数可导或连续）。

51、1086.5差分进化算法及其应用差分进化算法及其应用6.5.1差分进化算法差分进化算法6.5.2差分进化算法的流程差分进化算法的流程6.5.3差分进化算法的改进差分进化算法的改进1096.5.3差分进化算法的改进算法差分进化算法的改进算法DE的收敛速度远胜于一般的进化算法，但基本算法易陷入局部最优，存在早熟收敛现象。许多学者提出了改进型的DE。目前，对DE的改进工作主要包括：改进进化操作：控制参数的取值、参加变异的父代基向量的选择、差分策略以及差分操作等改进；嵌入新操作：在DE中嵌入有效的局部搜索策略、引入加速和迁移操作以及搜索空间扩展机制等；多种群：将DE分成多个子种群，各个子种群独立寻优，

52、在跨种群间实现信息交流，提高摆脱局部极值的能力。混合算法：与遗传算法、蚁群算法等算法进行混合。1106.6量子进化算法及其应用量子进化算法及其应用o6.6.1量子进化算法的基本概念量子进化算法的基本概念o6.6.2基本量子进化算法基本量子进化算法o6.6.3基本量子进化算法的流程基本量子进化算法的流程o6.6.4基于量子进化算法的生产调度方法基于量子进化算法的生产调度方法1116.6量子进化算法及其应用量子进化算法及其应用6.6.1量子进化算法的基本概念量子进化算法的基本概念o6.6.2基本量子进化算法基本量子进化算法o6.6.3基本量子进化算法的流程基本量子进化算法的流程o6.6.4基于量子

53、进化算法的生产调度方法基于量子进化算法的生产调度方法112量子进化算法的产生量子进化算法的产生理理论论上上已已经经证证明明：进进化化算算法法能能在在概概率率意意义义上上以以随随机机的的方方式式寻寻求求问问题题的的最最优优解解。但但在在实实际际应应用用中中也也存存在在着着容容易易产产生生早早熟熟、收收敛敛速速度度慢慢、局局部部寻寻优优能能力力差等缺点。差等缺点。能能否否将将量量子子理理论论应应用用到到经经典典进进化化算算法法中中去去，通通过过对对经经典典的的问问题题表表示示作作一一些些调调整整，使使其其具具有有量量子子理理论论的的特特点点，从从而而进进行行一一些些类类量量子子的的计计算算来来实实

54、现现更更为为有效的算法呢？有效的算法呢？113量子进化算法的产生量子进化算法的产生量量子子计计算算（QuantumComputing）是是20世世纪纪80年年代代初初提提出出的的一一种种新新兴兴计计算算理理论论，是是物物理理学学中中的的量量子子力力学学和计算机科学相结合的产物和计算机科学相结合的产物.量量子子计计算算利利用用量量子子叠叠加加、纠纠缠缠和和干干涉涉等等量量子子态态所所具具有的特性，通过并行计算来求解问题。有的特性，通过并行计算来求解问题。114量子进化算法的产生量子进化算法的产生量子计算理论量子计算理论传统进化算法传统进化算法量子进化算法量子进化算法将量子物理学引入到计算机科学，

55、利用量子理论中量子态将量子物理学引入到计算机科学，利用量子理论中量子态的叠加纠缠等特性，通过量子并行计算解决问题的叠加纠缠等特性，通过量子并行计算解决问题模拟自然界物种进化机制的启发式算法，基于适者生存的思模拟自然界物种进化机制的启发式算法，基于适者生存的思想，将问题的求解表达成想，将问题的求解表达成“染色体染色体”的适者生存的过程，通的适者生存的过程，通过染色体群的不断进化最终收敛到问题的满意解过染色体群的不断进化最终收敛到问题的满意解一种基于量子位、量子叠加态等量子机制的进化算法，建立在量子的态矢量表达基础上，将量子比特量子比特的概率幅表示的概率幅表示应用于染色体的编码。115量子进化算法

56、的产生量子进化算法的产生国国际际上上最最早早将将量量子子计计算算和和进进化化算算法法相相结结合合的的是是在在1996年年，Narayanan将将量量子子理理论论中中的的“宇宇宙宙”概概念念类类比比为为遗遗传传算算法法中中的的种种群群，指指出出量量子子态态的的干干涉涉作作用用可可以以通通过过遗遗传传算算法法的的交交叉叉操操作作实实现现，设设计计了了量量子子衍衍生生遗遗传传算算法法的的框框架架，解解决决了了小小规规模模TSP问题。问题。Han在在2000到到2004年年间间，提提出出了了一一系系列列量量子子进进化化算算法法的的新新想想法法，包包括括量量子子遗遗传传算算法法、并并行行量量子子遗遗传传

57、算算法法、基基于于移移民民操操作作的的量量子子进进化化算算法法、基基于于一一种种新新的的终终止止判判断断条条件件的的两两段段式式量量子子进进化化算算法法，同同时时对对算算法法的的参参数数设设计计问问题题进进行行了了探探讨讨，并并成成功应用于背包问题，取得了优于传统遗传算法的效果。功应用于背包问题，取得了优于传统遗传算法的效果。1166.6.1量子进化算法的基本概念量子进化算法的基本概念o量子位（量子比特量子位（量子比特Q-bit）在在量量子子进进化化算算法法中中，染染色色体体不不是是用用确确定定的的值值表表示示，而而是是采采用用量量子子位位表表示示，或或者者概概率率幅幅表表示示。一一个个量量子

58、子位位的的状状态态可可以以取取值值|0或或|1，还还可可以以是是两两种种状状态态的的线线性性叠叠加加，因因此此其状态可以表示为：其状态可以表示为：其中,和为复数，分别表示状态|0和|1的概率幅，和表示该量子位处于状态|0和|1的概率大小。117o量子染色体量子染色体进进化化算算法法EA常常用用编编码码方方式式有有二二进进制制编编码码、十十进进制制编编码码和和符号编码。符号编码。量量子子进进化化算算法法采采用用了了一一种种新新颖颖的的编编码码方方式式量量子子比比特特编编码码，具体形式可以描述为：，具体形式可以描述为：这这种种表表示示方方法法可可以以表表征征任任意意的的线线性性叠叠加加态态。基基于

59、于概概率率，长长度为度为m的染色体可以表示的染色体可以表示2m种状态。种状态。6.6.1量子进化算法的基本概念量子进化算法的基本概念118例如，一个具有如下概率幅的例如，一个具有如下概率幅的3量子比特组成的量子染色体：量子比特组成的量子染色体：而而传传统统的的编编码码方方式式只只能能表表示示一一个个具具体体的的状状态态，所所以以QEAQEA比比其他传统进化算法更容易保持种群的多样性。其他传统进化算法更容易保持种群的多样性。系统状态可以表示为：系统状态可以表示为：6.6.1量子进化算法的基本概念量子进化算法的基本概念119o6.6.1量子进化算法的基本概念量子进化算法的基本概念6.6.2基本量子

60、进化算法基本量子进化算法o6.6.3基本量子进化算法的流程基本量子进化算法的流程o6.6.4基于量子进化算法的生产调度方法基于量子进化算法的生产调度方法6.6量子进化算法及其应用量子进化算法及其应用120o量子进化算法基本要素量子进化算法基本要素：n染色体编码n初始化群体n量子观测n量子评价n量子更新n量子进化6.6.2基本量子进化算法基本量子进化算法121o染色体编码染色体编码n二进制编码令t=0，n多进制编码多进制编码 根据二进制编码的特点，可以用两个量子位表示根据二进制编码的特点，可以用两个量子位表示4个状态，个状态，以此类推，用以此类推，用n个量子位表示个量子位表示 个状态。个状态。多

61、进制编码是将二进制编码扩展到多进制编码是将二进制编码扩展到n维，每一维都代表一维，每一维都代表一个量子比特，通常用一个量子矩阵表示。个量子比特，通常用一个量子矩阵表示。矩阵的每一行即一个二进制编码表示，矩阵由矩阵的每一行即一个二进制编码表示，矩阵由n列这样的列这样的二进制编码组成，采用多个量子位来表示一个多状态基因，对二进制编码组成，采用多个量子位来表示一个多状态基因，对实际问题的编码设计通用性好且实现简单。实际问题的编码设计通用性好且实现简单。6.6.2基本量子进化算法基本量子进化算法122o初始化群体初始化群体初初始始化化方方法法一一：初始种群中量子染色体的所有量子位的初始值均可设为 。这

62、种初始化方法十分简单，但没有考虑到具体的应用问题，因此优化效果有一定的局限性。初初始始化化方方法法二二：在第一阶段中随机初始化量子位，经过若干次量子进化搜索后，将得到的优良结果用于第二阶段量子染色体的初始化，进行进一步的解空间的全局搜索。所以称为两阶段初始化方法。6.6.2基本量子进化算法基本量子进化算法123o量子观测量子观测：量子种群：量子种群Q(t)观测种群观测种群R R(t)量子观测的结果和作用就是将只有在量子计算机中才能观测的信息转换成在二进制计算机中能表示的信息。这一过程将导致具有2m个状态的量子染色体退变成一个确定的状态，在量子理论中被称为量子坍塌量子坍塌（collapse）。量

63、量子子观观测测的的一一般般方方法法：根据概率幅的取值情况构造长度为m的二进制串。产生0,1上的一个随机数s，若s ，则对应取值为1，否为0。由此得到二进制观测种群R(t)。6.6.2基本量子进化算法基本量子进化算法124o量子评价量子评价量子评价即根据实际的应用问题，对R(t)各个体进行评价并保留最优个体。该过程与遗传算法等进化算法中的评价适应度函数过程相同。6.6.2基本量子进化算法基本量子进化算法125o量子更新量子更新量子更新可以采用很多种方法，例如量子异或门、量子Hadamard变换门等各种量子门。应用最多的是采用量子旋转门量子旋转门来更新量子位概率幅：和 分别表示解r与当前最优个体b

64、的第i个量子位对应的二进制位。和分别为旋转角的幅度和旋转方向。6.6.2基本量子进化算法基本量子进化算法126o量子进化量子进化基本量子进化算法中，由于量子旋转门更新实际上就相当于对量子染色体进行了相应的进化操作，因此一般认为这些操作可以采用也可以省略。基本的量子进化操作主要是量量子子交交叉叉和量量子子变变异异。量子交叉和量子变异的基本思想和进化算法中的交叉和变异相同，所不同的只是操作的对象是量子染色体。6.6.2基本量子进化算法基本量子进化算法127还可以采用灾灾变变操操作作来确保算法全局优化性能的提高。灾变是指如果进化在某个特定代数之后没有产生任何优化，则算法将灾变到某个特定的状态并进行重

65、新优化。也可以采用全全干干扰扰算算子子：指同时引入多个个体进行操作，即将多个个体的染色体拆开，依照预先拟定的准则重组以构造新的个体，即使在多个个体完全相同的极端情况下也可以产生新个体等。6.6.2基本量子进化算法基本量子进化算法o量子进化量子进化128量子进化算法的改进量子进化算法的改进 目前对量子进化算法的改进主要可归纳为如下几方面：目前对量子进化算法的改进主要可归纳为如下几方面：对量子染色体的编码、种群初始化方法、种群规模的确定等方面的改进；对量子更新（动态量子旋转角、非量子旋转门更新）、量子进化等操作的改进；与其他算法的混合；算法终止的判断条件方面的改进；扩展为并行算法。1296.6.3

66、基本量子进化算法的流程基本量子进化算法的流程130量子进化算法的特点量子进化算法的特点 算法原理简单，容易实现；算法原理简单，容易实现；算法通用，不依赖于问题信息。算法通用，不依赖于问题信息。种种群群分分散散性性好好，小小种种群群个个体体可可以以对对应应多多个个个个体体编编码。码。群体搜索，具有极强的全局搜索能力。群体搜索，具有极强的全局搜索能力。协协同同搜搜索索，具具有有利利用用当当前前最最优优个个体体信信息息算算法法进进一一步搜索的能力。步搜索的能力。收敛速度快，易于与其他算法混合收敛速度快，易于与其他算法混合。1316.6量子进化算法及其应用量子进化算法及其应用o6.6.1量子进化算法的概念量子进化算法的概念o6.6.2基本量子进化算法基本量子进化算法o6.6.3量子进化算法的流程量子进化算法的流程6.6.4基于量子进化算法的生产调度方法基于量子进化算法的生产调度方法132流水车间调度问题流水车间调度问题问问题题描描述述：n 个个工工件件要要在在m 台台机机器器上上加加工工，每每个个工工件件需需要要经经过过m 道道工工序序，每每道道工工序序要要求求不不同同的的机机器器，n 个个工