遺傳算法入門(連載之十) 神經網絡入門(連載預告)

.遊戲程式設計中的人工智能技術

.

(連載之10)

..

這是《遺傳算法入門》連載的最後一篇，将對連載來源進行一些說明。

0.本連載來自《遊戲程式設計中的人工智能技術》一書，是該書第三章一章的基本上完整的内容。

1.全書介紹遺傳算法(GA)和神經網絡(NN)等人工智能技術的原理，以及它們在遊戲程式設計中的應用。

2.<遊戲程式設計中的人工智能技術> 目錄(這是我交給出版社的原始手稿目錄)如下

譯者序 ………………………………………………………………………………… i

前言 ……………………………………………………………………………………vi

緻謝 ……………………………………………………………………………………ix

關于作者 ………………………………………………………………………………ix

目錄 ……………………………………………………………………………………xi

叢書編輯者的來信 ……………………………………………………………………xx

引言 …………………………………………………………………………………xxii

第一部分 Windows程式設計

第1章 Windows程式設計初步 ………………………………………………………2

1.1 曆史一瞥 ………………………………………………………………………… 2

  1.1.1 Windows 1.0 …………………………………………………………………3

  1.1.2 Windows 2.0 …………………………………………………………………3

  1.1.3 Windows 3.0和3.1 ………………………………………………………… 3

  1.1.4 Windows 9.5 …………………………………………………………………4

  1.1.5 Windows 9.8.及其後續版本 ……………………………………………… 5

1.2 Hello World! …………………………………………………………………… 5

1.3 編寫第一個Windows程式 …………………………………………………………6

  1.3.1 匈牙利表示法 ……………………………………………………………… 9

  1.3.2 第一個視窗 …………………………………………………………………11

    1.3.2.1 注冊你的視窗 …………………………………………………………12

    1.3.2.2 建立視窗 ………………………………………………………………15

  1.3.3 Windows消息循環(Message Pump)…………………………………………18

  1.3.4 Windows過程(Windows Procedure)……………………………………… 21

    1.3.4.1 WM_CREATE消息 ……………………………………………………… 23

    1.3.4.2 WM_PAINT消息 …………………………………………………………24

    1.3.4.3 WM_DESTROY消息 ………………………………………………………26

    1.3.4.4 下面怎樣辦呢？……………………………………………………… 27

  1.3.5 鍵盤輸入 ……………………………………………………………………27

    1.3.5.1 虛拟鍵代碼(Virtual Key Codes)……………………………………27

  1.3.6 嗒的嗒！…………………………………………………………………… 29

第2章 Windows程式設計進階………………………………………………………30

2.1 Windows圖形裝置接口(GDI)…………………………………………………… 30

  2.1.1 裝置描述表(Device Context, DC)……………………………………… 31

    2.1.1.1 怎樣得到句柄(Handle)呢？………………………………………… 31

  2.1.2 各種繪圖工具：畫筆、畫刷、顔色、線和形狀 …………………………33

    2.1.2.1 自定義畫筆(Pen)………………………………………………………37

    2.1.2.2 畫刷(Brushes) ……………………………………………………… 40

    2.1.2.3 形狀(Shapes)… ………………………………………………………42

2.2 文本(Text)………………… ……………………………………………………46

  2.2.1 TextOut …………………………………………………………………… 47

  2.2.2 DrawText ……………………………………………………………………47

  2.2.3 加入顔色(color)和透明度(Transparency)………………………………48

  2.2.4 實時消息抽取循環 …………………………………………………………49

2.3 如何建立後備緩沖區? … ………………………………………………………51

  2.3.1 這聽上去很棒，但怎樣來實作呢？……………………………………… 53

  2.3.2 我怎樣來使用後備緩沖器呢？…………………………………………… 55

  2.3.3 保持幹淨(Tidy)…………………………………………………………… 57

2.4 使用資源(Resources)……………………………………………………………59

  2.4.1 圖示(Icons)…………………………………………………………………60

  2.4.2 光标(Cursors)………………………………………………………………61

  2.4.3 菜單(Menu)………………………………………………………………… 62

  2.4.4 為菜單添加具體功能 ………………………………………………………63

