信息與計算科學畢業(yè)論文

1、本科畢業(yè)設計(論文)基于粒子群算法的函數(shù)優(yōu)化問題研究院 （系）： 理 學 院 專 業(yè)： 信息與計算科學 班 級： 071001 學 生： 張磊 學 號： 071001120 指導教師： 過曉芳 2011年 6月本科畢業(yè)設計(論文)基于粒子群算法的函數(shù)優(yōu)化問題研究院 （系）： 理 學 院 專 業(yè)： 信息與計算科學 班 級： 071001 學 生： 張磊 學 號： 071001120 指導教師： 過曉芳 2011年 6月目 錄附錄1 畢業(yè)設計（論文）開題報告附錄2 西安工業(yè)大學畢業(yè)設計（論文）開題報告檢查表附錄3 畢業(yè)設計（論文）中期報告附錄4 西安工業(yè)大學畢業(yè)設計（論文）工作中期檢查表附錄5 西

2、安工業(yè)大學畢業(yè)設計（論文）指導教師評分表附錄6 西安工業(yè)大學畢業(yè)設計（論文）評閱教師評分表附錄7 西安工業(yè)大學畢業(yè)設計（論文）答辯暨綜合評分表 畢業(yè)設計(論文)開題報告基于粒子群算法的函數(shù)優(yōu)化問題研究院（系） 數(shù)理系 專 業(yè) 信息與計算科學 班 級 071001 姓 名 張磊 學 號 071001120 導 師 過曉芳 2011年 2月28日1 畢業(yè)設計（論文）綜述（題目背景、研究意義及國內外相關研究情況）1.1 題目背景：1986年craig reynolds提出了bold（bird-oid）模型。該模型用來模擬鳥群聚集飛行的行為，提出了群體中個體飛行的三個原則：(1) 遠離最近的鄰居；(2

3、) 向目標靠近；(3) 向群體中心靠近；群中的任何個體在飛行時都遵循以上三條規(guī)則。之后，frank heppner在bold模型的基礎上又加入了棲息地的仿真條件，即鳥群的活動范圍不會越出棲息地。受到bold（bird-oid）模型的啟發(fā)，1995年kennedy和eberhart通過模擬鳥群覓食過程中的遷徙和群聚行為而提出的一種基于群體智能的全局隨機搜索算法，粒子群優(yōu)化(particle swarm optimization, pso)算法。1995年ieee國際神經(jīng)網(wǎng)絡學術會議發(fā)表了題為“particle swarm optimization”的論文，標志著pso算法誕生。kennedy和e

4、berhart認為鳥之間存在著相互交換的信息，于是他們在仿真中增加了一些內容：每個個體能夠通過一定得規(guī)則估計自身位置的適應值；每個個體都能夠記住自己當前所找好的最好位置，稱為“局部最優(yōu)pbest”；此外還記住了群體中所有鳥中找到的最好位置，稱為“全局最優(yōu)gbest”。這兩個最優(yōu)變量使得鳥在某種程度上朝這些方向靠近。pso算法具有很好的生物社會背景而易理解、參數(shù)少而易實現(xiàn)，對非線性、多峰問題均具有較強的全局搜索能力，在科學研究與工程實踐中得到了廣泛的關注。1.2 研究意義：大量的問題最終可歸結為函數(shù)的優(yōu)化問題，通常這些函數(shù)是非常復雜的，主要表現(xiàn)為規(guī)模大，維數(shù)高，非線性，非凸和不可微等特性，而且有

5、的函數(shù)存在大量局部極小。許多傳統(tǒng)確定性優(yōu)化算法收斂速度較快，計算精度高，但對初值敏感，易陷入局部最小。而一些具有全局性的優(yōu)化算法，如遺傳算法，進化規(guī)劃等，受限于各自的機理和單一結構，對于高維復雜函數(shù)難以實現(xiàn)高效優(yōu)化。pso算法通過改進或結合其他算法，對高維復雜函數(shù)可以實現(xiàn)高效優(yōu)化。粒子群算法的優(yōu)勢在于算法的簡潔性，易于實現(xiàn)，沒有很多的參數(shù)需要調整，且不需要梯度信息，所以對不連續(xù)函數(shù)或者多峰函數(shù)有較強的全局搜索能力，適合解決這一類函數(shù)的優(yōu)化問題。與遺傳算法比較，粒子群優(yōu)化算法的信息共享機制是很不同的。在遺傳算法中，染色體互相共享信息，所以整個種群的移動是比較均勻的向最優(yōu)區(qū)域移動。在粒子群優(yōu)化算法

