1、游戲中的人工智能技術(shù),浙江大學計算機學院,學習內(nèi)容和目標,游戲AI的基本概念 游戲中簡單的AI模式 游戲中常用的AI技術(shù) 有限狀態(tài)機 A，模糊邏輯等 實現(xiàn)AI引擎的要點,GAME AI技術(shù)簡介（1）,GAME AI的描述 使得游戲表現(xiàn)出與人的智能行為/ 活動相類似，或者與玩家的思維/感知相符合的特性。 GAME AI的實現(xiàn) 技術(shù)實現(xiàn) 利用充分的領(lǐng)域知識和常識 客觀世界的運動規(guī)律(game physics) 利用已有的AI技術(shù) 融合娛樂性,GAME AI技術(shù)簡介（2）,游戲中涉及的AI技術(shù) 專家系統(tǒng) 用知識表示專家的經(jīng)驗，并在此基礎(chǔ)上作自動推理 案例式推理 將輸入與數(shù)據(jù)庫中已有的案例進行比較，選

2、取最為相近的案例，其已有的解決方法即為輸出 有限狀態(tài)機 基于規(guī)則的系統(tǒng)，有限個狀態(tài)連接成一有向圖，每一條邊稱為一個轉(zhuǎn)移,GAME AI技術(shù)簡介（3）,游戲中涉及的AI技術(shù)（續(xù)） 產(chǎn)生式系統(tǒng) 包含多個產(chǎn)生式，每一條產(chǎn)生式由條件和動作兩部分組成，當產(chǎn)生式的條件滿足時，系統(tǒng)就執(zhí)行相應的動作 決策樹 給定輸入，從樹的根部開始，將輸入與當前結(jié)點相比較，選擇當前結(jié)點的某一個子結(jié)點作為下一次比較的對象。當?shù)竭_樹的葉子時，則給出相應的決策 搜索方法 找到一列動作（或狀態(tài)轉(zhuǎn)移），使得最終的結(jié)果滿足某一特定目標,GAME AI技術(shù)簡介（4）,游戲中涉及的AI技術(shù)（續(xù)） 規(guī)劃系統(tǒng) 給定世界的初始狀態(tài)，以及下一步可能

3、采取的動作的精確定義，找到完成某個特定目標的最優(yōu)路徑 一階謂詞邏輯 謂詞邏輯通過定義“物體”、“屬性”、“關(guān)系”等對當前場景的狀態(tài)進行推理 情景演算 用一階邏輯計算在給定情景下AI生命的反應,GAME AI技術(shù)簡介（5）,游戲中涉及的AI技術(shù)（續(xù)） 多Agent 研究在多個相互競爭相互合作的智能體之間所產(chǎn)生的交互智能行為 人工生命 多agent系統(tǒng)一種，試圖將生命系統(tǒng)中一些普遍規(guī)律應用到虛擬世界的人工智能體上 群組行為(Flocking) 人工生命的一類，研究協(xié)同移動技術(shù)，例如人工智能體如何在大量的羊群中移動,GAME AI技術(shù)簡介（6）,游戲中涉及的AI技術(shù)（續(xù)） Robotics 讓機器在

4、自然環(huán)境下交互的工作 遺傳算法 直接模擬生物進化過程，通過隨機選擇、雜交和突變等對程序、算法或者一系列參數(shù)進行操作 神經(jīng)網(wǎng)絡(luò) 模擬動物神經(jīng)系統(tǒng)功能的機器學習方法 通過反復調(diào)節(jié)系統(tǒng)內(nèi)部中各個神經(jīng)元之間的連接參數(shù)，使得訓練得到的系統(tǒng)在大多數(shù)情況下作出優(yōu)或者近似優(yōu)的反應,GAME AI技術(shù)簡介（7）,游戲中涉及的AI技術(shù)（續(xù)） 模糊邏輯 與傳統(tǒng)二值（對-錯）邏輯不同，模糊邏輯用實數(shù)表示物體隸屬于某一類的可能性 置信網(wǎng)絡(luò) 提供建立不同現(xiàn)象之間內(nèi)在因果關(guān)系的工具，并利用概率理論處理未知的和不完全的知識 對當前狀態(tài)作出判斷，并決定下一步可能的動作以及其帶來的后果,GAME AI技術(shù)簡介（8）,GAME A

