文章快速检索  
  高级检索
基于余弦相似度反向策略的自然计算方法
孙小琳, 季伟东, 王旭    
哈尔滨师范大学大学计算机科学与信息工程学院, 黑龙江 哈尔滨 150025
摘要: 现有的基于反向策略的优化算法大多根据初始种群适应度值大小进行反向择优,没有充分考虑迭代过程中的反向且存在收敛速度慢的问题。针对此问题,提出一种基于余弦相似度反向策略的快速收敛自然计算方法,通过计算每个粒子与区域中心粒子的余弦相似度,将粒子划分为相似子群与非相似子群,对非相似子群按照相似程度进行加权反向,进而加快收敛速度,同时引入柯西扰动提高种群多样性。将该策略应用到三种不同的自然计算方法中,对收敛性进行分析,并采用12个经典测试函数验证其性能,对实验数据进行非参数检验。分析结果表明,应用余弦相似度反向策略的方法在大多数测试函数上表现优异,说明提出的方法具有很好的普适性和有效性。
关键词: 自然计算    快速收敛    余弦相似度    加权反向    
Natural Computation Method Based on Cosine Similarity Opposition Strategy
SUN Xiaolin, JI Weidong, WANG Xu    
College of Computer Science and Information Engineering, Harbin Normal University, Harbin 150025, China
Abstract: Most of the existing optimization algorithms based on the opposite learning strategy are under the initial population fitness value. The problem of opposition and slow convergence is not fully considered. Thus, a fast convergent natural computation method based on a cosine similarity opposition strategy is proposed to solve the aforementioned problem. The particles are divided into similar and nonsimilar subgroups by calculating the cosine similarity between each particle and the particle in the regional center. The nonsimilar subgroups are weighted opposition according to the similarity degree, thus the convergence speed is accelerated. The Cauchy disturbance is then introduced to improve population diversity. The strategy is applied to three different natural computing methods, and 12 classical test functions are used to analyze the convergence and verify its performance. Finally, nonparametric tests are performed on the experimental data. Experiments show that the method performs well in most test functions and has good universality and effectiveness.
Keywords: natural computation    fast convergence    cosine similarity    weighted opposition    

0 引言

自然计算(natural computation)通常是指那些试图从信息处理的角度来理解世界,受自然启发而形成的智能算法[1]。自然计算方法能够借鉴自然界的功能与作用机理,抽象出计算模型,如进化计算、生物分子计算、量子计算、模糊计算和情感计算等[2]。每种自然计算方法都对应各自实际的启发源[3],如植物生长算法对应植物的生长过程,灰狼算法、鲸鱼算法对应动物捕食行为等。自然计算方法具有自适应、自组织、自学习的特点[4],目前已广泛应用于许多领域,如模式识别与图像处理领域中基于遗传算法和自组织映射的模糊混合智能彩色图像分割方法[5],基于反向混沌变异的文本聚类特征选择算法[6]等;身份识别领域中交通拥堵识别的模糊识别算法[7],基于多目标的空间搜索算法识别模糊推理系统[8]等;医学领域中利用遗传算法的无符号基因排序[9],使用多目标进化策略的DNA核酸编码设计[10]等。除此以外还有基于灰狼算法的目标威胁评估[11],基于量子遗传的视觉目标跟踪[12],基于粒子群优化的室内定位[13]和基于萤火虫算法增强图像对比度[14]等应用。

虽然各种自然计算方法模拟的生物机理不同,但它们都是基于种群的优化方法[15]。针对算法收敛速度慢、易陷入局部最优等问题,为提高算法性能,学者们提出了很多解决方案,反向学习(opposition-based learning,OBL)[16]就是其中之一。尽管反向学习的思想简单,但在很多算法中都表现出了很好的性能。Rahnamayan等[17]首次将OBL与差分进化(differential evolution,DE)算法进行结合。受此启发,Wang等[18]将OBL应用于粒子群(particle swarm optimization,PSO)算法。而Iqbal等[19]则将OBL应用于遗传算法(genetic algorithm,GA)解决函数优化问题。Ewees等[20]将DE与OBL相结合,并将其应用于鲸优化算法进行多目标优化。Chen等[21]使用OBL初始化种群并利用正余弦加速系数(sine cosine acceleration coefficients,SCAC)指导函数寻优。上述算法中,利用OBL种群进行初始化时,是在搜索空间中先计算解的反向值,然后反向解与原解比较,选择最优元素进行后续迭代寻优,从而选出最优解。而Feng等[22]将OBL应用于果蝇算法(fruit fly optimization algorithm,FOA)中,并设计了动态收缩参数策略调整反向学习强度。Dhargupta等[23]将OBL与灰狼算法(grey wolf optimization,GWO)相结合,每次迭代中使用皮尔逊相关系数选择反向候选解。Xing等[24]提出了动态广义反向学习和即时策略有效优化狼群算法。除此之外,孙辉等[25]提出了混合均值中心反向学习粒子群优化算法,对混合均值中心进行OBL,从而扩大搜索区域。Rahnamayan等[26]以整个种群重心作为参考点计算反向解,提出了重心反向学习(centroid oppotion-based learning,COBL)。受COBL的启发,周凌云等[27]使用邻域重心作为参考点计算反向。邵鹏等[28]提出折射原理反向学习模型。罗强等[29]对全局最优粒子逐维进行重心反向学习。这些改进算法均产生了很好的效果,在全局探索能力、收敛速度、计算精度上都有显著提高,表明反向学习策略是一种十分有效的方法。但它们大多是针对某一特定算法在种群初始化时使用反向学习策略,且依赖算法具体实现过程,普适性不强。

