李嘉星 呂國 劉新月

DOI：10.19392/j.cnki.16717341.201714044

摘要：人工智能在諸多領域都得到了廣泛的應用。特別從AlphaGo在圍棋方面戰(zhàn)勝國手李世石后。人工智能更是又引起了業(yè)內(nèi)的廣泛討論而作為經(jīng)典問題的排課問題能否在這次新的科技浪潮中獲得一定的啟發(fā)呢？本文將從AlphaGo的算法和學校排課系統(tǒng)分別進行切入，從而對AlphaGo的算法應用于學校排課系統(tǒng)優(yōu)化的可行性進行相關研究。

關鍵詞：AlphaGo；排課系統(tǒng)；蒙特卡羅樹搜索；NP問題

近期4：1世界排名第二的韓國圍棋國手李世石不敵人工智能AlphaGo，人們都在感嘆是否人工智能的奇點已經(jīng)到來？人工智能是否在其他方面也會發(fā)展出巨大的潛力呢？一些現(xiàn)有的經(jīng)典問題的研究是否能在這種技術革新下有所突破呢？本文將對AlphaGo中的的算法能否應用于學校排課系統(tǒng)，來解決課程編排這一完全的NP問題進行可行性分析。

1 排課系統(tǒng)的實現(xiàn)原理

在現(xiàn)代高等院校的教學活動中，課程質(zhì)量和教學安排是決定在校學生能否獲取良好的科學文化知識的兩大關鍵因素。而其中課程的安排更是起到中流砥柱的作用。但早在上個世紀七十年代美國人S.EVEN就以提出并證明排課問題是一個完全性的NP問題。

“高校排課問題是一個多元分配問題，它研究的就是如何把學生和老師分配給課程，課程單元或者班級，如何把事件（上課事件）分配給教室和時間?！盵1]分析以上定義我們可以得出一個結論，排課問題即為一個多個有限元在有限空間和有限時間內(nèi)的分配問題。但這一分配問題有需要符合一系列的硬約束條件和一系列的軟約束條件。這些條件分別是硬約束：班級約束、教師約束和教室約束。這些約束規(guī)定了各個元素或在時間上或在空間上的唯一性，違背了這些約束的課表必然是錯誤的。另外就是軟約束，即所設計出的課表要盡可能的人性化，使學生和老師均能高效率的工作和學習。這些約束包括但不限于課程間的路程約束、每天課程量的安排等等。

我們應如何在這些約束條件下解決合理排課這一問題呢?，F(xiàn)有解決排課問題的算法多種多樣，從最初的循環(huán)遍歷到隨機散列。再到后來的進行優(yōu)化的遺傳算法、蟻群算法各種算法都有其優(yōu)勢與不足。下面我將對這些廣泛應用的排課算法進行簡要分析。排課系統(tǒng)中，若僅僅簡單的進行循環(huán)遍歷，再去根據(jù)約束求得可行解的方法，即簡單的暴力破解法。眾所周知暴力破解在解決NP問題中的效率是極為低下的，而且無論是暴利破解還是隨機散列法僅僅是隨機的出一個可行解。但在排課問題中這個解未必是可應用的因為其可能完全違背了軟約束條件，導致所編排出的課表正確但可應用性極低。在后期的優(yōu)化中許多研究人員采用遺傳算法來求解這一問題。從理論上分析該算法可以獲得一個較為合理的方案，但這一算法有可能導致的過早收斂會導致所得解不是那么優(yōu)秀。

而在AlphaGo的所應用的一系列算法能否用于排課算法這一完全的NP問題中并更好的去解決這一問題呢。

2 AlphaGo的算法原理

“AlphaGo是谷歌公司旗下DeepMind公司研發(fā)的圍棋人工智能程序其分布式版本構建于1920個CPU和280個GPU之上的圍棋程序?！盵2]

走棋網(wǎng)絡、快速走子、估值網(wǎng)絡和蒙特卡羅樹搜索構成了整個AlphaGo的系統(tǒng)。其中對解決排課問題這一NP問題可能會有所啟發(fā)的是快速走子、估值網(wǎng)絡和蒙特卡羅樹搜索。下面我將對這幾種算法進行簡要論述。

