遗传算法改进及经典算法应用PPT.ppt

;主要内容;1、优化方法;2、遗传算法优点;GA流程;遗传算法基本原理;选择运算 从旧的种群中选择适应度高的染色体，放入匹配集（缓冲区），为以后染色体交换、变异，产生新的染色体作准备。;具体步骤;举例：⒈具有6个染色体的二进制编码、适应度值、Pc累计值。;染色体被选的概率;交换操作;变异;简单遗传算法（GA）的基本参数 ;实例;3、选择;3、选择;3、选择;4、交叉;5、变异;6、至下一代，适应度计算→选择→交叉→变异，直至满足终止条件。;遗传算法的改进; 其次是在遗传进化的末了阶段,这个时候种群中的所有个体之间的差异不是很大了,因而适应度也很接近,所以此时的轮盘赌选择方法已经无效,丧失了继续选择的功能,也就无法分辨种群中个体的好坏了。 ;改进方法： 对种群中的全部个体来一次排序,根据种群中每个个体的适应度高低对这些个体进行降序列出。 把这些按顺序排列出来的所有个体从头到尾依次分成四等份。 适应度最低的排在最后面的1/4比例的个体全部扔掉,也就是直接淘汰掉,不进入到下一代当中;把适应度中等的排在中间的2/4比例的个体全部拷贝一份,也就是选择到下一代当中;剩下来的适应度最高的排在最前面的1/4比例的个体全部拷贝两份,也就是把这两份都选择到下一代当中。;采用此种改进策略进行选择操作可以有以下几种好处: 一、可以把适应度非常低的个体直接淘汰出该种群，使得这些个体没有机会进入到下一代当中，因此能够提升算法的收敛速度。 二、快速增加种群中适应度较好的个体的数量，使得算法更加高效实用。;交叉算子的改进; 假设个体x的染色体编码个体Y的染色体编码则个体X和个体Y的最长的共同子串就为101011。这个最长的共同子串的长度即为6，也就是C等于6，种群中个体染色体编码的长度是8，也即n等于8,因此就得到了个体X和个体Y的相似度的大小，即等于6/8。显然，种群中任意两个个体的相似度S的值是一个[0,1]之间的数。; r是一个(1/3,2/3]之间的数，并不是固定不变的，是随着当前的进化代数的增长而不断增大的。 如果需要进行交叉的两个父代个体的相似度S大于或等于当前的交叉临界值r时，则不准这两个父代个体进行交叉互换操作，以避免破坏它们的优良基因模式。 需要进行交叉的两个父代个体的相似度S小于当前的交叉临界值r时，则允许这两个父代个体进行交叉互换操作。 ; 在种群进化的初期，由于种群中各个个体之间的差异比较大，因此它们的染色体编码也具有很大的差别，这个时候种群中各个个体之间的相似程度也会很小，所以必须给出一个相对较小的交叉临界值。 随着种群的不断进化，种群中各个个体之间的差异会渐渐变小，因而各个个体之间的相似程度也会渐渐提高，所以此时必须给出一个相对较大的交叉临界值。 种群中个体之间的交叉临界值随着当前进化代数动态的改变是有道理的，有助于提高遗传算法的收敛性能以及收敛速度。;变异算子的改进; 变异的个体的适应度大于等于此时种群的平均适应度时，如果将要变异个体的适应度越大，则该个体的变异概率就越小，正好符合“优胜劣汰,适者生存”的进化规律。;遗传算法的应用及一些问题;基本遗传算法应用实例： 求函数的最大值;遗传算法算法实现背包问题; 遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因??gene）编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。; 在背包问题中，初始状态就是有一个空包，包的重量固定为W，有N个商品，每个商品的重量为Wi,价值Ci。目标状态就是将n(n=N)个商品装入包里，包重不超过W，使得包中商品的总重量最大。状态空间就是将商品装入包的所有组合，本实验的解就是价值和最大的装包组合。;算法实现 1、 数据结构 （1）重要参数： #define zhongqun_size 100 //种群的规模 #define pc 0.8 //杂交概率 #define pm 0.08 //变异概率 #define chrom_length 50 //染色体长度 #define max_daishu 1000 //最大进化代数 （2）染色个体： struct population { unsigned int chrom[chrom_length]; //染色体 double weight; //背包重量 double fitness;