2: Evolution -From biology to algorithms进化—从生物学到算法

Why Biology?为什么选择生物学？

  • Biology provides metaphors, not mechanisms

    生物学提供的是比喻和启发，而不是需要被完整复制的真实机制。

  • We borrow principles, not molecular details

    们借用的是生物学中的基本原则，而不是分子层面的细节

  • Our goal: understand how population + variation + selection become algorithms

    我们的目标是理解 population + variation + selection 如何转化成算法。

EC design principles

EC uses the principles of (EC 使用了以下原理）

  • Darwinian evolution (macroscopic view) - survival of the fittest达尔文进化论（宏观视角）——适者生存

    • In EC: selection operators favors sampling toward higher fitness

      在进化计算中：selection operators会倾向于选择 fitness 更高的个体。

  • Mendelian genetics (microscopic view) - heredity孟德尔遗传学（微观视角）——遗传

    • In EC: variation and preserving good building blocks

      在进化计算中：产生变异，同时保留优秀的 building blocks

      good building blocks：优良基因片段

Terminology术语

Terms borrowed from biology从生物学中借用的术语

  • Genotype:计算机内部存储的 candidate solution 的编码形式

    • 例:例:8-queen问题中->Genotype:0,1(单个皇后位置)

  • Phenotype：genotype 被 解释 / 解码之后得到的实际 solution。

    • 例:8-queen问题中 ->Phenotype: 8 个皇后在棋盘上的具体位置

  • Genome (chromosome):一个完整 candidate solution（候选解） 的编码

    • 例:8-queen问题中 ->Genome/Chromosome： [1,5,8,6,3,7,2,4]

  • Allele:某个 gene 所取的具体值。

    1
    2
    3
    4
    例:
    Chromosome:
    [1101]
    Gene 2的Allele为1

  • Locus:一个 gene 在 chromosome 里的index。

    1
    2
    3
    4
    5
    例:
    Chromosome:
    [1001]
    Locus 1->Allele 1
    Locus 2->Allele 0

Darwinian Evolution: survival of the fittest达尔文进化论：适者生存

  • All environments have finite resources

    所有环境中的资源都是有限的

  • Lifeforms have basic instinct / lifecycles geared towards reproduction

    生物具有基本的本能 / 生命周期，而这些通常都朝向繁殖。

  • Evolution is due to a “force” called natural selection which “selects” the individuals best adapted to the environment

    进化是由一种叫做 natural selection（自然选择） 的“力量”推动的，它会“选择”那些最适应环境的个体

  • Those individuals that compete for the resources most effectively have increased chance of reproduction

    那些能够最有效地竞争资源的个体，会有更高的繁殖机会

  • Constant vs. varying environment

    恒定环境 vs. 变化环境

Darwinian Evolution: diversity drives change 达尔文进化论：多样性推动变化

  • Phenotypic traits:表现型特征

    个体实际表现出来的特征。

    • Behavior / physical differences that affect response to environment

      不同个体之间会有不同特征，而这些特征会影响它们在环境中的表现

    • Partly determined by inheritance, partly by factors during development

      表现型特征一部分由遗传决定，一部分由发育过程中的因素决定

    • Unique to each individual, partly as a result of random changes

    每个个体的特征都是独特的，其中一部分来自随机变化

  • If a phenotypic trait evaluates favorably

    如果某种表现型特征被评价为有利的

    • Lead to higher chances of reproduction

    会带来更高的繁殖机会。

    • Propagate via the individual’s offspring

      这些特征会通过该个体的后代传播

  • Random variations during reproduction lead to new combinations of traits

    繁殖过程中的随机变异会产生新的特征组合。

Darwinian Evolution: population vs. individual 达尔文进化论：种群 vs. 个体

  • Population consists of diverse set of individuals

    一个种群由一组具有多样性的个体组成

  • Combinations of traits that are better adapted tend to increase reproduction in population

    那些更适应环境的特征组合，往往会在种群中获得更多繁殖机会

    • Individuals are “unit of selection”

      个体是 “选择的单位”。

  • Variations occur through random changes yielding constant source of diversity

    变化通过随机改变产生，从而持续提供多样性，再结合 selection，就意味着……

    • Population is the “unit of evolution”

      种群是 “进化的单位

  • Death is very likely the single best invention of Life. It is Life’s change agent. It clears out the old to make way for the new.

    死亡很可能是生命最伟大的发明。它是生命变化的推动者。它清除旧的，为新的让路

The Selfish Genes 自私的基因

  • Richard Dawkins理查德·道金斯

  • Gene-centered view of evolutio以基因为中心的进化观

  • A lineage evolves to maximize the number of copies of its genes passed on globally

一个谱系会朝着让自己的基因在整体上留下更多副本的方向进化

  • Organisms are fundamentally simple survival machines生物从根本上可以被看作简单的生存机器

  • Meme - an idea that spreads by imitation from person to person within a culture

    Meme：一种通过模仿，在一个文化中从一个人传播到另一个人的思想

Adaptive landscape metaphor (Wright, 1932)适应度景观比喻

image-20260925195932004

  • Population with n traits as existing in a n+1 dimensional space (landscape) with height corresponding to fitness

    具有 n 个 traits 的 population，可以看作存在于一个 n+1 维空间中，而额外的那一维高度表示 fitness。

  • Each different individual (phenotype) represents a single point on the landscape

    每一个不同的 individual（phenotype）都代表这个 landscape 上的一个点

  • Population is therefore a “cloud” of points, moving on the landscape over time as it evolves - adaptation

    因此，population 可以看作 landscape 上的一团“点云”，并且随着进化过程不断在 landscape 上移动——这就是 adaptation。

  • Selection “pushes” population up the landscape

选择（selection）会把 population “推”向适应度景观中更高的位置

  • Genetic drift遗传漂变

    population 中某些 traits / genes 的比例发生随机变化，而这种变化不一定是因为它们 fitness 更高

    • random variations in feature distribution arising from sampling error

      由于抽样误差造成的特征分布随机变化。

    • Can cause the population “melt down” hills, thus crossing valleys and leaving local optima

      遗传漂变可能使 population 从山坡上“融化”下来，从而穿过山谷并离开局部最优点

    • highly fit individuals may be lost from the population

      高 fitness 的 individuals 也可能从 population 中消失

  • Unimodal and multimodal problems 单峰问题和多峰问题

Mendelian Genetics 孟德尔遗传学

  • Followed the inheritance of traits from pea plants (wrinkled vs. smooth)、

    德尔研究了豌豆植物中性状的遗传，例如皱粒（wrinkled）和光滑（smooth）。

  • Postulated that the plants passed on traits to their offspring and described some of the characteristics (dominant vs. recessive)

    他提出，植物会把性状传递给后代，并描述了这些性状的一些特征，例如显性（dominant）和隐性（recessive）

  • Had no concept of DNA当时还没有 DNA 的概念。

Crick and Watson克里克和沃森

Discovered the existence of DNA in 1953 and the pairing of bases to form genes

在 1953 年发现了 DNA 的存在，以及碱基配对形成基因的机制

Genetics 遗传学

  • The information required to build a living organism is coded in the DNA of that organism

    构建一个生物体所需要的信息，被编码在这个生物体的 DNA 中

  • Genotype (DNA inside) determines phenotype

    Genotype（内部的 DNA / 遗传信息）决定 phenotype（表现型)

  • Genotype to phenotypic traits is a complex mapping

    从 genotype 到 phenotypic traits 的映射关系是复杂的

    • One gene may affect many traits (pleiotropy)

      一个 gene 可能影响多个 traits，这叫 pleiotropy（多效性）

    • Many genes may affect one trait (polygeny)

      多个 genes 可能共同影响一个 trait，这叫 polygeny（多基因性）

    • Mendelian traits (e.g., ear wax, albinism)

      孟德尔式性状，例如耳垢类型、白化症

  • Changes in the genotype may lead to changes in the organisms (e.g., height, hair color)
    Genotype 的变化可能导致生物体发生变化，例如身高、头发颜色等

