惯性质量衰减的引力搜索算法

钱伟懿, 张丽佳

(渤海大学 数理学院, 辽宁 锦州 121013)



运筹学与控制论

惯性质量衰减的引力搜索算法

钱伟懿, 张丽佳

(渤海大学 数理学院, 辽宁 锦州 121013)

针对引力搜索算法易陷入局部最优的缺点,提出一种惯性质量衰减的引力搜索算法。 该算法认为粒子的惯性质量有一定衰减,把粒子惯性质量的衰减率看成一个模糊变量,用其隶属度函数定义惯性质量的衰减率,把衰减率与粒子惯性质量乘积作为粒子的惯性质量,从而提高算法的开发能力。另外,为了提高算法的探索能力,给出一个新的变异算子。最后,把所提出算法应用到经典测试函数中,并与引力搜索算法及其他改进的引力搜索算法比较,数值结果表明所给出的算法能够提高求解精度和收敛速度。

引力搜索算法; 隶属度函数; 变异算子; 全局优化

在过去几十年中,研究人员从自然现象中得到启发,提出了许多启发式优化算法。例如,遗传算法[1]、蚁群优化算法[2]、粒子群优化算法[3-4]、模拟退火法[5]、人工蜂群算法[6]等。这些算法都是针对某些特定问题,目前尚没有哪一种算法能够成功地解决所有的优化问题。因此,探索新的算法十分必要。

引力搜索算法(Gravitational search algorithm, GSA)是一种新的启发式优化算法,在2009年,首先被Esmat等人提出[7-8],其原理源于对万有引力进行模拟产生的群体智能优化算法。目前引力搜索算法得到了广泛应用,如流水线调度[9]、模糊聚类[10-11]、滤波器的建模[12], 引起许多学者的关注。

Sun等人基于引力搜索算法和遗传算法提出了一种混合GSA算法[13]。曹茂俊等人[14]在引力搜索算法中融合量子计算提出了一种改进的引力搜索算法。Tsai等人提出了一种引力粒子群算法[15],该算法通过粒子群优化算法的速度更新公式和GSA加速度更新公式的结合提出一种新速度更新公式。张明等人把小生境技术引入到引力搜索算法中给出一种基于小生境技术的改进引力搜索算法[16]。徐遥等人对粒子的惯性质量附加一个权值,提出了基于权值的引力搜索算法[17]。隋永霞等人提出基于高斯变异的引力搜索算法[18]。王奇琪等人引入斥力,提出了基于斥力的引力搜索算法[19]。这些算法未对惯性质量进行研究,但随着时间推移粒子的惯性质量有一定衰减,故本文给出惯性质量衰减系数,该系数看成模糊变量,用其隶属度函数表示,质量衰减系数乘以惯性质量代替原惯性质量。为提高群体多样性,引入一个新的变异算子,在每次迭代中,以概率p实行新变异算子的位置更新,以概率(1-p)实施引力搜索算法位置更新,从而有效平衡了算法的探索能力和开发能力, 数值结果验证了算法的有效性。

1 引力搜索算法

GSA是基于牛顿的万有引力定律和运动定律为基本原理的启发式算法。在GSA中把可行域中的解看成一个粒子,粒子的惯性质量由粒子的适应值决定,适应值越好的粒子其质量越大,相反,适应值越差的粒子其质量越小。根据粒子的质量和粒子间的距离定义万有引力,粒子在万有引力作用下在可行域内朝着惯性质量大的粒子运动,即朝着较好的适应值运动,从而得到全局最优解。

在一个D维的搜索空间中,假设有N个粒子,定义第i个粒子的位置为

设第i个粒子在t时刻的质量为Mi(t),其表达式如下:

(1)

(2)

其中fiti(t)表示粒子i在t时刻的适应值,对于求最小值问题,best(t)和worst(t)定义如下:

(3)

(4)

根据万有引力定律,在时刻t,粒子j对粒子i在d维上的作用力定义如下:

(5)

其中:Rij(t)为粒子i和粒子j之间的欧氏距离;ε是指非常小的常数;G(t)是t时刻的引力常数,定义如下:

