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

关于遗传算法原理与关于遗传算法原理与应用应用第一页，本课件共有65页报告提纲报告提纲一、遗传算法概述一、遗传算法概述 二、遗传算法原理二、遗传算法原理三、遗传算法的应用三、遗传算法的应用第二页，本课件共有65页一、遗传算法概述1 1、智能优化算法智能优化算法 2 2、基本遗传算法基本遗传算法 3 3、遗传算法的特点遗传算法的特点 第三页，本课件共有65页1 1、智能优化算法、智能优化算法 智能优化算法又称为现代启发式算法，智能优化算法又称为现代启发式算法，是一种具有全局优化性能、通用性强、且是一种具有全局优化性能、通用性强、且适合于并行处理的算法。这种算法一般具适合于并行处理的算法。这种算法一般具有严密的理论依据，而不是单纯凭借专家有严密的理论依据，而不是单纯凭借专家经验，理论上可以在一定的时间内找到最经验，理论上可以在一定的时间内找到最优解或近似最优解。优解或近似最优解。第四页，本课件共有65页常用的智能优化算法常用的智能优化算法（1 1）遗传算法遗传算法遗传算法遗传算法 （Genetic AlgorithmGenetic Algorithm，简称简称简称简称GA）（2 2）模拟退火算法模拟退火算法模拟退火算法模拟退火算法（Simulated Annealing，简称简称SA）（3 3）禁忌搜索算法禁忌搜索算法（Tabu SearchTabu Search，简称简称TS）第五页，本课件共有65页智能优化算法的特点智能优化算法的特点 它们的共同特点：都是从任一解出发，它们的共同特点：都是从任一解出发，按照某种机制，以一定的概率在整个求解按照某种机制，以一定的概率在整个求解空间中探索最优解。由于它们可以把搜索空间中探索最优解。由于它们可以把搜索空间扩展到整个问题空间，因而具有全局空间扩展到整个问题空间，因而具有全局优化性能。优化性能。第六页，本课件共有65页遗传算法起源遗传算法起源 遗传算法是由美国的遗传算法是由美国的J.Holland教授于教授于1975年在他的专著年在他的专著自然界和人工系统的适自然界和人工系统的适应性应性中首先提出的，它是一类借鉴生物界中首先提出的，它是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法自然选择和自然遗传机制的随机化搜索算法。第七页，本课件共有65页遗传算法的搜索机制遗传算法的搜索机制 遗传算法模拟自然选择和自然遗传过程遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子从解群中选取较优的个体，利用遗传算子(选选择、交叉和变异择、交叉和变异)对这些个体进行组合，产对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。足某种收敛指标为止。第八页，本课件共有65页2 2、基本遗传算法、基本遗传算法 基本遗传算法（基本遗传算法（Simple Genetic Algorithms，简称，简称SGA，又称简单遗传算法，又称简单遗传算法或标准遗传算法），是由或标准遗传算法），是由Goldberg总结出的总结出的一种最基本的遗传算法，其遗传进化操作过程一种最基本的遗传算法，其遗传进化操作过程简单，容易理解，是其它一些遗传算法的雏形简单，容易理解，是其它一些遗传算法的雏形和基础。和基础。第九页，本课件共有65页基本遗传算法的组成基本遗传算法的组成 （1 1）编码（产生初始种群）编码（产生初始种群）（2 2）适应度函数）适应度函数（3 3）遗传算子（选择、交叉、变异）遗传算子（选择、交叉、变异）（4 4）运行参数）运行参数第十页，本课件共有65页 编码编码 GA是通过某种编码机制把对象抽是通过某种编码机制把对象抽象为由特定符号按一定顺序排成的串。象为由特定符号按一定顺序排成的串。正如研究生物遗传是从染色体着手，正如研究生物遗传是从染色体着手，而染色体则是由基因排成的串。而染色体则是由基因排成的串。SGA使用二进制串进行编码。使用二进制串进行编码。第十一页，本课件共有65页函数优化示例函数优化示例 求下列一元函数的最大值：求下列一元函数的最大值：x-1,2 x-1,2 ，求解结果精确到，求解结果精确到6 6位小数。位小数。第十二页，本课件共有65页SGA对于本例的编码对于本例的编码 由于区间长度为由于区间长度为3，求解结果精确到，求解结果精确到6位小数，位小数，因此可将自变量定义区间划分为因此可将自变量定义区间划分为3106等份。又因等份。又因为为221 3106 222，所以本例的二进制编码长，所以本例的二进制编码长度至少需要度至少需要22位，本例的编码过程实质上是将位，本例的编码过程实质上是将区间区间-1，2内对应的实数值转化为一个二进制串内对应的实数值转化为一个二进制串（b21b20b0）。）。第十三页，本课件共有65页几个术语几个术语 基因型：基因型：1000101110110101000111 表现型：表现型：0.637197 编码解码个体（染色体）基因第十四页，本课件共有65页初始种群初始种群 SGA采用随机方法生成若干个个采用随机方法生成若干个个体的集合，该集合称为初始种群。初体的集合，该集合称为初始种群。初始种群中个体的数量称为种群规模。始种群中个体的数量称为种群规模。第十五页，本课件共有65页 适应度函数适应度函数 遗传算法对一个个体（解）的好坏用适遗传算法对一个个体（解）的好坏用适应度函数值来评价，适应度函数值越大，解应度函数值来评价，适应度函数值越大，解的质量越好。适应度函数是遗传算法进化过的质量越好。适应度函数是遗传算法进化过程的驱动力，也是进行自然选择的唯一标准，程的驱动力，也是进行自然选择的唯一标准，它的设计应结合求解问题本身的要求而定。它的设计应结合求解问题本身的要求而定。第十六页，本课件共有65页选择算子选择算子 遗传算法使用选择运算来实现对群体中的个体遗传算法使用选择运算来实现对群体中的个体进行优胜劣汰操作：适应度高的个体被遗传到下一进行优胜劣汰操作：适应度高的个体被遗传到下一代群体中的概率大；适应度低的个体，被遗传到下代群体中的概率大；适应度低的个体，被遗传到下一代群体中的概率小。选择操作的任务就是按某种一代群体中的概率小。选择操作的任务就是按某种方法从父代群体中选取一些个体，遗传到下一代群方法从父代群体中选取一些个体，遗传到下一代群体。体。SGA中选择算子采用轮盘赌选择方法。中选择算子采用轮盘赌选择方法。中选择算子采用轮盘赌选择方法。中选择算子采用轮盘赌选择方法。第十七页，本课件共有65页轮盘赌选择方法轮盘赌选择方法 轮盘赌选择又称比例选择算子，它的基本思想是：轮盘赌选择又称比例选择算子，它的基本思想是：各个个体被选中的概率与其适应度函数值大小成正各个个体被选中的概率与其适应度函数值大小成正比。设群体大小为比。设群体大小为n，个体，个体，个体，个体i i 的适应度为的适应度为 F Fi，则个体，则个体，则个体，则个体i i 被被选中遗传到下一代群体的概率为：选中遗传到下一代群体的概率为：第十八页，本课件共有65页轮盘赌选择方法的实现步骤轮盘赌选择方法的实现步骤（1 1）计算群体中所有个体的适应度函数值（需要解码）；计算群体中所有个体的适应度函数值（需要解码）；计算群体中所有个体的适应度函数值（需要解码）；计算群体中所有个体的适应度函数值（需要解码）；（2 2）利用比例选择算子的公式，计算每个个体被选中遗利用比例选择算子的公式，计算每个个体被选中遗利用比例选择算子的公式，计算每个个体被选中遗利用比例选择算子的公式，计算每个个体被选中遗传到下一代群体的概率；传到下一代群体的概率；传到下一代群体的概率；传到下一代群体的概率；（3 3）采用模拟赌盘操作（即生成采用模拟赌盘操作（即生成0 0到到到到1 1之间的随机数之间的随机数之间的随机数之间的随机数与每个个体遗传到下一代群体的概率进行匹配）来确定与每个个体遗传到下一代群体的概率进行匹配）来确定与每个个体遗传到下一代群体的概率进行匹配）来确定与每个个体遗传到下一代群体的概率进行匹配）来确定各个个体是否遗传到下一代群体中。各个个体是否遗传到下一代群体中。各个个体是否遗传到下一代群体中。各个个体是否遗传到下一代群体中。第十九页，本课件共有65页交叉算子交叉算子 所谓交叉运算，是指对两个相互配对的染色所谓交叉运算，是指对两个相互配对的染色体依据交叉概率体依据交叉概率 P Pc 按某种方式相互交换其部分基按某种方式相互交换其部分基因，从而形成两个新的个体。交叉运算是遗传算法因，从而形成两个新的个体。交叉运算是遗传算法区别于其他进化算法的重要特征，它在遗传算法中区别于其他进化算法的重要特征，它在遗传算法中起关键作用，是产生新个体的主要方法。起关键作用，是产生新个体的主要方法。SGA中交中交叉算子采用单点交叉算子。叉算子采用单点交叉算子。第二十页，本课件共有65页单点交叉运算单点交叉运算 交叉前：交叉前：00000|0111000000001000011100|00000111111000101交叉后：交叉后：00000|0000011111100010111100|01110000000010000交叉点第二十一页，本课件共有65页变异算子变异算子 所谓变异运算，是指依据变异概率所谓变异运算，是指依据变异概率所谓变异运算，是指依据变异概率所谓变异运算，是指依据变异概率 Pm 将个体编将个体编码串中的某些基因值用其它基因值来替换，从而形码串中的某些基因值用其它基因值来替换，从而形成一个新的个体。遗传算法中的变异运算是产生新成一个新的个体。遗传算法中的变异运算是产生新个体的辅助方法，它决定了遗传算法的局部搜索能个体的辅助方法，它决定了遗传算法的局部搜索能力，同时保持种群的多样性。交叉运算和变异运算力，同时保持种群的多样性。交叉运算和变异运算的相互配合，共同完成对搜索空间的全局搜索和局的相互配合，共同完成对搜索空间的全局搜索和局部搜索。部搜索。SGASGA中变异算子采用基本位变异算子。中变异算子采用基本位变异算子。第二十二页，本课件共有65页基本位变异算子基本位变异算子 基本位变异算子是指对个体编码串随机基本位变异算子是指对个体编码串随机指定的某一位或某几位基因作变异运算。对指定的某一位或某几位基因作变异运算。对于基本遗传算法中用二进制编码符号串所表于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操作的某一基因示的个体，若需要进行变异操作的某一基因座上的原有基因值为座上的原有基因值为0 0，则变异操作将其变为，则变异操作将其变为1；反之，若原有基因值为；反之，若原有基因值为1，则变异操作将，则变异操作将其变为其变为0 0。第二十三页，本课件共有65页基本位变异算子的执行过程基本位变异算子的执行过程 变异前：变异前：000001110000000010000变异后：变异后：000001110001000010000变异点第二十四页，本课件共有65页运行参数运行参数（1）M ：种群规模种群规模（2）T ：遗传运算的终止进化代数遗传运算的终止进化代数（3）Pc ：交叉概率交叉概率（4）Pm：变异概率变异概率 第二十五页，本课件共有65页SGA的框图的框图 产生初始群体产生初始群体是否满足停止准则是否满足停止准则是是输出结果并结束输出结果并结束计算个体适应度值计算个体适应度值比例选择运算比例选择运算单点交叉运算单点交叉运算基本位变异运算基本位变异运算否否产生新一代群体产生新一代群体执行M/2次第二十六页，本课件共有65页3、遗传算法的特点、遗传算法的特点（1）群体搜索，易于并行化处理；）群体搜索，易于并行化处理；（2）不是盲目穷举，而是启发式搜索；）不是盲目穷举，而是启发式搜索；（3）适应度函数不受连续、可微等条件的约）适应度函数不受连续、可微等条件的约束，适用范围很广。束，适用范围很广。第二十七页，本课件共有65页二、遗传算法原理1 1、遗传算法的数学基础遗传算法的数学基础 2 2、遗传算法的收敛性分析遗传算法的收敛性分析 3 3、遗传算法的改进遗传算法的改进 第二十八页，本课件共有65页1 1、遗传算法的数学基础遗传算法的数学基础（1 1）模式定理）模式定理 （2 2）积木块假设）积木块假设 第二十九页，本课件共有65页模式模式 模式是指种群个体基因串中的相似样模式是指种群个体基因串中的相似样板，它用来描述基因串中某些特征位相同板，它用来描述基因串中某些特征位相同的结构。在二进制编码中，模式是基于三的结构。在二进制编码中，模式是基于三个字符集个字符集(0,1,*)的字符串，符号的字符串，符号*代表任意代表任意字符，即字符，即 0 或者或者 1。模式示例：模式示例：10*1第三十页，本课件共有65页两个定义两个定义定义定义1：模式：模式 H 中确定位置的个数称为模式中确定位置的个数称为模式 H 的阶，记作的阶，记作O(H)。例如。例如O(10*1)=3。定义定义2：模式：模式 H 中第一个确定位置和最后一个中第一个确定位置和最后一个确定位置之间的距离称为模式确定位置之间的距离称为模式 H 的定义距，的定义距，记作记作(H)。例如。例如(10*1)=4。第三十一页，本课件共有65页模式的阶和定义距的含义模式的阶和定义距的含义 模式阶用来反映不同模式间确定性的模式阶用来反映不同模式间确定性的差异，模式阶数越高，模式的确定性就越差异，模式阶数越高，模式的确定性就越高，所匹配的样本数就越少。在遗传操作高，所匹配的样本数就越少。在遗传操作中，即使阶数相同的模式，也会有不同的中，即使阶数相同的模式，也会有不同的性质，而模式的定义距就反映了这种性质性质，而模式的定义距就反映了这种性质的差异。的差异。第三十二页，本课件共有65页模式定理模式定理 模式定理：具有低阶、短定义距以及模式定理：具有低阶、短定义距以及平均适应度高于种群平均适应度的模式在平均适应度高于种群平均适应度的模式在子代中呈指数增长。子代中呈指数增长。模式定理保证了较优的模式（遗传算模式定理保证了较优的模式（遗传算法的较优解）的数目呈指数增长，为解释法的较优解）的数目呈指数增长，为解释遗传算法机理提供了数学基础。遗传算法机理提供了数学基础。第三十三页，本课件共有65页模式定理模式定理 从模式定理可看出，有高平均适应度、短定从模式定理可看出，有高平均适应度、短定义距、低阶的模式，在连续的后代里获得至少以指义距、低阶的模式，在连续的后代里获得至少以指数增长的串数目，这主要是因为选择使最好的模式数增长的串数目，这主要是因为选择使最好的模式有更多的复制，交叉算子不容易破坏高频率出现的、有更多的复制，交叉算子不容易破坏高频率出现的、短定义长的模式，而一般突变概率又相当小，因而短定义长的模式，而一般突变概率又相当小，因而它对这些重要的模式几乎没有影响。它对这些重要的模式几乎没有影响。第三十四页，本课件共有65页积木块假设积木块假设 积木块假设：遗传算法通过短定义距、低阶以积木块假设：遗传算法通过短定义距、低阶以及高平均适应度的模式（积木块），在遗传操作下及高平均适应度的模式（积木块），在遗传操作下相互结合，最终接近全局最优解。相互结合，最终接近全局最优解。模式定理保证了较优模式的样本数呈指数增长，从模式定理保证了较优模式的样本数呈指数增长，从模式定理保证了较优模式的样本数呈指数增长，从模式定理保证了较优模式的样本数呈指数增长，从而使遗传算法找到全局最优解的可能性存在；而积木块而使遗传算法找到全局最优解的可能性存在；而积木块而使遗传算法找到全局最优解的可能性存在；而积木块而使遗传算法找到全局最优解的可能性存在；而积木块假设则指出了在遗传算子的作用下，能生成全局最优解。假设则指出了在遗传算子的作用下，能生成全局最优解。假设则指出了在遗传算子的作用下，能生成全局最优解。假设则指出了在遗传算子的作用下，能生成全局最优解。第三十五页，本课件共有65页2 2、遗传算法的收敛性分析遗传算法的收敛性分析 遗传算法要实现全局收敛，首先要求任遗传算法要实现全局收敛，首先要求任意初始种群经有限步都能到达全局最优解，意初始种群经有限步都能到达全局最优解，其次算法必须由保优操作来防止最优解的其次算法必须由保优操作来防止最优解的遗失。与算法收敛性有关的因素主要包括遗失。与算法收敛性有关的因素主要包括种群规模、选择操作、交叉概率和变异概种群规模、选择操作、交叉概率和变异概率。率。第三十六页，本课件共有65页种群规模对收敛性的影响种群规模对收敛性的影响 通常，种群太小则不能提供足够的采通常，种群太小则不能提供足够的采样点，以致算法性能很差；种群太大，尽样点，以致算法性能很差；种群太大，尽管可以增加优化信息，阻止早熟收敛的发管可以增加优化信息，阻止早熟收敛的发生，但无疑会增加计算量，造成收敛时间生，但无疑会增加计算量，造成收敛时间太长，表现为收敛速度缓慢。太长，表现为收敛速度缓慢。第三十七页，本课件共有65页选择操作对收敛性的影响选择操作对收敛性的影响 选择操作使高适应度个体能够以更大的概率选择操作使高适应度个体能够以更大的概率选择操作使高适应度个体能够以更大的概率选择操作使高适应度个体能够以更大的概率生存，从而提高了遗传算法的全局收敛性。如果生存，从而提高了遗传算法的全局收敛性。如果生存，从而提高了遗传算法的全局收敛性。如果生存，从而提高了遗传算法的全局收敛性。如果在算法中采用最优保存策略，即将父代群体中最在算法中采用最优保存策略，即将父代群体中最在算法中采用最优保存策略，即将父代群体中最在算法中采用最优保存策略，即将父代群体中最佳个体保留下来，不参加交叉和变异操作，使之佳个体保留下来，不参加交叉和变异操作，使之佳个体保留下来，不参加交叉和变异操作，使之佳个体保留下来，不参加交叉和变异操作，使之直接进入下一代，最终可使遗传算法以概率直接进入下一代，最终可使遗传算法以概率直接进入下一代，最终可使遗传算法以概率直接进入下一代，最终可使遗传算法以概率1收收敛于全局最优解。敛于全局最优解。第三十八页，本课件共有65页交叉概率对收敛性的影响交叉概率对收敛性的影响 交叉操作用于个体对，产生新的个体，交叉操作用于个体对，产生新的个体，实质上是在解空间中进行有效搜索。交叉概实质上是在解空间中进行有效搜索。交叉概率太大时，种群中个体更新很快，会造成高率太大时，种群中个体更新很快，会造成高适应度值的个体很快被破坏掉；概率太小时，适应度值的个体很快被破坏掉；概率太小时，交叉操作很少进行，从而会使搜索停滞不前，交叉操作很少进行，从而会使搜索停滞不前，造成算法的不收敛。造成算法的不收敛。第三十九页，本课件共有65页变异概率对收敛性的影响变异概率对收敛性的影响 变异操作是对种群模式的扰动，有利于增变异操作是对种群模式的扰动，有利于增加种群的多样性加种群的多样性。但是，变异概率太小则很。但是，变异概率太小则很难产生新模式，变异概率太大则会使遗传算法难产生新模式，变异概率太大则会使遗传算法成为随机搜索算法。成为随机搜索算法。第四十页，本课件共有65页遗传算法的本质遗传算法的本质 遗传算法本质上是对染色体模式所进行的遗传算法本质上是对染色体模式所进行的一系列运算，即通过选择算子将当前种群中的一系列运算，即通过选择算子将当前种群中的优良模式遗传到下一代种群中，利用交叉算子优良模式遗传到下一代种群中，利用交叉算子进行模式重组，利用变异算子进行模式突变。进行模式重组，利用变异算子进行模式突变。通过这些遗传操作，模式逐步向较好的方向进通过这些遗传操作，模式逐步向较好的方向进化，最终得到问题的最优解。化，最终得到问题的最优解。第四十一页，本课件共有65页3 3、遗传算法的改进遗传算法的改进 遗传欺骗问题：在遗传算法进化过程中，遗传欺骗问题：在遗传算法进化过程中，有时会产生一些超常的个体，这些个体因竞有时会产生一些超常的个体，这些个体因竞争力太突出而控制了选择运算过程，从而影争力太突出而控制了选择运算过程，从而影响算法的全局优化性能，导致算法获得某个响算法的全局优化性能，导致算法获得某个局部最优解。局部最优解。第四十二页，本课件共有65页遗传算法的改进途径遗传算法的改进途径（1）对编码方式的改进）对编码方式的改进（2）对遗传算子）对遗传算子 的改进的改进（3）对控制参数的改进）对控制参数的改进（4）对执行策略的改进）对执行策略的改进 第四十三页，本课件共有65页对编码方式的改进对编码方式的改进 二二进进制制编编码码优优点点在在于于编编码码、解解码码操操作作简简单单，交交叉叉、变变异异等等操操作作便便于于实实现现，缺缺点点在在于于精精度度要要求求较较高高时时，个个体体编编码码串串较较长长，使使算算法法的的搜搜索索空空间间急急剧剧扩扩大大，遗遗传传算算法法的的性性能能降降低低。格格雷雷编编码码克克服服了了二二进进制制编编码码的的不不连连续续问问题题，浮浮点点数数编编码码改善了遗传算法的计算复杂性改善了遗传算法的计算复杂性。第四十四页，本课件共有65页对遗传算子对遗传算子 的改进的改进排序选择排序选择 均匀交叉均匀交叉 逆序变异逆序变异（1）对群体中的所有个体按其适应度大小进行降序排序；（2）根据具体求解问题，设计一个概率分配表，将各个概率值按上述排列次序分配给各个个体；（3）以各个个体所分配到的概率值作为其遗传到下一代的概率，基于这些概率用赌盘选择法来产生下一代群体。第四十五页，本课件共有65页对遗传算子对遗传算子 的改进的改进排序选择排序选择 均匀交叉均匀交叉 逆序变异逆序变异（1）随机产生一个与个体编码长度相同的二进制屏蔽字P=W1W2Wn；（2）按下列规则从A、B两个父代个体中产生两个新个体X、Y：若Wi=0，则X的第i个基因继承A的对应基因，Y的第i个基因继承B的对应基因；若Wi=1，则A、B的第i个基因相互交换，从而生成X、Y的第i个基因。第四十六页，本课件共有65页对遗传算子对遗传算子 的改进的改进排序选择排序选择 均匀交叉均匀交叉 逆序变异逆序变异变异前：3 4 8|7 9 6 5|2 1变异前：3 4 8|5 6 9 7|2 1第四十七页，本课件共有65页对控制参数的改进对控制参数的改进 Schaffer建议的最优参数范围是：建议的最优参数范围是：M=20-100，T=100-500，Pc=0.4-0.9，Pm=0.001-0.01。第四十八页，本课件共有65页对控制参数的改进对控制参数的改进 Srinvivas等人提出自适应遗传算法，即等人提出自适应遗传算法，即PC和和Pm能够随适应度自动改变，当种群的各个个体适应度能够随适应度自动改变，当种群的各个个体适应度趋于一致或趋于局部最优时，使二者增加，而当种群趋于一致或趋于局部最优时，使二者增加，而当种群适应度比较分散时，使二者减小，同时对适应值高于适应度比较分散时，使二者减小，同时对适应值高于群体平均适应值的个体，采用较低的群体平均适应值的个体，采用较低的PC和和Pm，使性，使性能优良的个体进入下一代，而低于平均适应值的个能优良的个体进入下一代，而低于平均适应值的个体，采用较高的体，采用较高的P PC和和和和Pmm，使性能较差的个体被淘汰，使性能较差的个体被淘汰，使性能较差的个体被淘汰，使性能较差的个体被淘汰 。第四十九页，本课件共有65页对执行策略的改进对执行策略的改进混合遗传算法混合遗传算法免疫遗传算法免疫遗传算法小生境遗传算法小生境遗传算法单亲遗传算法单亲遗传算法并行遗传算法并行遗传算法第五十页，本课件共有65页三、遗传算法的应用1 1、遗传算法的应用领域遗传算法的应用领域 2 2、遗传算法的应用示例遗传算法的应用示例 第五十一页，本课件共有65页1 1、遗传算法的应用领域遗传算法的应用领域（1）组合优化）组合优化 （2）函数优化）函数优化（3）自动控制）自动控制 （4）生产调度）生产调度（5）图像处理）图像处理 （6）机器学习）机器学习（7）人工生命）人工生命 （8）数据挖掘）数据挖掘 第五十二页，本课件共有65页遗传算法应用于组合优化遗传算法应用于组合优化 随着问题规模的增大，组合优化问题的搜索空随着问题规模的增大，组合优化问题的搜索空间也急剧扩大，有时在计算机上用枚举法很难甚至间也急剧扩大，有时在计算机上用枚举法很难甚至不可能求出其最优解。实践证明，遗传算法已经在不可能求出其最优解。实践证明，遗传算法已经在求解旅行商问题、背包问题、装箱问题、布局优化、求解旅行商问题、背包问题、装箱问题、布局优化、网络路由等具有网络路由等具有NP难度的组合优化问题上取得了成难度的组合优化问题上取得了成功的应用。功的应用。第五十三页，本课件共有65页2 2、遗传算法的应用示例遗传算法的应用示例 弹药装载问题（弹药装载问题（Ammunition Loading Problem，简称，简称ALP），就是在满足各类），就是在满足各类通用弹药运输规程和安全性的前提下，如通用弹药运输规程和安全性的前提下，如何将一批通用弹药箱装入军用运输工具，何将一批通用弹药箱装入军用运输工具，使得通用弹药的装载效率达到最大值的问使得通用弹药的装载效率达到最大值的问题。题。第五十四页，本课件共有65页AGSAA的基本原理的基本原理 在在弹弹药药装装载载中中，考考虑虑到到模模拟拟退退火火算算法法的的基基本本思思想想是是跳跳出出局局部部最最优优解解，将将模模拟拟退退火火思思想想引引入入遗遗传传算算法法，应应用用改改进进型型遗遗传传算算法法和和模模拟拟退退火火算算法法相相结结合合，构构建建自自适适应应遗遗传传模模拟拟退退火火算算法法（AGSAAAGSAA），从从而而综综合合了了全全局局优优化化和和局局部部搜搜索索的的特特点点，为为解解决决弹弹药药装装载载这这一一组组合合优优化化问问题题提提供供了新的思路。了新的思路。第五十五页，本课件共有65页AGSAA的编码方式的编码方式 AGSAAAGSAA采采用用二二进进制制编编码码方方式式，每每一一个个二二进进制制位位对对应应一一个个待待装装弹弹药药箱箱，若若为为，表表示示该该弹弹药箱装入运输工具，为则不装。药箱装入运输工具，为则不装。第五十六页，本课件共有65页AGSAA的解码和适应度函数的解码和适应度函数 AGSAAAGSAA采采用用弹弹药药装装载载的的启启发发式式算算法法来来解解码码，解解码码后后最最终终确确定定装装入入运运输输工工具具的的弹弹药药箱箱。适适应应度度函函数数主主要要考考虑虑两两个个方方面面，即即载载重重率率和和积积载载率率，对这两个因素加权，来计算适应度函数值。对这两个因素加权，来计算适应度函数值。第五十七页，本课件共有65页弹药装载的启发式算法弹药装载的启发式算法 （1 1）定位规则（）定位规则（Locating ruleLocating rule）定位规则是指用来确定当前待装弹药箱在运定位规则是指用来确定当前待装弹药箱在运输工具剩余装载空间中摆放位置的规则。输工具剩余装载空间中摆放位置的规则。（2 2）定序规则（）定序规则（Ordering ruleOrdering rule）定序规则是指用来确定弹药箱放入运输工具定序规则是指用来确定弹药箱放入运输工具装载空间先后顺序的规则。装载空间先后顺序的规则。第五十八页，本课件共有65页遗传算子的选择遗传算子的选择AGSAAAGSAA的选择算子采用轮盘赌选择算子，的选择算子采用轮盘赌选择算子，并结合最优保存策略；变异算子采用基本位并结合最优保存策略；变异算子采用基本位变异算子；同时，在变异运算之后，增加退变异算子；同时，在变异运算之后，增加退火算子，以增强算法的局部搜索能力；交叉火算子，以增强算法的局部搜索能力；交叉概率和变异概率为自适应概率，以提高种群概率和变异概率为自适应概率，以提高种群的进化效率。的进化效率。第五十九页，本课件共有65页交叉算子的选择交叉算子的选择 由于由于AGSAAAGSAA是采用将弹药箱的编号排列成串是采用将弹药箱的编号排列成串来进行编码的，如果个体交叉采用传统方式进行，来进行编码的，如果个体交叉采用传统方式进行，就有可能使个体的编码产生重复基因（即一个弹就有可能使个体的编码产生重复基因（即一个弹药箱编号在一个个体中出现两次以上），从而产药箱编号在一个个体中出现两次以上），从而产生不符合条件的个体，因此，生不符合条件的个体，因此，AGSAAAGSAA采用的是部采用的是部分映射交叉算子。分映射交叉算子。第六十页，本课件共有65页部分映射交叉算子部分映射交叉算子交叉前：交叉前：8 7|4 3|1 2 6 58 7|4 3|1 2 6 5 1 2|5 7|8 3 4 6 1 2|5 7|8 3 4 6交叉后：交叉后：8 3|6 7|1 2 4 58 3|6 7|1 2 4 5 1 7|6 2|8 3 4 5 1 7|6 2|8 3 4 5第六十一页，本课件共有65页参考文献参考文献1 1 张伟，李守智，高峰等张伟，李守智，高峰等张伟，李守智，高峰等张伟，李守智，高峰等.几种智能最优化算法的比较研究几种智能最优化算法的比较研究几种智能最优化算法的比较研究几种智能最优化算法的比较研究.Proceedings of the.Proceedings of the 24th Chinese Control Conference,Guangzhou,P.R.China July 15-18,24th Chinese Control Conference,Guangzhou,P.R.China July 15-18,2005:13162005:1316132013202 2马玉明马玉明马玉明马玉明,贺爱玲贺爱玲贺爱玲贺爱玲,李爱民李爱民李爱民李爱民.遗传算法的理论研究综述遗传算法的理论研究综述遗传算法的理论研究综述遗传算法的理论研究综述.山东轻工业学院学报山东轻工业学院学报山东轻工业学院学报山东轻工业学院学报,2004,18(3):772004,18(3):7780803 Andreas Bortfeldt,Hermann Gehring.A Hybrid Genetic Algorithm for The 3 Andreas Bortfeldt,Hermann Gehring.A Hybrid Genetic Algorithm for The Container Loading Problem.European Journal of Operational Research,Container Loading Problem.European Journal of Operational Research,2001(131):1432001(131):143161.161.4 D.Y.He,J.Z.Cha.Research on Solution to Complex Container Loading Problem 4 D.Y.He,J.Z.Cha.Research on Solution to Complex Container Loading Problem Based on Genetic Algorithm.The First International Conference on Machine Based on Genetic Algorithm.The First International Conference on Machine Learning and Cybernetics.Beijing-China,2002:78Learning and Cybernetics.Beijing-China,2002:788282第六十二页，本课件共有65页参考文献参考文献5 C.Pimpawat,N.Chaiyaratana.Using A Co-Operative Co-Evolutionary 5 C.Pimpawat,N.Chaiyaratana.Using A Co-Operative Co-Evolutionary Genetic Algorithm to Solve A Three-Dimensional Container Loading Genetic Algorithm to Solve A Three-Dimensional Container Loading Problem.The Second International Conference on Machine Learning and Problem.The Second International Conference on Machine Learning and Cybernetics.Mongkut-Thailand,2003:1197Cybernetics.Mongkut-Thailand,2003:1197120412046 6王春水，肖学柱，陈汉明王春水，肖学柱，陈汉明王春水，肖学柱，陈汉明王春水，肖学柱，陈汉明.遗传算法的应用举例遗传算法的应用举例遗传算法的应用举例遗传算法的应用举例.计算机仿真计算机仿真计算机仿真计算机仿真20052005，22(6):15522(6):1551571577 7姚文俊姚文俊姚文俊姚文俊.遗传算法及其研究进展遗传算法及其研究进展遗传算法及其研究进展遗传算法及其研究进展.计算机与数字工程计算机与数字工程计算机与数字工程计算机与数字工程,2004,2004，32(4):4132(4):4143438 8吉根林吉根林吉根林吉根林.遗传算法研究综述遗传算法研究综述遗传算法研究综述遗传算法研究综述.计算机应用与软件计算机应用与软件计算机应用与软件计算机应用与软件,2004,2004，21(2):6921(2):6973739 9高艳霞，刘峰，王道洪高艳霞，刘峰，王道洪高艳霞，刘峰，王道洪高艳霞，刘峰，王道洪.改进型遗传算法及其应用研究改进型遗传算法及其应用研究改进型遗传算法及其应用研究改进型遗传算法及其应用研究.上海大学学报上海大学学报上海大学学报上海大学学报,2004(10):249,2004(10):249253253第六十三页，本课件共有65页参考文献参考文献1010马立肖马立肖马立肖马立肖,王江晴王江晴王江晴王江晴.遗传算法在组合优化问题中的应用遗传算法在组合优化问题中的应用遗传算法在组合优化问题中的应用遗传算法在组合优化问题中的应用.计算机工程与科学计算机工程与科学计算机工程与科学计算机工程与科学,2005,2005，27(7):7227(7):727373、82821111曹先彬曹先彬曹先彬曹先彬,刘克胜刘克胜刘克胜刘克胜,王煦法王煦法王煦法王煦法.基于免疫遗传算法的装箱问题求解基于免疫遗传算法的装箱问题求解基于免疫遗传算法的装箱问题求解基于免疫遗传算法的装箱问题求解.小型微型计算机系小型微型计算机系小型微型计算机系小型微型计算机系统统统统.2000,21(4):361.2000,21(4):361363 363 12 Rudolf Berghammer,Florian Reuter.A Linear Approximation Algorithm for Bin 12 Rudolf Berghammer,Florian Reuter.A Linear Approximation Algorithm for Bin Packing with Absolute Approximation Factor.Science of Computer Packing with Absolute Approximation Factor.Science of Computer Programming,2003(48):67Programming,2003(48):6780801313严心池严心池严心池严心池,安伟光安伟光安伟光安伟光,赵维涛等赵维涛等赵维涛等赵维涛等.遗传算法中遗传算法中遗传算法中遗传算法中“免疫算子免疫算子免疫算子免疫算子”的构造与性能的构造与性能的构造与性能