曹 莉, 許玉龍, 李亞威

(河南中醫(yī)藥大學,鄭州 450046)

通訊作者:許玉龍,E-mail:flyxyl@qq.com

CAO Li,XU Yu-Long,LI Ya-Wei

(Henan University of Chinese Medicine,Zhengzhou 450046,China)

單目標優(yōu)劣交叉的微分進化解決答辯分組問題①

曹 莉, 許玉龍, 李亞威

(河南中醫(yī)藥大學,鄭州 450046)

通訊作者:許玉龍,E-mail:flyxyl@qq.com

論文答辯分組是高校管理中的常見問題,為保證分組的公平性和科學性,須考慮老師和學生間的若干限制條件,存在兩個相互矛盾的條件——互回避原則和均勻原則.尋求最優(yōu)的分組方案使兩個條件都能盡量滿足,是本文要解決的核心問題.通過建立數(shù)學模型,使答辯分組問題可用矩陣編碼表示,并將兩個沖突的條件整合為一個目標函數(shù).然后采用單目標優(yōu)劣交叉的微分進化求解該問題,通過構造合適染色體、適應度函數(shù),進行初始化種群、優(yōu)劣交叉、變異修正等操作,逐代進化得到最優(yōu)解.為驗證該方法的優(yōu)越性,與一般算法求解效果對比,結(jié)果表明標優(yōu)劣交叉的微分算法能夠得到更科學的分組方案、更多的可行方案.

單目標;微分進化;答辯分組;數(shù)學模型;矩陣編碼;適應度

畢業(yè)生答辯分組問題是高校教學管理中的一個常見問題,為保證分組的公平性和科學性,在分組時須考慮老師和學生間、老師和老師間,以及學生之間的關系,同時須考慮每個組的若干限制條件[1].此類答辯分組問題已經(jīng)被證明是一個受限性NP(Non-Deterministic Polynomial)難問題[2].

該問題一般的描述是:已知有m個老師,n個學生,其中每個老師指導若干名學生,但每名學生只被一名老師指導.要求分成g組答辯小組,每組中由m/g個老師,來面試答辯n/g學生,假設g能夠被m和n整除.限制條件有:

(1)每個老師不能答辯面試自己指導的學生,自回避原則,必須滿足.

(2)存在兩個老師相互面試對方學生的情況,要盡可能的少,互回避原則.該條件盡量滿足.

(3)每個老師指導的學生,盡量均勻的分散到不同的面試組中,均勻原則.該條件盡量滿足.

條件2和3相互沖突,所以要盡量滿足,可以看出該問題是一個較為復雜的組合優(yōu)化問題.針對此類問題,用常規(guī)算法求解計算量較大且難以獲取最優(yōu)解[2],較適合用啟發(fā)式進化算法來解決.

微分進化算法(Differential Evolution algorithm,DE)是一種模擬生物自然化過程搜索全局最優(yōu)解的隨機優(yōu)化算法,是近年來最著名的進化算法之一[3,4].它具有簡單,快速,魯棒性好,易于實現(xiàn),控制參數(shù)少且搜索能力強等特點,因此被廣泛應用于各個領域,尤其是在處理復雜優(yōu)化問題方面得到了廣泛關注[5,6].

DE算法在求解連續(xù)變量的函數(shù)優(yōu)化問題時能快速、穩(wěn)定地收斂到全局最優(yōu)解[7,8].本文主要研究基于單目標的DE算法在答辯分組中的應用.通過設計合適的染色體編碼方式、適應度函數(shù),然后基于DE的進化策略進行初始化種群、變異、交叉、修正等操作,對問題的解進行搜索.最后給出結(jié)果并與常規(guī)的求解方法進行對比.

1 問題建模分析

1.1 模型假設

為簡化模型,對問題中的一些元素作以下約定:

(1)所有參加答辯的學生,按十進制序號升序排序,學生個體在建模中不作區(qū)分,認為完全一樣.

(2)所有老師按十進制序號升序排序,不同老師個體之間需要區(qū)分.

(3)分組結(jié)果中每組的先后順序沒有特別要求,可以調(diào)換,不影響整體的效果.

