模拟人工算法

2024-07-23

模拟人工算法（共3篇）

模拟人工算法篇1

0 引言

自然界中的群居性昆虫, 虽然其中每一个体均呈现为结构简单, 以及行为单一, 但是群居后的昆虫整体却构建了一种复杂的行为模式。而且无论自然环境如何恶劣, 这些群居性昆虫也均能找到食物和巢穴, 同时获得良好的生存适应性。由此可知, 自然界中的群居性生物有相当多数都在某种程度上表现出了宏观的群体智能行为, 而群体智能的概念就提炼于对自然界中昆虫群的观察与研究, 随即群居性生物在群体中凸显出的自组织、自适应以及社会分工和相互协作的智能行为则相应地称为群体智能[1]。针对以上现象与行为, 学者们已提出了许多群体智能优化算法。这些算法的基本思想即是将自然界中的生物个体假定为搜索空间的点, 由此则将个体的进化或者觅食行为模拟作最优解的搜索过程, 并通过将个体对环境的适应性定义为需求解问题的目标函数, 再将自然界中“优胜劣汰, 适者生存”的生存法则视作利用好解取代差解的选择, 整个群体将会逐步收敛、直至最优解, 这一过程就是迭代的搜索过程[2]。

蜜蜂是群居性昆虫中的一种, 其成为群体智能的两个必要条件在此可表述为自组织性和分工协作性。单一蜜蜂的行为简单明确, 但是蜜蜂群却可以在复杂的环境下高效率地找到食物源并完成采蜜, 同时也可以随着环境的变化而智能性地改变自身的行为。由此, 有关蜜蜂群行为的各种算法于2000年以后则相继提出, 这是一个全新的群体智能优化研究领域, 倍受各方学者的关注与青睐。众多研究成果中, 颇具里程碑意义的当属土耳其埃尔吉耶斯大学的Karaboga在2005年提出的人工蜂群算法[3] (Artificial Bee Colony Algorithm, ABC) 。自此之后, 尤其是2010年以来, 即涌现了与其相关的大量学术报告和研究文献。特别地, 2010年于太原召开的群体智能会议上, 人工蜂群算法还作为一个专题, 并围绕其展开了高端与广泛的讨论[4]。

人工蜂群算法是基于蜜蜂的觅食行为衍生而来的, 蜜蜂的觅食行为恰是一种典型的群体智能行为。人工蜂群算法即模拟了蜜蜂群寻找食物源的智能行为, 算法简单, 并且具有很好的鲁棒性[5]。Karaboga提出的人工蜂群算法可以解决数值函数的优化问题, 其后则又用于人工神经网络的训练、约束化问题的解决以及模糊聚类的实现等[6]。鉴于人工蜂群算法所具有的良好性能, 现已进入了各种研究领域。具体成果有:Sundar等人将该算法应用于求解最小二次生成树问题[7];刘华等则引入局部搜索和混沌思想, 提出了一种改进的人工蜂群算法, 并将其应用于流水线调度研究[8];付丽和罗钧又提出了引入跟踪搜索和免疫选择的人工蜂群算法[9]等等。

1 人工蜂群算法原理

1.1 自然界中的蜂群

根据蜂群中蜜蜂的不同分工, 可将蜂巢中的蜜蜂分为三类[10], 详细分析如下:

(1) 蜂王:是生殖器官发育完全的雌蜂, 更是蜂巢中唯一产卵的雌蜂, 其作用就是繁衍后代。蜂王一生只交配一次, 在接下来的时间里分批受精产卵, 补充新蜜蜂来维持群体数量的稳定。所有储存的精子消耗之后, 开始产下未受精的卵;

(2) 雄蜂:是由未受精的卵发育而来, 其作用是与蜂王交配, 交配之后, 很快就会死去, 寿命不会超过六个月;

(3) 工蜂:是蜂巢中数量最多的蜜蜂, 是性器官发育不成熟的雌蜂。工蜂要承担寻找食物源、采集食物、储存食物、清理垃圾和死蜂的尸体、筑巢并保持蜂巢的良好环境及保卫蜂巢等一系列任务。因年龄的不同, 可将其分为三种不同生理类型的工蜂———保育蜂、筑巢蜂和采蜜蜂。

蜂巢中的三类蜜蜂各司其职, 互相合作, 创造了神奇的群体智能现象, 这就使得在复杂恶劣的自然条件下, 依然能够生存并保持种群健壮的优势。蜂群通过完美的合作组成了有机的整体, 完成了很多智能化的群体活动来维持种群的生生不息。其主要的活动有:

(1) 婚飞行为, 即蜂王飞到离蜂巢很远的地方, 飞行过程中, 只有强健的青春期雄蜂才能追赶上蜂王, 并在空中与其交配;

(2) 筑巢选择行为, 即蜂群要根据巢穴尺寸、气候环境、筑巢需要的时间条件等等因素来全体一致地决定蜂巢位置;

(3) 觅食行为, 即觅食蜂飞离蜂巢, 开始搜索花蜜源, 找到质量上乘的花蜜并采集, 储存花蜜并带回蜂巢等等[11]。其中最重要的就是觅食行为。

