# 基因演算法

## 1. 流程

```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 的概念如下所示

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

### 1.1. selection

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

### 1.2. crossover

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

```def single_point(p1, p2) do
cx_point = :rand.uniform(p1.size)

{%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
```

### 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
```

### 1.4. reinsertion

```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

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

## 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
```

Date: 2023-01-31 Tue 00:00