从上面的例子我们可以看到应用PSO解决优化问题的过程中有两个重要的步骤: 问题解的编码和
适应度函数
采用实数编码
不需要像遗传算法一样是二进制编码(或者采用针对实数的
遗传操作.例如对于问题 f(x) = x1^2 + x2^2+x3^2 求解, 粒子可以直接编码为 (x1, x2, x3), 而
适应度函数就是f(x). 接着我们就可以利用前面的过程去寻优.这个寻优过程是一个叠代过程, 中止条件一般为设置为达到最大循环数或者最小错误
PSO中并没有许多需要调节的参数,下面列出了这些参数以及经验设置
粒子数: 一般取 20 – 40. 其实对于大部分的问题10个粒子已经足够可以取得好的结果, 不过对于比较难的问题或者特定类别的问题, 粒子数可以取到100 或 200
粒子的长度: 这是由优化问题决定, 就是问题解的长度
粒子的范围: 由优化问题决定,每
一维可是设定不同的范围
Vmax: 最大速度,决定粒子在一个循环中最大的移动距离,通常设定为粒子的范围宽度,例如上面的例子里,粒子 (x1, x2, x3) x1 属于 [-10, 10], 那么 Vmax 的大小就是 20
学习因子: c1 和 c2 通常等于 2. 不过在文献中也有其他的取值. 但是一般 c1 等于 c2 并且范围在0和4之间
中止条件: 最大循环数以及最小错误要求. 例如, 在上面的神经网络训练例子中, 最小错误可以设定为1个错误分类, 最大循环设定为2000, 这个中止条件由具体的问题确定.
全局PSO和局部PSO: 我们介绍了两种版本的粒子群优化算法: 全局版和局部版. 前者速度快不过有时会陷入局部最优. 后者收敛速度慢一点不过很难陷入局部最优. 在实际应用中, 可以先用全局PSO找到大致的结果,再用局部PSO进行搜索.
惯性权重
另外的一个参数是惯性权重, Shi 和Eberhart指出(A modified particle swarm optimizer,1998):当Vmax很小时(对schaffer的f6函数,Vmax<=2),使用接近于1的惯性权重;当Vmax不是很小时(对schaffer的f6函数,Vmax>=3),使用权重w=0.8较好.如果没有Vmax的信息,使用0.8作为权重也是一种很好的选择.惯性权重w很小时偏重于发挥粒子群算法的局部搜索能力;惯性权重很大时将会偏重于发挥粒子群算法的全局搜索能力。
实现C++代码
代码来自2008年数学建模东北赛区B题,
#include "stdafx.h"
#include <math.h>
#include <time.h>
#include <iostream>
#include <fstream>
using namespace std;
int c1=2; //加速因子
int c2=2; //加速因子
double w=1; //惯性权重
double Wmax=1; //最大惯性权重
double Wmin=0.6; //最小惯性权重
int Kmax=110; //迭代次数
int GdsCnt; //物资总数
int const Dim=10; //粒子维数
int const PNum=50; //粒子个数
int GBIndex=0; //最优粒子索引
int Xdown[Dim]=; //粒子位置下界数组
int Value[Dim]; //初始急需度数组
int Vmax[Dim]; //最大速度数组
class PARTICLE; //申明粒子节点
void Check(PARTICLE&,int); //约束函数
void Input(ifstream&); //输入变量
void Initial(); //初始化相关变量
double GetFit(PARTICLE&); //计算
适应度
void CalculateFit(); //计算
适应度
void BirdsFly(); //粒子飞翔
void Run(ofstream&,int=2000); //运行函数
//微粒类
class PARTICLE
{
public:
int X[Dim]; //微粒的坐标数组
int XBest[Dim]; //微粒的最好位置数组
int V[Dim]; //粒子速度数组
double Fit; //微粒适合度
double FitBest; //微粒最好位置适合度
};
PARTICLE Parr[PNum]; //粒子数组
int main() //主函数
{
ofstream outf("out.txt");
ifstream inf("data.txt"); //关联输入文件
inf>>GdsCnt; //输入物资总数
Input(inf);
Initial();
Run(outf,100);
system("pause");
return 0;
}
void Check(PARTICLE& p,int count)//参数:p粒子对象,count物资数量
{
srand((unsigned)time(NULL));
int sum=0;
for (int i=0;i<Dim;i++)
{
if (p.X
>Xup)
{
p.X
=Xup;
}
else if (p.X
<Xdown)
{
p.X
=Xdown;
}
if (p.V
>Vmax)
{
p.V
=Vmax;
}
else if (p.V
<0)
{
p.V
=0;
}
sum+=p.X
;
}
while (sum>count)
{
p.X[rand()%Dim]--;
sum=0;
for (int i=0;i<Dim;i++)
{
if (p.X
>Xup)
{
p.X
=Xup;
}
else if (p.X
<Xdown)
{
p.X=Xdown;
}
if (p.V>Vmax)
{
p.V=Vmax;
}
else if (p.V<0)
{
p.V=0;
}
sum+=p.X;
}
}
}
void Input(ifstream& inf) //以inf为对象输入数据
{
for (int i=0;i<Dim;i++)
{
inf>>Xup;
}
for (int i=0;i<Dim;i++)
{
inf>>Value;
}
}
void Initial() //初始化数据
{
GBIndex=0;
srand((unsigned)time(NULL));//初始化随机函数发生器
for (int i=0;i<Dim;i++)
{
Vmax=(int)((Xup-Xdown)*0.035);
}
for (int i=0;i {
for (int j=0;j<Dim;j++)
{
Parr.X[j]=(int)(rand()/(double)
RAND_MAX*(Xup[j]
-Xdown[j])-Xdown[j]+0.5);
Parr.XBest[j]=Parr.X[j];
Parr.V[j]=(int)(rand()/(double)RAND_MAX*(Vmax[j] -Vmax[j]/2));
}
Parr.Fit=GetFit(Parr);
Parr.FitBest=Parr.Fit;
if (Parr.Fit>Parr[GBIndex].Fit)
{
GBIndex=i;
}
}
}
double GetFit(PARTICLE& p)//计算对象
适应度
{
double sum=0;
for (int i=0;i<Dim;i++)
{
for (int j=1;j<=p.X;j++)
{
sum+=(1-(j-1)*a/(Xup-b))*Value;
}
}
return sum;
}
void CalculateFit()//计算数组内各粒子的
适应度
{
for (int i=0;i {
Parr.Fit=GetFit(Parr);
}
}
void BirdsFly()//粒子飞行寻找最优解
{
srand((unsigned)time(NULL));
static int k=10;
w=Wmax-k*(Wmax-Wmin)/Kmax;
k++;
for (int i=0;i {
for (int j=0;j<Dim;j++)
{
Parr.V[j]=(int)(w*Parr.V[j])
+(int)(c1*rand()/(double)RAND_MAX*
(Parr.XBest[j]-Parr.X[j])
+c2*rand()/(double)RAND_MAX*
(Parr[GBIndex].XBest[j]-Parr.X[j]));
}
Check(Parr,GdsCnt);
for (int j=0;j<Dim;j++)
{
Parr.X[j]+=Parr.V[j];
}
Check(Parr,GdsCnt);
}
CalculateFit();
for (int i=0;i {
if (Parr.Fit>=Parr.FitBest)
{
Parr.FitBest=Parr.Fit;
for (int j=0;j<Dim;j++)
{
Parr.XBest[j]=Parr.X[j];
}
}
}
GBIndex=0;
for (int i=0;i {
if (Parr.FitBest>Parr[GBIndex].FitBest&&i!=GBIndex)
{
GBIndex=i;
}
}
}
void Run(ofstream& outf,int num)//令粒子以规定次数num飞行
{
for (int i=0;i<num;i++)
{
BirdsFly();
outf<<(i+1)<<ends< for (int j=0;j<Dim;j++)
{
outf< }
outf<<endl;
}
cout<<"Done!"<<endl;
}