遗传算法及神经网络在游戏开发中的应用

1、摘耍2Abstract21绪论31.1什么是遗传算法31.2遗传算法的原理31.3 什么是神经网络41.4人工神经网络原理42遗传算法简介以及简单实例62.1遗传算法的一般步骤62.2迷宫寻路问题62.3迷宫寻路问题关键代码72.4遗传算法的时间复杂度112.5遗传算法的总结123基J：遗传算法的神经网络优化实例133.1神经网络介绍133.2神经元的数学模型133.3神经网络结构143.4 神经网络实例153.4.1程序运行效來153.4.2确定神经网络的输入输出153.4.3程序介绍173.4.4 问题的优化23总结24参考文献25運传算法及神经网络在游戏开发中的应用遗传算法及神经网络在游

2、戏开发中的应用摘 要：在游戏丿I：发中，游戏AI （人匚智能）的编程是相当复朵的部分，程用员必须保证游戏AI 能够满足玩家盂求。现在国内外很多的游戏丿：发公司都运用遗传算法和神经网络对游戏AI进彳f编用。 通过此种方法编出的游戏AI将变得更加灵活，并H旳校强的智能性。相对以前游戏AI编程中的人 駅条件判断来说，遗传算法和神经网络使得游戏AI的灵活性远高J：前者.关键词：遗传算法；神经网络；人工智能Application of Genetic Algoritlun and Neural Network ingame prograniniingAbstract: Aitificial intell

3、igence is tlie most complex pan m gaiue piogiaminmg Programei must insure the Al meet players needs Nowadays , many foreign companys uses genetic algorithm and neural nemrork to encode the game Al. It is more superiority tlian lots of lf-else encoding by GA and NN . Make the game Al become bright an

4、d has a stiong mtelligence It's moie intelligent than former .Key word : Genetic Algorithm; Neuial Network; Aitificial Intelligence#遣传算法及神经网络庄游戏开发中的应用1绪论图遗传算法流程1.1什么是遗传算法遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的牛物进化过程的计算模 型，是一种通过模拟自然进化过程搜索最优解的方法。它能解决的问题很多，臂如，数学 方程的最人最小值，背包问题、装箱问题等等。在游戏开发中遗传算法的应用也十分频繁， 不少的游戏AI

5、都利用遗传算法进行编码。1.2遗传算法的原理遗传算法是模拟了牛物进化而演变出來的一种计算模空。生物在牛存过程中需要生长、 生殖、以及死亡几个阶段，遗传算法正式模仿了生长和生殖阶段，生殖阶段保证了生物体能 够不断的延续卜去。而生长阶段中生物体在门然环境不断变化的前提卜，会因为环境的因素 而产生一些突变。突变是无向的，它止-些生物体能够更好的适应环境，另一些生物体却因 为不能够适W环境idj死亡。突变同样也发生在生殖阶段。生长：生物体从一个受梢卵绘终成长为一个成年个体 得通过环境的考验一一大敌、食物、自然环境、犬气等因 索都可能成为个体生存的威胁。强壮的个体能够逃脱天敌 的追捕以及其他因索的束缚，

6、得到了生存生殖的权利。因 此它的优良垄因能够传承给后代。生殖：生物体进行交配长生后代，父代和母代各提供 一半的染色体进行结合，最终子代就拥何父母代的基因。 子代会继承父母代的一些性状。比如，长相、身材等等。 一般來说，通过遗传产生的新个体刈坏境往a n Yr更好的 适应性。死亡：生物体垠终的归宿。代衣了本生物个体的死亡, 该生物个体已经被淘汰。用遗传算法解决问题时，每一个染色体代表了一个解 决问题的方案，该方案相当J：我们生物学上讲的某一个生 物体，它可能适应环境，也可能不适应环境。遗传算法解 决问题就是把能够适应环境的个体找出來，遗传算法盂要 找出种群中适应度较高的个体进行生殖产生后代，当后

