遗传算法原理与应用(最初级)ppt课件.ppt

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

1、遗传算法原理与应用遗传算法原理与应用唐唐 慧慧 丰丰2006 2006 年年 5 5 月月报告提纲报告提纲一、遗传算法概述一、遗传算法概述 二、遗传算法原理二、遗传算法原理三、遗传算法的应用三、遗传算法的应用一、遗传算法概述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：若：若W Wi i = 0 = 0，则，则X X的第的第i i个基因继

5、承个基因继承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、遗传算法的应用领域遗传算法的应用领域2 2、遗传算法的应用示例遗传算法的应用示例1 1、遗传算法的应

6、用领域遗传算法的应用领域（1）组合优化）组合优化（5）图像处理）图像处理遗传算法应用于组合优化遗传算法应用于组合优化2 2、遗传算法的应用示例遗传算法的应用示例 弹药装载问题（弹药装载问题（Ammunition Loading Problem，简称，简称ALP），就是在），就是在满足各类通用弹药运输规程和安全性的满足各类通用弹药运输规程和安全性的前提下，如何将一批通用弹药箱装入军前提下，如何将一批通用弹药箱装入军用运输工具，使得通用弹药的装载效率用运输工具，使得通用弹药的装载效率达到最大值的问题。达到最大值的问题。AGSAA的基本原理的基本原理在弹药装载中，考虑到模拟退火算法在弹药装载中，考虑

7、到模拟退火算法的基本思想是跳出局部最优解，将模拟退的基本思想是跳出局部最优解，将模拟退火思想引入遗传算法，应用改进型遗传算火思想引入遗传算法，应用改进型遗传算法和模拟退火算法相结合，构建自适应遗法和模拟退火算法相结合，构建自适应遗传模拟退火算法（传模拟退火算法（AGSAAAGSAA），从而综合了全），从而综合了全局优化和局部搜索的特点，为解决弹药装局优化和局部搜索的特点，为解决弹药装载这一组合优化问题提供了新的思路。载这一组合优化问题提供了新的思路。AGSAA的编码方式的编码方式AGSAAAGSAA采用二进制编码方式，每一个二采用二进制编码方式，每一个二进制位对应一个待装弹药箱，若为，表进制位

8、对应一个待装弹药箱，若为，表示该弹药箱装入运输工具，为则不装。示该弹药箱装入运输工具，为则不装。AGSAA的解码和适应度函数的解码和适应度函数AGSAAAGSAA采用弹药装载的启发式算法来解采用弹药装载的启发式算法来解码，解码后最终确定装入运输工具的弹药码，解码后最终确定装入运输工具的弹药箱。适应度函数主要考虑两个方面，即载箱。适应度函数主要考虑两个方面，即载重率和积载率，对这两个因素加权，来计重率和积载率，对这两个因素加权，来计算适应度函数值。算适应度函数值。弹药装载的启发式算法弹药装载的启发式算法（1 1）定位规则（）定位规则（Locating ruleLocating rule） 定位规

9、则是指用来确定当前待装弹药箱在定位规则是指用来确定当前待装弹药箱在运输工具剩余装载空间中摆放位置的规则。运输工具剩余装载空间中摆放位置的规则。 （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 张伟，李守智，高峰等张伟，李守智，高峰等. 几种智能最优化算法的比较研究几种智能最优化算法的比较研究. Proceedings of the 24th Chinese Control Conference, Guangzhou, P.R. China July 15-18,

12、 2005:131613202马玉明马玉明,贺爱玲贺爱玲,李爱民李爱民. 遗传算法的理论研究综述遗传算法的理论研究综述. 山东轻工业学院学报山东轻工业学院学报, 2004,18(3):77803 Andreas Bortfeldt, Hermann Gehring. A Hybrid Genetic Algorithm for The Container Loading Problem. European Journal of Operational Research, 2001(131):143161.4 D.Y.He, J.Z.Cha. Research on Solution to Co

13、mplex Container Loading Problem Based on Genetic Algorithm. The First International Conference on Machine Learning and Cybernetics. Beijing-China,2002:7882参考文献参考文献5 C.Pimpawat, N.Chaiyaratana. Using A Co-Operative Co-Evolutionary Genetic Algorithm to Solve A Three-Dimensional Container Loading Probl

14、em. The Second International Conference on Machine Learning and Cybernetics. Mongkut-Thailand, 2003:119712046王春水，肖学柱，陈汉明王春水，肖学柱，陈汉明. 遗传算法的应用举例遗传算法的应用举例. 计算机仿真计算机仿真2005，22(6):1551577姚文俊姚文俊. 遗传算法及其研究进展遗传算法及其研究进展. 计算机与数字工程计算机与数字工程, 2004，32(4):41438吉根林吉根林. 遗传算法研究综述遗传算法研究综述. 计算机应用与软件计算机应用与软件, 2004，21(2):

15、69739高艳霞，刘峰，王道洪高艳霞，刘峰，王道洪. 改进型遗传算法及其应用研究改进型遗传算法及其应用研究. 上海大学学报上海大学学报, 2004(10):249253参考文献参考文献10马立肖马立肖,王江晴王江晴. 遗传算法在组合优化问题中的应用遗传算法在组合优化问题中的应用. 计算机工程与科学计算机工程与科学, 2005，27(7):7273、8211曹先彬曹先彬, 刘克胜刘克胜, 王煦法王煦法. 基于免疫遗传算法的装箱问题求解基于免疫遗传算法的装箱问题求解. 小型微型计小型微型计算机系统算机系统. 2000, 21(4):361363 12 Rudolf Berghammer, Florian Reuter. A Linear Approximation Algorithm for Bin Packing with Absolute Approximation Factor. Science of Computer Programming, 2003(48):678013严心池严心池, 安伟光安伟光, 赵维涛等赵维涛等. 遗传算法中遗传算法中“免疫算子免疫算子”的构造与性能的构造与性能. 哈尔哈尔滨工程大学学报滨工程大学学报, 2005，26(6):732735谢谢大家谢谢大家!Q&A