基于思維進化算法的PID控制器參數(shù)優(yōu)化論文（很完整）

1、*畢業(yè)設計（論文）設計說明書設計(論文)題目：基于思維進化算法的pid控制器參數(shù)優(yōu)化學 生： *專 業(yè)： 自動化班 級： *班指導教師： *設計日期：*年6月18日*畢業(yè)設計（論文）任務書畢業(yè)設計（論文）題目：基于思維進化算法的pid控制器參數(shù)優(yōu)化畢業(yè)設計（論文）要求及原始數(shù)據（資料）：在工業(yè)過程控制的發(fā)展史上，pid控制是歷史最悠久、生命力最強的控制方式。在當前的工業(yè)控制器中，有半數(shù)以上的控制采用pid或變形pid控制。pid控制器被廣泛應用主要是因為其結構簡單、實際中容易被理解和實現(xiàn)，而且許多高級控制都是以pid控制為基礎的。它直接影響控制效果的好壞，并和系統(tǒng)的安全、經濟運行有著密不可分得

2、關系。但pid參數(shù)的整定一般需要經驗豐富的工程技術人員來完成，既耗時又耗力，加之實際系統(tǒng)千差萬別，使pid參數(shù)的整定有一定的難度。思維進化算法(mea)也是針對遺傳算法(ga)所出現(xiàn)的問題而提出的一種行之有效的解決方法。它模仿人類思維進化的過程，引入了遺傳算法的群體概念，但從根本上與ga存在著不同，它提出了用于進化的趨同和異化算子，引入了公告板記錄進化過程中的信息，從而能充分利用計算機的記憶功能，利用異化過程使得其具有很好的全局搜索性能。由于引入了記憶與定向學習機制，增強了演化算法的智能性，大大提高了搜索效率，mea成功地解決了演化算法中早熟和收斂速度慢等問題，并在一些領域得到成功應用。第1頁

3、本設計是在獲取控制對象模型后，采用算法優(yōu)化pid參數(shù)，并程序實現(xiàn)。要求設計（論文）包括以下幾方面內容：1. 掌握pid控制的基本知識；2. 了解進化計算的基本原理；3. 掌握思維進化算法的基本過程；4. 掌握matlab的設計與仿真及smulink軟件包；5. 編程實現(xiàn)思維進化算法優(yōu)化pid控制器參數(shù)；6. 仿真實例研究、結果分析；7. 進化計算的不足與展望。畢業(yè)設計（論文）主要內容：本畢業(yè)設計主要工作內容包括：1. 中英文摘要及關鍵字；2. 查找及閱讀相關文獻資料，介紹工業(yè)中pid控制的應用現(xiàn)狀；3. 掌握pid控制的基本知識；4. 查找及閱讀相關文獻資料，了解進化計算；5. 查找及閱讀相關

4、文獻資料，介紹進化計算及思維進化算法的應用；6. 掌握思維進化算法的基本步驟； 7. 掌握matlab軟件的程序設計與仿真；8. 設計思維進化算法優(yōu)化pid參數(shù)；9. 應用matlab軟件及smulink軟件包仿真；10.進行編程、實驗并分析結果；第2頁11. 總結思維進化算法的不足，展望應用前景；12. 總結pid控制和各種智能方法的結合應用前景。學生應交出的設計文件（論文）：畢業(yè)論文一份，論文文本文件及程序源代碼一份。英文10000字符翻譯。第3頁主要參考文獻（資料）：1 謝克明,王麗坤,謝剛,郭紅波.基于克隆思維進化算法的機器人足球協(xié)作策略. 太原理工大學學報.2007.(5).2 李士

5、勇.模糊控制神經控制和智能控制論m.哈爾濱：哈爾濱工業(yè)大學出版社,1996.3 顧峻,沈炯,陳來九.遺傳算法對模糊控制的優(yōu)化及其應用j.東南大學學報,vol.28,1998.4 臧輝.遺傳算法及其應用.武漢科技學院學報,2005,(4).5 楊俊杰,任雪梅,黃鴻,.基于遺傳算法的多智能體協(xié)作行為研究.計算機仿真,2006,(3).6 丁軻軻,劉久斌,林青.熱工過程自動調節(jié)m.北京:中國水利電力出版社,2000.7 榮雅君,竇春霞,袁石文.過熱汽溫模糊神經網絡預測控制器的設計.中國電機工程學報,vol.23no.1,jan.2003.8 孫增圻等.智能控制理論與技術m.北京:清華大學出版社,19

6、97.9 陳來九.熱工過程自動調節(jié)原理和應用m.北京:水利電力出版社,1982.10 劉金琨.先進pid控制matlab仿真.電子工業(yè)出版社m,2006.11 王麗愛,周旭東,陳崚,孫承意.雙層mec算法優(yōu)化多峰問題.計算機工程與應用, 2007,12.專業(yè)班級自動化*級班學生*要求設計(論文)工作起止日期2008年2月25日2008年6月18日指導教師簽字日期教研室主任審查簽字日期系主任批準簽字日期第4頁摘 要進化計算是模擬生物進化過程與機制的一類隨機優(yōu)化計算模型。根據對ga存在問題的思考以及對人類思維進步的分析，模仿人類社會中存在的趨同和異化現(xiàn)象，1998年提出了思維進化算法(mea)。本

