精品久久久久久人妻,91色花堂,韩国一区二区午夜久久

粒子群算法概述

粒子群算法(Particle Swarm Optimization)是由鳥群捕食得到啟發(fā)的一種算法，在鳥類覓食過程中，每只鳥都會利用自身經(jīng)驗和群體信息來尋找食物。在覓食過程中，每只鳥僅僅追蹤有限數(shù)量的鄰居，但是最終整個鳥群好像在某個中心的控制下飛行。這一現(xiàn)象說明復雜的全局行為可以由簡單規(guī)則的相互作用形成，其表現(xiàn)取決于群體搜索策略和群體之間的信息交換。

PSO基本原理

根據(jù)上面現(xiàn)象進行抽象，PSO算法是一種在 $n$ 維搜索空間中(搜索空間可能是解空間，也可能是問題空間，取決于如何對需要求解的問題進行編碼)，用由 $m$ 個粒子組成的種群通過一定的搜索策略進行位置更新，從而尋找搜索空間中適應度最佳值的算法。

在這個過程中，每個粒子的位置代表優(yōu)化問題的一個解(大多數(shù)情況下是可行解)。適應度函數(shù)是和優(yōu)化問題的目標函數(shù)直接相關的，它通常是針對具體問題進行具體設計，從而幫助算法收斂到最優(yōu)解。

我們將上面所述的種群記做 $X=(x_0,x_1,...,x_i,...,x_m-1)$ ，其中第 $i$ 個粒子的位置為 $x_i=(x_{i0},x_{i1},...,x_{in-1})$ ，速度為 $v_i=(v_{i1},v_{i2},...,v_{in})$ 。粒子 $i$ 的個體最佳適應度值為 $P_i=(p_{i0},p_{i1},...,p_{in-1})$ ，所屬鄰域的全局最佳適應度為 $P_g=(p_{g0},p_{g1},...,p_{gn-1})$ 。

粒子的位置和速度以迭代的方式進行如下更新：
$v_{id}^{k+1}=\omega v_{id}^k+c_1\xi (p_{id}^k-x_{id}^k)+c_2\eta (p_{gd}^k-x_{id}^k) \\x_{id}^{k+1}=x_{id}^k+v_{id}^{k+1}$
其中各參數(shù)說明如下：

$v_i^k$ 是粒子 $i$ 在第 $k$ 步迭代時的速度， $v_{id}^k$ 是 $v_i^k$ 在第 $d$ 維的速度分量；
$x_i^k$ 是粒子 $i$ 在第 $k$ 步迭代的位置， $x_{id}^k$ 是 $x_i^k$ 第 $d$ 維的位置分量；
$p_i^k$ 是粒子 $i$ 在第 $k$ 步迭代時的個體最佳適應度對應位置；
$p_g^k$ 是粒子 $i$ 在第 $k$ 步迭代時的所屬鄰域最佳適應度對應位置；
$\omega$ 稱為慣性權重，它體現(xiàn)了粒子繼承原有速度的多少，在一定范圍內(nèi)，慣性越大，則粒子受原有速度影響越大，受當前環(huán)境影響越小，表現(xiàn)為粒子具有更多的發(fā)散性，算法的全局搜索能力更好；慣性越小，則粒子受到當前環(huán)境影響越大，表現(xiàn)為粒子的收斂性強，局部搜索能力更佳；
$c_1、c_2$ 為加速度常數(shù)， $c_1$ 體現(xiàn)了粒子對于自身經(jīng)驗的信任情況， $c_2$ 體現(xiàn)了粒子對于鄰域內(nèi)其他個體傳遞信息的信任情況；
$\xi、\eta$ 是[0,1]之間的隨機數(shù)，服從均勻分布；

需要注意的是速度更新的每一步中，對 $v_i$ 的每一個分量都會進行一次取隨機數(shù)，因此移動的方向并非嚴格是自身速度、向自身最佳歷史位置和向鄰域最佳歷史位置的組合，而是在一個區(qū)域內(nèi)的近似，如下圖所示：

