一种基于Jenetics的遗传算法程序设计

王康

摘要：介绍了一个基于Java语言的遗传算法库Jenetics，分析了它的设计思想，原理以及整体架构。针对使用计算机程序来模拟演化目标图片的问题，提出了一种基于Jenetics的遗传算法的解决方案。

关键词： 遗传算法； 程序设计； Jenetics；

中图分类号：TP18 文献标识码：A 文章编号：1009-3044（2018）22-0169-02

Abstract：Jenetics is a genetic algorithm library based on Java programing language.Its design principal and overall architecture is analyzed. A solution based on Jenetics and genetic algorithm is proposed to solve the problem of evolving images by computer program.

Key words：genetic algorithm； program； Jenetics

1 引言

遺传算法是一种受自然选择和进化思想启发的一种高效并行的全局搜索算法。它依赖于几个生物遗传算子，包括选择，交叉以及变异等机制。自60年代初美国的密歇根大学的J.Holland教授提出以来，经历长期的发展，现在被广泛应用于人工智能的各个领域中。

遗传算法的思想虽然简单，但是实现遗传算法的程序，与一般的算法相比，通常是比较复杂的，所以为了方便编写遗传算法程序，在实际应用中，人们普遍会使用一些遗传算法库来解决问题。Jenetics是一个使用现代的Java面向对象程序设计语言的高级的遗传算法库。它很好地定义了遗传算法的主要算法概念，包括基因（Gene），染色体（Chromosome），种群（Population）以及适应度函数（Fitness Function）。

2 Jenetics的设计原理

2.1 算法设计

遗传算法是一种通过模拟自然进化的过程搜索最优解的方法，使用遗传算法的程序使用的算法基本上都是相通的，关键在于找到目标问题的遗传学表达，也就是为当前的问题建立一个合适模型。Jenetics使用的是经典的遗传算法，其基本步骤如下：

（1）创建初始种群。

（2）计算适应度。

（3）种群代数增加1。

（4）选择幸存者和后代种群。

（5）被选择的后代产生变异。

（6）去掉死亡的种群，结合幸存者种群和变异的后代种群形成新种群。

（7）反复执行（3）至（6）直到一定的结束标准被满足。

2.2 整体架构设计

Evolution Stream是Jenetics的基本类，它实现了Java 8 Stream的应用程序接口。 因此它不需要命令式的执行演化的步骤。Evolution Stream是由Evolution Engine驱动的。Evolution Engine执行每一代的演化的步骤。

图1中的ES（i）代表EvolutionStart对象（第i代），而ER（i）代表 EvolutionResult（第i代）。一旦Evolution Engine被创建，它就可被用于多个EvolutionStreams。如果limit断言返回真，则进化过程会继续，如果为假则EvolutionStream将中止。最后程序从EvolutionResult收集器收集EvolutionStream的结果。得到ER（best），也就是最终的演化结果。需要指出的是，Evolution Engine是非确定性的，也就是说，如果用同样初始条件两次调用前述过程，会产生不同的种群。

图2显示了演化相关的类的静态结构和它的依赖。因为Engine类是不可变的，而且创建后不能被修改，所以它是通过一个Builder来实例化和配置的。Engine可以被用于创建任意一个EvolutionsStream。EvolutionStream用于控制演化过程并收集最终的结果。就像普通的java.util.stream包里的Stream类一样。Engine和EvolutionStream的分离，就像演化的定义和演化的执行分离一样。

2.3 基础类

Jenetics的类库可以被分为三大类别：

（1）领域类（Domain Classes）。这些类构成了遗传算法的领域模型，它们一般都是数据类。

（2）操作类（Operation Classes）。这些类主要用于操作领域类，可以产生变异和进行选择。

（3）引擎类（Engine Classes）。这些类用于实现遗传算法。

Jenetics中的主要的Java类可总结如表1。

3 Jenetics的应用

演化目标图片是一个遗传算法的常见的应用，它使用半透明的多边形（也可采用三角形），来把目标图片尽可能准确的画出来。它实际上是一种用演化算法来逼近目标图片，作为一个近似最优解。