受以上方法启发,本文提出一种普适的基于余弦相似度反向学习(cosine similarity opposition-based learning,CSOBL)的快速收敛进化计算方法。首先,在迭代过程中,计算每个个体与区域中心个体的余弦相似度,根据其值将种群划分为相似种群与非相似种群。其次,根据非相似种群中每一个体与区域中心个体的相似程度对其进行加权反向计算,在加快收敛速度的同时增加了种群多样性。最后对种群最优个体进行柯西扰动,增加变异范围,进一步提高种群多样性。将本策略运用到3种不同的自然计算方法中,采用12个标准测试函数验证其性能,并与目前主流反向优化算法进行对比,用以验证基于余弦相似度反向策略的普适性和有效性。

1 余弦相似度与反向学习 1.1 余弦相似度

余弦相似度[30]是一种相关性度量方法,它是通过测量两个向量夹角的余弦值来度量它们之间的相似性,从而确定两个向量是否大致指向相同的方向。余弦相似度注重的是两个向量在方向上的差异,因此,对于高维空间,余弦相似度能够很好地度量两个向量之间的相关性。其相关定义为[31]:设D维空间中的两个可行解XY对应的向量分别为X=(x1x2,…,xD),Y=(y1y2,…,yD),那么它们之间的余弦相似度由式(1)确定,3维空间中两个向量的余弦相似度图像如图 1所示。

(1)
图 1 3维空间中两个向量的余弦相似度 Fig.1 The cosine similarity of two vectors in the three-dimensional space

其中,θ为向量XY之间的夹角,xi(i=1,2,…,D)为向量X在第i维的属性值,yi(i=1,2,…,D)为向量Y在第i维的属性值,D为问题空间的维度。cos θ∈[-1, 1],余弦相似度越靠近1表明两个向量的夹角越接近0,即两个向量越相似。反之,余弦相似度越靠近-1,表明两个向量越不相似。

1.2 反向学习策略

如果某个体离最优解很远,那么它的反向个体可能具有更好的适合度值[16]。反向学习定义为:假设X=(x1x2,…,xD)是D维空间中的某一可行解对应的向量,且xj∈[ajbj](j=1,2,…,D),则其对应的反向解向量X*=(x1*x2*,…,xD*)由式(2)确定,1维空间中反向解的位置如图 2所示。

(2)
图 2 1维空间反向 Fig.2 Opposition in the one-dimensional space
2 余弦相似度反向自然计算方法 2.1 余弦相似度反向策略

目前,数据规模庞大且大都具有多维特性[32],因此,本算法采用适用于多维数据的余弦相似度反向来度量问题空间中某一个体与全部个体的平均位置的相似程度。相关定义为:设问题空间中个体Xi对应的向量为(xi1xi2,…,xiD),其中i=1,2,…,N。每次迭代过程中全部个体的平均位置对应的中值向量μ=(μ1μ2,…,μD)如式(3)所示:

(3)

其中,N表示问题空间中全部个体的数目,j=1,2,…,D

个体Xi的余弦相似度可以定义为此个体对应的向量Xi与中值向量μ之间的余弦相似度,余弦相似度越接近1,说明此个体与平均位置的相似度越高,计算方法如式(4)所示。

(4)

其中,D为问题空间的维度,μj为中值向量第j维的值,xij为个体Xij维的值。

根据个体的余弦相似度,对个体进行相关性选择,相关性选择的分类阈值分别设置为-1/2,0,1/2。前期实验表明,分类阈值为0时寻优结果最佳,故本文选取0为相关性选择分类阈值。若个体的余弦相似度系数小于0,表明这些个体与中值向量的相似度很小,将这些个体归类为非相似种群,并根据余弦相似度系数对其进行加权反向。反向候选解Xi*的各维属性值按式(5)计算:

(5)

其中,aj为问题空间的下界,bj为问题空间的上界,S(Xi)为个体Xi的余弦相似度。

在基于余弦相似度的反向过程中,使用了动态收缩策略调整反向学习权重,任一个体与中值个体的相似度值越小,表示个体与中值个体越不相似,向量之间的夹角越大,相似度值的绝对值越大,则进行反向加权收缩后,反向粒子的位置离中值粒子越近。由于余弦相似度是基于方向性的相似程度度量,所以非相似种群中的个体能够避免不必要的反向,快速向中值个体靠拢,同时保证了种群的多样性。为直观描述描述反向过程,本文仅画出处于非相似子群中的3个个体,它们反向后的具体位置如图 3所示,其中,μ表示中值向量个体的位置,Xi(i= 1,2,…,N)表示任一个体,Xi*(i=1,2,…,N)表示余弦反向后的个体。

