基于主成分分析的高校排課算法研究

趙高長(zhǎng)a，覃飛b

(西安科技大學(xué)a.理學(xué)院; b.教務(wù)處, 西安710054)

摘要：通過(guò)充分市場(chǎng)調(diào)研，搜集目前高校排課所涉及的各種因素，然后對(duì)所有因素進(jìn)行定性分析，提取出具有研究?jī)r(jià)值的幾種因素，運(yùn)用統(tǒng)計(jì)學(xué)方法，包括SPSS相關(guān)性分析法及主成分分析法，對(duì)影響排課效果的各因素進(jìn)行定量分析，給出了一種排課主因素選擇模型，最終找到制約排課效果的核心關(guān)鍵因素，得到了排課過(guò)程中所需考慮的軟約束指標(biāo)及其優(yōu)先級(jí)順序。本文解決了排課過(guò)程考慮因素多、過(guò)程復(fù)雜的問(wèn)題，為高校排課完全自動(dòng)化奠定了理論基礎(chǔ)，同時(shí)也對(duì)其他類(lèi)似二分圖匹配問(wèn)題有一定的指導(dǎo)作用。

關(guān)鍵詞：主成分分析; 相關(guān)性分析; 軟約束指標(biāo); 二分圖

收稿日期:2014-12-08

基金項(xiàng)目:國(guó)家自然科學(xué)基金資助(41271518)

作者簡(jiǎn)介:趙高長(zhǎng)(1965-)，男，陜西大荔人，教授，主要從事數(shù)學(xué)教學(xué)與算法應(yīng)用研究。

中圖分類(lèi)號(hào)：TP301.6文獻(xiàn)標(biāo)志碼：A

0引言

高校排課是一項(xiàng)既基本又至關(guān)重要的教學(xué)管理工作，是高校建立穩(wěn)定教學(xué)秩序的基本保證。高校排課問(wèn)題一直以來(lái)是國(guó)內(nèi)外廣大學(xué)者的研究課題，隨著高等教育改革的不斷深入，辦學(xué)規(guī)模的迅速擴(kuò)大，新的教育體制對(duì)排課提出了更高的要求，因此排課問(wèn)題變得更加的復(fù)雜、棘手。那么，如何做好排課工作呢？光是靠排課模型的改進(jìn)和排課算法的完善是不夠的，不同的學(xué)校，由于環(huán)境的不同，實(shí)際情況的多樣性，對(duì)排課的要求就不一樣，所采用的排課模型和算法也就不同，但是目的都是為了找出適合自己學(xué)校的最佳排課方案，那么首要解決的就是掌握影響排課效果的各種因素，抓住重點(diǎn)，從實(shí)際情況出發(fā)進(jìn)行分析，掌握各因素間的關(guān)聯(lián)及其重要性，為后期排課問(wèn)題的求解建立理論基礎(chǔ)。

排課問(wèn)題可以看作是一個(gè)資源的合理分配問(wèn)題，是維持學(xué)校教學(xué)工作正常運(yùn)行的基本保障。排課的合理性和可行性要求：在任意一段時(shí)間內(nèi)，教師不沖突，授課不沖突，授課的班級(jí)不沖突，教室占用不沖突等。這是一個(gè)典型的多因素組合優(yōu)化和不確定性調(diào)度問(wèn)題，是解決對(duì)時(shí)間和空間資源爭(zhēng)奪而引起的沖突問(wèn)題。排課問(wèn)題的求解就是找出各個(gè)因素之間的關(guān)聯(lián)關(guān)系，充分的利用教學(xué)資源，課程、教室、教師、學(xué)生、時(shí)間、教學(xué)區(qū)域、院系等各因素之間的關(guān)系，堅(jiān)持以人為本，效率優(yōu)先，嚴(yán)格執(zhí)行教學(xué)計(jì)劃，正確落實(shí)教學(xué)任務(wù)，合理、有序、系統(tǒng)的做好排課工作。

