当前位置:首页 期刊杂志

一种自适应混沌蜂群优化算法研究∗

时间:2024-05-04

马济乔 李 越 华明宇 许立海

(中国人民解放军63602部队 酒泉 735000)

1 引言

近年来,在优化领域中出现了一种新的随机搜索方法—蜂群算法,它具有全局寻优能力强的优点,被广泛应用于优化问题。文献[1]设计了一种混沌局部搜索算子,提高了算法的寻优效率;文献[2]提出了一种基于改进人工蜂群算法的盲信号分离方法。文献[3~6]将人工蜂群算法应用到支持向量机的优化中,并取得了很好的优化效果。

虽然人工蜂群算法在优化领域取得了很好的成绩,但是其在快搜索到全局最优值时,样本的多样性减少,搜索速度减慢,容易陷入局部最优值。为此,本文提出一种自适应混沌蜂群算法,在不影响蜂群算法全局寻优的同时,提高蜂群全局的寻优速度并克服蜂群算法容易陷入局部最优的不足,通过对测试函数寻优结果的对比分析,验证了该算法的优越性。

2 蜂群算法的基本原理

2.1 蜂群算法

蜜蜂属于群居昆虫,单个个体的行为通常比较简单,但是群体却表现出了极其复杂的行为。在实际生活中,蜜蜂可以在任何环境下,以一种非常高的效率获取食物,而且它们能够随着环境的变化而改变觅食行为和交流方式。蜂群算法与求解最优问题的对应关系如表1所示。

表1 蜂群算法与求解最优值的关系

在蜂群算法中,蜜源的位置代表了所求优化问题的可行解,蜜源的丰富程度表示可行解的质量。首先初始化N个蜜源(可行解)Xi(i=1,2,…N),每个蜜源将会吸引一个引领蜂,所以N蜜源吸引N个引领蜂,而引领蜂所在的位置即为蜜源的位置。蜜源的个数不会随着迭代过程的进行而改变。引领蜂在舞蹈区将蜂源的信息同跟随蜂共享,会吸引大量的跟随蜂前去采蜜,跟随蜂的数量和蜜源的适应度有密切的关系,蜜源的适应度越大则被吸引过来的跟随蜂越多。跟随蜂将会依据选择概率来决定去哪个蜜源采蜜,当跟随蜂到达蜜源之后,对蜜源进行一次邻域搜索,然后对每个跟随蜂所搜索的位置进行对比,在引领蜂所对应的跟随蜂中找到最好的蜜源,并与以前引领蜂所探索的蜜源进行对比,如果比以前的蜜源好,则新位置作为新的蜜源,由引领蜂开采;否则,继续开采原来的蜜源,并记录开采次数。以上过程完成了一次迭代,然后所有的蜜源再次吸引引领蜂进行新的一轮开采。当同一个蜜源被开采的次数超过限定的次数后,如果解得质量还没有得到改善,此时采集该蜜源的引领蜂变成侦查蜂,并且侦查蜂随机的在解空间中产生一个新的蜜源来代替原来的蜜源。

现实生活中蜜蜂的采蜜过程如图1所示。

图1 蜜蜂采蜜过程

蜜蜂的采蜜过程可以简单地描述如下[7]。

以蜜源1为例,引领蜂采集完花蜜,来到蜂巢的某个区域卸下花蜜之后,将有三种选择。

1)直接放弃原来开采的蜜源,成为侦查蜂,如图1中的UF、S路线。

2)在摆尾舞区,引领蜂通过“摆尾舞”与跟随蜂分享蜜源的相关信息,根据蜜源的适应度吸引一定数量的跟随蜂前去采蜜,如图1中的EF1路线。

3)卸下花蜜之后,引领蜂不再招募其他的蜜蜂,继续回到原来的蜜源采蜜,如图1中的EF2路线。

在实际生活中,大多数蜜蜂在一次采蜜完成之后都会选择到摆尾舞区招募更多的跟随蜂去蜜源采蜜。为了使算法简单,这里直接选取EF1路线,即引领蜂回到摆尾舞区招募跟随蜂去蜜源采蜜。

假如已经发现了蜜源1和2,蜜蜂有两种选择。

1)开始没有蜜源信息的情况下,作为侦查蜂在蜂巢附近随机的寻找蜜源,按照图1中的S路线进行。

