基于改进遗传算法的路径选择算法及仿真实现

系统仿真学报 ›› 2016, Vol. 28 ›› Issue (8): 1805-1811.

基于改进遗传算法的路径选择算法及仿真实现

顾键萍¹, 张明敏², 王梅亮¹

1.丽水学院,丽水 323000;
2.浙江大学,杭州 310000

收稿日期:2014-08-30 修回日期:2015-02-01 出版日期:2016-08-08 发布日期:2020-08-17
作者简介:顾键萍(1970-),浙江上虞,硕士,讲师,研究方向为虚拟现实、数字媒体。
基金资助:
2014浙江省科技厅公益技术应用研究(2013C33G2260014)

Improved Genetic Algorithm-based Network Game Path Selection and Simulation

Gu Jianping¹, Zhang Mingmin², Wang Meiliang¹

1. Lishui University, Lishui 323000, China;
2. Zhejiang University, Hangzhou 310000, China

Received:2014-08-30 Revised:2015-02-01 Online:2016-08-08 Published:2020-08-17

摘要/Abstract

摘要： 传统路径最优算法把路径最短作为目标,不考虑网络拥堵和游戏区域人数等实时情况,使得算法存在局限性。根据网络游戏实际情况,提出网络游戏路径选择模型,并用改进的遗传算法仿真实现。对游戏地图与游戏相关数据进行预处理,得到游戏地图各路段实时加权长度值,通过遗传算法进行寻优求解。提出一种基于改进遗传算法的网络游戏路径选择方法,与经典算法Dijkstra相比,有效提高了路径搜索效率。

关键词: 遗传算法, 网络游戏, 路径选择, 建模与仿真

Abstract: Traditional optimal path algorithm only sets the shortest path as the target, and it does not consider the network congestion and the number of users in game area for real-time situation, thus resulting in some limitations. According to the actual circumstance of network game, network game path selection model was proposed, and the improved genetic algorithm was employed for simulation. The method pre-processed the game map to get each road weighted length value for a real-time game map, and optimization solution was obtained through the genetic algorithm. A network game path selection method based on improved genetic algorithm was proposed compared with the classical dijkstra algorithm, effectively improving the efficiency of the path search.

Key words: genetic algorithm, online game, path choice, modeling and simulation

中图分类号:

TP391.9

顾键萍, 张明敏, 王梅亮. 基于改进遗传算法的路径选择算法及仿真实现[J]. 系统仿真学报, 2016, 28(8): 1805-1811.

Gu Jianping, Zhang Mingmin, Wang Meiliang. Improved Genetic Algorithm-based Network Game Path Selection and Simulation[J]. Journal of System Simulation, 2016, 28(8): 1805-1811.

参考文献 13

[1]	Mingliang Xu, Zhigeng Pan, Hongxing Lu, et al.Moving-Target Pursuit Algorithm Using Improved Tracking Strategy[J]. IEEE Transactions on Computational Intelligence and AI in Games (S1943-068X), 2010, 2(1): 27-39.
[2]	Chong Jin Ong.Distance Computation between Smooth Convex Objects[C]// Proceedings of IEEE International Conference on Robotics and Automation, Minnesota, USA. USA: IEEE, 1996: 785-790.
[3]	石祥滨, 赵鑫, 刘芳, 等. MMOG中NPC的路径搜索算法的研究[J]. 小微型计算机系统, 2006, 27(12): 2206-2211.
[4]	钟瑛, 许明. 融合A*和Bresenham的游戏路径规划算法设计与实现[J]. 电子技术与软件工程, 2013 (9): 64-66.
[5]	王树西, 吴政学. 改进的Dijkstra最短路径算法及其应用研究[J]. 计算机科学, 2012, 39(5): 223-228.
[6]	Mark L Psiaki.Block Acquisition of weak GPS signals in a software receiver[C]// The Institute of Navigation, Salt Lake City, USA. USA: IEEE, 2001: 2838-2850.
[7]	侯燕. Steiner树遗传蚁群算法在路径选择中的应用[J]. 微电子学与计算机, 2013, 30(11): 88-92.
[8]	Tsui J B.Fundamentals of Global Positioning System Receivers: A Software Approach[M]. New York, USA: Wiley, 2000.
[9]	王海雄, 郭剑毅, 张月红. 改进遗传算法求解交通最优路径的实现[J]. 昆明理工大学学报(理工版), 2009, 34(4): 42-46.
[10]	Gunes M, Sorges U, Bouazizi I.ARA the Ant Colony based Routing Algorithm for MANETs[C]// International Conference on Parallel Processing Workshop (SICPPW02). Vancouver BC, Canada: IEEE, 2002: 79-85.
[11]	张敏捷, 蔡延光, 宋康, 等. 基于改进遗传算法的路网路径优化方法[J]. 微计算机信息, 2010, 26(2): 226-227.
[12]	张本群. 基于启发式算法的路径规划[J]. 计算机仿真, 2012, 29(10): 341-344.
[13]	邱敏, 王公宝, 张松涛, 等. 一种求解最优路径的改进遗传算法[J]. 计算机与现代化, 2010 (4): 6-8.

