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