求解约束优化问题的改进樽海鞘算法

An Improved Salp Swarm Algorithm for Con-strained Optimization Problems

摘要: 针对约束优化问题，提出了一种运用改进樽海鞘算法求解约束优化问题的方法。通过外点法将约束优化问题转化为一系列无约束优化问题，然后运用双领导者结合败者淘汰策略的樽海鞘算法(DLSSA)，并对所得界约束优化问题进行求解以获得约束问题的解。利用6个约束优化基准测试问题对所得算法进行数值实验，实验结果表明，对于所有问题算法，PF-DLSSA所求解均优于算法PF-SSA所求解，即实验所得的最优值及其他数据都优于对比算法PF-SSA所求，所得算法能够有效地求解约束优化问题，且比对比算法效果要好。

Abstract: Aiming at the constrained optimization problem, an improved salp swarm algorithm was proposed to solve the constrained optimization problem. The constrained optimization problem is trans-formed into a series of unconstrained optimization problems by the outer point method, and then the salp swarm algorithm (DLSSA), which combines the two-leader and loser elimination strategy, is used to solve the unconstrained optimization problem to obtain the solution of the constrained problem. The numerical experiments of the proposed algorithm are carried out by using six con-straint optimization benchmark problems. Experimental results show that, for all problem algo-rithms, the solution of algorithm PF-DLSSA is superior to that of algorithm PF-SSA, that is, the opti-mal value and other data obtained by the experiment are superior to that obtained by the compar-ison algorithm PF-SSA. The proposed algorithm can effectively solve constrained optimization problems, and the effect is better than that of the comparison algorithm.

1. 引言

生活及工业生产等其他领域的问题通常伴随着一定的约束条件 [1] 。因此，如何使用改进所得算法去求解约束优化问题十分值得研究。用群智能优化算法去求解有约束优化问题的方法有很多，例如外点罚函数法 [2] ，内点罚函数法 [3] ，增广拉格朗日法 [4] ，多目标法 [5] 等。本章采用外点罚函数法结合算法DLSSA去求解约束优化问题。

对于工业生产及其他领域的优化问题，往往伴随着约束条件，而不是纯粹的某一方面达到最优 [5] ，对应到优化问题中，即所求解问题的数学模型中须加入一定的约束条件，这些约束条件可描述为一系列的等式约束条件及不等式约束条件，其具体的数学模型如下：

$\begin{array}{l}\min f\left(x\right)\\ \text{s}\text{.t}\text{.}{h}_i\left(x\right)=0,i=1,2,\cdots ,s\\ g_j\left(x\right)\le 0,j=s+1,\cdots ,p\end{array}$ (1)

文献 [6] 针对樽海鞘群算法求解精度不高和收敛速度慢等缺点，提出一种正弦余弦算法的樽海鞘群算法(SCSSA)。引入Logistics混沌序列生成初始种群，增加初始个体的多样性；将正弦余弦算法作为局部因子嵌入到樽海鞘群算法中，对樽海鞘个体进行正弦和余弦优化；对最优樽海鞘的领域空间进行差分演化变异策略，增强局部搜索能力。将改进算法在8个典型复杂函数优化问题上进行仿真实验，并同正弦余弦算法和樽海鞘群算法进行对比。实验结果表明，该算法具有更好全局搜索能力和局部搜索能力，寻优精度比标准算法有所增强。文献 [7] 针对樽海鞘群算法求解精度不高和收敛速度慢等缺点，提出一种多子群的共生非均匀高斯变异樽海鞘群算法，根据不同适应度值将樽海鞘链群分为三个子种群，各个子种群分别进行领导者位置更新、追随者共生策略和链尾者非均匀高斯变异等操作。使用统计分析、收敛速度分析、Wilcoxon检验、经典基准函数和CEC2014函数的标准差来评估改进樽海鞘群算法的效率。结果表明，改进算法具有更好的寻优精度和收敛速度。尤其在求解高维和多峰测试函数上，改进算法拥有更好性能。文献 [8] 提出了一种具有交叉方案和Levy飞行的樽海鞘算法。即采用Levy飞行策略分别改进樽海鞘算法中领导者和追随者的位置更新方式。数值实验已经对各种测试函数进行了测试，测试函数包括单模态、多模态、复合函数。数值实验的结果表明，所提出的算法SSACL在精度、稳定性和性能方面均优于其他先进算法，此外，Wilcoxon的秩和检验说明了所提出的算法的优势明显。为了提升樽海鞘算法的求解精度和全局搜索能力。

