引言

自1970年起至今，研究人员在求解各种复杂优化问题时，突发奇想将自然界中不同生物的形态、习性和特征以及各种自然现象及其客观规律以仿生学和遗传学角度切入，进行高层次的模拟复现，从而创立了一系列仿生智能优化算法.一般意义上，传统的仿生智能优化算法有诸如遗传算法、蚁群优化算法、微粒群优化算法等，这些经典的算法有数量庞杂的各种改进型算法和融合型算法，针对不同的优化问题均取得了不错的求解效果.

近20年以来，伴随着大数据、人工智能和神经网络等学科研究的长足发展，各种新兴的仿生智能优化算法层出不穷，诸如萤火虫优化算法、狼群优化算法、鸡群优化算法、猴群优化算法、蝙蝠优化算法、杜鹃搜索算法、人工蜂群算法、人工鱼群算法、磷虾群优化算法、果蝇优化算法、群居蜘蛛优化算法、乌贼优化算法等等，还有很多.现在其应用方向已从最早的单目标优化问题逐步转为多目标优化问题、多目标协同优化问题、多目标动态优化问题等方向.

无人机航迹规划问题本身也是一个复杂的优化问题，因而利用各种仿生智能优化算法及其各种改进型算法或融合型算法求解此类问题是无人机航迹规划研究领域中不可忽视的重要方法.

本论文着重介绍四种在无人机航迹规划优化问题及相关研究领域有应用的新型仿生智能优化算法原理，并简要介绍这些优化算法在此领域的研究现状.

1 猴群优化算法

1.1 算法原理与步骤

猴群优化算法(Monkey Optimization Algorithm，MOA)由Zhao和Tang[1]于2008年提出，算法的设计思路是通过模拟自然界中猴群爬山过程中的攀爬、眺望和跳跃几个动作而引出的，旨在设计其相对应的寻优搜索过程，在求解高维数、大规模、多峰值、非凸函数优化问题时具有明显优势.

猴群优化算法的主要步骤分为初始化过程、攀爬过程、眺望-跳跃过程、空翻过程和终止过程等，详细步骤如下：

Step1初始化过程.设置猴群种群规模，最大迭代次数，问题维数，随机初始化每只猴子的初始位置.

Step2攀爬过程.通过多次迭代不断改变每只猴子的所处位置，也即不断更新目标函数的伪梯度值来逐步改善待优化问题的目标函数值，用于寻找局部最优解即每个猴子所在山峰的顶峰.

Step3眺望-跳跃过程.执行完攀爬过程后，猴群中所有猴子均到达各自所在位置附近的山峰的顶峰，也即目标函数达到了局部最优解，因而搜索停滞.此时站在顶峰的每只猴子都会向周围眺望，考察在当前区域的邻近区域内是否有更优解也即有更高的顶峰存在,若存在，则从当前位置跳跃过去，之后重复执行攀爬过程，以便于加快搜索速度.

Step4空翻过程.以当前猴群整体的重心为空翻支点，从当前搜索区域以一定步长空翻转移至新搜索区域，确保猴群跳出局部最优区域，以免算法陷入局部极值并早熟收敛.

Step5终止过程.迭代寻优，重复步骤(1)～(4)，当迭代次数达到预设最大值时算法将停止执行，此时具有最优适应度值的猴子所在位置输出即为所求全局最优解.

1.2 在无人机航迹规划及相关领域的研究现状

在无人机航迹规划问题中，障碍物碰撞检测是极为重要的方面，它是使用各种避障算法的先决条件.贾赛赛等[2]将人工鱼群算法中的人工鱼追尾行为引入猴群优化算法，形成一种混合猴群优化算法，该算法在凸多面体障碍物碰撞检测中能加快猴群整体进化速度，避免陷入局部极值和早熟收敛，同时提高了求解精度，且实验证明可行.

