 Computer Science and Application 计算机科学与应用, 2012, 2, 96-100 http://dx.doi.org/10.12677/csa.2012.22018 Published Online June 2012 (http://www.hanspub.org/journal/csa) An Modified Artificial Fish Swarm Algorithm for the Optimal Routing Problem* Hang Zhang, Qingbo Yang School of Information Science & Engineering, Central South University, Changsha Email: qtfj2005@163.com Received: Mar. 11th, 2012; revised: Mar. 29th, 2012; accepted: Apr. 9th, 2012 Abstract: Search for the shortest pa th in transportation network is one of the most i mportant problem of ITS. This pa- per analyzes the basic Artificial Fish Swarm Algorithm and presents an improved algorithm on initialize popu lation an d behavior. The results of the experimentation proved that the improved algorithm could find the shortest path more ac- curately and quickly than the b a sic algorithm, and it is feasible. Keywords: Transportation Network Analysis; Shortest Path; Artificial Fish Swarm Algorithm 基于改进人工鱼群算法的最短路径问题研究* 张 航，杨清波 中南大学信息科学与工程学院，长沙 Email: qtfj2005@163.com 收稿日期：2012 年3月11 日；修回日期：2012 年3月29 日；录用日期：2012 年4月9日 摘 要：最短路径问题是交通网络分析中的一个重要问题。本文在分析基本鱼群算法在求解交通网络两点之间 最短路径的基础上，针对其准确性和处理时间的不足，对人工鱼初值和行为进行了改进，提出了改进的人工鱼 群算法。仿真实验表明提出的方法较原始鱼群算法能更准确、更快速地找到交通路网中任意两点间的最短路径。 关键词：交通网络分析；最短路径；人工鱼群算法 1. 引言 最短路径问题是交通网络分析中的一个重要问 题，也是一个研究热点[1]。它是资源分配、路线设计 及分析等优化问题的基础，具有重要理论意义和实际 应用价值。有许多研究者曾对最短路径算法进行了大 量的研究，并取得了很大的进展，提出了很多解决这 类问题的方法。其中传统的算法有，Dijkstra 算法、 A*算法及其改进算法等等；还有近几十年来，通过模 拟或揭示某些自然现象而产生了一些新颖的启发式 智能算法，如遗传算法，模拟退火算法，禁忌搜索算 法、蚁群算法等，但传统算法内存占用空间大，运算 速度慢，新的智能算法也存在收敛速度慢，容易陷入 局部最优解的问题。鱼群算法作为新近开发的一种优 化算法在运算速度、收敛速度方面有其独特的优势， 本文在分析基本鱼群算法在求解交通网络两点之间 最短路径的基础上，针对其准确性和处理时间的不 足，对人工鱼初值和行为进行了改进，提出了改进的 人工鱼群算法。 2. 交通最短路径问题描述 城市道路网有道路路线、交叉路口等物理属性， 同时也具有路线长度、通行时间、路况等各种其它逻 *资助信息：2010 年中南大学硕士研究生学位论文创新资助项目(No. 2010ssxt209)国家自然基金，No. 50808025。 Copyright © 2012 Hanspub 96  基于改进人工鱼群算法的最短路径问题研究 辑属性。用节点来表示城市道路网中的交叉路口，连 接两节点之间的边表示道路路线，并将路线的长度、 通行时间，路况等属性表示为该边的权值，那么就可 以把道路网络抽象为一个带权有向图。 给定一个带权有向图 G为二元组 ,GVE ,2,, 9} ， 其中 V是包含 n个节点的集合，如图 1中的{1 ， E是包含 h条边(弧段)的集合，如图1中的 ， {1,2,1,48,9},ij 是 1。 6,9 ，权 是E中从节点i 至j的边，如图 1中1,ij w边非负权 值，图 1中边 1,值12 wS，T分别为 V 中的起始节点和目标节点，则最短路径问题就是指在 带权有向图 G中，寻找从指定起始节点到目标节点的 一条具有权值总和最小的路径[2]。如图 1中节点 1到 节点 9存在最短路径 1,2, 值总和为 4。 2 2的权 3, ，,ij的 设 3. 改进人工鱼群算法实现最短路径问题 3.1. 原始人工鱼群算法 3.1.1. 算法原理[3] 人工鱼群算法(Artificial Fish Swarm Algorithm， AFSA)是一种基于群体智能的演化计算技术。该算法 模拟鱼群行为，利用鱼的觅食、聚群和追尾行为，从 构造单条鱼的底层行为做起，通过鱼群中各个个体的 局部寻优行为，最终达到以群体合作实现全局最优。 AFSA 具有概念简单、实现容易、灵活 性高、鲁棒 性好、通用性强、寻优速度 快等特点[4]，目前其已被推 广用于连续性优化、组合优化、时变系统的在线辨识、 鲁棒 PID 的参数设定、优化前向神经网络、电力 系统 无功优化、多用户检测器、信息检索和油田多级站定 位等问题(领域)的求解计算，并取得较好效果[5]。 1 23 4 56 7 89 1 1 1 1 2 43 1 4 3 2 2 Figu re 1. Net wo rk wi t h we ig h t s 图1. 带权网络 由于 AFSA 是新 智能优化算法，属 于连续性 3.1.2. 模型的相关定义 表示为 近发展起来的 算法，不能直接用于离散组合优化问题的求 解，文献[6]作者通过重新定义AFSA 的距离、邻域等 概念，首次把 AFSA 应用于组合优化问题的求解。本 文借此方法，将最短路径问题转化为对所有节点的一 个组合优化问题，目标是找到一种节点组合使得从起 始节点到目标节点的路径最短。 人工鱼个体的状态可 12 ,,, n X xx x向 量，其中 (1,2,) i x in 为欲寻优的 前 所在位置 示为 Yfx，其中 Y为目标 函数值；人工鱼个体之间的 变量；人工鱼当 距离表示为 的食物浓度表 ,ijij dXX，Visual 表示人工鱼的感知距 的 ，本文中使用的是随机步长 rand step 离；step 表示人工鱼移动 步长 ； (0 < < 1)表示拥挤度因子；另外，本 体之 的距离为不用试属于文定义人工鱼个间i X 和 j X 的元素的个数： ,ijijj i dXXXX (1) 定义 n条鱼的中心位置为 j 11 nn ci ij ji X kX X (2) 设鱼 朝鱼 j X i X 方向移动一个随机步长 rand() step ，移动后 j X 的新状态为： rand() step ;1,, ji ji ji Xk Xk XkXkk Xk Xkn (3) 3.1.3. 行为描述 人工鱼当前状态为觅食行为：设 i X ，在其感知范 围内随机选择—个状态 j X ，在求极小值问题中，如 果 ij f XfX，则 向 j X 方向前进—步；反之，再 重新随机选择状态 j X ，判断是否满足前进条件；反 复几次后，如果仍不满足前进条件，则随机移动一步。 聚群行为：设人工鱼当前状态为 i X ，探索当前邻 域内即(Visual ij d )的伙伴数目 f n及中心位置 c X ， 如果 cf i Yn Y ，表明伙 ，则朝伙伴的中 伴中心有 的食物并 太拥挤 心位置方向前进一步；否则执 行觅食行为。 较多 且不 Copyright © 2012 Hanspub 97  基于改进人工鱼群算法的最短路径问题研究 追尾行为： i X 设人工鱼当前状态为 ，探索当前邻 域内即(Visual ij d)的伙伴中 j Y为最大的伙伴 j X ，如 果cf Yn i Y ，表明伙伴 j X 的状态具有较高的食物 浓度并且其周围不太拥挤，则朝伙伴 j X 的方向前进 一步；否则执行觅食行为。如果 f n = 也执行觅食 行为。 公告 0， 板：公告板用来记录最优人工鱼个体的状 态。 性质，对人工鱼 当前 针对原始人工鱼群算法初始鱼群覆盖空间的不 确定 始鱼群的个体分布状况直接影 响算 各人工鱼个体在寻优过程中，每次行动完毕就检 验自身状态与公告板的状态，如果自身状态优于公告 板状态，就将公告板的状态改写为自身状态，这样就 使公告板记录下历史最优的状态。 行为选择：根据所要解决的问题 所处的环境进行评价，从而选择一种行为。如对 于求取极大值的问题，最简单的评估方法可以用试探 法，就是模拟执行聚群、追尾等行为，然后评价行动 后的值，选择其中的最大者来实际执行，缺省的行为 方式为觅食行为。 3.2. 改进人工鱼群算法 性和收敛速度慢等问题[5]，对算法进行改进。 1) 初始化操作 人工鱼群算法初 法的全局收敛性能。由于原始鱼群算法的初始鱼 群是随机分布的，其覆盖空间具有很大的不确定性， 如果初始鱼群空间不包含全局最优解，而鱼群行为算 子又不能在有限次数的行为操作内将覆盖空间扩延 到全局最优解所在的区域，那么过早收敛就不可避 免。因此本文采用网格化鱼群，使初始人工鱼群在海 域中均匀分布，有利于人工鱼更快的在全局范围内寻 优。数学表达式如式(4)所示： MaxDMin Min 1 i kDk X kD ki n (4) 式中： i X k 表示第条人工鱼的第 k个分 行为改 保证鱼群算法的稳定性，鱼 1, ,ii n ax k分别为量， MinDk，MDk的下界与上界。 2) 进 ① 觅食行为： 觅食操作中，为了 i X 游动到新状态 j X ，必须使 j X 在问题解域的范围内 即随机游动一步 超出范围 由式(5)进行越界回折： 2Max, j DkXk ， Max 2Min, Min j j j j X kD k Xk DkXk X kD k (5) 若觅食执行 trynumber次操作失败，进行全局寻优操 作一次，即 inext rand() globle i XX (此处 globle 为寻 优参数的定 作结果劣于当前 状态，则人工鱼静止不动。这个操作的增加，既有利 于使人工鱼跳出局部最优，又保留了最优个体，避免 了人工鱼的退化。 ② 追尾和聚群 义域)，若此次全局寻优操 行为： 始的随机游动一步改为 由S 机移动 x 在鱼群行为描述中，将原 决定前进位置。即将式(3)中的 rand() step改为由 S代替，S由式(6)决定，其含义为若随 一步的 食物浓度大于直接移动到伙伴中心的食物浓度，则随 机前进一步，否则直接移动到伙伴中心位置。S的引 入提高了算法的搜索速度。 rand() step,F step step 11 , c c X nn cij ij ji F S X XXF F (6) 与原始鱼群算法相同，算法中需要设立一个公告 板， 路径问题 均匀 分布 用来记录最优人工鱼的状态和该人工鱼位置的食 物浓度。各人工鱼个体在寻优过程中，每次行动完毕 就检验自身状态与公告板状态，如果自身状态优于公 告板状态，就用自身状态改写公告板状态，这样就使 公告板记录下历史最优的状态。 3.3. 改进人工鱼群算法实现最短 算法思想：算法需要初始化一组鱼群，使之 ，将待求解最短路径的节点作为参数 12 ,,, n X xx x看成是一片水域中的个体 值 人工鱼， 对应的总路径的权 F X代表人工鱼个体所在位置 的食物浓度。根据路径 网络，利用改进后的追尾、 聚群和觅食行为，通过迭代寻找使得食物浓度最大的 权值 F X，由求得的最短路径 12 ,,, n X xx x。 法步骤： 算 参数值，设定人工鱼群规模 Fish Num 1) 初始化各 ber，拥挤度因子 ，最多尝试次数 TryNumber， 最大迭代次数 ，步 长，停滞参数 (迭Max_gen step tag 若 ， Copyright © 2012 Hanspub 98  基于改进人工鱼群算法的最短路径问题研究 代过程中，若迭代 tag 次最优值不变，提前终止迭 代)； 2) 初始化鱼群给定二元图的节点数 n作为人，将 工鱼个体的维数，第一个元素为起始节点i，其余元 素为节点随机产生，且不重复，检测终点 j，令元素j 之后的元素都记为 0，然后去除掉相邻元素组成路径 不属于二元组中边的集合 E的个体，使之均匀分布， 并依此计算各条鱼之间的平均距离作为视野 Vision ； 计算各人工鱼食物浓度 F，即相邻元素组成的 值总和，取最大者 max 边的权 F 。进入公告板，并保存其状态； 3) 各人工鱼分别执行改进后的追尾、聚群和觅食 行为 根据迭代次数 ，停 滞参 续 4. 算法仿真及结果分析 本文利用图 2向带权网络来进行算法的 分析 。然后评价行动后的 F值；如果优于公告板状态， 以自身状态取代之； 4) 判断结束条件： Max _ gen 结束，否 数tag 是否满足条件，若满足条件 则转 步骤 3继 。 所示的无 与仿真，可将其视为弧段正反向权值相等的有向 带权网络，即图 2中边 1, 2的权值 12 w与边2,1 的权值 21 w相等，均为 1以较便 的完 路径问题 研究。该网络与我们当前实际的城市交通 网络较为接近。各路段的权值为走完该路段所需的时 间，单位为(min)，各路段的权值均已标示在路段上， 此处需要寻找一条从节点l到节点 30 的最短路径。 在人工鱼优化算法中，决定人工鱼群算法收敛 ，如此可捷 成最短 的 1 7 13 19 25 2 8 14 20 26 4 10 16 22 28 3 9 15 21 27 5 11 17 23 29 6 12 18 24 30 1111 1 2333 3 2444 2 2 3333 1111 1 1 221 2 442 2 44 2 442 2 44 2 222 2 2 Figure 2.ed network with weights 无向带权网络 特性的参 为了提 Undirect 图2. 数主要是视 、范围和步长等参数。野 高收敛速度，算法引入停滞参数因子 tag (即相邻 tag 次迭代结果相同，则结束本次迭代)，通 实验发现， 设置参数不同会导致人工鱼算法收敛特性不同。利用 Matlab7.0 进行仿真，经过多次实验，算法的各参数设 置为：FishNumber 25 过 ，0.8 ，TryNumber 20 ， Max _ gen100 ，stepVision 4 ， 。 法有较好 的结果，能准确快速的找到最 径： 1—7—13 —19—25—26—27 —28—29 tag 此时 5，取 算 各条 鱼之间的平均距离作为视野 Vision 短路 —30 总权 值： 他算法进行了测试，在满足结果精 度要 法均可在短时间内求得 最短 算法与改进人工鱼群算 法的收敛 ts 表1. 多种算法仿真结果对比 收敛速度(ms) 11 min。 本人也使用其 求的前提下，对 Dijkstra 算法[7]，蚁群算法[8]，原 始人工鱼群算法，改进人工鱼群算法的收敛速度进行 对比，结果如下表 1。 由结果可以看出，各种算 路径，且改进的鱼群算法在收敛速度上还是优于 前三种算法的收敛速度的。 图3对比了原始人工鱼群 曲线，从图中可知，改进人工鱼群算法比原 始人工鱼群算法收敛速度更快，更准确。 Table 1. All the algorithms simulation resul 最短路径权值(min) Dijkstra算法 11 2160 蚁群算法 11 760 原始人工鱼群算法 11 640 改进人工鱼群算法 11 380 Figure 3. The simulation results comparison 图3. 仿真结果对比 Copyright © 2012 Hanspub 99  基于改进人工鱼群算法的最短路径问题研究 Copyright © 2012 Hanspub 100 5. 结语 最短路径问题转化为组合优化问题，又 据人工鱼算法搜索的特点，对人工鱼初值和行为进行 了改 参考文献 (References) anning and user interface for an . Kang and H. Miyagi. An optimal . 一种基于动物自治体的寻优模式: 优化 ni. Fuzzy clus- using the he research and emulation of traffic opti- 本文将根 r 进，并应用这一改进人工鱼群算法解决了这一问 题。实验证明，改进后的算法收敛速度更快，结果更 稳定。本文算法仅使用了目标问题的适应值，对搜索 空间有一定的自适应能力，多条人工鱼个体并行的进 行搜索，具有较高的寻优效率，随着工作状况或其它 因素的变更造成极值点的漂移，本算法具有较快跟踪 变化的能力，应用于最优路径问题上十分合适。 [1] V. Di Lecce, A. Amato. Route pl advanced intelligent transport system. Intelligent Transport Sys- tems, 2011, 5(3): 149-158. [2] Y. Matsuda, M. Naka mura, D outing problem for sightseeing with fuzzy time-varying weights. IEEE International Conference on Systems, Man and Cybernet- ics, 2004, 4: 3665-3669. [3] 李晓磊, 邵之江, 钱积新 鱼群算法[J]. 系统工程理论与实践, 2002, 22(11): 32-38. [4] 方金城, 张岐山. 配送中心配送决策问题及其鱼群算法 求解[J]. 计算机应用, 2011, 34(5): 1652-1655. [5] S. He, N. Belacel, H. Hamam and Y. Bouslima tering with improved artificial fish swarm algorithm. Computa- tional Sciences and Optimization (CSO), 2009, 2(1): 317-321. [6] 李晓磊, 路飞, 田国会等. 组合优化问题的人工鱼群算法应 用[J]. 山东大学学报: 工学版, 2004, 34(5): 64-67. [7] H. Kang, B. Lee and K. Kim. Path planning algorithm particle swarm optimization and the improved Dijkstra algo- rithm. Computational Intelligence and Industrial Application, 2008, 2: 1002-1004, 19-20. [8] H. Wang, C. Q. Ma. T mal routing problem based on ant colony algorithm. Computa- tional Intelligence and Software Engineering (CISE), 11-13 De- cember 2009: 1-5, 11-13. |