2. 罚函数法

罚函数法的目的将约束优化问题转化为一个新约束优化问题，用无约束优化方法来求解 [9] 。其主要方法是将约束条件转换为惩罚项，从而重新构造目标函数，通过调整惩罚因子，得到一系列的无约束优化问题，使其趋向最优解 [10] 。其主要包括外点罚函数法，内点罚函数法等。

2.1. 外点罚函数法

外点罚函数法可用于求解同时存在等式与不等式约束的约束优化问题，又称为障碍发法，即将惩罚项视为超出可行域的障碍。外点罚函数法的罚函数的可定义为：

$G\left(x\right)={\displaystyle {\sum }_{i=1}^s{\left(h_i\left(x\right)\right)}^2}+{\displaystyle {\sum }_{j=s+1}^p{\left\{\max \left\{g_j\left(x\right),0\right\}\right\}}^2}$ (2)

等式右端第一项为等式约束条件所对应的惩罚项，第二项为不等式约束所对应的惩罚项 [11] 。

2.2. 内点罚函数法

与外点罚函数法不同，内点罚函数法的惩罚因子随着迭代的进行不断减小，且内点罚函数法仅适用于只存在不等式条件的约束优化问题，这类问题的数学模型如下：

$\begin{array}{l}\min f\left(x\right)\\ \text{s}\text{.t}.g_j\left(x\right)\le 0,j=1,\cdots ,q\end{array}$ (3)

内点罚函数法罚函数的定义为

$R\left(x\right)={\displaystyle \underset{j=1}{\overset{q}{\sum }}\frac{1}{g_j\left(x\right)}}$ (4)

该罚函数仅由不等式约束对应的惩罚项构成 [12] 。

3. 改进的樽海鞘算法

在求解界约束子问题时运用群体智能优化算法，本文采用双领导者结合败者淘汰策略的樽海鞘算法(Double leader combined with loser elimination strategy of salp swarm algorithm, DLSSA)，算法DLSSA的具体过程如下所示。

3.1. 双领导者策略

为避免樽海鞘算法中的个体后期陷入局部最优，因此引入双领导者策略，即增加一个领导者，追随者随机选择其中一个领导者追随进行位置更新。

3.1.1. 领导者位置更新

在基本的樽海鞘算法中仅存在一个领导者，在迭代后期“链”的结构逐渐趋向稳定，导致个体出现聚集现象从而陷入局部最优。本章增加了一个新的领导者，即种群中的前两个个体均被视为领导者，在搜索前期，即当前迭代数t未达到最大迭代数T的一半时，两个领导者均按照原樽海鞘算法的领导者位置更新公式进行位置更新，其更新公式如下：

