遗传算法原理精选课件.ppt

《遗传算法原理精选课件.ppt》由会员分享，可在线阅读，更多相关《遗传算法原理精选课件.ppt（97页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、关于遗传算法原理关于遗传算法原理第一页，本课件共有97页报告提纲报告提纲一、遗传算法概述一、遗传算法概述 二、遗传算法原理二、遗传算法原理三、遗传算法的应用三、遗传算法的应用第二页，本课件共有97页一、遗传算法概述1 1、智能优化算法智能优化算法 2 2、基本遗传算法基本遗传算法 3 3、遗传算法的特点遗传算法的特点 第三页，本课件共有97页1 1、智能优化算法、智能优化算法 智能优化算法又称为现代启发式算法，智能优化算法又称为现代启发式算法，是一种具有全局优化性能、通用性强、且是一种具有全局优化性能、通用性强、且适合于并行处理的算法。这种算法一般具适合于并行处理的算法。这种算法一般具有严密的

2、理论依据，而不是单纯凭借专家有严密的理论依据，而不是单纯凭借专家经验，理论上可以在一定的时间内找到最经验，理论上可以在一定的时间内找到最优解或近似最优解。优解或近似最优解。第四页，本课件共有97页常用的智能优化算法常用的智能优化算法（1 1）遗传算法遗传算法遗传算法遗传算法 （Genetic AlgorithmGenetic Algorithm，简称简称简称简称GAGA）（2 2 2 2）模拟退火算法模拟退火算法模拟退火算法模拟退火算法（Simulated AnnealingSimulated Annealing，简称简称简称简称SASA）（3 3 3 3）禁忌搜索算法禁忌搜索算法禁忌搜索算法

3、禁忌搜索算法（Tabu SearchTabu Search，简称简称简称简称TSTS）第五页，本课件共有97页智能优化算法的特点智能优化算法的特点 它们的共同特点：都是从任一解出发，按它们的共同特点：都是从任一解出发，按照某种机制，以一定的概率在整个求解空间中照某种机制，以一定的概率在整个求解空间中探索最优解。由于它们可以把搜索空间扩展到探索最优解。由于它们可以把搜索空间扩展到整个问题空间，因而具有全局优化性能。整个问题空间，因而具有全局优化性能。返回返回第六页，本课件共有97页遗传算法起源遗传算法起源 遗传算法是由美国的遗传算法是由美国的J.Holland教授于教授于1975年在他的专著自然

4、界和人工系统的适应年在他的专著自然界和人工系统的适应性中首先提出的，它是一类借鉴生物界自然性中首先提出的，它是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法选择和自然遗传机制的随机化搜索算法。第七页，本课件共有97页遗传算法的搜索机制遗传算法的搜索机制 遗传算法模拟自然选择和自然遗传过程遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子从解群中选取较优的个体，利用遗传算子(选择、交叉和突变选择、交叉和突变)对这些个体进

5、行组合，对这些个体进行组合，产生新一代的候选解群，重复此过程，直到产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。满足某种收敛指标为止。返回返回第八页，本课件共有97页2 2、基本遗传算法、基本遗传算法 基本遗传算法（基本遗传算法（Simple Genetic Algorithms，简称，简称SGA，又称简单遗传算法或标准遗传算，又称简单遗传算法或标准遗传算法），是由法），是由Goldberg总结出的一种最基本的遗总结出的一种最基本的遗传算法，其遗传进化操作过程简单，容易理解，传算法，其遗传进化操作过程简单，容易理解，是其它一些遗传算法的雏形和基础。是其它一些遗传算法的雏形和基础。

6、第九页，本课件共有97页基本遗传算法的组成基本遗传算法的组成 （1 1）编码（产生初始种群）编码（产生初始种群）（2 2）适应度函数）适应度函数（3 3）遗传算子（选择、交叉、突变）遗传算子（选择、交叉、突变）（4 4）运行参数）运行参数第十页，本课件共有97页 编码编码 GA是通过某种编码机制把对象抽是通过某种编码机制把对象抽象为由特定符号按一定顺序排成的串。象为由特定符号按一定顺序排成的串。正如研究生物遗传是从染色体着手，正如研究生物遗传是从染色体着手，而染色体则是由基因排成的串。而染色体则是由基因排成的串。SGA使用二进制串进行编码。使用二进制串进行编码。第十一页，本课件共有97页函数优

7、化示例函数优化示例 求下列一元函数的最大值：求下列一元函数的最大值：x-1,2 x-1,2 ，求解结果精确到，求解结果精确到6 6位小数。位小数。第十二页，本课件共有97页SGA对于本例的编码对于本例的编码 由于区间长度为由于区间长度为3，求解结果精确到，求解结果精确到6位小位小数，因此可将自变量定义区间划分为数，因此可将自变量定义区间划分为3106等份。等份。又因为又因为221 3106 222，所以本例的二进制编，所以本例的二进制编码长度至少需要码长度至少需要22位，本例的编码过程实质上位，本例的编码过程实质上是将区间是将区间-1，2内对应的实数值转化为一个二内对应的实数值转化为一个二进制

