游戲中人工智能技術(shù)-課件

1、游戲中的人工智能技術(shù)浙江大學(xué)計(jì)算機(jī)學(xué)院程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔學(xué)習(xí)內(nèi)容和目標(biāo)游戲AI的基本概念游戲中簡(jiǎn)單的AI模式游戲中常用的AI技術(shù)有限狀態(tài)機(jī)A，模糊邏輯等實(shí)現(xiàn)AI引擎的要點(diǎn)程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔GAME AI技術(shù)簡(jiǎn)介（1）GAME AI的描述使得游戲表現(xiàn)出與人的智能行為/ 活動(dòng)相類似，或者與玩家的思維/感知相符合的特性。GAME AI的實(shí)現(xiàn)技術(shù)實(shí)現(xiàn)利用充分的領(lǐng)域知識(shí)和常識(shí)客觀世界的運(yùn)動(dòng)規(guī)律(game physics)利用已有的AI技術(shù)融合娛樂性程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔GAME AI技術(shù)簡(jiǎn)介（2）游戲中涉及

2、的AI技術(shù)專家系統(tǒng)用知識(shí)表示專家的經(jīng)驗(yàn)，并在此基礎(chǔ)上作自動(dòng)推理案例式推理將輸入與數(shù)據(jù)庫中已有的案例進(jìn)行比較，選取最為相近的案例，其已有的解決方法即為輸出有限狀態(tài)機(jī)基于規(guī)則的系統(tǒng)，有限個(gè)狀態(tài)連接成一有向圖，每一條邊稱為一個(gè)轉(zhuǎn)移程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔GAME AI技術(shù)簡(jiǎn)介（3）游戲中涉及的AI技術(shù)（續(xù)）產(chǎn)生式系統(tǒng)包含多個(gè)產(chǎn)生式，每一條產(chǎn)生式由條件和動(dòng)作兩部分組成，當(dāng)產(chǎn)生式的條件滿足時(shí)，系統(tǒng)就執(zhí)行相應(yīng)的動(dòng)作決策樹給定輸入，從樹的根部開始，將輸入與當(dāng)前結(jié)點(diǎn)相比較，選擇當(dāng)前結(jié)點(diǎn)的某一個(gè)子結(jié)點(diǎn)作為下一次比較的對(duì)象。當(dāng)?shù)竭_(dá)樹的葉子時(shí)，則給出相應(yīng)的決策搜索方法找到一列動(dòng)作（或狀態(tài)

3、轉(zhuǎn)移），使得最終的結(jié)果滿足某一特定目標(biāo)程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔GAME AI技術(shù)簡(jiǎn)介（4）游戲中涉及的AI技術(shù)（續(xù)）規(guī)劃系統(tǒng)給定世界的初始狀態(tài)，以及下一步可能采取的動(dòng)作的精確定義，找到完成某個(gè)特定目標(biāo)的最優(yōu)路徑一階謂詞邏輯謂詞邏輯通過定義“物體”、“屬性”、“關(guān)系”等對(duì)當(dāng)前場(chǎng)景的狀態(tài)進(jìn)行推理情景演算用一階邏輯計(jì)算在給定情景下AI生命的反應(yīng)程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔GAME AI技術(shù)簡(jiǎn)介（5）游戲中涉及的AI技術(shù)（續(xù)）多Agent研究在多個(gè)相互競(jìng)爭(zhēng)相互合作的智能體之間所產(chǎn)生的交互智能行為人工生命多agent系統(tǒng)一種，試圖將生命系統(tǒng)中一些普遍規(guī)

4、律應(yīng)用到虛擬世界的人工智能體上群組行為(Flocking)人工生命的一類，研究協(xié)同移動(dòng)技術(shù)，例如人工智能體如何在大量的羊群中移動(dòng)程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔GAME AI技術(shù)簡(jiǎn)介（6）游戲中涉及的AI技術(shù)（續(xù)）Robotics讓機(jī)器在自然環(huán)境下交互的工作遺傳算法直接模擬生物進(jìn)化過程，通過隨機(jī)選擇、雜交和突變等對(duì)程序、算法或者一系列參數(shù)進(jìn)行操作神經(jīng)網(wǎng)絡(luò)模擬動(dòng)物神經(jīng)系統(tǒng)功能的機(jī)器學(xué)習(xí)方法通過反復(fù)調(diào)節(jié)系統(tǒng)內(nèi)部中各個(gè)神經(jīng)元之間的連接參數(shù)，使得訓(xùn)練得到的系統(tǒng)在大多數(shù)情況下作出優(yōu)或者近似優(yōu)的反應(yīng)程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔GAME AI技術(shù)簡(jiǎn)介（7）游戲中涉