7、文首先介紹了進化計算的基本知識，闡述了思維進化算法的基本框架，特點和應用，并且利用思維進化算法進行了函數(shù)優(yōu)化，matlab軟件的仿真結果表明思維進化算法對函數(shù)優(yōu)化達到了比較好的效果。在工業(yè)過程控制的發(fā)展史上，pid控制是歷史最悠久、生命力最強的控制方式。接下來本文介紹了pid控制器的原理和應用，并且用matlab軟件實現(xiàn)了基于思維進化算法的pid控制器參數(shù)優(yōu)化。仿真結果表明思維進化算法應用于pid控制器參數(shù)優(yōu)化設計的可行性和有效性。最后本文總結了思維進化算法的不足并且展望了其應用前景。關鍵詞：進化計算；思維進化算法；matlab；pid控制器abstractthe evolution comp

8、utation which simulated the organic evolution process and mechanism was a kind of stochastic optimization computation model. according to the questions of ga and the human thinking progressive analysis, imitating the similartaxis and dissimilation phenomenon in the human society, mind evolution algo

9、rithm (mea) was proposed in 1998. this paper firstly introduced the basic knowledge of evolution computation, then introduced the basic architecture, the characteristic and the application of mind evolution algorithm. then the mind evolution algorithm carried on the function optimization, the matlab

10、 softwares simulation results had indicated that the mind evolution algorithm achieved the quite good effects to the function optimization.in the history of commercial process control, the pid control was the control mode with the longest histories and the strongest vitality. this paper also introdu

11、ced the pid controllers principles and the applications, then realized the pid controller parameter optimization design based on the mind evolution algorithm by the matlab software. the simulation results had indicated that the mind evolution algorithm applied in the pid controller parameter optimiz

12、ation feasibly and effectively. finally this paper summarized the deficiency of mind evolution algorithm and looked forward to its application perspective.key words: evolution computation; mind evolution algorithm; matlab; pid controller目 錄第1章 緒 論11.1 引言11.1.1 進化計算的發(fā)展背景11.1.2 智能控制的發(fā)展背景21.2 本文選題的意義3第

13、2章 進化計算42.1 進化計算的概述42.2 進化計算的主要分支62.2.1 遺傳算法62.2.2 進化策略72.2.3 進化規(guī)劃82.2.4 遺傳程序設計82.3 進化計算的主要特點92.4 進化計算的研究內容及其前景9第3章 思維進化算法123.1 思維進化算法的提出123.2 思維進化算法的基本框架133.2.1 思維進化算法的系統(tǒng)結構和基本知識133.2.2 三個基本機制163.3 思維進化算法的特點173.4 思維進化算法的應用17第4章 matlab軟件實現(xiàn)思維進化算法及其在函數(shù)優(yōu)化中的應用194.1 程序流程圖194.2 源程序204.3 子程序及仿真結果234.4 結果分析2

14、9第5章 pid控制的原理和應用305.1 pid控制的原理和特點305.2 pid控制原理315.2.1 模擬pid控制器315.2.2 數(shù)字pid控制器345.3 pid參數(shù)整定方法概述375.4 pid控制的性能指標395.5控制器參數(shù)對控制性能的影響415.6 pid控制的應用現(xiàn)狀41第6章 matlab軟件及simulink實現(xiàn)思維進化算法的pid控制器參數(shù)優(yōu)化446.1 matlab與simulink介紹446.1.1 matlab軟件介紹446.1.2 simulink介紹466.2 基于思維進化算法的pid控制器參數(shù)優(yōu)化方案476.3 程序流程圖476.3.1 主程序流程圖47

15、6.3.2 子程序流程圖486.4 源程序及仿真結果496.4.1 主程序496.4.2 子程序1536.4.3 仿真結果及結果分析546.4.4 子程序2576.4.5 仿真結果及結果分析58第7章 總結與展望627.1 工作總結627.2 應用前景展望62參考文獻64設計總結66致 謝67附錄一：英文68附錄二：中文78第1章 緒 論1.1 引言1.1.1 進化計算的發(fā)展背景傳統(tǒng)的進化計算是模擬“物競天擇”與“自然遺傳”的生物進化過程所產的隨機化計算模型。它的起源可以追溯到二十世紀50年代后期，其中bremermann，friedberg，box所做的工作是最具有影響的。但是，在以后的三十

16、年時間里，這一領域的工作對于廣大科學工作者來說，還是相當陌生的。造成這種狀況的原因主要是當時缺少強大的計算機硬件平臺和早期進化計算本身的方法論缺陷。一直到了二十世紀70年代，holland，rechenberg，schwefel，fogel等人的奠基性工作才慢慢地改變了這種狀況。特別是最近十年，以進化計算為主題的出版物和學術會議逐年增加，充分說明了進化計算作為一個新興學科分支的巨大潛力。如今，面向應用的進化計算研究幾乎滲透到各行各業(yè)，正掀起了一個世界范圍內的進化計算研究熱潮。那么，是什么原因使得進化計算在最近十年來被廣泛研究和應用呢？除了計算機性能有了極大的提高以外，最主要的應當歸功于進化計算

17、具有自組織性，自學習性，自適應性，自優(yōu)化等智能特征，同時又具有內在并行性，原理的簡單性，優(yōu)良的全局性，計算的隨機性與應用的廣泛性。傳統(tǒng)的進化計算是由幾個相互聯(lián)系，但事實上又是彼此獨立發(fā)展起來的分支組成的，它們是遺傳算法，進化策略，進化規(guī)劃和遺傳程序設計。其中以遺傳算法最具代表性。20世紀60年代中期，holland教授提出了遺傳算法(genetic algorithm，太原理工大學碩士學位論文簡記為ga)，它是以生物遺傳原則和類似于進化的操作為基礎的模仿的是自然界生物進化過程。經過三十多年的發(fā)展，無論在算法的改進方面，還是理論以及應用研究方面，都已取得了很大的進步。但是遺傳算法中仍然存在許多問