1-PSO searching move

上面的更新方程體現(xiàn)了粒子群算法的一些基本性質(zhì)：

在搜索過程中，粒子有三種方式調(diào)整自身的速度：沿著之前的方向；根據(jù)自身經(jīng)驗改變方向；根據(jù)鄰域內(nèi)其他粒子傳遞的信息改變方向；而 $\omega、c_1、c_2$ 三個參數(shù)反應了對這三種方式的權重分配；
粒子群中的粒子具有一定記憶特性和對環(huán)境的感知，這是通過記錄自身的最佳適應度對應位置和鄰域內(nèi)粒子的最佳適應度對應位置來實現(xiàn)的，這種個體之間的記憶和信息的交流共享是群體智能算法的重要特性。

基本PSO的改進

基本粒子群的一些問題

標準的粒子群算法存在的主要問題(大部分也是群體進化計算的共性問題)為：

初始化過程是隨機的，部分粒子位置不佳，在搜索過程中沒有有利作用。這樣雖然可以保證初始種群的粒子在搜索空間內(nèi)分布比較均勻，但是由于沒有利用問題的先驗信息，部分粒子遠離最優(yōu)解所在區(qū)域，在一定程度上影響到算法效率和解的質(zhì)量；
在高維復雜問題中，容易陷入“早熟”。也就是由于搜索空間較大，種群在還未找到全局最優(yōu)解時便已經(jīng)聚集到一起，從而收斂。早熟的收斂點有可能是局部最優(yōu)，也有可能是局部最優(yōu)鄰域中的某個點。也就是說，早熟的情況下，算法甚至不能保證收斂到局部最優(yōu)，這極大影響了算法的實用性；
超參數(shù)的選定比較困難。例如對于速度的設定，如果速度過大，前期搜索速度會很快，但是容易錯過最優(yōu)解(類似于梯度下降中步長過大的情況)；而速度設定過小則會導致搜索效率低，收斂慢，同樣難以應用；

收斂速度改進

對于粒子群算法來說，收斂速度主要由粒子的飛行速度決定，而飛行速度由 $\omega、c_1、c_2$ 三個超參數(shù)決定，因此對收斂速度的改進也就集中在對這三個超參數(shù)的選擇和更新策略上。

對于 $\omega$ ，如前所述，較大的 $\omega$ 有利于全局搜索，而較小值則對局部搜索有利，常用的慣性權重值介于0.8與1.2之間。在搜索前期，我們通常需要進行大規(guī)模的全局搜索，而在后期則是在最優(yōu)解鄰域內(nèi)對解進行fine tune，根據(jù)這個特點，現(xiàn)在比較常用的 $\omega$ 更新策略是線性權值遞減策略(Linearly Decreasing Weight, LDW)，即在搜索開始時采用較大的權值，而隨著搜索過程進行對權值進行遞減，從而滿足我們前面說的期望。

線性權值遞減的權值更新策略如下：
$\omega^k=\frac{(\omega_{ini}-\omega_{end})(k_{max}-k)}{k_{max}}+w_{end}$
其中， $w_{ini}$ 為權重初始值， $w_{end}$ 為權重最終值。 $k_{max}$ 為最大迭代步數(shù)， $k$ 為當前迭代步數(shù)。一個比較常用的默認參數(shù)是選擇 $\omega_{ini}=0.9, \omega_{end}=0.4$ 。采用線性權值遞減默認參數(shù)，得到的權值變化圖如下：

對于加速度常數(shù) $c_1,c_2$ 來說，通常是對具體問題進行一系列的實驗來選取最優(yōu)值。目前還沒有研究結果能在事先給出“最優(yōu)”的參數(shù)選取。一種常用的經(jīng)驗方法是在起始時先讓 $c_1=c_2$ 。