快速走子：為達到系統(tǒng)能得到快速且正確走子策略，為了這一目的，傳統(tǒng)的神經(jīng)網(wǎng)絡就顯得不夠迅速，顯而易見的就是神經(jīng)網(wǎng)絡的時間復雜度過大，不足以支持整個系統(tǒng)的高速運算需求。還是要結合傳統(tǒng)的局部特征值和線性回歸。這些算法組合并不具有很強的創(chuàng)新性。但應用十分廣泛。如競價排名、系統(tǒng)優(yōu)化、選擇求解等等。這種結合往往能使算法獲得局部的大局觀。

估值網(wǎng)絡：AlphaGo的估值網(wǎng)絡系統(tǒng)可以說是其作為人工智能能夠戰(zhàn)勝人類的不二功臣。可能也是整個系統(tǒng)中最難訓練的過程（在AlphaGo系統(tǒng)中通過上千萬次的自我實驗）。這一部分的主要作用即使通過對當前盤面進行分析，而判斷是誰將取得接下來的勝利。本質(zhì)上來講就是計算機通過深度卷積網(wǎng)絡把大問題依次分解，在分別進行解決方式。從而能使計算機實現(xiàn)類似于人腦那種舉一反三的思考能力。而估值網(wǎng)絡訓練起來是比較困難的。因其輸出僅有一個標量（可能獲勝的概率）。而所面對的輸入確是大于宇宙原子數(shù)的無限種可能。以我們的經(jīng)驗直接輸入或構造表達式來幫助其優(yōu)化算法幾乎是不可行的，只能通過系統(tǒng)近乎無窮多次的自我學習來不斷進行自我優(yōu)化與提升。

蒙特卡羅樹搜索：

蒙特卡羅樹搜索多用于一般的棋盤游戲，是一種用于某些決策過程的啟發(fā)式搜索算法。這種算法在AlphaGo程序中并無較大的創(chuàng)新。對于這一較為成熟算法AlphaGo程序組做出了一個值得探討的技術革新，即當蒙特卡羅樹遍歷至葉子節(jié)點時。并不立即將子節(jié)點展開而是當系統(tǒng)多次遍歷值一個節(jié)點。遍歷次數(shù)達到某一閾值時，才將該葉子節(jié)點進行展開。這樣可以避免蒙特卡羅樹在很短的時間內(nèi)就具有極大的廣度，導致算法的復雜性過度提升。

3 AlphaGo的算法應用于排課系統(tǒng)的可行性分析

對于排課算法這一經(jīng)典問題，歷代研究者和高校工作人員對算法進行了一次次的改進與優(yōu)化。但這一問題的解決算法仍不完善和成熟。而目前成為時代焦點的AlphaGo，給這個經(jīng)典問題的解決提供了新的啟迪。下面我將對AlphaGo的算法在排課系統(tǒng)中的應用進行詳細介紹。

快速走子，即局部特征值與線性回歸。這一經(jīng)典的算法組合應用廣泛，在之前的研究中也有學者將其與遺傳算法結合起來去進行排課可行解的求解過程。目的是為了在合理化的范圍內(nèi)降低遺傳算法的收斂速度，更優(yōu)化遺傳代數(shù)上的選擇。從而使想要求的解更具合理性。

估值網(wǎng)絡，要想應用于排課系統(tǒng)無需如同AlphaGo中的那樣進行大量的自我學習，因為排課中的結果估計是明確的，由若干硬性約束和軟性約束構成的他們能合理的構成一個價值表達式從而使排課結果的優(yōu)劣性得以一目了然。

蒙特卡羅樹搜索：對于這一經(jīng)典算法，AlphaGo團隊做出的創(chuàng)造性優(yōu)化是值得我們借鑒的，這種葉子節(jié)點的遍歷方法能極大的減少生成二叉樹的廣度，從而減少算法的復雜度。達到算法優(yōu)化的目的。

參考文獻：

[1]魏麗麗.排課算法的比較[J].人眾科技，2009（9）：150153.

[2]陶九陽，吳琳，胡曉峰.AlphaGo技術原理分析及人工智能軍事應用展望[J].指揮與控制學報，2016（6）：135137.

注：2016年河北省大學生創(chuàng)新創(chuàng)業(yè)訓練計劃項目資助：項目名稱：學校教務系統(tǒng)Web端及手機端系統(tǒng)研發(fā)（項目編號：201610084028）