彭光彬, 何靜媛

(1.重慶機電職業(yè)技術(shù)大學(xué) 信息工程學(xué)院,重慶 402760; 2.重慶大學(xué) 計算機學(xué)院,重慶 400044)

0 引言

面試是我國研究生招生入學(xué)考試復(fù)試時的重要環(huán)節(jié)之一。在分組時一般需要考慮組中對象的均衡性問題，對此，劉文麗等[1]使用了諸如隨機分組、聚類分組的方法分別對面試官和考生進行分組，但未涉及面試者與考官關(guān)系；陳媛等[2～4]也研究了面試過程中的均衡分組問題，并建立了相關(guān)模型，對雙目標函數(shù)采取加權(quán)求和方式求得適應(yīng)度值，并利用遺傳算法解決該類問題；葉鑫等[5]、樊治平等[6]所述的應(yīng)急救援分組問題，也通過線性加權(quán)法轉(zhuǎn)換為單目標問題。許玉龍等[7]研究了學(xué)生答辯分組問題，引入了NSGA Ⅱ算法，該方法在解決規(guī)模較小的答辯分組問題時性能較好。

另外，在分組時也需要權(quán)衡多方面的因素，故分組問題通常也是一個多目標優(yōu)化問題。進化算法、群體智能算法等被廣泛地用于解決分組優(yōu)化問題[8]。如Falkenauer提出了分組遺傳算法[9](grouping genetic algorithm, GGA)，并在如CFP[10]和多倉庫取貨及配送[11]等問題上取得較好效果。從上世紀80年代末開始，研究者們陸續(xù)開發(fā)了三代的多目標進化算法，其中比較經(jīng)典的是第二代的NSGA Ⅱ[12]算法，而第三代的MOEA/D[13]、NSGA Ⅲ[14]等算法，需對目標函數(shù)進行分解或劃分，這對分組問題似乎存在較大困難。NSGA Ⅱ算法對于二目標、三目標，尤其是二目標具有較好性能，但對于高維多目標優(yōu)化問題，則效率低、優(yōu)化效果不明顯[15]。賴文星等[16]人提出了基于支配強度的改進算法，該算法在多個領(lǐng)域取得比較好的結(jié)果[17～19]。

綜上所述，在分析研究生招生面試分組這一NP難問題基礎(chǔ)上，提出了一種基于支配強度和矩陣編碼的、隨機生成精英初始種群的多目標分組遺傳算法。該算法將NSGA Ⅱ算法有效地融入分組遺傳算法中，結(jié)果表明，優(yōu)化效果明顯。

1 研究生招生面試分組問題的數(shù)學(xué)模型

1.1 問題描述

設(shè)有m個面試導(dǎo)師，n個被面試的學(xué)生，每g個導(dǎo)師分成一組，共分為p組(p=m/g，要求m能被g整除)，導(dǎo)師團隊共有s個。一般地，研究生面試分組問題的限制條件如下：(1)某個學(xué)生、導(dǎo)師只能屬于某一個面試組；(2)每個學(xué)生限選1名導(dǎo)師，且學(xué)生與填報的導(dǎo)師必須分配在同一面試組，未填報導(dǎo)師的學(xué)生可以分配到任意一組。(3)每個組的導(dǎo)師盡量來自同一導(dǎo)師團隊(目前只需考慮大的導(dǎo)師團隊)；(4)每個組的學(xué)生數(shù)量盡量一致。

1.2 編碼設(shè)計

GGA算法的關(guān)鍵之一是設(shè)計一種有效的編碼方案。首先對研究團隊(下稱團隊)、學(xué)生、導(dǎo)師進行編號；其次使用矩陣即二維數(shù)組來表示導(dǎo)師與學(xué)生、導(dǎo)師與團隊之間的二維關(guān)系；最后也使用矩陣來存放分組結(jié)果。

定義1導(dǎo)師與學(xué)生關(guān)系矩陣A：

其中，aij(i=1,2,…,m)取值為1或0，列號表示學(xué)生，行號表示導(dǎo)師。要求每一列中最多只允許有1個為1的項，即1個學(xué)生最多只能填報1名導(dǎo)師；若某列j全為0，則表示學(xué)生j沒有填報任何導(dǎo)師。

定義2團隊與導(dǎo)師關(guān)系矩陣B:

其中，bij(i=1,2,…,m)取值為1或0，列號表示團隊，行號表示導(dǎo)師。要求在每一行中有且只有1個為1的項，即1個導(dǎo)師只能屬于1個團隊。

定義3分組結(jié)果矩陣C(即遺傳算法中的染色體)：

