03-通用的遗传算法

选择背景色：黄橙洋红淡粉水蓝草绿白色选择字体：宋体黑体微软雅黑楷体选择字体大小：小中大特恢复默认

5.2　通用的遗传算法

遗传算法通常是高度专用的，需要针对特定应用进行调优。在本章中，我们将定义一种通用的遗传算法，该算法适用于多种问题，且未针对其中任意一类问题进行专门的调优。虽然它会包含一些可配置的选项，但目标仍是为了演示算法的基本原理而不是可调优的程度。

首先我们将定义一个接口，以便定义该通用算法能够操作的个体。抽象类 Chromosome 定义了4种基本特征。染色体必须能够实现以下几个功能。

确定自己的适应度。
创建一个携带了随机选中基因的实例（用于填充第一代个体的数据）。
实现交换，即让自己与另一个同类结合并创建后代，换句话说，就是使自己与另一条染色体混合。
变异——让自己的体内数据发生相当随机的小变化。

代码清单5-1中给出了实现上述4个功能的 Chromosome 代码。

代码清单5-1　chromosome.py

from __future__ import annotations
from typing import TypeVar, Tuple, Type
from abc import ABC, abstractmethod
T = TypeVar('T', bound='Chromosome') # for returning self
# Base class for all chromosomes; all methods must be overridden
class Chromosome(ABC):
    @abstractmethod
    def fitness(self) -> float:
        ...
    @classmethod
    @abstractmethod
    def random_instance(cls: Type[T]) -> T:
        ...
    @abstractmethod
    def crossover(self: T, other: T) -> Tuple[T, T]:
        ...
    @abstractmethod
    def mutate(self) -> None:
        ...

提示　在构造函数中，将会把 TypeVar T 与 Chromosome 进行绑定，这意味着任何填入 T 类型变量的对象都必须是 Chromosome 的实例或子类。

算法本身（操纵染色体的代码）将被实现为一个泛型类，以便将来能够为专用的应用程序自由地实现子类化。但首先请重温一下本章开头对遗传算法的描述，清晰定义出执行遗传算法的步骤。

（1）创建随机的染色体初始种群，作为算法的第一代数据。

（2）测算这一代种群中每条染色体的适应度，如果有超过阈值的就将其返回，算法结束。

（3）选择一些个体进行繁殖，适应度最高的个体被选中的概率更大。

（4）某些被选中的染色体以一定的概率发生交换（结合），创建代表下一代种群的后代。

（5）通常某些染色体发生变异的概率比较低。这样新一代的种群就已创建完毕，它将取代上一代种群。

（6）返回第2步继续执行，直至代的数量到达最大值，然后返回当前找到的最优染色体。

以上对遗传算法的概述（如图5-1所示）缺少了许多重要的细节。种群中应该包含多少染色体？算法停止执行的阈值是多少？该如何选择要进行繁殖的染色体？它们该以多大的概率以及如何进行结合（交换）？发生变异的概率是多大？应该运行几代？

图5-1　基因算法概述

所有这些关键点都可以在 GeneticAlgorithm 类中进行配置。后续我们将逐点进行定义，这样就可以单独对每一点进行讨论了。具体代码如代码清单5-2所示。

代码清单5-2　genetic_algorithm.py

from __future__ import annotations
from typing import TypeVar, Generic, List, Tuple, Callable
from enum import Enum
from random import choices, random
from heapq import nlargest
from statistics import mean
from chromosome import Chromosome
C = TypeVar('C', bound=Chromosome) # type of the chromosomes
class GeneticAlgorithm(Generic[C]):
    SelectionType = Enum("SelectionType", "ROULETTE TOURNAMENT")

GeneticAlgorithm 的参数名为 C ，是符合 Chromosome 类的泛型类型。枚举 SelectionType 是一种内部类型，用于指定算法使用的选择方法。最常见的两种遗传算法的选择方法被称为轮盘式选择法（roulette-wheel selection）和锦标赛选择法（tournament selection），轮盘式选择法有时也被称为适应度比例选择法（fitness proportionate selection）。轮盘式选择法让每条染色体都有机会被选中，与其适应度成正比。在锦标赛选择法中，一定数量的随机染色体会相互挑战，适应度最佳的那个染色体将会被选中。具体代码如代码清单5-3所示。

