AlphaGo的算法应用于学校排课系统的可行性研究

李嘉星 吕国 刘新月

DOI：10.19392/j.cnki.16717341.201714044

摘要：人工智能在诸多领域都得到了广泛的应用。特别从AlphaGo在围棋方面战胜国手李世石后。人工智能更是又引起了业内的广泛讨论而作为经典问题的排课问题能否在这次新的科技浪潮中获得一定的启发呢？本文将从AlphaGo的算法和学校排课系统分别进行切入，从而对AlphaGo的算法应用于学校排课系统优化的可行性进行相关研究。

关键词：AlphaGo；排课系统；蒙特卡罗树搜索；NP问题

近期4：1世界排名第二的韩国围棋国手李世石不敌人工智能AlphaGo，人们都在感叹是否人工智能的奇点已经到来？人工智能是否在其他方面也会发展出巨大的潜力呢？一些现有的经典问题的研究是否能在这种技术革新下有所突破呢？本文将对AlphaGo中的的算法能否应用于学校排课系统，来解决课程编排这一完全的NP问题进行可行性分析。

1 排课系统的实现原理

在现代高等院校的教学活动中，课程质量和教学安排是决定在校学生能否获取良好的科学文化知识的两大关键因素。而其中课程的安排更是起到中流砥柱的作用。但早在上个世纪七十年代美国人S.EVEN就以提出并证明排课问题是一个完全性的NP问题。

“高校排课问题是一个多元分配问题，它研究的就是如何把学生和老师分配给课程，课程单元或者班级，如何把事件（上课事件）分配给教室和时间。”[1]分析以上定义我们可以得出一个结论，排课问题即为一个多个有限元在有限空间和有限时间内的分配问题。但这一分配问题有需要符合一系列的硬约束条件和一系列的软约束条件。这些条件分别是硬约束：班级约束、教师约束和教室约束。这些约束规定了各个元素或在时间上或在空间上的唯一性，违背了这些约束的课表必然是错误的。另外就是软约束，即所设计出的课表要尽可能的人性化，使学生和老师均能高效率的工作和学习。这些约束包括但不限于课程间的路程约束、每天课程量的安排等等。

我们应如何在这些约束条件下解决合理排课这一问题呢。现有解决排课问题的算法多种多样，从最初的循环遍历到随机散列。再到后来的进行优化的遗传算法、蚁群算法各种算法都有其优势与不足。下面我将对这些广泛应用的排课算法进行简要分析。排课系统中，若仅仅简单的进行循环遍历，再去根据约束求得可行解的方法，即简单的暴力破解法。众所周知暴力破解在解决NP问题中的效率是极为低下的，而且无论是暴利破解还是随机散列法仅仅是随机的出一个可行解。但在排课问题中这个解未必是可应用的因为其可能完全违背了软约束条件，导致所编排出的课表正确但可应用性极低。在后期的优化中许多研究人员采用遗传算法来求解这一问题。从理论上分析该算法可以获得一个较为合理的方案，但这一算法有可能导致的过早收敛会导致所得解不是那么优秀。

而在AlphaGo的所应用的一系列算法能否用于排课算法这一完全的NP问题中并更好的去解决这一问题呢。

2 AlphaGo的算法原理

“AlphaGo是谷歌公司旗下DeepMind公司研发的围棋人工智能程序其分布式版本构建于1920个CPU和280个GPU之上的围棋程序。”[2]

走棋网络、快速走子、估值网络和蒙特卡罗树搜索构成了整个AlphaGo的系统。其中对解决排课问题这一NP问题可能会有所启发的是快速走子、估值网络和蒙特卡罗树搜索。下面我将对这几种算法进行简要论述。

快速走子：为达到系统能得到快速且正确走子策略，为了这一目的，传统的神经网络就显得不够迅速，显而易见的就是神经网络的时间复杂度过大，不足以支持整个系统的高速运算需求。还是要结合传统的局部特征值和线性回归。这些算法组合并不具有很强的创新性。但应用十分广泛。如竞价排名、系统优化、选择求解等等。这种结合往往能使算法获得局部的大局观。

估值网络：AlphaGo的估值网络系统可以说是其作为人工智能能够战胜人类的不二功臣。可能也是整个系统中最难训练的过程（在AlphaGo系统中通过上千万次的自我实验）。这一部分的主要作用即使通过对当前盘面进行分析，而判断是谁将取得接下来的胜利。本质上来讲就是计算机通过深度卷积网络把大问题依次分解，在分别进行解决方式。从而能使计算机实现类似于人脑那种举一反三的思考能力。而估值网络训练起来是比较困难的。因其输出仅有一个标量（可能获胜的概率）。而所面对的输入确是大于宇宙原子数的无限种可能。以我们的经验直接输入或构造表达式来帮助其优化算法几乎是不可行的，只能通过系统近乎无穷多次的自我学习来不断进行自我优化与提升。

蒙特卡罗树搜索：

蒙特卡罗树搜索多用于一般的棋盘游戏，是一种用于某些决策过程的启发式搜索算法。这种算法在AlphaGo程序中并无较大的创新。对于这一较为成熟算法AlphaGo程序组做出了一个值得探讨的技术革新，即当蒙特卡罗树遍历至叶子节点时。并不立即将子节点展开而是当系统多次遍历值一个节点。遍历次数达到某一阈值时，才将该叶子节点进行展开。这样可以避免蒙特卡罗树在很短的时间内就具有极大的广度，导致算法的复杂性过度提升。

3 AlphaGo的算法应用于排课系统的可行性分析

对于排课算法这一经典问题，历代研究者和高校工作人员对算法进行了一次次的改进与优化。但这一问题的解决算法仍不完善和成熟。而目前成为时代焦点的AlphaGo，给这个经典问题的解决提供了新的啟迪。下面我将对AlphaGo的算法在排课系统中的应用进行详细介绍。

快速走子，即局部特征值与线性回归。这一经典的算法组合应用广泛，在之前的研究中也有学者将其与遗传算法结合起来去进行排课可行解的求解过程。目的是为了在合理化的范围内降低遗传算法的收敛速度，更优化遗传代数上的选择。从而使想要求的解更具合理性。

估值网络，要想应用于排课系统无需如同AlphaGo中的那样进行大量的自我学习，因为排课中的结果估计是明确的，由若干硬性约束和软性约束构成的他们能合理的构成一个价值表达式从而使排课结果的优劣性得以一目了然。

蒙特卡罗树搜索：对于这一经典算法，AlphaGo团队做出的创造性优化是值得我们借鉴的，这种叶子节点的遍历方法能极大的减少生成二叉树的广度，从而减少算法的复杂度。达到算法优化的目的。

参考文献：

[1]魏丽丽.排课算法的比较[J].人众科技，2009（9）：150153.

[2]陶九陽，吴琳，胡晓峰.AlphaGo技术原理分析及人工智能军事应用展望[J].指挥与控制学报，2016（6）：135137.

注：2016年河北省大学生创新创业训练计划项目资助：项目名称：学校教务系统Web端及手机端系统研发（项目编号：201610084028）