6、中, 只有gbest 給出信息給其他的粒子， 這是單向的信息流動。整個搜索更新過程是跟隨當前最優(yōu)解的過程。與遺傳算法比較, 在大多數(shù)的情況下，所有的粒子可能更快的收斂于最優(yōu)解。目前pso已經(jīng)廣泛應用于函數(shù)優(yōu)化、神經(jīng)網(wǎng)絡訓練、模糊系統(tǒng)控制以及其他遺傳算法的應用領域。pso最初應用到神經(jīng)網(wǎng)絡訓練上，在隨后的應用中，pso可以確定神經(jīng)網(wǎng)絡的結構。作為演化神經(jīng)網(wǎng)絡的例子，eberhart已經(jīng)成功用pso來分析人類帕金森綜合癥等顫抖類疾病，parsopoulos將pso用于解決多目標優(yōu)化問題、最小最大化問題、整數(shù)規(guī)劃問題和定位所有全局極值等問題。一般說來，pso比較有潛力的應用包括系統(tǒng)設計、多目標優(yōu)化、

7、分類、模式識別、調度、信號處理、決策機器人應用等。其中具體的應用實例有：模糊控制器設計、車間作業(yè)調度、機器人實時路徑規(guī)劃、自動目標檢測等。1.3 國內外研究情況：雖然近年來pso算法在國內外發(fā)展迅速并取得了可觀的研究成果,但其理論基礎仍相對薄弱，尤其是算法基本模型中的參數(shù)設置和優(yōu)化問題還缺乏成熟的理論論證和研究。鑒于pso的發(fā)展歷史尚短，它在理論基礎與應用推廣上都還存在一些缺陷，有待解決，在以下方面仍然值得進一步研究：(1) 理論研究：雖然目前對 pso 穩(wěn)定性和收斂性的證明已取得了一些初步成果，但自誕生以來其數(shù)學基礎一直不完備，特別是收斂性一直沒有得到徹底解決。因此，仍需要對 pso 的收斂

8、性等方面進行進一步的理論研究。(2) 控制參數(shù)自適應：雖然對pso參數(shù)的改進策略等方面已取得了一定進展，但仍然有很大的研究空間；特別是如何通過對參數(shù)自適應調節(jié)以實現(xiàn)“探索” 與“開發(fā)”之間的平衡、以及“nearer is better”、假設與“nearer is worse”假設之間的智能轉換，是一個令人很感興趣的課題。(3) 信息共享機制：基于鄰域拓撲的pso局部模型大大提高了算法全局搜索能力，充分利用或改進現(xiàn)有拓撲結構以及提出新的拓撲，進一步改善算法性能，是一個值得進一步研究的問題。同時，由于全局模型具有較快的收斂速度、而局部模型具有較好的全局搜索能力，對信息共享機制做進一步研究，保證算

9、法既具有較快的收斂速度、又具有較好的全局搜索能力，也是一個很有意義的研究方向。(4) 混合pso：混合進化算法是進化算法領域的趨勢之一，與其它進化算法或傳統(tǒng)優(yōu)化技術相結合，提出新的混合pso算法，甚至提出基于pso的超啟發(fā)式搜索算法，使算法對不同種類的問題具有盡可能好的普適性，并能“更好、更快、更廉”地得到問題的解，也是一個很有價值的研究方向。(5) 應用研究：算法的有效性和價值必須在實際應用中才能得到充分體現(xiàn)。廣大科學與工程領域的研究人員，在各自的專業(yè)背景下，利用 pso 解決各種復雜系統(tǒng)的優(yōu)化問題，進一步拓展其應用領域，是一項十分有意義的工作。2本課題研究的主要內容和擬采用的研究方案、研究

