GALib

• 下载 GALib 0.1 DLL - 10.8 KB
• 下载 GALib 0.1 项目源代码 - 25.4 KB
• 从 SourceForge 下载 GNU tarball

引言

GALib 是一个小型 C# 库，提供基于遗传算法功能的脚手架。它完全开源，并根据 GNU 通用公共许可证提供。

背景

我在开发一个解决旅行商问题的应用程序时创建了这个库。创建该应用程序的想法来自于阅读 Dario Floreano 和 Claudio Mattiussi 的《仿生人工智能》的第一部分。我想我需要实现我所读到的内容来检验自己。所有工作均在我业余时间完成。

使用代码

本节将介绍如何使用 GALib 创建您自己的 GA 实现。如果您不熟悉遗传算法的工作原理，建议您先仔细阅读此维基百科文章及相关页面，或这里 CP 上的众多精彩文章之一。本节将首先介绍实际的进化是如何进行的，然后通过指定个体类型来介绍如何创建您自己的特定实现。

类图

Population 类

Population 类是 GALib 的核心。它是一个由您指定的类型的个体组成的集合，可以在其上进行进化（选择和繁殖）。种群的进化是在后台线程上进行的，可以通过基于排名的选择、截断的基于排名的选择、轮盘赌选择和锦标赛选择来进行。每次创建新一代、找到新的最适应个体或进化完成时，都会触发事件。

构造函数

构造函数允许您指定一些在多种用例中可能不同的通用属性。这些属性包括：

• size - 可选。Int32。种群的大小（个体数量）。默认为 100。
• generations - 可选。Int64。进化的最大代数。默认为 100000。
• stagnationLimit - 可选。Int64。无适应度改进的最大代数。默认为 10000。

Population 会自动用 size 个新个体填充自身。由于 Population 是个体列表，您可以自行添加、删除和操作成员。但是，一旦进化开始，强烈不建议这样做。

进化方法

您可以在几种选择算法之间进行选择：

• 基于排名的选择

基于排名的选择根据个体的适应度排名分配繁殖名额。您可以使用 DoRankBasedSelection 方法启动基于排名的选择。同样，您可以进行截断的排名选择，这是一种只考虑前 n 个个体的排名选择，通过调用 DoTruncatedRankSelection 方法来实现，该方法接受一个表示 n 的 Int32 参数。

• 基于轮盘赌的选择

基于轮盘赌的选择根据个体的适应度成比例地分配繁殖名额。您可以使用 DoRouletteWheelSelection 方法启动基于轮盘赌的选择。

• 基于锦标赛的选择

基于锦标赛的选择包括将繁殖名额分配给随机选择的子集中的最佳个体。Population 包含几个重载的 DoTournamentBasedSelection 方法，允许您进行固定大小的锦标赛，或固定范围内的可变大小锦标赛，这两种都可以通过个体数量或种群大小的百分比来指定。

您可以通过调用 CancelEvolution 方法来停止进化。进化工作的后台线程将在当前一代完成后结束。

每一代之后，个体将根据其适应度排序，最适应者在前。这意味着 populationInstance[0] 将为您提供该代的最适应个体，而 populationInstance[populationInstance.Count - 1] 将获得适应度最低的成员。您还可以使用 GetFittest 来获取最适应个体的一个范围。它接受一个表示范围大小的 Int32 和一个表示是否包含精英个体的布尔值。

事件

Population 类包含三个事件，将在进化过程的各个阶段触发：

• GenerationComplete (Object sender, GenerationCompleteEventArgs<IndividualType> e)

每当一代完成时触发。这意味着依次发生了选择、繁殖和适应度确定。 GenerationCompleteEventArgs 包含当前代号和该代最适应的个体。

• NewFittest (Object sender, NewFittestEventArgs<IndividualType> e)

找到新的总体最适应个体时触发。 NewFittestEventArgs 包含当前代号和总体最适应个体。

• EvolutionComplete (Object sender, EvolutionCompleteEventArgs<IndividualType> e)

属性

下表列出了 Population 类最重要的属性，这些属性允许您极大地改变算法的工作方式。

个体

对于您自己的实现，您需要指定您自己的个体类型。这些类型的定义包含初始化、变异和交叉方法，以及基因型规范和适应度函数。GALib 提供了一个 IIndividual 接口和 Individual 抽象类作为脚手架。您必须在个体类型定义中实现该接口，才能创建您的类型种群。您可以（很可能应该）继承自 Individual，它将为您节省一些基本工作，并为您实现 IIndividual。

Individual 类

继承 Individual 会强制您实现一些抽象方法：

• void doBaseInitialization()
• void doRandomInitialization()
• void doMutation()
• void doCrossover(IIndividual mother, IIndividual father)
• Double determineFitness()

有关 Individual 所做的其他工作的详细信息，请参阅该类本身的源代码。

关注点

由于我创建这个库的主要动机是练习，我在构建它的过程中学到了很多。这是我写过的第一个 C# 库，也是我第一次进行任何 GA 编程（或 AI 编程）。以一种可以用于通用 GA 的方式抽象库非常有趣，它要求我扩展了我对如何使用接口和继承的知识，并首次以非基本的方式使用泛型。

另请参阅

• SourceForge 项目页面
• SourceForge SVN 存储库
• Skynet - 使用 GALib 实现的旅行商问题。
• 本文档的 Wiki 版本.

历史

• 版本 0.1：2010-01-24：初始发布。