人工智能基礎(chǔ)07自動規(guī)劃系統(tǒng)課件

1、目錄第一章緒論第二章知識表示 第三章搜索技術(shù)第四章推理技術(shù)第五章機器學(xué)習(xí) 第六章專家系統(tǒng) 第七章自動規(guī)劃系統(tǒng)第八章 自然語言理解第九章 智能控制第十章 人工智能程序設(shè)計自動規(guī)劃概述基于謂詞邏輯的規(guī)劃STRIPS規(guī)劃系統(tǒng)分層規(guī)劃基于專家系統(tǒng)的機器人規(guī)劃軌跡規(guī)劃簡介7.1 自動規(guī)劃概述7.1.1 規(guī)劃的概念及作用 1. 規(guī)劃的概念 定義7.1 從某個特定的問題狀態(tài)出發(fā)，尋求一系列行為動作，并建立一個操作序列，直到求得目標(biāo)狀態(tài)為止。這個求解過程就稱為規(guī)劃。 定義7.2 規(guī)劃是對某個待求解問題給出求解過程的步驟。規(guī)劃涉及如何將問題分解為若干相應(yīng)的子問題，以及如何記錄和處理問題求解過程中發(fā)現(xiàn)的各子問題間

2、的關(guān)系。 定義7.3 規(guī)劃系統(tǒng)是一個涉及有關(guān)問題求解過程步驟的系統(tǒng)。如計算機或飛機設(shè)計、火車或汽車運輸路徑、財政和軍事規(guī)劃等問題。7.1 自動規(guī)劃概述7.1.1 規(guī)劃的概念及作用 例：救援仿真機器人系統(tǒng)（RoboCup Rescue Simulation System，RCRSS） 消防智能體 醫(yī)療智能體 警察智能體 普通市民 中心智能體 路障 避難所 著火建筑物 普通建筑物） 7.1 自動規(guī)劃概述7.1.1 規(guī)劃的概念及作用 2. 規(guī)劃的作用 規(guī)劃可用來監(jiān)控問題求解過程，并能夠在造成較大的危害之前發(fā)現(xiàn)差錯。規(guī)劃的好處可歸納為簡化搜索、解決目標(biāo)矛盾以及為差錯補償提供基礎(chǔ)。 “十二五”規(guī)劃、城市

3、規(guī)劃、企業(yè)發(fā)展規(guī)劃7.1 自動規(guī)劃概述7.1.2 規(guī)劃的分類和問題分解途徑 1. 規(guī)劃的分類 （1）按規(guī)劃內(nèi)容分 國家、地方、重大項目、企業(yè)、交通、城市、環(huán)境 （2）按規(guī)劃方法分 非遞階（非分層）規(guī)劃與遞階（分層）規(guī)劃；線性規(guī)劃與非線性規(guī)劃；同步規(guī)劃與異步規(guī)劃；基于腳本、框架和本體的規(guī)劃；基于專家系統(tǒng)的規(guī)劃；基于競爭機制的規(guī)劃； （3）按規(guī)劃實質(zhì)分 任務(wù)規(guī)劃、路徑規(guī)劃、軌跡規(guī)劃7.1 自動規(guī)劃概述7.1.2 規(guī)劃的分類和問題分解途徑 2. 問題分解途徑把某些較復(fù)雜的問題分解為一些較小的子問題。有兩條實現(xiàn)這種分解的重要途徑。第一條重要途徑是當(dāng)從一個問題狀態(tài)移動到下一個狀態(tài)時，無需計算整個新的狀態(tài)

4、，而只要考慮狀態(tài)中可能變化了的那些部分。第二條重要途徑是把單一的困難問題分割為幾個有希望的較為容易解決的子問題。7.1 自動規(guī)劃概述7.1.2 規(guī)劃的分類和問題分解途徑 3. 域的預(yù)測和規(guī)劃的修正 （1）域的預(yù)測 問題論域的預(yù)測。對于不可預(yù)測的論域，考慮可能的結(jié)果集合，按照它們出現(xiàn)的可能性以某個次序排列。然后，產(chǎn)生一個規(guī)劃、并試圖去執(zhí)行這個規(guī)劃。 （2）規(guī)劃的修正 規(guī)劃執(zhí)行失敗導(dǎo)致對規(guī)劃的修正。 在規(guī)劃過程中不僅要記錄規(guī)劃的執(zhí)行步驟，而且要記錄每一步必須要執(zhí)行的理由。7.2 基于謂詞邏輯的規(guī)劃 用謂詞邏輯來描述世界模型及規(guī)劃過程。 世界模型的謂詞邏輯表示定義謂詞確定問題初始狀態(tài)確定問題目標(biāo)狀態(tài)

