本科論文答辯中專家-學生匹配分組模型及算法

狄衛民， 徐文君， 王 然

（鄭州大學管理工程學院，鄭州450001）

0 引 言

本科畢業論文直接反映了本科生的文字表達能力、知識應用能力和綜合創新能力，間接反映了指導教師的指導效果和教學水平［1-2］。畢業論文答辯是審查畢業論文質量的重要形式，越來越受到導師、學生和教學管理部門的重視［3］。在本科教學實踐中，往往需要在短時間內集中完成所有畢業生的論文答辯任務。面對這種情況，當同一專業的學生較多時，經常將答辯評議專家和答辯學生事先分組，然后再安排各組學生同時進行答辯。顯然，科學的分組方法是做好答辯工作的重要前提。對于分組問題，為了實現項目申請書與評審專家的自動匹配，毛晚堆等［4］提出了利用二部圖譜劃分異構對象的分組匹配算法。為了提高分組效率，避免分組差異引起的面試結果偏差，陳媛等［5］建立了綜合面試問題的雙目標均衡分組模型。為了減少社會化考試中的閱卷差錯，提高閱卷速度，汪定偉等［6］建立了評卷人分組的非線性0-1 整數多目標規劃模型，設計了模型求解的遺傳算法。這些成果為答辯分組提供了理論借鑒。針對小規模答辯分組問題，曹莉等［7］基于回避原則和均勻原則，探討了尋求最佳分組方案的單目標優劣交叉微分進化算法，但是沒有建立分組問題的數學規劃模型。方剛等［8］建立了研究生答辯分組和組內評審指派的兩階段非線性整數規劃模型，并利用Lingo 軟件求解該模型，取得了良好效果。不過，本科論文評審制度和答辯規則與研究生不盡相同，無法利用研究生分組答辯模型解決本科答辯問題；另外，研究生答辯時經常按研究方向分批或集中進行，同時答辯的人數較少，便于利用優化軟件解算分組模型，而本科生答辯時往往按專業集中進行，同時答辯的人數較多，答辯分組問題規模較大，不利于優化軟件的直接利用。以往研究為合理分組打下良好基礎，但是當同時考慮導師和學生的公平性要求時，答辯評議專家與答辯學生的匹配關系將更加復雜，還需結合決策順序進一步優化分組方案。考慮以上情況，本文根據本科論文答辯問題的特點，建立了答辯評議專家和答辯學生匹配分組的兩階段序貫決策模型，為快速得到分組結果，設計了模型求解的混合遺傳算法。

1 問題描述

假設某專業的m 名學生已經在n 位教師的指導下完成畢業論文，計劃分g 組同時答辯。該專業有b個研究方向，通過調查，已經獲知論文i（即學生i的論文，i ＝1，2，…，m）對方向d（d ＝1，2，…，b）的隸屬程度n）對方向d的熟悉程度βjd（0≤βjd≤1）。根據教務處“一個答辯評議組由3 ～5 名答辯評議專家構成”的規定，確定了各答辯評議組的專家人數nk（k ＝1，2，…，g）。根據該專業“答辯評議專家均由指導教師擔任”和教務處“一個答辯評議組至少含有2 名高級職稱專家（含副高和正高）”的規定及擔任答辯評議專家的其他要求，已經從指導教師中挑選出了不少于2g個具有前的任務是如何對這些答辯評議專家和答辯學生進行合理分組。

2 專家-學生匹配分組模型

以往制訂分組方案時，通常以所有論文相對于其答辯評議組的研究方向匹配度之和最大化為目標進行專家和學生的組別劃分。實際上，這種分組方法僅能提高論文與答辯評議組之間的平均匹配程度，很難保證最小匹配度的有效性。眾所周知，論文內容與答辯評議專家的研究方向越吻合，答辯評議組給出的論文評價結果越可靠。若最小匹配度過低，說明有學生分配到了答辯評議組不太熟悉其論文內容的答辯組中。此種情形下，該答辯評議組很難客觀評價其論文質量，可能導致答辯中的相對不公平。為解決這一問題，本文首先求得可以滿足分組約束的最大的最小論文匹配度；若該最小匹配度符合要求，再在確保此最小匹配度的前提下，尋找最大的平均論文匹配度。

