65.9K
CodeProject 正在变化。 阅读更多。
Home

C# 中的进化计算

Andrew Kirillov
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.93/5 (71投票s)

2006年10月16日

GPL3

13分钟阅读

viewsIcon

293587

downloadIcon

8294

本文描述了一个用于进化计算的 C# 库及其在多个问题求解中的应用。

Sample Image - dna.jpg

引言

进化计算领域有许多不同的研究工作，这导致了各种不同的进化算法的出现。许多研究人员广泛研究了这些方法，并尝试将其应用于广泛的任务。众所周知，存在许多传统方法无法在合理时间内精确解决的问题。此外，许多问题没有形式化的解决方案方法，这使得使用传统方法解决它们非常困难甚至不可能。例如旅行商问题 (TSP)，它要求找到一条绕过指定数量的城市、仅访问一次所有城市并最终返回起始城市的最短路径。对于其中一些问题，可以应用进化计算，在许多情况下，这可以在合理的时间内找到一个好的解决方案。这些方法不能保证找到特定问题的精确解决方案，但它们可以找到一个非常好的解决方案，可能非常接近最佳解决方案。这就是为什么这些方法在解决许多传统方法无法解决（或解决方案非常困难）的各种问题中变得相当流行。

在本文中，将讨论一个用于进化计算的 C# 库。该库实现了几种流行的进化算法，如遗传算法 (GA)、遗传编程 (GP) 和基因表达编程 (GEP)，并可用于解决许多不同的问题。该库的用法在四个示例中得到演示：函数优化、符号回归（逼近）、时间序列预测、旅行商问题。该库的主要思想是使其灵活且可重用，从而允许它用于解决不同的问题。本文无意详细描述进化算法。相反，本文简要介绍了这些算法的思想，并提供了一系列参考文献，以便详细研究这些方法。

进化计算

遗传计算的历史始于 20 世纪 60 年代，当时 John Holland 提出了该主题的第一批工作，他基于进化思想提出了遗传算法 (GA) 的最初想法。自那时以来，进化计算领域的研究工作很多，这导致了许多不同的方法出现 [1]。其中大多数方法都得到了广泛研究，并应用于许多不同的问题求解，在其中大部分问题上都产生了非常好的性能。尽管遗传计算有着悠久的历史，但这些方法仍在积极研究中，并且出现了不同的新方法，拓宽了可以使用这些方法解决的问题范围。

GA 基于达尔文的繁殖和适者生存原则以及自然发生的遗传操作（如交叉（重组）和变异）的类似物。该方法操作一个由个体（染色体）组成的种群，其中每个个体都编码了遗传算法所应用问题的可能解决方案。在 GA 中，染色体由固定长度的字符串（位串、数字等）表示，这使得遗传算子的实现非常简单。最初，种群是用随机染色体初始化的，然后通过应用交叉、变异和选择等遗传算子开始进化。

最简单的交叉变体是单点交叉——选择两个染色体的随机点，然后交换这两个染色体的部分。

One point crossover

另一种流行的交叉算子变体是双点交叉——选择两个随机点，然后在两个点之间交换染色体的部分。这两种交叉变体在 GA 中最受欢迎，但并非唯一存在的。实际上，这种算子有许多不同的变体，这些变体因问题而异。有些问题不适用于这两种经典交叉变体，因此它们有自己针对该问题的自定义变体。

变异算子只操作一个染色体，并且只是随机地改变染色体。单点变异只改变染色体中的一个基因。

One point mutation

与交叉一样，变异算子也有许多针对特定类型问题的变体。

因此，在初始种群创建后，GA 算法的每次迭代都包含以下步骤：

  1. 交叉 - 选择随机个体并对它们应用交叉算子；
  2. 变异 - 选择随机个体并对它们应用变异算子；
  3. 计算每个个体的适应度值；
  4. 选择 - 为新一代选择个体。

算法可以在指定的迭代次数后停止，也可以在找到一个合理好的解决方案后停止。染色体适应度值的计算取决于问题——该值显示染色体有多好。值越高，染色体越好，这给了它更多的机会被选入下一代。

存在几种选择算子 [1]。它们的主要思想是通过给予适应度值较高的较好个体更多的机会来选择下一代的个体。最流行的方法之一称为精英主义——选择一定数量的最佳染色体进入下一代。

1992 年，John Koza 提出了一种新的显著方法——遗传编程 (GP) [2]。在 GP 中，个体种群成员（染色体）不是编码问题可能解决方案的固定长度线性字符字符串，如 GA 中所示，而是执行后可提供问题解决方案的程序。在 GP 中，这些程序以各种大小和形状的解析树表示，这使得这些方法在应用到广泛的问题时具有灵活性。染色体表示的差异是这种方法与 GA 之间唯一的主要差异。整体的达尔文主义的生存思想保持不变，但在变异和交叉算子以及适应度函数计算方面存在变化。在 GP 中，变异算子可以再生单个树节点或染色体树的整个子树，而不是改变字符串染色体中的单个基因。交叉也是如此——在 GP 中，染色体交换的是它们的子树，这些子树的大小和形状都可能不同，而不是交换相同长度的染色体部分。然而，始终需要对染色体进行一些检查，并在它们变得过长时进行修剪。

