孫雅芳， 王曉丹， 徐俊彥， 劉慶懷

（長春工業(yè)大學(xué)應(yīng)用數(shù)學(xué)研究所，吉林長春 130012）

0 引 言

近幾年來，全局優(yōu)化方法得到了快速的發(fā)展，尤其是智能優(yōu)化算法中的禁忌搜索算法、模擬退火算法、神經(jīng)網(wǎng)絡(luò)算法、遺傳算法、蟻群算法得到了廣泛的研究與應(yīng)用，但是還需進(jìn)一步的完善與改進(jìn)。

禁忌搜索算法[1-2]是模擬人類智能的全局優(yōu)化算法，此算法具有較好的局部尋優(yōu)能力，但會(huì)出現(xiàn)早熟現(xiàn)象。模擬退火算法[3]屬于一種低級(jí)的智能，它模擬物體退火而形成的一種現(xiàn)代優(yōu)化算法，其計(jì)算量雖然比Monte Carlo方法明顯減少，但其全局收斂性仍很差。神經(jīng)網(wǎng)絡(luò)算法[4]是通過構(gòu)造人工神經(jīng)網(wǎng)絡(luò)模型的一種智能算法。此算法計(jì)算快速簡單，但此算法容易陷入局部最優(yōu)解。遺傳算法[5]是一種利用進(jìn)化論中優(yōu)勝劣汰、適者生存的原理而提出基于生物自身能力的智能算法。遺傳算法是在整個(gè)空間內(nèi)進(jìn)行全局搜索，但其算法的計(jì)算時(shí)間長，經(jīng)常會(huì)出現(xiàn)早熟收斂現(xiàn)象。蟻群算法是模仿螞蟻依賴信息素進(jìn)行通信而顯示出的社會(huì)行為一種分布式智能模擬算法。此算法可以得到較好的全局最優(yōu)解，有較強(qiáng)魯棒特性，它是一無監(jiān)督并行算法。此算法缺點(diǎn)是參數(shù)較多，而且沒有確定的方法給出參數(shù)一個(gè)固定值，只能依靠實(shí)驗(yàn)或者是經(jīng)驗(yàn)，計(jì)算時(shí)間較長，且容易出現(xiàn)死循環(huán)或者停止現(xiàn)象。了望算法[6]是基于通過了望確定群山最高點(diǎn)的常識(shí)提出的一種算法。在了望算法中主要包括了望管理機(jī)制、產(chǎn)生了望點(diǎn)策略、局部問題構(gòu)造與求解。此算法是全局搜索，但易產(chǎn)生漏點(diǎn)現(xiàn)象。禁忌搜索算法、模擬退火算法、神經(jīng)網(wǎng)絡(luò)算法、遺傳算法、蟻群算法、了望算法在解決全局優(yōu)化問題會(huì)產(chǎn)生漏點(diǎn)的現(xiàn)象或者只是達(dá)到局部最優(yōu)，由此提出基于視覺認(rèn)知的全局優(yōu)化算法。

文中給出了基于視覺認(rèn)知的全局優(yōu)化算法，確保在產(chǎn)生眺望點(diǎn)時(shí)，不存在漏點(diǎn)的現(xiàn)象，且用數(shù)學(xué)的方法證明了由算法產(chǎn)生的序列依概率收斂于全局最小值，通過數(shù)值例子對(duì)算法加以實(shí)現(xiàn)，并對(duì)全文進(jìn)行了總結(jié)。

1 主要結(jié)果

1.1 基于視覺認(rèn)知的全局優(yōu)化算法

針對(duì)如下形式的全局優(yōu)化問題

假設(shè):

1）f:Rn→R連續(xù)，且有下界;

2）存在一個(gè)實(shí)數(shù)c0，使得水平集

非空有界。

算法:

1）取ε＞0充分小，樣本點(diǎn)數(shù)N∈Z+，令k= 0，c0=f（x0）。

3）產(chǎn)生眺望記憶機(jī)制。

5）計(jì)算

1.2 取樣與更新