另外，學生答辯時，不同專家的給分尺度存在差異但又不易統計（尤其存在首次擔任答辯評議專家的教師時），這種差異將最終導致答辯評議組之間的給分差異。于是，對于一名學生而言，若將其分配到不同的答辯組中，即便相應答辯評議組同樣熟悉其論文內容，也很難得到相同的答辯成績。對于導師而言，若將同一導師指導的學生集中分配在少數幾個答辯組中，則難以充分比較導師之間的指導效果，不便根據學生答辯成績客觀評價導師們的指導水平。極端情況下，若將一位導師的學生全部分配在一個給分最為“嚴厲”的答辯組中，還可能影響其考核結果（尤其存在答辯未通過學生時），進而導致導師之間的相對不公平。針對這一問題，考慮到專家-學生協同分組需要，本文建模時將同一導師的學生盡量分在了多個答辯組中。

為了建立專家-學生匹配分組的兩階段序貫決策模型，下面首先分析約束條件，然后給出目標函數。

2． 1 約束條件

（1）被選為答辯評議專家的導師將被分配在某個答辯評議組中，未被選中的導師不會分配在任何答辯評議組中，有：

式中：pj為導師j是否被選為答辯評議專家，是取1，否取0；yjk為決策變量，表示導師j 是否分配在第k 個答辯評議組中，是取1，否取0。

（2）各答辯評議組中，專家數量應符合要求且至少含有2 名高級職稱專家，有：

式中：tj為導師j是否具有高級職稱，是取1，否取0。

（3）每個學生僅能分配在一個答辯組中，有：

式中：xik為決策變量，表示學生i是否分配在第k 個答辯組中，是取1，否取0。

（4）學校建議了學生答辯時的論文陳述時間和專家提問時間，因此一個答辯組的工作時間主要取決于該組的學生數量。為了平衡各答辯評議組的工作時間，每個答辯組的學生數量應盡量相等（即答辯組之間的學生數量差值不能超過1），有：

式中：符號·和·分別為小于“·”的最大整數和大于“·”的最小整數。

（5）由于答辯評議專家不可避免地存在系統性評分差異（如評判基準分差異、優劣程度的給分區間差異等），因而難以根據不同組的學生答辯成績直接判斷組間論文質量的優劣［9］。為便于客觀反映導師們的指導效果，方便導師之間的相互比較，此處將同一導師的學生盡量均勻地分布在多個答辯組中。同時，還須堅持導師回避制度，即每名學生均不能分配在與自己導師所在答辯評議組相對應的答辯組中。綜合以上要求，有：

式中：rij為導師j是否為學生i 的指導教師，是取1，否取0；qj為導師j指導的學生數量。

（6）論文i對方向d 的隸屬程度為αid，導師j 對方向d的熟悉程度為βjd，因此導師j 對論文i 的熟悉若將學生i分配在第k答辯組中，則第k答辯評議組對論文i 的熟悉程度可量化為該評議組專家對論文i 的平均熟悉程度，即于是，若稱該平均熟悉程度為論文i與其答辯評議組的研究方向匹配度，簡稱論文i的匹配度，并記s0為所有論文中的最小論文匹配度，有：

（7）考慮各決策變量的現實意義，有：

2． 2 目標函數

（1）第一階段使最小論文匹配度最大化，有目標函數：

求解該模型，可以得到最佳的專家-學生匹配分組方案。

3 模型算法

3.1 總體思路

