遗传算法库GALib的介绍与应用

遗传算法是一种模拟自然选择和遗传学机制的搜索算法,广泛应用于优化问题。GALib是一个小型的C#库,它提供了遗传算法的实现框架,使得开发者可以更容易地在自己的应用程序中集成遗传算法。GALib是完全开源的,遵循GNU通用公共许可证。

在开发一个解决旅行商问题的应用程序时,创建了这个库。这个想法来自于阅读了《生物启发式人工智能》一书的第一部分,作者是达里奥·弗洛雷亚诺和克劳迪奥·马蒂乌西。决定将所学付诸实践,以测试自己的能力。所有的工作都是在业余时间完成的。

使用代码

本节将解释如何使用GALib创建自己的遗传算法实现。如果不熟悉遗传算法的工作原理,建议先阅读相关的维基百科文章或CP上的许多优秀文章。本节将首先介绍实际的进化过程是如何进行的,然后是如何通过指定个体类型来创建自己的特定实现。

在GALib中,Population类是核心。它是一个指定类型的个体集合,可以在其上进行进化(选择和繁殖)。Population类的进化是在后台线程上进行的,可以使用基于等级的选择、截断基于等级的选择、轮盘赌选择和锦标赛选择。每当生成新一代、找到新的最适个体或进化完成时,都会触发事件。

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

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

Population将自动用size数量的新个体填充自己。由于Population是个体的列表,可以自己添加、移除和操作成员。然而,一旦进化开始,这是非常不推荐的。

可以选择几种选择算法:

  • 基于等级的选择:基于等级的选择根据个体的适应度等级分配繁殖槽位。可以通过调用DoRankBasedSelection方法来启动基于等级的选择。同样,可以通过调用DoTruncatedRankSelection方法来执行截断等级选择,该方法接受一个Int32参数,指示n。
  • 轮盘赌选择:轮盘赌选择根据个体的适应度按比例分配繁殖槽位。可以通过调用DoRouletteWheelSelection方法来启动轮盘赌选择。
  • 锦标赛选择:锦标赛选择包括将繁殖槽位分配给随机选择的子集中最好的个体。Population包含几个重载的DoTournamentBasedSelection方法,允许举行固定大小或在两个界限之间的可变大小的比赛,这两个界限可以指定为个体数量或种群大小的百分比。

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

Population类包含三个事件,它们将在进化过程中的不同点触发:

  • GenerationComplete (Object sender, GenerationCompleteEventArgs e):每次代完成时发生。这意味着选择、繁殖和适应度确定已经按顺序发生。GenerationCompleteEventArgs包含当前代数和代中最适合的个体。
  • NewFittest (Object sender, NewFittestEventArgs e):当找到新的总体最适合个体时发生。NewFittestEventArgs包含当前代数和总体最适合的个体。
  • EvolutionComplete (Object sender, EvolutionCompleteEventArgs e):进化完成时发生。

Population类包含以下最重要的属性,它们允许大幅改变算法的工作方式:

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

继承Individual会迫使实现一些抽象方法:

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

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

沪ICP备2024098111号-1
上海秋旦网络科技中心:上海市奉贤区金大公路8218号1幢 联系电话:17898875485