基于多Agent遗传算法求解迷宫游戏.pdf

《基于多Agent遗传算法求解迷宫游戏.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第27卷第3期北京建筑工程学院学报Vo1．27No．32011年9月JournalofBeijingUniversityofCivilEngineeringandArchitectureSep．201l文章编号：1004—6011(2011)03—0039—05基于多Agent遗传算法求解迷宫游戏李少保，赵春晓(北京建筑工程学院计算机教学与网络信息部，北京100044)摘要：游戏设计的实质是设计一些相互关联的游戏规则．通过分析迷宫游戏元素之间的关系，抽象制定出一套游戏规则，并在此基础上，提出了一种以寻路个体为单个智能体的多Age

2、nt遗传算法．通过C++进行模拟仿真，实验结果验证了所提优化算法的合理性；与传统的遗传算法相比，此算法在避免早熟的同时有很快的全局收敛性．关键词：迷宫游戏；游戏规则；多Agent；遗传算法中图分类号：TP18文献标志码：ASolutionfortheMazeGameBasedonMulti-AgentGeneticAlgorithmLiShaobao，ZhaoChunxiao(DepartmentofComputerTeachingandNetworkInformation，BUCEABeijing100044)Abstract

3、：Theessenceofgamedesignistodesignsomerelatedrulesofthegame．Onthebasisoftheanalysisofrelationshipsamongvariouselementsinthemazegame，asetofrulesofthegameisworkedoutabstractlyinthepaper．Thenamulti—agentgeneticalgorithm，inwhichtheindividualoffindingthemaze’Spathisasanage

4、nt．isproposed．AtlastitissimulatedbyC++andcomparedwiththetraditionalgeneticalgorithm．Thesimulationresultsindicatethattheproposedoptimizationmodelisreasonableandthisalgorithmcanavoidprecociousphenomenaandhavequickerconvergencerateandbetterglobalastringency．，Keywords：ma

5、zegame；gamerules；multi—agent；geneticalgorithm游戏是按照一定规则进行的娱乐行为．一个游决这个问题上，各国学者做了很多研究，其中也包括戏在进行的过程中，所有玩家都必须遵守游戏规则．了遗传算法．没有游戏规则的游戏是不存在的．近年来，越来越遗传算法是由Holland提出的一种模拟生物遗多的游戏采用人工智能技术设计与玩家对抗的智能传进化机制的全局搜索算法．遗传算法简单通用，AI角色，以此提高游戏的可玩性和吸引众多的游戏不依赖表达形式，有很强的并行性和鲁棒性，并且同玩家．路径搜索是在给定的地图中

6、寻找一条从起点求解问题的其他启发式算法有较好的兼容性，因此到终点的最优或次最优路径．它通常是游戏人工智近年来在各个领域得到了广泛的研究和应用．但是能中一块神圣的基石．以迷宫或地形遍历为主体的传统的遗传算法存在全局收敛速度慢，易于早熟等2D(或2．5D)游戏主要使用路径搜索算法．在3D缺点，难以在合理的时间内找到满意解，尤其当游戏FPS类型的游戏中智能AI角色也非常依赖路径搜问题复杂、角色数量和活动空间增加时，这些弊病就索在环境中进行进攻和自我防御的移动．因此在解更加明显．实践表明仅使用遗传算法为代表的进化收稿日期：2011—07

7、—28作者简介：李少保(1984一)，男，硕士研究生，研究方向：人工智能北京建筑工程学院学报算法来模拟生物的智能远远不够，还必须更加深层1．1游戏规则的设计次地挖掘与利用生物的智能资源．在复杂性科学针对迷宫，我们设计一套规则来控制Agent的中，多Agent(MAS)技术已经成为人工智能的主要寻路过程．本游戏规则设计如下：研究热点之一．1)Agent在每走一步的过程中，能够感知迷宫多Agent系统是一种多个智能自治的Agent通环境中状态(0表示可行区域，1表示障碍物)．过协作、协商、竞争等操作来共同完成复杂任务的分2)在Age

8、nt寻路过程中，如果随机选择的下一布式自主系统．鉴于Agent的自治性、主动性、响应步是可行区域，则前进一步，改变Agent得分分值并性、交互性、自学习性等特点，遗传算法的优点和进行下一步；当Agent面前有障碍时，则停在原位，多Agent系统的优点正好能够结合