18、題，如建筑塊假設、早熟收斂和進化時間長等問題。根據對ga存在問題的思考以及對人類思維進步的分析，模仿人類社會中存在的趨同和異化現(xiàn)象，孫承意教授于1998年8月提出了思維進化算法(mind evolutionary algorithm，縮寫為mea)。mea繼承了ga的“群體”和“進化”的思想，但其它方面與ga均不相同，進行了重大創(chuàng)新。mea將群體劃分為若干子群體，提出了“趨同”和“異化”兩種操作?！摆呁逼痖_采的作用，而“異化”起勘探的作用，這兩個操作都隱含有選擇操作。重要的是，這二者的作用是非對立的，它們是協(xié)調工作的。趨同對系統(tǒng)從環(huán)境得到局部信息加以開采，迅速搜索局部的最優(yōu)。而異化操作在整個

19、解空間進行搜索，選擇較優(yōu)的個體作為中心，創(chuàng)建新的臨時子群體。1.1.2 智能控制的發(fā)展背景從1932年奈魁斯特(h.nyquist)發(fā)表反饋放大器的穩(wěn)定性論文以來，控制理論學科的發(fā)展已走過近70年的歷程，自動控制理論經歷了經典控制理論和現(xiàn)代控制理論兩個重要發(fā)展階段。前者主要解決單變量系統(tǒng)的反饋控制問題，而后者則著重解決多變量系統(tǒng)的優(yōu)化問題。他們在許多領域均取得了成功的應用，促進了社會生產力的發(fā)展。二十世紀七十年代中期以來，科學技術的高度發(fā)展，致使被控對象結構上的日益復雜化和大型化。傳統(tǒng)的自動控制理論面臨復雜性所帶來的困境，力圖突破舊的模式以適應社會對自動化學科提出的新要求。能否建立新一代的控制

20、理論來解決復雜系統(tǒng)的控制問題，已經成為各國控制控制理論界共同關心的熱點。在二十世紀七十年代大系統(tǒng)理論問世后的一段時間里，有人曾推測它是第三代控制理論的雛形。但這種觀點未能得到實踐的認可。實際上大系統(tǒng)理論仍未突破以往控制理論的基本思想與框架，除了高維線性系統(tǒng)之外，它對其它復雜系統(tǒng)仍然束手無策。人們開始認識到，在許多系統(tǒng)中，復雜性不僅僅表現(xiàn)在高維性上，更多的則是表現(xiàn)在系統(tǒng)信息的模糊性、不確定性、偶然性和不完全性上?；诰_數(shù)學模型的大系統(tǒng)理論當然無法解決好它們的控制問題。正當人們?yōu)閷ふ乙环N新理論費盡心機時，模糊邏輯、神經網絡、進化計算等人工智能技術由于得益于計算機技術而飛速發(fā)展，漸漸形成一門學科，

21、并在實際應用中顯示出很強的生命力。與此同時，國際學術界對智能控制的研究十分活躍，1985年ieee在美國紐約召開了第一屆智能控制學術討論會，這次會議的召開，為智能控制作為一個獨立的新學科在國際學術界的崛起奠定了基礎。接著1988年8月召開了第二屆智能控制的國際會議，以后智能控制會議每年都舉行一次。到了二十世紀九十年代，各種智能控制的國際學術會議日益頻繁。國內在八十年代初開始智能控制的研究，并在許多領域成功進行了應用。智能控制是一個新興的學科領域，它是隨著計算機技術的進步在經典控制理論和現(xiàn)代控制理論的基礎上發(fā)展起來的。與傳統(tǒng)的控制理論相比，智能控制對于環(huán)境和任務的復雜性有更大的適配程度。它不僅僅

22、是對建立的模型，而且對于環(huán)境和任務能抽取多級的描述精度，進而發(fā)展了自學習、自適應和自組織等概念，所以能在更廣泛的領域中獲得應用。雖然智能控制理論只有十幾年的歷史，尚未形成比較完整的理論體系，但其應用成果和理論發(fā)展己說明智能控制正成為自動控制的前沿學科之一。pid控制3是工業(yè)生產中應用較為廣泛的一種控制方式，它原理簡單、形式固定，控制效果一般比較令人滿意，容易被廣大工程技術人員所接受，因此研究pid控制器參數(shù)的整定技術具有重要意義。1942年ziegler-nichols方法被提出，并得到了廣泛的應用和改進；后來又出現(xiàn)了cohen-coon響應曲線方法和kappakau調節(jié)方法。但是，由于此類p

23、id控制器參數(shù)整定技術大都是對經驗的總結，只能適用于滿足經驗公式條件的對象，且只利用了較少的系統(tǒng)動態(tài)特性信息，所以得到的控制器性能也是很局限的。隨著遺傳算法(ga)的提出，又出現(xiàn)了利用遺傳算法對pid控制器參數(shù)進行優(yōu)化整定的算法。但遺傳算法22要涉及到繁瑣的編碼、譯碼過程以及較大的計算量，而且在整個搜索過程中，染色體互相共享信息，整個種群是比較均勻地向最優(yōu)區(qū)域移動，影響該算法的尋優(yōu)效率。針對遺傳算法存在的問題并受到新研究進展的啟發(fā)，孫承意于1998年提出了基于思維進化的機器學習算法，即思維進化算法mea(mind evolutionary algorithm)，該算法繼承了進化算法(ec)中“

