極小極大問題的生物地理學優化鄰近點算法

楊國平,劉三陽,張建科

(1.西安電子科技大學數學與統計學院,陜西西安 710071; 2.西安郵電大學理學院,陜西西安 710121)

極小極大問題的生物地理學優化鄰近點算法

楊國平1,劉三陽1,張建科2

(1.西安電子科技大學數學與統計學院,陜西西安 710071; 2.西安郵電大學理學院,陜西西安 710121)

離散型非線性極小極大問題本質上為一個傳統的梯度類算法難以求解的不可微優化問題.針對每個分量函數都是凸函數的此類問題,利用熵函數法將其轉化為一個光滑的無約束凸優化問題,并將具有并行搜索機制的生物地理學優化算法和具有全局收斂性的鄰近點算法相混合,設計了一種具有全局收斂性的混合算法.為了充分發揮生物地理學優化算法的并行搜索機制和無需使用初始點的優點,該混合算法采用生物地理學優化為內層算法鄰近點算法為外層算法.數值仿真結果表明,所提算法是求解此類非線性極小極大問題的一種有效算法.

生物地理學優化;進化算法;極小極大問題;鄰近點算法

極大極小問題來源于博弈論,是一類重要的不可微優化問題,具有廣泛的應用,因此如何求解此類問題具有重要的理論意義和實際價值.求解此類問題的主要困難在于目標函數的不可微性,這就使得經典的梯度類算法難以直接使用.文獻[1]基于熵函數法將極小極大問題轉化為一個光滑優化問題進行求解.文獻[2]針對約束極小極大問題提出一種解決此類問題的可行信賴域算法.文獻[3]采用提升技術將極小極大問題轉化為無約束優化問題并設計了一個光滑化信賴域擬牛頓算法.這些算法均取得了良好的計算效果,然而,提升技術和極大熵函數法的本質優勢是將問題轉化為可微的優化問題,進而采用基于傳統的梯度類算法進行求解[1-3],這些算法依賴于初始點的選取、梯度和海森陣的計算,特別是在一些實際問題中計算量主要集中在梯度和海森陣上.

近年來,差分進化[4]、粒子群優化[5]、細菌覓食優化[6]及生物地理學優化[7]等智能優化算法因具有無需梯度信息和選取初始點的優點而得到了廣泛應用.生物地理學優化算法(Biogeography-Based Optimization,BBO)是模擬生物物種在各棲息地之間遷入、遷出及消亡過程而提出來的一種智能優化算法[7].BBO算法由于進化機理的新穎性,近幾年已經得到了極大的發展,其優化性能已被大量標準測試函數和實際應用問題所檢驗[7-9].目前,BBO算法已成功應用于圖像處理、天線優化、混沌系統參數估計等領域[10-11].近年來,將各類智能優化算法與極大熵相結合來求解極大極小問題已受到一些研究者的關注.文獻[12]提出了一種粒子群算法與極大熵函數法相結合的混合算法;在此基礎上,一些研究者還將該方法推廣到非線性l1模極小化問題和非線性互補問題上,并取得了一些成效[13].因為,這些算法屬于隨機搜索算法,本質上僅僅是依概率收斂的,熵函數僅起到將不可微優化問題轉化為可微優化問題的作用;因此,算法不能保證100%收斂到問題的全局最優解.

筆者以每個分量函數均為凸函數的離散型非線性極小極大問題為研究對象.首先,采用熵函數法給出極小極大問題一個無約束的光滑逼近子問題;然后,將生物地理學優化算法作為內層算法,鄰近點算法作為外層算法,構造出100%收斂的生物地理學優化-鄰近點混合算法.文中選取幾個典型的離散型非線性極小極大問題進行測試,測試結果表明,該算法是求解此類問題的一種有效算法.

1　離散型非線性極小極大問題的轉化

一般的離散型非線性極小極大問題表示如下:

其中,fi(x),x∈D?Rn,(i=1,2,…,m,m≥2)為可微凸函數.因目標函數f(x)的不可微性使得該問題成為一個復雜的非光滑凸優化問題.采用熵函數作為光滑技術將該離散型非線性極小極大問題轉化為一系列光滑的逼近子問題.

定理1 對任意x∈D?Rn,函數Fp(x)與f(x)在D上滿足[12]:

即當p→+∞時,Fp(x)在D上一致收斂到f(x).

定理2 對任意x∈D?Rn,若fi(x)中存在一個嚴格凸函數,則Fp(x)滿足如下性質:

(1)函數Fp(x)是嚴格凸的可微函數;

(2)函數Fp(x)隨參數p的增大而減小,且Fp(x)從上方一致逼近f(x);

(3)Fp( x)與f(x)之間的誤差不超過(ln m)p.