Genes and the genome 基因和基因组

  • Deoxyribonucleic acid (DNA) and nitrogenous bases

    • Adenine, Thymine, Cytosine, Guanine

      • Adenine = 腺嘌呤，A

        Thymine = 胸腺嘧啶，T

        Cytosine = 胞嘧啶，C

        Guanine = 鸟嘌呤，G

    • 3 billion base pairs in humans人类大约有 30 亿个碱基对

  • Genes are functional unit of stretches of DNA on chromosomes (~20k in human genome)

    Gene 是 chromosome 上 DNA 片段中的功能单位；人类基因组中大约有 2 万个 genes

  • The complete genetic material in an individual’s genotype is called the Genome

    一个个体 genotype 中完整的遗传物质称为 Genome（基因组）

Mutation 突变

  • Occasionally some of the genetic material changes very slightly during this process (replication error)
    在复制过程中，偶尔会有一些遗传物质发生非常轻微的变化，这叫复制错误（replication error）。

  • This means that the child might have genetic material information not inherited from either parent

    这意味着 child 可能会拥有一些并不是从任何一个 parent 直接继承来的遗传信息。

  • This can be 可能是以下几种情况

    • catastrophic: offspring is not viable

      灾难性的：offspring 无法正常存活

    • neutral: new feature not influences fitness

      中性的：新特征不会影响 fitness

    • advantageous: strong new feature occurs

      有利的：出现了一个很有优势的新特征

  • Redundancy in the genetic code forms a good way of error checking

    遗传密码中的冗余提供了一种很好的错误检查机制

