遺傳算法及神經(jīng)網(wǎng)絡(luò)在游戲開(kāi)發(fā)中的應(yīng)用

1、摘耍2Abstract21緒論31.1什么是遺傳算法31.2遺傳算法的原理31.3 什么是神經(jīng)網(wǎng)絡(luò)41.4人工神經(jīng)網(wǎng)絡(luò)原理42遺傳算法簡(jiǎn)介以及簡(jiǎn)單實(shí)例62.1遺傳算法的一般步驟62.2迷宮尋路問(wèn)題62.3迷宮尋路問(wèn)題關(guān)鍵代碼72.4遺傳算法的時(shí)間復(fù)雜度112.5遺傳算法的總結(jié)123基J：遺傳算法的神經(jīng)網(wǎng)絡(luò)優(yōu)化實(shí)例133.1神經(jīng)網(wǎng)絡(luò)介紹133.2神經(jīng)元的數(shù)學(xué)模型133.3神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)143.4 神經(jīng)網(wǎng)絡(luò)實(shí)例153.4.1程序運(yùn)行效來(lái)153.4.2確定神經(jīng)網(wǎng)絡(luò)的輸入輸出153.4.3程序介紹173.4.4 問(wèn)題的優(yōu)化23總結(jié)24參考文獻(xiàn)25運(yùn)傳算法及神經(jīng)網(wǎng)絡(luò)在游戲開(kāi)發(fā)中的應(yīng)用遺傳算法及神經(jīng)網(wǎng)絡(luò)在游

2、戲開(kāi)發(fā)中的應(yīng)用摘 要：在游戲丿I：發(fā)中，游戲AI （人匚智能）的編程是相當(dāng)復(fù)朵的部分，程用員必須保證游戲AI 能夠滿足玩家盂求。現(xiàn)在國(guó)內(nèi)外很多的游戲丿：發(fā)公司都運(yùn)用遺傳算法和神經(jīng)網(wǎng)絡(luò)對(duì)游戲AI進(jìn)彳f編用。 通過(guò)此種方法編出的游戲AI將變得更加靈活，并H旳校強(qiáng)的智能性。相對(duì)以前游戲AI編程中的人 駅條件判斷來(lái)說(shuō)，遺傳算法和神經(jīng)網(wǎng)絡(luò)使得游戲AI的靈活性遠(yuǎn)高J：前者.關(guān)鍵詞：遺傳算法；神經(jīng)網(wǎng)絡(luò)；人工智能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#遣傳算法及神經(jīng)網(wǎng)絡(luò)莊游戲開(kāi)發(fā)中的應(yīng)用1緒論圖遺傳算法流程1.1什么是遺傳算法遺傳算法是模擬達(dá)爾文生物進(jìn)化論的自然選擇和遺傳學(xué)機(jī)理的牛物進(jìn)化過(guò)程的計(jì)算模 型，是一種通過(guò)模擬自然進(jìn)化過(guò)程搜索最優(yōu)解的方法。它能解決的問(wèn)題很多，臂如，數(shù)學(xué) 方程的最人最小值，背包問(wèn)題、裝箱問(wèn)題等等。在游戲開(kāi)發(fā)中遺傳算法的應(yīng)用也十分頻繁， 不少的游戲AI

5、都利用遺傳算法進(jìn)行編碼。1.2遺傳算法的原理遺傳算法是模擬了牛物進(jìn)化而演變出來(lái)的一種計(jì)算模空。生物在牛存過(guò)程中需要生長(zhǎng)、 生殖、以及死亡幾個(gè)階段，遺傳算法正式模仿了生長(zhǎng)和生殖階段，生殖階段保證了生物體能 夠不斷的延續(xù)卜去。而生長(zhǎng)階段中生物體在門(mén)然環(huán)境不斷變化的前提卜，會(huì)因?yàn)榄h(huán)境的因素 而產(chǎn)生一些突變。突變是無(wú)向的，它止-些生物體能夠更好的適應(yīng)環(huán)境，另一些生物體卻因 為不能夠適W環(huán)境idj死亡。突變同樣也發(fā)生在生殖階段。生長(zhǎng)：生物體從一個(gè)受梢卵繪終成長(zhǎng)為一個(gè)成年個(gè)體 得通過(guò)環(huán)境的考驗(yàn)一一大敵、食物、自然環(huán)境、犬氣等因 索都可能成為個(gè)體生存的威脅。強(qiáng)壯的個(gè)體能夠逃脫天敵 的追捕以及其他因索的束縛，

6、得到了生存生殖的權(quán)利。因 此它的優(yōu)良?jí)乓蚰軌騻鞒薪o后代。生殖：生物體進(jìn)行交配長(zhǎng)生后代，父代和母代各提供 一半的染色體進(jìn)行結(jié)合，最終子代就擁何父母代的基因。 子代會(huì)繼承父母代的一些性狀。比如，長(zhǎng)相、身材等等。 一般來(lái)說(shuō)，通過(guò)遺傳產(chǎn)生的新個(gè)體刈壞境往a n Yr更好的 適應(yīng)性。死亡：生物體垠終的歸宿。代衣了本生物個(gè)體的死亡, 該生物個(gè)體已經(jīng)被淘汰。用遺傳算法解決問(wèn)題時(shí)，每一個(gè)染色體代表了一個(gè)解 決問(wèn)題的方案，該方案相當(dāng)J：我們生物學(xué)上講的某一個(gè)生 物體，它可能適應(yīng)環(huán)境，也可能不適應(yīng)環(huán)境。遺傳算法解 決問(wèn)題就是把能夠適應(yīng)環(huán)境的個(gè)體找出來(lái)，遺傳算法盂要 找出種群中適應(yīng)度較高的個(gè)體進(jìn)行生殖產(chǎn)生后代，當(dāng)后

