高维优化进化算法及其应用研究

论文摘要

进化算法（Evolutionary Algorithm）是由生物进化规律而演化出的一种搜索和优化的计算方法,其主要特点是群体搜索策略和群体中个体之间的信息交换,搜索不依赖于梯度信息。主要包括:遗传算法、进化策略、进化规划,也称之为广义遗传算法。它的主要特点是原理简单、参数少、收敛速度较快,所需领域知识少。该算法的出现引起了学者们极大的关注,己在函数优化、神经网络训练、组合优化、机器人路径规划等领域获得了广泛应用,并取得了较好的效果。尽管进化算法发展数十年,但无论是理论分析还是实践应用都尚未成熟,仍有大量的问题值得研究。本论文围绕多移动机器人领域抽象出的若干高维空间优化问题进行了深入研究。就如何改进传统进化算法性能以及该算法在高维复杂函数优化、约束优化、进化神经网络、大规模组合优化以及多机器人系统软故障检测等领域的应用作了详细的论述。本文的主要研究工作和创新点可归纳如下:1.提出了一种基于佳点集原理的实数域进化算法,该算法对于高维约束优化问题和高维函数优化问题围绕如何设计有效的约束处理技术和高效的进化算法两方面展开;吸取正交、差异、粒子群等进化算法的成功经验;在佳点集理论研究的基础上,构造一种适应度不受维数限制的进化算法。佳点集的构造与空间维数无关,因此克服了用正交设计法的不足,也为高维近似计算提供了一个非常好的算法。多组标准测试函数的测试结果对算法进行了有效地证明。2.针对进化神经网络中网络结构和权值同时可调整存在的困难,利用Leung的编码基础,用基于差异技术和佳点集技术相结合的高维优化进化算法同时调整网络结构和参数。差异进化的全局搜索能力结合佳点集交叉算子的局部搜索能力,能有效避免目标函数的局部最优,特别是参数的数目非常大时。网络的权值与结构一同进化,进化结果使具有全连通的三层神经网络变成一个部分连接的前馈网络。从硬件实现和处理时间的角度出发,此法的优点在于实现神经网络的耗费明显减少。3.针对多移动机器人任务分配和路径规划中提出了大规模组合优化问题,提出了一种新的编码方法,能将离散的组合空间映射到一段连续的区间,结合成熟进化算法的搜索机制使新算法的性能大大提高。新编码与问题的组合向量一一对应。所有编码均为可行方案,有效避免了以往算法中的冗余运算。在新编码的基础上通过理论证明进一步缩小了问题的搜索空间;其次,进化策略中加入了一个精英队列,并且建立了相应的精英学习策略。在整个群体进化的同时,精英个体也按照相应的策略不断优化,从而能有效吸收以往算法在组合优化问题上的成功经验,有利于保留较好的基因段。最后证明了新算法的收敛性全局最优。仿真实验的结果表明了算法的有效性。4.针对多机器人系统中的软故障检测,提出了一种基于（μ+λ）进化策略的阴性选择算法;构造匹配信噪比方法综合运用海明规则和r位连续匹配规则,使检测器分布更均匀;同传统的阴性选择算法相比,进化机制使得检测器的搜索不再盲目。对于较大规模的自体集也可以快速准确生成成熟检测器。数值实验表明新算法产生成熟检测器的迭代次数、黑洞数量均大幅下降,同时检测率显著提高。在此基础之上,引入正交选择机制更有效降低了算法的运算复杂度。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 优化技术与进化计算
• 1.1.1 优化技术
• 1.1.2 进化算法
• 1.1.3 进化算法的应用
• 1.2 高维进化在多机器人领域的国内外研究现状分析
• 1.2.1 国内外研究现状分析
• 1.2.2 研究难点及解决途径
• 1.3 课题来源与研究意义
• 1.3.1 课题来源
• 1.3.2 研究意义
• 1.4 研究内容及章节安排
• 1.4.1 研究内容
• 1.4.2 章节安排
• 1.4.3 论文的组织框架
• 第二章 约束优化技术及高维进化框架
• 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.3.4 其他框架或算子
• 2.4 个体优劣的比较准则
• 2.5 需要解决的几个主要问题
• 2.6 小结
• 第三章 佳点集实数域进化算法用于约束优化
• 3.1 进化策略与约束优化
• 3.2 交叉算子概述
• 3.2.1 二进制交叉算子
• 3.2.2 实数交叉算子
• 3.3 基于佳点集原理的约束优化进化算法
• 3.3.1 分步交叉策略
• 3.3.2 佳点集的基本定义和性质
• 3.3.3 在t维空间中取佳点的方法
• 3.3.4 变异
• 3.3.5 初始化种群的佳点集方法
• 3.3.6 选择下一代种群
• 3.4 约束优化进化算法的测试
• 3.5 实验结果与分析
• 3.5.1 结果分析
• 3.5.2 分步交叉的选定
• 3.6 小结
• 第四章 高维进化策略用于演化神经网络
• 4.1 演化神经网络现状
• 4.2 网络的整体编码
• 4.3 混合进化策略
• 4.3.1 粒子群优化算子
• 4.3.2 佳点集进化算子
• 4.3.3 混合进化策略的算法流程
• 4.4 实验结果与分析
• 4.4.1 鲁棒性分析
• 4.4.2 高维全局优化数值实验
• 4.5 小结
• 第五章 字典序进化算法用于组合优化问题
• 5.1 基于字典序进化算法的基本思想及理论分析
• 5.1.1 搜索空间的压缩
• 5.1.2 空间转移技术
• 5.2 基于字典序的进化算法
• 5.1.1 初始种群与精英队列
• 5.1.2 交叉
• 5.1.3 变异
• 5.1.4 精英个体的自学习
• 5.1.5 求解TSP问题的字典序进化算法流程
• 5.1.6 算法的收敛性
• 5.3 仿真试验及结果
• 5.4 小结
• 第六章 进化策略用于阴性选择
• 6.1 生物免疫技术
• 6.1.1 BIS的特征与机理
• 6.2 人工免疫系统
• 6.2.1 免疫系统中的几个基本概念
• 6.2.2 阴性选择算法
• 6.2.3 克隆选择算法
• 6.3 故障监测和诊断
• 6.3.1 问题的描述
• 6.3.2 比较机制
• 6.3.3 基于比较机制的进化算法
• 6.3.4 理论分析
• 6.3.5 仿真实验与分析
• 6.4 结论
• 第七章 结论与展望
• 7.1 本论文工作总结
• 7.2 进一步的研究方向
• 参考文献
• 致谢
• 攻读博士学位期间的科研工作与研究成果