粒子群算法的研究

1、目錄 TOC o 1-5 h z HYPERLINK l bookmark0 o Current Document 目錄 I HYPERLINK l bookmark2 o Current Document 摘要 II前言 III2引言 1 HYPERLINK l bookmark4 o Current Document 背景研究和課題意義 1 HYPERLINK l bookmark7 o Current Document 應(yīng)用領(lǐng)域 13基本粒子群算法 2粒子群思想的起源 2 HYPERLINK l bookmark12 o Current Document 算法原理 3 HYPERLINK

2、 l bookmark14 o Current Document 帶權(quán)重的粒子群算法 34粒子群算法的改進策略 4粒子群初始化 4 HYPERLINK l bookmark19 o Current Document 領(lǐng)域拓撲 4 HYPERLINK l bookmark21 o Current Document 混合策略 45測試結(jié)果 5參數(shù)設(shè)置 5 HYPERLINK l bookmark26 o Current Document 實驗結(jié)果 5 HYPERLINK l bookmark28 o Current Document 6總結(jié) 7 HYPERLINK l bookmark30 o C

3、urrent Document 致謝 8 HYPERLINK l bookmark32 o Current Document 附錄代碼 9摘要粒子群優(yōu)化是一種新興的基于群體智能的啟發(fā)式全局搜索算法，粒子群 優(yōu)化算法通過粒子間的競爭和協(xié)作以實現(xiàn)在復(fù)雜搜索空間中尋找全局最優(yōu) 點。它具有易理解、易實現(xiàn)、全局搜索能力強等特點，倍受科學(xué)與工程領(lǐng)域 廣泛關(guān)注，已經(jīng)成為發(fā)展最快的智能優(yōu)化算法之一。論文介紹了粒子群優(yōu)化 算法的基本原理，分析了其特點。論文中圍繞粒子群優(yōu)化算法的原理、特點、 參數(shù)設(shè)置與應(yīng)用等方面進行全面綜述，重點利用單因子方差分析方法，分析 了粒群優(yōu)化算法中的慣性權(quán)值，加速因子的設(shè)置對算法基本性

4、能的影響，給 出算法中的經(jīng)驗參數(shù)設(shè)置。最后對其未來的研究提出了 一些建議及研究方向 的展望。關(guān)鍵詞：粒子群優(yōu)化算法；參數(shù)；方差分析；最優(yōu)解II刖百群體智能算法(SwarmIntelligenceAlgoHthm,SIA)的研究開始于20世紀 90年代，其基本思想是模擬自然界生物的群體行為來構(gòu)造隨機優(yōu)化算法1,2,3,通常單個自然界的生物并不是智能的，但是整個生物群體卻表現(xiàn)出處理復(fù)雜問題的能力，群體智能算法就是模仿這些生物的團體行為并把它應(yīng)用在人工智能問 題中，其中粒子群優(yōu)化算法(ParticleSwarmOptimization,PSO) 就是群體智能算法的一種，它是由美國社會心理學(xué)家 Jam

5、esKennedy和電氣工程師RussellEberhart在1995年提出的，具基本思想是對鳥群、魚群的覓食過程中的遷徙和聚集的行 為模擬，并利用了生物學(xué)家 FrankHeppner的生物群體模型4,5,6。PSO算法是一類基于群體智能的隨機優(yōu)化技術(shù)，相對遺傳算法而言，二者都是基于群體的迭代搜索，但是PSO算法沒有交叉、變異算子，粒子群優(yōu)化算法是 通過個體之間的協(xié)作來搜尋最優(yōu)解，它利用了生物群體中信息共享的思想，其概念簡單、易于實現(xiàn)，同時又有深刻的智能背景，既適合科學(xué)研究，又特別適合工程應(yīng)用。因此，PSO一提出，就引起了眾多學(xué)者的關(guān)注，并在短短幾年的時間里出現(xiàn)了大量的研究成果III2引言背景

6、研究和課題意義現(xiàn)在已經(jīng)有很多源于生物現(xiàn)象的計算技巧。例如，人工神經(jīng)網(wǎng)絡(luò)是簡化的大腦模型。遺傳算法是模擬基因進化過程的?，F(xiàn)在我們討論另一種生物系統(tǒng)-社會系統(tǒng)。也可稱做“群智能”(swarm intelligence)。這些模擬系統(tǒng)利用局部信息從而可能產(chǎn)生不可預(yù)測的群體行為。粒子群優(yōu)化算法(PSO)也是起源對簡單社會系統(tǒng)的模擬。最初設(shè)想是模擬鳥群覓食的過程。但后來發(fā)現(xiàn)PSO是一種很好的優(yōu)化工具。優(yōu)化是科學(xué)研究、工程技術(shù)和經(jīng)濟管理等領(lǐng)域的重要研究課題。粒子群優(yōu)化算法1(簡稱PSO)是由Kennedy和Eberhart通過對鳥群、魚群和人類社會某 些行為的觀察研究，于1995年提出的一種新穎的進化算法

