牛骏峰的音乐:多种群多编码遗传算法通用控件

多种群多编码遗传算法通用控件MPGA 1.5

HBD 2007

(一)    多种群多编码遗传算法通用控件介绍

设计遗传算法通用控件的目的是向用户提供一个工程优化工具箱, 利用此工具箱用户可以方便地把遗传算法加入自己的软件中来优化用户自己定义的目标函数。用户只需要提供目标函数，再加入相应的设置代码后便可以用遗传算法进行优化，使用户从繁琐的遗传算法编程中脱离出来，把注意力集中到目标函数的设计上来。

采用控件把遗传算法封装起来的好处是可以适用于各种开发平台如：VC++、VB、Delphi等等，另外利用控件的消息处理，用户可以方便的加入目标函数和计算结果通知函数。

多种群多编码遗传算法通用控件并不是采用简单的标准遗传算法，而是采用了一系列的改进方法：

1.          实现了多种编码：二进制编码、实数编码、整数编码。用户可以自行选择。

2.          其次实现了多种群进化，种群的数量由用户定义，每个种群的编码方式也是用户自定义。每个种群的进化都是在独立的线程中的，多种群进化时进化线程是并发的，如有5个种群进化，便有5个线程同时并发优化。种群间的个体是可以移民的，每隔一定的进化代数后，每个种群或引入其他种群的优良个体，或输出自己的优良个体到其他种群。每个种群的编码方式、交叉函数、变异函数、交叉概率、变异概率、保留比率都可以互不相同，保证了各种群的多样性。

3.          每个种群的进化都采用了精英法则，加速了收敛速度。

(二)    多种群多编码遗传算法通用控件的使用方法

1.          注册控件

开始菜单－》运行，输入

regsvr32 相应目录\MPGA.ocx

2.          加入控件到自己的工程

在VC++下，在设计窗单击右键选择”Insert ActiveX control”在弹出的窗体中选择MPGA 

3.          响应消息

为控件添加两个消息响应函数。

两个消息分别为GetEvaluation和 Report, 在响应GetEvaluation消息函数中添加目标函数，Report消息响应函数得到当前计算出的最优解。

4.          关联控件变量

为控件关联一个变量，如m_ga。

5.          添加目标函数

目标函数添加到GetEvaluation消息函数，消息函数原型如下：

void CTestmpDlg::OnGetEvaluationMpgactrl1(long iPopulation, long iIndividual, double FAR* Evaluation)

iPopulation                   表示第几个种群

iIndividual           表示种群中的第几个个体

Evaluation           表示要传回的评价值

举例：

{

         double x1,x2;

         x1=m_ga.GetVarFromInd(iPopulation,iIndividual,0);

         x2=m_ga.GetVarFromInd(iPopulation,iIndividual,1);

         (*Evaluation)=-20*exp(-0.2*sqrt(0.5*(x1*x1+x2*x2)))-exp(0.5*(cos(2*3.1415926*x1)+cos(2*3.1415926*x2)))+22.71282;

}

在这个目标函数的例子中，优化变量有两个x1,x2。通过函数m_ga.GetVarFromInd(iPopulation,iIndividual,0)得到当前的变量值，0表示变量的编号，即第0个变量。

(*Evaluation)=-20*exp(-0.2*sqrt(0.5*(x1*x1+x2*x2)))-exp(0.5*(cos(2*3.1415926*x1)+cos(2*3.1415926*x2)))+22.71282;此句话便把目标函数给出，目标函数为：

-20*exp(-0.2*sqrt(0.5*(x1*x1+x2*x2)))-exp(0.5*(cos(2*3.1415926*x1)+cos(2*3.1415926*x2)))+22.71282

6.          添加 Report函数

Report消息响应函数被调用时，即控件通知软件计算出结果，一般是每隔几代报告一个，这是可以设置的具体见接口说明。Report消息响应函数原型为：

void CTestmpDlg::OnReportMpgactrl1(long iGeneration, long iPopulation, double Evaluation)

iGeneration         表示当前进化到第几代

iPopulation                   表示第几个种群

Evaluation           表示但前计算出的最佳目标函数值

举例：

{       CString str;

         double x1,x2;

         x1=m_ga.GetVarFromBestInd(0);

         x2=m_ga.GetVarFromBestInd(1);

         str.Format("Generation=%d  Population=%d  Evaluation%f :\r\n",iGeneration,iPopulation,Evaluation);

         disstr+=str;

         str.Format("1--%f  2--%f\r\n\r\n",x1,x2);

         disstr+=str;

         this->SetDlgItemText(IDC_EDIT1,disstr);

}