7、代 达到原种群数帚时进行适应度测试，当子代种群屮某个个 体能够达到要求，遗传算法就找到了一个问题的解决方 案：否则，子代种群無续匕一个步骤：牛殖。如此循环市 到程序找出达到耍求的个体。见图1.3什么是神经网络从生物学的角度來讲，神经网络是一个仃很多个神经细胞组成的错综复杂的神经网。神 经细胞是山细胞体、细胞核、树突、轴灾和轴突末梢组成，也叫作神经元。神经尤的树突连 接着其他的神经元，信号通过树突传递给卜一个神经元的轴突末梢,轴突末梢处理信号之后, 通过轴突传递给了这个神经尤。神经尤Z间的信息传递是单向的，即由一个神经尤的树突传 递给另一个神经尤的轴突末梢。生物神经细胞如图2所示【2】：神好细煦

8、图1.2生物神经细胞3遣传算法及神经网络庄游戏开发中的应用#遣传算法及神经网络庄游戏开发中的应用图1.3数字位图人类通过多年來的研究，仿照生物神经网络的模熨，设计出了人工神经网络。人工神经 网络是-种模仿动物神经网络行为特征，进行分布式并行倍息处理的算法数学模型。这种网 络依靠神经元权重Z间的联系，权值的调整，从而达到处理信息的口的。人工神经网络几何 自学习和自适应的能力，町以通过预先提供的一批相互对应的输入和输出数据，分析掌握 两者Z间潜在的规律，最终根据这些规律，用新的输入数据来推算输出结果。各个神经元的 权值恰到好处的表达了一个规律，就像-个物理公式一样。1.4人工神经网络原理肖我们看见

9、一个图片的时候，我们可以很准确的告诉他人，这个图片描 述的是什么。为然，在看这个图片之前，我们应该对该爭物己经冇所了解。 人工神经网络其实也是如此，我们给出一个图片，如图1.3所示，我们能够 清晰的看到这幅图片上显示的是一个阿拉们数字“0”。但是计算机却不能跟 我们人一样瞬间就识别这个数字。这是个6*10像索的图片，计算机接收的 只是每一个像素的信息，这些像素就相当输入。假设被着上黑色的代表1, 白色的为0.那么当所仃的60个信息输入人丁神经网络的神经尤，经过计 算输出的结果是1,就说明计算机认出了这个图片显示的是“0”反之，计 算机就没能认出这个图片是“0”。人工神经网络就是耍通过调整神经元

10、上的 权值，让计算机能够顺利地识别出这张图片。神经网络会根据输入的值进行运算判断，如果网络作出错误的的判决，则通过网络的学 习（遗传算法等进行权值优化），应使得网络减少卜次犯同样错误的可能性。首先，给网络的 并连接权值赋予（0, 1）区间内的随机值，将“0”所对应的图象模式输入给网络，网络将输入模 式加权求和、与门限比较、再进行菲线性运算，得到网络的输出。在此情况卜，网络输出 为“1”和“0”的概率各为50%,完全是随机产生。当输出为'T”（正确结果）时，说明权值之 间的关系是合理的。当输出为“0”（错谋结果）时，进化算法将改变各个权值，达到减小 犯同样错误的町能性。一般说来，网络中所

11、含的神经元个数越多，则它能记忆、识别的模式 也就越多。以卜是使用进化算法対神经尤权值进行优化的流程，如图4所示。图1-4神经网络权值忧化流程5遣传算法及神经网络庄游戏开发中的应用2遗传算法简介以及简单实例通过对遗传算法的简单介绍，我们対遗传算法并没仃多深刻的理解。卜面给出一个程序, 相信我们将対遗传算法的了解会变得深刻些。2.1遗传算法的一般步骤遗传算法编程的一般步骤分为以F：1. 计算染色体的适应度，记录卜每条染色体的适应值。2. 用轮盘法选出两条染色体。3. 将这两条染色体进行组合交叉，用随机两数确定组合交义进行的位置。4. 将新组合成的个体进行突变测试.5. 重复2、3、4步骤，11到新