7、。鑒于 PSO的發(fā)展歷史尚短，它在理論基礎(chǔ)與應(yīng)用推廣上都還存在一些缺陷，有待解決。本文通過對PSO算法的步驟的歸納、特點的分析，利用統(tǒng)計中的方差分析，通過抽樣實驗方法，論證了該算法中關(guān)鍵參數(shù)因子：慣性權(quán)值、加速因子對算法整體性能的影響效果，并提出了參數(shù)設(shè)置的指導(dǎo)原則，給出了關(guān)鍵參數(shù)設(shè)置，為PSO算法的推廣與改進提供了思路。應(yīng)用領(lǐng)域近年來，PSO快速發(fā)展，在眾多領(lǐng)域得到了廣泛應(yīng)用。本文將應(yīng)用研究分 典型理論問題研究和實際工業(yè)應(yīng)用兩大類。典型理論問題包括：組合優(yōu)化、約 束優(yōu)化、多目標優(yōu)化、動態(tài)系統(tǒng)優(yōu)化等。實際工業(yè)應(yīng)用有：電力系統(tǒng)、濾波器設(shè)計、自動控制、數(shù)據(jù)聚類、模式識 別與圖像處理、化工、機械、通

8、信、機器人、經(jīng)濟、生物信息、醫(yī)學(xué)、任務(wù)分 配、TSP等等。3基本粒子群算法粒子群思想的起源粒子群優(yōu)化(Particle Swarm Optimization, PSO痹法1是 Kennedy 和 Eberhart 受人工生命研究結(jié)果的啟發(fā)、通過模擬鳥群覓食過程中的遷徙和群聚行為而提出的 一種基于群體智能的全局隨機搜索算法，1995年IEEE國際神經(jīng)網(wǎng)絡(luò)學(xué)術(shù)會議發(fā)表 了題為一Particle Swarm Optimization II的論文，標志著 PSO算法誕生(注：國內(nèi)也 有很多學(xué)者譯為一微粒群優(yōu)化II )。它與其他進化算法一樣，也是基于一種群II和一 進化口的概念，通過個體間的協(xié)作與競爭，

9、實現(xiàn)復(fù)雜空間最優(yōu)解的搜索；同時，PSO 又不像其他進化算法那樣對個體進行交叉、變異、選擇等進化算子操作，而是將群 體(swarm)中的個體看作是在D維搜索空間中沒有質(zhì)量和體積的粒子(particle),每 個粒子以一定的速度在解空間運動，并向自身歷史最佳位置pbest和鄰域歷史最佳位置pbest聚集，實現(xiàn)對候選解的進化。PSO算法具有很好的生物社會背景2而易 理解、參數(shù)少而易實現(xiàn)，對非線性、多峰問題均具有較強的全局搜索能力，在科學(xué) 研究與工程實踐中得到了廣泛關(guān)注。自然界中各種生物體均具有一定的群體行為，而人工生命的主要研究領(lǐng)域之一 是探索自然界生物的群體行為，從而在計算機上構(gòu)建其群體模型。自然

10、界中的鳥群 和魚群的群體行為一直是科學(xué)家的研究興趣，生物學(xué)家 Craig Reynolds在1987年 提出了一個非常有影響的鳥群聚集模型7,在他的仿真中，每一個個體遵循：(1)避免與鄰域個體相沖撞；(2)匹配鄰域個體的速度；(3)飛向鳥群中心，且整個群體飛向目標。算法原理粒子群優(yōu)化算法的實現(xiàn)步驟如下：假設(shè)在一個D維的搜索空間中，有 m個粒子組成一個群落，其中第i個粒子表示為一個D維的向量 Xi =(Xii,Xi2,., XiD)o即第I個粒子在 D維搜索空間的位置是 X。換言之， 每個粒子的位置就是一個潛在的解。將X代入一個目標函數(shù)就可以計算出其適應(yīng)值，根據(jù)適應(yīng)值的大小衡量解的優(yōu)劣。第 i個

11、粒子的“飛翔”速度也是一個 D維向量記為V =(Vii,Vi2,., ViD)。記第i個粒子迄今為止搜索到的最優(yōu)位 置為P =( Pii, Pi 2,. PiD),整個粒子群迄今為止搜索到的最優(yōu)位置為 Pg (Pg1，Pg2,., PgD) 帶權(quán)重的粒子群算法探索是偏離原來的尋優(yōu)軌跡去尋找一個更好的解，探索能力是一個算法的 全局搜索能力。開發(fā)是利用一個好的解，繼續(xù)原來的尋優(yōu)軌跡去搜索更好的解，它是算法的局部搜索能力。如何確定局部搜索能力和全局搜索能力的比例，對 一個問題的求解過程很重要。1998年，Yuhui Shi9提出了帶有慣性權(quán)重的改進粒子群算法。具進化過程為：Vi(k 1) = (wv

12、i(k),儲口-Xi(k)/ tc2r4Pg - Xi(k)八 tXi(k 1)= Xi(k) Vi(k 1) - t其中，w為慣性權(quán)重，其值可取為常數(shù)，也可以自適應(yīng)調(diào)整，例如隨迭代 次數(shù)的增加而線性地減少，C1和C2為調(diào)節(jié)Pi和Pg相對重要性的參數(shù)；1和2是介于0和1之間的隨機數(shù)；是時間問隔，通常取為單位時間；通常附加 限制，其中是常數(shù)，可根據(jù)具體問題設(shè)定。4粒子群算法的改進策略粒子群初始化研究表明，粒子群初始化對算法性能產(chǎn)生一定影響。為了初始種群盡可能 均勻覆蓋整個搜索空間，提高全局搜索能力，Richard和Ventura提出了基于centroidal voronoi tessellati

13、ons (CVTs)的種群初始化方法；薛明志等人采用正交設(shè)計方法對種群進行初始化；Campana等人將標準 PSO迭代公式改寫成線性動態(tài)系統(tǒng)，并基于此研究粒子群的初始位置，使它們具有正交的運動軌跡；認 為均勻分布隨機數(shù)進行初始化實現(xiàn)容易但尤其對高維空間效果差，并另外比較 了 3種初始化分布方法。領(lǐng)域拓撲空間鄰域直接在搜索空間按粒子間的距離(如歐式距離)進行劃分，如 Suganthan23引入一個時變的歐式空間鄰域算子：在搜索初始階段，將鄰域定 義為每個粒子自身；隨著迭代次數(shù)的增加，將鄰域范圍逐漸擴展到整個種群。性能空間指根據(jù)性能指標(如適應(yīng)度、目標函數(shù)值)劃分的鄰域。環(huán)形拓撲 (ring or

14、 circle topology)、 輪形拓撲 (wheel topology)或星形拓撲 (star topology)、塔形拓撲 (pyramid topology)、馮一諾以曼拓撲 (Von Neumann topology)以及隨機拓撲(random topology)等。針對不同的優(yōu)化問題，這些拓撲 的性能表現(xiàn)各異；但總的來說，隨機拓撲往往對大多數(shù)問題能表現(xiàn)出較好的性 能，初始階段粒子采用環(huán)形拓撲(ring-type topology),隨著迭代次數(shù)的增加，逐漸增加粒子間連接，最后形成星形拓撲(star-type topology)?；旌喜呗曰旌喜?略混合pso就是將 其它進化算法或

15、傳統(tǒng) 優(yōu)化算法或其它技術(shù) 應(yīng)用到PSO中，用于提高粒子多樣性、增強粒子的全局探索能力，或者提高局部開發(fā)能力、增強收斂速度與精度。這種結(jié)合的途徑通常有兩種：一是利用其它優(yōu)化技術(shù)自適應(yīng)調(diào)整收縮因子 /慣性權(quán)值、加速常數(shù)等；二是將 PSO與其它進化算法操作算子或其它技術(shù)結(jié)合。5測試結(jié)果5.1參數(shù)設(shè)置PSO的參數(shù)主要包括最大速度、兩個加速常數(shù)和慣性常數(shù)或收縮因等。a）最大速度的選擇：如式（2.1）所示的粒子速度是一個隨機變量，由粒子位置更新公式（2.2）產(chǎn)生的運動軌跡是不可控的，使得粒子在問題空間循環(huán)跳動3,6 o Vmax增大，有利于全局探索 （global exploration） ； Vmax減

16、小，則有利于局 部開發(fā)。但是 Vmax過高，粒子運動軌跡可能失去規(guī)律性，甚至越過最優(yōu)解所 在區(qū)域，導(dǎo)致算法難以收斂而陷入停滯狀態(tài)；相反 maxv太小，粒子運動步長 太短，算法可能陷入局部極值。Vmax的選擇通常憑經(jīng)驗給定，并一般設(shè)定為問題空間的1020%。b）加速常數(shù)的選擇：式 （1）中的加速常數(shù) c1和c2分別用于控制粒子指向 自身或鄰域最佳位置的運動。通常去c1=c2=2 。5.2實驗結(jié)果x2 %cos(2?i)cos(222)-0. 2函數(shù) f(x) - -20e2- e 2202.71289當(dāng) Ci =C2 = 1.49445, Vmin = -1,Vmax = 1,種群規(guī)模 20,迭

17、代次數(shù) 200 時, 運行結(jié)果如下圖:由于每次產(chǎn)生隨機數(shù)不可能相同，所有繪制曲線不一致。但大體趨勢是相似的：隨著迭代次數(shù)增加，適應(yīng)度逐漸減低，最終弄那個趨近于06總結(jié)大四第一學(xué)期，我學(xué)習(xí)了技能計算，初步了解了如何利用MATLAB語言編寫面向過程的程序。在這門課程的學(xué)習(xí)過程中，我常常對傅里葉變換的 性質(zhì)及其應(yīng)用感到難以適應(yīng)，感覺自己對這方面太沒有天賦了，久而久之，便 失去了學(xué)習(xí)的樂趣。好在老師在這一年里一直在鼓勵著我們。她告訴我們，這東西其實不難， 最主要的就是那個快速傅里葉變換，只要把這個搞懂行了。老師的這些話，我 感到有一定的道理，心里卻仍存疑慮，將信將疑。但也不好拂卻了老師的好意 與付出，

18、于是，我只好硬著頭皮堅持著，堅持了幾個月。這次課程設(shè)計，是我與同學(xué)一起第一次合作完成較大的程序編寫，開始時,我們心里根本沒底，想都不敢想自已能寫出一點東西來，并真正地解決這一實 際問題。但隨著工作的逐漸深入，對問題的理解越來越透徹，想寫的東西越來 越多，信心越來越足，程序越編越大，能夠解決的問題也就越多，自己心中的 疑問就越來越少?？傮w來說這篇課程設(shè)計還是比較滿意的，但還是有不足的地 方。不過，我很慶幸能夠又一次理論與實踐結(jié)合的機會，讓我能夠深入探索傅 里葉變換。在以后的學(xué)習(xí)生活中我會不斷完善自己，用更過的知識來豐富和充 實自己，為以后的人生道路打下堅實的基礎(chǔ)。致謝一份課程設(shè)計的總結(jié)，一份對老

19、師的感謝。雖然我們課程設(shè)計程序代碼在這學(xué)期開始的時候已經(jīng)有了，但是在明天即 將給老師的時刻，程序代碼也發(fā)生了許多變化，功能也逐漸提高；一些變化， 一些收獲。老師說過：“道雖遠，不行不至；事雖難，不為不成。”這專業(yè)真的很累, 老師們累，學(xué)生們也累，謝謝老師們和我們一起堅持著。明天結(jié)果如何是無法 知道的，而今天我們都努力過。附錄代碼function varargout = PSO(varargin)mfilename, .gui_Singleton = 1;gui_State = struct(gui_Name,gui_Singleton, gui_Singleton, .gui_OpeningF

20、cn, PSO_OpeningFcn, . function pushbutton1_Callback(hObject, eventdata, handles) cl = str2num(get(handles.c1,String);gui_OutputFcn,PSO_OutputFcn, .gui_LayoutFcn,gui_Callback,);if nargin & ischar(varargin1)gui_State.gui_Callback = str2func(varargin1);endif nargoutvarargout1:nargout = gui_mainfcn(gui_

21、State, varargin:); elsegui_mainfcn(gui_State, varargin:);endfunction PSO_OpeningFcn(hObject, eventdata, handles, varargin) handles.output = hObject;guidata(hObject, handles);function varargout = PSO_OutputFcn(hObject, eventdata, handles) varargout1 = handles.output;c2 = str2num(get(handles.c2,String

22、);maxgen=str2num(get(handles.edit2,String);sizepop=str2num(get(handles.edit3,String);Vmin=str2num(get(handles.Vmin,String);Vmax=str2num(get(handles.Vmax,String);popmin = str2num(get(handles.Popmin,String);popmax = str2num(get(handles.Popmax,String);%產(chǎn)生初始粒子和速度for i=1:sizepop%隨機產(chǎn)生一個種群pop(i,:)=5*rands(

23、1,2);%初始種群V(i,:)=rands(1,2);% 初始化速度%計算適應(yīng)度fitness(i)=fun(pop(i,:);%染色體的適應(yīng)度end%找最好的染色體bestfitness bestindex=min(fitness);zbest=pop(bestindex,:);% 全局最佳gbest=pop;%個體最佳fitnessgbest=fitness;%個體最佳適應(yīng)度值fitnesszbest=bestfitness;% 全局最佳適應(yīng)度值%迭代尋優(yōu)for i=1:maxgen10for j=1:sizepop%速度更新V(j,:) = V(j,:) + c1*rand*(gbest(j,:) - pop(j,:) + c2*rand*(zbest - pop(j,：)；V(j,find(V(j,:)Vmax)=Vmax;V(j,find(V(j,:)popmax)=popmax;pop(j,find(pop(j,:)0.8k