#第八章群智能通過本書前面各章所介紹的人工智能實現途徑所實現的均是單個個體的智能。雖然在進化主義中，牽涉到群體的進化，但最終在解決問題時依靠的還是單個個體的能力。群智能則不同，它通過多個智能實體之間的協作來解決問題，利用的是群體的智慧，而不是單個個體的能力。目前，在群智能上主要包括兩大類工作。一類是多智能體系統，利用多個智能體之間的協調和協作，完成單智能體不能完成或難以有效完成的任務。另一類是群智能優化算法。與進化計算所要解決的問題類似，群智能優化算法也是用于搜索問題的全局最優解，并且其中同樣體現了仿生的思想，它模擬了生物群體通過相互協作解決復雜問題的行為方式。目前群智能優化算法主要包括蟻群優化算法和粒子群優化算法。其中，蟻群優化算法模擬了螞蟻群體覓食的行為方式，粒子群優化算法則模擬了鳥群的群體性行為。本章首先介紹多智能體系統中核心的協調與協作機制以及相應的強化學習方法，然后闡述蟻群優化算法和粒子群優化算法的基本原理。8.1多智能體系統多智能體系統是在單智能體基礎上發展起來的，它通過多個智能體相互之間的協調和協作，來解決單個智能體不能解決或者難以有效解決的復雜問題。其中，智能體之間的協調和協作是多智能體系統中的核心問題，有效的協調與協作方法是多智能體系統中的主要設計內容。8.1.1智能體之間的通信機制為了進行協調和協作，智能體之間需要彼此通信、交換信息。目前，智能體之間的主要通信機制包括黑板系統和消息系統。1.黑板系統黑板是黑板系統中的公共信息存儲和交流區。在黑板系統中，各智能體之間不發生直接通信，而是通過黑板交換數據、信息和知識。智能體在需要時按照自身權限訪問黑板，確定是否有新的信息，或者向黑板上添加自己的信息。黑板系統的主要問題是當系統中存在很多智能體時，黑板上的數據量會按指數率增長，難以進行高效的信息存儲和檢索。解決這一問題的一種思路是為每個智能體在黑板上分配一個單獨的區域。2.消息系統消息通信機制是實現靈活復雜的協調策略的基礎。相對于黑板系統，消息系統的通信方式更為靈活。在消息系統中，任意兩個智能體之間可直接通過消息交換數據、信息和知識。一個智能體可以向另外一個智能體發送消息，也可以將消息廣播給多個智能體。發送消息的智能體被稱為發送者，接受消息的智能體被稱為接受者。發送者在發送消息時指定消息的接受者，除了接受者以外的其它智能體不能讀取消息。為了支持消息系統，消息的發送和接收需遵守預先定義的通信語言。目前，智能體通信語言的主要理論基礎是英國哲學家和語言學家奧斯汀提出的言語行為理論。言語行為理論認為：通信語言是一種動作，和物理上的動作一樣，發言者的目的是改變世界的狀態，通常是指聽眾的某種心智狀態。在智能體通信語言的研究中，言語行為理論主要被用來研究主體之間可以交互的信息類型。一種通用的分類方式是將言語行為分為表示型和知識型，還可進一步細分為斷言型、指示型、承諾型、允許型、禁止型、聲明型等類型。在言語行為理論基礎上，目前國際上有一定影響的智能體通信語言包括美國國防部高級研究計劃署(Advancedresearchprojectagency,ARPA)提出的知識查詢與操縱語言(KnowledgeQueryandManipulationLanguage,KQML)、知識交換格式(KnowledgeInterchangeFormat,KIF)和歐洲智能體協會(foundationforintelligentphysicalagents,FIPA)提出的智能體通信語言(AgentCommunicationLanguage,ACL)語言。這里主要介紹KQML語言的基本內容。KQML分為通信、消息和內容三個層次。其中通信層是通信參數協議；消息層規定與消息有關的言語行為的類型,相應的消息被稱為動作表達式。這些動作表達式主要是從言語行為理論演化而來的；內容層則規定了消息的內容。在KQML中，除了可以通過發送-接受方式進行智能體之間的通信外,還提供了基于通信服務器的消息交換方式。通信服務器類似于黑板系統中的黑板，但是其功能比黑板豐富，它將搜索信息的智能體與提供信息的智能體連接起來。智能體之間的協調策略智能體之間的協調是指在開放、動態的多智能系統環境下，如何協調不同智能體之間的行為，解決其在目標規劃、資源利用等方面可能存在的沖突，以保證多智能系統的正常運行；或者使各智能體以一致、和諧的方式共同工作。協調的一個主要方面是避免智能體的死鎖和活鎖問題。死鎖是指各智能體互相等待，無法進入下一步工作；活鎖是指智能體雖在不斷工作，卻無任何進展。目前，多智能體系統的協調策略主要分為四種：組織型：提供一個專門用于協調的、全面了解系統狀況的智能體，由它按照某種特定的結構組織智能體之間的協調。合同型：通過訂立合同的方式進行協調。在此過程中，每個智能體兼有管理者和投標者的雙重職能。當智能體無法用本地資源解決問題時，將問題分解為若干子問題，并尋找合適的智能體來解決這些子問題。子任務分配通過投標和簽訂合同方式實現。規劃型：通過規劃智能體的行為實現協調，消除彼此間的沖突。具體分為集中式規劃和分布式規劃兩種方式。在集中式規劃方式中，各智能體將自己的規劃發送給一個集中的協調者，由該協調者分析不同智能體的行為，判斷并解決其中的潛在沖突；在分布式規劃方式中，各智能體管理自己的規劃，通過通信了解其他智能體的規劃，并根據需要修改各自的規劃，直到消除彼此間的沖突為止。法規型：為智能體制定一套行為法規，要求每個智能體必須遵守。這些法規一方面會限制每個智能體所能采取的行動，另一方面也可以使智能體在確定行動規劃時，可以確定其他智能體的行為方式，從而確保智能體之間沒有沖突。法規型適合于空中運輸控制或城市交通控制等具有明確法規形式的多智能體系統。智能體之間的協作策略智能體之間的協作是指如何在不同智能體之間建立合作關系，以完成某一共同任務。智能體之間的協調是其協作的基礎，而協作則是協調的主要目的。有時，協調與協作是難以明確區分的，如上述合同式協調方式也可認為是一種協作過程。根據智能體之間的協作方式，可將多智能體系統劃分為兩種類型：合作型：各智能體為實現系統的共同利益而相互協作，設計目標是系統的整體性能