下面对蜂群的觅食过程进行分析。在觅食过程中有三个重要的要素, 即花蜜源、被雇佣蜜蜂和未被雇佣蜜蜂[12]。被雇佣蜜蜂又称为引领蜂, 未被雇佣蜜蜂则分为跟随蜂和侦查蜂。一只蜜蜂由于某种自然的原因飞出巢穴寻找花蜜源, 此时该个体将成为侦查蜂。当找到了花蜜源时即转换为引领蜂, 每一只引领蜂都与找到的花蜜源一一对应, 然后就利用自己的能力在记住该花蜜源的位置, 花蜜的质量等等可以评判该花蜜源的因素后飞回巢穴。接下来, 该引领蜂将出现以下几种可能的行为:

(1) 在和其他引领蜂发现的花蜜源比较之后, 放弃自己发现的质量并不高的花蜜源, 重新成为侦查蜂;

(2) 在蜂巢的舞蹈区跳舞招募蜜蜂, 此时跟随引领蜂飞出蜂巢采蜜的蜜蜂即为跟随蜂;

(3) 继续在同一花蜜源处采蜜而不进行招募。就这样, 蜂群中的工蜂完成觅食行为, 由此而保障了蜂群的食物来源, 并使其群体得以维持和繁衍。

1.2 人工蜂群算法的基本模型及原理

时下, 基于蜜蜂觅食过程的算法主要有两种, 一种是蜂群算法 (Bees Algorithm, BA) [13], 另一种就是本文即将提到的人工蜂群算法 (Artificial Bee Colony Algorithm, ABC) , 这两种算法基本相同, 其主要区别就在于引领蜂、跟随蜂和侦查蜂在蜂群中所占比例的各不相同, 另外ABC还引入了参数limit, 具体作用是将限制侦查蜂在一个食物源附近的搜索次数, 而这一参数BA却是没有的。

人工蜂群算法主要就是模拟自然界中蜂群的觅食过程[14], 其首度提出即是用于解决连续函数的求解问题, 其后更是广泛应用于优化问题的求解。其中, 算法与问题的具体对应关系可做如下描述:蜂群觅食行为即具体的优化问题食物源即优化问题的可行解;食物源的位置即优化问题解的位置;食物源的质量即优化问题中的适应度值;寻找和采集食物源的过程即优化问题的求解过程;另外, 食物源的最大质量即优化问题的最优解。

因为人工蜂群算法源起自自然界中的蜂群模拟, 具体地该算法也由三个重要部分组成, 分别是:食物源、雇佣蜂、非雇佣蜂。其中, 食物源即为花蜜源, 雇佣蜂又称为引领蜂, 非雇佣蜂则分为跟随蜂和侦查蜂。蜜蜂种群的群体智能是依据蜜蜂之间的信息共享、相互协作、甚至是在必要的条件下进行的相应角色转换来实现的。在此, 将对人工蜂群算法的搜索过程做如下实际描述:最开始时候, 所有蜜蜂对食物源均没有认识, 都是侦查蜂, 在整个解空间随机搜索, 当侦查蜂搜索到食物源后, 携带能评判该食物源质量的信息回到蜂巢与其他蜜蜂共享, 根据对这些信息的某种比较, 侦查蜂可进行角色转变。当该食物源的质量排名靠前时, 该侦查蜂即转变为引领蜂, 与其搜索到的食物源一一对应, 并将招募到更多的跟随蜂到食物源附近搜索新的食物源;当该食物源的质量排名居中时, 该侦查蜂即转变为跟随蜂, 并将按某种选择机制选择引领蜂, 跟随该引领蜂到其对应的食物源附近进行搜索;当该食物源的质量排名靠后时, 该侦查蜂将放弃搜索到的食物源, 再次成为侦查蜂在解空间开展新一轮的随机搜索[15]。

综上可得, 与其对应的算法流程可概述如下[16]:算法开始时, 初始化种群, 派出侦查蜂搜索食物源, 评估食物源的质量即适应度值, 满足条件时开始循环, 选择适应度值高的侦查蜂为引领蜂, 引领蜂将招募跟随蜂, 并带队到对应的食物源附近搜索新的食物源, 令适应度值低的侦查蜂则继续搜索食物源, 而且评估所有蜜蜂搜索到的食物源的适应度值, 此时结束循环, 输出最优解, 算法结束。

1.3 人工蜂群算法的实现步骤

人工蜂群算法的主要步骤包括[17]初始化阶段、循环、雇佣蜂阶段、追随蜂阶段、侦查蜂阶段、记录目前为止搜索到的最优解和结束循环 (达到最大循环次数) , 现对各实现步骤具体展开, 可得详细内容为[18]:

步骤一初始化种群, 包括初始化蜂群数量NP、食物源数量NP/2、控制参数limit、最大循环数Max Cycle、D维解空间, 并且在解空间随机产生初始解Xi (i=1, 2, …, NP) , 计算其适应度值。

步骤二开始循环 (循环次数小于最大循环次数) 。

