一种新型群智能优化算法-鸽群算法

摘要

本发明属于优化算法领域，提供了一种新型群智能优化算法‑鸽群算法。算法包括起飞、飞行、归巢三大过程。起飞过程包括初始化、腾空和上升三个子过程，用于初始化鸽群位置、飞行速度和最优解的方向；飞行过程包括平飞、转弯和追逐三个子过程，用于寻找局部最优解、全局最优解和改善全局最差解；归巢过程则避免算法陷入局部最优解。本发明算法具有如下特点：1)算法对目标函数的性质要求不高，可以是函数表达式，也可以是非函数形式的表示形式；2)对低维函数具有全局收敛性较强、算法循环次数少、收敛速度快的特点；3)对高维、多峰值、复杂问题具有较强的全局收敛性、较少的循环次数以及较高的稳定性。

主权项

一种新型群智能优化算法‐鸽群算法，其特征在于，步骤如下：(1)起飞过程：模拟鸽群起飞的特点，包含初始化、腾空和上升三个子过程，用来均匀化初始值并寻找最优解的方向；1)初始化定义N为鸽群中鸽子数量；向量X_i＝(x_i1,x_i2,…,x_ij,…,x_in)，i＝1,2,…,N，j＝1,2,…,n为鸽子i的当前位置；n为未知数个数，即维度；每只鸽子的当前位置向量x_i对应优化问题的一个可行解，并具有相同的维度n；向量Y_i＝(y_i1,y_i2,…,y_in)为鸽子i当前最优位置；向量P_b＝(p_b1,p_b2,…,p_bn)为鸽群当前最优位置；向量P_w＝(p_w1,p_w2,…,p_wn)为鸽群当前最差位置；步骤1：鸽群位置的初始化对于一个多维函数，变量x_ij有定义域[x_down,x_up]，由于鸽群在起飞时有先有后，因此在定义域范围内，每只鸽子的初始定义域范围按式(1)递减，使得鸽群的初始化位置丰富，定义向量将向量λ打乱顺序获得向量λ'：$x_{ij}={\lambda }_i^{\prime }[\beta (x_{up}-x_{down})+x_{down}]---\left(1\right)$式中：β为[0,1]内的随机数；步骤2：鸽群敏感度初始化鸽子反应灵敏，警觉性高，易受到惊吓，每只鸽子的敏感性不同；定义α_i为鸽子i的敏感系数，α_i从[0,1]中随机产生；步骤3：鸽群速度初始化定义向量V_i＝(v_i1,v_i2,…,v_ij,…v_in)为鸽子i的飞行速度，[‑V_max,V_max]为飞行速度的范围，v_ij从中随机产生，其表达式为：v_ij＝δV_max                    (2)式中：δ为[‑1,1]内的随机数；2)腾空鸽群在起飞时，蹬地的高度有所不同；根据这一特性，均匀化初始值，定义[down,up]为鸽群的腾空区间；步骤1：ΔX_i＝(Δx_i1,Δx_i2,…,Δx_ij,…,Δx_in)为鸽子i的腾空高度，ΔX_i中的每一分量从腾空范围中随机产生，其表达式：Δx_ij＝ε(up‑down)+down              (3)式中：ε为[0,1]内的随机数；步骤2：更新每只鸽子的当前位置X_i，其表达式X_i＝Y_i+α_i*ΔX_i                 (4)若X_i优于当前最优位置Y_i，则将当前位置X_i赋给当前最优位置Y_i，即Y_i＝X_i，若X_i优于鸽群当前最优位置P_b，则令P_b＝X_i；腾空区间[down,up]的精度与鸽群当前最优位置P_b分量p_ij的最大值相同；当P_b中p_ij的最大值的精确度为十分之一时，腾空区间[down,up]按下式保持相同的精确度：$\left\{\begin{array}{c}{\mathrm{up}}_{new}=up*0.1\\ {\mathrm{down}}_{new}=down*0.1\end{array}\right.---\left(5\right)$3)上升鸽群腾空后有上升过程，使鸽群朝更优的方向飞行；用伪梯度方法模拟，寻找最优解的方向，称为上升方向f′_ij(X_i)；步骤1：通过式(6)，随机产生向量ΔC_i＝(Δc_i1,Δc_i2,…,Δc_ij,…,Δc_in)式中：ri为上升高度；步骤2：计算鸽子i在每一维度j的上升方向f′_ij(X_i)，其表达式：$f_{ij}^{\prime }\left(X_i\right)=\frac{f(X_i+{\mathrm{\Delta C}}_i)-f(X_i-{\mathrm{\Delta C}}_i)}{2{\mathrm{\Delta c}}_{ij}},i=1,2,...,N,j=1,2,...,n;---\left(7\right)$步骤3：更新每只鸽子的当前位置X_i，其表达式：x_ij＝y_ij+ri*sign(f′_ij(X_i))               (8)式中：sign(x)为符号函数，当x>0时sign(x)＝1；当x＝0时sign(x)＝0；当x＜0时sign(x)＝‑1；若X_i优于当前最优位置Y_i，则令Y_i＝X_i，若X_i优于鸽群当前最优位置P_b，则令P_b＝X_i；步骤4：再循环一次步骤1至步骤3；为了避免随机向量ΔC_i有较大的偏差对f′_ij(X_i)准确度产生影响，重复操作；当腾空范围[down,up]的取值变化时，上升高度ri比腾空范围的精确度多一位；(2)飞行过程：模拟鸽群飞行的特点，包含平飞、转弯和追逐三个子过程；平飞用于局部寻优，转弯用于全局寻优，追逐用于改善全局最差解；当鸽群升空后，进入飞行阶段，鸽子在平缓飞行时，方向是听从邻居的，鸽子在急转弯时，方向是听从领导的；利用这一特点，令鸽群在平飞时寻找局部最优，转弯时寻找全局最优；1)平飞定义鸽子i的邻居范围为M，即鸽子周围的M只鸽子作为自身的邻居；Ave_i为邻居鸽群的平均位置；平飞次数为F₁；步骤1：计算鸽子i的平均位置Ave_i，其表达式：式中，M是一个非常重要的参数，它影响局部最优值的寻优；当M的取值过大时，Ave_i的值会趋近于全局最优，影响算法的收敛速度；当M的取值过小时，算法容易早熟收敛，影响算法的精度；在该公式中是向下取整函数；步骤2：计算鸽子i的飞行速度V_i；V_i＝w*V_i+c₁*(Ave_i‑X_i)                 (10)式中：c₁是局部飞行因子，w是飞行权重系数，从0.9到0.4递减，其表达式：$w=0.9-\frac{0.5}{M_c-1}*(cn-1)---\left(11\right)$式中：M_c是总迭代次数，cn是算法当前迭代次数；步骤3：更新每只鸽子的当前位置，其表达式：X_i^r+1＝X_i^r+V_i              (12)若X_i^r+1优于当前最优位置Y_i，则令Y_i＝X_i^r+1，若X_i优于鸽群当前最优位置P_b，则令P_b＝X_i^r+1；步骤4：重复步骤1至步骤3，直至达到平飞循环次数F₁；2)转弯鸽群在飞行过程中经常转弯来保证鸽群的飞行方向，模拟这一特性，定义转弯次数为F₂；步骤1：计算鸽子i的飞行速度V_i；V_i＝c₂(P_b‑Y_i)                  (13)式中：c₂是全局飞行因子；步骤2：更新每只鸽子的当前位置，其表达式同式(12)；若X_i^r+1优于当前最优位置Y_i，则令Y_i＝X_i^r+1，若X_i优于鸽群当前最优位置P_b，则令P_b＝X_i^r+1；步骤3：重复步骤1至步骤2，直至达到转弯循环次数F₂；3)追逐鸽子与其他鸟类相比，是“一夫一妻”制的鸟类，当雌鸽飞出巢穴后，雄鸽会有“逐妻”行为，称为追逐；设定鸽群最优位置P_b为雌鸽，鸽群最差位置P_w为雄鸽，让它们配对，改善全局最差解；步骤1：在n维空间向量的[n/2]～n维度之间随机产生一个整数位cp，作为位置替代点：cp＝[n/2]+[φ(n/2)]              (14)式中：φ为[0,1]内的随机数；步骤2：将P_b＝(p_b1,p_b2,…,p_bcp,…,p_bn)中从cp～n位置的值直接复制到P_w＝(p_w1,p_w2,…,p_wcp,…,p_wn)中cp～n相应位置，如果更新后的群体最差位置P_w优于之前的最差位置，则保留更新，否则不进行更新；(3)归巢过程：根据鸽子具有强烈归巢性的特点，在归巢的过程中避免算法陷入局部最优解；鸽子具有强烈的归巢性，飞行完成后总会返回自己的巢穴；定义[‑rg,rg]为归巢范围，归巢范围越小则最后着陆的范围越小，反之亦然；由于每只鸽子的记忆力都不同，因此引入平均位置差ΔH_i，防止个别鸽子着陆时产生大的偏差；步骤1：对于鸽子i，在[‑rg,rg]中随机产生一个归巢系数r_i；步骤2：根据每只鸽子的当前最优位置，判断个体位置与其他鸽子平均位置的差距；${\mathrm{\Delta H}}_i=r_i*\left(\right(\underset{i=1}{\overset{N}{\Sigma }}{Y}_i-Y_i)/(N-1)-Y_i)---\left(15\right)$步骤3：更新鸽子i的当前位置；X_i＝Y_i+ΔH_i              (16)若X_i优于当前最优位置Y_i，则令Y_i＝X_i，若X_i优于鸽群当前最优位置P_b，则令P_b＝X_i；完整的一次鸽群算法流程即：起飞、飞行和归巢三大过程；反复迭代此过程，直到找到全局最优解或满足终止条件。