$x_1^j\left(t+1\right)=\{\begin{array}{l}{F}^j+c_1\left(\left(u{b}^j-l{b}^j\right)c_2+l{b}^j\right)c_3\ge 0.5\\ F^j-c_1\left(\left(u{b}^j-l{b}^j\right)c_2+l{b}^j\right)c_3<0.5\end{array}$ (5)

其中i = 1，2。在搜索后期，即当前迭代数t超过最大迭代数T的一半T/2后，第一个领导仍按(4-1)式进行位置更新，而令第二个领导者远离食物的位置，其更新机制类似于象群算法中女首领的位置更新 [13] ，即：

$x_2\left(t+1\right)=0.01F$ (6)

其中t > T/2。

3.1.2. 追随者位置更新

种群中除前两个个体外，其余个体均为追随者，对种群中的追随者，可选择不同的领导者进行跟随。为增强种群多样性，追随者随机加入不同的樽海鞘链，为使跟随两个不同领导者的概率基本相同，在每一个追随者 $x_l\left(t\right)\left(l=3,4,\cdots ,N\right)$ 位置更新前，生成一个(0,1)中的随机数p_l，，当p_l大于0.5时，该个体加入第一组，追随第一个领导者，反之该个体加入第二组，追随第二个领导者，从而所有追随者随机分成两组，记为 $x_{\text{1},\text{2}}\left(t\right),x_{\text{1},\text{3}}\left(t\right),\cdots ,x_{\text{1},N_1}\left(t\right)$ 与 $x_{\text{2},\text{2}}\left(t\right),x_{\text{2},\text{3}}\left(t\right),\cdots ,x_{\text{2},N_2}\left(t\right)$ ，其中 $N_1+N_2=N$ 。若令 $x_{\text{1},\text{1}}\left(t\right)=x_{\text{1}}\left(t\right)$ ， $x_{\text{2},\text{1}}\left(t\right)=x_{\text{2}}\left(t\right)$ 则追随者的位置更新公式可描述如下：

$x_{g,k}\left(t+1\right)=\left(x_{g,k}\left(t\right)+x_{g,k-1}\left(t\right)\right)/2$ (7)

其中g = 1，2，表示该个体在第g组，而k则表示该组中的第k个追随者，且有 $k\ge 2$ 。

3.2. 败者淘汰策略

在自然界的种群中，不同的生物个体进化程度不同。优胜劣汰，自然选择的现象十分普遍。在种群中许多实力较弱的个体，这些个体的狩猎等其他竞争能力较低，因此会被种群淘汰。使用新生个体对现有较弱个体进行替换，有利于保持种群多样性。因此本章引入败者淘汰策略，以改进原樽海鞘算法：在所有追随者完成位置更新后，计算每个个体的适应度值，种群中适应度值最差的10%的个体，即所对应目标函数值大的10%的个体，将被新生成的个体所替换，替换公式如下：

$x_f\left(t+1\right)=lb+\left(ub-lb\right)rand$ (8)

其中x_f表示种群中适应度值大的10%的个体。

在进行上述过程后，对所有个体进行适应度值的计算，其中适应度值最小的个体与食物的适应度值进行比较，两者中适应度值更小的个体为新的食物，并令迭代次数加1，进行再一次的领导者与追随者的位置更新，重复上述过程，直至达到终止条件即达到最大迭代次数T，然后停止迭代。

3.3. 双领导者结合败者淘汰策略改进的樽海鞘算法的步骤

双领导者结合败者淘汰策略改进的樽海鞘算法具体步骤如下：

步骤1：初始化种群，设置最大迭代次数T，并令当前迭代次数t = 0；

步骤2：计算个体适应度值，选出食物的位置；

步骤3：领导者1按照公式(5)进行更新，迭代前期，即t小于T/2时领导者2按照(5)式更新，迭代后期，即t不小于T/2时领导者2按照式(6)进行位置更新；

步骤4：对每个追随者，先生成一个随机数以选择其追随的领导者，然后根据公式(7)进行位置更新；

步骤5：计算所有个体的适应度值，并比较当前最优个体与食物的适应度值：适应度值更小的则为新的食物的位置；

步骤6：对种群中适应度值大的10%的个体根据公式(8)进行位置更新；

步骤7：判断是否满足终止条件：

若满足，则停止迭代输出全局最优解；

否则，令t = t + 1，并回到步骤3。

3.4. 双领导者结合败者淘汰策略改进的樽海鞘算法的伪代码

双领导者结合败者淘汰策略改进的樽海鞘算法伪代码如下：

1. 初始化种群，并设定最大迭代次数T，Let t = 0；

2. 计算个体的适应度值，并确定食物的位置；

3. while t < T

3.1领导者1根据公式(5)进行位置更新；

If t < T/2

领导者2按照公式(5)进行位置更新；

Else

领导者2按照公式(6)进行位置更新；

End

3.2对每个追随者，先生成一个随机数以选择其追随的领导者，然后根据公式(7)进行位置更新；

3.3计算所有个体的适应度值，并比较当前最优个体与食物的适应度值：适应度值更小的则为新的食物的位置；

3.4对种群中适应度值大的10%的个体根据公式(8)进行位置更新；

3.5 Let t = t + 1.

4. End

5.输出食物及其适应度值。

4. 基于外点罚函数改进的双领导者结合败者淘汰策略樽海鞘算法

对于改进得到的双领导者结合败者淘汰策略的樽海鞘算法DLSSA，在无约束问题的求解方面已经通过数值实验表明了其求解能力优异，但其无法求解约束优化问题，本节结合外点罚函数法和算法DLSSA得到的算法PF-DLSSA，以用于解决约束问题。

对于约束优化问题(1)可转换如下：

$F\left(x\right)=f\left(x\right)+\lambda {\displaystyle {\sum }_{i=1}^s{\left(h_i\left(x\right)\right)}^2}+\lambda {\displaystyle {\sum }_{j=s+1}^p{\left\{\max \left\{g_j\left(x\right),0\right\}\right\}}^2}$ (9)

其中f(x)为约束问题的目标函数， $\lambda$ 为惩罚因子，其表达式为 $\lambda ={10}^k$ ，( $k=0,1,\cdots ,20$ )，k为算法PF-DLSSA的外层迭代次数，即随着外层迭代的进行，惩罚因子逐渐增大，从而得到一系列的无约束优化问题。

本文利用外点罚函数法，将式(5-1)所示的优化问题转化为式(5-7)为目标函数的无约束优化问题，即将约束问题转化为一系列的无约束优化问题，再使用算法DLSSA求解转换后的无约束优化问题，从而得到算法PF-DLSSA。算法PF-DLSSA的求解过程主要为两个部分，即外层迭代及内层迭代。其中首先进行外层迭代，通过改变惩罚因子 $\lambda$ ，将约束优化问题转换为无约束优化问题；而后进行内层迭代，根据算法DLSSA的流程和位置更新机制进行领导者和追随者的位置更新，以及较差的个体淘汰及替换；内层迭代的终止条件为达到最大内层迭代次数T，然后判断其是否满足外层迭代的终止条件 $G\left(x\right)\le \epsilon$ 或 $k\ge 20$ ：若满足，则输出食物的位置及其适应度值；否则更新惩罚因子，进行下一次的迭代。

4.1. 算法PF-DLSSA的步骤

算法PF-DLSSA的步骤如下：

步骤1：初始化惩罚因子 $\lambda =1$ 及外层迭代精度 $\epsilon$ ，并设置外层迭代次数k = 0；

步骤2：根据约束优化问题中的目标函数、等式约束与不等式约束构造式(9)目标函数；

步骤3：种群初始化，设置种群中个体数量N，内层迭代最大次数T，并令当前内层迭代次数为t=0；

步骤4；按照式(9)计算每一个个体的适应度值，得到食物的位置及确定两个领导者的位置；

步骤5：领导者1按照公式(5)进行更新，迭代前期，即t小于T/2时领导者2按照(5)式更新，迭代后期，即t不小于T/2时按照式(6)进行位置更新；

步骤6：对每个追随者，先生成一个随机数以选择其追随的领导者，然后根据公式(7)进行位置更新；

步骤7：按照式(9)计算所有个体的适应度值，并比较当前最优个体与食物的适应度值：适应度值更小的则为新的食物的位置；

步骤8：对种群中适应度值大的10%的个体根据公式(8)进行位置更新，并令t=t+1；

步骤9：判断是否满足内层终止条件t = T：

若满足，则终止内层迭代；

否则，回到步骤4；

步骤10：判断是否满足外层迭代终止条件：

若满足则输出食物的位置及其适应度值；

否则，令外层迭代次数k = k + 1，更新惩罚因子并回到步骤2。

4.2. 算法PF-DLSSA的伪代码

算法PF-DLSSA的伪代码如下：

1. 设置惩罚项及外层迭代精度，外层迭代次数k=0；

2. 根据约束优化问题中的目标函数、等式约束与不等式约束构造式(9)目标函数；

3. 初始化种群，设置种群规模N，最大迭代次数T，当前内层迭代次数t=0；

4. 计算个体的适应度值，并确定食物的位置及两个领导者；

5. while $G\left(x\right)\le \epsilon$

6.while t < T

6.1 领导者1根据公式(5)进行位置更新；

If t < T/2

领导者2按照公式(5)进行位置更新；

Else

领导者2按照公式(6)进行位置更新；

End

6.2对每个追随者，先生成一个随机数以选择其追随的领导者，然后根据公式(7)进行位置更新；

6.3计算所有个体的适应度值，并比较当前最优个体与食物的适应度值：适应度值更小的则为新的食物的位置；

6.4对种群中适应度值大的10%的个体根据公式(8)进行位置更新；

6.5 Let t = t + 1.

7. End

8. Let k = k + 1

9. End

10. 输出食物的位置及其适应度值。

5. 数值实验

为检验算法PF-DLSSA求解约束优化问题的能力，本章选取了较为常用的6个约束优化问题进行了数值实验，6个约束优化问题的目标函数及约束条件及理论最优值在附录部分。

对比算法为算法PF-DLSSA与外点罚函数法结合原樽海鞘算法得到的算法PF-SSA。算法PF-SSA分为外层迭代与内层迭代，首先进行外层迭代，通过改变惩罚因子 $\lambda$ ，将约束优化问题转换为无约束优化问题；而后进行内层迭代，根据算法SSA的流程和位置更新机制进行领导者和追随者分别按照式(2-3)与式(2-5)进行位置更新；内层迭代的终止条件为达到最大内层迭代次数T，然后判断其是否满足外层迭代的终止条件或：若满足，则输出食物的位置及其适应度值；否则更新惩罚因子，进行下一次的迭代。

数值实验中，算法PF-DLSSA与算法PF-SSA种群规模均设置为100，内层最大迭代次数T为500，外层迭代次数最大值设为20，惩罚因子为10^k。为避免实验存在偶然性，对每一个问题进行30次的重复求解，30次求解所得到目标函数值的最好值，最差值，平均值及标准差见表1。

Table 1. Comparison results of objective function values for constrained optimization problems

表1. 约束优化问题目标函数值对比结果

见表1，对于所有问题，算法PF-DLSSA所求得的目标函数值均优于算法PF-SSA所求。对于问题c₁，算法PF-DLSSA在30次独立求解所得目标函数值的最好值为理论最优值，且标准差明显小于算法PF-SSA所求目标函数值的标准差。对于问题c₂，两算法均未在30次独立求解中求得理论最优值−1，但算法PF-DLSSA在30次独立求解中得到的目标函数最好值及平均值均小于−0.09，明显小于算法PF-SSA所求得的目标函数值。对于问题c₃与问题c₄，算法PF-SSA在30次独立求解中均不能在20次外层迭代中得到满足约束条件的解，而算法PF-DLSSA可以求得可行解，且对于问题c₃，算法PF-DLSSA在30次独立求解中得到的目标函数值的标准差较小。对于问题c₅，两个算法所得结果均较差，但算法PF-DLSSA所求得的目标函数值优于算法PF-SSA所求得的目标函数值。对于问题c₆，算法PF-DLSSA所求目标函数值的最好值接近理论最优值−15，而算法PF-SSA相较理论最优值相差很远。综上，算法PF-DLSSA求解无约束优化问题的性能好于算法PF-SSA。

6. 结论

本章介绍了约束优化问题的基本概念及其数学模型，同时介绍了一些求解约束优化问题的方法，即罚函数法、多目标函数法等。将改进所得算法DLSSA与外点罚函数法结合得到算法PF-DLSSA以用于约束优化问题的求解。为验证算法PF-DLSSA求解约束优化问题的性能，选取了6个约束优化问题进行数值实验，数值实验结果表明，数值实验的结果表明算法PF-DLSSA求解约束优化问题的性能好于算法PF-SSA。本文创新点如下：

1) 对樽海鞘算法进行改进得到求解无约束优化问题能力更优的算法DLSSA。