(4)為了簡便處理,每位老師指導學生人數(shù)相同,每一組分配老師學生人數(shù)分別相同.

同時約定以下符號:

m:老師總?cè)藬?shù).

n:學生總?cè)藬?shù).

p:每位老師指導學生人數(shù).

g:分組總數(shù).

s:分組結(jié)果中每組參加答辯學生人數(shù).

t:分組結(jié)果中每組參加答辯老師人數(shù).

B:分組矩陣,m*n.

C:檢驗矩陣,m*m.

num:檢驗矩陣C中不滿足老師互回避情況的對數(shù)與零元素個數(shù)的總和.

為了簡化處理,其中人數(shù)均為整數(shù),而且有n=m*p,m=g*t,n=g*s,如 m=6,n=12,p=2,g=3,s=4,t=2 情況,則表示6位老師,12名學生,每位老師指導2名學生,共分為3組,每組學生4人,老師2人.

1.2 模型定義

定義1.老師指導學生矩陣A

1.3 模型定理

定理1.分組結(jié)果中每組的先后順序不影響整體的效果.

證明:假設分組中每組的先后順序影響分組效果,隨意變換分組中的先后順序,每組參與老師學生不變,通過計算變換順序后的互回避指標,發(fā)現(xiàn)任意變化分組的先后順序,互回避指標不變,評價整體效果的互回避指標與分組結(jié)果中每組的先后順序無關,故與假設矛盾,因此分組結(jié)果中每組的先后順序不影響整體的效果,證畢.

定理2.檢驗矩陣C可以來評估分組結(jié)果的優(yōu)劣.

證明:由于老師指導學生矩陣A乘以分組矩陣B的轉(zhuǎn)置矩陣是矩陣C,對于矩陣C(i,j),就是老師i指導的學生接受老師j面試的人數(shù).C主對角線元素是0,說明分組結(jié)果必須滿足老師自回避原則.關于主對角線對稱位置的兩元素同時不為零說明是滿足互回避原則的,矩陣C中每列零元素越少說明學生分布的越均勻.num是檢驗矩陣C中關于主對角線對稱的兩元素同時不為零的對數(shù)加上每列零元素的個數(shù)的總和,可以反饋分組方案滿足老師互回避原則的情況以及滿足均勻原則的情況信息,因此,檢驗矩陣C可以評估分組結(jié)果的優(yōu)劣,證畢.

通過例4進一步推導可知，若極限式中有冪指函數(shù)地f(x)g(x)，常用換底公式eg(x)lnf(x)將其化為指數(shù)函數(shù)進行處理。

1.4 答辯分組問題數(shù)學模型

根據(jù)以上的研究分析,建立答辯分組問題數(shù)學模型如下:

2 DE算法解決答辯分組問題

2.1 種群初始化

針對答辯分組問題,采用隨機的0/1矩陣構造一個老師矩陣A(如圖1)[11,12].矩陣的行屬性定義為學生,列屬性定義為老師,則矩陣的行數(shù)為m*n,列數(shù)為m.矩陣元素0代表老師不帶某個學生,1表示老師帶的學生,并滿足每個老師帶2個學生,每個學生只屬于一個老師.圖1中的矩陣A表示老師1指導學生2和6,老師2指導學生1和12,老師3指導學生3和7,老師4指導學生9和10,老師5指導學生4和8,老師6指導學生5和11.

圖1 老師矩陣A

然后設置種群規(guī)模N=10,來構造10個染色體矩陣,即種群矩陣.該矩陣用于表現(xiàn)答辯分組后的結(jié)果,問題的最終目標是得到該矩陣的最優(yōu)解.種群矩陣的行列屬性與矩陣A相同,假設老師和學生數(shù)都可以被均勻的分到g個組中,每個答辯老師答辯n/g個學生,每個學生被m/g個老師答辯.圖2中的矩陣B表示老師1和3答辯學生1,4,5,8;老師2和5答辯學生3,9,10,11;老師4和6答辯學生2,6,7,12(如圖2).

圖2 分組矩陣B

2.2 變異操作

