粒子群演算法英文文獻

『壹』 什麼是粒子群演算法

粒子群演算法介紹（摘自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)

『貳』 高分急求！ 關於 粒子群解決車間調度的英文文獻 ！ ！先50 滿意再加50

基於動態雙種群粒子群
演算法的柔性工作車間調度
摘 要: 針對標准粒子群優化演算法存在易陷入局部最優點的缺點,提出了一種基於動態雙種群的粒子群
優化演算法(DPSO) ·DPSO 演算法將種群劃分成兩個種群規模隨進化過程不斷變化的子種群,兩個子種群分別采
用不同的學習策略進行進化,並在進化過程中相互交換信息·該演算法提高了全局尋優能力,有效地避免了早熟
收斂的發生·將以DPSO 演算法為基礎的排序演算法和啟發式分配演算法(HA) 相結合形成了解決柔性工作車間調
度問題的新方法(DPSO2HA) ·通過對算例的研究和與其他方法的比較表明,該方法是有效可行的·
A Dynamic Double2Population Particle Swarm Optimization
Algorithm for Flexible Job2Shop Scheling
L I Dan , GA O L i2qun , MA Jia , L I Yang
( School of Information Science & Engineering , Northeastern University , Shenyang 110004 , China.
Correspondent : L I Dan , E2mail : lidanneu @163. com)
Abstract : A dynamic double2population particle swarm optimization ( DPSO) algorithm is
presented to solve the problem that the standard PSO algorithm is easy to fall into a locally
optimized point , where the population is divided into two sub2populations varying with their own
evolutionary learning st rategies and the information exchange between them. The algorithm thus
improves it s solvability for global optimization to avoid effectively the precocious convergence.
Then , an ordering algorithm based on DPSO is integrated with the heuristic assignation ( HA)
algorithm to form a new algorithm DPSO2HA so as to solve the flexible job2shop scheling
problem (FJ SP) . The new algorithm is applied to a set of benchmark problems as instances , and
the simulation result s show the effectiveness and feasibility of DPSO2HA algorithm for the flexible
job2shop scheling.
Key words : double population ; PSO(particle swarm optimization) ; learning st rategy ; DPSO2HA
algorithm; flexible job2shop scheling
柔性工作車間調度問題( flexible job2shop
scheling problem , FJ SP) 是經典工作車間調度
問題的一個延伸,它允許工件被給定的有處理能
力的任何機器處理·柔性工作車間調度問題由於
減少了機器約束,擴大了可行解的搜索范圍,提高
了問題的復雜性,所以與傳統工作車間調度問題
相比更加接近實際生產環境的模擬·
相對於傳統工作車間調度,關於柔性工作車
間調度問題的文獻還比較少·目前所採用的方法
主要有分枝定界法[1 ] 、多項式演算法、分等級法和
傳統進化演算法( EA) [2 ]等,在近幾年中,很多研究
者使用禁忌搜索和遺傳演算法對FJ SP 進行求
解[3 - 4 ]
·
本文提出一個新的求解柔性工作車間調度問
題的方法———基於動態雙種群粒子群優化的分階
段方法·本方法的主要思想是:將柔性工作車間調
度問題分解成兩個有時間順序的子問題來考慮,
首先考慮工序排序子問題,在獲得可行的排序後
再考慮機器分配子問題·本文首先利用動態雙種
群粒子群優化演算法為工序進行排序,使其滿足約
束條件從而獲得一個可行解,然後利用文中所提
出的分配演算法為每道工序分配合適的機器,形成
可行的調度方案·本文所考慮的優化目標是最小
化最大完工時間(makespan) ·
1 柔性工作車間調度問題描述
柔性工作車間調度問題可描述為將n 個加工
順序不同的工件在m 台機器上加工完成·每個工
件使用同一台機器可以多於一次,每道工序的加工
過程不允許中斷·機器的集合用U 來表示,每個工
件J 包含nj 道工序,各工序之間的順序不允許改
變·Oij表示工件J 的第i 道工序,它可以在有處理
能力的任何一台機器上被加工·Ti , j , k表示工序Oij
用機器Mk 來加工所需要的時間, 可用集合T =
{ Ti , j , k| 1 ≤j ≤N ;1 ≤i ≤nj ;1 ≤k ≤M}表示, N 為
工件的數量, M 為機器的數量·例如表1 即是一個
實際的柔性工作車間調度加工時間表·
表1 柔性工作車間調度加工時間表
Table 1 Proce ssing schele for FJ SP
工件工序M1 M2 M3 M4
J1
O1 ,1 1 3 4 1
O2 ,1 3 8 2 1
O3 ,1 3 5 4 7
J2
O1 ,2 4 1 1 4
O2 ,2 2 3 9 3
O3 ,2 9 1 2 2
J3
O1 ,3 8 6 3 5
O2 ,3 4 5 8 1
在柔性工作車間調度問題中, 應滿足以下假
設:
(1) 所有的機器在時間t = 0 時都是可以使
用的,每個工件都可以在t = 0 時開始加工;
(2) 在給定的時間內, 一台機器只能加工一
道工序,直到加工完此工序後方可加工其他工序,
這就是所謂的資源約束;
(3) 對於每個工件的各道工序只能按照事先
給定的順序加工,這就是所謂的優先約束·
對於每一道工序Oi , j , 本文用ri , j來表示其
最早開始加工時間, 對不同的工序分別用下式進
行計算:
ri , j =
0 , 1 ≤ j ≤ N ;
ri - 1 , j +γi , j , 2 ≤ i ≤ nj ,1 ≤ j ≤ N ·
式中,γi , j = mink ( Ti , j , k) ,1 ≤i ≤nj ;1 ≤j ≤N·
對於FJ SP 來說一般存在兩個難題:第一個
是如何為每道工序選擇合適的機器;第二個是如
何計算每道工序的開始加工時間t i , j和結束加工
時間tf i , j·
本文所要研究的FJ SP 的優化目標是,在滿
足上述優先約束和資源約束的條件下尋找最優調
度方案,使全部工件的最大完工時間(Makespan)
最短·
2 排序演算法———動態雙種群粒子群
優化演算法
2. 1 標准粒子群優化演算法
粒子群優化(particle swarm optimization ,簡
稱PSO) 演算法是由Kennedy 和Eberhart 在1995
年提出·在PSO 系統中,每個潛在解被稱為一個
粒子,多個粒子共存、合作尋優,每個粒子根據它
自身的經驗在目標搜索空間中向更好的位置飛
行,搜索最優解·由文獻[ 5 ]可知,每個粒子根據如
下的公式來更新自己的速度和在解空間的位置·
v ( t +1)
id = w v ( t)
id + c1 r1 p ( t)
id - x ( t)
id +
c2 r2 p ( t)
gd - x ( t)
id , (1)
x ( t +1)
id = x ( t)
id + v ( t +1)
id · (2)
其中, d = 1 ,2 , ⋯, n , i = 1 ,2 , ⋯, m , m 為種群規
模; t 為當前進化代數; r1 和r2 為均勻分布於[0 ,
1]的隨機數; w 為慣性權重, 其值由下式來確
定[6 ] :
w = w max -
w max - w min
itermax
×iter · (3)
式中, w max , w min分別是w 的最大值和最小值;
iter ,itermax分別是當前迭代次數和最大迭代次數·
2. 2 粒子群優化演算法的學習策略
由標准粒子群優化演算法可知,粒子通過跟蹤
自己迄今為止所找到的最優解和種群迄今為止所
找到最優解這兩個極值來更新自己的速度,從而
更新自己的位置·這種行為也可以理解為,粒子在
借鑒自身和整個群體所取得的成功經驗,通過對
以往的成功經驗的學習獲得有用的信息,指導自
己下一步的行動策略·但人們也常說「失敗乃成功
之母」「, 吃一塹,長一智」,可見從一些失敗的嘗試
中也可以獲得有用的信息,基於這一點,提出了新
的粒子群優化演算法學習策略,這就是從以往的失
敗中獲得有價值的信息,使粒子遠離粒子本身和
整個群體所找到的最差的位置,從而更新粒子的
速度和位置·粒子在搜索過程中的失敗可以表現
為搜索到的具有較差適應值的位置,記第i 個粒
子迄今為止搜索到的最差位置為si = ( si1 , si2 ,
⋯, sin) ,整個粒子群迄今為止搜索到的最差位置
為sg = ( sg1 , sg2 , ⋯, sg n) ,則第i 個粒子的速度和
位置更新公式如下:
v ( t +1)
id = w v ( t)
id + c1 r1 x ( t)
id - s ( t)
id +
c2 r2 x ( t)
id - s ( t)
gd , (4)
x ( t +1)
id = x ( t)
id + v ( t +1)
id · (5)
如果只是利用上述的位置和速度更新公式更
新粒子,也就是說只是從失敗中獲取經驗,這與實
際經驗不符·一般來說,還是更多地從成功的經歷
中獲取信息,而從失敗的經歷中獲得相對少的信
息,基於這一點本文的演算法同時從成功和失敗的
經歷中獲取信息來更新粒子·
2. 3 動態雙種群粒子群優化演算法
由上面的敘述可以知道粒子群中的粒子可以
按照不同的學習策略進行學習,對速度和位置作
出更新·所以本文將一個種群分成兩個子種群,每
個子種群選用不同的學習策略,即第一個子種群
中的粒子選用從成功經歷中獲得學習信息的策
略,更新自己;第二個子種群中的粒子選用從失敗
的經歷中獲得學習信息的策略進行進化·本文可
以設置一個比例系數ρ來控制兩個子種群中粒
子的個數·
ρ =
m1
m2
, m1 + m2 = m · (6)
式中, m 為粒子群中的粒子總數; m1 為第一個子
種群中的粒子個數; m2 為第二個子種群中的粒
子個數·
為了使每個粒子都能從自身和群體的經歷中
獲得充分的學習, 本文規定兩個子種群中的粒子
是不斷變化的, 即每隔一定的代數後將整個種群
按照比例系數ρ重新隨機劃分成兩個子種群·從
粒子群優化演算法的進化過程中知道在優化的初期
粒子的位置比較分散, 得到較優值和較差值的機
會相差不多,所以此時採用上述兩種不同學習策
略的粒子的個數應大致相等·在優化搜索的後期
粒子將聚集在最優值的附近,這時將很難出現比
歷史最差值更差的值了,第二個子種群將從失敗
經歷中得不到太多的有價值的信息·此時第二個
子種群中的粒子數應該遠遠小於第一個子種群中
的粒子個數,直至完全採用跟蹤最優值來更新粒
子,即第二個子種群消亡·基於上述原因將ρ設
為一個線性變化的量,其值由下式確定:
ρ = ρmax -
ρmax - ρmin
018 ×itermax
×iterc · (7)
式中,ρmax和ρmin分別是ρ的最大值和最小值;
iterc 和itermax分別是種群重新劃分時的進化代數
和最大進化代數·
動態雙種群粒子群優化演算法的實現步驟如
下:
(1) 設PSO 種群規模為m , 加速常數為c1
和c2 ,慣性權重的最大值和最小值為w max , w min ,
比例系數ρ的最大值和最小值為ρmax ,ρmin ,種群
重新劃分代數iterc ,最大進化代數為Tmax·將當前
進化代數置為t = 1 ;
(2) 在解空間中初始化粒子的速度和位置;
(3) 將種群按照比例系數ρ劃分為兩個子種
群;
(4) 按式(3) 更新慣性權重w , 按式(7) 更新
比例系數ρ, 第一個子種群按式(1) 和(2) 更新粒
子速度和位置,第二個子種群按式(4) 和(5) 更新
子種群中的粒子,從而產生新種群Xt ;
(5) 評價種群Xt·將第i 個粒子當前點適應
值與該粒子迄今找到的最優位置pi (最差位置
si) 的適應值進行比較, 若更優(差) , 則更新pi
( si) ,否則保持pi ( si) 不變,再與種群迄今找到的
最優位置pg (最差位置sg) 的適應值進行比較,若
更優(差) ,則更新pg ( sg) ;否則保持pg ( sg) 不變;
(6) 檢查是否滿足尋優結束條件, 若滿足則
結束尋優, 求出最優解; 否則, 置t = t + 1 , 轉至
(3) ;結束條件為尋優達到最大進化代數Tmax·
2. 4 基於動態雙種群粒子群優化演算法的工序排序
2. 4. 1 粒子的編碼和解碼
根據第1 節對柔性工作車間調度問題的描
述,本文定義所有工件的總工序數L = 6n
j =1
nj ,把
一個粒子表示為一個L 維的向量·對所有工序進
行連續編號,即為每道工序指定一個固定的編號·
例如可以對表1 所給出的例子中的工序進行編
號,如表2 所示,則粒子的位置向量x [ L ]就是由
一組連續的自然數組成的L 維的向量,自然數的
順序決定了工序調度的順序·xi = [1 ,7 ,2 ,4 ,8 ,3 ,
5 ,6 ]就表示了一個滿足優先約束的可行的工序排
序·
表2 工序編號
Table 2 Serial numbers of operations
工序O1 ,1 O2 ,1 O3 ,1 O1 ,2 O2 ,2 O3 ,2 O1 ,3 O2 ,3
編號1 2 3 4 5 6 7 8
2. 4. 2 位置向量和速度向量的更新
對每個粒子, 粒子的速度向量可以用v [ L ]
表示·按照上面所述的更新公式對x [ L ] , v [ L ]
進行更新·由於粒子群優化演算法經常用在連續空
間上,而柔性工作車間調度問題為整數規劃問題
而且有工序先後順序約束,所以將粒子群演算法用
於柔性工作車間調度問題時,在速度和位置更新
方式上要做如下的修改:令粒子i 的當前的位置
為xi = [1 , 7 , 2 , 4 , 8 , 3 , 5 , 6 ] , 在經過一次迭代以
後位置向量變為xi = [ 2. 5 , 6. 7 , 3. 6 , 5. 9 , 8. 5 ,
112 ,4. 1 ,7. 6 ]·位置向量里存放的是工序的編號,
很明顯不能為小數, 本文對迭代後的位置向量進
行如下的處理:將更新後的位置向量中各分量的
值按照由小到大的順序進行排列, 並為其進行重
新編號:1. 2 (1) < 2. 5 (2) < 3. 6 (3) < 4. 1 (4) < 5. 9
(5) < 6. 7 (6) < 7. 6 (7) < 8. 5 (8) ,式中括弧內的數
字為該分量的編號, 然後位置向量中各分量用其
獲得的相應的編號代替·例如,第一個分量2. 5 用
編號2 代替,第二個分量6. 7 用編號6 代替等等,
此時位置向量變為xi = [2 , 6 , 3 , 5 , 8 , 1 , 4 , 7 ]·但
是這個工序排序不滿足優先約束,還要對其進行
調整,使其滿足約束條件·例如第一個分量2 代表
的是工序O21 ,第6 個分量1 代表的是工序O11 ,
工序O21應在工序O11之後進行加工, 所以要對
其進行調整·調整的方法為:對屬於同一個工件的
工序調換其相應先後位置使其滿足約束, 對每個
工件都做相似的處理, 則可以得到滿足優先順序約
束的位置向量: xi = [1 ,4 ,2 ,5 ,7 ,3 ,6 ,8 ]·
3 啟發式分配演算法
通過上一節介紹的排序演算法本文可以獲得一
個滿足工序優先約束的可行的工序序列·這一節
通過一個啟發式演算法為這一工序序列中的每一工
序分配一台合適的機器對其進行加工·
本文所採用的分配演算法的主要思想是:選擇
一台能使本道工序獲得最小完工時間的機器分配
給待加工的工序·可以用如下公式表示選擇機器
Mk 分配給待加工的工序以使本道工序的完工時
間最短:
tf i , j = min k ( ri , j + Ti , j , k) ,
ri , j = max ( rpfk , ropf) ·
式中, tf i , j 為工序Oi , j 的完工時間; ri , j 為工序的
開始加工時間; Ti , j , k為工序用機器k 加工消耗的
時間; rpfk為機器Mk 當前狀態下所加工的最後一
個工件的完工時間; ropf為待加工工序緊前工序的
完工時間·
利用排序演算法和分配演算法就可以獲得一個滿
足優先約束和資源約束的可行的調度方案, 並且
利用分配演算法還可以得到目標函數———全部工件
的最大完工時間的值·
將前面介紹的排序演算法和分配演算法綜合起來
便形成本文所採用的處理柔性工作車間調度優化
問題的方法,記為DPSO2HA·該方法將柔性工作
車間調度問題分解為兩個子問題———排序問題和
分配問題,在每一次迭代中首先通過動態雙種群
粒子群演算法獲得一個可行的工序序列, 然後利用
分配演算法給該序列分配合適的機器並計算目標函
數值,直至達到最大進化代數·
4 算例模擬
4. 1 模擬研究1
本文選用文獻[ 7 ]中的一個10 ×10 (10 個工
件,10 台機器) ,30 道工序的柔性工作車間調度問
題來計算最大完工時間·實驗參數如下:粒子群的
種群規模為m = 30 , c1 = c2 = 2 ,ρmax = 015 ,ρmin =
0 ,每隔5 代重新劃分種群,最大迭代次數Tmax =
150·
實驗中採用本文所提出的演算法運行10 次,和
傳統的GA 方法、文獻[8 ]中採用的MSA 演算法相
比較,比較結果如表3 所示·
表3 實驗結果比較
Table 3 Comparison of te sting re sults
方 法最優值平均值標准偏差
GA 8 11. 5 2. 67
MSA 7 7. 9 0. 97
DPSO2HA 7 7. 1 0. 32
從表3 中可以看出DPSO2HA 求得的平均值
和標准偏差都明顯優於GA 和VEGA , 這說明
DPSO2HA 的精度與穩定性明顯優於GA 和
VEGA 演算法·實驗中所獲得的一個較優的調度方
案的甘特圖如圖1 所示·圖中方框內的數字「i . j」
表示第j 個工件的第i 道工序·,
（不好意思，圖粘貼不下來，要不你告我郵箱）
圖1 柔性工作車間調度優化結果
Fig. 1 Optimization solution to the problem
10 ×10 with 30 operations
4. 2 模擬研究2
為了進一步對本文提出的演算法的性能加以驗
證,選用文獻[ 9 ]中所給出的實驗數據,利用本文
提出的演算法進行求解,並將調度結果與文獻[ 9 ]及
文獻[ 10 ]中所提演算法的調度結果加以比較·比較
結果如表4 所示·
表4 不同方法的調度結果比較
Table 4 Comparison of different scheling re sults
算例描述Brandimarte GENACE DPSO2HA
MK1 10 ×6 42 41 40
MK2 10 ×6 32 29 28
MK4 15 ×8 81 67 61
MK5 15 ×4 186 176 173
MK6 10 ×15 86 68 62
MK7 20 ×5 157 148 141
MK8 20 ×10 523 523 523
MK9 20 ×10 369 328 307
MK10 20 ×15 296 231 207
由上述的比較結果可以看出,本文所提出的
DPSO2HA 方法對上述算例的求解結果較另外兩
種方法有了較大的提高·
5 結 論
本文提出了一種動態雙種群粒子群優化演算法
(DPSO) ·DPSO 將種群劃分成兩個種群規模隨進
化過程不斷變化的子種群,兩個子種群分別採用
不同的學習策略進行進化,並在進化過程中相互
交換信息·該演算法在保持PSO 演算法高效簡單的基
礎上提高了全局尋優能力·將以DPSO 演算法為基
礎的排序演算法和啟發式分配演算法相結合形成了解
決柔性工作車間調度問題的新方法·通過對算例
的研究和與其他方法的比較表明,該方法是有效
可行的·
參考文獻:
[ 1 ] Carlier J , Pinson E. An algorithm for solving the job2shop
problem[J ] . Management Science , 1989 ,35 (2) :164 - 176.
[ 2 ] Reynolds R G. An introction to cultural algorithms[ C] ‖
Proceedings of the Third Annual Conference on Evolutionary
Programming. River Edge : World Scientific , 1994 : 131 -
139.
[ 3 ] Mastrolilli M , Gambardella L M. Effective neighborhood
functions for the flexible job shop problem[ J ] . Journal of
Scheling , 2002 ,3 (1) :3 - 20.
[ 4 ] Kacem I , Hammadi S , Borne P. Pareto2optimality approach
for flexible job2shop scheling problems : hybridization of
evolutionary algorithms and fuzzy logic[J ] . Mathematics and
Computers in Simulation , 2002 ,60 (3) :245 - 276.
[ 5 ] Kennedy J , Eberhart R. Particle swarm optimization [ C] ‖
Proceedings of IEEE International Conference on Neural
Networks. Perth : IEEE Press , 1995 :1942 - 1948.
[ 6 ] Shi Y, Eberhart R C. Empirical study of particle swarm
optimization [ C ] ‖Proceedings of the 1999 Congress on
Evolutionary Computation. Washington , 1999 : 1945 -
1950.
[ 7 ] Xia WJ , Wu Z M. An effective hybrid optimization approach
for multi2objective flexible job2shop scheling problems[J ] .
Computers & Inst rial Engineering , 2005 ,48 (2) :409 -
425.
[ 8 ] Najid N M , Stephane D P , Zaidat A. A modified simulated
annealing method for flexible job shop scheling problem[C]
‖Proceedings of the IEEE International Conference on
Systems , Man and Cybernetics. Hammamet : IEEE Press ,
2002 :89 - 94.
[ 9 ] Brandimarte P. Routing and scheling in a flexible job shop
by tabu search[J ] . A nnals of Operations Research , 1993 ,41
(3) :158 - 183.
[ 10 ] Ho N B , Tay J C. GENACE: an efficient cultural algorithm
for solving the flexible job2shop problem[C] ‖Proceedings of
the IEEE Congress on Evolutionary Computation. Portland :
IEEE Press , 2004 :1759 - 1766.