7、代 達(dá)到原種群數(shù)帚時(shí)進(jìn)行適應(yīng)度測(cè)試，當(dāng)子代種群屮某個(gè)個(gè) 體能夠達(dá)到要求，遺傳算法就找到了一個(gè)問(wèn)題的解決方 案：否則，子代種群無(wú)續(xù)匕一個(gè)步驟：牛殖。如此循環(huán)市 到程序找出達(dá)到耍求的個(gè)體。見(jiàn)圖1.3什么是神經(jīng)網(wǎng)絡(luò)從生物學(xué)的角度來(lái)講，神經(jīng)網(wǎng)絡(luò)是一個(gè)仃很多個(gè)神經(jīng)細(xì)胞組成的錯(cuò)綜復(fù)雜的神經(jīng)網(wǎng)。神 經(jīng)細(xì)胞是山細(xì)胞體、細(xì)胞核、樹(shù)突、軸災(zāi)和軸突末梢組成，也叫作神經(jīng)元。神經(jīng)尤的樹(shù)突連 接著其他的神經(jīng)元，信號(hào)通過(guò)樹(shù)突傳遞給卜一個(gè)神經(jīng)元的軸突末梢,軸突末梢處理信號(hào)之后, 通過(guò)軸突傳遞給了這個(gè)神經(jīng)尤。神經(jīng)尤Z間的信息傳遞是單向的，即由一個(gè)神經(jīng)尤的樹(shù)突傳 遞給另一個(gè)神經(jīng)尤的軸突末梢。生物神經(jīng)細(xì)胞如圖2所示【2】：神好細(xì)煦

8、圖1.2生物神經(jīng)細(xì)胞3遣傳算法及神經(jīng)網(wǎng)絡(luò)莊游戲開(kāi)發(fā)中的應(yīng)用#遣傳算法及神經(jīng)網(wǎng)絡(luò)莊游戲開(kāi)發(fā)中的應(yīng)用圖1.3數(shù)字位圖人類(lèi)通過(guò)多年來(lái)的研究，仿照生物神經(jīng)網(wǎng)絡(luò)的模熨，設(shè)計(jì)出了人工神經(jīng)網(wǎng)絡(luò)。人工神經(jīng) 網(wǎng)絡(luò)是-種模仿動(dòng)物神經(jīng)網(wǎng)絡(luò)行為特征，進(jìn)行分布式并行倍息處理的算法數(shù)學(xué)模型。這種網(wǎng) 絡(luò)依靠神經(jīng)元權(quán)重Z間的聯(lián)系，權(quán)值的調(diào)整，從而達(dá)到處理信息的口的。人工神經(jīng)網(wǎng)絡(luò)幾何 自學(xué)習(xí)和自適應(yīng)的能力，町以通過(guò)預(yù)先提供的一批相互對(duì)應(yīng)的輸入和輸出數(shù)據(jù)，分析掌握 兩者Z間潛在的規(guī)律，最終根據(jù)這些規(guī)律，用新的輸入數(shù)據(jù)來(lái)推算輸出結(jié)果。各個(gè)神經(jīng)元的 權(quán)值恰到好處的表達(dá)了一個(gè)規(guī)律，就像-個(gè)物理公式一樣。1.4人工神經(jīng)網(wǎng)絡(luò)原理肖我們看見(jiàn)

9、一個(gè)圖片的時(shí)候，我們可以很準(zhǔn)確的告訴他人，這個(gè)圖片描 述的是什么。為然，在看這個(gè)圖片之前，我們應(yīng)該對(duì)該爭(zhēng)物己經(jīng)冇所了解。 人工神經(jīng)網(wǎng)絡(luò)其實(shí)也是如此，我們給出一個(gè)圖片，如圖1.3所示，我們能夠 清晰的看到這幅圖片上顯示的是一個(gè)阿拉們數(shù)字“0”。但是計(jì)算機(jī)卻不能跟 我們?nèi)艘粯铀查g就識(shí)別這個(gè)數(shù)字。這是個(gè)6*10像索的圖片，計(jì)算機(jī)接收的 只是每一個(gè)像素的信息，這些像素就相當(dāng)輸入。假設(shè)被著上黑色的代表1, 白色的為0.那么當(dāng)所仃的60個(gè)信息輸入人丁神經(jīng)網(wǎng)絡(luò)的神經(jīng)尤，經(jīng)過(guò)計(jì) 算輸出的結(jié)果是1,就說(shuō)明計(jì)算機(jī)認(rèn)出了這個(gè)圖片顯示的是“0”反之，計(jì) 算機(jī)就沒(méi)能認(rèn)出這個(gè)圖片是“0”。人工神經(jīng)網(wǎng)絡(luò)就是耍通過(guò)調(diào)整神經(jīng)元

10、上的 權(quán)值，讓計(jì)算機(jī)能夠順利地識(shí)別出這張圖片。神經(jīng)網(wǎng)絡(luò)會(huì)根據(jù)輸入的值進(jìn)行運(yùn)算判斷，如果網(wǎng)絡(luò)作出錯(cuò)誤的的判決，則通過(guò)網(wǎng)絡(luò)的學(xué) 習(xí)（遺傳算法等進(jìn)行權(quán)值優(yōu)化），應(yīng)使得網(wǎng)絡(luò)減少卜次犯同樣錯(cuò)誤的可能性。首先，給網(wǎng)絡(luò)的 并連接權(quán)值賦予（0, 1）區(qū)間內(nèi)的隨機(jī)值，將“0”所對(duì)應(yīng)的圖象模式輸入給網(wǎng)絡(luò)，網(wǎng)絡(luò)將輸入模 式加權(quán)求和、與門(mén)限比較、再進(jìn)行菲線性運(yùn)算，得到網(wǎng)絡(luò)的輸出。在此情況卜，網(wǎng)絡(luò)輸出 為“1”和“0”的概率各為50%,完全是隨機(jī)產(chǎn)生。當(dāng)輸出為'T”（正確結(jié)果）時(shí)，說(shuō)明權(quán)值之 間的關(guān)系是合理的。當(dāng)輸出為“0”（錯(cuò)謀結(jié)果）時(shí)，進(jìn)化算法將改變各個(gè)權(quán)值，達(dá)到減小 犯同樣錯(cuò)誤的町能性。一般說(shuō)來(lái)，網(wǎng)絡(luò)中所

