一种基于育种思想的全局优化算法—原理、性能及应用

论文摘要

优化技术作为工程决策的定量分析方法,其目的是基于研究对象的某种指标寻找最优的变量取值。但是,对于采用某种优化算法所获得的优化结果,当问及是否存在比之更好的解或者其是否全局最优解时,现有的算法尚难作出令人满意的回答。包括遗传算法(Genetic Algorithm,GA)在内的诸多算法,可以在经历无穷代演化后以概率1收敛到全局最优,但实际操作往往只能是有限次计算。因此,寻找更为有效的算法或策略以提高优化计算的效率,并对优化算法有限次计算的结果进行评价,以为决策提供更为可靠的信息,似将成为优化技术研究领域所关注的重要课题。本文基于遗传算法对上述课题展开研究,其主要工作内容和贡献如下。1.通过理论分析与实验研究,本文对常规遗传算法在优化计算的全局性和精确性等方面存在的问题进行了分析,指出遗传算法同时进行广度搜索和局部搜索的思想策略所存在的内在缺陷及其所面临的困境,为算法策略的进一步改进指出了合理可行的方向。2.本文借鉴现代育种操作思想,提出一类新的进化算法—育种算法(Breeding Algorithm,BA)。算法将全局优化过程转化为种子的选择和培育两个阶段的操作。提出利用自由采样选种实现广度搜索,采用基因置换技术执行育种操作以实现局部搜索的新思想,指出算法实现全局优化的基本原理并建立相应的实施模型。实验结果表明,实现相同概率的全局优化,育种算法所需计算代价一般不到常规遗传算法的1/2,并且具有更高的计算精度。3.根据育种算法的采样选种过程,本文提出采样探测灵敏度的概念,并结合采样得到的最优个体建立了解的全局性评价方法。4.本文对基因置换技术实现局部搜索的机理进行了分析和描述。对于二进制编码遗传算法所出现的海明悬崖现象,根据基因置换完毕的编码特征,提出识别和修复方法,从而可以确保算法实现二进制编码的最高计算精度。与此同时,对基因置换操作实现局部搜索的计算代价进行分析估计,指出该操作函数值计算次数上限和经验估计。5.本文对算法的实施和演化方式进行了研究,针对函数优化问题的性状及复杂函数的构造特征指出了算法的相应策略。对于约束优化问题,建立采用罚因子确定的经验方法。对40余例变量数1～50的经典测试函数进行实验和比较的结果表明,育种算法成功地刷新了现有部分最优解记录,其全局和局部搜索性能都优于常规遗传算法。6.本文对平行育种算法应用于多目标优化问题的效果进行了研究。结果表明,在求取多目标优化问题的帕累托(Pareto)有效解集方面,采用平行育种算法结合随机权系数,一般可以获得多个有效解。另外,针对过程系统控制参数的不确定性所产生的多模态和敏感系统优化问题,提出了系统平均效果最优解的概念,并结合平行育种算法建立了相应的求解和评价方法,然后通过工程实例的求解,对该方法的实施过程进行了更为确切的描述。7.最后,本文给出运用育种算法求解工程优化问题的基本实施流程,并对相关策略进行说明。本文研究结果表明,和常规遗传算法相比,育种算法在全局优化的原理上更加明确,算法构造更为简单,且在优化计算的精确性和效率方面也具有明显优势,可作为一种实用的工程优化方法。

论文目录