5、及的AI技術(shù)（續(xù)）模糊邏輯與傳統(tǒng)二值（對(duì)-錯(cuò)）邏輯不同，模糊邏輯用實(shí)數(shù)表示物體隸屬于某一類的可能性置信網(wǎng)絡(luò)提供建立不同現(xiàn)象之間內(nèi)在因果關(guān)系的工具，并利用概率理論處理未知的和不完全的知識(shí)對(duì)當(dāng)前狀態(tài)作出判斷，并決定下一步可能的動(dòng)作以及其帶來的后果程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔GAME AI技術(shù)簡(jiǎn)介（8）GAME AI技術(shù)的分類確定型基于領(lǐng)域固定領(lǐng)域知識(shí)，模擬簡(jiǎn)單的固定行為行為型基于行為模式來模擬智能行為戰(zhàn)術(shù)型策略模擬RTS（real time strategy）其他程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔確定型AI算法確定性算法指預(yù)先編入代碼當(dāng)中的可預(yù)測(cè)的行為從最

6、簡(jiǎn)單的算法開始例如，系統(tǒng)中有一顆小行星，以某一速度作勻速直線運(yùn)動(dòng)，它在任意時(shí)刻的位置由下列公式?jīng)Q定：某種程度上，它們是智能的，但是這種智能是確定的，可預(yù)測(cè)的程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔Tracking/Chasing AI當(dāng)智能體找到目標(biāo)后，一心一意向其移動(dòng)，而不考慮任何其他的因素，例如障礙物、另外的目標(biāo)等非常機(jī)械化在每一幀中，智能體計(jì)算其到目標(biāo)的前進(jìn)方向，并根據(jù)其速度，前進(jìn)一段距離 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室 程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔Tracking/Chasing算法Tracking算法還可以做的更為真實(shí)一點(diǎn)，就像紅外導(dǎo)彈一樣：

7、在每一幀中，智能體仍然首先計(jì)算其到目標(biāo)的前進(jìn)方向這時(shí)，智能體的速度允許發(fā)生變化，并根據(jù)更新后的速度，計(jì)算下一幀的位置速度有一個(gè)上限，超過這個(gè)上限，智能體的速度將減慢，直到重新加速為止 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室 程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔Evading算法與前面的chasing算法基本相同，唯一區(qū)別是智能體沿著遠(yuǎn)離物體的方向移動(dòng) 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室 程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔追逐行為的模擬示例你追我趕Game AI/chasing and avoiding demo程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文

8、檔基于行為模式的AI在任一時(shí)間點(diǎn)，每一個(gè)智能體都按照預(yù)先設(shè)定的某種模式運(yùn)動(dòng)決策系統(tǒng)根據(jù)系統(tǒng)當(dāng)前的狀態(tài)，為每一個(gè)智能體從模式集合中選擇適當(dāng)?shù)哪Ｊ侥Ｊ矫枋隽酥悄荏w將在下面幾幀中所采取的一系列動(dòng)作特例：scripted AI，當(dāng)系統(tǒng)到達(dá)某一特定狀態(tài)（例如，每個(gè)回合的結(jié)束），系統(tǒng)運(yùn)行的一段程序（用腳本寫），決定系統(tǒng)下一步的動(dòng)作程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔典型的行為模式基本模式用一段指令定義模式寫一個(gè)解釋器解釋這段指令，并用于控制智能體的行為條件邏輯模式更為靈活的控制可以通過條件邏輯選擇模式也可以選擇本身帶有條件邏輯轉(zhuǎn)移的模式程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔編

9、程技巧非常直觀Pattern是一列數(shù)組數(shù)組的每一項(xiàng)定義智能體在該幀的速度（方向大?。┰谀M過程中，智能體就按照預(yù)先設(shè)定的參數(shù)在每一幀之間運(yùn)動(dòng)當(dāng)移動(dòng)到數(shù)組末尾時(shí)，重新選擇一個(gè)新的模式程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔行為型的AI技術(shù)示例Chasing behavior AI demo程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔策略性AI與通用問題求解AI的研究人員試圖尋找一個(gè)通用的計(jì)算模型和方法，解決所有的問題感知輸入系統(tǒng)有一個(gè)記憶模擬存儲(chǔ)系統(tǒng)推理機(jī)行為輸出系統(tǒng)博弈問題有限狀態(tài)機(jī)（FSM）規(guī)劃和搜索程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔有限狀態(tài)機(jī)狀態(tài)（要采

