遗传算法理论.ppt

在第1页，遗传算法的介绍，在第2页，非线性规划的基本概念，定义了优化问题，当至少一个目标函数或约束是非线性函数的非线性规划问题。(1)的一般形式，即En上定义的实函数，缩写为：在其他情况下，目标函数或约束条件的最大值小于或等于零的：个情况可以通过取其反数转换成上述一般形式。第3页麦加_zj，评论，非线性规划的解决通常比线性规划的解决困难得多，不同于线性规划，线性规划有一个适应一般情况的单纯形法。我们知道线性规划的可行域一般是凸集，其最优解是在可行域的边界上达到的。然而，非线性规划问题的可行域一般不是凸集，最优解不一定到达边界。现在各种算法都针对其特定的应用范围，这也是一个研究开发的课题领域。在第4页“罚函数法”中，罚函数法的基本思想是通过构造罚函数将约束问题转化为一系列无约束优化问题，然后用无约束优化方法求解。这种方法称为顺序无约束最小化方法。它简称为SUMT方法。一种是SUMT外点法，另一种是SUMT内点法。在第5页，T(X，M)被称为罚函数。M称为罚因子，M项称为罚项。这里的惩罚函数只惩罚不满足约束条件的点：此时，每个点都满足，所以惩罚项=0，没有惩罚。那时，必须有约束条件，所以惩罚项0受到惩罚。SUTM外部点法，麦加_zj，SUTM内部点法(障碍函数法)，第6页，麦加_zj，遗传算法，传统优化方法(局部优化)共轭梯度法，拟牛顿法，单纯形法，全局优化法，随机游走法，模拟退火法，遗传算法。关于优化问题，比较：传统的优化方法，1)依赖于初始条件。2)它与解空间密切相关，这有助于更快地收敛到局部解，但同时它对解域有约束，如可微的或连续的。使用这些约束，收敛很快。3)一些方法，如戴维森-弗莱彻-鲍威尔法，至少直接依赖于一阶导数；共轭梯度法隐含地依赖于梯度。第8页麦加_zj，全局优化方法，1)不依赖于初始条件；2)它与解空间没有密切关系，对解域没有可微的或连续的要求。解是鲁棒的，但是收敛速度很慢。可以获得全局最优解。它适用于解决空间未知的情况，第9页麦加_ zj , (1)选择操作，(2)交换操作，(3)变异，遗传算法的基本操作，遗传算法的基本原理，模拟自然界优胜劣汰的进化现象，将搜索空间映射到遗传空间，将可能的解编码成一个染色体的向量，向量的每个元素称为基因。通过不断计算每条染色体的适应度值，选择最佳染色体获得最优解。第10页，选择操作从旧群体中选择适应性强的染色体，并将它们放入匹配组(缓冲区)中，为染色体交换、突变和新染色体的产生做准备。选择方法适合度标度法(轮法)根据每条染色体的适合度标度确定要选择的染色体数目。选择一条染色体的概率：Pc，xi是群体中的第一条染色体，第11页，具体步骤：1)计算每条染色体的适合度值2)累加所有染色体的适合度值，记录中间累加值S-mid和最终累加值sum=f(xi)3)生成一个随机数n，0 n sum4)选择对应于中间累加值S-mid的第一条染色体并进入交换组5)重复(3)和(4)直到获得足够多的染色体。(选择对应于第一个=N的S-mid的染色体)，例如：1。六染色体二进制码，适应值和Pc cumu在第12页，麦加_zj，通过转轮法选择染色体的适合度和比例，在第13页，麦加_zj，染色体选择的概率，选择的染色体数，在第12页，10个染色体群体的比例选择过程，在第14页，麦加_zj，交换操作，方法：随机选择两条染色体(亲代染色体)，随机指定一个或多个点，通过交换可以获得两条新的染色体(后代染色体)。新的子代染色体：A11010|001B01011|110模拟了自然环境中生物体的变化并导致基因突变。在染色体二进制编码中，1变成0；或者0比1。突变产生了染色体的多样性，避免了进化中的早熟和陷入局部极值点。变异的概率很低。突变、复制不能创新，染色体的创新可以通过交换