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

《第7章遗传算法及其应用.ppt》由会员分享，可在线阅读，更多相关《第7章遗传算法及其应用.ppt（79页珍藏版）》请在优知文库上搜索。

1、第第 7 章章 遗传算法及其应用遗传算法及其应用2第7章 遗传算法及其应用o 7.1 遗传算法的产生与发展遗传算法的产生与发展 o 7.2 遗传算法的基本算法遗传算法的基本算法 o 7.3 遗传算法的改进算法遗传算法的改进算法 o 7.4 基于遗传算法的生产调度方法基于遗传算法的生产调度方法3第7章 遗传算法及其应用7.1 遗传算法的产生与发展遗传算法的产生与发展 o 7.2 遗传算法的基本算法遗传算法的基本算法 o 7.3 遗传算法的改进算法遗传算法的改进算法 o 7.4 基于遗传算法的生产调度方法基于遗传算法的生产调度方法4 7.1 遗传算法的产生与发展 遗传算法遗传算法（genetic

2、algorithms，GA）：一类借鉴生物界自然选择和自然遗传机制的随机搜索算法,非常适用于处理传统搜索方法难以解决的复杂和非线性优化问题。遗传算法可广泛应用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域。57.1 遗传算法的产生与发展7.1.1 遗传算法的生物背景遗传算法的生物背景7.1.2 遗产算法的基本思想遗产算法的基本思想7.1.3 遗产算法的发展历史遗产算法的发展历史7.1.4 设计遗产算法设计遗产算法的基本原则与内容的基本原则与内容67.1.1 遗传算法的生物学背景o 适者生存适者生存：最适合自然环境的群体往往产生了更大的后代群最适合自然环境的群体往往产生了更大的后代群

3、体。体。o 生物进化的基本过程：生物进化的基本过程：染色体染色体(chromosome)：生物生物的遗传物质的主要载体。的遗传物质的主要载体。基因基因(gene)：扩展生物性状扩展生物性状的遗传物质的功能单元和结的遗传物质的功能单元和结构单位。构单位。基因座（基因座（locus）：染色体：染色体中基因的位置。中基因的位置。等位基因（等位基因（alleles）：基因：基因所取的值。所取的值。77.1.2 遗传算法的基本思想生物遗传概念生物遗传概念遗产算法中的应用遗产算法中的应用适者生存适者生存目标值比较大的解被选择的可能性大目标值比较大的解被选择的可能性大个体（个体（Individual）解解染

4、色体（染色体（Chromosome）解的编码（字符串、向量等）解的编码（字符串、向量等）基因（基因（Gene）解中每一分量的特征解中每一分量的特征适应性（适应性（Fitness）适应函数值适应函数值群体（群体（Population）根据适应函数值选定的一组解（解的个根据适应函数值选定的一组解（解的个数为群体的规模）数为群体的规模）婚配（婚配（Marry）交叉（交叉（Crossover）选择两个染色体进行）选择两个染色体进行交叉产生一组新的染色体的过程交叉产生一组新的染色体的过程变异（变异（Mutation）编码的某一分量发生变化的过程编码的某一分量发生变化的过程87.1.2 遗传算法的基本思想

5、 遗传算法的基本思想：遗传算法的基本思想：在求解问题时从多个解开始，然后通过一定的法在求解问题时从多个解开始，然后通过一定的法则进行逐步迭代以产生新的解。则进行逐步迭代以产生新的解。最优化问题 遗传算法 目标函数 可 行 解 一组 解 适应度函数染 色 体 种 群97.1.3 遗传算法的发展历史o 1962年，Fraser提出了自然遗传算法。o 1965年，Holland首次提出了人工遗传操作的重要性。o 1967年，Bagley首次提出了遗传算法这一术语。o 1970年，Cavicchio把遗传算法应用于模式识别中。o 1971年，Hollstien在论文计算机控制系统中人工遗传自适应方法中

