《分布式估计算法讲解》由会员分享，可在线阅读，更多相关《分布式估计算法讲解（78页珍藏版）》请在金锄头文库上搜索。
1、算法设计与分析 分布式估计算法主要知识点：1 、传统遗传算法2 、分布式估计算法与传统遗传算法的区别3 、分布式估计算法应用举例4、分布式估计算法的分类5、分布式估计算法的理论基础2 21、传统遗传算法1. 个体与种群个体与种群 个体就是模拟生物个体而对问题中的对象 （一般就是问题的解）的一种称呼，一个个 体也就是搜索空间中的一个点。 种群(population)就是模拟生物种群而由若 干个体组成的群体, 它一般是整个搜索空间 的一个很小的子集。3 32. 适应度与适应度函数适应度与适应度函数 适应度(fitness)就是借鉴生物个体对环境的 适应程度,而对问题中的个体对象所设计的 表征其优劣
2、的一种测度。 适应度函数(fitness function)就是问题中的 全体个体与其适应度之间的一个对应关系。 它一般是一个实值函数。该函数就是遗传算 法中指导搜索的评价函数。4 43. 3. 染色体与基因染色体与基因染色体（chromosome）就是问题中个体的某种字符串形式的编码表示。字符串中的字符也就称为基因（gene）。 例如： 个体 染色体 9 - 1001 （2，5，6）- 010 101 1105 54. 4. 遗传操作遗传操作亦称遗传算子(genetic operator)，就是关于染色体的运算。遗传算法中有三种遗传操作: 选择-复制(selection-reproducti
3、on) 交叉(crossover，亦称交换、交配或杂交) 变异(mutation，亦称突变) 6 6选择-复制通常做法是：对于一个规模为N的种群S,按每个染色体xiS的选择概率P(xi)所决定的选中机会, 分N次从S中随机选定N个染色体, 并进行复制。 这里的选择概率P(xi)的计算公式为7 7交叉 就是互换两个染色体某些位上的基因。 s1=01000101, s2=10011011可以看做是原染色体s1和s2的子代染色体。 例如, 设染色体 s1=01001011, s2=10010101, 交换其后4位基因, 即8 8 变异变异 就是改变染色体某个(些)位上的基因。 例如, 设染色体 s=
4、11001101将其第三位上的0变为1, 即 s=11001101 11101101= s。 s也可以看做是原染色体s的子代染色体。9 91.2 基本遗传算法 遗传算法基本流程框图生成初始种群计算适应度选择-复制交叉变异生成新一代种群终止 ?结束1010 基本遗传算法步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中适应度最大的个体作为所求结果，算法结束。111
5、1 步5 按选择概率P(xi)所决定的选中机会，每次从S中随机选定1个个体并将其染色体复制，共做N次，然后将复制所得的N个染色体组成群体S1； 步6 按交叉率Pc所决定的参加交叉的染色体数c，从S1中随机确定c个染色体，配对进行交叉操作，并用产生的新染色体代替原染色体，得群体S2；1212 步7 按变异率Pm所决定的变异次数m，从S2中随机确定m个染色体，分别进行变异操作，并用产生的新染色体代替原染色体，得群体S3；步8 将群体S3作为新一代种群，即用S3代替S，t = t+1，转步3； 13131.3 遗传算法应用举例 例例1 利用遗传算法求解区间0,31上的二次函数y=x2的最大值，x为整
6、数。y=x2 31 XY1414 分析 原问题可转化为在区间0, 31中搜索能使y取最大值的点a的问题。那么，0, 31 中的点x就是个体, 函数值f(x)恰好就可以作为x的适应度，区间0, 31就是一个(解)空间 。这样, 只要能给出个体x的适当染色体编码, 该问题就可以用遗传算法来解决。1515解(1) 设定种群规模,编码染色体，产生初始种群。 将种群规模设定为4；用5位二进制数编码染色体；取下列个体组成初始种群S1: s1= 13 (01101), s2= 24 (11000) s3= 8 (01000), s4= 19 (10011) (2) 定义适应度函数, 取适应度函数：f (x)
7、=x2 1616(3) 计算各代种群中的各个体的适应度, 并对其染色体进行遗传操作,直到适应度最高的个体(即31（11111）)出现为止。 1717首先计算种群S1中各个体 s1= 13(01101), s2= 24(11000) s3= 8(01000), s4= 19(10011)的适应度f (si) 。 容易求得 f (s1) = f(13) = 132 = 169 f (s2) = f(24) = 242 = 576 f (s3) = f(8) = 82 = 64 f (s4) = f(19) = 192 = 3611818再计算种群S1中各个体的选择概率。选择概率的计算公式为 由此可
8、求得 P(s1) = P P(s2) = P(24) = 0.49 P(s3) = P P(s4) = P1919 赌轮选择法s40.31s20.49s10.14s30.062020在算法中赌轮选择法可用下面的子过程来模拟: 在0, 1区间内产生一个均匀分布的随机数r。 若rq1,则染色体x1被选中。 若qk-1rqk(2kN), 则染色体xk被选中。 其中的qi称为染色体xi (i=1, 2, , n)的积积累累概概率率, 其计算公式为 2121选择-复制 设从区间0, 1中产生4个随机数如下: r1 = 0.450126, r2 = 0.110347 r3 = 0.572496, r4 染
9、色体 适应度选择概率积累概率选中次数s1=01101 169 0.14 0.14 1s2=11000 576 0.49 0.63 2s3=01000 64 0.06 0.69 0s4=10011 361 0.31 1.00 12222于是，经复制得群体：s1 =11000（24）, s2 =01101（13） s3 =11000（24）, s4 =10011（19） 2323交叉 设交叉率pc=100%，即S1中的全体染色体都参加交叉运算。 设s1与s2配对，s3与s4配对。分别交换后两位基因，得新染色体： s1=11001（25）, s2=01100（12） s3=11011（27）, s4
10、=10000（16）2424变异 设变异率pm。 这样，群体S1中共有 54位基因可以变异。 位显然不足1位，所以本轮遗传操作不做变异。2525 于是，得到第二代种群S2： s1=11001（25）, s2=01100（12） s3=11011（27）, s4=10000（16） 2626 第二代种群第二代种群S2中各染色体的情况中各染色体的情况 染色体 适应度选择概率积累概率 估计的选中次数s1=11001 625 0.36 0.36 1s2=01100 144 0.08 0.44 0s3=11011 729 0.41 0.85 2s4=10000 256 0.15 1.00 12727如此
11、不断进化，直到种群中出现适应度最高的染色体s1=11111。于是，遗传操作终止，将染色体“11111”作为最终结果输出。然后，将染色体“11111”解码为表现型，即得所求的最优解：31。 将31代入函数y=x2中，即得原问题的解，即函数y=x2的最大值为961。28282、分布式估计算法与传统遗传算法的区别分布式估计算法是一种全新的进化模式，没有传统遗传算法的交叉和变异操作，取而代之的是概率模型的学习和采样。分布式估计算法通过一个概率模型描述候选解在空间的分布，采用统计学习的手段从宏观上建立一个描述解分布的概率模型，然后对概率模型进行随机采样产生新的种群，如此反复进行，实现种群的进化，直到终止
12、条件。2929根据概率模型的复杂程度以及不同的采样方法，分布式估计算法发展了很多不同的具体实现方法，但是都可以归纳为下面两个主要步骤：1）、构建描述解空间的概率模型。通过对种群的评估，选择优秀的个体集合，然后采样统计学习等手段构造一个描述当前解集的概率模型2）、由概率模型随机采样产生新的种群。一般的，采用蒙特卡罗方法，对概率模型采样得到新的种群。3030下面通过一个简单的EDA算例，介绍该方法独特的进化操作，使读者对EDA方法有一个直观的认识.3 、分布式估计算法应用举例3131323233333434353536363737分布式估计和传统遗传算法的对比38384、分布式估计算法的分类变量无
13、关双变量相关多变量相关3939、变量无关的分布式估计算法最简单，假设各变量之间是独立的，那么任意解的概率可以表示为：比较有代表性的算法有如下几种：PBIL(Population based Incremental Algorithm)UMDA(Univariate Marginal Distribution Algorithm)cGA(compact Genetic Algorithm)4040PBIL方法41414242算法伪代码4343应用例子旅行推销员问题（又称为旅行商问题、TSP问题）是一个多局部最优的最优化问题：有n个城市，一个推销员要从其中某一个城市出发，唯一走遍所有的城市，再回到
14、他出发的城市，求最短的路线。 工作调度问题。函数优化问题。4444UMDA UMDA与PBIL唯一不同在于概率向量的更新算法，前面的例子实际就是UMDA算法！算法描述如下：45454646应用例子4747484849495050515152525353545455555656请同学们继续！5757cGA 与UMDA、PBIL不同也在于概率向量的更新算法，并且种群规模很小，只产生两个个体，算法描述如下：58585959双变量相关的分布式估计算法这类算法，概率模型可以表示至多两个变量之间的关系。主要有MIMIC(Mutual information maximization for input clustering)、COMIT、BMDA6060MIMIC解空间描述模型为（假设）：6161衡量两个分布之间的距离，可以采用K-L距离，定义如下：实际上是信息理论中的相对熵，它是非对称的。6262熵：简单学习一下熵理论：6363条件熵：6464h(p)是p分布的熵，是固定值，随排列变化而变化，我们希望最小化：656566666767多变量相关分布式估计算法68686969707071717272贝叶斯信念网络737374747575767677775、分布式估计算法的理论基础略!7878
