《2遗传算法2学习资料》由会员分享，可在线阅读，更多相关《2遗传算法2学习资料（43页珍藏版）》请在金锄头文库上搜索。
1、河北大学,吴彬 ( ),1,2遗传算法(2),遗传算法技术介绍,河北大学,2,吴彬 ( ),2.1遗传算法,产生初始群体 （编码） 循环(终止) 计算适应度（解码） 复制（轮盘选择实现） 交换（单点交换） 变异（基本变异）,河北大学,3,吴彬 ( ),2.4遗传算法更多技术,遗传算法是个体多样性搜索和提高种群整体适应度的结合。 适应度是和目标函数相关的，可以认为适应度是目标函数的一个函数。 适应度的分配是很重要的，处理好各个个体的适应度的差别。(分配适应度原因) 复制（选择）过程是依赖于适应度的。 交换和变异过程，都是扩大种群多样性的过程。,河北大学,4,吴彬 ( ),2.4遗传算法更多技术,
2、复制（选择）的一个矛盾 选择的过程，是既要保证种群多样性又要促进收敛。 为了解决这个矛盾需要进行适应度调整，或者说进行适应度分配。也究是说，进行适应度分配的原因是为了解决“选择”的矛盾。,河北大学,6,吴彬 ( ),重新分配适应度解决“选择” 矛盾,在初期，左图需要缩小适应度之间的差别，以保证种群的多样性。 在后期，右图需要扩大适应度之间的差别，以保证好的个体更容易被选出。,河北大学,7,吴彬 ( ),适应度与选择,适应度分配的过程可以放到选择过程中进行，即先调整适应度，然后进行选择。 或者把适应度分配选择看出两个过程进行。 我们采用后者，于是适应度分配有 线性变换 Ranking适应度分配（
3、相对适应度，或称为选择概率） 波尔兹曼法适应度分配 选择过程有 比例选择法（轮盘选择） 随机一致选择 竞技选择法,河北大学,8,吴彬 ( ),2.4遗传算法更多技术,二进制编码格雷码 适应度 线性变换 Ranking适应度分配 波尔兹曼法适应度分配 约束条件处理（下次课介绍） 复制 比例选择法（轮盘选择） 随机一致选择 竞技选择法 交换 1点交换(单点交换) K点交换(多点交换) K点杂乱交换 均匀交换 突变 种群规模 其他算子 倒序算子,河北大学,9,吴彬 ( ),谢谢,参考文献 GEATbx_Intro_Algorithmen_v33a， Evolutionary Algorithms a
4、nd Optimization: Theory and its Applications, ppt, From Internet. 进化算法，云庆夏，冶金工业出版社，2000 遗传算法原理及应用，周明，孙树栋，国防工业出版社，1999 二进制格雷码与自然二进制码的互换, 游志宇,中国科学院光电技术研究所,河北大学,10,吴彬 ( ),后面是细节,前面的ppt是后面的一个纲要 后面的ppt是前面纲要的细节,河北大学,11,吴彬 ( ),二进制编码格雷码,二进制编码格雷码 格雷码是为了提高遗传算法的局部搜索能力而产生的。 原始的二进制编码的搜索能力差表现在如下： 交叉：相近个体的交叉，新个体却远离
5、原先个体。 变异：二进制编码染色体某一位的微小变化，新个体却产生了较大变化。,河北大学,12,吴彬 ( ),二进制编码格雷码,交叉 变异,河北大学,13,吴彬 ( ),二进制编码格雷码,为了避免上述问题，希望二进制编码在差别不大时，其对于的实际值也差别不大。 0100 7 1100 8 为此人们提出“格雷码”，使得连续整数对应的格雷码只相差一位。 1 0001 2 0011 3 0010,河北大学,14,吴彬 ( ),二进制编码格雷码,河北大学,15,吴彬 ( ),二进制编码格雷码,自然二进制码转换成二进制格雷码,河北大学,16,吴彬 ( ),二进制编码格雷码,二进制格雷码转换成自然二进制码,
6、河北大学,17,吴彬 ( ),二进制编码格雷码,格雷码特点 任意两个相邻整数的海明距离总是1。 海明距离：两个码字的对应比特取值不同的比特数称为这两个码字的海明距离。 换句话说就是“相邻整数对应的编码只差一位”。,河北大学,18,吴彬 ( ),线性变换,先决条件：应保证 均大于0 可以看到a,b直接影响了变化的大小，一般对其选择有两个要求。 对群体规模大小为50100个个体情况，一般c1.22,河北大学,19,吴彬 ( ),线性变换,一般情况,河北大学,20,吴彬 ( ),线性变换,河北大学,21,吴彬 ( ),线性变换,带入a, b,河北大学,22,吴彬 ( ),线性变换,为了避免出现情况
7、做判断,河北大学,23,吴彬 ( ),线性变换,当有 情况出现时，不再要求条件(*)，而是要求,河北大学,24,吴彬 ( ),线性变换,存在 情况,河北大学,25,吴彬 ( ),线性变换,河北大学,26,吴彬 ( ),线性变换总结,判断 是 否,河北大学,27,吴彬 ( ),Ranking适应度分配,思想：按某一原则对目标函数排序，适应度的分配根据排序后该个体在排序中的位置来分配。,河北大学,28,吴彬 ( ),Ranking适应度分配,线性分级 q为最优个体的相对适应度（选择概率） d为相邻个体的相对适应度之差（相邻个体的选择概率之差） 写成通式 下面的问题是q和d如何确定。,河北大学,29
8、,吴彬 ( ),Ranking适应度分配,为了确定q或d的范围考虑两种极端情况 (1)d0 (2)d最大，即 q-(M-1)d=0,河北大学,30,吴彬 ( ),Ranking适应度分配,把两种情况代入，计算得到q的变换范围，在范围内任选q，之后可根据下式计算d的大小。,河北大学,31,吴彬 ( ),波尔兹曼法适应度分配,通过控制温度T来调节选择力度，使选择力度随时间而变化。（T仿照模拟退火的方式降温）,河北大学,32,吴彬 ( ),波尔兹曼法适应度分配,在遗传算法初期，T值取大值，则 之间的差值被缩小，性能欠佳的个体容易被选中参与复制。 随着选代过程的进行，T值不断变小，优劣个体之间的差距增
9、大，从而阻止劣质个体参与复制。,河北大学,33,吴彬 ( ),复制(选择),选择力度：好坏个体被选择的差别的大小。 选择力度越大，群体缺乏多样性，提高收敛速度。 选择力度越小，保持群体多样性，降低收敛速度。,河北大学,34,吴彬 ( ),复制_比例选择法（轮盘选择）,0.81, 0.32, 0.96, 0.01, 0.65, 0.42. 6, 2, 9, 1, 5, 3,河北大学,35,吴彬 ( ),复制_随机一致选择,1/6=0.167 0, 0.167 0.1 1, 2, 3, 4, 6, 8,河北大学,36,吴彬 ( ),复制_竞技选择法,(1)从第t代群体中随机选择k个个体 (2)比较
10、k个个体的适应度，复制适应度最大者进入第t+1代，被复制的个体仍保留在第t代。 (3)重复执行(1)(2)M次，直至产生同t代一样的个体数目。 选择的力度取决于k值的大小。k值越大，每次选出的优胜者有很高的适应度。反之，k值越小，优胜者的适应度或高或低，随机性较强。,河北大学,37,吴彬 ( ),交换,1点交换(单点交换),河北大学,38,吴彬 ( ),交换,K点交换(多点交换),河北大学,39,吴彬 ( ),交换,K点杂乱交换 1,打乱顺序 2,K点交换 3,复原顺序,河北大学,40,吴彬 ( ),交换,均匀交换,河北大学,41,吴彬 ( ),突变,突变概率的选取 突变概率取决于字符串长度和群体规模。 突变概率随时间而变换。,河北大学,42,吴彬 ( ),突变,河北大学,43,吴彬 ( ),其他算子,倒序算子,