11、含的神經(jīng)元個(gè)數(shù)越多，則它能記憶、識(shí)別的模式 也就越多。以卜是使用進(jìn)化算法対神經(jīng)尤權(quán)值進(jìn)行優(yōu)化的流程，如圖4所示。圖1-4神經(jīng)網(wǎng)絡(luò)權(quán)值憂化流程5遣傳算法及神經(jīng)網(wǎng)絡(luò)莊游戲開(kāi)發(fā)中的應(yīng)用2遺傳算法簡(jiǎn)介以及簡(jiǎn)單實(shí)例通過(guò)對(duì)遺傳算法的簡(jiǎn)單介紹，我們対遺傳算法并沒(méi)仃多深刻的理解。卜面給出一個(gè)程序, 相信我們將対遺傳算法的了解會(huì)變得深刻些。2.1遺傳算法的一般步驟遺傳算法編程的一般步驟分為以F：1. 計(jì)算染色體的適應(yīng)度，記錄卜每條染色體的適應(yīng)值。2. 用輪盤(pán)法選出兩條染色體。3. 將這兩條染色體進(jìn)行組合交叉，用隨機(jī)兩數(shù)確定組合交義進(jìn)行的位置。4. 將新組合成的個(gè)體進(jìn)行突變測(cè)試.5. 重復(fù)2、3、4步驟，11到新

12、的種群個(gè)體數(shù)與原種群個(gè)體數(shù)的相同。2.2迷宮尋路問(wèn)題幫助Bob找到阿家的路是一個(gè)尋路程序。圖2.1是一個(gè)2D迷宮，Bob要從右卜的 紅方塊，找到左上的紅方塊。遺傳代數(shù):0抜冋車(chē)開(kāi)始運(yùn)打圖2-1尋路程序效果第一步我們得確定一個(gè)解決的方案，也就是一個(gè)個(gè)體。它代表了一個(gè)解決問(wèn)題的方案， 但不一定能夠找到答案，用該說(shuō)人佇可能找不到答案。毎一個(gè)個(gè)體都佇很多的基因組成，很 多基因組介在一起才能表現(xiàn)出一個(gè)個(gè)體的行為.在這個(gè)程序中，我們要解決的問(wèn)題是一一從 一個(gè)點(diǎn)到另一個(gè)點(diǎn)。Bob走出的每一步就相當(dāng)于一個(gè)苴因，Bob可以選擇往匕、卞、左、右 四個(gè)方向移動(dòng)。那么甚因的種類(lèi)就仃四種。用2進(jìn)制表示所仃的可能只需耍兩

13、位。見(jiàn)卜表2.1：表2. 1方向編碼二進(jìn)制十進(jìn)制方向000北011南102東113西染色體長(zhǎng)度與問(wèn)題本身休戚相關(guān)，從這個(gè)迷宮來(lái)看，Bob從起點(diǎn)到終點(diǎn)的最好方案需耍 18步。那么染色體的長(zhǎng)度將人丁或者等丁36,為什么是36而不是18呢，原因在丁我們用 2個(gè)二進(jìn)制數(shù)衣示了 個(gè)基因，也就是說(shuō)尿因長(zhǎng)度為2。然后確定種樣中的個(gè)體數(shù)彊，這個(gè)數(shù)的収值肖接關(guān)系到解決問(wèn)題所需耍的遺傳代數(shù)。就 像擲色子一樣.你有2個(gè)色子.分別給你擲10次和20次.20次能擲出6-6的組合的槪率肯 定比10次的人。但是由在遺傳算法中，雖然種祥中的個(gè)體數(shù)越人，找出可行方案所需的遺 傳代數(shù)將會(huì)變小，但是，由J個(gè)體數(shù)駅直接決定了遺傳算法

14、在每一代遺傳屮的運(yùn)算昴，所以 在用遺傳算法解決問(wèn)題時(shí)，無(wú)限帚地提高種群個(gè)體數(shù)將得不償失。遺傳算法屮，另自兩個(gè)因索十分的重耍。一個(gè)是發(fā)生組合交叉的概率，一個(gè)是窠變的概 率。組合交義的概率決定了，父母代是否耍進(jìn)行組合交義。為什么婆在遺傳算法中添加這一 個(gè)變看呢？當(dāng)隨機(jī)數(shù)不能滿足交義組合條件的時(shí)候，程序?qū)⑼瓿扇旧w復(fù)制的過(guò)程。在遺傳 算法屮，父母都是篩選出來(lái)的，適應(yīng)度越高的個(gè)體被選到的概率越人，換言之，能作為父代 母代的都是比較能適應(yīng)環(huán)境的。設(shè)置這個(gè)變屆的好處：能夠讓遺傳算法得到了代的種類(lèi)更加 的豐密，口然也能夠節(jié)省一定的遺傳代數(shù)。卜一個(gè)是突變率，突變率的存在融必要的?，F(xiàn)在 地球上的生物都是通過(guò)究變