變異操作是微分進化算法的核心.當種群中個體的適應度相差不大時,說明種群中的各個體基本上趨于一致,因而可能導致進化停滯,過早地收斂于局部的極值解.為此必須通過變異操作來改變不利因素,使算法 具有全局收斂性[3].變異機制如下所示:

2.3 優(yōu)劣個體的交叉策略

為增加干擾參數(shù)向量的多樣性,經(jīng)典DE中的交叉機制是:

對于基因j隨機生成一個0～1的隨機數(shù),如果隨機數(shù)小于CR那么就將變異后的個體v基因j給交叉后的個體ui,否則將變異前的i種群的j基因給變異后的種群個體ui,交叉后的個體為u.對于答辯分組問題采取行列交叉操作,即隨機選取雙親中相對應的一行,將其互換得到兩個新的子代個體[4,5].

但是,在標準進化算法的進化后期,當大多數(shù)個體聚集在局部最優(yōu)解時,種群多樣性減少,種群不能通過變異和交叉操作產(chǎn)生新的更優(yōu)個體.為增加種群多樣性,加大探索空間,依據(jù)前期研究成果[6,7],這里采用一種基于優(yōu)劣個體交叉策略.該方案中優(yōu)劣交叉具體是指,在目標向量(父代向量)和變異向量中調(diào)整出部分優(yōu)秀和劣質(zhì)個體之間完成,其中包括優(yōu)劣交叉和優(yōu)優(yōu)交叉,若種群多樣性指標非常小,即大部分個體過度聚集,采用優(yōu)劣個體間交叉可提高種群多樣性;否則,采用優(yōu)優(yōu)個體間交叉提高種群的探索能力.

用種群多樣性指標η來判斷采用哪種交叉策略.該指標受種群中個體之間的距離和適應度值的影響.為計算個體間的距離,首先介紹基因的多樣性程度

從個體之間距離的角度計算多樣性,用每五個個體(種群大小為100)中隨機選擇一個作為參照來計算種群多樣性程度,然后使用20個值得到均值為最終的多樣性程度值ξ.從上面公式(5)中可以知道,ξ的值在(0,1)之間.

另一方面,從適應度值φ來測量種群多樣性:

在公式(6)中用φ來表示多樣性.σf表示種群個體適應度值的標準偏差,fworst和fbest分別表示種群中最優(yōu)的和最差的個體適應度值.顯然,φ的值也在0和1之間.

結(jié)合ξ和φ來計算種群多樣性,并在公式(7)中使用η為最終參數(shù)表示.

η的值在0到1之間變化,根據(jù)ξ和φ,可判斷應該使用哪種交叉策略.如果η<ε,即當前種群多樣性小于容忍度ε,執(zhí)行優(yōu)劣交叉以增加種群多樣性.否則,當η≥ε,執(zhí)行優(yōu)優(yōu)交叉來提高種群的探索性.基于我們前期的工作,仿真實驗將ε=ε1=0.05作為經(jīng)驗值,更多關于優(yōu)劣交叉相關參見文獻[6,8],在此不再贅述.

2.4 選擇操作

選擇的后的是要對個體進行適應度函數(shù)評價,以此來決定是否在下一代中用候選個體替換當前目標個體.其對應法則如下:

適應度函數(shù)是選擇下一代種群的一個重要依據(jù),用來評估種群優(yōu)劣的一個指標,有的適應度函數(shù)評價值越大表示個體越優(yōu)秀,有的則是越小越優(yōu)秀,要根據(jù)具體情況而定,DE算法主要以適應度函數(shù)來指導搜索策略.假設適應度最小的為最優(yōu)解,那么當變異交叉后的U種群的個體適應度比初始種群的適應度小的時候,就將U種群選取為第G+1;反之,則將原來的第G代個體選取為第G+1代[9,10].

2.5 適應度計算

對于答辯分組問題,要求的最優(yōu)解應當滿足每個老師的學生盡可能的分布在多個答辯老師中同時盡量避免兩個老師相互面試對方學生的情況,使用檢驗矩陣C(見公式1)來反饋分組方案中滿足老師互回避原則的情況信息(定理2).適應度計算依據(jù)定理2中的num的值.

