# Selection and Reproduction 選擇與繁殖

## Generic Evolutionary Algorithm 通用進化算法​

$X_0$ := generate initial population of solutionsterminationflag := falset := 0Evaluate the fitness of each individual in $X_0$.while (terminationflag != true)  Selection: Select parents from $X_t$ based on their fitness.  Variation: Breed new individuals by applying variation operators to parents Fitness calculation: Evaluate the fitness of new individuals. Reproduction: Generate population $X_{t+1}$ by replacing least-fit individuals  t := t + 1  If a termination criterion is met: terminationflag := trueOutput $x_best$

## Selection 選擇​

• Selection is not a search operator but influences search performance significantly 選擇不是搜索運算符，但會顯著影響搜索性能

• Selection usually is performed before variation operators: selects better fit individuals for breeding 選擇通常在變異算子之前進行：選擇更適合的個體進行育種

• Selection: emphasises on exploiting better solutions in a population: 強調在群體中開發更好的解決方案：

• Select one or more copies of good solutions. 選擇一份或多份好的解決方案。
• Inferior solutions will be selected but with a much less chance 將選擇較差的解決方案，但機會要小得多
• Question: Why we still select those inferior solutions? 為什麼我們仍然選擇那些劣質的解決方案？

## Selection Schemes 選擇方案​

• Fitness Proportional Selection (FPS) 適應度比例選擇
• Ranking Selection 排名選擇
• Truncation Selection 截斷選擇
• Tournament Selection 比賽選擇
• $(μ + λ)$ and $(μ, λ)$ selection

## Fitness Proportional Selection 適應度比例選擇​

• Fitness Proportional Selection (FPS) 適應度比例選擇 = Roulette Wheel Selection 輪盤選擇

• Selecting individuals $i$ with a probability: 選擇個體 $i$ 的概率為：

$P(i) = \frac{f_i}{\sum_{j=1}^N f_j}$

where $f_i$ is the fitness of individual $i$ and $N$ is the population size. 其中 $f_i$ 是個體 $i$ 的適應度，$N$ 是群體大小。

• Does not allow negative fitness values. 不允許負的適應度值。

• Individual with higher fitness will be less likely to be eliminated, but still a chance that they may be (Discuss later). 適應度較高的個體不太可能被淘汰，但仍有機會被淘汰（稍後討論）。

• Individual with low fitness values may survive the selection process: allows some weak individuals who may help escaping from local optima. 適應度較低的個體可能會在選擇過程中存活下來：允許一些弱的個體，這些個體可能有助於逃離局部最優解。

## Fitness Proportional Selection: scaling 適應度比例選擇：縮放​

• Observation: in early generations, there might be a domination of "super individuals" with very high fitness values 在早期代，可能會有一些"超級個體"擁有非常高的適應度值

• Question: what problems will "super individuals" cause in EAs? 什麼問題會導致"超級個體"在 EAs 中產生？

• Observation: In later generations, there might be no much separation among individuals 在後代，個體之間可能沒有太多的分離

• Question: What are the problems in EAs with no much separation among individuals? 在沒有太多分離的 EAs 中有什麼問題？

• Problems:

• Question: what problems will "super individuals" cause in EAs? 什麼問題會導致"超級個體"在 EAs 中產生？
• Answer: Premature convergence to a local optimum 早期收斂到局部最優解
• Question: What problems will caused in EAs with no much separation among individuals? 在沒有太多分離的 EAs 中有什麼問題？
• Question: How to maintain the same selection pressure throughout the run? 如何在運行過程中維持相同的選擇壓力？

• Solution: replace raw fitness values $f_{i}$ with a scaled fitness value $f_{i}^{\prime}$ 用縮放的適應度值 $f_{i}^{\prime}$ 代替原始的適應度值 $f_{i}$

• Linear scaling:

$$f_i^{\prime}=a+b \cdot f_i$$

where a and b are constants, usually set as $a = max(f)$ and $b = min(f)/M < 1$, where $f = f1,f2,··· ,M$

## Ranking Selection 排名選擇​

• Sort population size of M from best to worst according to their fitness values: 根據適應度值將群體大小為 M 的個體從最好到最差進行排序：

$$x{(M-1)}^{\prime}, x{(M-2)}^{\prime}, x{(M-3)}^{\prime}, \cdots, x{(0)}^{\prime}$$

• Select the top $γ$-ranked individual $x_{γ}^{\prime}$ with probability $p(γ)$, where $p(γ)$ is a ranking function, e.g.

• linear ranking
• exponential ranking
• power ranking
• geometric ranking

## Linear Ranking Function 線性排名函數​

• Linear ranking function:

$p(\gamma)=\frac{\alpha+(\beta-\alpha) \cdot \frac{\gamma}{M-1}}{M}$

where implies $\alpha + \beta = 2$ and 1 ≤ $\beta$ ≤ 2

• In expectation

• Best individual, i.e., $γ = M - 1$, reproduced $\beta$ times: $p(M-1) = \frac{\beta}{M}$.
• Worst individual, i.e., $γ = 0$, reproduced $\alpha$ times: $p(0) = \frac{\alpha}{M}$.
• Question: how to set $\alpha$ and $\beta$ to make EA behave like a random search algorithm?