5、I技術(shù)的分類 確定型 基于領(lǐng)域固定領(lǐng)域知識，模擬簡單的固定行為 行為型 基于行為模式來模擬智能行為 戰(zhàn)術(shù)型 策略模擬 RTS（real time strategy） 其他,確定型AI算法,確定性算法指預先編入代碼當中的可預測的行為 從最簡單的算法開始 例如，系統(tǒng)中有一顆小行星，以某一速度作勻速直線運動，它在任意時刻的位置由下列公式?jīng)Q定： 某種程度上，它們是智能的，但是這種智能是確定的，可預測的,Tracking/Chasing AI,當智能體找到目標后，一心一意向其移動，而不考慮任何其他的因素，例如障礙物、另外的目標等 非常機械化 在每一幀中，智能體計算其到目標的前進方向，并根據(jù)其速度，前進一

6、段距離,浙江大學CAD&CG 國家重點實驗室,Tracking/Chasing算法,Tracking算法還可以做的更為真實一點，就像紅外導彈一樣： 在每一幀中，智能體仍然首先計算其到目標的前進方向 這時，智能體的速度允許發(fā)生變化，并根據(jù)更新后的速度，計算下一幀的位置 速度有一個上限，超過這個上限，智能體的速度將減慢，直到重新加速為止,浙江大學CAD&CG 國家重點實驗室,Evading算法,與前面的chasing算法基本相同，唯一區(qū)別是智能體沿著遠離物體的方向移動,浙江大學CAD&CG 國家重點實驗室,追逐行為的模擬示例,你追我趕Game AI/chasing and avoiding dem

7、o,基于行為模式的AI,在任一時間點，每一個智能體都按照預先設(shè)定的某種模式運動 決策系統(tǒng)根據(jù)系統(tǒng)當前的狀態(tài)，為每一個智能體從模式集合中選擇適當?shù)哪Ｊ?模式描述了智能體將在下面幾幀中所采取的一系列動作 特例：scripted AI，當系統(tǒng)到達某一特定狀態(tài)（例如，每個回合的結(jié)束），系統(tǒng)運行的一段程序（用腳本寫），決定系統(tǒng)下一步的動作,典型的行為模式,基本模式 用一段指令定義模式 寫一個解釋器解釋這段指令，并用于控制智能體的行為 條件邏輯模式 更為靈活的控制 可以通過條件邏輯選擇模式 也可以選擇本身帶有條件邏輯轉(zhuǎn)移的模式,編程技巧,非常直觀 Pattern是一列數(shù)組 數(shù)組的每一項定義智能體在該幀的速

8、度（方向大小） 在模擬過程中，智能體就按照預先設(shè)定的參數(shù)在每一幀之間運動 當移動到數(shù)組末尾時，重新選擇一個新的模式,行為型的AI技術(shù)示例,Chasing behavior AI demo,策略性AI與通用問題求解,AI的研究人員試圖尋找一個通用的計算模型和方法，解決所有的問題 感知輸入系統(tǒng) 有一個記憶模擬存儲系統(tǒng) 推理機 行為輸出系統(tǒng) 博弈問題 有限狀態(tài)機（FSM） 規(guī)劃和搜索,有限狀態(tài)機,狀態(tài)（要采取的行為） 追擊 隨機走動 巡邏 吃 轉(zhuǎn)移（發(fā)生轉(zhuǎn)移的原因） 時間片結(jié)束 發(fā)生某個時間 完成某個行為,伐木,將木頭運往最近的倉庫,足夠多木材,放下木頭: 返回林場,到倉庫,到林場,有限狀態(tài)機,機器