定理1給出了極大熵函數逼近目標函數時產生的誤差,當控制參數p充分大時,就可以用極大熵函數Fp(x)替代目標函數f(x);定理2表明極大熵函數與目標函數具有相同的凹凸性.這就為將離散型非線性極小極大問題轉化為一個光滑優化問題提供了堅實的理論基礎.控制參數p取值適當大時即可保證具有較高的求解精度.例如,若m=3,取p=103,此時計算誤差就不會超過ln3×10-3.

2　生物地理學優化鄰近點混合算法

2.1生物地理學優化算法

BBO算法主要由遷移算子(Migration operator)和變異算子(Mutation operator)兩個算子組成,它們分別模擬了生物地理學中物種在棲息地之間的遷移、突變及其消亡過程.算法的基本原理是將種群中的每個個體模擬成一個棲息地(habitat),采用該棲息地的適宜度指數(Habitat Suitability Index,HSI)對個體進行評價,將刻畫該棲息地的特征變量(如氣候、植被、降雨量等因素)定義為適宜度索引變量(Suitable Index Variable,SIV)用來表示自變量,并以此設計了個體遷移算子(Habitat migration)和個體變異算子(Habitat mutation),使得不同個體間可以進行信息共享,從而獲得問題的最優解.個體的適宜度指數HSI越高,候選解越好,反之亦然.適宜度指數高的個體以更大的概率共享自己的特征,而適宜度指數低的個體以更大的概率接受此特征.

BBO算法中,每個棲息地具有各自的遷入率λ和遷出率μ.棲息地遷入率越高,表明棲息地所含物種數越少,當該棲息地中的物種數目為0時,該棲息地λ=I,μ=0.每個棲息地的λ和其具有的物種數目成反比而μ和物種數目成正比,當該個體中的物種數目達到最大時,此時,λ=0,μ=E,I,E分別表示最大遷入率和遷出率.設BBO算法種群中第k個個體包含k個物種時,則常用的線性遷移公式為

其中,n表示該個體所能容納的最大物種數,根據生物地理學的不同數學模型,可以得到不同的遷移公式,通常考慮最大遷入率和最大遷出率相等的情形.遷移算子就是基于遷移公式的個體特征交換方法,它使BBO算法具有很強的開發能力,詳見文獻[7].

BBO算法中,變異算子根據棲息地所含物種數量k的概率以隨機方式對其特征變量進行變異運算,用以增加種群的多樣性.生物物種數量的概率大,意味該棲息地的生態系統處于一個相對平衡的狀態,發生突變的可能性小.反之,生物物種數量概率較少,棲息地的生態系統處于不穩定狀態,棲息地容易受外突發事件的影響,發生突然變異,從而導致棲息地的生物物種數量急劇增多或減少.因此,種群中第k個個體的變異概率與該棲息地的數量概率成反比,其計算公式為

其中,mmax為用戶指定的變異率,并且Pmax=arg max Pk,k=1,2,…,n,是指棲息地的種群概率的最大值.

變異算子可以增加種群的多樣性,從而增強算法的全局搜索性能.

2.2鄰近點算法

鄰近點算法(Proximal Point Algorithm,PPA)是求解凸優化問題的一類基本方法.近年來,一些研究者從理論和算法設計兩個方面對PPA算法進行了深入的研究[14-16].

考慮以下無約束凸優化問題:

其中,f(x)為閉正則凸函數.

采用鄰近點算法求解式(5),其迭代序列{xk}由如下式子產生:

其中,x0∈Rn,為任意選取的初始點,{λk}為正值有界序列,D(x)為距離函數.早期的鄰近點算法常采用歐氏距離函數,近年來,Bregman函數、類似熵函數等滿足凸性的距離函數相繼被提出來.根據不同的距離函數可以設計不同類型的鄰近點算法,對凸優化問題,鄰近點算法產生的迭代序列{xk}收斂于問題的全局最優點,詳細內容見文獻[14].

2.3生物地理學優化鄰近點混合算法

針對離散型極小極大問題,采用生物地理學優化算法求解臨近點子問題式(6),將其嵌入到臨近點算法中設計出生物地理學優化-鄰近點混合算法.

2.3.1混合算法的主要步驟

步驟1 給定初始點x0,控制參數p,正數λ0,置k:=1;

步驟2 執行BBO算法求解鄰近點子問題,得到xk+1;

步驟3 檢驗是否滿足算法終止條件,若是,算法停止;否則,置k:=k+1,轉步驟2.

2.3.2生物地理學優化算法

步驟1 隨機生成初始種群;

步驟2 計算每個個體的適宜度指數(HSI),對問題式(1),其適宜度指數為,此處的距離函數也可以使用其他距離;

