遺傳演算法 GA

我們將 GA 定義為用交叉和突變優化固定長度陣列的演化演算法。

對於離散問題和連續問題，GA 的策略會稍有不同

遺傳演算法訓練任何模型，都需要 3 個主要部分：

  • 訓練設置：種群數量，精英數，交叉和突變演算法……
  • 超參數：定義模型的結構，類似神經網路模型中神經元的數目，設定好就不再更改
  • 參數（向量）：模型在訓練過程中調整的內容，遺傳演算法利用交叉和突變來調整參數向量

    遺傳演算法解決旅行商問題

我們有過採用模擬退火法解決 TSP，它是一個離散的問題
9. 離散優化
動態編程是解決 TSP 的另一種方法
image.png

與蠻力和動態編程不同，遺傳演算法不能保證找到最優解，它將找到一個「很好的」解

DNA：城市的列表，初始種群將是城市的隨機排列

  1. [Los Angles, Chicago, New York]
  2. [Chicago, Los Angles, New York]
  3. [New York, Los Angles, Chicago]

計分函數：在該路徑上行駛的總距離（或是代價、費用、機票價格……）

  1. [Los Angles, Chicago, New York] -> Score: 2,016 + 790 = 2,806
  2. [Chicago, Los Angles, New York] -> Score: 2,016 + 2,776 = 4,792
  3. [New York, Los Angles, Chicago] -> Score: 2,776 + 2,016 = 4,792

種群規模：初始化 1000 條路徑

交叉：無重複的拼接交叉，因為不能走過相同的城市

突變：改組突變，交換 DNA 中兩個（或多個）城市的順序

遺傳演算法訓練徑向基函數網路

徑向基函數網路是一個連續的問題
Radial Basic Function Network 徑向基函數網路
我們用遺傳演算法訓練之前的徑向基函數網路，訓練設置如下：

超參數 RBF 數量設置為 5，這對於鳶尾花資料集效果很好

其他應用

標籤雲

image.png
上圖為 Artificial Intelligence for Human Vol 1 的標籤雲

要統計單詞數目：

  1. 341 algorithm
  2. 239 training
  3. 203 data
  4. 201 output
  5. 198 random
  6. 192 algorithms
  7. 169 number
  8. 163 input
  9. ...

選擇一些單詞並確定它們的大小（如選 100 個，出現次數越多，單詞越大）
每個單詞通過 x 坐標，y坐標，以及方向表示，因此若選 100 個詞，向量的長度為 300

消除空白，對於空白和重疊的文本，會進行扣分，計分函數可以設計如下：

  1. 空白畫素數 + （重疊畫素數 x 100）

通過遺傳演算法最小化這個計分函數。

馬賽克藝術

image.png
由較小圖像組成較大圖像

使用計分函數比較生成的馬賽克圖像和目標圖像的差異，並最小化該差異