族群多樣性改進

對于隨機優(yōu)化算法的性能來說，族群的多樣性是非常重要的：

為了盡最大可能找到全局最優(yōu)解，我們總是希望在計算開始時，粒子能夠在搜索空間內(nèi)盡可能均勻發(fā)散的分布；而隨著計算的進行，粒子逐漸聚集，最終達到收斂；
在另一方面，族群多樣性會影響到收斂速度，如果族群非常分散，那么其收斂速度通常會比較慢。

對于族群多樣性的改進一般有兩種方法：改進拓撲結構（也就是粒子之間相互連接的方式）和設計保持種群多樣化策略。

拓撲結構的改進

粒子群算法在鄰域中共享信息，而鄰域是由拓撲結構定義的，因此不同的拓撲結構決定了信息在粒子之間傳遞的速度。下圖展示了一些常見的鄰域拓撲結構：

3-Neighborhood topology

當鄰域結構是全連接(Fully connected)時，對于任意粒子來說，整個種群都是它的鄰居，這種情況下的PSO也叫做全局版本；當鄰域結構是其他拓撲結構時，對于一個粒子，只有在拓撲結構上與其直接相連的粒子才是它的鄰居，這種情況下的PSO也叫做局部版本。

除了固定的拓撲結構以外，也有學者提出用動態(tài)拓撲結構來改變種群中信息的流動速度；還可以引入聚類的思想，用聚類后的簇中心粒子位置來替代粒子自身最優(yōu)解位置，用全局的簇中心位置來替代全局最優(yōu)解位置。

種群多樣化策略

在粒子群算法中，隨著迭代的進行，種群逐漸收斂到一點，也就喪失了進化的動力，如果收斂時機過早，就會影響到找到的解的質(zhì)量。為了保持種群的多樣性，研究者設計了一系列的策略，下面列出幾個比較有名的：

Clerc提出了no-hope/re-hope策略，在迭代過程中對種群進行no-hope檢驗，如果發(fā)現(xiàn)種群進化動力喪失，就進入re-hope過程，讓種群重新在搜索空間中分散開，防止陷入局部最優(yōu)；
Xie提出了一種耗散粒子群優(yōu)化算法，通過施加噪聲擾動，為系統(tǒng)引入負熵，從而為種群保留不斷進化的動力；
Thiemo等提出了一種粒子空間擴展策略，為每個粒子賦予一個半徑值，以檢測是否發(fā)生碰撞，當兩個粒子發(fā)生碰撞時，讓它們彈開，以保持種群的多樣性；
...

融合其他算法思想

單一算法的搜索策略和脫離局部最優(yōu)的能力是有限的，因此智能算法常常會選擇融合其他算法的機制來增加尋優(yōu)能力。

微分進化思想、遺傳算法、多種群協(xié)作和競爭思想、混沌搜索、免疫算法和模擬退火等等算法和思想都可以融合進PSO中。

PSO算法流程

標準PSO的流程可以用下面的流程圖表示：

4-PSO flowchart

離散粒子群算法(Discrete PSO)

在求解VRP類問題，或者擴大到離散優(yōu)化和組合優(yōu)化問題時，我們首先需要注意PSO的編碼問題。

原始的PSO采用實數(shù)編碼，對于速度計算、位置更新等非常方便而自然，但是對于離散優(yōu)化和組合優(yōu)化問題，有時實數(shù)編碼難以直接應用，這就需要應用二進制編碼(Binary encoding)或者排列編碼(Permutation encoding)，對于非實數(shù)編碼，需要重新定義距離、速度、位置的含義和相應操作。

從連續(xù)到離散 -- 操作的重定義

粒子群算法中的抽象操作

回顧基本的粒子群算法，在整個搜索過程中，我們涉及的抽象操作有以下幾種：

