基于分组的大规模全局优化算法研究

发布时间：2020-10-26 06:05

　　 随着计算机技术与信息科学的发展,优化问题在工程中的应用越来越广泛。如何设计一种简单高效的算法,使得它可以在有限的计算资源下求得更加精确的最优解,已经成为当前求解一个工程优化问题的热点。当前在求解大规模全局优化问题时面临的挑战主要有三方面:首先,搜索空间大,一般随着维数的增加搜索空间呈指数增长,算法陷入局部最优解可能性大。第二,求解目标复杂,现实世界中的目标函数,具有非线性、非凸、不可微等特点,很多经典的优化算法求解此类问题时面临巨大挑战。第三,局部极小点有多个,传统算法很容易陷入局部最优解。进化算法在求解过程中有很多突出的优点,如高鲁棒性、自适应性、自学习性、并行搜索、全局搜索能力强、不要求目标函数可微等,因此被广泛应用于工程优化中来求解一些复杂的优化建模问题,并在相关研究领域取得非常显著的研究成果。然而随着目标函数维数的增加,进化算法在求解过程中易陷入局部最优解,使问题的求解变得更加困难。现在的进化算法研究主要有如下挑战:1)大规模问题难以求解:由于搜索空间的急剧增大,算法性能锐减,无法得到最优解。2)早熟收敛:算法容易陷入局部最优解。针对这些挑战,本文主要做了以下几方面的工作:1.变量分组:进化算法在求解高维问题时面临巨大挑战,因此有研究者提出的基于分组的协同进化算法,把大规模问题分解成若干个不相关的子问题,再用进化算法对各个子问题独立优化,直至终止条件到达。协同进化算法的难点是分组策略的选取,本文在表达式分组的基础上,针对完全可分问题与完全不可分问题分别提出再分组策略。出于计算资源利用率最大化这一目的,针对完全不可分问题提出一种自适应混合分组方法,并依据贡献度对可分问题进行随机再分组。2.基于贡献度的迭代次数分配策略:采用进化算法对各个子分组进行优化时,各个子问题对原问题的贡献度存在一定差异。本论文针对这一问题,提出了一种量化子问题贡献度的算子,并根据贡献度对各个子问题差额分配计算资源,在子问题中形成一种竞争机制,让对原问题贡献程度更大的分组得到更多的进化次数。以达到有限的计算资源下得到更准确的解这一目的。3.针对完全可分问题的新算法:完全可分问题的求解是若干个一维问题的集合,现有的进化算法不适宜用来求解一个可分问题。本文提出了一种基于区间采样的新算法,在可行域内均匀采点,以达到探测最优解的目的,同时结合了聚类思想,以维持样本多样性,避免陷入局部最优解。在该基础上,我们构建了一种新的可分问题求解算法。4.改进的局部搜索算子:考虑到算法求解效率的问题,我们在求解过程中加入局部搜索算法,以提高算法的搜索效率,但是已有的一些局部搜索算法如牛顿法等一般要求函数可导,我们改进了一种算法,来模拟函数在某个点的下降方向,以提高算法的搜索效率。为了测试以上几个算法的性能,我们在常用的标准测试集上进行了测试,并与多个知名算法进行对比分析。结果表明,我们的算法是有效的。
【学位单位】：西安电子科技大学
【学位级别】：硕士
【学位年份】：2018
【中图分类】：TP18
【部分图文】：

幂函数图像

分组和均匀设计的混合遗传算法172）指数函数 ( ) ( 0, 1)xf x a a a 和对数函数 ( ) log ( 0)xaf x a 单调性分别如图3.2 和图 3.3 所示，从图里可以看出，指数函数和对数函数在其定义域内都是单调的，因此不影响变量相关性。图 3.2 指数函数图像 图 3.3 对数函数图像3) 六种三角函数 (sin(x ), cosx( ), taxn ( ), cxo t( ),x s ec( )x, c与sc六( )种)反三角函数(arcsinx( ), arccoxs ( ), arc xt an( ), arxc cot( ), ax rc sec( )x, a因rc为cs在c(其 )整)个定义域内都是周期函数，所以不存在单调性影响，被作用的变量会导致不可分，跟内层函数无关。(3) 特殊情况说明： 因为函数的一些性质，会导致前面两条判断准则出现失误，因此对一些特殊情况予以说明。1）合并幂函数拆分项：有些幂函数的拆分会导致判断错误，应该合并相关的部分，例如31 2f ( x ) ( x x)，根据我们的准则 2，内层函数可分，外层函数单调，变量1x 和2x 应该是可分的，但是若展开表示为3 2 2 31 1 2 2 1 2f ( x ) x 3 x x 3x x x

图 3.2 指数函数图像 图 3.3 对数函数图像3) 六种三角函数 (sin(x ), cosx( ), taxn ( ), cxo t( ),x s ec( )x, c与sc六( )种)反三角函数(arcsinx( ), arccoxs ( ), arc xt an( ), arxc cot( ), ax rc sec( )x, a因rc为cs在c(其 )整)个定义域内都是周期函数，所以不存在单调性影响，被作用的变量会导致不可分，跟内层函数无关。
【参考文献】

相关期刊论文 前1条

1 董红斌;黄厚宽;印桂生;何军;;协同演化算法研究进展[J];计算机研究与发展;2008年03期

相关博士学位论文 前1条

1 杨振宇;基于自然计算的实值优化算法与应用研究[D];中国科学技术大学;2010年

本文编号：2856607