遗传算法在教学中的可视化设计与实现

吴清扬

（广东省财政职业技术学校，广东广州，510445）

遗传算法在教学中的可视化设计与实现

吴清扬

（广东省财政职业技术学校，广东广州，510445）

遗传算法、网络神经算法等智能算法（进化算法）是一种快速、高效非精确算法，由于它突破了传统的精确算法的思维，因而一直是教学上的难点与重点。文章尝试以遗传算法求解8位二进制最大数为例，通过可视化的方式来展现遗传算法的运算过程，加深对遗传算法思想的理解，达到帮助学生理解遗传算法的目的。

遗传算法教学选择操作交叉操作变异操作

0 引言

近年来，随着科技的不断进步，智能化已经不可回避成为的热点问题，尤其是2016年3月份阿尔法围棋程序（AlphaGo）以4:1战胜了世界围棋冠军李世石后，以遗传算法、网络神经、模拟退火、禁忌搜索等为代表的智能算法已然成为学习的焦点与热点，而由于智能算法突破了传统精确算法的思维，它是通过模拟自然现象的方式进行优化处理，一直是教学上的难点与重点。本文尝试以遗传算法求解8位二进制最大数为例，通过可视化的方式来展现遗传算法的运算过程，从而激发学生的学习兴趣，达到帮助学生理解遗传算法的目的。

1 遗传算法思想概要

遗传算法是根据达尔文进化论的“物竞天择，适者生存”现象而提出的一种随机搜索算法，该算法将优化问题看作是自然界的进化过程，通过模拟大自然中生物的进化过程中的遗传规律，来达到寻优的目的。生物进化与遗传算法之间的对应关系如表1所示。

在遗传算法中，首先对优化问题进行编码，编码后的一个解称为一个染色体，组成染色体的元素称为基因。一个群体由若干个染色体组成，染色体的个数称为群体的规模。与自然界中的生存环境相对应，在遗传算法中用适应函数表示环境，它是已编码的解的函数，是一个解适应环境的评价。一般情况下，适应函数值大表示染色体的适应环境的能力强。适应函数相当于自然中环境的作用。

当适应函数确定后，自然选择规律将以适应函数值的大小来决定一个染色体继续生存下去的概率。生存下来的染色体成为种群，它们中的部分或者全部以一定概率进行交叉，繁衍，从而得到下一代的群体。交叉是一个生殖过程，发生在两个染色体之间，作为双亲的两个染色体，交换部分基因，生殖出两个新的染色体，即问题的新解。交叉或者称为杂交，是遗传算法区别于其他优化算法的最主要特征。进行进化的过程中，染色体的某些基因可能会发生变异，即表示染色体的编码发生某些变化。一个群体的进化需要染色体的多样性，而变异对保持群体的多样性具有一定的作用。

表1 生物进化与遗传算法之间的对应关系

2 教学中遗传算法的可视化设计

2.1 问题的提出

基于教学目的问题设计，既需要容易理解又需要有代表性，这样才能有利于学生对遗传算法思想的理解。本文提出了如何利用遗传算法来求解8位二进制数中的最大数，即任意给出10个在0-255之间的自然数，利用遗传算法循环进行选择、交叉、变异运算，求出最大的8位二进制数（即十进制的255），同时在这运算的过程当中，能够动态的显示出包括染色体基因，适应值函数选择过程和选择结果、交叉过程、变异过程和相关结果。

2.2 问题编码的设计

在设计遗传算法时首先考虑的是编码的设计问题，将问题的解以适合于遗传算法求解的形式编码；本文采用二进制编码，用二进制值表示当前的染色体的值，由于所求的目标数用二进制表示最大为八位，所以染色体的设计为8位染色体。

2.3 适应函数的设计

直接选取问题的目标函数作为适应函数，在这里目标函数为染色体与目标最大数的差，差值越小（和目标数越接近）适应函数值越大，越容易被在繁殖中保存下来。

2.4 选择操作设计（评估染色体设计）

依据适应函数值的大小，选择操作从规模为N的群体中随机地选择若干染色体构成种群，种群的规模可以与原来的群体的规模一致，也可以不一致，为方便演示，本系统设计成二者的规模是一致的，即从10个原来的群体选择10个构成新的种群。从群体中选择存活的染色体，这里采用“轮盘赌”的方法，方法简述如下：

