刘全明,贺剑强,张虎

(山西大学 计算机与信息技术学院,山西 太原 030006)

0 引言

函数优化问题作为一种常见的目标优化求解问题,广泛应用于各领域,工程、控制、决策等领域的大多数问题都能通过分析与抽象转换成函数优化问题[1]。传统的函数求解方法要求目标函数具备一系列苛刻的条件,这导致部分不具备相关性质的函数求解困难,不易求得全局最优解。20世纪中后期以来,一部分学者从仿生学的运行机制中得到启式,提出了一系列基于种群优化的计算方法,如遗传算法，人工免疫算法，粒子群算法，模拟退火算法，人工鱼群算法等,将这些基于种群优化的智能算法运用到函数求解后取得较好的结果。但是由于被优化函数的多样性和复杂性,在实际使用中所有算法都或多或少地表现出了优势与不足。

人工鱼群算法[2](artificial fish swarm algorithm,AFSA)是我国学者李晓磊等人于2002年提出的一种基于鱼群自主寻优的群体优化算法,被广泛应用于多个优化计算领域,该算法实现简单,鲁棒性强,对初值、参数不敏感。但是研究发现人工鱼群存在两个明显缺点:(1)当函数最优解所在范围较大或相对平稳时,算法收敛缓慢,搜索结果精度不高;(2)算法在运行初期收敛速度较快,能快速收敛到最优解周围,但是后期收敛缓慢还可能出现不收敛现象。目前,已有部分学者提出一些改进算法,来克服基本鱼群算法的缺点。文献[3]中将粒子群算法中粒子的寻优方式引入,改进人工鱼个体的觅食、聚群、追尾等行为,使得改进后的人工鱼个体,只需依据自身视野进行位置更新,避免了固定步长给算法性能带来的影响。文献[4-5]通过对人工鱼自身聚群、追尾、觅食行为的改进来达到更好的效果。文献[6-8]引入遗传算法的交叉、变异算子,当人工鱼最优个体在连续多次迭代中改变程度低于预期或者保持不变时,则停止算法迭代,并保留最优个体状态,将剩余个体中的一部分按一定概率进行交叉、变异操作。此方法通过引入遗传算法中的交叉、变异算子,让人工鱼个体实现了突变,从而使得算法后期个体改变较慢的问题得到解决,人工鱼收敛速度加快的同时算法收敛精度也得以提高。文献[9-10]通过引入粒子群算法,将初始种群随机分成两个不同的子种群,分别利用粒子群算法和人工鱼群算法进行优化。计算结束后,比较两个算法得到的最优值,将其中的较优值代替公告板中当前最优值,用作下一次比较使用。其变异算子是将两组种群中最差的5个个体按照一定的概率进行变异,变异结束后加入各自种群。此算法虽然对两个算法的缺点起到一定的改进作用,但是也会使得局部最优解形成聚集效应,导致算法失去应有的作用,并且两个算法各自单独进化,没有对算法缺点有根本性的改变。

遗传算法(genetic algorithm,GA)是由Holland教授模拟自然界中物种的选择进化和基因传播提出的一种仿生智能优化算法,通过模拟物竞天择的自然选择法则来搜索最优解[11]。遗传算法的优点是具有较强的全局收敛能力,对问题领域不敏感,鲁棒性强;搜索过程从解的串集出发,不是从单个解个体出发,同时处理种群中的多个个体有助于找到全局最优解,同时使得算法易于并行化;对最优个体的评价采用适应度函数,不受其他无关信息影响,使得遗传算法适用性大大增加。但是由于遗传算法采用遗传机理进行计算,编码和解码会增大算法的复杂度影响效率,同时遗传算法对进化过程中系统的反馈信息未能加以利用。

综合分析人工鱼群算法和遗传算法的优缺点,本文将引入文化算法作为基本框架,利用文化算法的双层进化机制,建立遗传算法演化的信仰空间和人工鱼群算法演化的种群空间,种群空间通过接受函数不断向信仰空间贡献精英个体,信仰空间通过自身演化并利用影响函数来指导种群空间,最终形成双演化双促进的双层进化机制。改进算法充分利用了遗传算法全局搜索能力强,搜索精度高和人工鱼群算法初期收敛速度快的优点,使得改进后的算法比原算法搜索速度更快,精度更高。

1 算法基本原理

1.1 人工鱼群算法

