智能优化算法

您所在的位置：网站首页 › 鸟巢sbi原文 › 智能优化算法

智能优化算法

2024-01-30 11:29| 来源: 网络整理| 查看: 265

基本概念

算法具体流程

算法流程图

测试函数

优化结果

visual studio2017C++代码

基本概念

布谷鸟搜索算法（Cuckoo Search，缩写 CS）是由剑桥大学杨新社教授和S.戴布于2009年提出的一种新兴启发算法。根据昆虫学家的长期观察研究发现，一部分布谷鸟以寄生的方式养育幼鸟，它们不筑巢，而是将自己的卵产在其他鸟的巢中（通常为黄莺、云雀等），由其他鸟(义亲)代为孵化和育雏。然而，如果这些外来鸟蛋被宿主发现，宿主便会抛弃这些鸟蛋或新筑鸟巢。

通俗理解就是，布谷鸟蛋找到能成功在其他鸟巢成功孵化这个过程就是寻优过程。布谷鸟算法源于对布谷鸟繁育行为的模拟，为了简化自然界中布谷鸟的繁衍习性，Yang 等将布谷鸟的产卵行为假设为3个理想状态。

布谷鸟一次只产一个卵，并随机选择鸟窝位置来孵化它。在随机选择的一组鸟窝中，最好的鸟窝将会被保留到下一代。可选择的寄生巢的数量是固定的，寄生巢主人发现外来鸟蛋的概率为pa，其中 $0\leq pa\leqslant 1$ 。

基于这 3 个理想状态，Yang 等采用式（1）对下代鸟巢位置 $X_{i}^{t+1}$ 进行更新：

$X_{i}^{t+1}=X_{i}^{t}+\alpha \bigotimes Levy(\lambda )$ (1)

式中： $X_{i}^{t}$ 表示第 $i(i=1,2,3,...,n)$ 个鸟巢在第t代的位置； $\bigotimes$ 表示点对点乘法； $\alpha$ 表示步长控制量，用来控制步长大小，通常情况下，取 $\alpha=1$ 。 $Levy(\lambda )$ 为Levy随机搜索路径，属于随机行走，采用莱维飞行机制，其行走的步长满足一个重尾的稳定分布，而随机步长为levy分布:

$Levy:\mu =t^{-\lambda },1\leq \lambda \leqslant 3$ (2)

基本布谷鸟搜索算法先按照式（1）对下一代的鸟巢位置进行更新，并且计算目标函数的适应度值，如果该值优于上一代的目标函数值，则更新鸟巢位置，否则保持原来位置不变。通过位置更新后，用随机产生的服从 0 到 1 均匀分布的数值𝑅与鸟巢主人发现外来鸟蛋的概率pa相比较，若R>pa，则 $X_{i}^{t+1}$ 对进行随机改变，反之不变。最后保留测试值较好的一组鸟窝位置 $X_{i}^{t+1}$ ，记为 $X_{i}^{t+1}$ 。判断算法是否满足设置的最大迭代次数：若满足，结束迭代寻优，输出全局最优值fmin ；否则，继续迭代寻优。该算法具有全局探索和局部开发性能的平衡以及种群的多样性。

算法具体流程

Step 1（初始化）确定目标函数 $f(x),X=(x_{1},...,x_{d})^{T}$ 初始化群体，随机产生n个鸟窝的初始位置 $X_{i}(i=1,2,...,n)$ 。设置算法参数：种群规模N、维度D、发现概率pa、界值大小L、最大迭代次数MaxN、最优鸟窝位置 $X_{best}^{0}$ 和最优解 $f_{min}$ 。

Step 2（循环体）按式（1）、（2）更新当代鸟窝的位置；将当代鸟窝与上一代鸟窝位置 $P_{t-1}=\left [ X_{1}^{t-1} ,X_{2}^{t-1},...,X_{n}^{t-1} \right ]^{T}$ 进行对比,用适应度值较好的鸟窝位置替换适应度值较差的鸟窝位置： $g_{t}=\left [ X_{1}^{t} ,X_{2}^{t},...,X_{n}^{t} \right ]^{T}$ 。