图 3 非相似子群个体经余弦相似度反向学习后的位置 Fig.3 Positions of individuals in non-similar subgroups after cosine similarity opposition-based learning
2.2 柯西扰动

当个体陷入局部最优时,由图 4可知,柯西分布的两端延伸能够产生距中心较远的随机数,柯西算子能以更高的概率跳出局部最优,且变异后的个体与原个体具有较大差异。因此,为了使个体具有更强的搜索能力,本算法使用柯西变异机制[33]对全局最优个体位置进行变异扰动。

图 4 高斯分布和标准柯西分布概率密度函数曲线 Fig.4 Probability density function curves of Gaussian distribution and standard Cauchy distribution

标准柯西分布概率密度如下[34]

(6)

本算法的变异概率随迭代次数增加而减小,减少变异值以避免最优值的动荡,从而更可能探寻新区域,帮助提高种群的多样性,使搜索能够跳出局部最优区域,增大发现最优解的概率。对最优个体的柯西变异如下:

(7)

其中,gbi为第i代的全局最优个体,gbi为当前最优个体经柯西扰动后的新值,C为生成的柯西变异随机数。

2.4 余弦相似度反向策略

余弦相似度反向策略流程如图 5所示。

图 5 余弦相似度反向策略流程图 Fig.5 The flow chart of cosine similarity opposition-based strategy

基于余弦相似度反向策略的算法步骤见算法1。

算法1   基于余弦相似度反向的自然计算方法
输入:相关参数;
输出:最优解
1. 在给定区域内随机初始化种群pop,种群规模N,维数D等参数
2. 计算当前种群pop中个体的适应度值fitness;
3. 根据相应公式产生下一代种群pop1
4. 根据式(3)计算中值向量μ位置,式(4)计算个体jμ的相似程度;
5. 若相似程度 < 0,则将pop1划分为相似子群s与非相似子群;
6. 根据式(5),计算的余弦反向;
7. 根据式(6)以一定概率对全局最优柯西扰动;
8. 判断算法是否达到结束条件,若结束,则返回最优解;否则,转步骤3。

3 算法时间复杂度与收敛性分析 3.1 算法时间复杂度分析

从算法1的描述中可以看出,基于余弦相似度反向的计算方法主要包含以下部分:初始化种群并计算适应度值、速度与位置更新操作、余弦相似度反向策略、柯西变异操作。设种群规模为N,目标函数维数为D,最大迭代次数为Gmax。易知,初始化种群并计算适应度值的时间复杂度为O(ND),速度与位置更新操作以及柯西变异的时间复杂度为O(GmaxND),余弦相似度反向策略分为两个部分,分别是计算余弦相似度和根据余弦相似度权重反向。其中计算余弦相似度需要的时间复杂度为O(Gmax((N+1)D))=O(GmaxND);进行位置更新时条件判断以及权重反向的时间复杂度也是O(N)级别的时间复杂度。综上,本算法的总的时间复杂度为O(N)级别。

3.2 算法的收敛性分析

定义1    个体在可行解空间中的随机运动位置称为个体状态,在迭代中的所有可能状态称为个体状态空间,记为X[35]

定义2    对于问题〈Sf〉,采用某随机优化算法M,对于个体x,第t次迭代的结果为xk,则t+1代为xt+1=M(xtζ),其中,S表示解空间,f表示适应度函数,ζ表示曾搜索过的解。那么在Lebesgue空间中,搜索下界:

(8)

其中,v(X)为集合X上的Lebesgue测度,则最优解可定义为

(9)

其中,c表示充分大的正数,ξ>0,若算法M在迭代过程中找到了Rξ中的某个解,那么就认为算法M找到了可以接受的全局最优解[36]

条件1    f(M(xζ))≤f(x),且若ζSf(M(xζ))≤f(ζ)。

条件2[37]    对∀AS,s. t. v(A)>0,有:

(10)

其中,vt(A)表示解在空间A上,算法M在第t次迭代过程中能够找到解的概率测度。

定理1    对于任意渐近收敛算法,CSOBL算法不会破坏原算法的渐近收敛性。

证明    对于任意渐近收敛算法,符合条件1,即渐近收敛算法中每个个体的第t+1次最优位置一定优于第t次最优位置,同时符合条件2,即在任意多次迭代后,算法以概率为1收敛。对于CSOBL算法,余弦相似度取值在-1到1之间,所以每个个体以概率P=1/2反向,个体位置更新公式:

(11)

其中,xt+1*为个体位置更新的中间结果,对于任意渐近收敛算法,个体在一次迭代后的位置为

(12)

即CSOBL算法符合条件1,CSOBL算法不会破坏原始渐近收敛算法的渐近收敛性。定理1得证。