人工鱼群算法把实际待优化问题中的解抽象成一条人工鱼,每条人工鱼的位置状态可以用向量X=(x1,x2,…,xn)来表示,其中xi(i=1,…,n)表示待寻优的变量,人工鱼当前所在位置的食物浓度Y=f(X)其中Y为目标函数值;di,j=‖Xi-Xj‖表示两条人工鱼之间的距离;V表示人工鱼的感知视野;S表示人工鱼的移动步长;δ表示食物周围的拥挤度因子。每条人工鱼通过模拟鱼的觅食、聚群、追尾和随机移动行为来寻找最优适应度从而达到搜素优化的目的。

觅食行为:设当前人工鱼所在位置为Xi,在视野范围内随机寻找位置Xj,在求极大值寻优问题中,如果Yj>Yi,按公式(1)更新人工鱼所在位置;反之,则在视野范围内重新尝试寻找位置Xj,判断新的Xj是否满足更新条件,设最大尝试次数为Tr，当进行Tr次尝试后依然无法找到满足条件的Xj,即Yj

(1)

聚群行为:设当前人工鱼所在位置为Xi,nf和Xc分别表示视野范围内(即di,jδYi,则按公式(2)更新人工鱼所在位置,否则执行觅食行为。

(2)

追尾行为:设当前人工鱼所在位置为Xi,搜寻自身视野范围内食物浓度值Ym最大的人工鱼Xm,并以Xm为中心搜寻其视野范围内的人工鱼数目nf,如果Ym/nf>δYi则表明Xm处食物浓度较大且不拥挤,按公式(3)向Xj的方向移动一步,否则执行觅食行为。

(3)

随机行为:在当前人工鱼视野内随机选择一条人工鱼,并以所选人工鱼为目标移动一步,是觅食行为的默认行为。

更新公告板:每次迭代结束后,比较当前最优解和公告板,若当前最优解优于公告板则将公告板用当前最优解替换。

1.2 遗传算法

遗传算法基本流程为:

(1)个体编码。种群中的每一个个体代表解集中的一个解,在遗传算法运行时需要将个体编码为二进制的染色体,利用编码好的二进制串进行运算。

(2)初始化种群。根据实际问题的规模,设定种群的大小,并初始化种群个体。

(3)适应度计算。每次迭代过程中,利用适应度函数计算每个个体的适应度。

(4)遗传算子(选择、交叉、变异)

a)选择:选择算子从旧种群中按一定概率选择优秀个体组成新的种群进行繁殖产生新一代种群。选择过程中个体被选中的概率与适应度值成正比。

b)交叉:交叉算子从种群中随机选择两个个体,选择交叉点,并将交叉点处染色体互换,产生新个体。

c)变异:变异算子随机从种群中选择一个个体,将个体的部分染色体进行变异,通过变异操作产生新的优秀个体,同时保持种群多样性。

2 基于文化算法框架的遗传鱼群算法

2.1 文化算法

自然界给人类提供了许多仿生智能计算的灵感,关于这方面的研究大多数集中在种群的自然选择层面上。随着时间的推移,人类在自身发展过程中通过对信息知识的采集、提取、编码和传播,逐渐形成了共同的知识结晶,这种超越种群层面的知识积累与传播是自然界其他生物所不具备的。正是这种能力使得人类社会高速发展,形成了现如今高度发达的文明。

文化算法模拟人类文明的发展,在传统的种群空间之上引入可以进行知识积累、进化和传播的信仰空间,形成双层进化机制。信仰空间通过接受函数获得种群空间进化过程中积累的知识,把这些知识保存并加以演化,最终用于影响和指导种群空间进化[11]。

文化算法总体包括三部分:种群空间、信仰空间和沟通渠道,其中沟通渠道又包括影响函数和接受函数两部分。种群空间和信仰空间分别从微观和宏观两个层面模拟人类社会的发展进化,在进化过程中保持相对独立,通过沟通渠道进行相互作用。

2.2 文化算法框架下的改进遗传人工鱼群算法(CA_GAFSA)

文化算法的双层进化机制给基于种群的进化算法提供改进的灵感和条件。通过分析发现蚁群算法、粒子群算法、人工蜂群算法等都是通过模仿特定生物群体中个体的行为来优化待求解问题,这样使得最优解容易集中到局部最优解附近陷入局部收敛;而遗传算法通过选择、交叉、变异操作,在给种群加入新的优秀个体时具有一定的随机性,有利于跳出局部最优值,从而达到全局收敛。因此本文提出的改进算法模型主要是基于文化算法的框架结构,建立以遗传算法优化的信仰空间和以人工鱼群算法优化的种群空间。经遗传算法初始化信仰空间、人工鱼群算法优化种群空间后,通过适应度函数评价种群空间中的个体适应度,每次迭代过程中将种群空间中的最优个体通过接受函数传递给信仰空间,信仰空间通过遗传算法演化后每隔一定时间将积累的优秀个体通过影响函数反馈给种群空间,种群空间利用更新后的新种群继续演化,并不断向信仰空间传递最优个体,整个过程不断重复,直到满足结束条件,算法终止。