早在50年代末，國(guó)外就有人開(kāi)始研究排課問(wèn)題。1962年，Gotlieb曾提出一個(gè)課表問(wèn)題的數(shù)學(xué)模型，并使用匈牙利算法求解[1]；此后，人們對(duì)排課問(wèn)題的因素分析、排課算法、解的存在性等問(wèn)題做了很多深入探討,使得人們對(duì)排課問(wèn)題有更加深入的認(rèn)識(shí)。近40年來(lái),人們利用計(jì)算機(jī)的優(yōu)越性，也對(duì)課表問(wèn)題的計(jì)算機(jī)解法做了許多嘗試。此外,有些文獻(xiàn)通過(guò)圖論知識(shí)，運(yùn)用圖的染色方法嘗試解決排課問(wèn)題[2]；早在70年代S.Even證明了排課問(wèn)題是一個(gè)NP完全問(wèn)題[3]，即此算法的計(jì)算時(shí)間是呈指數(shù)增長(zhǎng)的，這一論斷確立了排課問(wèn)題的理論深度。其實(shí)好多研究都是從理論基礎(chǔ)上分析研究，但是實(shí)際的復(fù)雜度遠(yuǎn)遠(yuǎn)超乎想象。進(jìn)入90年代,國(guó)外對(duì)排課問(wèn)題的研究仍然非?；钴S。如印度Vastapur大學(xué)管理學(xué)院的Arabinda Tripathy、加拿大Montreal大學(xué)的Jean Anbin和JacquesA.Ferland以及Charles Fleutent等[4]。漸曲inda知pathy的工作是針對(duì)以“人”為單位進(jìn)行課表編排的,他運(yùn)用拉格朗日松弛法和分支定界技術(shù)求解,這種方法的缺點(diǎn)是為減少變量的個(gè)數(shù)，人為造成科目間的沖突。在國(guó)內(nèi)，對(duì)課表問(wèn)題的研究開(kāi)始于80年代初期，具有代表性的有：南京工學(xué)院的UTSS(A University Timetable Scheduling System)系統(tǒng)，清華大學(xué)的TISER(Timetable SchedulER)系統(tǒng)，大連理工大學(xué)的智能教學(xué)組織管理與課程調(diào)度系統(tǒng)等[5]。這些系統(tǒng)都是模仿手工排課過(guò)程，以“班”為單位，運(yùn)用啟發(fā)式函數(shù)來(lái)進(jìn)行編排的；但是這些課表編排系統(tǒng)往往比較依賴(lài)于各個(gè)學(xué)校的教學(xué)體制，不宜進(jìn)行大面積推廣。如今，排課問(wèn)題依然是廣大學(xué)者喜愛(ài)研究的課題，新的算法和方法不斷涌現(xiàn)，使得排課工作不段完善和健全，充分的提升了教學(xué)質(zhì)量，適應(yīng)了發(fā)展的需求。

本文的目的是了解和分析目前影響排課效果的各種因素，找出制約排課效果的各因素間的內(nèi)在聯(lián)系，探索出潛在的真正因素，分析出各因素對(duì)排課效果的影響程度。把理論分析得到的結(jié)論和實(shí)際情況相比較，分析其合理性，通過(guò)對(duì)比，尋找出現(xiàn)有排課現(xiàn)狀的一些不足，加以完善。本文給出了排課問(wèn)題建模時(shí)的理論依據(jù)，驗(yàn)證了其合理性和可靠性，文章所得到的結(jié)論能使排課模型的建立變得更加完善；使排課問(wèn)題得到更完美的解決。

1模型準(zhǔn)備

通過(guò)一個(gè)月左右對(duì)不同高校師生及教務(wù)工作人員的的調(diào)研及材料的整理和分析，基本掌握了當(dāng)前形勢(shì)下所有的制約排課效果的各種因素，進(jìn)行初步的定性分析?？傻孟旅鎱R總表：

表1　因素匯總表

對(duì)調(diào)研的所有這些因素進(jìn)行分析，歸納總結(jié)如下，具體的可歸為以下幾類(lèi)：

(1)教學(xué)計(jì)劃。規(guī)定了各個(gè)專(zhuān)業(yè)的課程性質(zhì)及其各學(xué)期課程的分布情況，是安排教學(xué)進(jìn)程和落實(shí)教學(xué)任務(wù)的核心文件，具有一定的穩(wěn)定性和權(quán)威性，對(duì)排課效果影響顯著。

(2)教師資源。反映在這么幾個(gè)方面：教師的數(shù)量、教師工作量的不平衡和教師的個(gè)性化要求，滿(mǎn)足教師的個(gè)性化要求是學(xué)校以人為本的具體體現(xiàn)。

(3)合班問(wèn)題的合理性分析。對(duì)排課效果的影響主要指合班的數(shù)量和合班的方式，經(jīng)驗(yàn)總結(jié)合班問(wèn)題是排課的難點(diǎn)，一般合班數(shù)量越多課表越難安排。

(4)教室資源。指各種教室數(shù)量，教室屬性。如體育場(chǎng)地、實(shí)驗(yàn)室、設(shè)計(jì)室、多媒體及非多媒體教室等。

