【主要内容】 介绍遗传算法的主要思想、关键步骤、如何实现以及在数学建模中的应用。

Presentation on theme: "【主要内容】 介绍遗传算法的主要思想、关键步骤、如何实现以及在数学建模中的应用。"— Presentation transcript:

0 第13讲 智能计算模型 —遗传算法

1 【主要内容】 介绍遗传算法的主要思想、关键步骤、如何实现以及在数学建模中的应用。
【主要目的】 掌握遗传算法在求解数学建模非线性优化问题中的应用。 遗传算法是解优化问题的一种通用框架

2 遗传算法本质上可以认为是一类模拟生物进化过程确定优化方向的随机寻优算法。
遗传算法的一般描述： 遗传算法本质上可以认为是一类模拟生物进化过程确定优化方向的随机寻优算法。 关键问题： （1）目标（适应度函数）的设计 （2）可行解（个体）的编码 （3）遗传策略（选择、交叉、变异）的选择 自然选择目的是适者生存，即好的个体能够保存下来 遗传机理：进化中存在随机现象，具体表现为交叉、变异，从而导致可能获得更好的个体

3 遗传算法基本原理： 遗传算法的基本原理是类比生物进化论的自然选择和遗传机理的过程来设计目标寻优算法。
（1）自然选择：在每一个个体种群中，好的个体会被继承下来——物竞天择，适者生存,这既是生物进化的方向，同时也存在一定随机性，适者生存仅仅反映的是适者会获得更大生存的机会。 这里要注意的是，并不是说就一定是下一代的个体一定比上一代好，也就是说不一定是总是朝着好的方向走，其是以一定概率朝着好的方向走，但也有可能朝着坏的方向走，当然总的方向是越来越好或者说生物中最好的个体越来越好，但并不一定是所有个体都越来越好，也正因为这种机制，使得遗传机制并不会单线发展

4 （2）遗传机理：种群中个体通过交叉、变异等进化过程来繁殖下代；遗传机理依靠随机性提供了更多的迭代方向。
优化和随机两个过程在方向上有冲突性，但也有相互依存性，共同促进整体优化目标的实现。 隐含的数学思想：迭代寻优、随机游走。 注意到生物中的遗传是以群体出现的，是通过群体进化来达到更加的优化，群体中的个体又各自发展并带有随机性 在收敛与发散之间寻求平衡

5 遗传机理：交叉如何进行？变异如何进行？繁衍如何进行？
遗传算法操作的关键点： 自然选择：个体定义、种群规模、“好”的个体、继承策略； 遗传机理：交叉如何进行？变异如何进行？繁衍如何进行？ 生物学中的个体是简单个体，就是一个染色体，而染色体又是由基因组成，因此要将解表示成这种形式 交叉：在染色体某个位置或几个位置对两个染色体进行交换 变异：在染色体某个位置改变值

6 基本对象，是问题的一个可行解，一般需要用一种编码方式表达，也称为染色体，其中每一位称为基因。
生物学 遗传算法 个体 基本对象，是问题的一个可行解，一般需要用一种编码方式表达，也称为染色体，其中每一位称为基因。 种群 一组可行解 好的个体 适应度函数优的个体。适应度函数为个体（染色体）的一个评价函数（目标函数），它决定进化的方向 选择 选择操作，通过一定选择策略选择适应度函数更好的个体继承 交叉 交叉操作，两个父代个体交换部分编码段，生成子代个体 变异 变异操作，某些编码的随机变化或某段编码的反转 繁衍 通过上述操作生成新的一个种群