2.5 對話框(Dialog Boxes)………………………………………………………… 65

  2.5.1 一個簡單的對話框 …………………………………………………………66

  2.5.2 一些更有用的知識 …………………………………………………………68

2.6 正确定時(Timing)……………………………………………………………… 73

2.7 結束了！………………………………………………………………………… 74

第二部分 遺傳算法

第3章 遺傳算法入門 …………………………………………………………76

3.1 鳥和蜜蜂………………………………………………………………………… 76

3.2 二進制數速成…………………………………………………………………… 81

3.3 計算機内的進化………………………………………………………………… 83

  3.3.1 什麼是賭輪選擇(Roulette Wheel Selection)？ ………………………84

  3.3.2 什麼是雜交率(Crossover Rate)？ ………………………………………85

  3.3.3 什麼是變異率(Mutation Rate)？ ……………………………………… 85

  3.3.4 咂搞的呀！………………………………………………………………… 85

3.4 幫助Bob找回家 ………………………………………………………………… 86

  3.4.1 為染色體編碼 ………………………………………………………………88

  3.4.2 Epoch方法 ………………………………………………………………… 93

  3.4.3 選取參數值 …………………………………………………………………95

  3.4.4 算子函數(Operator Functions)………………………………………… 96

    3.4.4.1 重溫賭輪選擇 …………………………………………………………96

    3.4.4.2 重溫雜交(Crossover)算子 ………………………………………… 97

    3.4.4.3 重溫變異(Mutation)算子 ……………………………………………98

  3.4.5 運作尋路人(Pathfinder)程式 ……………………………………………99

3.5 練習題 ……………………………………………………………………………99

第4章 置換碼與巡回銷售員問題 ……………………………………………100

4.1 巡回銷售員問題(TSP)………………………………………………………… 100

  4.1.1 小心陷阱 ………………………………………………………………… 102

  4.1.2  CmapTSP，SGenome，CgaTSP………………………………………… 104

    4.1.2.1 CmapTSP類 ……………………………………………………………104

    4.1.2.2 SGenome結構 …………………………………………………………107

    4.1.2.3 CgaTSP類 …………………………………………………………… 109

4.2 置換變異算子(Permutation Mutation Operator)………………………… 111

4.3 置換雜交算子(Permutation Crossover Operator)…………………………115

4.4 挑選一個适應性函數 ………………………………………………………… 116

4.5 選擇 (Selection) …………………………………………………………… 118

4.6 把一切組裝在一起 …………………………………………………………… 119

  4.6.1 #defines檔案 …………………………………………………………… 120

4.7 總結 …………………………………………………………………………… 121

4.8 練習 …………………………………………………………………………… 122

第5章 遺傳算法優化 ………………………………………………………… 123

5.1 TSP用的各種算子……………………………………………………………… 124

  5.1.1 各種置換變異算子…………………………………………………………124

    5.1.1.2 移位變異(Displacement Mutation，DM)………………………… 127

    5.1.1.3 插入變異 (Insertion Mutation，IM) ……………………………128

    5.1.1.4 倒置變異 (Inversion Mutation，IVM) ………………………… 129

    5.1.1.5 倒置移位變異(Displaced Inversion Mutation，DIM)………… 129

  5.1.2 各種置換雜交算子 ……………………………………………………… 130

    5.1.2.1 基于順序的雜交(Order-Based Crossover，OBX)…………………130

    5.1.2.2 基于位置的雜交(Position-Based Crossover，PBX)…………… 133