要计算 GP 中个体染色体的适应度值，不会仅仅将染色体作为值传递给某种计算适应度值的函数。相反，需要执行染色体所表示的程序，并根据程序的输出计算适应度值。

2001 年，Candida Ferreira 引入了另一种称为基因表达编程 (GEP) 的方法 [3]。该方法在思想上与遗传编程和遗传算法相似。一方面，该方法也操作程序，执行后可提供解决方案，这使其类似于 GP。但 GEP 中这些程序的表示方式不同。在这种方法中，染色体不表示为树，而是像 GA 中一样，是固定长度的线性实体。这种染色体表示的变化使得交叉和变异等遗传算子的实现更简单，但存在一些小限制以确保这些算子安全。

Genetic tree * + / a b c a
(a) (b)
GP (a) 和 GEP (b) 中的染色体表示

上图显示了 GP 和 GEP 方法中染色体表示的差异。两个染色体都编码相同的程序——代数表达式 (a + b) * (c / a)。GP 将染色体表示为表达式的解析树，而 GEP 则将其表示为线性字符串，其中上面解析树的节点以从左到右、从上到下的顺序书写。GEP 字符串可以通过从左到右、从上到下填充，同时考虑每个函数参数的数量信息，轻松地转换回解析树。

使用库

创建库时，主要思想是使其灵活且可重用，从而允许其用于解决不同的问题。库的代码不依赖于任何特定问题，而是实现了进化计算的一般概念以及遗传算法、遗传编程和基因表达编程等算法。进化计算的实体，如种群、染色体、选择方法和适应度函数，被实现为独立的类，这使得它们易于组合以解决特定问题。在大多数情况下，库用户只需为他的问题定义一个适应度函数，然后定义染色体类型、选择算法和其他一些参数，如种群大小、变异率和交叉率等。如果特定问题需要某些特定的染色体变体或变异和交叉等遗传算子，用户可以创建自己的实现 IChromosome 接口或从现有的染色体类派生的染色体类。选择方法和适应度函数也是如此——如果有人需要自定义选择算法或适应度函数，则需要分别创建实现 ISelectionMethod 或 IFitnessFunction 接口的类。创建任何实现了上述定义的接口的自定义类后，这些类将与库中的所有其他类一起工作，扩展库并允许解决特定问题。

Library class diagram

为了演示该库的用法，将描述四个示例，它们使用了不同的进化计算算法。

  • 函数优化（遗传算法）；
  • 符号回归（遗传编程和基因表达编程）；
  • 时间序列预测（遗传编程和基因表达编程）；
  • 旅行商问题（遗传算法）。

函数优化

Function Optimization

函数优化是演示遗传算法的经典问题之一。要使用该库解决该问题，您只需定义在优化范围内为正的优化函数，然后创建一个遗传种群，指定进化算法所需的参数。

// define optimization function
public class UserFunction : OptimizationFunction1D
{
    public UserFunction( ) :
        base( new DoubleRange( 0, 255 ) ) { }

    public override double OptimizationFunction( double x )
    {
        return Math.Cos( x / 23 ) * Math.Sin( x / 50 ) + 2;
    }
}
...
// create genetic population
Population population = new Population( 40,
    new BinaryChromosome( 32 ),
    new UserFunction( ),
    new EliteSelection( ) );
// run one epoch of the population
population.RunEpoch( );

在上面的示例中，创建了一个由 40 个染色体组成的种群，其中每个染色体都是一个 32 位长的二进制染色体，使用了精英选择方法，并使用了一个旨在优化一维函数的适应度函数。在上面的示例和所有其他示例中，您不会看到对遗传算法或其他进化方法的任何明确引用。所有实现的遗传方法中的种群创建都是相同的。决定所使用方法类型的主要因素是染色体本身，因为染色体定义了问题解决方案的表示以及所用遗传算子的实现。

符号回归（逼近）

Function Optimization

符号回归问题的目标是找到输入数据的最佳逼近函数。为了解决该问题，可以使用遗传编程或基因表达编程方法。使用这两种方法，都可以找到一个表达式，该表达式以 X 值和一些常数作为参数，并提供一个输出值，该值非常接近实际函数的 Y 值。