粒子的速度計算：位置-位置 -> 速度
速度的標量乘：標量*速度 -> 速度
速度和：速度+速度 -> 速度
粒子的位置更新：位置+速度 -> 位置

此外還有粒子的評價，但是由于評價涉及到粒子的解碼，是具體問題具體設計的，并不具有通用性，因此無法進行抽象層面的定義。

PSO求解VRP問題的排列編碼

對于有 $N$ 個顧客的VRP問題，這里采用排列編碼，即粒子的位置 $X(x_0,x_1,...,x_{n-1})$ 用0到 $N-1$ 的整數(shù)排列來表示。

例如對一個包含5個顧客的問題來說，一個可能的粒子位置為 $X=(0,2,1,3,4)$ 。

操作的定義

這里參考Clerc在用PSO求解TSP問題中定義的操作：

粒子速度的定義

對于排列編碼，其搜索空間為所有可能的排列。為了進行不同排列的探索，速度定義為對排列的一系列交換。

設 $\|v\|$ 為速度的長度(即交換的次數(shù))， $XO(x_i,x_j)$ 定義為對 $x_i,x_j$ 兩數(shù)進行一次交換，那么速度可以定義為：
$v=(XO_0,XO_1,...,XO_{\|v\|-1})$
一個空的速度定義為 $\empty$ ，也就是空集。

定義 $\urcorner XO(x_i,x_j)=XO(x_j,x_i)$ ，則負速度 $\urcorner v$ 可以定義為：
$\urcorner v=(\urcorner XO_0, \urcorner XO_1,..., \urcorner XO_{\|v\|-1})$
粒子的位置更新

明確了位置和速度的含義之后，就可以很容易的對粒子的位置進行更新了。

假設在某個時刻，一個長度為5的粒子的位置為 $X=(0,3,1,4,2)$ ，速度為 $v=((2,3),(1,3))$ ，那么可以得到：
$X'=X+v=(0,2,1,4,3)+((1,3))=(0,2,3,4,1)$
需要注意的是，對于 $v'=((1,3),(2,3))$ ，我們可以得到同樣的 $X'=X+v'$ ，這也就是說 $v$ 和 $v'$ 是等效的。

粒子的速度計算

粒子的速度通過兩個位置的差得到，也就是說從兩個位置 $X_1,X_2$ ，我們可以計算出 $v=X_2-X_1$ 使得 $X_1+v=X_2$ 。如前所述，給定的兩個位置并不能得到唯一的速度 $v$ ，因此我們需要設計一些算法來求得速度。

一個可行的算法是“換位減”，對于有 $N$ 個顧客的VRP問題，“換位減”的步驟如下：

1. 初始化i=0，v為空集
2. 如果i=N，跳轉(zhuǎn)到步驟4，否則進入步驟3
3. 比較X1和X2，如果在第i個位置上 X1[i] = X2[i]，設定i=i+1，跳轉(zhuǎn)到步驟2；如果 X1[i] != X2[i]，則交換X2中的元素X1[i]和X2[i]，設定i=i+1，將(X1[i],X2[i])加入v，轉(zhuǎn)入步驟2
4. 算法結束，輸出速度

下圖給出了一個計算過程的示例：

5-position minus

最終我們得到速度 $V=X_1-X_2=((0,1),(1,4))$

速度的標量積

速度 $v$ 乘以一個標量 $c$ 得到的仍然是速度。這里的標量有幾種可能性：

$c=0$ ，此時 $cv=\empty$ ；
$c\in(0,1]$ ，令 $\|cv\|=\lfloor c\|v\| \rfloor$ ，從 $v$ 中取前 $\|cv\|$ 個分量；即 $cv=(XO_0,XO_1,...,XO_{\|cv\|-1})$ ；
$c>1$ ，那么 $c$ 可以拆分為一個不大于 $c$ 的整數(shù) $c_N$ 和一個 $[0,1)$ 之間的小數(shù) $c_f$ ，即 $c=c_N+c_f$ ，此時 $cv=(c_N+c_f)v=c_Nv+c_fv$ ，第二部分的計算同上，第一部分則是對 $v$ 的重復 -- $c_Nv=v+v+v+...+v$ ，也即重復 $c_N$ 次 $v$ ；
$c<0$ ，則 $cv=(-c)\urcorner v$ ，也就是對常數(shù)取負，得到一個正系數(shù)，然后乘以負速度；

