求解约束优化新的引力搜索算法

吴施豫+钱伟懿

摘要： 针对约束优化问题，提出了一种新的引力搜索算法。在该算法中，对每一个粒子定义两个质量，一是“可行质量”另一个是“不可行质量”。若对可行粒子更新，则采用可行质量；否则采用不可行质量。其目的使可行粒子向目标函数值好的方向发展，使不可行粒子向可行域方向发展。最后对5个测试函数进行数值实验，数值结果表明提出的算法是可行的、有效的。

Abstract： A new gravitational search algorithm is proposed for constrained optimization problem. In this algorithm， two mass are defined for each particle， "feasible mass" and "infeasible mass". If feasible particles are updated， feasible mass is used； otherwise， infeasible mass is used. Its purpose is to make feasible particles develop to the direction of good objective function value， and the infeasible particles develop to the direction of feasible domain. Finally， the numerical experiments of five test functions are carried out. The numerical results show that the proposed algorithm is feasible and effective.

关键词： 引力搜索算法；约束优化；违反约束度；全局优化

Key words： gravitational search algorithm；constraint optimization；violation of constraint；global optimization

中图分类号：TP301.6 文献标识码：A 文章编号：1006-4311（2017）12-0205-02

1 概述

本文考虑如下约束优化问题：

min f（x）

s.t. gi（x）？燮0，i=1，2，3…q

hj（x）=0，j=q+1，q+2，…m（1）

lk？燮xk？燮uk，k=1，2，…，n

其中x=（x1，x2，…xn）∈Rn为决策向量，整体搜索空间 ？赘={x∈Rn|lk？燮xk？燮uk，k=1，2，…，n}，可行域為S={x∈？赘|gi（x）？燮0，hj（x）=0，i=1，2，…q，j=q+1，…，m}，f（x）：S？奂Rn→R是一实值目标函数。问题（1）经常出现在科学和工程等领域，因此它在优化问题中起到重要作用。 解决约束优化问题的常用有确定性和随机性两种方法。 由于一些问题中存在目标函数或约束函数不可微等问题，从而导致确定性方法具有一定局限性，因此，近年来一些随机性优化方法被广泛应用到求解约束优化问题。最近，Rashedi 等人提出一种新的启发式优化算法，称为引力搜索算法[1]（Gravitational Search Algorithm，简称GSA），自从GSA被提出后，一些学者利用GSA来求解约束优化问题。Pal 等人利用GSA算法使用修复方法解决约束优化问题[2]。 Mondal等人使用GSA通过重新初始化不可行的粒子来解决约束优化问题[3]。Yadav 和Deep给出求解约束优化问题的引力搜索算法[4]。刘勇和马良对灰色非线性约束优化问题给出了GSA方法[5]。 Poole等人[6]提出了一种有效的约束处理方法，通过可行群和不可行群分别优化目标函数和约束违反程度，但是该方法当不可行的粒子更新时，可行解的目标函数的信息尚未被充分考虑。基于目标函数和约束违反度，本文对每个粒子定义两个质量，一个是“可行质量”，另一个是“不可行质量”。当可行粒子更新时，在GSA中使用“可行质量”，当不可行粒子更新时使用“不可行质量”。其目的当粒子可行时使其向好的适应值方向进化，当粒子不可行时向可行域方向进化。数值结果表明所提出的算法是有效的。

2 改进的引力搜索算法

GSA是一个用于求解全局优化问题的群体启发式方法。在GSA中，搜索区域中的每个解被视为具有一定质量的粒子。根据目标函数值定义其质量，基于牛顿引力定律定义粒子间的引力，在引力作用下，粒子在搜索空间内向质量大的粒子移动，即向具有较好目标函数值的粒子移动。由于GSA最初用于解决盒子约束优化问题，所以定义的质量只与目标函数有关，对于解决一般约束优化问题，对质量定义必须进行新的研究。因此本文对每个粒子定义两个质量，从而提出新的引力搜索算法。

假设粒子群体由N个粒子组成，第i（i=1，2，…，N）个粒子在t时刻的位置和速度分别为x■■=（x■■，x■■，…x■■）和v■■=（v■■，v■■，…v■■）其中x■■和v■■分别表示第i个粒子在第d维空间上的位置和速度。

设粒子x违反第j个约束的程度为

Hj（x）=max{gj（x），0}， j=1，2，…，qmax{hj（x）-■，0} j=q+1，…，m（2）

其中？着 >0为等式约束允许的估值，则粒子x违反约束程度定义如下：H（x）=■Hj（x）（3）

假设粒子i在t时刻是“可行”，即x■■∈S，则定义他的可行质量为mi（t）=■（4）

FMi（t）=■（5）

不可行质量为■■（t）=1+■（6）

IMi（t）=■（7）

其中fitnessbest（t）表示在t时刻粒子在S中最好的适应值；fitnessworst（t）表示t时刻粒子粒子在中S最差的适应值。