12、的种群个体数与原种群个体数的相同。2.2迷宫寻路问题帮助Bob找到阿家的路是一个寻路程序。图2.1是一个2D迷宫，Bob要从右卜的 红方块，找到左上的红方块。遗传代数:0抜冋车开始运打图2-1寻路程序效果第一步我们得确定一个解决的方案，也就是一个个体。它代表了一个解决问题的方案， 但不一定能够找到答案，用该说人佇可能找不到答案。毎一个个体都佇很多的基因组成，很 多基因组介在一起才能表现出一个个体的行为.在这个程序中，我们要解决的问题是一一从 一个点到另一个点。Bob走出的每一步就相当于一个苴因，Bob可以选择往匕、卞、左、右 四个方向移动。那么甚因的种类就仃四种。用2进制表示所仃的可能只需耍两

13、位。见卜表2.1：表2. 1方向编码二进制十进制方向000北011南102东113西染色体长度与问题本身休戚相关，从这个迷宫來看，Bob从起点到终点的最好方案需耍 18步。那么染色体的长度将人丁或者等丁36,为什么是36而不是18呢，原因在丁我们用 2个二进制数衣示了 个基因，也就是说尿因长度为2。然后确定种样中的个体数彊，这个数的収值肖接关系到解决问题所需耍的遗传代数。就 像掷色子一样.你有2个色子.分别给你掷10次和20次.20次能掷出6-6的组合的槪率肯 定比10次的人。但是由在遗传算法中，虽然种祥中的个体数越人，找出可行方案所需的遗 传代数将会变小，但是，由J个体数駅直接决定了遗传算法

14、在每一代遗传屮的运算昴，所以 在用遗传算法解决问题时，无限帚地提高种群个体数将得不偿失。遗传算法屮，另自两个因索十分的重耍。一个是发生组合交叉的概率，一个是窠变的概 率。组合交义的概率决定了，父母代是否耍进行组合交义。为什么婆在遗传算法中添加这一 个变看呢？当随机数不能满足交义组合条件的时候，程序将完成染色体复制的过程。在遗传 算法屮，父母都是筛选出來的，适应度越高的个体被选到的概率越人，换言之，能作为父代 母代的都是比较能适应环境的。设置这个变届的好处：能够让遗传算法得到了代的种类更加 的丰密，口然也能够节省一定的遗传代数。卜一个是突变率，突变率的存在融必要的。现在 地球上的生物都是通过究变

15、而衍变成现在这样，他们都能够很好的适应环境。如果没自突变, 世界将不堪设想。突变率的设置在程序中起到了匝要的作用。以这个程序为例，如果我们在 开始决定个体基因的时候，每一个个体的皐因中都没有向北（00）的皋因。那丢弃了突变率 这个园，后果不堪设想。因为Bob不可能不往北找到终点。2.3迷宫寻路问题关键代码根据遗传算法编程的一般步骤分析，其中有这样儿个问题十分的亜耍。1. 如何判断个体的适应程度；2. 如何随机的找到两条适应度比较高的个体:3. 怎样进行交叉组介。在这个程序中,我们定义了一个迷宫类:CBobsMap：计算个体的适应度由CBobsMap类完成,以卜罗列了地图的基本信息:static

16、 con st i ntmapMAP_HEIGHTMAP_WIDTH;/ 存储地图信息数组static const intmM apWidth;地图宽度static const intm_iMapHeight;static const intmStartX;地图高度起始点X坐标7運传算法及神经网络在游戏开发中的应用static const int mJStartY;起始点 丫坐标static const int EndX;终点 X 坐标static const int mJEndY;终点 丫坐标int memoryMAP_HEIGHTMAP_WIDTH; 存储的当前地图信息 这些信息在遗传算法

17、计算个体的适应度中使用到。计算个体适应度是一个十分重耍的问题，我们设计计算适皿度程序时需耍注意：每一个 个体都有可能成为卜一代个体的父母代。所以在计算个体适应度时，我们尽最不能让任何一 个个体的适应度为0。适应度决定染色体符介耍求的程度。我们将染色体翻译成移动方向的集合，从起点坐标 开始对每一个方向进行比较，当将移动到的方位可以行走(值为0), bob向该方向移动：如 果将移动到的方位不可行走(值为1)，bob保持氐地不动。当染色体上所仃的基冈全部测试 完后bob的所在点为P (X, y)o终点为E (endx. endy)。测试染色体适应度的函数：Fitness = :x 一 endx +y

