分布式估计算法讲解课件

算法设计与分析

分布式估计算法

主要知识点：1、传统遗传算法2、分布式估计算法与传统遗传算法的区别3、分布式估计算法应用举例4、分布式估计算法的分类5、分布式估计算法的理论基础21、传统遗传算法1.

个体与种群●个体就是模拟生物个体而对问题中的对象（一般就是问题的解）的一种称呼，一个个体也就是搜索空间中的一个点。●种群(population)就是模拟生物种群而由若干个体组成的群体,它一般是整个搜索空间的一个很小的子集。33.染色体与基因

染色体（chromosome）就是问题中个体的某种字符串形式的编码表示。字符串中的字符也就称为基因（gene）。例如：个体染色体

9----

1001（2，5，6）----01010111054.遗传操作亦称遗传算子(geneticoperator)，就是关于染色体的运算。遗传算法中有三种遗传操作:

●

选择-复制(selection-reproduction)

●

交叉(crossover，亦称交换、交配或杂交)

●

变异(mutation，亦称突变)

6

选择-复制通常做法是：对于一个规模为N的种群S,按每个染色体xi∈S的选择概率P(xi)所决定的选中机会,分N次从S中随机选定N个染色体,并进行复制。

这里的选择概率P(xi)的计算公式为7

变异就是改变染色体某个(些)位上的基因。例如,设染色体s=11001101将其第三位上的0变为1,即s=11001101→11101101=s′。s′也可以看做是原染色体s的子代染色体。91.2基本遗传算法

遗传算法基本流程框图生成初始种群计算适应度选择-复制交叉变异生成新一代种群终止?结束10

基本遗传算法

步1在搜索空间U上定义一个适应度函数f(x)，给定种群规模N，交叉率Pc和变异率Pm，代数T；

步2随机产生U中的N个个体s1,s2,…,sN，组成初始种群S={s1,s2,…,sN}，置代数计数器t=1；

步3计算S中每个个体的适应度f()；

步4若终止条件满足，则取S中适应度最大的个体作为所求结果，算法结束。11

步7按变异率Pm所决定的变异次数m，从S2中随机确定m个染色体，分别进行变异操作，并用产生的新染色体代替原染色体，得群体S3；

步8

将群体S3作为新一代种群，即用S3代替S，t=t+1，转步3；

131.3遗传算法应用举例

例1利用遗传算法求解区间［0,31］上的二次函数y=x2的最大值，x为整数。

y=x2

31

XY14分析原问题可转化为在区间［0,31］中搜索能使y取最大值的点a的问题。那么，［0,31］中的点x就是个体,函数值f(x)恰好就可以作为x的适应度，区间［0,31］就是一个(解)空间。这样,只要能给出个体x的适当染色体编码,该问题就可以用遗传算法来解决。15

(3)计算各代种群中的各个体的适应度,并对其染色体进行遗传操作,直到适应度最高的个体(即31（11111）)出现为止。

17首先计算种群S1中各个体s1=13(01101),s2=24(11000)

s3=8(01000),s4=19(10011)的适应度f(si)。容易求得f(s1)=f(13)=132=169f(s2)=f(24)=242=576f(s3)=f(8)=82=64f(s4)=f(19)=192=36118再计算种群S1中各个体的选择概率。选择概率的计算公式为

由此可求得

P(s1)=P(13)=0.14P(s2)=P(24)=0.49P(s3)=P(8)=0.06P(s4)=P(19)=0.3119

在算法中赌轮选择法可用下面的子过程来模拟:①在［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=0.450126,r2=0.110347r3=0.572496,r4=0.98503

染色体适应度选择概率积累概率选中次数s1=011011690.140.141s2=110005760.490.632s3=01000640.060.690s4=100113610.311.00122于是，经复制得群体：s1’

=11000（24）,s2’

=01101（13）s3’

=11000（24）,s4’

=10011（19）

23变异设变异率pm=0.001。这样，群体S1中共有5×4×0.001=0.02位基因可以变异。0.02位显然不足1位，所以本轮遗传操作不做变异。25于是，得到第二代种群S2：s1=11001（25）,s2=01100（12）

s3=11011（27）,s4=10000（16）

262、分布式估计算法与传统遗传算法的区别分布式估计算法是一种全新的进化模式，没有传统遗传算法的交叉和变异操作，取而代之的是概率模型的学习和采样。分布式估计算法通过一个概率模型描述候选解在空间的分布，采用统计学习的手段从宏观上建立一个描述解分布的概率模型，然后对概率模型进行随机采样产生新的种群，如此反复进行，实现种群的进化，直到终止条件。29根据概率模型的复杂程度以及不同的采样方法，分布式估计算法发展了很多不同的具体实现方法，但是都可以归纳为下面两个主要步骤：1）、构建描述解空间的概率模型。通过对种群的评估，选择优秀的个体集合，然后采样统计学习等手段构造一个描述当前解集的概率模型2）、由概率模型随机采样产生新的种群。一般的，采用蒙特卡罗方法，对概率模型采样得到新的种群。30下面通过一个简单的EDA算例，介绍该方法独特的进化操作，使读者对EDA方法有一个直观的认识.3、分布式估计算法应用举例31323334353637分布式估计和传统遗传算法的对比384、分布式估计算法的分类变量无关双变量相关多变量相关394.1、变量无关的分布式估计算法最简单，假设各变量之间是独立的，那么任意解的概率可以表示为：比较有代表性的算法有如下几种：PBIL(PopulationbasedIncrementalAlgorithm)UMDA(UnivariateMarginalDistributionAlgorithm)cGA(compactGeneticAlgorithm)40PBIL方法4142算法伪代码43应用例子旅行推销员问题（又称为旅行商问题、TSP问题）是一个多局部最优的最优化问题：有n个城市，一个推销员要从其中某一个城市出发，唯一走遍所有的城市，再回到他出发的城市，求最短的路线。工作调度问题。函数优化问题。44UMDAUMDA与PBIL唯一不同在于概率向量的更新算法，前面的例子实际就是UMDA算法！算法描述如下：4546应用例子47484950515253545556请同学们继续！57cGA

与UMDA、PBIL不同也在于概率向量的更新算法，并且种群规模很小，只产生两个个体，算法描述如下：58594.2双变量相关的分布式估计算法这类算法，概率模型可以表示至多两个变量之间的关系。主要有MIMIC(Mutualinformationmaximizationforinputclustering)