6: Genetic Algorithm

What are the different types of EAs EA 有哪些不同类型？

Historically different flavors of EAs have been associated with different representations

从历史上看，不同流派/形式的 EA 通常与不同的表示方式（representations）联系在一起
- Binary strings: Genetic Algorithms
  
  二进制字符串：遗传算法（Genetic Algorithms, GA）
- Real-valued vectors: Evolution Strategies
  
  实数向量：进化策略（Evolution Strategies, ES）
- Finite state machines: Evolutionary Programming
  
  有限状态机：进化规划（Evolutionary Programming, EP）
- Trees: Genetic Programming
  
  树结构：遗传编程（Genetic Programming, GP）
These historical distinctions are less important today

如今，这些历史上的严格区分已经不那么重要了
- choose representation to suit problem
  
  根据问题特点选择最适合的表示方式
- choose variation operators to suit representation
  
  根据所选的表示方式选择/设计匹配的变异与重组算子（variation operators）
Selection operators only use fitness and so are independent of representation

选择算子（Selection operators）仅依据适应度（fitness）进行操作，因此与具体的解表示方式无关（具有独立性）

function optimization problem 一个函数优化问题的示例

function optimization problems：在允许的候选解范围内，寻找一个 $x$ ，使函数 $f(x)$ 的值尽可能大或尽可能小。

What if the function is a black box? 如果函数是一个黑箱，怎么办？

We do not need to know the internal structure of the function. We only need to be able to evaluate it.

我们不需要知道函数的内部结构，我们只需要能够对它进行评估。
Black-box optimization examples

黑箱优化应用示例：
- hyperparameter tuning
  
  超参数调节（如机器学习模型中的学习率、批大小等）
- neural architecture search
  
  神经网络架构搜索（NAS）
- drug discovery
  
  药物发现（分子结构筛选与性质优化）
- engineering design, stress/weight
  
  工程设计（例如在满足结构应力约束的同时最小化重量）
- scheduling
  
  任务调度与排程
- robot controller tuning
  
  机器人控制器参数调节
- game strategy
  
  博弈/游戏策略优化
Surrogate-assisted evolutionary optimization

代理模型辅助的进化优化（当黑箱评估极度耗时或昂贵时，使用轻量级的近似代理模型来辅助预测与筛选候选解）

GA quick overview GA 快速概览

Developed: USA in the 1970’s

发展历史：20 世纪 70 年代起源于美国
- Adaptation in Natural and Artificial Systems, John Holland, 1975
  
  代表作：John Holland 于 1975 年出版的《自然系统与人工系统中的适应》（奠定了遗传算法的理论基础）
Early names: J. Holland, E. Goodman, K. DeJong, D. Goldberg

早期代表学者：J. Holland、E. Goodman、K. DeJong、D. Goldberg
Typically applied to:

典型应用场景：
- discrete function optimization problems
  
  离散函数优化问题
- benchmark problems
  
  基准测试问题（用于横向对比与验证算法性能）
- straightforward problems using a binary representation
  
  易于直接采用二进制串进行编码表示的问题
Features:

算法特征：
- not very fast
  
  运行速度通常不够快（因种群迭代与反复的适应度评估带来一定计算开销）
- good heuristic for combinatorial problems
  
  针对组合优化问题表现出色的启发式方法
  
  combinatorial problems：从有限但数量巨大的离散组合中，选择一个满足约束且最优或较优的方案。
- traditionally emphasizes combining information from good parents
  
  传统上尤为强调重组（交叉），即通过组合来自优秀父代的信息来构建高质量子代
- many variants, e.g., reproduction models, operators
  
  衍生版本丰富，例如在繁殖模型（世代更替 vs. 稳态更替）、选择/变异/重组算子等方面存在多种变体

Genetic Algorithms 遗传算法（GA）

Holland’s original GA is now known as the simple genetic algorithm (SGA)

Holland 最初提出的 GA 现在被称为简单遗传算法（Simple Genetic Algorithm, SGA）。
Other GAs use different:

其他 GA 可以采用不同的：
- representations
  
  表示方式（如二进制串、排列、实数向量或树结构等）