15、而衍變成現(xiàn)在這樣，他們都能夠很好的適應(yīng)環(huán)境。如果沒(méi)自突變, 世界將不堪設(shè)想。突變率的設(shè)置在程序中起到了匝要的作用。以這個(gè)程序?yàn)槔绻覀冊(cè)?開(kāi)始決定個(gè)體基因的時(shí)候，每一個(gè)個(gè)體的皐因中都沒(méi)有向北（00）的皋因。那丟棄了突變率 這個(gè)園，后果不堪設(shè)想。因?yàn)锽ob不可能不往北找到終點(diǎn)。2.3迷宮尋路問(wèn)題關(guān)鍵代碼根據(jù)遺傳算法編程的一般步驟分析，其中有這樣兒個(gè)問(wèn)題十分的亜耍。1. 如何判斷個(gè)體的適應(yīng)程度；2. 如何隨機(jī)的找到兩條適應(yīng)度比較高的個(gè)體:3. 怎樣進(jìn)行交叉組介。在這個(gè)程序中,我們定義了一個(gè)迷宮類(lèi):CBobsMap：計(jì)算個(gè)體的適應(yīng)度由CBobsMap類(lèi)完成,以卜羅列了地圖的基本信息:static

16、 con st i ntmapMAP_HEIGHTMAP_WIDTH;/ 存儲(chǔ)地圖信息數(shù)組static const intmM apWidth;地圖寬度static const intm_iMapHeight;static const intmStartX;地圖高度起始點(diǎn)X坐標(biāo)7運(yùn)傳算法及神經(jīng)網(wǎng)絡(luò)在游戲開(kāi)發(fā)中的應(yīng)用static const int mJStartY;起始點(diǎn) 丫坐標(biāo)static const int EndX;終點(diǎn) X 坐標(biāo)static const int mJEndY;終點(diǎn) 丫坐標(biāo)int memoryMAP_HEIGHTMAP_WIDTH; 存儲(chǔ)的當(dāng)前地圖信息 這些信息在遺傳算法

17、計(jì)算個(gè)體的適應(yīng)度中使用到。計(jì)算個(gè)體適應(yīng)度是一個(gè)十分重耍的問(wèn)題，我們?cè)O(shè)計(jì)計(jì)算適皿度程序時(shí)需耍注意：每一個(gè) 個(gè)體都有可能成為卜一代個(gè)體的父母代。所以在計(jì)算個(gè)體適應(yīng)度時(shí)，我們盡最不能讓任何一 個(gè)個(gè)體的適應(yīng)度為0。適應(yīng)度決定染色體符介耍求的程度。我們將染色體翻譯成移動(dòng)方向的集合，從起點(diǎn)坐標(biāo) 開(kāi)始對(duì)每一個(gè)方向進(jìn)行比較，當(dāng)將移動(dòng)到的方位可以行走(值為0), bob向該方向移動(dòng)：如 果將移動(dòng)到的方位不可行走(值為1)，bob保持氐地不動(dòng)。當(dāng)染色體上所仃的基岡全部測(cè)試 完后bob的所在點(diǎn)為P (X, y)o終點(diǎn)為E (endx. endy)。測(cè)試染色體適應(yīng)度的函數(shù)：Fitness = :x 一 endx +y

18、- endy +1測(cè)試適應(yīng)度代碼如下：double CBobsMap:TestRoute(const vector<int> &vecPath, CBobsMap &Bobs)從起始點(diǎn)開(kāi)始int posX = m_iStartX;int posY = mStartY;for (int dir=O; dir<vecPath.size(); +dir)int NextDir = vecPathdir;switch(vecPathdir)case 0: 北測(cè)試卜一步能不能行走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;找到終點(diǎn)直接返回if(posY=m_iEndY && posX=m_iEndX) return 1;所仃基因都被測(cè)試后計(jì)算最終的位置與終點(diǎn)X軸丫軸的距離Int DiffX = abs(posX EndX);int DiffY = abs(posY mEndY);計(jì)算適應(yīng)度return 1/(double)(DiffX+DiffY+1);從這個(gè)兩數(shù)來(lái)看，我們很容易得到了此程

20、序推出循環(huán)的條件(找到一條答案)一一當(dāng)此 函數(shù)返回1的時(shí)候。第二個(gè)問(wèn)題：如何找到適應(yīng)度比較高的個(gè)體？輪盤(pán)法可以解決這一問(wèn)題，什么是輪盤(pán)法？簡(jiǎn)單的說(shuō)就是高概率的被選到的概率人，低 概率的相對(duì)較小。正如卜面這條線段，這條線段分為兒條長(zhǎng)短不一的小線段，長(zhǎng)的町以認(rèn)為 是適應(yīng)度高的個(gè)體，而短的則是適皿度低的。當(dāng)電腦隨機(jī)選擇一個(gè)區(qū)間在0至10的數(shù)，這圖2. 2輪盤(pán)法示意圖個(gè)數(shù)落在長(zhǎng)度較長(zhǎng)的線段上的概率相對(duì)較高。如圖2.2所示。輪盤(pán)法選擇適應(yīng)度較高的個(gè)體函數(shù)為：SGenome& CgaBob:RouletteWheelSelection()選取一個(gè)點(diǎn)double fSlice= RandFloat(

21、) * mdTotalFitnessScore;double cfTotal = 0.0;int SelectedGenome = 0;循環(huán)計(jì)算該點(diǎn)落在那個(gè)個(gè)體上for (int i=0; i<m_iPopSize; +i)cfTotal += m_vecGe no mesi.dFit ness;if (cfTotal > fSlice)/找到該點(diǎn)退出循壞SelectedGe nome = i;break;retur n m_vecGe no mesSelectedGe no me;第三個(gè)問(wèn)題是如何進(jìn)行交叉組合？給出兩條染色體染色體 1：0100110100000110染色體 2：

22、1101100101101101首先耍選擇交義組合的位點(diǎn)，比如位點(diǎn)選擇在了8這個(gè)位置，兩條染色體進(jìn)行交義組合。染色體 1：11011001 00000110染色體 2：01001101 01101101字體加粗部分為交叉組介的基因段。我們將交叉組合的函數(shù)命名為Crossover ()；原型如F：void CgaBob:Crossover( const vector<int> &mum, const vector<int> &dad, vector <int>& babyl,vector<int>& baby2) 是