5、確定基本操作 基于謂詞邏輯規(guī)劃的基本過程問題分解子問題規(guī)劃得到操作序列7.3 STRIPS規(guī)劃系統(tǒng) 7.3.1 積木世界的機器人規(guī)劃求解機器人完成規(guī)定工作的動作序列 BACCBA機械手機械手(a)(b)7.3 STRIPS規(guī)劃系統(tǒng) 7.3.1 積木世界的機器人規(guī)劃 1. 積木世界的機器人問題 機器人能夠執(zhí)行的動作舉例如下： unstack(a,b)：把堆放在積木b上的積木a拾起。在進行這個動作之前，要求機器人的手為空手，且積木a的頂上是空的。 stack(a,b)： 把積木a堆放在積木b上。動作之前要求機械手必須已抓住積木a，而且積木b頂上必須是空的。 pickup(a)： 從桌面上拾起積木a

6、，并抓住它不放。在動作之前要求機械手為空手，而且積木a頂上沒有任何東西。 putdown(a)： 把積木a放置到桌面上。要求動作之前機械手已抓住積木a。7.3 STRIPS規(guī)劃系統(tǒng) 7.3.1 積木世界的機器人規(guī)劃 1. 積木世界的機器人問題狀態(tài)描述謂詞：ON(a,b)： 積木a在積木b之上。ONTABLE(a)： 積木a在桌面上。CLEAR(a)： 積木a頂上沒有任何東西。HOLDING(a)： 機械手正抓住積木a。HANDEMPTY： 機械手為空手。7.3 STRIPS規(guī)劃系統(tǒng) 7.3.1 積木世界的機器人規(guī)劃 2.用F規(guī)則求解規(guī)劃序列采用F規(guī)則表示機器人的動作，這是一個叫做STRIPS規(guī)

7、劃系統(tǒng)的規(guī)則，它由3部分組成：第一部分是先決條件。為了使F規(guī)則能夠應(yīng)用到狀態(tài)描述中去。第二部分是一個叫做刪除表的謂詞。當(dāng)一條規(guī)則被應(yīng)用于某個狀態(tài)描述或數(shù)據(jù)庫時，就從該數(shù)據(jù)庫刪去刪除表的內(nèi)容。第三部分叫做添加表。當(dāng)把某條規(guī)則應(yīng)用于某數(shù)據(jù)庫時，就把該添加表的內(nèi)容添進該數(shù)據(jù)庫。7.3 STRIPS規(guī)劃系統(tǒng) 7.3.1 積木世界的機器人規(guī)劃 2.用F規(guī)則求解規(guī)劃序列例： move(x, y, z): 把物體x從物體y上面移到物體z上面。 先決條件：CLEAR(x), CLEAR(z), ON(x,y) 刪除表：ON(x, y), CLEAR(z) 添加表：ON(x, z), CLEAR(y)7.3 S

8、TRIPS規(guī)劃系統(tǒng) 7.3.2 STRIPS規(guī)劃系統(tǒng) 斯坦福大學(xué)人工智能研究所于1966-72年研制的Shakey機器人是第一臺能夠進行行動推理的多用移動機器人，該項目融合了機器人視覺、機器人學(xué)和自動推理研究成果。機器人的任務(wù)是在一些相連的房間里，將用戶指定的箱子推到指定的位置。對于用戶輸入的每一個任務(wù)，Shakey自主地規(guī)劃完成該任務(wù)的行動并依次執(zhí)行。 Shakey項目技術(shù)：規(guī)劃語言STRIPS（ STanford Research Institute Problem SolverSTRIPS ）和A*算法等。 STRIPS語言用來描述外部世界模型并支持任務(wù)規(guī)劃，它提供了框架問題的一種簡潔、