6、阐述了遗传算法用于数字反馈控制的方法。o 1975年，美国J.Holland出版了自然系统和人工系统的适配；DeJong完成了重要论文遗传自适应系统的行为分析。o 20世纪80年代以后，遗传算法进入兴盛发展时期。107.1.4 设计遗传算法的基本原则与内容 设计的基本原则：设计的基本原则：适用性适用性：算法所能适用的问题种类。：算法所能适用的问题种类。可靠性可靠性：算法对于所设计的问题，以适当的精度求解算法对于所设计的问题，以适当的精度求解其中大多数问题的能力其中大多数问题的能力。收敛性收敛性：算法能否收敛到全局最优。：算法能否收敛到全局最优。稳定性稳定性：算法对其控制参数及问题数据的敏感度算

7、法对其控制参数及问题数据的敏感度。生物类比生物类比：通过类比的方法引入在生物界被认为是有：通过类比的方法引入在生物界被认为是有效的方法及操作。效的方法及操作。11设计的基本内容：设计的基本内容：7.1.4 设计遗传算法的基本原则与内容 编码方案编码方案：编码表示方式。：编码表示方式。适应度函数适应度函数：目标函数。：目标函数。选择策略选择策略：优胜劣汰。：优胜劣汰。控制参数控制参数：种群的规模、算法执行的最大代数、执行：种群的规模、算法执行的最大代数、执行不同遗传操作的概率等。不同遗传操作的概率等。遗传算子遗传算子：选择：选择(selection)；交叉；交叉(crossover)；变异；变异

8、(mutation)。算法的终止准则算法的终止准则：规定一个最大的演化代数，或算法：规定一个最大的演化代数，或算法在连续多少代以后解的适应值没有改进。在连续多少代以后解的适应值没有改进。12第7章 遗传算法及其应用o 7.1 遗传算法的产生与发展遗传算法的产生与发展 7.2 遗传算法的基本算法遗传算法的基本算法 o 7.3 遗传算法的改进算法遗传算法的改进算法 o 7.4 基于遗传算法基于遗传算法的生产调度方法的生产调度方法137.2 遗传算法的基本算法o 遗传算法的五个基本要素遗传算法的五个基本要素：n 参数编码n 初始群体的设定n 适应度函数的设计n 遗传操作设计n 控制参数设定147.2

9、 遗传算法的基本算法7.2.1 编码编码7.2.2 群体设定群体设定7.2.3 适应度函数适应度函数7.2.4 选择选择7.2.5 交叉交叉7.2.6 变异变异7.2.7 遗传算法遗传算法的一般步骤的一般步骤157.2.1 编码 1.位串编码位串编码一维染色体编码方法一维染色体编码方法：将问题空间的参数编码为一维排列的染色体的方法。二进制编码二进制编码：用若干二进制数表示一个个体，将原问题的解空间映射到位串空间 B=0，1上，然后在位串空间上进行遗传操作。（1）二进制编码二进制编码167.2.1 编码(1)二进制编码二进制编码（续）（续）优点优点：类似于生物染色体的组成，算法易于用生物遗传理论

