改進(jìn)單純形最優(yōu)搜索的可視化仿真與訓(xùn)練

魏曉玲(廣州工商學(xué)院 計算機科學(xué)與工程系，廣東 廣州 510850)

遺傳、模擬退火、蟻群、粒子群、神經(jīng)網(wǎng)絡(luò)以及單純形算法成為近期研究的熱點，一度成為主流尋優(yōu)方法，但由于算法自身的缺陷造成其適用范圍具有一定的局限性，如遺傳算法搜索速度慢，易出現(xiàn)早熟[1]；模擬退火算法進(jìn)入最有希望搜索的區(qū)域較慢，運算效率低[2]；蟻群算法收斂速度慢、易陷入局部最優(yōu)[3]；粒子群算法處理復(fù)雜的多峰搜索問題時容易產(chǎn)生早熟收斂[4]；人工神經(jīng)網(wǎng)絡(luò)容易出現(xiàn)難以解釋的結(jié)果[5]；單純形算法易出現(xiàn)最長邊較長，但體積已接近零的病態(tài)現(xiàn)象[6].單純形算法最早是由Splendley等[7]于1962年提出，隨后為了提高正規(guī)單純形的搜索速度，Neledr和Mead[8]在Splendley的基礎(chǔ)上于1965年提出了N-M單純形算法.單純形算法被稱為序貫性尋優(yōu)方法，即依據(jù)于上次的尋優(yōu)結(jié)果，及時調(diào)整尋優(yōu)方向和步長，其局部尋優(yōu)速度仍是某些算法所不能替代的，鑒于其優(yōu)點部分學(xué)者將單純形融入到其它算法中，如遺傳算法[9-13]、人工魚群算法[14-15]、量子粒子群算法[16-17]、自適應(yīng)步長的花朵授粉算法[18]以及人口遷移算法[19]等，并且取得了較好的效果，有效的彌補了算法的自身不足.也有大量的學(xué)者將單純形尋優(yōu)算法應(yīng)用到生產(chǎn)生活中，例如生產(chǎn)工藝試驗設(shè)計[20-24]、教學(xué)方法改進(jìn)[25]、近鄰鏈查詢[26-29]等.近期學(xué)者們研究單純形主要集中在兩方面，將單純形應(yīng)用在實驗設(shè)計中，或與其他算法融合尋優(yōu).單純形的可視化仿真的設(shè)計研究相對較少，故本研究擬借助于MATLAB軟件，實現(xiàn)單純形的可視化仿真的設(shè)計；并進(jìn)行函數(shù)仿真訓(xùn)練，驗證效果，使尋優(yōu)軌跡更直觀.

1 單純形最優(yōu)搜索數(shù)學(xué)模型

1.1 單純形簡介

正規(guī)單純形是指在S維空間中，以S+1個頂點構(gòu)成的最簡單的圖形，其尋優(yōu)過程中不是沿著一個方向進(jìn)行搜索，而是對S維空間的S+1個頂點上的函數(shù)進(jìn)行比較.丟掉最壞的點，代之以新點，從而構(gòu)成新的單純形，其尋優(yōu)過程類似下圖1.它是迭代之前，先確定最優(yōu)的方向，然后逐步向最優(yōu)逼近的過程.N-M單純形在正規(guī)單純形的基礎(chǔ)上，通過增加擴張和壓縮步驟，將正規(guī)單純形擴展至任意單純形，加速收斂速度，減少迭代次數(shù).

圖1 單純形尋優(yōu)過程模擬圖Fig.1 The simulation diagram of simplex optimization

1.2 初始單純形的構(gòu)造