24、群體”和“進化”的概念，引入趨同和異化兩種操作，模擬人類思維、知識的進化過程。思維進化算法突破了自然進化的限制，在進化中引入了記憶與定向學習機制，增強了進化算法的智能程度，提高了搜索效率，成功解決了進化計算中早熟和收斂速度慢等問題。本文借助mea算法的群體尋優(yōu)能力來優(yōu)化整定pid控制參數(shù)。1.2 本文選題的意義在工業(yè)過程控制中，目前采用最多的控制方式依然是pid方式。pid3控制器被廣泛應用主要是因為其結構簡單、實際中容易被理解和實現(xiàn)，而且許多高級控制都是以pid控制為基礎的。它直接影響控制效果的好壞，并和系統(tǒng)的安全、經濟運行有著密不可分得關系。然而，pid參數(shù)復雜繁瑣的整定過程一直困擾著工程

25、技術人員，研究pid參數(shù)自整定技術具有十分重大的工程實踐意義。pid的設計與參數(shù)整定依然是工業(yè)控制中的一個研究重點。原因就在于pid比例系數(shù)、積分系數(shù)、微分系數(shù)三個參數(shù)需要設計和整定，再加上采樣周期等系統(tǒng)參數(shù)需要選擇，因此要設計出理想的參數(shù)有相當?shù)碾y度。傳統(tǒng)的整定方法有ziegler-nichols整定算法、cohen-coon整定算法，基于幅值與相位裕量設定的算法等，這些方法都屬于經驗設計方法。新的設計和整定方法都把重點放在pid控制器的優(yōu)化設計及自適應設計上。本文試圖利用思維進化算法的群體尋優(yōu)能力來優(yōu)化pid控制器的參數(shù)，通過matlab軟件在給定的目標函數(shù)下，利用思維進化算法，搜索最優(yōu)參

26、數(shù)，并利用程序實現(xiàn)。第2章 進化計算2.1 進化計算的概述當前科學技術正進入多學科互相交叉、互相滲透、互相影響的時代。這一點在計算機科學領域表現(xiàn)得尤為突出。一方面，計算機科學的迅猛發(fā)展，從根本上改變了人類的生活、學習和工作的方式，使人類文明進入了一個嶄新的時代；另一方面，隨著人類生存空間的擴大和認識世界改造世界范圍的拓寬，人們又對計算機科學提出了新的要求與期望。而所有的期望值中，對計算機的計算速度和具有智能的要求可能是最迫切和最基本的。很多實際應用問題不僅涉及到大量的計算而且需要實時響應，這對計算機的速度提出了強有力的挑戰(zhàn)。由于提高單機速度受其物理極限的限制，解決這一問題的根本途徑便是并行化。

27、雖然目前并行機已較為普遍，但因為缺乏有效的并行算法，以至于使用并行機難以獲得較高的加速比。制造出具有智能的機器一直是人類的夢想，直到1956年人工智能技術的出現(xiàn)，人們已為此作出了巨大的努力。近年來，隨著人工智能應用領域的不斷拓寬，傳統(tǒng)的基于符號處理機制的人工智能方法在知識表示、處理模式信息及解決組合爆炸等方面所碰到的困難己變得越來越突出，甚至使得某些學者對強人工智能提出了強烈批評，對人工智能的可能性提出了質疑。基于上述原因，尋求一種適于大規(guī)模并行機且具有某些智能特征如自組織、自適應、自學習等的算法已成為有關學科的一個研究目標。近年來，一些新的研究方向如神經網絡、細胞自動機和進化計算等，由于它們

28、都是模擬某一自然現(xiàn)象或過程而發(fā)展起來的，并且具有適于高度并行、自組織、自適應、自學習的特征，因而引起了人們的極大興趣。這些新方法通過“擬物”與“仿生”以使問題得到解決，它們也許能為解決某些復雜問題提供新的契機。大自然是我們解決各種問題時獲得靈感的源泉。幾百年來，將生物界所提供的答案應用于實際問題的求解已被證明是一個成功的方法，并且已形成了一個專門的科學分支仿生學(bionics)。自然界所提供的答案是經過漫長的自適應過程進化過程而獲得的結果。除了進化過程的最終結果，我們也可以利用這一過程本身去解決一些較為復雜的問題。這樣，我們不必非常明確的描述問題的全部特征，只需要根據自然法則來產生新的更好解

29、。進化計算正是基于這種思想而發(fā)展起來的一種通用的問題求解方法。從19世紀50年代開始就有許多作者開始利用達爾文的進化論解決優(yōu)化問題，在以后的30年中出現(xiàn)了許多基于此概念的算法，一般稱為“進化計算方法”，它采用簡單的編碼技術來表示各種復雜的結構，并通過對一組編碼表示進行簡單的遺傳操作和優(yōu)勝劣汰的自然選擇來指導學習和確定搜索的方向。由于它采用種群（即一組表示）的方式組織搜索，這使得它可以同時搜索解空間的多個區(qū)域。而且用種群組織搜索的方式使得進化計算特別適合大規(guī)模并行。在賦予進化計算自組織、自適應、自學習等特征的同時，優(yōu)勝劣汰的自然選擇和簡單的遺傳操作使進化計算具有不受其搜索空間限制性條件（如可微、

30、連續(xù)、單峰等）的約束及不需要其它輔助信息（如導數(shù)）的特點。這些嶄新的特點使得進化計算不僅能獲得較高的效率而且具有簡單、易于操作和通用的特性，而這些特性正是進化計算越來越受到人們青睞的主要原因之一。進化計算在20世紀六七十年代并未受到普遍的重視。其主要原因一是當時這些方法本身還不夠成熟；二是由于這些方法需要較大的計算工作量，而當時的計算機還不夠普及而且速度也跟不上要求，這樣便限制了它們的應用；三是當時基于符號處理的人工智能方法正處于其頂峰狀態(tài)，使得人們難以認識到其它方法的有效性及適應性。到了20世紀80年代，人們越來越清楚地意識到傳統(tǒng)人工智能方法的局限性，并且由于計算機速度提高以及并行計算機的普