10、取的行為）追擊隨機(jī)走動(dòng)巡邏吃轉(zhuǎn)移（發(fā)生轉(zhuǎn)移的原因）時(shí)間片結(jié)束發(fā)生某個(gè)時(shí)間完成某個(gè)行為伐木將木頭運(yùn)往最近的倉庫足夠多木材放下木頭:返回林場(chǎng)到倉庫到林場(chǎng)程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔有限狀態(tài)機(jī)機(jī)器所有部件的總稱狀態(tài)對(duì)于層次有限狀態(tài)機(jī)而言，狀態(tài)包括各種子狀態(tài)轉(zhuǎn)移系統(tǒng)從當(dāng)前活動(dòng)狀態(tài)出發(fā)，判斷下一個(gè)活動(dòng)狀態(tài)，改變系統(tǒng)當(dāng)前的格局，并執(zhí)行相應(yīng)的操作 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室 程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔有限狀態(tài)機(jī)條件定義發(fā)生轉(zhuǎn)移的先決條件輸入和事件允許狀態(tài)機(jī)對(duì)環(huán)境變化作出反應(yīng)動(dòng)作作為狀態(tài)的一部分，或者伴隨轉(zhuǎn)移出現(xiàn) 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室

11、 程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔狀態(tài)空間圖有向圖每個(gè)結(jié)點(diǎn)表示系統(tǒng)狀態(tài)模型，每條弧表示狀態(tài)轉(zhuǎn)移所伴隨的動(dòng)作行為結(jié)點(diǎn)可以是無窮多個(gè)有些結(jié)點(diǎn)之間可能沒有弧相連接程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔特定狀態(tài)的查找結(jié)點(diǎn) 包含查找目標(biāo)終點(diǎn) 搜索路徑的結(jié)束查找空間 所有結(jié)點(diǎn)的集合目標(biāo) 所要到達(dá)的結(jié)點(diǎn)經(jīng)驗(yàn) 在一定程度上提示下一步搜索的方向解答路徑 從起始結(jié)點(diǎn)開始，到目標(biāo)的一條有向路徑程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔模糊的有限狀態(tài)機(jī)將模糊邏輯和有限狀態(tài)機(jī)結(jié)合狀態(tài)之間的遷移不再是確定的同時(shí)有多個(gè)狀態(tài)程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔有限狀

12、態(tài)機(jī)和模糊的有限狀態(tài)機(jī)示例FSM/FuFSM代碼示例隸屬度演示程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔規(guī)劃Part of intelligence is the ability to plan - Move to a goal State將系統(tǒng)表示成一系列狀態(tài)的集合通過操作（Operator）改變狀態(tài) 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室 程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔路徑規(guī)劃狀態(tài)智能體在空間的位置其他離散空間體素室內(nèi)位置局部區(qū)塊（tile）操作從一個(gè)位置移動(dòng)到其他位置 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室 程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔

13、路徑規(guī)劃算法必須對(duì)狀態(tài)空間進(jìn)行搜索，才能轉(zhuǎn)移至目標(biāo)狀態(tài)完全性如果目標(biāo)狀態(tài)存在，算法是否能夠?qū)⑵湔业?？時(shí)間復(fù)雜度空間復(fù)雜度能夠找到最優(yōu)解 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室 程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔搜索策略如何評(píng)價(jià)搜索算法時(shí)間：多長時(shí)間能夠找到解找到的解是最優(yōu)、次優(yōu)還是其他盲目搜索沒有先驗(yàn)知識(shí)僅僅知道目標(biāo)狀態(tài)是什么經(jīng)驗(yàn)搜索用經(jīng)驗(yàn)公式表示擁有的先驗(yàn)知識(shí)“經(jīng)驗(yàn)”只能作相對(duì)簡(jiǎn)單、低級(jí)的決策 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室 程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔廣度優(yōu)先搜索根結(jié)點(diǎn)-兒子結(jié)點(diǎn)-孫子結(jié)點(diǎn)缺點(diǎn)：內(nèi)存消耗大 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室

14、RootRootChild1Child2RootChild1Child2GChild1GChild2GChild3GChild4(1)(2)(3)程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔深度優(yōu)先搜索先兒子結(jié)點(diǎn)，后兄弟 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室 RootChild1GChild1GChild2RootChild1RootChild1GChild1(1)(2)(3)程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔雙向搜索同時(shí)產(chǎn)生兩棵搜索樹一棵從起點(diǎn)出發(fā)一棵從目標(biāo)出發(fā) 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室 程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔啟發(fā)式搜索定義

15、目標(biāo)函數(shù)，反映擁有的先驗(yàn)知識(shí)估計(jì)離目標(biāo)的距離估計(jì)到達(dá)目標(biāo)的花費(fèi)用上述估計(jì)指導(dǎo)路徑的搜索，加快搜索過程 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室 程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔貪婪搜索法永遠(yuǎn)沿著具有最小目標(biāo)函數(shù)值的路徑進(jìn)行搜索不一定能夠找到目標(biāo)可能得到局部最優(yōu)解，而不是全局最優(yōu) 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室 程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔A*啟發(fā)搜索考慮到貪婪搜索法不能保證找到最優(yōu)解改進(jìn) 目標(biāo)函數(shù)由兩個(gè)部分組成從當(dāng)前狀態(tài)到目標(biāo)狀態(tài)的“花費(fèi)”（估計(jì)）從初始狀態(tài)到當(dāng)前狀態(tài)的“花費(fèi)” 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室 程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多

