遗传算法 - 基础知识

本节介绍理解 GA 所需的基本术语。此外，GA 的通用结构以伪代码和图形形式呈现。建议读者正确理解本节中介绍的所有概念，并在阅读本教程的其他部分时牢记它们。

基本术语

在开始讨论遗传算法之前，有必要熟悉本教程中将使用的一些基本术语。

  • 人口- 它是给定问题的所有可能（编码）解决方案的子集。遗传算法的种群类似于人类的种群，只不过我们有代表人类的候选解，而不是人类。

  • 染色体- 染色体就是给定问题的解决方案之一。

  • 基因- 基因是染色体的一个元素位置。

  • 等位基因- 它是基因对特定染色体的值。

术语

  • 基因型- 基因型是计算空间中的群体。在计算空间中，解决方案以易于使用计算系统理解和操作的方式表示。

  • 表型- 表型是实际现实世界解决方案空间中的群体，其中解决方案以现实世界情况中表示的方式表示。

  • 解码和编码- 对于简单的问题，表型和基因型空间是相同的。然而，在大多数情况下，表型和基因型空间是不同的。解码是将解从基因型空间转换到表型空间的过程，而编码是从表型空间转换到基因型空间的过程。解码应该很快，因为在适应度值计算过程中，它在 GA 中重复执行。

    例如，考虑 0/1 背包问题。表型空间由仅包含要挑选的项目的项目编号的解决方案组成。

    然而，在基因型空间中，它可以表示为长度为 n 的二进制字符串（其中 n 是项目数）。位置 x 处的 0表示第x个项目被选取，而 1 则表示相反的情况。这是基因型和表型空间不同的情况。

表型和基因型空间

  • 适应度函数- 简单定义的适应度函数是将解作为输入并产生解的适用性作为输出的函数。在某些情况下，适应度函数和目标函数可能相同，而在其他情况下，根据问题的不同，适应度函数和目标函数可能会有所不同。

  • 遗传运算符- 这些改变后代的遗传组成。其中包括交叉、变异、选择等。

基本结构

GA 的基本结构如下 -

我们从初始群体（可能是随机生成的或通过其他启发式播种）开始，从该群体中选择父母进行交配。对父母应用交叉和变异算子以生成新的后代。最后，这些后代取代了种群中现有的个体，这个过程不断重复。通过这种方式，遗传算法实际上试图在某种程度上模仿人类的进化。

本教程后面的每个步骤将作为单独的章节进行介绍。

基本结构

下面的程序解释了 GA 的通用伪代码 -

GA()
   initialize population
   find fitness of population
   
   while (termination criteria is reached) do
      parent selection
      crossover with probability pc
      mutation with probability pm
      decode and fitness calculation
      survivor selection
      find best
   return best