23、否需耍進(jìn)行交叉組介if ( (RandFloat() > m_dCrossoverRate) | (mum = dad) 父母苴接作為卜一代的個(gè)體babyl = mum;baby2 = dad;return;選擇交叉組合位點(diǎn)int cp = Randlnt(0, m_iChromoLength 1);進(jìn)行染色體段的交換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遺傳算法的時(shí)間復(fù)雜度遺傳算法是一個(gè)需耍人吊運(yùn)算的算法，它的不確定性十分的大。就像這個(gè)程序一樣，Bob 根本就不知道回家的路，他通過(guò)挾索才能回到一家。讓我們計(jì)算一卜這個(gè)程序的時(shí)間復(fù)雜度。在程序開(kāi)始Z前，我們要定義兒個(gè)鼠。種群的個(gè)體數(shù)最，個(gè)體的染色體長(zhǎng)度，以及基因 的長(zhǎng)度。根據(jù)上文得到基因長(zhǎng)度為2。種群的個(gè)體數(shù)最和個(gè)體染色體長(zhǎng)度，我們假設(shè)他們?yōu)?pop_size, chromo_length.簡(jiǎn)稱(chēng) P 和 C。程序開(kāi)始時(shí)，種群中沒(méi)有任何個(gè)體，程序給這個(gè)種群增加這些個(gè)體。假設(shè)給每個(gè)個(gè)體賦 值所有用的時(shí)間復(fù)雜度為C,初期賦值所用的時(shí)間復(fù)雜度為t*P*Co接下來(lái)就是將染色體的 基

25、因轉(zhuǎn)化成10進(jìn)制,這次操作需要消耗n*C*P的時(shí)間復(fù)雜度,之后是計(jì)算適應(yīng)度,適應(yīng)度 計(jì)算需耍時(shí)間復(fù)雜度為m*C*P.輪盤(pán)法選樣個(gè)體耗費(fèi)x*P,交義紐合為y*C*P,突變?yōu)閦*C*P. 第一次循壞結(jié)束，進(jìn)入卜次循壞。一次循環(huán)需要的時(shí)間復(fù)雜度為： n*C*P+m*C*P+x*P+y*C*P+z*C*P=(n+m+y+z)*C*P+x*P,假設(shè)找到最佳答案的循環(huán)次數(shù)為 Go那么整個(gè)程序找到答案的時(shí)間復(fù)雜度為：fP9+(n+m+y+z)9*P+x*P)9 程序的時(shí)間復(fù)雜度為O (P*C*G)o這個(gè)程序的時(shí)間復(fù)雜度取決三個(gè)因索：染色體長(zhǎng)度，個(gè)體的數(shù)呈，遺傳的代數(shù)。這三 個(gè)因素的確定有很人的客觀性。染色體

26、的長(zhǎng)度吋以選擇36以上的任何一個(gè)，當(dāng)你把染色體個(gè) 數(shù)設(shè)置為36的時(shí)候，這樣看來(lái)這個(gè)個(gè)體將是十分完美的，它就是一條到達(dá)終點(diǎn)的最短路徑。 在這個(gè)程序開(kāi)始時(shí)，每個(gè)個(gè)體的甚因都是由計(jì)算機(jī)隨機(jī)取的，個(gè)體的不確定因素十分多。如 來(lái)每個(gè)個(gè)體的我因沒(méi)仃那條M因是通向最短的那條路徑，那么一切將不堪設(shè)想。唯一的可能 就是等待窠變。而在這程序中突變率，只有T分2 ，町想Ifu知這樣低的災(zāi)變率，什么時(shí)候 才能窠變出適合的基肉呢？當(dāng)然提高突變兒率在這樣的悄況卜創(chuàng)以増加遺傳找到終點(diǎn)的概 率。好吧，讓我們將染色體的長(zhǎng)度加人。染色體的長(zhǎng)度直接的決定了 Bob冋家的路徑的多少。 染色體越大，路徑越多，找到終點(diǎn)的概率相對(duì)也較大。

27、個(gè)體的數(shù)錄直接的決定了個(gè)體中基因 11遺傳算法及神經(jīng)網(wǎng)絡(luò)莊游觀開(kāi)發(fā)中的應(yīng)用的多樣性，個(gè)體數(shù)越人對(duì)答案的產(chǎn)生越令利。個(gè)體數(shù)超人也不能夠體現(xiàn)出程序的優(yōu)化，畢競(jìng) P*C*G的值會(huì)很人。最后就是遺傳代數(shù)，這個(gè)因素并不是由程序員來(lái)決定的，當(dāng)然也不好確 定，只能夠根據(jù)多次測(cè)試才能夠?qū)t近似值確定卜來(lái)。2.5遺傳算法的總結(jié)通過(guò)這個(gè)程序，我們対遺傳算法白了更深入的了解。遺傳算法町以解決一切求取最優(yōu)解 的問(wèn)題，但是在具體問(wèn)題面前，也許會(huì)變得不可取。大家也許會(huì)提出這樣的疑問(wèn)：這只是個(gè) 簡(jiǎn)單的尋路程序?yàn)槭裁此Ｓ眠z傳算法來(lái)做的？在利用遺傳算法來(lái)解決這個(gè)問(wèn)題之前，我們可 以通過(guò)對(duì)所仃路徑的遍歷得到一條最優(yōu)的解，而且在