步骤三引领蜂在初始解的邻域按公式Vij=Xij+Φij (Xij-Xkj) 搜索新解Vi, 计算新解的适应度值。其中, k∈{1, 2, …, NP}, j∈{1, 2, …, D}, 且k≠j, Φij为[-1, 1]之间的随机数。

步骤四根据贪婪选择机制, 按照公式

选择具有更高适应度值的解保留给下一代种群。公式含义为:如果Vi的适应度值优于Xi, 则用Vi替换Xi, 并将Vi作为当前的最优解, 否则保留Xi不变。

步骤五按照公示计算食物源的概率Pi。

步骤六跟随蜂依据概率Pi选择引领蜂对应的食物源, 按照搜索新解的公式产生新解Vi, 并计算其适应度值。

步骤七重复步骤四。

步骤八当某只引领蜂在其食物源邻域搜索次数d达到控制参数limit时, 仍然没有找到适应度值更高的新解, 即放弃该食物源, 随机初始化该引领蜂的位置。

步骤九记录当前最优解。

步骤十判断循环结束的条件, 当循环次数达到最大循环次数时, 终止循环, 输出最优解, 否则, 返回步骤三继续搜索。

人工蜂群算法作为一种群体智能优化算法, 能真实模拟自然界中的蜂群觅食行为, 而且控制参数的设置亦能有效平衡全局搜索和局部搜索, 这就尽量避免了算法陷入局部最优, 从而显著提高了算法的性能。

2 人工蜂群算法的研究现状

人工蜂群算法在2005年首次提出之后, 第一篇介绍人工蜂群算法的会议论文即于次年正式发表, 而第一篇描述人工蜂群算法并评估其效能的期刊论文则由Karaboga和Basturk在2007年公开见刊, 这篇论文将人工蜂群算法和遗传算法以及粒子群优化算法进行了本质上的研究比较。2009年, 一个以人工蜂群算法为主题的网站得以问世, 其域名是http://mf.erciyes.edu.tr/abc。该网站中包含有几种用不同程序语言编写的人工蜂群算法源代码, 同时也集结了关于改进人工蜂群算法及其应用的许多出版刊物[19]。人工蜂群算法和其实现均相对简单, 因此也可以相对简单地解决优化问题, 而综合以上的研究可知, 人工蜂群算法是低耗、且高效的。因此, 在这些最初的研究成果涌现后, 学者们即随之开启了更多的关于人工蜂群算法的研究进程。其后的研究大体上可以分为三类:比较和修改、混合型及应用。

2.1 比较和修改

基于最初的人工蜂群优化算法是为了解决数值问题而提出并形成的, 这就使得研究目的即设定为是和其他著名的算法, 例如粒子群优化算法、差分进化算法、蚁群优化算法在一个标准的数值函数上进行测试, 从而评估人工蜂群算法的总体表现。2007年, Karaboga和Basturk即比较了人工蜂群算法、遗传算法和粒子群优化算法在优化多变量函数问题中的应用效果[20]。2008年, Karaboga和Basturk又再次比较了人工蜂群算法、差分进化算法和粒子群优化算法, 及进化算法在多维函数问题上的应用结果[21]。2009年, Karaboga和Akay更进一步比较了人工蜂群算法与遗传算法, 粒子群优化算法, 以及差分进化算法在大量数值函数问题上的应用成果[22]。与此类似的研究还有, Mala et al.把人工蜂群算法应用到一系列的优化问题中, 并和蚁群算法进行了相应比较, 由此总结出人工蜂群算法与蚁群算法相比所独具的几种优势。2010年, Li et al.则在著名的基准测试数据上给出了人工蜂群算法, 差分进化算法和蜂群算法的对比效果呈现[23]。随着研究的推进, 2011年, Chu等发表了重要的包括人工蜂群算法在内的的群体智能综述[24]。并且2012年, Mohammed和El-Abd在整体上实现了包括人工蜂群算法和进化算法的觅食性能评估[25]。

人工蜂群算法在处理连续搜索空间上的成功推动着研究者将其应用继续拓展到其他的领域。例如, 2009年, Akay and Karaboga即将人工蜂群算法应用到整数规划问题中, 并总结出ABC可以有效地处理证书规划问题[26]。2010年, Wang等则将人工蜂群算法应用到支持向量机的自由参数, 应用实践表明二进制人工蜂群算法可以获得入侵检测系统的最优特征选择[27]。2011年, Kashan等介绍了一个新版本的ABC, 叫做Dis ABC, 就是为二进制优化而特别设计的[28]。2013年, 任子武等再次提出一种数值求解并联机器人正运动学问题的改进人工蜂群算法, 藉此表明了该方法是求解并联机器人正运动学问题的一种有效方法[29]。2014年, 庞柒、阮平南和关志强更提出一种改进的人工蜂群算法用于解决煤炭物流中生产物资的运输问题, 该问题属于典型的车辆路径问题[30]。

2.2 混合型

