一种基于局部Lipschitz估计的自适应群体全局优化方法

摘要

一种基于局部Lipschitz估计的自适应群体全局优化方法，在群体进化算法框架下，结合Lipschitz估计理论，首先，设计参数自适应机制来动态调整各变异策略的参数，同时通过提取新个体的邻域信息建立下界支撑面，进而利用下界支撑面估计目标函数值来竞争选择各策略生成的新个体，并指导种群更新；其次，利用下界估计区域极值点快速枚举算法有效的识别出部分无效区域，并借助下界支撑面的下降方向作局部增强。

主权项

一种基于局部Lipschitz估计的自适应群体全局优化方法，其特征在于：所述全局优化方法包括以下步骤：1)初始化：设置常数C，种群规模N_P，学习代数L_G和各变量的下界a_i和上界b_i，置无效区域IR为空，代数G＝0，均值C_Rm^t＝0.5，成功进入下一代的新个体的个数N_s^t＝0，在各变量定义域范围内随机生成初始种群2)建立n叉树保存各下界估计值：2.1)根据公式(1)对单位单纯形区域的各顶点进行转换得到点x¹，x²，...，x^N+1；$x_i=x_i^{\prime }{\Sigma }_{i=1}^N(b_i-a_i)+a_i,i=\mathrm{1,2},...,N---\left(1\right)$其中a_i为x_i的下界，b_i为x_i的上界，其中x′_i为各顶点在S中的坐标值；2.2)根据公式(2)计算各点的支撑向量l¹，l²，...，l^N+1，式中f(x^k)表示x^k对应的目标函数值；$l^k=(\frac{f\left(x^k\right)}{C}-x_1^k,\frac{f\left(x^k\right)}{C}-x_2^k,...,\frac{f\left(x^k\right)}{C}-x_{N+1}^k)---\left(2\right)$其中，C为足够大的常数；2.3)以支撑矩阵L＝{l¹，l²，...，l^N+1}为根建立树，支撑矩阵L如公式(4)；$L=\left(\begin{array}{cccccc}{l}_1^{k_1}& l_2^{k_1}& ·& ·& ·& l_{N+1}^{k_1}\\ l_1^{k_2}& l_2^{k_2}& ·& ·& ·& l_{N+1}^{k_2}\\ ·& ·& ·& & & ·\\ ·& ·& & ·& & ·\\ ·& ·& & & ·& ·\\ l_1^{k_{N+1}}& l_2^{k_{N+1}}& ·& ·& ·& l_{N+1}^{k_{N+1}}\end{array}\right)---\left(3\right)$3)判断是否满足终止条件：计算出当前群体中的最优个体x_best和最差个体x_worst，如果满足终止条件(如|f(x_best)‑f(x_worst)|≤ε，其中，ε为允许误差)，则保存结果并退出，否则进入步骤4)；4)利用参数自适应机制交叉、变异产生新个体：4.1)任意选取四个个体{x^a，x^b，x^c，x^d|a，b，c，d∈{1，2，...，popSize}，a≠b≠c≠d≠k)；4.2)分别根据公式(4)和(5)的变异策略对{x^a，x^b，x^c，x^d}执行变异操作，生成变异个体${\hat{x}}^k=x^a+F_k·(x^b-x^c)---\left(4\right)$${\hat{x}}^k=x_{\mathrm{pbest}}^{\psi }+F_k(x^a-x^b)+F_k(x^c-x^d)---\left(5\right)$其中，F_k＝normrnd(0.5，0.3)表示第k个目标个体的增益常数，normrnd(0.5，0.3)表示产生均值为0.5，标准偏差为0.3的正态分布随机数，ψ表示[1，0.5N_P]之间的随机整数，表示ψ个个体中的最优个体；4.3)根据公式(6)分别对公式(4)和公式(5)产生的变异个体执行交叉操作，生成新个体$x_{\mathrm{trial}}^t\left[i\right]=\begin{array}{cc}\left\{\begin{array}{cccc}{\hat{x}}_i^k& \mathrm{if}(\mathrm{randb}\left(\mathrm{0,1}\right)\le C_{\mathrm{Rk}}^t)& \mathrm{or}& i=\mathrm{rnbr}\left(i\right)\\ x_i^k& \mathrm{if}(\mathrm{randb}\left(\mathrm{0,1}\right)>C_{\mathrm{Rk}}^t)& \mathrm{or}& i\ne \mathrm{rnbr}\left(i\right)\end{array}\right.& i=\mathrm{1,2},...,N---\left(6\right)\end{array}$其中，randb(0，1)表示为产生0到1之间的随机小数，rnbr(i)表示随机产生1到N之间的整数，表示第t个变异策略生成的新个体，表示第k个目标个体对应的第t个变异策略的交叉概率，可根据公式(7)和(8)求得；$C_{\mathrm{Rk}}^t=\mathrm{normrnd}({C_{\mathrm{Rm}}}^t,0.1)---\left(7\right)$${C_{\mathrm{Rm}}}^t=\frac{\underset{g=G-L_G}{\overset{G-1}{\Sigma }}\underset{i=1}{\overset{N_{\mathrm{Sg}}^t}{\Sigma }}{C}_{\mathrm{RMi},g}^t}{\underset{g=G-L_G}{\overset{G-1}{\Sigma }}{N}_{\mathrm{Sg}}^t},(t=1,...,T;G>L_G)---\left(8\right)$其中，normrnd(C_Rm^t，0.1)表示生成均值为C_Rm^t，标准偏差为0.1的正态分布随机数，表示第g代中第t个变异策略生成的新个体成功进入下一代的数目，表示第g代中第t个策略生成的新个体成功进入下一代的交叉概率值，T表示总共有T个变异策略；5)找出离新个体最近的两个个体，并对其构建支撑向量：5.1)根据公式(9)将x^k转换到单位单纯形空间中得到x^k′；$\left\{\begin{array}{c}{x}_i^{\prime }\equiv (x_i-a_i)/{\Sigma }_{i=1}^N(b_i-a_i)\\ x_{N+1}^{\prime }\equiv 1-{\Sigma }_{i=1}^N{x}_i^{\prime }\end{array},i=\mathrm{1,2},...,N---\left(9\right)\right.$5.2)根据公式(2)计算x^k′的支撑向量l^k；5.3)根据条件关系式(10)(11)更新树：$\forall i,j\in I,i\ne j:l_i^{k_j}>l_i^{k_i}---\left(10\right)$$\forall r\notin \{k_1,k_2,...,k_{N+1}\},\exists i\in I:L_{\mathrm{ii}}=l_i^{k_i}\ge l_i^r---\left(\text{11}\right)$其中，表示存在；5.3.1)找出针对步骤5.2)构建的支撑向量l^k不满足条件(11)的叶子节点；5.3.2)用l^k替换步骤5.3.1)中找到的叶子节点矩阵中的第i个支撑向量从而形成新的叶子节点；5.3.3)判断步骤5.3.2)中产生的新的叶子节点是否满足条件关系式(10)，如果满足，则保留，否则删除；6)根据下界估计值竞争选择新个体：对个体进行如下操作：6.1)根据公式(9)对个体作变换得到6.2)根据公式(12)从树中找出包含个体的树叶在节点TreeNode，其中x^*用代替；$(x_j^{*}-x_j^{k_j})<(x_i^{*}-x_i^{k_j}),i,j\in I,i\ne j---\left(12\right)$其中为所找的叶子节点矩阵中的元素；6.3)根据公式(13)计算出所在节点TreeNode的下界估计值其中xⁱ用代替；$H^k\left(x\right)=\underset{k\le K}{\max }\underset{i=1,...N+1}{\min }C(l_i^k+x^i)---\left(13\right)$其中max表示求最大值，min表示求最小值，xⁱ为单位单纯形空间中的向量；6.4)比较下界估计值的值，选择最小的新个体作为当前目标个体对应的新个体x_trial；7)选择：通过如下操作决定新个体x_trial是否可以替换其对应的目标个体x^k：7.1)如果x_trial被包含在无效区域IR中，则保留x^k不变，并转到步骤7.7)，否则继续步骤7.2)；7.2)如果x_trial的下界估计值y_trial大于目标个体的函数值f(x^k)，则目标个体不变，并转到7.3)，否则转到步骤7.7)；7.3)继续根据公式(14)计算出节点TreeNode所对应的下界估计区域的极小值d_min；$d\left(L\right)=H^K\left(x_{\min }^{\prime }\right)=\frac{C(\mathrm{Trace}\left(L\right)+1)}{N+1}---\left(14\right)$其中Trace(L)表示矩阵的迹，即正对角线元素之和，其中L为支撑矩阵；7.4)如果d_min大于当前最优值f(x_best)，则将TreeNode所对应的区域视为无效区域，并加入LR中；7.5)如果x_trial个体的目标函数值f(x_trial)小于f(x_i)，则x_trial个体取代目标个体x^k，并继续步骤7.6)，否则转到步骤7.7)；7.6)继续做局部增强，进行如下操作：7.6.1)继续根据公式(15)计算出TreeNode对应区域的下界支撑函数的极小值点x′_min，式中L用TreeNode对应的支撑矩阵代替；$x_{\min }^{\prime }\left(L\right)=\frac{d}{C}-l_i^k---\left(15\right)$7.6.2)根据公式(1)对x′_min转换得到x_min；7.6.3)计算x_min对应的目标函数值f(x_min)；7.6.4)如果f(x_min)小于目标个体的函数值f(x^k)，则x_min取代目标个体x^k；7.7)删除树并转到步骤3)；8)设置G＝G+1，并转到步骤3)。