遺傳算法機器人與智能技術室課件

目錄第一章緒論第二章搜索技術第三章知識表示第四章推理技術第五章機器學習第六章計算智能

第七章數據挖掘第八章智能體技術目錄第一章緒論可求解與難求解問題遺傳算法群智能算法可求解與難求解問題現實世界中的問題分類6.1可求解與難求解問題計算機在有限時間內能夠求解的(可求解問題)計算機在有限時間內不能求解的(難求解問題)計算機完全不能求解的(不可計算問題)計算復雜性是指問題的一種特性，即利用計算機求解問題的難易性或難易程度，其衡量標準：計算所需的步數或指令條數(即時間復雜度)計算所需的存儲空間大小(即空間復雜度)----通常表達為關于問題規(guī)模n的一個函數O(f(n))問題的計算復雜性現實世界中的問題分類6.1可求解與難求解問題計算機在有限時問題規(guī)模n計算量1010！2020！100100！10001000！1000010000！20！=1.216×1017203=

8000O(n3)O(3n)0.2秒4

1028秒=1015年注：每秒百萬次，n=60，1015年相當于10億臺計算機計算一百萬年O(n3)與O(3n)的差別O(n!)與O(n3)的差別O(bn),O(n!)O(1),O(logn),O(n),O(nlogn),O(nb)6.1可求解與難求解問題問題規(guī)模n計算量1010！2020！100100！10001P類問題，NP類問題，NPC類問題P類問題：多項式問題(PolynomialProblem)，指計算機可以在有限時間內求解的問題，即：P類問題是可以找出一個呈現O(na)復雜性算法的問題，其中a為常數。NP類問題：非確定性多項式問題(Non-deterministicPolynomial)。有些問題，其答案是無法直接計算得到的，只能通過間接的猜算或試算來得到結果，這就是非確定性問題(Non-deterministic)。雖然在多項式時間內難于求解但不難判斷給定一個解的正確性的問題，即：在多項式時間內可以由一個算法驗證一個解是否正確的非確定性問題，就是NP類問題。NPC問題：完全非確定性多項式問題(NP-Complete)。如果NP問題的所有可能答案都可以在多項式時間內進行正確與否的驗算的話就叫做完全非確定性多項式問題，即NP-Complete問題。6.1可求解與難求解問題P類問題，NP類問題，NPC類問題P類問題：多項式問題(P6.1可求解與難求解問題旅行商問題

對于銷售員旅行問題（TravellingSalesmanProblem,TSP），設有n個城市，城市I和城市j之間的距離為d(i,j)，要求找到一條遍訪每個城市一次而且恰好一次的旅行線路，使其路徑總長度為最短。6.1可求解與難求解問題旅行商問題NPC類問題求解窮舉法或稱遍歷法：對解空間中的每一個可能解進行驗證，直到所有的解都被驗證是否正確，便能得到精確的結果---精確解可能是O(n!)或O(an)近似解求解算法---近似解應該是O(na)?=|近似解–精確解|滿意解：?充分小時的近似解TSP問題的遍歷算法TSP問題的貪心算法仿生學算法進化算法，遺傳算法，蟻群算法，蜂群算法,…6.1可求解與難求解問題NPC類問題求解窮舉法或稱遍歷法：對解空間中的每一個可能解進6.2遺傳算法生物群體的生存過程普遍遵循達爾文的物競天擇、適者生存的進化準則；生物通過個體間的選擇、交叉、變異來適應大自然環(huán)境。6.2遺傳算法生物群體的生存過程普遍6.2遺傳算法生物染色體用數學方式或計算機方式來體現就是一串數碼，仍叫染色體，有時也叫個體；適應能力用對應一個染色體的數值來衡量；染色體的選擇或淘汰問題是按求最大還是最小問題來進行。

遺傳算法（GeneticAlgorichmsGA）是模仿生物遺傳學和自然選擇機理，通過人工方式構造的一類優(yōu)化搜索算法，是對生物進化過程進行的一種數學仿真，是進化計算的一種最重要形式。

6.2遺傳算法生物染色體用數學方式或計算6.2遺傳算法遺傳算法提出：于20世紀60年代由密歇根(Michigan)大學Hollstien,Bagleyh和Rosenberg等人在其博士論文中首先加以研究；1975年，美國J.H.Holland教授在其著作“AdaptationinNaturalandArtificialSystems”中系統(tǒng)地闡述了遺傳算法，給出了遺傳算法的基本定理和大量的數學理論證明。遺傳算法發(fā)展：DavidE.Goldberg教授1989年出版了“GeneticAlgorichms”一書，這一著作通常被認為是遺傳算法的方法、理論及應用的全面系統(tǒng)的總結。從1985年起，國際上開始陸續(xù)舉行遺傳算法的國際會議，后來又更名為進化計算。參加進化計算國際會議的人數及收錄文章的數量、廣度和深度逐年擴大。從此，進化計算逐漸成為人們用來解決高度復雜問題的新思路和新方法。

6.2遺傳算法遺傳算法提出：于20世紀60年代由6.2

遺傳算法

遺傳算法特點：遺傳算法是一種基于空間搜索的算法，它通過自然選擇、遺傳、變異等操作以及達爾文適者生存的理論，模擬自然進化過程來尋找所求問題的解答。遺傳算法具有以下特點：

(1)遺傳算法是對參數集合的編碼而非針對參數本身進行進化；

(2)遺傳算法是從問題解的編碼組開始而非從單個解開始搜索；

(3)遺傳算法利用目標函數的適應度這一信息而非利用導數或其它輔助信息來指導搜索；

(4)遺傳算法利用選擇、交叉、變異等算子而不是利用確定性規(guī)則進行隨機操作。6.2遺傳算法遺傳算法特點：遺傳算法是一種基于空間6.2

遺傳算法6.2.1遺傳算法的基本原理

霍蘭德提出的遺傳算法通常稱為簡單遺傳算法（SGA）。編碼與解碼許多應用問題的結構很復雜，但可以化為簡單的位串形式編碼表示。將問題結構變換為位串形式編碼表示的過程叫編碼；而相反將位串形式編碼表示變換為原問題結構的過程叫解碼或譯碼。把位串形式編碼表示叫染色體，有時也叫個體。

6.2遺傳算法6.2.1遺傳算法的基本原理6.2

遺傳算法對于TSP問題，可以按一條回路中城市的次序進行編碼。從城市w1開始，依次經過城市w2

，……，wn，最后回到城市w1，我們就有如下編碼表示：

w1

w2……wn由于是回路，記wn+1=w1。它其實是1，……，n的一個循環(huán)排列。要注意w1，w2，……，wn是互不相同的。6.2遺傳算法對于TSP問題，可以按一條回路中城市的次6.2

遺傳算法適應度函數為了體現染色體的適應能力，引入了對問題中的每一個染色體都能進行度量的函數，叫適應度函數（fitnessfunction）。TSP的目標是路徑總長度為最短，自然地，路徑總長度的倒數就可作為TSP問題的適應度函數:其中wn+1=w1適應度函數要有效反映每一個染色體與問題的最優(yōu)解染色體之間的差距。適應度函數的取值大小與求解問題對象的意義有很大的關系。

6.2遺傳算法適應度函數6.2

遺傳算法遺傳操作簡單遺傳算法的遺傳操作主要有有三種:選擇(selection)、交叉(crossover)、變異(mutation)。改進的遺傳算法大量擴充了遺傳操作，以達到更高的效率。選擇操作也叫復制（reproduction）操作，根據個體的適應度函數值所度量的優(yōu)劣程度決定它在下一代是被淘汰還是被遺傳。簡單遺傳算法采用賭輪選擇機制，令∑fi表示群體的適應度值之總和，fi表示種群中第i個染色體的適應度值，它產生后代的能力正好為其適應度值所占份額fi

/∑fi。6.2遺傳算法遺傳操作6.2

遺傳算法

交叉操作的簡單方式是將被選擇出的兩個個體P1和P2作為父母個體，將兩者的部分碼值進行交換。產生一個1~7之間的隨機數c，假設為3，則將P1和P2的低3位交換

10001110P1：11011001P2：10001110P1：11011001P2：1000100111011110Q1：Q2：6.2遺傳算法交叉操作的簡單方式是將被選擇出的兩個個體6.2

遺傳算法變異操作的簡單方式是改變數碼串的某個位置上的數碼。二進制編碼表示的簡單變異操作是將0與1互換：0變異為1，1變異為0。隨機產生一個1~8之間的數k，假設k=5，對從右往左第5位變異操作。

1010011016.2遺傳算法變異操作的簡單方式是改變數碼串的某個位置6.2

遺傳算法控制參數交叉發(fā)生的概率：0.6~0.95

變異的概率：0.001~0.01

種群的個數：30~100

個體的長度：定長和變長

6.2遺傳算法控制參數6.2

遺傳算法6.2.2遺傳算法的結構選擇：由個體適應度值決定

的某個規(guī)則。交叉：按概率Pc進行變異：按概率Pm進行終止條件：①完成了預先給定的進化代數②種群中的最優(yōu)個體在連續(xù)若干代

沒有改進或平均適應度在連續(xù)若

干代基本沒有改進開始初始化種群選擇操作終止條件否適應度最有優(yōu)個體計算適應度值交叉操作變異操作結束6.2遺傳算法6.2.2遺傳算法的結構開始初始化種群選擇6.2

遺傳算法6.2.3遺傳算法的性能

遺傳算法求得的解是一滿意解。影響解質量的因素：

種群的數量：太小缺少多樣性，太多影響效率

適應度函數：提升優(yōu)良個體的適應度

交叉和變異：不同的問題需構造性能更優(yōu)的交叉和變異操作

交叉概率和變異概率：6.2遺傳算法6.2.3遺傳算法的性能分析：對該問題雖然也可以采用枚舉的方法來解決,但枚舉法卻是一種效率很低的方法.可運用遺傳算法來求解該問題.解：首先對問題進行初始化，以獲得初始種群;（1）確定編碼方案：將x編碼表示為染色體的數字符號串。針對本題自變量x定義域,取值范圍為[0，31],考慮采用二進制數來對其編碼,由25=32,故使用5位無符號二進制數組成染色體數字字符串,用以表達變量x及問題的解答過程。

例:

設有函數f(x)=x2,用遺傳算法求其自變量x在區(qū)間[0，31]取整數值時的最大值。

6.2

遺傳算法分析：對該問題雖然也可以采用枚舉的方法來解決,但枚舉法卻是一

（2）選擇初始種群:通過隨機的方法來產生染色體的數字串，并組成初始種群。例如，為得到數字串的某位——又稱之為基因(genes)，使用計算機在0～1之間產生隨機數K，并按照數K的變化區(qū)域來規(guī)定基因代碼如下：

0，（0≤K＜0.5）

1，（0.5≤K≤1）6.2

遺傳算法G=（2）選擇初始種群:通過隨機的方法來產生染色體的數字串，于是隨機生成4個染色體的數字符串為：01101110000100010011從而構造了初始種群，完成了遺傳算法的準備。6.2

遺傳算法于是隨機生成4個染色體的數字符串為：6.2遺傳算法表6.1初始種群染色體及對應的適應值

6.2

遺傳算法染色體標號

串x

適應值f(x)=x2占整體的百分數

1

01101

169

14.4%

2

11000

576

49.2%

3

01000

64

5.5%

4

10011

361

30.9%

總計∑（初始種群值）

1170

100.0%表6.1初始種群染色體及對應的適應值6.2遺傳算法染色（3）復制(選擇)選擇適應值大的串作為母本，使在下一代中有更多的機會繁殖其子孫。要在四個種子個體中做選擇，要求仍然得到四個染色體，可依據適應度概率比例制定如下規(guī)則：低于0.125以下的染色體被淘汰；在0.125～0.375之間的染色體被復制一個；在0.375～0.625之間的染色體被復制兩個；在0.625～0.875之間的染色體被復制三個；在0.875以上的染色體可復制四個。6.2遺傳算法（3）復制(選擇)6.2遺傳算法對應于上例，按照適應度的計算，經復制操作后，得到新的染色體種群為

011011100011000100116.2

遺傳算法對應于上例，按照適應度的計算，經復制操作后，得到新的染色體種

某個染色體是否被復制,可以通過概率決策法、適應度比例法或“輪盤賭”的隨機方法來斷定。對應輪盤賭轉盤的隨機方法,根據表6.1數據，繪制出的輪盤賭轉盤,如圖所示:

6.2

遺傳算法49.2﹪30.9%14.4%5.5%01101110001100010011某個染色體是否被復制,可以通過概率決策法、適應度比例法或6.2

遺傳算法初始種群x

值適應度選擇概率期望值實際復制數編號（隨機產生）（無符號整數）f(x)=x2Pc

f(xi)/fA（或轉輪法）

101101131690.1440.581

211000245760.4921.972

3010008640.0550.220

410011193610.3091.231

∑11701.004.004.0

平均(A)

2930.251.001.0

MAX5760.491.972.0初始種群染色體準備復制操作的各項計算數據

6.2遺傳算法初始種群（4）交叉交叉具體分兩步：①將新復制產生的染色體隨機兩兩匹配,稱其為雙親染色體；②再把雙親染色體進行交叉繁殖。交叉的實現:設染色體數字串長度為L，把L個數字位間空隙分別標記為：1，2，…，L－1

隨機從[1，L－1]中選取某一整數位置k，0<k<L交換雙親染色體交換點位置k右邊的部分，就形成了兩個新的數字符串（也可以只交換其中的第k基因），得到了兩個新的染色體，又稱之為下一代染色體。6.2

遺傳算法（4）交叉6.2遺傳算法例如，將上例初始種群的兩個體A1=01┇10┇1A2=11┇00┇0假定從1到4間選取兩個隨機數，得到к1=2，к2=4，那么經過交叉操作之后將得到如下兩組新的數字符串A1#=01000

A2#=11101

6.2

遺傳算法A3#=01100A4#=11001

前一組數字串是使用к1=2,即將第2位后的3～5位交換得到；后一組數字串是使用к2=4，即僅將第5位因子進行交換而得。例如，將上例初始種群的兩個體6.2遺傳算法A3#=01106.2

遺傳算法編號復制操作后的區(qū)配池匹配號(隨機選取)交叉空隙位(隨機選取)交叉后新種群新種群x值適應度f(x)=x21011012201000864211000121110129841311000441100125625410011341000016256總計（∑）1786平均(A)446.5最大值(MAX)

841復制、交叉操作的各項數據6.2遺傳算法編號復制操作后的區(qū)配池匹配號(隨機選取)交叉（5）變異設變異概率取為0.001,則對于種群總共有20個基因位.期望的變異串位數計算:20×0.001=0.02(位),

故一般來說,該例中無基因位數值的改變.從表中可以看出,每經過一次復制、交叉和變異操作后,目標函數的最優(yōu)值和平均值就會有所提高。在上例中，種群的平均適應值從293增至446.5;最大的適應度數值從576增至841。特點：每經一次進化計算步驟,問題解答便向著最優(yōu)方向前進了一步;若該過程一直進行下去,就將最終走向全局的最優(yōu)解.可見進化計算的每一步操作簡單,并且系統(tǒng)的求解過程是依照計算方法與規(guī)律來決定,與本源問題自身的特性很少相關。6.2

遺傳算法（5）變異6.2遺傳算法

作業(yè)調度問題（job

shopschedulingproblem，JSSP）

對工場內的作業(yè)進行組織、調度和管理。

例：完成下述三個作業(yè)：

j1：型號a產品30件；

j2：型號b產品45件；

j3：型號a產品50件；產品a,b的生產流程有下述幾種選擇：

a:流程a1(opr2,opr7,opr9)；

a:流程a2(opr1,opr3,opr7，opr8)；

a:流程a3(opr4,opr6)；

b:流程b1(opr2,opr6,opr7)；

a:流程b2(opr1,opr9)；

6.2

遺傳算法作業(yè)調度問題（jobshopscheduling

作業(yè)調度問題（job

shopschedulingproblem，JSSP）

此處opri表示第i種操作過程，每種操作所需要的機器及時間為：

opr1

：(m110)(m320)

opr2

：(m220)

opr3

：(m220)(m330)

opr4：(m110)(m230)(m320)

opr5

：(m110)(m330)

opr6

：(m140)

opr7

：(m320)

opr8：(m150)(m230)(m310)

opr9：(m220)(m340)

此處(mjt)表示占用機器j共t個時間單元。還可以假設機器關機后的啟動時間為

m1:3，m2:5，m3:76.2

遺傳算法作業(yè)調度問題（jobshopscheduling

作業(yè)調度問題（job

shopschedulingproblem，JSSP）

編碼策略：為每臺機器建立一個優(yōu)先表（preference

list）。該表的第一個元素為機器的啟動時刻，接著是個作業(yè)的操作順序，另外兩項為“等待”（wait）和“閑置”（idle）。其譯碼過程為：只要在某機器的啟動時刻，該機器可用，則首先選擇其優(yōu)先表中的第一個允許操作。例如：

m1:（40

j3

j1

j2

‘wait’‘idle’）譯碼為：在第40時間步從作業(yè)j3中找一產品用機器m1生產。如不成功，再從j1中搜索產品進行,…遺傳算子：閑置（run-idle）：僅從那些已經等待1小時以上機器的優(yōu)先表進行操作。交叉：交換所選機器的有先表打亂（scramble）：該操作“打亂”優(yōu)先表中的成員。6.2

遺傳算法作業(yè)調度問題（jobshopscheduling地球上的生物物種在漫長的過程中形成了豐富的行為特性，并且一直不斷地完善和發(fā)展，以更好地適應其所生存的環(huán)境。生物群體和自然生態(tài)系統(tǒng)可以通過自身的演化就能使許多在人類看起來高度復雜的優(yōu)化問題得到完美解決。因此，各種模仿生物群體的智能仿生算法被相繼提出，得到了深入研究和應用實踐。群智能思想的產生主要源于復雜適應系統(tǒng)理論以及人工生命的研究。6.3群智能算法地球上的生物物種在漫長的過程中形成了豐富的行

群智能(SwarmIntelligence,SI)：1992年由Beni,Hack-wood和Wang在分子自動機系統(tǒng)中提出。1999年,Bonabeau,Dorigo和Theraulaz在《SwarmIntel-ligence:FromNaturaltoArtificialSystems》中對群智能進行了詳細的論述和分析。

2003年IEEE第一屆國際群智能研討會在美國印第安納州首府召開。

群智能定義：任何一種由昆蟲群體或其它動物社會行為機制而激發(fā)設計出的算法或分布式解決問題的策略均屬于群智能。

6.3群智能算法群智能(SwarmIntelligence,SSwarm可被描述為一些相互作用相鄰個體的集合體,蜂群、蟻群、鳥群、魚群都是Swarm的典型例子。社會性動物群體所擁有的這種特性能幫助個體很好地適應環(huán)境，個體所能獲得的信息遠比它通過自身感覺器官所取得的多，其根本原因在于個體之間存在著信息交互能力。信息的交互過程不僅僅在群體內傳播了信息，而且群內個體還能處理信息，并根據所獲得的信息(包括環(huán)境信息和附近其它個體的信息)改變自身的一些行為模式和規(guī)范,這樣就使得群體涌現出一些單個個體所不具備的能力和特性,尤其是對環(huán)境的適應能力。這種對環(huán)境變化所具有的適應能力可以被認為是一種智能,也就是說動物個體通過聚集成群而涌現出了智能。

6.3群智能算法Swarm可被描述為一些相互作用相鄰個體的集合體,6.3群智能算法

SI的定義進一步推廣（Bonabeau）:無智能或簡單智能的主體通過任何形式的聚集協(xié)同而表現出智能行為的特性。群智能理論還非常不成熟,但已成為有別于傳統(tǒng)人工智能中連接主義、行為主義和符號主義的一種新的關于智能的描述方法,并成為人工智能領域的新研究熱點。6.3群智能算法6.3.1蟻群算法

蟻群算法(AntColonyOptimization—ACO)由Colorni,Dorigo和Maniezzo于1991年提出,它是通過模擬自然界螞蟻社會的尋找食物的方式而得出的一種仿生優(yōu)化算法。自然界種蟻群尋找食物時會派出一些螞蟻分頭在四周游蕩,如果一只螞蟻找到食物,它就返回巢中通知同伴并沿途留下“信息素”(pheromone)作為蟻群前往食物所在地的標記。信息素會逐漸揮發(fā),如果兩只螞蟻同時找到同一食物,又采取不同路線回到巢中,那么比較繞彎的一條路上信息素的氣味會比較淡,蟻群將傾向于沿另一條更近的路線前往食物所在地。ACO算法設計虛擬的“螞蟻”,讓它們摸索不同路線,并留下會隨時間逐漸消失的虛擬“信息素”。根據“信息素較濃的路線更近”的原則,即可選擇出最佳路線。

6.3群智能算法6.3.1蟻群算法6.3群智能算法

ACO算法首先應用于TSP問題中,這里以TSP問題為例對算法作簡單介紹。當某一個螞蟻走到一個城市,下一步可選的路徑集合為E,集合中任一條路徑e∈E上的信息素濃度為τe,走這條路的代價為ηe,那么選擇某一條路徑v∈E的幾率為：6.3群智能算法

ACO算法首先應用于TSP問題中,這里其中,α和β兩個參數分別用來控制信息素和路徑長度的相對重要程度。當螞蟻在所有城市走過一遍之后，路徑上的信息素濃度將變?yōu)?τe(t+1)=(1-ρ)·τe(t)+Δe其中，0≤ρ<1用于控制信息素隨時間揮發(fā)的速度，Δe是上次螞蟻經過此路段所留下的信息素，未經過則為0。上式以及Δe可以根據問題進行設計。6.3群智能算法其中,α和β兩個參數分別用來控制信息素和路徑

ACO算法應用

車輛路徑問題（vehicle

routing

problem，VRP）已知一批客戶，各客戶點的位置坐標和貨物需求已知，供應商具有若干派送車輛，運載能力給定，每兩車都從起點出發(fā)，完成若干客戶點的運送任務后再回到起點，要求以最少的車輛、最小的車輛總行程完成貨物的派送任務。與TSP區(qū)別：TSP中每只螞蟻均要經過所有節(jié)點，VRP中每只螞蟻并不需要遍歷所有節(jié)點；TSP中每只螞蟻移動只需考慮路徑距離和信息量，VRP中還需考慮車輛容量限制；TSP中每只螞蟻構造出來的路徑均是一個可行解，VRP中每只螞蟻所構造的回路僅是可行解的一部分。

6.3群智能算法ACO算法應用6.3群智能算法

ACO算法應用

機組最優(yōu)投入問題（unit

commitment，UC）機組最優(yōu)投入是尋求一個周期內各個負荷水平下機組的最優(yōu)組合方式及開停機計劃，使運行費用最小，它是一個高維度、非凸的、離散的非線性組合優(yōu)化問題，很難找出理論上的最優(yōu)解。

UC的目標函數中主要包括兩個基本部分：（1）機組的發(fā)電費用；（2）機組的費用，同時還必須滿足一定的約束條件。

6.3群智能算法ACO算法應用6.3群智能算法

ACO算法應用

PID參數優(yōu)化（proportional-integral-differential，PID）

PID控制器本質上是一種對“過去”、“現在”和“未來”信息估計的控制算法。在控制工程領域中約90%的控制回路具有PID結構。在常規(guī)PID控制算法上發(fā)展了大量改進PID算法，如非線性PID、最優(yōu)PID、智能PID、自適應PID等。

任何PID控制器的性能取決于其控制參數優(yōu)化，三個部分（比例-積分-微分）參數分別是Kp、Ki、Kd，目標函數主要考慮單位階躍響應超調量σ、上升時間tr以及調整時間ts。6.3群智能算法ACO算法應用6.3群智能算法

ACO算法應用

其他應用：巖土工程：邊坡非圓弧臨界滑動面搜索技術，邊坡穩(wěn)定性分析，高填石路堤穩(wěn)定性和邊坡穩(wěn)定性分析。

化學工程：化學計量學科的光譜解析，反應動力學參數估計。生命科學：蛋白質折疊問題是生物信息學中的一個重要問題，它研究蛋白質從一維序列到三維結構的過程。親-疏水格點（hydrophobic

and

polarmonomers，HP）模型是研究該復雜過程的一個最重要的簡化模型。蛋白質折疊問題已被證明是一個NP-C問題。ACO算法可用于HP模型測試序列求解。6.3群智能算法ACO算法應用6.3群智能算法6.3.2粒子群算法

粒子群優(yōu)化算法（ParticleSwarmOptimization—PSO)源于1987年Reynolds對鳥群社會系統(tǒng)boids的仿真研究，boids也是一個CAS。在boids中,一群鳥在空中飛行,每個鳥遵守以下三條規(guī)則:

（1）避免與相鄰的鳥發(fā)生碰撞沖突;（2）盡量與自己周圍的鳥在速度上保持協(xié)調和一致;

（3）盡量試圖向自己所認為的群體中心靠近。僅僅通過使用這三條規(guī)則,boids系統(tǒng)就出現非常逼真的群體聚集行為,鳥成群地在空中飛行,當遇到障礙時它們會分開繞行而過,隨后又會重新形成群體。不過Reynolds僅僅將其作為CAS的一個實例作仿真研究,而并未將它用于優(yōu)化計算中,也無任何實用價值。

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

在PSO系統(tǒng)初始化為一群隨機粒子(隨機解)，然后通過迭代找到最優(yōu)解。在每一次迭代中,粒子通過跟蹤兩個“極值”來更新自己,同時也通過跟蹤它們實現粒子間的信息交換。第一個就是粒子本身所找到的最優(yōu)解,這個解叫作個體極值pBest(“自身經驗”)。另一個極值是整個群體目前找