2)如果是在看到引领蜂的“摆尾舞”后,飞到摆尾舞区,被招募到蜜源去采蜜,按照图1中的R路线进行。

2.2 基本流程

基本蜂群算法的步骤可以描述如下[8~12]。

1)随机产生Sn个初始解,即随机产生Sn个蜜源和引领蜂,每一个解 xi(i=1,2,…,Sn)都是一个D维向量,D是优化参数的个数;初始化各个参数,包括蜂群总数、蜜源被开采次数以及同一蜜源的开采极限等。

2)初始化之后,进入采蜜过程。每个蜜源对应一个引领蜂,由引领蜂招募跟随蜂,跟随蜂不断地搜索蜜源,以此来更新引领蜂所处的位置,一次次迭代,直到达到算法终止条件为止。

3)计算每个蜜源的适应度,记录并保留当前的最优解。引领蜂以一定的概率对记忆中的蜜源位置发生改变,进而找到新的蜜源,并且计算新蜜源的适应度。假如计算出来的适应度大于原蜜源的适应度,则引领蜂将新蜜源的位置代替原蜜源的位置。

4)判断是否满足终止条件,若没有,则转到步骤2)继续执行;否则,输出最优解,结束程序。蜂群算法的流程图如图2所示。

跟随蜂选择蜜源的概率计算公式为

式中 fi为第i个蜜源的适应度。

引领蜂和跟随蜂对记忆中的原始解的邻域进行搜索的公式为

如果蜜源经过一定次数循环后不能被改进,则放弃该蜜源所对应的解。该处的引领蜂变成侦查蜂,然后继续寻找新的蜜源,其计算公式为

图2 蜂群算法流程图

3 自适应混沌蜂群算法

蜂群算法是群体智能算法中比较典型的一种,其自我改进能力和局部搜索能力较强,几乎能满足大部分的优化求解问题。相比遗传和蚁群等智能算法,蜂群算法能很快的搜索到最优值,但是其在快搜索到全局最优值时,样本的多样性减少,搜索速度减慢,容易陷入局部最优值。为此,本文提出一种自适应混沌蜂群算法,在不影响蜂群算法全局寻优的同时,提高蜂群全局的寻优速度并克服蜂群算法容易陷入局部最优的不足。

3.1 混沌算法

混沌是一种看似比较凌乱,但实际却是非常有规则的运动。混沌现象是确定性非线性系统中所特有的一种现象,不需要添加任何随机因素便可以产生。一个混沌变量同随机变量一样,表现的很杂乱,但是它却可以无重复地遍历搜索空间内的所有状态,并且表现出一定的规律性,其体现在变量由确定的迭代方程给出。正是因为混沌的这些特性,使得混沌蜂群算法易跳出局部最优解,是一种很好的搜索机制。

本文采用的Logistic映射就是一种典型的混沌模型,被广泛应用于各个领域,其方程如下:

当变量a=4的,该模型就完全进入混沌状态。

混沌算法搜索的步骤如下,

1)将n个初始值分别赋予式(),可以得到n个不同的混沌值。令x*为当前搜索的最优解,则g(x*)为当前最优适应值。

2)利用混沌变量进行搜索。

式中,pj和qj为常数且恒大于零。通过对其值的调整,可以把混沌变量的取值范围转换到与其对应的优化变量的取值范围内。

根据下式计算性能指标量。

3)如果 g(k)<g(x*),则 x*=x(k),循环达到指定的次数便结束;否则,转到2)继续进行循环。

混沌优化算法利用其特有的遍历性,将混沌方法引入到优化变量中,使其进行混沌运动,将混沌运动的范围限制在优化变量约束范围内,这样达到了搜索全局最优的目的。本文将混沌算法引入到基本的ABC算法中,利用混沌算法对蜂群进行初始,形成初始解,并将其应用到ABC算法的搜索后期,使其跳出局部最优解的范围,从而使ABC算法快速找到全局最优解,提高了该算法的寻优性能。

3.2 自适应混沌蜂群算法的提出

1)混沌初始化

