遗传算法是一种模拟自然选择和遗传学机制的搜索算法,广泛应用于优化问题。GALib是一个小型的C#库,它提供了遗传算法的实现框架,使得开发者可以更容易地在自己的应用程序中集成遗传算法。GALib是完全开源的,遵循GNU通用公共许可证。
在开发一个解决旅行商问题的应用程序时,创建了这个库。这个想法来自于阅读了《生物启发式人工智能》一书的第一部分,作者是达里奥·弗洛雷亚诺和克劳迪奥·马蒂乌西。决定将所学付诸实践,以测试自己的能力。所有的工作都是在业余时间完成的。
本节将解释如何使用GALib创建自己的遗传算法实现。如果不熟悉遗传算法的工作原理,建议先阅读相关的维基百科文章或CP上的许多优秀文章。本节将首先介绍实际的进化过程是如何进行的,然后是如何通过指定个体类型来创建自己的特定实现。
在GALib中,Population类是核心。它是一个指定类型的个体集合,可以在其上进行进化(选择和繁殖)。Population类的进化是在后台线程上进行的,可以使用基于等级的选择、截断基于等级的选择、轮盘赌选择和锦标赛选择。每当生成新一代、找到新的最适个体或进化完成时,都会触发事件。
构造函数允许指定一些可能在多个用例中不同的通用属性。这些属性包括:
Population将自动用size数量的新个体填充自己。由于Population是个体的列表,可以自己添加、移除和操作成员。然而,一旦进化开始,这是非常不推荐的。
可以选择几种选择算法:
可以通过调用CancelEvolution方法来停止进化。进化所在的工作线程将在当前代完成后结束。
Population类包含三个事件,它们将在进化过程中的不同点触发:
Population类包含以下最重要的属性,它们允许大幅改变算法的工作方式:
继承Individual会迫使实现一些抽象方法:
void doBaseInitialization()
void doRandomInitialization()
void doMutation()
void doCrossover(IIndividual mother, IIndividual father)
Double determineFitness()
有关Individual所做的其他工作的详细信息,请参见该类本身的源代码。