5: EA Behaviors

EA for 8-Queens 用于八皇后问题的 EA

Why do we sometimes prohibit certain constraint violations (e.g., horizontal or vertical) but allow others (e.g., diagonal), when designing representation and variation operators?

在设计表示方式和变异算子时，为什么有时禁止某些约束违反（例如水平方向或垂直方向的冲突），但允许其他约束违反（例如对角线冲突）？
How large should the population be? How can we reason about an appropriate or effective population size?

种群应该多大？我们如何判断一个合适或有效的种群规模？
Do we need both crossover and mutation? In which order should they be applied?

我们是否同时需要交叉（crossover）和变异（mutation）？它们应该按照什么顺序应用？
If I propose a different crossover strategy, how can we evaluate whether it is valid or effective?

如果我提出一种不同的交叉策略，如何评价它是否有效或合理？

Typical behavior of an EA EA 的典型行为

Phases in optimizing on a 1-dimensional fitness landscape

在一维 fitness landscape（适应度景观）上进行优化时经历的不同阶段。
Exploration vs. exploitation

探索（Exploration）与利用（Exploitation）之间的权衡与动态演变。

Early phase: quasi-random population distribution

早期阶段：种群呈准随机分布（个体分散在不同区域，侧重全局探索 Exploration）。

Middle phase: population arranged around/on hills

中期阶段：种群分布在山峰周围或山峰上（个体逐渐向有潜力的局部峰值聚拢，兼顾探索与利用）。
Late phase: population concentrated on high hills

后期阶段：种群集中在较高的山峰上（个体高度集中于高适应度区域，侧重局部深入搜索 Exploitation，多样性降低）。

Typical behavior of an EA (EA 的典型行为)

Phases in optimizing on a 1-dimensional fitness landscape

在一维 fitness landscape（适应度景观）上进行优化时经历的不同阶段。
Exploration vs. exploitation

探索（Exploration）与利用（Exploitation）之间的权衡与动态演变。
Early phase: quasi-random population distribution

早期阶段：种群呈准随机分布（个体分散在不同区域，侧重全局探索 Exploration）。
Middle phase: population arranged around/on hills

中期阶段：种群分布在山峰周围或山峰上（个体逐渐向有潜力的局部峰值聚拢，兼顾探索与利用）。
Late phase: population concentrated on high hills

后期阶段：种群集中在较高的山峰上（个体高度集中于高适应度区域，侧重局部深入搜索 Exploitation，多样性降低）。

Typical run: progression of fitness 一次典型运行：fitness 的提升过程

Anytime behavior 任意时刻可用的特性

Are long runs beneficial? 长时间运行是否有益？

曲线前半段（Progress in 1st half）：前期收敛速度快，适应度提升显著
曲线后半段（Progress in 2nd half）：后期曲线变平缓，边际收益递减，提升幅度极小
It depends: how much you want the last bit of progress

这取决于你对最后一点改进的需求程度（权衡获得极小性能提升与付出的高额计算成本）
It may be better to do more shorter runs

进行更多次较短的运行可能更好（利用随机初始化的多样性探索不同的解空间区域，降低陷入局部最优的风险）

EAs in context 从整体背景看 EAs

There are many views on the use of EAs as robust problem solving tools

对于是否应该将 EAs 作为稳健的问题求解工具，人们存在许多不同看法。
For most problems a problem-specific tool may:

对于大多数问题，针对具体问题设计的工具（problem-specific tool）可能会：
- perform better than a generic search algorithm on most instances
  
  在大多数问题实例上比通用搜索算法表现得更好。
- have limited utility
  
  用途相对有限（通用性较差）。
- not do well on all instances
  
  在所有问题实例上不一定都表现良好。
Goal is to provide robust tools that have:

目标是提供具有以下特点的稳健工具（robust tools）：
- evenly good performance
  
  均衡而良好的性能。
- over a range of problems and instances
  
  能够适用于一系列不同的问题和问题实例。

EAs as problem solvers: Goldberg’s 1989 view 作为问题解决者的环境分析师(戈德堡1989年的观点)

No-Free-Lunch (NFL) Theorem No-Free-Lunch（NFL）定理 / “没有免费午餐”定理

There is no universally best algorithm for solving all optimization problems

不存在能够解决所有优化问题的普遍最佳算法。
For any two optimization algorithms A and B, if we average their performance across all possible objective functions, their performances will be equal

对于任意两个优化算法 A 和 B，如果将它们在所有可能的目标函数上的表现取平均，那么它们的平均表现将相等。
Implications:

推论：
- no universal best algorithm
  
  不存在普遍适用且始终最好的算法。
- tailor algorithms to problems (i.e., domain knowledge)
  
  应该根据问题定制算法（即利用领域知识/先验知识）。
- bias in algorithms (i.e., assumptions about one problem)
  
  算法中存在归纳偏置（即算法对特定问题结构所作出的内在假设）。

EAs and domain knowledge 进化算法与领域知识

Trends:

发展趋势：
- adding problem specific knowledge to EAs
  
  将特定问题的领域知识加入到进化算法中