8、串（进制串（b21b20b0）。）。第十三页，本课件共有97页几个术语几个术语 基因型：基因型：1000101110110101000111 表现型：表现型：0.637197 编码解码个体（染色体）基因第十四页，本课件共有97页初始种群初始种群 SGA采用随机方法生成若干个个采用随机方法生成若干个个体的集合，该集合称为初始种群。初体的集合，该集合称为初始种群。初始种群中个体的数量称为种群规模。始种群中个体的数量称为种群规模。第十五页，本课件共有97页 适应度函数适应度函数 遗传算法对一个个体（解）的好坏用遗传算法对一个个体（解）的好坏用适应度函数值来评价，适应度函数值越大，适应度函数值来评价，

9、适应度函数值越大，解的质量越好。适应度函数是遗传算法进解的质量越好。适应度函数是遗传算法进化过程的驱动力，也是进行自然选择的唯化过程的驱动力，也是进行自然选择的唯一标准，它的设计应结合求解问题本身的一标准，它的设计应结合求解问题本身的要求而定。要求而定。第十六页，本课件共有97页选择算子选择算子 遗传算法使用选择运算来实现对群体中的个体进行遗传算法使用选择运算来实现对群体中的个体进行遗传算法使用选择运算来实现对群体中的个体进行遗传算法使用选择运算来实现对群体中的个体进行优胜劣汰操作：适应度高的个体被遗传到下一代群体中优胜劣汰操作：适应度高的个体被遗传到下一代群体中优胜劣汰操作：适应度高的个体被

10、遗传到下一代群体中优胜劣汰操作：适应度高的个体被遗传到下一代群体中的概率大；适应度低的个体，被遗传到下一代群体中的的概率大；适应度低的个体，被遗传到下一代群体中的的概率大；适应度低的个体，被遗传到下一代群体中的的概率大；适应度低的个体，被遗传到下一代群体中的概率小。选择操作的任务就是按某种方法从父代群体中概率小。选择操作的任务就是按某种方法从父代群体中概率小。选择操作的任务就是按某种方法从父代群体中概率小。选择操作的任务就是按某种方法从父代群体中选取一些个体，遗传到下一代群体。选取一些个体，遗传到下一代群体。选取一些个体，遗传到下一代群体。选取一些个体，遗传到下一代群体。SGASGA中选择算子

11、采中选择算子采中选择算子采中选择算子采用轮盘赌选择方法。用轮盘赌选择方法。用轮盘赌选择方法。用轮盘赌选择方法。第十七页，本课件共有97页轮盘赌选择方法轮盘赌选择方法 轮盘赌选择又称比例选择算子，它的基本思想轮盘赌选择又称比例选择算子，它的基本思想是：各个个体被选中的概率与其适应度函数值大小是：各个个体被选中的概率与其适应度函数值大小成正比。设群体大小为成正比。设群体大小为n，个体，个体i 的适应度为的适应度为 Fi i，则，则个体个体i 被选中遗传到下一代群体的概率为：被选中遗传到下一代群体的概率为：第十八页，本课件共有97页轮盘赌选择方法的实现步骤轮盘赌选择方法的实现步骤（1 1 1 1）计

12、算群体中所有个体的适应度函数值（需要解码）；计算群体中所有个体的适应度函数值（需要解码）；计算群体中所有个体的适应度函数值（需要解码）；计算群体中所有个体的适应度函数值（需要解码）；（2 2 2 2）利用比例选择算子的公式，计算每个个体被选中利用比例选择算子的公式，计算每个个体被选中利用比例选择算子的公式，计算每个个体被选中利用比例选择算子的公式，计算每个个体被选中遗传到下一代群体的概率；遗传到下一代群体的概率；遗传到下一代群体的概率；遗传到下一代群体的概率；（3 3 3 3）采用模拟赌盘操作（即生成采用模拟赌盘操作（即生成采用模拟赌盘操作（即生成采用模拟赌盘操作（即生成0 0 0 0到到到到

13、1 1 1 1之间的随机数之间的随机数之间的随机数之间的随机数与每个个体遗传到下一代群体的概率进行匹配）来与每个个体遗传到下一代群体的概率进行匹配）来与每个个体遗传到下一代群体的概率进行匹配）来与每个个体遗传到下一代群体的概率进行匹配）来确定各个个体是否遗传到下一代群体中。确定各个个体是否遗传到下一代群体中。确定各个个体是否遗传到下一代群体中。确定各个个体是否遗传到下一代群体中。第十九页，本课件共有97页交叉算子交叉算子 所谓交叉运算，是指对两个相互配对的染色体依据所谓交叉运算，是指对两个相互配对的染色体依据所谓交叉运算，是指对两个相互配对的染色体依据所谓交叉运算，是指对两个相互配对的染色体依

