大规模全局优化问题的算法研究

发布时间：2020-07-23 13:37

【摘要】：社会生产、生活中的很多问题都可以通过建模为最优化问题加以解决。其中有些问题包含大量的参数或者决策变量,这类问题可以建模为大规模全局优化问题来解决。大规模全局优化问题指的问题的维度非常高(参数或决策变量的个数非常多)的一类优化问题。目前,在大规模全局优化问题的最新测试集中,每个测试问题的维度为1000维。大规模全局优化问题是目前存在的一类非常复杂、难以解决的问题,其面临的主要困难有:1)由于问题的维度升高导致搜索次数指数级升高,使算法无法在有限的时间(计算资源)内有效探测巨大的搜索空间;2)很多大规模问题非凸、不可微,使很多经典有效的算法无法应用到此类问题上;3)随着问题维度的升高,问题的局部最优解的数目增多,导致算法难以从局部最优解跳出,从而难以找到全局最优解。此外,现有的大多数优化算法仅对中小规模的问题有效。目前,解决大规模全局优化问题的一种有效方式是基于分解的协同进化方法。这类方法的思路是使用分而治之的策略,通过设计高效的分组方法将大规模问题进行分解,然后对分解后的子问题在协同进化框架下使用进化算法加以解决。在这种解决框架下,分组算法的优劣严重制约着大规模优化算法的效果。除了基于分解的协同进化算法之外,求解大规模全局优化问题的另一类算法不显式的分解问题,而是通过设计或结合多种高效的搜索算法来实现。论文针对目前大规模全局优化问题的研究现状和存在的问题,提出了新的解决方案。本论文的主要工作和创新点如下:1.很多优化问题包含数目众多的局部最优解,这使得优化算法经常会陷入到某些局部最优解无法跳出,从而无法找到问题的全局最优解。针对这个问题,我们设计了一种无参数的辅助函数来帮助算法跳出局部最优解。结合辅助函数方法和进化算法,设计了一个求解小规模全局优化问题的新算法。实验表明,该辅助函数方法是有效的。2.填充函数方法通过在算法当前求得的局部最优解处构造一个填充函数,帮助算法不断跳出当前局部最优解进入另一个更优的局部最优解的邻域。我们设计了一个不带任何参数,并且是连续可微的填充函数,克服了现有的填充函数方法的两个主要缺陷:带有较难调节的参数、不可微等问题。基于该填充函数设计了一个可以求解中小规模全局优化问题的算法。该算法在常用的函数测试集上进行了实验,和最新算法的对比结果表明了该填充函数算法更高效。3.协同进化方法是目前求解大规模全局优化问题的一类最常用的方法。在该框架下,算法通过设计有效的分组方法将大规模问题分解为多个小规模问题分别解决。针对大规模问题的分组方法存在计算量大、分组精确度不够高的问题,本文设计了一种基于表达式的白盒分组方法。该方法可以检测大规模问题的可分性,并分解可分的大规模问题。基于该分组方法,本文设计了一种求解大规模全局优化问题的新算法。该算法在最新最难的大规模测试集上进行了实验,并在可扩展的测试集上做了扩展到2000维和5000维的实验,实验结果表明该算法是有效的。4.针对大规模问题的另一个困难:维度高、搜索空间大导致算法无法在给定的时间或计算资源的条件下有效搜索巨大的空间,提出了一种自适应的离散扫描法。为了更加高效的分配有限的计算资源以便取得更好的优化效果,我们提出了一个自适应分组搜素方法。该方法根据分组的贡献度优先优化贡献度大的分组并且根据贡献度的不同自动分配不同的计算资源。结合基于表达式的分组方法本章提出了一个求解大规模全局优化问题的新算法。该算法和当前最新、结果最好的算法做了对比,实验表明该算法是有效的。5.针对大规模问题中最难的一类问题:不可分的大规模问题,提出了一种基于贡献度的分组方法。该方法可以合理、有效地将不可分的大规模问题分解为中小规模的问题,降低了问题的难度。并设计了一种可以高效解决大规模全局优化问题的新算法:基于贡献度分组的两阶段混合优化算法。通过在最新最难的大规模测试集上的实验,并且与最新、结果最好的一些算法的比较,表明新算法是目前结果最好的算法。
【学位授予单位】：西安电子科技大学
【学位级别】：博士
【学位授予年份】：2018
【分类号】：O224

【相似文献】