而不是針對其中單個智能體。競爭型：各智能體都是為著擴大自身利益而工作。為實現自身利益，各智能體可以與其它智能體達成一致，但也可能沒有協作關系，甚至可能存在競爭和互斥關系。目前，智能體之間的協作主要通過兩條途徑來解決。一條途徑是將博弈論、經典力學理論中有關多實體行為的方法和技術用于智能體之間的協作；另一條途徑是基于智能體的目標、意圖、規劃等心智狀態來研究智能體之間的協作。后一類方法應用更為廣泛。一些典型的協作方法包括部分全局規劃、基于約束傳播的規劃、基于生態學的協作與規劃、基于博弈論的協作與規劃、基于意圖的協商和基于范例推理的合同網協商等8.1.4多智能體強化學習對于多智能體的強化學習，存在多種不同的分類方法。一種分類方法是根據學習的組織方式，將多智能體學習劃分為三類：乘積形式(multiplication)、分割形式(division)和交互形式(interaction)［92］。其中，乘積形式是將多智能體系統作為一個單獨的學習型智能體;在分割形式中，每個智能體擁有獨立的強化學習機制，并且不與其它智能體進行交互；在交互形式中，每個智能體有獨立的強化學習機制，但通過與其它智能體的適當交互加快學習過程。另一種分類方法是根據智能體之間的協作方式，將多智能體強化學習方法劃分為合作型學習、競爭型學習和半競爭型學習三類［77］。下面按后一種分類方法介紹多智能體的強化學習。合作型多智能體強化學習在合作型多智能體強化學習中，各智能體的目標與整體系統的目標是一致的。因此。可以將多智能體系統作為一個單智能體，多智能體系統的行為是其中所有單智能體的聯合行為，在此基礎上采用單智能體的強化學習方法進行合作型學習。競爭型多智能體強化學習在競爭型多智能體系統中，每個智能體目標與其它智能體目標是完全相反的。由于某一智能體所獲得的獎勵值取決于其它智能體的動作，因此傳統的單智能體強化學習方法不再適用。根據博弈論，這種競爭型關系對應于零和決策，因此最簡單的解決方法是極大極小策略。以兩個競爭型智能體為例，對于其中一個智能體，其最優策略應是在另一智能體采取對于當前智能體而言最壞動作的情況下，選擇獎勵值最大的動作。當采用Q-學習方法時，極大極小策略可形式化地表示為：V(sV(s)=maxmin(8-1)aeAbeB半競爭型多智能體強化學習在很多實際多智能體系統中，單個智能體所得獎勵值并不是其它智能體所得獎勵值的負數，即不是非零和決策問題，從而不能應用極大極小策略獲得最優解。本質上非零和決策問題更能反映多智能體系統中個體理性與群體理性發生沖突的本質。有學者利用元博弈理論在考慮智能體自身愿望的基礎上，通過預測對手的策略來修正自己的策略。8.2蟻群優化算法蟻群優化算法是由意大利學者M.多利格在二十世紀九十年代提出的一種模擬螞蟻群

體覓食行為的優化算法。該算法思路新穎，具有魯棒、并行性等優點，已得到人們的廣泛關注和應用，并在應用中表現出優異的性能和廣闊的應用前景，成為人工智能和最優化領域中的研究熱點和前沿性課題之一。821蟻群覓食行為對計算的啟示螞蟻是群居性昆蟲。研究群居型昆蟲的科學家們發現：昆蟲在群落一級的合作基本上是自組織的，似乎沒有集中的指揮。而且在許多場合下昆蟲的合作形式是很簡單的，但它們卻可以通過簡單的合作解決許多復雜的問題。以螞蟻為例，它們在其合作尋找食物的過程中，總能找到從蟻巢到食物源的最短路徑，表現出驚人的群體性智能。這正是蟻群優化算法的思想源泉。那么，為什么螞蟻能夠通過群體的合作找到從蟻巢到食物源的最短路徑呢？原因在于：螞蟻在運動時，會分泌并在經過的路徑上留下一種被稱為信息素的化學物質。所有螞蟻都能感知信息素的存在及其濃度，并在其指導下傾向于朝著信息素濃度高的方向移動。下面以圖8-1所示例子，詳細說明螞蟻的覓食過程。圖8-1(a)中，蟻巢與食物源之間沒有障礙，螞蟻選擇直線行走。一旦在其行走路線上出現障礙物時，如在圖8-l(b)所示情況下，螞蟻將如何處理呢？顯然，螞蟻有兩條路徑可供選擇。路徑1為“巢穴-障礙物上方-食物”路徑2為“巢穴-障礙物下方-食物”起初，螞蟻等概率地選擇從障礙物的上方或下方繞過障礙物，如圖8-1(c)所示。由于路徑1的長度小于路徑2的長度，因此單位時間內繞過障礙物上方行走的螞蟻數量將多于繞過障礙物下方行走的螞蟻數量。這意味著螞蟻們在路徑1上遺留的信息素的濃度逐漸會高于在路徑2遺留的信息素的濃度。這樣，根據螞蟻傾向于朝著信息素濃度高的方向移動的特性，通過路徑1的螞蟻數量將越來越多，而通過路徑2的螞蟻數量將越來越少，這又反過來增大了兩條路徑上信息素濃度的差異，使得不僅螞蟻選擇路徑1的概率不斷增加，而且相應概率的增長率也不斷增加，表現出信息的正反饋現象。最終使得每個螞蟻個體都能找到蟻巢與食物源之間的最短路徑，即路徑1,如圖8-1(d)所示。iiimiiiniiio(a)(b)iiimiiiniiio(a)(b)(c)(d)圖8-1螞蟻覓食過程示例

綜上所述，在整個路徑尋優過程中，單只螞蟻的尋優能力有限，但蟻群具有高度的自組

織性，通過信息素交換路徑信息，形成集體自催化行為，找到最優路徑。根據螞蟻覓食原理

和過程，可構造人工螞蟻，使其按照類似于真實螞蟻的覓食過程尋找問題的最優解。人工螞

蟻應具有真實螞蟻的如下特性：1.人工螞蟻之間應能夠相互通信和影響。真實螞蟻通過信息素互相影響，人工螞蟻也應能夠在所經過的解的路徑上留下數字信息素，該信息素記錄了人工螞蟻當前解和歷史解的性能狀態，而且可以被后繼人工螞蟻讀取。數字信息素的濃度也是人工螞蟻選擇路徑的啟發式信息。此外，真實螞蟻的信息素具有揮發特性，即隨著時間推移信息素逐漸揮發，減小歷史遺留信息對蟻群的影響。同樣，人工螞蟻的數字信息素也應具有揮發性。使人工螞蟻逐漸忘卻歷史遺留信息，在選擇路徑時不局限于以前人工螞蟻的殘留經驗。2.在當前信息的引導下應采用隨機選擇策略。真實螞蟻的路徑選擇行為是隨機性的，信息素的作用是提高了螞蟻對路徑的偏愛，但選擇仍然是隨機的。人工螞蟻對解的路徑的選擇也應具有這種特性，這樣才有可能跳出局部最優解。8.2.2蟻群優化算法的基本原理根據上述螞蟻覓食過程的啟示，蟻群優化算法是采用人工螞蟻的行走路線來選擇問題最優解的一種算法。每只人工螞蟻獨立地在問題解空間中搜索(行走)，當碰到解的分支路徑時，隨機地選擇某條路徑行走，其中信息素濃度更高的路徑具有更大的選擇概率。人工螞蟻在行走的路徑上釋放出與路徑長度有關的信息素。路徑越短，信息素濃度越高。隨著時間的推移，路徑長度短的路徑上的信息素濃度越來越高，引導更多的人工螞蟻通過最優的求解路徑，釋放出更多的信息素，而其他路徑上的信息素在揮發特性的作用下卻逐漸消失，從而形成正反饋效應。最終整個蟻群在正反饋的作用下集中到代表最優解的路徑上，表明找到了最優解。最初提出的蟻群優化算法被稱為螞蟻系統。下面以螞蟻系統解決旅行商問題的過程為例，詳細說明蟻群優化算法的數學模型和實現過程。對下面所描述的解決TSP問題的蟻群優化算法稍加修改，即可應用于其它組合優化問題。關于TSP問題的說明，請見第4.5.3節中的相應內容。1.解決TSP問題的螞蟻系統首先給出解決TSP問題的螞蟻系統中的如下符號及其意義：c--第i座城市id--城市c與c之間路徑距離ijijm--蟻群中螞蟻的數量TC)--第t時刻在路徑c-c上殘留的信息素量，初始時刻各條路徑上TC)相同ijijijTkC)--第t時刻第k只螞蟻在路徑c-c上釋放的信息素量ijij耳C)--第t時刻在路徑c-c上問題所提供的啟發式信息，通常取為1d，表示優先選擇局部距離短的路徑NkC)--第t時刻在c處允許第k只螞蟻訪問的下一個城市的集合iipkC)--第t時刻第k只螞蟻在路徑c-c上的移動概率，ijij可以認為工C）是由蟻群所提供的啟發式信息，耳C）則是由問題本身所提供的啟發式信ijij息。研究表明：如果僅考慮信息素，而不考慮任何有效的由問題本身所提供的啟發式信息算法的效果將變得非常糟糕。在下面的敘述中，啟發式信息專指由問題本身所提供的啟發式信息，即耳C）,ij螞蟻系統中，每個人工螞蟻根據各條允許路徑上的信息素量和啟發式信息隨機確定其移動方向。一種合理的方式是優先選擇信息素量大且局部距離短的路徑，相應地有pi(t'lJIwNk(t)iJeNk(t)lJ電Nkl(8-2)其中?和0為參數，分別反映了信息素和啟發式信息的影響程度。在螞蟻走完一步或完成對所有城市的遍歷后，要對路徑信息素進行更新，其更新基本公式為AtlJ0=^Atk(t),lJk=1t(t+1)=G-p)-TC)+At(t).lJlJlJ(8-3)(8-4)公式（8-4）中P是信息素揮發系數，要求0<P<1。在公式（8-3）、（8-4）所表示的基本信息素更新公式基礎上，有三種不同的信息素更新策略，分別對應于螞蟻系統的三種版本：蟻密模型，蟻量模型，蟻周模型。其中，在蟻密模型和蟻量模型中，螞蟻每走一步就更新路徑上的信息素；而在蟻周模型中，螞蟻完成一次城市的遍歷后才更新所有路徑上的信息素。蟻周模型的效果優于蟻密模型和蟻量模型。現在所說的螞蟻系統一般是指對應于蟻周模型的螞蟻系統。設Q為常量，Lk為第k只螞蟻遍歷城市的路徑長度和，則蟻周模型對應的Aak（t）如下:lJAt?C）_JQ/",第k只螞蟻在本次遍歷中經過路徑cl-CjlJ〔0，其他(8-5)根據路徑選擇方法和信息素更新公式，螞蟻系統解決旅行商問題的算法流程如表8-1所示。表8-1解決TSP問題的螞蟻系統算法Stepl參數初始化Step2將m只螞蟻隨機放在n個城市上Step3針對每只螞蟻執行以下步驟：Step3.1根據公式(8-2)計算螞蟻選擇城市的概率Step3.2使螞蟻移動到具有最大轉移概率的城市Step3.3重復Step3.1-Step3.2,直到螞蟻遍歷所有城市Step4按照公式(8-4)更新所有路徑上的信息素。Step5如果滿足終止條件，算法停止，輸出當前最優結果；否則返回Step3。表8-1所示算法流程中的核心步驟是Step3和Step4，分別完成解路徑的構建和信息素的更新。包括螞蟻系統在內的所有蟻群優化算法都可認為是由解路徑構建和信息素更新兩個關鍵過程構成的。8.2.3蟻群優化算法的改進對螞蟻系統的改進包括兩個方面。一個方面的改進是提高其性能，改善其尋優的效果與效率；另一個方面的改進是擴大其應用領域，使其不僅可以應用于離散的組合優化問題，也可應用于連續優化問題，如函數優化問題等。本節僅討論第一個方面的改進，關于第二個方面的改進，請讀者參考有關文獻。在性能的改善上存在兩種策略。一種策略是在螞蟻系統上進行擴展，使用與螞蟻系統相同的解路徑構建過程和信息素更新過程，但在信息素更新細節方面有所區別。這一類擴展算法包括精化螞蟻系統,基于排列的螞蟻系統和最大最小螞蟻系統。另一種策略是對螞蟻系統進行較大幅度的修改。這一類改進算法包括蟻群系統，近似非確定樹搜索算法和超立方體框架。精化螞蟻系統EAS的主要改進思想是對算法迄今為止找到的最優路徑給與額外的正反饋，或者說使找到當前最優路徑的螞蟻向相應路徑釋放額外的信息素。設b表示找到當前最優路徑的螞蟻，e為加權系數，則信息素更新公式為：(8-6)tC+1)=(1-p)-T(t)+AtC)+eAibC).(8-6)ijijijij基于排列的螞蟻系統在ASran算法中，螞蟻釋放的信息素大小隨著螞蟻在排列中的先后次序逐漸減小。此外，與EAS算法類似，找到當前最優路徑的螞蟻會在相應路徑上釋放更多的信息素。在更新信息素之前，螞蟻按照其對應路徑長度的遞增關系排序。只有排列在最前面的(w-1)只螞蟻和找到當前最優路徑的螞蟻才能釋放信息素(當前最優路徑可能不是在本次循環中發現的)。螞蟻釋放的信息素將按照其排列順序賦予權值。具體權值更新公式如下：tij(8-7)(+1)=G-p)?TC)+燈(w-r)AtrC)+wAtbC).tij(8-7)ijijijr=1最大最小螞蟻系統在最大最小螞蟻系統中，同樣只允許找到最優路徑的螞蟻釋放信息量，但此處最優路徑可以是在本輪循環中發現的最優路徑，也可以是在當前已發生的所有循環中找到的最優路徑。設b表示對應上述兩種最優路徑中任一種的螞蟻，則信息素更新公式為：Tij(8-8)(t+1)=(L-p)-T(t)+Atb(t).Tij(8-8)ijij在MMAS中，對應兩種不同最優路徑的螞蟻輪流使用，其輪換頻率可隨迭代次數而改變。為了避免算法過早陷入局部最優，MMAS將每條路徑上的信息素量限制在一個區間內，并在初始時將路徑上的信息素量設定為區間的上界，使算法能在搜索初步階段探索盡可能多的路徑。MMAS被認為是目前解決TSP等離散組合優化問題的最好蟻群算法之一。4.蟻群系統ACS算法對螞蟻系統的改進集中在以下兩點：（1）采用偽隨機比例規則（Pseudo-RandomProportionalRule）確定螞蟻的移動方向。在這種規則下，存在一個參數qe[0,1]。第k只螞蟻在確定移動方向時，首先產生一個[0,1]0范圍內的隨機數q，如果qJq0，則按下式確定移動方向:(8-9)=argmaxTh,(8-9)ililleNki否則仍按公式（8-2）確定移動方向。公式（8-9）表示的是按確定方式選擇當前最優移動方向，公式（8-2）則表示的是按隨機方式選擇移動方向，但對當前最優移動方向有所偏愛。因此偽隨機比例規則是綜合了確定性選擇和隨機性選擇的策略。同時在這種規則下，還可以通過調整q，達到均衡集中搜索當前最優路徑與探索其他區域的目的。（2）在信息素更新方式上采用全局更新與局部更新相結合的方式。螞蟻每移動一步，就根據局部信息對路徑上的信息素進行更新。當所有螞蟻的路徑構建完畢后，再進行一次全局更新。在全局更新時僅考慮當前所找到的最優路徑。局部更新規則：T（+1）=（1一就C）+￡t,（8-10）ijij0其中三為常數，滿足0〈＜1，T0是信息素量的初始值。全局更新規則：(8-11)T(+1)=(1-p]C)+pATbC).(8-11)ijijij8.3粒子群優化算法1995年，詹姆斯?肯尼迪和魯塞爾?埃伯哈特提出了粒子群優化算法。粒子群優化算法的優點包括：（1）算法簡單，易于實現；（2）實數編碼方式適合于處理實值優化問題；（3）與進化計算方法一樣，只要函數值即可進行優化，無需函數的梯度信息，適應面較廣（；4）優

化性能良好；。近年來，粒子群優化算法已成為國際上人工智能與優化計算領域的熱點問題之一。鳥群飛行方式對計算的啟示動物學家雷諾茲和海珀樂分別在1987年和1990年發表論文，討論在鳥群群體運動中蘊含的美學。他們發現：由數目龐大的個體組成的鳥群可以在飛行中進行方向改變，隊形散開或隊形重組等行動。在鳥群的群體性行為中，有某種潛在的能力或規則保證了鳥群中各個個體采取同步的行為。海珀樂提出了一個模仿鳥群飛行行為的模型。肯尼迪和埃伯哈特對海珀樂的模型進行了修正，使得粒子在解空間中飛行，并在最好解處降落，從而得到了粒子群優化算法。粒子群優化算法的基本原理在粒子群優化算法中，由m個粒子組成的群體在d維解空間中以一定速度飛行。粒子飛過的每個位置都對應于問題的一個解，粒子飛行的過程就是搜索的過程。粒子的飛行速度受限于最大速度v。粒子的位置和速度一般在連續實數空間中取值。每個粒子在飛行時,max根據自己飛過的歷史最優點和群體鄰域內其他粒子飛過的歷史最好點，對自己的位置和速度進行調整。算法停止后，選擇群體內所有粒子飛過的歷史最好點作為最優解。粒子位置和速度的調整是粒子群優化算法的關鍵。設x=（x,X，…,X），TOC\o"1-5"\h\zii1i2idv,v，…,v）,p=（p,p，…,p）分別表示第i個粒子的位置、速度和當前飛過ii1i2idii1i2id的歷史最優點，p=C,p，…,p）表示群體鄰域內所有粒子飛過的歷史最優點，t表gg1g2gd示迭代次數，則常用的速度和位置更新公式如下：(8-12)(8-13)vt+1=wvt+ct^pt-xtLcv^pt一xt)k=1,2，…,d,