解决该问题的代码与上述代码相当相似。我们将使用相同的种群类和相同的选择方法类。唯一不同的部分是适应度函数，这是显而易见的，因为我们面临的是另一个问题，还有染色体类。要解决任务，如果我们要使用遗传编程方法，可以使用 GPTreeChromosome 类；如果我们要使用基因表达编程，则可以使用 GEPChromosome 类。

// function to be approximated
double[,] data = new double[5, 2] {
    {1, 1}, {2, 3}, {3, 6}, {4, 10}, {5, 15} };
// create population
Population population = new Population( 100,
    new GPTreeChromosome( new SimpleGeneFunction( 6 ) ),
    new SymbolicRegressionFitness( data, new double[] { 1, 2, 3, 5, 7 } ),
    new EliteSelection( ),
    0.1 );
// run one epoch of the population
population.RunEpoch( );

在上面的示例中，要逼近的函数由二维 (X, Y) 对数组定义。上述示例的另一个有趣之处是 Population 类的构造函数的最后一个参数——该值指定新一代的 10% 由新的随机染色体组成，而 90% 将是当前一代的最佳成员。

时间序列预测

Time Series Prediction

时间序列预测问题旨在构建一个模型，该模型根据历史（过去的函数值）预测未来的函数值。为了实现这一目标，模型是在提供的训练数据集样本上构建（训练）的，当模型在训练集上开始产生令人满意的结果时，模型将被用于预测未来的函数值。

// time series to predict
double[] data = new double[13] { 1, 2, 4, 7, 11, 16, 22, 29, 37, 46, 56, 67, 79 };
// constants
double[] constants = new double[10] { 1, 2, 3, 5, 7, 11, 13, 17, 19, 23 };
// sliding window size
int windowSize = 5;
// create population
Population population = new Population( 100,
new GPTreeChromosome( new SimpleGeneFunction( windowSize + constants.Length ) ),
new TimeSeriesPredictionFitness( data, windowSize, 1, constants ),
new EliteSelection( ) );
// run one epoch of the population
population.RunEpoch( );

正如您所看到的，时间序列预测问题的代码与符号回归问题的代码几乎相同——我们只更改了适应度函数和算法的一些参数。这一事实证明了该库的易用性和可重用性。

旅行商问题

Traveling Salesman Problem

旅行商问题旨在找到一条绕过指定数量的城市、仅访问每个城市一次并最终返回起始城市的最短路径。该问题被称为 NP-hard 问题，对于大量城市，使用传统方法解决它可能需要极长的时间。然而，可以使用遗传算法来找到该问题的一个相当接近精确解的解决方案，并且在合理的时间内。

// create population
Population population = new Population( populationSize,
    new PermutationChromosome( citiesCount ),
    new TSPFitnessFunction( map ),
    new EliteSelection( )
    );

考虑到 PermutationChromosome 类是库的一部分，我们看到，只需为新问题创建一个新的适应度函数 (TSPFitnessFunction)，并使用其余现有代码即可解决新问题。然而，可以改进算法的性能。默认的通用 PermutationChromosome 类可以找到或多或少好的解决方案，但继承该类并重写交叉算子将带来更好的性能。自定义 TSPChromosome 类（请参阅应用程序源代码）实现了所谓的贪婪交叉，这使得在更短的时间内找到更好的解决方案成为可能。

多年来，遗传算法方法在解决旅行商问题方面一直提供最佳结果。这个问题非常受欢迎且实际，以至于每年都会为解决该问题的最佳方法举行一次竞赛。而且众所周知，在 20 世纪 90 年代末，出现了另一种用于解决该问题的方法，并且其性能得到了提高。这种新方法也来自人工智能领域，并且基于蚂蚁群体的思想（请参阅蚁群算法 (AS) 和蚁群系统 (ACS) 算法）。

结论

演示的四个示例表明，该库实现了最初的目标——使其灵活、可扩展、可重用且易于使用。尽管仍有大量工作要做，因为目前进化计算方法种类繁多，但该库仍然可以用于解决许多不同的问题，并且可以轻松扩展以解决新问题。该库的工作不仅帮助我深入了解了进化方法，而且其成果也帮助了我进行遗传编程和基因表达编程算法的研究。

参考文献

  1. Ajith Abraham, Nadia Nedjah and Luiza de Macedo Mourelle, Evolutionary Computation: from Genetic Algorithms to Genetic Programming // Genetic Systems Programming: Theory and Experiences, volume 13 of Studies in Computational Intelligence, pages 1-20. Springer, Germany, 2006.
  2. John R. Koza, Genetic Programming // Version 2 – Submitted August 18, 1997 for Encyclopedia of Computer Science and Technology.
  3. Ferreira, C., Gene Expression Programming: A new adaptive algorithm for solving problems // Complex Systems, Vol. 13, No. 2, pp. 87–129, 2001.

历史

  • [2006年10月16日] - 文章的初步发布
© . All rights reserved.