7 （1）初始化：确定解的编码形式和种群规模；定义适应度函数；确定交叉概率和变异概率
遗传算法的基本步骤 （1）初始化：确定解的编码形式和种群规模；定义适应度函数；确定交叉概率和变异概率 （2）按照设定规模生成初始种群 （3）指定选择策略（选择策略与适应度函数有关），按照选择策略选择更优的个体 （4）按照交叉和变异策略对选择的个体执行交叉和变异操作生成新种群 蓝色部分为算法的关键要素，遗传算法的目的是通过迭代求优化问题的最优解，所以重点要保障两点：迭代能收敛，收敛能收敛到全局最优解 （5）重复（3）和（4）过程直到满足算法结束条件。

8 基本思想 遗传算法中三个最重要的保障：种群，选择和多样性 遗传算法 局部搜索 梯度法

9 遗传算法中选择、交叉和变异策略设计的目的是要保证算法做到两个方面：
遗传算法的关键 遗传算法中选择、交叉和变异策略设计的目的是要保证算法做到两个方面： （1）收敛到全局最优解——多样性 （2）收敛速度快——收敛性 好的遗传算法设计应该做到两个关键的权衡。 遗传算中三个最重要的保障：种群，选择和多样性

10 遗传算法的实现—编码 编码就是将待优化问题的解空间中的可行解以一种编码的方法表达。 （1）编码应该满足与解空间的可行解一一对应。 （2）编码方式决定了在解空间中的搜索过程，算法的效率和复杂度与之息息相关—效率。 （3）编码对于连续的解空间中的解不能完全表达，具体设计时需要考虑到一定的精度，将解空间离散化—精度。

11 二进制编码 二进制编码是以二进制字符0和1为基因的定长字符串。
二进制编码 二进制编码是以二进制字符0和1为基因的定长字符串。 设X=(x1,x2,…,xn),xi∈[ai,bi],i=1,2,…,n，对于给定精度ɛ，则xi的编码长度li应满足 00000…0000 → ai 00000…0001 → ai+ ɛ …… 11111…1111 → bi 注意每个分量的编码长度不一定一样，但每个解的的长度是固定的 即编码长度要足以保证编码分辨率高于ɛ

12 二进制编码优缺点 （1）编码简单，符合计算机中数的表示； （2）执行交叉、变异等操作时解的变化更加广泛； （3）可能破坏解空间的拓扑连续性，两个在解空间上相隔很近的点，可能编码距离较远（例如011与100）；或者编码相近的两个点，在解空间中却相隔甚远（例如011与111） ，并且编码位数越多，这种情况会越明显（例如0111与1111）。 这种对拓扑连续性的破坏在算法后期是很糟糕的 对于精度要求高，连续性寻优问题中，较短的二进制码可能达不到精度要求，而较长的二进制码则又使得搜索空间急剧扩大，所以需要在精度和复杂度之间作权衡

13 格雷码(Gray coding) 格雷码是二进制码的一种变形，其具有与二进制码相同的精度，但弥补二进制码不能保持可行解空间连续性的问题。格雷码要求在两个连续的编码值之间仅仅只有一个码位不相同，其余完全相同。 十进制整数 标准二进制码 格雷码 1 2 3 4 5 6 7 0000 0001 0010 0011 0100 0101 0111 0110 8 9 10 11 12 13 14 15 1000 1001 1010 1011 1100 1101 1110 1111

