徐焕芬，刘 伟，谢月珊

（广东工业大学应用数学学院，广东广州510520）

现实生活中的大部分优化问题都属于约束优化问题，因此研究高效求解约束优化问题的算法尤为重要。文献[1]提出利用参数方法处理等式约束，具有显著的效果，且运用遗传算法结合死亡罚函数对目标函数进行处理。但该方法存在明显的不足：对违反约束的值直接丢弃，导致算法易陷入局部最优且实验效果不稳定；文献[2]主要用罚函数法处理约束函数，然后在差异演化算法的基础上，改进约束条件处理机制和差异演化算法的运行参数以达到较好的收敛值,但存在随机性较大的问题；文献[3]对违反约束条件的候选解的离差统计信息和联赛选择机制进行了改进,并综合改进粒子群算法的变异策略，使该算法具有较优的群体智能搜索机制，但整体算法的稳定性不高；文献[4]选用最简单的静态罚函数法处理约束，并使用改进的混合蛙跳算法加强原函数的全局搜索能力，但使用静态罚函数法存在收敛效果差的问题；文献[5]提出利用静态罚函数与人工萤火虫算法进行结合，达到比较好的全局搜索效果，但该算法误差较大。

针对以上所存在的问题，结合文献[6]烟花算法处理投资优化组合的思想，本文提出一种新的求解约束优化问题的烟花算法。新的烟花算法选用参数方程法处理等式约束，使用退火罚函数法处理不等式约束，将求解约束优化问题转为求解无约束优化问题。

1 烟花算法

烟花算法是受实际生活中烟花爆炸产生火花的启发而提出的一种智能优化算法[7]，在这里烟花被视为可行域内的一个解向量，烟花爆炸产生的火花即解在其领域内的搜索过程。烟花算法的寻优性能主要是由爆炸算子、变异算子和选择策略决定，烟花算法其程序框图如图1所示。

图1 烟花算法流程图

1.1 烟花初始化

在烟花算法中，假设求解的问题为如下n维函数的无约束优化问题

其中Ω为可行域，在可行域内随机产生N个烟花，第i个烟花的位置为Xi=（x1，x2，…，xn），并计算每个烟花的适应值fi。

1.2 烟花爆炸操作

烟花爆炸操作，首先评价可行域中产生的烟花的适度值，然后再根据动态搜索思想[8-9]，使烟花的最大爆炸半径随着迭代次数的增加呈非线性递减，以达到前期侧重全局搜索，后期接近找到最优值时侧重局部搜索的目的，可有效提高算法的效率，最后根据这一思想对烟花爆炸的半径和爆炸数量进行设计[10-11]。

根据下式可计算第i个烟花的爆炸半径Ai及爆炸数量Si

其中，MaxIter代表最大迭代次数；curIter代表当前迭代次数；A代表当前迭代中最大的爆炸半径；Ainit代表最初时的爆炸半径；Afinal代表最末时的爆炸半径；ymin=min f（Xi）（i=1，2，…，N）代表当前烟花中适应值最小值；ymax=max f（Xi）（i=1，2，…，N）代表当前烟花中适应值最大值；S代表最大爆炸数量；ε代表一个非常小的数；式（3）表示较优烟花的搜索半径较小，执行局部搜索行为，较差的个体执行全局搜索行为；式（4）表示每一轮迭代质量较好的烟花可爆炸更多数量的火花，获得较多优质烟花。

烟花爆炸过程是对初始化的第i个烟花的第k维度按照该烟花的爆炸半径和爆炸数量，利用下式（5）更新烟花。为了保证烟花爆炸后产生的新火花在可行域范围内，利用下式（6）进行越界处理，将不可行解重新映射到可行域内。

1.3 烟花变异操作

烟花变异过程是按照高斯分布额外产生m个变异烟花，以达到增加种群多样性的目的，避免陷入局部最优。在初始化烟花中重新选择m个烟花，每个烟花随机选择z个维度进行高斯变异操作，按照下式（7）进行个体位置的更新。

其中，Gaussian（1，1）代表均值和方差均为1的高斯分布的随机数，代表第i个烟花的第k维度的值，该过程同样存在产生不可行解的情况，因此需要按式（6）对新产生的烟花进行越界处理。

1.4 烟花选择策略

经过烟花爆炸和变异后产生的烟花总数为K=N+S+m个，从K中选择N个新的烟花进入下一轮迭代。为了尽可能多的将优秀个体留下，将传统烟花算法的轮盘赌选择策略改用锦标赛策略[12]，使得烟花算法的迭代效率和迭代精度提高。

将该轮迭代中的最优烟花保留下来作为下一轮烟花进行迭代爆炸，然后在剩余的K-1个烟花中利用锦标赛策略选择N-1个烟花进行下一轮迭代。锦标赛的选择方式为：在K-1个烟花中有返回地随机抽取10个烟花进行锦标赛，适应值较小的烟花被保留下来，循环往复，直到N-1个烟花被选中后，停止操作进行下一轮的烟花爆炸操作。

2 求解约束优化问题的烟花算法

约束优化问题标准形式为

其中，gi为不等式约束函数，hj为等式约束函数，Q为不等式约束的个数，M为等式约束的个数。

2.1 不等式约束条件处理

退火精度罚函数法是处理不等式约束最常用的方法之一[13-14]，它通过对约束条件施加惩罚，从而将求解不等式约束优化问题转变为求解无约束优化问题。退火精度罚函数法选取方式为

其中，σk=1/T，T=T*α，α∈（0，1），该罚函数法引入模拟退火的思想，使得在进化过程中 σk不断增大，使解趋于可行。该罚函数法克服了传统罚函数算法需要计算梯度的缺点，实用性较大。

2.2 等式约束条件处理