步驟3 計算每個個體的種群數k,遷入率λ和遷出率μ;

步驟4 基于遷入率λ和遷出率μ對種群中進行個體的遷移運算;

步驟5 用變異算子對種群中的個體進行變異;

步驟6 采用精英選擇策略保留最好個體;

步驟7 如果終止條件滿足,則停止;否則,返回到步驟2執行下一次的迭代.

2.3.3兩點說明

(2)由于鄰近點算法的全局收斂性,內層生物地理學優化算法只需求得鄰近點子問題的近似最優解,因此,其種群規模和迭代次數不必選取得太大.

3　數值實驗

為了檢驗所提生物地理學優化-鄰近點算法(記為PPBBO)的有效性,采用4類典型的測試函數進行測試并與標準的生物地理學優化算法和經典的梯度類算法進行比較.在MatlabR2008a編程環境下,采用Intel (R)Core(TM)i3-3110M,2.40 GHz CPU內存2 GB的微機進行實驗.PPBBO和標準BBO算法的參數設置如下:種群規模:PN=5D;最大遷入概率I=1;最大遷出概率E=1;變異率mmax=0.05;求解精度ε=10-6;光滑參數p=106;最大迭代次數(MaxIter)為100.算例1和算例2的每個變量搜索范圍分別為[-2,2]和[-3,3];初始點x0分別為(0.3,0.5)和(0.5,0.5,1,-0.5).算例3和算例4的每個變量搜索范圍均為[-5,5].經典梯度類算法選取文獻[5]中的信賴域牛頓共軛梯度算法(記為TRNCG).為公平比較起見,采用與文獻[3]中相同的光滑函數,對算例3和算例4中不同維數和函數個數進行仿真.各算法獨立運行30次,統計它們的運行時間和目標值,仿真結果見表1.

表1　算法PPBBO和其它算法的統計結果

問題2 考慮如下非線性極小極大問題:

已知最優解和最優值分別為x*=(0,1,2,-1)T,f(x*)=-44.

從表1可以看出,隨著極小極大問題規模的增大,PPBBO、TRNCG及標準BBO在相同的精度要求下,算法耗費時間越來越長,BBO算法對同樣問題規模耗費時間大概是PPBBO兩倍以上;而對例3和例4問題維數不超過80時,PPBBO和TRNCG算法耗時相差無幾,但當維數超過100時,PPBBO耗時接近TRNCG的兩倍.從這幾個典型的數值算例說明,PPBBO算法在一定程度上綜合了經典算法在迭代過程每一步都取最優的優點,改善了隨機搜索的盲目性;同時將隨機算法多點搜索優點引入經典算法,使得經典算法在一定程度上放寬對初始點的苛刻要求.

4　結束語

采用熵函數法將一類每個分量函數都是凸函數的離散型非線性極小極大問題轉化為一個可微的優化問題,并將生物地理學優化算法與鄰近點算法相混合提出了求解此類問題的一種新的混合算法.新算法具有智能算法的并行性和鄰近點算法的全局收斂性的兩個優點.數值算例仿真結果表明,在計算的精度方面與文獻[3]所得結果相當,并且當控制參數p足夠大時,所得結果與理論值趨于一致.為了與傳統的優化算法作比較研究混合算法的性能,采用分段多項式光滑函數為光滑化函數進行試驗,新算法在求解時間上比標準BBO算法有及大的降低,在精度上和TRNCG算法相差無幾,在計算成功率上達到100%.以上指標表明了新算法求解此類非線性極小極大問題的有效性.

[1]黃震宇,沈祖和.解一類非線性極大極小問題的熵函數方法[J].科學通報,1996,41(17):1550-1554. HUANG Zhenyu,SHEN Zuhe.Entropy Function Method for Solving a Class of Nonlinear Minimax Problem[J]. Chinese Science Bulletin,1996,41(17):1550-1554.

[2]歐宜貴,鄧謀杰,洪世煌.一類極大極小優化問題的信賴域算法[J].工程數學學報,2004,21(8):41-57. OU Yigui,DENG moujie,HONG Shihuang.Trust Region Algorithm for a Class of Minimax Optimization Problems [J].Journal of Engineering Mathematics,2004,21(8):41-57.

[3]YE F,LIU H W,ZHOU S S,et al.A Smoothing Trust-region Newton-CG Method for Minimax Problem[J].Applied Mathematics and Computation,2008,199(2):581-589.

[4]李蕊,史小衛,徐樂,等.競爭差分進化算法及其在共形陣綜合中的應用[J].西安電子科技大學學報,2012,39(3): 114-119. LI Rui,SHI Xiaowei,XU Le,et al.Synthesis of a Conformal Antenna Array Using the Competition Differential Evolution Strategy[J].Journal of Xidian University,2012,39(3):114-119.