群体的规模为10，F(X)为染色体的二进制转化为十进制的值，是其中第10个染色体的适应值，则第i个染色体被选中的概率见公式1。

公式1 染色体的被选中概率计算公式

①R=random(0,1),s=0,i=0;

②如果s≥R,则转④

⑤结束。

其中random(0,1)是一个产生在[0，1]之间均匀分布的随机数的函数。这样经过10次“轮盘赌”之后，就得到了规模为10的新的种群。

2.5 交叉操作设计

双亲双子法是遗传算法交叉环节最常用的一种设计方法，就是当参与交叉的两个双亲染色体确定后，随机产生一个交叉位，双亲染色体交换各自的交叉位之后的基因给对方，得到两个子染色体。

本文设计的种群数目有10个，基因的位数8位，采用双亲双子法交叉两次，然后从中得出的4个染色体中，随机的抽取2个做为下一代的新的种群。这样的设计主要是防止染色体基因位的重复相同，使产生的新的染色体在基因位上进可能少的重叠，有利于种群基因的多样性，以便在多次交叉中寻找到目标解。

2.6 变异操作设计

变异发生在某个染色体的某个基因上，它将可变性引入群体，增强了群体的多样性，从而提供了从局部最优中逃脱出来的一种手段。

本文问题的编码形式采用的是二进制数表示，所以随机产生一个变异位后，被选中的基因由“0”变成“1”，或者由“1”变成“0”。在问题求解上，由于只有10个染色体，每个染色体位，所以为了更好的体现遗传交叉得出最优解的结果，应尽量的减少变异的概率，所以设置变异的概率为1%，当然也可以用户自定义，以寻求相应的速度找到目标解。

2.7 遗传算法的评价方法的设计

当进化代数趋向于无穷时，遗传算法中找到最优解的概率为1，但需要随时了解算法的进展情况，监视算法的变化趋势，本文使用所在的第n代中染色体的平均指标函数的值（所有染色体转化成十进制的平均值）来刻画算法的趋势，并用随代数变化的曲线图表示出来。

2.8 遗传算法的实现过程

图1 求解遗传算法流程图

在确定了问题的编码，适应函数的设计以及选择、交叉、变异的规则后，整个遗传算也就确定了，具体的实现过程如下：

1）给定群体规模为10，交叉的概率为=100%（可用户自定义）和变异概率为=1%（可用户自定义），t=0；

2）随机生成（用户自定义）10个染色体作为初始群体；

4）如果算法满足停止准则，则转⑽；

6）根据计算得到的概率值，从群体中随机的选取10个染色体，得到新的种群；

9）用新群体替代旧群体，t=t+1;转⑶；

10）进化过程中适应值最大的染色体，经解码后作为最优解输出；

根据遗传算法的实现过程，得到相应的流程图如图1所示。

2.9 遗传算法的可视化设计

2.9.1 染色体设计界面

染色体用红色表示“1”基因，用绿色表示“0”基因，即用八位的二进制的“0”和“1”编码来表示0-255之间的数。

2.9.2 染色体图形设计方法

在五个面板中共保存了10个染色体的基因特征，每个染色体有8个基因，所以一个8个色块表示染色体的八个基因。在画图方法上

用MFC在图形控件上画图。同时在评估图形左边以十进制的形式显示当代群体的染色体的值。

2.9.3 遗传繁衍过程动画显示

运用windows 时间消息响应机制，在每个时间片中显示算法关键节点的信息。如在选择过程为10个时间片，分别选出10个新的种群；交叉过程为5个时间片，包括选中交叉的染色体，第一次交叉结果的染色体，第二次交叉结果的染色体，交叉结果选出新染色体，在交叉结果显示新的染色体；变异过程为1个时间片，即更新变异结果。

2.9.4 遗传算法性能曲线设计