(5)課程性質(zhì)。包括課程的學(xué)分高低及周學(xué)時(shí)安排，對(duì)排課效果影響顯著，多學(xué)時(shí)，高學(xué)分的課程需要優(yōu)先考慮安排；而且需安排在教學(xué)黃金時(shí)間段。

(6)時(shí)間因素。指不同類(lèi)別課程上課時(shí)間的安排，某些重要的公選課及專(zhuān)業(yè)課需安排在上課黃金時(shí)間，有些特殊要求的課安排需考慮實(shí)際要求。[6]

這次共發(fā)出550份問(wèn)卷，最終回收524份，為了獲得好的實(shí)驗(yàn)效果，首先對(duì)所獲得的500多份調(diào)查問(wèn)卷進(jìn)行整理排查，去除一部分填寫(xiě)不完整度過(guò)高，數(shù)據(jù)缺乏可靠性問(wèn)卷，在對(duì)問(wèn)卷按院校進(jìn)行歸類(lèi)，去除院校數(shù)量特別少的問(wèn)卷，在將問(wèn)卷進(jìn)行打亂，從其中隨機(jī)抽取100份問(wèn)卷樣本作為分析材料。

對(duì)滿(mǎn)意度Y及各因素(Xi),通過(guò)SPSS進(jìn)行相關(guān)分析得下表。

表2　Y與X的相關(guān)性分析(部分)：

**.在置信度(雙測(cè))為 0.01 時(shí)，相關(guān)性是顯著的。

*.在置信度(雙測(cè))為 0.05 時(shí)，相關(guān)性是顯著的。

根據(jù)相關(guān)性分析(correlation analysis)原理，Spearman等級(jí)相關(guān)系數(shù)r在(-1，1)之間，其絕對(duì)值越接近于1，表示相關(guān)密切程度越大，由表可以看出自變量X10與Y相關(guān)性顯著相關(guān)(P=0.003<0.01)但是r=0.298表示比起其他因素(如X1與Y顯著相關(guān)：r=0.794)與Y相關(guān)性不強(qiáng)，X11與Y不相關(guān)(r=0.151)，X13，X16，X17，X18(P>0.5，)與因變量Y基本不相關(guān) ，表示對(duì)排課效果的影響甚微，姑且我們進(jìn)行因素剔除，一般在相關(guān)性分析時(shí)，如果因素比較多，就可以考慮剔除相關(guān)性低于0.5的因素(X10，X11，X13，X16，X17，X18)。得到初步判定影響排課效果的主要因素14個(gè)，但是這些因素之間又存在著關(guān)聯(lián)和影響，仍需我們探索，下面通過(guò)因子分析法來(lái)尋找因素間的聯(lián)系。

2建立模型

因子分析中有多種確定因子變量的方法，其中主成分模型的主成分分析法是使用最普遍的因子分析方法之一。主成分分析通過(guò)坐標(biāo)變換將原有的P個(gè)相關(guān)變量xi作線性變化，轉(zhuǎn)換為另外一組不相關(guān)的變量，可以表示為：

(1)

其中u1k+u2k+…+upk=1,(k=1,2,3,…,p)，F(xiàn)1,F2…,Fp為原有變量的第1、第2、…第p個(gè)主成分。其中F1在總方差中占的比例最大，綜合原有變量的能力最強(qiáng)，其主成分在總方差中占的比例最大，綜合原有變量的能力最強(qiáng)，其余主成分在總方差中占的比例逐漸減少，即綜合原有變量的能力依次減弱。主成分分析就是選取前幾個(gè)方差最大的主成分，這樣達(dá)到了因子分析較少變量的目的，同時(shí)又能以較少的變量反映原有變量的絕大部分信息。

主成分分析步驟如下[7]：

(1)數(shù)據(jù)的標(biāo)準(zhǔn)化處理

(2) 計(jì)算數(shù)據(jù)[xij]n×p的協(xié)方差矩陣R。

(3)求R的前m個(gè)特征值：λ1≥λ2≥…≥λm，以及對(duì)應(yīng)的特征值向量u1,u2,…um。

(4)求m個(gè)變量的因子載荷矩陣。

(2)

用因子的累積方差貢獻(xiàn)率確定m

前m個(gè)因子的累計(jì)方差貢獻(xiàn)率計(jì)算方法為：

(3)

若數(shù)據(jù)已經(jīng)標(biāo)準(zhǔn)化，則

(4)

一般方差的累計(jì)貢獻(xiàn)率應(yīng)在85%以上表示主成分法效果良好。本例分析結(jié)果如下：