9、高效的解法，但理論上并不完備。7.3 STRIPS規(guī)劃系統(tǒng) 7.3.2 STRIPS規(guī)劃系統(tǒng) STRIPS系統(tǒng)的組成如下：(1) 世界模型。為一階謂詞演算公式。(2) 操作符(F規(guī)則)。包括先決條件、刪除表和添加表。(3) 操作方法。應(yīng)用狀態(tài)空間表示和中間-結(jié)局分析。規(guī)劃過程每個STRIPS問題的解答為某個實現(xiàn)目標(biāo)的操作符序列，即達到目標(biāo)的規(guī)劃。 A Service Robot Copes with Changes Understanding, Learning, Planning, and Acting7.4 分層規(guī)劃 探索規(guī)劃時首先只考慮一層的細節(jié)，然后再注意規(guī)劃中比這一層低一層的細節(jié)，所

10、以把它叫做長度優(yōu)先搜索。NOAH規(guī)劃系統(tǒng)1. 應(yīng)用最小約束策略一個尋找非線性規(guī)劃而不必考慮操作符序列的所有排列的方法是把最少約束策略應(yīng)用來選擇操作符執(zhí)行次序的問題。問題求解系統(tǒng)NOAH采用一種網(wǎng)絡(luò)結(jié)構(gòu)來記錄它所選取的操作符之間所需要的排序。它也分層進行操作運算，即首先建立起規(guī)劃的抽象輪廓，然后在后續(xù)的各步中，填入越來越多的細節(jié)。7.4 分層規(guī)劃 2. 檢驗準(zhǔn)則準(zhǔn)則法已被應(yīng)用于各種規(guī)劃生成系統(tǒng)。對于早期的系統(tǒng)，如HACKER系統(tǒng)，準(zhǔn)則只用于舍棄不滿足的規(guī)劃。在NOAH系統(tǒng)中，準(zhǔn)則被用來提出推定的方法以便修正所產(chǎn)生的規(guī)劃。第一個涉及的準(zhǔn)則是歸結(jié)矛盾準(zhǔn)則。第二個準(zhǔn)則叫做消除多余先決條件準(zhǔn)則，包括除去

11、對子目標(biāo)的多余說明。可以把分層規(guī)劃和最少約束策略十分直接地結(jié)合起來，以求得非線性規(guī)劃而不產(chǎn)生一個龐大的搜索樹。 7.5 基于專家系統(tǒng)的機器人規(guī)劃1. 系統(tǒng)結(jié)構(gòu)及規(guī)劃機理（1）知識庫：用于存儲某些特定領(lǐng)域的專家知識和經(jīng)驗，包括機器人工作環(huán)境的世界模型、狀態(tài)、物體描述等事實和可行操作或規(guī)則等。（2） 控制策略：包含綜合機理，確定系統(tǒng)應(yīng)當(dāng)應(yīng)用什么規(guī)則以及采取什么方式去尋找該規(guī)則。（3） 推理機：用于記憶所采用的規(guī)則和控制策略及推理策略。（4）知識獲?。菏紫全@取某特定域的專家知識。然后用程序設(shè)計語言把這些知識變換為計算機程序。最后把它們存入知識庫待用。7.5 基于專家系統(tǒng)的機器人規(guī)劃(5)解釋與說明：

12、通過用戶接口，在專家系統(tǒng)與用戶之間進行對話，從而使用戶能夠輸入數(shù)據(jù)、提出問題、知道推理結(jié)果以及了解推理過程等。2. 任務(wù)級機器人規(guī)劃三要素（1）建立模型：世界模型。（2）任務(wù)說明：定義狀態(tài)及狀態(tài)變換次序。（3）程序綜合。3. ROPES機器人規(guī)劃系統(tǒng)7.6 軌跡規(guī)劃簡介 軌跡：機械手在運動過程中的位移、速度和加速度。 軌跡規(guī)劃：根據(jù)任務(wù)的要求，計算出預(yù)期的軌跡。 在機械手運動學(xué)和動力學(xué)基礎(chǔ)上，討論在關(guān)節(jié)空間和笛卡爾空間中機器人運動的軌跡規(guī)劃和軌跡生成方法 7.6 軌跡規(guī)劃簡介 例：NAO機器人檢球動作。 地球上的生物物種在漫長的過程中形成了豐富的行為特性，并且一直不斷地完善和發(fā)展，以更好地適應(yīng)