14、据交叉概率交叉概率交叉概率交叉概率 P Pc c 按某种方式相互交换其部分基因，从按某种方式相互交换其部分基因，从而形成两个新的个体。交叉运算是遗传算法区别而形成两个新的个体。交叉运算是遗传算法区别于其他进化算法的重要特征，它在遗传算法中起于其他进化算法的重要特征，它在遗传算法中起关键作用，是产生新个体的主要方法。关键作用，是产生新个体的主要方法。SGA中交中交叉算子采用单点交叉算子。叉算子采用单点交叉算子。第二十页，本课件共有97页单点交叉运算单点交叉运算 交叉前：交叉前：00000|0111000000001000011100|00000111111000101交叉后：交叉后：00000|

15、0000011111100010111100|01110000000010000交叉点第二十一页，本课件共有97页突变算子突变算子 所谓突变运算，是指依据突变概率所谓突变运算，是指依据突变概率 Pm m 将个将个将个将个体编码串中的某些基因值用其它基因值来替换，从体编码串中的某些基因值用其它基因值来替换，从体编码串中的某些基因值用其它基因值来替换，从体编码串中的某些基因值用其它基因值来替换，从而形成一个新的个体。遗传算法中的突变运算是产而形成一个新的个体。遗传算法中的突变运算是产而形成一个新的个体。遗传算法中的突变运算是产而形成一个新的个体。遗传算法中的突变运算是产生新个体的辅助方法，它决定了

16、遗传算法的局部搜生新个体的辅助方法，它决定了遗传算法的局部搜生新个体的辅助方法，它决定了遗传算法的局部搜生新个体的辅助方法，它决定了遗传算法的局部搜索能力，同时保持种群的多样性。交叉运算和突变索能力，同时保持种群的多样性。交叉运算和突变索能力，同时保持种群的多样性。交叉运算和突变索能力，同时保持种群的多样性。交叉运算和突变运算的相互配合，共同完成对搜索空间的全局搜索运算的相互配合，共同完成对搜索空间的全局搜索运算的相互配合，共同完成对搜索空间的全局搜索运算的相互配合，共同完成对搜索空间的全局搜索和局部搜索。和局部搜索。和局部搜索。和局部搜索。SGA SGA中突变算子采用基本位突变算子。中突变算

17、子采用基本位突变算子。中突变算子采用基本位突变算子。中突变算子采用基本位突变算子。第二十二页，本课件共有97页基本位突变算子基本位突变算子 基本位突变算子是指对基本位突变算子是指对基本位突变算子是指对基本位突变算子是指对个体编码串个体编码串个体编码串个体编码串随机指随机指随机指随机指定的某一位定的某一位定的某一位定的某一位或或或或某几位基因某几位基因某几位基因某几位基因作突变运算。对于基作突变运算。对于基作突变运算。对于基作突变运算。对于基本遗传算法中用二进制编码符号串所表示的个本遗传算法中用二进制编码符号串所表示的个本遗传算法中用二进制编码符号串所表示的个本遗传算法中用二进制编码符号串所表示

18、的个体，若需要进行突变操作的体，若需要进行突变操作的体，若需要进行突变操作的体，若需要进行突变操作的某一基因某一基因某一基因某一基因座上的原座上的原有基因值为有基因值为0，则突变操作将其变为，则突变操作将其变为1；反之，；反之，若原有基因值为若原有基因值为1，则突变操作将其变为，则突变操作将其变为0。第二十三页，本课件共有97页基本位突变算子的执行过程基本位突变算子的执行过程 突变前：突变前：000001110000000010000突变后：突变后：000001110001000010000突变点第二十四页，本课件共有97页运行参数运行参数（1）M ：种群规模种群规模（2）T ：遗传运算的终止

19、进化代数遗传运算的终止进化代数（3）Pc ：交叉概率交叉概率（4）Pm：突变概率突变概率 第二十五页，本课件共有97页SGA的框图的框图 产生初始群体产生初始群体是否满足停止准则是否满足停止准则是是输出结果并结束输出结果并结束计算个体适应度值计算个体适应度值比例选择运算比例选择运算单点交叉运算单点交叉运算基本位突变运算基本位突变运算否否产生新一代群体产生新一代群体执行M/2次返回返回第二十六页，本课件共有97页3、遗传算法的特点、遗传算法的特点（1）群体搜索，易于并行化处理；）群体搜索，易于并行化处理；（2）不是盲目穷举，而是启发式搜索；）不是盲目穷举，而是启发式搜索；（3）适应度函数不受连续

