知识引导的智能优化算法在航路规划中的应用＊

刘 钢，老松杨，侯绿林，谭东风

（国防科学技术大学 信息系统工程重点实验室，湖南 长沙 410073）

航路规划是一种多约束多目标非线性优化问题，反舰导弹航路规划是其中的一类新问题，对它的研究应把握反舰导弹的航路特征而有针对性地展开.反舰导弹航路规划是一个空间搜索问题，需要采用基于几何学的搜索算法进行求解.目前关于这类寻优算法的研究比较深入，智能优化算法是其中的一个大类，它是一类基于种群、能够自适应搜索的优化方法.近年来出现了很多基于智能优化算法的航路规划方法，常用的有遗传算法[1]、蚁群算法[2]和粒子群算法[3]等.这些算法大都思想简单，易于操作，且对优化函数没有特殊的要求.

智能优化算法的主要缺点是收敛性问题，包括容易出现早熟收敛和收敛速度慢2个方面[4].导致这些缺点的一个重要原因就是智能优化算法中缺乏明确的导向因子[5－6]，引导进化的思想因此而被提出，其目的就是加速收敛和避免早熟收敛.

在现有的求解航路规划问题的智能优化算法中，还没有考虑直接挖掘和应用航路规划问题领域知识进行引导优化的方法.鉴于此，本文直接将航路规划问题相关领域知识平行地融入到智能优化算法中，提出一类基于智能优化算法的航路规划方法.

1 知识引导进化

1.1 引导进化及其存在的问题

引导进化就是利用特定问题领域的启发式知识来指导、约束进化过程，它对问题的求解效果依赖于对问题领域认识的深度，并且算法性能也依赖于设计的技巧[7].针对这个问题，有关学者[5]提出通过传统人工智能手段和特定知识模型来实现对智能优化算法的进化引导，具体措施是采用知识模型从前期优化过程中挖掘有用知识来指导智能优化模型的后续优化过程.这种知识存在明显缺陷：1）这种知识是间接和抽象的“隐式”知识，它需要从前期进化过程中学习和归纳，而可供学习的样本太少，因此，这种知识的可信度很低；2）它对算法的引导仍然是在对优化算法本身后期的进化机制和进化过程逐步进行修补，无法适应进化环境的改变，缺乏全局性；3）由于它并没有直接以问题领域为牵引，而是被动地、“守株待兔”式地获取知识，因此，在求解具体问题时，这种知识具有极大的不确定性，并且无法解决如何运用这种知识引导算法的问题.

1.2 特定领域知识

本文认为在求解航路规划问题时，可从问题背景中直接挖掘一些有用的知识，然后应用这些知识对优化过程进行全过程引导和监督.这里的知识指的是特定的领域知识，首先对它们进行形式化建模，然后结构化为可以融入智能优化算法的优化策略，具体的智能优化算法都可以通过开放的方式对这些策略进行更新和应用.本文所采用的特定领域知识与传统引导进化所采用知识[5－7]的比较如表1所示.

表1 特定领域知识与传统引导进化知识的比较Tab.1 Comparison of customizing domain knowledge and the knowledge adopted by conventional conducting evolution

本文所指特定领域知识与智能优化算法的关系如图1所示.传统引导进化所采用的知识[5]与智能优化算法的关系如图2所示.

图1 特定领域知识与智能优化算法的关系Fig.1 The relation between customizing domain knowledge and intelligent optimization algorithms

从图1和图2可以看出，特定领域知识直接来源于待优化问题，而在传统的引导进化方法[5]中，所采用的知识来源于对智能优化算法进化过程的学习，智能优化算法也只是十分隐含地从待优化问题所输出的适应度中获得极为有限的“暗示”，其知识模型与待优化问题之间并无直接交互.因此，对于求解待优化问题，特定领域知识的针对性更强，引导效果更好.

图2 传统引导进化的知识与智能优化算法的关系Fig.2 The relation between knowledge adopted by conventional conducting evolution and intelligent optimization algorithms

2 知识引导型智能优化算法的航路规划求解框架