31、及，進化計算對機器速度的要求己不再是制約其發(fā)展的因素。更由于進化計算的不斷發(fā)展及其在一些應用領域內取得的成功，表現(xiàn)出了良好的應用前景。德國dortmund大學1993年末的一份研究報告報導，據不完全統(tǒng)計進化計算已在16個大領域250多個小領域獲得了應用。由于進化計算在機器學習、過程控制、經濟預測、工程優(yōu)化等領域取得的成功，己引起了包括數(shù)學、物理學、化學、生物學、計算機科學、社會科學及工程應用等領域科學家們的極大興趣。自80年代中期以來，世界上許多國家都掀起了進化計算的研究熱潮。目前，有數(shù)種以進化計算為主題的國際會議在世界各地定期召開。國際互聯(lián)網上也有多種相關的mailing list，usen

32、et還有專門的新聞組comp.ai.genetic。由于化計算應用范圍之廣泛，從一些雜志及國際會議論文集中都比較容易看到這方面的文章?，F(xiàn)在已出版兩種專門關于進化計算的新雜志“evolutionary computation”和“ieee transactions on evolutionary computation”而且一些國際性期刊也競相出版以進化計算為主題的專刊。新的一輪日本計算機發(fā)展規(guī)劃rwc計劃(real world computing program)也把進化計算作為它的主要支撐技術之一，以進行信息的集成、學習及組織等19。另外，某些學者研究了進化計算的自現(xiàn)行為(emeregent

33、 behavior)后聲稱，進化計算將與混沌理論和分形幾何一道成為人們研究非線性現(xiàn)象和復雜系統(tǒng)的新的三大方法，并將與神經網絡一道成為人們研究認知過程的重要工具。當前，進化計算的研究內容十分廣泛，如進化計算的設計與分析、進化計算的理論基礎及其在各個領域中的應用等等?？梢灶A料隨著進化計算研究的不斷深入和應用領域的不斷拓寬，進化計算將取得更大的成功16。2.2 進化計算的主要分支自計算機出現(xiàn)以來，生物模擬（也稱仿生）成了計算機科學的一個組成部分。其目的一是企圖建立一種人工模擬環(huán)境，以便使用計算機進行仿真，以更好地了解人類自己和人類的生存空間；二是從研究生物系統(tǒng)出發(fā)，探索產生基本認知行為的微觀機理，然

34、后設計成具有生物智能的機器或模擬系統(tǒng)以解決更為復雜的問題。如神經網絡、細胞自動機和進化計算都是從不同角度模擬生物系統(tǒng)而發(fā)展起來的研究方向。進化計算最初具有三大分支：遺傳算法(genetical gorithm，簡稱ga)，進化規(guī)劃(evolutionary programming，簡稱ep)和進化策略(evolution strategy，簡稱es)。20世紀90年代初，在遺傳算法的基礎上又發(fā)展了一個分支：遺傳程序設計(genetic programming，簡稱gp)。雖然這幾個分支在算法實現(xiàn)方面具有一些細微的差別，但它們具有一個共同特點，都是借助生物進化的思想和原理來解決實際問題的。下面本

35、文將分別對幾個分支作一個簡單的介紹。2.2.1 遺傳算法把計算機科學與進化論結合起來的嘗試始于20世紀50年代末，但由于缺乏一種通用的編碼方法，使得人們只能依賴變異而不是交叉來產生新的基因結構，故而收效甚微。到20世紀60年代中期，美國密西根大學的john holland在a.s.frase和h.j.bremermann等工作的基礎上提出了位串編碼技術，這種編碼既適合于變異又適合交叉（即雜交）操作，他還強調將交叉作為主要的遺傳操作。隨后，john holland將該算法用于自然和人工系統(tǒng)的自適應行為的研究之中，并于1975年出版了其開創(chuàng)性的著作(daptationin nauraland ar

36、tificial system)后來，john holland與他的學生們將該算法加以推廣并應用到優(yōu)化及機器學習的問題之中，并且正式定名為遺傳算法。遺傳算法的通用編碼技術及簡單有效的遺傳操作為其廣泛的應用和成功奠定了基礎6。john holland的遺傳算法常被稱為簡單遺傳算法(sga)，其操作對象是一群二進制串（稱為染色體、個體），即種群(population)。這里每個染色體都對應于問題的一個解。從初始群體出發(fā)，采用基于適應值比例的選擇策略在當前種群中選擇個體，使用雜交(crossover)和變異(mutation)來產生下一代種群。如此一代代演化下去，直到滿足期望的終止條件5。遺傳算法可