(6)

其中:G0为一个初始值;α为一个常数;t为当前迭代数;tmax为最大迭代次数.

作用在第i个粒子在d维上的作用力定义如下:

(7)

其中randj是[0,1]之间的随机数,kbest从N到1随着时间t线性地减小,使得算法到最后在搜索空间中只有最好的解的那个粒子去作用于其他的粒子。

(8)

粒子i在第d维上的速度和位置更新如下:

(9)

(10)

其中randi是[0,1]之间的随机变量。

2 质量衰减的GSA

随着时间的推移,粒子的质量要有一定的衰减,本文把粒子质量衰减率看成一个模糊变量,模糊变量取决于他的隶属度函数,本文基于高斯函数、钟型函数、Sigmoid函数定义质量的衰减率,第i粒子在t时刻质量衰减率φi(t)定义如下:

若质量衰减率隶属度函数基于高斯函数建立的,则

(11)

若质量衰减率隶属度函数基于钟型函数建立的,则

(12)

若质量衰减率隶属度函数基于Sigmoid函数建立的,则

(13)

其中Pt表示t时刻最好位置,β为一参数,定义如下:

β=best(t)/log(1+t)

显然t越大,β越小,从而质量衰减率越小,质量衰减越快。粒子i在t时刻衰减后的质量为

(14)

表1 测试函数

对于极小问题,粒子j的适应值越差(目标函数值大),其质量衰减率越小,从而衰减后质量越小,对其他粒子引力越小,相反,粒子j的适应值越好(目标函数值小),其质量衰减率越大,从而衰减后质量大,对其他粒子引力越大。该策略在算法后期可能导致陷入局部最优,为此给出一种新的变异算子

(15)

1) 设置算法中的参数,随机初始化粒子的位置及速度,计算粒子的适应值,确定最好粒子;

2) 按式(1),式(2),式(3)和式(4)计算每个粒子的惯性质量;按式(6)计算引力常数;

3) 按式(11)或式(12)或式(13)计算惯性质量衰减率,按式(14)计算衰减后质量;

4) 按式(5)和式(7)计算每个粒子的引力;

5) 按式(8)计算加速度;

6) 按式(9)更新粒子的速度;

7) 在[0,1]中随机选取一个随机数r,若r

8) 计算每个粒子适应值,更新最好粒子;

9) 若算法满足终止条件,则输出最好适应值,否则转步2.

3 数值实验

为检验本文算法性能,选用文献[20]中10个基准测试函数进行实验。实验在MATLAB7.0,Windows 7操作系统,2.00GB RAM 内存和2.10 GHz CPU环境下运行所有程序,且每个实验独立运行30次。表2给出了实验所用到的基准测试函数,其中:D表示函数的维数;Ω是搜索区间;fopt表示最优值。

表2 衰减率为高斯函数、钟型函数、Sigmoid函数的GSA的比较结果

表2显示的是基于不同衰减率本文算法的数值结果,其中:G-GSA,B-GSA和S-GSA分别表示质量衰减率为高斯函数、钟型函数、Sigmoid函数定义的质量衰减的GSA;best、worst、mean和std分别表示30次实验中最好适应值、最差适应值、平均适应值和标准差。

表3 B-GSA与GSA,GSAGJ和QGSA比较结果

从表2可以看出,对于最好适应来说,在函数F7和F9上G-GSA优于其他2种算法,在函数F3,F4,F5,F6和F10上B-GSA优于其他2种算法,在F1,F2和F8上S-GSA优于其他2种算法;对于最差适应值来说,在函数F9上G-GSA优于其他2种算法,在函数F3,F4,F5,F6,F7和F10上B-GSA优于其他2种算法,在F1,F2和F8上S-GSA优于其他2种算法;对于平均适应值来说,在函数F6和F9上G-GSA优于其他2种算法,在函数F3,F4,F5,F7和F10上B-GSA优于其他2种算法,在F1,F2和F8上S-GSA优于其他2种算法.综合考虑可以看出,B-GSA优于其他2种算法。