定理2    CSOBL算法满足渐近收敛准则。

证明   由定理1可知,在CSOBL算法中,总是有f(xt+1)≤f(xt),在迭代次数足够多时,f(xt)会逐渐逼近最优值,即lim f(xt)=f(gtbest),其中gtbest为算法第t迭代中的全局最优值位置。因此可以得到:

(13)

所以有:

(14)

即CSOBL算法满足条件2,所以CSOBL算法最终以概率为1收敛至迭代最优值gbest。定理2证毕。

4 仿真实验与结果分析

实验仿真环境为Intel® CoreTM,CPU@3. 30 GHz,RAM 16,Windows 10,Matlab 2020a。本实验把CSOBL策略分别应用于标准粒子群算法[38]、标准遗传算法[39]和灰狼算法[40]中,得到CSOPSO、CSOGA和CSOGWO,并与PSO、GA、GWO和几个经典基于反向优化算法进行对比。为了测试应用了本文所提出策略的算法性能,选取了表 1中的12个经典测试函数进行仿真实验分析,表 1给出了经典测试函数的表达式、搜索范围和理论最优值。单峰函数F1~F4F12只有一个全局最优点,因此适合作为算法开发的基准。多峰函数F5~F11具有大量的局部最优点,求解难度较高。

表 1 经典测试函数 Tab.1 Classical test function
函数名称 测试函数 搜索范围 最优解
Sphere [-100, 100] 0
Rosenbrock [-5, 10] 0
dixon-price [-10, 10] 0
sum of different powers [-1, 1] 0
Ackley [-32.76,32.76] 0
Rastrigin [-5.12,5.12] 0
Griewank [-600, 600] 0
Powell [-4, 5] 0
Levy [-10, 10] 0
Schwefel [-500, 500] 0
Alpine
[-10, 10] 0
sum squares [-10, 10] 0
4.1 CSOBL策略与标准算法的实验结果分析 4.1.1 参数设置

为了比较结果的公平性,实验参数设置如下:PSO算法和CSOPSO算法的参数设置为:加速因子c1=c2=2,惯性权重ω由0. 9到0. 4线性递减,最大迭代次数FEs=1 000,种群规模N=50,维数D=30;GA算法和CSOGA算法的参数设置为:交叉概率Pc=0. 70,变异概率Pm=0. 05,最大迭代次数FEs=1 000,种群规模N=50,维数D=30;GWO算法和CSOGWO算法的参数设置为:种群规模N=100,最大迭代次数FEs=1 000,维数D=30。

4.1.2 实验结果及分析

各算法对12个标准测试函数分别独立运行10次,记录各算法的平均值、最优值、标准差等结果,用于评价算法的性能。将改进算法与其对应的标准算法进行比较,结果如表 2所示,其中加黑部分表示结果更接近最优解。从表 2的结果可以看出,应用了本文所提出策略的综合算法在大部分测试函数中的表现明显优于标准算法的结果。对于得到的优化结果来说,在10个函数上CSOPSO比PSO的寻优结果更接近最优值,3个函数优势不明显。在8个函数上CSOGA比GA的寻优结果更接近最优值,4个函数优势不明显。在5个函数上CSOGWO比GWO的寻优结果更接近最优值,3个函数优势不明显,4个函数二者表现相同。比较结果充分说明了余弦相似度反向策略较标准算法更具优势。这是因为余弦相似度反向策略充分利用了余弦相似度的方向特性,保证了种群的多样性,提高了计算精度,一定程度上避免了陷入局部最优。另外,本文对各测试函数进行了收敛性测试,并给出了它们的收敛比较图,横坐标表示种群迭代次数,纵坐标表示平均适应度值,如图 6所示。从图 6的收敛走势图中可以看出,函数F1~F7F11的收敛速度十分迅速,同时,F1F4F6F7F11F12的收敛速度迅速下降且并未趋于稳定,在迭代次数较少的情况下即可找到全局最优解,这是因为使用余弦相似度调整反向学习权重能够在保证多样性的情况下迅速向最优解靠拢,从而进一步说明了余弦相似度反向策略能够强化局部区域的搜索能力,避免不必要的反向,从而使算法具有更快的收敛速度。但在函数F11中,收敛速度提高不大,这是由于函数本身是具有多个局部最优值导致的,使得算法收敛速度相对较慢。