10、解释，遗传操作如交叉、变异等易实现；算法处理的模式数最多。缺点：缺点：相邻整数的二进制编码可能具有较大的Hamming距离，降低了遗传算子的搜索效率。15：01111 16：10000 要先给出求解的精度。求解高维优化问题的二进制编码串长，算法的搜索效率低。17 7.2.1 编码 1.位串编码位串编码（2）Gray 编码编码Gray编码:将二进制编码通过一个变换进行转换得到的编码。二进制串 n.21 Gray n.21二进制编码 Gray编码1111kkkkkGray编码 二进制编码)2(mod1kiik18 7.2.1 编码 2.实数编码实数编码 采用实数表达法不必进行数制转换不必进行数制转

11、换，可直接在解的表现型上进行遗传操作。多参数映射编码的基本思想多参数映射编码的基本思想：把每个参数先进行二进制编码得到子串，再把这些子串连成一个完整的染色体。多参数映射编码中的每个子串对应各自的编码参数，所以，可以有不同的串长度和参数的取值范围有不同的串长度和参数的取值范围。19 7.2.1 编码 3.有序串编码有序串编码 有序问题有序问题：目标函数的值不仅与表示解的字符串的值有关，而且与其所在字符串的位置有关。4结构式编码结构式编码 Goldberg等提出MessyGA(mGA)的遗传算法编码方法。201.初始种群的产生初始种群的产生 7.2.2 群体设定（1）根据问题固有知识，把握最优解所

12、占空间在整个问题空间中的分布范围，然后，在此分布范围内设定初始群体。（2）随机产生一定数目的个体，从中挑选最好的个体加到初始群体中。这种过程不断迭代，直到初始群体中个体数目达到了预先确定的规模。212.种群规模的确定种群规模的确定 7.2.2 群体设定 模式定理模式定理表明：若群体规模为M，则遗传操作可从这M 个个体中生成和检测 个模式，并在此基础上能够不断形成和优化积木块，直到找到最优解。3M 群体规模太小，遗传算法的优化性能不太好，易陷入局部最优解。群体规模太大，计算复杂。221.1.将目标函数映射成适应度函数的方法将目标函数映射成适应度函数的方法 7.2.3 适应度函数 若目标函数为最大

13、化最大化问题，则 若目标函数为最小化最小化问题，则)()(xfxfFit)(1)(xfxfFit将目标函数转换为求最大值的形式将目标函数转换为求最大值的形式,且保证函数值非负！且保证函数值非负！若目标函数为最大化最大化问题，则 若目标函数为最小化最小化问题，则minmin()()()0f xCf xCFit f x其他情况maxmax()()()0Cf xf xCFit f x其他情况231.1.将目标函数映射成适应度函数的方法将目标函数映射成适应度函数的方法(续）续）7.2.3 适应度函数 存在界限值预选估计困难或者不能精确估计的问题！存在界限值预选估计困难或者不能精确估计的问题！若目标函数

14、为最大化最大化问题，则 若目标函数为最小化最小化问题，则 ：目标函数界限的保守估计值。1()0()01()Fit f xccf xcf x，1()0()01()Fit f xccf xcf x，c242.适应度函数的尺度变换适应度函数的尺度变换 在遗传算法中，将所有妨碍适应度值高的个体产生，从而 影 响 遗 传 算 法 正 常 工 作 的 问 题 统 称 为 欺 骗 问 题欺 骗 问 题（deceptive problem）。7.2.3 适应度函数 过早收敛过早收敛：缩小这些个体的适应度，以降低这些超级个体的竞争力。停滞现象停滞现象：改变原始适应值的比例关系，以提高个体之间的竞争力。适应度函数

15、的尺度变换（尺度变换（fitness scaling）或者定标定标：对适应度函数值域的某种映射变换。252.适应度函数适应度函数的尺度变换的尺度变换(续）续）（1）线性变换：baff7.2.3 适应度函数 minfffaavgavgminminffffbavgavgavgavgmultfffCamax)1(avgavgavgmultffffCfbmaxmax)(,avgavgff avgmultfCfmax满足满足最小适应度值非负 262.适应度函数适应度函数的尺度变换的尺度变换(续）续）（2）幂函数变换法：Kff affe7.2.3 适应度函数（3）指数变换法：277.2.4 选择 1.个体

16、选择概率分配方法个体选择概率分配方法 选择操作也称为复制（reproduction）操作：从当前群体中按照一定概率选出优良的个体，使它们有机会作为父代繁殖下一代子孙。判断个体优良与否的准则是各个个体的适应度值：个体适应度越高，其被选择的机会就越多。287.2.4 选择 1.个体选择概率分配方法个体选择概率分配方法（1）适应度比例方法适应度比例方法（fitness proportional model）或蒙特卡或蒙特卡罗法罗法（Monte Carlo）Miiisiffp1 各个个体被选择的概率和其适应度值成比例。个体 被选择的概率为：i297.2.4 选择 1.个体选择概率分配方法个体选择概率分配方法（2）排序方法排序方法（rank-based model）线性排序：J.E.Baker 群体成员按适应值大小从好到坏依次排列：个体 按转盘式选择的方式选择父体Nxxx,21 iipx 分配选择概率)1(MMbiapi307.2.4 选择 1.个体选择概率分配方法个体选择概率分配方法（2）排序方法排序方法（rank-based model）非线性排序：Z.Michalewicz 将群体成员按适