初始單純形構(gòu)造過程中，由于最優(yōu)結(jié)果的方向是未知的，因此初始單純形的構(gòu)造一般設(shè)計為正規(guī)單純形.然而實際應(yīng)用中，由于各因素的量綱不同，采用統(tǒng)一的搜索步長很難滿足各因素快速收斂的需求.Long[30]在1969年提出了一種系數(shù)表構(gòu)成初始單純形的方法，但其局限性在于只能構(gòu)造10個因素以內(nèi)的單純形.也有部分研究者為了初始布點的均勻性，用均勻設(shè)計來構(gòu)造初始單純形頂點，取得了較好的應(yīng)用.而本研究主要針對函數(shù)進(jìn)行測試，不涉及到實際生產(chǎn)應(yīng)用及各因素對應(yīng)的量綱問題，故只介紹正規(guī)單純形頂點構(gòu)造方法，即單純形RS空間中多面體的每條棱長(步長a)相等，且滿足以下定義：

定義1{V1，V2，…，VS，VS+1}為RS空間的某一單純形S+1頂點的位置矢量，vi表示S個變量的取值.

定義2令S個因素各取一起始水平的點為x0，則有V1=x0.Vi=x0+z(i) (i=2，3，…，S+1)，其中z(i)為S維矢量，z(i)=[q，…，q，p，q，…，q]T，上式中：

滿足以上條件，可證明S+1個頂點的正規(guī)單純形各棱長均相同，若令初始點坐標(biāo)為V1=[v1,v2,…,vs]，則剩余各頂點的坐標(biāo)為，即初始單純形頂點：

V2=[v1+p,v2+q,…,vs+q]，

V3=[v1+q,v2+p,…,vs+q]，

………………

Vs+1=[v1+q,v2+q,…,vs+p].

1.3 單純形最優(yōu)搜索設(shè)計

Step1給定初始單純形的一個頂點V(1)及搜索步長a，依據(jù)1.2中定義2計算出初始單純形的其余頂點：V(2)，……，V(S)，V(S+1)，并計算出單純形頂點的函數(shù)值：f(V(1))，f(V(2))，……，f(V(S))，f(V(S+1)).

Step2比較單純形各頂點的函數(shù)值，確定函數(shù)最優(yōu)V(H)點，最差點V(L)點及次差V(C)點，并檢驗︱(f(V(H))-f(V(L)))︳≤ε(ε為收斂精度)，若滿足條件，則輸出最優(yōu)點為V(H)點，最優(yōu)值為f(V(H))，計算結(jié)束，若不滿足條件轉(zhuǎn)入第Setp3步反射運算.

Step3反射運算

(1)計算剔除最差點V(L)后的重心V(S+1)(H).

i=1，2，……，S+1，且i≠L.

(2)以重心點V(S+1)(H)為基本點，沿著最差點V(L)到重心點方向反射延長到反射點V(S+2)(H)，計算反射點V(S+2)(FS)坐標(biāo)及對應(yīng)的函數(shù)f(V(S+2)(FS)).

V(S+2)(FS)=V(s+1)(H)+(V(S+1)(H)-V(L))=

2V(S+1)(H)-V(L).

若f(V(S+2)(FS))>f(V(H)，則執(zhí)行擴張運算；

若f(V(L))

若f(V(S+2)(FS))

擴張運算：

V(S+2)(KZ)=V(S+1)(H)+

γ(V(S+2)(FS)-V(L))，γ=1.2～2.5.

若f(V(S+2)(KZ))>f(V(S+2)(FS))，以擴張點V(S+2)(KZ)代替最差點V(L)構(gòu)造新的單純形；否則擴張不成功，以反射點V(S+2)(FS)代替最差點V(L)構(gòu)造新的單純形，轉(zhuǎn)入Setp2中繼續(xù)最優(yōu)搜素，直至滿足收斂條件.

收縮運算：

V(S+2)(SS)=V(S+1)(H)+

δ(V(S+2)(FS)-V(S+1)(H)),δ=0～1.

以收縮點V(S+2)(SS)代替最差點V(L)，構(gòu)造新的單純形轉(zhuǎn)入Setp2中進(jìn)行最優(yōu)搜索，直至滿足收斂條件.

壓縮運算：

V(S+2)(YS)=V(S+1)(H)+

η(V(L)-V(S+1)(H)),η=0～1.

以壓縮點V(S+2)(YS)代替最差點V(L)，構(gòu)成新的單純形轉(zhuǎn)入Setp2中進(jìn)行最優(yōu)搜索，直至滿足收斂條件.

Step4若經(jīng)過有限N次迭代之后，仍不能滿足收斂，證明最優(yōu)搜索方向有誤，需要以次最差點V(G)和去除次最差點后的重心V(S+1)(G)為基本點進(jìn)行搜索，然后重復(fù)Setp2，直至滿足收斂條件.

2 可視化仿真界面的設(shè)計

2.1 設(shè)計流程(圖2)

圖2 仿真設(shè)計流程圖Fig.2 The flow chart of simulation design

2.2 可視化界面

本文借助于MATLAB軟件中的GUI設(shè)計模塊制作單純形最優(yōu)搜索界面.本界面中函數(shù)表達(dá)式采用inline函數(shù)的書寫格式，同時本界面只適用于最大結(jié)果的搜索，針對具有極小值的函數(shù)可通過函數(shù)改造使其變?yōu)榍髽O大值，仿真界面見圖3 .