20、、可微等条件的约）适应度函数不受连续、可微等条件的约束，适用范围很广。束，适用范围很广。返回返回第二十七页，本课件共有97页二、遗传算法原理1 1、遗传算法的数学基础遗传算法的数学基础 2 2、遗传算法的收敛性分析遗传算法的收敛性分析 3 3、遗传算法的改进遗传算法的改进 返回返回第二十八页，本课件共有97页1 1、遗传算法的数学基础遗传算法的数学基础（1 1）模式定理）模式定理 （2 2）积木块假设）积木块假设 返回返回第二十九页，本课件共有97页模式模式 模式是指种群个体基因串中的相似样模式是指种群个体基因串中的相似样板，它用来描述基因串中某些特征位相同板，它用来描述基因串中某些特征位相同

21、的结构。在二进制编码中，模式是基于三的结构。在二进制编码中，模式是基于三个字符集个字符集(0,1,*)的字符串，符号的字符串，符号*代表任意代表任意字符，即字符，即 0 或者或者 1。模式示例：模式示例：10*1第三十页，本课件共有97页两个定义两个定义定义定义1：模式：模式 H 中确定位置的个数称为模式中确定位置的个数称为模式 H 的阶，记作的阶，记作O(H)。例如。例如O(10*1)=3。定义定义2：模式：模式 H 中第一个确定位置和最后一个中第一个确定位置和最后一个确定位置之间的距离称为模式确定位置之间的距离称为模式 H 的定义距，的定义距，记作记作(H)。例如。例如(10*1)=4。第

22、三十一页，本课件共有97页模式的阶和定义距的含义模式的阶和定义距的含义 模式阶用来反映不同模式间确定性模式阶用来反映不同模式间确定性的差异，模式阶数越高，模式的确定性的差异，模式阶数越高，模式的确定性就越高，所匹配的样本数就越少。在遗就越高，所匹配的样本数就越少。在遗传操作中，即使阶数相同的模式，也会传操作中，即使阶数相同的模式，也会有不同的性质，而模式的定义距就反映有不同的性质，而模式的定义距就反映了这种性质的差异。了这种性质的差异。第三十二页，本课件共有97页模式定理模式定理 模式定理：具有低阶、短定义距以及平模式定理：具有低阶、短定义距以及平均适应度高于种群平均适应度的模式在子代均适应度

23、高于种群平均适应度的模式在子代中呈指数增长。中呈指数增长。模式定理保证了较优的模式（遗传算法模式定理保证了较优的模式（遗传算法的较优解）的数目呈指数增长，为解释遗传的较优解）的数目呈指数增长，为解释遗传算法机理提供了数学基础。算法机理提供了数学基础。第三十三页，本课件共有97页模式定理模式定理 从模式定理可看出，有高平均适应度、短定义距、从模式定理可看出，有高平均适应度、短定义距、从模式定理可看出，有高平均适应度、短定义距、从模式定理可看出，有高平均适应度、短定义距、低阶的模式，在连续的后代里获得至少以指数增长的低阶的模式，在连续的后代里获得至少以指数增长的低阶的模式，在连续的后代里获得至少以

24、指数增长的低阶的模式，在连续的后代里获得至少以指数增长的串数目，这主要是因为选择使最好的模式有更多的复串数目，这主要是因为选择使最好的模式有更多的复串数目，这主要是因为选择使最好的模式有更多的复串数目，这主要是因为选择使最好的模式有更多的复制，交叉算子不容易破坏高频率出现的、短定义长的制，交叉算子不容易破坏高频率出现的、短定义长的制，交叉算子不容易破坏高频率出现的、短定义长的制，交叉算子不容易破坏高频率出现的、短定义长的模式，而一般突变概率又相当小，因而它对这些重要模式，而一般突变概率又相当小，因而它对这些重要模式，而一般突变概率又相当小，因而它对这些重要模式，而一般突变概率又相当小，因而它对

25、这些重要的模式几乎没有影响。的模式几乎没有影响。的模式几乎没有影响。的模式几乎没有影响。返回返回第三十四页，本课件共有97页积木块假设积木块假设 积木块假设：遗传算法通过短定义距、低阶以及积木块假设：遗传算法通过短定义距、低阶以及积木块假设：遗传算法通过短定义距、低阶以及积木块假设：遗传算法通过短定义距、低阶以及高平均适应度的模式（积木块），在遗传操作下相互高平均适应度的模式（积木块），在遗传操作下相互高平均适应度的模式（积木块），在遗传操作下相互高平均适应度的模式（积木块），在遗传操作下相互结合，最终接近全局最优解。结合，最终接近全局最优解。结合，最终接近全局最优解。结合，最终接近全局最优解