表 2 各算法对12个标准测试函数优化结果 Tab.2 The optimization results of various algorithms on 12 test functions
函数 特征 平均结果及标准方差
PSO CSOPSO GA CSOGA GWO CSOGWO
F1 均值 1.57×101 0 1.94×103 0 1.32×10-84 0
方差 9.28×100 0 3.69×102 0 2.34×103 1.84×103
F2 均值 8.95×101 2.63×101 2.27×103 1.60×103 2.71×101 2.50×101
方差 7.20×101 1.10×101 2.03×103 1.23×102 5.35×104 3.72×104
F3 均值 5.57×100 6.67×10-1 5.48×102 8.01×10-1 6.67×10-1 6.67×10-1
方差 2.59×100 3.58×10-2 6.81×102 7.35×101 4.60×104 3.96×104
F4 均值 6.09×10-10 0 1.25×10-9 0 0 0
方差 1.79×10-8 2.38×10-8 1.13×10-6 1.90×10-9 3.25×10-2 1.56×10-2
F5 均值 4.16×100 8.88×10-16 1.08×101 8.88×10-16 7.99×10-15 8.88×10-16
方差 6.22×10-1 0 8.43×10-1 0 2.01×100 6.48×10-1
F6 均值 3.94×101 0 1.18×102 0 0 0
方差 1.96×101 1.53×101 1.80×101 0 4.91×101 2.71×101
F7 均值 1.04×100 0 1.93×101 0 0 0
方差 1.53×10-1 0 3.54×100 0 2.28×101 2.25×101
F8 均值 1.21×100 1.06×10-3 3.13×101 7.16×10-1 8.35×10-7 1.10×10-6
方差 4.30×101 2.92×100 2.22×101 9.31×100 5.24×102 4.14×102
F9 均值 6.01×10-1 4.58×10-6 1.31×101 2.23×100 1.16×100 6.59×10-1
方差 7.77×10-1 3.53×10-1 1.33×101 6.21×10-2 7.57×101 3.31×101
F10 均值 3.86×103 1.76×102 7.08×103 6.79×103 6.06×103 5.92×103
方差 6.99×102 1.86×102 3.16×102 1.12×103 9.86×102 1.30×103
F11 均值 8.92×10-1 2.68×10-70 1.05×101 0 7.28×10-48 0
方差 1.95×100 2.97×100 1.81×100 0 3.82×100 1.94×100
F12 均值 3.36×100 0 1.83×102 0 2.55×10-86 0
方差 6.13×100 0 4.62×101 0 4.14×102 1.94×100
图 6 经典测试函数优化的收敛曲线 Fig.6 Convergence curves for optimization of classical test functions
4.2 CSOGWO与其他应用OBL策略的算法实验结果分析

COPSO[26]是应用了重心反向策略的粒子群算法,DCOPSO[29]是对最优粒子逐维重心反向的粒子群算法,OGA-CM[19]是应用了反向学习和柯西变异的遗传算法,ODE[17]是基于反向学习的差分进化算法,OLGWO[41]是Long等提出的反向学习灰狼算法。将CSOGWO与上述文献中的进化算法进行对比。为了与文献中的结果保持一致,各算法的种群大小设置为60,最大迭代次数设置为500,每个函数的维数都设置为30,其他参数均与原论文相同。结果如表 3所示,其中加黑部分表示结果更接近最优解。从表 3中可以直观地看到,CSOGWO在5个测试函数中找到了最优解,在6个测试函数中的寻优结果优于其他5个算法。基于余弦相似度的反向是方向性的,能够在快速收敛的同时保证种群多样性,提高计算精度。算法加入柯西扰动,能够增强全局搜索能力,进一步提高种群多样性,很大程度上避免种群陷入局部极值。但是CSOGWO在测试函数F2F9中取得的成果不理想,这是因为在多维的情况下,函数相关系数太多,无法精确地进行余弦反向。

表 3 各算法的实验对比结果 Tab.3 The experimental comparison results of various algorithms
测试函数 COPSO DCOPSO OGA-CM ODE OLGWO CSOGWO
F1 1.28×10-12 5.67×10-27 1.84×103 5.57×10-30 2.06×10-54 0
F2 3.87×10-2 4.91×100 4.51×103 5.29×10-17 1.97×10-28 2.70×101
F5 7.86×10-8 3.99×10-14 1.18×101 2.81×101 2.88×101 8.88×10-16
F6 1.24×10-12 0 1.42×102 0 0 0
F7 8.86×10-13 0 2.24×101 3.96×10-3 1.57×10-6 0
F9 4.65×10-2 1.00×10-4 2.38×101 2.97×10-31 1.05×10-51 4.46×10-1
F11 7.96×10-9 6.12×10-9 1.14×101 2.07×10-26 9.05×10-48 0
F12 2.36×10-12 3.05×10-27 2.56×102 5.10×101 0 0
4.3 非参数检验

为了对实验结果有一个更加全面的了解,对CSOGWO和其他算法的结果逐一进行非参数检验[42]。选用Mann-Whitney检验方法,显著水平p=0. 05。由于文[36]不包含ODE和OLGWO的检验数据,故在此省略。表 4列出了其余3种算法的检验数据。以“COPSO”列与“F1”行交叉的数据“0. 013↑”为例,其中,“0. 013”为Mann-Whitney检验的渐近显著性值,“↑”表示COPSO在F1上运行数据的秩均值大于CSOGWO在F1上运行数据的秩均值。

