離散粒子群最佳化.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Recent Advances in Particle Swarm 授課教授 ：葉榮懋 教授 報 告 者 ：蔡宏林 報告大綱 1.緒論 2.基本算法 3.離散粒子群最佳化 4.在複雜環境的PSO算法 6.總結 5. PSO的應用 1.緒論 粒子群演算法是以鳥群為根基的隨機最佳化技術由Kennedy和Eberhart在1995提出 本文回顧了粒子演算法近年來的發展，以及討論各種參數使用情況並修改參數，以適應不同的現實複雜環境  1.緒論 在過去幾年中粒子演算法，已經發表超過300篇有關粒子群的文章，越來越多的研究者對於這種新的算法有興趣，並從不同角度下去研究  每年發表論文的數量,2003年報告不完整 2.基本算法 起源 生物社會學家對鳥群尋找食物行為的研究 原理 我們可以設想這樣的一個場景，一群鳥再隨機搜尋食物。這個區域裡只有一塊食物。所有的鳥都不知道食物再哪裡，但他們知道目前距離食物還有多遠，那麼找到食物的最佳策略是什麼？最簡單的方法就是找尋距離食物最近的鳥之周圍區域及根據自己本身飛行的經驗判斷食物的所在。  ， 2.基本算法 在總體有哪些信誉好的足球投注网站空間，粒子群每個單一的解答，就像是“鳥”的有哪些信誉好的足球投注网站空間，被稱為“粒子”所有的粒子的適合價值是要評估適合函數的優選和粒子飛行的速度，按照粒子的最佳解決方案讓這些粒子穿過問題空間 特點 分散式搜尋 具記憶性 元件較少，容易實現 適合在連續性的範圍內搜尋  2.基本算法  Food Global Best Solution Past Best Solution 鳥群的覓食行為 2.基本算法 初始化： 將群族做初始化，以隨機的方式求出每一粒子之初始位置與速度 估算： 依據適應度函數計算出其最適合值以作為判斷每一粒子之好壞 適合的Pbest： 找出每一粒子到目前為止的搜尋過程中最佳解，這個最佳解我們將之稱為Pbest 適合的Gbest： 找出所有粒子到目前為止所搜尋到的整體最佳解，此最佳解我們稱之為Gbest 更新： 更新每一粒子之速度與位置 回到步驟2繼續執行，直到獲得一個令人滿意的結果或符合終止條件為止 最後會得到Pgd ， f(Pgd)就是解的結果  2.基本算法-速度更新函數  Vid：每一粒子在第d維之速度 i：粒子之編號 d：維度 w：Inertia Weight c1、c2：學習常數 Rand( )：一介於0至1的亂數 Pid ：每一粒子到目前為止，所出現的最佳位置 Pnd：所有粒子到目前為止，所出現的最佳位置 Xid ：每一粒子目前之所在 2.基本算法-更新位置  粒子群內的每一個粒子點更新如下公式 2.基本算法 pBest nBest C1和C2 w 是取得最好的粒子本身位置 是目前為止粒子鄰居的一個最佳位置 代表權重的隨機加速限制 慣性權重 2.基本算法-pBest 適應度函數的唯一最好的位置並不總是取決於價值 許多限制因素，可用於定義的最佳位置，以適應不同的問題. 而這並不會降低有哪些信誉好的足球投注网站能力和性能 例如，在非線性限制最佳化問題, 在可行解空間粒子只記得這些位置和無視不可行的解決方案, 這個簡單的修改成功定位最佳化系列基準問題 2.基本算法-nBest 傳統來說, PSO算法需要某些預先設定共同粒子的鄰居，鄰居的數目或大小會影響收斂算法的速度. 普遍認為，規模較大的鄰居粒子收斂更快，而小規模鄰居將有助於防止粒子的不成熟提早收斂. gBest是一個極端的情況的nBest版本 2.基本算法-C1 C2 從心理學的角度, 認知項代表個人的傾向重複過去的行為，已證明是成功的，而社會的長期趨勢是遵循別人的成功 學習常數一般設定為 c1 = c2 = 2 不過在文獻中也有其他的取值，一般設定c1 = c2 值介於0~4之間 2.基本算法-其它參數 粒子數：一般取 20 ~ 40個，大部分的問題用10 ~ 20個粒子就能取的不錯的結果 Vmax ：最大速度，決定粒子再一個循環中最大的移動距離 例如: 問題適應度函數: f(x)= x1^2+x2^2+x3^2 其中限制式為 -10= x1, x2, x3 = 10 則Vmax 的大小就是10-(-10) = 20 3.離散粒子群最佳化 許多最佳化問題涉及離散或二進制變量，典型的例子是調度問題或路徑問題 PSO程序的更新公式被導向為而設計連續的空間 必須設法適應離散的空間，該編碼的變化可能很簡單，但是很難定義速度的意思以及決定軌道的變化 3.離散粒子群最佳化 Kennedy Chang Mohan 定義 PSO 的第一個離散二進制粒子群的版本，這些粒子