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

变异算子的改进 基本遗传算法(SGA)中,变异概率是固定不变的，通常是一个很小的常数。在遗传进化后期,如果变异概率不发生改变，很容易造成局部收敛的情况,从而对算法的运行效率产生极大地影响。 提出一种修正过的变异概率p。随适应度作自适应变化的公式： Pm为将要变异个体的变异概率，Pm_max 为最大变异概率, 这里取0.2，Pm_min为最小变异概率,这里取0.001，f即为将 要变异个体的适应度， f_max为种群中最大的适应度，favg为每一代种群适应度的平均值。 变异的个体的适应度大于等于此时种群的平均适应度时，如果将要变异个体的适应度越大，则该个体的变异概率就越小，正好符合“优胜劣汰,适者生存”的进化规律。 变异的个体的适应度小于此时种群的平均适应度时，说明此个体为劣质个体或是非优良个体，不适应生存，为了扩大解空间，增强种群的多样性,需要给该个体一个较大的变异概率。 这样做还可以使算法的局部有哪些信誉好的足球投注网站能力增强，有助于算法更快地达到全局收敛，因而能够很好的改善遗传算法的性能。 遗传算法的应用及一些问题 1、遗传算法的应用领域 （1）组合优化 （2）函数优化 （3）自动控制 （4）生产调度 （5）图像处理 （6）机器学习 （7）人工生命 （8）数据挖掘 2、遗传算法在应用中的一些问题 1）知识的编码 二进制和十进制的比较：二进制有更多图式和更大的有哪些信誉好的足球投注网站范围；十进制更接近于实际操作。 基本遗传算法应用实例： 求函数的最大值 遗传算法算法实现背包问题 假定背包的最大容量为W，N件物品，每件物品都有自己的价值和重量，将物品放入背包中使得背包内物品的总价值最大。 背包问题是一种组合优化的NP完全问题。 背包问题 可以想象这样一个场景—小偷在屋子里偷东西，他带着一只背包。屋子里物品数量有限—每件物品都具有一定的重量和价值—珠宝重量轻但价值高，桌 子重但价值低。最重要的是小偷背包容量有限。很明显，他不能把桌子分成两份或者带走珠宝的3/4。对于一件物品他只能选择带走或者不带走。 遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。 所谓状态,?是指在一定的时空范围内，问题所涉及的人、物、时间等的布局关系。通常把问题的初始布局关系称为初始状态，问题解决时到达的状态叫目标状态。 知识表示 状态空间 在背包问题中，初始状态就是有一个空包，包的重量固定为W，有N个商品，每个商品的重量为Wi,价值Ci。目标状态就是将n(n=N)个商品装入包里，包重不超过W，使得包中商品的总重量最大。状态空间就是将商品装入包的所有组合，本实验的解就是价值和最大的装包组合。 3、遗传算法中的抽象概念在背包问题的具体化 （1）基因：0或1，代表相应的商品选还是不选。 （2）染色体：本实验中固定有50个商品，所以染色体就是50个基因序列， 也就是40个0、1串，代表了一种往包里装商品的组合。 一个染色体例：0111101101011011110101110101010101011110。 （3）群体：一定数量的基因个体组成了群体(population),群体中个体的数量 叫做群体大小。本实验的背包问题中，种群大小为100，代表100个往包里 装商品的组合。 （4）适应度:各个个体对环境的适应程度叫做适应度。本实验的背包问题中， 每染色体个体的适应度为选入包中的商品的价值和。 算法实现 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; //适应度 unsigned int parent1,parent2,cross;