13、其所生存的環(huán)境。生物群體和自然生態(tài)系統(tǒng)可以通過自身的演化就能使許多在人類看起來高度復(fù)雜的優(yōu)化問題得到完美解決。因此，各種模仿生物群體的智能仿生算法被相繼提出，得到了深入研究和應(yīng)用實踐。 群智能思想的產(chǎn)生主要源于復(fù)雜適應(yīng)系統(tǒng)理論以及人工生命的研究。群智能算法群智能思想起源群智能算法群智能思想起源 復(fù)雜適應(yīng)系統(tǒng)( Complex Adaptive System, CAS) 理論：1994 年由 Holland 教授正式提出。CAS中成員稱為具有適應(yīng)性的主體, 簡稱主體。 主體的適應(yīng)性, 是指它能夠與環(huán)境以及其它主體進行交流，在交流的過程中 “學(xué)習(xí)” 或 “積累經(jīng)驗”，并且根據(jù)學(xué)到的經(jīng)驗改變自身的結(jié)

14、構(gòu)和行為方式。CAS具有四個基本特點: （1）首先, 主體是主動的、活的實體。具有適應(yīng)性的主體的概念把個體主動性提高到了系統(tǒng)進化基本動因的位置, 從而成為研究與考察宏觀行為的出發(fā)點。 （2）其次, 個體與環(huán)境(包括個體之間)之間的相互影響、相互作用是系統(tǒng)演變和進化的主要動力。相互作用是“可記憶”的, 它表現(xiàn)為進化過程中每個個體的結(jié)構(gòu)和行為方式的變化，以不同的方式 “存儲” 在個體內(nèi)部。群智能算法群智能思想起源 （3）再次, 這種方法不像許多其他的方法那樣, 把宏觀和微觀截然分開, 而是把它們有機地聯(lián)系起來。 （4）最后, 這種建模方法還引進了隨機因素的作用, 使它具有更強的描述和表達能力。隨機

15、因素的影響不僅影響狀態(tài), 而且影響組織結(jié)構(gòu)和行為方式。具有主動性的個體會接受教訓(xùn),總結(jié)經(jīng)驗, 并且以某種方式把 “經(jīng)歷” 記住, 使之 “固化” 在自己以后的行為方式中。 CAS理論提供了模擬生物、 生態(tài)、 經(jīng)濟、 社會等復(fù)雜系統(tǒng)的巨大潛力。群智能算法群智能思想起源 人工生命(Artificial Life, AL)是用來研究具有某些生命基本特征的人工系統(tǒng)。 近年來, 人工生命的研究發(fā)展非常快, 在某些方面的研究已與傳統(tǒng)的生物科學(xué)形成了互補。人工生命包括兩方面的內(nèi)容: 如何利用計算技術(shù)研究生物現(xiàn)象; 如何利用生物技術(shù)研究計算問題。 第二部分的內(nèi)容的研究中，現(xiàn)已經(jīng)有了很多源于生物現(xiàn)象的計算技巧，

16、例如，人工神經(jīng)網(wǎng)絡(luò)是簡化的大腦模型，遺傳算法是模擬基因進化的過程，目前這一類計算技術(shù)被統(tǒng)稱為自然計算。群智能屬于自然計算中的一類，它模擬另一種生物系統(tǒng)：社會系統(tǒng)，更確切地說，是模擬由簡單個體組成的群落與環(huán)境以及個體之間的互動行為，這些模擬系統(tǒng)利用局部信息從而可能產(chǎn)生不可預(yù)測的群體行為。群智能算法群智能思想起源 群智能( Swarm Intelligence, SI)： 1992年由 Beni, Hack-wood 和 Wang在分子自動機系統(tǒng)中提出。 1999 年, Bonabeau, Dorigo 和 Theraulaz 在 Swarm Intel-ligence: From Natural

