劉國志

（遼寧石油化工大學(xué) 理學(xué)院，撫順 113001）

考慮如下的極大極小問題：

其中fi(x)(i =1,2,…,m ) 為變量 x ∈Ω?Rn的非線性光滑實值函數(shù)。由于目標(biāo)函數(shù)是一個不可微函數(shù)，所以該問題是一個較為復(fù)雜的不可微優(yōu)化問題。非線性極大極小問題由于其在工程設(shè)計、電子線路規(guī)劃、方程組求解、數(shù)據(jù)擬合以及多目標(biāo)優(yōu)化中有著廣泛應(yīng)用，受到了人們廣泛關(guān)注。關(guān)于它的求解方法較多，較為流行的有兩類：一是把問題（1）轉(zhuǎn)化為非線性規(guī)劃問題

1 非線性極大極小問題的新的混合算法

1.1 粒子群算法

令n表示搜索空間的維數(shù)，xi=(xi1,xi2,…,xin)表示微粒i當(dāng)前的位置，pi=(pi1,pi2,…,pin)表示微粒i曾經(jīng)達(dá)到的最好位置。種群中最優(yōu)微粒的序號用g表示，微粒i的速度用Vi=(vi1,vi2,…,viD)表示。每個微粒根據(jù)（2）式來更新自己的速度和位置：

式中：k表示迭代次數(shù)，c1,c2為學(xué)習(xí)因子，rand(·)，Rand(·)是[0,1]區(qū)間的隨機(jī)數(shù)，為慣性權(quán)重。

1.2 可行基規(guī)則

眾所周知，懲罰函數(shù)法由于其簡單且易實施一直是最流行的約束處理技術(shù).問題（2）的精確罰函數(shù)可構(gòu)造為：

稱viol(x)為約束偏差函數(shù)，其中M是一個適當(dāng)大的正數(shù).

由于在懲罰函數(shù)中同時考慮了目標(biāo)函數(shù)和約束偏差函數(shù)，因此這種方法表現(xiàn)好壞與懲罰因子的選取有著直接的關(guān)系.然而選擇適當(dāng)?shù)牧P因子一般不是一件容易的事情，它與所討論的問題有關(guān).為了避免罰因子的選取，本文采用文［3-4］所提出的可行基規(guī)則處理約束條件，具體敘述如下.

當(dāng)一個是可行解，另外一個是不可行解時，可行解優(yōu)先；

當(dāng)兩個解都是可行解時，目標(biāo)函數(shù)值小的優(yōu)先；

當(dāng)兩個解都是不可行解時，約束偏差函數(shù)值小的優(yōu)先。

關(guān)于第i個例子曾經(jīng)達(dá)到的最好位置 pi和所有粒子的歷史最好位置gbest，在每一代按著上述規(guī)則進(jìn)行更新。

1.3 新的混合算法

混合算法把微粒群算法全局尋優(yōu)性和Hooke-Jeeves方法的快速收斂性結(jié)合起來，利用可行基規(guī)則，避免了懲罰函數(shù)法的缺點，且計算結(jié)果表明了Hooke-Jeeves方法的快速收斂性和微粒群算法的可靠性都得到了進(jìn)一步的改善。

混合算法：

第1步：隨機(jī)初始化一群微粒的位置和速度；

第2步：以z為評價函數(shù)，分別對每個微粒求問題（2）目標(biāo)函數(shù)值；

第3步：以當(dāng)前最好微粒位置 pg為初始點，使用Hooke-Jeeves搜索法進(jìn)行優(yōu)化計算求出（4）式的最優(yōu)解x*，并令 pg=x*；

第4步：根據(jù)式（3）更新每個微粒的速度和位置；

第5步：對每個微粒，將其經(jīng)歷過的最好位置pbest按可行基規(guī)則更新；

第6步：對每個微粒，將其全局所經(jīng)歷的最好位置 pg按可行基規(guī)則更新；

第7步：如果沒有達(dá)到結(jié)束條件（通常為足夠好的函數(shù)值或達(dá)到一個預(yù)先給定的最大迭代次數(shù)或最優(yōu)解停滯不再變化），則返回第2步。

2 實例分析

為了測試本文算法的求解性能，下面選擇兩個例子進(jìn)行數(shù)值計算，其參數(shù)設(shè)置為：

表1 例1的計算結(jié)果Tab.1 Computable result for example 1

表2 例2的計算結(jié)果Tab.2 Computable result for example 2

本例的極大極小最優(yōu)解為 x*=[1,1]T，f(x*)=f1(x*)=f2(x*)=f3(x*)=2。

從表1和表2可以看出，本文提出的算法的計算結(jié)果較文［1］和文［2］好的多，而且基本上達(dá)到了理論值。

3 結(jié)論

非線性極大極小問題是一類經(jīng)常出現(xiàn)在工程、電子線路規(guī)劃方程組求解數(shù)據(jù)擬合以及多目標(biāo)優(yōu)化中的一類非光滑優(yōu)化問題。因此求解非線性極大極小問題精度較高的解具有非常重要的現(xiàn)實意義。本文提出了一個求解這類問題的一個新的算法—Hooke-Jeeves搜索法和與可行基規(guī)則相結(jié)合的微粒群算法的混合算法。通過實例計算結(jié)果表明，這種新的算法在收斂速度和求解精度上都有了很大的提高。因此可以應(yīng)用到工程實際中。

［1］李興斯.解非線性極大極小問題的凝聚函數(shù)法［J］.計算結(jié)構(gòu)力學(xué)及其應(yīng)用，1991（1）：85-91.

［2］雍龍泉，孫培民，張建科.一類非線性極大極小問題的極大熵社會認(rèn)知算法［J］.計算機(jī)工程與應(yīng)用，2010，46（26）：36-42.

［3］K Deb.An efficient constraint handling method for genetic algorithms，Comput.Meth Appl Mech Eng，2000（186）：311-338.

［4］Qie He，Ling Wang.A hybrid particle swarm optimizatuion with a feasibility-based rule for constrained optimization［J］.Applied Mathematics and Computation，2007，186（2）：1407-1422.