遗传算法原理与应用

1、遗传算法原理与应用遗传算法原理与应用郭学会郭学会20082008年年 10 10 月月报告提纲报告提纲一、遗传算法概述一、遗传算法概述 二、遗传算法原理二、遗传算法原理三、遗传算法的应用三、遗传算法的应用一、遗传算法概述1 1、智能优化算法智能优化算法2 2、基本遗传算法基本遗传算法3 3、遗传算法的特点遗传算法的特点返回返回返回返回0 . 2)10sin()(xxxf基因型：基因型：1000101110110101000111编码解码个体（染色体）基因niiiiFFP1/交叉点交叉点突变点突变点产生初始群体产生初始群体是否满足停止准则是否满足停止准则是是输出结果并结束输出结果并结束计算个体适

2、应度值计算个体适应度值比例选择运算比例选择运算单点交叉运算单点交叉运算基本位突变运算基本位突变运算否否产生新一代群体产生新一代群体执行执行M/2M/2次次返回返回返回返回二、遗传算法原理1 1、遗传算法的数学基础遗传算法的数学基础2 2、遗传算法的收敛性分析遗传算法的收敛性分析3 3、遗传算法的改进遗传算法的改进返回返回1 1、遗传算法的数学基础遗传算法的数学基础返回返回模式的阶和定义距的含义模式的阶和定义距的含义 模式阶用来反映不同模式间确定性模式阶用来反映不同模式间确定性的差异，模式阶数越高，模式的确定性的差异，模式阶数越高，模式的确定性就越高，所匹配的样本数就越少。在遗就越高，所匹配的样

3、本数就越少。在遗传操作中，即使阶数相同的模式，也会传操作中，即使阶数相同的模式，也会有不同的性质，而模式的定义距就反映有不同的性质，而模式的定义距就反映了这种性质的差异。了这种性质的差异。模式定理模式定理返回返回返回返回2 2、遗传算法的收敛性分析遗传算法的收敛性分析收敛性的影响收敛性的影响收敛性的影响收敛性的影响收敛性的影响收敛性的影响收敛性的影响收敛性的影响返回返回3 3、遗传算法的改进遗传算法的改进遗传算法的改进途径遗传算法的改进途径（1 1） 对群体中的所有个体对群体中的所有个体按其适应度大小进行降序排按其适应度大小进行降序排序；序；（2 2） 根据具体求解问题，根据具体求解问题，设计

4、一个概率分配表，将各设计一个概率分配表，将各个概率值按上述排列次序分个概率值按上述排列次序分配给各个个体；配给各个个体；（3 3） 以各个个体所分配到以各个个体所分配到的概率值作为其遗传到下一的概率值作为其遗传到下一代的概率，基于这些概率用代的概率，基于这些概率用赌盘选择法来产生下一代群赌盘选择法来产生下一代群体。体。 （1 1） 随机产生一个与个体随机产生一个与个体编码长度相同的二进制屏蔽编码长度相同的二进制屏蔽字字P = WP = W1 1W W2 2W Wn n ；（2 2） 按下列规则从按下列规则从A A、B B两两个父代个体中产生两个新个个父代个体中产生两个新个体体X X、Y Y：若

5、：若W Wi i = 0 = 0，则，则X X的第的第i i个基因继承个基因继承A A的对应基因，的对应基因，Y Y的第的第i i个基因继承个基因继承B B的对应基的对应基因；若因；若W Wi i = 1 = 1，则，则A A、B B的第的第i i个基因相互交换，从而生成个基因相互交换，从而生成X X、Y Y的第的第i i个基因。个基因。 突变前：突变前：3 4 8 | 7 9 6 5 | 2 13 4 8 | 7 9 6 5 | 2 1突变后：突变后：3 4 8 | 5 6 9 7 | 2 13 4 8 | 5 6 9 7 | 2 1返回返回三、遗传算法的应用1 1、遗传算法的应用领域遗传算

6、法的应用领域2 2、遗传算法的应用示例遗传算法的应用示例3 3、我的研究、我的研究1 1、遗传算法的应用领域遗传算法的应用领域（1）组合优化）组合优化（4）图像处理）图像处理返回返回遗传算法应用于组合优化遗传算法应用于组合优化返回返回返回返回返回返回图像处理图像处理返回返回返回返回返回返回2 2、遗传算法的应用示例遗传算法的应用示例 弹药装载问题（弹药装载问题（Ammunition Loading Problem，简称，简称ALP），就是在），就是在满足各类通用弹药运输规程和安全性的满足各类通用弹药运输规程和安全性的前提下，如何将一批通用弹药箱装入军前提下，如何将一批通用弹药箱装入军用运输工具

7、，使得通用弹药的装载效率用运输工具，使得通用弹药的装载效率达到最大值的问题。达到最大值的问题。AGSAA的基本原理的基本原理在弹药装载中，考虑到模拟退火算法在弹药装载中，考虑到模拟退火算法的基本思想是跳出局部最优解，将模拟退的基本思想是跳出局部最优解，将模拟退火思想引入遗传算法，应用改进型遗传算火思想引入遗传算法，应用改进型遗传算法和模拟退火算法相结合，构建自适应遗法和模拟退火算法相结合，构建自适应遗传模拟退火算法（传模拟退火算法（AGSAAAGSAA），从而综合了全），从而综合了全局优化和局部搜索的特点，为解决弹药装局优化和局部搜索的特点，为解决弹药装载这一组合优化问题提供了新的思路。载这一

8、组合优化问题提供了新的思路。AGSAA的编码方式的编码方式AGSAAAGSAA采用二进制编码方式，每一个二采用二进制编码方式，每一个二进制位对应一个待装弹药箱，若为，表进制位对应一个待装弹药箱，若为，表示该弹药箱装入运输工具，为则不装。示该弹药箱装入运输工具，为则不装。AGSAA的解码和适应度函数的解码和适应度函数AGSAAAGSAA采用弹药装载的启发式算法来解采用弹药装载的启发式算法来解码，解码后最终确定装入运输工具的弹药码，解码后最终确定装入运输工具的弹药箱。适应度函数主要考虑两个方面，即载箱。适应度函数主要考虑两个方面，即载重率和积载率，对这两个因素加权，来计重率和积载率，对这两个因素加

9、权，来计算适应度函数值。算适应度函数值。弹药装载的启发式算法弹药装载的启发式算法（1 1）定位规则（）定位规则（Locating ruleLocating rule） 定位规则是指用来确定当前待装弹药箱在定位规则是指用来确定当前待装弹药箱在运输工具剩余装载空间中摆放位置的规则。运输工具剩余装载空间中摆放位置的规则。 （2 2）定序规则（）定序规则（Ordering ruleOrdering rule） 定序规则是指用来确定弹药箱放入运输工定序规则是指用来确定弹药箱放入运输工具装载空间先后顺序的规则。具装载空间先后顺序的规则。遗传算子的选择遗传算子的选择AGSAAAGSAA的选择算子采用轮盘赌选

10、择算的选择算子采用轮盘赌选择算子，并结合最优保存策略；突变算子采子，并结合最优保存策略；突变算子采用基本位突变算子；同时，在突变运算用基本位突变算子；同时，在突变运算之后，增加退火算子，以增强算法的局之后，增加退火算子，以增强算法的局部搜索能力；交叉概率和突变概率为自部搜索能力；交叉概率和突变概率为自适应概率，以提高种群的进化效率。适应概率，以提高种群的进化效率。交叉算子的选择交叉算子的选择 由于由于AGSAAAGSAA是采用将弹药箱的编号排列成是采用将弹药箱的编号排列成串来进行编码的，如果个体交叉采用串来进行编码的，如果个体交叉采用传统方式传统方式进行，就有可能使个体的编码产生进行，就有可能

11、使个体的编码产生重复基因重复基因（即（即一个弹药箱编号在一个个体中出现两次以一个弹药箱编号在一个个体中出现两次以上上），从而产生），从而产生不符合条件的个体不符合条件的个体，因此，因此，AGSAAAGSAA采用的是采用的是部分映射交叉算子部分映射交叉算子。部分映射交叉算子部分映射交叉算子交叉前：交叉前： 8 7 | 4 3 | 1 2 6 58 7 | 4 3 | 1 2 6 5交叉后：交叉后： 8 3 | 6 7 | 1 2 4 58 3 | 6 7 | 1 2 4 5返回返回返回返回适应性函数适应性函数是计算出每条染色体的适应值。在本研究中，染色体若其适应值较大者，表示该排课结果拥有较多较佳授课时段，将会被给予较大的生存概率于下一代演化中。首先建立每位教师的授课时段优先度，如表1所示，可由教师填入自己较喜欢的时段及其喜好程度，该表格将提供做适应性使用，其中3代表最喜欢的授课时段，2代表较喜欢的授课时段，1代表