一種保證全局收斂的認(rèn)知優(yōu)化算法

王春梅,　孫家澤

(西安郵電大學(xué) 計(jì)算機(jī)學(xué)院,陜西 西安　710121)

一種保證全局收斂的認(rèn)知優(yōu)化算法

王春梅,孫家澤

(西安郵電大學(xué) 計(jì)算機(jī)學(xué)院,陜西 西安710121)

摘要:文章針對傳統(tǒng)社會認(rèn)知優(yōu)化算法全局收斂慢的問題,提出了一種保證全局收斂的認(rèn)知優(yōu)化算法。該算法應(yīng)用Tent 映射初始化知識庫,提高初始解的質(zhì)量;鄰域搜索過程采用混沌搜索,增強(qiáng)算法跳出局部最優(yōu)解的能力;通過增加混沌庫來提高搜索的遍歷性,實(shí)現(xiàn)和知識庫協(xié)同尋優(yōu),從而構(gòu)建為一種新的混沌混合認(rèn)知優(yōu)化算法；同時以Solis和Wets提出的隨機(jī)算法收斂定理為基礎(chǔ)，給出了該算法的全局收斂性證明。標(biāo)準(zhǔn)測試函數(shù)的仿真優(yōu)化結(jié)果表明,該混合算法對非線性規(guī)劃問題具有較強(qiáng)的求解能力,算法尋優(yōu)效率高、全局性能好、優(yōu)化結(jié)果穩(wěn)定,性能明顯優(yōu)于標(biāo)準(zhǔn)認(rèn)知優(yōu)化算法。

關(guān)鍵詞:社會認(rèn)知算法;混沌優(yōu)化;Tent映射;全局收斂;非線性規(guī)劃問題

0引言

非線性規(guī)劃是具有非線性約束條件或目標(biāo)函數(shù)的數(shù)學(xué)規(guī)劃,是運(yùn)籌學(xué)的一個重要分支,非線性規(guī)劃在工程、管理、經(jīng)濟(jì)、科研、軍事等方面都有廣泛的應(yīng)用,為最優(yōu)設(shè)計(jì)提供了有力的工具。一般來說,約束非線性規(guī)劃問題可以表示為:

minf(x)，

(1)

其中,x=[x1…xq…xn]，1≤q≤n,xq∈[lq,uq],lq和uq分別為定義域的下界和上界;S為定義空間,SF為滿足所有約束的可行空間,SF?S;f(x)為最小化目標(biāo)函數(shù)。由于f(x)和g(x)往往是非線性、不可微、不連續(xù)的,并且此問題是NP-hard[1]問題,傳統(tǒng)的確定性算法解決此類約束優(yōu)化問題非常困難,因此尋找求解該問題的有效方法是科學(xué)技術(shù)和工程應(yīng)用中的一個重要課題。

社會認(rèn)知理論研究表明,社會學(xué)習(xí)比生物或昆蟲系統(tǒng)的進(jìn)化要智能得多。文獻(xiàn)[2]基于社會認(rèn)知理論提出了社會認(rèn)知優(yōu)化算法(social cognitive optimization algorithm,SCO),該算法比基于生物和昆蟲社會的遺傳算法、粒子群等優(yōu)化算法的智能性和社會性更高。學(xué)習(xí)個體充分利用社會群體的交互和共享進(jìn)行模仿學(xué)習(xí)和觀察學(xué)習(xí)來進(jìn)化迭代,因此該算法具有較強(qiáng)的收斂速度,適合于大規(guī)模的約束問題的處理[3],該算法對于解決多峰、非連通甚至難以建立數(shù)學(xué)模型的優(yōu)化問題都有著很好的效果,并在調(diào)度、設(shè)計(jì)、控制等實(shí)際問題上得到應(yīng)用[4],該算法的收斂速度快、穩(wěn)定性好并且與初始值無關(guān),是一個值得進(jìn)一步深入研究的智能算法。