ikik1ikik2gkik(8-12)(8-13)xt+1=xt+vt+1,k=1,2,???,d,ikikik其中，E和耳是［0,1］區間內服從均勻分布的偽隨機數，c和c被稱為學習因子或加速系數，12?被稱為慣性權重。公式（8-12）、（8-13）表明，粒子在修正自身速度和位置時，考慮了三個方面的因素：公式（8-12）右側第一項，表示前次迭代時自身的飛行速度，即飛行中的慣性，這是粒子能夠進行飛行的基本條件；公式（8-12）右側第二項，代表自我認知的部分，粒子在飛行中考慮到自身的經驗，盡量向曾經飛過的歷史最優點靠近；公式（8-12）右側第三項，代表社會經驗的部分，粒子在飛行中還考慮到社會的經驗，向粒子中其他粒子學習，盡量向所有粒子曾經飛過的歷史最優點靠近基于速度和位置更新公式，粒子群優化算法的一般流程如表8-2所示。表8-2粒子群優化算法流程Stepl采用隨機方法初始化粒子群中各粒子的位置和速度。Step2計算每個粒子的適應值（目標函數值）。Step3確定每個粒子的歷史最優點和所有粒子的歷史最優點。Step4按公式（8-12）更新各粒子的位置和速度。Step5如達到停止條件，算法結束，否則轉Step2。這里，停止條件一般為預設的最大迭代次數或找到可以接受的滿意解。粒子群優化算法中的有關參數上述粒子群優化算法中存在一些參數，其意義和設定方法分別闡述如下。最大速度vmaxv決定了粒子在一次飛行中最大的飛行距離。該值較大，則算法的廣域搜索能力強，max但粒子容易飛過最優解；該值較小，則算法的局部搜索能力強，但容易陷入局部最優。分析和實驗表明，V的作用可以通過慣性權重來實現。因此，現在V—般僅用于限定分量maxmax的變化范圍，無需細致的選擇和調整。群體鄰域拓撲結構群體鄰域有不同定義策略，相應定義策略被稱為鄰域拓撲結構。可將鄰域拓撲結構分為兩大類。第一類方法是將群體中所有粒子定義為鄰域，相應算法為全局粒子群優化算法；第二類是取群體中部分粒子為鄰域，相應算法為局部粒子群優化算法。全局粒子群優化算法收斂速度快，但存在陷入局部最優的可能；而局部粒子群優化算法收斂速度慢，但不易陷入局部最優。在局部粒子群優化算法中，可以按位置相鄰或按索引號相鄰兩種原則確定鄰域。（1）基于位置的鄰域拓撲結構在每次迭代時，計算一個粒子與其他粒子之間的距離，根據距離遠近確定該粒子的鄰域。一種具體的實現方法被稱為動態鄰域拓撲結構。在動態鄰域拓撲結構中，初始時粒子的鄰域只有自己，隨著迭代次數的增加，鄰域范圍逐漸增大，直至最后將群體中所有粒子作為自己的鄰域。這樣可以使初始迭代有較好的局部搜索性能，而在迭代后期有較好的廣域搜索性能。（2）基于索引號的鄰域拓撲結構基于索引號的鄰域確定方法按照粒子之間的固定拓撲結構確定其鄰域，避免了計算粒子間距離的過程，因而效率較高。固定拓撲結構類型有環形結構、輪形結構、星形結構和隨機結構。在環形結構和輪形結構中還可加入捷徑，形成帶捷徑的環形結構和帶捷徑的輪形結構學習因子c和c12學習因子使粒子具有自我總結和向群體中優秀個體學習的能力，從而在飛行中向自己的歷史最優點和群體鄰域內歷史最優點靠近。c和c通常取為2。但為了提高算法性能，也可12