其中，cij(i=1,2,…,m)取值為1或0。要求在每一列中有且只有g(shù)個為1的項，表示每組導(dǎo)師數(shù)必須為g。

1.3 構(gòu)建優(yōu)化目標函數(shù)

定義4導(dǎo)師與學(xué)生關(guān)系評價函數(shù)如式(1)所示。

(1)

其中A*表示經(jīng)過處理的導(dǎo)師與學(xué)生關(guān)系矩陣A，處理方法是：若矩陣A中某列j全為0，則將該列所有項置為1，表示學(xué)生j可與任意一個導(dǎo)師分在一組。fst的取值范圍為[0,u*g+n-u],u是未填報導(dǎo)師的學(xué)生數(shù)。

定義5導(dǎo)師與團隊關(guān)系評價函數(shù)fs如式(2)所示。

(2)

定義6每組學(xué)生人數(shù)評價函數(shù)如式(3)所示。

(3)

其中，snumst表示第st組的學(xué)生人數(shù)。fstd的取值范圍為[-n,0]。

根據(jù)以上分析，建立的研究生面試分組數(shù)學(xué)模型如式(4)所示:

max(fst,fs,fstd)

(4)

2 基于支配強度的NSGAⅡ改進算法求解分組問題

基于支配強度的NSGAⅡ[16]改進算法繼承了經(jīng)典的NSGAⅡ的算法的快速非支配排序算法。兩者不同點在于：前者采用支配強度來比較非支配集中個體的優(yōu)劣性能，而后者通過擁擠度加以比較；在支配強度一樣時，前者通過新型擁擠距離來評價個體；前者采取自適應(yīng)精英保留策略，而后者使用常規(guī)的精英保留策略，本文根據(jù)分組問題實際，采取常規(guī)的精英保留策略，并在種群初始化時就生成較好的精英種群，以加快優(yōu)化進程，從而滿足快速分組用戶偏好。

2.1 支配強度計算與個體間的比較

支配強度ε的計算如式(5)所示，文獻[16]描述的是最小值的優(yōu)化，而本文是最大值的優(yōu)化，故稍有不同。顯然，個體的支配強度越小，表示越接近目標值，因而個體越優(yōu)秀。支配強度可有效識別和去除偽非支配解。

(5)

考慮方差的新型擁擠距離iD的計算方法與文獻[16]提供的方法一樣。改進后的NSGA Ⅱ算法經(jīng)過快速非支配排序、支配強度計算及擁擠距離計算后，每個個體就有了三個屬性：非支配的評級即Rank、支配強度ε和擁擠距離iD。對于任意兩個個體i和個體j，可有如式(6)所示的優(yōu)先級關(guān)系：

(6)

2.2 改進的帕累托支配關(guān)系

假設(shè)X1和X2是多目標優(yōu)化問題的兩個解，當且僅當式(7)成立時，稱X1支配X2，記作X1?X2，其中X1是非支配的，X2是被支配的。

(7)

由于研究生招生面試分組問題應(yīng)滿足目標函數(shù)fst、fs最大化，為了在所有目標函數(shù)上盡可能的取得最大值，對帕累托支配規(guī)則進行了修改，如滿足式(8)，則個體i支配個體j。

(8)

2.3 初始種群次精英化

NSGAⅡ算法在求解分組問題時，對規(guī)模較大問題，需要迭代上千次才有可能收斂，且易陷于局部最優(yōu)。因此采取初始種群次精英化的策略：即初始種群的所有個體在目標函數(shù)fst、fs上取得最大值。初始種群次精英化的步驟如下：(1)將矩陣A生成復(fù)制成初始染色體矩陣C；(2)從矩陣A中獲取未填報導(dǎo)師的學(xué)生集合，同時從矩陣B獲取每個團隊的導(dǎo)師數(shù)；(3)在每個團隊上隨機選取導(dǎo)師生成?tnumk/g」個分組，記下未分配組的導(dǎo)師；(4)根據(jù)每個團隊未分配組的導(dǎo)師數(shù)按降序排序，按照一種“湊數(shù)”法組合剩余的導(dǎo)師形成分組，使得團隊與導(dǎo)師的評分最大化；(5)將已填報導(dǎo)師的學(xué)生分配到所填報導(dǎo)師的分組中；(6)計算每組學(xué)生人數(shù)，將未填報導(dǎo)師的學(xué)生逐一分配到學(xué)生人數(shù)小于標準學(xué)生人數(shù)的組中去，并更新每組學(xué)生人數(shù)。

