劉勇,陸軍,徐裕生,李陽

(1.西安建筑科技大學(xué)理學(xué)院,陜西西安 710055;2.鄭州師范高等專科學(xué)校,河南鄭州 450044)

多點(diǎn)收縮混沌優(yōu)化方法及全局收斂性證明

劉勇1,陸軍2,徐裕生1,李陽1

(1.西安建筑科技大學(xué)理學(xué)院,陜西西安 710055;2.鄭州師范高等?？茖W(xué)校,河南鄭州 450044)

針對(duì)目前混沌優(yōu)化算法在選取局部搜索空間時(shí)的盲目性,提出一種具有自適應(yīng)調(diào)節(jié)局部搜索空間能力的多點(diǎn)收縮混沌優(yōu)化方法.該方法在當(dāng)前搜索空間搜索時(shí)保留多個(gè)較好搜索點(diǎn),之后利用這些點(diǎn)來確定之后的局部搜索空間,以達(dá)到對(duì)不同的函數(shù)和當(dāng)前搜索空間內(nèi)已進(jìn)行搜索次數(shù)的自適應(yīng)效果.給出了該算法以概率1收斂的證明.仿真結(jié)果表明該算法有效的提高了混沌優(yōu)化算法的性能,改善了混沌算法的實(shí)用性.

混沌優(yōu)化;多點(diǎn)收縮混沌優(yōu)化算法;全局收斂性;概率1收斂

1 引言

混沌是一種普遍的非線性現(xiàn)象,具有隨機(jī)性、遍歷性和內(nèi)在的規(guī)律性的特點(diǎn).基于混沌遍歷性的混沌優(yōu)化一經(jīng)出現(xiàn),其直觀、易實(shí)現(xiàn)的特點(diǎn)就引起了廣泛關(guān)注[13].但目前混沌優(yōu)化發(fā)展歷史較短,因此許多問題還有待進(jìn)一步研究和討論.現(xiàn)有的研究表明,當(dāng)直接利用混沌變量進(jìn)行搜索時(shí):1)單純的提高迭代步數(shù)不能顯著的提高算法搜索的遍歷程度;2)多軌道并行搜索不能顯著提高混沌搜索的遍歷程度;3)在粗略搜索的最優(yōu)點(diǎn)附近進(jìn)行細(xì)搜索,可能導(dǎo)致當(dāng)前最優(yōu)點(diǎn)偏離全局最優(yōu)點(diǎn)[4],影響算法的搜索速度.由此可見,在大范圍的搜索后對(duì)有較大概率出現(xiàn)全局最優(yōu)點(diǎn)的局部空間進(jìn)行再搜索是提高混沌優(yōu)化算法性能的一種較為理想的改進(jìn)方法.但易知不同的函數(shù)在進(jìn)行局部搜索前需要進(jìn)行的搜索次數(shù)是不同的,需要進(jìn)行局部搜索的區(qū)域也是不同的,故對(duì)局部搜索的控制策略和局部搜索策略的選取是至關(guān)重要的.而以往的混沌算法都是在進(jìn)行一定次數(shù)的混沌搜索的基礎(chǔ)上,以固定的比例縮小搜索空間[23],顯然這種局部搜索空間的選取是較為盲目的.本文提出利用多個(gè)較好搜索點(diǎn)來確定局部搜索空間的策略,這種策略能針對(duì)不同的函數(shù)和針對(duì)在當(dāng)前搜索空間內(nèi)已進(jìn)行搜索的次數(shù)自適應(yīng)的調(diào)節(jié)之后的局部搜索空間.通過這種改進(jìn),既保證了算法的收斂速度又可對(duì)算法的全局收斂效果進(jìn)行控制,從而大大提高了混沌算法的實(shí)用性.

2 算法的初步介紹

2.1 局部搜索空間的選取策略

多點(diǎn)收縮混沌優(yōu)化方法局部搜索空間選取策略如圖1所示.其中A為當(dāng)前搜索空間, “·”表示在空間A內(nèi)已得到的所有搜索點(diǎn),“*”表示在空間A內(nèi)通過比較得出的前個(gè)較好搜索點(diǎn).本文選取包含所有“*”在內(nèi)的最小超長(zhǎng)方體B為相對(duì)空間A的局部搜索空間,同樣在B空間上可繼續(xù)按上述過程再進(jìn)行搜索并重新確定相對(duì)B空間的局部搜索空間,直到達(dá)到算法終止條件.

圖1 局部搜索空間選取策略示意圖

2.2 算法自適應(yīng)控制能力的分析

對(duì)于性態(tài)較好的函數(shù)和在空間A內(nèi)搜索點(diǎn)數(shù)iter相對(duì)較多時(shí),搜索空間宜快速收縮以提高搜索效率;而在相反情況時(shí),搜索空間則不宜縮小過快以避免搜索陷入局部最優(yōu).當(dāng)按照上述方法確定局部搜索空間時(shí),由于混沌變量具有隨機(jī)性、遍歷性的特點(diǎn),故函數(shù)性態(tài)的好壞和iter的大小將直接決定搜索得到的num個(gè)較好點(diǎn)的集中和分散程度,從而決定了之后局部搜索空間的大小,而多個(gè)較好點(diǎn)的使用又可以極大概率的保證全局最優(yōu)點(diǎn)落在由其決定的局部搜索空間之中,由此就實(shí)現(xiàn)了算法對(duì)上述不同情況的自適應(yīng)控制.