2) 提出一种基于改进的樽海鞘算法结合外点罚函数法的算法PF-DLSSA，以用以解决约束优化问题。

3) 选取标准测试问题进行数值实验，实验结果表明算法PF-DLSSA的求解约束优化问题的能力强于算法PF-SSA。

附录

6个约束问题如下：

C₁：

$\begin{array}{l}\min f\left(x\right)=x_1^2+{\left(x_2-1\right)}^2\\ s.t.h_1\left(x\right)=x_2-x_1^2=0,\\ -1\le x_1\le 1,-1\le x_2\end{array}$

全局最优值为0.75。

C₂

$\begin{array}{l}\min f\left(x\right)=-\frac{{\sin }^3\left(2\pi x_1\right)sin\left(2\pi x_2\right)}{x_1^3\left(x_1+x_2\right)}\\ \text{s}\text{.t}.g_1\left(x\right)=x_1^2-x_2+1\le 0\\ g_2\left(x\right)=-x_1+x_2-3\le 0\\ 0\le x_1\le 10,0\le x_2\le 10,\end{array}$

全局最优值为−0.095825。

C₃：

$\begin{array}{l}\min f\left(x\right)=-x_1-x_2\\ s.t.g_1\left(x\right)=-2x_1^4+8x_1^3-8x_1^2+x_2-2\le 0,\\ g_2\left(x\right)=-4x_1^4+32x_1^3-88x_1^2+96x_1+x_2-36\le 0,\\ 0\le x_1\le 3,0\le x_2\le 4\end{array}$