17、 to Artificial Systems中對群智能進行了詳細的論述和分析。 2003年 IEEE 第一屆國際群智能研討會在美國印第安納州首府召開。 群智能定義：任何一種由昆蟲群體或其它動物社會行為機制而激發(fā)設(shè)計出的算法或分布式解決問題的策略均屬于群智能。 群智能算法群智能思想起源 Swarm 可被描述為一些相互作用相鄰個體的集合體, 蜂群、蟻群、鳥群、魚群都是Swarm的典型例子。社會性動物群體所擁有的這種特性能幫助個體很好地適應(yīng)環(huán)境，個體所能獲得的信息遠比它通過自身感覺器官所取得的多，其根本原因在于個體之間存在著信息交互能力。信息的交互過程不僅僅在群體內(nèi)傳播了信息，而且群內(nèi)個體還能處理信

18、息，并根據(jù)所獲得的信息 (包括環(huán)境信息和附近其它個體的信息)改變自身的一些行為模式和規(guī)范, 這樣就使得群體涌現(xiàn)出一些單個個體所不具備的能力和特性, 尤其是對環(huán)境的適應(yīng)能力。這種對環(huán)境變化所具有的適應(yīng)能力可以被認為是一種智能, 也就是說動物個體通過聚集成群而涌現(xiàn)出了智能。 群智能算法群智能思想起源 SI 的定義進一步推廣（Bonabeau）: 無智能或簡單智能的主體通過任何形式的聚集協(xié)同而表現(xiàn)出智能行為的特性。 群智能理論還非常不成熟, 但已成為有別于傳統(tǒng)人工智能中連接主義、 行為主義和符號主義的一種新的關(guān)于智能的描述方法, 并成為人工智能領(lǐng)域的新研究熱點。群智能算法群智能理論 James Ke

19、nnedy 和 Russell C.Eberhart 在 2001 年出版的Swarm Intelligence 是群智能發(fā)展的一個重要歷程碑。他們不反對Bonabeau 關(guān)于 SI 的定義，贊同其定義的基本精神，但反對定義中使用 “主體” 一詞。 其理由是 “主體” 所帶有的自治性和特殊性是許多 Swarm的個體所不具備和擁有的，這將大大限制 Swarm的定義范圍。 Mark Millonas( 1994) 構(gòu)建一個 SI 系統(tǒng)所應(yīng)滿足的五條基本原則: Proximity Principle: 群內(nèi)個體具有能執(zhí)行簡單的時間或空間上的評估和計算的能力。 群智能算法群智能理論 Quality P

20、rinciple: 群內(nèi)個體能對環(huán)境(包括群內(nèi)其它個體)的關(guān)鍵性因素的變化做出響應(yīng)。 Principle of Diverse Response: 群內(nèi)不同個體對環(huán)境中的某一變化所表現(xiàn)出的響應(yīng)行為具有多樣性。 Stability Principle: 不是每次環(huán)境的變化都會導(dǎo)致整個群體的行為模式的改變。 Adaptability Principle: 環(huán)境所發(fā)生的變化中, 若出現(xiàn)群體值得付出代價的改變機遇, 群體必須能夠改變其行為模式。群智能算法群智能理論 以上五條原則現(xiàn)在成為了群智能的最基本理論，現(xiàn)有的群智能方法和策略都符合這些原則。 Swarm Intelligence 最重要的觀點是：M

21、ind is social, 也就是認為人的智能是源于社會性的相互作用，文化和認知是人類社會性不可分割的重要部分，這一觀點成為了群智能發(fā)展的基石。 群智能模擬的是社會系統(tǒng)的變化，其最基本單位是 “敏因”(Meme) ，這一詞由 Dawkin 在 The Selfish Gene中提出，它是指思想文化傳播中的基本單位，個體在社會中會根據(jù)環(huán)境來改變自身的思想，敏因的傳播途徑是在個體與個體之間，在人類社會中它還可以在人腦與書本之間、 人腦與計算機、 計算機與計算機之間傳播。當(dāng)然，“敏因” 應(yīng)該如何嚴格描述和定義還沒有定論。群智能算法群智能理論 群智能研究的更進一步目標(biāo)是對人類思想變化的社會行為的模擬