改进后的算法流程描述如下:

(1)种群空间初始化:种群空间采用人工鱼群算法演化,编码方式采用十进制方式。在求解问题变量空间域内随机初始化N个人工鱼个体(问题的N个初始解),并计算适应度值。设定人工鱼最大视野V,移动步长S,最大尝试次数Tr,拥挤度因子δ。

(2)信仰空间初始化:信仰空间采用遗传算法演化,编码方式采用二进制方式。在求解问题变量空间域内随机初始化一定数量的个体(问题的解),数量规模取种群空间个体数量的20%到30%。

(3)定义接受函数。每次种群空间和信仰空间更新结束后,信仰空间接受种群空间中的当前最优解,替换自身当前最劣解。

(4) 定义影响函数。每迭代5次,用信仰空间中适应度排名前T个(本文取T=5)个体(问题的解)将种群空间中等量的适应度较差的个体(问题的解)进行替换。

(5)迭代求解:

a)种群空间更新。当满足条件时,运行影响函数。然后利用人工鱼群算法对种群空间进行演化(新的一次求解过程)。

b)信仰空间更新。运行接受函数,然后利用遗传算法对信仰空间进行演化(新的一次求解过程)。

(6)更新公告板。每次迭代完成后比较当前公告板的值和种群空间中的最优值,并将两者中的较优值赋给公告板。

(7)判断终止条件。比较终止条件和公告板上的值,如果满足终止要求,算法终止;否则重复步骤(5)-(7),直到满足终止条件。

(8)算法终止,将最优值和其对应的状态值输出。

3 实验设计与结果分析

3.1 实验设计

为了验证本文算法的有效性,本实验采用的实验平台处理器为AMD处理器,主频2.35 GHz,内存大小4 GB,操作系统为Windows10家庭中文版,程序运行环境为Matlab R2014a。

同时选取了4个具有代表性的基准测试函数,通过两种不同的测试方法来评价改进算法和其他算法对测试函数的优化性能[13]:(1)在固定迭代次数下,比较优化函数的最优值、平均值和最差值,通过比较可以从一定程度上反映出优化算法的搜索精度和速度;(2)成功率和迭代次数,成功率指在指定的求解精度以及最大迭代次数下,算法优化结果达到预定精度的次数和总的测试次数的比值,此项指标可在一定程度上反映出算法的可靠性,达到指定精度的下的平均迭代次数可反映出算法的进化速度。本文选取的四个基准测试函数如表1所示:

表1 基准测试函数Table 1 Benchmark function

3.2 结果分析

本文对四个基准函数进行测试过程中遗传算法采用谢菲尔德遗传算法工具箱,其中参数设置均为:变量的二进制编码位数PRECI=20,选择算子代沟GGAP=0.95,交叉概率px=0.7,变异概率pm=0.1。分别对两个二维函数和两个多维函数进行测试,验证本文算法对不同变量维度函数的优化性能,并将文献[4]和[15]中的两种改进算法与基本鱼群算法加入对比,以验证本文算法相对于其他改进算法的性能优势。

3.2.1 二维函数优化分析

函数f1为多模态函数,存在多个极小值点,但是最小值只有一个。因其最小值周围有一个环形的波谷,在函数求解中很容易陷入局部极小值[18],因此该函数常被当作基准函数检验算法的性能。在测试过程中,遗传算法参数设置如前所述,人工鱼群算法参数均设置为:人工鱼个数N=100,最大尝试次数Tr=100,视野V=1,步长S=0.3,拥挤度因子δ=0.618,实验独立进行30次。迭代次数取50次和100次的结果如表2所示。寻优精度分别为0.000 1和0.000 01时结果比较如表3所示。迭代次数取50次和100次时算法的平均最优值随迭代次数的变化曲线分别如图1和图2所示。

表2 固定迭代次数下四种算法比较Table 2 Comparison of four algorithms under fixed iteration times

表3 固定精度下四种算法比较Table 3 Comparison of four algorithms under fixed precision

Fig.1 Change curve of average optimal solution图1 平均最优解变化曲线

Fig.2 Change curve of average optimal solution图2 平均最优解变化曲线