全局最优值为−5.508013。

C₄：

$\begin{array}{l}\min f\left(x\right)=x_1+x_2+x_3\\ s.t.g_1\left(x\right)=-1+0.0025\left(x_4+x_6\right)\le 92,\\ g_2\left(x\right)=1+0.0025\left(x_5+x_7-x_4\right)\le 0,\\ g_3\left(x\right)=-1+0.01\left(x_8-x_5\right)\le 0,\\ g_4\left(x\right)=-x_1{x}_6+833.33252x_4+100x_1-83333.333\le 0,\end{array}$

$\begin{array}{l}{g}_5\left(x\right)=-x_2{x}_7+1250x_5+x_2{x}_4-1250x_4\le 0,\\ g_6\left(x\right)=-x_3{x}_8+1250000{\left(x_2-2\right)}^2+x_3{x}_5-2500x_5\le 0,\\ 100\le x_1\le 10000,1000\le x_i\le 10000\left(i=2,3\right),10\le x_i\le 1000\left(i=4,5,6,7,8\right)\end{array}$

全局最优值为7049.3307。

C₅：

$\begin{array}{l}\min f\left(x\right)={\left(x_1-10\right)}^3+{\left(x_2-20\right)}^3\\ s.t.g_1\left(x\right)=-{\left(x_1-5\right)}^2-{\left(x_2-5\right)}^2+100\le 0,\\ g_2\left(x\right)=-{\left(x_1-6\right)}^2-{\left(x_2-5\right)}^2-82.81\le 0\\ \text{13}\le x_1\le 100,\text{0}\le x_2\le 100\end{array}$