5.2 各種處理工具 ………………………………………………………………… 136

  5.2.1 選擇(Selection)技術 ……………………………………………………137

    5.2.1.1 精英選擇(Elitism)………………………………………………… 138

    5.2.1.2 穩态選擇(Steady State Selection)………………………………138

    5.2.1.3 适應性比例選擇(Fitness Proportionate Selection)………… 138

    5.2.1.4 賭輪選擇(Roulette Wheel Selection)……………………………138

    5.2.1.5 随機遍及取樣(Stochastic Universal Sampling)……………… 139

    5.2.1.6 錦标賽選擇(Tournament Selection)………………………………140

  5.2.2 變比技術(Scaling Techniques)…………………………………………142

    5.2.2.1 排名變比(Rank Scaling)……………………………………………142

    5.2.2.2 西格瑪變比(Sigma Scaling)……………………………………… 143

    5.2.2.3 波茲曼變比(Boltzmann Scaling)………………………………… 146

  5.2.3 其它雜交算子 …………………………………………………………… 147

    5.2.3.1 單點雜交(Single-Point Crossover)………………………………147

    5.2.3.2 兩點雜交(Two-Point Crossover)………………………………… 147

    5.2.3.3 多點雜交(Multi-Point Crossover)……………………………… 148

  5.2.4 子群技術(Niching Techniques)…………………………………………150

5.3 總結 …………………………………………………………………………… 151

5.4 練習 …………………………………………………………………………… 151

第6章 登月也不難………………………………………………………………152

6.1 建立和處理矢量圖形 ………………………………………………………… 153

  6.1.1 頂點和頂點緩沖 ………………………………………………………… 153

  6.1.2 頂點變換 ………………………………………………………………… 155

    6.1.2.1 平移(Translation)………………………………………………… 156

    6.1.2.2 變比(Scaling)……………………………………………………… 157

    6.1.2.3 旋轉(Rotation)………………………………………………………157

    6.1.2.4 綜合運用 …………………………………………………………… 159

  6.1.3 矩陣魔法(Matrix Magic)…………………………………………………161

    6.1.3.1 矩陣究竟是什麼？……………………………………………………161

    6.1.3.2 矩陣的乘法 ………………………………………………………… 162

    6.1.3.3 機關矩陣 …………………………………………………………… 163

    6.1.3.4 用矩陣變換頂點 …………………………………………………… 163

    6.1.3.5 奇妙部分來了 ……………………………………………………… 165

6.2 矢量是什麼？……………………………………………………………………166

  6.2.1 矢量加、減法 …………………………………………………………… 168

  6.2.2 計算矢量大小 …………………………………………………………… 169

  6.2.3 矢量的數量乘 …………………………………………………………… 170

  6.2.5 矢量的分解(投影)…………………………………………………………171

  6.2.6 奇妙的點積(Dot Product)……………………………………………… 172

  6.2.7 SVector2.D實用工具類 ………………………………………………… 173

6.3 絕頂聰明的牛頓 ……………………………………………………………… 173

  6.3.1 時間(Time)…………………………………………………………………174

  6.3.2 長度(Length)………………………………………………………………175

  6.3.3 品質(Mass)…………………………………………………………………175

  6.3.4 力(Force)………………………………………………………………… 176

  6.3.5 運動－速度(Velocity)……………………………………………………177

  6.3.6 運動－加速度(Acceleration)……………………………………………178

  6.3.7 感覺到了力，真快活 …………………………………………………… 180

  6.3.8 引力(Gravity)…………………………………………………………… 180

6.4 登月工程－人控制的 ………………………………………………………… 181

  6.4.1 Ccontroller類的定義 ……………………………………………………182

  6.4.2 CLander類的定義 …………………………………………………………183

  6.4.3 UpdateShip函數 ………………………………………………………… 185

6.5 遺傳算法控制的登月艇 ……………………………………………………… 191

  6.5.1 為基因組編碼 …………………………………………………………… 191

  6.5.2 雜交和變異操作 ………………………………………………………… 193

  6.5.3 适應性函數(Fitness Function)…………………………………………194

  6.5.4 更新函數(Update Function)…………………………………………… 196

  6.5.5 運作程式 ………………………………………………………………… 199

6.6 小結 …………………………………………………………………………… 199

6.7 習題 …………………………………………………………………………… 199

第三部分 神經網絡

第7章 用平常語言講神經網絡…………………………………………………202

7.1 神經網絡介紹……………………………………………………………………202

7.2 一個生物學的神經網絡-大腦 …………………………………………………203

7.3 數字版的神經網絡 …………………………………………………………… 206

  7.3.1 現在需要一些數學了 …………………………………………………… 208

  7.3.2 我知道什麼是神經細胞了，但用它來幹什麼呢？………………………210

