您好, 访客   登录/注册

几种仿生优化算法综述

来源:用户上传      作者:

  摘 要:仿生优化算法是模拟自然中生物体的行为或状态的算法总称。由于该类算法的随机性和相对复杂性,故其应用范围较传统算法更广。介绍了人工神经网络、苍狼算法及鸽群智能算法的背景、基本原理及实现步骤,深入剖析了它们之间的异同,对该类算法的发展远景进行了展望。
  关键词:仿生优化算法;人工神经网络;苍狼算法;鸽群智能算法
  DOI:10. 11907/rjdk. 181975
  中图分类号:TP312 文献标识码:A 文章编号:1672-7800(2019)002-0049-03
  Abstract:Bionic optimization algorithm is a generic term for a class of algorithms that simulates the behavior or state of organisms in nature. Due to the randomness and relative complexity of this type of algorithm,it is wider than traditional algorithms about the application range.This paper proposes the backgrounds, basic principles and implementation steps of three hot or new biology-based algorithms(artificial neural network, gray wolf algorithm, and pigeon-inspired optimization);then their similarities and differences thoroughly are analyzed;finally, some remarks on the development prospects of the algorithms are presented.
  Key Words:bionic optimization algorithm;artificial neural network;grey wolf algorithm;pigeon-inspired optimization
  0 引言
  大数据时代复杂事件的优化问题引人关注,对时间空间复杂度的要求也日益求精。20世纪后期,为解决传统算法能力缺陷,研究出了一系列仿生优化算法。
  仿生优化算法思路从生物系统的进化和自适应现象中得到,它不依赖于严格的数学关系,而是模拟自然界中生物的社会或生存行为,所以应用范围比传统算法更广。目前比较热门或新颖的仿生优化算法有人工神经网络、苍狼算法、鸽群优化算法等。
  人工神经网络(Artificial Neural Network,ANN )是由心理学家McCulloch和数理逻辑学家Pitts通过对人脑的神经元进行抽象而引出,而后被法国地质学家Morlet[1]运用在小波分析即寻找地质数据上,近年在模式识别、信息处理、医学等领域应用广泛。
  苍狼算法(Grey Wolf Algorithm,GWA)是一种群体智能优化算法,2007年Yang等 [2]根据狼群在自然界中的生存行为提出了狼群搜索(Wolf Pack Search,WPS)。2014年,Seyedali Mirjalili等 [3]依照苍狼群居时的领导等级和捕食机制正式提出了苍狼算法,该算法广泛使用在感应电机参数辨识[4]、并行搜索策略优化[5]等方面。
  鸽群优化算法(Pigeon-Inspired Optimization,PIO)是一种新兴的群体智能优化算法,受到自然界中鸽子群体总是自行归巢的启示,2014年由段海滨等[6]提出并成功运用于无人机编控等领域。该算法在飞行器路线规划和控制[7-8]、计算机图像处理、自适应控制[9]等方面潜力巨大。
  1 基本原理
  1.1 人工神经网络
  人脑具有极强的信息辨别能力,在认知外界到一定的阈值时可以将接触的部分信息由神经传输给大脑,也就是人的学习能力。为使机器等其它物质也具有该能力,对人脑神经系统进行精簡和模拟——由相当多数目的神经元(或称节点)交错连接,两个相邻的神经元有一个权重控制信息的传输,最后由每个节点带有的一个激活函数(Activation Function)[10]作为导火索,便构成了人工神经网络。
  以第三代人工神经网络即脉冲神经网络(Spiking Neuron Networks,SNN)[11]为例,它不是基于神经脉冲的频率进行编码,而是加入时间对事物影响因素,所以更具灵活性和适应性,也更接近人脑神经元。脉冲神经网络基本步骤如下:
  (1)收集神经网络参数形成一个数据域,在数据域里选取若干组数据,一部分数据用于完善脉冲神经元模型(数据训练),另一部分数据用于纠正脉冲神经网络模型(数据测试)。
  (2)初始化脉冲神经网络参数,设置所有模块的初始连接权和阈值以及各个模块的准确率。
  (3)对脉冲神经网络进行训练和测试,将项目的数据作为神经网络的输入输出,选取适当的算法如梯度下降学习算法、突触可塑性学习算法和脉冲序列卷积学习算法[12-13]进行训练,关键是选取适当的突触权值学习规则适当修订连接的突触权。
  (4)脉冲神经网络测试。基于测试样本寻找合适的测试样例,输入对应项目参数,得到每个模块的输出(脉冲发放的频率),而后次第计算神经网络的平均输出准确率,如果该准确率不在期望值的允许误差之内则继续进行。
  (5)当所有训练项目结束后进行后续神经网络应用。   1.2 苍狼算法
  狼是群居动物,一般由5-12只组成团队集体活动。它们的等级很像金字塔,由上而下分成4个部分,分别是α、β、δ和ω。α是一对头狼,它们一定时期在部落里具有绝对的权力;β狼负责协助和反馈给α狼,在其它时期有可能成为α狼;δ狼处于权利的第三顺位,通常在捕猎中负责侦查、放哨和实施等工作,它只能命令ω狼;ω狼在金字塔的最下端,数量通常多于α、β、δ狼的总和,它总是听命并跟随前三种狼进行活动,所以该算法的关键是如何利用占群狼数目大半的ω狼搜索能力。
  GWA算法有一个明显缺陷:容易陷入寻找局部最优解僵局,因此以改进过的基于领导者策略的狼群优化算法(Wolf Colony Search Algorithm Based on the Strategy of the Leader,LWCA)[14]为例,最优搜索步骤如下:
  (1)初始化苍狼位置,要求分布尽可能均匀,以便为第(2)步寻找头狼作准备,并确定狼群的规模等基本参数。
  (2)计算苍狼个体的最优值并按顺序排列,选取记录中前三的数据作为实验中苍狼的位置,分别记作α、β、δ,此为领导者分组,余下的苍狼个体组成被领导者分组。
  (3)每只狼都要在周围的N个方向搜索猎物,被领导狼会向领导狼的位置移动。
  (4)由于猎物不一定总离领导狼最近,如果被领导者远离了领导者狼,证明猎物离领导者不是最近,则更新领导者。
  (5)领导者找到食物后通过一个预先设定好的阈值触发告知其它狼对食物进行包围,更新狼的位置。
  (6)寻找接近理论的最优值,按照等级高低先后分配食物并淘汰劣等狼。
  (7)迭代,如果满足条件则输出最优值。
  1.3 鸽群优化算法
  科学家发现鸽子有自主归巢的行为,鸽群飞行时会在不同阶段使用不同的工具辨别方向以快速到达目的地,受此启发提出鸽群算法。鸽群优化算法和苍狼算法一样,群体内部都有着严格的等级顺序,数目类型亦呈现金字塔形状,级别越高个数越少。此外,PIO算法依赖于外界的开放信息,主要受太阳方向、地磁场和对地标记忆力的影响。根据上述机制,模拟出两种新的算子。
  1.3.1 地图和指南针算子
  鸽子本身可以感受到磁场,在飞行过程中会依据磁场强弱纠正飞行方向。当接近目的地时,磁场越来越弱,故用指南针算子[15]衡量这一特性。
  1.3.2 地标算子
  地标泛指鸽群在记忆里见到的所有相似地形。由于鸽群离目的地逐渐接近,随着太阳高度和磁场影响的淡化,地标的导向越发加重。倘若鸽子检索到熟悉的地标就直接向目的地飞去,否则将按照适应值排序后跟随其它熟悉地标的鸽子飞行并淘汰迷失方向者,具体步骤如下:
  (1)初始化鸽群个体位置、速度等在使用PIO算法时所涉及的参数。
  (2)进入地图和指南针算子的使用阶段(地磁操作),更新个体位置,对种群中鸽子个体的适应值(最优值)进行比较并找出全局最优和局部最优。
  (3)比较该阶段迭代次数和最大迭代次数的关系,如果前者大于后者则进行下一步,否则从步骤(2)开始。
  (4)将鸽群中距离目的地较远的鸽子个体淘汰。
  (5)进入地标算子使用阶段(地标操作),计算鸽群中剩余鸽子个体的适应值,重新更新鸽子个体的全局最优和局部最优。
  (6)倘若当前迭代次数大于最大迭代次数则鸽群成功到达目的地,否则从步骤(2)开始。
  为了解决鸽群算法同其它智能仿生算法一样容易陷入局部优化的僵局,尤其是在地磁操作阶段容易陷入局部最优的问题,实际操作时可先引入带权有向图的Dijstra算法[16]进行初步优化,再进行地磁操作和地标操作。
  2 几种仿生优化算法比较
  上述算法都属于目前较流行的智能仿生算法,主要通过借助自然界中生物体的群体行为或机能解决工程中的最优化问题,相同点有:
  (1) 都具有不确定性。与传统算法相比,由于仿生优化算法是利用生物的天然个性,所以在随机搜索过程中有很多不确定因素。
  (2)都需要大量的重复试验。一个仿生算法的使用必然伴随着若干参数,参数的优劣决定了实验结果是否精确,而就目前技术来说只能通过大量的重复实验确定参数取值。
  (3)都不具備严密的数学性[17]。在一些比较权威的基础学科知识如数学的连续性、单调性、凸凹性等面前,仿生优化算法并不能严格遵守。
  (4)适用范围都有局限。一方面,一个新的仿生算法提出会提供一种解决问题的新思路,但从另一方面来说其问题也暴露得非常明显,即不同仿生算法所能解决问题的能力远不如现代计算机,如鸽群优化算法目前只在无人机航路规划[18]方面应用,其它区域尚未有显著成果。
  (5)都具有鲁棒性(Robustness)[19]。因为上述仿生算法不严格依赖于数学分析和建模,故在一定的参数支持下,处于不同环境和条件下的算法强健性有所保障,换句话说便是算法的核心部分无需改正。
  3 其它比较
  相对于基于梯度的人工神经网络来说,苍狼算法和鸽群智能优化算法都容易陷入局部优化的僵局。由于是新提出的仿生算法,应用领域相对较少。而神经网络是大型非线性系统[20],相较于苍狼算法和鸽群算法,会随着时间推进而不断淘汰劣种而逼近“目标”,故人工神经网络的精度分析性能稍显不足。
  4 结语
  本文就模拟生物界中的现象或者活动的3种热门算法进行了论述和对比,尽管它们已经在各自领域得到应用,在某些地方有了创新,但还存在很多不足,将来应从以下方面完善:
  (1)由于仿生优化算法不具备严密的数学性,尤其是在数学分析的基础理论和建模工具上略显不足,所以在今后的研究中应注重理论研究和实际操作的结合推进。   (2)将仿生优化算法和传统算法结合,弥补仿生优化算法局部优化僵局以及传统算法处理大数据的短板,做到取长补短,使多种仿生优化算法糅合在一起,令本来作用领域有限的各个算法互补产生更大的优势,向功能更强、结构更复杂的系统过渡。
  (3)尽管距离第一个仿生算法思想的提出已有半个多世纪,然而该类算法的开发仍旧有很大的空间,很多领域甚至只是浅尝辄止。应扩大此类算法的使用范围,深入挖掘其最大的可能性和可行性,避免其短板,使后续研究人员能有的放矢。
  参考文献:
  [1] 黎林,朱军. 基于小波分析与神经网络的语音端点检测研究[J]. 电子测量与仪器学报,2013,27(6):528-534.
  [2] YANG C G,TU X Y,CHEN J.Algorithm of marriage inhoney bees optimization based on the wolf pack search[C]. Proc of International Conference on Intelligent Pervasive Computing,2007:462-467.
  [3] MIRJALILI S,MIRJALILI S M,LEWIS A.Grey wolf optimizer[J]. Advances in Engineering Software,2014,69(3):46-61.
  [4] 吕小意.  感应电机参数辨识及控制策略研究[D]. 无锡:江南大学,2017.
  [5] 符强,汪鹏君,童楠. 一种基于并行搜索策略的苍狼算法[J]. 计算机应用研究,2016,33(6):1662-1665.
  [6] DUAN H B,QIAO P X.Pigeon-inspired optimization: a new swarm intelligence optimizer for air robot path planning[J]. International Journal of Intelligent Computing and Cybernetics,2014 ,7(1) :24-37.
  [7] 张亚平,孙佩华,李昱辉,等. 基于改进鸽群算法的高超声速飞行器轨迹优化[J]. 飞行力学,2017,35(4):60-64.
  [8] 张亚平. 鸽群智能算法的改进及其在高超声速飞行控制中的应用[D]. 南京:南京航空航天大学,2017.
  [9] 李恩源. 可控串补(TCSC)阻尼电力系统低频振荡控制方法研究[D]. 沈阳:辽宁工程技术大学,2017.
  [10] 石琪. 基于卷积神经网络图像分类优化算法的研究与验证[D]. 北京:北京交通大学,2017.
  [11] 徐学良. 人工神经网络的发展及现状[J]. 微电子学,2017,47(2):239-242.
  [12] MOHEMMED A,SCHLIEBS S,MATSUDA S,et al. Training spiking neural networks to associate spatio-temporal input-output spike patterns[J]. Neurocomputing,2013(107):3-10.
  [13] YU Q,TANG H J,TAN K C,et al. Precise-spike-driven synaptic plasticity: learning hetero-association of spatiotemporal spike patterns[J]. Neurocomputing,2015(5):33-40.
  [14] ZHOU Y Q,LIU J K,ZHAO G W. Leader glowworm swarm optimization algorithm for solving nonlinear equations systems[J]. Electrical Review,2012,88(1b):101-106.
  [15] 段海濱,叶飞. 鸽群优化算法研究进展[J]. 北京工业大学学报,2017,43(1):1-7.
  [16] 黄思铭.  基于改进鸽群算法的无人机航路规划研究[D]. 沈阳:沈阳航空航天大学,2018.
  [17] 王茂海.  仿生优化算法的研究与应用[D]. 无锡:江南大学,2011.
  [18] 段海滨,邱华鑫,范彦铭. 基于捕食逃逸鸽群优化的无人机紧密编队协同控制[J]. 中国科学技术,2015,45(6):559-572.
  [19] 陈建辉.  ART网络的鲁棒性增强方法研究[D]. 成都:电子科技大学,2016.
  [20] 赵启林,卓家寿. 非线性方程组的耦合神经网络算法[J]. 河海大学学报:自然科学版,2000(5):38-40.
  (责任编辑:杜能钢)
转载注明来源:https://www.xzbu.com/8/view-14806499.htm