3-EAbasics

Main components of the design of an EA EA 设计的主要组成部分

How does an EA turn trial-and-error into a systematic adaptive search?

EA 如何把试错（trial-and-error）变成一种系统性的自适应搜索（systematic adaptive search）？
- Representation (definition of individuals) - What can we try?
  
  表示方式（individual 的定义）——我们可以尝试什么？
- Evaluation function (or fitness function) - How do we know they are good?
  
  评价函数（或 fitness function）——我们怎么知道这些 solution 好不好？
- Population and initialization - How do we start?
  
  种群和初始化——我们怎么开始？
- Parent selection mechanism - Which solutions do we learn from?
  
  父代选择机制——我们从哪些 solutions 中学习？
- Variation (recombination/mutation) - How do we generation new possibilities?
  
  变异机制（重组 / 突变）——我们怎样产生新的可能性？
- Survivor selection mechanism (replacement) - What do we keep?
  
  幸存者选择机制（replacement）——我们保留什么？
- Termination - When do we stop?
  
  终止条件——我们什么时候停止？

General scheme of EAs 进化算法的总体框架

How does an EA turn trial-and-error into a systematic adaptive search?

一个进化算法（EA）是如何将试错过程转化为系统化的自适应搜索的？

Pseudo-code for typical EA 进化算法的伪代码进化算法的伪代码

BEGIN # 开始
  INITIALISE population with random candidate solutions; # 用随机候选解初始化种群
  EVALUATE each candidate; # 评估每个候选解的适应度
  REPEAT UNTIL ( TERMINATION CONDITION is satisfied ) DO # 重复循环，直到满足终止条件：
    1 SELECT parents; # 1. 选择父代个体
    2 RECOMBINE pairs of parents; # 2. 将成对的父代进行重组/交叉
    3 MUTATE the resulting offspring; # 3. 对生成的子代进行变异
    4 EVALUATE new candidates; # 4. 评估新生成的候选解
    5 SELECT individuals for the next generation; # 5. 选择进入下一代的个体
  OD # 循环结束
END # 程序结束

Representations 表示方式 / 编码方式

Candidate solutions (individuals) exist in phenotype space (problem world)

Candidate solutions（候选解 / individuals）存在于 phenotype space（表现型空间），也就是实际问题世界中。
They are encoded in genome/chromosomes, which exist in genotype space

这些 candidate solutions 会被编码成 genome / chromosomes，而这些编码存在于 genotype space（基因型空间）中。
- Encoding: phenotype -> genotype
  
  编码：phenotype → genotype
- Decoding: genotype -> phenotype (one to one)
  
  解码：genotype → phenotype（一对一）
Chromosomes contain genes, which are in (usually fixed) positions called loci and have a value (allele)

Chromosome 包含 genes；这些 genes 位于通常固定的位置，这些位置叫做 loci，而每个 gene 具有一个具体的值，叫 allele。

loci ：位置index

allele: 值value
In order to find the global optimum, every feasible solution must be represented in genotype space!

为了能够找到 global optimum（全局最优解），每一个 feasible solution（可行解）都必须能够在 genotype space 中表示出来！

Evaluation (fitness) function 评价函数 / 适应度函数

Represents the requirements that the population should adapt to

它代表 population 需要去适应的要求
- a.k.a. quality function or objective function
  
  也叫：quality function（质量函数）或 objective function（目标函数）
Assigns a single real-valued fitness to each phenotype which forms the basis for selection

它给每一个 phenotype 分配一个实数形式的 fitness 值，而这个 fitness 值构成 selection 的基础
Typically we talk about fitness being maximized

通常我们会把 fitness 看作是要被最大化的
- Some problems may be best posed as minimization problems
  
  有些问题更适合被表示成最小化问题

Explicit vs. implicit fitness 显式与隐式适应度

For many of the approaches, an explicit fitness function is used. Why?

在很多方法中，会使用一个显式的 fitness function。为什么？
- better determine the kinds of good solutions
  
  可以更好地确定什么样的 solution 是好的。
- useful to solve particular problems
  
  对于解决特定问题很有用。
Can have fitness be determined implicitly

Fitness 也可以被隐式地（implicitly）决定。
- competition in some form for resources, where better competitors are more fit
  
  个体通过某种形式竞争资源，其中竞争能力更强的个体被认为具有更高的 fitness。
- Tierra, Avida, mostly Artificial Life
  
  Tierra、Avida，以及其他主要用于 Artificial Life（人工生命）的系统。
- evolutionary robotics
  
  进化机器人学。
- game strategy optimization
  
  游戏策略优化。

explicit显式的：直接、明确写出来

如直接比较A,B分数

implicitly隐式地:不直接写出来，而是通过结果间接体现

如 A 和 B 对战

Population 种群

Holds (representations of) possible solutions

保存的是各种可能 solution 的表示。
Usually has a fixed size and is a multiset of genotypes

通常有固定大小，并且是一个 genotype 的 multiset（多重集合）。
Some sophisticated EAs also assert a spatial structure on the population, i.e. a grid

一些更复杂的 EA 还会给 population 加上空间结构，例如一个 grid（网格）。
Selection operators usually take whole population into account, i.e reproductive probabilities are relative to current generation

Selection operators 通常会把整个 population 考虑进去，即繁殖概率是相对于当前 generation 来决定的。
Diversity of a population refers to the number of different fitnesses / phenotypes / genotypes present (note not the same thing)

Population 的 diversity（多样性），指 population 中存在多少不同的 fitnesses / phenotypes / genotypes（注意：这些不是同一个东西）。