這樣就完整定義了速度的數(shù)乘。

速度和

兩個速度的和定義為兩個速度中交換操作的有順序的并集。例如 $v_1=((1,3),(1,2)),v_2=((2,3),(3,4))$ ，那么有：
$v_1+v_2=((1,3),(1,2),(2,3),(3,4))$
這里需要注意的是 $v_1+v_2\ne v_2+v_1$ ，也就是速度求和并不具備交換性。

時間復雜度分析

對于優(yōu)化算法來說，時間復雜度是一個重要的問題。如果時間復雜度過高，算法的可擴展性就較差，對于大規(guī)模問題很可能不能適用。

假設PSO算法的種群規(guī)模為 $P$ ，迭代次數(shù)為 $K$ ，問題規(guī)模為 $N$ 。我們可以先對單個粒子上的操作進行時間復雜度分析，然后擴展到整個種群。

對于單個粒子，各個操作的復雜度如下：

適應度評價：對于VRP問題來說，我們需要對每個個體的路徑長度進行加總，其復雜度為 $O(N)$ ；
選擇個體歷史最優(yōu)和鄰域歷史最優(yōu)位置：復雜度為 $O(1)$ ；
速度計算：采用換位減的方式，需要對編碼從左向右進行一次線性掃描，其平均復雜度為 $O(N)$ ；
位置更新：復雜度和速度的長度相關，在最壞情況下速度的長度也不會超過 $O(N)$ ，因此位置更新的復雜度也是 $O(N)$ ；

因此對于單個粒子來說，一次迭代的時間復雜度和問題規(guī)模成正比，為 $O(N)$ 。

可以得到整體算法的復雜度為 $KPO(N)$ 。

用離散粒子群算法求解CVRP問題

算例介紹

本文采用的CVRP算例來自Augerat et al. 的數(shù)據(jù)集，可以到這里下載。

下面就數(shù)據(jù)結構進行說明，任意一個數(shù)據(jù)文件，例如A-n32-k5，都分為下面幾個部分:

數(shù)據(jù)信息

這部分形如：

NAME : A-n32-k5
COMMENT : (Augerat et al, Min no of trucks: 5, Optimal value: 784)
TYPE : CVRP
DIMENSION : 32
EDGE_WEIGHT_TYPE : EUC_2D 
CAPACITY : 100

給出了數(shù)據(jù)集的基本信息：

數(shù)據(jù)集名為 A-n32-k5
最小用車5輛，最優(yōu)解路徑總長度為784
類型是CVRP問題
維度，也就是節(jié)點數(shù)為32
邊的權重類型為2D的歐幾里得距離
車輛最大載重為100單位

節(jié)點坐標

NODE_COORD_SECTION 
 1 82 76
 2 96 44
 3 50 5
 4 49 8
 ...

給出了節(jié)點的編號和X，Y坐標。根據(jù)這個信息我們就可以計算兩個節(jié)點之間的二維歐幾里得距離了。

節(jié)點需求

DEMAND_SECTION 
1 0 
2 19 
3 21 
4 6 
5 19 
6 7 
...

給出了各個節(jié)點的需求量。

車庫

DEPOT_SECTION 
 1  
 -1

表明這個問題中只有一個車庫，也就是節(jié)點1。要求每條路徑從車庫出發(fā)，到車庫結束。

代碼實現(xiàn)

