粒子群優化算法及其改進(1)

标準粒子群優化算法

算法原理

PSO算法思想來源于仿生學的社會認知理論，展現了群智能的特性–即簡單的智能個體通過合作産生出複雜的智能行為。目前，PSO算法可以歸納為三個過程，即評價、比較和學習。

• 評價過程~對粒子目前所處的階段進行評價，通常是按照特定的适應度函數來評價自身适應度的好壞。類比自然界中有機生命的行為，就是有機生命通過評估周圍各種環境激勵對自身産生的影響完成對周圍環境的學習。
• 比較過程~指粒子群中的粒子與其他的粒子進行适應度值的比較，以确定學習的方向和動機。
• 學習過程~粒子通過對自身的評價以及同周圍其他粒子的比較産生出模拟其他粒子的行為。

通過這三個過程的有機結合，粒子群優化算法可以适應各種複雜多變的環境，用以解決一些困難的優化問題。

數學模型

在連續空間中，PSO算法的具體描述如下所示：

設 M 是粒子群的種群規模，決策空間有n維，那麼粒子 i 在時刻t在坐标中的位置就可以表示為 Xti=(xti1,xti2,⋯,xtim),i=1,2,⋯,M ，粒子 i 的速度就是每次疊代過程中的位移，用Vti=(vti1,vti2,⋯,vtim)來表示，粒子 i 在時刻t的第 d(d=1,2,3⋯) 維空間中的速度和位置按照如下公式更新：

vtid=wvt−1id+c1r1(pid−xt−1id)+c2r2(gd−xt−1id)xtid=xt−1id+vtidvtid={vmax−vmaxvtid>vmaxvtid<−vmax

• w 是慣性權值，用來表示粒子對原來速度的保持程度。
• c1是加速因子，用來表示粒子跟蹤自身曆史最優值的系數。
• c2 也是加速因子，用來表示目前粒子對全局最優的粒子學習程度的系數。
• r1 , r2 是在 [0,1] 範圍内的兩個随機數。
• p 是目前粒子的曆史最優值。
• g是全局粒子的曆史最優值。

其中 vt−1id 為粒子帶第 t−1 次疊代的速度，也就是上一次疊代後的速度。 W 是慣性權值，慣性權值的設定是為了影響粒子的局部搜尋能力與全局搜尋能力的均衡。主要表示上一代的速度對這一代的速度産生的影響，慣性權值w越大，那麼表示上一代的速度對目前影響較大，粒子将很大程度的沿着自身上一代的速度移動。如果慣性權值很小，那麼表明粒子受上一代的影響很小，粒子将很大程度的沿着自身學習的速度移動。第二部分 (ptid−xidt) 是粒子對自身的認識，也叫做“認知”部分，可以引導粒子向自身的曆史最佳位置移動。是以說這個模型可以不斷地促使粒子減小誤差。第三部分 (ptg−xtid) 稱為“社會知識”，也簡稱做“社會”部分。“社會”部分是粒子群中的個體互相合作的提現，每個粒子通過共享資訊來引導群體中的所有粒子都像全局最優解靠近。

适應度函數

為了評價目前狀态的優越性需要構造一個适應度函數 f(x) ， f(x) 用來表示目前狀态的好壞。

算法的實作

import random
import copy

birds=int(input('Enter count of bird: '))
xcount=int(input('Enter count of x: '))
pos=[]
speed=[]
bestpos=[]
birdsbestpos=[]
w=
c1= 
c2=
r1=
r2=
for i in range(birds):
    pos.append([])
    speed.append([])
    bestpos.append([])

def GenerateRandVec(list):
    for i in range(xcount):
        list.append(random.randrange(,))

def CalDis(list):
    dis=
    for i in list:
        dis+=i**
    return dis

for i in range(birds):          #initial all birds' pos,speed
    GenerateRandVec(pos[i])
    GenerateRandVec(speed[i])
    bestpos[i]=copy.deepcopy(pos[i])

def FindBirdsMostPos():
    best=CalDis(bestpos[])
    index=
    for i in range(birds):
        temp=CalDis(bestpos[i])
        if temp<best:
            best=temp
            index=i
    return bestpos[index]

birdsbestpos=FindBirdsMostPos()   #initial birdsbestpos

def NumMulVec(num,list):         #result is in list
    for i in range(len(list)):
        list[i]*=num
    return list

def VecSubVec(list1,list2):   #result is in list1
    for i in range(len(list1)):
        list1[i]-=list2[i]
    return list1

def VecAddVec(list1,list2):      #result is in list1
    for i in range(len(list1)):
        list1[i]+=list2[i]
    return list1

def UpdateSpeed():
    #global speed
    for i in range(birds):
        temp1=NumMulVec(w,speed[i][:])
        temp2=VecSubVec(bestpos[i][:],pos[i])
        temp2=NumMulVec(c1*r1,temp2[:])
        temp1=VecAddVec(temp1[:],temp2)
        temp2=VecSubVec(birdsbestpos[:],pos[i])
        temp2=NumMulVec(c2*r2,temp2[:])
        speed[i]=VecAddVec(temp1,temp2)

def UpdatePos():
    global bestpos,birdsbestpos
    for i in range(birds):
        VecAddVec(pos[i],speed[i])
        if CalDis(pos[i])<CalDis(bestpos[i]):
            bestpos[i]=copy.deepcopy(pos[i])
    birdsbestpos=FindBirdsMostPos()

for i in range():
    #print birdsbestpos
    #print (CalDis(birdsbestpos))
    print (birdsbestpos)
    UpdateSpeed()
    UpdatePos()
input()
           

算法的優缺點

标準粒子群優化算法具有的優點：

• 初始化時限制較少，對問題資訊幾乎沒有什麼依賴。
• 算法的記憶能力，存儲最優解的能力較強。
• 算法的原理簡單，實作起來比較容易。
• 有着很強的群智能算法的特性，粒子群的個體間之共享資訊，有利于搜尋的進行。

标準粒子群優化算法具有的缺點：

• 算法的收斂速度過快，導緻局部搜尋能力不強，直接導緻搜尋精度不高。
• 無法保證做到全局搜尋，經常在某個局部最優收斂。
• 參數的選擇對算法的性能影響較大，很難調整到最适宜的參數。

通過大量的研究與實驗證明，标準粒子群算法存在的主要問題就是容易陷入局部最優。是以實際使用中标準粒子群優化算法很少單獨出現，通常是與其他智能算法混合改進以後才使用的。