在优化算法中,种群初始化是非常关键的一步,因为初始种群将会决定寻优的速度以及解的质量。在没有先验知识的前提下,一般采用随机初始化的方法产生初始解,这样没有充分利用解空间的信息,在一定程度上限制了求解的效率。为了使初始解充分利用解空间的信息,本文采用混沌算法产生初始解。在不改变初始解具有随机性的前提下,充分利用解空间的信息,提高了蜂群的多样性和搜索的遍历性。利用混沌算法产生初始解的过程如下:

(1)随机产生N个初始解,并将其映射到Logistic方程的定义域内;

(2)用Logistic方程进行迭代产生混沌序列;

(3)将产生的混沌序列映射回原来的定义域内;

(4)将两类初始解进行排序,将适应度较优的解作为种群的初始解。

2)自适应搜索方程

在ABC中,引领蜂和跟随蜂根据式(2)对记忆中解的邻域进行搜索,从式中可以看出,跟随蜂和引领蜂是随机搜索,没有方向和范围,具有一定的盲目性,特别是到了后期,随着搜索蜜源数量的增加,而搜索范围没有改变,导致搜索时间花费较长,收敛较慢。

在ABC中,搜索的新蜜源位置与以前蜜源的位置有一个差值ϕij(xij-xkj),在整个搜索过程中,这个差值都是随机的,而在实际的搜索过程中,搜索后期,搜索的范围将减小。为此,提出了自适应步长:

式中,ϕ为随机系数,取值为1.1~1.5;N为总的迭代次数;t为当前迭代次数。从式(4~7)中可以看出,随着迭代次数的增加,步长在不断的减小,达到了减小搜索范围的效果,有利于提高算法的搜索效率。根据自适应步长,将式(2)改进为

3)混沌搜索过程

蜂群算法在寻优初期,可以快速地接近最优解,但是当进行到搜索后期时,解之间的相似性增强,差距变小,导致算法易陷入局部最优。因此,本文考虑将混沌算法应用到搜索后期,使其跳出局部最优。在搜索后期利用混沌算法在较优蜜源处进行搜索,具体步骤如下:

(1)将蜜源映射到Logistic方程的定义域内;

(2)用Logistic方程进行迭代产生混沌序列;

(3)将产生的混沌序列映射回原来的定义域内,计算其适应度,并与原来的解进行对比;

(4)将最优解保留,判断是否达到结束条件。若满足结束条件,则退出;否则转步骤(2)。

3.3 人口分布寻优分析

将自适应算法和混沌算法引入到人工蜂群算法中,不仅克服了蜂群算法易陷入局部最优的缺点,而且提高了寻优的效率和解的质量。利用ABC算法和HABC算法分别对人口分布进行寻优,结果如图3~6所示。从图中可以看出,在算法初期,HABC算法产生的初始种群距最优解较近,分布也比较集中,从整个搜索过程来看,HABC算法搜索速度很快并且搜索到解的质量很高,在搜索进行到第14代时,基本完成了寻优。

图3 ABC算法和AHABC算法第一代寻优对比

图4 ABC算法和AHABC算法第三代寻优对比

图5 ABC算法和AHABC算法第五代寻优对比

图6 ABC算法和AHABC算法第十代寻优对比

4 仿真分析

4.1 测试函数

为了进一步验证HABC算法的优越性,选择以下四个函数来评价算法的性能[13~16],函数详细信息如表2所示。

Sphere函数是经典的单峰函数,其全局最优值为0,分布在(0,0)位置处,Sphere函数主要是测试算法的寻优精度;Rosenbrock函数的最优解为0,分布在x=[1,1,…1]处,用来监测算法的寻优速度;Rastrigin函数,全局最优值为0,分布在x=[0,0,…0]处;Griewank函数,当且仅当xi=0时,全局最小值为0。Rastrigin函数和Griewank函数是典型的多模态函数,搜索范围广泛,局部最优值多且分布散乱,全局最优值难于搜索,因此用来监测全局搜索能力和跳出局部最优值的能力。四个函数的三维图如图7所示。

表2 测试函数

图7 测试函数

4.2 寻优性能分析

首先对人工分群算法和自适应混沌蜂群算法的参数进行设置,蜂群总数为1000,其中引领蜂和跟随蜂各500,分别改变维数和迭代次数对以上四个测试函数进行分析。

1)Sphere函数寻优对比

首先在迭代次数相同维数不同的情况下,利用ABC算法和AHABC算法分别对Sphere函数进行寻优搜索,结果如表3所示。