用B-GSA与GSA,GSAGJ[17]和QGSA[18]3种算法进行比较.比较结果见表3。从表3可以看出,B-GSA与GSA相比,对于最好适应值的指标,在函数F3,F4,F6,F7和F9上B-GSA优于GSA,在函数F1,F2和F8上B-GSA略好于GSA,但在F5和F10上GSA优于B-GSA;对于最差适应值指标,在函数F1,F3,F4,F5,F6,F7,F9和F10上B-GSA优于GSA,在函数F2和F8上B-GSA略好于GSA;对于平均适应值指标,在函数F1,F3,F4,F5,F6,F7,F9和F10上B-GSA优于GSA,在函数F2和F8上B-GSA略好于GSA。B-GSA与GSAGJ相比,对于最好适应值的指标,在函数F3,F4,F6,F7和F9上B-GSA优于GSAGJ,在函数F2和F8上B-GSA略好于GSA,但在F5和F10上GSAGJ优于B-GSA,在函数F1上GSAGJ略优于B-GSA;对于最差适应值指标,在函数F1,F3,F4,F5,F6,F7,F9和F10上B-GSA优于GSAGJ,在函数F2上B-GSA略好于GSAGJ;对于平均适应值指标,在函数F3,F4,F5,F6,F7,F9和F10上B-GSA优于GSAGJ,在函数F1,F2和F8上B-GSA略好于GSAGJ.B-GSA与QGSA相比,对于最好适应值来说,在函数F1,F3,F4,F5,F6,F9和F10上,B-GSA优于QGSA,在函数F8上,B-GSA略优于QGSA,但在函数F2和F7上,QGSA优于B-GSA,对于适应值最差来说,在函数F1,F3,F4,F5,F9和F10上,B-GSA优于QGSA,在函数F2和F8上,B-GSA略优于QGSA,但在函数F7上,QGSA优于B-GSA,在函数F6上,QGSA略优于B-GSA;对于平均适应值来说,在函数F1,F3,F4,F5,F9和F10上,B-GSA优于QGSA,在函数F8上,B-GSA略优于QGSA,但在函数F6和F7上,QGSA优于B-GSA,在函数F2上,QGSA略优于B-GSA。对于标准差来说,除了函数F5和F10外,B-GSA都有较好稳定性.综上所述,B-GSA提高了算法的寻优能力和求解精度。

为比较各算法性能,图1～图6分别表示4种算法在函数F1,F3,F5,F7,F9,F10上的适应值收敛曲线。

图1 函数F1的寻优曲线

图2 函数F3的寻优曲线

图3 函数F5的寻优曲线

图4 函数F7的寻优曲线

从图1～图6中可以看出,B-GSA在函数F3,F9,F10的收敛速度上明显优于其他3种算法,在函数F1和F5上,B-GSA的收敛速度相差不多,在函数F7上,QGSA明显优于其他3种算法,总之,B-GSA能够提高了算法的收敛速度。

图5 函数F9的寻优曲线

图6 函数F10的寻优曲线

4 小 结

在引力搜索算法(GSA)中,引力搜索算法易陷入局部最优,为提高算法的探索与开发能力,用隶属度函数定义粒子质量的衰减率并给出一个新的变异算子,从而提出了惯性质量衰减的引力搜索算法。数值实验结果显示所提出的算法在求解精度与收敛速度明显优于标准引力搜索算法、基于权值的引力搜索算法及基于高斯变异的引力搜索算法。在未来的工作中,进一步研究更好的衰减率。

[ 1 ]TANG K, MAN K, KWONG S, et al. Genetic algorithms and their applications[J]. IEEE Signal Process Mag, 1996,13(6):22-37.

[ 2 ]DORIGO M, MANIEZZO V, COLORNI A. The ant system: optimization by acolony of cooperating agents[J]. IEEE Trans Syst Man Cybern B, 1996,26(1):29-41.

[ 3 ]BERGH F, ENGELBRECHT A. A study of particle swarm optimization particle trajectories[J]. Inf Sci, 2006,176(8):937-971.

[ 4 ]KENNEDY J, EBERHART R. Particle swarm optimization[C]∥Proceedings of IEEE International Conference on Neural Networks, Perth WA: IEEE Press, 1995:1942-1948.