对于经典的旅行销售员问题(Traveling Salesman Problem，TSP)，最早由美国宾夕法尼亚州的Ramser B[3]于1959年以车辆线路“一笔画”问题为由而提出，可以描述为：由一个销售员为位置确定的不同客户配送货物，该配送任务由一个车队执行，要求规划并选择一条遍历所有老客户位置的行车路径且路径无重复，目标是使总行车里程最短.TSP问题可以看成是一个广义的路径规划问题，对于二维平面内或者俯视三维空间而转化形成的二维平面内，基于已指定所需遍历航迹点的物资给养配送无人机的航迹规划问题也有一定借鉴意义.徐小平等[4]利用猴群优化算法求解TSP问题：采用整数编码方式表示猴群位置，解决了猴群算法在处理离散型优化问题时攀爬过程失效的问题,在猴群攀爬过程中引入好动策略并给出改进算法，有效的提高了猴群算法的性能.

2 果蝇优化算法

2.1 算法原理与步骤

果蝇优化算法(Fruit Fly Optimization Algorithm，FFOA)由潘文超[5-6]于2011年提出，算法的设计思路是基于自然界中果蝇觅食行为而推演引出的，旨在设计其相对应的寻优搜索过程，在求解数学函数极值、数据挖掘、广义回归神经网络参数优化等领域已有初步成果.果蝇首先利用敏锐的嗅觉排查空气中漂浮的各种气味以期找到食物源散发的气味，食物源气味浓度与果蝇和食物源间距离有关，距离越近，气味浓度越高，相应地果蝇感知能力就越强.由此可见，果蝇优化算法是一种基于气味源识别寻优原理的优化算法.果蝇优化算法在寻优过程中具有一定的随机性，为了确保果蝇群体向着正确的方向飞行，该算法引入了气味浓度判定值和气味浓度判定函数.

果蝇搜索食物源的过程可以描述为：果蝇群体中每个个体从初始位置向随机方向飞出，之后所有果蝇根据存在个体差异的嗅觉能力再飞向已知食物气味浓度最高的果蝇位置，飞近该位置后，再利用敏锐的视觉寻找食物源或同伴聚集的位置，形成新的果蝇群体位置，再沿随机方向飞出，进而飞往新的食物气味浓度最高的果蝇位置并再次聚集，不断循环往复，直到找到食物源为止.

果蝇优化算法的主要步骤如下：

Step1参数初始化.设置果蝇种群规模，最大迭代次数，随机初始化果蝇种群的初始位置.

Step2分配果蝇个体利用嗅觉搜寻食物源气味的随机方向与距离.

Step3估计每只果蝇个体与原点的距离，距离的倒数即为气味浓度判定值.

Step4将气味浓度判定值代入气味浓度判定函数求出该果蝇个体位置气味浓度.

Step5找出果蝇群体中个体位置气味浓度判定值最大的那只果蝇.

Step6保留这只果蝇的位置坐标与此时的最佳气味浓度判定值(这只果蝇所在位置的气味浓度判定值)，此时果蝇群体利用嗅觉飞向该位置.

Step7迭代寻优，重复步骤(2)～(5)，并判断气味浓度是否优于前次迭代的气味浓度，若是则执行步骤(6)，当迭代次数达到预设最大值时算法将停止执行，此时具有最优气味浓度判定值的果蝇所在位置输出后即为所求全局最优解.

2.2 在无人机航迹规划及相关领域的研究现状

月球探测巡视器常被称为“月球车”，这是一种能够在月球表面实施短距离移动、探测照相、土壤岩石标本采样等作业任务的小型航天器.月球车在探测周围陌生环境的过程中，需要找到从起始位置到目标位置的安全行进路径，也即需要进行路径规划.“月球车”路径规划问题与无人机航迹规划问题有异曲同工之妙，“月球车”和无人机都隶属于无人驾驶机器人，在二维平面内或者俯视三维空间而转化形成的二维平面内，基于动态飞行环境中无人机航迹规划优化算法就可以从“月球车”动态路径规划优化算法中得到启发和借鉴，存在一定的创新价值和推广意义.毛正阳和方群等[7]针对“月球车”动态路径规划的实时性要求，提出一种基于改进型果蝇优化算法的“月球车”路径规划方法：通过改进气味浓度判定值避免算法陷入局部极值和早熟收敛；同时，提出了一种动态环境下“月球车”遇到未知静态障碍物时的避障策略，为月面探测技术进一步发展提供了技术支撑.之后毛正阳和方群等[8]在自己之前研究的基础上，将果蝇个体与原点间距离直接带入气味浓度判定函数，也能避免算法陷入局部极值和早熟收敛，实验表明这种改进型果蝇优化算法能够既快又好地找到“月球车”全局优化路径.