18、- endy +1测试适应度代码如下：double CBobsMap:TestRoute(const vector<int> &vecPath, CBobsMap &Bobs)从起始点开始int posX = m_iStartX;int posY = mStartY;for (int dir=O; dir<vecPath.size(); +dir)int NextDir = vecPathdir;switch(vecPathdir)case 0: 北测试卜一步能不能行走if ( (posY-1) < 0 ) | (mapposY-1posX = 1)不能

19、行走呆在原位break;else 可以行走posY 二 1;break;case 1:/南break;case 2:/东break;case 3: 西break;Bobs.memoryposYposX = 1;找到终点直接返回if(posY=m_iEndY && posX=m_iEndX) return 1;所仃基因都被测试后计算最终的位置与终点X轴丫轴的距离Int DiffX = abs(posX EndX);int DiffY = abs(posY mEndY);计算适应度return 1/(double)(DiffX+DiffY+1);从这个两数來看，我们很容易得到了此程

20、序推出循环的条件(找到一条答案)一一当此 函数返回1的时候。第二个问題：如何找到适应度比较高的个体？轮盘法可以解决这一问题，什么是轮盘法？简单的说就是高概率的被选到的概率人，低 概率的相对较小。正如卜面这条线段，这条线段分为儿条长短不一的小线段，长的町以认为 是适应度高的个体，而短的则是适皿度低的。当电脑随机选择一个区间在0至10的数，这图2. 2轮盘法示意图个数落在长度较长的线段上的概率相对较高。如图2.2所示。轮盘法选择适应度较高的个体函数为：SGenome& CgaBob:RouletteWheelSelection()选取一个点double fSlice= RandFloat(

21、) * mdTotalFitnessScore;double cfTotal = 0.0;int SelectedGenome = 0;循环计算该点落在那个个体上for (int i=0; i<m_iPopSize; +i)cfTotal += m_vecGe no mesi.dFit ness;if (cfTotal > fSlice)/找到该点退出循坏SelectedGe nome = i;break;retur n m_vecGe no mesSelectedGe no me;第三个问题是如何进行交叉组合？给出两条染色体染色体 1：0100110100000110染色体 2：

22、1101100101101101首先耍选择交义组合的位点，比如位点选择在了8这个位置，两条染色体进行交义组合。染色体 1：11011001 00000110染色体 2：01001101 01101101字体加粗部分为交叉组介的基因段。我们将交叉组合的函数命名为Crossover ()；原型如F：void CgaBob:Crossover( const vector<int> &mum, const vector<int> &dad, vector <int>& babyl,vector<int>& baby2) 是

23、否需耍进行交叉组介if ( (RandFloat() > m_dCrossoverRate) | (mum = dad) 父母苴接作为卜一代的个体babyl = mum;baby2 = dad;return;选择交叉组合位点int cp = Randlnt(0, m_iChromoLength 1);进行染色体段的交换for (int i=0; i<cp; +i)babyl push_back(mumi);baby2.push_back(dadi);for (i=cp; i<mum.size(); +i)babyl .push_back(dadi);baby2.push_ba

24、ck(mumi);2.4遗传算法的时间复杂度遗传算法是一个需耍人吊运算的算法，它的不确定性十分的大。就像这个程序一样，Bob 根本就不知道回家的路，他通过挾索才能回到一家。让我们计算一卜这个程序的时间复杂度。在程序开始Z前，我们要定义儿个鼠。种群的个体数最，个体的染色体长度，以及基因 的长度。根据上文得到基因长度为2。种群的个体数最和个体染色体长度，我们假设他们为 pop_size, chromo_length.简称 P 和 C。程序开始时，种群中没有任何个体，程序给这个种群增加这些个体。假设给每个个体赋 值所有用的时间复杂度为C,初期赋值所用的时间复杂度为t*P*Co接下来就是将染色体的 基

25、因转化成10进制,这次操作需要消耗n*C*P的时间复杂度,之后是计算适应度,适应度 计算需耍时间复杂度为m*C*P.轮盘法选样个体耗费x*P,交义纽合为y*C*P,突变为z*C*P. 第一次循坏结束，进入卜次循坏。一次循环需要的时间复杂度为： n*C*P+m*C*P+x*P+y*C*P+z*C*P=(n+m+y+z)*C*P+x*P,假设找到最佳答案的循环次数为 Go那么整个程序找到答案的时间复杂度为：fP9+(n+m+y+z)9*P+x*P)9 程序的时间复杂度为O (P*C*G)o这个程序的时间复杂度取决三个因索：染色体长度，个体的数呈，遗传的代数。这三 个因素的确定有很人的客观性。染色体