以上步驟中，關(guān)鍵在于步驟(4)中的“湊數(shù)”法。在1.3的定義5中的例子中，在步驟(3)后，每個團隊未分配組的導(dǎo)師人數(shù)的降序序列為N={4,4,3,3,1}，顯然N[1]與N[5]、N[2]與N[4]中隨機選擇1位導(dǎo)師以及N[3]與N[4]中剩余的2位導(dǎo)師正好可湊成每組導(dǎo)師人數(shù)5，從而可組合成最大化導(dǎo)師與團隊評分的分組。

2.4 多交叉算子

GGA算法的另一關(guān)鍵技術(shù)是構(gòu)造高效的交叉算子和變異算子，以便能快速地收斂到最優(yōu)值。研究生招生面試分組問題采用矩陣方式編碼染色體，同時在矩陣中涉及到分組，因此提出了四種交叉算子：行交叉、列交叉、組中師交叉和組交叉。這幾種交叉算子在遺傳算法執(zhí)行的過程中以相同的概率(25%)隨機執(zhí)行。

(1)行交叉。先隨機選擇一行r來交叉，設(shè)參與交叉的兩個染色體分別為C1和C2，找到C1和C2的第r行所屬的組(設(shè)為g1和g2)，接下來用C2的第r行替換C1的g1組中的所有行，同樣用C1的第r行替換C2的g2組中的所有行，進行沖突檢測后更新染色體的相關(guān)屬性(如fst、fs、fstd等)。

(2)列交叉。列交叉的流程與行交叉類似，交叉后也需要進行調(diào)整，在此不再贅述。

(3)組中師交叉。進行組中師交叉時，分別在參與交叉的染色體中，隨機選擇1個不同的導(dǎo)師(組號也不能一樣)進行交叉。

(4)組交叉。對兩個染色體，隨機找一組號為gn的組進行交換。交換時先保存每組有哪些學(xué)生，再交換這2個組中的導(dǎo)師，最后對重復(fù)的導(dǎo)師進行調(diào)整。

2.5 變異算子

按列變異與按組變異以等概率方法隨機選擇變異算子。按列變異時，隨機選擇不同的2列進行交換。按組變異時先隨機選擇不同的兩組，再分別在這兩組中隨機選擇一個導(dǎo)師進行交換。

2.6 算法流程

圖1 研究生招生面試分組問題流程圖

3 實驗結(jié)果與分析

下述說明中：INSGA2DSE是基于支配強度的次精英化初始種群的NSGAⅡ算法、NSGA2E是經(jīng)典的次精英化初始種群的NSGAⅡ算法、INSGA2DS是基于支配強度的隨機初始化種群的NSGAⅡ算法、NSGA2是經(jīng)典的隨機初始種群的NSGAⅡ算法。

3.1 最優(yōu)前沿比較

采用初始種群次精英化策略后的最優(yōu)前沿明顯高于未采用該策略的算法；由于有意識迎合了用戶偏好，該策略多樣性也明顯不足?；谥鋸姸鹊腘SGA2算法明顯優(yōu)于經(jīng)典NSGA2算法；由于去除了NSGA2算法中的部分偽支配解，基于支配強度的NSGA2算法的多樣性似乎弱于經(jīng)典NSGA2算法。

采用初始種群次精英化策略且改進了帕累托支配關(guān)系的最優(yōu)前沿主要集中在平行于fstd軸的一條線上，在fst、fs上取得了不錯的優(yōu)化；而未改進帕累托支配關(guān)系的最優(yōu)前沿分布較前者均勻，但在fstd的優(yōu)化上要差一些。因此，從“面試分組”應(yīng)用的角度看，修改過的帕累托支配關(guān)系的優(yōu)化無疑是成功的，基本滿足了用戶偏好。

3.2 進化效果分析

選取2種典型的導(dǎo)師和學(xué)生人數(shù)(其中，團隊數(shù)、每組導(dǎo)師數(shù)皆為5)：50個導(dǎo)師、100個學(xué)生，100個導(dǎo)師、200個學(xué)生；設(shè)置三種學(xué)生未填報導(dǎo)師比率：0.3、0.15、0.0，這樣一共6種情形，在交叉率0.9、變異率0.5的前提下，基于支配強度的次精英化初始種群的NSGAⅡ算法(INSGA2DSE)、經(jīng)典的次精英化初始種群的NSGAⅡ算法(INSGA2DSE)各進化300代，基于支配強度的隨機初始化種群的NSGAⅡ算法(INSGA2DS)、經(jīng)典的隨機初始種群的NSGAⅡ算法(NSGA2)各進化1500代，各算法在每次運行相同的分組問題，共運行100次，對最佳個體的各個比較維度取其平均值(最佳前沿面的個體在進化結(jié)束時各目標函數(shù)與最佳個體基本一致，故不做比較)。