用圖1中的矩陣A和圖2中的矩陣B代入定義3得到檢驗矩陣C(如圖3).從圖3中可以看出,矩陣C主對角線的元素全部為零,說明滿足自回避原則,關于主對角線對稱的兩元素同時不為零的對數(shù)為6,矩陣中的非零元素個數(shù)為18,因此該分組方案的適應度num為24.

圖3 檢驗矩陣C

2.6 修正操作

在對種群始化,或者變異和交叉時,可能會產(chǎn)生不合法的個體,比如產(chǎn)生了與矩陣A相同行列位置同為1的情況(不滿足自回避原則),或者矩陣中某個數(shù)變成小數(shù),此時就要把不合法個體修正為合法的染色體.

修正過程既是對個體進行限制條件的驗證過程,使得個體中的值為0或1,而且行滿足限制條件,列滿足限制條件

2.7 總體流程

使用DE求解答辯分組問題步驟如下:

(1)生成初始種群,種群中包含10個體,進化代數(shù)G=0.

(2)修正操作,對隨機生成的個體依據(jù)限制條件進行修正.

(3)開始進化,對種群中每個個體進行交叉,變異和選擇操作,得到新一代的個體.

(4)判斷是否滿足終止進化條件,即是否進化迭代次數(shù)達到50代,若不滿足則進化到下一代,繼續(xù)執(zhí)行(3)中的交叉變異等操作.如果滿足終止條件,則停止搜索,算法結(jié)束并輸出結(jié)果.

圖4是DE算法流程圖,圖中G表示代數(shù),NP表示種群大小.

圖4 算法總體流程圖

3 一般算法解決答辯分組問題

為了與DE算法求解答辯分組問題做對比,給出一般方法的求解過程.一般算法即用常規(guī)的程序設計方法,在設計過程中應考慮參數(shù)的限制,死循環(huán)的處理等問題,用數(shù)組和循環(huán)來求解該問題.確定已知參數(shù)m個老師,n個學生,共分成g組,每組老師個數(shù)為m/g,每組學生個數(shù)為n/g,根據(jù)已知老師進行答辯組分組.

(1)選擇老師

隨機生成1～m個數(shù)的隨機排列,每次順序取兩個作為每答辯組的答辯老師,這種老師與老師的組合是隨機的,共可以選擇g次.

(2)選擇學生

逐一遍歷每個老師,每次從老師指導的學生中選一名學生進入答辯組,直到選夠n/g個為止,這樣才能近可能滿足均勻原則.迭代到某個老師時,首先將該老師與本組中已分配的答辯老師進行對比,如果沒有相同結(jié)果,再從該老師的學生中進行選擇(遵循自回避原則).

(3)死鎖處理

迭代過程中,可能會出現(xiàn)排除自答辯老師組學生,其它學生已全被選取的情況,此時會產(chǎn)生死鎖,出現(xiàn)這種情況需要重新進行分組.設置運行次數(shù)Runtime,如果死鎖就重新開始分組,最多運行10次.算法流程如圖5所示.

(4)適應度

為了檢驗分配方案的均勻性和互回避性,需要計算分配結(jié)果的適應度,這里定義適應度由兩個指標組成,一個是分配結(jié)果中每個答辯組里屬于同一個老師的學生個數(shù);另一個是老師互相答辯對方學生的對數(shù),最終適應度等于這兩個值之和.

圖5 一般算法流程圖

4 算法實驗測試結(jié)果

對于以上兩種算法,分別用兩組數(shù)據(jù)測試算法的優(yōu)劣.程序中用T1,T2,……Tm來表示老師的編號,用T1_1,T1_2,……T1_n來表示同屬于T1老師指導的學生編號,依此類推,Tm_n則表示由Tm老師指導的第n個學生.第一組數(shù)據(jù):m=6,n=12,g=3,對應的老師指導學生信息如表1.

第二組數(shù)據(jù):m=8,n=32,g=4,對應的老師指導學生信息如表2.

表1 6名老師指導12名學生的信息

表2 8名老師指導32名學生的信息

4.1 DE算法測試結(jié)果

