一种求解一维全局优化问题的重点取样统计模拟算法

曾 鑫,丁卫平

(1.福州大学 数学与计算机科学学院,福建 福州 350108;2.湖南理工学院 数学学院,湖南 岳阳 414006)

0 引言

1 基本概念

2 重点取样统计模拟算法

下面证明ISSM 算法的全局收敛性.

由于λB是常数,所以易得.

3 数值实验

为了检验ISSM 算法的有效性,再来比较ISSM 算法和MPAS 算法在文[10]中构造的系列算例下的数值表现.该系列算例如下:令,

我们在图1 中给出该算例的部分函数图.实验环境配置为MATLAB R2018a,Intel(R)Core(TM)i7-6500U CPU @2.50GHz,8.00GB RAM.用rk表示的全局鲁棒常数,从文[10]中可以知道r0=1,,且.

图1 部分测试函数图象

为了充分比较ISSM 算法和MPAS 算法,我们保留了文[10]中MPAS 算法的一些初始值设置,分别为N=100,ε=1.0 ×10-7,α=0.85,β=0.90,q=6.实验最终结果(见表1)是ISSM 算法与MPAS 算法在每个算例中各运行20 次所取的平均值.表1中err 表示算法得到的解与最优解的误差即,其中x*表示问题的全局最优解;iter 表示迭代次数;Nf表示目标函数的调用次数;cpt 表示运行时间.

由表1的实验数据可以看出,在函数0～8ff上,ISSM 算法与MPAS 算法保持了几乎一致的解的精确度,但所需的函数调用次数更少,所消耗的时间也更少,因此ISSM 算法在此算例中的采样效率更高,能够更准确、更快速地获得最优值点,说明保留精英集合这一策略能够充分保留重要的样本点.在函数f9、f10上,MPAS 算法表现得更好,这是因为函数f0到f10的鲁棒常数是逐渐变小的[10],在f9、f10的鲁棒常数.充分小的情况下,需要采样更多的点才能达到最优值对应的水平集,而ISSM 算法在每步迭代保留精英样本使得每次迭代的新采样点变少,所以会花费更多的迭代步以保证充足的采样点数,因此在函数f9、f10上性能比MPAS 方法差.

表1 ISSM 算法与MPAS 算法的实验数据比较

4 总结

本文提出一种重点取样统计模拟算法用于求解一维无约束全局优化问题,并且在一定条件下证明了算法的收敛性.实验结果表明,所提出的ISSM 算法在目标函数的鲁棒常数大于某个常数时,比已有的MPAS 算法在计算时间和函数调用次数等性能上有一定提升.