14 格雷码与二进制码的转换 设某整数对应的二进制码为A=anan-1…a2a1，相应格雷码为G=gngn-1…g2g`，则
这里 相应逆变换为 格雷码主要是解决拓扑连续问题，但表示精度是不变的

15 实数编码 个体的每个基因用一个实数来表达，编码的长度即为决策变量个数，即直接用各个变量所取的实数构成的向量作为一种编码方式。
这种编码方式具有以下优点： • 适合于连续解空间，便于较大空间搜索； • 适合于精度要求较高的遗传算法； • 改善了遗传算法的计算复杂性，提高了运算效率； • 便于处理复杂的决策变量约束条件。 但同时带来了后续操作（交叉、变异）的不便，从而可能导致搜索空间不够灵活，寻找全局最优解能力较弱。

16 其它编码方式 自然数编码，符号编码、矩阵编码、树形编码、量子比特编码……
不同编码有各自的适应环境和各自的问题，同时又跟后续交叉和变异操作息息相关。一般来说，二进制编码用得比较多，同时二进制编码从理论上获得求出最优解的保证。

17 （1）适应度函数和优化目标函数既有联系又有区别
遗传算法的实现—适应度函数 （1）适应度函数和优化目标函数既有联系又有区别 适应度函数本质上反映目标函数，可以说是其一种具体的实现方式，注意适应度函数要求是具体的，可计算的，但并不一定要求有解析表达式。 遗传算法相比其他优化算法，是用适应度函数（与目标相关）值来决定搜索方向，而不是用解空间性质或目标函数局部性质决定搜索方向。 比如有些目标函数是分情况讨论的，这种情况下就难以确定一个唯一的目标。但可以设定适应度函数，因为一旦决策变量的值取定，目标函数也就唯一确定 一般来说，对于可表达的目标函数可直接用作适应度函数，总结起来，适应度函数就应该是一旦决策变量明确确定了值就能够计算的，但目标函数设计的时候因为不知道决策变量的确切取值就可能难以定义，对于这样的问题就尤其适合遗传算法来求解 解空间性质：如最优解在边界或顶点达到 目标函数局部性质：如梯度

18 （2）适应度函数是一个映射，即f=xn→R，用于度量群体中各个个体在优化计算中有可能达到或接近于或有助于找到最优解的优良程度。
一般来说，适应度函数要求大于等于0。 若适应度函数求最大值，而又不能保证一定大于等于0，一般可以加上一个常数，使得新的目标函数大于0，而对于求最小值，就可以通过一个常数减去目标函数以保证其大于等于0

19 （3）适应度函数不一定拘泥于解析表达，只要能够根据决策变量的值来获得一个评价值即可。
（4）可以对适应度函数进行适当变换等处理来保证算法一方面有更大可能获得全局最优解，另一方面保证收敛速度。 第（4）条是在遗传算法上做的进一步优化

20 选择策略用来确定如何从父代群体中按某种方法选取个体遗传到下一代群体中。
好策略 选优 适应度“优”的个体有更多机会遗传到下一代 多样 当前适应度相对较差的个体也有机会遗传到下一代 （1）轮盘赌策略（按比例策略） （2）锦标赛策略（竞技选择策略） （3）精英策略 （4）排序策略 保持多样性的目标主要是避免算法陷入局部最优解，称之为早熟。

21 以个体的适应度占种群中所有个体适应度总和的比例作为选择的概率，即对于n个个体，若f为适应度函数，个体xi的被选择概率为
（1）轮盘赌策略（按比例策略） 以个体的适应度占种群中所有个体适应度总和的比例作为选择的概率，即对于n个个体，若f为适应度函数，个体xi的被选择概率为 要求：适应度函数大于等于0 优点：简单直观，符合常理 问题：实际应用中可能出现两种情况（1）由于随机数产生的原因可能导致好的个体并未被选进来（2）策略本身偏重适应度大的被优先选择，可能导致选择到下一代的都是同样一种或几种个体，从而导致种群多样性差，尤其是在算法开始阶段，从而产生早熟现象（陷入局部最优解）。 产生[0,1]均匀分布随机数,按照轮盘赌的策略判断个体xi是否被选入下一代种群。如此操作n次，选择n个个体进入下一代。

22 （2）锦标赛策略（竞技选择策略） 这种选择法通过相互竞争，优胜者进入下一代种群。在每一代群体中，每次都随机选择 k个个体构成一个小群体，然后从这 k个个体中取适应度最优的个体进入下一代群体。被复制的个体仍返回父代种群中参与下次 k个个体的随机选择。这种随机选择重复n次，产生n个下一代个体。 竞技策略中，选择的力度取决于k值的大小。k值愈大，优良性得以保障，但多样性缺失。反之，k值愈小，多样性得以保障，但优良性可能继承不够。 优点：合适的k值使得最优继承性和多样性得到一定的平衡，既保持了适应度较好的个体能遗传又不至于使得适应度最高的部分个体总是占优。 缺点：增加了操作的复杂性； k值的取定需要一定的经验；相对来说这条策略更注重多样性，在最优继承性上作了一定妥协。 个体是否被选中仍有一个概率问题，但这个概率不取决于适应度相对的大小，而取决于该适应度群体相对的大小。

23 （3）精英策略 精英策略确保当前种群中一定比例的最优个体能存活到下一代，最优个体不经过随机选择，直接复制到新种群中，其余不足种群数量个体再通过随机选择进入下一代。 精英策略中，比例的选择至关重要，比例越大，种群多样性越小，比例越小，多样性越大，虽然最大适应度保持继承，但适应度较好的个体遗传可能不够。

24 将种群中个体按照适应度排序，依次将其被选择概率设计成等差数列，如优劣排序后的各个体为x1,x2,…,xn，则第i个个体的被选择概率为:
（4）排序策略 为避免种群中由于个别个体的适应度绝对占优从而导致其选择性过大（缺乏多样性），排序策略重新对个体的选择概率进行定义，从而降低适应度绝对占优个体被选中的概率。 将种群中个体按照适应度排序，依次将其被选择概率设计成等差数列，如优劣排序后的各个体为x1,x2,…,xn，则第i个个体的被选择概率为: 其中： q —— 最优个体被选中的概率； d —— 相邻个体被选中概率之差。

25 可推导q最差情况下应为1/n（平均概率),最好情况下根据总概率和为1和设定适应度最差个体概率为0可求得q的上限应为2/n，所以
确定q后，根据总概率为1，可得到d应为 不同个体的选择概率按照新的概率pi选择。 优点：消除个体适应度差别悬殊时的影响，代替适应度的缩放技术。 缺点：抹杀个体适应度的实际差别，未能充分运用遗传信息,可能影响算法收敛速度。 既未使用适应度的绝对差异信息，也没有使用等适应度群体规模信息，而仅使用适应度排序信息。

26 选择策略在遗传算法中至关重要 选择策略是遗传算法最关键的一步，选择策略为最优解的进化和全局搜索能力提供了基础。遗传算法是否早熟陷入局部最优解或者收敛速度过慢都有可能是选择策略所导致的影响，所以在运行遗传算法时应注意检查选择策略下种群的变化情况，有针对性地采取有效的策略既加速算法收敛又保证全局最优性。

27 交叉操作主要涉及到两点，一是确定交叉点位置，二是如何交换基因片段。
交叉策略 交叉策略是指对两个相互配对的染色体按某种方式相互交换其部分基因，从而形成两个新的个体。交叉操作应达到两个目的： （1）为产生较好的新个体提供机会，实际上是一种随机漫步，提供了一种跳转的机制，从而避免陷入局部最优解，所以交叉操作为算法提供全局搜索能力； （2）不应过多破坏适应度优良的个体 交叉操作的执行需要定义交叉概率，也就是说交叉操作是在一定概率意义下发生的。 交叉操作主要涉及到两点，一是确定交叉点位置，二是如何交换基因片段。

28 个体A：1001|111 1001000：个体A’ 个体B：0011|000 0011111： 个体B’
（1）单点交叉，即在个体串中随机选定一个交叉点，将两个父代个体该点前后的子串进行互换，生成两个新个体 个体A：1001| ：个体A’ 个体B：0011| ： 个体B’ （2）两点交叉：与单点交叉类似，但是是随机选择两个交叉点，交换两个交叉点之间的这一段 还存在多点交叉、均匀交叉等方式，多点交叉顾名思义就是存在多个交叉点，然后交替交叉，均匀交叉是对每个基因位按照交叉概率决定是否交叉，这些交叉操作一般来说要慎用，主要是考虑尽量避免过多破坏好的模式 个体A：10|0111| ：个体A’ 个体B：00|1100| ：个体B’

29 变异策略 变异策略是指个体中某一个或某几个基因以一定的概率随机发生变动。变异操作是产生新个体的辅助方法，但它也是必不可少的一个运算步骤，因为它决定了遗传算法的局部搜索能力。通过变异策略，来达到两个目的： (1) 改善遗传算法的局部搜索能力； (2) 维持群体的多样性，防止出现早熟现象。 变异操作同样涉及到两点，一是确定变异位置，二是如何变异相应位置基因。

30 个体A： x1x2…xi…xn x1x2…xi’ …xn个体A’
（1）基因位变异：以某一概率独立的改变个体中一个或几个基因位的值 个体A： ：个体A’ （2）均匀变异：用符合某个变量范围内均匀分布的随机数来确定变异基因，以某一较小的概率来替换个体编码串中该基因位上的原有基因值。 个体A： x1x2…xi…xn x1x2…xi’ …xn个体A’ 这里：xi’ = ai+ r · (bi – ai )， r是均匀分布的随机数 点变异：随机选择一个位置，以某一概率判断是否发生变异 当然还有非均匀变异，如正态变异，要求变异的值是服从某种正态分布，还可在原值上做随机扰动来变异 总之变异是很灵活的，目的就是在原来值上做局部少量变动来增加局部搜索能力 另外还有一种操作有时候也归结为变异，就是反转，将染色体反转生成新的个体 这两种变异策略强调了增加种群多样性，个体变化相对较大

31 （3）正态变异：针对实数编码，用服从正态分布的随机数N(xi,σ)代替原有基因，即yi=xi+N(0, σ)
（4）非一致变异：也是强调局部化操作的变异策略，设X=x1，x2…,xn是算法产生的第t代个体，非一致变异定义为 r为[0,1]之间服从均匀分布随机数，T为最大进化代数，b是可调参数

32 交叉和变异策略增加遗传算法全局和局部搜索能力
（1）交叉策略和变异策略往往与编码密切相关。 （2）选择哪种交叉和变异策略不是关键，关键是其蕴含的随机“漫步”的思想，全局和局部搜索能力的综合。 （3）交叉和变异策略的选择注意防止破坏优良的个体。 （4）对于带约束优化问题中应确保交叉和变异后的个体依然满足约束条件。

33 遗传算法是一个反复迭代的过程，每次选代期间，要执行适应度计算、选择、交叉、变异等操作，直至满足终止条件。
算法结束条件 遗传算法是一个反复迭代的过程，每次选代期间，要执行适应度计算、选择、交叉、变异等操作，直至满足终止条件。 结束条件可以分为三类： （1）指定最大迭代次数（代数），一般为 代； （2）对于适应度明确的目标，若知道其界限，可规定最小偏差来定义终止条件； （3）适应度稳定，迭代不能进一步提高适应度； （4）观察适应度变化趋势，人工确定。 第（1）点当然也可以设定为大大指定的时间或费用等

34 最优的继承性和种群的多样性是遗传算法得以获得好效果的关键。但这两点在迭代的不同阶段又体现出不同的特点。
遗传算法小结 遗传算法通过简单的策略（选择、交叉、变异）实现目标寻优，其蕴含深刻的数学思想：迭代寻优、随机漫步。选择策略体现了迭代寻优，交叉和变异策略体现了随机漫步。算法既体现确定性思维又反映随机性思维，既反映出全局搜索能力又有局部搜索能力。 最优的继承性和种群的多样性是遗传算法得以获得好效果的关键。但这两点在迭代的不同阶段又体现出不同的特点。 遗传算法中种群的引入是非常重要的，没有种群，全局搜索能力就没有保障

35 带约束优化问题的处理 实际优化问题中，解空间的解可能存在一定约束条件，对于这类问题的遗传算法求解需要考虑约束条件，尤其是涉及到交叉和变异操作时需保证解的可行性。一般有三种方法： （1）搜索空间限定法：确定可行解的空间，保证编码只限定在可行解空间中； （2）罚函数法：将约束条件通过处理加入到目标函数中； （3）变换法：通过某种变换的设计，保证编码经过这种变化一定能满足约束条件或者说落入可行解空间中。

36 例1：求一元函数 在[-1,2]区间内的最大值 此函数在 [-1,2]有多个局部极值点，其全局最大点在约1.85处达到，最大值为3.85

37 编码：二进制，精度保持在0.001,则 L至少为11.55，所以L=12。对于12位0-1串，如 若取种群规模为20，则每一代种群有20个12位0-1串。

38 适应度函数： 选择策略：轮盘赌。对种群所有个体（20个）按照适应度函数计算选择概率： 产生[0,1]区间均匀分布随机数，计算随机数所落区域选择种群个体进入下一代，选择进行20次。

39 交叉和变异：对选择策略选择的20个个体，按照交叉概率以单点交叉策略交叉，以及按照变异概率以单点变异策略进行变异生成新的20个个体
判断结束条件：计算新的种群的适应度，种群平均适应度和最大适应度不再发生变化，则停止，否则继续进行选择、交叉和变异操作。

40 X=1.851

41 例2：求二元函数 在[0,5]区间内的最大值 此函数在[0,5]×[0,5]有多个局部极值点，其全局最大点在约（3,3）处达到，最大值为1

42

43 例3：求二元函数 在[-5,5]×[-5,5]区间内的最小值
此函数在[-5,5]局部极值点更多，其全局最小点在（0,0）处达到，最小值为0。

44

45 若选择策略采用按均匀分布选择

46 若不发生变异，只考虑交叉，则可能求不到最优解
过早收敛

47 若不发生交叉，只考虑均匀变异概率0.5，则不收敛。

48 例4：十滴水游戏遗传算法求解 游戏规则：6*6的棋盘格中分别有0-4滴水，当前你有10滴水，可以加入到棋盘格中，若加入后棋盘格中水大于4滴，则将破灭并向上下左右四个方向各弹出一滴水，同样可能引起其他棋盘格中水破灭，若没破灭，则棋盘格中多一滴水。问：如何使用手中的10滴水使得棋盘中剩余的水滴最少？

49 （1）问题编码 一个染色体表示10滴水的一种位置分布。一共有36个位置，对应1到36范围内的一个整数（比如(3,4)对应的整数为16）, 用二进制编码，每一个位置（1到36内整数）表示为一个6位二进制数，这样每个染色体是长度为60的0-1变量串。 （2）适应度函数 适应度是棋盘中的剩余水滴数。 一个染色体表示10滴水的一种位置分布，每一滴水的位置用一个6位二进制数表示。

50 （3）选择、交叉和变异 自行考虑采取何种策略。

51 （1）遗传算法对于非连续、不可微和带噪声等非线性程度高和不易解析表达的目标更有效；
遗传算法的适用范围 （1）遗传算法对于非连续、不可微和带噪声等非线性程度高和不易解析表达的目标更有效； （2）解空间明确但规模大一般优化方法不易求解； （3）对于解空间的解能够较好的编码和评价。 几点注意 （1）遗传算法实际提供了一种求解优化问题的通用框架，不要局限于介绍的遗传策略，完全可以自行设计策略； 比如某些解是带条件的、解是无限的等就不宜使用遗传算法 一般说来，能够使用经典优化问题求解的尽量使用经典方法求解。 （2）算法不能保证一次运行收敛就一定是最优解，有时需要运行多次才能找到更好的解。

52

53 作业： 滴水遗传算法求解

54 谢 谢！