26、的长度吋以选择36以上的任何一个，当你把染色体个 数设置为36的时候，这样看来这个个体将是十分完美的，它就是一条到达终点的最短路径。 在这个程序开始时，每个个体的甚因都是由计算机随机取的，个体的不确定因素十分多。如 來每个个体的我因没仃那条M因是通向最短的那条路径，那么一切将不堪设想。唯一的可能 就是等待窠变。而在这程序中突变率，只有T分2 ，町想Ifu知这样低的灾变率，什么时候 才能窠变出适合的基肉呢？当然提高突变儿率在这样的悄况卜创以増加遗传找到终点的概 率。好吧，让我们将染色体的长度加人。染色体的长度直接的决定了 Bob冋家的路径的多少。 染色体越大，路径越多，找到终点的概率相对也较大。

27、个体的数录直接的决定了个体中基因 11遺传算法及神经网络庄游观开发中的应用的多样性，个体数越人对答案的产生越令利。个体数超人也不能够体现出程序的优化，毕竞 P*C*G的值会很人。最后就是遗传代数，这个因素并不是由程序员来决定的，当然也不好确 定，只能够根据多次测试才能够将Jt近似值确定卜來。2.5遗传算法的总结通过这个程序，我们対遗传算法白了更深入的了解。遗传算法町以解决一切求取最优解 的问题，但是在具体问题面前，也许会变得不可取。大家也许会提出这样的疑问：这只是个 简单的寻路程序为什么耍用遗传算法來做的？在利用遗传算法來解决这个问题之前，我们可 以通过对所仃路径的遍历得到一条最优的解，而且在

28、运算效率方而也人人的优J遗传算法。 再设患出II是被封死的，那通过遗传算法來计算星优解又会是什么样的结果呢？我们知道遗传算法能够确定一些不确定的因索，遗传算法的这一特性正好适合來找神经 网络算法中各个神经尤的权值。如何用遗传算法优化神经尤的权值？将会在卜一章介绍。13運传算法及神经网络在游戏开发中的应用3基于遗传算法的神经网络优化实例通过上一章对遗传算法的硏究，我们知道遗传算法可以找到问题中不确定因素。这一特 性正好在这一章屮得到应用。3. 1神经网络介绍神经网络是生物人脑思维的形式。生物的人脑冇很多的神经尤组成，为生物受到刺激， 电流信息将会从突出末梢通过轴灾传递到神经细胞中，然后神经细胞对

29、信息进行处理后从树 突传递给卜一个神经元。人彊的神经元Z间进行传递Z后,最终生物就做出了反应。3.2神经元的数学模型人丁神经网络（ANN）是模仿生物人脑而建芷起來的，它是由很多个神经元相互的链接 形成的一种结构。每一个人工神经尤是程序模拟的简化了的生物神经元，用ANN进行编程所 使用的神经元个数的多少取决F程序的解决问题的复杂程度，让我们来看看ANN中的神经元 的庐山真面目.如图3.1所示：图中标有w的小圈代表了 ANN中神经冗中突出末梢的权重（weight）。ANN中的输入（input） 和这些重磺决定了神经网络的整体活动。所仃这些权巫都设宣为到1 Z间的随机值。这些 权重直接的影响了神经元

