交叉突變 變異

一旦選擇了親本，就需要用特定的演化演算法來產生後代，這也是種群產生新個體的唯一途徑。

三種不同類型的演化運算元：

  • 精英
  • 交叉
  • 突變

根據演化演算法的不同，演化運算元也會有所不同

常見的演化演算法：

  • 遺傳演算法 Genetic Algorithms (GA)
  • 遺傳編程 Genetic Programming (GP)
  • 基於人的遺傳演算法 Human-Based Genetic Algorithm (HBGA)
  • 蟻群優化 Ant Colony Optimization (ACO)
  • 粒子群優化 Particle Swarm Optimization (PSO)

    其中，蟻群優化和粒子群優化又屬於「群體智慧演算法」

選用競爭種群的演化演算法，如遺傳編程，遺傳演算法，基於人的遺傳等，它們將利用精英，交叉和突變。一般使用如下 4 個配置：

  • 種群規模：1000
  • 精英數：3
  • 交叉百分比：80
  • 突變百分比：20

    注意，交叉和突變的百分比加起來等於 1

解的編碼，也就是 DNA，種群中的個體的表示法，一般採用定長數組表示，每個個體的 DNA 長度和其他個體相同。

交叉

大多數演化演算法都允許個體與其他任何個體交叉，也就是沒有性別之分。

此外，也不一定需要兩個親本產生一個後代，可以三個或更多親本

拼接交叉

兩個親本，產生兩個後代

隨機選擇第一個剪切點，然後加上剪切長度（訓練的一個超參數）得到第二個剪切點，之後交換兩個剪切點中間的部分
image.png

有時，我們希望孩子中沒有重複的資料，也就是「無重複的拼接」

突變

選擇突變演算法時，要考慮陣列的元素是數值的還是分類值的

改組突變 Shuffle Mutation

改變陣列中元素的順序，不修改實際的值

如親本 [1, 2, 3, 4, 5]，
產生後代 [1, 5, 3, 4, 2]

我們交換了 2 和 5 的順序，也可以交換多次

突變操作不會改變親本，我們的目的是得到後代

擾動突變

針對數值型的資料

有許多不同的實現：

  • 隨機增加或減少陣列中的每個數值，為隨機程度提供一個配置超參數
  • 也可以使用正態分佈作為擾動範圍
  • 或是提供一個擾動的概率，不是擾動所有
  • 或是隨機選擇一個元素，且只擾動該元素

精英 Elitism

直接複製

精英可以防止最佳分數倒退
image.png