26、。模式定理保证了较优模式的样本数呈指数增长，从模式定理保证了较优模式的样本数呈指数增长，从模式定理保证了较优模式的样本数呈指数增长，从模式定理保证了较优模式的样本数呈指数增长，从而使遗传算法找到全局最优解的可能性存在；而积木块而使遗传算法找到全局最优解的可能性存在；而积木块而使遗传算法找到全局最优解的可能性存在；而积木块而使遗传算法找到全局最优解的可能性存在；而积木块假设则指出了在遗传算子的作用下，能生成全局最优解。假设则指出了在遗传算子的作用下，能生成全局最优解。假设则指出了在遗传算子的作用下，能生成全局最优解。假设则指出了在遗传算子的作用下，能生成全局最优解。返回返回第三十五页，本课件共有

27、97页2 2、遗传算法的收敛性分析遗传算法的收敛性分析 遗传算法要实现全局收敛，首先要求任意遗传算法要实现全局收敛，首先要求任意初始种群经有限步都能到达全局最优解，其次初始种群经有限步都能到达全局最优解，其次算法必须由保优操作来防止最优解的遗失。与算法必须由保优操作来防止最优解的遗失。与算法收敛性有关的因素主要包括种群规模、选算法收敛性有关的因素主要包括种群规模、选择操作、交叉概率和突变概率。择操作、交叉概率和突变概率。第三十六页，本课件共有97页种群规模对种群规模对收敛性的影响收敛性的影响 通常，种群太小则不能提供足够的采样通常，种群太小则不能提供足够的采样点，以致算法性能很差；种群太大，尽

28、管可点，以致算法性能很差；种群太大，尽管可以增加优化信息，阻止早熟收敛的发生，但以增加优化信息，阻止早熟收敛的发生，但无疑会增加计算量，造成收敛时间太长，表无疑会增加计算量，造成收敛时间太长，表现为收敛速度缓慢。现为收敛速度缓慢。第三十七页，本课件共有97页选择操作对选择操作对收敛性的影响收敛性的影响 选择操作使高适应度个体能够以更大的概选择操作使高适应度个体能够以更大的概选择操作使高适应度个体能够以更大的概选择操作使高适应度个体能够以更大的概率生存，从而提高了遗传算法的全局收敛性。率生存，从而提高了遗传算法的全局收敛性。率生存，从而提高了遗传算法的全局收敛性。率生存，从而提高了遗传算法的全局

29、收敛性。如果在算法中采用最优保存策略，即将父代群如果在算法中采用最优保存策略，即将父代群如果在算法中采用最优保存策略，即将父代群如果在算法中采用最优保存策略，即将父代群体中最佳个体保留下来，不参加交叉和突变操体中最佳个体保留下来，不参加交叉和突变操体中最佳个体保留下来，不参加交叉和突变操体中最佳个体保留下来，不参加交叉和突变操作，使之直接进入下一代，最终可使遗传算法作，使之直接进入下一代，最终可使遗传算法作，使之直接进入下一代，最终可使遗传算法作，使之直接进入下一代，最终可使遗传算法以概率以概率以概率以概率1 1收敛于全局最优解。收敛于全局最优解。收敛于全局最优解。收敛于全局最优解。第三十八页

30、，本课件共有97页交叉概率对交叉概率对收敛性的影响收敛性的影响 交叉操作用于个体对，产生新的个体，实交叉操作用于个体对，产生新的个体，实质上是在解空间中进行有效搜索。交叉概率太质上是在解空间中进行有效搜索。交叉概率太大时，种群中个体更新很快，会造成高适应度大时，种群中个体更新很快，会造成高适应度值的个体很快被破坏掉；概率太小时，交叉操值的个体很快被破坏掉；概率太小时，交叉操作很少进行，从而会使搜索停滞不前，造成算作很少进行，从而会使搜索停滞不前，造成算法的不收敛。法的不收敛。第三十九页，本课件共有97页突变概率对突变概率对收敛性的影响收敛性的影响 突变操作是对种群模式的扰动，有利于增突变操作是

31、对种群模式的扰动，有利于增加种群的多样性加种群的多样性。但是，突变概率太小则很难。但是，突变概率太小则很难产生新模式，突变概率太大则会使遗传算法成产生新模式，突变概率太大则会使遗传算法成为随机搜索算法。为随机搜索算法。第四十页，本课件共有97页遗传算法的本质遗传算法的本质 遗传算法本质上是对染色体模式所进行的一遗传算法本质上是对染色体模式所进行的一系列运算，即通过选择算子将当前种群中的优良模系列运算，即通过选择算子将当前种群中的优良模式遗传到下一代种群中，利用交叉算子进行模式重式遗传到下一代种群中，利用交叉算子进行模式重组，利用突变算子进行模式突变。通过这些遗传操组，利用突变算子进行模式突变。