在這里我們用代碼實現(xiàn)一個標準的整數(shù)編碼PSO，在前面提到的數(shù)據(jù)集里選擇幾個進行測試，了解不額外增加局部搜索和脫出局部最優(yōu)機制的情況下，整數(shù)編碼PSO的性能表現(xiàn)。

代碼作為演示之用，沒有經(jīng)過性能優(yōu)化，只能作為一個參考。

速度類

對于速度，按照之前所列，我們需要實現(xiàn)標量乘、取反和加法操作，這些可以通過運算符重載做到。

# --------------------------------
# 速度類
# --------------------------------
class Velocity(object):
    """
    整數(shù)編碼下PSO的速度形如[(1,3), (2,5)]，其含義為先對1, 3節(jié)點進行交換，然后對2, 5節(jié)點進行交換
    """

    def __init__(self, exchange_list=None):
        if exchange_list is None:
            self._vel = list()  # 私有變量，保存交換對
        else:
            self._vel = exchange_list

    def __mul__(self, c: float):
        """
        重載乘法，允許浮點數(shù) c 和速度 v 相乘
        浮點數(shù)c有下面四種情況：
        1. c < 0， 此時對常數(shù)取負，得到一個正數(shù)，同時對速度也取負，轉(zhuǎn)化為正數(shù)和速度的乘法
        2. c = 0，此時得到 cv = empty set
        3. c in (0,1]，此時從v中提取前 int(c * len(v)) 個分量
        4. c > 1，此時可以拆分為一個大于1的數(shù)
        :param c: float，一個浮點數(shù)
        :return: 處理之后的速度
        """
        # 數(shù)據(jù)類型檢查
        try:
            c = float(c)
        except:
            raise ValueError('Velocity can only be multiplied with a float, not {}'.format(type(c)))
        # 進行乘法
        if c < 0.0:  #
            return -c * (-Velocity(self._vel))
        elif c == 0.0:  # 返回空速度
            return Velocity()
        elif 0 < c <= 1:  # 從前向后取v中的部分分量
            vel_len = len(self._vel)
            cnt = int(c * vel_len)
            return Velocity([self._vel[i] for i in range(cnt)])
        else:  # c > 1的情況，分成整數(shù)和小數(shù)部分進行處理
            int_part = int(c)  # 整數(shù)部分
            dec_part = c - int_part  # 小數(shù)部分
            return Velocity(int_part * self._vel) + dec_part * Velocity(self._vel)

    def __rmul__(self, c: float):
        return Velocity(self._vel) * c

    def __neg__(self):
        """
        重載取反操作
        對于Velocity([x,y],[y,z],...)來說， -Velocity = ([y,x],[z,y],...)
        :return:
        """
        return Velocity([[elem[1], elem[0]] for elem in self._vel])

    def __add__(self, other):
        """
        重載速度加法
        對于兩個速度 vel1 = [[x,y], [y,z], [z,t]]和 vel2 = [[z, x]]
        vel1 + vel2 = [[x,y], [y,z], [z,t], [z,x]]
        :param other:
        :return:
        """
        return Velocity(self._vel + other.exchange_list)

    def __repr__(self):
        return "Velocity({})".format(str(self._vel))

    @property
    def exchange_list(self):
        """
        Getter函數(shù)，取出交換對
        :return:
        """
        return self._vel

位置類

對于位置類，我們需要實現(xiàn)換位減以及和速度相加：

