導航:首頁 > 源碼編譯 > 粒子群演算法與自然科學的關系

粒子群演算法與自然科學的關系

發布時間:2023-06-05 12:04:16

Ⅰ 什麼是粒子群演算法

粒子群演算法介紹(摘自http://blog.sina.com.cn/newtech)
優化問題是工業設計中經常遇到的問題,許多問題最後都可以歸結為優化問題. 為了解決各種各樣的優化問題,人們提出了許多優化演算法,比較著名的有爬山法、遺傳演算法等.優化問題有兩個主要問題:一是要求尋找全局最小點,二是要求有較高的收斂速度. 爬山法精度較高,但是易於陷入局部極小. 遺傳演算法屬於進化演算法( Evolutionary Algorithms) 的一種,它通過模仿自然界的選擇與遺傳的機理來尋找最優解. 遺傳演算法有三個基本運算元:選擇、交叉和變異. 但是遺傳演算法的編程實現比較復雜,首先需要對問題進行編碼,找到最優解之後還需要對問題進行解碼,另外三個運算元的實現也有許多參數,如交叉率和變異率,並且這些參數的選擇嚴重影響解的品質,而目前這些參數的選擇大部分是依靠經驗.1995 年Eberhart 博士和kennedy 博士提出了一種新的演算法;粒子群優化(Partical Swarm Optimization -PSO) 演算法 . 這種演算法以其實現容易、精度高、收斂快等優點引起了學術界的重視,並且在解決實際問題中展示了其優越性.

粒子群優化(Partical Swarm Optimization - PSO) 演算法是近年來發展起來的一種新的進化演算法( Evolu2tionary Algorithm - EA) .PSO 演算法屬於進化演算法的一種,和遺傳演算法相似,它也是從隨機解出發,通過迭代尋找最優解,它也是通過適應度來評價解的品質. 但是它比遺傳演算法規則更為簡單,它沒有遺傳演算法的「交叉」(Crossover) 和「變異」(Mutation) 操作. 它通過追隨當前搜索到的最優值來尋找全局最優 .

粒子群演算法

1. 引言

粒子群優化演算法(PSO)是一種進化計算技術(evolutionary computation),有Eberhart博士和kennedy博士發明。源於對鳥群捕食的行為研究

PSO同遺傳演算法類似,是一種基於疊代的優化工具。系統初始化為一組隨機解,通過疊代搜尋最優值。但是並沒有遺傳演算法用的交叉(crossover)以及變異(mutation)。而是粒子在解空間追隨最優的粒子進行搜索。詳細的步驟以後的章節介紹

同遺傳演算法比較,PSO的優勢在於簡單容易實現並且沒有許多參數需要調整。目前已廣泛應用於函數優化,神經網路訓練,模糊系統控制以及其他遺傳演算法的應用領域

2. 背景: 人工生命

"人工生命"是來研究具有某些生命基本特徵的人工系統. 人工生命包括兩方面的內容

1. 研究如何利用計算技術研究生物現象
2. 研究如何利用生物技術研究計算問題

我們現在關注的是第二部分的內容. 現在已經有很多源於生物現象的計算技巧. 例如, 人工神經網路是簡化的大腦模型. 遺傳演算法是模擬基因進化過程的.

現在我們討論另一種生物系統- 社會系統. 更確切的是, 在由簡單個體組成的群落與環境以及個體之間的互動行為. 也可稱做"群智能"(swarm intelligence). 這些模擬系統利用局部信息從而可能產生不可預測的群體行為

例如floys 和 boids, 他們都用來模擬魚群和鳥群的運動規律, 主要用於計算機視覺和計算機輔助設計.

在計算智能(computational intelligence)領域有兩種基於群智能的演算法. 蟻群演算法(ant colony optimization)和粒子群演算法(particle swarm optimization). 前者是對螞蟻群落食物採集過程的模擬. 已經成功運用在很多離散優化問題上.

粒子群優化演算法(PSO) 也是起源對簡單社會系統的模擬. 最初設想是模擬鳥群覓食的過程. 但後來發現PSO是一種很好的優化工具.

3. 演算法介紹

如前所述,PSO模擬鳥群的捕食行為。設想這樣一個場景:一群鳥在隨機搜索食物。在這個區域里只有一塊食物。所有的鳥都不知道食物在那裡。但是他們知道當前的位置離食物還有多遠。那麼找到食物的最優策略是什麼呢。最簡單有效的就是搜尋目前離食物最近的鳥的周圍區域。

PSO從這種模型中得到啟示並用於解決優化問題。PSO中,每個優化問題的解都是搜索空間中的一隻鳥。我們稱之為「粒子」。所有的例子都有一個由被優化的函數決定的適應值(fitness value),每個粒子還有一個速度決定他們飛翔的方向和距離。然後粒子們就追隨當前的最優粒子在解空間中搜索

PSO 初始化為一群隨機粒子(隨機解)。然後通過疊代找到最優解。在每一次疊代中,粒子通過跟蹤兩個"極值"來更新自己。第一個就是粒子本身所找到的最優解。這個解叫做個體極值pBest. 另一個極值是整個種群目前找到的最優解。這個極值是全局極值gBest。另外也可以不用整個種群而只是用其中一部分最為粒子的鄰居,那麼在所有鄰居中的極值就是局部極值。

在找到這兩個最優值時, 粒子根據如下的公式來更新自己的速度和新的位置

v[] = v[] + c1 * rand() * (pbest[] - present[]) + c2 * rand() * (gbest[] - present[]) (a)
present[] = persent[] + v[] (b)

v[] 是粒子的速度, persent[] 是當前粒子的位置. pbest[] and gbest[] 如前定義 rand () 是介於(0, 1)之間的隨機數. c1, c2 是學習因子. 通常 c1 = c2 = 2.

程序的偽代碼如下

For each particle
____Initialize particle
END

Do
____For each particle
________Calculate fitness value
________If the fitness value is better than the best fitness value (pBest) in history
____________set current value as the new pBest
____End

____Choose the particle with the best fitness value of all the particles as the gBest
____For each particle
________Calculate particle velocity according equation (a)
________Update particle position according equation (b)
____End
While maximum iterations or minimum error criteria is not attained

在每一維粒子的速度都會被限制在一個最大速度Vmax,如果某一維更新後的速度超過用戶設定的Vmax,那麼這一維的速度就被限定為Vmax

4. 遺傳演算法和 PSO 的比較

大多數演化計算技術都是用同樣的過程
1. 種群隨機初始化
2. 對種群內的每一個個體計算適應值(fitness value).適應值與最優解的距離直接有關
3. 種群根據適應值進行復制
4. 如果終止條件滿足的話,就停止,否則轉步驟2

從以上步驟,我們可以看到PSO和GA有很多共同之處。兩者都隨機初始化種群,而且都使用適應值來評價系統,而且都根據適應值來進行一定的隨機搜索。兩個系統都不是保證一定找到最優解

但是,PSO 沒有遺傳操作如交叉(crossover)和變異(mutation). 而是根據自己的速度來決定搜索。粒子還有一個重要的特點,就是有記憶。

與遺傳演算法比較, PSO 的信息共享機制是很不同的. 在遺傳演算法中,染色體(chromosomes) 互相共享信息,所以整個種群的移動是比較均勻的向最優區域移動. 在PSO中, 只有gBest (or lBest) 給出信息給其他的粒子,這是單向的信息流動. 整個搜索更新過程是跟隨當前最優解的過程. 與遺傳演算法比較, 在大多數的情況下,所有的粒子可能更快的收斂於最優解

5. 人工神經網路 和 PSO

人工神經網路(ANN)是模擬大腦分析過程的簡單數學模型,反向轉播演算法是最流行的神經網路訓練演算法。進來也有很多研究開始利用演化計算(evolutionary computation)技術來研究人工神經網路的各個方面。

演化計算可以用來研究神經網路的三個方面:網路連接權重,網路結構(網路拓撲結構,傳遞函數),網路學習演算法。

不過大多數這方面的工作都集中在網路連接權重,和網路拓撲結構上。在GA中,網路權重和/或拓撲結構一般編碼為染色體(Chromosome),適應函數(fitness function)的選擇一般根據研究目的確定。例如在分類問題中,錯誤分類的比率可以用來作為適應值

演化計算的優勢在於可以處理一些傳統方法不能處理的例子例如不可導的節點傳遞函數或者沒有梯度信息存在。但是缺點在於:在某些問題上性能並不是特別好。2. 網路權重的編碼而且遺傳運算元的選擇有時比較麻煩

最近已經有一些利用PSO來代替反向傳播演算法來訓練神經網路的論文。研究表明PSO 是一種很有潛力的神經網路演算法。PSO速度比較快而且可以得到比較好的結果。而且還沒有遺傳演算法碰到的問題

這里用一個簡單的例子說明PSO訓練神經網路的過程。這個例子使用分類問題的基準函數(Benchmark function)IRIS數據集。(Iris 是一種鳶尾屬植物) 在數據記錄中,每組數據包含Iris花的四種屬性:萼片長度,萼片寬度,花瓣長度,和花瓣寬度,三種不同的花各有50組數據. 這樣總共有150組數據或模式。

我們用3層的神經網路來做分類。現在有四個輸入和三個輸出。所以神經網路的輸入層有4個節點,輸出層有3個節點我們也可以動態調節隱含層節點的數目,不過這里我們假定隱含層有6個節點。我們也可以訓練神經網路中其他的參數。不過這里我們只是來確定網路權重。粒子就表示神經網路的一組權重,應該是4*6+6*3=42個參數。權重的范圍設定為[-100,100] (這只是一個例子,在實際情況中可能需要試驗調整).在完成編碼以後,我們需要確定適應函數。對於分類問題,我們把所有的數據送入神經網路,網路的權重有粒子的參數決定。然後記錄所有的錯誤分類的數目作為那個粒子的適應值。現在我們就利用PSO來訓練神經網路來獲得盡可能低的錯誤分類數目。PSO本身並沒有很多的參數需要調整。所以在實驗中只需要調整隱含層的節點數目和權重的范圍以取得較好的分類效果。

6. PSO的參數設置

從上面的例子我們可以看到應用PSO解決優化問題的過程中有兩個重要的步驟: 問題解的編碼和適應度函數
PSO的一個優勢就是採用實數編碼, 不需要像遺傳演算法一樣是二進制編碼(或者採用針對實數的遺傳操作.例如對於問題 f(x) = x1^2 + x2^2+x3^2 求解, 粒子可以直接編碼為 (x1, x2, x3), 而適應度函數就是f(x). 接著我們就可以利用前面的過程去尋優.這個尋優過程是一個疊代過程, 中止條件一般為設置為達到最大循環數或者最小錯誤

PSO中並沒有許多需要調節的參數,下面列出了這些參數以及經驗設置

粒子數: 一般取 20 – 40. 其實對於大部分的問題10個粒子已經足夠可以取得好的結果, 不過對於比較難的問題或者特定類別的問題, 粒子數可以取到100 或 200

粒子的長度: 這是由優化問題決定, 就是問題解的長度

粒子的范圍: 由優化問題決定,每一維可是設定不同的范圍

Vmax: 最大速度,決定粒子在一個循環中最大的移動距離,通常設定為粒子的范圍寬度,例如上面的例子里,粒子 (x1, x2, x3) x1 屬於 [-10, 10], 那麼 Vmax 的大小就是 20

學習因子: c1 和 c2 通常等於 2. 不過在文獻中也有其他的取值. 但是一般 c1 等於 c2 並且范圍在0和4之間

中止條件: 最大循環數以及最小錯誤要求. 例如, 在上面的神經網路訓練例子中, 最小錯誤可以設定為1個錯誤分類, 最大循環設定為2000, 這個中止條件由具體的問題確定.

全局PSO和局部PSO: 我們介紹了兩種版本的粒子群優化演算法: 全局版和局部版. 前者速度快不過有時會陷入局部最優. 後者收斂速度慢一點不過很難陷入局部最優. 在實際應用中, 可以先用全局PSO找到大致的結果,再有局部PSO進行搜索.

另外的一個參數是慣性權重, 由Shi 和Eberhart提出, 有興趣的可以參考他們1998年的論文(題目: A modified particle swarm optimizer)

Ⅱ 粒子群演算法及應用的介紹

粒子群演算法是一種新的模仿鳥類群體行為的智能優化演算法,現已成為進化演算法的一個新的重要分支。全書共分為八章,分別論述了基本粒子群演算法和改進粒子群演算法的原理,並且詳細介紹了粒子群演算法在函數優化、圖像壓縮和基因聚類中的應用,最後給出了粒子群演算法的應用綜述和相關程序代碼。

Ⅲ 粒子群演算法的引言

優化問題是工業設計中經常遇到的問題,許多問題最後都可以歸結為優化問題. 為了解決各種各樣的優化問題,人們提出了許多優化演算法,比較著名的有爬山法、遺傳演算法、神經網路演算法等. 一是要求尋找全局最優點,
二是要求有較高的收斂速度. 近年來,一些學者將PSO演算法推廣到約束優化問題,其關鍵在於如何處理好約束,即解的可行性。如果約束處理的不好,其優化的結果往往會出現不能夠收斂和結果是空集的狀況。基於PSO演算法的約束優化工作主要分為兩類:
(1)罰函數法。罰函數的目的是將約束優化問題轉化成無約束優化問題。
(2)將粒子群的搜索范圍都限制在條件約束簇內,即在可行解范圍內尋優。
根據文獻介紹,Parsopoulos等採用罰函數法,利用非固定多段映射函數對約束優化問題進行轉化,再利用PSO演算法求解轉化後問題,模擬結果顯示PSO演算法相對遺傳演算法更具有優越性,但其罰函數的設計過於復雜,不利於求解;Hu等採用可行解保留政策處理約束,即一方面更新存儲中所有粒子時僅保留可行解,另一方面在初始化階段所有粒子均從可行解空間取值,然而初始可行解空間對於許多問題是很難確定的;Ray等提出了具有多層信息共享策略的粒子群原理來處理約束,根據約束矩陣採用多層Pareto排序機制來產生優良粒子,進而用一些優良的粒子來決定其餘個體的搜索方向。
但是,目前有關運用PSO演算法方便實用地處理多約束目標優化問題的理論成果還不多。處理多約束優化問題的方法有很多,但用PSO演算法處理此類問題目前技術並不成熟,這里就不介紹了。 粒子群優化演算法(PSO)是一種進化計算技術(evolutionary computation),1995 年由Eberhart 博士和kennedy 博士提出,源於對鳥群捕食的行為研究 。該演算法最初是受到飛鳥集群活動的規律性啟發,進而利用群體智能建立的一個簡化模型。粒子群演算法在對動物集群活動行為觀察基礎上,利用群體中的個體對信息的共享使整個群體的運動在問題求解空間中產生從無序到有序的演化過程,從而獲得最優解。
PSO同遺傳演算法類似,是一種基於迭代的優化演算法。系統初始化為一組隨機解,通過迭代搜尋最優值。但是它沒有遺傳演算法用的交叉(crossover)以及變異(mutation),而是粒子在解空間追隨最優的粒子進行搜索。同遺傳演算法比較,PSO的優勢在於簡單容易實現並且沒有許多參數需要調整。目前已廣泛應用於函數優化,神經網路訓練,模糊系統控制以及其他遺傳演算法的應用領域。

Ⅳ 粒子群演算法

粒子群演算法(Particle Swarm Optimization),又稱鳥群覓食演算法,是由數學家J. Kennedy和R. C. Eberhart等開發出的一種新的進化演算法。它是從隨機解開始觸發,通過迭代尋找出其中的最優解。本演算法主要是通過適應度來評價解的分數,比傳統的遺傳演算法更加的簡單,它沒有傳統遺傳演算法中的「交叉」和「變異」等操作,它主要是追隨當前搜索到的最優值來尋找到全局最優值。這種演算法實現容易,精度高,收斂快等特點被廣泛運用在各個問題中。

粒子群演算法是模擬鳥群覓食的所建立起來的一種智能演算法,一開始所有的鳥都不知道食物在哪裡,它們通過找到離食物最近的鳥的周圍,再去尋找食物,這樣不斷的追蹤,大量的鳥都堆積在食物附近這樣找到食物的幾率就大大增加了。粒子群就是這樣一種模擬鳥群覓食的過程,粒子群把鳥看成一個個粒子,它們擁有兩個屬性——位置和速度,然後根據自己的這兩個屬性共享到整個集群中,其他粒子改變飛行方向去找到最近的區域,然後整個集群都聚集在最優解附近,最後最終找到最優解。

演算法中我們需要的數據結構,我們需要一個值來存儲每個粒子搜索到的最優解,用一個值來存儲整個群體在一次迭代中搜索到的最優解,這樣我們的粒子速度和位置的更新公式如下:

其中pbest是每個粒子搜索到的最優解,gbest是整個群體在一次迭代中搜索到的最優解,v[i]是代表第i個粒子的速度,w代表慣性系數是一個超參數,rang()表示的是在0到1的隨機數。Present[i]代表第i個粒子當前的位置。我們通過上面的公式不停的迭代粒子群的狀態,最終得到全局最優解

Ⅳ 粒子群演算法原理

粒子群算悉銀法原理如下:

粒子群優化(Particle Swarm Optimization,PSO)演算法是1995年由美國學者Kennedy等人提出的,該演算法是模擬鳥類覓食等群體智能行為的智能優化演算法。在自然界中,鳥群在覓食的時候,一般存在個體和群體協同的行為。

每個粒子都旦薯會向兩個值學習,一個值是個體的歷史最優值 ;另一個值是群體的歷史最優值(全局最優值) 。粒子會根據這兩個值來調整自身的速度和位置,而每個位置的優劣都是根據適應度值來確定的。適應度函數是優化的目標函數。

Ⅵ 粒子群演算法及其應用

既然是數學系的,可以考慮從粒子群演算法的收斂性證明和分布性檢驗方面著手,偏理論性的證明,這方面比較欠缺,有點類似於高樓地基不穩,大家卻在上面繼續壘
可以參考遺傳演算法的模式定理或隱性並行性定理等,如果能夠提出關於粒子群演算法的定理,應該足夠具有挑戰性了
還有就是對粒子群演算法進行演算法融合或改進,然後針對改進的演算法進行測試,檢驗其在函數優化等方面的效能。

Ⅶ 粒子群演算法屬於什麼學科

粒子群演算法屬於計算智能的范疇,如果按照學科分的話當然是計算機學科。
另外粒子群演算法是一種進化計算技術(evolutionary computation),1995 年由Eberhart 博士和kennedy 博士提出,源於對鳥群捕食的行為研究 。
——————————————————————————
另外關於計算智能的相關介紹便可以了解
計算智能的主要方法有人工神經網路、遺傳演算法、遺傳程序、演化程序、局部搜索、模擬退火等等。這些方法具有以下共同的要素:自適應的結構、隨機產生的或指定的初始狀態、適應度的評測函數、修改結構的操作、系統狀態存儲器、終止計算的條件、指示結果的方法、控制過程的參數。計算智能的這些方法具有自學習、自組織、自適應的特徵和簡單、通用、魯棒性強、適於並行處理的優點。在並行搜索、聯想記憶、模式識別、知識自動獲取等方面得到了廣泛的應用。
典型的代表如遺傳演算法、免疫演算法、模擬退火演算法、蟻群演算法、微粒群演算法(也就是粒子群演算法,翻譯不同罷了),都是一種仿生演算法,基於「從大自然中獲取智慧」的理念,通過人們對自然界獨特規律的認知,提取出適合獲取知識的一套計算工具。總的來說,通過自適應學習的特性,這些演算法達到了全局優化的目的。

Ⅷ 粒子群演算法(一):粒子群演算法概述

  本系列文章主要針對粒子群演算法進行介紹和運用,並給出粒子群演算法的經典案例,從而進一步加深對粒子群演算法的了解與運用(預計在一周內完成本系列文章)。主要包括四個部分:

  粒子群演算法也稱粒子群優化演算法(Particle Swarm Optimization, PSO),屬於群體智能優化演算法,是近年來發展起來的一種新的進化演算法(Evolutionary Algorithm, EA)。 群體智能優化演算法主要模擬了昆蟲、獸群、鳥群和魚群的群集行為,這些群體按照一種合作的方式尋找食物,群體中的每個成員通過學習它自身的經驗和其他成員的經驗來不斷地改變搜索的方向。 群體智能優化演算法的突出特點就是利用了種群的群體智慧進行協同搜索,從而在解空間內找到最優解。
  PSO 演算法和模擬退火演算法相比,也是 從隨機解出發,通過迭代尋找最優解 。它是通過適應度來評價解的品質,但比遺傳演算法規則更為簡單,沒有遺傳演算法的「交叉」和「變異」,它通過追隨當前搜索到的最大適應度來尋找全局最優。這種演算法以其 容易實現、精度高、收斂快 等優點引起了學術界的重視,並在解決實際問題中展示了其優越性。

  在粒子群演算法中,每個優化問題的解被看作搜索空間的一隻鳥,即「粒子」。演算法開始時首先生成初始解,即在可行解空間中隨機初始化 粒子組成的種群 ,其中每個粒子所處的位置 ,都表示問題的一個解,並依據目標函數計算搜索新解。在每次迭代時,粒子將跟蹤兩個「極值」來更新自己, 一個是粒子本身搜索到的最好解 ,另一個是整個種群目前搜索到的最優解 。 此外每個粒子都有一個速度 ,當兩個最優解都找到後,每個粒子根據如下迭代式更新:

  其中參數 稱為是 PSO 的 慣性權重(inertia weight) ,它的取值介於[0,1]區間;參數 和 稱為是 學習因子(learn factor) ;而 和 為介於[0,1]之間的隨機概率值。
  實踐證明沒有絕對最優的參數,針對不同的問題選取合適的參數才能獲得更好的收斂速度和魯棒性,一般情況下 , 取 1.4961 ,而 採用 自適應的取值方法 ,即一開始令 , 使得 PSO 全局優化能力較強 ;隨著迭代的深入,遞減至 , 從而使得PSO具有較強的局部優化能力

  參數 之所以被稱之為慣性權重,是因為 實際 反映了粒子過去的運動狀態對當前行為的影響,就像是我們物理中提到的慣性。 如果 ,從前的運動狀態很少能影響當前的行為,粒子的速度會很快的改變;相反, 較大,雖然會有很大的搜索空間,但是粒子很難改變其運動方向,很難向較優位置收斂,由於演算法速度的因素,在實際運用中很少這樣設置。也就是說, 較高的 設置促進全局搜索,較低的 設置促進快速的局部搜索。

閱讀全文

與粒子群演算法與自然科學的關系相關的資料

熱點內容
很黃很暴力的電影:審美趨勢與社會反思 瀏覽:977
如何搭建liunx伺服器配置 瀏覽:657
vs編譯成功後 瀏覽:29
java界面開發與案例詳解 瀏覽:592
伺服器太累了怎麼回事 瀏覽:991
勝利之日伺服器做什麼 瀏覽:108
6688電影電視劇:推薦、變革與影響 瀏覽:297
電影免費鬼片:觀影方法和推薦網站 瀏覽:444
關於變臉電影的信息 瀏覽:584
在線看片的網址:10個熱門選擇 瀏覽:596
無廣告影院:提供純凈觀影體驗的新選擇 瀏覽:377
胡八一全部電影:中國電影史上的經典之作 瀏覽:592
日本加密路線 瀏覽:463
三級免費電影:探索年輕人追夢的冒險之路 瀏覽:842
聯想電腦解壓字體如何下到ps中 瀏覽:154