为了使人工蜂群算法的研究更趋深入与完整, 研究者们则将一些传统的和进化的优化算法与人工蜂群算法进行了创新组合, 这类人工蜂群算法即称做混合型人工蜂群算法。2009年, Kang等提出了组合Nelder-Mead单形法与人工蜂群算法的混合型人工蜂群算法, 这一算法的出现提高了人工蜂群算法的计算效率。接着, Marinakis等提出了一种新的混合算法, 该算法是基于人工蜂群的概念和贪婪随机自适应搜索算法, 可以实现将N个对象最佳聚集到K个集群。Pulikanti和Singh继而又提出了混合人工蜂群算法和贪婪启发式、局部搜索算法的混合型人工蜂群算法, 并用以解决二次背包问题[31]。2010年, Duan等再次提出了一种新算法, 混合了人工蜂群算法和量子进化算法以用于解决连续的优化问题。Zhaoet等进一步提出了基于遗传算法的并行计算优点和人工蜂群算法的快速自提高优点的新的混合型群体智能算法。同时, Banharnsakun等也提出了新的混合方法解决TSP问题, 在人工蜂群算法的开采过程中使用贪婪交叉方法, 以此而提高了算法效能[32]。较新的研究成果还有, 2011年, Sharma和Pant提出将差分进化算法的操作数组合到基本人工蜂群算法的结构中。Bin and Qian随之又提出了一种新的人工蜂群算法, 用来解决全局数值优化问题[33]。2012年, Sundar和Singh提出了混合人工蜂群算法和局部搜索方法解决集合覆盖问题[34]。2013年, 杨琳和孔峰发表了嵌入粒子群优化算法的混合人工蜂群算法[35]。2014年, 更有柳欢和高亚兰提出了一种结合Sobel算子和人工蜂群算法的方法用于对图像的边缘检测[36]。

2.3 应用

虽然最初的人工蜂群算法是用来解决数值问题的, 但其后的丰富成果却已经用来解决离散和连续类型问题。2009年, Singh就提出了用于左限制条件的最小生成树的人工蜂群算法[37]。2010年, Hemamalini和Simon则通过运用斜坡率限制和禁止操作区而将人工蜂群算法应用到经济负荷分配问题中, 并总结出这种方法具有强鲁棒性和快速收敛性, 而且比其他现有的技术更适用于此类问题的成功解决。同年, Sundar和Singh又将人工蜂群算法应用到二次最小生成树问题中, 这个问题即是最小生成树的扩展。Sundar等在将人工蜂群算法算法应用到0-1背包问题后, 其计算结果清晰表明了人工蜂群算法不仅比其他群体智能算法收获了更好的实践效果, 而且还可以快速收敛。其后, Sundar和Singh又将人工蜂群算法应用到二次多背包问题中, 这个问题就是著名的背包问题、多背包问题和二次背包问题的扩展[38]。更多的研究成果还有, 2011年, Szeto等设计了加强版的人工蜂群算法提高了原始版本的解的质量, 并以此解决了车辆路径问题。Ziarati等深入研究了用于受工程限制的资源排班问题的人工蜂群算法的应用。Pal等则提出用人工蜂群算法解决一条供应链的综合采购, 产品生产和装货卸货问题。Hemamalini和Simon又使用人工蜂群算法解决动态经济调度问题, 而在能源操作控制系统中这是一个重要的动态问题[39]。2012年, Singh和Sundar也对应提出了用于最短路径花费的生成树问题的人工蜂群算法[40]。2013年, 宁爱平等再次将人工蜂群算法应用于语音识别。刘俊霞等还将人工蜂群算法应用于信道分配, 具体仿真结果表明, 改进后的算法能较好地解决无线信道分配问题[41]。2014年, 再有张春琴将人工蜂群算法应用于无线传感器网络分簇规划中。此外, 王荣杰等进一步发表了人工蜂群算法在复数盲源分离中的应用[42]。

人工蜂群算法已经在不同领域开发了众多的应用。具体来说, 即包括训练神经网络、解决电气工程中的优化问题、机械和土木工程领域、数据挖掘领域, 尤其是采集、特征选择和规则的发现上、图像处理领域等等。

3 结束语

人工蜂群算法和其他群体智能优化算法有着很多相似之处。具体来说, 就是:

(1) 都具有系统性, 使用群体的概念来表示解空间中的个体集合, 个体与个体之间都是通过信息共享、相互协作来完成迭代繁衍以及最优搜索等任务, 表现出了很强的自组织性。

(2) 大都采用了选择算子, 这就对应了生物界中“优胜劣汰, 适者生存”的自然法则, 而且也是找到最优解的关键因素。

和其他群体智能优化算法相比, 人工蜂群算法也表现出一些独有特性。较为突出的就是, 人工蜂群算法在进行全局搜索的同时, 也进行局部搜索, 并且具有跳出局部最优的优势能力。引领蜂引导个体的搜索方向, 跟随蜂可使算法加速收敛, 侦查蜂则能有助于算法在一定程度上有效地跳出局部最优。而这也是人工蜂群算法中蜜蜂之间互换角色的关键所在, 藉此算法的性能即获得了显著提升。

