路径规划典型算法范文
时间：2023-06-02 15:01:41
导语：如何才能写好一篇路径规划典型算法，这就需要搜集整理更多的资料和文献，欢迎阅读由公务员之家整理的十篇范文，供你借鉴。
篇1
作者简介： 朱新平（1983-），男，博士，研究方向为先进机场场面运行控制，电话：13419037831，E-mail：
通讯作者： 韩松臣（1963-），男，教授，博士，研究方向为空中交通安全、空域规划管理，E-mail：
文章编号： 0258-2724（2013）03-0565-09DOI： 10.3969/j.issn.0258-2724.2013.03.027
摘要：
为支持先进机场场面活动引导与控制系统（A-SMGCS，advanced surface movement guidance and control system）实施航空器滑行的精确引导，将场面分为滑行道交叉口和直线段等典型运行单元，利用改进的扩展赋时库所Petri网，建立了场面运行模块化模型；采用该模型进行染色体编码，并考虑场面运行管制规则，提出了染色体合法性检测与修复算法，以及染色体交叉和变异算法.基于首都国际机场01号跑道实际运行数据，用本文模型和算法进行了多个航班滑行初始路径规划，研究结果表明：与节点-路段类模型相比，本文模型能更充分地描述场面管制规则约束，可避免生成违反管制规则的路径；本文算法的每个航班初始路径规划耗时小于10 s，符合A-SMGCS的要求；由于考虑了航空器滑行速度调整特征，更符合场面运行的实际情况.
关键词：
空中交通；A-SMGCS；滑行路由规划； Petri网；遗传算法
中图分类号： V351.11文献标志码： A
航空器滑行自动路由规划可以协调进离港航班安全有序地滑行，从而减少场面拥堵并提升场面容量.在国际民航组织（International Civil Aviation Organization， ICAO）提出的先进机场场面引导与控制系统（advanced surface movement guidance and control system， A-SMGCS）中，路由规划功能是实现航空器场面滑行精确引导的前提[1].航空器场面滑行具有并发、资源共享特性，并受多种管制规则约束. A-SMGCS路由规划不同于传统道路网络中的车辆路径规划，文献[2]提出了A-SMGCS三阶段路由规划策略：
（1） 初始路径规划，为进离港航班确定最优滑行路径和s-1个次优滑行路径（s值由管制员动态交互确定）；
（2） 滑行前路由指派，依据航空器开始滑行前的场面态势，为其确定合理路由；
（3） 路由实时更新，在航空器滑行过程中实时调整路由，以避免冲突发生.
本文仅考虑第（1）阶段，即初始路径规划问题.
Petri网广泛用于A-SMGCS场面运行过程的建模与冲突监控[3-4]，但较少用于航空器滑行路由规划.文献[5]将无向交通网络转换为Petri网表示的有向图，并通过Petri网仿真器求解最短有向路径.文献[6]将机场滑行路径描述为有向图，并转换为Petri网图求解最佳滑行路径.文献[2]建立了基于Petri网的场面活动模型，并通过时间窗调度来进行路由规划.上述研究建立的Petri网模型对场面管制规则约束考虑不全面，在算法设计上未充分利用Petri网的数学特征，且通常针对某一特定机场进行分析，实用性和通用性均显不足.另一方面，将航空器场面滑行速度假设为恒定值[7-9]，忽略了航空器在场面不同区域滑行速度的调整变化，导致所得路由结果不能支持航空器滑行的精确引导.
在文献[2]的基础上，本文从以下方面展开研究：
（1） 给出一种扩展赋时库所Petri网（extended timed place Petri net， ETPPN），以准确描述场面运行管制规则约束，并提出一种模块化、面向路由规划的场面运行ETPPN模型建模方法；
（2） 采用遗传算法规划航空器初始滑行路径，其染色体编码采用场面ETPPN模型的变迁激发序列，且交叉和变异均仅针对模型中的变迁进行，避免了以滑行道系统拓扑结构中的交叉口或直线段为基因组成染色体，在此基础上展开的遗传操作保证了方法的通用性；
（3） 与文献[7-9]中关于航空器场面滑行速度恒定的假设不同，细化了航空器加减速特性对路段占用时间的影响，使路由规划结果的精确度更高，实用性更强.
1
航空器场面运行过程建模
1.1
面向资源的场面运行过程建模
可见，采用ETPPN模型对场面运行进行建模，可描述航空器对场面各单元的动态占用与释放，以及航空器在各单元滑行应遵循的管制规则.场面其它典型单元运行过程的Petri网建模也可采用本节的方法.不同机场的场面交通系统具有不同构型，但基本组成单元类似且有准确的数量和明确的运行规则.因此，利用各单元对应的ETPPN模型，并采用Petri网同步合成技术[10]可实现场面运行过程建模.
1.2
航空器滑行特征分析
航空器场面滑行速度具有以下特征：
（1） 当航空器先后通过的两路段均为直线或弯道时，无须加减速；
（2） 当航空器从弯道滑入直线段时，须启动加速过程；
（3） 当航空器从直线段滑入弯道时，减速过程通常在进入弯道前完成.
2
基于GA的初始路径规划算法
2.1
面向初始路径规划的GA设计
遗传算法（genetic algorithm， GA）在工程优化领域已得到广泛应用[11]，并越来越多地应用于航空器路由优化[12-15].本文提出基于场面ETPPN模型和GA的初始路径规划方法，基本思路为：
（1）
采用第1节方法，建立场面活动区中各典型运行单元对应的ETPPN模型，同时将场面管制规则约束集成到Petri网元素中，最终得到场面ETPPN模型；
（2）
以场面ETPPN模型为基础，采用合适的编码方式对模型中所含相关元素进行染色体编码，并设计相关遗传操作，求解初始滑行路径集合（包括1个最优和s-1个次优滑行路径）.
上述思路的优势在于，对任何一个机场的航空器初始路径规划，所要解决的问题只需采用第1节的模块化建模方法，将场面交通系统映射为对应的ETPPN模型并输入管制规则约束即可，因而保证了所给算法的实用性和通用性.
2.2
染色体编码
染色体应满足以下约束：
（1） 物理约束.指与航空器自身占用物理空间大小或与滑行性能相关的约束，如翼展对通过某些区域的限制等.
（2） 管制规则约束.指管制规则确定的航空器在某些路段的滑行约束，如滑行速度约束、进出某机坪必经的交叉口等.
算法2中，步骤1保证了染色体不会出现重复基因，即所规划滑行路径不会出现环路；步骤2保证了航空器在单元内部的滑行过程满足航空器性能要求，例如航空器在同一交叉口滑行时不能多次转弯；步骤3～5保证了航班按照所规划路径滑行时能满足相关约束.
2.3
选择算子与遗传算子
2.3.1选择算子
2.3.2
交叉算子
2.3.3
变异算子
由于采用变迁激发序列进行染色体编码，若采取随机改变某一基因位变迁进行变异，则极有可能产生不满足可激发约束的解.以往采取两种方法解决该问题：第1种方法是随机改变染色体，当生成了不满足约束的解时再进行改正；第2种方法是在进行变异时保证不产生不可行解[16].
3
仿真试验
3.1
仿真试验设计
以首都国际机场为研究对象，采集T3航站楼东侧飞行区某日实际运行数据，为所有进离港航班规划初始滑行路径集.该部分飞行区的场面交通系统结构如图6所示，采用北向运行模式（使用01号跑道），且假设所有离港航班均使用全跑道起飞，即从跑道等待区Q0处（图中方框所示区域）进入跑道起飞，进港航班从快速脱离道Q5、Q6、Q7脱离的比例为0.1∶0.6∶0.3.作为对比，采用文献[12]的方法为图6所示飞行区建立对应的节点-路段类有向图模型，并采用基于遗传算法的路径规划方法为航班规划滑行路径.
文献[12]采取的优化目标是所有航班滑行的总里程最短，将其修改为与本文算法相同的优化目标，即滑行时间较短的s条滑行路径（设s=3）.对比的目的是：
（1） 检验用本文所建场面模型进行路径规划是否比节点-路段类模型能更好地遵循管制规则；
（2） 检验本文初始路径规划算法的效率和有效性.
计算环境CPU为Interl（R） Pentium Dual 2.2 GHz，内存为4 GB.
具体实施过程为：在基于Anylogic的场面运行仿真平台上建立对应的场面ETPPN模型，然后解析得到该模型对应的关联矩阵并导入MATLAB2008a中，采用Sheffield大学的遗传算法工具箱GATBX求解滑行路径.在求解过程中，MATLAB可直接调用Anylogic存储的相关库所属性数据库，并采用遗传算法工具箱GATBX进行求解.文献[12]中算法的实现直接用MATLAB的遗传算法工具箱GATBX完成.
3.2
仿真试验结果及分析
为了给每个航班的进离港滑行规划s
个滑行时间较短的初始滑行路径，需要设置合理的遗传算法参数.但目前在遗传算法参数设定方面缺乏通用理论，一般根据问题难易程度和染色体编码形式，由经验和反复试凑来设定参数值.
用上述参数为离港航班SK996（所在机位511）规划初始滑行路径集（包含3条路径）.由于遗传算法具有一定的随机性，可进行多次试验，每次试验得到的最短滑行时间均为246 s，因此认为对应的滑行路径为最短滑行路径.
图8为在1次随机试验中不同遗传代数所得路径集的最短滑行时间和平均滑行时间变化曲线.由图8可以看出，每次优化均能获得最短滑行路径，且随着进化代数的增加，平均滑行时间越来越接近最短滑行时间，表明算法收敛性良好.
最终为该航班确定的初始滑行路径集如表3所示.对每条路径进行分析可知，在优化场面资源使用的同时，满足了各类场面运行管制规则约束.
采用文献[12]的遗传算法为该航班规划初始滑行路径集，将求出的前3条较短滑行路径参照图6转化为对应的节点形式，如表4所示.
由表4可见，路径1和路径2分别在滑行道K5和K4上未遵循该路段的运行方向约束，这与该算法设计仅考虑避免航空器之间的滑行冲突约束但未充分考虑其它约束有关.可见，在节点-路段类模型中，模型本身对管制规则约束的描述能力有限，仅在算法实现过程中考虑各类约束，可能影响路径规划结果的有效性.
此外，文献[12]中设定的航空器具有单一固定滑行速度5 m/s，路径3的滑行时间为467 s（表4），用本文方法路径3的滑行时间为260 s（表3），二者相差较大.可见，考虑航空器滑行速度的调整特性，可更精确地计算航空器的滑行时间.
4
结束语
提出了一种面向A-SMGCS的航空器场面滑行初始路径规划方法，该方法具有以下特点：
（1） 定义一种扩展赋时库所Petri网（ETPPN），可对航空器场面滑行过程进行建模，该模型充分体现了管制规则约束；
（2） 考虑航空器场面滑行速度调整特性，使规划结果更接近实际运行需要；
（3） 采用场面运行ETPPN模型中的变迁激发序列进行GA染色体编码，结合场面滑行特征给出交叉与变异设计，改变以往研究中对问题空间（场面拓扑结构）的直接处理，算法的通用性更好.
在求解初始滑行路径时仅以滑行时间最短作为优化目标，今后需要考虑更多的优化目标，例如航空器加减速次数、转弯次数等，并与其它路径规划方法进行比较.
参考文献：
[1]International Civil Aviation Organization （ICAO）. Doc.9830-AN/452， Advanced surface movement guidance and control systems （A-SMGCS） manual[S]. 2004.
[2]汤新民，王玉婷，韩松臣. 基于DEDS的A-SMGCS航空器动态滑行路径规划研究[J]. 系统工程与电子技术，2010，32（12）： 2669-2675.
TANG Xinmin， WANG Yuting， HAN Songchen. Aircraft dynamic taxiway routes planning for A-SMGCS based on DEDS[J]. Systems Engineering and Electronics， 2010， 32（12）： 2669-2675.
[3]朱新平，汤新民，韩松臣. 基于EHPN的A-SMGCS机场滑行道运行控制建模[J]. 交通运输工程学报，2010，10（4）： 103-108.
ZHU Xinping， TANG Xinmin， HAN Songchen. EHPN-based modeling of airport taxiway operation control in A-SMGCS[J]. Journal of Traffic and Transportation Engineering， 2010， 10（4）： 103-108.
[4]朱新平，汤新民，韩松臣. 基于DES监控理论的滑行道对头冲突控制策略[J]. 西南交通大学学报，2011，46（4）： 664-670.
ZHU Xinping， TANG Xinmin， HAN Songchen. Avoidance strategy for head-on conflict on taxiway based on supervisory control theory of DES[J]. Journal of Southwest Jiaotong University， 2011， 46（4）： 664-670.
[5]黄圣国，孙同江，吕兵. 运输网络的最短有向路Petri网仿真算法[J]. 南京航空航天大学学报，2002，34（2）： 121-125.
HUANG Shengguo， SUN Tongjiang， LU Bing. Petri net simulation arithmetic of the shortest directional path in transportation net[J]. Journal of Nanjing University of Aeronautics and Astronautics， 2002， 34（2）： 121-125.
[6]张威，谢晓妤，刘晔. 基于Petri网的机场场面路径规划探讨[J]. 现代电子工程，2007，4（1）： 59-61.
ZHANG Wei， XIE Xiaoyu， LIU Ye. Petri-net based airport surface routes planning[J]. Modern Electronic Engineering， 2007， 4（1）： 59-61.
[7]GARCIA J， BERLANGAA A. Optimization of airport ground operations integrating genetic and dynamic flow management algorithms[J]. AI Communications， 2005， 18（2）： 143-164.
[8]KEITH G， RICHARDS A， SHARMA S. Optimization of taxiway routing and runway scheduling[C]∥Proc. of AIAA Guidance， Navigation， and Control Conference and Exhibit. Honolulu： [s. n.]， 2008： 1-11.
[9]MARN G. Airport management： taxi planning[J]. Annals of Operations Research， 2006， 143（1）： 191-202.
[10]王化冰. 一种基于同步合成Petri网的FMS建模方法[J]. 系统工程理论与实践，2001，21（2）： 35-42.
WANG Huabing. A Petri net synchronous synthesis method for modeling flexible manufacturing systems[J]. System Engineering： Theory and Practice， 2001， 21（2）： 35-42.
[11]GEN M， CHENG R W. Genetic algorithms and engineering optimization[M]. New York： John Wiley and Sons， 2000： 297-340.
[12]刘长有，丛晓东. 基于遗传算法的飞机滑行路径优化[J]. 交通信息与安全，2009，27（3）： 6-8.
LIU Changyou， CONG Xiaodong. Taxing optimization for aircraft based on genetic algorithm[J]. Transportation Information and Safety， 2009， 27（3）： 6-8.
[13]刘兆明，葛宏伟，钱锋. 基于遗传算法的机场调度优化算法[J]. 华东理工大学学报：自然科学版，2008，34（3）： 392-398.
LIU Zhaoming， GE Hongwei， QIAN Feng. Airport scheduling optimization algorithm based on genetic algorithm[J]. Journal of East China University of Science and Technology： Nature Science Edition， 2008， 34（3）： 392-398.
[14]GOTTELAND J， DURAND N， ALLIOT J M， et al. Aircraft ground traffic optimization[C]∥Proc. of the Genetic and Evolutionary Computation Conference. San Francisco： IEEE Press， 2001： 1-9.
[15]GOTTELAND J， DURAND N. Genetic algorithms applied to airport ground traffic optimization[C]∥Proc. of the 2003 Congress on Evolutionary Computation. Canberra： IEEE Press， 2003： 544-551.
篇2
关键词：最短路径；动态规划；C 语言编程
中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2013）09-2191-03
1 概述
数学源于生活，又服务于生活.它是一门研究现实世界中的数量关系与空间形式的学科.当今社会，随着物质水平的不断提高，生活需求的不断扩大，自然资源的不断开发利用.像天然气管道铺设问题，厂区布局问题，旅行费用最小问题等都已成为我们平时经济生活中的普遍问题.它们其实都可以化归为最短路线问题，而最短路问题实质上是一个组合优化问题[1]。
动态规划方法主要是研究与解决多阶段决策过程的最优化问题，它将求解分成多阶段进行，不但求出了全过程的解，还能求出后部子过程的一组解，在求解一些生活实际问题时，更显其优越性。为了快速、简单的计算最短路径，节约运输时间与成本，该文利用动态规划的思想编写了C语言程序，解决物流运输过程中多地点的最短路径的选择问题。
2 最短路径问题
2.1 最短路径问题算法的基本思想
在求解网络图上节点间最短路径的方法中，目前国内外一致公认的较好算法有迪杰斯特拉（Dijkstra）及弗罗伊德（Floyd）算法。这两种算法中，网络被抽象为一个图论中定义的有向或无向图，并利用图的节点邻接矩阵记录点间的关联信息。在进行图的遍历以搜索最短路径时，以该矩阵为基础不断进行目标值的最小性判别，直到获得最后的优化路径[2]。
Dijkstra算法是图论中确定最短路的基本方法，也是其它算法的基础。为了求出赋权图中任意两结点之间的最短路径，通常采用两种方法。一种方法是每次以一个结点为源点，重复执行Dijkstra算法n次。另一种方法是由Floyd于1962年提出的Floyd算法，其时间复杂度为[On3]，虽然与重复执行Dijkstra算法n次的时间复杂度相同，但其形式上略为简单，且实际运算效果要好于前者。
2.2 最短路径问题算法的基本步骤[3]
这样经过有限次迭代则可以求出[v1]到[vn]的最短路线。
（2）Floyd算法的基本步骤
（3）动态规划算法基本步骤
我们将具有明显的阶段划分和状态转移方程的规划称为动态规划[1]。在解决多个阶段决策问题时采用动态规划法是一个很有效的措施，同时易于实现。
根据动态规划的基本概念，可以得到动态规划的基本步骤：1）确定问题的决策对象。2）对决策过程划分阶段。3）对各阶段确定状态变量。4）根据状态变量确定费用函数和目标函数。5）建立各阶段状态变量的转移过程，确定状态转移方程。
根据动态规划的基本模型，确定用动态规划方法解题的基本思路，是将一个[n]阶段决策问题转化为一次求解[n]个具有递推关系的单阶段的决策问题，以此来简化计算过程.其一般步骤如下：
用于衡量所选决策优劣的函数称为指标函数.指标函数有有阶段的指标函数和过程的指标函数之分.阶段的指标函数是对应某一阶段状态和从该状态出发的一个阶段的某种效益度量，用[vkxk，uk]表示。在本文里用[dkxk，uk]来表示某一阶段的决策的最短路径。过程的指标函数是指从状态[xn（k=1，2，...，n）]出发至过程最终，当采取某种子策略时，按预定的标准得到的效益值。这个值既与[xk]本身的状态值有关，又与[xk]以后所选取的策略有关，它是两者的函数值，记作[dk，nxk，uk，xk+1，uk+1，…xn，un]。过程的指标函数又是它所包含的各阶段指标函数的函数。本文研究的过程的的指标函数是其各阶段指标函数的和的形式.当[xk]的值确定后，指标函数的值就只同k阶段起的子策略有关。对应于从状态[xk]出发的最优子策略的效益值记作[fkxk]，于是在最短路问题中，有[fkxk=mindk，n]。动态规划求解最短路径程序流程图如图2所示。
3 最短路径态规划实际应用举例
设某物流配送网络图由12个配送点组成，点1为配送中心起点，12为终点，试求自终点到图中任何配送点的最短距离。图中相邻两点的连线上标有两点间的距离[4]。
首先用动态规划法来讨论图3的最短路径，由图可知：
1）集合[ξ4]中有点9、10、11，它们在一步之内可到达点12；
2）集合[ξ3]中有点6，7，8，它们不超过两步就可达到点12；
3）集合[ξ2]中包括点 2、3、4、5，不超过三步就可到达点12；
4）集合[ξ1]中包括点1，不超过四步可到达点12；
按照动态规划法类推，得到最优路径长为16，径路通过点为1，2，7，10，12和1，3，6，10，12。
根据动态规划算法编写C语言计算程序[5] [6]，计算得到实验结果如下图4所示：
由图4可以看出程序得到的结果与本文推出的结果一样。证明了本文编写的C语言程序是正确的。
4 结束语
综上所述，用动态规划解决多阶段决策问题效率高，而且思路清晰简便，同时易于实现.我们可以看到，动态规划方法的应用很广泛，已成功解决了许多实际问题，具有一定的实用性。此种算法我们用动态规划思想来编程，并解决相应的问题，其在 VC 环境下实现，能方便快速的计算出到达目的地的最短距离及路径，节省更多的运输时间与成本。不过，该文只考虑了动态规划算法在生活中的简单运用，在实际生活中可能存在多个目的地或者更复杂的情况.因此我们可以考虑将其进行改进或者结合启发式算法，使之更好的运用在实际生活中，这有待于以后的继续研究。
参考文献：
[1] 杜彦娟.利用动态规划数学模型求解最短路径[J].煤炭技术，2005（1）：94-95.
篇3
关键字：最优路径选择；A-Star算法；贪婪算法；模拟仿真
中图分类号：TP301.6 文献标识码：A DOI：10.3969/j.issn.1003-6970.2013.06.012
0 前言
物流与国民经济及生活的诸多领域密切相关，越来越多得到重视，甚至被看作是企业“第三利润的源泉”，而在物流成本方面，运输费用占大约50% ，比重最大[1]。因此，物流配送中最优路径选择的研究具有巨大的经济意义。物流配送中的最优路径选择问题的研究和应用都相当广泛，近几十年，国内外均有大量企业机构、学者对该问题进行了大量而深入的研究，取得丰硕的学术成果。如1953年，Bodin，Golden 等人便撰文综述了该问题的有关研究进展情况，列举了几百余篇相关文献，这些文献成为了早期车辆路径问题研究资料，随后随着该问题不断研究深入，约束模型及条件不断变化，车辆路径问题研究的最新进展可见Alt- inkerner 和 Oavish，Laporte，Salhi 等人的综述性文章[2]。围绕该问题的解决也极大推动了计算机学科的发展，不断有新的模型和算法推出。针对物流配送车辆路径优化问题的求解方法很多，根据算法原理的不同大致可分为两大类：精确算法和智能式启发算法。精确算法是指可以车辆路径问题的数学模型可求出其最优解算法，但由于算法存在诸多缺陷，所以在实际中应用并不广泛。目前，启发式算法是解决物流配送中最优路径选择的主要方法和主向[3]。近年来，随着科学的发展，一些新的启发式方法被用在求解物流路径选择及优化问题上，可以通过使用启发式方法获得较快的收敛速度和较高质量的全局解，常用的算法有模拟退火算法、GA 算法等[4]。A*算法是人工智能中一种典型的启发式搜索算法，被广泛应用于最优路径求解和一些策略设计的问题中[5、6]。本文结合贪婪算法的思想，深入研究A-Star（A*）算法，在QT Creator平台上，采用Visual C++编程对物流配送问题进行模拟仿真，同时考虑最短时间和最短路径两个方面，以此来解决物流配送中最优路径选择的问题，达到物流配送最优线路规划的目的。
1 需求分析
1.1 总体框架
在物流配送时，物流车装载当日需要配送的货品从仓库出发，按照事先规划好的最优配送路径为每一个客户进行配送，最后返回仓库。这就涉及在配送时配送路线的选择问题，而在配送之前，IT系统需要根据客户的配送地址间线路间距和经验路况分析计算出一条最优配送路径。并且在配送过程中，如果某路段发生堵车状况，需要动态调整配送路线，以达到最优配送的目的。为此，在QT Creator平台上，以面向对象的设计方式来开发最优物流配送的功能软件。通过再现交通运输环境，模拟物流运输中的突发事件，优化物流配送的路线，分别根据需求，设计出最短路径和最少时间两种配送方式，并通过二维动画的效果显示出来。通过此软件呆模拟解决物流配送中各种情况，从而降低运输成本。设计本软件的总体思路如图1所示。
1.2 功能设计
设计的软件从功能上来说，主要包括以下几点：
（1）载入一张已有地图（*.map的文件）或生成一张空白地图。用户可以在这张空白地图上操作，通过障碍物的增删来设置城市的道路。
（2）道路突发事件设置。
a.用户可以根据实际情况或主观意愿对地图进行规划。在地图中添加障碍物，设置道路前方的暂时封闭或者道路施工等未知路况。
b.也可以模拟城市人流量大的地方，通过在地图上，设置易堵车而导致前行速度下降的未知路况。
（3）设置仓库及客户点。
a.随机生成仓库及客户点。在地图中，用户可随机生成若干个客户点和仓库点。
b.指定生成仓库及客户点。在已生成或者模拟的地图上，根据用户的不同需求，可在地图上任意位置生成客户点和仓库点。
c.可以对仓库及客户点进行增删。
（4）计算路径及优化。
a.根据用户之前模拟的各种情况，计算其最短路径。根据用户载入或者自己规划的地图，模拟计算出最短路径，在界面的左上角显示其时间，并在地图上显示其路径。
b.根据用户之前模拟的各种情况，计算其最短时间。根据用户载入或者自己规划的地图，模拟计算出最短时间，在界面的左上角显示其时间，并在地图上显示其对应路径。
软件的大致功能如下图2所示。
图2 功能模块图
2 算法描述
2.1 贪婪算法
贪婪算法（Greedy algorithm）又叫登山法，它的根本思想是逐步到达山顶，即逐步获得最优解，是解决最优化问题时的一种简单但适用范围有限的策略[7]。
贪婪算法是基于邻域的搜索技术，它在计算过程中逐步构造最优解[8]。在构造解的过程中，每一步常以当前情况为基础根据某个优化测度（greedy criterion，贪婪准则，也称贪婪因子）作最优选择，而不考虑各种可能的整体情况，选择一旦做出就不再更改，这省去了为找最优解要穷尽所有可能而必须耗费的大量时间。它采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题。通过每一步贪心选择，可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，一般情况下只是近似最优解[9]。虽然贪婪法不是对所有问题都能得到整体最优解，但对范围相当广泛的求最优解问题来说，它是一种最直接的算法设计技术，通过一系列局部最优的选择，即贪婪选择可以产生整体最优解[10]。
对于一个给定的问题，往往可能有好几种量度标准。初看起来，这些量度标准似乎都是可取的，但实际上，用其中的大多数量度标准作贪婪处理所得到该量度意义下的最优解并不是问题的最优解，而是次优解。因此，选择能产生问题最优解的最优量度标准是使用贪婪算法的核心。一般情况下，要选出最优量度标准并不是一件容易的事，但对某问题能选择出最优量度标准后，用贪婪算法求解则特别有效。最优解可以通过一系列局部最优的选择（贪婪选择）来达到。根据当前状态做出在当前看来是最好的选择，即局部最优解选择，然后再去解出这个选择后产生的相应的子问题。每做一次贪婪选择就将所求问题简化为一个规模更小的子问题，最终可得到问题的一个整体最优解。它是一种改进了的分级处理方法。
2.2 A-Star算法
A*算法是人工智能中一种典型的启发式搜索算法，它是一种静态路网中求解最短路最优算法，其公式可表示为：
（1）
其中，是从初始点经由节点到目标点的估价函数；是在状态空间中从初始节点到节点的实际代价；是从到目标节点最佳路径的估计代价[11、12]。
在A*算法中，找到最短路径（最优解的）的关键在于估价函数的选取。当估价值到目标节点的距离实际值时，搜索的点数多，搜索范围大，效率低，但能得到最优解；当估价值到目标节点的距离实际值时，搜索的点数少，搜索范围小，效率高，但不能保证得到最优解[13、14]。
A*算法的难点在于建立一个合适的估价函数，估价函数构造得越准确，则A*算法搜索的时间就越短[15]。A*算法的估价函数可表示为：
（2）
这里，是估价函数，是起点到节点的最短路径值，是到目标的最短路径的启发值。由于这个其实是无法预先知道的，所以我们用前面的估价函数做近似。当时，可以代替（大多数情况下都是满足的，可以不用考虑），但只有在时，才能代替。可以证明，应用这样的估价函数能有效地找到最短路径。
本文综合贪婪算法和A*算法的思想来求解决物流配送中最优路径选择的问题。图3为综合算法的流程图。
3 实验仿真设计
3.1 软件概述
开发的软件要具有实用性，这就是说，能给企业带来效益，这就包了两方面的内容：企业能获得的利润和客户的满意程度。也就是说采用所建立的模型要设计出合理的物流配送路线，保证在较短的路程或时间内遍历所有的节点，从而保证货物按时送到。
从算法角度来看，为了保证算法的有效性和高效性，结合软件的功能，则该软件的设计目标[16]为：①路径最短或时间最短， ②满足实际中遍历节点的要求， ③算法高效性， ④软件的普度适用性。
软件操作流程具体步骤如下：
第一步.用户载入一张已有地图或生成一张空白地图。
第二步.设置相关参数及约束条件。
第三步.显示计算结果和最优路径。
该软件可运行于Windows 7操作系统，主要包括3个部分：地图文件的读取部分、算法部分和用户界面部分。
3.2 软件模拟实现
1.初始化
根据软件的需求分析，本软件初始产生一个空白的二维平面图，在该模块用户可以根据实际情况模拟出实际路况，提供两种方式来实现该功能：
（1）通过点击工具栏上面的初始化按钮自动初始化。
（2）通过鼠标右键选择初始化选项。
图4 系统初始化界面
2.道路的参数设置
在视图界面中，用户可以点击鼠标右键，选择生成障碍物或删除障碍物来模拟现实生活中城市道路可能发生的各种情况，如：
（1）用户可以根据实际情况，点击鼠标右键，在出现的下拉菜单中，选中添加障碍物，设置道路前方的暂时封闭或者道路施工等未知路况。
（2）也可以在地图上，点击鼠标右键来设置易堵车而导致前行速度下降的未知路况。
在地图中浅黄色的区域是模拟人流量大的闹市区。深褐色方块模拟障碍物。
图5 道路模拟图
3.仓库点及客户点的生成
客户点和仓库点的生成包括两种情况：
（1）随机生成客户点和仓库点。在视图界面中，通过顶端的输入框，输入生成客户点或仓库点的个数，点击生成客户点或仓库点按钮来随机生成客户点或仓库点。
（2）在指定位置生成客户点和仓库点。在已生成或者模拟的地图上，根据用户不同的需求，在地图指定位置生成客户点和仓库点。
在如图5的道路设计下，在地图上随机添加了10个客户点和1个仓库点，如图6所示。
图6 场景界面图
4.路径最短和时间最短的配送路径
根据图6所设计的场景，通过贪婪算法和A*算法，分别计算出路径最短和时间最短的配送路径，并在地图上显示其路径。图7依据最短路径实现物流配送的最优方案，主要从距离这个方面进行考虑；图8根据最短时间实现物流配送的最优方案，主要考虑的是在道路有突发状况发生时物流配送的时间最少。
图7 路径最短的配送路径
图8 时间最短的配送路径
4 认识与结论
通过对物流配送中的实际问题进行模拟研究，在QT Creator平台上采用Visual C++编程开发出针对物流配送中最优路径选择问题的软件，从最短时间和最短路程两方面考虑，为物流配送公司提供可靠有效的参考信息，使配送方案符合实际情况。同时，深入研究了贪婪算法和A*算法，从算法的角度对物流配送中的时间和路程进行分析，设计实现了物流配送中最优数学模型，以期达到最优路径的目的。通过本研究的结果来看，开发的模拟软件能解决物流运送过程中的时间、路径等实际问题，同时实现了二维图形的可视化，更加直观地体现了物流配送中存在的问题和解决方式，对物流配送企业提高运营效率、降低运营成本等具有重要意义。
参考文献
[1]黄中鼎. 现代物流管理学[M]. 上海： 上海财经大学出版社， 2004， 1-37.
[2]谢秉磊， 郭耀煌， 郭强. 动态车辆路径问题：现状与展望[J]. 系统工程理论方法应用， 2002， 11（2）： 116-120.
[3]邹挺. 基于蚁群和人工鱼群混合群智能算法在物流配送路径优化问题中的应用研究[D]. 苏州： 苏州大学， 2011， 3-7.
[4]吴云志， 乐毅， 王超， 等. 蚁群算法在物流路径优化中的应用及仿真[J]. 合肥工业大学学报（ 自然科学版）， 2009， 32（2）：211-214.
[5]王海梅， 周献中. 直线优化A*算法在最短路径问题中的高效实现[A]. 全国第计算机技术与应用（CACIS）学术会议论文集（下册）[C]， 2008， 932-936.
[6]陈和平， 张前哨. A*算法在游戏地图寻径中的应用与实现[J]. 计算机应用与软件， 2005， 22（12）：94-96.
[7]晏杰. Matlab 中贪婪算法求解背包问题的研究与应用[J]. 赤峰学院学报（自然科学版）， 2012， 28（9）：23-24.
[8]刘纪岸， 周康渠， 宁李俊， 等. 基于贪婪算法的摩托车生产物流配送规则优化[J]. 制造业自动化， 2010， 32（5）：97-99.
[9]蒋建国， 李勇， 夏娜. 一种求解单任务Agent联盟生成的贪婪算法[J]. 系统仿真学报， 2008， 20（8）：1961-1964.
[10]江朝勇， 陈子庆， 谢赞福. 基于优先级贪婪算法的排课系统排研究与实现[J]. 信息技术， 2008， 24（7）：173-176.
[11]徐伟， 孙士兵. 基于A-Star算法警用地图查询系统的设计与实现[J]. 信息安全与技术， 2011. 5-2：52-56.
[12]王敬东， 李佳. A*算法在地图寻径中的实用性优化[J]. 电脑开发与应用， 2007， 20（7）：24-25.
[13]（美）Stuart Russell，（美）Peter Norvig. 人工智能——一种现代方法[M]. 姜哲，译. 北京：人民邮电出版社， 2004， 76-83.
[14]王文杰， 叶世伟. 人工智能原理与应用[M]. 北京：人民邮电出版社， 2004， 115-121.
篇4
【关键词】虚拟场景；路经规划；八叉树；A*算法
中图分类号：TP39文献标识码A文章编号1006-0278（2013）06-172-01
一、引言
随着虚拟现实技术的日益成熟，只有景色、建筑物等一般视景信息的虚拟场景已不能满足人们的视觉需求，迫切需求一个有生命的对象引入到虚拟场景中，增加浏览者的沉浸感。虚拟场景中虚拟人的路径规划是虚拟现实研究中的一项关键技术。目前，研究者们已经把研究的重心放在如何为虚拟人规划出一条行走的最优路径，使虚拟人的路径导航更具有真实感和可信度。
由于虚拟环境中的模型多由三角面网格组成，通过使用基于空间多层次划分的八叉树方法，充分发挥了其空间划分的优势，加快了场景的渲染速度，减少了确定对象的处理时间以及存储空间①。
文章采用八叉树和A*算法相结合的方法，对路径进行规划，并对A*算法做了改进，以适应八叉树的存储结构。
二、密集型区域八叉树划分算法
八叉树是由四叉树推广到三维空间而形成的一种三维栅格数据结构，它作为一种场景组织方法，广泛应用于虚拟现实系统，可显著减少对场景中多边形进行排序的时间。
由于传统八叉树对空间的划分是均匀的，导致了最终生成一个结构不平衡的八叉树，从而增加整个八叉树的存储空间以及各结点的遍历时间。文章采用了对传统八叉树算法进行改进，采用基于密集型区域八叉树划分方法。密集型区域八叉树的网格划分算法是对每一子空间重新建立最小包围盒，这样避免了在建立顶点树时，由于该部分顶点在空间上分布不均匀而导致树的深度的增加，进而减少了存储空间，加快了网格模型数据的读取速度。另外，由于建立了顶点的最小包围盒，在误差较小时，只有空间距离比较近的顶点才会聚合在一起；而相距较远的顶点只有在深层次简化时才会聚合，这些特点在一定程度上保证了简化时网格模型的逼真度。
密集型区域八叉树划分方法的算法描述如下：
步骤1使用OBB包围盒方法建立模型的最小包围盒。
步骤2以包围盒的X轴、Y轴、Z轴方向的中分面作为分割基准，将包围盒平均划分为八个子包围盒。
步骤3如果每个子空间内存在物体的属性不相同或未达到规定的限差，则重新从步骤1开始进行划分。否则，划分结束，并对划分后的每一个结点记录下结点编号、划分标志、结点在顶点树中的深度以及它所含的景物面片表的入口指针。
三、A*算法
A*算法是建立在典型的Dijkstra算法上的，是由Hart，Nilsson，Raphael等人首先提出的。该算法的创新之处在于选择下一个被检查的节点时引入了已知的全局信息，对当前节点距终点的距离做出估计，作为评价该节点处于最优路线上的可能性的量度，这样就可以首先搜索可能性较大的节点，从而提高了搜索过程的效率。
下面是对A*算法的介绍，我们首先来介绍一下启发式搜索中的估计函数。因为在启发式搜索中，对位置的估价是十分重要的。估价函数的表示如下：
其中是节点的估价函数，是已知的，指在状态空间中从初始节点到节点的实际代价；是从结点到目标节点最佳路径的估计代价，它体现了搜索的启发信息，启发信息决定着算法的启发能力。启发信息越多，估价函数就越好，即约束条件越多，则排除的节点就越多，说明这个算法越好。这种做法存在一个平衡的问题，也会使算法的准确性下降。具体的说，代表了搜索的广度优先趋势，当时，可以省略，这样就提高了搜索效率。
A*算法是一个可采纳的最好优先算法。A*算法的估价函数可表示为：
这里，是估价函数，是起点到终点的最短路径值，是到目标的最短路经启发值。由于这个其实是无法预先知道的，所以我们用前面的估价函数做近似。代替，但需要满足（在大多数情况下都满足时，可以不用考虑）。代替，并满足。可以证明应用这样的估价函数是可以找到最短路径的。
四、基于密集型区域八叉树的A*算法改进
由于使用八叉树存储结构存储的环境地图扩展步长不一致，采用传统的A*算法效率较低，因此对A*算法做了改进，以适应八叉树结构的搜索。改进的办法是从叶节点开始搜索并为Open表设置两个优先队列，命名为队列1和队列2（队列1中存放的节点总是高于队列2），在两个队列中分别存放相邻层次的全部节点，层次越高的优先级越高。通过这种分层次的搜索，也大大缩小了搜索的空间并缩短了搜索时间，这样一来大大提高了搜索效率。
五、结束语
针对于复杂的3D环境，文章根据八叉树适合虚拟场景划分的特点，采用了一种适合密集型区域的八叉树划分方法，进行场景划分。为适合八叉树的存储结构，对A*算法做了改进，引入优先级队列并采用了分层结构，采用了从叶节点到根节点的搜索方法，规划出了虚拟人行走的最优路径。
篇5
关键词：多智能体；寻路；游戏开发
中图分类号：TP312文献标识码：A文章编号：1009-3044(2012)13-3159-06
Application of Multi-Agent Pathfinding System in Computer Game
HUANG Jin1, HUANG Zong-Wen1, LING Zi-Yan2
(1.XingJian College of Science and Liberal Arts, Guangxi University, Naning 530004, China; 2.Geomatics Center of Guangxi, Naning 530023, China)
Abstract: This research presents a real-time multi-agent pathfinding system in computer game. In our system, each agent thinks independently, and continues to search and move to reach its destination, so a group behaviors with significant individual characteristic can be better simulated; The concept of soft obstacle is introduced to implement collision avoidance between agents and crowd movement simulation; The pathfinding algorithm is applied and bridged on the 3D games, which provides efficient multi NPC pathfinding function for re? al-time game. The paper expounds the system from overall structure, components detail, core algorithms and practical application, and then obtains the experimental results.
Key words: multi-agent; pathfinding; computer game
路径搜索，在碰撞避免的条件下对智能体到目的地的路径规划问题，是游戏设计中的一个典型问题。在静态网格的条件下，A*算法能够很好的解决这个问题。但是，如果需要考虑多智能体之间或者智能体与其他有可能运动的障碍物的碰撞避免的话，那么我们就要对A*算法进行改进，使智能体能够感知潜在的障碍物碰撞。多智能体寻路系统令系统内的每一个智能体独立进行思考，使他们能够通过各自思维实现从出发地到目的地的导航。多智能体寻路系统在很多领域得到了应用，包括机器人运动规划，空中交通控制，车辆路径规划，灾害救援，以及本文将要讨论的电脑游戏[1]。
A*算法由Peter Hart等首次提出，它被用来在静态网格地图中寻找指定起点到目的地的最佳路径[2]。A*是在Dijkstra算法的基础上形成的[3]，Dijkstra算法对启示节点周围的所有节点逐一进行搜索，直到找到目标节点，而A*则在此基础上扩展了一个更直接的启发方式，即估计目标节点与当前节点的距离，并以此作为移动当前点的重要指标。
然而，正如前面讨论的那样，A*算法只能在静态网格地图中对单一目标路径规划上得到应用，为了解决这一问题，Silver提出了一种被广泛应用在电子游戏上的多智能体寻路系统，Local Repair A*（LRA*）[4]。在LRA*里，每一个智能体独立的考虑自己的路径规划，当智能体发现它的下一步路径将出现障碍物导致的碰撞后，它们将重新规划新的路径，防止碰撞发生。这种算法的缺点在于经常性出现的循环依赖和死锁，从而导致在实际应用中智能体始终无法达到目的地。
Jeremy和Jansen等人则尝试为网格地图中智能体所可能占据的每一个位置估算一个移动方向，并且令在该位置上的智能体按照这个方向移动[5] [6]。在这种算法中，他们也需要利用A*或者Dijkstra算法对网格进行遍历，只不过是将遍历得出的数据转化为对于某一位置的移动方向而不是一条移动路径。这种算法在群体行为的模拟中非常有效，但是却无法很好的模拟游戏中经常出现的与群体目的相违背的个体行为。
1系统结构
本文构建的多智能体网格地图寻路系统主要由以下几个部分组成（如图1所示）。
地图网格：用于标记地图中的静态障碍物，这和A*算法中的障碍物一样，做了障碍标记的网格将无法通行。
寻路单元：用于读取文本形式的地图网格信息，执行网格的初始化和网格信息的更新，为智能体提供路径搜索功能等。
动作单元：为智能体提供在3D空间内的移动及旋转功能。
智能体：系统中执行寻路、移动、旋转以及其他一些游戏中必须动作的基本单元。
智能体管理器：负责对智能体进行管理，包括注册、移除、获取以及在适当的时刻命令智能体进行寻路。
2系统细节
2.1寻路单元
寻路单元为我们的整个系统提供寻路的核心算法，这个算法由寻路网格初始化和寻找最佳路径两部分组成，智能体通过调用寻路函数获得一个被算法承认的最佳路径。每当智能体调用寻路函数时寻路网格初始化都将进行一次，这是因为我们的寻路网格不是静态的，而是随着障碍物或者场景内游戏单元位置变化而动态更新的。我们都知道，A*算法用H值来表示当前节点距离终点的距离，而G值用来表示从起始点到当前节点的消耗值。我们在寻路网格初始化中，将保留A*算法H值的计算方式而对G值，即消耗值，进行适当调整，引入一种软障碍的概念使其更符合游戏要求。此外，我们在A*算法静态障碍物的基础上添加了一个排除列表，用它来标记寻路网格内动态障碍物，和静态障碍物一样，路径将无法从它们上面通过。总之，这个算法是在一个动态更新的网格地图上，通过考虑静态障碍物、动态障碍物及软障碍物的避让，搜索最佳路径的过程。下面，我们详细介绍网格初始化和寻找最佳路径这两部分的实现过程：
2.1.1寻路网格初始化
寻路网格由网格细胞的二维数组构成，一个网格细胞中记录了以下几个重要的数值：F值、G值及H值，距离损耗，密度损耗。这里，F值、G值及H值的含义和A*算法中保持一致，而G的具体取值由距离损耗和密度损耗计算得出。
距离损耗用于存储智能体通过该网格所需的移动损耗，密度损耗则用于表示智能体在通过该网格时，由于场景内软障碍所造成的消耗。在游戏中，我们希望人群在空间充裕的条件下保持一定的距离，但是又不希望当空间比较狭窄时造成堵塞，所以我们引入软障碍的概念。如图2所示，在左边的黑色格子，是一个硬障碍，路径将无法在黑色区域的格子通行，而右边具有灰色圆形图案的则是一个软障碍，对于中心的黑色格子，路径无法通过，但是对于灰色的圆形范围，算法将不鼓励但不禁止路径从此通过，并且，越是靠近圆形中心，路径从此通过受到的阻力越大，即密度损耗的值越大。我们使用软障碍来表示场景中的NPC和玩家，之所以将存储软障碍消耗的变量称之为密度损耗，正是因为这个值可以帮助我们控制场景中人群的密度。
在程序中，我们首先创建一个空的寻路网格，然后从硬盘读文本形式的静态障碍信息，通过静态障碍信息修改相应网格细胞类型，对场景内每一个智能体所在位置以及它们下一个移动目标所在位置的网格细胞设置为软障碍，这样在实际应用中就能极大的降低智能体相互穿越（图3）、死锁（图4）等情况的发生。
图4死锁
2.1.2寻找最佳路径
一旦网格初始化过程完成，我们便基于这个最新初始化的网格进行路径搜索。
搜索路径算法首先将起始节点放入closed列表里，并检查它相邻的8个子节点；接着，将这些节点放入open列表里，并以F值的大小顺序排列；算法接下来挑选open列表中F值最小的节点作为下一个检查目标，将这个节点从open列表中移除并与结束节点进行比较：
如果它不是结束节点，将其放入closed列表里，并且将它相邻子节点按照其F值的大小顺序放入open列表中，这个过程一直持续到我们搜索到结束节点，或者open列表中为空。如果它是结束节点，路径搜索完成，我们计算出路径上的所有节点并返回。
下面给出寻找最佳路径的伪代码：
Create Start Node with Current Position
Add Start Node to Open List
while Open List NOT Empty do
Update Nodes in Open List
Sort Open List by F Value in Descending
Get First Node from Open List call Node“N”
Remove N from Open List
在循环搜索的过程中，每一个节点都要首先进行更新，注意到在执行路径搜索部分之前，网格已经被重新初始化，这意味着每一个节点的F值都是最新的，同时，子节点也已经对父节点的F值进行累加，这样做是为了保证软障碍能够起到控制拥挤程度的作用。此外，在将相邻节点加入open列表时，我们还需要对节点的类型做出判断，仅当节点不是静态障碍物、处于排出列表中（动态障碍物）或穿越者障碍物转角时，我们才能继续进行余下操作。为了防止路径穿越者障碍物转角，我们对图5所示的这种情况进行测试，根据实际情况返回真或者假。
图5智能体在不进行障碍物转角判断时的错误路径
2.2动作单元
由于本文涉及的游戏是一款3D游戏，我们除了完成在2D网格中的路径搜索外，还需要命令我们的智能体按照路径在3D空间中完成旋转和移动。动作单元为智能体提供一个通用的移动函数，智能体只要在每次更新的时候调用这个函数便能完成旋转和移动的动作。下面，我们介绍这个函数的细节：
下面给出移动函数伪代码：
Calculate the Direction from Agent to the Goal Call“Dire”
Calculate the Dot Product of Dire and Agent’s Face Direction Call“Dot”
if Dot is NOT larger than the Angle Threshold than
if is Clockwise than
Rotate Agent Clockwise
else
Rotate Agent Counterclockwise end if end if
Calculate the Distance between Agent and the Goal Call“Dist”
if Dist is NOT larger than the Distance Threshold than
Move Agent to Dire
else
Set Path Target to Null
end if
函数首先计算得出智能体目的地所在方向，然后计算它与智能体自身朝向之间的夹角，如果夹角大于转角阀值，进行旋转，否则不进行旋转直接移动。在进行旋转之前，我们还要通过比较这两个方向向量在极坐标下的极角，得出正确的旋转方向。接下来，计算智能体与目的地的距离，如果这个距离大于距离阀值，令智能体向目的地方向移动，否则不进行移动，并将移动目标清空。注意到智能体将在每帧渲染前都调用这个函数，我们只需要令其按照计算得出的移动方向和旋转方向移动和旋转一个与帧速率相关的微小量即可得到连续播放的动作。
2.3智能体及智能体管理器
智能体由两部分组成，其一是用于寻路的寻路组件，其二是用于在游戏中显示的3D组件。寻路组件存储了智能体在网格地图上的位置，智能体最近一次成功寻路的路径以及路径目标索引。3D组件则用于存储智能体在3D世界中的位置、朝向、移动目标等信息，它还负责在适当的时候调用动作单元的移动函数，是智能体“真正”的发生移动。
我们注意到，这里存在两张地图，一张是用于寻路的网格地图，而另一张是3D世界中的真实地图，网格地图是离散的，而真实地图是连续的，所以我们需要分别使用寻路组件和3D组件存储他们各自的位置和目标等信息。并且，在必要的时候，我们还需要将这其中一套信息换算成另外一套。
智能体管理器负责在每一次更新时遍历场景内的所有智能体，判断智能体是否已经完成了最新路径的第一步移动，如果已经完成，则重新搜索最佳路径，否则不做任何操作。这里，该文和LRA*算法不同，不是在检查到下一步路径上有障碍物时才对路径进行修正，而是每移动一步就要重新计算路径，这是因为只有这样才能让移动着的软障碍发挥作用。假设我们不是这样做，一个智能体在第一次寻路时搜索得出一条路径，而在这个智能体的移动过程中，它路径周围的软障碍变得多起来，而恰好路径又没有通过软障碍的中心，那么就算密度消耗非常的高，智能体还是会沿着路径一直走，这并不是我们想要的效果。
下面给出智能体管理器更新函数伪代码：
for all Agent in Agents of the Scene call“A”do
if A’s Path Movement Finished then
Update Pathfinding Unit
Find new Path for A
Set the First Cell of the new Path A’s next Path Target
end if
end for
3结果
这套多智能体寻路系统能够高效的模拟小规模人群（大约20-40智能体）在中型网格地图（大约40*40到60*60）上的寻路活动。我们将测试程序在一台具有3.00GHz Inter Core2 Duo处理器及ATI Radeon 4850显卡配置的计算机上运行，得到45FPS以上的帧速率，在智能体数量达到100时，帧速率下降到3-6FPS。由于本文没有将算法在GPU上实现，运行效率受到了明显限制，在将来的工作中，可以尝试将这个算法在GPU上实现，这样便能显著的提高运行效率，满足大规模人群在大型网格地图上的寻路活动。
图6是一个20智能体在测试地形上的寻路过程。10个女性NPC和10个男性NPC分别在初始化在地图的两个角落，女性NPC和男性NPC都以对方的初始位置为移动目标，通过本文实现的寻路系统，他们成功的绕过墙壁，避开NPC之间的碰撞，到达了目的地。
图6多智能体寻路测试
图7显示了将本系统应用在3D游戏上的运行效果。游戏要求每个NPC在场景中都拥有各自的目的，他们可能移动到场景内的任何一个房间，和主角谈话，甚至可能停下来发一会呆，所以，这些NPC的行为不是一个群体行为，而本文的寻路系统能够很好的模拟这一点。
参考文献：
[1] Ko-Hsin Cindy Wang and Adi Botea.Fast and Memory-Efficient Multi-Agent Pathfinding[C].Proceedings of the Eighteenth International Conference on Automated Planning and Scheduling,2008:380-387.
[2] Peter Hart,Nils Nilsson,Bertram Raphael.A Formal Basis for the Heuristic Determination of Minimum Cost Paths[J].IEEE Transactions on Systems Science and Cybernetics,1968,4(2):100-107.
[3] Ian Millington.Articial Intelligence for Games (The Morgan Kaufmann Series in Interactive 3D Technology)[C].Morgan Kaufmann Publish? ers Inc.,San Francisco, CA, USA,2006.
[4] Silver D.Cooperative pathfinding[J].In Young, R. M.,and Laird, J. E., eds.,AIIDE,AAAI Press,2005:117-122.
篇6
[关键词]三角形单联络；中压配电网；智能规划
中图分类号：TM715；TP18 文献标识码：A 文章编号：1009-914X（2014）37-0240-02
城市配电网中重要的一部分就是中压配电网，中压配电网的“筋骨”是网络结构，一个坚强的网架对电网的安全可靠运以及经济的运营有重要的意义。国内一直以来都将网络架构的研究重点放在接线模式方面，但是当前很多发达国家的网架建设已经不再考虑单纯的应用接线模式，而是利用标准的供电模型来对高水平的中压配电网进行构筑，结合国外的先进经验，国内一些学者进行了有关供电模型以及其特性的研究，并构建了与我国中压配电网相适应的若干种典型的供电模型。
一、配电模型分析
配电模型能够对供电区域的地形特点、负荷密度以及电网现状之间的关系进行反映，它针对某一供电的区域，以高压配电的变电站作为源点并以中压馈线作为网，使供电网络单元通过组合优选来形成。供电模型的是以供电架构为基础并对中压配电网的接线模式相配合来完成构建的。供电模型主要分为点状供电模型、链式供电模型以及三角供电模型和矩形供电模型四种，本文以单联络三角形供电模型为研究对象，图1表示的是单联络三角形供电模型，其中是高压变电站，是分段开关，是联络开关，线段代表10KV供电线路。
二、配电网规划的相关数学模型
本文在配电网络的规划数学模型的选择上，最小的目标函数是以线路的规划年综合费用来充当，这其中包含了投资费用以及网损费用。电网的线路主要有主干线线、联络线路以及分支线路来组成。如果在进行优化时将这三者都考虑到，是非常复杂的，所以本文主要的优化对象是主干线以及联络线路，只将分支线路做近似考虑，就是说在总费用中只将其近似的投资费用计入。目标函数表示为，在该式中表示的是主干以及联络线路投资，表示的是主干线路的网损，表示的是分支线路的近似投资。在这其中，又可得：（1）其中是变电站低压侧线路的折旧年限，是贴现率，是单位长度的线路投资费用，N是变电站的总数，是第i座变电站的第j条主要干线长度，是第 个变电站的所出路线总数，K是本组模型的联络线路的总数，是第条联络线路的长度。（2），φ，b表示线路的网损折算系数，表示单位电能损耗折价系数，表示线路的单位长度电阻，表示线路年损耗的小时数，表示功率因数，U表示变电的压低压侧线路的线电压，表示第j条主干线带的负荷。（3）其中，表示单位长度的分支线路投资，表示分布于第i座变电站第j条主干线路的垂直分支路长度的总和，q表示的是分支线路的曲折系数。
三、智能规划方法
1、基础数据
在供电模型的基础上进行布线规划时，主要需要变电站的位置、容量以及供电范围和负荷点的位置以及负荷值，还有配电网络的地理信息等基础数据。
2、构建优化模型
2.1 构建辐射线路
在对辐射线路进行构建时，采用的方法是备选路径集方法。本文采用的是蚁群算法来对备选路径集进行建立，因为它的性能更优秀。图2为蚁群算法的流程图。
2.2 构建联络线路
在将辐射线路进行构建后，联络线路包含了站间联络、站内联络，这些都产生于辐射线路的末端。并且，联络线路通常都选用的是辐射线路末端节点间的最小路径，所以可以应用Floyd最短路径算法的来实现联络线路的构建。
2.3 主干线路的供电范围
在形成了变电站的主干线后，就要对每条主干线路的带负荷情况进行确定，也就是主干线路的供电范围，在进行确定时的方法是先将每条主干线路的负载余量进行计算，之后选择任意一个负荷点，从近到远的搜索最短的路径。此方法能够搜索出所有的负荷点，就可以对每条线路的主干线的供电范围进行确定。
2.4 构建优化模型
本文采用的主要优化手段是遗传算法，所以在构建优化模型时，主要的工作是对主干以及联络线路的染色体进行建立。生成染色体的初始种群过程为对每个变电站，以每个变电站为中心将其供电范围近似为一个圆，然后做圆的N等分线，等分线数目等于主干线路的数目。接着随机选择来自于等分线末端的任一领域内的一个街道分段点来作为主干线路的末端节点，这样就形成了一个末端节点的集合，因为随机选择所以此集合的组合方式有很多的方式，并且随着圆的等分线进行转动，其对应的转动角会有不同的组合方式。
3、适应度计算
一个染色体代表的是一个供电模型的规划方案，在这里适应度就代表的是上述的总目标函数。
4、遗传模拟退火操作
模拟退火操作的对象是遗传种群中的所有染色体，随机选择其邻域的一种状态，然后对其进行模拟退火的接受概率接受或是拒绝的过程。本文构建的染色体代表其中的某一主干线路，对和它有一样末端节点进行选择，并且选择之前的K条最短路以外的备选路径集中的随便一条线路来作为领域的状态，并按照下文的接受概率进行接受或拒绝过程。接受概率公式：，其中代表新状态的评价值，第k代的温度，代表原状态评价值。通过这个过程能够得到新的染色体种群，之后对其做遗传操作，一直循环一直到能够满足终止的条件。
结束语
在过去，先进行辐射线路的布局，之后进行联络线路的优化是带联络线路的配电网主要的布线方法，但这种方法具有局限性。本文对基于三角形单联络模型的中压配电网进行智能规划时，构建了主干以及联络线路的整体优化模型，并对其布线的方案进行了优化，这就使得优化的全局性得到了优化，优化的方法的是以优化模型中的染色体的构成特点为依据，并在遗传算法中引入了模拟退火思想，这样做的优点是可以克服算法过早收敛的问题，能有效的进行优化。
参考文献
篇7
关键词：蚁群算法；物流配送；路径优化；数学模型
DOIDOI：10.11907/rjdk.161974
中图分类号：TP319
文献标识码：A 文章编号文章编号：16727800（2016）011014004
基金项目基金项目：
作者简介作者简介：袁文涛（1993-）男，安徽马鞍山人，上海理工大学光电信息与计算机工程学院硕士研究生，研究方向为模式识别与智能系统；孙红（1964-）女，上海人，上海理工大学光电信息与计算机工程学院副教授、硕士生导师，研究方向为模式识别与智能系统、 控制理论与控制工程、企业信息化系统与工程。
0 引言
解决组合优化问题的最优化求解算法有多种现代人工智能算法方案，优化算法用来处理问题最优解的求解，该问题通常由多个变量共同决定。当前，求解最短路径问题是图论研究中的一个典型求解组合优化算法问题，旨在寻找图表（由节点和路径构成）中两节点或多节点之间的最短路径。常用的最优化路径求解方法有Bellman-Ford算法、Dijkstra算法、A*算法和蚁群算法。这些算法都有自身的优点和不足。在对不同算法作出比较后，可以得出蚁群算法在解决网络路由和城市交通系统的问题中是相对有利的。
就目前研究来看，随着实际组合问题的变化，基本的智能算法已经不能满足解决这类组合优化问题，同时其优势也在减弱[1]。本文采取改进后的组合优化蚁群算法以弥补传统蚁群算法易陷入局部最优解的不足，加快了求全局最优解的构造速率。
蚁群算法（Ant Colony Optimization， ACO），是一种模拟蚂蚁群体智能行为的进化仿生类优化算法，在求解性能上具有强鲁棒性、优良的分布式计算能力、便于与其它算法相结合等优点[2-3]。通常作为一种用来在多变量组合优化问题的多候选解中寻找最优化路径的机率型算法。它由Marco Dorigo于1992年在其博士论文《Ant system： optimization by a colony of cooperating agents》中首先提出，其灵感来源于通过对蚁群社会的长期跟踪观察后发现，虽然单个蚂蚁没有视力、智慧程度低、工作方式简单，但它们却有强大的执行能力和协同工作能力，依靠复杂群体的自组织协同能力发挥出超出单个个体累加的智能，是一种超个体（superorganism，又称超有机体）存在现象。蚁群是在这样的超个体案例中最有名的例子。虽然蚁群算法的严格理论基础和实际应用尚未成熟，国内外相关研究暂处于实验阶段，但这并不妨碍人们对蚁群算法的研究已经由当初单一的解决商旅问题（TSP）发展到解决调度问题、网络通信等多个方向的最优化求解应用。
目前，蚁群优化算法已广泛应用于多种求组合最优化问题，在面临路例如作业安排调度问题和路由车辆的二次分派问题上表现出了良好的性能，也经常被用来求旅行推销员问题的拟最优解。它在图表动态变化情况问题的求解上相比萤火虫算法和遗传算法具有绝对优势：蚁群算法的最大优点在于可以连续运行并适应实时变化；缺陷是在处理较大规模和复杂数据问题时，容易存在运算耗时长、收敛速度慢、得不到全局最优解等问题。
在求最优解的历次迭代中，单个蚂蚁会根据给定的规则和限定条件选择从一个城市（节点）转移到另一个城市（节点）：它必须对所有城市访问一次，而相对距离越远的城市被选中为下一个访问点的机会越少（能见度低）；相反，在两个城市（节点）边际的一边形成的信息素越浓烈，则该边际作为路径被选择的概率越大；在较短路程情况下，短时间内更多蚂蚁会在所有走过的路径上留下更多信息素，在每次迭代更新后，信息素轨迹浓度会按百分比挥发从而反馈给下一只途经的蚂蚁并影响它作出路径选择。
1 车辆路径问题
传统的车辆路径问题也叫VRP（Vehicle Routing Problem）问题，是关系到现代物联网发展过程中物流配送系统的一个关键问题，属于NP难题。一直以来，该问题也是管理科学和物流运输方面的重要课题[4]，受到国内外学者的广泛关注。
VRP问题描述如下：在一些由于经济或者地理限定的条件约束下，组织一个车队，从一个或者多个初始点出发，规定达到多个不同的地点，设计一个成本最小、路程最短的路线集，使得：① 每个城市只能被一辆车访问，只访问一次；②所有送货车辆必须从起始点出发再回到起始点；③某些特定的约束条件需要被满足。
VRP的数学模型表示如下：一共有k个客户，第i个客户的货物需求为gi，配送中心派出车辆承担运输任务，其载重为q。设gi
如果前提有约束条件用于车辆本身，即容量限制和总长限制，则称为有能力约束的车辆路径问题（Capacitated Vehicle Routing Problem）。此模型是车辆路径问题的基本模型，这类VRP问题叫作CVRP问题[5]。
设每个客户点只允许被访问一次，车辆所访问的客户点的需求总和不能超过车辆的负载能力，且总行驶的路程也不得超过其最大的行驶距离，达到用最少的车辆最短的路径完成既定任务。
。
2 可约束蚁群算法实现
2.1 算法实现方式
当前蚁群算法领域存在MPDACO局部更新和MPDACO全局更新两种方式。前者指当单个蚂蚁从一个节点到达下一个节点完成转移后就立刻更新蚂蚁通过路径时所留下的的信息素，后者是当蚂蚁遍历完所有给定节点后再更新整条路径上的信息素，不再是对所有的蚂蚁，而是仅对全局最优的蚂蚁得到的路径使用。从两种更新方式得到的结果作对比可以得出，全局信息素更新方法虽然可以加快收敛速率，但是存在着一定的缺陷和不足，易使路径更快地集中于单一解，易陷入局部最优，这些缺点限制了它的广泛传播及应用。
本文综合上述两种更新方法的优点和不足，列出了一种新的组合叠加更新方法：在路径搜索的前十次循环中，采用局部最优解更新，十次固定循环结束后，再采用全局最优解进行更新，这种更新方式可以有效避免蚁群搜索得到的路径沉入局部最优解中，有利于发现更多较优解。
2.2 算法实现步骤
根据改进的蚁群算法，将优化后的蚁群算法应用于CVRP问题的实现步骤如下：
（1）参数初始化。设迭代次数 Nc=0；每条路径上的信息素浓度Δτij（0）=c（c为常数），并且Δτij=0；随机将m个蚂蚁放置到初始点上。
（2）更新迭代（循环）次数，即Nc=Nc+1。
（3）初始化禁忌表，蚂蚁禁忌表的索引号k=1。
（4）更新蚂蚁数目k=k+1。
（5）判断路径是否在搜索热区内。按照式（a）～（f）计算出每只蚂蚁应当转移至下一个城市（节点）的概率并完成移动。
（6）当蚂蚁从i城市（节点）出发到达j城市（节点）时，对其所经过的路径上的信息素进行更新，并修改禁忌表，将禁忌表指针按照当前状况进行修改，即将新城市（节点）j置于禁忌表tabuk中。
（7）执行步骤（b）～（f），直到所有蚂蚁都找到了一条包含所有城市（节点）的可行路径解。
（8）在新生成的所有可行解中找到一条最短路径作为本次迭代中的最优路径解。
（9）判断循环次数是否小于十次，若小于十次，则对蚂蚁找到的最优路径按照本次迭代最优值进行信息素更新；若循环次数超过十次，则按照全局信息素进行更新。
（10）对所有蚂蚁经过的路径，按式（1）进行一次全局更新。
（11）循环执行（b）～（j），直到连续多次的迭代中得到的解已收敛或循环次数Nc的值已经达到给定的最大迭代次数的情况下选取当前输出值作为本次最优解。
3 实验仿真
设存在一个物流中心有4辆运输车， 单辆车最大载重为1 000kg， 现需要同时向7个随机分布的客户点派送货物， 蚁群算法的初始化参数为： 蚂蚁总数为20只， 算法的最大迭代数为100次， α和β分别为1，2， 信息素的挥发速度为0.75， 实验重复运行100次， 求得的平均结果为最终结果。同时初始时刻各边上的信息痕迹为1，残留信息的相对重要度为1，设置预见度为5。原始数据进行处理结果分析如图3所示。按本文提出的优化蚁群算法求解CVRP后的处理仿真结果如图4所示。
观测图3、图4的收敛曲线，可以知道蚁群算法优化后的结果相比之前的行车路径有大幅度优化[810]，如图5所示。针对每个收敛的点结合数据可以看出，传统蚁群算法的平均路径在迭代次数为45时可以得到最优解，而改进后的蚁群算法可以在第5次左右得到最优解，相当于收敛速度提高了近80%。
4 结语
在当今应用数学和理论计算机科学的领域中，组合优化（Combinatorial Optimization）是在一个有限的对象集中找出最优对象的一类重要课题，属于运筹学的一个重要分支。在很多组合优化问题中，穷举搜索/枚举法是不可行的。组合优化问题的特征为可行解的集是离散或者可以简化到离散的，并且目标是找到最优解。解决组合优化问题一般采用智能算法，而这些算法都有自身的优点和缺点。组合优化的难处，主要是加进来拓扑分析，在不同的拓扑形态下，算法也需随着不同部分的约束关系作出相应调整。从目前研究来看，随着实际组合问题的变化，基本的智能算法已不能解决这类组合优化问题。
蚁群算法作为一种仿生类进化算法在求路径最优化解方面具有很好的效果。本文首先引出蚁群算法可以用于解决这一类问题，然后介绍了约束车辆路径问题，也即CVRP问题，说明了其约束模型；接着研究了基本的蚁群算法步骤，并对其中信息素更新和改进了启发因子，解析并改良了蚁群算法应用于CVRP问题的实现步骤和处理方法。
本文提出的组合叠加更新方法可有效克服传统蚁群算法收敛质量低、耗时长、易陷入局部最优解等缺陷，使蚁群算法的全局优化能力得到大幅度提高。对比实验前数据可以看出，蚁群算法找到最短路径的收敛速度比传统方法快了80%左右，确实是一种求解最短物流配送路径的有效算法。
参考文献：
[1] 陈昌敏.基于蚁群算法的物流配送路径优化研究与应用[D].成都：西华大学，2012（4）：1154.
[2] 宋留勇，王锐，周永旺，等.动态城市交通网络优化模型研究及算法设计[J].测绘科学，2011，36（1）：134136.
[3] 钟石泉，贺国光.有时间窗约束车辆调度优化的一种禁忌算法[J].系统工程理论方法应用，2005，14（6）：523527.
[4] CHAO YIMING.A tabu search method for the truck and trailer routing problem[J].Computer and Operations Research，2002，29（1）：3351.
[5] 杨中秋，张延华.改进蚁群算法在交通系统最短路径问题的研究[J].科学计算与信息处理，2009，32（8）：7678.
[6] 李松，刘兴，李瑞彩.基于混合禁忌搜索算法的物流配送路径优化问题研究[J].铁道运输与经济， 2007， 29（3）：66 69.
[7] 陶波， 朱玉琴.改进的7动态规划法在车辆最短路径问题中的应用[J].重庆工学院学报， 2009，23（1）：2427.
[8] 李军，郭耀煌.物流配送车辆优化调度理论与方法[M].北京：中国物资出版社， 2001：101113.
[9] 张万旭，林健良，杨晓伟.改进的最大最小蚂蚁算法在有时间窗车辆路径问题中的应用[J].计算机集成制造系统，2005，11（4）：572576.
[10] 余h，胡宏智.基于改进遗传算法的物流配送路径求解[J].计算机技术与发展，2009，19（3）：5255.
[11] 朱庆保，蚁群优化算法的收敛性分析[J]. 控制与决策，2006，21（7）：3016.
[12] 郑松，侯迪波，周泽魁，动态调整选择策略的改进蚁群算法[J].控制与决策，2008，23（2）：13.
[13] 夏亚梅，程渤，陈俊亮，等.基于改进蚁群算法的服务组合优化[J].计算机学报，2012，35（2）：311.
篇8
关键词：群体算法；模糊聚类；预测模型；预测
中图分类号：TP301文献标识码：A
1前言
电力负荷预测是电力系统调度和计划部门安排购电计划和制定运行方式的基础，它对于电力系统规划、运行与控制有着重要的意义。为了提高电网运行的安全性和经济性，改善供电质量，负荷预测需要尽可能高的预测精度。随着分时电价的市场化营运，精度高、速度快的预测理论和方法愈显重要和迫切。
负荷预测已有很长的研究历史。早期的方法以时间序列法、回归分析法为主[1]，这类方法计算量小，速度较快，但由于模型过于简单而无法模拟复杂多变的电力负荷。近年来，随着人工智能技术的迅猛发展，灰色理论法[2]、神经网络法[3]、相似日聚类[4]，模糊聚类[5]在负荷预测领域得到广泛应用。它们较以前的方法更能处理负荷和影响因素之间的非线形关系，因而得到了较高的预测精度。但他们有各自的缺点，灰色预测模型从理论上讲可以适用于任何非线性变化的负荷指标预测，但其微分方程指数解比较适合于具有指数增长趋势的负荷指标，对于具有其他趋势的指标，则拟合灰度大，精度难以提高。利用神经网络进行电力负荷预测时，神经网络可以通过学习，从复杂的样本数据中拟合出输入输出之间高维、非线性的映射关系，从而进行较高精度的预测。但是，电力负荷受到多种因素的影响，电力负荷曲线的变化形态差异较大。
目前，针对电力负荷预测较好的方法是采用组合式预测模型-FCBP模型[6]。其原理是这样的：首先，采用模糊聚类分析方法，以每天的负荷数据、天气数据以及天类别数据为指标，将历史数据分成若干类别；然后对每一类别建立相应的神经网络预测模型；预测时找出与预测天相符的预测类别，利用相应的神经网络预测模型进行电力负荷预测，实践证明这种方法是有效的。
但是传统的模糊聚类算法有易陷入局部最优解，处理大量、高维的数据时，在时间性能上难以令人满意的缺陷。蚁群算法是最近几年才提出的一种新型的模拟进化算法，由意大利学者Dorigo,M[7]等人首先提出，用蚁群在搜索食物源的过程中所体现出来的寻优能力来解决一些离散系统优化中困难问题。已经用该方法求解了旅行商问题、指派问题、调度问题等，取得了一系列较好的实验结果。本文将蚁群算法引入此模型，用蚁群算法改进模糊聚类，并和神经网络组合，得到新型预测模型-AFCBP模型，经实验证明得到良好效果。
2理论分析
2.1蚁群算法优化理论
经过大量研究发现，蚂蚁个体之间是通过一种称之为外激素的物质进行信息传递，从而能相互协作，完成复杂的任务。蚂蚁在运动过程中，能够在它所经过的路径上留下该种物质，而且蚂蚁在运动过程中能够感知这种物质的存在及其强度，并以此指导自己的运动方向，蚂蚁倾向于朝着该物质强度高的方向移动。因此，由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。蚂蚁个体之间就是通过这种信息的交流达到搜索食物的目的。
以TSP问题为例说明基本蚁群算法的框架，设有m个城市，dij(i,j=1,2,…,n)表示城市i和j间的距离，τij(t)表示在t时刻城市i和j之间的信息量，用它模拟实际蚂蚁的外激素。设共有m只蚂蚁，用 表示在t时刻蚂蚁k由城市i转移到城市j的概率：
其中，U为蚂蚁已经搜索过的部分路径，S表示蚂蚁k下一步允许走过的城市的集合，a表示路径上的信息量对蚂蚁选择路径所起的作用大小， 表示为由城市i转移到城市j的期望程度，例如，可以取 。当a=0时，算法就是传统的贪心算法；而当b=0时，就成了纯粹的正反馈的启发式算法。经过n个时刻，蚂蚁可走完所有的城市，完成一次循环。每只蚂蚁所走过的路径就是一个解，此时，要根据下式对各路径上信息量作更新：
其中，Q为常数，Lk为蚂蚁k在本次循环中所走路径的长度。在经过若干次循环以后，可以根据适当的停止条件来结束计算。
由上述可知，蚁群算法的优化过程的本质在于：1) 选择机制，信息量越大的路径，被选择的概率越大；2) 更新机制，路径上面的信息量会随蚂蚁的经过而增长，而且同时也随时间的推移逐渐减小；3) 协调机制，蚂蚁之间实际上是通过信息量来互相通讯、协同工作的，这样的机制使得蚁群算法具有很强的发现较好解能力。
2.2模糊聚类基本原理
聚类分析算法可以描述为：给定m维空间R中的n个向量，把每个向量归属到m个聚类中的某一个，使得每一个向量与其聚类中心的距离最小。经常用的基于划分的聚类算法是c-均值算法，它把n个向量 (i= 1，2,…,n)分成m个类 (i=1,2,…,m)，并求每类的聚类中心，使得非相似性（或距离）指标的目标函数达到最小。当选择第i个类 中向量 与相应的聚类中心 间的度量为欧基里德距离时，目标函数定义为：
这里p是循环计算的次数， 是类 内的目标函数， 表明参数确定属于哪个簇团。显然 的大小取决于聚类中心 和 的形状， 越小，表明聚类的效果越好。
c-均值算法的隶属度要么是1，要么是0，这种硬性的划分数据点属于某一类团不能反映数据点与簇团中心的实际关系。为了处理这个问题，人们引入了模糊集的概念。自1969年Ruspini首先提出第一个解析的模糊聚类算法以来，已经有很多人提出了许多的模糊聚类算法。基于模糊划分的模糊聚类算法，其主要思想是将经典划分的定义模糊化，可以认为数据点以某种隶属度属于一个簇团，又以某种隶属度属于其它簇团。
在众多的模糊聚类算法中，应用最广泛而且较成功的是1974年由Dunn提出并由Bezdek加以推广的模糊C-均值(fuzzy C-means，简称FCM)算法。同样，FCM算法是把n个向量 (I=1,2,…,n)分成m个模糊簇团 ，并求得每个簇团的聚类中心,使目标函数达到最小，FCM的目标函数定义为：
由于多约束优化问题的求解是一个NPC问题，常用的求解方法是分别对U和C进行偏优化的Fk-prototypes 算法[8]，主要思想是：（1）先选择C的一个初始值，找到使 最小的U值；（2）然后固定U找到使 最小的C；（3）优化过程交替进行，直到前后目标函数的差值与目标函数的比小于ε为止。
这一算法的缺陷在于需要赋予不同的c值进行多次重复计算，且结果通常是局部最优解，同时运算时间是很大的，因为一次矩阵乘法所需要的时间为O(n3)，实现算法的第一步的时间复杂度就达到O(n4logn)。
2.3用蚁群算法改进模糊聚类
提高模糊聚类计算速度的关键之一是隶属度矩阵的初始点的选取，如果能开始就得到每个参数点归于每个簇团的隶属度近似结果，那么将较大的改进模糊聚算法的速度，蚁群算法就可以实现这以功能。
其基本思想是将数据视为具有不同属性的蚂蚁，聚类中心看作是蚂蚁所要寻找的“食物源”[9]，所以数据聚类就看作是蚂蚁寻找食物源的过程。具体过程如下：每只蚂蚁从各个聚类中心出发，在整个解空间中搜索到下一个样本点后；再从聚类中心出发，在整个解空间中搜索到另一个样本点，当搜索到样本点达到该聚类原来的样本点总数后，就认为蚂蚁完成了一个路径的搜索。为使蚂蚁在同一路径的搜索中不重复搜索同一个样本点，给每只蚂蚁设置禁忌表tabu(N)。规定：如果tabu(j)为1，则结点j是可以选择的搜索样本点，当蚂蚁选择了结点j后，就将tabu(j)置为0，此时蚂蚁就不能选择结点。
设 是待进行聚类分析的数据集合，τij(t)表示在t时刻数据 和 之间的信息量。当所有蚂蚁都完成了一次路径搜索后，称算法进行了一个搜索周期。第t个搜索周期内，路径选择概率：
其中 ，其他参数和上面说明一致。在i值确定下，从j=1到m，分析 ，找到最大值后，则 归并到到 领域。令 ， 表示所有归并到 的数据集合，求出聚类中心当蚁群完成一个搜索周期后，根据 就得到了每个参数点归于某簇团的可能性，从而得到了模糊聚类隶属度矩阵的大体准确的初始值，并用 作为模糊聚类的初始中心。
由于蚁群算法本身也有一定的计算量，不宜在每次模糊聚类循环中使用蚁群算法，选用蚁群算法的策略是这样的：首先在步骤1的初始几个循环选用蚁群算法和确定初始值 （本文设为4个）和聚类的中心 ，然后根据公式4和5，模糊聚类自己循环迭代，当优化过程趋缓时，再采用一到两次蚁群算法进行优化，一直得到小于ε的结果为止。
2.4根据聚类结果建立神经网络预测模型
由于电力系统由各种因素强烈影响，存在着大量的非线性关系。其发展规律很难用一个显式的数学公式表示，许多文献利用神经网络对复杂非线性拟合能力的优点，构造预测模型。文献[6]采用了3层BP网络建立预测模型，文献[10]采用了径向基函数神经网络对电力负荷进行预测。本文经过比较和分析，发现采用MATLAB提供的动量BP神经网络计算结果比较好。由此，将历史数据聚成簇团以后，采用动量BP神经网络构造预测模型，此组合模型也称之为AFCBP模型。进行预测时，首先逐一计算预测天与各聚类中心的欧基里德距离，以距离最短的类别作为预测天的类别，再利用相应AFCBP模型进行预测。
3实际应用
3.1聚类分析
本文以某地区一年的电力负荷变化数据为对象进行实例分析, 把全年的366条负荷曲线的样本的负荷曲线作为测试样本以后，进行聚类分析。每一样本 由29个数据组成即为第i天最高温度和最低温度为对第i+1天的最高温度和最低温度的预报值为第i+1天的天类别值。
在采用蚁群算法优化（用 表示）的模糊聚类算法时，计算 的参数设为：ρ=0.7，a=1，b=1,η=1,ε=0.01, τij(0)=0。
3.2预测实例
采用上述方法建立预测模型以后，首先对负荷进行负荷预测。并与基于单一神经网络的预测模型和仅用模糊聚类的组合模型进行比较。这里用于对比的基于单一神经网络的预测模型采用MATLAB提供的动量BP神经网络，网络的样本简单地选取了预测天前4星期的负荷数据，统计误差结果如表1 所示。结果表明：预测任何种类的日负荷，采用AFCBP模型和FCBP模型要远远好于仅采用动量BP神经网络的预测模型，这充分说明了采用组合式神经网络预测模型的优势；AFCBP模型和FCBP模型在预测普通工作日的负荷都比较稳定，AFCBP模型仅比FCBP模型略好一些，这是因为聚类簇团中普通工作日样本数据较多，两种模型预测都比较好；在预测双休日和节假日时，AFCBP模型具有更好的预测精度，这是因为AFCBP模型聚类的效果更细致、更准确的结果。
然后分析两种模型对夏季典型日负荷预测的结果。如图1所示，可以发现采用AFCBP预测模型整体上要比FCBP预测模型效果要好，尤其在边缘点和变化剧烈区域预测结果较好。平均绝对百分误差 和最大绝对百分误差 的数值也反映了这一点。
图1：典型负荷预测结果比较
4结论
本文把蚁群算法和c-means算法相结合，把蚂蚁k由城市i转移到城市j的概率 作为隶属度矩阵的初值，计算出的中心作为FCM的初始中心，对模糊聚类进行改进，得到较好结果，并以每天的24 点负荷数据、天气数据以及天类别数据为指标，用改进后模糊聚类把历史数据聚分成若干簇团；然后，采用动量BP神经网络针对每一簇团建立相应的预测模型。对山东地区1年的实际负荷变化数据进行预测分析的结果表明，该模型不仅对普通工作日有较高的预测精度，对双休日、节假日和一些特殊情况（夏季典型日负荷）也有较好的预测精度。
参考文献：
[1] 周继芗. 实用回归分析[M]. 上海: 上海科学技术出版社,1990.
[2] Burke J J , et al . Power quality-two different perspectives [J]. IEEE Transaction on Power Delivery, 1990,(3).
[3] Verdelho P , et al . An active filter and unbalanced current compensator [J]. IEEE Transaction on Power Electronics , 1997(3).
[4] Gerbec D，Gasperic S，Smon I et al． An approach to customers daily load profile determination [C]. IEEE Power Engineering Society Summer Meeting，Chicago，IL USA，2002(1).
[5] Papadakis S E，Theocharis J B，Bakirtzis A G．A load curve based fuzzy modeling technique for short-term load forecasting.[J] Fuzzy Sets and Systems, 2003(2).
[6] 陈耀武, 汪乐宇, 龙洪玉等. 基于组合式神经网络的电力负荷预测模型[J]. 中国电机工程学报,2001(4).
[7] Dorigo, M., Maniezzo, V., Colorni, A., 1996. Ant system: optimizationby a colony of cooperating agents. IEEE Trans. Syst. Man Cybernet. B (1).
[8] 陈宁, 陈安, 周龙骧. 数值型和分类型混合数据的模糊K-Prototypes聚类算法[J]. 软件学报, 2001(8).
篇9
【关键词】 TSP问题 数学模型 智能优化算法
随着我国经济的持续快速发展，人们对交通运输的各种需求也显著增长。从1999年到2010年，我国公路总长度从130万公里上升到370万公里，增长幅度为185%，同期我国注册的车辆数量由1500万辆上升到8000万辆，增长幅度为433%，明显高于中国公路总长的增长幅度。由于车辆数量的激增，导致城市交通拥堵严重，交通事故频发，物流成本居高不下，物流时效性也无法得到保证。我国物流成本占GDP的比重持续偏高，约为20%，远高于发达国家物流成本占GDP的比重10%，以及中等发达国家的16%。而城市闲置土地资源的紧缺，导致修建和拓宽道路的成本越来越高，且修建和拓宽道路的速度远远赶不上城市车辆的增长速度，此时提高城市道路的利用率、安全性和舒适性以及降低城市物流成本就成为我们急需解决的问题。
物流配送调度系统就是针对以上问题提出的，它能提供可靠的交通信息、高效快速的应急服务，在降低物流成本方面有着显著的成效，能满足现代物流经济性、准时性和灵活性的多种需求。迄今为止，国外研究物流配送调度系统的理论和算法已经不少，并且在实际应用方面取得显著的成果，如美国IBM基于最短路径法和启发式算法研究出来的VSPX系统，日本富士通以节约法为核心研发出来的VSS系统，以及美国美孚以扫描法为核心研究出来的HPCAD系统。但是国内在这方面的研究仅停滞于初步理论阶段，在开发实用的物流配送调度系统方面还是一片空白。造成这种现象的根本原因在于大部分算法只考虑了TSP（Traveling salesman problem）问题的部分约束条件，且设置了许多假设条件，限制了他们的应用范围，在实际应用中缺乏灵活性。由于研发物流配送调度系统的核心在于解决贴合实际的TSP问题，因此研究可以妥善解决TSP问题的算法，并在此基础上开发出智能的物流配送调度系统具有现实的理论意义和实践意义。
一、TSP问题
1、TSP问题的简介
TSP问题也称旅行推销员问题、货郎担问题，是经典的组合优化问题，最早的记录来自于1759年欧拉研究的骑士周游问题，即对象棋中的64个方格，走访每个方格有且仅有一次。TSP问题的历史可以分成以下几个阶段：1800―1900年，首次描述TSP问题；1920―1930年，TSP问题得到较好的定义；1940―1950年，研究人员意识到TSP问题是个难题；1954年，42个城市的TSP问题求得最优解；1980年，Crowder和Padberg求解了318个城市的问题；1987年，Padberg和Rinaldi求解了2392个城市的问题；1992年，美国Rice大学的CRPC研究小组解决了3038个城市的问题；1994年，Applegate、Bixby和Chvatal等人解决了7393个城市的问题；1998年，CRPC研究解决了美国13509个城市组成的TSP问题；2003年，Hisao Tamaki发现了TSPLIB中pla33810的一个次优解；2004年，Keld Helsguan 发现了pla85900问题的一个次优解。
2、TSP问题的数学模型
二、求解TSP问题的各种解法
目前求解TSP问题的主要方法主要分两类：精确求解算法和近似求解算法。
精确求解算法通过搜索整个问题的全部解空间，在所有解集中求得最优解。精确求解算法包括整数规划法、动态规划法、分支定界算法等，这类算法虽然可以得到精确解，但由于过大的搜索空间范围导致计算时间过长，计算效率非常低下，很少用于实际应用。最早用于解决TSP问题的精确求解算法是穷举法，思路简单，可以直观快速地求出少量城市点数的最优解，但是求解大规模数据集时运算量太大，运算效率不高，时间上难以承受。
近似求解法又可称为启发式求解算法，部分近似求解算法又被称为智能优化算法。典型的近似算法有插入算法、r-opt算法和最近邻算法等，这类算法虽然可以较快的计算出可行解，但是其接近最优解的程度不够令人满意。智能优化算法主要包括神经网络算法、遗传算法、禁忌搜索算法、模拟退火法、粒子群算法和蚁群算法等，是近几年来非常活跃的研究领域，它是利用仿生学的原理，让算法在计算过程中不断自我调整，使之具备自适应能力。智能优化算法虽然不能在有限的时间内获得最优解，但其接近最优解的程度是非常可喜的。
求解TSP问题的算法很多，要评价和比较各种算法的优劣，必须有一个综合的性能评价标准，TSP算法的综合性能评价标准包括：算法求解的精确程度，即接近最优解的程度；求解算法的复杂度，包括时间的复杂度和空间的复杂度；求解算法的适应性，即算法在各个领域的通用程度；求解算法的严密性，即保证求解算法充分的理论基础。
综合比较，智能优化算法是一类综合性能比较强的TSP算法，也是目前最适合用于开发物流配送调度系统的算法，本文将对几种智能优化算法进行详细说明。
1、神经网络算法
人工神经网络（Artificial Neural Network,简称ANN），又名神经网络（Neural Network,简称NN），是一种通过模拟动物神经网络的特点进行数据分析的方法。1985年，Hopfield和Tank首次将这种算法应用于求解TSP问题。它的主要思想是用能量函数替代TSP问题中的目标函数，通过能量函数确定神经元之间的相互连接权限，随着网络状态的逐渐变化，当能量达到平衡时，就可以得到局部最优解。
由于神经网络是一种数据驱动型非线性映射模型，可以实现任何复杂的因果关系映射，能够从大量的历史数据中进行聚类和学习，进而找到某些行为变化规律，因此可以用来处理难以用数学模型描述的系统，具有很强的并行性、自适应、联想记忆、容错鲁棒以及任意逼近非线性等特性。目前神经网络技术在解决TSP问题上取得了一定的成绩，但是神经网络存在严重缺陷，很难确定算法的参数，必须通过多次反复的数据测试才能获得一个相对较好的参数，因此严重限制了神经网络的适用范围。
2、遗传算法
遗传算法是Holland于1973年首次提出的，是一种模拟生物界自然选择和遗传机制的随机搜索算法。它的基本思想是将TSP问题的求解表示成“染色体”的适者生存的过程，通过“染色体”的一代代的进化，即通过选择、交叉和变异等操作，最终得到“最适应环境”的个体，从而求得最优解或满意解。
遗传算法能准确模拟自然界生物进化过程中的染色体，整个遗传过程操作简单，在数据优化过程中不受外界条件的限制，能用简单的计算方法实现全局解空间的搜索。但是遗传算法中容易出现“早熟”现象，必须通过设置变异概率来控制“早熟”，高的变异率扩大了搜索空间，有利于诱导产生更加优秀的个体，但是交叉概率和变异概率过大会导致收敛速度过慢，迭代次数过大。因此实现收敛速度和最优解之间的平衡是遗传算法的一大难点。
3、禁忌搜索算法
禁忌搜索算法是由Fred Glovert等于1986年首次提出的，是一种全局性逐步寻优的邻域搜索算法，可以模拟人类记忆功能的寻优特征，通过局部邻域搜索机制和相应的禁忌准则来避免重复搜索，并通过藐视准则赦免一些被禁忌的优良状态，进而保证多样化的有效搜索，最终实现全局优化。
在禁忌搜索算法的搜索过程中，邻域结构、候选解、禁忌长度、禁忌对象、藐视准则、终止准则等都是影响算法性能的关键因素。且禁忌搜索算法对初始解和邻域结构有较大的依赖性，由于禁忌算法串行的搜索机制，一个不理想的初始解将直接影响到搜索质量。
4、模拟退火法
现代模拟退火算法是由Kirkpatrick S等于1983年提出，是基于Mente Carlo迭代求解策略的一种随机寻优算法。它通过模拟物理中固体物质的退火过程，结合具有概率突跳特性的Metropolis抽样策略，在解空间中随机寻找目标函数的全局最优解，在降温过程中不断重复抽样，最终实现问题的最优解。
模拟退火算法解的优越性依赖初始温度和退火时间，当初始温度过低或者退火速度过快，算法将陷入局部最优解。但是如果迭代次数较高，随着退火速度的降低将极大增加运行时间。
5、蚁群算法
蚁群算法是由意大利学者Dorigo M于1991年首次提出，是一种模拟自然界蚂蚁寻找食物的过程来计算路径的算法，通过群体间信息素的交换和相互合作寻求最优解的过程。蚂蚁独立寻找食物，在找寻食物的路程中会释放信息素，信息素会影响随后的蚂蚁对路径的选择，信息素越强的路径，越可能被蚂蚁选择。对于蚂蚁算法来说，各条路径的初始信息素相同，但是随着时间的推移，较优路径上的信息素会越来越多，最后实现寻求最优解或次优解的目的。
蚂蚁算法中，蚂蚁数量M的设置是影响算法性能的重要因素，M过小会导致未被所搜索过的路径信息素趋向于0，全局搜索能力太差，稳定性变差。M过大会导致所有路径上的信息素过于平均，随机性太强，收敛速度过慢，信息正反馈能力过弱。有研究表明，M取值范围在[0.6n,0.9n]（n代表城市规模），蚂蚁算法的收敛速度和接近全局最优解的能力最理想。
在蚂蚁算法中，总信息量Q表示循环一周蚂蚁释放的信息素的总和，Q也同样对蚂蚁算法的性能有很大的影响。Q越大信息素增长越快，正反馈效果越好，算法收敛速度越快。研究表明，Q的取值与TSP问题的规模和路径长度有关，在小规模的TSP问题中，Q一般取100。
蚂蚁算法具有正反馈、并发性、较强的鲁棒性、易于其他算法相结合等优点，但是蚂蚁算法易出现停滞现象。
【参考文献】
[1] 国家发展和改革委员会经济运行调节局、南开大学现代物流研究中心：中国现代物流发展报告（2010）[M].中国物资出版社，2010.
[2] 唐纳德, J.鲍尔索科斯、戴维J.克劳斯：物流管理[M].机械工业出版社，1999.
篇10
【关键词】计算机智能 群体智能 算法
计算机技术不断发展，算法技术也在不断更新。群体智能（Swarm Intelligent，SI）算法始于20世纪90年代初，主要是受自然界生物群体智能现象的启发，通过模仿社会性动物的行为，而提出的一种随机优化算法。群体智能是基于种群行为对给定的目标进行寻优的启发式搜索算法，其的核心是由众多简单个体组成的群体能够通过相互之间的简单合作来实现某一较复杂的功能。所以群体智能可以在没有集中控制并且缺少全局信息和模型的前提下，为寻找复杂的分布式问题的解决方案提供了基础。
1 传统群体智能算法
1.1 蚁群算法（ACO）
1991年意大利学者Dorigo M等受到自然界中蚁群觅食行为启发而提出了蚁群算法（Ant Colony Optimization，ACO）。蚁群算法的基本理念是蚁群生物性的利用最短路径的根据局部信息调整路径上的信息素找寻的特征，这个算法的优势非常的明显，而且具有较为突出的应用性，在这个过程中蚂蚁可以逐步地构造问题的可行解，在解的构造期间，每只蚂蚁可以使用概率方式向下一个节点跳转，而且由于这个节点是具有较强信息素和较高启发式因子的方向，直至无法进一步移动。此时，蚂蚁所走路径对应于待求解问题的一个可行解。蚁群算法目前已成功地用于解决旅行商TSP问题、数据挖掘、二次指派问题、网络路由优化、机器人路径规划、图着色、物流配送车辆调度、PID控制参数优化及无线传感器网络等问题。
1.2 人工鱼群算法（AFO）
2002年由我国的李晓磊等受鱼群运动行为的启发而提出了人工鱼群算法（Artificial Fish-Swarm Algorithm，AFSA）。人工鱼群算法的思想主要是利用鱼个体的四种行为（觅食、聚群、追尾和随机）的特征，通过技术应用将人工鱼随机地分布于解空间中，解空间中包含着若干局部最优值和一个全局最优值。在进行应用时，可以有效的利用相关特点进行，特别是应用的寻优期间，每次迭代执行完，人工鱼都将对比自身状态和公告板状态，如自身具有优势，则更新公告板状态，确保公告板为最优状态。 人工鱼群算法已在参数估计、组合优化、前向神经网络优化、电力系统无功优化、输电网规划、边坡稳定、非线性方程求解等方面得到应用，且取得了较好的效果。
1.3 蜂群算法（ABC）
人工蜂群算法（ABC）是一种非数值优化计算方法。人工蜂群算法的思想是：将虚拟蜜蜂群初始时随机分布在解空间中，将食物源的位置抽象成解空间中的点（可行解）。蜂群算法由3个基本要素构成：蜜源、采蜜蜂和待工蜂。在蜜蜂与外部环境的交流中蜜蜂通过自身的反应阀值（threshold）和外界的激励信号（stimulation）来自行安排工作。
1.4 粒子群算法（PSO）
PSO（粒子群算法）是一种新兴的基于群体智能的启发式全局搜索算法，具有易理解、易实现、全局搜索能力强等特点。粒子群算法模拟鸟群的捕食行为，通过群聚而有效的觅食和逃避追捕。在鸟群的捕食过程中，个体之间存在着信息的交换与协作，整个群体中信息是共享，每个个体的行为是建立在群体行为的基础之上。可以设想这样一个场景：一群鸟在随机搜索食物，每只鸟在初始状态下处于随机位置，且朝各个方向随机飞行，在这个区域里只有一块食物，所有的鸟都不知道食物在那里，但随着时间推移，处于随机状态的鸟通过搜寻目前离食物最近的鸟的周围区域，聚集成一个个小的群落，并最终将整个群落聚集在食源的位置。受到这种模型的启示，在PSO算法中，优化问题的解都是被称为“粒子”。通过类似于鸟群捕食的方式，追随当前的最优粒子在解空间中搜索，并最终找到最优解。
2 混合群体智能优化方法
2.1 基于PSO的混合优化算法
传统的粒子群算法在低维空间上，可以快速高效寻找最优解，但随着函数维数的增加，容易陷入局部极值，导致收敛精度低。而混合粒子群算法是在标准粒子群算法中加入进化算法，保证了群体的多样性，快速收敛效果和避免陷入局部极值的能力。混合粒子群算法利用选择机制改进的算法将每个个体的适应度，并与几个其它个体进行比较，记下最差的一个点，通过这种方式排序之后，最高的得分出现在群体最前面，逐步淘汰掉较差的区域，因此可以更加合理地分配有限的资源。在杂交算子改进的PSO中，将粒子群算法与杂交算子的结合，在该种算法运行过程中根据适应度的大小，粒子之间可以两两杂交，这个杂交概率是随机的。经过杂交操作，将随机产生粒子的最新位置。这种杂交操作只改变了粒子的方向，而没有改变粒子的数量，保证群体的多样性，避免陷入局部极值。因此应用了杂交算子的粒子群算法比传统粒子群算法效率更高。
2.2 基于BFO的混合优化算法
BFO（细菌觅食算法）来源于细菌的群体行为特性，是近年来研究提出的一种新的算法。BFO搜索通过群体细菌之间的竞争和协作，实现搜索的优化。关于BFO混合算法目前的研究结果基本是加入PSO的机理来解决函数优化问题，通过对分析各种算子的步长以及细菌的生存期的过滤，从而实现算法性能的提高。近年来，Kim和Abraham又将遗传算法引入BFO，该算法结合了BFO算法中大肠杆菌的觅食机制菌和PSO算法中的鸟类云集模式。基于BFO和PSO提出一种混合优化算法，解决了多模态高维函数的优化，提高了对高维函数优化的收敛速度和局部搜索能力。
2.3 自适应菌群约束优化算法
自适应菌群约束优化算法是基于BFO提出了一种处理约束优化问题新方法。该算法引入Tent混沌方法对符合迁徙条件的细菌进行位置初始化，并加入了基于佳点集的交叉算子，使得迁徙后的新菌群具有随机性的特点，使群体均匀的分布在搜索空间中，有跳出局部最优的可能；同时选择精英细菌作为混沌映射的初始解，趋药性步长的自适应变化使得算法避免了在最优值附近的振荡，并能够在维持菌群总数不变的同时得到质量更优的细菌新个体，扩大精英群体的规模。
3 结束语
由于科学技术不断进步，许多应用领域涉及因素、规模以及难度也越来越高，面对的优化问题日益复杂化，这些常规的优化算法都远不能满足要求。而混合智能优化方法，计算简单，易于实现，能够在复杂的问题中快速有效的得到最优解。鉴于智能算法的混合结构很多，关于群体智能优化算法的混合算法还有待进一步研究。
参考文献
[1]李俊.群体智能融合算法研究及其应用[D].南昌航空大学，2013.
[2]向万里.混合群体智能优化算法及应用研究[D].天津大学，2014.
[3]冯月华，陈州吉.基于群体智能的蚁群算法原理及应用研究[J].兰州文理学院学报（自然科学版），2014，02期.
作者简介
刘利波（1983-），男，河南省济源市人。硕士学位。现为新疆轻工职业技术学院讲师。研究方向计算机软件技术。
作者单位