对于求解TSP问题，Li Hengyu等[9]针对标准果蝇优化算法易陷入局部极值和收敛速度慢等缺陷，提出一种改进型果蝇优化算法：引入变异算子，改善种群多样性以避免早熟收敛，采用自适应变步长策略，高效提升搜索速率，实验结果证明有效.Lvjiang Yin等[10]将遗传算法和微粒群优化算法中诸多操作手法引入果蝇优化算法的框架中，形成一种新的融合型算法：在嗅阶段，将果蝇集群机理用于拷贝食物气味浓度最高的果蝇位置，将遗传算法中的变异操作用于随机搜索时果蝇个体间的信息交流，在视觉搜索阶段，使用广义的微粒群优化算法以平衡全局搜索能力和局部搜索能力,实验证明可行有效.段艳明等[11]提出一种改进型果蝇优化算法：把应用于连续型空间的果蝇优化算法离散化处理，来求解路径规划这个离散型优化问题,利用轮盘赌方法初始化路径参数以代替种群的随机初始化,将遗传算法中的交叉算子、变异算子用于全局路径优化,将C2Opt(Complete2-Option)算子应用于局部路径优化以提升局部搜索能力和收敛速度,实验证明可行有效.

3 群居蜘蛛优化算法

3.1 算法原理与步骤

群居蜘蛛优化算法(Social Spider Optimization Algorithm，SSOA)由Erik Cuevas等[12]于2013年提出，算法的设计思路是基于模拟自然界中某种群居蜘蛛合作捕食行为，织网交流行为和繁衍后代行为等而引出的.群居蜘蛛优化算法相较于其他大多数仿生智能优化算法最突出的差异在于，模型中蜘蛛个体是根据性别来分工合作.这种设定不但能真实模仿群体中不同个体间的合作行为，而且在一定程度上权衡了算法的探测能力和开采能力.在群居蜘蛛优化算法中，将蜘蛛网等效为搜索空间，蜘蛛个体在空间中所处位置代表优化问题的一个解，通过让雌雄蜘蛛不断协同进化，最终实现问题的求解寻优.

在生物学中，蜘蛛的大小将用于评价蜘蛛个体完成所指派任务能力的强弱.对应于群居蜘蛛优化算法，将通过计算为每个蜘蛛分配一个权重值，以此代表这个蜘蛛的质量或大小.

在自然界中，蜘蛛个体间的交流方式为主要通过震动公共蛛网来传递信息，震动强度由蜘蛛大小以及两个蜘蛛间的距离共同决定，蜘蛛质量越大，距离越近，震动就越强烈，于是通过公共蛛网所传递的信息亮就越大.群居蜘蛛优化算法中针对震动信息的接收做出如下理想假设，即每只蜘蛛只接收来自其它三类蜘蛛的震动信息：距离它最近且比它重的蜘蛛的震动信息；全局最优蜘蛛个体的震动信息；距离它最近的雌性个体的震动信息.

群居蜘蛛优化算法的主要步骤分为：参数初始化过程、种群协作过程、繁殖交配过程和终止过程等，具体步骤为：

(1)参数初始化过程.

Step1设置搜索空间维数、最大迭代次数、概率因子，计算每一维的蜘蛛交配半径.

Step2根据蜘蛛种群中雌雄比例分配种群性别比例，从而初始化蜘蛛种群规模(包含由随机数计算生成的雌性个体数目和进而得到的雄性个体数目)，进而计算并初始化雌性初始种群中雌性个体的初始位置和雄性初始种群中雄性个体的初始位置，开始优化迭代过程.

Step3根据目标函数计算蜘蛛个体适应度值，为每只蜘蛛分配权重值.找到全局最优的蜘蛛个体，找到与每只蜘蛛距离自己最近的雌性个体和距离自己最近且权重值比自己更高的蜘蛛个体，并分别计算这三种蜘蛛的震动因子.

(2)种群协作过程.

