游戏引擎最短路径搜索优化遗传算法设计  

Optimized genetic algorithm for shortest-path problem in game engine

作　　者：黎忠文[1] 覃志东[2] 王全宇[2] 倪仲余 

机构地区：[1]成都大学信息科学与技术学院,成都610106 [2]东华大学计算机科学与技术学院,上海201620 [3]西华大学数学与计算机学院,成都610039

出　　处：《计算机应用研究》2014年第1期76-79,共4页Application Research of Computers

基　　金：国家自然科学基金资助项目(60903160);中央高校基金资助项目(11D11209);四川省科技支撑计划资助项目(2013GZ0016);四川省教育厅科技资助项目(12ZB176;13ZA0296)

摘　　要：为满足游戏地图中最短路径搜索求解,提出了一种优化的自适应遗传算法。该算法采用与游戏地图中节点数和弧段数相关联的节点复杂度算子,结合种群的整体情况和进化潜力来设定自适应遗传算法的交叉率和变异率。实验表明,该算法避免了搜索结果陷入局部最优解,确保最短路径的搜索成功率及提高搜索速度,在游戏引擎设计中具有一定的实用价值。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.

关 键 词：遗传算法 最短路径 节点复杂度算子 交叉率 地图 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]