- mutations
  
  变异算子（如位翻转、对调/交换、实数高斯扰动等）
- crossovers
  
  交叉/重组算子（如单点交叉、均匀交叉、顺序交叉、切割与交叉填充等）
- selection mechanisms
  
  选择机制（如轮盘赌选择、锦标赛选择、基于排名的选择等）
- population management
  
  种群管理方式（如世代更替模型 Generational、稳态更替模型 Steady-state、精英保留策略 Elitism 等）

Population management（种群管理）

它通常需要决定：

种群规模：每一代保留多少个个体；

替换方式：新产生的 offspring 替换哪些旧个体；

更新频率：每次替换整个种群，还是只替换少数个体；

精英保留：是否确保当前最好的个体进入下一代；

多样性维护：是否避免种群中的个体变得过于相似；

重复个体处理：是否允许种群中出现相同的解。

Simple GA 简单遗传算法（SGA）

Has been subject of many (early) studies

曾是许多早期研究的核心对象。
- often used as benchmark for novel GAs
  
  常被用作衡量新提出 GA 性能的基准（benchmark）。
Show several important limitations

展现出若干重要局限性：
- representation is too restrictive
  
  表示方式限制性太强（固定使用定长二进制串编码，不适合实数、排列或树状等更复杂的结构）。
- mutation & crossover only applicable for bit-string integer representations
  
  其变异与交叉算子（位翻转与单点交叉）仅适用于比特串整数表示。
  
  仅适用于比特串整数表示示例：
  
  00000 → 0
  
  00001 → 1
  
  00101 → 5
  
  11111 → 31
- fitness-proportional selection sensitive for converging populations with close fitness values
  
  适应度比例选择对趋于收敛且个体 fitness 值十分接近的 population 过于敏感（在后期各个体 fitness 差距微弱时，选择压力显著退化，难以区分优劣）。
  
  例如
  
  $P(A) = \frac{100}{394} \approx 25.4\%$
  
  $P(B) = \frac{99}{394} \approx 25.1\%$
  
  $P(C) = \frac{98}{394} \approx 24.9\%$
  
  $P(D) = \frac{97}{394} \approx 24.6\%$
  
  可以看到，A 只比 D 多大约 0.8 个百分点。实际上，四个个体几乎拥有相同的被选择概率。
- generational population model can be improved with explicit survivor selection
  
  世代种群模型（generational population model）可以通过引入显式的幸存者选择机制进行改进
  
  每一代都会产生与原 population 数量相同的 offspring，然后用这一整批 offspring 替换旧 population。
  
  旧 population 中的优秀个体可能被无条件删除，因此可以加入明确的 survivor selection 来决定哪些个体进入下一代。

SGA technical summary SGA 技术总结

项目	SGA实现方式	****
Representation	Binary strings	表示方式：二进制字符串（由 0 和 1 构成的定长串）
Mutation	Bit flip	变异方式：位翻转（以小概率将 0 反转为 1，或 1 反转为 0）
Recombination	One-point crossover	重组方式：单点交叉（选取单个交叉切分点交换父代片段）
Parent selection	Fitness proportional - implemented using Roulette Wheel	父代选择：适应度比例选择——基于轮盘赌算法（Roulette Wheel）实现
Survivor selection	Generational	幸存者选择：世代更替（用全新生成的一代子代个体整体替换上一代种群）

SGA representation (SGA 的表示方式)

Encoding 是把 phenotype 转换成 genotype 的过程

Decoding 是把 genotype 转换回 phenotype 的过程

SGA iteration SGA 的迭代

Select parents for the mating pool (size of mating pool = population size)

为交配池（mating pool）选择父代（mating pool的大小等于种群规模 population size）。
Shuffle the mating pool

随机打乱交配池中的个体顺序。
Apply crossover for each consecutive pair with probability $p_c$ , otherwise copy parents

对每一对相邻个体以概率 $p_c$ 执行交叉（crossover）；否则直接复制父代个体。
Apply mutation to each offspring (bit-flip with probability $p_m$ independently for each bit)

对每个子代个体施加变异（每个位独立地以概率 $p_m$ 进行位翻转 bit-flip）。
Replace the whole population with the resulting offspring