- (special variation operators, repair, etc)
  
  （例如：设计针对特定问题的变异/重组算子、设计解的修复机制 repair 等）
Result: EA performance curve “deformation”:

结果：进化算法的性能曲线发生“变形”：

这里的“性能曲线变形”是一个比喻。加入领域知识后，EA 不再对所有问题表现得完全一样，而是对某些问题更有优势，对另一些问题可能失去通用性。
- better on problems of the given type
  
  在属于该特定类型的问题上表现更好
- worse on problems different from given type
  
  在偏离或不同于该特定类型的问题上表现变差
- amount of added knowledge is variable
  
  所融入的领域知识量是可多可少的（存在灵活的权衡空间）
Theory suggests the search for an “all purpose” algorithm may be fruitless

理论表明，试图寻找一种能解决所有问题的“万能算法”可能是徒劳的（与 NFL 定理相呼应）

EAs as problem solvers: Michalewicz’s 1996 view 执行助理作为问题解决者：米哈列维奇1996年的观点

EC and global optimization EC 与全局优化

Global optimization: search for finding best solution $x^*$ out of some fixed set $S$

全局优化：从某个固定集合 $S$ 中搜索最优解 $x^*$ 。
Deterministic approaches allowed to run to completion

允许确定性方法运行至完成

**确定性方法（deterministic approaches）**在相同的输入和条件下，通常会产生相同的搜索过程和结果。

“运行至完成”意味着算法可以系统地检查所有必要的情况，直到能够确定最优解。
- guarantee to find $x^*$ , but may run in super-polynomial time
  
  保证能够找到 $x^*$ ，但运行时间可能是超多项式时间（随着规模增加，计算时间急剧膨胀）。
Heuristic approaches (generate-and-test)

启发式方法（生成并测试机制）
启发式方法不会系统地检查所有可能解，而是反复执行：
1. 生成一个候选解；
2. 计算它的质量；
3. 根据结果决定下一步生成什么样的候选解
- rules for deciding which $x$ from $S$ to generate next
  
  用特定规则决定下一步从解空间 $S$ 中生成哪个候选解 $x$
- no guarantees that best solutions found are globally optimal
  
  无法保证找到的最佳解一定是全局最优解（以牺牲绝对最优性保证为代价，换取在合理时间内得到高质量解的实用性）。

EAs as generate-and-test algorithms 作为“生成并测试”算法的 EAs

EAs are population based, i.e., they process a whole collection of candidate solutions simultaneously

EAs 是基于种群的算法，也就是说，它们会同时处理一组候选解。
Most EAs use recombination, mixing information from two or more candidate solutions to create a new one

大多数 EAs 使用重组（recombination），将两个或更多候选解中的信息混合起来，生成一个新的候选解。
EAs are stochastic

EAs 是随机性的算法。
An EA is a systematic way of doing trial-and-error in a large search space

EA 是在大型搜索空间中进行试错的一种系统化方法。

EC and neighborhood search EC 与邻域搜索

Many heuristics impose a neighborhood structure on $S$

许多启发式方法会在解空间 $S$ 上定义一种邻域结构。
Such heuristics may guarantee that best point found is locally optimal, like hill-climbers

这类启发式方法可能保证找到的最佳点是局部最优解，例如爬山法（hill-climbers）
- but problems often exhibit many local optima
  
  但是，问题通常会呈现出许多局部最优解（容易陷入次优山峰而无法跳出）
- often very quick to identify good solutions
  
  这类方法通常能够很快找到较好的解（局部搜索效率高）
EAs are distinguished by:

进化算法（EAs）的区别性特征包括：
- use of population -> intrinsic parallelism, multiple regions of the search space
  
  使用种群机制 -> 带来内在的并行性，能够同时覆盖搜索空间的多个不同区域
- use of multiple search operators with different arities
  
  使用多个具有不同元数（arities）的搜索算子（如一元的变异 mutation、二元或多元的交叉重组 recombination 等）
- stochastic operators of variation and selection
  
  具有随机性的变异算子与选择算子（通过概率机制避免陷入固定路径，兼顾多样性与定向搜索）

启发式方法（Heuristics / Heuristic Methods）

放弃追求“理论上的最优解或绝对精确”，以换取“在合理时间内找到足够好（satisficing）的近似解

算子（Operator）

算子本质上就是一个“映射”或“变换”规则。如果说“函数”通常是把一个数映射成另一个数，那么“算子”往往站在更高的抽象层次上——它通常接受一个输入（可以是数、向量，也可以是另一个函数或数据结构），并将其变换成另一个输出。

Summary 总结

EAs are stochastic generate-and-test algorithms

EAs 是具有随机性的“生成并测试”算法。
EAs balance exploration and exploitation

EAs 会平衡探索（Exploration）与利用（Exploitation）。
There is no universally best search algorithm; algorithm design should exploit problem knowledge

不存在普遍最好的搜索算法；算法设计应该充分利用问题领域知识。

problem knowledge

关于“这个问题有什么规律、约束和特点”的知识。