28、運(yùn)算效率方而也人人的優(yōu)J遺傳算法。 再設(shè)患出II是被封死的，那通過(guò)遺傳算法來(lái)計(jì)算星優(yōu)解又會(huì)是什么樣的結(jié)果呢？我們知道遺傳算法能夠確定一些不確定的因索，遺傳算法的這一特性正好適合來(lái)找神經(jīng) 網(wǎng)絡(luò)算法中各個(gè)神經(jīng)尤的權(quán)值。如何用遺傳算法優(yōu)化神經(jīng)尤的權(quán)值？將會(huì)在卜一章介紹。13運(yùn)傳算法及神經(jīng)網(wǎng)絡(luò)在游戲開(kāi)發(fā)中的應(yīng)用3基于遺傳算法的神經(jīng)網(wǎng)絡(luò)優(yōu)化實(shí)例通過(guò)上一章對(duì)遺傳算法的硏究，我們知道遺傳算法可以找到問(wèn)題中不確定因素。這一特 性正好在這一章屮得到應(yīng)用。3. 1神經(jīng)網(wǎng)絡(luò)介紹神經(jīng)網(wǎng)絡(luò)是生物人腦思維的形式。生物的人腦冇很多的神經(jīng)尤組成，為生物受到刺激， 電流信息將會(huì)從突出末梢通過(guò)軸災(zāi)傳遞到神經(jīng)細(xì)胞中，然后神經(jīng)細(xì)胞對(duì)

29、信息進(jìn)行處理后從樹(shù) 突傳遞給卜一個(gè)神經(jīng)元。人彊的神經(jīng)元Z間進(jìn)行傳遞Z后,最終生物就做出了反應(yīng)。3.2神經(jīng)元的數(shù)學(xué)模型人丁神經(jīng)網(wǎng)絡(luò)（ANN）是模仿生物人腦而建芷起來(lái)的，它是由很多個(gè)神經(jīng)元相互的鏈接 形成的一種結(jié)構(gòu)。每一個(gè)人工神經(jīng)尤是程序模擬的簡(jiǎn)化了的生物神經(jīng)元，用ANN進(jìn)行編程所 使用的神經(jīng)元個(gè)數(shù)的多少取決F程序的解決問(wèn)題的復(fù)雜程度，讓我們來(lái)看看ANN中的神經(jīng)元 的廬山真面目.如圖3.1所示：圖中標(biāo)有w的小圈代表了 ANN中神經(jīng)冗中突出末梢的權(quán)重（weight）。ANN中的輸入（input） 和這些重磺決定了神經(jīng)網(wǎng)絡(luò)的整體活動(dòng)。所仃這些權(quán)巫都設(shè)宣為到1 Z間的隨機(jī)值。這些 權(quán)重直接的影響了神經(jīng)元

30、的輸出o他們起到的作用可能的正面的也可能是負(fù)面的。那這些權(quán) 逼是如何聯(lián)系起來(lái)決定整個(gè)神經(jīng)尤的輸出（output）的呢？我們用一個(gè)數(shù)學(xué)公式來(lái)解決：a=W1X1+W2X2+W3X3+.+wnxn在人工神經(jīng)網(wǎng)絡(luò)編程屮，這些是遠(yuǎn)遠(yuǎn)不夠的。通過(guò)對(duì)*個(gè)輸入和權(quán)值乘積的累加運(yùn)算后, 得出的值（activation）并不是能夠直接作為輸出，成為卜一個(gè)神經(jīng)元的輸入因子，正如人工 神經(jīng)網(wǎng)絡(luò)工作原理中寫(xiě)的，輸出將被限制為0或者1。在人工神經(jīng)網(wǎng)絡(luò)屮，定義了一個(gè)臨界值來(lái)限制輸出值。如果輸出的值人J臨界值，則輸出值為仁 反Z為0。用數(shù)學(xué)坐標(biāo)如圖3.2 所示：輸出值 4u -累加結(jié)果IIIIk-2 -1 0 1 2圖3.

31、2輸入輸岀的數(shù)學(xué)坐標(biāo)將這個(gè)臨界值設(shè)置為仁那么當(dāng)輸出值大jr的時(shí)候，輸出值為仁小r的時(shí)候輸出為-3.3神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)在生物人腦內(nèi)，神經(jīng)元與神經(jīng)尤直接是相互連接的，他們以某種特定的形式連接。如卜圖3.3所示,這是一個(gè)前饋網(wǎng)絡(luò)，輸入值通過(guò)輸入層傳遞到隱含層，圖中圓圈表示神經(jīng)尤.輸入層輸入的 值.經(jīng)過(guò)隱金層神經(jīng)元的計(jì)算.隱介層的輸出作為卜一層輸出層的輸入.經(jīng)過(guò)輸出層處理后得到的結(jié)果才是最終的值.輸出層隱金層輸入g神經(jīng)網(wǎng)絡(luò)并不局限這個(gè)模型，隱含的數(shù)彊也町以根據(jù)問(wèn)題需要增加或者減少。輸入輸出的 個(gè)數(shù)也是按照問(wèn)題需耍而界。接卜來(lái)我將介紹一個(gè)關(guān)神經(jīng)網(wǎng)絡(luò)的實(shí)例。15連傳算法及神經(jīng)網(wǎng)絡(luò)在游戲開(kāi)發(fā)中的應(yīng)用3.4神經(jīng)網(wǎng)

32、絡(luò)實(shí)例接卜來(lái)介紹一個(gè)用神經(jīng)網(wǎng)絡(luò)做的智能采礦程序。我們用神經(jīng)網(wǎng)絡(luò)來(lái)實(shí)現(xiàn)小乍門(mén)動(dòng)采礦，通過(guò)遺 傳算法對(duì)小車(chē)神經(jīng)元權(quán)值進(jìn)行調(diào)整,使小車(chē)能夠更加靈活地采礦。程序運(yùn)行效果如圖3.4所示:3.4 1程序運(yùn)行效果圖3. 4采礦車(chē)效果圖中右2種顏色的小車(chē)，這兩種小車(chē)都是幣個(gè)種群中的個(gè)體.紅色的小車(chē)為適應(yīng)度比較為的。綠色 的方塊代表了礦。3.4.2確定神經(jīng)網(wǎng)絡(luò)的輸入輸出在程序開(kāi)始前，我們紂確定輸入輸出的數(shù)最以及他們的內(nèi)容。酋先，我們要知道小車(chē)口身的位 置（坐標(biāo)），最近礦的位置也要作為輸入。這樣兩個(gè)坐標(biāo)就有4個(gè)輸入，分別是小車(chē)坐標(biāo)（xi, yi） 以及礦的坐標(biāo)（X2, y2）o但這些就足夠了嗎？當(dāng)然不是，小車(chē)有自