30、的输出o他们起到的作用可能的正面的也可能是负面的。那这些权 逼是如何联系起来决定整个神经尤的输出（output）的呢？我们用一个数学公式來解决：a=W1X1+W2X2+W3X3+.+wnxn在人工神经网络编程屮，这些是远远不够的。通过对*个输入和权值乘积的累加运算后, 得出的值（activation）并不是能够直接作为输出，成为卜一个神经元的输入因子，正如人工 神经网络工作原理中写的，输出将被限制为0或者1。在人工神经网络屮，定义了一个临界值来限制输出值。如果输出的值人J临界值，则输出值为仁 反Z为0。用数学坐标如图3.2 所示：输出值 4u -累加结果IIIIk-2 -1 0 1 2图3.

31、2输入输岀的数学坐标将这个临界值设置为仁那么当输出值大jr的时候，输出值为仁小r的时候输出为-3.3神经网络结构在生物人脑内，神经元与神经尤直接是相互连接的，他们以某种特定的形式连接。如卜图3.3所示,这是一个前馈网络，输入值通过输入层传递到隐含层，图中圆圈表示神经尤.输入层输入的 值.经过隐金层神经元的计算.隐介层的输出作为卜一层输出层的输入.经过输出层处理后得到的结果才是最终的值.输出层隐金层输入g神经网络并不局限这个模型，隐含的数彊也町以根据问题需要增加或者减少。输入输出的 个数也是按照问题需耍而界。接卜来我将介绍一个关神经网络的实例。15連传算法及神经网络在游戏开发中的应用3.4神经网

32、络实例接卜來介绍一个用神经网络做的智能采矿程序。我们用神经网络來实现小乍门动采矿，通过遗 传算法对小车神经元权值进行调整,使小车能够更加灵活地采矿。程序运行效果如图3.4所示:3.4 1程序运行效果图3. 4采矿车效果图中右2种颜色的小车，这两种小车都是幣个种群中的个体.红色的小车为适应度比较為的。绿色 的方块代表了矿。3.4.2确定神经网络的输入输出在程序开始前，我们紂确定输入输出的数最以及他们的内容。酋先，我们要知道小车口身的位 置（坐标），最近矿的位置也要作为输入。这样两个坐标就有4个输入，分别是小车坐标（xi, yi） 以及矿的坐标（X2, y2）o但这些就足够了吗？当然不是，小车有自

33、己的速度，速度用一个矢最表示 （X. y）o如此我们就冇了 6个输入。在神经网络中，输入的多少决定了每个神经尤的输入个数，从 而时间复杂度将人人的增加。在神经网络优化中，如何减少输入的多少是最巫耍的。在这个程序中，英实小车的坐标和矿的坐标可以介成一个欠量一一小车指向矿的欠鼠 （yi-xi,y2-x2）o 如图 3.5 所示:图3. 5小车输入变呈输入减少到了 4个。输入已经找出，那接卜來就是决定输出的个数。输出的个数在程序中只影响到输出层神经元的 个数，如果神经网络庞人的话，输出层所消耗的CPU时间往往可以忽略。在决定输diZijij,让我们看卜小车是如何设计的。如图3.6所示：神经网络的输出

34、来控制小乍的移动。小车的左右连个轮子动力的人小可以决定小乍移动的速度以及小乍的转弯。如此看來这两个吊就可以决定小作的移动。那么，该神经网络的输出为2个，一个左轮的力，另一个是右轮的力。小车的转向值通过左轮力减去右轮力而来，小车速度则是他们的和。RotForce = mTrack - m.rTrack;转向力度m_d Speed = mTack + mrTrack;速度或许人家会冇疑问.神经网络的输出为o和仁但是在这个图3.6采矿车模空 问题中，如果输出为0和1的,那么小车的移动将只有4种情况。在这个程序中,我们不把神经元的输出限定为0和仁 取而代之,它的输出将被限定在0到1Z间 的小数。这样小