Step1雌性种群协作过程.雌性蜘蛛通过震动公共蛛网来吸引或排斥其它个体，群居蜘蛛优化算法为模拟这一行为，针对雌性个体设计了依概率判别吸引或者排斥的两种合作震动模式，由此计算更新雌性蜘蛛位置.

Step2雄性种群协作过程.雄性蜘蛛会根据权重值大小被分为统治雄蜘蛛与被统治雄蜘蛛.权重较大的统治雄蜘蛛会吸引雌性蜘蛛进行繁殖交配行为，而权重较小的被统治雄蜘蛛则会向种群的中间位置聚集，协同其它被统治雄蜘蛛利用统治雄蜘蛛所浪费的食物和资源等存活下来.在雄性子种群中，雄性个体按权重值降序排列，取中间权重值为参考值，由此计算更新雄性蜘蛛位置.

(3)繁殖交配过程.

Step1蜘蛛种群中的雌性蜘蛛将与在她交配半径范围内的统治雄蜘蛛发生交配繁殖行为，同时在统治雄蜘蛛的交配半径范围内也可能存在不止一只雌性蜘蛛，因而对相互处于交配半径范围内的雌性蜘蛛与统治雄蜘蛛采用轮盘赌机制产生新生蜘蛛个体的位置，概率为父代蜘蛛权重值占总权重值的比例.

Step2为了真实再现自然界中“物竞天择，适者生存”的法则，同时为了保证种群规模的稳定性：评价新生蜘蛛个体的适应度值，将其与种群中适应度值最差的蜘蛛个体进行比较:若新生个体较好，则淘汰原有最差个体，将新生个体保留加入蜘蛛种群；若新生个体较差，则淘汰新生个体，蜘蛛种群无变化.

Step3再次评价蜘蛛群体中所有个体适应度值，找出最优蜘蛛个体及其位置.

(4)终止过程.迭代寻优，重复步骤(2)～(3)，当迭代次数达到预设最大值时算法将停止执行，此时输出的最优蜘蛛个体所在位置，即为所求全局最优解.

3.2 在无人机航迹规划及相关领域的研究现状

对于求解TSP问题，王丽等[13]为了改善群居蜘蛛优化算法的寻优性能，提出一种自适应多种群回溯群居蜘蛛优化算法：通过引入自适应决策半径，保证算法执行后期蜘蛛种群的多样性,动态划分蜘蛛种群为多个子种群，设计不同的蜘蛛个体适应度值更新方式，提升了算法的局部深度寻优能力.根据进化程度差异执行不同的回溯迭代更新策略，以确保最大限度寻找到全部极值点.实验结果表明这种改进型群居蜘蛛优化算法具有较快收敛速度和较高收敛精度，并可以成功应用于TSP问题的求解.

4 乌贼优化算法

4.1 算法原理与步骤

乌贼优化算法(Cuttlefish Optimization Algorithm，COA)由Adel Sabry Eesa等[14]于2013年提出，算法的设计思路是通过模拟海洋中乌贼的皮肤细胞变色原理来寻找优化问题的最优解而引出的，在乌贼皮肤细胞变色过程中，反射和可见是两个最主要的进程.反射进程仿真了入射光线的反射机制，可见进程则仿真了乌贼可见度的匹配模式，这两个进程被用来做为全局最优解的搜索策略.简单来说，乌贼优化算法主要是通过潜在解(也即细胞)模拟乌贼皮肤中不同层次细胞反射和吸收光线的机制，进而迭代求解出搜索空间中个体代价最小的乌贼皮肤细胞.

乌贼作为一种通过改变身体颜色来适应环境变化而谋求生存的水生头足类动物，是广为人知的.乌贼能够变色的原因在于皮肤表面堆积了不同层次的三种细胞，分别为色素细胞、虹彩细胞和白色素细胞.色素细胞位于乌贼皮下第一层，是包含色素的弹性小囊细胞，每个小囊通过15～25块肌肉来控制其伸缩：肌肉收缩时，细胞舒张，小囊内部色素大面积呈现于细胞表面；肌肉舒张时，细胞收缩，色素则被回收到小囊内部.虹彩细胞位于乌贼皮下第二层，是由不同层次结构的高亮血小板堆积而成，其主要作用是反射光线来隐藏乌贼器官.白色素细胞位于乌贼皮下第三层，是使乌贼呈现白色斑点的扁平结构细胞，能够有效反射大部分可见光波长的入射光线，使得乌贼呈现出与入射光线同波长的颜色并自然而然“隐身”融入周围环境当中，这种能力常被用于躲避天敌.

