AlphaGo的算法應(yīng)用于學(xué)校排課系統(tǒng)的可行性研究

李嘉星 呂國(guó) 劉新月

DOI：10.19392/j.cnki.16717341.201714044

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

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

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

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

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

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

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

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

2 AlphaGo的算法原理

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

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

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

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

蒙特卡羅樹搜索：

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

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

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

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

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

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

參考文獻(xiàn)：

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

[2]陶九陽，吳琳，胡曉峰.AlphaGo技術(shù)原理分析及人工智能軍事應(yīng)用展望[J].指揮與控制學(xué)報(bào)，2016（6）：135137.

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