粒子群算法python实现

来源:岁月联盟 编辑:exp 时间:2012-09-06

1、 概述

粒子群算法作为一种优化算法,在很多领域都有应用。所谓优化,我的理解是对一个问题求出它足够好的解,目前的优化算法有很多,如蚁群算法、遗传算法等。粒子群算法相对于这些算法来说,它更简单,而且有很快的收敛速度。

2、 算法描述

举一个优化问题的例子,若求的最小值,当然可以通过数学手段求出当向量时的最小值为0 ,但是对于更复杂的函数表达式来说,运用数学手段求解是复杂的,而且在实际应用中,并不一定要求出它的精确解,只要是满足足够精度的精确解就够了,这时通过一定的优化算法求解就很方便。

粒子群算法思想来源于实际生活中鸟捕食的过程。假设在一个n维的空间中,有一群鸟(m只)在捕食,食物位于n维空间的某个点上,对于第i只鸟某一时刻来说,有两个向量描述,一个是鸟的位置向量,第二个是鸟的速度(i=1,2...m)。假设鸟能够判断一个位置的好坏,所谓“好坏”,就是离食物更近了还是更远了。鸟在捕食的过程中会根据自己的经验以及鸟群中的其他鸟的位置决定自己的速度,根据当前的位置和速度,可以得到下一刻的位置,这样每只鸟通过向自己和鸟群学习不断的更新自己的速度位置,最终找到食物,或者离食物足够近的点。更新速度和位置的表达式如下。

更新速度:


对应的python实现如下:

[python] 
import random 
import copy 
 
birds=int(raw_input('Enter count of bird: ')) 
xcount=int(raw_input('Enter count of x: ')) 
pos=[] 
speed=[] 
bestpos=[] 
birdsbestpos=[] 
w=0.8 
c1=2  
c2=2 
r1=0.6 
r2=0.3 
for i in range(birds): 
    pos.append([]) 
    speed.append([]) 
    bestpos.append([]) 
 
def GenerateRandVec(list): 
    for i in range(xcount): 
        list.append(random.randrange(1,100)) 
         
def CalDis(list): 
    dis=0.0 
    for i in list: 
        dis+=i**2 
    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[0]) 
    index=0 
    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(100): 
    #print birdsbestpos 
    print CalDis(birdsbestpos) 
    UpdateSpeed() 
    UpdatePos() 
                 
 
raw_input() 

若搜索空间鸟群中鸟的个数为30,问题规模x的个数为5个,100次迭代运行的结果如下,可以看到最终的值已经非常接近0这个最优解了。
Enter count of bird: 30

Enter count of x: 5

6300.0

6300.0

5286.56

253.7792

253.7792

169.750784

169.750784

29.27174656

29.27174656

14.3572668416

14.3572668416

10.7095755489

10.7095755489

10.4166336974

10.4166336974

10.3952346067

10.3952346067

10.38162211

10.38162211

10.38162211

10.38162211

10.38162211

10.38162211

10.3816078435

10.3816078435

10.3815990193

10.3815990193

10.3815990193

10.3815990193

10.3815990193

10.3815990193

10.3815990038

8.61600314002

6.75814610104

0.697031173541

0.697031173541

0.586257672539

0.319653330666

0.308201304448

0.277551198357

0.152964935388

0.11330877896

0.0897094795931

0.0849797134585

0.0824510053969

0.0824510053969

0.0817642679444

0.0293278926344

0.0101946030255

0.0101946030255

0.00880640894843

0.00517872172034

0.00517872172034

0.00517872172034

0.00517872172034

0.00517872172034

0.00514217487311

0.00511832820187

0.00510609755302

0.00510609755302

0.00510609755302

0.0039233096712

0.00319253923712

0.00142224947992

0.000847531318472

0.000682710187325

0.000126289737569

0.000126289737569

0.000109415873528

0.000109415873528

0.000106080598721

0.000106080598721

0.000105801137376

0.000105801137376

0.000105654750511

0.000105654750511

0.000105654750511

0.000105654750511

0.000105654750511

0.000105654750511

0.000105653808938

0.000105653808938

0.000105653808938

7.63547737464e-05

2.56599311271e-05

6.88805040513e-06

6.88805040513e-06

2.93943099726e-07

2.93943099726e-07

2.93943099726e-07

1.65997040259e-07

1.49983822855e-07

1.45620647032e-07

1.30809105417e-07

1.30631326401e-07

1.29726054702e-07

1.2360770395e-07

1.2360770395e-07

1.2360770395e-07

1.23467030689e-07

 

 

图片内容