37、以形式化描述如下：這里=(（0）,(0),.,(0)，表示初始群體；表示長度為的二進制串全體，稱為位串空間；n表示種群中含有個體的個數(shù)；表示二進制串的長度；s:表示選擇策略；g表示遺傳算子，通常它包括繁殖算子:、雜交算子和變異算子；表示遺傳算子的操作概率，包括繁殖概率,雜交概率和變異概率；是適應度函數(shù)；是終止準則。當然，目前的遺傳算法己不再局限于二進制編碼。同z.michalewicz將不同的編碼策略(即不同的數(shù)據結構)與遺傳算法的結合稱為進化程序(evolution program)。2.2.2 進化策略20世紀60年代初，柏林工業(yè)大學的z.rechenberg和h.-p.schwefel等

38、在進行風洞實驗時，當遇到設計中描述物體形狀的參數(shù)難以用傳統(tǒng)方法進行優(yōu)化時，他們利用生物變異的思想來隨機地改變參數(shù)值并獲得了較好的結果。隨后，他們便對這種方法進行了深入地研究，使其不斷發(fā)展完善，形成了進化計算的另一個分支進化策略。早期進化策略的種群中只包含一個個體，而且只使用變異操作。在每一進化代，變異后的個體與其父體進行比較再選擇兩者之優(yōu)。這一選擇策略日前稱為(1+1)策略。它使用的變異算子是基于正態(tài)分布的變異操作，這種進化策略稱為(1+1)進化策略和二元進化策略。(1+1)進化策略存在很多弊端，如有時收斂不到全局最優(yōu)、效率較低等。它的改進即是增加種群內個體的數(shù)量，從而形成(+l)進化策略。此

39、時種群內含有個個體，隨機地選取一個個體進行變異，然后取代群體中最差的個體。(+1)進化策略與(1+1)進化策略的相似之處是每次只產生一個后代。為了進一步提高效率，后來發(fā)展成(+)進化策略和(，)進化策略，并且引進了重組(recombination)操作，即由二個個體按類似于雜交方式生成一個新個體(+)進化策略根據種群內的個個體產生個個體(用變異和重組)，然后將這(+)個體進行比較再在其中選取個優(yōu)勝者。(，)進化策略則是在新產生的()個個體中選擇個最優(yōu)者。這兩種進化策略的選擇方法分別被稱為(+)和(，)選擇。進化策略與遺傳算法不同之處還在于遺傳算法要將原問題的解空間映射到位串空間中，然后再施行遺

40、傳操作，它強調個體基因結構的變化對其適應度的影響。而進化策略則是直接在解空間上進行操作，它強調進化過程中從父代到后代行為的自適應性和多樣性。從搜索空間的角度來說，進化策略所強調的是直接在解空間上進行操作，強調進化過程中搜索方向和步長的自適應調節(jié)。進化策略主要用于求解數(shù)值優(yōu)化問題。近年來，遺傳算法也采用十進制編碼（或稱浮點數(shù)編碼）技術來求解數(shù)值優(yōu)化問題。進化策略與遺傳算法的相互滲透使得它們之間沒有很明顯的界限。2.2.3 進化規(guī)劃進化規(guī)劃(evolutionary programming)的方法最初是由l.j.fogel等在20世紀60年代提出的。他們在人工智能的研究中發(fā)現(xiàn)，智能行為即是要具有能

41、預測其所處環(huán)境的狀態(tài)，并按照給定的目標作出適當響應的能力。在研究中，他們將模擬環(huán)境描述成為由有限字符集中的符號組成的序列。于是問題便轉化為怎樣根據當前觀察到的符號序列作出響應以獲得最大的收益，這里收益的計算是按照環(huán)境中將要出現(xiàn)的下一個符號及預先定義好的效益目標來確定的。進化規(guī)劃中常用的有限態(tài)自動機(finite statemachine，簡稱fsm)來表示這種的策略。這樣，問題便成為如何設計出一個有效的fsm?l.j.fogel等借用進化的思想對一群fsm進行進化以獲得較好的fsm。他們將此方法應用到數(shù)據診斷、模式識別和分類以及控制系統(tǒng)的設計等方面，并取得了較好的結果。后來，d.b.fogel

42、借助于進化策略方法對進化規(guī)劃進行了發(fā)展，并用到解決數(shù)值優(yōu)化及神經網絡的訓練等問題之中。2.2.4 遺傳程序設計自從計算機出現(xiàn)以來，計算機科學的一個重要目標是讓計算機自動進行程序設計，即只要明確地告訴計算機要解決的問題，而不需要告訴它如何去做，遺傳程序設計(genetic programming)便是在該領域中的一種嘗試。它采用遺傳算法的基本思想，但使用一種更為靈活的表示方式分層結構來表示其解空間。這些分層結構的葉結點是問題的原始變量，中間節(jié)點則是組合這些原始變量的函數(shù)。它們還類似于lisp語言中的s一表達式。這樣的每一個分層結構對應問題的一個解。也可以理解為求解該問題的一個計算機程序。遺傳程序

43、設計是使用一些遺傳操作動態(tài)地改變這些機構，從而獲得解決該問題可行性的計算機程序。遺傳程序設計的思想是斯坦福大學的j.r.koza在20世紀90年代初提出的，并于1992年出版了專著“genetic programming”，1994年又出版了第二卷。由于遺傳程序設計所采用的是一種更自然的表示方式，所以它應用領域非常之廣。日本atr研究中心的h.de garis甚至提出遺傳程序設計不僅可以進化計算機程序，而且可以進化任何復雜系統(tǒng)。他目前正致力于cam-brain計劃，正是基于這種思想之上的。該計劃的目標是要制造具有人類大腦部分功能的人工腦(artificial brain)。2.3 進化計算的主

44、要特點進化計算與傳統(tǒng)的方法有很多不同之處，但最主要的特點體現(xiàn)在下述兩方面:1.智能性進化計算的智能性包括自組織、自適應和自學習性等。應用進化計算求解問題時，確定了編碼方案、適應值函數(shù)及遺傳算子之后，算法將利用進化過程中獲得的信息自行組織搜索。由于基于自然的選擇策略為適者生存、不適應者淘汰，故適應值大的個體具有較高的生存概率。通常適應值大的個體具有對環(huán)境較適應的基因結構，再通過雜交和基因突變等遺傳操作就可能產生與環(huán)境更適應的后代。進化計算的這種自組織、自適應特征也賦予了它具有根據環(huán)境的變化自動發(fā)現(xiàn)環(huán)境的特性和規(guī)律的能力。自然選擇消除了算法設計過程中的一個最大障礙即需要事先描述問題的全部特點，并說

45、明針對問題的不同特點算法應采取的措施。因而，利用進化計算的方法，可以解決那些結構尚無人能理解的復雜問題。2.本質并行性進化計算的本質并行性表現(xiàn)在兩個方面:一是進化計算是內在并行(inherent parallelism)，即進化計算本身非常適合大規(guī)模并行。最簡單的并行方式是上幾百甚至數(shù)千臺計算機各自進行獨立種群的進化計算，運行過程中不進行任何通信，等到運算結束時才通信比較，選取最佳個體，這種并行處理方式對并行系統(tǒng)結構也沒有什么限制和要求?？梢哉f，進化計算適合在目前所有的并行機和分布式系統(tǒng)上進行并行處理，而且對其并行效率沒有太大的影響。二是進化計算的內含進行性(implicit parallel

46、ism),由于進化計算采用種群的方式組織搜索，從而它可以同時搜索解空間的多個區(qū)域，并相互交流信息，這種搜索方式使得它雖然每次只執(zhí)行與種群規(guī)模成比例的計算，而實際上己進行了大約次有效搜索。這使得進化計算能以較少的計算獲得較大的收益。2.4 進化計算的研究內容及其前景進化計算的研究內容相當廣泛，反映了多學科相互交叉的特點。目前進化計算的研究主要集中在以下幾個方面:1.進化計算的理論研究:由于進化計算缺乏統(tǒng)一、完整的理論體系，目前一些理論結果主要集中在收斂性分析，但很難給出收斂速度的估計。諸如在編碼方案的選擇、控制參數(shù)的選取、如何根據特定的編碼方案設計有效的遺傳算子以及算法的分析和性能評價等等方面，

47、只能就具體問題具體分析。而且分析主要依賴計算機模擬的實驗結果，現(xiàn)在還缺乏嚴密、科學的一般規(guī)律和方法。為了推動進化計算研究的發(fā)展，迫切需要宏觀的理論指導。2.新的計算機模型:進化計算目前實現(xiàn)的計算模型只是生物進化模型的很小一部分。近年來實現(xiàn)的免疫系統(tǒng)模型和協(xié)同進化模型等在解決某些問題是取得了較好效果。這對嘗試新的進化模型是一種促進。3.進化優(yōu)化:當代科學技術的各個領域都存在大量的優(yōu)化問題。雖然優(yōu)化方法有很多分支且碩果累累，但是實際存在的問題是千變萬化的，形成的數(shù)學模型自然也是千姿百態(tài)五花八門。因此要想以一種優(yōu)化方法有效地解決所有的問題是不現(xiàn)實也是不可能的。近年來，進化計算在解決復雜優(yōu)化問題方面取

48、得了振奮人心的成就。但是在如何根據具體問題設計有效的進化算法以提高計算速度及解決約束優(yōu)化等方面，還有許多工作需要去做。4.進化人工神經網絡:人工神經網絡(ann)是近年來受到廣泛關注的一個研究領域。在神經網絡的應用中，ann的網絡結構的設計和權值的訓練是一個十分困難而重要的問題，傳統(tǒng)方法大多是憑經驗或啟發(fā)知識來設計網絡，用梯度法來確定其中的權值，因此常常需要進行反復試驗而且還很難找到最優(yōu)的網絡結構和權值。而進化計算為ann的自動設計和訓練提供了一種新的途徑。但目前的一些研究成果還主要集中在小型網絡的設計上，在實用化方面還面臨著很多問題需要解決。5.并行和分布式進化計算:對并行進化計算的研究表明

49、，通過多個種群的進化和適當?shù)乜刂品N群的相互作用，可以提高求解的速度和解的質量。并行化甚至可以使進化計算獲得超線性加速比。由于進化計算的并行處理平臺可以是大規(guī)模并行計算機系統(tǒng)也可以是分布式處理系統(tǒng)(如工作站群集等)。因此，近幾年來，對并行和分布式進化計算的研究也越來越受到重視孟目前已有幾種較為成功的并行化和分布式模型。但是，種群之間以什么方式進行聯(lián)系和進行多大的通信才能獲得更大的效率以及其它并行化模型的研究都將是以后研究的重點。6.進化機器學習:傳統(tǒng)的機器學習方法都是根據預先確定的規(guī)則和知識來決定所采取的策略。因而它很難用于環(huán)境不斷變化的問題之中，而進化計算正好可以為此助一臂之力。目前，進化計算