[5]常磊,顧華璽,張之義,等.一種粒子群優化的用戶優先級虛擬網絡映射算法[J].西安電子科技大學學報,2015,42(1):16-22. CHANG Lei,GU huaxi,ZHANG Zhiyi,et al.Particle Swarm Optimization User-priority Virtual Network Embedding Algorithm[J].Journal of Xidian University,2015,42(1):16-22.

[6]姜建國,周佳薇,鄭迎春,等.一種自適應細菌覓食優化算法[J].西安電子科技大學學報,2015,42(1):75-81. JIANG Jianguo,ZHOU Jiawei,ZHENG Yingchun,et al.Adaptive Bacterial Foraging Optimization Algorithm[J]. Journal of Xidian University,2015,42(1):75-81.

[7]SIMON D.Biogeography-based Optimization[J].IEEE Transactions on Evolutionary Computation,2008,12(6):702-713.

[8]MA H P,DAN S,FEI M R,et al.Hybrid Biogeography-based Evolutionary Algorithms[J].Engineering Applications of Artificial Intelligence,2014,30:213-224.

[9]GONG W Y,CAI Z H,LING C X.DE/BBO:A Hybrid Differential Evolution with Biogeography-based Optimization for Global Numerical Optimization[J].Soft Computing,2011,15(4):645-665.

[10]鄭肇葆.生物地理學優化(BBO)在圖像分割中的應用[J].武漢大學學報:信息科學版,2011,36(8):932-935. ZHENG Zhaobao.Application of Biogeography-based Optimigation to Image Segmentation[J].Geomatics and Information Science of Wuhan University,2011,36(8):932-935.

[11]WANG L,XU Y.An Effective Hybrid Biogeography-based Optimization Algorithm for Parameter Estimation of Chaotic Systems[J].Expert Systems with Applications,2011,38(12):15103-15109.

[12]周暢,張建科.一類非線性極小極大問題的粒子群-鄰近點算法[J].計算機工程與應用,2012,48(36):19-22. ZHOU Chang,ZHANG Jianke.Particle Swarm Optimization-proximal Point Algorithm for a Class of Nonlinear Minimax Problems[J].Computer Engineering and Applications,2012,48(36):19-22.

[13]雍龍泉,劉三陽,張建科,等.基于差分算子的和聲搜索算法求解非線性l1極小化問題[J].蘭州大學學報:自然科學版,2013,49(4):541-546. YONG Longquan,LIU Sanyang,ZHANG Jianke,et al.Improved Harmony Search Algorithm with Differential Operator for Nonlinear l1Norm Minimization Problems[J].Journal of Lanzhou University(Natural Sciences),2013,49(4):541-546.

[14]DONG Y D.The Proximal Point Algorithm Revisited[J].Journal of Optimization Theory and Applications,2014,161(2):478-489.

[15]YAO Y H,SHAHZAD N.Strong Convergence of a Proximal Point Algorithm with General Errors[J].Optimization Letters,2012,6(4):621-628.

[16]HARE W L,LUCET Y.Derivative-free Optimization via Proximal Point Methods[J].Journal of Optimization Theory and Applications,2014,160(1):204-220.

(編輯:王 瑞)

Biogeography based optimization-proximal point algorithm for nonlinear minimax problems

YANG Guoping1,LIU Sanyang1,ZHANG Jianke2
(1.School of Mathematics and Statistics,Xidian Univ.,Xi’an 710071,China; 2.School of Sciences,Xi’an Univ.of Posts and Telecommunications,Xi’an 710121,China)

Concerning the discrete nonlinear minimax problems with the convex function as each of its components,a new method,called the biogeography based optimization-proximal point algorithm,is presented.By using maximum-entropy methods,the minimax problem is transformed into the unconstrained optimization problem of the smooth function.The algorithm employs the proximal point algorithm as the outer algorithm,and the biogeography based optimization as the internal algorithm.The proposed algorithm which resolves several minimax problems is global convergent.Preliminary numerical experiments show that the proposed algorithm is an effective algorithm for nonlinear minimax problems.

biogeography based optimization;evolutionary computation;minimax problems;proximal point algorithm

O224

A

1001-2400(2016)05-0088-05

10.3969/j.issn.1001-2400.2016.05.016

2015-07-28 網絡出版時間:2015-12-10

國家自然科學基金資助項目(61373174,71271165);陜西省教育廳自然科學專項基金資助項目(2013JK1130,11JK1051);中央高校基本科研業務費專項資金資助項目(JB140705,2014GXNSFBA118023)

楊國平(1975-),男,副教授,碩士,E-mail:guoping02@126.com.

網絡出版地址:http://www.cnki.net/kcms/detail/61.1076.TN.20151210.1529.032.html