3 多點(diǎn)收縮混沌優(yōu)化算法

對(duì)于連續(xù)的全局優(yōu)化模型

4 算法全局收斂性的證明

4.1預(yù)備知識(shí)

4.2 全局收斂性證明

5 數(shù)值方真

5.1 算法對(duì)隨機(jī)參數(shù)自適應(yīng)性測(cè)試

為了檢驗(yàn)算法對(duì)不同函數(shù)和參數(shù)的自適應(yīng)性.我們選取了兩個(gè)經(jīng)常被用來測(cè)試混沌化算法有效性的兩個(gè)函數(shù)進(jìn)行了仿真測(cè)試.

設(shè)計(jì)隨機(jī)操作如下:

1)混沌變量在區(qū)間(0,1)上隨機(jī)取定;

2)參數(shù)iter在100～1000之間隨機(jī)取定;

3)參數(shù)num在10～20之間隨機(jī)取定.

F1和F2理論最小值皆為0.表1為在以上的隨機(jī)操作和ε=0.01的規(guī)定下我在P4(1.4G) 的PC機(jī)上連續(xù)對(duì)F1和F2進(jìn)行了10次運(yùn)算的結(jié)果.

圖1 算法隨機(jī)參數(shù)仿真結(jié)果

由表1可見對(duì)F1和F2的10次隨機(jī)仿真運(yùn)算均能很好的收斂到各自的理論值,并且所耗費(fèi)的時(shí)間基本是相同的,而當(dāng)進(jìn)行隨機(jī)參數(shù)實(shí)驗(yàn)時(shí)文[1-3]的算法均很難在短時(shí)間內(nèi)收斂,這充分證明了本文算法的有效性和對(duì)不同的參數(shù)和函數(shù)的自適應(yīng)性.

5.2 算法對(duì)于不同維數(shù)的自適應(yīng)性

一個(gè)好的優(yōu)化算法最終是為解決實(shí)際問題服務(wù)的,而實(shí)際問題一般為高維函數(shù),為了測(cè)試本算法對(duì)高維函數(shù)的適應(yīng)性,我們進(jìn)行如下數(shù)值仿真.

由表可見當(dāng)n=1,2,…,10時(shí)算法均能全局收斂,雖然隨著函數(shù)維數(shù)的增長(zhǎng)計(jì)算精度有所降低,且計(jì)算時(shí)間快速增長(zhǎng),但是由于所有計(jì)算結(jié)果都是在相同參數(shù)下計(jì)算得出的,所以整體的計(jì)算結(jié)果還是十分令人滿意的.

6 結(jié)語

本文提出的多點(diǎn)收縮混沌優(yōu)化算法,對(duì)混沌算法應(yīng)如何縮小搜索空間,如何設(shè)計(jì)算法終止條件,如何選取初始控制參數(shù)和控制策略給出了一種較為理想的解決方案.由證明過程可見只要每次保留的較好搜索點(diǎn)數(shù)num足夠大,本算法可以以概率1收斂于全局最優(yōu)解.而在實(shí)際應(yīng)用中可以通過控制num的取值,快速的得出滿足實(shí)際需求的最優(yōu)解.

圖2 算法對(duì)不同維函數(shù)仿真結(jié)果

[1]李兵,蔣慰孫.混沌優(yōu)化方法及其應(yīng)用[J].控制理論與應(yīng)用,1997,14(4):613-615.

[2]張彤,王宏偉,王子才.變尺度混沌優(yōu)化方法及其應(yīng)用[J].控制與決策,1999,14(3):285-288.

[3]修春波,劉向東,張寧河.雙混沌機(jī)制優(yōu)化方法及其應(yīng)用[J].控制與決策,2003,18(6):724-726.

[4]杜守強(qiáng),陳元媛.推廣線搜索下一類共軛梯度法的全局收斂性[J].純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué),2004,20(3):209-212

[5]李宏,王宇平,焦永昌.解非線性兩層規(guī)劃問題的新的遺傳算法及全局收斂性[J].系統(tǒng)工程理論與實(shí)踐,2005, 26(3):62-71

Multipoint shrinking chaos optimization algorithm and its global convergence

LIU Yong1,LU Jun2,XU Yu-sheng1,LI Yang1
(1.School of Science,Xi’an University of Architecture and Technology,Xi’an710055,China; 2.Department of Mathematics,Zhengzhou Teachers College,Zhengzhou450044,China)

A multipoint shrinking chaos optimization algorithm which local searching space can be decided under an self-adaptive contral strategy is proposed.The method keeps multiple better searching points at present searching space to decide its local searching space later.By this way the method have a self-adaptive on different functions and different times the search has carried out before.The global convergence of the algorithm are proved.Simulation results show that the algorithm can improve the chaos optimization algorithm’s performance effectivly as well as make the chaos optimization more practical.

chaos optimization,multipoint shrinking chaos optimization algorithm,global optimization,almost sure convergence

O221

A

1008-5513(2009)03-0491-06

2007-11-28.

國(guó)家自然科學(xué)基金(70173037).

劉勇(1979-),碩士,研究方向：最優(yōu)化理論.

2000MSC:40K