分布式估计算法讲解.ppt

分布式估计算法讲解
【通用模板】【教育说课】【述职报告】【工作汇报】
交叉 就是互换两个染色体某些位上的基因。
s1′=01000101, s2′=10011011
可以看做是原染色体s1和s2的子代染色体。
例如, 设染
19
● 赌轮选择法
s4

s2

s1


20
在算法中赌轮选择法可用下面的子过程来模拟: 　① 在［0, 1］区间内产生一个均匀分布的随机数r。
　　② 若r≤q1,则染色体x1被选中。
　　③ 若qk-1<r≤qk(2≤k≤N), 则染色体xk被选中。 其中的qi称为染色体xi (i=1, 2, …, n)的积累概率, 其计算公式为
21
选择-复制
设从区间［0, 1］中产生4个随机数如下:
r1 = , r2 =
r3 = , r4 =
染色体
适应度
选择概率
积累概率
选中次数
s1=01101
169


1
s2=11000
576


2
s3=01000
64


0
s4=10011
361


1
22
于是，经复制得群体：
s1’ =11000（24）, s2’ =01101（13）
s3’ =11000（24）, s4’ =10011（19）
23
交叉
设交叉率pc=100%，即S1中的全体染色体都参加交叉运算。
设s1’与s2’配对，s3’与s4’配对。分别交换后两位基因，得新染色体：
s1’’=11001（25）, s2’’=01100（12）
s3’’=11011（27）, s4’’=10000（16）
24
变异
设变异率pm=。
这样，群体S1中共有
5×4×=
位基因可以变异。
，所以本轮遗传操作不做变异。
25
于是，得到第二代种群S2：
s1=11001（25）, s2=01100（12）
s3=11011（27）, s4=10000（16）
26
第二代种群S2中各染色体的情况
染色体
适应度
选择概率
积累概率
估计的
选中次数
s1=11001
625


1
s2=01100
144


0
s3=11011
729


2
s4=10000
256


1
27
如此不断进化，直到种群中出现适应度最高的染色体s1=11111。于是，遗传操作终止，将染色体“11111”作为最终结果输出。
　　然后，将染色体“11111”解码为表现型，即得所求的最优解：31。
将31代入函数y=x2中，即得原问题的解，即函数y=x2的最大值为961。
28
2、分布式估计算法与传统遗传算法的区别
分布式估计算法是一种全新的进化模式，没有传统遗传算法的交叉和变异操作，取而代之的是概率模型的学****和采样。
分布式估计算法通过一个概率模型描述候选解在空间的分布，采用统计学****的手段从宏观上建立一个描述解分布的概率模型，然后对概率模型进行随机采样产生新的种群，如此反复进行，实现种群的进化，直到终止条件。
29
根据概率模型的复杂程度以及不同的采样方法，分布式估计算法发展了很多不同的具体实现方法，但是都可以归纳为下面两个主要步骤：
1）、构建描述解空间的概率模型。通过对种群的评估，选择优秀的个体集合，然后采样统计学****等手段构造一个描述当前解集的概率模型
2）、由概率模型随机采样产生新的种群。一般的，采用蒙特卡罗方法，对概率模型采样得到新的种群。
30
下面通过一个简单的EDA算例，介绍该方法独特的进化操作，使读者对EDA方法有一个直观的认识.
3 、分布式估计算法应用举例
31
32
33
34
35
36
37
分布式估计和传统遗传算法的对比
38
4、分布式估计算法的分类
变量无关
双变量相关
多变量相关
39
、变量无关的分布式估计算法