多变异拟子—基因共同进化算法的理论及应用研究

论文摘要

遗传算法（Genetic Algorithm, GA）是一类借鉴生物界的进化规律演化而来的采用概率转移准则的随机化搜索方法。由于它在求解复杂优化问题上的巨大潜力,近年来在工程技术领域中获得了极其广泛的应用,同时也随之涌现出数目繁多的改进遗传算法。这些改进GA针对具体问题,或改进算子,或混合策略,或构造编码,取得了良好的应用效果。但是这些改进GA往往具有强的领域性,所用改进也缺乏理论支持和对比,鲁棒性不足,极大地限制了GA的实际应用。本文首次将社会生物学理论与遗传算法结合,提出了拟子-基因共同进化策略,以提高算法搜索效率和鲁棒性为目的,充分利用改进GA成果和GA固有的并行优势,构造出一种新的源于社会进化和文化传播理论的具有结构策略自适应、自组织性的综合进化算法。论文对这种进化算法系统地进行了理论分析,并选择性地将其应用在三个不同领域的具体问题,在算法的研究方面取得了一些基础性和开创性的成果。全文主要涉及到以下几个方面的工作:1、基于社会生物学文化进化理论,分析了拟子进化和基因进化的基本特征,综合成可操作的数学概念,提出了拟子分类和基因-文化信息的数据结构,提出了拟子进化算子（复制、感染、复兴）,构造了文化进化策略,构成了多变异拟子-基因共同进化算法。2、针对CEOP问题,描述了一种简单可实现的共同进化算法的基本结构,利用Markov链分析了算法的收敛性,证明了算法的全局收敛。基于指标熵的概念,分析了算法的群体多样性,得出若干结论。分析了算法的时间复杂度,研究了文化算子对算法时间复杂度的影响。3、提出了GA的应用性能评价标准,从连续性、多峰性、随机性、振荡性、广域性多个角度出发选择五个测试函数,对共同进化算法的搜索性能和鲁棒性作了函数优化的性能测试,分析了仿真结果,研究了文化算子对算法的影响。4、基于集覆盖的概念,研究了MAS中的任务分配问题,建立了任务分配问题的分层数学模型,给出了子任务分解共同进化算法,实验比较了IGA、SGA、CN,验证了共同进化算法对NP完全问题的有效性。5、针对近地天线加载优化设计问题,结合多种改进GA策略,提出了策略型拟子,给出天线加载设计的共同进化算法,对有耗半空间对称偶极子天线加载优化设计作了仿真实验,验证了共同进化算法对多变量多峰连续搜索问题上的有效性。6、针对图像模板匹配问题的领域知识,采用单类拟子和实数编码,给出快速共同进化匹配算法策略,基于NPROD相似度测度,仿真试验了无差别和有差别模板匹配,验证了共同进化算法对实数编码和实时性搜索问题上的有效性。本文研究工作表明:多学科交叉会拓展研究思路,改进研究方法。从应用技术角度出发,也能产生新的理论研究方向。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景及意义
• 1.2 国内外研究发展现状
• 1.2.1 遗传算法的研究和发展现状
• 1.2.2 3MGCA 的提出
• 1.2.3 三个具体应用问题的研究现状
• 1.3 论文的研究内容和章节安排
• 第二章 GA 的应用技术基础及常用的改进算法
• 2.1 引言
• 2.2 遗传算法应用技术基础
• 2.2.1 选用遗传算法的原因
• 2.2.2 应用遗传算法的相关知识
• 2.2.3 遗传算法的应用性能评价
• 2.3 改进遗传算法
• 2.3.1 小生境技术遗传算法
• 2.3.2 混合遗传算法
• 2.3.3 并行遗传算法
• 2.4 本章小结
• 第三章 多变异拟子-基因共同进化算法及其理论分析
• 3.1 引言
• 3.2 拟子进化理论和MA 算法
• 3.2.1 拟子进化理论
• 3.2.2 Memetic Algorithms
• 3.3 多变异拟子-基因共同进化算法的遗传策略
• 3.4 一种满足3MGCA 策略的算法设计举例
• 3.4.1 CEOP 问题中领域先验知识的策略引入
• 3.4.2 拟子分类与文化进化
• 3.4.3 多变异拟子-基因共同进化算法的整体结构
• 3.5 多变异拟子-基因共同进化算法的理论分析
• 3.5.1 3MGCA 的收敛性分析
• 3.5.2 3MGCA 的群体多样性分析
• 3.5.3 3MGCA 的算法时间复杂度分析
• 3.5.4 3MGCA 同目前并行GA 的区分
• 3.6 3MGCA 在函数优化上的仿真及性能分析
• 3.6.1 选择测试函数
• 3.6.2 仿真结果和性能评价
• 3.7 本章小结
• 第四章 基于3MGCA 的MAS 任务分配优化
• 4.1 引言
• 4.2 多AGENT 系统的任务分解问题
• 4.2.1 Agent 与MAS 的基本理论
• 4.2.2 MAS 的体系结构和协作机制
• 4.2.3 MAS 任务分解问题和CN 算法
• 4.3 基于3MGCA 的任务分解优化算法
• 4.3.1 问题数学模型的建立
• 4.4 仿真实验及结果分析
• 4.5 本章小结
• 第五章 基于3MGCA 的有耗半空间加载天线优化设计
• 5.1 引言
• 5.2 加载天线优化设计问题的理论基础
• 5.2.1 加载天线的定义和特点
• 5.2.2 加载天线的电流分布和效率
• 5.2.3 加载天线的积分方程
• 5.3 近地加载天线数学模型的建立和3MGCA 的设计
• 5.3.1 近地加载天线的数学分析方程
• 5.3.2 基于3MGCA 的近地加载天线优化设计算法
• 5.4 仿真和结果分析
• 5.5 本章小结
• 第六章 基于实数3MGCA 的图像模板相关匹配
• 6.1 引言
• 6.2 图像匹配问题的相关理论
• 6.2.1 图像匹配问题的关键要素
• 6.2.2 图像匹配的算法分类
• 6.3 模板匹配的数学模型和实数3MGCA 设计
• 6.3.1 模板匹配的匹配特征和相似度测度
• 6.3.2 实数编码3MGCA 匹配算法设计
• 6.4 仿真和实验结果
• 6.5 本章小结
• 结论
• 参考文献
• 攻读学位期间发表的与学位论文内容相关的学术论文
• 致谢