16、媒體課件 PPT文檔基本想法貪婪搜索法對(duì)可能的后繼狀態(tài)n，計(jì)算其到目標(biāo)狀態(tài)的“花費(fèi)”h(n)，并置于一個(gè)優(yōu)先隊(duì)列中A*對(duì)可能的后繼狀態(tài)n，計(jì)算其目標(biāo)函數(shù)f(n)，并置于優(yōu)先隊(duì)列中f(n) = g(n) + h(n)，其中g(shù)(n)是從初始狀態(tài)到n的“花費(fèi)” 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室 程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔基本想法選擇下一步狀態(tài)n，使得f(n)是隊(duì)列中最小的如果h(n)估計(jì)準(zhǔn)確的話，方法是可行的 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室 程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔結(jié)束條件A*算法結(jié)束條件是：當(dāng)且僅當(dāng)目標(biāo)狀態(tài)被從優(yōu)先隊(duì)列中挑選出來 浙江

17、大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室 程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔A*算法優(yōu)先隊(duì)列PQ 初始為空V（一系列三元組(狀態(tài)，f，回溯指針)集合，表示訪問過的結(jié)點(diǎn)） 初始為空將初始結(jié)點(diǎn)S置于PQ中，V中放入(S, f(s), NULL)算法：如果V為空，退出程序，沒有解否則，從PQ中取出第一項(xiàng)，記為n如果n就是目標(biāo)結(jié)點(diǎn)，則搜索結(jié)束否則，產(chǎn)生n的后繼結(jié)點(diǎn) 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室 程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔A*算法對(duì)n的每一個(gè)后繼結(jié)點(diǎn)n計(jì)算f=g(n)+h(n)=g(n)+cost(n,n)+h(n)如果n未被訪問過，或者n曾經(jīng)被訪問過，但是記

18、錄的f(n)f，或者n已經(jīng)在PQ隊(duì)列中，但是記錄的f(n)f放置/更新n于優(yōu)先隊(duì)列中，使其對(duì)應(yīng)的目標(biāo)函數(shù)值為f添加(n, f, n)至V當(dāng)中否則忽略n 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室 程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔A*算法能否找到最優(yōu)路徑否 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室 程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔A*算法性質(zhì)令h*(n)=從目標(biāo)到n最小花費(fèi)真實(shí)值.經(jīng)驗(yàn)h稱為可行的當(dāng)且僅當(dāng)對(duì)所有的狀態(tài)n, h(n) =h*(n).可行經(jīng)驗(yàn)確保永不過估計(jì)結(jié)點(diǎn)到目標(biāo)的花費(fèi)具有可行經(jīng)驗(yàn)的A*算法一定收斂到最優(yōu)解比較費(fèi)內(nèi)存當(dāng)不存在解時(shí)，算法失敗避免對(duì)全空間進(jìn)

19、行搜索作雙向搜索程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔路徑的規(guī)劃和尋找演示A star demo最短路經(jīng)戰(zhàn)術(shù)最短路經(jīng)暴露時(shí)間有效火力視野程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔群體行為的模擬（1）物群的行為物群聚集在一起飛行，遇到另一物群時(shí)，他們將避開和分散，必要時(shí)分成多群分開后，將尋找伙伴，形成新的物群，并最終恢復(fù)原來的物群物群能夠?qū)Ω锻话l(fā)行為，能否對(duì)不斷變化的環(huán)境做出實(shí)時(shí)的反應(yīng)，并作為一個(gè)整體行動(dòng)。程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔群體行為的模擬（2）物群模擬的簡(jiǎn)單規(guī)則分離（separation）：同物群中的其他成員若即若離。列隊(duì)(alignme

20、nt)：與物群中的其他成員保持相同的航向內(nèi)聚(cohesion)：不掉隊(duì)避開（avoidance）：避開障礙物和天敵生存（survival）:必要時(shí)進(jìn)行捕食或者逃脫被吃.程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔群體行為的模擬（3）游戲中的物群行為RTS游戲的部隊(duì)的編隊(duì)模擬RPG游戲中的群體行為模擬行為模擬的實(shí)現(xiàn)無狀態(tài)不紀(jì)錄任何信息每次將重新評(píng)估其環(huán)境程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔群體行為的模擬（4）示例前進(jìn)方向不確定，但整體行動(dòng)避開障礙物飛行動(dòng)物老鷹：飛行速度快，視野廣，吃麻雀麻雀：飛行速度一般，視野一般，吃昆蟲昆蟲：飛行速度慢，視野小，不捕食，能繁殖物群的喂

