全局优化的若干随机性算法

论文摘要

在求解实际问题时,一般建立的数学模型要么维数高,要么没有好的解析性质或解析性质难以获知,因此确定性全局优化算法很难或不能求解这些问题。当问题的规模增大时,其局部最优解的个数一般会急剧增加,从成千上万个局部最优解中找出全局最优解是极有挑战性的事情。随着以遗传算法为代表的随机性优化算法的出现,确定性算法中存在的困难问题得到很好的解决。这些随机性算法一般起源于对自然现象或社会行为的模拟,可以很好地解决高维、多态、噪声、不可微等问题。其最大的特点是对优化函数的解析性质要求很低,甚至可以没有显式的解析表达式。然而,由于随机技术的使用、理论研究的落后,因此设计高效求解高维困难复杂问题的鲁棒算法成为一个重要的研究课题。本文以无约束全局优化问题为研究对象,以提高算法的通用性、高效性和鲁棒性为主要目标,提出了几种求解全局优化问题的随机性算法,主要工作如下:（1）借鉴确定性算法的优点,设计了两类混合遗传算法。一是利用遗传算法繁殖算子的随机性和信赖域方法求解二次优化问题的高效性,提出了一种信赖域遗传算法,算法能够克服信赖域方法的缺点,同时能够有效求解一类欺骗性问题。通过数值试验说明了算法的有效性;二是针对传统区间优化算法求解高维问题耗时的缺点,将区间算法和遗传算法进行融合,提出了一种区间遗传算法。在每一次迭代中,该算法一方面利用区间算法的分支定界为遗传算法提供一个逐渐缩小的搜索区域,另一方面将遗传算法获得的当前全局最优值作为全局最优值的一个上界,用其删除工作集中不包含全局最优解的区间,加速算法的收敛。数值试验表明该算法相比传统区间优化算法更加有效,而且随着问题维数的增大,算法的高效性更加明显。（2）常用的Moore—Skelboe规则和Hansen规则保证了区间算法的可靠性。但是随着问题维数增大,耗时、内存不足成为区间算法最大的瓶颈,构建新的区间选择规则成为一个重要的解决途径。一个好的区间选择规则会大大降低计算耗时,同时也会保证可靠性,受Casado选择规则的启示,提出了一种新的区间选择规则,该规则利用了Casado等人提出的拒绝指标,在每次选择时只选择出不超过一个常数的区间,使问题维数增大时,算法的复杂度不会过度增大。基于提出的区间选择规则,给出了一种区间优化算法。大量的数值试验表明该算法在可靠性和收敛速度上均表现出明显优势,同时将100维Michalewicz基准测试函数的已知全局最优值-99.2784改进为-99.3289。（3）为了改善差分进化算法的求解性能,提出一种新的混合差分变异策略。该策略将种群中的每一个个体视作带电粒子,利用粒子所带的电荷量以及粒子之间的吸引排斥机制确定个体移动方向和位移大小。该策略会使个体在其它三个个体施加于它的力的方向上自适应地移动,从而避免比例因子设置的麻烦。数值试验表明基于该策略的差分进化算法能很好平衡全局搜索和加速收敛之间的矛盾。（4）合适的参数赋值常会大大改善差分进化算法的求解性能,但是如何赋值并非易事。推荐的参数设置常常使得算法在某方面优越,而在另一方面却表现逊色。借鉴类电磁机制算法中带电粒子之间的吸引和排斥机制以及用于工程设计的Taguchi方法的基本思想,提出了三种免参差分进化算法,算法消除了比例因子F和交叉概率Cr,仅有唯一的参数:种群规模POP,数值试验表明所提出的算法具有更好的求解性能。（5）传统Taguchi方法中信噪比一般是将零作为质量特征数的期望值,如果用具有传统Taguchi方法的进化算法求解具有零最优值的优化问题,则显得不合理!因为这种方法默认了优化问题的全局最优解为零。基于此,提出了一种修改的免参数差分进化算法。该方法是（4）中方法的改进,对20个标准测试函数的数值实验表明,算法能够有效求解30维、100维的问题,而且优于相比较的其它算法。同时将100维Michalewicz基准测试函数已知全局最优值-99.3289改进为-99.61225。

论文目录

• 摘要
• ABSTRACT
• 表格
• 插图
• 算法
• 第一章 绪论
• 1.1 全局优化问题
• 1.2 全局优化研究方法
• 1.2.1 确定性算法
• 1.2.2 随机性算法
• 1.3 随机性算法的研究特点
• 1.4 随机性算法的研究现状
• 1.5 内容安排
• 第二章 混合遗传算法
• 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.2.5 算法（Ⅲ）
• 2.3 本章小结
• 第三章 基于新的区间选择规则的区间全局优化算法
• 3.1 相关知识
• 3.2 区间选择规则
• 3.2.1 Casado启发式选择规则
• 3.2.2 新选择规则的基本思想
• 3.3 算法描述
• 3.4 数值试验
• 3.4.1 IGA和HTGA、EABLL之间的性能比较
• 3.4.2 IGA和FIOA之间的性能比较
• 3.4.3 Michalewicz函数最优值的改进
• 3.5 本章小结
• 3.6 测试函数
• 第四章 差分进化算法
• 4.1 标准差分进化
• 4.2 差分进化新策略
• 4.2.1 相关知识
• 4.2.2 新策略的基本思想
• 4.2.3 数值试验
• 4.3 免比例因子的差分进化算法
• 4.3.1 免参数F的基本思想
• 4.3.2 DE1/F和DE2/F的数值试验
• 4.4 几乎免参差分进化算法
• 4.4.1 Taguchi方法
• 4.4.2 两水平正交数组的构造
• 4.4.3 免参数Cr的思想
• 4.4.4 FDE性能测试
• 4.5 修改的免参数差分进化
• 4.5.1 改进FDE的基本思想
• 4.5.2 MFDE和BBDE之间性能比较
• 4.5.3 参数λ的研究
• eva在MFDE中的作用'>4.5.4 f_eva在MFDE中的作用
• 4.5.5 Michalewicz函数最优值的进一步改进
• 4.6 本章小结
• 结束语
• 致谢
• 参考文献
• 在读博士期间撰写（发表）的论文
• 参加的科研项目