7 ABC算法 的概念，代码，小例子
2017-01-13 本文已影响0人
Silly_N_Fool
先上代码
#include<iostream>
#include<time.h>
#include<stdlib.h>
#include<cmath>
#include<fstream>
#include<iomanip>
using namespace std;
const int NP = 40;//种群的规模，采蜜蜂+观察蜂
const int FoodNumber = NP / 2;//食物的数量，为采蜜蜂的数量
const int limit = 20;//限度，超过这个限度没有更新采蜜蜂变成侦查蜂
const int maxCycle = 10;//停止条件
double result[maxCycle] = { 0 };//每轮循环中的函数值
/*****函数的特定参数*****/
const int D = 2;//函数的参数个数
const double lb = -5;//函数的下界
const double ub = 5;//函数的上界
/*****种群的定义****///定义了输入输出结构，IO结构
struct BeeGroup
{
double code[D];//函数的维数 //估计是函数有几个参数，不是几个参数用D就可以定义。我知道了，是输入变量的函数值。
double trueFit;//记录真实的最小值//估计是最优函数值
double fitness;//把最有函数值转化为适应度
double rfitness;//相对适应值比例
int trail;//表示实验的次数，用于与limit作比较//随机采样的次数。
}Bee[FoodNumber];//FoodNumber表示多少个采样点。然后再采样点附近局部采样。
BeeGroup NectarSource[FoodNumber];//蜜源，注意：一切的修改都是针对蜜源而言的 //蜜源应该是可行解集合 //？
BeeGroup EmployedBee[FoodNumber];//采蜜蜂 //每个采样点都有人在计算（采蜜/IO）
BeeGroup OnLooker[FoodNumber];//观察蜂 //？
BeeGroup BestSource;//记录最好蜜源 //记录最有解的input或者output，或者都记录。看到initial就是到时最有xy对。
/*****函数的声明*****/
double random(double, double);//产生区间上的随机数
void initilize();//初始化参数
double calculationTruefit(BeeGroup);//计算真实的函数值
double calculationFitness(double);//计算适应值
void CalculateProbabilities();//计算轮盘赌的概率
void evalueSource();//评价蜜源
void sendEmployedBees();//采蜜蜂，计算蜂，局部变异蜂
void sendOnlookerBees();//观察蜂？
void sendScoutBees();//侦察蜂？
void MemorizeBestSource();//记录最有解xy对的函数
/*******主函数*******/
int main()
{
ofstream output; output.open("dataABC.txt");//写文件
srand((unsigned)time(NULL));//生成随机数，随机种子是时间
initilize();//初始化
MemorizeBestSource();//保存最好的蜜源
int gen = 0;
while (gen < maxCycle) {
sendEmployedBees();//体现计算蜂功能的时候到了//ok，计算蜂的功能是在采样点附近找更优的解。//这个函数只是进行了一次局部搜索
CalculateProbabilities();
sendOnlookerBees();//Onlook的功能是什么？也是进行一次局部变异
MemorizeBestSource();
sendScoutBees();//局部尝试若干次，无法找到最优解，就换个地方找找
MemorizeBestSource();
output << setprecision(10) << BestSource.trueFit << ","<< BestSource.code[0]<<","<< BestSource.code[1] << endl;
gen++;
}
output.close();
cout << "运行结束!!" << endl;//C++编程语言互换流中的标准输出流，需要iostream支持。
system("pause");
return 0;
}
void initilize()//初始化参数
{
int i, j;
for (i = 0; i<FoodNumber; i++) //就是随机取多少个可行解。
{
for (j = 0; j<D; j++)//如果输入x是向量的话就要用到D，就是一共有几个输入。
{
NectarSource[i].code[j] = random(lb, ub);//cout << NectarSource[i].code[j] << endl;
//code表示输入x，是随机生成的可行解。lb, ub是给定了上下界。NectarSource[i]也是xy对，但为什么取名Nectar，和其他类似数组有何区别不得而知。
EmployedBee[i].code[j] = NectarSource[i].code[j];
//同样，计算蜂也是xy对，EmployedBee[i].code[j] = NectarSource[i].code[j];表示蜜源Nectar被计算了，交给Employ计算/采蜜了
OnLooker[i].code[j] = NectarSource[i].code[j];
//OnLook的功能？
BestSource.code[j] = NectarSource[0].code[j];
//BestSource是用来存放最有xy对的。
}
/****蜜源的初始化*****/
NectarSource[i].trueFit = calculationTruefit(NectarSource[i]);//cout << NectarSource[i].trueFit << endl;
NectarSource[i].fitness = calculationFitness(NectarSource[i].trueFit); //cout << NectarSource[i].fitness << endl;
NectarSource[i].rfitness = 0;
NectarSource[i].trail = 0;
/****采蜜蜂的初始化*****/
//采蜜蜂的计算功能由蜜源承担了
EmployedBee[i].trueFit = NectarSource[i].trueFit;
EmployedBee[i].fitness = NectarSource[i].fitness;
EmployedBee[i].rfitness = NectarSource[i].rfitness;
EmployedBee[i].trail = NectarSource[i].trail;
/****观察蜂的初始化****/
//观察蜂的功能仍然不清楚
OnLooker[i].trueFit = NectarSource[i].trueFit;
OnLooker[i].fitness = NectarSource[i].fitness;
OnLooker[i].rfitness = NectarSource[i].rfitness;
OnLooker[i].trail = NectarSource[i].trail;
}
/*****最优蜜源的初始化*****/
//随机选定一个最有解/初始最优解。
BestSource.trueFit = NectarSource[0].trueFit;
BestSource.fitness = NectarSource[0].fitness;
BestSource.rfitness = NectarSource[0].rfitness;
BestSource.trail = NectarSource[0].trail;
}
double random(double start, double end)//随机产生区间内的随机数
{
return start + (end - start)*rand() / (RAND_MAX + 1.0);
}
double calculationTruefit(BeeGroup bee)//计算真实的函数值 //外面传入的蜜源，这里传入的是的形参是bee，bee的功能相当于一个桥梁，传递参数。
{
//计算一下目标函数值。
double truefit = 0;
/******测试函数1******/
truefit = bee.code[0] * bee.code[0] + bee.code[1] * bee.code[1]; //bee.code[0]* bee.code[1]*bee.code[0]* bee.code[1];
return truefit;
}
double calculationFitness(double truefit)//计算适应值 //构造了一个连续递减函数
{
double fitnessResult = 0;
if (truefit >= 0)
{
fitnessResult = 1 / (truefit + 1);
}
else
{
fitnessResult = 1 + abs(truefit);
}
return fitnessResult;
}
//以上4个函数共同完成了initial 操作，下面返回主函数
//主函数下一步是保存最好蜜源，就是最有xy解。
void MemorizeBestSource()//保存最优的蜜源 //就是把当前最优解与第i次循环中所有采蜜点比较
{
int i, j;
for (i = 1; i<FoodNumber; i++)
{
if (NectarSource[i].trueFit<BestSource.trueFit)
{
for (j = 0; j<D; j++)
{
BestSource.code[j] = NectarSource[i].code[j];
}
BestSource.trueFit = NectarSource[i].trueFit;
}
}
}
void sendEmployedBees()//修改采蜜蜂的函数
{
int i, j, k;
int param2change;//需要改变的维数
double Rij;//[-1,1]之间的随机数
for (i = 0; i<FoodNumber; i++){//对于每个采样点都随机局部变换
//对每个采样点都遍历一遍
param2change = (int)random(0, D);//随机选取需要改变的维数，取向量输入x的一个子集。
/******选取不等于i的k********/
while (1){
k = (int)random(0, FoodNumber);
if (k != i){
break;
}
}
for (j = 0; j<D; j++){
EmployedBee[i].code[j] = NectarSource[i].code[j];
}
/*******采蜜蜂去更新信息*******/
Rij = random(-1, 1);
EmployedBee[i].code[param2change] = (1- Rij)*NectarSource[i].code[param2change] + Rij*(NectarSource[k].code[param2change]);
//随机选择一个局部点位code[param2change]，在这个点位上把采样点i和k的值进行杂交
/*******判断是否越界********/
if (EmployedBee[i].code[param2change]>ub){
EmployedBee[i].code[param2change] = ub;
}
if (EmployedBee[i].code[param2change]<lb){
EmployedBee[i].code[param2change] = lb;
}
EmployedBee[i].trueFit = calculationTruefit(EmployedBee[i]);
EmployedBee[i].fitness = calculationFitness(EmployedBee[i].trueFit);
/******贪婪选择策略*******/
if (EmployedBee[i].trueFit<NectarSource[i].trueFit){
for (j = 0; j<D; j++){
NectarSource[i].code[j] = EmployedBee[i].code[j];
}
NectarSource[i].trail = 0;
NectarSource[i].trueFit = EmployedBee[i].trueFit;
NectarSource[i].fitness = EmployedBee[i].fitness;
}
else{
NectarSource[i].trail++;
}
}
}
void CalculateProbabilities()//计算轮盘赌的选择概率
{
int i;
double maxfit;
maxfit = NectarSource[0].fitness;
for (i = 1; i<FoodNumber; i++)
{
if (NectarSource[i].fitness>maxfit)
maxfit = NectarSource[i].fitness;
}
for (i = 0; i<FoodNumber; i++)
{
NectarSource[i].rfitness = (0.9*(NectarSource[i].fitness / maxfit)) + 0.1;
}
}
void sendOnlookerBees()//采蜜蜂与观察蜂交流信息，观察蜂更改信息
{
int i, j, t, k;
double R_choosed;//被选中的概率
int param2change;//需要被改变的维数
double Rij;//[-1,1]之间的随机数
i = 0;
t = 0;
while (t<FoodNumber){
R_choosed = random(0, 1);
if (R_choosed<NectarSource[i].rfitness){//根据被选择的概率选择 //对于每个采样点，都在局部变动一次，一定会被选择，不选择t就保持不变，
//不出循环，t<FoodNumber，说明t和全局采样点有关。i是NectarSource中的一点，说明也与全局采样点有关。
t++;
param2change = (int)random(0, D);//选择变异的x分量param2change
/******选取不等于i的k********/
while (1){
k = (int)random(0, FoodNumber);
if (k != i){
break;
}
}
for (j = 0; j<D; j++){
OnLooker[i].code[j] = NectarSource[i].code[j];
}
/****更新******///完成对param2change的变异，i=t-1
Rij = random(-1, 1);
OnLooker[i].code[param2change] =(1-Rij)*NectarSource[i].code[param2change] + Rij*(NectarSource[k].code[param2change]);
/*******判断是否越界*******/
if (OnLooker[i].code[param2change]<lb){
OnLooker[i].code[param2change] = lb;
}
if (OnLooker[i].code[param2change]>ub){
OnLooker[i].code[param2change] = ub;
}
OnLooker[i].trueFit = calculationTruefit(OnLooker[i]);
OnLooker[i].fitness = calculationFitness(OnLooker[i].trueFit);
/****贪婪选择策略******/
if (OnLooker[i].trueFit<NectarSource[i].trueFit){
for (j = 0; j<D; j++)
{
NectarSource[i].code[j] = OnLooker[i].code[j];
}
NectarSource[i].trail = 0;
NectarSource[i].trueFit = OnLooker[i].trueFit;
NectarSource[i].fitness = OnLooker[i].fitness;
}
else
{
NectarSource[i].trail++;
}
}
i++;
if (i == FoodNumber)
{
i = 0;
}
}
}
/*******只有一只侦查蜂**********/
void sendScoutBees()//判断是否有侦查蜂的出现，有则重新生成蜜源
{
int maxtrialindex, i, j;
double R;//[0,1]之间的随机数
maxtrialindex = 0;
for (i = 1; i<FoodNumber; i++)
{
if (NectarSource[i].trail>NectarSource[maxtrialindex].trail)
{
maxtrialindex = i;
}
}
if (NectarSource[maxtrialindex].trail >= limit)
{
/*******重新初始化*********/
for (j = 0; j<D; j++)
{
R = random(0, 1);
NectarSource[maxtrialindex].code[j] = lb + R*(ub - lb);
}
NectarSource[maxtrialindex].trail = 0;
NectarSource[maxtrialindex].trueFit = calculationTruefit(NectarSource[maxtrialindex]);
NectarSource[maxtrialindex].fitness = calculationFitness(NectarSource[maxtrialindex].trueFit);
}
}
这段代码解决的问题是x12+x22，迭代10次，结果可以，如图所示。
收敛趋势
还有一个问题，Onlooker和Employed的区别是什么？
EmployedBees：将采蜜蜂与蜜源一一对应，根据上面第一个公式更新蜜源信息，同时确定蜜源的花蜜量；对于每个采矿点，先进行一次试探性的局部搜索。
OnlookerBees：根据试探的结果，有选择性的进一步挖掘。挖掘就是多试几次。多产生几次随机数。利用轮盘赌概率，选中某个采矿点，然后在其附近搜索。
ScoutBees：当所有的采蜜蜂和观察蜂都搜索完整个搜索空间时，如果一个蜜源的适应值在给定的步骤内(定义为控制参数“limit”) 没有被提高, 则丢弃该蜜源，而与该蜜源相对应的采蜜蜂变成侦查蜂，侦查蜂通过已下公式搜索新的可能解。意思就是说生产全局最优解。
俄罗斯轮盘赌的选择情况如下图，但是OnlookerBees不是这么选的。t<=FoodNumber，就是说选中20次，至于选哪个，从0个开矿点开始，没被选中，就换下一个采矿点。选中了t=t+1；然后再对第i个采矿点进行局部变异搜索。那么ABC里的选择方法比轮盘赌又高明了一点。
Paste_Image.png
case 2
Paste_Image.png
Paste_Image.png
经过多次对照，确实可以求到近似最优解。
【-1，5】，最小值在5附近，ABC算法求导的最优解确实4.9x，没错。
Paste_Image.png