函数f2在测试过程中,遗传算法参数设置如前所述,人工鱼群算法参数均设置为:人工鱼个数N=100,最大尝试次数Tr=100,视野V=2.97,步长S=1.31,拥挤度因子δ=0.618,实验独立进行30次。迭代次数取50次和100次的结果如表4所示。寻优精度分别为199.999和199.999 9时的结果比较如表5所示。迭代次数取50次和100次时的平均最优值随迭代次数的变化曲线分别如图3和图4所示。

表4 固定迭代次数下四种算法比较Table 4 Comparison of four algorithms under fixed iteration times

表5 固定精度下四种算法比较Table 5 Comparison of four algorithms under fixed precision

Fig.3 Change curve of average optimal solution图3 平均最优解变化曲线

Fig.4 Change curve of average optimal solution图4 平均最优解变化曲线

从表2和表3可以看出,对于函数f1本文提出的算法结果在最优值、平均值、最差值上均优于文中的对比算法,在寻优精度方面同样高于对比算法。从表4、表5可以看出,对于函数f2虽然三种对比算法也取得较好的优化结果,但是在各对比项中本文算法还是全面优于其他三种对比算法,表现出很好的优化能力。从图1-4可以看出在相同迭代次数下本文算法的迭代速度更快,更加接近最优解。表明本文算法具有更高的精度、更快的搜索速度和更好的可靠性。

3.2.2 多维函数优化分析

函数f3在测试过程中,遗传算法参数设置如前所述,人工鱼群算法参数均设置为:人工鱼个数N=100,最大尝试次数Tr=50,视野V=1.5,步长S=1,拥挤度因子δ=0.618,实验独立进行30次。当变量维数分别取10和20时,迭代次数分别取1 000次和1 500次的结果如表6所示。图5中按从左到右、从上到下的顺序四幅图分别表示变量维数取10维迭代次数取1 000次、变量维数取10维迭代次数取1 500次、变量维数取2维迭代次数取1 000次、变量维数取2维迭代次数取1 500次时四种算法的平均最优值随迭代次数的变化曲线。

函数f4在测试过程中,遗传算法参数设置如前所述,人工鱼群算法参数均设置为:人工鱼个数N=100,最大尝试次数Tr=100,视野V=20,步长S=2,拥挤度因子δ=0.618,实验独立进行30次。当变量维数取10和20时,基本鱼群算法和本文算法迭代1 000次和1 500次的结果如表7所示。图6中按从左到右、从上到下的顺序四幅图分别表示变量维数取10维迭代次数取1 000次、变量维数取10维迭代次数取1 500次、变量维数取2维迭代次数取1 000次、变量维数取2维迭代次数取1 500次时四种算法的平均最优值随迭代次数的变化曲线。

表6 四种算法比较Table 6 Comparison of four algorithms

Fig.5 Change curve of average optimal solution图5 平均最优解变化曲线

由表6可以看出对函数f3来说,在变量维数增加到10维和20维时,本文算法优化结果优于其他三种对比算法,且随着迭代次数的增加本文算法的结果依然不断向最优值收敛,展现了本文算法在迭代后期良好的收敛性;而其他三种算法在增加迭代次数的同时,优化结果并没有太大的改变,其中文献[4]中算法出现一定的退化,表明算法后期收敛能力的弱化,甚至不再继续收敛。图6展现了在相同迭代次数下,本文算法收敛精度明显好于其他对比算法,表明本文算法收敛速度更快。由表7可以看出对于函数f4来说,在变量维数取到10 时四种算法均取得很好的优化结果,文献[4]中算法的最优值比本文算法结果还要好,但是其平均值和最差值却劣于本文算法结果,甚至出现最差值完全不收敛的情况。在函数f4变量维数取到20维时,本文算法结果依然在接受范围内,而其他三种对比算法的求解结果却距离最优值相差甚远,完全没有起到优化求解的效果。

表7 四种算法比较Table 7 Comparison of four algorithms

Fig.6 Change curve of average optimal solution图6 平均最优解变化曲线

综上分析,本文算法对比其他三种算法在对文中四个基准测试函数优化过程中,虽然极个别结果稍微劣于对比算法,但总体上本文算法对于四个测试函数都能起到很好的优化求解结果,针对不同情况都能表现出较为均衡的优化能力,鲁棒性更强。对于算法的收敛速度,由于人工鱼群算法作为仿生学算法的一种,其算法行为都是模仿自然界中动物的生活习性来设计提出,理论性较弱,但是可以从图1-6中函数最优值随迭代次数的变化曲线上直观看出,本文算法相对其他三种对比算法在相同迭代次数下迭代结果更优,同时在取得相同的迭代精度时需要更少的迭代次数,表明本文算法具有更快的迭代速度。