圖3 單純形尋優(yōu)仿真GUI界面Fig.3 The simulation GUI interface about simplex optimization

3 仿真訓(xùn)練

3.1 測試函數(shù)

為了驗證本文算法的正確性和有效性，通過對四個包括單峰、多峰、低緯、高維的測試函數(shù)進(jìn)行仿真來驗證可視化界面及尋優(yōu)效果，測試用函數(shù)介紹如下：

函數(shù)1簡單函數(shù)：y=-(x1-1)2-(x2-1)2,x∈[-10，10]，該函數(shù)為單峰函數(shù)，該函數(shù)在x=(1,1)取得全局最優(yōu)，且最優(yōu)值y(max)=0.

函數(shù)2改造的Beale函數(shù)，由于該函數(shù)在自變量區(qū)間[-10,10]內(nèi)存在極小值，為了適應(yīng)于本可視化界面，將其改造后變?yōu)閷O大值，改造后的函數(shù)在x=(3，0.5)存在極大值，且最優(yōu)值y(max)=0，該函數(shù)的表達(dá)式為：

y=-(1.5-x1(1-x2))2-

(2.25-x1(1-x22))2-

(2.625-x1(1-x23))2,

x∈[-4.5,4.5] .

函數(shù)3改造的多峰Six Hump Camel back函數(shù)，經(jīng)改造后該函數(shù)在區(qū)間[-5，5]有六個極大值峰，且在x=(0.0898，-0.7126)處有極大值，且最優(yōu)值y(max)=1.0316，該函數(shù)表達(dá)式為

x1x2+4x22-4x24,

x∈[-5,5].

函數(shù)4改造的Colville 函數(shù)，經(jīng)改造后該函數(shù)在區(qū)間[-10,10]存在極大值，且在x=(1，1,1,1)極大值為y(max)=0，該函數(shù)表達(dá)式為：

y=-100(x2-x12)2-(1-x1)2-

90(x4-x32)2-(1-x3)-

10.1[(x2-1)2+(x4-1)2]-

19.8(x2-1)(x4-1)2,

x∈[-10,10].

3.2 測試訓(xùn)練效果

為了直觀觀察函數(shù)的極值個數(shù)，本文借助于MATLAB中mesh函數(shù)，以0.02為步長，制作了測試函數(shù)1、測試函數(shù)2及測試函數(shù)3的三維圖見圖4、圖5及圖6，從三圖可知三函數(shù)在搜索區(qū)間內(nèi)均存在極大值，滿足測試要求.

圖4 簡單函數(shù)三維圖Fig.4 The 3D graph of simple function

圖5 改造Beale函數(shù)三維圖 Fig.5 The 3D graph of transform Beale function

圖6 改造 Six Hump Camel back函數(shù)三維圖 Fig.6 The 3D graph of transform Six Hump Camel back function