用DE算法運行第一組數(shù)據(jù),初始種群包含10個個體,進化代數(shù)為50代,運行結(jié)果顯示了答辯分組矩陣B對應的10個個體,均為12×6的矩陣,由于篇幅所限,不再一一展開.運行結(jié)束后,種群中個體最小的適應度值是20,圖6給出了DE算法進化的曲線.在末代種群中,個體1,5,8的適應度均為20,即是理想的答辯分組結(jié)果,表3,表4,表5分別給出了他們的分配方案.

圖6 DE運行第1組數(shù)據(jù)進化曲線

表3 個體1對應的分組方案

表4 個體5對應的分組方案

表5 個體8對應的分組方案

從上述三個分組方案中可以看出,DE算法得出的解決方案呈現(xiàn)了多樣化的特征.

運行第二組數(shù)據(jù),仍然設定初始種群包含10個個體,進化50代,輸出10個32×8的矩陣,以此表示答辯分組結(jié)果,同時輸出這10個分組方案對應的適應度.進化曲線如圖7所示,圖中顯示種群中適應度最小為28,也就是最理想的答辯分組結(jié)果.運行結(jié)束后,種群中個體1、2的適應度都是28,即他們兩種分配方案有同樣的適應度,都可以供使用者選擇.

圖7 DE運行第2組數(shù)據(jù)進化曲線

個體1和2對應的分組方案如表6和表7所示.

表6 個體1對應的分組方案

表7 個體2對應的分組方案

4.2 一般算法測試結(jié)果

一般算法運行一次只能得到一個解,運行第1組數(shù)據(jù)結(jié)果如表8所示,這個結(jié)果的適應度為12.

表8 一般算法運行第1組數(shù)據(jù)的結(jié)果

用一般算法運行第2組數(shù)據(jù),結(jié)果如表9所示,適應度為24.

表9 一般算法運行第2組數(shù)據(jù)的結(jié)果

一般算法在運行數(shù)據(jù)時,有時會發(fā)生死鎖的情況,如表10所示,在完成3組分配后,進行第4組分配時遇到了排除自答辯老師沒有學生可分配的情況.此時,需要重新運行程序進行分組.

表10 一般算法運行第2組數(shù)據(jù)時遇到死鎖的情況

根據(jù)實驗結(jié)果,死鎖發(fā)生的概率與測試數(shù)據(jù)的規(guī)模成正比,測試第1組數(shù)據(jù)(m=6,n=12,g=3)時,程序運行30次,發(fā)生死鎖的次數(shù)為0.測試第2組數(shù)據(jù)(m=8,n=32,g=4)時,程序運行10次,發(fā)生了9次死鎖,死鎖概率為90%;運行20次時,發(fā)生了15次死鎖,死鎖概率為75%;運行30次,發(fā)生了20次死鎖,死鎖概率為67%.由此可以推斷,隨著一般算法運行次數(shù)增多,死鎖的概率會逐漸下降,但是想得到多個分組方案的話,程序至少要運行十次以上.由此可見,一般算法在問題規(guī)模較小的情況下輸出可行解是快速、高效的,但輸出的解不具有進化過程.當問題規(guī)模稍大時,輸出無效解的概率過大,算法效率明顯降低.

5 結(jié)果分析

從測試結(jié)果來看,兩種算法都能解決答辯分組問題,并且都能滿足自回避原則,對于互回避原則和均勻原則都能盡量滿足.但一般算法運行一次只能得到一個解,只有運行多次才能得到多個解,且這些解不具有進化的過程,不能從所有可能的解當中尋得最優(yōu)值,在實際應用中難以為決策者提供更全面可行的方案.而DE算法運行一次能得到多個最優(yōu)解,且這些解是經(jīng)過N代進化選擇的結(jié)果.因此,單目標微分進化算法所具備的進化過程使最優(yōu)解能從眾多的備選方案中快速顯現(xiàn),表現(xiàn)出較好的優(yōu)越性.

由于篇幅所限,只用了兩組數(shù)據(jù)測試,當每增加一位老師時會增加更多的學生,如果學生足夠多就能完全滿足自回避和互回避條件,但m,n具體增加到多少才能滿足條件,還留待以后進行深入探究.