32、通过这些遗传操作，模式逐步向较好的方向进化，最终得到问题的作，模式逐步向较好的方向进化，最终得到问题的最优解。最优解。返回返回第四十一页，本课件共有97页3 3、遗传算法的改进遗传算法的改进 遗传欺骗问题：在遗传算法进化过遗传欺骗问题：在遗传算法进化过程中，有时会产生一些超常的个体，这程中，有时会产生一些超常的个体，这些个体因竞争力太突出而控制了选择运些个体因竞争力太突出而控制了选择运算过程，从而影响算法的全局优化性能，算过程，从而影响算法的全局优化性能，导致算法获得某个局部最优解。导致算法获得某个局部最优解。第四十二页，本课件共有97页遗传算法的改进途径遗传算法的改进途径（1）对编码方式的改

33、进）对编码方式的改进（2）对遗传算子）对遗传算子 的改进的改进（3）对控制参数的改进）对控制参数的改进（4）对执行策略的改进）对执行策略的改进 第四十三页，本课件共有97页对编码方式的改进对编码方式的改进 二二进进制制编编码码优优点点在在于于编编码码、解解码码操操作作简简单单，交交叉叉、突突变变等等操操作作便便于于实实现现，缺缺点点在在于于精精度度要要求求较较高高时时，个个体体编编码码串串较较长长，使使算算法法的的搜搜索索空空间间急急剧剧扩扩大大，遗遗传传算算法法的的性性能能降降低低。格格雷雷编编码码克克服服了了二二进进制制编编码码的的不不连连续续问问题题，浮点数编码改善了遗传算法的计算复杂性

34、浮点数编码改善了遗传算法的计算复杂性。第四十四页，本课件共有97页对遗传算子对遗传算子 的改进的改进排序选择排序选择 均匀交叉均匀交叉 逆序突变逆序突变（1）对群体中的所有个体按其适应度大小进行降序排序；（2）根据具体求解问题，设计一个概率分配表，将各个概率值按上述排列次序分配给各个个体；（3）以各个个体所分配到的概率值作为其遗传到下一代的概率，基于这些概率用赌盘选择法来产生下一代群体。第四十五页，本课件共有97页对遗传算子对遗传算子 的改进的改进排序选择排序选择 均匀交叉均匀交叉 逆序突变逆序突变（1）随机产生一个与个体编码长度相同的二进制屏蔽字P=W1W2Wn；（2）按下列规则从A、B两个

35、父代个体中产生两个新个体X、Y：若Wi=0，则X的第i个基因继承A的对应基因，Y的第i个基因继承B的对应基因；若Wi=1，则A、B的第i个基因相互交换，从而生成X、Y的第i个基因。第四十六页，本课件共有97页对遗传算子对遗传算子 的改进的改进排序选择排序选择 均匀交叉均匀交叉 逆序突变逆序突变突变前：3 4 8|7 9 6 5|2 1突变后：3 4 8|5 6 9 7|2 1第四十七页，本课件共有97页对控制参数的改进对控制参数的改进 Schaffer建议的最优参数范围是：建议的最优参数范围是：M=20-100，T=100-500，Pc=0.4-0.9，Pm=0.001-0.01。第四十八页，

36、本课件共有97页对控制参数的改进对控制参数的改进 Srinvivas等人提出自适应遗传算法，即等人提出自适应遗传算法，即PC和和和和P Pmm能够随适应度自动改变，当种群的各个个体适应能够随适应度自动改变，当种群的各个个体适应能够随适应度自动改变，当种群的各个个体适应能够随适应度自动改变，当种群的各个个体适应度趋于一致或趋于局部最优时，使二者增加，而当度趋于一致或趋于局部最优时，使二者增加，而当度趋于一致或趋于局部最优时，使二者增加，而当度趋于一致或趋于局部最优时，使二者增加，而当种群适应度比较分散时，使二者减小，同时对适应种群适应度比较分散时，使二者减小，同时对适应种群适应度比较分散时，使二

37、者减小，同时对适应种群适应度比较分散时，使二者减小，同时对适应值高于群体平均适应值的个体，采用较低的值高于群体平均适应值的个体，采用较低的值高于群体平均适应值的个体，采用较低的值高于群体平均适应值的个体，采用较低的P PC C和和和和P Pm，使性能优良的个体进入下一代，而低于平均适应，使性能优良的个体进入下一代，而低于平均适应，使性能优良的个体进入下一代，而低于平均适应，使性能优良的个体进入下一代，而低于平均适应值的个体，采用较高的值的个体，采用较高的值的个体，采用较高的值的个体，采用较高的P PC C和和和和P Pmm，使性能较差的个体被，使性能较差的个体被，使性能较差的个体被，使性能较差

38、的个体被淘汰淘汰淘汰淘汰 。第四十九页，本课件共有97页对执行策略的改进对执行策略的改进混合遗传算法混合遗传算法免疫遗传算法免疫遗传算法小生境遗传算法小生境遗传算法单亲遗传算法单亲遗传算法并行遗传算法并行遗传算法返回返回第五十页，本课件共有97页三、遗传算法的应用1 1、遗传算法的应用领域遗传算法的应用领域 2 2、遗传算法的应用示例遗传算法的应用示例 3 3、我的研究、我的研究第五十一页，本课件共有97页1 1、遗传算法的应用领域遗传算法的应用领域（1）组合优化）组合优化（2 2）函数优化）函数优化）函数优化）函数优化 （3 3）智能控制）智能控制）智能控制）智能控制 （4）图像处理）图像处