9、 所有部件的總稱 狀態(tài) 對于層次有限狀態(tài)機而言，狀態(tài)包括各種子狀態(tài) 轉(zhuǎn)移 系統(tǒng)從當前活動狀態(tài)出發(fā)，判斷下一個活動狀態(tài)，改變系統(tǒng)當前的格局，并執(zhí)行相應的操作,浙江大學CAD&CG 國家重點實驗室,有限狀態(tài)機,條件 定義發(fā)生轉(zhuǎn)移的先決條件 輸入和事件 允許狀態(tài)機對環(huán)境變化作出反應 動作 作為狀態(tài)的一部分，或者伴隨轉(zhuǎn)移出現(xiàn),浙江大學CAD&CG 國家重點實驗室,狀態(tài)空間圖,有向圖 每個結(jié)點表示系統(tǒng)狀態(tài)模型，每條弧表示狀態(tài)轉(zhuǎn)移所伴隨的動作行為 結(jié)點可以是無窮多個 有些結(jié)點之間可能沒有弧相連接,特定狀態(tài)的查找,結(jié)點 包含查找目標 終點 搜索路徑的結(jié)束 查找空間 所有結(jié)點的集合 目標 所要到達的結(jié)點 經(jīng)驗

10、 在一定程度上提示下一步搜索的方向 解答路徑 從起始結(jié)點開始，到目標的一條有向路徑,模糊的有限狀態(tài)機,將模糊邏輯和有限狀態(tài)機結(jié)合 狀態(tài)之間的遷移不再是確定的 同時有多個狀態(tài),有限狀態(tài)機和模糊的有限狀態(tài)機示例,FSM/FuFSM 代碼示例 隸屬度 演示,規(guī)劃,Part of intelligence is the ability to plan - Move to a goal State 將系統(tǒng)表示成一系列狀態(tài)的集合 通過操作（Operator）改變狀態(tài),浙江大學CAD&CG 國家重點實驗室,路徑規(guī)劃,狀態(tài) 智能體在空間的位置 其他離散空間 體素 室內(nèi)位置 局部區(qū)塊（tile） 操作 從一個位

11、置移動到其他位置,浙江大學CAD&CG 國家重點實驗室,路徑規(guī)劃算法,必須對狀態(tài)空間進行搜索，才能轉(zhuǎn)移至目標狀態(tài) 完全性 如果目標狀態(tài)存在，算法是否能夠?qū)⑵湔业剑?時間復雜度 空間復雜度 能夠找到最優(yōu)解,浙江大學CAD&CG 國家重點實驗室,搜索策略,如何評價搜索算法 時間：多長時間能夠找到解 找到的解是最優(yōu)、次優(yōu)還是其他 盲目搜索 沒有先驗知識 僅僅知道目標狀態(tài)是什么 經(jīng)驗搜索 用經(jīng)驗公式表示擁有的先驗知識 “經(jīng)驗”只能作相對簡單、低級的決策,浙江大學CAD&CG 國家重點實驗室,廣度優(yōu)先搜索,根結(jié)點-兒子結(jié)點-孫子結(jié)點 缺點：內(nèi)存消耗大,浙江大學CAD&CG 國家重點實驗室,Root,Ro

12、ot,Child1,Child2,(1),(2),(3),深度優(yōu)先搜索,先兒子結(jié)點，后兄弟,浙江大學CAD&CG 國家重點實驗室,(1),(2),(3),雙向搜索,同時產(chǎn)生兩棵搜索樹 一棵從起點出發(fā) 一棵從目標出發(fā),浙江大學CAD&CG 國家重點實驗室,啟發(fā)式搜索,定義目標函數(shù)，反映擁有的先驗知識 估計離目標的距離 估計到達目標的花費 用上述估計指導路徑的搜索，加快搜索過程,浙江大學CAD&CG 國家重點實驗室,貪婪搜索法,永遠沿著具有最小目標函數(shù)值的路徑進行搜索 不一定能夠找到目標 可能得到局部最優(yōu)解，而不是全局最優(yōu),浙江大學CAD&CG 國家重點實驗室,A*啟發(fā)搜索,考慮到貪婪搜索法不能保

