2遗传算法(2)

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