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

狄衛(wèi)民， 徐文君， 王 然

（鄭州大學(xué)管理工程學(xué)院，鄭州450001）

0 引 言

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

1 問題描述

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

2 專家-學(xué)生匹配分組模型

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

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

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

2． 1 約束條件

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

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

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

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

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

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

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

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

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

式中：rij為導(dǎo)師j是否為學(xué)生i 的指導(dǎo)教師，是取1，否取0；qj為導(dǎo)師j指導(dǎo)的學(xué)生數(shù)量。

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

（7）考慮各決策變量的現(xiàn)實意義，有：

2． 2 目標(biāo)函數(shù)

（1）第一階段使最小論文匹配度最大化，有目標(biāo)函數(shù)：

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

3 模型算法

3.1 總體思路

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

3.2 第一階段模型算法

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

3.2.1 生成初始種群

令每條染色體代表一個專家分組方案，每個基因?qū)?yīng)一個專家編號。亦即，染色體由被選中導(dǎo)師的編號構(gòu)成，長度為n′，其中前n1個編號對應(yīng)分配在第1個答辯評議組中的專家，第（ni-1+ 1）～第（ni-1+ ni）個編號對應(yīng)分配在第i（i ＝2，…，g）個答辯評議組中的專家。這種染色體滿足式（1）、（2）的要求，并且據(jù)其可以得到y(tǒng)jk的值。隨機(jī)產(chǎn)生規(guī)定數(shù)量的染色體，形成初始種群。

3.2.2 計算適應(yīng)度值

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

需要注意的是，在向染色體庫錄入染色體時，為避免染色體重復(fù)，應(yīng)將染色體內(nèi)各答辯評議組中的專家編號分別由小到大重新排序，然后再按照各答辯評議組中第1 位專家的編號大小，對各答辯評議組的順序進(jìn)行重新調(diào)整（答辯評議組中第1 位專家的編號越小，該答辯評議組的編號也越?。Ｔ谑褂萌旧w庫時，必須考慮這個規(guī)定。

3.2.3 遺傳算子操作

（1）選擇。根據(jù)隨機(jī)遍歷抽樣算法，結(jié)合代溝技術(shù)，從當(dāng)代種群中挑選出作為父輩的部分染色體。

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

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

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

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

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

3.2.4 繼續(xù)或終止運算

循環(huán)迭代計算適應(yīng)度值和遺傳算子操作，以便獲得最大的最小論文匹配度。如果迭代到了最大允許進(jìn)化代數(shù)或者最優(yōu)目標(biāo)值在規(guī)定代數(shù)內(nèi)沒有變化，則終止運算，此時的最佳目標(biāo)值就是最小論文匹配度的滿意值。如果該值滿足實際要求，可將其作為s0*。

4 模型及算法應(yīng)用

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

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

圖3 第1階段第2次運算的進(jìn)化過程

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

圖4 論文匹配度直方圖

圖5 僅追求最大平均論文匹配度的進(jìn)化過程

5 結(jié) 語

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