遗传算法 - 基础知识

本节介绍理解遗传算法所需的基本术语。此外，还以伪代码和图形形式介绍了遗传算法的通用结构。建议读者正确理解本节介绍的所有概念，并在阅读本教程的其他部分时牢记这些概念。

基本术语

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

• 种群 − 它是给定问题所有可能(编码)解决方案的子集。 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