遗传算法（Genetic Algorithm） Natural Computing

Presentation on theme: "遗传算法（Genetic Algorithm） Natural Computing"— Presentation transcript:

1 遗传算法（Genetic Algorithm） Natural Computing
1、算法起源 2、基本术语和遗传算子 3、模式定理 4、遗传算法的应用

2 算法起源 遗传算法（简称GA）的基本思想起源于生物体的遗传进化。生物的进化是发生在作为生物体结构编码的染色体上，染色体主要是由DNA和蛋白质组成，其中DNA又是最主要的遗传物质，它储存着遗传信息，可以准确地复制，也能够发生突变，并可通过控制蛋白质的合成而控制生物的性状。 生物的遗传特性，使生物界的物种能够保持相对的稳定；生物的变异特性，使生物个体产生新的性状，以至于形成了新的物种，推动了生物的进化和发展。 遗传算法正是模拟这一过程，通过向自然学习来求解问题。

3 算法起源 1975年，美国Michigan大学的Holland教授出版了系统论述遗传算法的第一本专著，标志着遗传算法的诞生。
80年代，遗传算法得到了广泛应用与研究。 1989年，D.J.Goldberg出版了他的著作，对遗传算法作了系统的阐述，确立了现代遗传算法的基础。

4 基本遗传算法是一种概率搜索算法，利用编码技术作用于称为染色体（chromosome）的二进制数串，模拟由这些串组成的群体的进化过程。类似于自然进化，遗传算法通过作用于染色体上的基因，寻找好的染色体来求解问题。 遗传算法通过有组织的然而是随机的信息交换来重新结合那些适应性好的串。 虽是一类随机算法，但又不是简单的随机走动，它可以有效利用已有的信息来搜寻那些有希望改善解质量的串。 与自然界相似，遗传算法对求解问题本身一无所知，它所需要的仅是对算法所产生的每个染色体进行评价，并基于适应值来选择染色体，使适应性好的染色体比适应性差的染色体有更多的繁殖机会。

5 基本术语和遗传算子 定义1 将待解决问题的解变量用某种编码技术编制成特定形式的数字串，称这个数字串为染色体（chromosome）；数字串的每位数字码称为基因（gene）（基本GA中，采用二进制编码串），串的长度即为染色体的长度 定义2 由一定数目的同等长度染色体组成的集合称为一个种群（population）；相应的染色体称为种群的一个个体（individual） 定义3 根据拟定的函数对个体性质评价的一种度量，称为个体的适应值或适应度（fitness）

6 基本术语和遗传算子 定义 4 对两个个体进行部分基因互换，产生两个新个体的操作，称为交叉或杂交运算（crossover）
定义 5 对个体的某些基因进行改变，产生新个体的操作，称作变异运算（mutation） 定义 6 从当前种群中选出优良的个体，使之有机会作为父代繁殖下一代的操作，称作选择运算（selection），或复制运算（reproduction） 实际上，从生物角度来看，个体的适应值就是生物体对生存环境的适应性；交叉运算就是生物界的有性繁殖；变异运算就是生物界的突变现象。