文獻(xiàn)[5]提出了無免費(fèi)午餐定理(no free lunch theorem,NFL)。該定理指出沒有一種算法對任何問題都是最優(yōu)的,不同的算法都有其不同的應(yīng)用優(yōu)勢與不足,算法之間存在著互補(bǔ)性。SCO 也不例外,它的算法簡單、快速,是一種很好的問題求解模式,但是缺乏有效的局部搜索機(jī)制。因此,從解決實(shí)際問題角度出發(fā),融合不同類型機(jī)制的優(yōu)化算法,充分發(fā)揮它們各自的優(yōu)勢,構(gòu)造混合優(yōu)化算法,是拓寬算法適用范圍和提高算法性能的有效手段。

為此,一些研究者對SCO算法進(jìn)行了改進(jìn)研究。文獻(xiàn)[6]用SCO融合自組織遷移算法,通過2個參數(shù)來協(xié)調(diào)2個算法優(yōu)化的過程;文獻(xiàn)[7]針對電力系統(tǒng)無功優(yōu)化問題,提出了基于農(nóng)夫捕魚算法的社會認(rèn)知算法;文獻(xiàn)[8]對SCO算法進(jìn)行改進(jìn),并融合到文化算法的過程中,構(gòu)造了一種文化社會認(rèn)知優(yōu)化算法,并解決QoS感知的云服務(wù)組合優(yōu)化問題;文獻(xiàn)[9]提出用離散自然認(rèn)知優(yōu)化算法解決三維碎片的全局匹配問題。

本文基于算法混合的思想,在認(rèn)知優(yōu)化算法中引入基于Tent映射的混沌搜索機(jī)制,增加個體的多樣性,增強(qiáng)算法的全局和局部尋優(yōu)能力,從而構(gòu)建一種新的認(rèn)知優(yōu)化算法——混沌認(rèn)知優(yōu)化算法TSCO；同時以Solis和Wets提出的隨機(jī)算法收斂定理[10]為基礎(chǔ)，給出了該算法的全局收斂性證明。標(biāo)準(zhǔn)測試函數(shù)的優(yōu)化試驗(yàn)結(jié)果表明,混沌認(rèn)知優(yōu)化算法尋優(yōu)效率高、收斂速度快,明顯優(yōu)于基本認(rèn)知優(yōu)化算法。

1混沌優(yōu)化算法

混沌是自然界廣泛存在的一種非線性現(xiàn)象,具有隨機(jī)性、遍歷性和對初始條件的極度敏感性等特點(diǎn),在一定范圍內(nèi)能夠按其自身的規(guī)律不重復(fù)地遍歷所有狀態(tài)?；煦绮呗越?jīng)常應(yīng)用在優(yōu)化領(lǐng)域,以提高尋優(yōu)速度。

基于混沌的優(yōu)化理論,主要是利用混沌序列的遍歷性、隨機(jī)性、規(guī)律性來搜索尋找問題的最優(yōu)解?；煦缧蛄械漠a(chǎn)生有很多種方法[11],文獻(xiàn)[12]研究表明基于Tent映射的混沌序列的迭代速度優(yōu)于基于Logistic映射的混沌序列,并且具有全局遍歷性,初始值敏感性不強(qiáng),迭代過程適合于計(jì)算機(jī)運(yùn)行,該方法已經(jīng)在一些領(lǐng)域成功應(yīng)用[13]。一維Tent映射函數(shù)經(jīng)過貝努利變換后可表示為:

(2)

即

xk+1=2xkmod1

(3)

對于[0,1]之間的浮點(diǎn)數(shù),在計(jì)算機(jī)進(jìn)行Tent映射時,實(shí)際是將小數(shù)部分的二進(jìn)制數(shù)進(jìn)行無符號左移。這種運(yùn)算特點(diǎn)充分利用了計(jì)算機(jī)的特性,因此Tent映射的迭代速度要快于Logistic 映射。但是由于計(jì)算機(jī)字長有限,小數(shù)部分的二進(jìn)制序列經(jīng)過一定次數(shù)的無符號左移運(yùn)算將趨向全0,即趨向Tent映射的不動點(diǎn)。并且迭代序列中存在小周期,例如4周期(0.2,0.4,0.6,0.8);還存在不穩(wěn)周期點(diǎn),例如(0,0.25,0.50,0.75,1.00)都將迭代到不動點(diǎn)0。

