遗传算法及应用.pptx

《遗传算法及应用.pptx》由会员分享，可在线阅读，更多相关《遗传算法及应用.pptx（35页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、引子：智能优化算法 智能优化算法又称为现代启发式算法，是一种具有全局优化性能、通用性强、且适合于并行处理的算法。这种算法一般具有严密的理论依据，而不是单纯凭借专家经验，理论上可以在一定的时间内找到最优解或近似最优解。第1页/共35页常用的智能优化算法（1）遗传算法（Genetic Algorithm，简称GA）（2）模拟退火算法（Simulated Annealing，简称SA）（3）禁忌搜索算法（Tabu Search，简称TS）第2页/共35页智能优化算法的特点它们的共同特点：都是从任一解出发，按照某种机制，以一定的概率在整个求解空间中探索最优解。由于它们可以把搜索空间扩展到整个问题空间，

2、因而具有全局优化性能。第3页/共35页遗传算法起源 遗传算法是由美国的J.Holland教授于1975年在他的专著自然界和人工系统的适应性中首先提出的，它是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。第4页/共35页遗传算法的搜索机制 遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。第5页/共35页一、基本遗传算法概念一、基本遗传算法概念 基本遗传算法（基本遗传算法（Simple Gene

3、tic AlgorithmsSimple Genetic Algorithms，简称，简称SGASGA，又称简单遗传算法或标准遗传算法），又称简单遗传算法或标准遗传算法），是由是由GoldbergGoldberg总结出的一种最基本的遗传算法，其遗传进化操作过程简单，容易理解，是其它一些遗传算总结出的一种最基本的遗传算法，其遗传进化操作过程简单，容易理解，是其它一些遗传算法的雏形和基础。法的雏形和基础。第6页/共35页基本遗传算法的组成基本遗传算法的组成 （1 1）编码（产生初始种群）编码（产生初始种群）（2 2）适应度函数）适应度函数（3 3）遗传算子（选择、交叉、变异）遗传算子（选择、交叉、

4、变异）（4 4）运行参数）运行参数第7页/共35页 编码编码 GA GA是通过某种编码机制把对象抽象为由特定符号按一定顺序是通过某种编码机制把对象抽象为由特定符号按一定顺序排成的串。正如研究生物遗传是从染色体着手，而染色体则是由基因排成的串。正如研究生物遗传是从染色体着手，而染色体则是由基因排成的串。排成的串。SGASGA使用二进制串进行编码。使用二进制串进行编码。第8页/共35页函数优化示例函数优化示例 求下列一元函数的最大值求下列一元函数的最大值：x-1,2 x-1,2 ，求解结果精确到，求解结果精确到6 6位小数。位小数。第9页/共35页SGASGA对于本例的编码对于本例的编码 由于区间

5、长度为由于区间长度为3 3，求解结果精确到，求解结果精确到6 6位小数，因此可将自变量定义区间划分位小数，因此可将自变量定义区间划分为为3 3 10106 6等份。又因为等份。又因为2 22121 3 3 10106 6 2 22222 ，所以本例的二进制编码长度至少需要，所以本例的二进制编码长度至少需要2222位，本例的编码过程实质上是将区间位，本例的编码过程实质上是将区间-1-1，22内对应的实数值转化为一个二进制串内对应的实数值转化为一个二进制串（b21b20b0b21b20b0）。）。第10页/共35页几个术语几个术语 1000101110110101000111 表现型：表现型：0.

6、637197 编码解码个体（染色体）基因第11页/共35页初始种群初始种群 SGA SGA采用随机方法生成若干个个体的集合，该集合称为初始种群。初采用随机方法生成若干个个体的集合，该集合称为初始种群。初始种群中个体的数量称为种群规模。始种群中个体的数量称为种群规模。第12页/共35页 适应度函数适应度函数 遗传算法对一个个体（解）的好坏用适应度函数值来评价，适应度遗传算法对一个个体（解）的好坏用适应度函数值来评价，适应度函数值越大，解的质量越好。适应度函数是遗传算法进化过程的驱动力，也函数值越大，解的质量越好。适应度函数是遗传算法进化过程的驱动力，也是进行自然选择的唯一标准，它的设计应结合求解

7、问题本身的要求而定。是进行自然选择的唯一标准，它的设计应结合求解问题本身的要求而定。第13页/共35页选择算子选择算子 遗传算法使用选择运算来实现对群体遗传算法使用选择运算来实现对群体中的个体进行优胜劣汰操作：适应度高的个体中的个体进行优胜劣汰操作：适应度高的个体被遗传到下一代群体中的概率大；适应度低的被遗传到下一代群体中的概率大；适应度低的个体，被遗传到下一代群体中的概率小。选择个体，被遗传到下一代群体中的概率小。选择操作的任务就是按某种方法从父代群体中选取操作的任务就是按某种方法从父代群体中选取一些个体，遗传到下一代群体。一些个体，遗传到下一代群体。SGASGA中选择算中选择算子采用子采用