22、。人類心理中存在著群體性、習(xí)慣性、一致性, 常常是習(xí)慣性地遵循一些習(xí)俗和規(guī)則。無論什么時候, 人們思想和行為總是因相互影響而變得非常近似, 道德規(guī)范以及文化的形成就是這種通過相互間影響而導(dǎo)致近似的結(jié)果。 人類的社會思想行為并不簡單類似鳥群或魚群的行為, 人類思想的形成過程是一種在高維認知空間的探索歷程。 兩種思想意見在認知空間上聚集到一點上, 被稱為 “一致” 或 “認同” , 而不是鳥群或魚群系統(tǒng)中的 “碰撞” 。如果某人認同認知空間某個點, 那么就努力靠近它, 反之則盡量遠離它, 這里認知空間中的某個點就是某個人的思想。人類通過這種社會行為達成社會的共識: 習(xí)俗、道德規(guī)范等。 目前, 群智

23、能理論研究處于基本思想描述階段, 還未能提出一些較為明確的概念和定義, 盡管已經(jīng)有人提出廣義群智能的模型。 蟻群算法(Ant Colony OptimizationACO)由 Colorni, Dorigo 和 Maniezzo 于 1991 年提出,它是通過模擬自然界螞蟻社會的尋找食物的方式而得出的一種仿生優(yōu)化算法。 自然界種蟻群尋找食物時會派出一些螞蟻分頭在四周游蕩, 如果一只螞蟻找到食物, 它就返回巢中通知同伴并沿途留下 “信息素” ( pheromone)作為蟻群前往食物所在地的標(biāo)記。 信息素會逐漸揮發(fā), 如果兩只螞蟻同時找到同一食物,又采取不同路線回到巢中, 那么比較繞彎的一條路上信

24、息素的氣味會比較淡, 蟻群將傾向于沿另一條更近的路線前往食物所在地。ACO算法設(shè)計虛擬的 “螞蟻” , 讓它們摸索不同路線, 并留下會隨時間逐漸消失的虛擬 “信息素” 。根據(jù) “信息素較濃的路線更近” 的原則, 即可選擇出最佳路線。 群智能算法蟻群算法 ACO算法首先應(yīng)用于 TSP 問題中, 這里以 TSP 問題為例對算法作簡單介紹。當(dāng)某一個螞蟻走到一個城市, 下一步可選的路徑集合為 E, 集合中任一條路徑 eE 上的信息素濃度為e, 走這條路的代價為 e, 那么選擇某一條路徑 vE 的幾率為：群智能算法蟻群算法 其中, 和 兩個參數(shù)分別用來控制信息素和路徑長度的相對重要程度。當(dāng)螞蟻在所有城市

25、走過一遍之后，路徑上的信息素濃度將變?yōu)? e( t+1) =( 1- )e( t) +e 其中，0 1 用于控制信息素隨時間揮發(fā)的速度，e是上次螞蟻經(jīng)過此路段所留下的信息素，未經(jīng)過則為 0。上式以及e可以根據(jù)問題進行設(shè)計。 目前，ACO算法已被廣泛應(yīng)用于組合優(yōu)化問題中，在車輛調(diào)度問題、 機器人路徑規(guī)劃問題、 路由算法設(shè)計等領(lǐng)域均取得了良好的效果。 由于 ACO算法具有廣泛實用價值，成為了群智能領(lǐng)域第一個取得成功的實例，曾一度成為群智能的代名詞，相應(yīng)理論研究及改進算法近年來不斷取得新的成果。群智能算法蟻群算法 粒子群優(yōu)化算法（Particle Swarm OptimizationPSO)源于 1

26、987 年 Reynolds 對鳥群社會系統(tǒng)boids的仿真研究，boids 也是一個 CAS。 在 boids 中, 一群鳥在空中飛行, 每個鳥遵守以下三條規(guī)則: （1）避免與相鄰的鳥發(fā)生碰撞沖突; （2）盡量與自己周圍的鳥在速度上保持協(xié)調(diào)和一致; （3）盡量試圖向自己所認為的群體中心靠近。 僅僅通過使用這三條規(guī)則, boids 系統(tǒng)就出現(xiàn)非常逼真的群體聚集行為, 鳥成群地在空中飛行, 當(dāng)遇到障礙時它們會分開繞行而過, 隨后又會重新形成群體。不過 Reynolds 僅僅將其作為 CAS的一個實例作仿真研究, 而并未將它用于優(yōu)化計算中, 也無任何實用價值。 群智能算法粒子群優(yōu)化算法 Kenne