10、方法或措施2.1 主要內容：（1）學習基本粒子群算法的基本原理。 （2）為了克服基本粒子群算法對于多峰函數(shù)收斂速度緩慢且易于收斂到局部最優(yōu)解的缺點，對基本粒子群算法進行改進，從而改善其局部搜索能力。（3）選取幾個函數(shù)優(yōu)化問題的算例，利用matlab編程求解問題的全局最優(yōu)解。2.2 研究方法： 學習粒子群優(yōu)化算法的理論基礎和研究現(xiàn)狀；學習粒子群優(yōu)化算法的原理及算法流程；對粒子群算法參數(shù)設置做詳細的研究并通過比較實驗數(shù)據(jù)，選取合適的參數(shù)并進行相應的函數(shù)仿真實驗；采用慣性權重自適應調整方法改進基本粒子群算法，并在matlab程序中實現(xiàn)。3.本課題研究的重點及難點，前期已開展工作 3.1重點及難點：（

11、1）學習粒子群算法的基本原理。（2）粒子群算法的改進。（3）函數(shù)的選取和最優(yōu)解求解過程。（4）熟悉并掌握matlab編程。3.2 前期開展工作：在2010年寒假期間，通過網(wǎng)絡和書本初步學習了粒子群算法的基本原理和函數(shù)的選取，對matlab編程加以鞏固學習，另外在網(wǎng)上搜集有關資料，借閱和購買有關書籍。開學第1,2周整理相關資料，撰寫開題報告。4.完成本課題的工作方案及進度計劃（按周次填寫） 第一階段：第1周-第2周，撰寫開題報告，整理畢業(yè)設計所需資料。第二階段：第3周，撰寫并修改論文提綱。第三階段：第4周-第14周，完成實驗，外文翻譯，撰寫畢業(yè)論文。第四階段：第14周-第15周，修改畢業(yè)論文。第

12、五階段：第15周-第16周，定稿，打印，提交畢業(yè)論文。第六階段：第17周-第18周，畢業(yè)設計答辯。參考文獻：1 紀震，廖惠連，吳青華.粒子群算法及應用.北京：科學出版社，2009.16-232 崔遜學. 多目標進化算法及其應用.北京：國防工業(yè)出版社，2006.66-733 恩格爾波利特著，譚營等譯.計算群體智能基礎.北京：清華大學出版社.2009.245-2524 李麗，牛奔.粒子群優(yōu)化算法.北京：冶金工業(yè)出版社，2009.78-965 王超能.算法設計及其matlab實現(xiàn).北京:高等教育出版社,2006.10-156 吳祈宗，鄭志勇，鄧偉.運籌學與最優(yōu)化matlab編程.北京：機械工業(yè)出版社

13、，2009.164-1687 王萬良, 唐宇. 微粒群算法的研究現(xiàn)狀與展望. 浙江工業(yè)大學學報, 2, 2007: 136-1418 謝曉鋒, 張文俊, 楊之廉. 微粒群算法綜述.北京大學學報 ,2003.129-1349 kennedy j. small worlds and mega-minds: effects of neighborhood topology on particle swarm performance . in: proc. ieee congr. evol. comput. jul. 1999.19311938.10 veeramachaneni k, peram t

14、, mohan c, osadciw l a. optimization using particle swarms with near neighbor interactions a. in: proc. genetic and evolutionary computation (gecco 2003) .2003.110121. 11 abraham a, guo h, liu h. swarm intelligence: foundations, perspectives and applications . swarm intelligent systems, studies in c

15、omputational intelligence , n. nedjah, l. mourelle (eds.), springer verlag, 2006.3-25. 12 poli r, kennedy j, blackwell t. particle swarm optimization: an overview . swarm intelligence, 2007.33-57. 13 jelmer van a, robert b, bart de s. particle swarms in optimization and control. in: proceedings of t

16、he 17th world congress the international federation of automatic control seoul, korea, 2008.5131-513614 kennedy j. the particle swarm: social adaptation of knowledge a. in: proc. ieee int. conf. evol. comput. apr. 1997, pp. 303308 15 langdon w b, poli r. evolving problems to learn about particle swa

