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

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

0 引 言

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

1 問題描述

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

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

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

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

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

2． 1 約束條件

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 第一階段模型算法

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

3.2.1 生成初始種群

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

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

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

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

3.2.3 遺傳算子操作

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

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

圖1 染色體兩點(diǎn)交叉示意圖

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

圖2 染色體單點(diǎn)變異示意圖

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

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

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

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

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

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

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

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

圖4 論文匹配度直方圖

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

5 結(jié) 語

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