代码清单5-3　genetic_algorithm.py（续）

def __init__(self, initial_population: List[C], threshold: float, max_generations:
     int = 100, mutation_chance: float = 0.01, crossover_chance: float = 0.7, 
     selection_type: SelectionType = SelectionType.TOURNAMENT) -> None: 
    self._population: List[C] = initial_population
    self._threshold: float = threshold
    self._max_generations: int = max_generations
    self._mutation_chance: float = mutation_chance
    self._crossover_chance: float = crossover_chance
    self._selection_type: GeneticAlgorithm.SelectionType = selection_type
    self._fitness_key: Callable = type(self._population[0]).fitness

代码清单5-3中给出了遗传算法的所有属性，它们将在对象被创建时由 __init__() 进行配置。 initial_population 是算法的第一代中的染色体。 threshold 是适应度水平，该水平标示本遗传算法要求解的问题的解已经找到了。 max_generations 表示最多要运行几代。如果我们运行了很多代还没有找到适应度水平超过 threshold 的解，则会返回已找到的最优解。 mutation_chance 是每一代中每条染色体发生变异的概率。 crossover_chance 是被选中繁殖的双亲生育出带有它们的混合基因的后代的概率，若无混合基因的后代，则后代只是其双亲的副本。 selection_type 是要采用的选择法的类型，由枚举 SelectionType 进行说明。

上述 __init__ 方法需要给出一长串的参数，其中大多数都带有默认值。这些参数对上述介绍过的可配置属性建立了实例。本示例采用 Chromosome 类的 random_instance() 方法，把 _population 初始化为一系列随机的染色体。换句话说，第一代染色体只是一群随机的个体。更复杂的遗传算法可以对此做出优化。经过对问题的一些了解，可以不从纯随机的个体开始，第一代种群可以包含更接近于解的个体，这被称为播种（seeding）。

_fitness_key 是对 GeneticAlgorithm 一直都要用到的方法的一个引用，用于计算染色体的适应度。回想一下， GeneticAlgorithm 类需要操纵 Chromosome 的子类，因此， _fitness_key 将因子类的不同而不同。为了能访问它，我们用 type() 来引用当前正待求适应度的 Chromosome 的某个子类。

下面将介绍本类支持的两种选择法。具体代码如代码清单5-4和代码清单5-5所示。

代码清单5-4　genetic_algorithm.py（续）

# Use the probability distribution wheel to pick 2 parents
# Note: will not work with negative fitness results
def _pick_roulette(self, wheel: List[float]) -> Tuple[C, C]:
    return tuple(choices(self._population, weights=wheel, k=2))

依据每个染色体的适应度与同一代所有适应度之和的比例，采用轮盘式选择法做出选择。适应度最高的染色体被选中的概率会更高一些。代表每个染色体适应度的值由参数 wheel 给出。实际的选择过程用 choices() 函数即可很方便地完成，该函数位于Python标准库的 random 模块中。该函数的参数包括待选取的对象列表、该列表中每项的权重的列表（与第一个参数列表等长）和要选中的项数。

如果我们要自己实现 choices() 函数，可以计算每一个列表项占总适应度的百分比（相对适应度），表示为0到1之间的浮点数。用一个0到1之间的随机数（ pick ）即可算出应该选择哪一条染色体。依次使 pick 减去每个染色体的相对适应度，本算法即能正常工作。当 pick 小于0时，就遇到了要选中的染色体。

请问上述过程有道理吗？根据适应度的比例就能让每个染色体可供选择吗？如果没有理解，请拿出纸和笔来思考一下。请画出一个表示比例的轮盘，如图5-2所示。

图5-2　轮盘式选择法实例

最基础的锦标赛选择法要比轮盘式选择法简单。它不需要计算比例，只要随机从整个种群中选出 k 个染色体即可。在这些随机选出的个体中，适应度最佳的两个染色体将会胜出。

代码清单5-5　genetic_algorithm.py（续）

# Choose num_participants at random and take the best 2
def _pick_tournament(self, num_participants: int) -> Tuple[C, C]:
    participants: List[C] = choices(self._population, k=num_participants)
    return tuple(nlargest(2, participants, key=self._fitness_key))

