“第一性原理”在演化算法教学中的应用研究

2017-11-06郑波尽代航

计算机教育 2017年10期

郑波尽　代航

摘要：演化计算是人工智能中一个重要的分支，目前的本科教学实践对演化算法的讲授多从标准遗传算法出发，学生普遍反映算法复杂、难懂。文章提出“第一性原理”教学方法，将演化算法归结到最简单的状态，再逐步推广，最后总结提高到理论层次；以中南民族大学计算机科学学院软件与理论教研室在演化算法的本科教学中的做法为例展示“第一性原理”教学方法，说明该教学方法的效果。

关键词：演化算法；遗传算法；简化；优化问题

0 引言

很多高校的计算机科学与技术专业、信息技术专业以及相关的本科专业都开设了人工智能的课程。AlphaGO以4：1大胜世界超一流围棋高手李世石、AlphaGO的高级版本Master在围棋网上以60：0击败中日韩三国顶尖高手、AlphaGO以3：0大胜当前围棋等级分第一人柯洁九段等事件使得人工智能[1-2]学科得到了公众的广泛关注。这些轰动一时的事件也表明，人工智能正以超乎想象的速度进入到公众的话语体系中。演化计算作为人工智能的重要分支也必然会受益于公众的支持和期许，如会有更多的学生开始学习演化算法等。

1 演化算法教学困境

目前，对于演化算法的本科教学，国内高校普遍以John Holland提出的标准遗传算法[3-4]作为基准来开展教学。标准遗传算法用C语言来写的话，大约需要200多行代码，这就导致了一个困境：如果着重于介绍标准遗传算法的理论知识，学生难以将算法融会贯通应用于实践环节，体现在不能写出代码；如果强调实践环节，代码实在冗长，学生普遍反映理解起来有困难。

2 “第一性原理”教学方法

演化算法的教学通常是从标准遗传算法开始讲解，该算法的复杂和难以理解使得“第一性原理”教学方法的引入成为必然。

2.1 概述

“第一性原理”原本是物理学的概念，经过Elon Musk的大力宣传，被广泛应用于各行各业。本质上，“第一性原理”是基于因果关系的思维方式，即首先发现一件事情最核心的原因，然后基于此原因一步步往外推理出想要的结果。将“第一性原理”教学方法应用到演化算法的教学中的基本思路是：将演化算法约简到最简单的形式，在最简单的形式下教学，然后推广到更复杂的情形。方法应用的主要步骤是：将演化算法大幅度化简到10多行代码的程度，从实践环节出发来讲授；再将示例算法一般化，举一反三，把理论和实践联系起来，达到强调理论教学的目的。这种方法既有案例，又有理论，有利于本科学生加深对于演化算法机制的理解，写出处理各种优化问题的演化算法。

2.2 具體步骤

“第一性原理”教学方法可以分4步进行。第1步是约简，即将演化算法进行简化，一直简化到一目了然的程度，简化后的演化算法被称为最简单演化算法（the simplest evolutionary algorithm）。第2步是展现，即展现简化后的演化算法（最简单演化算法）的机理和实验效果，通过多个案例来加深学员的理解。第3步是推广，即从简到繁、举一反三，根据实验效果和问题特性，对最简单演化算法进行改进。第4步是提高，即万法归宗，将感性认识和实践经验上升到理论层次，在以前的教学基础上，总结归纳出演化算法相关理论。

2.3 与通常教学法的比较

通常的演化算法教学是从标准演化算法开始，按算法原理、思想和算法的流程依次讲授；再进一步介绍选择算子（如轮盘赌算子、竞标赛选择算子等）、交叉算子、变异算子、终止条件等；最后，介绍算法在处理各种优化问题时的弱点以及对算法所做的各种改进。实践教学方面，则让学生参考标准遗传算法，针对各种优化问题对算法进行修改，仿真运行得到结果，最后对结果进行统计分析。

“第一性原理”教学法有所不同，以正弦和余弦函数构造出来的优化函数：maxf（x）=5sin（9x）+7cos（4x），x∈[0，7]为例，阐释第一性原理教学法的具体做法。①将演化算法写成最简单的形式使学生容易理解算法的每一句话，最简单的演化算法是一个具体的案例，学生更容易脱离抽象的算法理论细节；②用最简单的演化算法来求解具体的优化问题；③继续第一性原理教学法的第②步，对于每个优化问题，给出其地形图，并仿真执行最简单演化算法，让学生看到每一个世代、种群在地形图上所处的点，从而直观地感受到种群在地形图上一步一步挪动的情景，从而理解演化算法群体爬山的机制；④切换到第③步，讲授和演示最简单演化算法的早熟问题，从而引入算法的改进，可以使用各种变异算子；⑤继续第③步，即进一步讲授选择算子和交叉算子的改进，从而可以过渡到讲授标准遗传算法的框架上；⑥进入第④步，在学生已经得到了大量直观经验的基础上，讲授演化算法的理论。

