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

王春梅,　孫家澤

(西安郵電大學 計算機學院,陜西 西安　710121)

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

王春梅,孫家澤

(西安郵電大學 計算機學院,陜西 西安710121)

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

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

0引言

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

minf(x)，

(1)

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

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

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

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

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

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

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

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

(2)

即

xk+1=2xkmod1

(3)

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

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

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

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

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

(4)

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

2.1改進策略

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

2.2混沌社會認知算法的基本概念

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.4TSCO算法的全局收斂性

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

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

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

(5)

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

(6)

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

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

定理2TSCO算法滿足假設1。

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

(7)

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

定理3TSCO算法滿足假設2。

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

(8)

其中,Mi,k為在算法第k代時點i的支撐集。

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

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

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

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

(9)

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

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

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

(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個問題下對社會認知優(yōu)化算法(SCO)和基于Tent映射的混沌社會認知優(yōu)化算法(TSCO)性能進行對比測試。

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

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

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

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

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

圖3　迭代過程適應值變化對比圖

4結(jié)束語

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

[參考文獻]

[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]孫家澤,王曙燕,張建科,等.求解非線性互補問題的熵函數(shù)認知優(yōu)化算法[J].計算機工程與應用,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]彭斌.社會認知優(yōu)化改進及其應用研究 [D].南京:南京工業(yè)大學,2006.

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

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

[9]孫家澤,耿國華.基于群體智能的三維碎片全局最優(yōu)匹配方法[J].計算機應用,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].計算機應用與軟件,2013,30(3):67-70.

(責任編輯胡亞敏)

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

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

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

doi:10.3969/j.issn.1003-5060.2016.05.013

中圖分類號:TP18

文獻標識碼：A

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