基于Tent映射的區(qū)間(Vmin,Vmax)中混沌序列產(chǎn)生的步驟如下:

(1) 取初值x0(x0應(yīng)避免落入小周期點(diǎn)內(nèi))。

(2) 以(3)式進(jìn)行迭代,迭代M(一般取300)次,產(chǎn)生區(qū)間(0,1)中的混沌點(diǎn)xM,在迭代過程中,如果xi={0,0.25,0.50,0.75,1.00}或者xi=xi-k，k={1,2,3,4},這時讓xi=xi-1+ε來避免落入小周期和不穩(wěn)定點(diǎn)。

(3) 根據(jù)(4)式計(jì)算混沌值,Vmax為區(qū)間上界,Vmin為區(qū)間下界。

(4)

2基于Tent映射的混沌認(rèn)知優(yōu)化算法

2.1改進(jìn)策略

SCO算法的迭代策略是根據(jù)社會認(rèn)知理論中人類的學(xué)習(xí)過程來進(jìn)行的,傳統(tǒng)SCO算法主要考慮的是大多數(shù)人群的學(xué)習(xí)模式。為了提高算法的遍歷性,本文算法進(jìn)一步考慮遍歷性和隨機(jī)性強(qiáng)的混沌搜索策略,引入混沌搜索庫和傳統(tǒng)的知識庫同步迭代,協(xié)同更新?；煦鐜觳捎没赥ent映射的混沌搜索策略來避免迭代過程的早熟,同時在局部搜索操作中使用混沌搜索來提高局部搜索的效率,同時初始化采用混沌映射來產(chǎn)生初始位置。

2.2混沌社會認(rèn)知算法的基本概念

(1) 知識點(diǎn)。知識點(diǎn)是位于知識空間(例如搜索空間)中對位置x水平(例如適應(yīng)值函數(shù)值)的描述構(gòu)成的點(diǎn)。

(2) 知識庫。知識庫是一系列知識點(diǎn)的集合,這個集合是有固定大小的。

(3) 學(xué)習(xí)代理。學(xué)習(xí)代理是一個學(xué)習(xí)行為個體,支配庫中的一個知識點(diǎn),通過學(xué)習(xí)代理個體的學(xué)習(xí)來更新知識庫。

(4) 領(lǐng)域搜索。2個點(diǎn)x1和x2,對x2的領(lǐng)域搜索就是以x1作為參考點(diǎn)選出一個新的點(diǎn)x′。

(5) 混沌搜索。即按照Tent映射產(chǎn)生的混沌序列來構(gòu)造新的點(diǎn)。

整個優(yōu)化過程通過一系列學(xué)習(xí)代理的多次迭代來完成,其原理如圖1所示。

圖1　混沌社會認(rèn)知優(yōu)化原理圖

2.3基于混沌策略的認(rèn)知優(yōu)化算法步驟

假設(shè)知識庫中知識點(diǎn)的個數(shù)是Npop,混沌庫中知識點(diǎn)個數(shù)是Ntent,學(xué)習(xí)代理的數(shù)量是Nc,混沌認(rèn)知優(yōu)化算法流程圖如圖2所示,算法具體步驟如下:

(1) 初始化過程。① 在知識庫中按Tent映射生成(Npop+Ntent)個知識點(diǎn),并計(jì)算其適應(yīng)值;② 給每個學(xué)習(xí)代理隨機(jī)分配庫中的一個知識點(diǎn),但不允許把一個知識點(diǎn)重復(fù)分配給多個學(xué)習(xí)代理。

(3) 庫更新過程。從知識庫中移去Nc個具有最差水平的知識點(diǎn),用本次迭代學(xué)習(xí)中(包括混沌庫中點(diǎn))最好的Nc個體。