# --------------------------------
# 位置類
# --------------------------------
class Position(object):
    """
    整數(shù)編碼下的位置類形如[3,2,6,4,5]，它是 *所有節(jié)點* 的一個permutation
    """

    def __init__(self, seq=None):
        if seq is None:
            self._seq = list()  # 保存一個permutation，代表路徑上訪問節(jié)點的次序
        else:
            self._seq = seq

    def __sub__(self, other):
        """
        兩個Position實例進行 *換位減* ，得到一個Velocity實例
        :param other: Position實例
        :return: Velocity實例
        """
        exchange_list = list()
        if len(self._seq) != len(other.visit_sequence):
            raise Exception("Cant perform calculation for Positions with different sequence length")
        pos2_seq = list(other.visit_sequence)
        for i in range(len(self._seq)):
            elem_seq1 = self._seq[i]
            elem_seq2 = pos2_seq[i]
            if elem_seq1 != elem_seq2:  # 如果兩個position對應位置上的元素不相等
                # 找到pos2_seq中這兩個元素對應的index
                idx1, idx2 = pos2_seq.index(elem_seq1), pos2_seq.index(elem_seq2)
                # 交換兩個元素并將該操作加入velocity
                pos2_seq[idx1], pos2_seq[idx2] = pos2_seq[idx2], pos2_seq[idx1]
                exchange_list.append([elem_seq1, elem_seq2])
        return Velocity(exchange_list)

    def __add__(self, other):
        """
        Position + Velocity = Position
        也即是在permutation上應用Velocity所表示的變換
        例如Position = [1, 3, 2, 4, 5]， Velocity = [[1,3], [2,5], [3,4]]
        Position + Velocity = [4, 1, 5, 3, 2]
        :param other:
        :return: 一個Position實例
        """
        seq_new = list(self._seq)
        for elem in other.exchange_list:
            idx0, idx1 = seq_new.index(elem[0]), seq_new.index(elem[1])
            seq_new[idx0], seq_new[idx1] = seq_new[idx1], seq_new[idx0]
        return Position(seq_new)

    def __repr__(self):
        return "Position({})".format(str(self._seq))

    @property
    def visit_sequence(self):
        return self._seq

粒子類

最終粒子類除了包含一個速度實例和一個位置實例以外，還需要保存?zhèn)€體最佳位置和鄰域最佳位置：

# --------------------------------
# 粒子類
# --------------------------------
class Particle(object):
    def __init__(self, position=None, velocity=None):
        if position is None:
            self.pos = Position()
        else:
            self.pos = position  # 當前位置，一個Position實例
        if velocity is None:
            self.vel = Velocity()
        else:
            self.vel = velocity  # 當前速度，一個Velocity實例
        self.fitness = 0.0  # 當前位置對應的適應度
        self.pbest_pos = None  # 個體歷史最佳位置，Position實例
        self.pbest_fitness = float('Inf')  # 個體歷史最佳適應度
        self.gbest_pos = None  # 鄰域最佳位置，Position實例
        self.gbest_fitness = float('Inf')  # 鄰域最佳適應度
        self._dimension = utilities.problem_dimension  # 問題維度

    def __repr__(self):
        return "Particle:\n\tPosition:({})\n\tVelocity({})\n\tFitness: {}".format(str(self.pos.visit_sequence),
                                                                                  str(self.vel.exchange_list),
                                                                                  self.fitness)

    def initialize_pos(self) -> None:
        """
        初始化粒子位置
        :return:
        """
        perm = [i for i in range(2, self._dimension + 1)]
        random.shuffle(perm)
        self.pos = Position(perm)

    def __update_velocity(self, omega: float, c1: float, c2: float) -> None:
        """
        根據(jù)gbest_pos和pbest_pos更新速度
        :return:
        """
        inertia = omega * (self.pbest_pos - self.pos)
        individual_experience = (c1 * random.random()) * (self.pbest_pos - self.pos)
        social_experience = (c2 * random.random()) * (self.gbest_pos - self.pos)
        self.vel = inertia + individual_experience + social_experience

    def update_pos(self, omega: float, c1: float, c2: float):
        """
        根據(jù)速度更新粒子的位置
        :param omega:
        :param c1:
        :param c2:
        :return:
        """
        self.__update_velocity(omega, c1, c2)
        self.pos = self.pos + self.vel

算法性能測試

超參數(shù)

作為簡單測試，并沒有對超參數(shù)進行特別調(diào)優(yōu)，按照經(jīng)驗選取超參數(shù)如下：