21、養(yǎng)餓吃試圖接近獵物昆蟲不能滅絕程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔群體行為的模擬（4）演示: flocking demo程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔模糊邏輯傳統(tǒng)邏輯把思維過程絕對(duì)化，從而達(dá)到精確、嚴(yán)格的目的舉例：一個(gè)被討論的對(duì)象X，要么屬于某一個(gè)集合A，要么不屬于該集合，兩者比居其一，而且兩者僅居其一，決不模棱兩可對(duì)于命題：張三的性格穩(wěn)重，如何判斷這一命題的真假？程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔模糊邏輯對(duì)于上述的例子，模糊邏輯允許我們用一個(gè)0,1的實(shí)數(shù)表示X屬于A的隸屬程度。傳統(tǒng)邏輯即隸屬程度只能從0和1之間選擇的情況對(duì)于“性格穩(wěn)重”

22、這個(gè)模糊概念，我們能夠用“一點(diǎn)而也不穩(wěn)重”、“不太穩(wěn)重”、“不好說”、“有點(diǎn)穩(wěn)重”、“挺穩(wěn)重”、“很穩(wěn)重”等沒有明確界限的詞語形容程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔模糊邏輯的應(yīng)用將重心轉(zhuǎn)移至物體屬于某個(gè)集合的隸屬程度上在AI領(lǐng)域的主要應(yīng)用為決策行為選擇輸入、輸出過濾 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室 程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔符合邏輯操作設(shè)A,B,C均為U中的模糊集模糊并若對(duì)8x2U，均有c=max(A(x),B(x)，則稱C為A與B的模糊并模糊交若對(duì)8x2U，均有c=min(A(x),B(x)，則稱C為A與B的模糊交 浙江大學(xué)CAD&CG 國家

23、重點(diǎn)實(shí)驗(yàn)室 程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔例子 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室 大約6英尺長的高的人程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔與 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室 程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔或 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室 程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔非 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室 程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔模糊控制舉例：車輛駕駛前提：兩輛車之間不能相撞在模糊邏輯中的實(shí)現(xiàn)：用兩個(gè)變量描述每一輛車當(dāng)前時(shí)刻，車與前面一輛車之間的距離d當(dāng)前時(shí)刻與前一

24、時(shí)刻距離的差d 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室 程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔模糊控制If d=0且d=兩個(gè)車位長，保持現(xiàn)有速度If d0且d0且d兩個(gè)車位長，加快速度 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室 程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔小結(jié)模糊邏輯和模糊控制被廣泛用于游戲當(dāng)中當(dāng)你想模擬人的思維模式時(shí)模糊邏輯同樣能夠用于表示無生命時(shí)間給定風(fēng)速和方向，問云如何移動(dòng) 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室 程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔小結(jié)在游戲中，模糊邏輯還能夠用于對(duì)抗敵人的人工智能非玩家的角色（描述某個(gè)販賣情報(bào)的人對(duì)你的信任

25、程度）Flocking算法 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室 程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔神經(jīng)網(wǎng)絡(luò)簡(jiǎn)化的人腦模型人腦大概有1012個(gè)神經(jīng)元每一個(gè)神經(jīng)元都能夠處理和發(fā)送信息神經(jīng)元的三個(gè)主要組成部分：細(xì)胞體，神經(jīng)元新陳代謝的中心樹突，接收來自其他神經(jīng)元的信號(hào)軸突，向其他神經(jīng)元發(fā)送信號(hào) 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室 程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔神經(jīng)網(wǎng)絡(luò)生物學(xué)發(fā)現(xiàn)神經(jīng)元是人腦的基本組成部分如果將神經(jīng)元看作結(jié)點(diǎn)，它們之間的連接看作弧，則這些神經(jīng)元組成一個(gè)稠密連接的圖雖然單個(gè)神經(jīng)元的工作過程較簡(jiǎn)單，當(dāng)大量神經(jīng)元連成一個(gè)網(wǎng)絡(luò)并動(dòng)態(tài)運(yùn)行時(shí)，系統(tǒng)是非常

26、復(fù)雜的 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室 程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔人工神經(jīng)元模型是人類大腦神經(jīng)元的簡(jiǎn)化N個(gè)輸入1個(gè)輸出作用函數(shù) 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室 程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔人工神經(jīng)網(wǎng)絡(luò)基礎(chǔ)McCulloch and Pitts與1943年第一次提出人工神經(jīng)網(wǎng)絡(luò)概念一個(gè)處理單元將接收的信息x0,x1,xn-1通過用W0,W1,Wn-1表示互聯(lián)強(qiáng)度，以點(diǎn)積的形式合成自己的輸入，并將輸入與以某種方式設(shè)定的閾值相比較，再經(jīng)某種形式的作用函數(shù)f的轉(zhuǎn)換，得到該單元的輸出yf可以是階梯函數(shù)、線性或者是指數(shù)形式的函數(shù) 浙江大學(xué)CAD

27、&CG 國家重點(diǎn)實(shí)驗(yàn)室 程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔神經(jīng)計(jì)算神經(jīng)網(wǎng)絡(luò)是基于人腦的平行體系結(jié)構(gòu)與多處理器計(jì)算機(jī)相類似獨(dú)立處理單元高度互聯(lián)簡(jiǎn)單消息傳遞適應(yīng)性交互 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室 程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔訓(xùn)練神經(jīng)網(wǎng)絡(luò)初始化：隨機(jī)設(shè)定各條邊的W值給定一對(duì)（輸入，輸出），已有神經(jīng)網(wǎng)絡(luò)根據(jù)輸入計(jì)算輸出，將其與預(yù)計(jì)輸出相比較，并根據(jù)兩者之間的差值調(diào)整各條邊的W值神經(jīng)網(wǎng)絡(luò)也可以自動(dòng)學(xué)習(xí)，但是相比訓(xùn)練，收斂速度要慢很多 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室 程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔訓(xùn)練神經(jīng)網(wǎng)絡(luò)對(duì)已知樣本分類的正

28、確率對(duì)未知樣本分類的正確率過訓(xùn)練 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室 程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔對(duì)邏輯關(guān)系“或”的學(xué)習(xí) 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室 網(wǎng)絡(luò)有兩個(gè)輸入，一個(gè)輸出，都是二元變量輸出為1如果 W0I0 +W1I1 + Wb 0 輸出為0如果 W0 I0+W1 I1 + Wb = 0 程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔調(diào)整權(quán)重權(quán)重的修改與期望輸出和實(shí)際輸出之差成正比是學(xué)習(xí)率，d是期望輸出，y是實(shí)際輸出，xi是輸入 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室 I0I1Desired output000011101111程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教

29、學(xué)設(shè)計(jì) 多媒體課件 PPT文檔示例當(dāng)?shù)?步時(shí)，(d-y)=0，因此W=0，則訓(xùn)練結(jié)束 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室 程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔多層感知器反向傳播網(wǎng)絡(luò)徑向基函數(shù)網(wǎng)絡(luò) 能夠?qū)W習(xí)任意復(fù)雜的模式輸入、輸出均可以為實(shí)數(shù) 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室 程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔反向傳播網(wǎng)絡(luò)三層：輸入層、隱含層、輸出層，前一層的輸出是后一層的輸入是一種前饋網(wǎng)，不形成回路可以有多個(gè)隱含層三層結(jié)點(diǎn)已經(jīng)能夠產(chǎn)生任意復(fù)雜的映射 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室 程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔典型BP網(wǎng)絡(luò)結(jié)構(gòu)

