自适应视野的人工鱼群算法求解最短路径问题

doi:10.3969/j.issn.1000-436x.2014.01.001

摘要/Abstract

摘要：

针对基本人工鱼群算法的参数视野固定不变导致算法后期收敛速度慢、运算量大、易陷入局部最优等问题，提出自适应视野的改进人工鱼群算法。改进后的算法只对人工鱼的觅食行为的视野进行调整，使其随着算法的迭代次数的增加而逐渐减小，但当视野小于初始值的一半时，停止减小，使其等于初始值的一半。将提出的改进型人工鱼群算法应用到求解基于道路网络的最短路径问题中，并通过实验证明了改进后的人工鱼群算法比基本人工鱼群算法及蚁群优化算法收敛速度快、计算量小，而且更加准确和稳定。

关键词: 最短路径, 人工鱼群算法, 自适应视野, 蚁群优化算法

Abstract:

To solve basic artificial fish-swarm algorithm(AFSA)’s drawbacks of low convergence rate in the latter stage,a large amount of computation and easiness of trapping in local optimal solution,caused by the constant vision of the artificial fish,an improved artificial fish-swarm algorithm based on adaptive vision(AVAFSA) was proposed.The improved algorithm only adjusted the vision of the preying behavior of artificial fish to make the vision gradually decrease with the increase of the number of iterations of the algorithm.When the value became less than half the initial value,it made the value be equal to half the initial value.The proposed improved artificial fish swarm algorithm was applied to the static shortest path problem based on road network to provide customers with the best path.Simulation results depict the improved algorithm has higher convergence rate,a smaller amount of calculation,and is more accurate and stable than the basic AFSA and ant colony optimization(ACO).

Key words: shortest path, artificial-fish swarm algorithm, adaptive vision, ant colony optimization

马宪民,刘妮. 自适应视野的人工鱼群算法求解最短路径问题[J]. 通信学报, 2014, 35(1): 1-6.

Xian-min MA,IUN L. Improved artificial fish-swarm algorithm based on adaptive vision for solving the shortest path problem[J]. Journal on Communications, 2014, 35(1): 1-6.

图/表 7

图1

图2

图3

表1

图4

图5

表2

参考文献 10

[1]	孙中华 . GIS路径寻优中的蚁群算法研究[D]. 南京:南京理工大学, 2009. SUN Z H . Research on Ant Colony Algorithm in GIS Path Optimiza-tion[D]. Nanjing:Nanjing University of Science and Technology, 2009.
[2]	谭国真, 高文 . 时间依赖网络最小时间路径算法[J]. 计算机学报, 2002,25(2): 165-172. TAN G Z , GAO W . The minimum time path algorithm of the time-dependent network[J]. Chinese Journal of Computers, 2002,25(2): 165-172.
[3]	王海梅 . 基于 GIS 的最优路径算法研究与实现[D]. 南京:南京理工大学, 2008. WANG H M . Research and Implementation of the Optimal Path Algo-rithm Based on the GIS[D]. Nanjing:Nanjing University of Science and Technology, 2008.
[4]	甘荣伟 . 蚁群优化算法及其应用研究[D]. 广州:中山大学, 2009. GAN R W . Research on Ant Colony Optimization and Its Application[D]. Guangzhou:Sun Yat-sen University, 2009.
[5]	张学敏, 张航 . 基于改进蚁群算法的最短路径问题研究[J]. 自动化技术与应用, 2009,28(6): 4-7. ZHANG X M , ZHANG H . Research on the shortest path problem based on an improved ant colony algorithm[J]. Automation Technol-ogy and Application, 2009,28(6): 4-7.
[6]	潘海珠, 杜晓昕, 王波 . 基于人工鱼群的交通诱导系统最优查询研究[J]. 齐齐哈尔大学学报, 2012,28(5): 6-9. PAN H Z , DU X X , WANG B . Research on the optimal query research of traffic guidance system based on artificial fish-swarm algorithm[J]. Journal of Qiqihar University, 2012,28(5): 6-9.
[7]	郑根让 . 基于混合人工鱼群算法车辆拥堵调度方案[J]. 计算机仿真, 2012,29(6): 328-331. ZHEN G R . Vehicle congestion scheduling scheme based on a mixed artificial fish-swarm algorithm[J]. Computer Simulation, 2012,29(6): 328-331.
[8]	李晓磊, 邵之江, 钱积新 . 一种基于动物自治体的寻优模式：鱼群算法[J]. 系统工程理论与实践, 2002,22(11): 32-38. LI X L , SHAO Z J , QIAN J X . An optimization mode based on Autonomous:fish-swarm algorithm[J]. Systems Engineering Theory and Practice, 2002,22(11): 32-38.
[9]	李晓磊 . 一种新型的智能优化方法—人工鱼群算法[D]. 杭州:浙江大学, 2003. LI X L . A New Type of Intelligent Optimization Method:Artificial Fish-swarm Algorithm[D]. Hangzhou:Zhejiang University, 2003.
[10]	江铭炎, 袁东风 . 人工鱼群算法及其应用[M]. 北京: 科学出版社, 2012. JIANG M Y , YUAN D F . Artificial Fish-swarm Algorithm and Its Ap-plication[M]. Beijing: Science PressPress, 2012.