[ 5 ]KIRKPATRICK S, GELATTO C, VECCHI M P. Optimization by simulated annealing[J]. Science, 1953,220:671-680.

[ 6 ]KARABOGA D, BASTURK B. On the performance of artificial bee colony(ABC) algorithm[J]. Appl Soft Comput, 2008,8(1):687-697.

[ 7 ]RASHEDI E, NEZAMABADI-POUR H, SARYAZDI S. GSA: a gravitational search algorithm[J]. Inf Sci, 2009,179(13):2232-2248.

[ 8 ]RASHEDI E, NEZAMABADI-POUR H, SARYAZDI S. BGSA: binary gravitational search algorithm[J]. Nat Comput, 2010,9(3):727-745.

[ 9 ]谷文祥,李向涛,朱磊,等. 求解流水线调度问题的万有引力搜索算法[J]. 智能系统学报, 2010,5(5):411-418.

[10]RASHEDI E, NEZAMABADI-POUR H, SARYAZDI S. Filter modeling using gravitational search algorithm[J]. Eng Appl Artif Intell, 2011,24(1):117-122.

[11]YIN M,HU Y, YANG F, et al. A novel hybrid K-harmonic means and gravitational search algorithm approach for clustering[J]. Expert Syst Appli, 2011,38(8):9319-9324.

[12]刘伯颖,张素琪,张丽丽. 一种引力搜索和K-means的混合聚类算法[J]. 河北工业大学学报, 2013,42(3):23-27.

[13]SUN G, ZHANG A. A hybrid genetic algorithm and gravitational search algorithm for image segmentation using Multilevel Thresholding[J]. Pat Recognit Image Anal, 2013,7887:707-714.

[14]曹茂俊,李盼池,尚福华. 量子行为引力搜索算法[J]. 控制与决策, 2016,31(9):1678-1684.

[15]TSAI H C, TYA N Y Y, WU Y W, et al. Gravitational Particle Swarm[J]. Appl Math Comput, 2013,219(17):9106-9117.

[16]张明,田娜,纪志成,等. 基于小生境技术的改进引力搜索算法[J]. 南京航空航天大学学报, 2016,48(5):753-760.

[17]徐遥,王士同. 引力搜索算法的改进[J]. 计算机工程与应用, 2011,47(35):188-192.

[18]隋永霞,孙合明. 基于高斯变异的引力搜索算法[J]. 江南大学学报(自然科学版), 2015,14(5):596-600.

[19]王奇琪,孙根云,王振杰等. 基于斥力的引力搜索算法[J]. 计算机科学, 2015,42(9):240-245.

[20]YAO X, LIU Y, LIN G. Evolutionary programming made faster[J]. IEEE Trans Evol Comput, 1999,3(2):81-102.

Gravitational search algorithm with inertial mass attenuation

QIAN Weiyi, ZHANG Lijia

(College of Mathematics and Physics, Bohai University, Jinzhou 121000, China)

In order to overcome the shortcomings that gravitational search algorithm (GSA) traps into local optima easily, a gravitational search algorithm with inertial mass attenuation is proposed. In this algorithm, the particle’s inertial mass is considered to have certain attenuation, the attenuation rate of particle's inertial mass is regarded as a fuzzy variable, the attenuation rate is defined based on membership functions, the particle’s inertial mass is redefined by the product of attenuation rate and particle’s inertial mass. Such exploitation ability of the proposed algorithm is improved. In addition, a new mutation operator is proposed to improve the exploration ability. Finally, the proposed algorithm is tested on several benchmark test functions and compared with GSA and the other improved GSA. The numerical results indicate that the proposed algorithm can improve the convergence speed and precision.

gravitational search algorithm; membership function; mutation operator; global optimization

1673-5862(2017)02-0138-07

2017-02-06。

国家自然科学基金资助项目(11371071); 辽宁省教育厅科学研究一般项目(L2013426)。

钱伟懿(1963-),男,辽宁锦州人,渤海大学教授,博士。

TP18

A

10.3969/ j.issn.1673-5862.2017.02.003