パーティクルクラスタアルゴリズムpython実装
4108 ワード
1、概要
粒子群アルゴリズムは最適化アルゴリズムとして多くの分野で応用されている.最適化とは、私の理解は一つの問題に対して十分な解を求めることであり、現在の最適化アルゴリズムには蟻群アルゴリズム、遺伝アルゴリズムなどがたくさんあります.粒子群アルゴリズムはこれらのアルゴリズムに比べてより簡単で,収束速度が速い.
2、アルゴリズムの説明
最適化問題の例を挙げると、求める最小値は、もちろん、ベクトルの場合の最小値が0であることを数学的手段で求めることができるが、より複雑な関数式にとって、数学的手段を用いて解くことは複雑であり、実際の応用では、必ずしもその正確な解を要求するものではなく、十分な精度を満たす正確な解であれば十分である.この場合,一定の最適化アルゴリズムで解くと便利である.
粒子群アルゴリズムの思想は実際の生活の中で鳥が捕食する過程に由来する.1つのn次元の空間の中で、1群の鳥(m匹)が捕食していると仮定し、食べ物はn次元の空間のある点に位置し、i番目の鳥のある時点では、2つのベクトル記述があり、1つは鳥の位置ベクトルであり、2つ目は鳥の速度(i=1,2...m)である.鳥が位置の良し悪しを判断できると仮定すると、「良し悪し」とは、食べ物に近いのか遠いのか.鳥は捕食の過程で自分の経験と鳥の群れの中の他の鳥の位置によって自分の速度を決定して、現在の位置と速度によって、次の瞬間の位置を得ることができて、このようにすべての鳥は自分と鳥の群れに学ぶことを通じて絶えず自分の速度の位置を更新して、最終的に食べ物を見つけて、あるいは食べ物に十分近い点を見つけることができます.更新速度と位置の式は次のとおりです.
更新速度:
対応するpythonは次のように実現されます.
探索空間鳥群における鳥の個数が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
粒子群アルゴリズムは最適化アルゴリズムとして多くの分野で応用されている.最適化とは、私の理解は一つの問題に対して十分な解を求めることであり、現在の最適化アルゴリズムには蟻群アルゴリズム、遺伝アルゴリズムなどがたくさんあります.粒子群アルゴリズムはこれらのアルゴリズムに比べてより簡単で,収束速度が速い.
2、アルゴリズムの説明
最適化問題の例を挙げると、求める最小値は、もちろん、ベクトルの場合の最小値が0であることを数学的手段で求めることができるが、より複雑な関数式にとって、数学的手段を用いて解くことは複雑であり、実際の応用では、必ずしもその正確な解を要求するものではなく、十分な精度を満たす正確な解であれば十分である.この場合,一定の最適化アルゴリズムで解くと便利である.
粒子群アルゴリズムの思想は実際の生活の中で鳥が捕食する過程に由来する.1つのn次元の空間の中で、1群の鳥(m匹)が捕食していると仮定し、食べ物はn次元の空間のある点に位置し、i番目の鳥のある時点では、2つのベクトル記述があり、1つは鳥の位置ベクトルであり、2つ目は鳥の速度(i=1,2...m)である.鳥が位置の良し悪しを判断できると仮定すると、「良し悪し」とは、食べ物に近いのか遠いのか.鳥は捕食の過程で自分の経験と鳥の群れの中の他の鳥の位置によって自分の速度を決定して、現在の位置と速度によって、次の瞬間の位置を得ることができて、このようにすべての鳥は自分と鳥の群れに学ぶことを通じて絶えず自分の速度の位置を更新して、最終的に食べ物を見つけて、あるいは食べ物に十分近い点を見つけることができます.更新速度と位置の式は次のとおりです.
更新速度:
対応する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
探索空間鳥群における鳥の個数が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