曾玉华

(湖南第一师范学院数理系，湖南 长沙 410205)

一种基于重点样本的积分水平集算法

曾玉华

(湖南第一师范学院数理系，湖南 长沙 410205)

以极小化相对熵(minimizes cross-entropy)技术为主要工具，提出一类求总极值的启发式随机算法——基于重点样本的积分水平集算法。数值试验结果验证了算法的有效性。

全局优化；随机型算法；重点样本；积分水平集方法

考虑下面的优化问题:

其中，D∈Rn是可行集；f是定义在D上的下半连续函数。

如果存在x*∈D，使得∀x∈D，f(x*)≤f(x)，称x*为优化问题(1)的全局最优解，f*=f(x*)为全局最优值。寻找全局最优解的优化问题称为全局优化问题。

利用问题的解析性质，通过严格的数学过程构造一个确定的收敛于全局最优解的点列来求得(1)的全局最优解的算法称为确定型优化方法[1]。常见的确定型算法有分支定界法、广义梯度方法等[2]。 随着问题的规模增大，极小点数目增加，传统的确定型优化算法，容易陷入局部极小，难以寻找到全局最优解。同时，这种算法对问题本身的依赖性非常强，初始点的选取，问题的光滑性，特别是问题的凸性，是寻找最优解的关键。而在工程和实际问题中大多不能满足确定型方法对目标函数与约束条件的解析性要求，或者根本不知道它的解析性质。因此，人们转而求助于随机型方法来寻求问题的全局最优解[3]。

1 相对熵和积分水平集算法

1.1相对熵

相对熵方法(The Cross-Entropy Method)是以色列专家R.Y.Rubinstein和De Boer等在1997年最早提出来的基于极小化的基本思想来更新取样密度的一种重点取样随机搜索算法。这种算法的主要创新在于每次取样前依照某种机制更新样本密度，使得在当前迭代中有更多的样本接近全局最优点[5]。

1.2积分水平集算法

构造如下2个序列：

Hck={x∈D：f(x)≤ck}

可以证明，在适当条件下，上述2个序列分别收敛到问题的总极值和总极值点。

一个简单基于随机取样的水平集算法描述如下：

步骤1 任取x0∈D，令c0=f(x0)，并设H0={x∈D:f(x)≤c0}，令k:=0。

步骤2 在水平集Hk+1={x∈Hk:f(x)≤ck}上随机投点，令:

ck+1=min{f(xi):xi∈Hk,i=1,2,…,N}

步骤3 判断：如果ck+1满足最优性条件，则转向下一步；否则，转向第2步。

步骤4 输出：f*=ck+1为最优值，H*=Hk+1为最优点的集合。

该算法的收敛性是显然的。但水平集Hk+1={x∈Hk:f(x)≤ck}的确定，涉及到高维不等式的求解，是一个特别困难的问题。郑权用积分水平集来替代上面那个简单的水平集，使该算法的困难在一定程度上得到了克服，但依旧存在同样的问题。邬冬华、田蔚文教授等对积分水平集算法进行了改进[6]，这种改进采用“削去山头”的方法，并且每次取样均在原始的约束集上，从而基本克服了遗漏全局最优解的问题，但却牺牲了收敛速度，甚至有因迭代计算中停止不前，而导致不能到达全局最优点的可能性。

2 基于极小化相对熵与重点取样的逼近积分水平集算法

先将文献[6]中的均值表示成:

(2)

对(2)进行变形：

步骤4 输出：令f*=ck+1为最优值，H*=Hk+1为最优点的集合。

当ε取得非常小，例如εlt;10-10，而N取得足够大时，可以认为由新算法得到的是问题(1)的全局最优解。

3 数值试验

下面4个函数均是经典的全局优化算法测试问题，笔者用此测试新算法的有效性。

问题1(Trigonometric函数)[8]

η=7μ=1ui=0.9i=1,2,…,n

(4)

问题2(Rosenbrock函数)[9]

(5)

问题3(Rastrigin函数)[10]

subject to -5.12≤xi≤5.12i=1,2,…,n

(6)

问题4(Shekel-5函数)[11]

subject to -32.195≤xi≤32.195i=1,2,…,n

(7)

上述这些函数均具有许多局部最优点，全局最优值均为0。利用笔者构造的新算法计算这4个测试问题的全局最优值，测试结果如表1。

表1 数值测试结果

表1的测试结果表明，新算法对于求解多极值问题的全局最优值是有效的。

4 结 语

结合极小化相对熵技术和积分水平集算法，提出了一种求解连续全局优化问题的基于重点样本的积分水平集算法。计算实践表明，笔者所提出的算法对于多极值优化的全局最优值问题的求解是有效的。

[1]Panos M P，Edwin R H， Hoang T. Recent developments and trends in global optimization[J].Journal of Computational and Applied Mathematics， 2000，124:209～228.

[2]袁亚湘，孙文瑜. 最优化理论与方法[M]. 北京：科学出版社，1997.

[3]Zhang L S，Ng C， Li D，etal.A new filled function method for global optimization[J]. J Global Optimization ， 2004，28: 17～43.

[4] Dzemyda G，Saltenis V，Zilinskas A. Stochastic and Global Optimization[M]. New York:Kluwer Academic Publishers， 2002.

[5]彭拯. 全局优化的水平值逼近理论与算法研究[D]. 上海:上海大学，2008.

[6]邬冬华，田蔚文. 一种修正的求总极值的积分水平集方法的实现算法收敛性[J]. 应用数学学报，2001，24(1):95～98.

[7]龚光鲁，钱敏平. 应用随机过程教程[M]. 北京：清华大学出版社， 2004.

[8]De Boer，Kroese D P. A Tutorial on the Cross-Entropy Method[J]. Annals of Operations Research， 2005，134:19～67.

[9] Brink A D，Pendock N E. Minimum Cross-Entropy Threshold Selection[J]. Pattern Recognition， 1996， 29(1):179～188.

[10]Au S K， Beck J L. Importanct sampling in high dimensions[J].Structural Safety， 2003，25:139～163.

[11] Karl-Heinz Zimmermann.Solving constrained combinatorial optimization problems via importance sampling in the grand canonical ensemble[J]. Computer Physics Communications， 2005，165: 243～259.

[编辑] 洪云飞

2009-07-23

湖南省教育厅科学研究项目(06C054)。

曾玉华(1973-),男,1995年大学毕业，硕士,副教授,现主要从事非线性规划方面的研究工作。

O224

[MR(2000)主题分类号]90C33；49K99

A

1673-1409(2009)04-N005-03