粒子群アルゴリズムの原理とC++コードの例
9495 ワード
本ブログはオリジナルブログで、許可を得ずに転載してはいけません!仲間たちが別の場所で見ているなら、csdnで見てみることをお勧めします(原文リンク先はhttp://blog.csdn.net/bettarwang/article/details/12179995)、結局csdnでコードや質問、議論を見るのが便利です.
粒子群最適化アルゴリズム(PSO)は進化計算技術(evolutionarycomputation)であり,1995年にEberhart博士とkennedy博士によって提案され,鳥群捕食の挙動研究に由来する.このアルゴリズムは最初に飛鳥クラスタ活動の法則性に啓発され,さらに集団知能を利用して構築された簡略化モデルである.粒子群アルゴリズムは動物クラスタの活動挙動の観察に基づいて,集団中の個体による情報の共有を利用して集団全体の運動を問題解空間において無秩序から秩序への進化過程を生じさせ,最適解を得た.
PSOは遺伝的アルゴリズムと類似しており,反復に基づく最適化アルゴリズムである.システムはランダム解のセットに初期化され、反復によって最適値を検索します.しかし遺伝アルゴリズム用のクロス(crossover)や変異(mutation)ではなく,粒子が解空間で最適な粒子に追随して探索する.遺伝的アルゴリズムと比較して,PSOの利点は簡単で容易に実現でき,多くのパラメータを調整する必要がないことである.粒子群アルゴリズムは連続空間問題を解くために多く用いられ,離散空間問題の応用は少ない.
粒子群アルゴリズムでは,各個体を1つの粒子と呼び,粒子は問題を解く潜在的に可能な解であり,粒子種群はいくつかの粒子からなる.粒子群アルゴリズムの基本原理は,粒子種群が探索空間を一定の速度で飛行し,各粒子が探索する際に,自分が探索した履歴最適位置と種群内の他の粒子の履歴最適位置を考慮し,これに基づいて位置の変化を行うことである.
下図は粒子群飛躍の概略図である.
クラスタの最適な位置間の距離で速度を更新します.そして粒子は式(2−3)に従って新しい位置に飛ぶ.粒子群アルゴリズムのフローチャートを図2-2に示す.
現在国内外の多くの学者は基本粒子群最適化アルゴリズムの各パラメータとトポロジー構造]から研究に着手し,パラメータの設定と構造の変化によってアルゴリズムの性能を改善することを試みている.慣性因子wは平衡アルゴリズムのグローバル探索能力と局所探索能力の役割を果たす.小さい慣性因子w(w<0.8)はアルゴリズムの局所探索能力を強くすることができる.大きな慣性因子w(w>1.2)はアルゴリズムに強いグローバル探索能力をもたらす.従って、通常慣性因子wは定数値ではなく、反復グラデーションに伴う数値である.反復初期慣性因子wの値が大きく、アルゴリズムに強いグローバル検索能力を持たせ、解空間全体で実行可能な解を検索する.慣性因子wは反復代数の増加に伴って徐々に減少し,アルゴリズムが反復後期に局所探索能力を増強してグローバル探索能力を弱め,探索された最適解への収束を加速させる.慣性因子wのグラデーション式は、通常、以下のようになる.
RatnaweeraらはPSOアルゴリズムの性能に及ぼす可変学習因子の影響を研究し,c 1とc 2を定義した.
下:
次に、40*40の平面直角座標領域において、点(10,20)に最も近い点を探す例を説明する.
まず、新しいクラスを作成します.ソースファイルはCoordinateです.h
実行結果01:
実行結果02:
実行結果03:
実行結果04:
実行結果05:
結論:以上の結果から,最適化が進むにつれて,見出されたクラスタの最も利点の誤差が急速に減少していることが明らかになった.これにより粒子群アルゴリズムの有効性を実証した.
読者は、慣性因子、学習因子などのパラメータを変更し、最適化プロセスに及ぼす影響を観察することを試みることができる.
粒子群最適化アルゴリズム(PSO)は進化計算技術(evolutionarycomputation)であり,1995年にEberhart博士とkennedy博士によって提案され,鳥群捕食の挙動研究に由来する.このアルゴリズムは最初に飛鳥クラスタ活動の法則性に啓発され,さらに集団知能を利用して構築された簡略化モデルである.粒子群アルゴリズムは動物クラスタの活動挙動の観察に基づいて,集団中の個体による情報の共有を利用して集団全体の運動を問題解空間において無秩序から秩序への進化過程を生じさせ,最適解を得た.
PSOは遺伝的アルゴリズムと類似しており,反復に基づく最適化アルゴリズムである.システムはランダム解のセットに初期化され、反復によって最適値を検索します.しかし遺伝アルゴリズム用のクロス(crossover)や変異(mutation)ではなく,粒子が解空間で最適な粒子に追随して探索する.遺伝的アルゴリズムと比較して,PSOの利点は簡単で容易に実現でき,多くのパラメータを調整する必要がないことである.粒子群アルゴリズムは連続空間問題を解くために多く用いられ,離散空間問題の応用は少ない.
粒子群アルゴリズムでは,各個体を1つの粒子と呼び,粒子は問題を解く潜在的に可能な解であり,粒子種群はいくつかの粒子からなる.粒子群アルゴリズムの基本原理は,粒子種群が探索空間を一定の速度で飛行し,各粒子が探索する際に,自分が探索した履歴最適位置と種群内の他の粒子の履歴最適位置を考慮し,これに基づいて位置の変化を行うことである.
下図は粒子群飛躍の概略図である.
クラスタの最適な位置間の距離で速度を更新します.そして粒子は式(2−3)に従って新しい位置に飛ぶ.粒子群アルゴリズムのフローチャートを図2-2に示す.
現在国内外の多くの学者は基本粒子群最適化アルゴリズムの各パラメータとトポロジー構造]から研究に着手し,パラメータの設定と構造の変化によってアルゴリズムの性能を改善することを試みている.慣性因子wは平衡アルゴリズムのグローバル探索能力と局所探索能力の役割を果たす.小さい慣性因子w(w<0.8)はアルゴリズムの局所探索能力を強くすることができる.大きな慣性因子w(w>1.2)はアルゴリズムに強いグローバル探索能力をもたらす.従って、通常慣性因子wは定数値ではなく、反復グラデーションに伴う数値である.反復初期慣性因子wの値が大きく、アルゴリズムに強いグローバル検索能力を持たせ、解空間全体で実行可能な解を検索する.慣性因子wは反復代数の増加に伴って徐々に減少し,アルゴリズムが反復後期に局所探索能力を増強してグローバル探索能力を弱め,探索された最適解への収束を加速させる.慣性因子wのグラデーション式は、通常、以下のようになる.
RatnaweeraらはPSOアルゴリズムの性能に及ぼす可変学習因子の影響を研究し,c 1とc 2を定義した.
下:
次に、40*40の平面直角座標領域において、点(10,20)に最も近い点を探す例を説明する.
まず、新しいクラスを作成します.ソースファイルはCoordinateです.h
#ifndef COORDINATE_H
#define COORDINATE_H
class Coordinate
{
public:
float x;
float y;
Coordinate();
Coordinate(float x,float y);
};
#endif
以下は対応するCoordinateである.cppファイル.#include "stdafx.h"
#include "Coordinate.h"
using namespace std;
Coordinate::Coordinate()
{
x=0.0f;
y=.0f;
}
Coordinate::Coordinate(float x,float y)
{
this->x=x;
this->y=y;
}
は次に、粒子クラスの定義である.ソースファイルはParticle.h. #ifndef PARTICLE_H
#define PARTICLE_H
#include "Coordinate.h"
#include
#include
using namespace std;
class Particle
{
friend ostream& operator<
以下は対応するParticleである.cppファイル.#include "stdafx.h"
#include "Particle.h"
#include
#include
using namespace std;
float Particle::Xmax=30.0f; // , , 1e-006 , 1e-009 。 , 。
float Particle::Xmin=0.0f;
float Particle::Ymax=30.0f;
float Particle::Ymin=0.0f;
float Particle::Vxmax=Xmax-Xmin; // Vmax=Xmax-Xmin;
float Particle::Vxmin=0-Vxmax;
float Particle::Vymax=Ymax-Ymin;
float Particle::Vymin=0-Vymax;
float Particle::c1=2.0f;
float Particle::c2=2.0f;
Particle::Particle(float x,float y)
{
c.x=x;
c.y=y;
//p=100.0f; // ( )。
p=pow(c.x-10.0f,2)+pow(c.y-20.0f,2);
Vx=(Xmax-Xmin)/8.0f; ////////////////////// , , Vmax/8.0f, Vmax=Xmax-Xmin=30-0=30; , , 。 , , (Xmax-Xmin)/8.0f 。
Vy=(Xmax-Xmin)/8.0f;
/// pBest
pBest.x=x;
pBest.y=y;
}
void Particle::setP() // p , pBest , setPBest() 。
{
float temp=pow(c.x-10.0f,2)+pow(c.y-20.0f,2);
if(tempVxmax)
Vx=Vxmax;
else if(VxVxmax)
Vy=Vxmax;
else if(VyXmax)
c.x=Xmax;
else if(c.xYmax)
c.y=Ymax;
else if(c.ygetX()<getY()<
の下にmainファイルがあります.#include "stdafx.h"
#include "Particle.h"
#include // sprintf 。
#include
#include
#include
#include
#include
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
Particle*p[40];
float w;// wmax=1.2f; wmin=0.5;
Particle*temp;
float randX,randY;
srand((int)time(NULL));
for(int i=0;i<40;++i)
{
randX=(rand()/(float)RAND_MAX)*30.0f;
randY=(rand()/(float)RAND_MAX)*30.0f;
cout<getX()<getY()<getP();
gBest=p[0]->getPBest();
for(int i=1;i<40;++i)
{
if(p[i]->getP()getP();
gBest=p[i]->getPBest();
bestIndex=i;
}
}
///////////////////////////////////
cout<getX()<getY()<getX()<getY()<getP()<setV(gBest,w);
temp->setCoordinate();
temp->setP();
sprintf(buf,"coordinate%d.dat",i);
temp->outputFile(buf);
}
bestP=p[0]->getP();
gBest=p[0]->getPBest();
for(int i=1;i<40;++i)
{
temp=p[i];
if(temp->getP()getP();
gBest=temp->getPBest();
bestIndex=i;
}
/*
if((pow(gBest.x-10,2)+pow(gBest.y-20,2))<0.00001f)
{
cout<getP()<
実行後の結果は(実行結果が長いため、代表的な結果画像をいくつか選択しただけですが、最適化のプロセスがわかります.読者は自分で実行して結果を表示できます):実行結果01:
実行結果02:
実行結果03:
実行結果04:
実行結果05:
結論:以上の結果から,最適化が進むにつれて,見出されたクラスタの最も利点の誤差が急速に減少していることが明らかになった.これにより粒子群アルゴリズムの有効性を実証した.
読者は、慣性因子、学習因子などのパラメータを変更し、最適化プロセスに及ぼす影響を観察することを試みることができる.