(C++ソースコード、詳細な注釈)pso粒子群アルゴリズムのパラメータ調整技術と改善方法
15254 ワード
粒子群アルゴリズムのパラメータ調整技術と改善方法
C++ソースコード実装
1基本粒子群アルゴリズムの簡単な紹介
1.1粒子群アルゴリズム(Particle Swarm Optimization,PSO)は典型的な集団知能アルゴリズムである.最初はアメリカの心理学者Eberhartと電気技師Kennedyが1995年に提案した鳥類集団の餌探し行為をシミュレートする擬生知能計算方法である.鳥の群れは全体の捜索の過程の中で、互いにそれぞれの情報を伝達することを通じて、他の鳥に自分の位置を知らせて、同時に最も良い解の情報を全体の鳥の群れに伝達して、最終的に、全体の鳥の群れはすべて食べ物の源の周囲に集まることができて、つまり私達の言った最も良い解を見つけて、つまり問題は収束します.各鳥は、次の更新位置と速度の根拠として、自分の歴史的最適位置、鳥群のグローバル最適位置をリアルタイムで記録します.
1.2利点:簡単で実現しやすく、パラメータが少なく、改善しやすく、初期位置に対する耐性が弱く、時間複雑度が低い
1.3標準PSOアルゴリズムの流れ:(本ブログ、ソースコード実装付)
ステップ1:粒子群の位置と速度(クラスタ規模N)をランダムに初期化する.
ステップ2:各パーティクルの適応度を計算します.
ステップ3:各粒子について、その適応値を通過した最適位置pbestと比較し、現在の値がより良い場合はpbest(履歴最適)を更新する.
ステップ4:各粒子について、その適応値を通過する最良の位置gbestと比較し、現在の値がより良い場合はgbest(グローバル最適)を更新する.
手順5:パーティクルの速度と位置を調整します.
ステップ6:終了条件を満たし、終了;そうでない場合は、2)に進みます.
2調整参加改善の概要
多くの論文を見て、現在の学術界で粒子群アルゴリズムの性能を高めるには主に以下の3つの方法がある.
2.1合理的な設定基本パラメータ:(本ブログ、ソースコード付)
(1)クラスタ規模amoutの設定:モデル複雑度に応じて定義
(2)慣性重みw,加速係数c 1,c 2の設定:w範囲0.7-0.9,c 1=c 2=(1-w)/2
(3)最大速度係数V_scale:0.05-0.15の範囲
(4)アニーリング思想(学習率が徐々に減少):種群規模N,Vmax,wの前期設定が大きく,後期が徐々に小さくなり,前期はグローバル探索に偏り最適解の漏れを回避し,後期は局所探索に偏り収束速度を向上させる.
2.2トポロジーの使用(このブログ、ソースコード付)
Global Topology Global Topology:フルコネクション(標準パーティクルクラスタアルゴリズム)
ローカルトポロジ:リングトポロジ、フォンノイマン、四クラスタ構造
メリットとデメリット:
グローバルトポロジー構造は速度が速いが、早熟になりやすく、局所的に最適に陥る.
局所トポロジーの収束速度が遅く、グローバル検索の能力が強い.
通常,フォンノイマン,四クラスタ構造の総合性能が優れている.
2.3他のインテリジェント最適化アルゴリズムとの連携(ソースコード実装、後続ブログ参照)
1粒子群アルゴリズムはタブー探索と併用される:局所的な陥没を早期に回避できる(シミュレーション速度と最適化構造は4クラスタ構造に似ている).
2粒子群アルゴリズムとPCA主成分分析を併用:収束速度を大幅に向上させることができる(パラメータ間に強い相関がある場合に使用するとより良い効果がある);
3粒子群と勾配降下を併用:収束速度を向上させることができる;
4遺伝子アルゴリズムの変異因子を粒子群に導入する:すべての粒子が局所に陥り停滞した後、変異因子が局所から飛び出してシミュレーションを継続することができる.
など
3.C++ソースファイル3.1 Pso_singleクラス:単一粒子の基本情報とメソッド関数、粒子の位置、適応値、各重みと係数、速度位置の更新方法、適応値計算方法などを含む.所在文.3件:SinglePso.cpp、SinglePso.h;
3.2 Psoクラス:複数のPsoを含むsingleオブジェクトは、粒子群を構成します.係数アニーリング法、gbest計算法、粒子群初期化、更新などが含まれる.所在書類:Pso.cpp、Pso.h;
3.3 Pso_Topクラス:Psoクラスから継承されます.3種類の局所top構造(環状トポロジー,フォンノイマン,四クラスタ構造)を実現した.所在するファイル:top.cpp、top.h;
3.4ツール関数:適応値関数、ランダム配列生成関数、粒子群優劣比較関数など.ファイル:funs.cpp、funs.h;
3.5主関数:main.cpp
4.ソース4.1 SinglePso.h
4.3 Pso.h
4.4 Pso.cpp
4.5 top.h
4.6 top.cpp
4.7 funs.h
4.8 funs.cpp
4.9 main.cpp
C++ソースコード実装
1基本粒子群アルゴリズムの簡単な紹介
1.1粒子群アルゴリズム(Particle Swarm Optimization,PSO)は典型的な集団知能アルゴリズムである.最初はアメリカの心理学者Eberhartと電気技師Kennedyが1995年に提案した鳥類集団の餌探し行為をシミュレートする擬生知能計算方法である.鳥の群れは全体の捜索の過程の中で、互いにそれぞれの情報を伝達することを通じて、他の鳥に自分の位置を知らせて、同時に最も良い解の情報を全体の鳥の群れに伝達して、最終的に、全体の鳥の群れはすべて食べ物の源の周囲に集まることができて、つまり私達の言った最も良い解を見つけて、つまり問題は収束します.各鳥は、次の更新位置と速度の根拠として、自分の歴史的最適位置、鳥群のグローバル最適位置をリアルタイムで記録します.
1.2利点:簡単で実現しやすく、パラメータが少なく、改善しやすく、初期位置に対する耐性が弱く、時間複雑度が低い
1.3標準PSOアルゴリズムの流れ:(本ブログ、ソースコード実装付)
ステップ1:粒子群の位置と速度(クラスタ規模N)をランダムに初期化する.
ステップ2:各パーティクルの適応度を計算します.
ステップ3:各粒子について、その適応値を通過した最適位置pbestと比較し、現在の値がより良い場合はpbest(履歴最適)を更新する.
ステップ4:各粒子について、その適応値を通過する最良の位置gbestと比較し、現在の値がより良い場合はgbest(グローバル最適)を更新する.
手順5:パーティクルの速度と位置を調整します.
ステップ6:終了条件を満たし、終了;そうでない場合は、2)に進みます.
2調整参加改善の概要
多くの論文を見て、現在の学術界で粒子群アルゴリズムの性能を高めるには主に以下の3つの方法がある.
2.1合理的な設定基本パラメータ:(本ブログ、ソースコード付)
(1)クラスタ規模amoutの設定:モデル複雑度に応じて定義
(2)慣性重みw,加速係数c 1,c 2の設定:w範囲0.7-0.9,c 1=c 2=(1-w)/2
(3)最大速度係数V_scale:0.05-0.15の範囲
(4)アニーリング思想(学習率が徐々に減少):種群規模N,Vmax,wの前期設定が大きく,後期が徐々に小さくなり,前期はグローバル探索に偏り最適解の漏れを回避し,後期は局所探索に偏り収束速度を向上させる.
2.2トポロジーの使用(このブログ、ソースコード付)
Global Topology Global Topology:フルコネクション(標準パーティクルクラスタアルゴリズム)
ローカルトポロジ:リングトポロジ、フォンノイマン、四クラスタ構造
メリットとデメリット:
グローバルトポロジー構造は速度が速いが、早熟になりやすく、局所的に最適に陥る.
局所トポロジーの収束速度が遅く、グローバル検索の能力が強い.
通常,フォンノイマン,四クラスタ構造の総合性能が優れている.
2.3他のインテリジェント最適化アルゴリズムとの連携(ソースコード実装、後続ブログ参照)
1粒子群アルゴリズムはタブー探索と併用される:局所的な陥没を早期に回避できる(シミュレーション速度と最適化構造は4クラスタ構造に似ている).
2粒子群アルゴリズムとPCA主成分分析を併用:収束速度を大幅に向上させることができる(パラメータ間に強い相関がある場合に使用するとより良い効果がある);
3粒子群と勾配降下を併用:収束速度を向上させることができる;
4遺伝子アルゴリズムの変異因子を粒子群に導入する:すべての粒子が局所に陥り停滞した後、変異因子が局所から飛び出してシミュレーションを継続することができる.
など
3.C++ソースファイル3.1 Pso_singleクラス:単一粒子の基本情報とメソッド関数、粒子の位置、適応値、各重みと係数、速度位置の更新方法、適応値計算方法などを含む.所在文.3件:SinglePso.cpp、SinglePso.h;
3.2 Psoクラス:複数のPsoを含むsingleオブジェクトは、粒子群を構成します.係数アニーリング法、gbest計算法、粒子群初期化、更新などが含まれる.所在書類:Pso.cpp、Pso.h;
3.3 Pso_Topクラス:Psoクラスから継承されます.3種類の局所top構造(環状トポロジー,フォンノイマン,四クラスタ構造)を実現した.所在するファイル:top.cpp、top.h;
3.4ツール関数:適応値関数、ランダム配列生成関数、粒子群優劣比較関数など.ファイル:funs.cpp、funs.h;
3.5主関数:main.cpp
4.ソース4.1 SinglePso.h
#ifndef SINGLEPSO_H_INCLUDED
#define SINGLEPSO_H_INCLUDED
/*
Pso_single: ;
, :
:in_dims, , , , , ,
, , , , , ,
: 、 、 、
*/
class Pso_single
{
private:
int in_dims; //
float *in_max, *in_min; //
float *v_max,*v_min; //
float w,c1,c2; // , 、
public:
float *v_; //
float fitness_; //
float *in_; //
float fitness_pbest; //
float *in_pbest; //
float fitness_gbest; //
float *in_gbest; //
//Pso_single:
Pso_single(int in_dims_,float *inmax, float *inmin, float *vmax, float *vmin,float w_,float c1_,float c2_);
//init_:
void init_();
//get_fitness:
void get_fitness();
//init_pbest:
void init_pbest();
//updata_pbest:
void updata_pbest();
//get_gbest:
void get_gbest(float *in_gbest_,float fitness_gbest_);
//updata_v::
void updata_v();
//updata_in:
void updata_in();
};
#endif // SINGLEPSO_H_INCLUDED
4.2 SinglePso.cpp #include
#include
#include"SinglePso.h"
#include"funs.hpp"
using namespace std;
Pso_single::Pso_single(int in_dims_,float *inmax, float *inmin, float *vmax, float *vmin,float w_,float c1_,float c2_)
{
in_dims = in_dims_; //
fitness_ = 0.0; //
in_ = new float [in_dims]; //
v_ = new float [in_dims]; //
fitness_pbest = 0.0 ; //
in_pbest = new float [in_dims]; //
fitness_gbest = 0.0; //
in_gbest = new float [in_dims]; //
in_max = inmax; //
in_min = inmin; //
v_max = vmax; //
v_min = vmin; //
w = w_; // ,
c1 = c1_; //
c2 = c2_; //
}
void Pso_single::init_()
{ //
in_ = random_array(in_dims,in_max,in_min);
//
v_ = random_array(in_dims,v_max,v_min);
}
void Pso_single::get_fitness()
{
//
fitness_ = fitness_fun(in_);
}
void Pso_single::init_pbest()
{
// ,
copy_(in_,in_pbest,in_dims);
fitness_pbest = fitness_;
}
void Pso_single::updata_pbest()
{ // pbest,
if (fitness_<=fitness_pbest)
copy_(in_,in_pbest,in_dims);
fitness_pbest = fitness_;
}
void Pso_single::get_gbest(float *in_gbest_,float fitness_gbest_)
{ // ,
// ,
// 。 。
copy_(in_gbest_,in_gbest,in_dims);
fitness_gbest = fitness_gbest_;
}
void Pso_single::updata_v(){
//
//v=v*w + (pbestin-in)*c1 + (gbestin-in)*c2
// 、
for(int i = 0;iv_max[i])
{v_[i] = v_max[i];}
if (v_[i]in_max[i])
{in_[i] = in_max[i];}
if (in_[i]
4.3 Pso.h
#ifndef PSO_H_INCLUDED
#define PSO_H_INCLUDED
#include "SinglePso.h"
#include
using namespace std;
/*
Pso :
: Single_pso, 、
*/
class Pso
{
protected:
int swarm_amount; //
int in_dim; //
float w,c1,c2; //
float* max_in; //
float* min_in; //
float* max_v; //
float* min_v; //
float* fitness_list; //
float v_scale = 0.1; // 。 0.05 vector_pso; //
public:
float* in_gbest_final; //
float fitness_gbest_final; //
//Pso:
Pso(int swarm_amount_,int in_dim_,float w_,float* max_,float* min_,float v_scale_);
//set_w_col:
void set_w_col(float w_col);
//set_v_col:
void set_v_col(float v_col);
//gbest: gbest
void gbest(int flag);
//initialize: 、 、 、 、 、
void initialize();
//update: 、 、 、 、 、
void update();
//gone: 。circle_
void gone(int circle_);
};
#endif // PSO_H_INCLUDED
4.4 Pso.cpp
#include
#include
#include
#include
#include
#include "Pso.h"
#include"funs.hpp"
using namespace std;
// :
Pso::Pso(int swarm_amount_,int in_dim_,float w_,float* max_,float* min_,float v_scale_)
{
in_gbest_final = new float[in_dim];
swarm_amount = swarm_amount_;
fitness_list = new float[swarm_amount];
in_dim = in_dim_;
w = w_;
c1 = (1-w)/2;
c2 = (1-w)/2;
min_in = new float[in_dim];
max_in = new float[in_dim];
min_v = new float[in_dim];
max_v = new float[in_dim];
max_in = max_;
min_in = min_;
v_scale = v_scale_;
for(int i = 0; iinitialize();
for (int i = 0; iupdate();
}
//get_final_gbest:
get_final_gbest(swarm_amount,vector_pso,in_gbest_final,&fitness_gbest_final,in_dim);
}
4.5 top.h
#ifndef TOP_H_INCLUDED
#define TOP_H_INCLUDED
#include
#include
#include "Pso.h"
using namespace std;
/*
Pso_Top :
Pso , top 。
*/
class Pso_Top : public Pso
{
private:
int top_flag = 0; //
public:
//Pso_Top:
Pso_Top(int swarm_amount_,int in_dim_,float w_,float* max_,float* min_,float v_scale_):Pso(swarm_amount_,in_dim_,w_,max_,min_,v_scale_)
{
}
//set_topFlag: top
void set_topFlag(int topFlag);
//gbest:
void gbest(int init_flag);
};
#endif // TOP_H_INCLUDED
4.6 top.cpp
#include
//#include
#include
#include
#include
//#include
#include "top.h"
#include"funs.hpp"
using namespace std;
void Pso_Top::set_topFlag(int topFlag)
{
top_flag = topFlag;
}
/*top_index_0: top ,
top_index_1: top ,
top_index_2: , 4 , ; */
// top
void top_index_0(int i_ ,int size_v,int* index_v)
{
index_v[0] = (i_+size_v-1)%size_v;
index_v[1] = i_;
index_v[2] = (i_+1)%size_v;
}
//get_row_col:top_index_1 。
// : ,
int get_row_col(int num_)
{
int row = 0;
for(int i=1; i<=sqrt(num_); i++)
{
if (num_%i==0)
{
row = i;
}
}
return row;
}
//get_index:top_index_1 。
// : 、 、 、 。
//(i,j) = (-1,0)
//(i,j) = (1,0)
//(i,j) = (0,-1)
//(i,j) = (0,1)
int get_index(int row,int col,int row_curr,int col_curr,int i,int j)
{
return ((row_curr+i+row)%row)*col + ((col_curr+j+col)%col);
}
//
void top_index_1(int i_ ,int size_v,int* index_v)
{
int row,col,row_curr,col_curr;
row = get_row_col(size_v);
col = size_v/row;
row_curr = i_/col;
col_curr = i_%col;
index_v[0] = get_index(row,col,row_curr,col_curr,-1,0);//
index_v[1] = get_index(row,col,row_curr,col_curr,1,0);//
index_v[2] = i_;//
index_v[3] = get_index(row,col,row_curr,col_curr,0,-1);//
index_v[4] = get_index(row,col,row_curr,col_curr,0,11);;//
}
// : 4 , ;
int top_index_2(int group_id ,int swarm_id)
{
/*
: group-i-k i k ; group-1-0, 1 0 ;
group_index_0 :group-0 0、1、2 group-1-0,group-2-1,
group-3-2 ;group_index_1,group_index_2,group_index_3 。
*/
int group_index_0[3][2] = {{1,0},{2,1},{3,2}};
int group_index_1[3][2] = {{0,0},{3,1},{2,0}};
int group_index_2[3][2] = {{1,2},{0,1},{3,0}};
int group_index_3[3][2] = {{2,2},{1,1},{0,2}};
switch(group_id)
{
case 0:
return group_index_0[swarm_id][0]*4 + group_index_0[swarm_id][1];
break;
case 1:
return group_index_1[swarm_id][0]*4 + group_index_0[swarm_id][1];
break;
case 2:
return group_index_2[swarm_id][0]*4 + group_index_0[swarm_id][1];
break;
case 3:
return group_index_3[swarm_id][0]*4 + group_index_0[swarm_id][1];
break;
};
}
void Pso_Top::gbest(int init_flag)
{
float* in_gbest_temp = new float[in_dim];
float fitness_gbest_temp;
int* index_;
if (top_flag < 2)
{
// top_flag = 0:
// top_flag = 1:
for(int i=0; i vector_local; // ,
for(int j = 0; j vector_local; // ,
for(int j = 0; j
4.7 funs.h
#ifndef FUNS_HPP_INCLUDED
#define FUNS_HPP_INCLUDED
#include
#include "SinglePso.h"
using namespace std;
//random_single: 0-1
float random_single();
//random_array: dims
float* random_array(int dims,float *max_, float *min_);
//fitness_fun:
float fitness_fun(float* in_);
//copy_:
void copy_(float src[],float dst[],int dims);
//get_max: ,
void get_min(int mount,vector temp_pso,float* max_in,float* max_fit,int in_dims_);
//get_max: ,
void get_final_gbest(int mount,vector temp_pso,float* final_in,float* final_fit,int in_dims_);
#endif // FUNS_HPP_INCLUDED
4.8 funs.cpp
#include
#include
#include
#include
#include
#include "SinglePso.h"
#include "funs.hpp"
#define PI 3.1415926
using namespace std;
// 0——1
float random_single()
{
return ((float)(rand()%1000))/1000.0;
}
// dims
float* random_array(int dims,float *max_,float *min_)
{
float *temp = new float[dims];
for(int i=0; i temp_pso,float* min_in,float* min_fit,int in_dims_)
{
for(int i=0; i temp_pso,float* final_in,float* final_fit,int in_dims_)
{
for(int i=0; i
4.9 main.cpp
#include
#include
#include
#include
#include
#include "SinglePso.h"
#include "Pso.h"
#include "funs.hpp"
#include "top.h"
using namespace std;
int main()
{
srand(time(0)); //
int amout_ = 400; //
float w_ = 0.8; //
// , c1、 c2 , (1-w)/2
float v_scale_ = 0.1; // 。 、
int circle_ = 80 ;//
// 。 、
int in_dims_ = 2; // 2
float max_in[] = {5.0,5.0}; //
float min_in[] = {-5.0,-5.0}; //
Pso_Top pso_(amout_,2,0.8,max_in,min_in,v_scale_); // , top
// top , 12
// , 4 12
pso_.set_topFlag(2); // top {0: ;1: ; 2: }
/*
top 。
:
Pso pso_(amout_,2,0.8,max_in,min_in,v_scale_);
*/
pso_.set_w_col(0.99); // 。 0.99。c1 c2
pso_.set_v_col(0.99); // 。 。
pso_.gone(circle_); //
cout<