4 结论

利用文化算法模型的双层进化机制,提出了一种基于文化算法框架的改进人工鱼群算法,旨在解决基本人工鱼群算法存在的缺点。通过4个基准测试函数的优化实验表明:本文算法相比三种对比算法来说优化结果精度更高,算法收敛速度更快,鲁棒性更强;尤其是对于高维函数,其他三种算法优化结果较差甚至无法优化,本文算法优化结果精度较高且收敛速度较快。

参考文献：

[1] 刘白,周永权.基于遗传算法的人工鱼群优化算法[J].计算机工程与设计,2008,29(2):5827-5829. DOI:10.16208/j.issn1000-7024.2008.22.077.

[2] 李晓磊,邵之江,钱积新.一种基于动物自治体的寻优模式:鱼群算法[J].系统工程理论与实践,2002,22(11):32-38.DOI:10.3321/j.issn:1000-6788.2002.11.007.

[3] 姚卫红,方仁孝,张旭东.基于混合人工鱼群优化SVR的交通流量预测[J].大连理工大学学报,2015,55(6):632-637.DOI:10.7511/dllgxb201506011.

[4] 黄美华,温洁娥,何勇.求解多目标背包问题的改进人工鱼群算法[J]广东工业大学学报(自然科学版),2016,33(5):44-48.DOI:10.3969/j.issn.1007-7162.2016.05.008.

[5] 刘东林,李乐乐.一种新颖的改进人工鱼群算法[J].计算机科学,2017,44(4):281-287. DOI:10.11896/j.issn.1002-137X.2017.04.058.

[6] 吴旭,洪联系,魏德志,等.改进的人工鱼群混合算法在智能组卷中的应用[J]集美大学学报(自然科学版),2012,17(5):394-400.DOI:10.3969/j.issn.1007-7405.2012.05.013.

[7] 姚丽莎,王占凤,程家兴.基于人工鱼群遗传算法的异构多核系统任务调度研究[J].计算机工程与科学,2014,36(10):1866-1871.DOI:10.3969/j.issn.1007-130X.2014.10.005.

[8] 姜山,季业飞.改进的人工鱼群混合算法在交通分配中的应用[J].计算机仿真,2011,28(6):326-329. DOI:10.3969/j.issn.1006-9348.2011.06.080.

[9] 罗德相,周永权,黄华娟.粒子群和人工鱼群混合优化算法[J].计算机与应用化学,2009,26(10):1257-1261. DOI:10.3969/j.issn.1001-4160.2009.10.011.

[10] 洪蕾粒.子群及人工鱼群算法优化研究[J].软件,2014,35(8):83-86.DOI:10.3969/j.issn.1003-6970.2014.08.019.

[11] Holland J.Genetic Algorithms,Gomputer Programs that Evolve in Ways that Even Their Greators do Not Fully Understand[J].ScientificAmerican,1975(267):66-72.

[12] Reynolds R G.An Introduction to Cultural Algorithms[C]∥Proceedings of the Third Annual Conferenceon Evolutionary Programming,World Scientific.River Edge,New Jersey:[s.n.],1994:131-139.DOI:10.1136/ewjm.172.5.335.

[13] 陈雷.基于群智能优化方法的盲信号分离算法研究[D].天津：天津大学，2011.

[14] 费腾,张立毅,白煜,等.基于DNA的改进人工鱼群算法[J].天津大学学报(自然科学与工程技术版),2016,49(6):581-588.DOI:10.11784/tdxbz201501007.

[15] 邓涛,姚宏,杜军.多峰函数优化的改进人工鱼群混合算法[J].计算机应用,2012,32(10):2904-2906,2910.DOI:10.3724/SP.J.1087.2012.02904.

[16] Mao M,Duan Q,Yang Z,etal.Modeling and Global MPPT for PV System under Partial Shading Conditions using Modified Artificial Fish Swarm Algorithm[C]∥IEEE International Symposium on Systems Engineering.IEEE,2016:1-7.

[17] Azizi R.Empirical Study of Artificial Fish Swarm Algorithm[J].ComputerScience,2014,17(6):626-641.

[18] 张严,楚晓丽.一种改进的人工鱼群算法[J].计算机系统应用,2011,20(5):199-201. DOI:10.3969/j.issn.1003-3254.2011.05.046.