本节拟建立一个知识引导型智能优化算法的航路规划问题求解框架.该框架采用智能优化算法和航路规划中的特定领域知识相结合的集成建模思路：首先，通过分析反舰导弹的航路特征提炼出某种特定领域知识；其次，将这种特定领域知识形式化并结构化为某种能够改进算法性能的元策略；最后，将元策略实例化为与具体优化算法相匹配的优化策略，这将是个开放式的问题，不同的智能优化算法就有不同的匹配策略.特定领域知识以元策略的形式对智能优化算法的优化过程进行引导和监督.

2.1 知识引导方式

对于同一个待优化问题，采用的智能优化算法不同，所对应的编码形式就不同，其算法搜索空间和约束条件表示形式也是不一样的.因此，本文把算法搜索空间和约束条件表示形式归于智能优化算法范畴.为了描述引导方式，将智能优化算法形式化定义为3个引导对象的集合.

定义1 智能优化算法的集合论定义.

式中：IOA表示智能优化算法；CC表示约束条件表示形式；SS表示算法搜索空间；EMP表示算法进化机制和过程.

从上述形式化定义中可以看出，对智能优化算法的引导方式无非就是对它的3个引导对象进行单独引导或者是组合引导，那么，这里一共有7（即23－1）类引导方式.可以将每一类引导方式看作一个集合，每一类引导方式又包括多种引导方法和策略.7类引导方式的集合论描述如图3所示，其中，Ⅰ，Ⅱ，Ⅲ类为分别引导；Ⅳ，Ⅴ，Ⅵ，Ⅶ类为组合引导.

图3 7类引导方式的集合论描述Fig.3 The set theory description of 7kinds of conducting manner

实际上，现有的对智能优化算法的许多改进工作都可以归结为这几类引导方式.例如，精英保留[4，8－9]和引入子群[10－11]这2种策略都属于对算法搜索空间SS的设计，它们的出发点是使算法的搜索空间更加合理，但最终只在一定程度上达到了维持个体多样性以及使早熟收敛局部化的效果，对进化过程的引导并不明确.其他比如采用自适应操作算子[12]属于对约束条件表示形式CC的设计，用机器学习来控制进化[13]属于引导进化机制和过程EMP，它们都没有考虑到个体进化（环境和特点）的复杂性，并且对进化过程的引导都不明确.以上都是从单独引导的角度进行阐述，事实上各类引导方式之间往往是互相耦合的，更多的时候以组合引导的形式呈现.

2.2 反舰导弹航路规划的特定领域知识

通过对反舰导弹航路规划问题进行分析研究，得到了一些特定领域知识，这些知识主要来源于反舰导弹的航路特征[14]，包括功能区域簇及其几何学渐变规律以及其他航路性能约束.现将本文主要采用几个相关知识归纳如下[14－15]：

1）功能区域簇及其几何学渐变规律.

规律1 由于受最大有效射程的限制，满足导弹航路距离约束的所有航路转向点（导弹航向发生改变的航路点）必然在功能区域之内；

规律2 由于受剩余最大有效射程的限制，满足导弹航路距离约束条件的所有航路点必然在与其对应的剩余功能区域之内；逆之，也成立；

规律3 在逆向航路规划过程中，剩余功能区域逐渐变小，最后收敛于发射点；对于相邻两功能区域而言，后者包含于前者，并且两者必内切于一点.

2）其他航路性能约束 .最大转向角度的约束；最小直线航段距离的约束.

2.3 航路规划的求解框架及其运行机制

根据上述知识各自的特点，它们对智能优化算法的引导方式也是不同的：其他航路性能约束用来设计约束条件表示形式CC，属于Ⅰ类引导方式；功能区域（规律1）用来设计合理的算法搜索空间SS，属于Ⅱ类引导方式；功能区域簇及其几何学渐变规律（规律2和规律3）也是对算法搜索空间SS的引导，并且其所引导的是算法实时搜索空间，这似乎也属于Ⅱ类引导方式，但前提是它必须被结构化为某种元策略来引导算法的进化机制和过程EMP，这又属于Ⅲ类引导方式，因此本质上它是一种组合引导方式.知识引导型智能优化算法的航路规划基本求解框架如图4所示.知识引导型智能优化算法的航路规划求解框架的运行机制分别如图5和图6所示.