35、车就能够很口然的移动了。既然每个神经元的输出被限定在了 o到1 Z间的小数， 它如何来实现呢。卜图是一个数学坐标图（如图3.7所示）：它能够很形象的解决这个问题.1这个曲线的数学方程式为oMpM = ：Z7V o e为常凤e的近似值为2.7183。p值通常被 1 + £ z设置为1.那我们需耍多少个隐含层呢？先來说说隐含层的好处吧。隐禽层顾名思义它并没仃在实际的输 出上引川，但是他对输出有着决泄性作用。就辔如这个问题吧。当没仃隐含层的时候，小车会做出 一些十分古怪的动作，即使是遗传很影次的个体同样存在着这样的问题。众所周知，人类人脑很发 达，其神经尤的个数是比他动物的千力倍。为什么人

36、类能统治地球，其原因可想而知。在这个问题 上，我们将隐禽层的个数设置为1。这样小乍的行为看起來会更加的门然。图3. 7神经元输出值曲线3. 4 3 程序介绍介绍了那么多，让我们看看神经元、隐含层以及神经网的定义吧。神经元：struct SNeuron输入的数最intm_Numlnputs;毎个输入的权匝vector<double> m_vecWeight;SNeuron(int Numlnpu；;隐含层：struct SNeuronLayer隐介层中神经元的数砒intm_NumNeuro ns;隐含层中所有神经元vector<SNeuro n> m_vecNeur on

37、s;SNeuronLayer(int NumNeurons, int NumlnputsPerNeuron);神经网：class CNeuralNet private:intm_Numlnputs;输入个数intmNumOutputs;输出个数intm_NumHiddenLayers;隐金层数吊intm_Neur on sPerHidde nLyr;隐倉层的神经尤数vector<SNeur on Layer>m_vecLayers; 隐會层CNeuralNet();/创建神经网络void CreateNet();获取神经网络的所冇神经元的权啦vector<double>

38、GetWeights()c onst;获取神经网络所何神经元的权巫个数intGetNumberOfWeights()const;替换所有权重voidPutWeights(vector<double> &weights);s型曲线函数inline double Sigmoid(double activation, double response);计算输出vector<double> Update(vector<double> &nputs);介绍了神经网络的一些币:耍的函数之后，遗传算法如何加入到神经网络屮，成了接卜來要解决 的问题。K实，遗

39、传算法并没仃戏接的跟神经网络进行挂钩，它还是很平常的遗传算法一样完成门 C的使命(上一章寻路问题)。唯不同的就是他的基冈染色体不是简单的0和1序列了。神经网络 中所有神经尤的权重将成为遗传算法屮的染色体。那么，遗传算法屮的染色体长度将由神经网络中 神经尤来决定。如何来测试个体的适应度才是这个程序比较核心的问题。这并不像上一章中的寻路问题一样简 单了，在这个问题中，对个体适应度的测试并不是一步就能解决的。用观察的方式來测试个体适应 度，我们给每个小车2000步(游戏2000帧)的机会，当小车吃到-个矿的时候小车的适应度加1, 直到2000步结束。假定小车一步能够釆到的矿个数为m,那么适应度函数如

40、卜：2000Fitn ess =工“i=lstruct SGe nomevector <double> vecWeights;doubledFit ness;SGenome():dFitness(0)SGenome( vector <double> w, double f): vecWeights(w), dFitness(f)O雨我<用于排序friend bool operator<(const SGenome& Ihs, const SGenome& rhs)return (Ihs.dFitness < rhs.dFitness);

41、变异程序:void CGenAlg:Mutate(vector<double> &chromo)for (int i=0; i<chromo.size(); +i)if (RandFloat() < m_dMutationRate)chromoi += (RandomClamped() * CParams:dMaxPerturbation);在突变程序中，我们并没勺看到像寻路问题中直接将基因取反操作，而是将该基因(权咆)加 匕了一个很小的数(可正可负)，该数完全由电脑给出的随机数。小车类(遗传算法中的个体)：class CMinesweeperprivate:小

42、乍的人脑(神经网络)CNeuralNet mtsBrain;小乍所处在的位置坐标SVector2D m_vPosition;小车的朝向SVector2D m_vLookAt;小车速度(速度包含了方向和速度人小，第一个变炭代表了转弯的人小)doublem_dRotati on;doublem_dSpeed;存储神经网络输出，左轮力鼠以及右轮力晟doublemTrack,m_rTrack;小车适应度doublem_dFit ness;小乍显示比例大小(游戏中应用较广)doublem_dScale;最近矿的编号intmClosestMine;CMinesweeper();测试适应度的核心，在此程序中

43、毎次遗传需耍运行2000次boolUpdate(vector<SVector2D> & mines);世界坐标的转变voidWorldTransform(vectorvSPoint> &sweeper);获取垠近矿的坐标SVector2D GetClosestMine(vector<SVector2D> &objects);資看是否己经找到了一个矿intCheckForMine(vector<SVector2D> &mines, double size);voidReset();SVector2D Position()c

44、onstreturn m_vPosition;voidIn creme ntFitn ess(double val)m_dFitness += val;doubleFitness()constreturn m.dFitness;voidPutWeights(vector<double> &w)mtsBrain.PutWeights(w);intGetNumberOfWeights()constreturn m_ltsBrain.GetNumberOfWeights();遗传算法核心类：class CGenAIgprivate:所有个体的染色体vector <SGeno

45、me>m_vecPop;个体数量int mJPopSize;/个体基因长度int mChromoLength;/种群的适应度double m_dTotalFitness;显住个体适应度double m.dBestFitness;平均适应度double m_dAverageFitness;放差个体适应度double m_dWorstFitness;/垃佳个体编号int mFittestGe nome;突变概率double m_d Mutation Rate;交义组介率double m_dCrossoverRate;/记录遗传代数intm.cGe nerati on;voidCrossove

46、r(const vector<double> &mum,const vector<double> &dadt vector<double>&baby1 fvector<double>&baby2);void Mutate(vector<double> &chromo);SGenome GetChromoRoulette();void GrabNBest(intNBest,const intNumCopies.vector<SGenome> &vecPop);void Fitn

47、essScaleRank();void CalculateBestWorstAvTot();void Reset();public:CGenAlg(int popsize,doubleMutRat,doubleCrossRat,intnu mweights);遗传一代vector<SGe no me>Epoch(vector<SGenome> &old_pop);vector<SGe no me>GetChromos()constreturn m_vecPop;doubleAverageFitness()constfreturn m_dTotalFi

48、tness / m_iPopSize;doubleBestFitness()constreturn m.dBestFitness;；肖遗传算法的问题解决Z后，但是我们发现神经网络和遗传算法Z间似乎没令任何联系，所令我们继续一个类来将他们进行冇机的结合。我们乂编写了这么一个控制类，来把两者联系。接卜來让我们揭开这个程序的神秘面纱:class CControllerprivate:存储所仃个体基因vector<SGe no me>m_vecThePopulation;个体vector<CMinesweeper> m_vecSweepers;矿vector<SVecto

49、r2 D>m_vecMi nes;23連传算法及神经网络在游戏开发中的应用遗传算法类指什CGenAIg*intint int绘制小车所需 vector<SPoint> vector<SPoint> 存储平均适应度 vector<double> 存储最佳适应度 vector<double> 用r画图HPENHPENHPEN HPEN 窗LI句柄 HWND选择模式m_pGA; m_NumSweepers; m_NumMines; m_NumWeightslnNN;m_SweeperVB;m_MineVB;m_vecAvFitness;m_vecBestFit ness;m.RedPen;m.BluePen;m_GreenPe n;m_OldPen;m.hwndMain;boolm_bFastRender;小乍步数，测试适应度所需intmTicks;遗传代数记录intmGen erations;窗I I人小泊tcxClient, cyClient;void PlotStats(HDC surface);public:CController(HWND hwndMain);CController();voidRender(HDC surface);voidWorldTr