求解非線性極大極小問題的一種新的混合算法

劉國志

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

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

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

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

1.1 粒子群算法

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

式中：k表示迭代次數，c1,c2為學習因子，rand(·)，Rand(·)是[0,1]區間的隨機數，為慣性權重。

1.2 可行基規則

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

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

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

當一個是可行解，另外一個是不可行解時，可行解優先；

當兩個解都是可行解時，目標函數值小的優先；

當兩個解都是不可行解時，約束偏差函數值小的優先。

關于第i個例子曾經達到的最好位置 pi和所有粒子的歷史最好位置gbest，在每一代按著上述規則進行更新。

1.3 新的混合算法

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

混合算法：

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

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

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

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

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

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

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

2 實例分析

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

表1 例1的計算結果Tab.1 Computable result for example 1

表2 例2的計算結果Tab.2 Computable result for example 2

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

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

3 結論

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

［1］李興斯.解非線性極大極小問題的凝聚函數法［J］.計算結構力學及其應用，1991（1）：85-91.

［2］雍龍泉，孫培民，張建科.一類非線性極大極小問題的極大熵社會認知算法［J］.計算機工程與應用，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.