布谷鸟算法（C++实现）

算法思想

布谷鸟鸟群最终只有最健康的蛋才能孵化出来。
布谷鸟群每只鸟都在拼命寻找好巢穴以达到下最健康的蛋的母的。

算法步骤

在这里插入图片描述

步骤一初始化

初始化布谷鸟种群数量（鸟窝个数），计算各个鸟窝（解）的函数适应值，并保存最好的鸟窝（当前最优解）。

步骤二循环体

算法主体的位置更新包含两个，一个是莱维飞行和局部随机行走

莱维飞行

在这里插入图片描述

莱维飞行是由较长时间的短步长和较短时间的长步长组成
Levy分布就是小概率值较大和大概率值较小，和自然界中大多数动物觅食方式方式类似，也就是先找到一片区域再细致的查找猎物，如果没找到，就换一片区域找。

在这里插入图片描述
布谷鸟算法使用 Mantegna 算法来实现对称的 Lévy 稳定分布。

局部随机行走

在宿主鸟发现布谷鸟蛋时，布谷鸟去寻找新的寄生巢时的位置更新。

在这里插入图片描述
a是步长缩放因子。

循环体步骤（1）位置更新

在这里插入图片描述
注意：
1.保留上代最优鸟窝位置，其余布谷鸟进行莱维飞行寻找寄宿鸟窝，此处可利用小技巧，如下方让 Lévy 稳定分布乘以系数
(i.x - OldNestPop[bestNum].x)，当鸟窝是最优解时，此系数为0，避免丢失最优鸟窝位置。

double stepX = (i.x - OldNestPop[bestNum].x) * R(e) / (pow(abs(R1(e)), 1 / beta));
double stepY = (i.x - OldNestPop[bestNum].x) * R(e) / (pow(abs(R1(e)), 1 / beta));

2.布谷鸟群新寄生一组鸟窝群，与原来的鸟窝群对比，替换原来适应度较差的鸟窝，布谷鸟群只守护适应度高的鸟窝。

循环体步骤（2）存安去险

在这里插入图片描述
注意：
1.布谷鸟群守护的寄生鸟窝的原宿主会跟布谷鸟打架，布谷鸟如果打不过，这只布谷鸟就会在这个鸟巢附近随机寻找一个新
鸟巢下蛋，并守护。（布谷鸟打不过的概率一般是Pa = 0.25）。
正规说法如下图。
在这里插入图片描述
2.布谷鸟群对更新后的鸟窝群里的布谷鸟蛋进行检测，选出最健康的蛋（找出更新后的当前最优解）。

步骤三终止条件

在这里插入图片描述

应用举例

以下是对一个二维函数求最小值的C++程序：
此函数为
在这里插入图片描述
此函数图像

算法结果图

在这里插入图片描述

C++程序如下