17、rm and other optimizers a. in: proc. cec-2005.2005.81-88西安工業(yè)大學畢業(yè)設計（論文）開題報告檢查表專業(yè)： 信息與計算科學 班級： 071001 學生姓名：張磊設計（論文）題目基于粒子群算法的函數(shù)優(yōu)化問題研究檢查方式開題答辯審閱開題報告檢查標準序號項目要 求滿分1文獻綜述能認真閱讀教師指定的參考資料、文獻，并能閱讀與課題有關的自選資料，能獨立搜集資料和分析、研究、綜合，論述全面。202內容理解開題符合設計任務要求，對選題內容理解準確，重點明確，預期目標得當。303設計方案所選研究方案先進、適當，技術路線嚴密，措施得當，掌握技術資料準確，可能

18、遇到的問題分析合乎邏輯，可行性好，工作安排合理、緊湊。304開題報告與表達開題報告內容表述清楚、準確，能正確回答問題。105學習態(tài)度表現(xiàn)積極主動，學習態(tài)度端正。10總 分檢查結論 同意開題 不同意開題檢查人（小組成員）簽字： 年 月 日建議與要求畢i-4注：1 “檢查方式”“檢查結論”欄內可在相應方框內劃“”。2 本表裝訂入附件冊。 畢業(yè)設計(論文)中期報告基于粒子群算法的函數(shù)優(yōu)化問題研究院（系） 數(shù)理系 專 業(yè) 信息與計算科學 班 級 071001 姓 名 張磊 學 號 071001120 導 師 過曉芳 2011年 5月5日1. 設計（論文）進展狀況本學期第二周之前收集了粒子群算法的相關資

19、料。清楚了所做論文的主要內容和任務，并且完成了基于粒子群算法的函數(shù)優(yōu)化問題的開題報告。經(jīng)過一段時間的學習，基本了解了粒子群算法的基本原理和具體流程。完成了基本粒子群算法的matlab編程代碼,并通過實驗研究了參數(shù)如何設置問題。具體學習內容如下：1.1粒子群算法原理：粒子群算法初始化為一群隨機粒子 , 然后通過迭代找到最優(yōu)解。在每一次迭代中, 粒子通過跟蹤兩個極值來更新自己。第一個就是粒子本身所找到的最優(yōu)解。另一個極值是整個種群目前找到的最優(yōu)解。這個極值是全局極值。假設在一個維的目標搜索空間中，有個粒子組成一個群落，其中第個粒子表示為一個維的向量：，第個粒子的“飛行 ”速度也是一個維的向量，記為

20、：，第個粒子迄今為止搜索到的最優(yōu)位置稱為個體極值，記為：，整個粒子群迄今為止搜索到的最優(yōu)位置為全局極值，記為：在找到這兩個最優(yōu)值時，粒子根據(jù)如下的公式(1)和(2)來更新自己的速度和位置： (1) (2)其中：和為學習因子， 和為0，1范圍內的均勻隨機數(shù)。式(1)右邊由三部分組成，第一部分為“慣性”或“動量”部分，反映了粒子的運動“習慣”，代表粒子有維持自己先前速度的趨勢；第二部分為“認知”部分，反映了粒子對自身歷史經(jīng)驗的“記憶”或“回憶”，代表粒子有向自身歷史最佳位置逼近的趨勢；第三部分為“社會”部分，反映了粒子間協(xié)同合作與知識共享的群體歷史經(jīng)驗，代表粒子有向群體或鄰域歷史最佳位置逼近的趨勢

21、，根據(jù)經(jīng)驗，通常。是粒子的速度，是常數(shù)，由用戶設定用來限制粒子的速度。和是介于之間的隨機數(shù)。1.2基本粒子群算法流程：算法的流程如下： 初始化粒子群，包括群體規(guī)模，每個粒子的位置和速度 計算每個粒子的適應度值； 對每個粒子，用它的適應度值和個體極值比較，如果 ，則用替換掉； 對每個粒子，用它的適應度值和全局極值比較，如果則用替； 根據(jù)公式（1），（2）更新粒子的速度和位置 ； 如果滿足結束條件(誤差足夠好或到達最大循環(huán)次數(shù))退出，否則返回1.3函數(shù)測試實驗利用matlab編寫出基本粒子群算法代碼，選取了以下兩個函數(shù)進行了基本粒子群算法的測試，通過調整學習因子和慣性權重,求出函數(shù)的全局極值（最優(yōu)