表3 不同维数下Sphere函数的寻优结果

从上表中可以看出,随着搜索维数的增加,人工蜂群算法和自适应混沌蜂群算法搜索的最优值都越来越接近函数的最优值0,但是,后者搜索的最优值明显比前者要小很多,提高了算法的精度。图8是在维数相同迭代次数不同的条件下两种算法的搜索曲线。

从图中可以看出,在对Sphere函数进行寻优过程中,ABC算法在迭代600次后开始收敛,而AHABC算法在480次后就开始收敛,表明AHABC算法的搜索速度明显大于ABC算法,并且搜索到的最优值更接近函数的最优值。

图8 Sphere函数的寻优曲线

2)Rosenbrock函数寻优对比

首先在迭代次数相同维数不同的情况下,利用人工蜂群算法和自适应混沌蜂群算法分别对Rosenbrock函数进行寻优搜索,搜索结果如表4所示。

表4 不同维数下Rosenbrock函数的寻优结果

从表中可以看出,在迭代次数相同维数不断增加的情况下,两种算法搜索的最优值都不断远离函数的最优值0,为了验证算法的搜索速度,在维数相同迭代次数不同的条件下进行寻优,结果如图9所示。

图9 Rosenbrock函数的寻优曲线

从图中看出,在对Rosenbrock函数进行寻优的过程中,ABC算法在迭代400次后开始收敛,而AHABC算法在迭代300次后开始收敛,收敛速度快于ABC算法。AHABC算法搜索到的最优值明显比ABC算法搜索到的最优值更接近函数的最优值。

3)Rastrigin函数寻优对比

在迭代次数相同维数不同的情况下,两种算法对Rastrigin的寻优结果如表5所示。

表5 不同维数下Rastrigin函数的寻优结果

从表中可以看出,两种算法对Rastrigin的寻优结果同Rosenbrock函数类似,都是随着维数的增加,搜索结果渐渐远离函数的最优值0。两种算法在维数相同迭代次数不同的条件下进行寻优,结果如图10所示。

图10 Rastrigin函数的寻优曲线

从图中可以看出,在对Rastrigin函数进行寻优的过程中,两种算法在迭代300次后都开始收敛,收敛速度相差不大,但是AHABC算法搜索到的最优值与函数的最优值更接近。

4)Griewank函数寻优对比

在迭代次数相同维数不同的条件下,利用人工蜂群算法和自适应混沌蜂群算法对Griewank函数进行搜索,结果如表6所示。

表6 不同维数下Griewank函数的寻优结果

从表中可以看出,随着维数的增加,两种算法搜索的最优值越来越接近函数的最优值0,但是,自适应混沌蜂群算法搜索的最优值更接近0,精确度更高。两种算法在维数相同迭代次数不同的条件下进行寻优,结果如图11所示。

图11 Griewank函数的寻优曲线

从图中可以看出,在对Griewank函数寻优的过程中,ABC算法在迭代400后开始收敛,而AHABC算法在迭代300次后开始收敛,收敛速度明显快于ABC算法,并且AHABC算法搜索到的最优值更接近函数的最优值。

通过AHABC和ABC对四个函数的寻优结果表明:1)两种优化算法搜索测试函数的最优值随着维数的增加而变化;2)在空间维数相同的条件下,两种优化算法搜索的最优值随着迭代次数的增加而逐渐减小,最后保持某一固定值不变;3)通过对测试函数的寻优结果不难发现,AHABC算法的搜索速度要快于ABC算法,搜索精度也明显大于ABC算法。

5 结语

本文在人工蜂群优化算法的基础上,提出了一种新的优化算法—自适应混沌蜂群算法。利用混沌算法初始化种群,提高了蜂群的多样性和搜索的遍历性;提出了一种自适应步长计算方法,提高了算法搜索后期的寻优速度,同时将混沌算法应用到后期蜜源的搜索中,防止算法陷入局部最优。通过对测试函数寻优结果的对比分析,验证了该算法的优越性。

免责声明

我们致力于保护作者版权,注重分享,被刊用文章因无法核实真实出处,未能及时与作者取得联系,或有版权异议的,请联系管理员,我们会立即处理! 部分文章是来自各大过期杂志,内容仅供学习参考,不准确地方联系删除处理!