Step 3（循环体）用随机数𝑅作为鸟窝主人发现外来鸟蛋的可能性，将其与鸟被淘汰的概率pa进行比较。若𝑅 >pa则随机改变 $g_{t}$ 中的鸟窝位置,得到一组新的鸟窝位置。再更新鸟窝位置，得到一组较好的鸟窝位置： $p_{t}=\left [ X_{1}^{t} ,X_{2}^{t},...,X_{n}^{t} \right ]^{T}$ 。更新最优鸟窝位置 $X_{best}^{t}$ 和最优解 $f^{t}_{min}$ 。

Step 4 判断算法是否满足设置的最大迭代次数：若满足，结束搜索过程，输出全局最优值 $f_{min}$ ，否则，重复step2进行迭代寻优。

算法流程图

测试函数

优化变量： $x_{1},x_{2}$

约束条件： $x_{low}=\left \{ -2,-2 \right \},x_{high}=\left \{ 2,2 \right \}$

目标函数: $f(x)=\left [ 1+(x_{1}+x_{2}+1)^{2} (19-14x_{1}+3x_{1}^{2}-14x_{2}+6x_{1}x_{2}+3x_{2}^{2})\right ]\times \left [ 30+(2x_{1}-3x_{2})^{2} (18-32x_{1}+12x_{1}^{2}+48x_{2}-36x_{1}x_{2}+27x_{2}^{2})\right ]$

式中， Goldstein-Price函数f(x)是一个二元八次多项式，作为常见的算法测试函数，许多科研人员利用它研究其局部最小值。上式为该优化问题的数学优化模型，该函数的理论结果为在(0,-1)处取得最小值3。

优化结果

从上图可以看出，布谷鸟搜索算法优化最小值为3.02573，迭代400次用时2.119s。

visual studio2017C++代码

头文件：

//布谷鸟搜索算法 //开发人员：chenshuai 开发日期：2019.11.25 邮箱：[email protected] //************************************************************************************// //布谷鸟算法参数设定 //************************************************************************************// #ifndef PCH_H #define PCH_H #include # include #include #include #include // 标准库 #include // 时间库 #include //容器头文件 #include #define PI 3.1415926535897 //π值 using namespace std; //产生随机小数或整数 class RandomNumber { public: RandomNumber() { srand((unsigned)time(NULL)); //析构函数，在对象创建时数据成员执行初始化操作 } int integer(int begin, int end) { return rand() % (end - begin + 1) + begin; } double decimal(double a, double b) { return double(rand() % 10000) / 10000 * (b - a) + a; } }; class cs { private: int N_nest;//种群（布谷鸟巢总数） int Max_iteration;//最大迭代次数， int D_egg;//变量个数(布谷鸟蛋维数) double pa;//布谷鸟蛋被发现的概率 double cs_alpha;//步长控制量 double R; //随机数R public: double lambda; vectorfmin; //最优解 vectorf_nest; //鸟窝的适应度值 vectorp_t; //与上一代比较后最优的鸟窝种群 vectorg_t; //被发现之后，更新的最优鸟窝种群 vectornest_best; //最好的鸟窝 vectornest_low = { -2,-2 }; //储存变量上限值（鸟窝的上限） vectornest_high = { 2,2 }; //储存变量下限值（鸟窝的下限） //*******************************************// //定义函数 //*******************************************// void setParameters();//设置算法参数int N_nest,int Max_iteration,int D_egg,double cs_alpha void initialize(); //初始化 double select_optimal(vectorx); //选择最优的鸟巢 double fit_function(vector x); //目标函数 vector update_Levyflight(vectorx, int t);//莱维飞行更新鸟窝位置 vector update_Rrandomnumber(vectorx);//随机数R更新鸟窝位置 }; #endif //PCH_H

函数文件：