## Other Ranking Functions 其他排名選擇函數​

Give you different, usually non-linear relationships between the rank γ and the selection probability $p(γ)$:

• Power ranking function:

$p(\gamma)=\frac{\alpha+(\beta - \alpha) \cdot \left(\frac{\gamma}{M-1}\right)^k}{C}$

• Geometric ranking function:

$p(\gamma)=\frac{\alpha \cdot (1 - \alpha)^{M-1-\gamma}}{C}$

• Exponential ranking function:

$p(\gamma)=\frac{1-e^{-\gamma}}{C}$

where $C$ is a normalising factor and $0<\alpha<\beta$.

## Truncation Selection 截斷選擇​

• Steps:
• Rank individuals by fitness values
• Select some proportion, $k$, (e.g. $k = \frac{1}{2}$), of the top ranked individuals
• Usually, k = 0.5 (top 50%) or k = 0.3 (top 30%)
• Can be seen as the simplest, deterministic ranking selection

## Tournament Selection 比賽選擇​

• Tournament selection with tournament size k:
• Step 1: Randomly sample a subset $P\prime$ of k individuals from population $P$
• Step 2: Select the individual in $P\prime$ with highest fitness Repeat Steps 1 and 2 until enough offspring are created
• Among the most popular selection methods in genetic algorithms
• Binary tournament selection $(k = 2)$ is the most popular one

## $(μ + λ)$ and $(μ, λ)$ selection​

• First proposed in Evolution Strategies. 首先在演化策略中提出。
• $(μ + λ)$ selection:
• Parent population of size $μ$
• Generate $λ$ offspring from randomly chosen parents
• Next population is $μ$ best individuals among parents and offspring
• $(μ, λ)$ selection where $λ > μ$
• Parent population of size $μ$
• Generate $λ$ offspring from randomly chosen parents
• Next population is $μ$ best individuals among offspring

## Selection Pressure 選擇壓力​

• Selection pressure: degree to which selection emphasises on the better individuals. 選擇壓力：選擇強調優秀個體的程度。
• Question 1: How does selection pressure affect the balance between exploitation and exploration? 選擇壓力如何影響探索和開發之間的平衡？
• Higher selection pressure → exploitation → fast convergence to local optimum, e.g., premature
• Low selection pressure → exploration → slow convergence
• Question 2: Given an EA with a selection scheme, how will you measure selection pressure? 給定一個具有選擇方案的 EA，如何衡量選擇壓力？
• Answer 2: Take-over time $τ^∗$ [1]:
• Let's assume population size is M and initial population with one unique fittest individual $x^{∗}$
• Apply selection repeatedly with no other operators.
• $τ^∗$ is number of generations until population consists of $x^{∗}$ only.
• Higher take-over time means lower selection pressure.

[1]: Goldberg, D. E. and Deb, K. (1991). A comparative analysis of selection schemes used in genetic algorithms. In Foundations of Genetic Algorithms. Morgan Kaufmann.

Selection functionτ∗ ≈Note
Fitness prop.$\frac{M ln M}{c}$Assuming a power law objective function f (x) = xc
Linear ranking$\frac{2ln(M-1)}{\beta-1}$1≤β≤2
Truncation$ln M$
Tournament$\frac{M}{k}$tournament size $k$
$(μ+λ)$$\frac{lnλ}{ln(\frac{λ}{μ})}$

## Reproduction 繁殖​

• Reproduction: to control how genetic algorithm creates the next generation 繁殖：控制遺傳演算法如何創建下一代

• Generational vs Steady state 世代 vs 穩態

• Generational EAs: also called standard EAs, use all new individuals after variations to replace the worse individuals in the old population to create a new population (then selection) 世代式 EA：也稱為標準 EA，在變異後使用所有新個體來取代舊世代中較差的個體以創建新世代（然後選擇）
• Steady state EAs: only use a few or even one single new individual to replace the old population at any one time 堅定狀態 EA：只在任何一個時間點使用一些甚至一個新個體來取代舊世代
• n-Elitisms: always copy the N best individuals to the next generation n-Elitisms：總是將 N 個最好的個體複製到下一代

• Generational gap: the overlap (i.e., individuals that did not go through any variation operators) between the old and new generations. 世代間隙：舊世代和新世代之間的重疊（即沒有經過任何變異運算子的個體）。

## Conclusion 結論​

• Selection and reproduction are two important ingredients of EAs 選擇和復制是 EA 的兩個重要組成部分
• The major difference between selection methods is based on: 選擇方法之間的主要差異在於：
• Relative fitness: fitness proportional selection 相對適應度：適應度比例選擇
• Ranking: tournament, truncation, (μ + λ) and (μ, λ) 排名：比賽，截斷，（μ + λ）和（μ，λ）
• Takeover time: quantitative measure of selection pressure 接管時間：選擇壓力的定量衡量
• Selection pressure is used to control the balance between exploitation and exploration: 選擇壓力用於控制探索和開發之間的平衡：
• Higher selection pressure → exploitation → fast convergence to local optimum, e.g., premature 更高的選擇壓力 → 利用 → 快速收斂到局部最優，例如，過早
• Low selection pressure → exploration → slow convergence 低選擇壓力 → 探索 → 慢速收斂