在算法中，起始密度選取為g0（x）=U（D），D?Rn為足夠大的超立方體，其它步驟的取樣密度選取以下核密度函數(shù)，即令

在這里，利用相對(duì)熵方法[7]來更新取樣密度函數(shù)gk+1（x）。

為了簡化計(jì)算，所選取的核函數(shù)為

式中:xj——向量x=（x1，x2，…，xn）的第 j個(gè)分量。

這樣的核函數(shù)給取樣和密度函數(shù)的更新帶來了方便，結(jié)合式（2）與式（3），得到取樣核密度函數(shù)為:

1.3 算法的收斂性

定理1 設(shè){ck}是由算法產(chǎn)生的序列，存在c使

證明:由算法知

所以{ck}為單調(diào)下降序列。又因?yàn)橛杉僭O(shè)（1）知ck有界，則

證明 先證必要性:

再證充分性:

則?x∈Rn，有

采用反正法證明:

根據(jù)算法

所以

即可知

證明 由終止條件，當(dāng)

時(shí)，對(duì)?ε，存在K，當(dāng)k≥K時(shí)，有

即可知對(duì)?x∈Hc，有

相應(yīng)地Hc為最優(yōu)點(diǎn)集。

2 數(shù)值算例[8]

所有的算法使用Matlab編程實(shí)現(xiàn)[9]，計(jì)算條件:CPU P4-1.0 GHz，256 M RAM，Matlab7.0。

例1 Rosenbrock函數(shù):

最優(yōu)解（1，1）T，

根據(jù)文中的方法，投點(diǎn)數(shù)N=2 000，迭代次數(shù)k=4，得到最優(yōu)解（1，1）T，

例2 Easom（ES）函數(shù):

搜索范圍:-100＜xi＜100，i=1，2;

全局最優(yōu)解:

通過文中的算法，當(dāng)N=4 000，k=3時(shí)，最優(yōu)解為（3.1423，3.148 9）T，最優(yōu)值為-0.999 989。

例3 Sphere Model函數(shù):

取n=3，最優(yōu)解xi=0（i=1，2，3），

根據(jù)文中算法，當(dāng)N=3 000，k=5時(shí)，得到最優(yōu)解（0.002 0，0.001 9，0.002 1）T，

3 結(jié) 語

給出了求解全局優(yōu)化問題的一個(gè)新方法——基于視覺認(rèn)知的全局優(yōu)化算法，確保在產(chǎn)生眺望點(diǎn)時(shí)，不存在漏點(diǎn)的現(xiàn)象，且用數(shù)學(xué)方法證明了由算法產(chǎn)生的序列依概率收斂于全局最小值，通過以上數(shù)值例子對(duì)算法加以實(shí)現(xiàn)，結(jié)果表明算法具有可行性和有效性。

[1] Glover F.Tabu search:partⅠ[J].ORSA Journal on Computing，1989，21（1）:190-206.

[2] Glover F.Tabu Search:partⅡ[J].ORSA Journal on Computing，1990，22（2）:4-32.

[3] Lundy M，Mess A.Convergence of an annealing algorithm[J].Math.Program-ming，1986，34（1）: 111-124.

[4] 刑文訓(xùn)，謝金星.現(xiàn)代優(yōu)化計(jì)算方法[M].北京:清華大學(xué)出版社，2007.

[5] 汪定偉，王俊偉，王洪峰，等.智能優(yōu)化方法[M].北京:高等教育出版社，2007.

[6] CAI Yan-guang，QIAN Ji-xin，SUN You-xian. Outlook algorithm for global optimiza-tion[J]. Journal of Guangdong University of Technology，2006，23（2）:1-10.

[7] De Boer.A tutorial on the cross-entropy method [J].Annals of Operations Research，2005，134（2）: 19-67.

[8] PENG Zheng，ZHANG Hai-dong，WU Dong-hua. A level value descent method forunconstrained global optimization problems[J].Applied Mathematics，2007，20（1）:213-219.

[9] 薛定宇，陳陽泉.高等應(yīng)用數(shù)學(xué)問題的MAT LAB求解[M].北京:清華大學(xué)出版社，2008.