人工蜂群算法以其控制参数少、简单易实现、强鲁棒性和应用范围广等特点, 日益受到广大研究者的关注与重视。本文介绍了人工蜂群算法的基本模型、原理、实现流程和步骤, 以及国内外的研究现状。据此可知, 人工蜂群算法虽然已经取得了丰硕成果, 但对其的探索依然存有广阔空间, 还有很多需要改进并深入研究之处。例如, 假设算法中有n个食物源, 问题有d维, 迭代t次, 则其时间复杂度大约为nd+t (3nd/2+4n+d) , 这就略高于粒子群算法的时间复杂度, 未来将可从降低复杂度的角度来改进现有算法。

摘要：人工蜂群算法是Karaboga在2005年提出的一种基于蜜蜂觅食行为的群体智能算法, 该算法可以很好地解决连续函数的求解问题, 后因其强大的性能深受研究者的青睐, 得以广泛的研究和应用。本文首先简要介绍了群体智能和人工蜂群算法的发展, 然后详细介绍了人工蜂群算法的原理及实现步骤, 最后综述近十年来国内外对该算法及其应用的研究状况, 进而总结出该算法具有控制参数少、强鲁棒性等优点, 并指出该算法时间复杂度略高的基本事实, 可成为今后改进的研究方向。

关键词：人工蜂群算法,群体智能,觅食行为,连续函数,强鲁棒性

模拟人工算法篇2

在工程技术和科学计算中,经常会遇到求解数值积分∫ $_{a}^{b}$ f(x)dx,除了几种有限类型外,被积函数f(x)往往很难甚至无法求出它的原函数,即使有的原函数能求出来,但是也相当麻烦不适宜于计算,这时常常需要借助近似方法求解近似数值解。数值积分虽然计算方法很多,如梯形求积方法[1]、抛物线求积方法[1]、Newton-Cotes方法、Romberg 方法、Gauss 方法等[2],但这些传统方法都有一定的局限性。其中梯形求积方法和抛物线求积方法适用于光滑性较差的被积函数,但是对于其它被积函数精度较低;Newton-Cotes方法是一种利用插值多项式来构造数值积分的常用方法,但高阶Newton-Cotes方法的收敛性没有保证;Romberg方法虽然收敛速度快,计算精度较高,但是计算量较大;Gauss方法积分精度高、数值稳定、收敛速度较快,但节点与系数的计算较困难。针对这些问题,本文基于对基本人工鱼群算法进行改进提出一种基于人工鱼群算法的优化分割数值积分算法。通过仿真实验与传统的数值积分方法比较表明新算法十分有效,可以看作是传统方法的补充和拓展,在工程中有较大的应用价值。

1 人工鱼群算法

1.1 基本人工鱼群算法

在一片水域中,鱼往往能自行或尾随其它鱼找到营养物质多的地方,因而鱼生存数目最多的地方一般就是本水域中营养物质最多的地方。人工鱼群算法AFSA(Artificial Fish-school Algorithm)[3]就是根据鱼群上述特点提出的一种新型仿生优化算法,通过构造人工鱼来模仿鱼群的觅食、聚群、追尾及随机行为,从而实现寻优,是群体智能思想[4]的一个具体应用。它的主要特点是不需要了解问题的特殊信息,只需要对问题进行优劣的比较,通过各人工鱼个体的局部寻优行为,最终使全局最优值突现出来。作为一种新型的全局寻优策略,它已应用于时变系统的在线辩识、鲁棒PID的参数整定和优化前向神经网络中,取得了较好的效果。

然而随着优化问题的复杂性,基本AFSA在应用中也存在不足:当寻优的空间维数高或区域较大或处于变化平坦的区域时收敛于全局最优解的速度减慢,搜索性能劣化,甚至会陷入局部极小;算法一般在优化初期收敛快,后期却往往较慢;得到的解是满意解,精度不高。因此在具体应用中常常要对它进行改进。

1.2 柯西变异人工鱼群算法

Gunter[5]通过理论分析表明柯西变异算子具有较强的局部逃逸能力。为了增强人工鱼群算法在高维复杂环境下的全局搜索能力和提高搜索效率,本文在基本人工鱼群算法中引入柯西变异算子来对人工鱼的状态Xi=(xi1,xi2,...,xin)进行变异,定义如下:

X′i=Xi·[1+k·Cauchy(0,1)] (1)

其中Cauchy(0,1)的一维概率密度函数为 $f (x) = \frac{1}{π} \cdot \frac{1}{1 + x^{2}}, - \infty < x < + \infty$ ,k是随迭代由1线性减为0的变量,迭代前期变异幅度大,后期变异幅度小。

设ξ是[0, 1]上的服从均匀分布的随机变量,由随机变量生成函数定理[6],Cauchy(0,1)的柯西分布的随机变量生成函数为 η=tan[(ξ-0.5)π]。

为判断随迭代次数增加搜索结果是否有改进,种群迭代后将种群中最优鱼的状态的函数值与公告板[7]进行比较,如果优于公告板,则取代公告板状态。当在连续两次迭代过程中公告板没有改变或变化极小时,此时我们看作鱼群迭代停滞,则启用变异操作。此算法CMAFSA(Artificial Fish-school Algorithm Based on Cauchy Mutation)流程如下:

Step1 初始化群体:在控制变量可行域内随机生成Np条人工鱼,形成初始鱼群。

Step2 公告板赋初值:计算初始鱼群各人工鱼当前状态的函数值y,取y为最小值者进入公告板,并将此鱼位置状态也赋值给公告板。

Step3 行为选择:各人工鱼分别模拟追尾行为和聚群行为,评价行动后的值,选择y值较小的行为实际执行,缺省行为方式为觅食行为。

Step4 公告板更新:种群迭代后,如果种群最优鱼状态的y优于公告板的y,则更新公告板。

Step5 变异条件判断:若公告板在连续两次迭代过程没有改变或变化极小(<η),则执行Step6;否则执行Step7。

Step6 变异操作:用历史最优鱼替换当前群体的最差鱼形成中间种群,对中间种群的人工鱼按式(1)变异,计算变异后各状态的函数值与公告板比较,若优,更新公告板。

Step7 终止条件判断:判断是否已达到预置的最大迭代次数MaxIteration或判断最优值是否达到了满意的误差界内(<ε),若不满足,执行Step3,进行下一代鱼群优化过程;否则执行Step8。

Step8 算法终止:输出最优解(即公告板中人工鱼状态和函数值)。

1.3 CMAFSA性能测试

本文用一个典型的高维(30维)、多峰函数Ackley来测试CMAFSA的性能。算法参数设置如下:Np=100,Try_number=30,δ=0.618, η=10-4,最大迭代次数200次, Visual=5,Step=0.5。独立测试5次(随机生成5个初始群体分别用AFSA和CMAFSA运行), 运行结果如表1和图1(为了便于比较, 图中纵坐标是5次的每代最优值的平均值的常用对数)所示。

从表1和图1可以看出AFSA在优化高维、多峰问题时效果很差,而CMAFSA的精度、收敛速度、稳定性有了非常明显的提高,实际上5次实验中CMAFSA最差的一次是在第114(从图1也可看出)代达到了理论最优值。

2基于人工鱼群算法的优化分割数值积分算法

在数值积分 $\int_{a}^{b} f (x) d x \approx \sum_{i = 1}^{n} f (ξ_{i}) Δ x_{i}$ 的近似计算中,分割的优劣和f(ξi)的替代对求解结果的精度有很大的影响。我们的基本思想是在积分区间[a,b]上用柯西变异人工鱼群算法搜到一个最优的分割,考虑到函数值的变化关系和曲线的弯曲情况,在得到的最优分割对应的小区间上用一个合适的值代替f(ξi)来达到近似计算,算法步骤如下:

Step1 确定人工鱼个体的表达式:Xi=(x1,x2,...,xn),其中xi为积分区间[a,b]内的随机n个节点。

Step2 鱼群初始化:在[a,b]内随机生成Np条人工鱼, 形成初始鱼群。实际上就是在[a,b]上产生Np个随机分割。

Step3 公告板赋初值:计算初始鱼群各人工鱼当前状态的函数值y,取y为最小值者进入公告板,并将此鱼位置状态也赋值给公告板。其中函数值是这样计算的:将人工鱼的状态值置于积分区间的左端点和右端点之间,各自按照升序排好顺序。这样,积分区间[a,b]总共有n+2个节点和n+1个小区间,然后分别计算这n+2个节点相邻节点之间的长度Δxi,i=1, 2, …,n+1。再计算出这n+2个节点对应的函数值和每个小区间中点的函数值。找出每个小区间左端点、中点和右端点的函数值中的最小值wi和最大值Wi,i=1,2,…,n+1,则该个体所对应的函数值 $y = \sum_{i = 1}^{n + 1} | W_{i} - w_{i} | Δ x_{i}$ 。

Step4 行为选择:各人工鱼分别模拟追尾行为和聚群行为,评价行动后的值,选择y值较小的行为实际执行,缺省行为方式为觅食行为。

Step5 公告板更新:种群迭代后,如果种群最优鱼状态的y优于公告板的y,则更新公告板。

Step6 变异条件判断:若公告板在连续两次迭代过程没有改变或变化极小(<η),则执行Step7;否则执行Step8。

Step7 变异操作:用历史最优鱼替换当前群体的最差鱼形成中间种群,对中间种群的人工鱼按式(1)变异,计算变异后各状态的函数值与公告板比较,若优,更新公告板。

Step8 鱼群算法终止条件判断:判断是否已达到预置的最大迭代次数MaxIteration或判断y的最优值是否达到了满意的误差界内(<ε),若不满足,执行Step4,进行下一代鱼群优化过程;否则执行Step9。

Step9 得到最优人工鱼个体状态(xbest1,xbest2,...,xbestn),这n个数同a,b一起排序,从而得到最优分割。