30、 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室 作用函數(shù)：程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔BP學(xué)習(xí)算法將全部權(quán)值與結(jié)點(diǎn)的閾值設(shè)置為一個(gè)小的隨機(jī)值加在輸入與輸出計(jì)算實(shí)際輸出修正權(quán)值從輸出結(jié)點(diǎn)開始，反向的向第一隱含層（即存在多層隱含層時(shí)最接近輸入層的隱含層）傳播由總誤差誘發(fā)的權(quán)值修正在到達(dá)預(yù)定誤差精度和循環(huán)次數(shù)后退出，否則轉(zhuǎn)步驟2重復(fù) 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室 程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔徑向基函數(shù)網(wǎng)絡(luò)前饋網(wǎng)絡(luò)，只有一個(gè)隱含層能夠表示任意復(fù)雜的映射隱含層的作用函數(shù)稱為徑向基函數(shù)，在某一點(diǎn)函數(shù)有最大值，而離開該點(diǎn)一定距離的值被映射為0一般的，取徑向基函

31、數(shù)為高斯函數(shù) 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室 程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔訓(xùn)練RBF網(wǎng)絡(luò)需要決定隱含層包含多少個(gè)結(jié)點(diǎn)每個(gè)結(jié)點(diǎn)作用函數(shù)訓(xùn)練過程首先通過觀察訓(xùn)練樣本，決定作用函數(shù)的形狀用前面的delta規(guī)則修正權(quán)重應(yīng)用物體分類函數(shù)插值 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室 程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔小結(jié)BP和RBF網(wǎng)絡(luò)是兩個(gè)常用的神經(jīng)網(wǎng)絡(luò)模型當(dāng)系統(tǒng)遇到新的未知樣本，RBF可以通過添加隱含層結(jié)點(diǎn)加強(qiáng)系統(tǒng)的判斷能力兩者都能處理動(dòng)態(tài)時(shí)序數(shù)據(jù) 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室 程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔神經(jīng)網(wǎng)絡(luò)應(yīng)用當(dāng)我們