對以上函數(shù)將相關(guān)參數(shù)輸入圖3中的GUI界面，經(jīng)過后臺運算輸出相關(guān)參數(shù)見表1及尋優(yōu)軌跡見圖7至圖10.從表1中可知本程序的尋優(yōu)結(jié)果與實際的最優(yōu)結(jié)果均較為接近，從圖7至圖10可以發(fā)現(xiàn)隨著迭代次數(shù)的延長(100次)尋優(yōu)結(jié)果均有向最優(yōu)結(jié)果靠近的趨勢，證明該可視化界面能適用于一般函數(shù)尋優(yōu)，從迭代次數(shù)上來看，對于單純形尋優(yōu)搜索，其收斂速度具有一定的優(yōu)勢.

圖7 簡單函數(shù)尋優(yōu)軌跡圖Fig.7 The optimization track map about simple function

圖8 改造Beale函數(shù)尋優(yōu)軌跡圖Fig.8 The optimization track map about transform Beale function

表1 函數(shù)輸入及輸出參數(shù)
Tab.1 The input and output parameters about function

函數(shù)初始頂點最優(yōu)頂點尋優(yōu)結(jié)果實際最優(yōu)最優(yōu)迭代次數(shù)函數(shù)10，00．98191，0．98191-0．0006544022函數(shù)21，12．9274，0．4879-0．0018046函數(shù)33，30．0843，-0．6691491．01721．031645函數(shù)43，3，3，30．9921，0．9985，0．9937，0．9933-0．0138075

圖9 改造Six Hump Camel back函數(shù)尋優(yōu)軌跡圖Fig.9 The optimization track map about transform Six Hump Camel back function

圖10 改造的Colville 函數(shù)尋優(yōu)軌跡圖Fig.10 The optimization track map about transform Colville function

4 結(jié)束語

尋優(yōu)算法的改進(jìn)、應(yīng)用及多種算法的融合屬于近幾年研究的熱點，其中對于單純形的研究主要集中在應(yīng)用及與其他算法的融合尋優(yōu)兩個方面，對于該算法的可視化仿真的研究較少.本研究利用MATLAB軟件設(shè)計開發(fā)改進(jìn)單純形的可視化仿真平臺，使該尋優(yōu)方法的使用及運行過程更加直觀、易實現(xiàn).后續(xù)研究主要借助于MATLAB軟件中的Mbuild-setup函數(shù)，結(jié)合實際應(yīng)用，開發(fā)改進(jìn)單純形尋優(yōu)可視化的獨立運行程序，使其使用更方便.

[1]劉建文，丁潔玉，潘坤，等.基于個體相似度的改進(jìn)自適應(yīng)遺傳算法研究[J].青島大學(xué)學(xué)報(工程技術(shù)版)，2016,31(1)：16-19.

[2]謝云.模擬退火算法綜述[J].計算機應(yīng)用研究，1999(5)：7-9.

[3]袁亞搏，劉羿，吳斌.改進(jìn)蟻群算法求解最短路徑問題[J]. 計算機工程與應(yīng)用，2016,52(6)：8-12.

[4]劉華鎣，林玉娥，張君施. 基于混沌搜索解決早熟收斂的混合粒子群算法[J].計算機工程與應(yīng)用，2006(13)：77-79.

[5]王輝.人工神經(jīng)網(wǎng)絡(luò)研究與發(fā)展綜述[J].電腦知識與技術(shù)，2008，4(3)：710-711.

[6]孔銳睿，仇汝臣，周田惠.單純形的加速算法[J].南京理工大學(xué)學(xué)報，2003,27(2)：209-231.

[7]SPLENDLEY W, HEXT G R, HIMSWORTH F R. Seqauential application of simplex designs in optim ization and evolutinary operation[J] .Technometrics, 1962(4): 441- 461.

[8]NELDER J A, MEAD R. A simplex method for function minimization[J] . Computer J, 1965, 7: 308- 313.

[9]肖宏峰，譚冠政.單純形搜索在遺傳算法中的融合研究[J].計算機工程與應(yīng)用，2008，44(18)：30-33.

[10]宋星原，舒全英，王海波，等.SCE-UA、遺傳算法和單純形優(yōu)化算法的應(yīng)用[J].武漢大學(xué)學(xué)報(工學(xué)版)，2009,42(1)：6-9,15.