[1]	李智杰, 石昊琦, 李昌华, 张颉. 基于改进遗传算法的影像中心布局优化方法[J]. 系统仿真学报, 2022, 34(6): 1173-1184.
[2]	付建林, 丁国富, 张剑, 江海凡, 郭沛佩. 基于响应面和NSGA-II的AGV系统多目标优化配置[J]. 系统仿真学报, 2022, 34(5): 994-1002.
[3]	李锋, 魏莹. 社会学习和参照点效应对企业产品决策的影响[J]. 系统仿真学报, 2022, 34(2): 234-246.
[4]	王语童, 马世伟, 杨元睿, 陈超宇. 多机器人组合最大覆盖面积寻优及预测方法[J]. 系统仿真学报, 2022, 34(1): 86-92.
[5]	樊长佳, 杜炎秋, 梁笛, 胡凯, 黄葭燕. COVID-19期间上海市应急医疗资源配置建模与仿真[J]. 系统仿真学报, 2022, 34(1): 93-103.
[6]	司光亚, 王艳正. 新一代大型计算机兵棋系统面临的挑战与思考[J]. 系统仿真学报, 2021, 33(9): 2010-2016.
[7]	何昕杰, 周少武, 张红强, 吴亮红, 周游. 基于改进遗传算法的四向穿梭车系统订单排序优化[J]. 系统仿真学报, 2021, 33(9): 2166-2179.
[8]	唐婕, 曹瑾鑫. 共享汽车联合调度优化研究[J]. 系统仿真学报, 2021, 33(8): 1959-1968.
[9]	李文翔, 李晔, 董洁霜, 李一鸣. 引入碳交易机制的新能源汽车发展路径研究[J]. 系统仿真学报, 2021, 33(6): 1451-1465.
[10]	王凌, 吴楚格, 范文慧. 边缘计算资源分配与任务调度优化综述[J]. 系统仿真学报, 2021, 33(3): 509-520.
[11]	李锋, 魏莹. 复杂网络对羊群效应现象影响的仿真研究[J]. 系统仿真学报, 2021, 33(3): 539-553.
[12]	陈芮莹, 王承涛, 刘振元. 考虑服务水平的IT运维人员调度的智能遗传算法[J]. 系统仿真学报, 2021, 33(3): 732-744.
[13]	张琪, 曾俊杰, 许凯, 秦龙, 尹全军. 基于机器学习的计算机生成兵力行为建模研究综述[J]. 系统仿真学报, 2021, 33(2): 280-287.
[14]	陆嘉波, 程培星, 黄羿, 姚进强, 杨雪梦, 马新强, 刘勇. 用于时敏目标打击链快速构建的智能方法[J]. 系统仿真学报, 2021, 33(2): 346-357.
[15]	孙国栋, 何其昌. 螺钉机工艺智能化设计与仿真方法研究[J]. 系统仿真学报, 2021, 33(1): 62-73.