图4 知识引导型智能优化算法的航路规划求解框架Fig.4 The framework of knowledge－conducting intelligent optimization algorithms for solving path planning

图5 特定领域知识引导进化的过程Fig.5 The process of evolution conducted by customizing domain knowledge

图6 每次迭代中的分步更新元策略Fig.6 The sequential update meta－strategy in every iteration

图5中描述了特定领域知识引导进化的过程.图5中上部描述了智能优化算法的优化进程，不同的智能优化算法按照各自的进化机制对航路规划问题的可行空间进行搜索，经过k次迭代，最终收敛到最优或近似最优的个体 .图5中下部描述了获取特定领域知识以及引导进化的过程，先从航路规划问题中获取特定领域知识，然后根据它们各自特点选择对应的引导方式对智能优化算法的优化进程进行引导.图6描述的是算法每次迭代中个体的更新机制及过程.图6中所刻画的功能区域（簇）及其几何学渐变规律对算法（实时）搜索空间的引导是十分直观的，实现这种引导的前提条件是需要元策略的支持，即必须引入某种元策略来改进进化机制，使得特定领域知识与智能优化算法相匹配.为此，作如下定义.

定义2 功能区域的几何学渐变规律使得航路的相邻节点间存在关联关系，即后一个节点的合法范围受到前一个节点的约束，需要将其映射为智能优化算法中个体分量之间的关联关系，为了在算法中实现这种约束关联性，对个体中参与更新的各分量按顺序逐步进行更新，将这种策略称为分步更新元策略.

其他航路性能约束对进化过程的引导则通过适应值函数的设计来实现.

将知识引导型智能优化算法的航路规划求解框架实例化为采用具体智能优化算法的航路规划方法，这是一个开放式问题，智能优化算法不同，优化策略就不同.将（分步更新）元策略实例化为具体优化策略的过程必须要适应所采用智能优化算法的特征.下面以粒子群优化（Particle Swarm Optimization，PSO）算法为例，验证上述基本框架的正确性和有效性.

3 仿真实验及分析

3.1 选用算法及其基本设计

本文选用PSO算法主要是考虑两个方面的原因.一方面是PSO算法本身具有的性能优势 .首先，PSO算法具有概念简单，实现容易，易于操作，调整参数少等优点 .其次，PSO算法的鲁棒性好，收敛速度快，这两个显著特点使得它非常适合于对实时性要求较高的复杂问题进行求解.另一方面是PSO算法对航路规划问题的适应性 .首先，PSO算法无论是从编码方式还是进化过程来说，都具有与其他智能优化算法无可比拟的几何表达能力，从几何空间到解空间（搜索空间）的映射十分直观 .其次，作为一种全局连续搜索算法，其进化公式和进化过程都是连续的，这两点与非网格拓扑的航路规划问题的几何学特点十分吻合.

知识引导的航路规划PSO算法是知识引导型智能优化算法的航路规划求解框架的验证及应用实例，它是在通用求解框架下采用PSO算法来求解反舰导弹航路规划问题，技术方法就是运用元策略来改进算法性能，需要采用合适的编码方式和进化过程将通用求解框架中的元策略映射为与PSO算法相匹配的进化策略.算法基本设计如下：1）为了记录每个航路转向点的位置信息，采用定长实数编码粒子结构.一个粒子表示搜索空间中的一条备选航路，粒子中的相应分量代表航路点的位置分量.2）采用文献[15]中的多属性模糊优化方法建立适应度函数.

3.2 实验方案设计和实验环境

实验方案：为了测试本文提出的不同引导方式对PSO算法的引导效果，在相同的实验条件下，分别在不采用知识引导进化和采用Ⅰ，Ⅳ，Ⅶ3类引导方式的情况下对PSO算法进行4组仿真实验.

实验1 不采用知识引导进化.

实验2 采用引导方式Ⅰ.使用航路性能的限制对算法进行约束引导，具体方法是将航路性能约束条件以惩罚代价的形式加入适应值函数的“加权和”.