33、己的速度，速度用一個(gè)矢最表示 （X. y）o如此我們就冇了 6個(gè)輸入。在神經(jīng)網(wǎng)絡(luò)中，輸入的多少?zèng)Q定了每個(gè)神經(jīng)尤的輸入個(gè)數(shù)，從 而時(shí)間復(fù)雜度將人人的增加。在神經(jīng)網(wǎng)絡(luò)優(yōu)化中，如何減少輸入的多少是最巫耍的。在這個(gè)程序中，英實(shí)小車(chē)的坐標(biāo)和礦的坐標(biāo)可以介成一個(gè)欠量一一小車(chē)指向礦的欠鼠 （yi-xi,y2-x2）o 如圖 3.5 所示:圖3. 5小車(chē)輸入變呈輸入減少到了 4個(gè)。輸入已經(jīng)找出，那接卜來(lái)就是決定輸出的個(gè)數(shù)。輸出的個(gè)數(shù)在程序中只影響到輸出層神經(jīng)元的 個(gè)數(shù)，如果神經(jīng)網(wǎng)絡(luò)龐人的話，輸出層所消耗的CPU時(shí)間往往可以忽略。在決定輸diZijij,讓我們看卜小車(chē)是如何設(shè)計(jì)的。如圖3.6所示：神經(jīng)網(wǎng)絡(luò)的輸出

34、來(lái)控制小乍的移動(dòng)。小車(chē)的左右連個(gè)輪子動(dòng)力的人小可以決定小乍移動(dòng)的速度以及小乍的轉(zhuǎn)彎。如此看來(lái)這兩個(gè)吊就可以決定小作的移動(dòng)。那么，該神經(jīng)網(wǎng)絡(luò)的輸出為2個(gè)，一個(gè)左輪的力，另一個(gè)是右輪的力。小車(chē)的轉(zhuǎn)向值通過(guò)左輪力減去右輪力而來(lái)，小車(chē)速度則是他們的和。RotForce = mTrack - m.rTrack;轉(zhuǎn)向力度m_d Speed = mTack + mrTrack;速度或許人家會(huì)冇疑問(wèn).神經(jīng)網(wǎng)絡(luò)的輸出為o和仁但是在這個(gè)圖3.6采礦車(chē)?？?問(wèn)題中，如果輸出為0和1的,那么小車(chē)的移動(dòng)將只有4種情況。在這個(gè)程序中,我們不把神經(jīng)元的輸出限定為0和仁 取而代之,它的輸出將被限定在0到1Z間 的小數(shù)。這樣小

35、車(chē)就能夠很口然的移動(dòng)了。既然每個(gè)神經(jīng)元的輸出被限定在了 o到1 Z間的小數(shù)， 它如何來(lái)實(shí)現(xiàn)呢。卜圖是一個(gè)數(shù)學(xué)坐標(biāo)圖（如圖3.7所示）：它能夠很形象的解決這個(gè)問(wèn)題.1這個(gè)曲線的數(shù)學(xué)方程式為oMpM = ：Z7V o e為常鳳e的近似值為2.7183。p值通常被 1 + £ z設(shè)置為1.那我們需耍多少個(gè)隱含層呢？先來(lái)說(shuō)說(shuō)隱含層的好處吧。隱禽層顧名思義它并沒(méi)仃在實(shí)際的輸 出上引川，但是他對(duì)輸出有著決泄性作用。就轡如這個(gè)問(wèn)題吧。當(dāng)沒(méi)仃隱含層的時(shí)候，小車(chē)會(huì)做出 一些十分古怪的動(dòng)作，即使是遺傳很影次的個(gè)體同樣存在著這樣的問(wèn)題。眾所周知，人類(lèi)人腦很發(fā) 達(dá)，其神經(jīng)尤的個(gè)數(shù)是比他動(dòng)物的千力倍。為什么人