Parent selection mechanism 父代选择机制

Assigns variable probabilities of individuals acting as parents depending on their fitnesses

根据 individuals 的 fitness，为它们分配不同的成为 parent 的概率。
Usually probabilistic

通常是概率性的。
- High quality solutions more likely to become parents than low quality ones
  
  高质量的 solutions 比低质量的 solutions 更有可能成为 parents。
- but not guaranteed
  
  但并不保证一定如此。
- even worst in current population usually has non-zero probability of becoming a parent
  
  即使是当前 population 中最差的 individual，通常也仍然有非零概率成为 parent。
This stochastic nature can aid escape from local optima but slow you down

这种随机性质可以帮助算法逃离 local optima，但也可能让搜索变慢。
Selection provides direction; randomness preserves possibilities

Selection 提供方向；randomness 保留可能性。
Exploration/exploitation tension

探索与利用之间的张力 / 平衡。

Variation operators 变异算子

Role is to generate new candidate solutions

作用是生成新的候选解。
- From parents to child (offspring)
  
  从父代生成子代（后代）。
Usually divided into two types according to their arity (number of inputs):

通常根据元数arity（输入的数量）分为两种：
- Mutation: modify one solution
  
  变异：修改一个解。
- Recombination: combine information from multiple solutions
  
  重组：结合多个解中的信息。
- Neither is expected to produce a better solution every time
  
  这两种操作都不要求每次都产生更好的解。
There has been much debate about relative importance of recombination and mutation

关于重组和变异相对重要性的讨论一直很多。
- Nowadays most EAs use both
  
  如今，大多数进化算法都会同时使用两者。
- Choice of particular variation operators is representation dependent
  
  具体选择哪种变异算子取决于解的表示方式。

Mutation 变异

Act on one genotype and delivers another

对一个genotype进行操作，并产生另一个genotype。
Element of randomness is essential and differentiates it from other unary heuristic operators

随机性是变异不可缺少的要素，也使它区别于其他一元启发式算子。

启发式算子（heuristic operator）是算法中用来构造或修改候选解的一种操作。它利用问题结构或经验规则，引导搜索朝着可能有用的方向进行，但通常不保证找到最优解。

一元启发式算子，是指只接收一个解作为输入并对它进行处理的算子。“一元”描述的是输入数量，不代表操作简单。变异就是一种一元算子；它还带有随机性，因此可以尝试不同的新解。
Importance ascribed depends on representation and dialect:

变异的重要程度取决于解的表示方式和算法类型：
- Binary GAs - background operator responsible for preserving and introducing diversity
  
  二进制遗传算法（Binary GAs）中，变异通常是辅助算子，负责维持并引入多样性。
- Continuous variables ES - sole search operator
  
  连续变量的进化策略（ES）中，变异是唯一的搜索算子。

Recombination 重组

Merges information from parents into offspring

将父代的信息合并到子代中。
Choice of what information to merge is stochastic

选择合并哪些信息的过程是随机的（stochastic）。
Most offspring may be worse, or the same as the parents

大多数子代可能比父代更差，或者与父代相同。
- Combining representations in a heritable way
  
  以能够遗传的方式组合不同表示。
- Hope is that some are better by combining elements of genotypes that lead to good traits
  
  期望通过组合genotypes中带来良好性状的元素，使部分子代变得更好。
In nature, higher-level organisms reproduce sexually

在自然界中，高等生物通过有性繁殖进行繁殖。
- Increased genetic diversity
  
  增加遗传多样性。
- Faster adaptation in changing environments (Red Queen hypothesis)
  
  在变化的环境中更快地适应（红皇后假说）。
- Removal of deleterious mutations (Muller’s Ratchet)
  
  去除有害突变（穆勒棘轮）。
- Separation of exploration and exploitation
  
  将探索与利用分开。
- Scaling to high complexity
  
  适用于高复杂度情形。

Survivor selection (replacement) 幸存者选择（替换）

Sometimes also called environmental selection

有时也称为环境选择。
Most EAs use fixed population size, and need a way of going from (parents + offspring) to next generation

大多数进化算法使用固定的种群规模，因此需要一种方法，将（父代 + 子代）转变为下一代。
Often deterministic (different from parent selection!)

通常是确定性的（不同于父代选择！）。
- Fitness based: e.g., ranking parents + offspring and save the best
  
  基于适应度：例如，将父代和子代进行排名，并保留其中最好的个体。
- Age based: e.g., use offspring to replace worst individuals in the previous generation
  
  基于年龄：例如，使用子代替换上一代中最差的个体。
Elitism

精英保留策略。

Initialization and termination 初始化与终止

Initialization usually done at random

初始化通常以随机方式进行。
- Need to ensure even spread and mixture of possible allele values
  
  需要确保各种可能的allele值能够均匀分布并充分混合。
- Can include existing solutions, or use problem-specific heuristics to “seed” the population
  
  可以加入已有的解，或者使用针对特定问题的启发式方法来“播种”种群。
Termination condition checked every generation (can be disjointed)

每一代都会检查终止条件（这些条件可以是彼此独立的）。
- Reaching some (known/hoped for) fitness
  
  达到某个预先知道的或期望达到的适应度。
- Reaching some allowed limit number of generations
  
  达到允许的最大代数。
- Reaching some minimum level of diversity
  
  达到某个最低多样性水平。
- Reaching some specified number of generations without fitness improvement (stagnation)
  
  达到规定的连续若干代没有适应度改进的次数（停滞）。
- Anytime algorithm
  
  任意时刻可返回结果的算法（随时算法）。