超參數(shù)	解釋	取值
popsize	種群規(guī)模	100
$\omega_{ini}$	初始權重	0.9
$\omega_{end}$	最終權重	0.4
$c_1$	加速度常數(shù)	0.4
$c_2$	加速度常數(shù)	0.4
$N_{iter}$	迭代步數(shù)	500

測試結果

這里我選擇了4個不同點數(shù)的問題進行測試，對每個數(shù)據(jù)集，運行5次算法，下表中列出了最佳值和平均值，計算gap時使用的是5次平均結果：

數(shù)據(jù)集	已知最優(yōu)	5次最佳	5次平均	gap
A-32-K5	784	1301.521	1329.807	69.6%
A-33-K6	742	1067.427	1122.482	51.3%
A-54-K7	1167	2066.366	2172.210	86.1%
A-61-K9	1034	2008.647	2126.348	105.6%

結果討論

在所有的計算中，算法都已經(jīng)達到了收斂，對于A-32-k5數(shù)據(jù)集的一次計算中的迭代過程如下：

6-example_result_iteration_A32k5

對應的路徑圖如下：

7-example_result_routes_A32k5

可以看到，即使對于這樣一個節(jié)點數(shù)比較少的問題，從圖像上看得到的路徑也和最有路徑相去甚遠，可以看到不少的路徑交叉出現(xiàn)，這也是因為我們沒有在算法中加入opt這樣的local search機制。

總結

整數(shù)編碼的PSO提供了一套對速度和位置以及其相關運算的定義，拓展了PSO的可用范圍，看著還是比較有意思的
雖然編碼方式比較簡單，但是由于定義了一整套的相關運算，其實現(xiàn)還是相對復雜的，而且換位減的時間復雜度也比較高，從效率上并不是非常好的選擇
僅從編碼方式看，也存在一定的問題，例如說[3,2,1,4]和[4,1,2,3]，雖然在定義上是兩個不同的位置，但是實際上代表的路徑的總距離是相同的(symmetric edge的情況下)；這可能會讓解在兩個局部最優(yōu)之間擺動，盡管這兩個局部最優(yōu)實際上是同一回事
從結果上看，總體上整數(shù)編碼的PSO在不添加額外搜索機制的情況下，只能說可以用于求解，但是其相對于最優(yōu)結果的gap是較大的，也就是說單獨這套方法的實用性并不高，甚至比不上一些簡單的啟發(fā)式方法

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

CVRP問題求解（一）整數(shù)編碼的粒子群算法

CVRP問題求解（一）整數(shù)編碼的粒子群算法

粒子群算法概述

PSO基本原理

基本PSO的改進

基本粒子群的一些問題

收斂速度改進

族群多樣性改進

融合其他算法思想

PSO算法流程

離散粒子群算法(Discrete PSO)

從連續(xù)到離散 -- 操作的重定義

粒子群算法中的抽象操作

PSO求解VRP問題的排列編碼

操作的定義

時間復雜度分析

用離散粒子群算法求解CVRP問題

算例介紹

代碼實現(xiàn)

速度類

位置類

粒子類

算法性能測試

超參數(shù)

測試結果

結果討論

總結

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

CVRP問題求解（一）整數(shù)編碼的粒子群算法

粒子群算法概述

PSO基本原理

基本PSO的改進

基本粒子群的一些問題

收斂速度改進

族群多樣性改進

融合其他算法思想

PSO算法流程

離散粒子群算法(Discrete PSO)

從連續(xù)到離散 -- 操作的重定義

粒子群算法中的抽象操作

PSO求解VRP問題的排列編碼

操作的定義

時間復雜度分析

用離散粒子群算法求解CVRP問題

算例介紹

代碼實現(xiàn)

速度類

位置類

粒子類

算法性能測試

超參數(shù)

測試結果

結果討論

總結

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av