7.4 聰明的掃雷機工程 …………………………………………………………… 212

  7.4.1 選擇輸出 ………………………………………………………………… 213

  7.4.2 選擇輸入 ………………………………………………………………… 215

  7.4.3 隐藏的神經細胞要多少？…………………………………………………216

  7.4.4 CNeuralNeth檔案 …………………………………………………………217

    7.4.4.1 SNeuron結構  ……………………………………………………… 217

    7.4.4.2 SNeuronLayer結構 ………………………………………………… 219

    7.4.4.3 CNeuralNet類 ……………………………………………………… 219

  7.4.5 神經網絡的編碼 ………………………………………………………… 224

  7.4.6 遺傳算法 ………………………………………………………………… 225

  7.4.7 掃雷機類(CMinesweeper Class)…………………………………………226

    7.4.7.1 CMinesweeper::Update函數 ……………………………………… 228

  7.4.8 CController類 ……………………………………………………………230

    7.4.8.1 CController::Update方法 ……………………………………………233

  7.4.9 運作此程式 ……………………………………………………………… 235

    7.4.1.0 功能的兩個改進 …………………………………………………… 236

    7.4.1.1 改進一 ……………………………………………………………… 236

    7.4.1.2 改進二 ……………………………………………………………… 239

7.5 最後說幾句 …………………………………………………………………… 241

7.6 練習題 ………………………………………………………………………… 241

第8章 為你的Bot提供知覺器 …………………………………………………242

8.1 回避障礙物 …………………………………………………………………… 243

  8.1.1 認識環境 ………………………………………………………………… 243

  8.1.2 适應性函數 ……………………………………………………………… 246

8.2 為您的Bot提供一個記憶器(memory)………………………………………… 248

  8.2.1 适應性函數 ……………………………………………………………… 255

  8.3 本章小結 …………………………………………………………………… 256

  8.4 練習題 ……………………………………………………………………… 257

第9章 有監督的訓練方法 …………………………………………………… 258

9.1 異或函數(XOR Function)………………………………………………………258

  9.1.1 反向傳播(BP)怎麼工作？…………………………………………………259

    9.1.1.1 調整輸出層的權重 ………………………………………………… 261

    9.1.1.2 為隐藏層調整權重 ………………………………………………… 262

    9.1.1.3 一個例子 …………………………………………………………… 262

    9.1.1.4 改變成CNeuralNet代碼 …………………………………………… 265

9.2  RecognizeIt - 滑鼠手勢的識别 ……………………………………………270

  9.2.1 用向量來表示一個手勢 ………………………………………………… 271

  9.2.2 訓練網絡(Training the Network)………………………………………273

  9.2.3 記錄并變換滑鼠資料 …………………………………………………… 275

  9.2.4 增加新的手勢 …………………………………………………………… 277

  9.2.5 CController類 ……………………………………………………………278

9.3 一些有用的技術和竅門 ……………………………………………………… 281

  9.3.1 增加動量(Momentum)………………………………………………………281

  9.3.2 過拟合(Over Fitting)……………………………………………………282

  9.3.3 柔性最大激勵函數 ……………………………………………………… 284

9.4 監督學習的應用 ……………………………………………………………… 285

9.5 一個現代寓言 ………………………………………………………………… 286

9.6 練習題 ………………………………………………………………………… 287

第10 章 實時演化 …………………………………………………………… 288

10.1 聰明的外星人(Brainy Aliens)………………………………………………288

  10.1.1 程式實作 …………………………………………………………………290

    10.1.1.1 Roswell再現了：外星人大腦的屍體解剖 ……………………… 290

    10.1.1.2 外星人的演化 ………………………………………………………295

    10.1.1.3 CController::Update方法 ………………………………………… 299

  10.1.2 運作Brainy Aliens程式 ………………………………………………… 301

10.2 練習題………………………………………………………………………… 302

第11章 神經網絡拓撲結構的演化 ……………………………………………303

11.1 競争約定(competing convention)問題 ……………………………………304