32、沒辦法明確給出一個(gè)算法解時(shí)當(dāng)我們有充足的樣本時(shí)當(dāng)我們需要從數(shù)據(jù)中獲得一點(diǎn)什么時(shí)我們可以使用神經(jīng)網(wǎng)絡(luò) 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室 程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔神經(jīng)網(wǎng)絡(luò)應(yīng)用對(duì)于那些傳統(tǒng)計(jì)算解決不了的問題，神經(jīng)網(wǎng)絡(luò)也無法解決神經(jīng)網(wǎng)絡(luò)可以簡(jiǎn)化某些特定問題的解答，例如，從數(shù)據(jù)中提煉一個(gè)模型對(duì)于數(shù)據(jù)形成過程未知或者復(fù)雜的問題而言，神經(jīng)網(wǎng)絡(luò)能夠幫助我們從一定程度上理解內(nèi)在的規(guī)律 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室 程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔神經(jīng)網(wǎng)絡(luò)應(yīng)用投資分析筆跡分析過程控制市場(chǎng)調(diào)查狀態(tài)監(jiān)控 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室 程序設(shè)計(jì) 網(wǎng)絡(luò)課

33、件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔神經(jīng)網(wǎng)絡(luò)與游戲判斷所處的環(huán)境決定下一步的動(dòng)作用于表示積累的經(jīng)驗(yàn) 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室 程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔神經(jīng)元網(wǎng)絡(luò)坦克的射擊訓(xùn)練示例Neuro network demo程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔遺傳算法遺傳算法的基本思想是基于Darwin進(jìn)化論和Mendel的遺傳學(xué)說的 適者生存原理 基因遺傳原理（基因突變和基因雜交）遺傳算法一般用于在難易預(yù)測(cè)其中各個(gè)因素之間相互作用的大型系統(tǒng)上作非線性優(yōu)化 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室 程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔遺

34、傳算法工作原理選擇初始群體觀察每個(gè)個(gè)體對(duì)環(huán)境的適應(yīng)能量選擇重復(fù)雜交變異觀察每個(gè)個(gè)體對(duì)環(huán)境的適應(yīng)能量選擇直到滿足某些結(jié)束條件 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室 程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔進(jìn)化和遺傳學(xué)的概念 串（string）它是個(gè)體(Individual)的形式，在算法中為二進(jìn)制串，并且對(duì)應(yīng)于遺傳學(xué)中的染色體(Chromosome)群體(Population)個(gè)體的集合稱為群體，串是群體的元素基因(Gene)基因是串中的元素，基因用于表示個(gè)體的特征。例如有一個(gè)串S1011，則其中的1，0，1，1這4個(gè)元素分別稱為基因。它們的值稱為等位基因(Alletes)基因位置(

35、Gene Position)一個(gè)基因在串中的位置稱為基因位置，有時(shí)也簡(jiǎn)稱基因位?；蛭恢糜纱淖笙蛴矣?jì)算，例如在串S1101中，0的基因位置是3?；蛭恢脤?duì)應(yīng)于遺傳學(xué)中的地點(diǎn)(Locus)程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔進(jìn)化和遺傳學(xué)的概念基因特征值(Gene Feature)在用串表示整數(shù)時(shí)，基因的特征值與二進(jìn)制數(shù)的權(quán)一致；例如在串S=1011中，基因位置3中的1，它的基因特征值為2；基因位置1中的1，它的基因特征值為8非線性它對(duì)應(yīng)遺傳學(xué)中的異位顯性(Epistasis)適應(yīng)度(Fitness)表示某一個(gè)體對(duì)于環(huán)境的適應(yīng)程度程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文

36、檔選擇這是從群體中選擇出較適應(yīng)環(huán)境的個(gè)體。這些選中的個(gè)體用于繁殖下一代。故有時(shí)也稱這一操作為再生(Reproduction)。由于在選擇用于繁殖下一代的個(gè)體時(shí)，是根據(jù)個(gè)體對(duì)環(huán)境的適應(yīng)度而決定其繁殖量的，故而有時(shí)也稱為非均勻再生(differential reproduction) 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室 程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔選擇根據(jù)適者生存原則選擇下一代的個(gè)體。在選擇時(shí)，以適應(yīng)度為選擇原則。適應(yīng)度準(zhǔn)則體現(xiàn)了適者生存，不適應(yīng)者淘汰的自然法則給出目標(biāo)函數(shù)f，則f(bi)稱為個(gè)體bi的適應(yīng)度 為選中bi為下一代個(gè)體的次數(shù) 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)