用最终得到的子代整体替换旧种群（实现世代更替）。

SGA operators: parent selection SGA 算子：parent selection

Main idea: better individuals get higher chance to reproduce

核心思想：表现更好的 individual 会获得更高的 reproduction 机会。
- chances proportional to fitness
  
  被选中的概率与自身的 fitness 成正比。
- implementation: roulette-wheel selection
  
  具体实现方式：轮盘赌选择（roulette-wheel selection）。
  - Assign to each individual a part of the roulette wheel
    
    为每个 individual 分配轮盘（roulette wheel）上对应其 fitness 比例的扇形区域。
  - Spin wheel $n$ times to select $n$ individuals
    
    转动轮盘 $n$ 次，以选出 $n$ 个 individual 进入交配池。

SGA operators: crossover

SGA operators: one-point crossover SGA 算子：单点交叉

Choose a random point on the two parents

在两个父代染色体上随机选取一个交叉点。
Split parents at this crossover point

在此交叉点处将两个父代各自切分为两部分。
Create children by exchanging tails

通过交换两个父代的后半段（尾部）来生成子代个体。
- 图示说明：
  - 父代（parents）：一个全为 0（灰色），一个全为 1（白色）
  - 切分后交换尾部：生成子代（children）分别为前半段 0 拼接后半段 1，以及前半段 1 拼接后半段 0
$p_c$ typically in range $(0.6, 0.9)$

交叉概率 $p_c$ 通常设置在 $0.6$ 到 $0.9$ 之间（以较高概率组合父代优良特征，保留少量直接复制父代的机会）。

排序对one-point crossover 的performance影响(positional bias位置偏置)

使用 one-point crossover 的性能取决于变量在 representation 中的排列顺序。

more likely to keep together genes that are near each other

更有可能将彼此相邻的 genes 保留在同一个 offspring 中。

如果 A 和 B 是相邻的 genes，那么只有当 crossover point 正好位于 A 和 B 之间时，它们才会被分开：
can never keep together genes from opposite ends of string

无法将位于染色体两端的 genes 作为一个整体保持在一起

两个 genes 之间距离越远，它们之间可作为切点的位置越多，被分开的概率就越高。
known as positional bias

这种现象被称为位置偏置（positional bias）。
not automatically bad; can be exploited if we know about the structure of our problem (the algorithm imposes a structure of the problem)

这并不直接等同于缺陷；如果我们事先了解问题的内在结构，就可以主动利用这种偏置（此时算法会给问题施加一种结构上的先验假设）。

Alternative crossover operators 其他 crossover 算子

n-point crossover n 点交叉

Choose $n$ random crossover points

在两个父代染色体上随机选择 $n$ 个交叉点。
Split along those points

沿着这些交叉切点切。
Glue parts, alternating between parents

交替从两个父代中提取对应位置的片段并拼接起来，生成新的 offspring。
- 图示说明（以 $n=3$ $n = 3$ 的三点交叉为例）：
  - 父代（parents）：一个全为 0（灰色），一个全为 1（白色）。
  - 切分后片段长度分别为 5、3、6、4。
  - 交叉拼接后生成两个 offspring（图中标注为 children）：第一个 offspring 的片段交替为 0-1-0-1，第二个 offspring 的片段交替为 1-0-1-0。
Generalization of one-point crossover

该算子是单点交叉（one-point crossover）的推广（当 $n=1$ 时即为单点交叉；增加切点数有助于打破两端基因无法组合的位置偏置，但切点过多也可能破坏有益的基因块）。

Uniform crossover 均匀交叉

Assign “heads” to one parent, “tails” to the other

将“正面（heads）”分配给一个 parent，将“反面（tails）”分配给另一个 parent（作为随机选择基因来源的比喻）。
Flip a coin for each gene of the first child

对第一个 offspring（图中标注为 child）的每个 gene 独立抛掷一次硬币，决定该位置继承哪一个 parent 的对应 gene。
Make an inverse copy of the gene for the second child

对第二个 offspring，在每个基因位上取与第一个 offspring 完全相反的 parent 来源（即若第一个 offspring 取自 parent 1，则第二个 offspring 在该位置取自 parent 2，反之亦然）。