[11]杜修力，崔冬，侯本偉.基于初始群改進(jìn)策略的經(jīng)驗遺傳-單純形法[J].北京工業(yè)大學(xué)學(xué)報，2014,40(12)：1876-1883.

[12]張佳程，周邵萍，蘇永升，等.基于數(shù)據(jù)融合與單純形遺傳算法的管道損傷識別[J].華東理工大學(xué)學(xué)報(自然科學(xué)版)，2015,41(1)：132-136.

[13]謝學(xué)斌，羅海霞，楊承祥，等.基于遺傳單純形算法與RBF網(wǎng)絡(luò)的地應(yīng)力場反演方法[J].鐵道科學(xué)與工程學(xué)報，2015,12(1)：72-78.

[14]張紅霞，羅毅，師瑞峰.基于單純形法的改進(jìn)型人工魚群算法[J].計算機應(yīng)用，2011,31(5)：1321-1323,1327.

[15]彭培真，俞毅，王兆嘉，等.基于單純形的改進(jìn)全局人工魚群優(yōu)化算法[J].計算機技術(shù)與發(fā)展，2015,25(8):75-79.

[16]任小康，郝瑞芝，孫正興，等.基于單純形法的量子粒子群優(yōu)化算法[J].微電子學(xué)與計算機，2010,27(1)：154-157.

[17]鄭偉博，張紀(jì)會.基于Nelder-Mead單純形法的改進(jìn)量子行為粒子群算法[J].復(fù)雜系統(tǒng)與復(fù)雜科學(xué)，2016,13(2)：97-104.

[18]肖輝輝.基于單純形法和自適應(yīng)步長的花朵授粉算法[J].計算機工程與科學(xué)，2016,38(10)：2126-2133.

[19]歐陽艾嘉，張偉偉，周永權(quán).單純形和人口遷移的混合全局優(yōu)化算法[J].計算機工程與應(yīng)用，2010,46(4)：29-31,35.

[20]胡德庚，朱云勤，王朝軍,等.基于單純形的硅鈣鉀肥制備工藝研究[J].化學(xué)工業(yè)與工程，2013,30(3)：55-59.

[21]鈕琰星，倪光遠(yuǎn)，萬楚筠,等.基于單純形-中心設(shè)計的菜籽粕生物改良菌株的復(fù)配研究[J].中國油脂，2015,40(2)：72-76.

[22]楊樹朝.基于單純形法的重介密度控制系統(tǒng)PID自尋最優(yōu)控制的設(shè)計[J].選煤技術(shù)，2016，(1)：81-83.

[23]聶強，何仁，黃永春，等.單純形重心法優(yōu)化西番蓮果汁飲料的穩(wěn)定劑配方[J].安徽農(nóng)業(yè)科學(xué)，2016,44(9)：109-111,188.

[24]何慧蓉，陳際達(dá)，陳世金，等.單純形化法研究改良型全加成PCB的銅電鍍液配方[J].電鍍與涂飾，2016,35(13)：677-680.

[25]李士森，裴俊紅.MATLAB在運籌學(xué)(單純形法)教學(xué)中的應(yīng)用[J].石家莊鐵路職業(yè)技術(shù)學(xué)院學(xué)報，2009,8(3)：108-111.

[26]張麗平，李林，李松，等.預(yù)定數(shù)據(jù)鏈規(guī)模的單純型連續(xù)近鄰鏈查詢[J].計算機工程，2012,38(10)：51-53.

[27]張麗平，李松，趙紀(jì)橋，等.受限區(qū)域內(nèi)的單純型連續(xù)近鄰查詢方法[J].計算機應(yīng)用，2014,34(2)：406-410.

[28]李松，張麗平，劉艷等.障礙物環(huán)境下的動態(tài)單純型連續(xù)近鄰查詢[J].計算機工程，2014,40(8)：52-57.

[29]李松，張麗平，朱德龍，等.動態(tài)受限區(qū)域內(nèi)的單純型連續(xù)近鄰鏈查詢方法[J].計算機科學(xué)，2014,41(6)：136-141.

[30]熊沛石.初始單純形的構(gòu)造方法[J].湖南有色金屬，1986,2(6)：42-46.