表 4 Mann-Whitney检验结果 Tab.4 The result of Mann-Whitney test
测试函数 COPSO DCOPSO OGA-CM
F1 0.013↑ 1.000↑ 0.000↑
F2 1.000↓ 0.728↑ 0.000↑
F5 0.001↑ 0.341↑ 0.000↑
F6 0.068↓ 1.000↓ 0.000↑
F7 0.061↑ 0.683↓ 0.000↑
F9 1.000↓ 0.007↓ 0.077↓
F11 0.023↑ 0.023↑ 0.000↑
F12 0.013↓ 1.000↓ 0.000↑
劣于对比算法个数 1 1 0
与对比算法无明显差异个数 4 5 1
优于对比算法个数 3 2 7

表 4可以看出CSOGWO劣于对比函数的次数明显较少,检验结果表明,在统计意义上应用了本文所提策略的算法明显占优。同时结合表 3及以上分析,可以说明余弦相似度反向策略有效提高了算法的收敛速度与精度。

5 结论

本文提出一种基于余弦相似度反向的快速收敛策略提高种群的全局搜索能力,通过大量的理论分析和实验结果表明,本策略具有快速收敛能力,且能够保证种群多样性,能够带领种群探索更大的空间范围,找到精度更高的解。将其与三种自然计算方法结合,与标准算法和基于反向学习策略的改进算法进行比较,选取12个测试函数验证其普适性和有效性。实验结果表明,与其他先进的反向学习算法相比,应用所提策略的算法具有更好的竞争力,表现出了很好的结果。但是,对于某些并非对单一个体进行变异的算法,本文策略具有一定的局限性。因此在后续的研究工作中,考虑将余弦相似度与欧氏距离结合,改进算法性能。