由于式（9）、（13）～（14）均含有關于決策變量的非線性表達式，并且在第一階段s0為連續型決策變量，故第一階段的模型屬于非線性混合整數規劃模型，第二階段的模型屬于非線性純整數規劃模型，兩階段序貫決策模型整體上屬于非線性整數規劃模型。一般地，對于規模較小的非線性規劃問題，可以利用優化軟件（如Lingo、Matlab 等）直接求解［10-11］；但是，當問題規模稍大時，不便直接解算，當同時含有整數決策變量時，求解難度更大。本文模型均為含有整數變量的非線性規劃模型，不宜直接利用軟件求解。但是，如果給定專家分組方案，即把yjk變為常量，那么，第一階段的模型便成了線性的整數規劃模型，能夠大幅度降低求解難度。由于同一專業的學生數量不會過多（例如不超過210 人），經測試，利用Lingo12 軟件可以快速求解這類線性整數規劃模型（測試時，假設學生數為210，專業方向數為5，答辯組數分別為5、6 和7，每組專家數分別為4 或5，隨機產生專家分組方案；利用Lingo12 求解，所有模型均可在數10 s內得到結果，其中絕大多數模型數秒得到結果；但是，當利用Matlab R2015b的相應函數intlinprog 解算模型時，運算時間較長）。考慮遺傳算法（Genetic Algorithm，GA）特點［12］，對于第一階段的決策模型而言，如果用GA 中的染色體代表專家分組方案并通過一定方法產生染色體（即給定專家分組方案），那么，利用Lingo軟件便可得到各代種群中相應于不同染色體的學生分組結果和對應目標函數值；這樣，結合GA 迭代尋優過程，能夠得到較為理想的最小論文匹配度。在第二階段模型中，由于以約束條件式（14）替換了第一階段模型的式（9），其可行域較比第一階段模型大幅度縮減，不利于GA的尋優運算。考慮序貫決策要求［13-14］，通過染色體庫把兩個階段的決策聯系起來，然后將染色體庫中滿足式（14）且使目標函數式（13）最大的染色體作為第二階段的滿意染色體，進而得到專家-學生的滿意匹配分組方案。這樣，便形成了以染色體庫為紐帶、嵌入線性整數規劃精確算法（由Lingo軟件實現精確計算）的混合遺傳算法。

3.2 第一階段模型算法

第一階段尋找最大的s0，主要步驟如下［15］：

3.2.1 生成初始種群

令每條染色體代表一個專家分組方案，每個基因對應一個專家編號。亦即，染色體由被選中導師的編號構成，長度為n′，其中前n1個編號對應分配在第1個答辯評議組中的專家，第（ni-1+ 1）～第（ni-1+ ni）個編號對應分配在第i（i ＝2，…，g）個答辯評議組中的專家。這種染色體滿足式（1）、（2）的要求，并且據其可以得到yjk的值。隨機產生規定數量的染色體，形成初始種群。

3.2.2 計算適應度值

對于一條給定的染色體，首先判斷其是否在染色體庫中。如果在庫中，則根據庫中記錄得到與其對應的模型目標值。如果不在庫中，則判斷其是否滿足式（3）。如果不滿足，令模型目標值為一個充分小的數；如果滿足，利用Lingo軟件（主要是應用其分支定界精確算法）求解以式（12）為目標函數、式（4）～（11）為約束條件的決策模型，得到模型目標值（已知該模型一定有最優解）［16］。然后，將該染色體及其模型目標值錄入染色體庫。當計算完一代種群中所有染色體所對應的模型目標值后，利用壓差為2 的線性排序方法、按照目標值越大越適應環境的原則，計算每條染色體的適應度值［15］。

需要注意的是，在向染色體庫錄入染色體時，為避免染色體重復，應將染色體內各答辯評議組中的專家編號分別由小到大重新排序，然后再按照各答辯評議組中第1 位專家的編號大小，對各答辯評議組的順序進行重新調整（答辯評議組中第1 位專家的編號越小，該答辯評議組的編號也越小）。在使用染色體庫時，必須考慮這個規定。

3.2.3 遺傳算子操作

（1）選擇。根據隨機遍歷抽樣算法，結合代溝技術，從當代種群中挑選出作為父輩的部分染色體。

（2）交叉。為生成不同的子代個體，根據交叉概率對選出的多對父輩染色體進行兩點交叉。每對染色體交叉時，首先在區間［1，n′］上隨機確定交叉段的起點p1和終點p2，然后互換兩條染色體的p1～p2基因段，若新換入的基因段中含有原染色體保留部分的專家編號，則參照原染色體中的基因對應關系修正這些編號，進而形成兩個子代個體（見圖1）。此處以圖1（b）所示染色體1 中重復編號8 的修正為例，說明單個重復編號的修正過程。在該染色體1 中，新換入基因段中的8 對應原染色體中的6，但6 也在新換入的基因段中，于是尋找新換入基因段中的6 所對應的原染色體中的專家編號；該編號為5，并且5 不在新換入的基因段中，于是用5 替換原染色體保留部分中的8，至此完成編號8 的修正過程。

