遗传算法 - 基础知识

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

基本术语

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

**种群** − 它是在给定问题的所有可能（编码）解中的一部分。遗传算法的种群类似于人类的种群，只不过我们用候选解来表示人类。
**染色体** − 染色体是给定问题的一个解。
**基因** − 基因是染色体的一个元素位置。
**等位基因** − 它是一个基因对于特定染色体所取的值。

**基因型** − 基因型是在计算空间中的种群。在计算空间中，解以一种易于使用计算系统理解和操作的方式表示。
**表现型** − 表现型是在实际现实世界解空间中的种群，其中解以现实世界中表示的方式表示。
**解码和编码** − 对于简单问题，**表现型和基因型**空间相同。但是，在大多数情况下，表现型和基因型空间是不同的。解码是从基因型到表现型空间转换解的过程，而编码是从表现型到基因型空间转换的过程。解码应该很快，因为它在遗传算法中在适应度值计算期间被反复执行。

例如，考虑0/1背包问题。表现型空间包含仅包含要选择的物品的物品编号的解。

但是，在基因型空间中，它可以表示为长度为n的二进制字符串（其中n是物品的数量）。**位置x处的0**表示**第x个**物品被选中，而1表示相反。这是一种基因型和表现型空间不同的情况。

**适应度函数** − 简单来说，适应度函数是一个以解作为输入并产生解的适用性作为输出的函数。在某些情况下，适应度函数和目标函数可能相同，而在其他情况下，根据问题可能不同。
**遗传算子** − 这些改变后代的遗传组成。这些包括交叉、变异、选择等。

基本结构

遗传算法的基本结构如下：

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

以下每个步骤将在本教程后面的单独章节中介绍。

遗传算法的通用伪代码在以下程序中解释：

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

打印页面