36、類(lèi)能統(tǒng)治地球，其原因可想而知。在這個(gè)問(wèn)題 上，我們將隱禽層的個(gè)數(shù)設(shè)置為1。這樣小乍的行為看起來(lái)會(huì)更加的門(mén)然。圖3. 7神經(jīng)元輸出值曲線3. 4 3 程序介紹介紹了那么多，讓我們看看神經(jīng)元、隱含層以及神經(jīng)網(wǎng)的定義吧。神經(jīng)元：struct SNeuron輸入的數(shù)最intm_Numlnputs;毎個(gè)輸入的權(quán)匝vector<double> m_vecWeight;SNeuron(int Numlnpu；;隱含層：struct SNeuronLayer隱介層中神經(jīng)元的數(shù)砒intm_NumNeuro ns;隱含層中所有神經(jīng)元vector<SNeuro n> m_vecNeur on

37、s;SNeuronLayer(int NumNeurons, int NumlnputsPerNeuron);神經(jīng)網(wǎng)：class CNeuralNet private:intm_Numlnputs;輸入個(gè)數(shù)intmNumOutputs;輸出個(gè)數(shù)intm_NumHiddenLayers;隱金層數(shù)吊intm_Neur on sPerHidde nLyr;隱倉(cāng)層的神經(jīng)尤數(shù)vector<SNeur on Layer>m_vecLayers; 隱會(huì)層CNeuralNet();/創(chuàng)建神經(jīng)網(wǎng)絡(luò)void CreateNet();獲取神經(jīng)網(wǎng)絡(luò)的所冇神經(jīng)元的權(quán)啦vector<double>

38、GetWeights()c onst;獲取神經(jīng)網(wǎng)絡(luò)所何神經(jīng)元的權(quán)巫個(gè)數(shù)intGetNumberOfWeights()const;替換所有權(quán)重voidPutWeights(vector<double> &weights);s型曲線函數(shù)inline double Sigmoid(double activation, double response);計(jì)算輸出vector<double> Update(vector<double> &nputs);介紹了神經(jīng)網(wǎng)絡(luò)的一些幣:耍的函數(shù)之后，遺傳算法如何加入到神經(jīng)網(wǎng)絡(luò)屮，成了接卜來(lái)要解決 的問(wèn)題。K實(shí)，遺

39、傳算法并沒(méi)仃戲接的跟神經(jīng)網(wǎng)絡(luò)進(jìn)行掛鉤，它還是很平常的遺傳算法一樣完成門(mén) C的使命(上一章尋路問(wèn)題)。唯不同的就是他的基岡染色體不是簡(jiǎn)單的0和1序列了。神經(jīng)網(wǎng)絡(luò) 中所有神經(jīng)尤的權(quán)重將成為遺傳算法屮的染色體。那么，遺傳算法屮的染色體長(zhǎng)度將由神經(jīng)網(wǎng)絡(luò)中 神經(jīng)尤來(lái)決定。如何來(lái)測(cè)試個(gè)體的適應(yīng)度才是這個(gè)程序比較核心的問(wèn)題。這并不像上一章中的尋路問(wèn)題一樣簡(jiǎn) 單了，在這個(gè)問(wèn)題中，對(duì)個(gè)體適應(yīng)度的測(cè)試并不是一步就能解決的。用觀察的方式來(lái)測(cè)試個(gè)體適應(yīng) 度，我們給每個(gè)小車(chē)2000步(游戲2000幀)的機(jī)會(huì)，當(dāng)小車(chē)吃到-個(gè)礦的時(shí)候小車(chē)的適應(yīng)度加1, 直到2000步結(jié)束。假定小車(chē)一步能夠釆到的礦個(gè)數(shù)為m,那么適應(yīng)度函數(shù)如

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);在突變程序中，我們并沒(méi)勺看到像尋路問(wèn)題中直接將基因取反操作，而是將該基因(權(quán)咆)加 匕了一個(gè)很小的數(shù)(可正可負(fù))，該數(shù)完全由電腦給出的隨機(jī)數(shù)。小車(chē)類(lèi)(遺傳算法中的個(gè)體)：class CMinesweeperprivate:小

42、乍的人腦(神經(jīng)網(wǎng)絡(luò))CNeuralNet mtsBrain;小乍所處在的位置坐標(biāo)SVector2D m_vPosition;小車(chē)的朝向SVector2D m_vLookAt;小車(chē)速度(速度包含了方向和速度人小，第一個(gè)變炭代表了轉(zhuǎn)彎的人小)doublem_dRotati on;doublem_dSpeed;存儲(chǔ)神經(jīng)網(wǎng)絡(luò)輸出，左輪力鼠以及右輪力晟doublemTrack,m_rTrack;小車(chē)適應(yīng)度doublem_dFit ness;小乍顯示比例大小(游戲中應(yīng)用較廣)doublem_dScale;最近礦的編號(hào)intmClosestMine;CMinesweeper();測(cè)試適應(yīng)度的核心，在此程序中

43、毎次遺傳需耍運(yùn)行2000次boolUpdate(vector<SVector2D> & mines);世界坐標(biāo)的轉(zhuǎn)變voidWorldTransform(vectorvSPoint> &sweeper);獲取垠近礦的坐標(biāo)SVector2D GetClosestMine(vector<SVector2D> &objects);資看是否己經(jīng)找到了一個(gè)礦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();遺傳算法核心類(lèi)：class CGenAIgprivate:所有個(gè)體的染色體vector <SGeno

45、me>m_vecPop;個(gè)體數(shù)量int mJPopSize;/個(gè)體基因長(zhǎng)度int mChromoLength;/種群的適應(yīng)度double m_dTotalFitness;顯住個(gè)體適應(yīng)度double m.dBestFitness;平均適應(yīng)度double m_dAverageFitness;放差個(gè)體適應(yīng)度double m_dWorstFitness;/垃佳個(gè)體編號(hào)int mFittestGe nome;突變概率double m_d Mutation Rate;交義組介率double m_dCrossoverRate;/記錄遺傳代數(shù)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;；肖遺傳算法的問(wèn)題解決Z后，但是我們發(fā)現(xiàn)神經(jīng)網(wǎng)絡(luò)和遺傳算法Z間似乎沒(méi)令任何聯(lián)系，所令我們繼續(xù)一個(gè)類(lèi)來(lái)將他們進(jìn)行冇機(jī)的結(jié)合。我們乂編寫(xiě)了這么一個(gè)控制類(lèi)，來(lái)把兩者聯(lián)系。接卜來(lái)讓我們揭開(kāi)這個(gè)程序的神秘面紗:class CControllerprivate:存儲(chǔ)所仃個(gè)體基因vector<SGe no me>m_vecThePopulation;個(gè)體vector<CMinesweeper> m_vecSweepers;礦vector<SVecto

49、r2 D>m_vecMi nes;23連傳算法及神經(jīng)網(wǎng)絡(luò)在游戲開(kāi)發(fā)中的應(yīng)用遺傳算法類(lèi)指什CGenAIg*intint int繪制小車(chē)所需 vector<SPoint> vector<SPoint> 存儲(chǔ)平均適應(yīng)度 vector<double> 存儲(chǔ)最佳適應(yīng)度 vector<double> 用r畫(huà)圖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;小乍步數(shù)，測(cè)試適應(yīng)度所需intmTicks;遺傳代數(shù)記錄intmGen erations;窗I I人小泊tcxClient, cyClient;void PlotStats(HDC surface);public:CController(HWND hwndMain);CController();voidRender(HDC surface);voidWorldTr