7 基本遗传算子：以二进制编码为例 单点交叉: (随机投点） 两点交叉：
X = ; X’ = ; Y = ； Y’ = ； 两点交叉： X = ; X’ = ; Y = ； Y’ = ； 或者 X” = ; Y” = ；

8 基本遗传算子：以二进制编码为例 单点变异: (随机投点） 多点变异：
X = ; X’ = ; Y = ； Y’ = ； 多点变异： X = ; X’ = ; Y = ； Y’ = ； 变异运算是避免陷入局部极小的关键；也是增加群体多样性的手段

9 基本遗传算子：以二进制编码为例 个体选择复制: (赌轮原则） 设种群规模为4 个体 fitness 概率 选择 X1 1 1/12 X2 2
1/6 X3 3 1/4 X4 6 1/2 X1 X3 X2 1．    赌轮选择（roulette wheel selection）机制 这是一种最基本的、常用的选择机制。在这种选择机制中，个体每次被选中的概率与其在群体环境中的相对适应度成正比。即将群体中的所有字符串的适应值按一定比例画在赌盘上，其形状是一块馅饼，群体中的所有字符串相应的馅饼构成一整块赌盘，然后将赌盘固定在一支架上并可转动，再设置一固定指针，接着随机转动赌盘，当赌盘停止转动时，固定指针所指方向的馅饼块表示选中了其对应的字符串 X4 Roulette Wheel Selection

10 标准遗传算法（SGA） 考虑全局优化问题 （P） max{f(x)：x∈DRn→R1} 遗传算法基于以下两条基本策略求解问题（P）：
（a）对于给定的目标函数 f ，它使用 f 的任一适应值函数（换言之，一个值域非负、与 f 有相同极点的函数）； （b）它不直接作用于实向量x，而是作用于x的某种编码（最常见的为定长二进制数串编码）。所以，对于取定 f 的任一适应值函数F和固定长度为L的二进制数串编码，遗传算法实质上是通过求解组合优化问题 （P’） max{F(x)：x∈S} 来求解问题（P）的，这里S={0，1}L为D的编码空间（即D中所有实变量的长度为L的二进制数串编码全体）。

11 X(k +1)=(X1 (k +1) ，X2 (k +1) ，…，XN (k +1))
Step 1 初始化： 1.1 指定种群规模N，杂交概率Pc ，变异概率Pm及终止进化准则； 1.2 随机生成初始种群X(0)=(X1 (0) ，X2 (0) ，…，XN (0))∈SN， 置k =0。 Step 2 种群进化： 2.1 （选择）依据Xi(k)的适应值，随机、独立、重复地从X(k)中选取N个个体为母体； 2.2 （交叉）依概率Pc独立地对所选N个母体执行杂交，以产生新的N个中间个体； 2.3 （变异）依概率Pm独立地对交叉生成的N个中间个体执行变异，从而生成新一代种群 X(k +1)=(X1 (k +1) ，X2 (k +1) ，…，XN (k +1))

12 Step 3 终止检验： 如果X（k+1）已满足预设的进化终止原则，则停止；否则，置k = k +1，转Step2。 常见的终止条件有： 1、 ,其中δ为给定的常数，与具体问题的 求解精度有关； 2、整个群体仅由某个个体生成； 3、进化次数超过预定的值。

13 常见的选择机制 1. 赌轮选择（roulette wheel selection）； 2.最佳保留（elitist model）；
3．期望值模型（expected value model）选择机制; 在该模型选择机制中，先按期望值Q的整数部分安排个体被选中的次数，而对期望值Q的小数部分可按下述几种方式进行处理： （1）   确定方式; （2）   赌轮方式; （3）  贝努利试验（Bernoulli Trials）方式 首先按赌轮选择机制执行遗传算法的选择功能；然后将当前解群体中适应度最高的个体结构完整地复制到下一代群体中。其主要优点在于能保证遗传算法终止时得到的最后结果一定是历代出现过的最高适应度的个体。 这种选择机制主要是为了克服赌轮选择机制所产生的随机选择错误而提出的。在赌轮选择机制中，由于群体规模有限等原因，使得个体实际被选中的次数与它应该被选中的期望值之间可能存在着一定的误差。 在期望值模型选择机制中，先按期望值Q的整数部分安排个体被选中的次数，而对期望值Q的小数部分可按下述几种方式进行处理： （1）   确定方式 将期望值Q的小数部分按值大小进行列表，然后自大到小依次选择，直到选满为止。 （2）   赌轮方式 将期望值Q的小数部分按上述赌轮机制进行选择，直到选满为止。 （3）   贝努利试验（Bernoulli Trials）方式 将期望值Q的小数部分作为概率进行贝努利试验，若实验成功，则该个体被选中，如此反复试验，直到选满为止。

14 遗传算法的改进——精英策略 采用精英策略(优、劣解同时保留)的遗传算法是保持当前一个最好解和最差解；
最好解(the fittest)不参与交叉和变异操作； 最差解不参加交叉操作，但参加变异操作； 从典型遗传算法的描述中，我们知道，遗传算法依靠再生保持优秀种群，依靠交叉和变异操作来改变搜索空间，以便不断得到最好解。变异和交叉操作的概率大时，破坏的可能性也越大。因此在应用遗传算法时，人们不断改变调整这两个概率，以便能扩大搜索空间，又能不破坏已经得到的最好解。保持当前一个最好解和最差解这个方法，就能达到既能扩大搜索空间，又能不破坏已经得到的最好解的目的。因为当前的一个最好解不参加交叉和变异操作，所以不可能破坏它，在下一代中所获得的解一定比当前一个最好解更好时才能保留它。而且我们对最差解采用保留方法直接参加变异，能避免劣解中的无效基因参加交叉，又能避免有效基因被删除，有助于调处局部极小值。因此，这个方法能够加快算法的搜索速度并逼近最优解。

15 Step 1初始化：随机产生一个规模为N的初始种群，其中每个个体为二进制位串的形式。
Step 4 交叉：从上述选择后的种群中，除了最优、最差两个个体外，随机选择两个染色体，按一定的交叉概率Pc进行基因变换，交换的位置随机选取。 Step 5 变异：从种群中，除了最优、最差两个个体外，随机选择一个染色体，按一定的变异概率Pm进行基因变异；对最差的个体按增大后的变异概率 kPm (k取10-20)进行基因变异。 Step 6 若达到预设的进化代数，则算法停止，否则，转Step 2.

16 模式定理 定义： 基于三值字符集 {0，1，*}所产生的能描述具有某些结构相似性的0、1字符串集的字符串称作模式。
模式是二值符号串的一种扩展，其中基因的取值可为0，1或*。符号“*”称作“无关符”，表示一种随意的情况，也就是说基因的取值可以是1也可以是0。例如（*01*00）、（******）和（100101）都是长为6位的二值符号串的模式。

17 包含个体与隐含模式 如果一个个体X符合模式H，就称X属于H，或H包含X。如： H=10*0**; 包含：101011,100001,…,
给定一个个体X, 如果X属于模式H，也称H为X隐含的模式。如： X=101011,它隐含的模式有 H1=1*****, H2=*01**1, H3=10**11,…,

18 定义： 模式H中确定位置的个数称作该模式的模式阶，记作O(H)。
比如模式011*0*的阶是4，而模式0*****为1。显然一个模式的阶数越高，其包含的样本数就越少，因而确定性也就越高。 定义： 模式H中第一个确定位置和最后一个确定位置之间的距离称作该模式的定义距，记作δ(H)。 比如模式011*1*的定义距是4，而模式0*****的定义距为0。

19 其中，f(H), f(t) 分别是模式H（在A(t)中）和群体A(t)的适应度平均值。
模式阶和定义距描述了模式的基本性质。下面讨论模式在遗传操作下的变化。令A(t) 表示第 t 代中串的群体，以Aj(j=1,2,···, n)表示一代中第j个个体串。 1、选择操作对模式的作用 假设在t代，群体A(t)中模式H所包含的个体数为m(H，t)。在选择运算中，一个串是根据其适应度进行复制的。即以概率Pi=fi /(∑fj）进行选择的，其中fi 是个体Ai(t)适应度。则模式H在第t+1代中包含的个体数为（从概率角度） m(H, t+1) = n (∑ fi (H) ) / (∑fj） = m(H,t) n (∑ fi (H) ) / m(H, t)(∑fj） = m(H,t) n f(H) / (∑fj） = m(H,t) f(H) / [(∑fj）/ n ] = m(H,t) f(H) / f(t) 其中，f(H), f(t) 分别是模式H（在A(t)中）和群体A(t)的适应度平均值。

20 可见，模式的增长（减少）依赖于模式的平均适应度与群体平均适应度之比：那些平均适应度高于群体平均适应度的模式将在下一代中增长；而那些平均适应度低于群体平均适应度的模式将在下一代中减少。
现在，假定模式H的平均适应度一直高于群体平均适应度(设至少为1+c倍）， c为正的常数，则有 即，在选择算子作用下，平均适应度高于群体平均适应度的模式将呈指数级增长；而低于群体平均适应度的模式将呈指数级减少。

21 2．模式在交叉算子作用下的变化 考虑一个长度为6的串以及隐含其中的两个模式： A = H1 = * 1 * * * 0 H2 = * * * * 假定A被选中进行交叉，不妨设交叉点为3，即 A = H1 = * 1 * * * 0 H2 = * * * *

22 模式在交叉算子作用下的变化 A = B= A’ = B’= H1 = * 1 * * * H2 = * * * * 显然，H1被破坏，而H2依然存在

23 模式H1的定义距为4，那么交叉点在l －1=5个位置上随机产生时， H1遭到破坏的概率是
Pd=δ(H1 ) / ( l－1 ) = 4 / 5， 换句话说，其生存概率为1/5； 模式H2的定义距是1，则H2遭破坏的概率是 Pd=δ(H2 ) /( l－1 ) = 1 / 5， 即生存概率是4/5。 一般地讲，当交叉点落在定义距之外时，模式H才能生存。在简单交叉（单点交叉）下的H的生存概率 Ps=1－δ( H ) / ( l－1 )

24 由于交叉本身也是以一定的概率Pc发生的，所以模式H的生存概率为
如果与A进行交叉的串在位置2，6上有一位与A相同，则H1将被保留。因此，以上公式只是生存概率的一个下界，即有： 这个公式描述了模式在交叉算子作用下的生存概率。如果考虑模式H在选择和交叉算子的共同作用下的变化。则有

25 3．模式在变异算子作用下的变化 考虑变异操作。串的某一位置发生改变的概率为Pm，故该位置不变的概率为1－Pm，而模式H在变异运算作用下若要不受破坏，则其中所有的确定位置必须保持不变。因此模式H保持不变的概率为 其中O( H )为模式H的阶数。当Pm<<1时，模式H在变异算子作用下的生存概率为

26 模式定理 综合三种算子对模式H的影响，有如下的生存概率估计：
在遗传算子选择、交叉和变异的作用下，具有低阶、短定义距以及平均适应度高于群体平均适应度的模式在子代中将得以(指数级)增长。 结论：在一定前提下，遗传算法以概率为1收敛到全局最优解！

27 遗传算法的应用 染色体编码：视具体问题而定，可以整数序列串，也可以实数序列。 适应值函数的定义，如何评估？
交叉算子的本质：保持父代基因段或信息； 变异算子的本质：新解的实质多样性； 如何定义这2个演化算子，使之保持解的可行性？（特别是约束情况下？） 参数设定问题。

28 SAT问题（无约束） F(x) ：布尔变量 x = (x1,…, xn)的合取范式.
问题：找到x = (x1,…, xn)的一个真值指派，使得 F(x) = TRUE ( or 1) . 例如： F(x) =（ x1 x3 ）  （ x2 x5  x6 ）  （  x4 x5 ） 取 x = (1, 0, 0, 0, 0, 1 )， 则 F(x) = 0； 取 x = (1, 0, 0, 0, 0, 0 )， 则 F(x) = 1；求得一个解！ 2019/2/23 智能技术课程－－叶东毅

29 编码和适应值函数 二进制编码：直接用原问题的变量编码； 适应值：直接采用问题的目标函数F(x)?
要么F(x)=1，找到解；要么F(x)=0，此时，如何区别不同个体的质量呢？如何引导选择过程呢？ 适应值函数的合理确定问题！！ F(x) = f1(x)  f2(x) …  fp(x) ; fi(x)为析取项; 适应值函数：Q(x) =  Boolean(fi(x) )；0 Q(x)  p 如果 Q(x) = p, 则 x 为一个解； 可以有其他（可能更好）的方式定义适应值函数。 2019/2/23 智能技术课程－－叶东毅

30 对称全通路TSP问题（含约束） 采用二进制编码？按照边，但是需要判断顶点集合的重叠性。同时，边数远远多于顶点数。另外，面临演化算子的设计问题。不合适！ 城市编号（顶点）序列为染色体（整数编码）： X = 1 2 3…n 的某一个排列，这样最自然！ 如何定义交叉、变异呢？ 简单交换或变异导致不可行的解： = 适应值函数：距离总和。 2019/2/23 智能技术课程－－叶东毅

31 1、基于次序的交叉：在父代随机选取一组位置，强加到另一个上
X = ; Y = X’ = Y’= 2、基于位置的交叉： X = ; Y = X’ = ；Y’=

32 3、部分映射交叉：在父代随机选取一组位置，段内元对应对交换
X = ; ：7，5：9，6：8 Y = X’ = Y’= 变异算子： 1、随机选2个元素，将第二元置于第一元之前； X = ， X’ = 2、随机选2个元素，交换位置； X = ， X’ =

33 图着色问题（混合算法） 贪心+遗传 给定每个顶点具有加权的图和 n 种颜色,图着色问题：从n 种颜色的集合中选择一种颜色到任一个顶点上，但要满足任何一条边关联的一对顶点不具有相同的颜色。未着色的顶点为无色的。着色顶点的加权总和为着色方案的分数。求具有最高分数的着色方案。 这是NP-完全问题。 2019/2/23 智能技术课程－－叶东毅

34 贪心策略 按照加权大小顺序对顶点排序； 按照该顺序取每个顶点，并为其指定它能够具有的第一个合法颜色。 该算法速度快，有时可以获得最优解。
2019/2/23 智能技术课程－－叶东毅

35 2-8 1-12 7-36 6-10 3-14 5-9 4-13 2019/2/23 智能技术课程－－叶东毅

36 n =1, Score =36; Best solution! Greedy idea wins!
2-8 1-12 7-36 6-10 3-14 5-9 4-13 2019/2/23 智能技术课程－－叶东毅

37 2-8 1-12 7-15 6-10 3-14 5-9 4-13 2019/2/23 智能技术课程－－叶东毅

38 n =1, Score =15; Not best! Greedy idea fails! 2-8 1-12 7-15 6-10 3-14
5-9 4-13 2019/2/23 智能技术课程－－叶东毅

39 n =1, Score =35; Best! 2-8 1-12 7-15 6-10 3-14 5-9 4-13 2019/2/23
智能技术课程－－叶东毅

40 n =2, Score =66; Best! 2-8 1-12 7-15 6-10 3-14 5-9 4-13 2019/2/23
智能技术课程－－叶东毅

41 n =3, Score =81; Best! Again, greedy idea wins!
2-8 1-12 7-15 6-10 3-14 5-9 4-13 2019/2/23 智能技术课程－－叶东毅

42 混合遗传算法 编码：有序顶点序列（整数串） 适应值函数：依照贪心策略，对给定的顶点序列进行着色，求出相应的分数作为适应值；
应用遗传算法进行演化，每得到新的一代，都按照贪心策略产生相应的着色方案，直至找到一个满意的着色方案。 杂交算子和变异算子可以类似TSP问题那样设计。 2019/2/23 智能技术课程－－叶东毅

43 2019/2/23 智能技术课程－－叶东毅