| 游戏引擎最短路径搜索优化遗传算法设计 |
| |
| 引用本文： | 黎忠文,覃志东,王全宇,倪仲余. 游戏引擎最短路径搜索优化遗传算法设计[J]. 计算机应用研究, 2014, 31(1): 76-79 |
| |
| 作者姓名： | 黎忠文 覃志东 王全宇 倪仲余 |
| |
| 作者单位： | 1. 成都大学 信息科学与技术学院, 成都 610106; 2. 东华大学 计算机科学与技术学院, 上海 201620; 3. 西华大学 数学与计算机学院, 成都 610039 |
| |
| 基金项目： | 国家自然科学基金资助项目（60903160）; 中央高校基金资助项目（11D11209）; 四川省科技支撑计划资助项目（2013GZ0016）; 四川省教育厅科技资助项目（12ZB176, 13ZA0296） |
| |
| 摘 要： | 为满足游戏地图中最短路径搜索求解, 提出了一种优化的自适应遗传算法。该算法采用与游戏地图中节点数和弧段数相关联的节点复杂度算子, 结合种群的整体情况和进化潜力来设定自适应遗传算法的交叉率和变异率。实验表明, 该算法避免了搜索结果陷入局部最优解, 确保最短路径的搜索成功率及提高搜索速度, 在游戏引擎设计中具有一定的实用价值。
|
| 关 键 词： | 遗传算法 最短路径 节点复杂度算子 交叉率 地图 |
Optimized genetic algorithm for shortest-path problem in game engine |
| |
| LI Zhong-wen,QIN Zhi-dong,WANG Quan-yu,NI Zhong-yu. Optimized genetic algorithm for shortest-path problem in game engine[J]. Application Research of Computers, 2014, 31(1): 76-79 |
| |
| Authors: | LI Zhong-wen QIN Zhi-dong WANG Quan-yu NI Zhong-yu |
| |
| Affiliation: | 1. School of Information Science & Technology, Chengdu University, Chengdu 610106, China; 2. School of Computer Science & Technology, Donghua University, Shanghai 201620, China; 3. School of Mathematics & Computer Engineering, Xihua University, Chengdu 610039, China |
| |
| Abstract: | In order to meet the shortest-path searching in game map, this paper presented an optimized adaptive genetic algorithm. It used the environment operator which was associated with the number of nodes and arcs of the graph to set the crossover probability and the mutation probability considering the whole population distribution and evolutionary potential. Experiments show that the algorithm can avoid falling into local optimal solutions, ensure the search success rate, and improve the search speed. It provides some valuable work in game engine designing. |
| |
| Keywords: | genetic algorithm shortest path node complexity operator crossover probability map |
|
| 点击此处可从《计算机应用研究》浏览原始摘要信息 |
|
点击此处可从《计算机应用研究》下载全文 |
|