Which crossover operator to use? 应该使用哪一种 crossover 算子？

Impossible to state that one or the other of those operators performs best on any given problem

无法断言这些算子中某一种在任何给定问题上都表现最好（遵循 NFL 定理，没有放之四海而皆准的最优算子）。
Important to understand the types of bias exhibited by different recombination operators

理解不同重组算子（recombination operators）所表现出的偏置类型至关重要（例如单点/多点交叉的位置偏置 positional bias，以及均匀交叉打破相邻基因关联的高重组破坏性）。

n-point crossover：当相邻的 genes 往往相关、连续片段具有意义时，

Uniform crossover:当各位置的 genes 没有特别的顺序关系，或希望每个位置都独立地从两个 parents 中取值时，可以尝试。它对每个 gene 单独随机决定来源，不依赖连续片段。
Know patterns or dependencies in the chosen representation when designing an algorithm for a particular problem

为特定问题设计算法时，需要深入了解所选 representation 中各个 gene 之间的关联模式与依赖关系（若关键相关变量彼此相邻，可利用位置偏置保留有用模式；若变量间相互独立或空间分散，则需权衡不同的 crossover 方式）。

SGA operators: mutation SGA 算子：变异

Alter each gene independently with a probability $p_m$

以概率 $p_m$ 独立地改变每个 gene（在二进制串中即进行 0/1 位翻转 bit-flip）。
$p_m$ is called the mutation rate

$p_m$ 称为变异率（mutation rate）。
- depends on the desired outcome
  
  其具体取值取决于期望达到的搜索行为与优化结果（通常设置较小，以维持多样性并进行局部探索，避免破坏已有的优良 genotype）。
图示说明：
- 上方个体：原始 genotype，全为 1（白色方块）。
- 下方个体：经过 mutation 后的 offspring genotype，灰色方块为发生 bit-flip（ $1 \rightarrow 0$ ）的基因位，白色方块为保持不变的位。

Crossover or mutation? 该用 crossover 还是 mutation？

Decade long debate: which one is better / necessary / main background search operator

长达数十年的争论：到底哪一个更好、是否不可或缺、或者谁才是主要的基础搜索算子。
Answer (at least, wide agreement):

结论（至少已达成广泛共识）：
- it depends on the problem, but
  
  这取决于具体问题，但是——
- in general, it is good to have both
  
  通常情况下，同时具备两者是有益的（crossover 负责重组既有优良信息，mutation 负责引入全新等位基因并维持多样性）。
- mutation-only-EA is possible, xover-only-EA would not work
  
  只使用 mutation 的 EA 是可行的，而只使用 crossover 的 EA 则无法奏效（若某个 gene 在种群的所有个体中全部丢失，仅靠 crossover 无法生成该位置的新取值，导致搜索空间被永久截断；mutation 则是保证解空间遍历性的底线）。

Exploration和Exploitation

Exploration: discovering promising areas in the search space, i.e., gaining information on the problem

探索（Exploration）：发现搜索空间中有希望的区域，即获取有关问题的新信息。
Exploitation: optimizing within a promising area, i.e., using information

利用（Exploitation）：在已有希望的区域内进行深度优化，即充分利用已掌握的信息。
There is co-operation and competition between them

它们之间既存在合作，也存在竞争：
- crossover is more explorative, it makes a big jump to an area somewhere “in between” two (parent) areas
  
  crossover 通常更偏向探索性（explorative），它通过组合不同 parent 的信息，大幅度跳跃到介于两个 parent 所在区域之间的某个位置。
- mutation is more exploitative, it creates random small diversions, thereby staying near (in the area of) the parent
  
  mutation 通常更偏向利用性（exploitative），它引入随机的小幅度扰动，从而使生成的 offspring 仍保留在 parent 附近或其所在区域。
- no strict mapping of those two to exploration/exploitation
  
  两者与探索/利用之间并不存在绝对严格的固定映射（例如大步长的 mutation 同样能实现强探索，而相近个体间的 crossover 也会起到局部微调作用）。

Unique Roles & Allelic Impact (两者独特机制与对 Alleles 的作用)