以使學習因子動態變化，如同步時變方法、異步時變方法等。在同步時變方法中，兩個學習

因子同步線性減小；而在異步時變方法中，隨著迭代次數不斷減小自我學習因子c和不斷增1大社會學習因子c，以達到在優化初期加強自我全局搜索，而在后期促使粒子收斂于群體2全局最優解的目的。4.慣性權重慣性權重決定了速度更新時當前速度對未來速度的影響程度。合適的選擇使粒子群優化算法具有均衡的局部探索能力和全局開發能力。較大的慣性權重使粒子在自己原來的方向上具有更大的速度，從而在原方向上飛行更遠，具有更好的局部探索能力；而較小的慣性權重則使粒子繼承的原方向的速度較小，從而飛行范圍更廣，具有更好的全局開發能力。在例子群優化算法的原始版本中，并沒有慣性權重，或者說其慣性權重始終為1。這樣的例子群優化算法被稱為基本粒子群優化算法，而帶有慣性權重的粒子群優化算法則被稱為標準粒子群優化算法。此外，人們還提出一種帶收縮因子的粒子群優化算法。其實，基本粒子群優化算法和帶收縮因子的粒子群優化算法均可視為標準粒子群優化算法的特例。慣性權重是粒子群優化算法中的重要參數，對算法的成敗有重要影響。目前，設置慣性權重的常用方法包括固定權重、時變權重、模糊權重和隨機權重。（1）固定權重：賦予慣性權重以［0,1］之間的常