基因演算法

基因演算法是一個通用的框架，指涉流程有 selection、crossover、mutation、reinsertion 組成的進化迴圈的一系列演算法。

1. 流程

其中 selection、crossover、mutation、reinsertion 等等都是可以替換的超參數。一個進化迴圈可以用以下虛擬碼替代

def evolve(population, problem, generation) do
    population = evaluate(population, &problem.fitness_function/1, opts)
  best = hd(population)
    if problem.terminate?(population, generation) do
    best
  else
    {parents, leftover} = select(population)
    children = crossover(parents)
    mutants = mutation(population)
    offspring = children ++ mutants
    new_population = reinsertion(parents, offspring, leftover)
    evolve(new_population, problem, generation + 1)
  end
end

evaluate 比較無聊，就是評估當前 population 中每個 chromosome 並排序而已，chromosome 跟 population 的概念如下所示

chromosome 個體，表示問題的解法，用一個叫做 genes 的序列編碼表示
population 全體，表示當前代的所有解法，也可以簡單的說是 List of chromosome

有了上面的資訊，我們就可以進一步來了解 selection、crossover、mutation、reinsertion 是怎麼操作 population 的了。

1.1. selection

首先，selection 是用來選擇要拿去 crossover 的 parents。其中最常用的策略是選最好的 n 個，可以定義成

def elite(population, n) do
  population
  |> Enum.take(n)
end

而這個策略會搭配一個超參數叫做 selection rate，表示會選擇整個 population 中的多少部分出來做 parents，比如 0.8 表示 80% 的 population

1.2. crossover

crossover 會把兩個被當成 parents 的 chromosome 中的 genes 進行交換，就像 selection，它也有很多可行的策略可以替換，比如隨意選擇一點裁斷進行互換：

def single_point(p1, p2) do
  cx_point = :rand.uniform(p1.size)
  {p1_head, p1_tail} = Enum.split(p1.genes, cx_point)
  {p2_head, p2_tail} = Enum.split(p2.genes, cx_point)
  {c1, c2} = {p1_head ++ p2_tail, p2_head ++ p1_tail}

  {%Chromosome{genes: c1, size: length(c1)}, %Chromosome{genes: c2, size: length(c2)}}
end

或是根據一定機率決定要不要互換一個基因

def uniform(p1, p2, rate) do
  {c1, c2} =
    p1.genes
    |> Enum.zip(p2.genes)
    |> Enum.map(fn {x, y} ->
      if :rand.uniform() < rate do
        {x, y}
      else
        {y, x}
      end
    end)
    |> Enum.unzip()

  {%Chromosome{genes: c1, size: length(c1)}, %Chromosome{genes: c2, size: length(c2)}}
end

要是剛好解法編碼是浮點數的話，還可以選擇具備權重特性的策略

def whole_arithmetic(p1, p2, alpha) do
  {c1, c2} =
    p1.genes
    |> Enum.zip(p2.genes)
    |> Enum.map(fn {x, y} ->
      {
        x * alpha + y * (1 - alpha),
        x * (1 - alpha) + y * alpha
      }
    end)
    |> Enum.unzip()

  {%Chromosome{genes: c1, size: length(c1)}, %Chromosome{genes: c2, size: length(c2)}}
end

這個很容易就能看出來說交換的方式就是按照權重去分配，假設 alpha 大，就是自己的資訊為主，反之則是對方為主。

1.3. mutation

mutation 這個過程是選出一小部分（通常是 5%）的 chromosome 進行一些修改，就好像自然界的隨機變異，這個方法可以避免徹底陷入搜尋空間的局部中沒辦法離開。常用的策略有 flip bit

def flip(chromosome) do
  genes =
    chromosome.genes
    |> Enum.map(&Bitwise.bxor(&1, 1))

  %Chromosome{genes: genes, size: chromosome.size}
end

重排等等

def scramble(chromosome) do
  genes =
    chromosome.genes
    |> Enum.shuffle()

  %Chromosome{genes: genes, size: chromosome.size}
end

這個部分的最終結果，是生出所謂的 chlidren

1.4. reinsertion

現在，我們有 parents, chlidren, leftover, mutants 等變數，chlidren 跟 mutants 構成 offspring，reinsertion 的任務就是適當的組合這些東西變成新的 population。最常見的策略是選最好的個體出來

def elitist(parents, offspring, leftover, survival_rate) do
  old = parents ++ leftover
  n = floor(length(old) * survival_rate)

  survivors =
    old
    |> Enum.sort_by(& &1.fitness, &>=/2)
    |> Enum.take(n)

  offspring ++ survivors
end

這一步結束之後就會進入新一輪的進化

1.5. termination criteria

最後，每個問題都應該定義自己的終止條件，常用的幾種是

達到最佳結果
代數 generation 已經達到一定值
不再產生更好的解（可以比較當前的最佳解與之前最佳解的連續變化率得知）
超過公司預算
你覺得等夠久了

或是以上條件的組合等等。

2. 結論

有了上面的描述，我想你已經對基因演算法有基本的了解，要更進一步的學習編寫可以參考《Genetic Algorithms in Elixir: Solve problems using Evolution》。而要是想要在實際場域中採用，我想就需要更多的練習跟參考別人的實驗了。

3. 輔助程式

問題的定義

defmodule Problem do
  alias Types.Chromosome

  @type t :: module()

  @callback genotype :: Chromosome.t()
  @callback fitness_function(Chromosome.t()) :: number()
  @callback terminate?(Enum.t(), integer(), integer()) :: boolean()
end

個體的定義

defmodule Types.Chromosome do
  @type t :: %__MODULE__{
          genes: Enum.t(),
          size: integer(),
          fitness: number(),
          age: integer()
        }

  @enforce_keys :genes
  defstruct [:genes, size: 0, fitness: 0, age: 0]
end