曹 莉, 許玉龍, 李亞威

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

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

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

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

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

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

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

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

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

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

1 問題建模分析

1.1 模型假設(shè)

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

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

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

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

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

同時(shí)約定以下符號(hào):

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:檢驗(yàn)矩陣,m*m.

num:檢驗(yàn)矩陣C中不滿足老師互回避情況的對數(shù)與零元素個(gè)數(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é)生不變,通過計(jì)算變換順序后的互回避指標(biāo),發(fā)現(xiàn)任意變化分組的先后順序,互回避指標(biāo)不變,評價(jià)整體效果的互回避指標(biāo)與分組結(jié)果中每組的先后順序無關(guān),故與假設(shè)矛盾,因此分組結(jié)果中每組的先后順序不影響整體的效果,證畢.

定理2.檢驗(yàn)矩陣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)于主對角線對稱位置的兩元素同時(shí)不為零說明是滿足互回避原則的,矩陣C中每列零元素越少說明學(xué)生分布的越均勻.num是檢驗(yàn)矩陣C中關(guān)于主對角線對稱的兩元素同時(shí)不為零的對數(shù)加上每列零元素的個(gè)數(shù)的總和,可以反饋分組方案滿足老師互回避原則的情況以及滿足均勻原則的情況信息,因此,檢驗(yàn)矩陣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 種群初始化

針對答辯分組問題,采用隨機(jī)的0/1矩陣構(gòu)造一個(gè)老師矩陣A(如圖1)[11,12].矩陣的行屬性定義為學(xué)生,列屬性定義為老師,則矩陣的行數(shù)為m*n,列數(shù)為m.矩陣元素0代表老師不帶某個(gè)學(xué)生,1表示老師帶的學(xué)生,并滿足每個(gè)老師帶2個(gè)學(xué)生,每個(gè)學(xué)生只屬于一個(gè)老師.圖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個(gè)染色體矩陣,即種群矩陣.該矩陣用于表現(xiàn)答辯分組后的結(jié)果,問題的最終目標(biāo)是得到該矩陣的最優(yōu)解.種群矩陣的行列屬性與矩陣A相同,假設(shè)老師和學(xué)生數(shù)都可以被均勻的分到g個(gè)組中,每個(gè)答辯老師答辯n/g個(gè)學(xué)生,每個(gè)學(xué)生被m/g個(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)種群中個(gè)體的適應(yīng)度相差不大時(shí),說明種群中的各個(gè)體基本上趨于一致,因而可能導(dǎo)致進(jìn)化停滯,過早地收斂于局部的極值解.為此必須通過變異操作來改變不利因素,使算法 具有全局收斂性[3].變異機(jī)制如下所示:

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

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

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

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

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

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

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

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

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

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

2.4 選擇操作

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

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

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

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

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

圖3 檢驗(yàn)矩陣C

2.6 修正操作

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

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

2.7 總體流程

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

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

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

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

(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è)計(jì)方法,在設(shè)計(jì)過程中應(yīng)考慮參數(shù)的限制,死循環(huán)的處理等問題,用數(shù)組和循環(huán)來求解該問題.確定已知參數(shù)m個(gè)老師,n個(gè)學(xué)生,共分成g組,每組老師個(gè)數(shù)為m/g,每組學(xué)生個(gè)數(shù)為n/g,根據(jù)已知老師進(jìn)行答辯組分組.

(1)選擇老師

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

(2)選擇學(xué)生

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

(3)死鎖處理

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

(4)適應(yīng)度

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

圖5 一般算法流程圖

4 算法實(shí)驗(yàn)測試結(jié)果

對于以上兩種算法,分別用兩組數(shù)據(jù)測試算法的優(yōu)劣.程序中用T1,T2,……Tm來表示老師的編號(hào),用T1_1,T1_2,……T1_n來表示同屬于T1老師指導(dǎo)的學(xué)生編號(hào),依此類推,Tm_n則表示由Tm老師指導(dǎo)的第n個(gè)學(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算法運(yùn)行第一組數(shù)據(jù),初始種群包含10個(gè)個(gè)體,進(jìn)化代數(shù)為50代,運(yùn)行結(jié)果顯示了答辯分組矩陣B對應(yīng)的10個(gè)個(gè)體,均為12×6的矩陣,由于篇幅所限,不再一一展開.運(yùn)行結(jié)束后,種群中個(gè)體最小的適應(yīng)度值是20,圖6給出了DE算法進(jìn)化的曲線.在末代種群中,個(gè)體1,5,8的適應(yīng)度均為20,即是理想的答辯分組結(jié)果,表3,表4,表5分別給出了他們的分配方案.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)果分析

從測試結(jié)果來看,兩種算法都能解決答辯分組問題,并且都能滿足自回避原則,對于互回避原則和均勻原則都能盡量滿足.但一般算法運(yùn)行一次只能得到一個(gè)解,只有運(yùn)行多次才能得到多個(gè)解,且這些解不具有進(jìn)化的過程,不能從所有可能的解當(dāng)中尋得最優(yōu)值,在實(shí)際應(yīng)用中難以為決策者提供更全面可行的方案.而DE算法運(yùn)行一次能得到多個(gè)最優(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)每增加一位老師時(shí)會(huì)增加更多的學(xué)生,如果學(xué)生足夠多就能完全滿足自回避和互回避條件,但m,n具體增加到多少才能滿足條件,還留待以后進(jìn)行深入探究.

1 李劍,朱延峰,吳畏.學(xué)生面試問題的分配策略.數(shù)學(xué)的實(shí)踐與認(rèn)識(shí),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)化算法.計(jì)算機(jī)應(yīng)用,2014,34(9):2547–2551,2561.[doi:10.11772/j.issn.1001-9081.2014.09.2547]

5 黃仁全,靳聰,賀筱軍,等.自適應(yīng)局部增強(qiáng)微分進(jìn)化改進(jìn)算法.空軍工程大學(xué)學(xué)報(bào)(自然科學(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ò)中的覆蓋問題.計(jì)算機(jī)工程與設(shè)計(jì),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 劉鯖潔,陳桂明,劉小方.基于矩陣編碼的遺傳算法研究.計(jì)算機(jī)工程,2011,37(13):160–162.[doi:10.3969/j.issn.1000-3428.2011.13.051]

12 戰(zhàn)紅,楊建軍.基于工序矩陣編碼遺傳算法的車間作業(yè)調(diào)度優(yōu)化.制造業(yè)自動(dòng)化,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)化解決答辯分組問題.計(jì)算機(jī)系統(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)

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

2016-12-26;采用時(shí)間:2017-01-23