(4) 重復(fù)步驟(2)～步驟(4),直到滿足停止條件(例如達(dá)到預(yù)先確定的迭代次數(shù),或者結(jié)果達(dá)到預(yù)先設(shè)定的精度)。

社會認(rèn)知優(yōu)化的參數(shù)包括Npop、Ntent、Nc和T，其中T為學(xué)習(xí)循環(huán)的循環(huán)次數(shù)。那么函數(shù)總的運(yùn)行次數(shù)為:

圖2　混沌認(rèn)知優(yōu)化算法流程圖

2.4TSCO算法的全局收斂性

從上述算法的過程可以看到,TSCO算法是一種典型的隨機(jī)類優(yōu)化算法,Solis和Wets給出了隨機(jī)算法全局收斂的充要條件[10],其主要內(nèi)容如下。

假設(shè)1f(D(z,ξ))≤f(z),且如果ξ∈S,則f(D(z,ξ))≤f(ξ)。

假設(shè)2假設(shè)S存在任意Borel子集A,如果它的測度滿足條件v(A)>0,v(A)是A的閉包,那么有:

(5)

其中,μk(A)為由測度μk所得到的A的概率。

(6)

其中,P[zk∈Rε]為第k步算法生成的解zk∈Rε的概率;Rε為全局最優(yōu)點(diǎn)集合。

下面分析TSCO算法是否滿足上述假設(shè)。

定理2TSCO算法滿足假設(shè)1。

對函數(shù)D進(jìn)行定義:

(7)

其中,pgk為第k步的全局最優(yōu)點(diǎn);g(xik)為第k步的第i個代理的更新;xik為第k代時的粒子i的位置。本算法保留了學(xué)習(xí)過程中的最優(yōu)解,從中容易看出,按照函數(shù)D的定義,TSCO算法滿足假設(shè)1。

定理3TSCO算法滿足假設(shè)2。

對于規(guī)模為N=Ntent+Nc的群體,如果假設(shè)2成立,即證明TSCO算法滿足(8)式:

(8)

其中,Mi,k為在算法第k代時點(diǎn)i的支撐集。

定理4TSCO算法以概率1全局收斂于全局最優(yōu)解。

由定理2和定理3可知,TSCO算法滿足假設(shè)1和假設(shè)2,由定理1可知TSCO算法以概率1全局收斂于全局最優(yōu)解。

2.5求解非線性規(guī)劃問題

應(yīng)用混沌認(rèn)知優(yōu)化算法求解非線性規(guī)劃問題時,以目標(biāo)函數(shù)作為知識點(diǎn)的適應(yīng)度評價(jià)函數(shù),且函數(shù)值越小表示該知識點(diǎn)的水平越好。在處理約束問題時,違約處理是一個重要問題,在群體智能算法中對于一個點(diǎn)違背約束處理常用策略如(9)式所示,即

(9)

對約束的處理規(guī)則為:① 任何可行空間中的點(diǎn)優(yōu)于非可行空間中的點(diǎn);② 可行空間中的2個點(diǎn)適應(yīng)值越小越好;③ 非可行空間中的2個點(diǎn)違約值越小越好。

3數(shù)值試驗(yàn)與仿真

為了測試本文提出的混沌認(rèn)知優(yōu)化算法(TSCO)求解帶約束的非線性規(guī)劃問題的性能,同時為使測試結(jié)果具有可比性,本文以文獻(xiàn)[2]中經(jīng)典的4個基準(zhǔn)非線性規(guī)劃問題為測試對象,4個基準(zhǔn)問題如下所述。

(1)G1。

minG1(x)=5x1+5x2+5x3+5x4-

定義域:

0≤xi≤100,i=10,11,12;

最優(yōu)值：G1(x*)=-15。

(2)G2。

0≤xi≤10,1≤i≤n。

最優(yōu)值：G2(x*)=0.803 553。

(3)G3。

105-4x1-5x2+3x7-9x8≥0,