13、證找到最優(yōu)解 改進 目標函數(shù)由兩個部分組成 從當前狀態(tài)到目標狀態(tài)的“花費”（估計） 從初始狀態(tài)到當前狀態(tài)的“花費”,浙江大學CAD&CG 國家重點實驗室,基本想法,貪婪搜索法 對可能的后繼狀態(tài)n，計算其到目標狀態(tài)的“花費”h(n)，并置于一個優(yōu)先隊列中 A* 對可能的后繼狀態(tài)n，計算其目標函數(shù)f(n)，并置于優(yōu)先隊列中 f(n) = g(n) + h(n)，其中g(shù)(n)是從初始狀態(tài)到n的“花費”,浙江大學CAD&CG 國家重點實驗室,基本想法,選擇下一步狀態(tài)n，使得f(n)是隊列中最小的 如果h(n)估計準確的話，方法是可行的,浙江大學CAD&CG 國家重點實驗室,結(jié)束條件,A*算法結(jié)束條件是

14、：當且僅當目標狀態(tài)被從優(yōu)先隊列中挑選出來,浙江大學CAD&CG 國家重點實驗室,A*算法,優(yōu)先隊列PQ 初始為空 V（一系列三元組(狀態(tài)，f，回溯指針)集合，表示訪問過的結(jié)點） 初始為空 將初始結(jié)點S置于PQ中，V中放入(S, f(s), NULL) 算法： 如果V為空，退出程序，沒有解 否則，從PQ中取出第一項，記為n 如果n就是目標結(jié)點，則搜索結(jié)束 否則，產(chǎn)生n的后繼結(jié)點,浙江大學CAD&CG 國家重點實驗室,A*算法,對n的每一個后繼結(jié)點n 計算f=g(n)+h(n)=g(n)+cost(n,n)+h(n) 如果n未被訪問過，或者n曾經(jīng)被訪問過，但是記錄的f(n)f，或者n已經(jīng)在PQ隊列

15、中，但是記錄的f(n)f 放置/更新n于優(yōu)先隊列中，使其對應的目標函數(shù)值為f 添加(n, f, n)至V當中 否則忽略n,浙江大學CAD&CG 國家重點實驗室,A*算法能否找到最優(yōu)路徑,否,浙江大學CAD&CG 國家重點實驗室,A*算法性質(zhì),令h*(n)=從目標到n最小花費真實值. 經(jīng)驗h稱為可行的當且僅當對所有的狀態(tài)n, h(n) =h*(n). 可行經(jīng)驗確保永不過估計結(jié)點到目標的花費 具有可行經(jīng)驗的A*算法一定收斂到最優(yōu)解 比較費內(nèi)存 當不存在解時，算法失敗 避免對全空間進行搜索 作雙向搜索,路徑的規(guī)劃和尋找演示,A star demo 最短路經(jīng) 戰(zhàn)術(shù)最短路經(jīng) 暴露時間 有效火力 視野,群

16、體行為的模擬（1）,物群的行為 物群聚集在一起飛行，遇到另一物群時，他們將避開和分散，必要時分成多群 分開后，將尋找伙伴，形成新的物群，并最終恢復原來的物群 物群能夠?qū)Ω锻话l(fā)行為，能否對不斷變化的環(huán)境做出實時的反應，并作為一個整體行動 。,群體行為的模擬（2）,物群模擬的簡單規(guī)則 分離（separation）：同物群中的其他成員若即若離。 列隊(alignment)：與物群中的其他成員保持相同的航向 內(nèi)聚(cohesion)：不掉隊 避開（avoidance）：避開障礙物和天敵 生存（survival）:必要時進行捕食或者逃脫被吃 .,群體行為的模擬（3）,游戲中的物群行為 RTS游戲的部隊的

17、編隊模擬 RPG游戲中的群體行為模擬 行為模擬的實現(xiàn) 無狀態(tài) 不紀錄任何信息 每次將重新評估其環(huán)境,群體行為的模擬（4）,示例 前進方向不確定，但整體行動 避開障礙物 飛行動物 老鷹：飛行速度快，視野廣，吃麻雀 麻雀：飛行速度一般，視野一般，吃昆蟲 昆蟲：飛行速度慢，視野小，不捕食，能繁殖 物群的喂養(yǎng) 餓吃試圖接近獵物 昆蟲不能滅絕,群體行為的模擬（4）,演示: flocking demo,模糊邏輯,傳統(tǒng)邏輯把思維過程絕對化，從而達到精確、嚴格的目的 舉例：一個被討論的對象X，要么屬于某一個集合A，要么不屬于該集合，兩者比居其一，而且兩者僅居其一，決不模棱兩可 對于命題：張三的性格穩(wěn)重，如何判