#include <iostream>
#include <vector>
#include <cmath>
#include <random>
#include <time.h>
#include <fstream>
#define pi acos(-1)
//5只布谷鸟
constexpr int NestNum = 40;	
//pi值
//规定X,Y 的取值范围
constexpr double X_max = 5;
constexpr double X_min = 0;
constexpr double Y_max = 5;
constexpr double Y_min = 0;
//最大迭代次数
constexpr int MaxIterationTimes = 300;
//被宿主发现的概率
constexpr double Pa = 0.25;//自变量结构体
struct Nest {double x;double y;double fitness;
};
void fitFunc(Nest& nest);
int findBetterNest(std::vector<Nest>&);
std::vector<Nest> levy(std::vector<Nest> OldNestPop, std::size_t bestNum);
std::vector<Nest> RandomAbandonPaNestPop(std::vector<Nest> OldNestPop);
//随机数引擎
static std::default_random_engine e(time(0));
static std::uniform_real_distribution<double> u(0, 1);
int main(void)
{bool flag_output = false;double Xold;double Xnew;double Yold;double Ynew;std::ofstream outfileX("D:\\cuckoo\\cuckooX.txt");std::ofstream outfileY("D:\\cuckoo\\cuckooY.txt");std::ofstream outfileZ("D:\\cuckoo\\cuckooZ.txt");//现在的鸟巢群std::vector<Nest> current_nestPop;//迭代次数int num = 0;//最优鸟巢int BestNestCurrent;	//初始化for (int i = 0; i < NestNum; ++i){Nest nestinitial;nestinitial.x = (X_max - X_min) * u(e) + X_min;nestinitial.y = (Y_max - Y_min) * u(e) + Y_min;fitFunc(nestinitial);current_nestPop.push_back(nestinitial);}//for (auto i : nestPop)//{//	std::cout << i.fitness << std::endl;//}//寻找最优个体BestNestCurrent = findBetterNest(current_nestPop);outfileX << current_nestPop[BestNestCurrent].x << std::endl;outfileY << current_nestPop[BestNestCurrent].y << std::endl;outfileZ << current_nestPop[BestNestCurrent].fitness << std::endl;while (num < MaxIterationTimes){//储存上次的最优解的X,YXold = current_nestPop[BestNestCurrent].x;Yold = current_nestPop[BestNestCurrent].y;//levy飞行--位置更新std::vector<Nest> NewNestPop = levy(current_nestPop, BestNestCurrent);//用适应值较好的鸟窝位置替换适应值较差的鸟窝位置for (decltype(NewNestPop.size()) i = 0; i < NewNestPop.size(); ++i){if (i != BestNestCurrent && NewNestPop[i].fitness < current_nestPop[i].fitness){current_nestPop[i] = NewNestPop[i];}}//此时得到更优的鸟窝位置//存安去险 保留鸟窝中被发现概率较小的鸟窝位置，并随机改变发现概率较大的鸟窝位置NewNestPop = RandomAbandonPaNestPop(current_nestPop);for (decltype(NewNestPop.size()) i = 0; i < NewNestPop.size(); ++i){if (i != BestNestCurrent && NewNestPop[i].fitness < current_nestPop[i].fitness){current_nestPop[i] = NewNestPop[i];}}//此时得到更优的鸟窝位置BestNestCurrent = findBetterNest(current_nestPop);//现在的最优鸟巢位置Xnew = current_nestPop[BestNestCurrent].x;Ynew = current_nestPop[BestNestCurrent].y;if (Xnew != Xold || Ynew != Yold){outfileX << current_nestPop[BestNestCurrent].x << std::endl;outfileY << current_nestPop[BestNestCurrent].y << std::endl;}outfileZ << current_nestPop[BestNestCurrent].fitness << std::endl;/*std::cout << current_nestPop[BestNestCurrent].fitness << std::endl;std::cout << "(x,y)" << '(' << current_nestPop[BestNestCurrent].x << ',' << current_nestPop[BestNestCurrent].y << ')' << std::endl;*///outfileX << current_nestPop[BestNestCurrent].x << std::endl;//outfileY << current_nestPop[BestNestCurrent].y << std::endl;//outfileZ << current_nestPop[BestNestCurrent].fitness << std::endl;num++;}std::cout << current_nestPop[BestNestCurrent].fitness << std::endl;return 0;
}void fitFunc(Nest& nest)
{nest.fitness = -sin(nest.x) * pow(sin(nest.x * nest.x / pi), 20) - sin(nest.y) * pow(sin(2 * nest.y * nest.y / pi), 20);//nest.fitness = -(nest.x - 1) * (nest.x - 1) + 1;
}int findBetterNest(std::vector<Nest>& nestPop)
{int BestNum = 0;for (decltype(nestPop.size()) i = 0; i < nestPop.size(); ++i){if (nestPop[i].fitness < nestPop[BestNum].fitness){BestNum = i;}}return BestNum;
}std::vector<Nest> levy(std::vector<Nest> OldNestPop,std::size_t bestNum)
{double beta = 1.5;//	double alpha = 0.01 * R(e);//有的论文写double alpha = 0.4;double sigma_u = pow((tgamma(1 + beta) * sin(pi * beta / 2)) / (beta * tgamma((1 + beta) / 2) * pow(2, (beta - 1) / 2)), 1 / beta);double sigma_v = 1;static std::normal_distribution<double> R(0, sigma_u);static std::normal_distribution<double> R1(0, sigma_v);for (auto& i : OldNestPop) {//前面的系数是保证最优鸟巢不会进行levy飞行double stepX = (i.x - OldNestPop[bestNum].x) * R(e) / (pow(abs(R1(e)), 1 / beta));double stepY = (i.x - OldNestPop[bestNum].x) * R(e) / (pow(abs(R1(e)), 1 / beta));//按范围更新Xif (i.x + alpha * stepX > X_max){i.x = X_max;}else if(i.x + alpha * stepX < X_min){i.x = X_min;}else{i.x = i.x + alpha * stepX;}//按范围更新Yif (i.y + alpha * stepY > Y_max){i.y = Y_max;}else if (i.y + alpha * stepY < Y_min){i.y = Y_min;}else{i.y = i.y + alpha * stepY;}fitFunc(i);}return OldNestPop;
}std::vector<Nest> RandomAbandonPaNestPop(std::vector<Nest> OldNestPop)
{double step_sizeX = 0;double step_sizeY = 0;static std::uniform_int_distribution<int> randomInt(0, OldNestPop.size() - 1);for(decltype(OldNestPop.size()) i = 0;i < OldNestPop.size();++i){if (u(e) < Pa)//被宿主发现了，要重新寻找新巢{step_sizeX = u(e) * (OldNestPop[randomInt(e)].x - OldNestPop[randomInt(e)].x);step_sizeY = u(e) * (OldNestPop[randomInt(e)].y - OldNestPop[randomInt(e)].y);if (OldNestPop[i].x + step_sizeX > X_max){OldNestPop[i].x = X_max;}else if(OldNestPop[i].x + step_sizeX < X_min){OldNestPop[i].x = X_min;}else{OldNestPop[i].x += step_sizeX;}if (OldNestPop[i].y + step_sizeY > Y_max){OldNestPop[i].y = Y_max;}else if (OldNestPop[i].y + step_sizeY < Y_min){OldNestPop[i].y = Y_min;}else{OldNestPop[i].y += step_sizeY;}fitFunc(OldNestPop[i]);}}return OldNestPop;
}