分布式估计算法讲解.ppt

算法设计与分析 分布式估计算法
主要知识点:
1 、传统遗传算法
2 、分布式估计算法与传统遗传算法的区别
3 、分布式估计算法应用举例
4、分布式估计算法的分类
5、分布式估计算法的理论基础
2
1、传统遗传算法
1. 个体与种群
●个体就是模拟生物个体而对问题中的对象
(一般就是问题的解)的一种称呼,一个个
体也就是搜索空间中的一个点。
●种群(population)就是模拟生物种群而由若
干个体组成的群体, 它一般是整个搜索空间
的一个很小的子集。
3
2. 适应度与适应度函数
●适应度(fitness)就是借鉴生物个体对环境的
适应程度,而对问题中的个体对象所设计的
表征其优劣的一种测度。
●适应度函数(fitness function)就是问题中的
全体个体与其适应度之间的一个对应关系。
它一般是一个实值函数。该函数就是遗传算
法中指导搜索的评价函数。
4
3. 染色体与基因
染色体(chromosome)就是问题中个体的某种字符串形式的编码表示。字符串中的字符也就称为基因(gene)。
例如:
个体染色体
9 ---- 1001
(2,5,6)---- 010 101 110
5
4. 遗传操作
亦称遗传算子(ic operator),就是关于染色体的运算。遗传算法中有三种遗传操作:
●选择-复制(selection-reproduction)
●交叉(crossover,亦称交换、交配或杂交)
●变异(mutation,亦称突变)
6
选择-复制通常做法是:对于一个规模为N的种群S,按每个染色体xi∈S的选择概率P(xi)所决定的选中机会, 分N次从S中随机选定N个染色体, 并进行复制。
这里的选择概率P(xi)的计算公式为
7
交叉就是互换两个染色体某些位上的基因。
s1′=01000101, s2′=10011011
可以看做是原染色体s1和s2的子代染色体。
例如, 设染色体 s1=01001011, s2=10010101, 交换其后4位基因, 即
8
变异就是改变染色体某个(些)位上的基因。
例如, 设染色体 s=11001101
将其第三位上的0变为1, 即
s=11001101 →11101101= s′。
s′也可以看做是原染色体s的子代染色体。
9
基本遗传算法
遗传算法基本流程框图
生成初始种群
计算适应度
选择-复制
交叉
变异
生成新一代种群
终止?
结束
10