18、斷這一命題的真假？,模糊邏輯,對于上述的例子，模糊邏輯允許我們用一個0,1的實數(shù)表示X屬于A的隸屬程度。傳統(tǒng)邏輯即隸屬程度只能從0和1之間選擇的情況 對于“性格穩(wěn)重”這個模糊概念，我們能夠用“一點而也不穩(wěn)重”、“不太穩(wěn)重”、“不好說”、“有點穩(wěn)重”、“挺穩(wěn)重”、“很穩(wěn)重”等沒有明確界限的詞語形容,模糊邏輯的應用,將重心轉(zhuǎn)移至物體屬于某個集合的隸屬程度上 在AI領(lǐng)域的主要應用為 決策 行為選擇 輸入、輸出過濾,浙江大學CAD&CG 國家重點實驗室,符合邏輯操作,設(shè)A,B,C均為U中的模糊集 模糊并 若對8x2U，均有c=max(A(x),B(x)，則稱C為A與B的模糊并 模糊交 若對8x2U，均

19、有c=min(A(x),B(x)，則稱C為A與B的模糊交,浙江大學CAD&CG 國家重點實驗室,例子,浙江大學CAD&CG 國家重點實驗室,大約6英尺,長的高的人,與,浙江大學CAD&CG 國家重點實驗室,或,浙江大學CAD&CG 國家重點實驗室,非,浙江大學CAD&CG 國家重點實驗室,模糊控制,舉例：車輛駕駛 前提：兩輛車之間不能相撞 在模糊邏輯中的實現(xiàn)： 用兩個變量描述每一輛車 當前時刻，車與前面一輛車之間的距離d 當前時刻與前一時刻距離的差d,浙江大學CAD&CG 國家重點實驗室,模糊控制,If d=0且d=兩個車位長，保持現(xiàn)有速度 If d0且d兩個車位長，加快速度,浙江大學CAD&

20、CG 國家重點實驗室,小結(jié),模糊邏輯和模糊控制被廣泛用于游戲當中 當你想模擬人的思維模式時 模糊邏輯同樣能夠用于表示無生命時間 給定風速和方向，問云如何移動,浙江大學CAD&CG 國家重點實驗室,小結(jié),在游戲中，模糊邏輯還能夠用于 對抗敵人的人工智能 非玩家的角色（描述某個販賣情報的人對你的信任程度） Flocking算法,浙江大學CAD&CG 國家重點實驗室,神經(jīng)網(wǎng)絡(luò),簡化的人腦模型 人腦大概有1012個神經(jīng)元 每一個神經(jīng)元都能夠處理和發(fā)送信息 神經(jīng)元的三個主要組成部分： 細胞體，神經(jīng)元新陳代謝的中心 樹突，接收來自其他神經(jīng)元的信號 軸突，向其他神經(jīng)元發(fā)送信號,浙江大學CAD&CG 國家重點

21、實驗室,神經(jīng)網(wǎng)絡(luò),生物學發(fā)現(xiàn) 神經(jīng)元是人腦的基本組成部分 如果將神經(jīng)元看作結(jié)點，它們之間的連接看作弧，則這些神經(jīng)元組成一個稠密連接的圖 雖然單個神經(jīng)元的工作過程較簡單，當大量神經(jīng)元連成一個網(wǎng)絡(luò)并動態(tài)運行時，系統(tǒng)是非常復雜的,浙江大學CAD&CG 國家重點實驗室,人工神經(jīng)元模型,是人類大腦神經(jīng) 元的簡化 N個輸入 1個輸出 作用函數(shù),浙江大學CAD&CG 國家重點實驗室,人工神經(jīng)網(wǎng)絡(luò)基礎(chǔ),McCulloch and Pitts與1943年第一次提出人工神經(jīng)網(wǎng)絡(luò)概念 一個處理單元將接收的信息x0,x1,xn-1通過用W0,W1,Wn-1表示互聯(lián)強度，以點積的形式合成自己的輸入，并將輸入與以某種方式

22、設(shè)定的閾值相比較，再經(jīng)某種形式的作用函數(shù)f的轉(zhuǎn)換，得到該單元的輸出y f可以是階梯函數(shù)、線性或者是指數(shù)形式的函數(shù),浙江大學CAD&CG 國家重點實驗室,神經(jīng)計算,神經(jīng)網(wǎng)絡(luò)是基于人腦的平行體系結(jié)構(gòu) 與多處理器計算機相類似 獨立處理單元 高度互聯(lián) 簡單消息傳遞 適應性交互,浙江大學CAD&CG 國家重點實驗室,訓練神經(jīng)網(wǎng)絡(luò),初始化：隨機設(shè)定各條邊的W值 給定一對（輸入，輸出），已有神經(jīng)網(wǎng)絡(luò)根據(jù)輸入計算輸出，將其與預計輸出相比較，并根據(jù)兩者之間的差值調(diào)整各條邊的W值 神經(jīng)網(wǎng)絡(luò)也可以自動學習，但是相比訓練，收斂速度要慢很多,浙江大學CAD&CG 國家重點實驗室,訓練神經(jīng)網(wǎng)絡(luò),對已知樣本分類的正確率 對

23、未知樣本分類的正確率 過訓練,浙江大學CAD&CG 國家重點實驗室,對邏輯關(guān)系“或”的學習,浙江大學CAD&CG 國家重點實驗室,網(wǎng)絡(luò)有兩個輸入，一個輸出，都是二元變量 輸出為1如果 W0I0 +W1I1 + Wb 0 輸出為0如果 W0 I0+W1 I1 + Wb = 0,調(diào)整權(quán)重,權(quán)重的修改與期望輸出和實際輸出之差成正比 是學習率，d是期望輸出，y是實際輸出，xi是輸入,浙江大學CAD&CG 國家重點實驗室,示例,當?shù)?步時，(d-y)=0，因此W=0，則訓練結(jié)束,浙江大學CAD&CG 國家重點實驗室,多層感知器,反向傳播網(wǎng)絡(luò) 徑向基函數(shù)網(wǎng)絡(luò) 能夠?qū)W習任意復雜的模式 輸入、輸出均可以為實數(shù)