实验3 采用引导方式Ⅳ，它是引导方式Ⅰ和Ⅱ的组合形式.使用功能区域对算法的搜索空间（解空间）进行引导，具体方法是将功能区域映射到粒子所存在的R2n空间中.

实验4 采用引导方式Ⅶ，它是引导方式Ⅰ，Ⅱ和Ⅲ的组合形式.使用功能区域簇及其几何学渐变规律所指代的航路规划领域知识的结构化元策略对算法的进化机制和过程进行引导，具体方法是将功能区域簇及其几何学渐变规律（粒子分量之间的关联性）映射到粒子进化过程中.为了体现这种关联性，算法并不是对粒子的整个速度（或位置）分量同时进行更新，而是采用递归思想对粒子各分量按顺序逐步进行更新的分步递归进化策略.

可以看出，以上4组实验所采用的引导方式是逐渐加强的.

实验环境：硬件环境为Genuine Intel（R）CPU 1.80GHz，1G内存的PC机，运行环境为Windows XP Professional，编 程 环 境 为 Matlab Release 2009a.综合考虑航路质量（精度）与规划时间，通过反复实验，设定种群大小为100，航路转向点个数为3，即粒子维数为6，最大迭代次数为200.

3.3 算法性能测度和实验结果

本文仿真实验的目的是测试算法的寻优精度和收敛速度，算法性能测试采用以下3个评价指标：1）平均最优适应值fmean；2）最优适应值的标准差σ；3）平均迭代次数MIT.其中，MIT是指所得适应值结果满足规定阈值时，算法所需平均迭代次数.对最大迭代次数内仍不能满足规定阈值的实验，不参与此测度计算.

每个实验独立进行20次仿真，对于第i次仿真，分别记录第j次迭代结束时生成的最优航路的适应值fi，j以及达到规定阈值所需的迭代次数ITi，再记录每组实验中迭代200次时仍不能满足规定阈值的仿真次数jn.则每组实验第j次迭代后的平均最优适应值fmeanj、迭代200次以后平均最优适应值的标准差σ以及MIT分别为：

经整理后的实验结果数据如表2所示.4组实验的平均最优适应值的收敛曲线如图7所示.

表2 4组实验的算法性能测度结果比较Tab.2 Comparison of performance measures results produced by 4experiments

图7 4组实验的平均最优适应值收敛曲线Fig.7 The convergence curve of mean best fitness respectively generated by 4experiments

3.4 实验结果比较与分析

对实验结果进行比较，可以得到以下结论：

1）从fmean的角度比较来说，除了实验1和实验2相差无几以外，随着引导方式的逐渐加强，得到的fmean越来越大，说明算法的寻优质量和精度逐渐提高.2）从σ的角度比较来说，除了实验1和实验2相差无几以外，随着引导方式的逐渐加强，得到的σ越来越小，并且是成数量级地减小，表明算法的鲁棒性和稳定性得到了很大的提高.3）从MIT的角度比较来说，实验4的MIT明显小于其他3组实验，实验2和实验3的MIT又比实验1的小了许多，表明算法的收敛速度也得到了不同程度的提高.

从以上结论可以看出：采用了知识引导的各组实验都比没有采用知识引导的实验1在算法的整体性能上有了不同程度的提高，这充分说明了知识引导进化的有效性.但实验4所提高的幅度要比其他各组实验的大很多，而实验2与实验1的比较却并不明显，这同时也说明了不同引导方式所产生的引导效果有很大的差别.具体分析如下：

1）实验1和实验2的实验结果在整体上相差不多，这说明对适应值函数的惩罚“加权和”形式的引导效果十分有限，究其原因是适应值函数只对个体的优劣进行排序，其对算法性能没有太大的影响.

2）实验3的实验结果在整体上比前2组实验有了一定程度的提高，说明对搜索空间的引导效果比较好，究其原因是其排除了种群中比较劣质的个体，从整体上提高了种群的质量.

3）实验4的实验结果在各方面均有很大幅度的提高，这说明对算法进化机制的引导效果非常好，究其原因是种群中的个体全部为非劣个体，每一代种群的质量都很好.

4 结束语