50、的機器學習方法，如分類系統(tǒng)等正被越來越多地應用到實際問題中。將進化計算與一些啟發(fā)式的機器學習方法相結合將可能是今后研究的一個重點。7.進化計算應用系統(tǒng):在理論與算法研究的基礎上，利用進化計算組成實際的應用系統(tǒng)，如用于圖像處理和模式識別、制造機器人、進行最優(yōu)控制等等。在設計各類應用系統(tǒng)的算法時，把進化計算與傳統(tǒng)的啟發(fā)式搜索算法結合起來可能會取得更好的結果。8.進化硬件:微電子工業(yè)的發(fā)展使得計算機硬件的成本越來越低，而軟件的成本越來越高。利用硬件的冗余實現(xiàn)對硬件的可編程是提高軟件效率的一種途徑。同時硬件可隨環(huán)境的變化而變化本身在工業(yè)中也可以找到很多的應用。隨著硬件電路的復雜度和密度增加，按照藍圖設

51、計方法進行設計，對于設計人員來說，必將超出其極限而不堪重負。實現(xiàn)硬件的自動演化將是對傳統(tǒng)的硬件設計方法藍圖設計的一次革命。它也將給我們帶來新的機遇與挑戰(zhàn)。9.進化軟件:基于遺傳程序設計而展開的自動式程序設計，正在發(fā)展成對進化軟件的研究。10.進化計算內涵的擴充:進化計算已從模擬生物的進化過程擴充到模擬大自然的進化過程(problem solving from nature，也稱natural computation)。它不僅采用“仿生”策略，也通過模擬“擬物”，進化過程來進行問題求解。隨著進化計算研究熱潮的興起，人工智能再次成為人們關注的一個焦點。有些學者甚至提出進化計算是人工智能的未來。其觀