2.4 精简后的算法形式

在“第一性原理”教学方法中，最重要的步骤是将演化算法写成最简单的形式。完整的精简后的算法以C语言的形式给出如下。

#include

#define POPSIZE 100

#define MAXGENS 2000

double f（double x） {

return 5*sin（9*x） + 7*cos（4 * x）；

}

double pop[POPSIZE]；

void initPop（） {

for （int i = 0； i

pop[i] = （double）（rand（） % 7）；

}

void main（） {

srand（（unsigned int）time（0））；

initPop（）；

for （int k = 0； k

for （int i = 0； i

double x = pop[i]+ （double） rand（） /RAND_MAX*（pop[i]-pop[（i+1）%POPSIZE]）；

if （f（x）> f（pop[i]）） pop[i] = x；

}

主函数的第1行代码是常见的初始化随机数种子函数。利用当前的时间作为随机数种子，使得每次产生出来的随机数都不相同。主函数的第2行代码是初始化种群，即让种群里的每个个体都有一个可行解。主函数的第3行代码是计算演化算法迭代的次数，即种群演化的世代数。主函数的第4行和第5行完成双亲个体的选择以及杂交操作，在双亲个体的选择上，本算法以个体的存储位置作为选择的标准，即轮流选择个体作为第1个双亲个体，然后，选择第1个双亲个体的右邻居（在数组中的下1个个体）作为第2个双亲个体，当数组越界时，通过模运算将个体重定位到数组的开始位置。也就是说，种群实际上是构成了1个环结构。在完成了双亲个体的选择后，算法在第5行执行了杂交操作。在实数编码的演化算法中，仿射杂交算子是1个常用的算子。该算子实际上是在两点连成的直线线段上，随机地选取1个点。这里实现的正是标准的仿射杂交算子，只不过在写法上和常用的对称写法不太一样，两种写法在数学上是一模一样的。主函数的第6行完成的是精英策略，即对于当前所获得的最优个体，需要将其保存下来。在本算法示例中，精英策略的实现和双亲个体的更新合并在一起，算法又得到了化简。

从上面给出的算法C语言代码来看，主函数只有7行代码，但已经包含了演化算法的精髓。即使将初始化种群函数initPop（）里面的代码加进来，也不过8行代码。对于学生们来说，只需要理解主函数的7～8行代码，就可以理解演化算法，有效降低了学生对于演化算法的理解难度。

2.5 程序运行效果

在具体的教学实践中，用MATLAB重写上述算法，在算法中，加入绘图代码。在代码中，加入fplot（'5*sin（9*x）+7*cos（4*x）'，[0 7]）这行代码，以绘制函数的地形图。然后，每隔几个世代就绘制每一个个体在地形图中的位置。学生能够看到种群向山峰攀爬的过程，能够直观地理解演化算法具有“群体爬上”的机制。如图1（x轴是自变量的取值，y轴是函数值，蓝色的线是函数的地形图，红点是每个个体）是最简单演化算法在第20世代时的运行结果图。

3 “第一性原理”教学效果

“第一性原理”教学方法的应用明显改善了演化算法理论理解困难、演化算法实践困难等问题。总结下来，在采用新方法以后，学生得到了较大的提高，表现在以下3个方面。

1）理解了群体爬山的机制。

绘图代码在电脑中的展现能够动态地展示不同世代各个个体的移动位置，直观展现演化算法在每个世代的效果，具体可感的图形有利于学生理解群体爬山机制。

2）大部分学生能编写演化优化程序。

新教学方法的应用促进了学生在实践环节的进步。通过新方法的实施，学生基本上能在电脑上完整地完成程序编写，即使在卷面默写的情况下，85%左右的学生也都能够完成程序的编写。

3）改变了对演化算法的畏难情绪。

演化算法的约简降低了该算法理解与应用的难度，有效地降低了学生学习该算法的畏难情绪，由“困难”到“简单”的想法有利于学生建立强大的自信心。

4 总结

演化算法是人工智能领域一个重要的部分，通过将演化算法大幅简化到只有十几行代码的程度的方式，学生能够轻易地理解算法中每一行代碼的意思和作用，提高演化算法的教学效果。“第一性原理”教学方法在演化算法教学中的应用还需要在实践中不断完善，以期更好地为教学服务。

参考文献：

[1] 钟义信. 高等人工智能：人工智能理论的新阶段[J]. 计算机教育， 2012（18）：6-11.