37、驗(yàn)室 程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔選擇性質(zhì)：適應(yīng)度較高的個(gè)體，繁殖下一代的數(shù)目較多。適應(yīng)度較小的個(gè)體，繁殖下一代的數(shù)目較少；甚至被淘汰。選擇產(chǎn)生對(duì)環(huán)境適應(yīng)能力較強(qiáng)的后代。對(duì)于問題求解角度來講，就是選擇出和最優(yōu)解較接近的中間解。 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室 程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔交叉 對(duì)于選中用于繁殖下一代的個(gè)體，隨機(jī)地選擇兩個(gè)個(gè)體的相同位置，按交叉概率P，在選中的位置實(shí)行交換。這個(gè)過程反映了隨機(jī)信息交換；目的在于產(chǎn)生新的基因組合，也即產(chǎn)生新的個(gè)體。交叉時(shí)，可實(shí)行單點(diǎn)交叉或多點(diǎn)交叉 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室 程序設(shè)計(jì) 網(wǎng)

38、絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔交叉例如有個(gè)體S1=100101S2=010111選擇它們的左邊3位進(jìn)行交叉操作，則有S1=010101S2=100111一般而言，交叉概率P的取值為0.25-0.75 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室 程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔變異 根據(jù)生物遺傳中基因變異的原理，以變異概率Pm對(duì)某些個(gè)體的某些位執(zhí)行變異。在變異時(shí)，對(duì)執(zhí)行變異的串的對(duì)應(yīng)位求反，即把1變?yōu)?，把0變?yōu)?。變異概率Pm與生物變異極小的情況一致，所以，Pm的取值較小，一般取0.01-0.2例如有個(gè)體S101011，對(duì)其的第1、4位置的基因進(jìn)行變異，則有S=0011

39、11單靠變異不能在求解中得到好處。但是，它能保證算法過程不會(huì)產(chǎn)生無法進(jìn)化的單一群體。因?yàn)樵谒械膫€(gè)體一樣時(shí)，交叉是無法產(chǎn)生新的個(gè)體的，這時(shí)只能靠變異產(chǎn)生新的個(gè)體。也就是說，變異增加了全局優(yōu)化的特質(zhì)。 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室 程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔組合選擇雜交進(jìn)化選擇使得適者生存雜交將不同個(gè)體中優(yōu)良的基因保存下來，創(chuàng)造新的具有各方面優(yōu)勢(shì)的品種選擇變異在優(yōu)化中加入隨機(jī)擾動(dòng)遺傳算法是采用隨機(jī)方法進(jìn)行最優(yōu)解搜索，選擇體現(xiàn)了向最優(yōu)解迫近，變異體現(xiàn)了全局最優(yōu)解的復(fù)蓋 壞的變異將最終被選擇出去 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室 程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多

40、媒體課件 PPT文檔組合選擇雜交突變遺傳算法的力量 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室 程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔遺傳算法P:= 以隨機(jī)方式產(chǎn)生串的集合如果最優(yōu)個(gè)體的適應(yīng)度還未達(dá)到給定的閥值，或者最優(yōu)個(gè)體的適應(yīng)度和群體適應(yīng)度仍然在上升令fi=Fitness(pi), i=1n令P= SelectionNewPopulation(p,f)隨機(jī)兩兩組合P中的個(gè)體對(duì)每一對(duì)個(gè)體，以概率C進(jìn)行雜交對(duì)P中的每一個(gè)個(gè)體，以概率M進(jìn)行編譯令P=P 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室 程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔結(jié)束條件最優(yōu)個(gè)體的適應(yīng)度達(dá)到給定的閥值最優(yōu)個(gè)體

41、的適應(yīng)度和群體適應(yīng)度不再上升達(dá)到預(yù)先設(shè)定的最大循環(huán)數(shù)（繁衍代數(shù)）群體中的所有個(gè)體具有相同的屬性 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室 程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔遺傳算法參數(shù)群體大小n交叉概率Pc變異概率Pm 繁衍代數(shù)其他：取決與具體的操作和結(jié)束條件 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室 程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔編碼方式 除二進(jìn)制編碼外，問題的各種參數(shù)可以用實(shí)數(shù)向量構(gòu)成子串 選擇：與串類似變異：將按照高斯概率分布的隨機(jī)變量g加到某個(gè)參數(shù)上 浙江大學(xué)CAD&CG 國家重點(diǎn)實(shí)驗(yàn)室 程序設(shè)計(jì) 網(wǎng)絡(luò)課件 教學(xué)設(shè)計(jì) 多媒體課件 PPT文檔遺傳規(guī)劃遺傳算法的一個(gè)分支，由Koza提出，與遺傳算法用串的形式表示所不同的是，遺傳規(guī)劃的表示是計(jì)算機(jī)程序它是一種自動(dòng)編程技術(shù)終結(jié)符集合：變量、常數(shù)函數(shù)集合：程序中的函數(shù)用分析樹的形式表