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

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

趙高長a，覃飛b

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

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

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

收稿日期:2014-12-08

基金項目:國家自然科學(xué)基金資助(41271518)

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

中圖分類號：TP301.6文獻標志碼：A

0引言

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

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

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

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

1模型準備

通過一個月左右對不同高校師生及教務(wù)工作人員的的調(diào)研及材料的整理和分析，基本掌握了當(dāng)前形勢下所有的制約排課效果的各種因素，進行初步的定性分析。可得下面匯總表：

表1　因素匯總表

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

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

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

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

(4)教室資源。指各種教室數(shù)量，教室屬性。如體育場地、實驗室、設(shè)計室、多媒體及非多媒體教室等。

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

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

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

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

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

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

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

根據(jù)相關(guān)性分析(correlation analysis)原理，Spearman等級相關(guān)系數(shù)r在(-1，1)之間，其絕對值越接近于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)性不強，X11與Y不相關(guān)(r=0.151)，X13，X16，X17，X18(P>0.5，)與因變量Y基本不相關(guān) ，表示對排課效果的影響甚微，姑且我們進行因素剔除，一般在相關(guān)性分析時，如果因素比較多，就可以考慮剔除相關(guān)性低于0.5的因素(X10，X11，X13，X16，X17，X18)。得到初步判定影響排課效果的主要因素14個，但是這些因素之間又存在著關(guān)聯(lián)和影響，仍需我們探索，下面通過因子分析法來尋找因素間的聯(lián)系。

2建立模型

因子分析中有多種確定因子變量的方法，其中主成分模型的主成分分析法是使用最普遍的因子分析方法之一。主成分分析通過坐標變換將原有的P個相關(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個主成分。其中F1在總方差中占的比例最大，綜合原有變量的能力最強，其主成分在總方差中占的比例最大，綜合原有變量的能力最強，其余主成分在總方差中占的比例逐漸減少，即綜合原有變量的能力依次減弱。主成分分析就是選取前幾個方差最大的主成分，這樣達到了因子分析較少變量的目的，同時又能以較少的變量反映原有變量的絕大部分信息。

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

(1)數(shù)據(jù)的標準化處理

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

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

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

(2)

用因子的累積方差貢獻率確定m

前m個因子的累計方差貢獻率計算方法為：

(3)

若數(shù)據(jù)已經(jīng)標準化，則

(4)

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

表3　主成分表

提取方法：主成份分析。

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

圖1　因子貢獻率的走勢

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

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

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

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

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

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

表5　成分得分矩陣表

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

旋轉(zhuǎn)法 :具有 Kaiser 標準化的正交旋轉(zhuǎn)法。

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

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

3結(jié)語

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

參考文獻:

[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]王仲華,盧嬌麗. 圖論在高校排課問題中的應(yīng)用研究[J].太原師范大學(xué)學(xué)報(自然科學(xué)報),2010(3)：39-42.

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

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

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

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

[7]駱方,劉紅云,黃崑.SPSS數(shù)據(jù)統(tǒng)計與分析[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