1 李劍,朱延峰,吳畏.學生面試問題的分配策略.數(shù)學的實踐與認識,2007,37(14):153–160.[doi:10.3969/j.issn.1000-0984.2007.14.020]

2 司守奎,孫璽菁.數(shù)學建模算法與應用.北京:國防工業(yè)出版社,2012.

3 Das S,Suganthan PN.Differential evolution:A survey of the state-of-the-art.IEEE Trans.Evolutionary Computation,2011,15(1):4–31.[doi:10.1109/TEVC.2010.2059031]

4 許玉龍,方建安,王曉鵬,等.基于非支配解排序的快速多目標微分進化算法.計算機應用,2014,34(9):2547–2551,2561.[doi:10.11772/j.issn.1001-9081.2014.09.2547]

5 黃仁全,靳聰,賀筱軍,等.自適應局部增強微分進化改進算法.空軍工程大學學報(自然科學版),2011,12(3):84–89.

6 Xu YL,Fang JA,Zhu W,et al.Differential evolution using a superior-inferior crossover scheme.Computational Optimization and Applications,2015,61(1):243–274.[doi:10.1007/s10589-014-9701-9]

7 許玉龍,方建安,趙靈東,等.微分進化求解無線傳感器網(wǎng)絡中的覆蓋問題.計算機工程與設計,2014,35(9):3007–3013.

8 Cheng SL,Hwang C.Optimal approximation of linear systems by a differential evolution algorithm.IEEE Trans.on Systems,Man,and Cybernetics-Part A:Systems and Humans,2010,31(6):698–707.

9 Plagianakos VP,Vrahatis MN.Parallel evolutionary training algorithms for “hardware-friendly” neural networks.Natural Computing,2011,1(2):307–322.

10 Gamperle R,Dmuller S,Koumoutsakos P.A parameter study for differential evolution.International Conference on Advances in Intelligent Systems,Fuzzy Systems,Evolutionary Computation.Interlaken,Switzerland.2002.293–298.

11 劉鯖潔,陳桂明,劉小方.基于矩陣編碼的遺傳算法研究.計算機工程,2011,37(13):160–162.[doi:10.3969/j.issn.1000-3428.2011.13.051]

12 戰(zhàn)紅,楊建軍.基于工序矩陣編碼遺傳算法的車間作業(yè)調(diào)度優(yōu)化.制造業(yè)自動化,2013,35(7):86–88.

Based on Single-Objective Differential Evolution with Superior-Inferior Crossover Scheme to Solve the Problem of Defense Grouping

The thesis defense grouping is a common problem in the college management.To ensure the fairness and scientificity,it is necessary to consider some constraints between supervisors and students when grouping.There are two inherent contradictions:the principles of mutual avoidance and uniformity.In this paper,the main issue is to find out an optimal solution that satisfies the two conditions as far as it is possible.Through the establishment of mathematical model,the respondent grouping problem is summarized as the matrix encoding.Then two conflict conditions are consolidated into one objective function.The single objective differential evolution with superior-inferior crossover scheme is adopted to solve this problem.A suitable chromosome representation and fitness function are designed.A series of operations such as mutation,superior-inferior crossover and modification are performed.The optimal solution is obtained when the evolution is terminated.To test the advantages of this method,a general algorithm is designed for comparison with it.The results show that the grouping solution obtained by differential evolution using a superior-inferior crossover scheme is more scientific and feasible than the general algorithm.

single-objective;differential evolution;defense grouping;matrix coding;mathematical model;fitness degree

曹莉,許玉龍,李亞威.單目標優(yōu)劣交叉的微分進化解決答辯分組問題.計算機系統(tǒng)應用,2017,26(9):32–39.http://www.c-s-a.org.cn/1003-3254/5966.html

CAO Li,XU Yu-Long,LI Ya-Wei

(Henan University of Chinese Medicine,Zhengzhou 450046,China)

① 基金項后:河南省教育廳高校重點科學技術研究項后(15A520083,16A520060,17B520017);河南省科技廳2014年基礎與前沿技術研究項后(142300410391);2015年河南中醫(yī)學院博士基金(2015BSJJ-19);2017年河南省科技攻關研究項后(172102210361,172102310536)

2016-12-26;采用時間:2017-01-23