#include "pch.h" //*********************************************** //设置布谷鸟算法参数 //********************************************** void cs::setParameters() { N_nest = 100; //种群（布谷鸟巢总数） Max_iteration = 400;//最大迭代次数， D_egg = 2;//变量个数(布谷鸟蛋维数) pa = 0.25;//布谷鸟蛋被发现的概率 cs_alpha = 1.0;//步长控制量 } //********************************************** //初始化群体，N个鸟窝的初始位置 //********************************************** void cs::initialize() { extern RandomNumber r; //定义随机数 fmin.resize(Max_iteration); p_t.resize(N_nest, vector(D_egg)); g_t.resize(N_nest, vector(D_egg)); f_nest.resize(Max_iteration, vector(N_nest)); nest_best.resize(D_egg); for (int i = 0; i < N_nest; i++) { for (int j = 0; j < D_egg; j++) { p_t[i][j] = r.decimal(nest_low[j], nest_high[j]);//初始化鸟窝的值 } } } //*********************************************** //鸟窝位置的适应度 //********************************************** double cs::fit_function(vectorx) { double fx = 0; //Rastrigin函数 /*for (int i = 0; i < 2; i++) { fx = fx + x[i] * x[i] - 10 * cos(2 * PI*x[i]) + 10; }*/ //Goldstein -Price函数 fx = (1 + pow((1 + x[0] + x[1]), 2)*(19 - 14 * x[0] + 3 * x[0] * x[0] - 14 * x[1] + 6 * x[0] * x[1] + 3 * x[1] * x[1]))*(30 + pow((2 * x[0] - 3 * x[1]), 2)*(18 - 32 * x[0] + 12 * x[0] * x[0] + 48 * x[1] - 36 * x[0] * x[1] + 27 * x[1] * x[1])); //SiX-Hump Camel函数 //fx = 4 * x[0] * x[0] - 2.1*pow(x[0], 4) + 1.0 / 3.0*pow(x[0], 6) + x[0] * x[1] - 4 * x[1] * x[1] + 4 * pow(x[1], 4); return fx; } //********************************************** //计算每个鸟窝的目标函数值并记录当前的最优解 //********************************************** double cs::select_optimal(vectorx) { double fmin = 0; fmin = fit_function(x[0]); for (int i = 1; i < N_nest; i++) { if (fmin > fit_function(x[i])) { fmin = fit_function(x[i]); for (int j = 0; j < D_egg; j++) { nest_best[j] = x[i][j]; } } } return fmin; } //********************************************** //随机数R更新鸟窝位置 //********************************************** vector cs::update_Rrandomnumber(vectorx) { extern RandomNumber r; //声明全局随机数 for (int j = 0; j < N_nest; j++) { for (int k = 0; k < D_egg; k++) { R = r.decimal(0, 1); if (R > pa) { x[j][k] = r.decimal(nest_low[k], nest_high[k]); } } } return x; } //********************************************** //莱维飞行更新每个鸟窝的位置 //********************************************** vector cs::update_Levyflight(vectorx, int t) { extern RandomNumber r; //声明全局随机数 for (int j = 0; j < N_nest; j++) { for (int k = 0; k < D_egg; k++) { lambda = r.decimal(1, 3); x[j][k] = x[j][k] + cs_alpha * pow(t, -1 * lambda); if (x[j][k]< nest_low[k] || x[j][k] > nest_high[k]) { x[j][k] = r.decimal(nest_low[k], nest_high[k]); } } } return x; }

主函数：

#include "pch.h" #include RandomNumber r; //随机数 int main() { clock_t startTime, endTime; //定义程序开始运行时间和结束时间 startTime = clock(); //计时开始 cs CS; //定义布谷鸟种群 CS.setParameters();//设置算法参数 CS.initialize(); //初始化 CS.fmin[0] = CS.select_optimal(CS.p_t);//选择初代最优个体 cout CS.select_optimal(CS.p_t)) { CS.fmin[i] = CS.select_optimal(CS.p_t); } out

【本文地址】

公司简介

联系我们

今日新闻

推荐新闻

专题文章