-10x1+8x2+17x7-2x8≥0,

8x1-2x2-5x9+2x10+12≥0,

3x1-6x2-12(x9-8)2+7x10≥0,

定義域:-10.0≤xi≤10.0,i=1,…,10。

最優(yōu)值:G3(x*)=24.306 209 1。

(4)G4。

minG4(x)=x1+x2+x3;

s.t.

1-0.002 5(x4+x6)≥0,

1-0.002 5(x5+x7-x4)≥0,

1-0.01(x8-x5)≥0,

x1x6-833.332 52x4-100x1+83 333.333≥0，

定義域:

100≤x1≤10 000；1 000≤xi≤10 000,i=2,3；

100≤xi≤10000,i=4,…,8。

最優(yōu)值:G4(x*)=7 049.330 923。

本文在4個問題下對社會認(rèn)知優(yōu)化算法(SCO)和基于Tent映射的混沌社會認(rèn)知優(yōu)化算法(TSCO)性能進(jìn)行對比測試。

在標(biāo)準(zhǔn)社會認(rèn)知優(yōu)化算法和改進(jìn)的社會認(rèn)知優(yōu)化算法中,設(shè)定庫中知識點(diǎn)個數(shù)Npop=95,Ntent=5,學(xué)習(xí)代理個數(shù)Nc=15,循環(huán)學(xué)習(xí)次數(shù)T=2 000,每個問題執(zhí)行50次。計(jì)算其最好結(jié)果、最差結(jié)果和平均結(jié)果來比較改進(jìn)后的算法和傳統(tǒng)認(rèn)知優(yōu)化算法的性能。

社會認(rèn)知優(yōu)化算法和改進(jìn)的社會認(rèn)知優(yōu)化算法獨(dú)立運(yùn)行50次,在目標(biāo)函數(shù)平均值、最差結(jié)果、最好結(jié)果方面的對比見表1所列。

從表1的試驗(yàn)結(jié)果可以看出,與傳統(tǒng)的社會認(rèn)知算法SOC相比,4個問題TSCO的平均值和最好值與問題的最優(yōu)值更接近,解的精度更高,這說明TSCO算法在求解非線性規(guī)劃問題中的效率更高、穩(wěn)定性更好。

2種算法在50次求解過程的平均目標(biāo)函數(shù)f(x)與該問題最優(yōu)值差的絕對值Fnorm和迭代次數(shù)的對數(shù)曲線如圖3所示。圖3中總的迭代次數(shù)為2 000次,為了圖示的清晰,選取了100的整數(shù)倍次(t/100)的優(yōu)化值。由圖3可以看出,該算法與傳統(tǒng)社會認(rèn)知算法相比收斂速度較快,隨著學(xué)習(xí)次數(shù)的增加,目標(biāo)函數(shù)減小更快。

表1　TSCO算法運(yùn)行結(jié)果

圖3　迭代過程適應(yīng)值變化對比圖

4結(jié)束語

本文提出了一個求解非線性規(guī)劃問題的、基于Tent映射的混沌社會認(rèn)知優(yōu)化算法,給出了該算法的全局收斂性證明。標(biāo)準(zhǔn)測試函數(shù)的仿真優(yōu)化結(jié)果表明,本文算法收斂速度快、尋優(yōu)效率高、全局性能好、優(yōu)化結(jié)果穩(wěn)定,性能明顯優(yōu)于標(biāo)準(zhǔn)認(rèn)知優(yōu)化算法,為求解非線性規(guī)劃問題提供了一種新的有效算法。

[參考文獻(xiàn)]

[1]Wang T.Global optimization for constrained nonlinear programming [M].Urbana:Illinois University Press,2001:8-11.

[2]Xie X F,Zhang W J,Yang Z L.Social cognitive optimization for nonlinear programming problems[C]//International Conference on Machine Learning and Cybernetics.IEEE,2002:779-783.

[3]Xie X F,Zhang W J.Solving engineering design problems by social cognitive optimization[M]//Genetic and Evolutionary Computation-GECCO 2004.Berlin:Springer,2004:261-262.