3.1设计步骤

第一步，建立模型。首先，根据演化的对象的特点可知，一个多边形就对应一个基因，于是可定义一个实现了Gene接口的领域类PolygonGene。然后，由多个基因构成染色体，于是可定义一个继承了AbstractChromosome的PolygonChromosome，它的基因类型为PolygonGene。

第二步，设计适应度函数，由于已经有一个明确的演化标准，也就是目标图片，于是可以用多边形近似产生的临时图片和目标图片进行像素到像素的对比，差距越小表示适应度越高。具体的，先产生一个Graphics2D对象，然后再使用PolygonChromosome将近似结果在这个对象上绘出，最后，将位于相同位置的像素点所对应的颜色值相减得到差。

第三步，分配选择器（Selector）。选择器用于将种群分为幸存者和后代，可以为幸存者和后代分别指定自己的选择器。Jenetics总共提供了10种选择器，这里只介绍要在本应用中使用到的TournamentSelector。在TournamentSelector的算法中，最佳的个体来自一个随机抽取的s只个体，它的选取规则是，最佳个体的适应度函数值要大于其他的s-1只个体的适应度函数值。自然选择的压力可以通过调节s的值来实现。当s的值较大时，弱个体被选择的可能性比较小。在本应用中，幸存者和后代的选择器都设置为TournamentSelector。

第四步，选择变化器（Alterer），变化器是Jenetics用于实现遗传多样化的措施，在Jenetics提供了两种类型的变化器，一种是变异（Mutation），一种是重组（Recombination）。对于变异，类似于生物的变异，它在遗传过程中主要起到了两种作用：一是探索搜索空间，即通过小步的变化产生变异，但这种探索方式较重组会比较慢；二是保持多样性，变异可以防止一个种群过于关联。对于重组（或者说是），它的过程和生物的生殖过程类似，是通过组合亲染色体来产生新的染色体。本应用中使用到的重组类型为UniformCrossover。

3.2 运行参数设计

演化目标图片程序的主要参数如下表2所示，这些参数将保存在一个文本文件engine.properties中，运行程序时读入。

3.3 运行结果

使用Java Swing设计的图形界面，运行结果如图3所示。左上为源图片（目标图片），右侧为通过多边形演化产生的图片。可以看出目标图片演化的结果基本的形状和颜色已经比较接近，但局部的细节的差异还是比较明显。这主要是因为演化的年代数还比较少，如果再多演化一段时间，可得到更好的结果。

4 结 论

Jenetics是一个优秀的遗传算法库，它基于主流的面向对象的Java语言实现，设计思路符合经典的遗传算法。在设计的各个环节，为应用程序开发者提供了很多的选择。同时它又是可扩展的，通过Java的类继承机制，开发者可以根据自己的需要编写符合自己需要的类，以满足一些特殊情况下的要求。本文提供的演化目标图片程序，是一个基于Jenetics的较为复杂的应用，但与遗传算法相关的核心代码只需要不到10行，可见Jenetics确实可以简化遗传算法的开发。

参考文献：

[1] 刘大有，卢奕南，王飞，等.遗传程序设计方法综述[J].计算机研究与发展，2001（02）：213-222

[2] 马永杰，云文霞.遗传算法研究进展[J].计算机应用研究，2012，29（04）：1201-1206+1210.

[3] 边霞，米良.遗传算法理论及其应用研究进展[J].计算机应用研究，2010，27（07）：2425-2429+2434.

[4] 朱灿，梁昔明，周书仁.基于物种选择的遗传算法[J].小型微型计算机系统，2009，30（03）：534-536.

[5] 吴力荣.基本遗传算法遗传策略优化与Java实现[J].通化师范学院学报，2011，32（06）：30-31.

[6] Franz Wilhelmst?tter.Jenetics用户指南[EB/OL] http：//jenetics.io/manual/manual-4.1.0.pdf.

【通聯编辑：唐一东】