Only crossover can combine information from two parents

只有 crossover 能够组合来自两个父代的信息（通过重组两个不同父代的片段或基因，构造出兼具两者特性的新 genotype）。
Only mutation can introduce new information (alleles)

只有 mutation 能够引入全新的信息（alleles）。如果某个基因位上的某种取值在当前种群的所有个体中全部丢失，任何仅复制父代取值的 crossover 都无法重新恢复它，唯有依靠 mutation 才能产生该位置的新取值。
Crossover often does not change the allele frequencies of the population

crossover 通常不会改变种群中的allele frequencies。它只是重新打乱并组合基因在各个个体中的分布，每个allele在种群中的总出现比例保持不变；真正改变allele频率的是选择操作（selection）与 mutation。

allele frequencies :某个基因位置上某种 allele value 出现的比例

The fundamental tension 根本性的矛盾（核心张力）

Diversity vs. convergence

多样性与收敛性之间的权衡（Diversity vs. Convergence）。
Variation operators, especially mutations, increase diversity, ensuring better search and preventing getting stuck in local optima

变异算子（variation operators），特别是 mutation，能够增加种群的多样性，从而确保更充分的搜索能力，并防止算法陷入局部最优（local optima）。
GA can possibly make progress as long as it is not converged

只要 GA 尚未完全收敛，就仍有可能产生新的优良 genotype 并取得进一步优化进展。
However, we cannot wait “forever” for a GA to converge, as we are seeking solutions

然而，在实际问题中我们无法“无休止地”等待 GA 慢慢收敛，因为我们的目标是在有限的计算资源和时间预算内求得满意的可行解。
Balancing these issues is the key

在维持种群多样性（防止过早早熟收敛）与加速收敛（高效利用已发现的优良解）之间取得动态平衡，是设计有效遗传算法的关键。

Example 示例

Maximize $x^2$ over $\{0, 1, 2, ..., 31\}$

在集合 $\{0, 1, 2, \dots, 31\}$ 中最大化函数 $x^2$ 。
GA approach

GA 方法设计：
- representation: binary code, 5 bits
  
  表示方式：5 位二进制编码（对应整数 $0\sim 31$ 的 genotype）
- population size: 4
  
  种群规模：4（每代包含 4 个 individual）
- one-point crossover, bitwise mutation
  
  单点交叉（one-point crossover）与逐位翻转变异（bitwise mutation）
- roulette wheel selection
  
  轮盘赌选择机制（roulette wheel selection）
- random initialization
  
  随机初始化（随机生成 4 个 5 位的二进制串作为初始种群）

parent selection

crossover

mutation

When to use a GA? 什么时候使用 GA？

Highly multimodal functions

高度多峰函数（搜索空间中包含大量局部最优解，基于种群的全局搜索能显著降低陷入单个局部峰值的风险）。
Discrete or discontinuous functions

离散函数或不连续函数（无需目标函数连续或具备导数信息，可直接对二进制、排列或离散编码进行评估）。
High-dimensionality functions, including many combinatorial ones

高维函数，包括许多组合优化问题（搜索空间巨大且无法通过穷举求解，依靠重组与变异探索潜在优质区域）。
Nonlinear dependencies on parameters (interactions)

参数间存在非线性依赖关系（相互作用/上位效应 interactions，变量无法单独分开优化，需要通过 crossover 组合不同父代间的协作模式）。
When not to use a GA?

什么时候不应该使用 GA？（例如已知平滑可微的凸函数、存在成熟专用高效多项式算法的问题、或评估代价极高且无法快速近似的场景）。
在以下情况下，GA 可能不是首选：
- 已经有一个针对该问题的高效精确算法；
- 问题规模很小，可以直接枚举；
- 目标函数有可用的梯度，可以使用高效的梯度优化方法；
- 只需要一次快速的局部改进；
- 每次 fitness evaluation 的成本极高，而 GA 需要评估大量候选解；
- 必须保证得到全局最优解，而 GA 无法提供这种保证。

当问题复杂、搜索空间大、目标函数不连续或难以分析，并且可以接受近似解时，GA 往往值得考虑。