为了解决传统智能优化算法的早熟收敛问题，本文引入知识引导进化的策略求解反舰导弹航路规划问题，提出了一种知识引导型智能优化算法的航路规划求解框架.以PSO算法为例，根据航路规划特定领域知识的各自特点选择相应的引导方式对不同的引导对象进行引导，实现了特定领域知识和引导对象之间的良好匹配以及问题领域背景和智能优化算法的良好结合.本文提出的对于智能优化算法的3个引导对象和7类引导方式具有普适意义，特定领域知识引导的智能优化算法问题求解框架也可以运用到其他优化问题中，具有很好的借鉴意义.

[1] TAL S，COREY S.Assignment of cooperating UAVs to simultaneous tasks using genetic algorithms[R].San Francisco：AIAA，2005：5829－5843.

[2] NAUYEN H V，NGO A V，SEUNG G L，etal.Obstacle avoidance path planning for mobile robot based on multi colony ant algorithm[C]／／First International Conference on Advances in Computer－Human Interaction.Martinique：IEEE，2008：285－289.

[3] JUNG L F，JARED S K，VIJAY K，etal.Path planning of unmanned aerial vehicles using B－splines and particle swarm optimization[J].Journal of Aerospace Computing，Information，and Communication，2009，6（4）：271－290.

[4] RUDOLPH G.Convergence analysis of canonical genetic algorithms[J].IEEE Transactions on Neural Networks，1994，5（1）：96－101.

[5] 邢立宁.演化学习型智能优化方法及其应用研究[D].长沙：国防科学技术大学信息系统与管理学院，2009.XING Li－ning.Research on the learnable intelligent optimization approaches and its applications[D].Changsha：School of Information Systems and Management，National University of Defense and Technology，2009.（In Chinese）

[6] 曹先彬，许凯，章洁，等.基于生命期引导的生态进化模型[J].软件学报，2000，11（6）：823－828.CAO Xian－bin，XU Kai，ZHANG Jie，etal.Ecological evolution model guided by life period[J].Journal of Software，2000，11（6）：823－828.（In Chinese）

[7] 范磊，阮怀忠，焦誉，等.用归纳学习引导进化[J].中国科学技术大学学报，2001，31（5）：565－570.FAN Lei，RUAN Huai－zhong，JIAO Yu，etal.Conduct evolution using induction learning[J].Journal of China University of Science and Technology，2001，31（5）：565－570.（In Chinese）

[8] DEJONG K A.An analysis of the behavior of a class of genetic adaptive systems[D].Michigan：University of Michigan，1975.

[9] BHANDARI D.Genetic algorithm with elitist model and its convergence[J].International Journal of Pattern Recognition and Artificial Intelligence，1996，10（6）：731－747.

[10] JONES T.Crossover，macromutation and population－based search[C]／／Eshelman Led.Proceedings of the 6th International Conference on Genetic Algorithms.San Francisco：Morgan Kaufmann Publishers，1995：73－80.

[11] SCHRADOPH N N.Dynamic parameter encoding for genetic algorithms[J].Machine learning，1992，9（1）：9－21.

[12] SRINIVAS M.Adaptive probabilities of crossover and mutation in genetic algorithms[J].IEEE Transactions on Systems，Man and Cybernetics，1994，24（4）：656－667.

[13] SEBAG M，RAVISE C，SCHOENAUER M.Controlling evolution by means of machine learning[C]／／Proceedings of the Fifth Annual Conference on Evolutionary Programming.San Diego，California：The MIT Press，1996：57－66.

[14] 刘钢，老松杨，谭东风，等.反舰导弹航路规划图形化快速逆推方法[J].弹道学报，2011，23（2）：52－56.LIU Gang，LAO Song－yang，TAN Dong－feng，etal.Fast graphic converse calculating method for anti－ship missile path planning[J].Journal of Ballistics，2011，23（2）：52－56.（In Chinese）

[15] 刘钢，老松杨，谭东风.基于功能区域的反舰导弹逆向航路规划[J].系统工程与电子技术，2011，33（4）：799－805.LIU Gang，LAO Song－yang，TAN Dong－feng.Converse path planning for anti－ship missiles based on operational area[J].Systems Engineering and Electronics，2011，33（4）：799－805.（In Chinese）