24、,浙江大學CAD&CG 國家重點實驗室,反向傳播網(wǎng)絡(luò),三層：輸入層、隱含層、輸出層，前一層的輸出是后一層的輸入 是一種前饋網(wǎng)，不形成回路 可以有多個隱含層 三層結(jié)點已經(jīng)能夠產(chǎn)生任意復雜的映射,浙江大學CAD&CG 國家重點實驗室,典型BP網(wǎng)絡(luò)結(jié)構(gòu),浙江大學CAD&CG 國家重點實驗室,作用函數(shù)：,BP學習算法,將全部權(quán)值與結(jié)點的閾值設(shè)置為一個小的隨機值 加在輸入與輸出 計算實際輸出 修正權(quán)值 從輸出結(jié)點開始，反向的向第一隱含層（即存在多層隱含層時最接近輸入層的隱含層）傳播由總誤差誘發(fā)的權(quán)值修正 在到達預定誤差精度和循環(huán)次數(shù)后退出，否則轉(zhuǎn)步驟2重復,浙江大學CAD&CG 國家重點實驗室,徑向基函

25、數(shù)網(wǎng)絡(luò),前饋網(wǎng)絡(luò)，只有一個隱含層 能夠表示任意復雜的映射 隱含層的作用函數(shù)稱為徑向基函數(shù)，在某一點函數(shù)有最大值，而離開該點一定距離的值被映射為0 一般的，取徑向基函數(shù)為高斯函數(shù),浙江大學CAD&CG 國家重點實驗室,訓練RBF網(wǎng)絡(luò),需要決定 隱含層包含多少個結(jié)點 每個結(jié)點作用函數(shù) 訓練過程 首先通過觀察訓練樣本，決定作用函數(shù)的形狀 用前面的delta規(guī)則修正權(quán)重 應用 物體分類 函數(shù)插值,浙江大學CAD&CG 國家重點實驗室,小結(jié),BP和RBF網(wǎng)絡(luò)是兩個常用的神經(jīng)網(wǎng)絡(luò)模型 當系統(tǒng)遇到新的未知樣本，RBF可以通過添加隱含層結(jié)點加強系統(tǒng)的判斷能力 兩者都能處理動態(tài)時序數(shù)據(jù),浙江大學CAD&CG 國