Evolution and Learning 进化与学习

Lamarckian Inheritance 拉马克式遗传

  • Inheritance of acquired characteristics

    获得性特征的遗传

  • Parent organism can pass onto its offspring physical characteristics acquired through use or disuse during its lifetime

    亲代生物可以把自己一生中因为某些身体结构的使用或不用而获得的身体特征，传给后代。

  • The classic view is not supported by biological evidence; however, epigenetic inheritance shows a nuanced partial exception

    这种经典观点并没有得到生物学证据支持；不过，表观遗传（epigenetic inheritance）显示出一种更细微的、部分例外情况。

Baldwin Effect 鲍德温效应

  • Phenotype-first theory of evolution

    一种“表现型优先”的进化理论

  • Organism’s ability to learn new behaviours affects its reproductive success

    生物学习新行为的能力会影响它的繁殖成功率

  • Therefore has an effect on the genetic makeup of its species through natural selection

    因此，通过自然选择，学习能力会影响整个物种的遗传组成

  • Learning can accelerate evolution

    学习可以加速进化

Terminology 术语

  • Terms borrowed from biology

    从生物学借用的术语

    • Genotype: underlying representation, that is manipulated by evolution

      Genotype：底层表示，也就是进化过程中实际被操作的表示。

    • Phenotype: expressed behavior or solution, that is optimized by evolution

      Phenotype：实际表现出来的行为或 solution，也就是进化最终要优化的东西。

    • Genome (chromosome): string representing the genetic encoding for the problem solution

      Genome（chromosome）：表示问题 solution 遗传编码的一串数据。

    • Gene: subpart of genome (chromosome) that maps to a particular feature/behavior in the phenotype

      Gene：genome / chromosome 的一部分，它对应 phenotype 中某个具体 feature 或 behavior。

    • Allele: a particular feature value of the gene

      Allele：某个 gene 的具体特征值。

    • Locus: position in the chromosome

      Locus：gene 在 chromosome 中的位置。