Step10 输出积分 $\int_{a}^{b} f (x) d x \approx \sum_{i = 1}^{n + 1} \bar{f}_{i} \cdot Δ x_{b e s t_{i}}$ 。其中 $\bar{f}_{i}$ 是最优分割所得到的n+1个小区间每个区间左、右端点和三点对应的函数值的加权平均 $\bar{f}_{i} = \frac{f_{i 左} + 4 f_{中} + f_{i 右}}{6}$ ,Δxbesti是最优分割所对应小区间的长度。

3 积分仿真实验与分析

为了检验本文提出的数值积分算法的有效性和正确性,本文给出的一些实例,以下仿真均在Matlab 7.0下编程运行。参数设置如下:Np=50,Try_number=20,δ=0.618, η=10-4,ε=10-4,最大迭代次数200次,Visual=0.1,Step=0.01, n=100。每个函数独立运行5次,并与传统的梯形法、Simpson方法、Composite Simpson方法、Romberg方法和神经网络等比较。

例1 分别计算被积函数 $x^{2}, x^{4}, \sqrt{1 + x^{2}}, \frac{1}{1 + x}, \sin (x), e^{x}$ 六个函数在[0,2]上的积分。与文献[8,9]的结果统计比较如表2所示。

由表2看出传统方法中只有Simpson法在求解函数x2时的结果优外,其他的在这6个函数上效果都不好,而本文的算法对每个函数均独立运行5次皆是精确值,可见精度高且很稳定。

例2 计算积分:

∫ $_{0}^{1}$ e-x2dx

被积函数的原函数不是初等函数,本文算法(参数设置同前)5次运算与文献[9]分别用矩形法、梯形法、Simpson法给出结果统计如表3所示。

由表3看出对于被积函数的原函数不是初等函数的函数,本文的算法也是相当有效的。

例3 计算积分:

$\int_{0}^{48} \sqrt{1 + (c o s x)^{2}} d x$

用传统的方法Romberg比较麻烦,不易处理,文献[9]用神经网络算法得到的结果是58.5205,文献[10]用Composite Simpson rule计算的结果是58.47082,而此积分的精确值是58.4704691。由于此被积函数是一个以π为周期的函数,48=15π+(48-15π),此积分可化为:

$\int_{0}^{48} \sqrt{1 + (c o s x)^{2}} d x = 15 \int_{0}^{π} \sqrt{1 + (c o s x)^{2}} d x + \int_{0}^{48 - 15 π} \sqrt{1 + (c o s x)^{2}} d x$

用本文的算法(参数设置同前)运行5次求得的积分值的最差值是58.47046674929646,最佳值是58.47046909676099,平均值是58.47046871265326,由此看出对于Romberg方法不易处理的函数积分,本文的算法也是很优的。

例4 计算奇异函数:

$f (x) = {\begin{cases} e^{- x} 0 \leq x < 1 \\ e^{- \frac{x}{2}} 1 \leq x < 2 \\ e^{- \frac{x}{3}} 2 \leq x \leq 3 \end{cases}$

在[0,3]上的积分该函数的积分精确值是1.546036,文献[9]用神经网络算法算得的结果是1.5467。用本文的算法(参数设置同前)运行5次求得的积分值的最差值是1.54554025335573,最佳值是1.54606116448507,平均值是1.54600370898978,可见本文算法也可求解奇异函数的积分。

4 结论

本文在分析传统数值积分和人工鱼群算法的基础上提出了一种求解定积分数值解的新算法,此算法对被积函数没有太多的限制,通过四组积分算例实验表明此方法十分有效,此方法可以看作是传统方法的补充和拓展。在优化区间的每一段上如何再处理以及用此算法计算重积分是我们下一段要做的工作。

摘要：在分析传统求数值积分和基本人工鱼群算法不足的基础上,提出了一种基于人工鱼群算法的优化分割数值积分算法,该算法不仅能求解通常意义下函数的数值积分,还能计算奇异函数的数值积分。通过算例与传统数值积分方法比较,实验结果表明该算法是可行的和有效的。

关键词：人工鱼群算法,柯西变异,优化分割,数值积分

参考文献

[1]华东师范大学数学系.数学分析[M].北京:高等教育出版社,2001.

[2]薛密.数值数学和计算[M].上海:复旦大学出版社,1991.

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

[4]Bonabeau E,Theraulaz G.SwarmSmarts[J].Scientific American,2000,282(3):72-79.

[5]Gunter R.Local convergence rates of simple evolutionary algorithms withCauchy mutation[J].IEEE Transactions on Evolutionary computation,1997,4(1):249-258.

[6]王梓坤.概率论基础及其应用[M].北京:科技出版社,1979.

[7]李晓磊,路飞,田国会,等.组合优化问题的人工鱼群算法应用[J].山东大学学报:工学版,2004,34(5):64-67.

[8]Burden R L,Faires J D.Numerical Analysis[M].7th Edition.Brooks/Cole,Thomson Learning,Inc,2001:190.

[9]王小华,何怡刚,曾喆昭.三角基函数神经网络算法在数值积分中的应用[J].电子与信息学报,2004,26(3).

人工鱼群算法研究综述篇3

关键词：鱼群算法,基本原理,改进算法,发展应用,研究趋势

近年来,人工智能学科飞速发展,学者们通过研究动物群体和人类社会的智能行为,提出了群体智能(Swarm Intelligence)算法。它具备天然的分布式和自组织特征[1],是通过模拟自然界生物群体行为来实现人工智能的一种方法。典型的群体智能算法主要有粒子群算法、蚁群算法、等。

2002年,李晓磊等[2]成功地将动物自治体的概念引入优化算法,提出了人工鱼群算法(Artificial Fish Swarm Algorithm,AFSA)。它采用自下而上的思路,应用了基于行为的人工智能方法,因为是从分析鱼类的活动出发进行寻优,故称为人工鱼群算法。目前,关于AFSA算法的研究已经渗透到多个应用领域,并且得到了很好的应用效果,成为群智能计算领域的研究热点之一。

1 人工鱼群算法的基本原理

在一片水域中,鱼生存数目最多的地方一般就是本水域中富含营养物质最多的地方,依据这一特点来模仿鱼群的觅食等行为,从而实现全局寻优,这就是AFSA的基本思想[2]。基本人工鱼群算法是用来解决连续值域内不受约束的优化问题,在离散域内将行为定义稍加改动也同样适用。

假设有条人工鱼,当前状态为Xi,随机选择人工鱼另一状态为Xj;其中,xi=[xid](i=1,2,L,SN,d=1,2,L,D)是一个D维向量,xi=[xid](i=1,2,L,SN,d=1,2,L,D)同为一个D维向量;状态Xi的食物浓度(适应度函数)为Yi=f(Xi),其中f(.)为目标函数;人工鱼个体之间的距离表示为di,j=‖Xi-Xj‖,其感知距离(视野范围)为Visual,移动步长为step,拥挤度因子为δ。算法中,几种行为与寻优命题的解决有着较密切的关系。

(1) 觅食行为

设人工鱼当前状态为Xi,在其感知范围内随机选择一个状态Xj,在求极大值问题时,若Yi

undefined

式中,Rand为一个(0,1)的随机数。

(2) 聚群行为

设人工鱼探索当前邻域内(di,jδYi,表明伙伴中心有较多的食物且其周围不太拥挤,则朝伙伴中心位置方向前进一步;否则执行觅食行为。其数学表达式为:

undefined

(3) 追尾行为

设邻域内(di,jδY,表明Xmax状态具有较高的食物浓度且其周围不太拥挤,则朝Xmax的方向前进一步;否则执行觅食行为。其数学表达式为:

undefined

(4) 公告板

用来记录最优人工鱼个体的状态。

2 基本人工鱼群算法的改进

2.1 初始化的改进

初始化种群是算法进行搜索的起点。AFSA算法的初始种群生成是随机的,通常情况下可以保证初始鱼群分布均匀,但对于个体的质量不能保证,解群中有一部分远离最优解。

宋潇潇等[3]提出了基于极坐标编码的改进人工鱼群算法。它通过设定编码规则,并将此编码方式运用到三种行为当中,计算出每一个编码母体获得的人工鱼的概率,选择大概率的母体作为算法初始化的起点,有效提高算法的收敛性。宋志宇等[4]利用混沌系统产生混沌变量,并在参数允许范围内随机产生各个人工鱼个体的初始状态。陈广洲等[5]引入了免疫算法中的消亡算子,经算子运算更新,相互比较,摒弃非优个体,将其重新初始化,以此保持种群的多样性。

2.2 算法参数的改进

AFSA算法参数较多,且通常情况下是固定的,δ设置不合理,收敛效果不明显。在算法后期,随着人工鱼个体逐渐靠近最优点,这时当前较好的解只有一两位元素与最优解不同,所以在其附近仍采用在Visual与step范围内觅食的方式寻优是不合理的。

王冬冬等[6]提出了分段优化的思想,令食物浓度η为分界线,大于η时,为前期过程,采用较大的step和Visual,能使算法较快地得到一个相对较优的解;小于η时为后期过程,采用较小的step和Visual,得到一个精度更高的解。黄华娟等[7]通过公式(4)和公式(5)自适应减小了步长和拥挤度因子。

undefined

δk+1=αδk . (5)

其中,k为当前迭代的代数,α∈[0,1]为衰减因子。俞洋等[8]通过公式(6)逐渐减小视野。

Visualk+1=αVisualk . (6)

Xiao J M等[9]运用最优适应值变化率K和变化方差σ2作为是否进行参数变化的衡量标准,从而避免算法的退化。

2.3 与其它算法相结合的改进

算法一般在优化初期具有较快的收敛性,而在后期却往往收敛较慢。虽然通过对参数的改进可以解决此问题,但是从计算复杂度、收敛效果及速率等因素来考虑,仅从算法自身改进不足难以达到更高的要求。因此,在AFSA算法中引入其它算法,综合二者的优点,成为AFSA改进的一个主流趋势。

(1) 与粒子群算法相结合

罗德相等[10]将种群分为两部分,一部分运用粒子群算法,一部分运用鱼群算法,将二者比较后的最优值赋予公告板,以此提高收敛速度。