26、家重點實驗室,神經(jīng)網(wǎng)絡(luò)應用,當我們沒辦法明確給出一個算法解時 當我們有充足的樣本時 當我們需要從數(shù)據(jù)中獲得一點什么時 我們可以使用神經(jīng)網(wǎng)絡(luò),浙江大學CAD&CG 國家重點實驗室,神經(jīng)網(wǎng)絡(luò)應用,對于那些傳統(tǒng)計算解決不了的問題，神經(jīng)網(wǎng)絡(luò)也無法解決 神經(jīng)網(wǎng)絡(luò)可以簡化某些特定問題的解答，例如，從數(shù)據(jù)中提煉一個模型 對于數(shù)據(jù)形成過程未知或者復雜的問題而言，神經(jīng)網(wǎng)絡(luò)能夠幫助我們從一定程度上理解內(nèi)在的規(guī)律,浙江大學CAD&CG 國家重點實驗室,神經(jīng)網(wǎng)絡(luò)應用,投資分析 筆跡分析 過程控制 市場調(diào)查 狀態(tài)監(jiān)控,浙江大學CAD&CG 國家重點實驗室,神經(jīng)網(wǎng)絡(luò)與游戲,判斷所處的環(huán)境 決定下一步的動作 用于表示積累的

27、經(jīng)驗,浙江大學CAD&CG 國家重點實驗室,神經(jīng)元網(wǎng)絡(luò),坦克的射擊訓練示例 Neuro network demo,遺傳算法,遺傳算法的基本思想是基于Darwin進化論和Mendel的遺傳學說的 適者生存原理 基因遺傳原理（基因突變和基因雜交） 遺傳算法一般用于在難易預測其中各個因素之間相互作用的大型系統(tǒng)上作非線性優(yōu)化,浙江大學CAD&CG 國家重點實驗室,遺傳算法工作原理,選擇初始群體 觀察每個個體對環(huán)境的適應能量 選擇 重復 雜交 變異 觀察每個個體對環(huán)境的適應能量 選擇 直到滿足某些結(jié)束條件,浙江大學CAD&CG 國家重點實驗室,進化和遺傳學的概念,串（string） 它是個體(Indiv

28、idual)的形式，在算法中為二進制串，并且對應于遺傳學中的染色體(Chromosome) 群體(Population) 個體的集合稱為群體，串是群體的元素 基因(Gene) 基因是串中的元素，基因用于表示個體的特征。例如有一個串S1011，則其中的1，0，1，1這4個元素分別稱為基因。它們的值稱為等位基因(Alletes) 基因位置(Gene Position) 一個基因在串中的位置稱為基因位置，有時也簡稱基因位?；蛭恢糜纱淖笙蛴矣嬎?，例如在串S1101中，0的基因位置是3?；蛭恢脤谶z傳學中的地點(Locus),進化和遺傳學的概念,基因特征值(Gene Feature) 在用串表示

29、整數(shù)時，基因的特征值與二進制數(shù)的權(quán)一致；例如在串S=1011中，基因位置3中的1，它的基因特征值為2；基因位置1中的1，它的基因特征值為8 非線性 它對應遺傳學中的異位顯性(Epistasis) 適應度(Fitness) 表示某一個體對于環(huán)境的適應程度,選擇,這是從群體中選擇出較適應環(huán)境的個體。這些選中的個體用于繁殖下一代。故有時也稱這一操作為再生(Reproduction)。由于在選擇用于繁殖下一代的個體時，是根據(jù)個體對環(huán)境的適應度而決定其繁殖量的，故而有時也稱為非均勻再生(differential reproduction),浙江大學CAD&CG 國家重點實驗室,選擇,根據(jù)適者生存原則選擇