52、點是雖然我們不能完全用機器代替人的自然智能，但我們可以利用進化獲得智能圈。目前，進化計算與神經網絡、模糊系統(tǒng)一起己形成一個新的研究方向計算智能(computational intelligence)。人工智能己從傳統(tǒng)的基于符號處理的符號主義向以神經網絡為代表的連接主義和以進化計算為代表的進化主義方向發(fā)展。雖然進化計算模擬了生物的進化過程，但是目前進化算法中群體的規(guī)模遠遠小于生物進化系統(tǒng)。隨著大規(guī)模并行計算機和分布式計算機系統(tǒng)性能的不斷提高以及對生物進化系統(tǒng)的進一步認識，我們將有可能模擬更接近于自然的進化系統(tǒng)。這樣，進化計算的本質并行性將得到充分發(fā)揮，從而為進一步揭示生命和智能的奧秘寫下新的篇章

53、。第3章 思維進化算法3.1 思維進化算法的提出遺傳算法是由holland教授提出來的，它模仿的是自然界的生物進化過程。經過三十多年的發(fā)展，無論在算法的改進方面，還是理論以及應用研究方面，都已取得了很大的進步和成功。但是遺傳算法中仍然存在許多問題，如建筑塊假設、早熟收斂和進化時間長等問題。自然界的生物通過遺傳和自然選擇，進化了數(shù)億年。而人類的思維進步的速度卻遠高于生物的進化。其原因為：人類能向前人和周圍的成功者學習。隨著信息技術的進步、信息交流的便利，近二百年人類的思維進步越來越快。人類的這種學習并不是簡單的模仿前人和成功者的行為，而是在他們的經驗的基礎上發(fā)展進步。同時人類不斷地改變自己的思維

54、方式，探索新的領域。正是這種探索，使新科學、新技術、新方法和新觀念不斷涌現(xiàn)。這兩種思維方式相互作用加速了科技的發(fā)展，推動了生產力的快速進步。針對ga存在的缺點，模仿人類思維進步的過程，孫承意教授于1998年8月提出了思維進化算法1(mind evolutionary algorithm，縮寫為mea)他給出了mea的框架，闡述了mea的產生。需要說明的是：在早期，該算法的名稱為“基于思維進化的機器學習(mind-evolution-based machine learning，縮寫為mebml)”，為了便于提及，接受國內外一些學者的建議，后來決定改名為“思維進化算法”，其內容完全不變。mea繼

55、承了ga的“群體”和“進化”的思想，但其它方面與ga均不相同，進行了重大創(chuàng)新。mea將群體劃分為若干子群體，提出了“趨同”和“異化”算子。進化操作“趨同”起開采的作用，“異化”起勘探的作用，這兩個操作都隱含有選擇操作。重要的是，這二者的作用是非對立的。趨同對系統(tǒng)從環(huán)境得到局部信息加以開采，迅速搜索局部最優(yōu)。而異化操作在整個解空間進行搜索，選擇較優(yōu)的個體作為中心創(chuàng)建新的臨時子群體。這兩種操作是協(xié)調工作的，趨同和異化操作的改進對整個算法提高搜索效率都有貢獻。另外需要說明的一點是：這里使用了術語“思維進化”，嚴格地說應該是“思維進步”。生物的進化采用的是一種非定向的機制，進化的概念并不天然地包含進步

56、意義，即不包含某種目標，也不暗示某種方向。生物進化中的適應是非常局部的、非定向的和近似的。這里借用進化一詞是要表明mea算法的基本思想是與進化計算的基本思想是一致的，mea屬于進化計算的一部分1。3.2 思維進化算法的基本框架3.2.1 思維進化算法的系統(tǒng)結構和基本知識mea的主要組成部分如圖3-1所示。下面我們將詳細介紹結構圖中的組成部分13。1群體和子群體思維進化算法是一種通過迭代進行進化的“學習”方法。進化的每一代中的所有個體的集合稱為一個群體。一個群體分為若干個子群體。子群體有兩類：優(yōu)勝子群體(superior group)和臨時子群體(temporary group)。優(yōu)勝子群體記錄

57、全局競爭中的優(yōu)勝者的信息，臨時子群體記錄全局競爭的中間過程。2公告板公告板(billboard)為個體之間和子群體之間交流信息提供了機會。公告板包含三個基本信息(或稱為必要信息)：個體或子群體的序號，動作(action)，得分(score)。動作的描述是與領域有關的，即動作的描述因領域而異。根據需要，還可以包含其它信息，如前若干代的信息。個體的得分是個標量，它是環(huán)境對個體動作的評價。這些信息就是個體得到的關于環(huán)境的知識。公告板中的信息根據應用的不同可以按不同的要求排序。子群體內的個體在局部公告板(local billboard)張貼各自的信息。全局公告板(global billboard)用于張貼各子群體的信息。3趨同和異化趨同(similartaxis)和異化(dissimilation)是mea重要的概念。下面給出它們的定義。在“學習”初期，個體在