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

劉國志

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

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

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

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

1.1 粒子群算法

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

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

1.2 可行基規(guī)則

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

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

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

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

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

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

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

1.3 新的混合算法

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

混合算法：

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

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

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

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

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

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

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

2 實例分析

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

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

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

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

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

3 結論

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

［1］李興斯.解非線性極大極小問題的凝聚函數(shù)法［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.