30、下一代的個體。在選擇時，以適應度為選擇原則。適應度準則體現(xiàn)了適者生存，不適應者淘汰的自然法則 給出目標函數(shù)f，則f(bi)稱為個體bi的適應度 為選中bi為下一代個體的次數(shù),浙江大學CAD&CG 國家重點實驗室,選擇,性質(zhì)： 適應度較高的個體，繁殖下一代的數(shù)目較多。 適應度較小的個體，繁殖下一代的數(shù)目較少；甚至被淘汰。 選擇產(chǎn)生對環(huán)境適應能力較強的后代。對于問題求解角度來講，就是選擇出和最優(yōu)解較接近的中間解。,浙江大學CAD&CG 國家重點實驗室,交叉,對于選中用于繁殖下一代的個體，隨機地選擇兩個個體的相同位置，按交叉概率P，在選中的位置實行交換。這個過程反映了隨機信息交換；目的在于產(chǎn)生新的基

31、因組合，也即產(chǎn)生新的個體。交叉時，可實行單點交叉或多點交叉,浙江大學CAD&CG 國家重點實驗室,交叉,例如有個體 S1=100101 S2=010111 選擇它們的左邊3位進行交叉操作，則有 S1=010101 S2=100111 一般而言，交叉概率P的取值為0.25-0.75,浙江大學CAD&CG 國家重點實驗室,變異,根據(jù)生物遺傳中基因變異的原理，以變異概率Pm對某些個體的某些位執(zhí)行變異。在變異時，對執(zhí)行變異的串的對應位求反，即把1變?yōu)?，把0變?yōu)?。變異概率Pm與生物變異極小的情況一致，所以，Pm的取值較小，一般取0.01-0.2 例如有個體S101011，對其的第1、4位置的基因進行

32、變異，則有S=001111 單靠變異不能在求解中得到好處。但是，它能保證算法過程不會產(chǎn)生無法進化的單一群體。因為在所有的個體一樣時，交叉是無法產(chǎn)生新的個體的，這時只能靠變異產(chǎn)生新的個體。也就是說，變異增加了全局優(yōu)化的特質(zhì)。,浙江大學CAD&CG 國家重點實驗室,組合,選擇雜交進化 選擇使得適者生存 雜交將不同個體中優(yōu)良的基因保存下來，創(chuàng)造新的具有各方面優(yōu)勢的品種 選擇變異在優(yōu)化中加入隨機擾動 遺傳算法是采用隨機方法進行最優(yōu)解搜索，選擇體現(xiàn)了向最優(yōu)解迫近，變異體現(xiàn)了全局最優(yōu)解的復蓋 壞的變異將最終被選擇出去,浙江大學CAD&CG 國家重點實驗室,組合,選擇雜交突變遺傳算法的力量,浙江大學CAD&

33、CG 國家重點實驗室,遺傳算法,P:= 以隨機方式產(chǎn)生串的集合 如果最優(yōu)個體的適應度還未達到給定的閥值，或者最優(yōu)個體的適應度和群體適應度仍然在上升 令fi=Fitness(pi), i=1n 令P= SelectionNewPopulation(p,f) 隨機兩兩組合P中的個體 對每一對個體，以概率C進行雜交 對P中的每一個個體，以概率M進行編譯 令P=P,浙江大學CAD&CG 國家重點實驗室,結(jié)束條件,最優(yōu)個體的適應度達到給定的閥值 最優(yōu)個體的適應度和群體適應度不再上升 達到預先設(shè)定的最大循環(huán)數(shù)（繁衍代數(shù)） 群體中的所有個體具有相同的屬性,浙江大學CAD&CG 國家重點實驗室,遺傳算法參數(shù),群體大小n 交叉概率Pc 變異概率Pm 繁衍代數(shù) 其他：取決與具體的操作和結(jié)束條件,浙江大學CAD&CG 國家重點實驗室,編碼方式,除二進制編碼外，問題的各種參數(shù)可以用實數(shù)向量構(gòu)成子串 選擇：與串類似 變異：將按照高斯概率分布的隨機變量g加到某個參數(shù)上,浙江大學CAD&CG 國家重點實驗室,遺傳規(guī)劃,遺傳算法的一個分支，由Koza提出，與遺傳算法用串的形式表示所不同的是，遺傳規(guī)劃的表示是計算機程序 它是一種自動編程技術(shù) 終結(jié)符集合：變量、常數(shù) 函數(shù)集合：程序中的函數(shù) 用分析樹的形式表示中間產(chǎn)生的程序,