（do you know）

『叄』 粒子群演算法的引言

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

『肆』 【PSO-LSTM】基於PSO優化LSTM網路的電力負荷預測（Python代碼實現）

PSOLSTM模型是基於粒子群優化演算法優化長短期記憶網路參數，用於電力負荷預測的一種有效方法。以下是其Python代碼實現的核心要點：

1. 導入必要的庫：

   • 需要導入如numpy、pandas用於數據處理，tensorflow或keras用於構建LSTM網路，以及sklearn中的評估函數等。

2. 數據預處理：

   • 載入電力負荷數據，並進行歸一化、劃分訓練集和測試集等操作。

3. 構建LSTM網路：

   • 使用keras.Sequential構建LSTM模型，設置輸入層、LSTM層、全連接層和輸出層。
   • LSTM層的神經元數量、學習率等作為待優化的參數。

4. 定義PSO演算法：

   • 實現粒子群優化演算法，包括初始化粒子位置、速度，以及適應度函數。
   • 通過迭代更新粒子的位置和速度，尋找最優的LSTM超參數。

5. 訓練LSTM網路：

   • 使用PSO找到的最優超參數訓練LSTM網路。
   • 記錄訓練過程中的損失值和准確率等指標。

6. 預測與評估：

   • 使用訓練好的LSTM網路對測試集進行預測。
   • 計算並輸出預測結果的誤差指標。

7. 可視化結果：

   • 可視化實際負荷與預測負荷的對比圖，以及PSO優化過程中的適應度值變化圖等。

由於具體的Python代碼實現涉及較多細節和庫函數調用，這里不給出完整的代碼示例。但可以根據上述步驟，結合tensorflow、keras和sklearn等庫的文檔，逐步編寫代碼實現PSOLSTM模型。同時，可以參考相關文獻和開源項目中的代碼，以獲取更具體的實現細節和技巧。