27、dy和 Eberhart （1995年）在 boids 中加入了一個特定點, 定義為食物, 鳥根據(jù)周圍鳥的覓食行為來尋找食物。他們的初衷是希望通過這種模型來模擬鳥群尋找食源的現(xiàn)象, 然而實驗結(jié)果卻揭示這個仿真模型中蘊涵著很強的優(yōu)化能力, 尤其是在多維空間尋優(yōu)中。 由于最初的仿真系統(tǒng)中每個鳥在計算機屏幕上表示為一個點, 而 “點( Points)” 這個詞在數(shù)學(xué)領(lǐng)域具有非常多的意義, 因此作者用了 “粒子( Particle)” 來表示每一個個體。于是也就得到了基本 PSO算法。群智能算法粒子群優(yōu)化算法群智能算法粒子群優(yōu)化算法粒子群特性群智能算法粒子群優(yōu)化算法 在PSO系統(tǒng)初始化為一群隨機粒子(

28、 隨機解)，然后通過迭代找到最優(yōu)解。在每一次迭代中, 粒子通過跟蹤兩個 “極值”來更新自己, 同時也通過跟蹤它們實現(xiàn)粒子間的信息交換。第一個就是粒子本身所找到的最優(yōu)解, 這個解叫作個體極值pBest( “自身經(jīng)驗” )。另一個極值是整個群體目前找到的最優(yōu)解, 這個極值是群體極值 gBest(群體的 “社會經(jīng)驗” )。群智能算法粒子群優(yōu)化算法 1998 年,Shi 和 Eberhart 正式給出標(biāo)準(zhǔn) PSO算法的數(shù)學(xué)描述如下: 設(shè)搜索空間為 M維, 粒子數(shù)為 N。第 i 個粒子位置表示為向量 Xi=( xi1, xi2, , xiD) ; 第 i 個粒子“飛行” 歷史中的過去最優(yōu)位置(即該位置對

29、應(yīng)解最優(yōu))為 Pi=( pi1, pi2, , piD)也就是 pBest，其中所有 Pi( i=1, , N)中的最優(yōu)個體被記作 Pg 也就是 gBest；第 i 個粒子的位置變化率(速度)為向量 Vi=( vi1, vi2, , viD)。每個粒子的位置按如下公式進行變化( “飛行” ) :群智能算法粒子群優(yōu)化算法 其中, c1, c2 為正常數(shù), 稱為加速因子; rand( )為0, 1之間的隨機數(shù); w稱慣性因子。第d( 1dM)維的位置變化范圍和速度變化范圍分別為- xd,max, xd,max和- vd,max, vd,max( 變化范圍可通過平移處理使之對稱) , 迭代中若某一維

30、的 xid 或 vid 超過邊界則取邊界值。粒子群初始位置和速度隨機產(chǎn)生, 然后按公式進行迭代, 直至滿足停止條件。群智能算法粒子群優(yōu)化算法 2003 年李曉磊、 邵之江等提出的人工魚群算法（Artificial Fish-Swarm AlgorithmAFSA)，它利用自上而下的尋優(yōu)模式模仿自然界魚群覓食行為, 主要利用魚的覓食、聚群和追尾行為, 構(gòu)造個體底層行為; 通過魚群中各個體的局部尋優(yōu), 達到全局最優(yōu)值在群體中凸現(xiàn)出來的目的。在基本運算中引入魚群的生存機制、競爭機制以及魚群的協(xié)調(diào)機制,提高算法的有效效率。李曉磊等又采用分解協(xié)調(diào)的思想構(gòu)造一種改進的人工魚群算法, 并以換熱器系統(tǒng)為例, 驗證了該算法，結(jié)果表明該算法具有較好的收斂性。 AFSA只使用目標(biāo)函數(shù)的函數(shù)值，無需目標(biāo)函