色素细胞中含有红色、橙色、黄色、黑色、棕色这五种染料，加上白色素细胞本身的白色，则乌贼体内共存在六种染料.乌贼皮肤能根据周围环境颜色变化而适应性呈现出相同颜色，主要依赖这三种细胞共同作用，相互协调来达成.具体而言，乌贼皮肤呈现的颜色取决于光线入射到皮肤时，被哪种细胞或哪几种细胞共同反射，此时将虹彩细胞和白色素细胞统称为反射细胞，这三种细胞的生理可变性确保了乌贼皮肤产生不同的光学效果.

乌贼优化算法的主要步骤如下：

Step1初始化过程.在搜索空间内随机生成初始乌贼皮肤细胞种群，并确定种群规模和最大迭代次数.

Step2计算每个乌贼皮肤细胞的代价函数，以此评估每个乌贼皮肤细胞位置优劣程度.

Step3将乌贼皮肤细胞种群均匀分为四个子种群.

Step4计算乌贼皮肤细胞种群的平均代价并存储.

Step5分别计算生成第一、二、三、四子种群中每个乌贼皮肤细胞的反射度和可见度，由此计算每个乌贼皮肤细胞的个体代价.

Step6终止过程.迭代寻优，重复步骤(4)～(5)，并判断本次四个子种群中乌贼皮肤细胞的个体代价是否大于前次迭代得到的最优乌贼皮肤细胞代价：若是，则保留前次迭代得到的最优乌贼皮肤细胞的位置和代价值，将其更新为本次迭代后得到的最优乌贼皮肤细胞，而后转去执行步骤(4)～(5)；若不是，则将本次四个子种群中个体代价最小的乌贼皮肤细胞更新为本次迭代后得到的最优乌贼皮肤细胞，保留其位置和代价值，而后执行步骤(4)～(5).直到迭代次数达到预设最大值时算法将停止执行，此时具有最小个体代价的乌贼皮肤细胞所在位置输出即为所求全局最优解.

4.2 在无人机航迹规划及相关领域的研究现状

舒纬伟等[15]将基本的乌贼优化算法与概率地图算法相结合，应用于不确定战场环境中无人机航迹规划优化问题的求解，有效缩小了概率地图的规划空间，减小了无人机航迹规划搜索范围，提高了算法收敛速度，缩短了计算时间.实验证明这种乌贼优化算法与概率地图算法相结合的融合型算法相较于传统的概率地图算法在求解无人机航迹规划优化问题时，复杂度更低，计算内存占用更少，更能满足无人机航迹规划的要求.

Mohammed Essaid Riffi等[16]首次将基本乌贼优化算法离散化处理，形成一种离散乌贼优化算法，并用此算法成功求解了TSP问题.

5 总结与展望

考虑到无人机航迹规划优化算法需要与时俱进以满足日益复杂的飞行任务与飞行环境的要求，本论文选取了猴群优化算法、果蝇优化算法、群居蜘蛛优化算法和乌贼优化算法四种新型仿生智能优化算法进行综述.着重介绍了其原始型算法的基本原理和步骤，基于无人机航迹规划优化及相关研究领域，列举了这四种新型仿生智能优化算法的近期研究成果.

仿生智能优化算法是一类不确定性拟自然算法，不但现有算法的各种改进型算法和融合型算法层出不穷，而且时常诞生新的算法.由此可见，其发展前景广阔，在未来依然会是智能优化领域的研究热点之一.

展望未来，将混沌、动态自适应、量子力学、反向学习和小生境等原理融合进算法的进化过程，是仿生智能优化算法改进的一个新趋势.将种群内部并发执行策略和若干子种群间信息传递与交互需求纳入仿生智能优化算法的群体适应度值评价体系和随机搜索策略等范畴，则又是仿生智能优化算法改进的另一个新趋势.