• 摘要
• Abstract
• 引言
• 1 文献评述
• 1.1 全局优化描述及编码转换
• 1.1.1 全局优化的一般性描述
• 1.1.2 二进制编码
• 1.2 遗传算法的基本构造及其实施技术
• 1.2.1 标准遗传算法的基本结构
• 1.2.2 终止准则
• 1.2.3 控制参数的确定
• 1.3 标准遗传算法的性能实验及其缺陷分析
• 1.3.1 标准遗传算法的性能实验
• 1.3.2 标准遗传算法的缺陷分析
• 1.4 遗传算法的改进策略及效果评价
• 1.4.1 种群多样性策略
• 1.4.2 平行搜索或多种群策略
• 1.4.3 区域压缩技术
• 1.4.4 简单育种技术
• 1.4.5 其它改进策略
• 1.5 遗传算法的进化机理和收敛性能
• 1.5.1 遗传算法的进化机理
• 1.5.2 遗传算法的收敛性
• 1.6 遗传算法的性能评价和比较方法
• 1.7 本文的主要研究内容及技术路线
• 2 育种算法的基本原理及其收敛性能
• 2.1 种子的选择与优化的全局性
• 2.1.1 选种目的
• 2.1.2 基于自由采样的选种方式及其代价估计
• 2.1.3 基于自由采样结果的全局性评价方法
• 2.1.4 自由采样对搜索空间的压缩作用
• 2.2 基因置换技术的进化原理与代价估计
• 2.2.1 基因置换技术的基本思想及其算法实施
• 2.2.2 一种基因置换操作的收敛特性及其代价估计
• 2.2.3 基因置换结果的精确修复与代价估计
• 2.2.4 基因置换的定精度局部优化性能及代价估计
• 2.3 育种算法的基本模型及其收敛性分析
• 2.3.1 育种算法的基本模型
• 2.3.2 育种算法的收敛性分析
• 2.4 育种算法性能的实验验证及其比较研究
• 2.4.1 育种算法的性能实验
• 2.4.2 育种算法与遗传算法的性能评判
• 2.5 小结
• 3 育种算法的实施策略及实验研究
• 3.1 种子判断准则与采样终止
• 3.2 单一种子育种模型（sBA）
• 3.2.1 定长度基因置换单种算法模型
• 3.2.2 分级基因置换单种算法模型
• 3.3 多种子平行育种模型（pBA）
• 3.3.1 平行育种算法的适用性
• 3.3.2 平行育种算法的实施
• 3.3.3 平行育种算法解的全局性评价方法
• 3.4 育种算法实验及结果分析
• 3.4.1 实验结果的评价方法
• 3.4.2 单种算法sBA实验结果及性能分析
• 3.4.3 单种cBA实验结果结果及性能分析
• 3.4.4 平行算法实验结果及性能分析
• 3.5 函数优化问题的复杂性及其构造特点
• 3.5.1 复杂函数的特征
• 3.5.2 复杂函数最优化问题的构造技术
• 3.6 结合区域压缩技术的育种算法
• 3.6.1 基于聚合特性的区域压缩技术
• 3.6.2 结合压缩操作的育种算法及其实验
• 3.7 结语
• 4 育种算法求解约束优化问题的策略及实验研究
• 4.1 约束条件的处理
• 4.2 育种算法求解约束优化问题的实验研究
• 4.3 约束优化的搜索特征及罚因子确定
• 4.3.1 可行区域的分布及罚因子的影响
• 4.3.2 罚因子的确定
• 4.4 结语
• 5 平行育种算法在多目标及敏感系统优化的应用
• 5.1 多目标优化问题
• 5.1.1 多目标优化问题的解集
• 5.1.2 帕累托（Pareto）有效解集的求取
• 5.1.3 求解Pareto有效解集的平行育种算法
• 5.1.4 算法实验和性能研究
• 5.2 敏感系统优化及其最优解的确定
• 5.2.1 过程系统单元优化模型及其敏感性
• 5.2.2 基于平均效果最优的敏感系统优化方法
• 5.2.3 敏感系统优化实施举例
• 5.3 结语
• 6 育种算法求解工程优化问题的基本流程
• 6.1 优化模型的构造和算法要求
• 6.2 育种算法的程序构成和操作步骤
• 6.2.1 育种算法程序及其内容说明
• 6.2.2 育种算法的运行前的准备工作
• 6.2.3 育种算法的运行进程
• 6.3 算法结果及其评价
• 结论和展望
• 一、结论
• 二、展望
• 创新点摘要
• 参考文献
• 附录1 实验函数列表
• 附录2 函数的复杂性分类及难度系数（φ）的参考取值方法
• 附录3 部分实验函数的难度系数（φ）和允差（δ）
• 附录4 主要符号对照表
• 攻读博士学位期间发表学术论文情况
• 致谢