人工智能：用于游戏NPC路径规划的改进遗传算法

《人工智能：用于游戏NPC路径规划的改进遗传算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、１１４传感器与微系统（ＴｒａｎｓｄｕｃｅｒａｎｄＭｉｃｒｏｓｙｓｔｅｍＴｅｃｈｎｏｌｏｇｉｅｓ）２０１７年第３６卷第６期殠檸檸檸檸檸殠檸ＤＯＩ：１０．１３８７３／Ｊ．１０００—９７８７（２０１７）０６—０１１４—０５檸殠计檸算与檸测檸试檸檸殠用于游戏ＮＰＣ路径规划的改进遗传算法李井颂１，钱１，３２，３谦，孙铭会（１．昆明理工大学云南省计算机技术应用重点实验室，云南昆明６５０５００；２．吉林大学计算机科学与技术学院，吉林长春１３００１２；３．吉林大学符号计算与知识工程教育部重点实验室，吉林长春１３００１２）摘要：针对游戏

2、非玩家控制（ＮＰＣ）路径规划中传统遗传算法计算速度慢、正确率低等问题，设计了改进型遗传算法。提出了最佳种群规模估计方法，设计了基于精英主义思想的遗传算子。根据游戏地图的特点，引入了基于启发式深度优先搜索的变异操作。与传统遗传算法以及其他学者的改进算法进行了对比实验。实验结果表明：算法能够在保证正确率的前提下，提高计算速度，并且在多目标的环境下同样适用。关键词：人工智能；路径规划；遗传算法；种群规模；精英主义；启发式深度优先搜索中图分类号：ＴＰ１８文献标识码：Ａ文章编号：１０００—９７８７（２０１７）０６—０１１４—０５

3、ＩｍｐｒｏｖｅｄｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｆｏｒｐａｔｈｐｌａｎｎｉｎｇｉｎｇａｍｅｓＮＰＣ１，１，３２，３ＬＩＪｉｎｇｓｏｎｇＱＩＡＮＱｉａｎ，ＳＵＮＭｉｎｇｈｕｉ（１．ＹｕｎｎａｎＫｅｙＬａｂｏｒａｔｏｒｙｏｆＣｏｍｐｕｔｅｒＴｅｃｈｎｏｌｏｇｙＡｐｐｌｉｃａｔｉｏｎｓ，ＫｕｎｍｉｎｇＵｎｉｖｅｒｓｉｔｙｏｆＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，Ｋｕｎｍｉｎｇ６５０５００，Ｃｈｉｎａ；２．ＣｏｌｌｅｇｅｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，ＪｉｌｉｎＵｎｉｖｅｒｓｉｔｙ，Ｃｈａｎ

4、ｇｃｈｕｎ１３００１２，Ｃｈｉｎａ；３．ＫｅｙＬａｂｏｒａｔｏｒｙｏｆＳｙｍｂｏｌｉｃＣｏｍｐｕｔａｔｉｏｎａｎｄＫｎｏｗｌｅｄｇｅＥｎｇｉｎｅｅｒｉｎｇｏｆＭｉｎｉｓｔｒｙｏｆＥｄｕｃａｔｉｏｎ，ＪｉｌｉｎＵｎｉｖｅｒｓｉｔｙ，Ｃｈａｎｇｃｈｕｎ１３００１２，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ：Ｔｏｉｍｐｒｏｖｅｔｈｅｐｅｒｆｏｒｍａｎｃｅｏｆｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｓｆｏｒｐａｔｈｐｌａｎｎｉｎｇｉｎｇａｍｅｓ，ａｎｉｍｐｒｏｖｅｄｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍｉｓｐｒｏｐｏｓｅｄ．Ａｗａｙｔｏｅｓｔｉｍａｔｅｔ

5、ｈｅｏｐｔｉｍａｌｐｏｐｕｌａｔｉｏｎｓｉｚｅｉｓｕｓｅｄ．Ｎｅｗｇｅｎｅｔｉｃｏｐｅｒａｔｏｒｓｂａｓｅｄｏｎｅｌｉｔｉｓｔｓｔｒａｔｅｇｙｉｓｄｅｓｉｇｎｅｄ．Ａｍｕｔａｔｉｏｎｍｅｔｈｏｄｂａｓｅｄｏｎｈｅｕｒｉｓｔｉｃｄｅｐｔｈｆｉｒｓｔｓｅａｒｃｈｉｓｉｎｔｒｏｄｕｃｅｄ．Ｔｈｅｐｒｏｐｏｓｅｄａｌｇｏｒｉｔｈｍｉｓｃｏｍｐａｒｅｄｗｉｔｈｔｈｅｔｒａｄｉｔｉｏｎａｌｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍａｎｄｔｈｅｉｍｐｒｏｖｅｄａｌｇｏｒｉｔｈｍｓｐｒｏｐｏｓｅｄｂｙｏｔｈｅｒｒｅｓｅａｒｃｈｅｒｓｔｏｓｈｏｗ

6、ｔｈｅｖａｌｉｄｉｔｙｏｆｔｈｅａｌｇｏｒｉｔｈｍ．Ｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｐｒｏｖｅｔｈａｔｔｈｅｐｒｏｐｏｓｅｄａｌｇｏｒｉｔｈｍｃａｎｓｈｏｒｔｅｎｔｈｅｒｕｎｎｉｎｇｓｐｅｅｄｏｆｔｈｅａｌｇｏｒｉｔｈｍｗｈｉｌｅａｓｓｕｒｉｎｇｓｕｃｃｅｓｓｒａｔｅａｎｄｉｔｉｓａｌｓｏｅｆｆｅｃｔｉｖｅｉｎｍｕｌｔｉｏｂｊｅｃｔｉｖｅｅｎｖｉｒｏｎｍｅｎｔｃｏｎｄｉｔｉｏｎ．Ｋｅｙｗｏｒｄｓ：ａｒｔｉｆｉｃｉａｌｉｎｔｅｌｌｉｇｅｎｃｅ（ＡＩ）；ｐａｔｈｐｌａｎｎｉｎｇ；ｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ；ｐｏ

7、ｐｕｌａｔｉｏｎｓｉｚｅ；ｅｌｉｔｉｓｔｓｔｒａｔｅｇｙ；ｈｅｕｒｉｓｔｉｃｄｅｐｔｈｆｉｒｓｔｓｅａｒｃｈ０引言大的交叉率与变异率来避免陷入局部最优解。此做法虽然计算出游戏非玩家控制（ＮＰＣ）角色从起点到目标点的提高了搜索成功率，但是增加了运行时间。孙宝林［７］和李最短路径是游戏开发中最基本的问题。游戏ＮＰＣ属于智擎［８］主要对遗传算法中的传统随机变异进行了改进，使变能Ａｇｅｎｔ的一种，研究出快速且高效的寻径方法，而且对于异能够朝着最优解的方向进行，虽然缩短了求得最优解所车辆路径规划［１］和机器人路径规划［２］以及最

8、短路径路由需的进化代数，但是计算速度并没有明显提高。问题［３］都有重要的借鉴意义。游戏地图一般存在多条从在遗传算法中，种群规模越大，全局搜索能力就越强，起点栅格到终点栅格的最短路径。而遗传算法由于其并行但是速度也就越慢［９］，而遗传进化代数与网络规模相关性搜索方式，每次运行时一般可以得到不同的路径，被广泛用并不大［１