[4]孫家澤,王曙燕,張建科,等.求解非線性互補(bǔ)問題的熵函數(shù)認(rèn)知優(yōu)化算法[J].計(jì)算機(jī)工程與應(yīng)用,2010,46(21):40-42.

[5]Wolpert D H,Macready W G.No free lunch theorems for optimization[J].IEEE Transactions on Evolutionary Computation,1997,1(1):67-82.

[6]彭斌.社會認(rèn)知優(yōu)化改進(jìn)及其應(yīng)用研究 [D].南京:南京工業(yè)大學(xué),2006.

[7]白云,徐剛剛,宋陽.基于改進(jìn)社會認(rèn)知算法的電力系統(tǒng)多目標(biāo)無功優(yōu)化[J].黑龍江電力,2012,34(2):120-124.

[8]劉志中,王志堅(jiān),薛霄,等.基于文化社會認(rèn)知算法的云服務(wù)優(yōu)化組合研究[J].計(jì)算機(jī)科學(xué),2013,40(5):103-106,140.

[9]孫家澤,耿國華.基于群體智能的三維碎片全局最優(yōu)匹配方法[J].計(jì)算機(jī)應(yīng)用,2016,36(1):266-270.

[10]Solis F J,Wets J B.Minimization by random search techniques[J].Mathematics of Operations Research,1981,6(1):9-30.

[11]程志剛,張立慶,李小林,等.基于Tent映射的混沌混合粒子群優(yōu)化算法[J].系統(tǒng)工程與電子技術(shù),2007,29(1):103-106.

[12]Rong H.Study of adaptive chaos embedded particle swarm optimization algorithm based on Skew Tent map[C]//International Conference on Intelligent Control and Information Processing.IEEE,2010:316-321.

[13]王立宏,王曙燕,孫家澤.一種分階段組合測試數(shù)據(jù)生成算法[J].計(jì)算機(jī)應(yīng)用與軟件,2013,30(3):67-70.

(責(zé)任編輯胡亞敏)

A social congitive optimization algorithm for guaranteeing global convergence

WANG Chun-mei,SUN Jia-ze

(School of Computer Science and Technology, Xi’'an University of Posts and Telecommunications, Xi’an 710121, China)

Abstract:To improve the global convergence speed of classical social cognitive optimization(SCO) algorithm, a guaranteed global convergence SCO based on Tent map(TSCO) is proposed. In the proposed algorithm, Tent map is used to initialize the knowledge libraries to improve the quality of the initial solution; neighborhood search by using chaotic search method enhances the algorithm’s ability for escaping from the local optimal solution; chaotic libraries improve the ergodicity of the search and achieve the collaborative optimization with knowledge libraries. So a new chaotic hybrid SCO is constructed. And the global convergence proof is made based on the convergence theorem in Solis and Wets’ stochastic algorithm. The results of simulated optimization in standard test functions show that the algorithm has a strong ability to solve the nonlinear programming problems. The algorithm has high searching efficiency, good global performance and stable optimized result, which is significantly better than standard cognitive optimization algorithms in performance.

Key words:social cognitive optimization(SCO); chaotic optimization; Tent map; global convergence; nonlinear programming problem

收稿日期：2015-07-01；修回日期：2016-02-17

基金項(xiàng)目：陜西省自然科學(xué)基金資助項(xiàng)目(2015JM6359);陜西省工業(yè)科技攻關(guān)資助項(xiàng)目(2016JY-086);陜西省教育廳自然科學(xué)基金資助項(xiàng)目(15JK1672;15JK1678)和西安市科技計(jì)劃資助項(xiàng)目(CXY1516 (4))

作者簡介：王春梅(1979-),女,甘肅蘭州人,西安郵電大學(xué)講師.

doi:10.3969/j.issn.1003-5060.2016.05.013

中圖分類號:TP18

文獻(xiàn)標(biāo)識碼：A

文章編號：1003-5060(2016)05-0636-06