22、解）。第一個函數(shù)是sphere函數(shù)：，-10，10 第二個函數(shù)是rastrigrin函數(shù)：，-100，100 2. 存在問題及解決措施存在問題：（1）粒子群算法中，各個參數(shù)如何設置。（2）如何實現(xiàn)慣性權重自適應的調整。解決措施：（1） 粒子群算法中，主要的參數(shù)有：粒子種群大小n；粒子的長度d；學習因子；慣性權重。通過對測試函數(shù)在基本粒子群算法中的測試，參數(shù)設置總結如下： 粒子種群大小n：較小的種群能充分探索解的空間，避免了過多的適應值評估和計算時間，10個粒子已經(jīng)足夠取得好的結果。粒子的長度d：這是由優(yōu)化問題決定的，就是問題解的長度。學習因子：實驗中通過設置 的值，發(fā)現(xiàn)當為1.5和2時，能以最

23、小的迭代次數(shù)搜索到最優(yōu)解。慣性權重：通過實驗，讓慣性權值隨著疊代次數(shù)的增加在1. 4到0之間逐步減少可以取得較好的效果。（2）根據(jù)種群多樣性變化非線性的調整的值。利用下式實現(xiàn)：其中，s(t)為種群多樣性指數(shù)。3. 后期工作任務及安排準備5月10號的中期答辯。第12周-第14周，在基本粒子群算法的基礎上，通過慣性權重自適應的調整對基本粒子群算法進行改進，另外選取幾個典型的測試函數(shù)，利用改進好的方法，求出全局最優(yōu)解。第14周-第16周，完成畢業(yè)論文撰寫。第16周-第17周，修改畢業(yè)論文，定稿，打印。第17周-第18周，準備畢業(yè)設計答辯。西安工業(yè)大學畢業(yè)設計（論文）工作中期檢查表姓 名張磊專業(yè)信息與

24、計算科學班級071001設計（論文）題目基于粒子群算法的函數(shù)優(yōu)化問題研究資料情況選題是否有變化 有 沒有中期報告 有 沒有英文翻譯 優(yōu) 良 中 差 工作進度 提前完成 按計劃完成 沒有完成工作態(tài)度 認真 一般 不認真工作質量 優(yōu) 良 中 差 檢查結論 通過 延期答辯 終止畢業(yè)設計（論文）存在的問題與建議： 指導教師（簽名）： 年 月 日注：1 指導教師在相應項目方框內劃“”。2 中期檢查結果應與是否有資格參加答辯相掛鉤。畢ii-23 本表裝訂入畢業(yè)設計（論文）附件冊。西安工業(yè)大學畢業(yè)設計（論文）指導教師評分表學生姓名張磊學號071001120班級071001院（系）理學院專 業(yè)信息與計算科學設

25、計（論文）題目基于粒子群算法的函數(shù)優(yōu)化問題研究序號評審項目標準滿分1業(yè)務能力與水平有收集、綜合和正確利用各種信息并獲取新知識的能力。能應用所學的基礎理論與專業(yè)知識，獨立分析和解決實際問題，完成了任務書規(guī)定的任務，軟件、硬件設計滿足要求，所得結論具有應用或參考價值，工作中有創(chuàng)新意識。302論文質量條理清晰，結構嚴謹；文筆流暢，語言通順；方法正確，分析、論證充分；設計、計算正確，工藝可行，設計圖紙質量高，標準使用規(guī)范；專業(yè)名詞術語準確。303規(guī) 范 化技術材料齊全，論文撰寫符合西安工業(yè)大學本科畢業(yè)設計（論文）撰寫規(guī)范的要求。204外語水平英文摘要寫作水平高，外文翻譯符合任務要求。105工作態(tài)度嚴肅認真，刻苦勤奮，善于與他人合作。10總 分 評語：結論： 同意按期答辯 延期答辯 不同意答辯 指導教師： 年 月 日 注：1 指導教師在相應項目方框內劃“”。畢iii-12 本表裝訂入畢業(yè)設計（論文）附件冊中。西安工業(yè)大學畢業(yè)設計（論文）評閱教師評分表學生姓名張磊學號071001120班 級071001院（系）理學院專業(yè)信息與計算科學指導教師過曉芳設計（論文）題目基于粒子群算法的函數(shù)優(yōu)化問題研究序號評審項目指 標滿分1選