表3　主成分表

提取方法：主成份分析。

表3給出了每個(gè)公因子所解釋的方差，以及所解釋方差的累計(jì)和，前6個(gè)因子提取平方和累積91.51%，遠(yuǎn)遠(yuǎn)高于85%，可以很好的解釋基本所有變量所涵蓋的信息。旋轉(zhuǎn)后的累計(jì)貢獻(xiàn)率也為91.51%，由此可以看出，影響排課的14個(gè)主要因素實(shí)際上可以用6個(gè)潛藏的本質(zhì)因素所解釋?zhuān)@就是我們所尋找的潛在因素。本例中，累計(jì)貢獻(xiàn)率高于90%，說(shuō)明主成分分析的效果很好。

圖1　因子貢獻(xiàn)率的走勢(shì)

圖1是初始特征值的碎石圖，是按照上面的“初始特征值”欄下的“合計(jì)列”作出的圖形，并按照降序排列，觀察看出，第六個(gè)因子后特征值變化趨緩，故而選取6個(gè)公因子較為合適。

表4　旋轉(zhuǎn)成分矩陣表

提取方法 :主成分分析法。

旋轉(zhuǎn)法 :具有 Kaiser 標(biāo)準(zhǔn)化的正交旋轉(zhuǎn)法，旋轉(zhuǎn)在 7 次迭代后收斂。

通過(guò)上面表4分析已經(jīng)得出影響高校排課效果的6大主要因素，通過(guò)旋轉(zhuǎn)成分矩陣，我們將相關(guān)聯(lián)程度大的因素歸類(lèi)，第一主成分包括因素(X3，X4，X20，X6，X15)，第二主成分包括因素(X8，X9，X1)，第三主成分包括因素(X19，X12)，第四主成分包括(X14)，第五主成分(X2，X7)，第六主成分(X5)。

其中第一主成分的得分最高為最主要因素,其次為第二主成分,依次排之。其每個(gè)主成分的得分可由因子得分系數(shù)矩陣得出:

表5　成分得分矩陣表

提取方法 :主成分分析法。

旋轉(zhuǎn)法 :具有 Kaiser 標(biāo)準(zhǔn)化的正交旋轉(zhuǎn)法。

由表5看出，第一主成分中因素X3=0.537，X4=0.521得分最高，第二主成分X8=0.677，第三主成分X19=0.756，第四主成分X14=0.897，第五主成分X2=0.816，第六主成分X5=0.935最高。這些得分最高表示對(duì)主成分的貢獻(xiàn)最大 ，起決定性作用。本課題中，指這些因素是制約排課效果軟約束中最具代表性的，是建模的依據(jù)。

通過(guò)問(wèn)卷分析，我們尋找出潛在的共同因素，命名為第一主成分因子：課程性質(zhì)因素，反映了課程的學(xué)分，課程的屬性，如公選課，專(zhuān)業(yè)課和選修課，排課時(shí)需考慮，公選課為全校都必須學(xué)的主要基礎(chǔ)課程，需優(yōu)先考慮安排，其次專(zhuān)業(yè)課，要安排在適合的最佳學(xué)習(xí)時(shí)間，選修課，可以放在晚上或周末學(xué)習(xí)。第二主成分因子：時(shí)間因素，反映上課時(shí)間的的安排，課程的時(shí)間分布，對(duì)排課效果影響甚大。第三主成分因子：教師因素，反映教師的工作量及個(gè)性化要求。滿(mǎn)足教師個(gè)性化要求是學(xué)校以人為本的重要體現(xiàn)，排課時(shí)需考慮每個(gè)老師的具體情況，排課要做到人性化安排，盡可能讓老師滿(mǎn)意。第四主成分因子：教室因素，反映教室屬性與所上課程屬性一致，一般學(xué)校的多媒體教室和體育場(chǎng)所及實(shí)驗(yàn)室資源比較短缺，因此對(duì)此類(lèi)有需求的課程需重點(diǎn)考慮，優(yōu)先安排。第五主成分因子：學(xué)時(shí)因素，學(xué)時(shí)大的課程理論上需優(yōu)先考慮排課，會(huì)產(chǎn)生好的排課效果。第六主成分因子：合班情況，反映教室所容納的人數(shù)，包括合班的數(shù)量及合班的方式，實(shí)踐證明合班數(shù)量越多，課表就越難安排。

3結(jié)語(yǔ)

