曹 莉, 許玉龍, 李亞威

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

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

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

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

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

曹 莉, 許玉龍, 李亞威

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

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

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

單目標(biāo);微分進(jìn)化;答辯分組;數(shù)學(xué)模型;矩陣編碼;適應(yīng)度

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

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

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

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

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

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

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

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

1 問題建模分析

1.1 模型假設(shè)

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

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

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

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

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

同時約定以下符號:

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

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

p:每位老師指導(dǎo)學(xué)生人數(shù).

g:分組總數(shù).

s:分組結(jié)果中每組參加答辯學(xué)生人數(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名學(xué)生,每位老師指導(dǎo)2名學(xué)生,共分為3組,每組學(xué)生4人,老師2人.

1.2 模型定義

定義1.老師指導(dǎo)學(xué)生矩陣A

1.3 模型定理

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

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

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

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

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

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

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

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

2.1 種群初始化

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

圖1 老師矩陣A

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

圖2 分組矩陣B

2.2 變異操作

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

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

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

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

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

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

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

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

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

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

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

2.4 選擇操作

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

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

2.5 適應(yīng)度計算

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

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

圖3 檢驗矩陣C

2.6 修正操作

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

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

2.7 總體流程

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

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

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

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

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

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

圖4 算法總體流程圖

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

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

(1)選擇老師

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

(2)選擇學(xué)生

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

(3)死鎖處理

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

(4)適應(yīng)度

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

圖5 一般算法流程圖

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

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

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

表1 6名老師指導(dǎo)12名學(xué)生的信息

表2 8名老師指導(dǎo)32名學(xué)生的信息

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

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

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

表3 個體1對應(yīng)的分組方案

表4 個體5對應(yīng)的分組方案

表5 個體8對應(yīng)的分組方案

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

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

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

個體1和2對應(yīng)的分組方案如表6和表7所示.

表6 個體1對應(yīng)的分組方案

表7 個體2對應(yīng)的分組方案

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

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

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

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

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

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

表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ī)模較小的情況下輸出可行解是快速、高效的,但輸出的解不具有進(jìn)化過程.當(dāng)問題規(guī)模稍大時,輸出無效解的概率過大,算法效率明顯降低.

5 結(jié)果分析

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

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

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

2 司守奎,孫璽菁.數(shù)學(xué)建模算法與應(yīng)用.北京:國防工業(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 許玉龍,方建安,王曉鵬,等.基于非支配解排序的快速多目標(biāo)微分進(jìn)化算法.計算機應(yīng)用,2014,34(9):2547–2551,2561.[doi:10.11772/j.issn.1001-9081.2014.09.2547]

5 黃仁全,靳聰,賀筱軍,等.自適應(yīng)局部增強微分進(jìn)化改進(jìn)算法.空軍工程大學(xué)學(xué)報(自然科學(xué)版),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 許玉龍,方建安,趙靈東,等.微分進(jìn)化求解無線傳感器網(wǎng)絡(luò)中的覆蓋問題.計算機工程與設(shè)計,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

曹莉,許玉龍,李亞威.單目標(biāo)優(yōu)劣交叉的微分進(jìn)化解決答辯分組問題.計算機系統(tǒng)應(yī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)

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

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