参考文献：

[1] ZHAO R Q， TANG W S. Monkey algorithm for global numerical optimization[J]. Journal of Uncertain Systems，2008，2(3)：164-175.

[2] 贾赛赛，刘志勤，杨雷,等.基于混合猴群算法的凸多面体碰撞检测[J].计算机工程与设计，2016，37(10)：2789-2793.

[3] 王凌.智能优化算法及其应用[M].北京：清华出版社，2001.

[4] 徐小平，张东杰.基于猴群算法求解旅行商问题[J/OL].计算机工程与应用，2017-02-10.(2017-02-10)[2017-04-12].http：//www.cnki.net/kcms/detail/11.2127.TP.20170210.0832.026.html.

[5] 潘文超.果蝇最佳化演算法[M].台北：沧海书局，2011.

[6] PAN Wentsao. A new fruit fly optimization algorithm：taking the financial distress model as an example[J]. Knowledge-based Systems，2012(26)：69-74.

[7] 毛正阳，方群，李克行,等.应用改进果蝇优化算法的月面巡视器路径规划[J].中国空间科学技术，2014(5)：87-93.

[8] 毛正阳，方群.基于果蝇优化算法的月球车全局路径规划[J].电子设计工程，2014，22(23)：45-50.

[9] LI Heng-yu, CHEN Ji-qing, HUANG Quan-zhen, et al. An improvement of fruit fly optimization algorithm for solving traveling salesman problems[R]. Hailar, China: International Conference On Information And Automation，2014.

[10] YIN Lv-jiang, LI Xin-yu, GAO Liang, et al. A new improved fruit fly optimization algorithm for traveling salesman problem[R]. Chiang Mai, Thailand: 8th International Conference On Advanced Computational Intelligence，2016.

[11] 段艳明，肖辉辉.求解TSP问题的改进果蝇优化算法[J].计算机工程与应用，2016，52(6)：144-149.

[12] CUEVAS E, CIENFUEGOS M, ZALDIVA D, et al. A swarm optimization algorithm inspired in the behavior of the social spider[J]. Expert System with Applications，2013，40(16)：6374-6384.

[13] 王丽，宫建平，王晓凯.自适应多种群回溯群居蜘蛛算法求解TSP问题[J].数学的实践与认识，2017，47(2)：221-229.

[14] EESA A S, BRIFCANI A M A, ORMAN Z. A new tool for global optimization problems: cuttlefish algorithm[J]. International Journal of Mathematical, Computational, Physical, Electrical and Computer Engineering，2014，8(9)：1235-1239.

[15] 舒纬伟，敬忠良，董鹏.基于乌贼算法的无人机航迹规划[J].科学技术与工程，2017，17(2)：120-125.

[16] MOHAMMED Essaid Riffi, MORAD Bouzidi. Discrete cuttlefish optimization algorithm to solve the traveling salesman problem[R]. Marrakech, Morocco: 3rd World Conference On Complex Systems，2015.

[责任编辑：史宝明]

TIANJiang

(School of Electrical Engineering and Information Engineering, Lanzhou University of Technology,

Lanzhou 730030, China)

Abstract:Considering the UAV (Unmanned Aerial Vehicle) trajectory planning optimization and other correlative research fields, four new types of bionic intelligence optimization algorithm: monkey optimization algorithm, fruit fly optimization algorithm, social spider optimization algorithm and cuttlefish optimization algorithm have been selected and reviewed in this paper. First, it emphatically introduces the basic principles and general steps of those algorithms’ archetypes; second, it enumerates the recent research achievements of these four new types of bionic intelligence optimization algorithm in the UAV trajectory planning and other correlative research fields; third, it forecasts the future trend of bionic intelligence optimization algorithm.

Key words:UAV trajectory planning；bionic intelligence algorithm；monkey optimization algorithm；fruit fly optimization algorithm；social spider optimization algorithm；cuttlefish optimization algorithm

作者简介：田疆(1990-)，男，陕西西安人，在读硕士，研究方向为智能优化与控制.E-mail:godface@126.com.

文章编号：2095-6991(2017)06-0080-06

中图分类号：V279.2