39、理（5 5）机器学习）机器学习）机器学习）机器学习（6）人工生命）人工生命 返回返回第五十二页，本课件共有97页遗传算法应用于组合优化遗传算法应用于组合优化组合优化是指在给定约束条件下组合优化是指在给定约束条件下组合优化是指在给定约束条件下组合优化是指在给定约束条件下,求解目标函数的最优值。求解目标函数的最优值。求解目标函数的最优值。求解目标函数的最优值。随着问题规模的增大，随着问题规模的增大，随着问题规模的增大，随着问题规模的增大，组合优化问题的搜索空间也急剧扩大，有时在计算机上用枚举法很难甚至不可能组合优化问题的搜索空间也急剧扩大，有时在计算机上用枚举法很难甚至不可能组合优化问题的搜索空间

40、也急剧扩大，有时在计算机上用枚举法很难甚至不可能组合优化问题的搜索空间也急剧扩大，有时在计算机上用枚举法很难甚至不可能求出其最优解。实践证明，遗传算法已经在求解求出其最优解。实践证明，遗传算法已经在求解求出其最优解。实践证明，遗传算法已经在求解求出其最优解。实践证明，遗传算法已经在求解旅行商问题、背包问题、装箱问旅行商问题、背包问题、装箱问旅行商问题、背包问题、装箱问旅行商问题、背包问题、装箱问题、布局优化、网络路由题、布局优化、网络路由题、布局优化、网络路由题、布局优化、网络路由等具有等具有等具有等具有NPNP难度的组合优化问题上取得了成功的难度的组合优化问题上取得了成功的难度的组合优化问题

41、上取得了成功的难度的组合优化问题上取得了成功的应用。应用。应用。应用。如旅行商问题，我们给定一组如旅行商问题，我们给定一组如旅行商问题，我们给定一组如旅行商问题，我们给定一组n n个城市和他们两两之间的直达距个城市和他们两两之间的直达距个城市和他们两两之间的直达距个城市和他们两两之间的直达距离离离离，通过遗传算法我们可以寻找一条，通过遗传算法我们可以寻找一条，通过遗传算法我们可以寻找一条，通过遗传算法我们可以寻找一条闭合的旅程，使得每个城市刚好经闭合的旅程，使得每个城市刚好经闭合的旅程，使得每个城市刚好经闭合的旅程，使得每个城市刚好经过一次且总的履行距离最短过一次且总的履行距离最短过一次且总的

42、履行距离最短过一次且总的履行距离最短。再如。再如。再如。再如车间作业调度问题车间作业调度问题车间作业调度问题车间作业调度问题，车间作业是指利用车间作业是指利用车间作业是指利用车间作业是指利用车间资源对某一对象进行生产的过程车间资源对某一对象进行生产的过程车间资源对某一对象进行生产的过程车间资源对某一对象进行生产的过程，作业调度实际上就是对车间作业进行作业调度实际上就是对车间作业进行作业调度实际上就是对车间作业进行作业调度实际上就是对车间作业进行有效排序，使某个目标函数最小有效排序，使某个目标函数最小有效排序，使某个目标函数最小有效排序，使某个目标函数最小。比方一台机床有多个工具，加工多种工件，

43、。比方一台机床有多个工具，加工多种工件，。比方一台机床有多个工具，加工多种工件，。比方一台机床有多个工具，加工多种工件，各工件有确定的加工期限约束，需要制定一个月的加工计划保证完成所有的各工件有确定的加工期限约束，需要制定一个月的加工计划保证完成所有的各工件有确定的加工期限约束，需要制定一个月的加工计划保证完成所有的各工件有确定的加工期限约束，需要制定一个月的加工计划保证完成所有的加工任务。由于加工任务。由于加工任务。由于加工任务。由于JSPJSP具有离散、动态、多变量耦合等属性，应用遗传算法具具有离散、动态、多变量耦合等属性，应用遗传算法具具有离散、动态、多变量耦合等属性，应用遗传算法具具有

44、离散、动态、多变量耦合等属性，应用遗传算法具有一定难度，主要体现在遗传编码方法上。有一定难度，主要体现在遗传编码方法上。有一定难度，主要体现在遗传编码方法上。有一定难度，主要体现在遗传编码方法上。返回返回第五十三页，本课件共有97页函数优化函数优化工程上经常会遇到在多准则或多设计目标下设计和决策的问题，工程上经常会遇到在多准则或多设计目标下设计和决策的问题，工程上经常会遇到在多准则或多设计目标下设计和决策的问题，工程上经常会遇到在多准则或多设计目标下设计和决策的问题，如果这些目标是相背的，需要找到满足这些目标的最佳设计如果这些目标是相背的，需要找到满足这些目标的最佳设计如果这些目标是相背的，需