在此例中有两个优化变量，当前最佳个体的变量是通过函数m_ga.GetVarFromBestInd(0)得到的，0代表变量的编号，即第0个变量。得到之后显示结果给用户。

7.          添加初始化及运行代码

举例：

void CTestmpDlg::OnOK()

{      

m_ga.RestGA();

         m_ga.AddPopulation(1,100,0,0.9,0,0.1,60);//增加一个种群

//1-实数编码 100-种群规模 0-交叉方法 0.9-交叉概率 0-变异方法 0.1-变异概率 60-保留百分比

         m_ga.AddPopulation(0,500,0,0.8,0,0.03,70); //增加一个种群

//1-二进制编码 500-种群规模 0-交叉方法 0.8-交叉概率 0-变异方法 0.03-变异概率 70-保留百分比

         m_ga.AddVariable(-5,5,20,0);//增加一个变量

//-5-变量的下限  5-变量的上限  20-若为二进制编码为二进制编码长度 0-非整数

         m_ga.AddVariable(-5,5,20,0); //增加一个变量

         m_ga.InitGA(0,1000,20,10);//初始化

//0-求最小值  1000-进化1000代  20-report间隔20代  10­-移民间隔10代

         m_ga.RunGA();//开始进行优化

}

(三)    多种群多编码遗传算法通用控件接口说明

Ø         long AddPopulation(long EncodeMethod, long PopSize, long CrossoverMethod, float CrossoverProbability, long MutMethod, float MutProbability, float KeepPercentage)

接口含义：增加一个种群

EncodeMethod           编码方式，0－二进制编码 1－实数编码 2－整数编码

PopSize                      种群规模  大于0

CrossoverMethod      交叉方法 在试用版本中对二进制编码 0－单点交叉 1－双点交叉  对实数编码 0－算术交叉

CrossoverProbability 交叉概率  范围为 0－1

MutMethod               变异方法  在试用版本下设为0

MutProbability          变异概率  范围0-1

KeepPercentage                   保留百分比 范围 1－100

返回值：0为成功

Ø         long AddVariable(double Min, double Max, long nBits, short IsInteger)

接口含义：增加一个优化变量

Min                   优化变量的最小值

Max                   优化变量的最大值

nBits        当为二进值编码时，二进制编码的长度 大于0

IsInteger   是否为整数 1－为整数 0－非整数

返回值：0为成功

Ø         long InitGA(short IsMax, long GenerationNumber, long ReportPeriod, long MigrationPeriod)

接口含义：初始化

IsMax                         0－求最小值  1－求最大值

GenerationNumber     进化代数  大于0

ReportPeriod              report间隔代数，要求为MigrationPeriod的倍数

MigrationPeriod         移民间隔代数 >0,建议值10-100

返回值：0为成功

Ø         void RestGA()

接口含义：rest GA, 当前正在进化时，会停止所有进化线程。

Ø         long RunGA()

接口含义：开始进行进化。

返回值：0为成功

Ø         double GetVarFromInd(long iPopulation, long iIndividual, long iVariable)

接口含义：从当前个体得到优化变量值，此接口提供变量值给目标函数计算。

iPopulation       第几个种群   此参数赋消息响应函数参数iPopulation

iIndividual         第几个个体   此参数赋消息响应函数参数iIndividual

iVariable            第几个变量   变量编号从0开始

返回值：变量值

Ø         double GetVarFromBestInd(long iVariable);

接口含义：从当前最佳个体得到优化变量值，此接口用户显示结果给用户。

iVariable            第几个变量   变量编号从0开始

返回值：变量值

(四)    多种群多编码遗传算法通用控件消息说明

Ø         GetEvaluation

void GetEvaluation(long iPopulation, long iIndividual, double* Evaluation)

消息含义：获取用户的目标函数值

iPopulation       第几个种群

iIndividual         第几个个体

Evaluation        返回目标函数值

Ø         Report

void Report(long iGeneration, long iPopulation, double Evaluation)

消息含义：报告结果给用户

iGeneration       第几代

iPopulation       第几个种群

Evaluation         当前最佳目标函数值

(五)    其他

l          VB 和delphi 用户如何使用？

VB 和delphi环境下和VC++的使用流程类似，不需要做额外的操作。

l          对于有约束条件的优化问题如何解决？

对于约束条件问题可以采用惩罚函数法，即把不符合条件的目标函数值增加响应的惩罚项，控件在优化时会淘汰较差个体。如：

(*Evaluation)=objectvalue+fa(x);   //fa为惩罚函数

详细例子和使用说明：下载1 http://download.csdn.net/source/262362

下载2：http://www.fileupyours.com/files/135326/MPGA1.5.rar