实际应用中通常接触到含等式约束的优化问题，这类问题的解决方法要么将一个等式约束变成两个不等式约束去求解，要么是使用松弛变量法[15]，即在等式一边加上一个比较小的ε，使其变成不等式约束，这两种方法都存在处理等式约束函数最优解与真实解之间误差较大的问题。为解决以上方法所存在的缺陷，本文引用参数方程法[16]。

参数方程法中，在M个等式约束hi中选择n-M个x的分量作为参数，得到M个参数方程，然后解参数方程组，不失一般性，假设x1，x2，…，xn-M为参数，式（8）参数方程组的解为

将参数方程组的解代到不等式约束和目标函数中得到降维后的目标函数和不等式约束。参数法处理等式约束可以使原本复杂的函数变得更简单，更易求得目标函数的最优值，从而使收敛速度和收敛精度提高。

2.3 新算法流程

求解约束优化问题的烟花算法步骤如下：

（1）设置参数，种群大小为N个，种群维度为n，规定最大迭代次数为MaxIter，当前迭代次数为curIter，上下界分别为Lb和Ub；

（2）初始化种群，确定N个烟花的位置，并判断烟花是否越界，若越界则按照式（6）处理；

（3）约束处理：利用参数方程法处理等式约束，使用退火罚函数法处理不等式约束，计算每个烟花的适应值fi（i=1，2，…，N）；

（4）对每个烟花的适度值进行评估，根据式（3）、（4）计算爆炸半径Ai和爆炸数量Si；

（5）将N个烟花根据式（5）、（7）进行爆炸和变异操作，得到S个爆炸火花和m个变异火花，并判断该爆炸和变异火花是否越界，若越界则按照式（6）处理。将可行解与不可行解分别排序；

（6）判断若存在可行解，则保留最优可行解；若不存在可行解，则保留不可行解中最优个体。根据锦标赛选择策略思想选取N-1个烟花进入下一轮迭代；

（7）若满足终止条件，则结束算法，否则转步骤（4）。

3 数值仿真

3.1 只含不等式约束的优化问题处理

为了评价本文所提出新算法的性能，选用只含不等式约束的测试函数F1、F2、F3、F4。将新的烟花算法（记为FA）的测试效果与文献[17]改进的粒子群算法（记为PSOA）、文献[18]改进的差分算法（记为DE）进行比较，如表1所示，三种算法的进化曲线图如图2～5所示。

本次测试结果运用MATLAB进行编程，设置最大迭代次数MaxIter为100，初始化种群个数N为100，试验次数为50次。

表 1 F1、F2、F3、F4 优化计算结果

图2 F1进化曲线图

图3 F2进化曲线图

图4 F3进化曲线图

图5 F4进化曲线图

对表1中的三种算法进行比较，从均值和最优值可以看出，新算法的最优值最接近精确值，且在误差精度下均能找到最优可行解，稳定性好；文献[17]改进的粒子群算法无论对线性约束优化函数还是非线性约束优化函数都能找到目标精度下的最优解；文献[18]改进的差分算法虽然可以直接找到精确值，但从成功率上可知找到最优可行解的随机性较大。从三种算法的进化曲线图（图2～5）可以看出，新算法具有不断寻找更优值的能力，而粒子群算法前期容易陷在不可行域上的局部最优，难以成功跳出局部最优的陷阱，差分算法对单峰函数效果不佳，但对于多峰函数则具有跳出局部最优的能力。

3.2 含等式约束的优化问题处理

为了测试新算法处理等式约束问题的性能，本文选用含等式约束的线性测试函数F5和非线性测试函数F6。

本次测试结果运用MATLAB进行编程，设置最大迭代次数MaxIter为100，初始化种群个数N为100，试验次数为50次。对F5和F6使用参数方程法进行处理得到测试函数F'5、F'6

3.2.1 处理含等式约束方法比较

新烟花算法（FA）使用参数方程法处理等式约束，将测试结果与使用松弛变量法处理等式约束的烟花算法（记为SC）作比较，如表2所示，两种算法的进化曲线图如图6～7所示。

表2 使用参数方程法前、后的烟花算法比较

从表2的均值和最优值数据可以看出，同样是结合烟花算法，使用参数方程降维后的最优值更接近精确值，可达到95%左右的成功率，算法效果较稳定；使用松弛变量法成功率不高，随机性较大，稳定性差。

图6 F5进化曲线图

图7 F6进化曲线图

将使用参数方程法和使用松弛变量法的进化曲线图（图6～7）进行比较可以看出，前者的收敛速度更快，且呈一直下降趋势，而后者在20代左右就已经陷入局部最优。

3.2.2 新算法处理含等式约束优化问题性能分析

由上述实验结果可知，使用参数方程法有利于提高算法的求解精度和收敛速度。为了检验新算法处理含等式约束优化问题性能，本文用新算法与文献[17]改进的粒子群算法（记为PSOA）、文献[18]改进的差分算法（记为DE）作比较，如表3所示。

表3 F5、F6优化计算结果

从表3可以看出，使用参数方程法处理等式约束能有效提高算法的求解精度。在这三种随机算法中，新算法的最优值与精确值之间的误差最小，且以高达95%的成功率达到本文的精度要求，说明算法稳定性好；而同样目标精度，粒子群算法和差分算法求解成功率只有80%左右，说明随机性偏大。新算法虽然在前期一直搜寻不到可行解，但具有可以不断寻找最优值的能力，而粒子群和差分难以跳出局部最优。

4 结语

本文提出求解约束优化问题的烟花算法，烟花算法比传统算法有更高的求解精度，并在此基础上加入参数方程法降维处理等式约束，且使用退火精度罚函数法处理约束。数值实验表明，新算法拥有更强的寻优能力，使用范围更广，是一种稳健的求解约束优化问题的新算法。