45、要找到满足这些目标的最佳设计如果这些目标是相背的，需要找到满足这些目标的最佳设计方案。通常的做法是根据某有效函数将多目标合成单一目标方案。通常的做法是根据某有效函数将多目标合成单一目标方案。通常的做法是根据某有效函数将多目标合成单一目标方案。通常的做法是根据某有效函数将多目标合成单一目标来进行优化。但大多数情况下，在优化之前这种效用函数是来进行优化。但大多数情况下，在优化之前这种效用函数是来进行优化。但大多数情况下，在优化之前这种效用函数是来进行优化。但大多数情况下，在优化之前这种效用函数是难以确切知道的。法国经济学难以确切知道的。法国经济学难以确切知道的。法国经济学难以确切知道的。法国经济学

46、V.Pareto(1848-1923)V.Pareto(1848-1923)最早研究最早研究最早研究最早研究经济领域内的多目标优化问题，他的理论称为经济领域内的多目标优化问题，他的理论称为经济领域内的多目标优化问题，他的理论称为经济领域内的多目标优化问题，他的理论称为ParetoPareto最优化最优化最优化最优化理论。理论。理论。理论。J.HornJ.Horn和和和和N.NafpliotisN.Nafpliotis提出了关于用遗传算法解决多目提出了关于用遗传算法解决多目提出了关于用遗传算法解决多目提出了关于用遗传算法解决多目标问题的基本算法思想，遗传算法界称为标问题的基本算法思想，遗传算法界

47、称为标问题的基本算法思想，遗传算法界称为标问题的基本算法思想，遗传算法界称为NPGANPGA。返回返回第五十四页，本课件共有97页智能控制智能控制许多许多许多许多控制领域控制领域控制领域控制领域问题，当考虑到系统优化、自适应、自组织和自学习等方面的要求问题，当考虑到系统优化、自适应、自组织和自学习等方面的要求问题，当考虑到系统优化、自适应、自组织和自学习等方面的要求问题，当考虑到系统优化、自适应、自组织和自学习等方面的要求时，一般存在许多常规方法难以凑效的困难。例如，当有非连续评价函数、时，一般存在许多常规方法难以凑效的困难。例如，当有非连续评价函数、时，一般存在许多常规方法难以凑效的困难。例

48、如，当有非连续评价函数、时，一般存在许多常规方法难以凑效的困难。例如，当有非连续评价函数、缺少初始信息、模型参数和结构或控制过程中的随机性、不确定性等复杂因缺少初始信息、模型参数和结构或控制过程中的随机性、不确定性等复杂因缺少初始信息、模型参数和结构或控制过程中的随机性、不确定性等复杂因缺少初始信息、模型参数和结构或控制过程中的随机性、不确定性等复杂因素出现时，现有的控制理论和方法往往因需要求导信息、对初始条件的敏感素出现时，现有的控制理论和方法往往因需要求导信息、对初始条件的敏感素出现时，现有的控制理论和方法往往因需要求导信息、对初始条件的敏感素出现时，现有的控制理论和方法往往因需要求导信息

49、、对初始条件的敏感性、对高品质的领域知识依赖性而难以得到很好的应用。性、对高品质的领域知识依赖性而难以得到很好的应用。性、对高品质的领域知识依赖性而难以得到很好的应用。性、对高品质的领域知识依赖性而难以得到很好的应用。19711971年年年年K.S.FuK.S.Fu从研从研从研从研究自学习控制系统入手，将智能控制概括为自动控制与人工智能的交集；究自学习控制系统入手，将智能控制概括为自动控制与人工智能的交集；究自学习控制系统入手，将智能控制概括为自动控制与人工智能的交集；究自学习控制系统入手，将智能控制概括为自动控制与人工智能的交集；19771977年，年，年，年，SaridisSaridis以

50、智能机器人的控制为主要研究背景，从研究机器智能的角以智能机器人的控制为主要研究背景，从研究机器智能的角以智能机器人的控制为主要研究背景，从研究机器智能的角以智能机器人的控制为主要研究背景，从研究机器智能的角度提出了智能控制是自动控制、人工智能及运筹学的交集，并提出了分级递度提出了智能控制是自动控制、人工智能及运筹学的交集，并提出了分级递度提出了智能控制是自动控制、人工智能及运筹学的交集，并提出了分级递度提出了智能控制是自动控制、人工智能及运筹学的交集，并提出了分级递阶智能控制的结构和方法；阶智能控制的结构和方法；阶智能控制的结构和方法；阶智能控制的结构和方法；AstromAstrom提出的专家