序号		ACO			AFSA			AV AFSA
序号	BEST_GEN	BEST	TIME/s	BEST_GEN	BEST	TIME/s	BEST_GEN	BEST	TIME/s
1	3	8	1.793 8	5	8	5.413 8	1	8	4.113
2	4	8	1.816 2	5	8	5.389 3	3	8	4.266 2
3	2	8	1.838 3	5	8	5.324 9	5	8	4.423 8
4	2	8	1.866 8	6	8	5.983 7	2	8	4.101 3
5	2	8	1.847 4	4	8	5.321 6	4	8	4.068 4
平均	2.6		1.832 5	5		5.486 7	3		4.194 5
成功率		100%			100%			100%

序号		ACO			AFSA			AV AFSA
序号	BEST_GEN	BEST	TIME/s	BEST_GEN	BEST	TIME/s	BEST_GEN	BEST	TIME/s
1	22	28	5.893 9	21	19	4.441	10	19	3.839 2
2	1	20	5.884 2	61	19	4.464 9	30	19	3.759 6
3	18	20	5.953 6	71	20	4.490 5	49	19	3.849 5
4	9	20	5.824 5	188	19	4.414 4	12	19	3.813 1
5	5	22	5.869	82	19	4.443 5	32	19	3.825 5
平均	11		5.885	84.6		4.450 9	26.6		3.817 4
成功率		0%			80%			100%

[1]	丛玉良, 孙闻晞, 薛科, 钱志鸿, 陈绵书. 基于改进的混合遗传算法的车联网任务卸载策略研究[J]. 通信学报, 2022, 43(10): 77-85.
[2]	何元智, 彭聪, 于季弘, 刘韵. 面向密集多波束组网的卫星通信系统资源调度算法[J]. 通信学报, 2021, 42(4): 109-118.
[3]	卢毅,徐梦颖,周杰. 基于改进的免疫克隆蛙跳算法的多约束QoS路由优化研究[J]. 通信学报, 2020, 41(5): 141-149.
[4]	顾秋阳, 琚春华, 吴功兴. 基于子图演化与改进蚁群优化算法的社交网络链路预测方法[J]. 通信学报, 2020, 41(12): 21-35.
[5]	兰巨龙,金子晋,孙鹏浩,江逸茗,王月. 基于可靠性的服务功能链构建算法[J]. 通信学报, 2019, 40(1): 64-70.
[6]	魏振春,孙仁浩,吕增威,韩江洪,石雷,徐俊逸. 联合充电和数据收集的WCE多目标路径规划算法[J]. 通信学报, 2018, 39(10): 22-33.
[7]	胡欣,宋航宇,刘帅军,李秀华,王卫东,汪春霆. 基于时间演进图的LEO星间切换实时预测及更新方法[J]. 通信学报, 2018, 39(10): 43-51.
[8]	王鹏,李红艳,张焘,李朋云. 基于时间聚合图的DTN网络最短时延路由算法[J]. 通信学报, 2017, 38(Z1): 1-8.
[9]	陈业斌,李颖,郑啸,陈涛. 关于有向环网平均直径的研究[J]. 通信学报, 2013, 34(2): 138-146.
[10]	马炫,刘庆. 基于人工鱼群算法的多播树演化寻优[J]. 通信学报, 2012, 33(9): 1-7.
[11]	唐伟,郭伟. 无线传感器网络中能量高效的基站位置优选算法[J]. 通信学报, 2010, 31(9): 1-7.
[12]	王兴伟,秦培玉,郭磊,黄敏,蒋定德. 基于混合人工鱼群的ABC支持型切换决策机制[J]. 通信学报, 2010, 31(12): 72-81.
[13]	聂仁灿,周冬明,赵东风,谭颖芳. 竞争型脉冲耦合神经网络及用于多约束QoS路由求解[J]. 通信学报, 2010, 31(1): 65-72.
[14]	饶育萍,林竞羽,侯德亭. 基于最短路径数的网络抗毁评价方法[J]. 通信学报, 2009, 30(4): 113-117.
[15]	李蔚,黄德修,刘德明,何军. 光网络中一种快速动态负荷均衡的波长路由算法[J]. 通信学报, 2005, 26(9): 60-67.