假设粒子i在t时刻是“不可行”，即x■■？埸S，则定义他的可行质量为FMi（t）=0（8）

不可行质量为■■（t）=■（9）

IMi（t）=■（10）

其中，Hbest（t）=■{H（x■■）}，Hworst（t）=■{H

（x■■）}。

粒子i对粒子j的引力定义如下：

F■■（t）=G（t）■（x■■-x■■）（11）

其中d=1，2，…n，G（t）=G0e■，G0表示万有引力的初始值，？琢为常数，Mi（t）表示粒子i的质量，T表示最大迭代次数，t表示当前迭代次数，？着是一个很小的常量，Rij=■ Xi，Xj ■ 表示第i个粒子和第j个粒子之间的欧氏距离。

作用在粒子粒子i上的引力为

F■■（t）=■randj×F■■（t）（12）

其中Kbest按较好适应值从N线性递减到1，rand是[0，1]之间的随机数。

根据运动法则，粒子i在第d维空间上的加速度为

a■■=■（13）

粒子i的速度和位置更新公式如下：

v■■=randi×v■■+a■■（14）

x■■=x■■+v■■（15）

由（5）、（8）和（11）式可以看出，对“可行”粒子操作时，“不可行”粒子对其没有影响，而质量越大的可行粒子对其影响越大，从而使其向适应值较好方向进化.由（7），（10），和（11）式可以看出，对“不可行”粒子操作时，“可行”粒子对其影响最大，而违反约束程度越小的不可行粒子对其影响也大，从而使其向可行域方向进化。改进GSA步骤如下：

步骤1：设置各参数，在？赘内随机初始化粒子的位置和速度，计算粒子的适应值或违反约束程度，保存当前最优可行解Pg，若没有可行粒子，令Pg为无穷大。令t=0；

步骤2： 判断粒子i（i=1，2，…，N）是否在S内，若在S内，计算各粒子的可行质量，用可行质量代替粒子质量，否则计算各粒子的不可行质量，用不可行质量代替粒子质量；

步骤3：按（12）计算粒子i的引力；

步骤4：按（13）式计算计算粒子i的加速度；

步骤5：按（14）和（15）式更新粒子i的速度和位置；

步骤6：计算各粒子的适应值和违反约束程度，更新当前最好的可行解Pg；

步骤7： 判断是否满足最大迭代步，若满足，则输出Pg；否则令t=t+1，转步骤2。

3 数值实验

为了评价改进算法（简称，IGSA）的性能，我们选取文献[7]中的5个测试函数进行实验研究并与其他算法进行比较。

从表1可以看出，对于测试函数G1和G4，IGSA算法与3S-MGSA算法都能够找到问题的最优解，而GSA算法不能够找到最优解。对于测试函数G2和G3，IGSA算法優于其他两种算法。对于测试函数G5，IGSA算法不如3S-MGSA算法，但优于GSA算法。总体来说，IGSA算法有较好的寻优能力，在解决约束优化问题方面具有更好的性能。

4 结束语

本文所提出的方法不需要使用惩罚函数，并且也不同于文献[2]的方法。我们在GSA中定义了粒子的可行的质量和不可行的质量，可行的质量可以引导可行粒子向全局最优解方向搜索，不可行的质量可以引导不可行粒子向可行区域方向搜索，从而提高了算法解决约束优化问题的性能。在未来研究中，我们将研究更好处理约束的方法，并应用到一些启发式算法中。

参考文献：

[1]Rashedi， E. Nezamabadi-pour， H.， Saryazdi， S. GSA： A gravitational search algorithm [J]. Information Sciences， 2009， 179（13）： 2232-2248.

[2]Pal，K. Saha，C. Das，S. et al. Dynamic constrained optimization with offspring repair based gravitation search algorithm [C]// Proc. CEC14， Cancun， Mexico： 2013： 2414-2421.

[3]Mondal S. Bhattacharya A. Halder S. Solution of cost constrained emission dispatch problems considering wind power generation using gravitational search algorithm [C]// Proc. ICAESM， Nagapattinam India： IEEE Press， 2012：169-174.

[4]Yadav A. Deep K. Constrained optimization using gravitational search algorithm [J]. National Academy Science Letters， 2013， 36（5）：527-534.

[5]刘勇，马良.灰色非线性约束规划的改进引力搜索算法求解[J].数学的实践与认识，2013，43（7）：99-103.

[6]Poole， D. J. Allen C. B. Rendall T. C. S. Analysis of constraint handling methods for the gravitational search algorithm [C]// Proc. CEC14， Beijing， China： IEEE Press， 2014： 2005-2012.

[7]Efren M. M. Coello C. A. C. A simple multimembered evolution strategy to solve constrained optimization problems [J]. IEEE Transactions on Evolutionary Computation， 2005， 9（1）： 1-17.