最佳個體通過式(9)進行比較，找到Fitness值最大的即是最佳個體。式(9)中乘以g(每組導(dǎo)師人數(shù))是為了保證Fitness非負性。

fitness=g×(fst+fs)+fstd

(9)

4個比較維度分別是：fstd、MaxNum、MaxDVst、MaxDVs。MaxNum是分組結(jié)果中標準學(xué)生人數(shù)與每組學(xué)生人數(shù)之差的絕對值中的最大值，該值可以衡量分組結(jié)果的優(yōu)劣，越小分組結(jié)果越好；MaxDVst是可獲取的最大的導(dǎo)師與學(xué)生關(guān)系評分與實際獲取的導(dǎo)師與關(guān)系評分的差值；MaxDVs是可獲取的最大的導(dǎo)師與團隊關(guān)系評分與實際獲取的導(dǎo)師與團隊評分的差值。MaxDVst、MaxDVs可以衡量分組結(jié)果的目標達成度，分組結(jié)果應(yīng)盡量滿足同組導(dǎo)師團隊一致的條件，必須滿足學(xué)生與學(xué)生所選導(dǎo)師在同一組的條件。這三個維度的計算如式(10)所示。

(10)

表1 不同組合情形下不同算法的比較

在進行實驗結(jié)果分析時，為了圖表更加直觀和清晰，對fstd函數(shù)取了相反數(shù)。表1是不同組合情形下不同算法在4個維度上的比較。從表1可以觀察到：

(1)次精英化策略非常有效。從表1可以看出，INSGA2DSE和NSGA2E算法的MaxDVst、MaxDVs的值非常小，這說明優(yōu)化后的導(dǎo)師與學(xué)生的評分fst、導(dǎo)師與團隊的評分fs與實際能獲取的最大值非常接近，個別值為負表示優(yōu)化后的結(jié)果比實際能獲取的結(jié)果還要好。fstd、MaxNum也表現(xiàn)優(yōu)異。以MaxNum為例，在學(xué)生未填報導(dǎo)師比例為0.3時，次精英化策略至少提升92.3%以上，平均提升93.5%；在學(xué)生未填報導(dǎo)師比例為0.15時，次精英化策略至少提升64%以上，平均提升70.8%；在學(xué)生未填報導(dǎo)師比例為0時，次精英化策略至少提升36.9%以上，平均提升38.9%。隨著學(xué)生未填報導(dǎo)師比例的減少，次精英化策略優(yōu)化效果存在下降趨勢，這是因為學(xué)生與導(dǎo)師關(guān)系也隨之更加確定的緣故。

(2)基于支配強度的NSGA Ⅱ算法的優(yōu)化效果更好。經(jīng)典NSGA Ⅱ算法與基于支配強度的NSGA Ⅱ算法在fstd、MaxNum(MaxNum與fstd具有一定的正相關(guān)性)上的優(yōu)化效果基本沒有太大區(qū)別，但在MaxDVst、MaxDVs上的優(yōu)化效果差距明顯，基于支配強度的NSGA Ⅱ算法比經(jīng)典NSGA Ⅱ算法在MaxDVs上平均提升20%，最差也提升了9%(序號5的數(shù)據(jù))；在MaxDVst上基于支配強度的NSGA Ⅱ算法，基本可認為優(yōu)化到最大值，而經(jīng)典NSGA Ⅱ算法在優(yōu)化效果上隨著導(dǎo)師、學(xué)生人數(shù)的增加，稍有下降趨勢。

4 結(jié)論

分組問題是日常工作、生活中的典型問題，面試分組問題隨著應(yīng)用的場景不同，可能也存在一些差異，本文以研究生招生復(fù)試過程中的面試分組問題為例，利用多目標優(yōu)化問題的經(jīng)典進化算法NSGA Ⅱ算法的改進算法來求解該問題，通過基于矩陣編碼的多交叉/變異算子、次精英化的初始化種群以及改進的帕累托支配關(guān)系等方法有效解決了經(jīng)典NSGA Ⅱ算法在求解大規(guī)模分組問題時的收斂速度慢、優(yōu)化效果有限的問題。在實驗過程中也發(fā)現(xiàn)，該方法針對超大規(guī)模的分組問題(如500個導(dǎo)師、1000個學(xué)生)還存在著計算機資源消耗過高的問題，未來可使用稀疏矩陣及其他多目標優(yōu)化算法改進面試分組問題。