8、轮盘赌轮盘赌选择方法。选择方法。第14页/共35页轮盘赌选择方法轮盘赌选择方法 轮盘赌选择又称比例选择算子，它的基本轮盘赌选择又称比例选择算子，它的基本思想是：各个个体被选中的概率与其适应度函数思想是：各个个体被选中的概率与其适应度函数值大小成正比。设群体大小为值大小成正比。设群体大小为n n，个体，个体i i 的适应度的适应度为为 F Fi i，则个体，则个体i i 被选中遗传到下一代群体的被选中遗传到下一代群体的概率概率为：为：第15页/共35页轮盘赌选择方法的实现步骤轮盘赌选择方法的实现步骤（1 1）计算群体中所有个体的适应度函数值（需计算群体中所有个体的适应度函数值（需要解码）；要解码

9、）；（2 2）利用比例选择算子的公式，计算每个个体利用比例选择算子的公式，计算每个个体被选中遗传到下一代群体的概率；被选中遗传到下一代群体的概率；（3 3）采用模拟赌盘操作（采用模拟赌盘操作（即生成即生成0 0 0 0到到1 1 1 1之间的随之间的随机数机数与每个个体遗传到下一代群体的概率进行与每个个体遗传到下一代群体的概率进行匹配）来确定各个个体是否遗传到下一代群体匹配）来确定各个个体是否遗传到下一代群体中。中。第16页/共35页轮盘赌图例：第17页/共35页交叉算子交叉算子 所谓交叉运算，是指对两个相互配对所谓交叉运算，是指对两个相互配对的染色体依据交叉概率的染色体依据交叉概率 P Pc

10、 c 按某种方式相互交换按某种方式相互交换其部分基因，从而形成两个新的个体。交叉运其部分基因，从而形成两个新的个体。交叉运算是遗传算法区别于其他进化算法的重要特征，算是遗传算法区别于其他进化算法的重要特征，它在遗传算法中起关键作用，是产生新个体的它在遗传算法中起关键作用，是产生新个体的主要方法。主要方法。SGASGA中交叉算子采用单点交叉算子。中交叉算子采用单点交叉算子。第18页/共35页单点交叉运算单点交叉运算 交叉前：交叉前：00000|0111000000001000000000|01110000000010000 11100|0000011111100010111100|0000011

11、1111000101 交叉后：交叉后：00000|0000011111100010100000|00000111111000101 11100|0111000000001000011100|01110000000010000交叉点交叉点第19页/共35页第20页/共35页多点交叉运算多点交叉运算第21页/共35页变异算子变异算子 所谓变异运算，是指依据变异概率所谓变异运算，是指依据变异概率 P Pm m 将个体将个体编码串中的某些基因值用其它基因值来替换，编码串中的某些基因值用其它基因值来替换，从而形成一个新的个体。遗传算法中的变异从而形成一个新的个体。遗传算法中的变异运算是产生新个体的辅助方

12、法，它决定了遗运算是产生新个体的辅助方法，它决定了遗传算法的局部搜索能力，同时保持种群的多传算法的局部搜索能力，同时保持种群的多样性。交叉运算和变异运算的相互配合，共样性。交叉运算和变异运算的相互配合，共同完成对搜索空间的全局搜索和局部搜索。同完成对搜索空间的全局搜索和局部搜索。SGASGA中变异算子采用基本位变异算子。中变异算子采用基本位变异算子。第22页/共35页基本位变异算子基本位变异算子 基本位变异算子是指对个体编码串随机指定的某基本位变异算子是指对个体编码串随机指定的某一位或某几位基因作变异运算。对于基本遗传算一位或某几位基因作变异运算。对于基本遗传算法中用二进制编码符号串所表示的个

13、体，若需要法中用二进制编码符号串所表示的个体，若需要进行变异操作的某一基因座上的原有基因值为进行变异操作的某一基因座上的原有基因值为0 0，则变异操作将其变为，则变异操作将其变为1 1；反之，若原有基因值；反之，若原有基因值为为1 1，则变异操作将其变为，则变异操作将其变为0 0。第23页/共35页基本位变异算子的执行过程基本位变异算子的执行过程 变异前：变异前：00000111000000001110000 0000010000000010000 变异后：变异后：00000111000000001110001 1000010000000010000变异点变异点第24页/共35页运行参数运行参

14、数 （1 1）M M ：种群规模种群规模 （2 2）T T ：遗传运算的终止进化代数遗传运算的终止进化代数 （3 3）P Pc c ：交叉概率交叉概率 （4 4）P Pm m：变异概率变异概率 第25页/共35页SGASGA的框图的框图 产生初始群体产生初始群体是否满足停止准则是否满足停止准则是是输出结果并结束输出结果并结束计算个体适应度值计算个体适应度值比例选择运算比例选择运算单点交叉运算单点交叉运算基本位变异运算基本位变异运算否否产生新一代群体产生新一代群体第26页/共35页遗传算法的应用领域n（1）组合优化 （2）函数优化 n（3）自动控制 （4）生产调度 n（5）图像处理 （6）机器学习 n（7）人工生命 （8）数据挖掘 第27页/共35页实例：寻找如下函数的最小值问题这是一个非常复杂多极值问题第28页/共35页第29页/共35页第30页/共35页第31页/共35页第32页/共35页上机练习题：1：利用遗传算法计算最大值第33页/共35页2、利用遗传算法求、利用遗传算法求Rosenbrock函数的极大值函数的极大值第34页/共35页感谢您的观看！第35页/共35页