本文從影響排課效果的各因素出發(fā)，詳細(xì)進(jìn)行了探討，先結(jié)合現(xiàn)狀和定性分析，給出了排課問(wèn)題所考慮的各個(gè)因素的初步判定，并進(jìn)行因素匯總和分類(lèi)，給出了分析結(jié)果，其次從具有研究?jī)r(jià)值排課問(wèn)題的軟約束出發(fā)，以調(diào)查問(wèn)卷的形式將問(wèn)題進(jìn)行量化，并運(yùn)用統(tǒng)計(jì)學(xué)方法，采用SPSS19.0進(jìn)行數(shù)據(jù)處理，得到了我們預(yù)期的效果，定性分析與定量分析相結(jié)合，定量分析的結(jié)果驗(yàn)證了定性分析的理論，使得我們對(duì)影響排課效果的因素有了更深入的認(rèn)識(shí)和理解，明白了其關(guān)聯(lián)和重要性，同時(shí)通過(guò)調(diào)查也了解到當(dāng)前形勢(shì)下高校的排課現(xiàn)狀，這對(duì)做好排課工作是非常有意義的。我們接著介紹了一種基于主成分分析的排課因素優(yōu)先級(jí)排序模型，這部分的研究是以建立在各因素統(tǒng)計(jì)分析的結(jié)果之上的，目的是為了更科學(xué)的搞明白制約排課效果的諸因素的重要程度，為我們提供了排課問(wèn)題的一種新思路，在進(jìn)行排課建模時(shí)，完全可以按主成分分析的結(jié)果，選取每個(gè)主成分中得分系數(shù)最大的，即權(quán)重最大的作為代表，具有很好的解釋性，即諸因素影響排課效果的優(yōu)先級(jí)排序：由大到小為教室屬性，合班數(shù)量，課程性質(zhì)，教師工作量，周學(xué)時(shí)，時(shí)間安排，學(xué)分?jǐn)?shù)。在以后排課中，不會(huì)盲目的考慮一些制約條件，本文的研究給出了明確的方向，是排課問(wèn)題的核心，為排課工作的順利展開(kāi)奠定了理論依據(jù)，同時(shí)也對(duì)當(dāng)前形勢(shì)下的高校排課情況有了全面而科學(xué)的認(rèn)識(shí)。

參考文獻(xiàn):

[1]GareyM R,JohnsonD S. Compute and Intractability: A Guide to the theory of NP completeness [M]. San francisco:W. H, Freem an Co.1979.

[2]王仲華,盧嬌麗. 圖論在高校排課問(wèn)題中的應(yīng)用研究[J].太原師范大學(xué)學(xué)報(bào)(自然科學(xué)報(bào)),2010(3)：39-42.

[3]張春梅,行飛,梁治安. 課表的多指標(biāo)數(shù)學(xué)模型及解決方法[J]. 內(nèi)蒙古大學(xué)學(xué)報(bào)(自然科學(xué)報(bào)),2004(3):139-144.

[4]趙靜,但琦. 數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn)[M]. 北京: 高等教育出版社,2003.

[5]盧志翔,藍(lán)玉龍,周秀梅. 高校排課系統(tǒng)的算法與研究[J]. 教育前沿(理論版),2008(12)：106-107.

[6]王俊生,戴云龍. 基于層次分析法的自動(dòng)排課優(yōu)先級(jí)模型[J]. 現(xiàn)代教育技術(shù)報(bào),2009(11):32-35.

[7]駱?lè)?劉紅云,黃崑.SPSS數(shù)據(jù)統(tǒng)計(jì)與分析[M]. 北京：清華大學(xué)出版社,2011.

責(zé)任編輯：程艷艷

Research on Algorithm of University Course Scheduling Based on Principal Component Analysis

ZHAO Gaochanga，QIN Feib

(a. College of Science; b. Office of Academic Affairs, Xi’an University of Science and Technology, Xi’an 710054, China)

Abstract：By adequate market survey, all factors that current universities’ course scheduling concern are collected, then analyzed qualitatively, several factors with great research value are extracted. This research utilizes statistics method, including SPSS correlation analysis and principal component analysis, to make a qualitative analysis on each factor influencing the effectiveness of course scheduling, presents a selection model of main factors, finds out the key factors restricting effectiveness of course scheduling and obtains the soft constraint index and its priority order that need considering in the process of course arrangement. This paper solves such problems as numerous factors and complex procedures, which lays a theoretical foundation for full automation of universities’ course scheduling and provides a guiding role for other similar bipartite graph matching problems.

Keywords：principal component analysis； correlation analysis； soft constraint index； bipartite graph