Skip to main content

Selection and Reproduction 選擇與繁殖

Generic Evolutionary Algorithm 通用進化算法

$X_0$ := generate initial population of solutions
terminationflag := false
t := 0
Evaluate 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 := true
Output $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 ii with a probability: 選擇個體 ii 的概率為:

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

    where fif_i is the fitness of individual ii and NN is the population size. 其中 fif_i 是個體 ii 的適應度,NN 是群體大小。

  • 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 中有什麼問題?
    • Answer: Slow convergence 慢速收斂
  • Question: How to maintain the same selection pressure throughout the run? 如何在運行過程中維持相同的選擇壓力?

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

  • Linear scaling:

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

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

    Figure 1: Fitness scaling using linear scaling

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γx_{γ}^{\prime} with probability p(γ)p(γ), where p(γ)p(γ) is a ranking function, e.g.

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

Linear Ranking Function 線性排名函數

  • Linear ranking function:

    p(γ)=α+(βα)γM1Mp(\gamma)=\frac{\alpha+(\beta-\alpha) \cdot \frac{\gamma}{M-1}}{M}

    where implies α+β=2\alpha + \beta = 2 and 1 ≤ β\beta ≤ 2

  • In expectation

    • Best individual, i.e., γ=M1γ = M - 1, reproduced β\beta times: p(M1)=βMp(M-1) = \frac{\beta}{M}.
    • Worst individual, i.e., γ=0γ = 0, reproduced α\alpha times: p(0)=αMp(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(γ)p(γ):

  • Power ranking function:

    p(γ)=α+(βα)(γM1)kCp(\gamma)=\frac{\alpha+(\beta - \alpha) \cdot \left(\frac{\gamma}{M-1}\right)^k}{C}

  • Geometric ranking function:

    p(γ)=α(1α)M1γCp(\gamma)=\frac{\alpha \cdot (1 - \alpha)^{M-1-\gamma}}{C}

  • Exponential ranking function:


    where CC is a normalising factor and 0<α<β0<\alpha<\beta.

Truncation Selection 截斷選擇

  • Steps:
    • Rank individuals by fitness values
    • Select some proportion, kk, (e.g. k=12k = \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 PP\prime of k individuals from population PP
    • Step 2: Select the individual in PP\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)(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? 選擇壓力如何影響探索和開發之間的平衡?
  • Answer 1:
    • 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 xx^{∗}
    • Apply selection repeatedly with no other operators.
    • ττ^∗ is number of generations until population consists of xx^{∗} 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.MlnMc\frac{M ln M}{c}Assuming a power law objective function f (x) = xc
Linear ranking2ln(M1)β1\frac{2ln(M-1)}{\beta-1}1≤β≤2
TruncationlnMln M
TournamentMk\frac{M}{k}tournament size kk

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 低選擇壓力 → 探索 → 慢速收斂