参考文献
[1]
Kari L, Rozenberg G. The many facets of natural computing[J]. Communications of the ACM, 2008, 51(10): 72-83. DOI:10.1145/1400181.1400200
[2]
康琦, 安静, 汪镭, 等. 自然计算的研究综述[J]. 电子学报, 2012, 40(3): 548-558.
Kang Q, An J, Wang L, et al. Nature-inspired computation: A survey[J]. Acta Electronica Sinica, 2012, 40(3): 548-558.
[3]
莫宏伟, 徐立芳. 自然计算与计算主义[C]//第十一届中国人工智能学术年会. 北京: 北京邮电大学出版社, 2005: 210-215.
Mo H W, Xu L F. Natural computing and computationalism[C]//The 11th China Annual Conference on Artificial Intelligence. Beijing: Beijing University of Posts and Telecommunications Press, 2005: 210-215.
[4]
汪镭, 张永韡, 郭为安, 等. 自然计算发展趋势研究[J]. 微型电脑应用, 2010, 26(7): 1-5, 10.
Wang L, Zhang Y W, Guo W A, et al. On development trends of nature inspired computing[J]. Microcomputer Applications, 2010, 26(7): 1-5, 10. DOI:10.3969/j.issn.1007-757X.2010.07.001
[5]
Khan A, Jaffar M A. Genetic algorithm and self organizing map based fuzzy hybrid intelligent method for color image segmentation[J]. Applied Soft Computing, 2015, 32: 300-310. DOI:10.1016/j.asoc.2015.03.029
[6]
Bharti K K, Singh P K. Opposition chaotic fitness mutation based adaptive inertia weight BPSO for feature selection in text clustering[J]. Applied Soft Computing, 2016, 43: 20-34. DOI:10.1016/j.asoc.2016.01.019
[7]
Yang Y F, Cui Z M, Wu J, et al. Fuzzy c-means clutering and opposition-based reinforcement learning for traffic congestion identification[J]. Journal of Information and Computational Science, 2012, 9(9): 2441-2450.
[8]
Huang W, Oh S K. Identification of fuzzy inference systems by means of a multiobjective opposition-based space search algorithm[J/OL]. Mathematical Problems in Engineering, 2013[2021-06-21]. https://www.hindawi.com/journals/mpe/2013/725017/. DOI: 10.1155/2013/725017.
[9]
da Silveora L A, Soncoo-Álvarez J L, de Lima T A, et al. Memetic and opposition-based learning genetic algorithms for sorting unsigned genomes by translocations[M]//Advances in Intelligent Systems and Computing, vol. 419. Berlin, Germany: Springer, 2015: 73-85.
[10]
张凯, 陈彬, 许志伟. 基于多目标进化策略算法的DNA核酸编码设计[J]. 电子与信息学报, 2020, 42(6): 1365-1373.
Zhang K, Chen B, Xu Z W. A multiobjective evolution strategy algorithm for DNA sequence design[J]. Journal of Electronics & Information Technology, 2020, 42(6): 1365-1373.
[11]
傅蔚阳, 刘以安, 薛松. 基于灰狼算法与小波神经网络的目标威胁评估[J]. 浙江大学学报(工学版), 2018, 52(4): 680-686.
Fu W Y, Liu Y A, Xue S. Target threat assessment using grey wolf optimization and wavelet neural network[J]. Journal of Zhejiang University (Engineering Science), 2018, 52(4): 680-686.
[12]
金泽芬芬, 侯志强, 余旺盛, 等. 基于量子遗传算法的视觉目标跟踪[J]. 电子学报, 2020, 48(8): 1493-1501.
Jin Z F F, Hou Z Q, Yu W S, et al. An object tracking approach based on quantum genetic algorithm[J]. Acta Electronica Sinica, 2020, 48(8): 1493-1501.
[13]
李泽, 田增山, 王中春, 等. 基于粒子群优化的多径辅助室内定位算法[J]. 电子学报, 2020, 48(10): 1952-1960.
Li Z, Tian Z S, Wang Z C, et al. Multipath-assisted indoor localization algorithm based on particle swarm optimization[J]. Acta Electronica Sinica, 2020, 48(10): 1952-1960.
[14]
Draa A, Benayad Z, Djenna F Z. An opposition-based firefly algorithm for medical image contrast enhancement[J]. International Journal of Information and Communication Technology, 2015, 7(4/5): 385-405. DOI:10.1504/IJICT.2015.070299
[15]
王蓉芳, 焦李成, 刘芳, 等. 自适应动态控制种群规模的自然计算方法[J]. 软件学报, 2012, 23(7): 1760-1772.
Wang R F, Jiao L C, Liu F, et al. Nature computation with self-adaptive dynamic control strategy of population size[J]. Journal of Software, 2012, 23(7): 1760-1772.
[16]
Tizhoosh H R. Opposition-based learning: A new scheme for machine intelligence[C]//International Conference on Computational Intelligence for Modelling, Control and Automation and International Conference on Intelligent Agents, Web Technologies and Internet Commerce. Piscataway, USA: IEEE, 2005: 695-701.
[17]
Rahnamayan S, Tizhoosh H R, Salama M M A. Opposition-based differential evolution algorithms[C]//IEEE International Conference on Evolutionary Computation. Piscataway, USA: IEEE, 2006: 2010-2017.
[18]
Wang H, Wu Z J, Rahnamayan S, et al. Enhancing particle swarm optimization using generalized opposition-based learning[J]. Information Sciences, 2011, 181(20): 4699-4714.
[19]
Iqbal M A, Khan N K, Jaffar M A, et al. Opposition based genetic algorithm with Cauchy mutation for function optimization[C/OL]//International Conference on Information Science and Applications. Piscataway, USA: IEEE[2021-05-15]. https://ieeexplore.ieee.org/document/5480382/. DOI: 10.1109/ICISA.2010.5480382.
[20]
Ewees A A, Elaziz M A, Oiego D. A new multi-objective optimization algorithm combined with opposition-based learning[J/OL]. Expert Systems with Applications, 2021, 165[2021-05-20]. https://www.sciencedirect.com/science/article/pii/S0957417420306539. DOI: 10.1016/j.eswa.2020.113844.
[21]
Chen K, Zhou F Y, Yin L, et al. A hybrid particle swarm optimizer with sine cosine acceleration coefficients[J]. Information Sciences, 2018, 422: 218-241.
[22]
Feng X Y, Liu A, Sun W L, et al. A dynamic generalized opposition-based learning fruit fly algorithm for function optimization[C/OL]//IEEE Congress on Evolutionary Computation. Piscataway, USA: IEEE[2021-02-21]. https://ieeexplore.ieee.org/document/8477794/. DOI: 10.1109/CEC.2018.8477794.
[23]
Dhargupta S, Ghosh M, Mirjalili S, et al. Selective opposition based grey wolf optimization[J/OL]. Expert Systems with Applications, 2020, 151[2021-04-14]. https://www.sciencedirect.com/science/article/pii/S095741742030213X?via%3Dihub. DOI: 10.1016/j.eswa.2020.113389.
[24]
Dhargupta S, Ghosh M, Mirjalili S, et al. Selective opposition based grey wolf optimization[J/OL]. Expert Systems with Applications, 2020, 151[2021-05-01]. https://www.mdpi.com/1999-4893/11/4/47. DOI: 10.1016/j.eswa.2020.113389.
[25]
孙辉, 邓志诚, 赵嘉, 等. 混合均值中心反向学习粒子群优化算法[J]. 电子学报, 2019, 47(9): 1809-1818.
Sun H, Deng Z C, Zhao J, et al. Hybrid mean center opposition-based learning particle swarm optimization[J]. Acta Electronica Sinica, 2019, 47(9): 1809-1818.
[26]
Rahnamayan S, Jesuthasan J, Bourennani F, et al. Computing opposition by involving entire population[C]//IEEE Congress on Evolutionary Computation. Piscataway, USA: IEEE, 2014: 1800-1807.
[27]
周凌云, 丁立新, 彭虎, 等. 一种邻域重心反向学习的粒子群优化算法[J]. 电子学报, 2017, 45(11): 2815-2824.
Zhou L Y, Ding L X, Peng H, et al. Neighborhood centroid opposition-based particle swarm optimization[J]. Acta Electronica Sinica, 2017, 45(11): 2815-2824.
[28]
邵鹏, 吴志健, 周炫余, 等. 基于折射原理反向学习模型的改进粒子群算法[J]. 电子学报, 2015, 43(11): 2137-2144.
Shao P, Wu Z J, Zhou X Y, et al. Improved particle swarm optimization algorithm based on opposite learning of refraction[J]. Acta Electronica Sinica, 2015, 43(11): 2137-2144.
[29]
罗强, 季伟东, 徐浩天, 等. 一种最优粒子逐维变异的粒子群优化算法[J]. 小型微型计算机系统, 2020, 41(2): 259-263.
Luo Q, Ji W D, Xu H T, et al. Particle swarm optimization with global best particle dimension-by-dimension mutation[J]. Journal of Chinese Computer Systems, 2020, 41(2): 259-263.
[30]
Koufakou A, Georgiopoulos M. A fast outlier detection strategy for distributed high-dimensional data sets with mixed attributes[J]. Data Mining and Knowledge Discovery, 2010, 20(2): 259-289.
[31]
Han S, Zhao C, Meng W X, et al. Cosine similarity based fingerprinting algorithm in WLAN indoor positioning against device diversity[C]//IEEE International Conference on Communications. Piscataway, USA: IEEE, 2015: 2710-2714.
[32]
刘爱琴, 张继福, 荀亚玲. 基于大熵值变化区域和余弦相似度的离群迭代算法[J]. 小型微型计算机系统, 2013, 34(7): 1518-1521.
Liu A Q, Zhang J F, Xun Y L. Outlier iteration algorithm based on large entropy vary and cosine similarity[J]. Journal of Chinese Computer Systems, 2013, 34(7): 1518-1521.
[33]
Wang H, Li C H, Liu Y, et al. A hybrid particle swarm algorithm with Cauchy mutation[C]//IEEE Swarm Intelligence Symposium. Piscataway, USA: IEEE, 2007: 356-360.
[34]
何庆, 林杰, 徐航. 混合柯西变异和均匀分布的蝗虫优化算法[J]. 控制与决策, 2021, 36(7): 1558-1568.
He Q, Lin J, Xu H. Hybrid Cauchy mutation and uniform distribution of grasshopper optimization algorithm[J]. Control and Decision, 2021, 36(7): 1558-1568.
[35]
张孟健, 龙道银, 王霄, 等. 基于马尔科夫链的灰狼优化算法收敛性研究[J]. 电子学报, 2020, 48(8): 1587-1595.
Zhang M J, Long D Y, Wang X, et al. Research on convergence of grey wolf optimization algorithm based on Markov chain[J]. Acta Electronica Sinica, 2020, 48(8): 1587-1595.
[36]
Solis F J, Wets R J B. Minimization by random search techniques[J]. Mathematics of Operations Research, 1981, 6(1): 19-30.
[37]
孙小晴, 程昊, 张潞瑶, 等. 一种基于空间分割搜索策略的自然计算方法[J]. 系统仿真学报, 2021, 33(11): 2589-2605.
Sun X Q, Cheng H, Zhang L Y, et al. A natural computing method based on spatial division search strategy[J]. Journal of System Simulation, 2021, 33(11): 2589-2605.
[38]
Kennedy J, Eberhart R. Particle swarm optimization[C]//International Conference on Neural Networks. Piscataway, USA: IEEE, 1995: 1942-1948.
[39]
孟凡超, 初佃辉, 李克秋, 等. 基于混合遗传模拟退火算法的SaaS构件优化放置[J]. 软件学报, 2016, 27(4): 916-932.
Meng F C, Chu D H, Li K Q, et al. Solving SaaS components optimization placement problem with hybrid genetic and simulated annealing algorithm[J]. Journal of Software, 2016, 27(4): 916-932.
[40]
Mirjalili S, Mirjalili S M, Lewis A. Grey wolf optimizer[J]. Advances in Engineering Software, 2014, 69: 46-61.
[41]
Long W, Jiao J J, Liang X M, et al. A random opposition-based learning grey wolf optimizer[J]. IEEE Access, 2019, 7: 113810-113825.
[42]
Derrac J, Garcíab S, Molina D, et al. A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms[J]. Swarm and Evolutionary Computation, 2011, 1(1): 3-18.
http://dx.doi.org/10.13976/j.cnki.xk.2022.1318
中国科学院主管,中国科学院沈阳自动化研究所、中国自动化学会共同主办。
0

文章信息

孙小琳, 季伟东, 王旭
SUN Xiaolin, JI Weidong, WANG Xu
基于余弦相似度反向策略的自然计算方法
Natural Computation Method Based on Cosine Similarity Opposition Strategy
信息与控制, 2022, 51(6): 708-718.
Information and Control, 2022, 51(6): 708-718.
http://dx.doi.org/10.13976/j.cnki.xk.2022.1318

文章历史

收稿/录用/修回: 2021-07-21/2021-09-29/2022-02-25

工作空间