_pick_tournament() 先利用 choices() 从 _population 中随机选取 num_participants 个参赛者，然后利用 heapq 模块中的 nlargest() 函数，找到 _fitness_key 最大的两个个体。 num_participants 应该取多大值合适呢？与遗传算法中的很多参数一样，不断试错可能是最佳方案。有一件事必须牢记，锦标赛的参赛者越多，种群的多样性就会越少，因为适应度较低的染色体将更有可能在竞争中被消灭^[1]。更复杂一些的锦标赛选择法可能会选取不是最强的那些个体，而是基于某种递减概率模型（decreasing probability model）选取第2强或第3强的个体。

_pick_roulette() 和 _pick_tournament() 这两个方法都可用于做出选择，选择在繁殖期间发生。在 _reproduce_and__replace() 中不仅实现了繁殖过程，它还负责确保用包含等量染色体的新种群替换上一代的染色体。具体代码如代码清单5-6所示。

代码清单5-6　genetic_algorithm.py（续）

# Replace the population with a new generation of individuals
def _reproduce_and_replace(self) -> None:
    new_population: List[C] = []
    # keep going until we've filled the new generation
    while len(new_population) < len(self._population):
        # pick the 2 parents
        if self._selection_type == GeneticAlgorithm.SelectionType.ROULETTE:
            parents: Tuple[C, C] = self._pick_roulette([x.fitness() for x in  
            self._population])
        else:
            parents = self._pick_tournament(len(self._population) // 2)
        # potentially crossover the 2 parents
        if random() < self._crossover_chance:
            new_population.extend(parents[0].crossover(parents[1]))
        else:
            new_population.extend(parents)
    # if we had an odd number, we'll have 1 extra, so we remove it
    if len(new_population) > len(self._population):
        new_population.pop()
    self._population = new_population # replace reference

在 _reproduce_and_replace() 中，粗略地实现了以下步骤。

（1）用两种选择法之一选出两条名为 parents 的染色体，用于进行繁殖。若是锦标赛选择法，则始终在整个种群的半数个体中进行竞赛，不过这是一个可配置的选项。

（2）双亲将以一定概率（ _crossover_chance ）结合并产生两条新的染色体，这时两条新的染色体会被添加到 new_population 中。如果没有后代，则把 parents 直接加入 new_population 中。

（3）如果 new_population 拥有与 _population 同样多的染色体，则替换之；否则返回第1步。

实现变异的方法 _mutate() 十分简单，我们将如何执行变异的细节留给了染色体类去实现。具体代码如代码清单5-7所示。

代码清单5-7　genetic_algorithm.py（续）

# With _mutation_chance probability mutate each individual
def _mutate(self) -> None:
    for individual in self._population:
        if random() < self._mutation_chance:
            individual.mutate()

目前我们已经有了运行遗传算法所需的所有构成部分。 run() 负责协同测算、繁殖（包括选择）和变异等步骤，将种群从一代传到下一代。它还会在搜索过程中随时记录下找到的最佳（适应性最强）染色体。具体代码如代码清单5-8所示。

代码清单5-8　genetic_algorithm.py（续）

# Run the genetic algorithm for max_generations iterations
# and return the best individual found
def run(self) -> C:
    best: C = max(self._population, key=self._fitness_key)
    for generation in range(self._max_generations):
        # early exit if we beat threshold
        if best.fitness() >= self._threshold: 
            return best
        print(f"Generation {generation} Best {best.fitness()} Avg {mean(map(self._
 fitness_key, self._population))}")
        self._reproduce_and_replace()
        self._mutate()
        highest: C = max(self._population, key=self._fitness_key)
        if highest.fitness() >best.fitness():
            best = highest # found a new best
    return best # best we found in _max_generations

best 记录了到目前为止发现的最佳染色体。主循环最多执行 _max_generations 次。只要有任何染色体的适应度超过 threshold ，就会返回该染色体，方法也就结束运行；否则就会调用 _reproduce_and_replace() 和 _mutate() 来创建下一代，并再次运行循环。如果循环次数到达 _max_generations ，则返回到目前为止找到的最佳染色体。

Previous 上一篇本节目录 Next 下一篇

03-通用的遗传算法

5.2 通用的遗传算法

5.2　通用的遗传算法