圖1 染色體兩點交叉示意圖

（3）變異。按照變異概率在子代種群中選擇需要變異的個體，進行單點變異。單點變異時，首先在染色體中隨機確定一個變異基因，并記下該基因對應的專家編號；然后隨機產生一個其他評議組的專家編號，并互換這兩個編號位置，進而形成變異個體（見圖2）。

圖2 染色體單點變異示意圖

（4）重組。按照代溝設置比例將父代種群中的個體精英保留下來，從而獲得完整的子代種群［15］。

3.2.4 繼續或終止運算

循環迭代計算適應度值和遺傳算子操作，以便獲得最大的最小論文匹配度。如果迭代到了最大允許進化代數或者最優目標值在規定代數內沒有變化，則終止運算，此時的最佳目標值就是最小論文匹配度的滿意值。如果該值滿足實際要求，可將其作為s0*。

4 模型及算法應用

某輔修專業的201 名本科生在38 位教師的指導下完成畢業論文，計劃分6 組同時答辯。該專業有5個主要研究方向。在統計每篇論文的具體方向時，要求學生結合實際情況最多填寫3 個方向；若某論文隸屬多個方向，則重要方向寫在前面，同時備注各方向隸屬度。在統計教師熟悉程度時，對每個方向給出了非常熟悉、較熟悉、一般、不太熟悉和不熟悉5 個選項，相應量化值為1、0． 8、0． 6、0． 4 和0。根據相關規定，為每個答辯評議組分配4 位專家，已確定24 位專家人選。

利用Matlab R2015b編寫混合遺傳算法程序。在程序的核心代碼中，應用批處理命令調用了Lingo12的Runlingo． exe 可執行文件，利用文本文件實現了Matlab與Lingo之間的數據傳遞；另外，還根據需要，調用了英國設菲爾德（Sheffield）大學的Matlab GA 工具箱。GA參數設置為：種群個體數目40，最大進化代數50，交叉概率0． 6，變異概率0． 1，代溝系數0． 95。連續運行5 次第1 階段程序，依次得到滿意目標值0． 705、0． 72、0． 715、0． 72 和0． 71。其中，第2 次進化過程見圖3。取其中的最好值0． 72 作為最大的最小論文匹配度。經研究，該最小匹配度符合現實要求，可轉入第2 階段的程序運算。在第2 階段，統計結果顯示，在染色體庫中有6 個個體的最小論文匹配度為0． 72，其中的最大平均論文匹配度為0． 844 2。這樣，根據平均論文匹配度為0． 844 2 的個體便可得到專家與學生的滿意匹配分組方案。該方案中，有2 名學生的論文匹配度為0． 72，5 名學生的論文匹配度為1，論文匹配度分布情況如圖4 所示。

圖3 第1階段第2次運算的進化過程

如果僅以平均論文匹配度最大為目標制訂分組方案，利用混合遺傳算法解算以式（13）為目標函數、式（1）～（8）和式（10）為約束條件的非線性整數規劃模型，可以得到最大的平均論文匹配度0． 882 1（進化過程見圖5），該值大于0． 844 2，但此時的最小論文匹配度僅為0． 42，很難滿足現實要求。可見，本文方法是切實可行的。

圖4 論文匹配度直方圖

圖5 僅追求最大平均論文匹配度的進化過程

5 結 語

本科畢業論文答辯是本科教學實踐中的重要一環，論文答辯成績關系到學生和指導教師的切身利益，是衡量專業教學效果的重要依據。為培養合格人才，提高教學質量，有必要對本科畢業論文答辯問題進行精準管理。為做好答辯評議專家和答辯學生的匹配分組工作，建立了兩階段序貫決策模型，提出了求解模型的混合遺傳算法，并對其進行具體應用。應用結果表明，模型和算法是切實可行的。本文的答辯評議專家均為指導教師，當某些專家不是指導教師時，僅需將他們排在指導教師后編號，模型和算法同樣適用；另外，當學生過多時，可以先將學生分成若干個200 人以下的大班，然后再利用本文方法制訂每個大班的具體分組方案。答辯成績反映了專業教學效果和導師指導水平，今后可以結合答辯成績完善相關教學管理制度。