在一个图形控件中绘制坐标，横坐标为遗传代数，纵坐标为当代群体的染色体适应函数的平均值；每代遗传后求出当代群体的染色体适应函数的平均值，在画图上同时记录相连两代的平均值，在遗传更新过程中连线表示遗传过程中的群体的染色体适应函数的平均值的变化，便形成了群体的染色体适应函数的平均值的曲线。

产生随机数时间种子的函数的设计

图2 遗传算法演示过程主界面

}采用此函数产生的随机数时间种子是以纳秒为单位的，极大程度上避免了产生重复的随机数时间种子，是实验设计的关键和重要技术。

2.9.5 主要界面内容介绍

如图2所示：

（1）左上角的染色体值显示了当代10个8位的染色体值，为了方便理解将二进制转化为十进制表示，从中很容易看到每一代染色体不断的靠近目标解。

（2）右上角的评估染色体、选择结果、交叉过程、交叉结果、变异结果等五个面板显示了每一代染色体的演化过程，直至生成下一代染色体。

（3）左下角遗传工程染色体平均性能图谱表示的是运算的代数与群体平均适应值的正相关关系，即随着运算代数的增加，群体平均适应值越来越接近目标解。

（4）右下角显示的是包括繁衍速度控制控件在内的控件群，可以选择开始演示算法、暂停算法、重新演示算法等操作。

3 遗传算法可视化实验主要测试情况

3.1 第一次测试

表2 第一次测试数据

图3 遗传算法第一次测试过程性能图谱

表3 第二次测试数据

图4 遗传算法第二次测试过程性能图谱

表2给出了随机产生的10个染色体及计算结果。图3为变异概率为1%遗传过程性能图谱，运行了105代以后群体平均适应值很接近目标解，但由于陷入局部最优，没能找到最优解。

3.2 第二次测试

表3给出了随机产生的10个染色体及计算结果。图4为变异概率为1%遗传过程性能图谱，运行到第67代时候得到了目标解。

3.3 第三次测试

表4 第三次测试数据

图5 遗传算法第三次测试过程性能图谱

表4给出了随机产生的10个染色体及计算结果。图5所示位变异概率为10%的遗传过程性能图谱，运行到第55代时候得到了目标解。

3.4 实验结果分析

以上三组群体的染色体都是随机产生的，染色体适应值平均分布在[0，255]之间的数，变异的概率分别为1%，1%，10%，可以看到染色体适应函数的平均值的曲线为上升趋势，第一组数据没有得出目标解；第二组数据得出目标解，基于遗传交叉的可能性比较大，染色体适应函数的平均值的曲线上升的曲线也比较明显；第三组数据变异的概率比较大（10%），得出结果基于变异的可能性比较大，但染色体适应函数的平均值的曲线上升的曲线变化也比较大。

4 小结

该设计不但能够动态演示遗传算法的运算过程，而且也展现了遗传算法的不足，即在某些条件下，可能会陷入局部最优。此外，通过不同的参数设置，比如调整变异概率，还可以对运速性能进行进一步的分析。

从课堂教学效果来看，学生可以动态的观察遗传算法在运算过程的选择、交叉、变异等步骤，大大激发了学生的学习兴趣，加深了对算法思想的认识与理解，因此，遗传算法在教学中的可视化设计是可行的。

[1] 马永杰,云文霞.遗传算法研究进展[J]. 计算机应用研究. 2012(04) .

[2] 李雅琼.基于模糊控制的遗传算法优化研究[J]. 长沙大学学报. 2016(05).

[3] 王小平, 曹立明.遗传算法的理论、应用与软件实现[M].西安:西安交通大学出版社, 2002: 28- 34.

Visualization design and implementation of the genetic algorithm forteaching demonstration

Wu Qingyang
(Guangdong Finance Institute，Guangdong,Guangzhou,510445)

Intelligence algorithms(evolution algorithms) like Genetic algorithm& neural network is a fast,high efficiency non exact algorithms.It is always the difficult&key point for the teaching demonstration as it breaks through the traditional thinking of the exact algorithm.This paper try to use genetic algorithm to solve maximum of 8 bit binary as example to present the computational procedure of genetic algorithm in a visualization way,get a deeper understanding of genetic algorithm thought & achieve the target of helping student understand the algorithm.

genetic algorithm;teaching;selection;crossover;mutation