11.2 直接編碼 ………………………………………………………………………305

  11.2.1 GENITOR(基因子)…………………………………………………………305

  11.2.2 二進制矩陣編碼 …………………………………………………………306

    11.2.2.1 幾個相關問題 ………………………………………………………307

  11.2.3 基于節點的編碼 …………………………………………………………308

  11.2.4 基于路徑的編碼 …………………………………………………………311

11.3 間接編碼 ………………………………………………………………………311

  11.3.1 基于文法的編碼 …………………………………………………………312

  11.3.2 二維生長編碼 ……………………………………………………………313

11.4 NEAT(拓撲擴張的神經演化)………………………………………………… 314

  11.4.1 NEAT基因組 ………………………………………………………………315

    11.4.1.1 SLinkGene結構 …………………………………………………… 315

    11.4.1.2 SNeuronGene結構 ………………………………………………… 317

    11.4.1.3 CGenome類……………………………………………………………319

  11.4.2 算子和創新(Operators and Innovations)………………………………322

    11.4.2.1 CGenome::AddLink方法 ……………………………………………324

    11.4.2.2 CGenome::AddNeuron方法 …………………………………………329

    11.4.2.3 創新怎樣幫助我們設計一個有效的雜交操作 ……………………336

  11.4.3 物種形成(Speciation)………………………………………………… 341

    11.4.3.1 相容性測試 …………………………………………………………342

    11.4.3.2 CSpecies 類…………………………………………………………345

  11.4.4 Cga換時代方法(Cga Epoch Method) ………………………………… 348

  11.4.5 将基因組轉變為表現型 …………………………………………………354

    11.4.5.1 SLink結構……………………………………………………………355

    11.4.5.2 SNeuron結構…………………………………………………………355

    11.4.5.3 把所有東西組合在一起…………………………………………… 357

    11.4.5.4 CNeuralNet類……………………………………………………… 358

  11.4.6 運作Demo程式 ……………………………………………………………363

11.5 本章小結 ……………………………………………… …………………… 364

11.6 練習題………………………………………………………………………… 365

第四部分 附錄

附錄A WEB資源 …………………………………………………………………367

  A1 相關的URL位址 ……………………………………………………………… 367

  A2 新聞討論區 …………………………………………………………………………368

附錄B 參考書目及推薦讀物 ………………………………………………… 369

  B1 技術書 …………………………………………………………………………369

  B2 論文 ……………………………………………………………………………370

  B3 能激發思想的書 ………………………………………………………………371

  B4 好得見血的科幻小說！……………………………………………………… 372

附錄C CD光牒上有些什麼？……………………………………………………………373

技術支援 …………………………………………………………………………… 374

後記 ………………………………………………………………………………… 375

索引 ………………………………………………………………………………… 376

3.該書是英文《AI Techniques for Game Programming》的翻譯，原書在Internet上可以找到很多好評，是目前國外、國内許多遊戲學校或教育訓練班的指定教材。其特點就是淺近易懂，且提供大量實際例子，也寫得生動活潑，被認為是人工智能難得的好書，是一本指南性讀物。

4.本書中文由沙鷹和我翻譯，連載的那一章由本人翻譯，是以沒有任何侵權行為。同時也歡迎大家引用，大家可以放心。

5.本書現在已交清華大學出版社出版。這裡的第三章是較早翻譯并較早（2005年）貼出來的，系未經出版社審校的原始譯文。出版時有過一些錯誤更正，但也不可避免會引入一些新的差錯（最終出版時有不少删改，未經本人校對，十分遺憾！）。如果發現問題，請對照檢查。

6.本連載所介紹内容的完整的VC++源程式和執行程式請到下面下載下傳：

www.zzwu.cn/ai/AIch03.rar

謝謝各位讀者提出的問題，我已作了更正，插圖也已經都有了。

歡迎各位和其他網友繼續批評指正！

預　告

遊戲程式設計中的人工智能技術

<神經網絡入門>連載

 即将開始

。 (共６篇)

1：生物學的神經網絡-大腦介紹

2：數字版的神經網絡

3：聰明的掃雷機工程

4：CNeuralNet.h等代碼

5：神經網絡的編碼及遺傳算法

6：功能的兩個改進