全局最优值为−6961.81388。

C₆：

$\begin{array}{l}\min f\left(x\right)=5{\displaystyle \underset{i=1}{\overset{4}{\sum }}{x}_i-5{\displaystyle \underset{i=1}{\overset{4}{\sum }}{x}_i^2-{\displaystyle \underset{i=5}{\overset{13}{\sum }}{x}_i}}}\\ \text{s}\text{.t}\text{.}{g}_1\left(x\right)=2x_1+2x_2+x_{10}+x_{11}-10\le 0\\ g_2\left(x\right)=2x_1+2x_3+x_{10}+x_{12}-10\le 0\\ g_3\left(x\right)=2x_2+2x_3+x_{11}+x_{12}-10\le 0\end{array}$

$\begin{array}{l}{g}_4\left(x\right)=-8x_1+x_{10}\le 0\\ g_5\left(x\right)=-8x_2+x_{11}\le 0\\ g_6\left(x\right)=-8x_3+x_{12}\le 0\\ g_7\left(x\right)=-2x_4-x_5+x_{10}\le 0\end{array}$

$\begin{array}{l}{g}_8\left(x\right)=-2x_6-x_7+x_{11}\le 0\\ g_9\left(x\right)=-2x_8-x_9+x_{12}\le 0\\ 0\le x_i\le 1\left(i=1,\cdots ,9\right)0\le x_i\le 10\left(i=10,11,12\right)0\le x_{13}\le 1\end{array}$

全局最优值为−15。

NOTES

^*通讯作者。