单目标优劣交叉的微分进化解决答辩分组问题①

曹 莉, 许玉龙, 李亚威

(河南中医药大学,郑州 450046)

通讯作者:许玉龙,E-mail:flyxyl@qq.com

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

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

单目标优劣交叉的微分进化解决答辩分组问题①

曹 莉, 许玉龙, 李亚威

(河南中医药大学,郑州 450046)

通讯作者:许玉龙,E-mail:flyxyl@qq.com

论文答辩分组是高校管理中的常见问题,为保证分组的公平性和科学性,须考虑老师和学生间的若干限制条件,存在两个相互矛盾的条件——互回避原则和均匀原则.寻求最优的分组方案使两个条件都能尽量满足,是本文要解决的核心问题.通过建立数学模型,使答辩分组问题可用矩阵编码表示,并将两个冲突的条件整合为一个目标函数.然后采用单目标优劣交叉的微分进化求解该问题,通过构造合适染色体、适应度函数,进行初始化种群、优劣交叉、变异修正等操作,逐代进化得到最优解.为验证该方法的优越性,与一般算法求解效果对比,结果表明标优劣交叉的微分算法能够得到更科学的分组方案、更多的可行方案.

单目标;微分进化;答辩分组;数学模型;矩阵编码;适应度

毕业生答辩分组问题是高校教学管理中的一个常见问题,为保证分组的公平性和科学性,在分组时须考虑老师和学生间、老师和老师间,以及学生之间的关系,同时须考虑每个组的若干限制条件[1].此类答辩分组问题已经被证明是一个受限性NP(Non-Deterministic Polynomial)难问题[2].

该问题一般的描述是:已知有m个老师,n个学生,其中每个老师指导若干名学生,但每名学生只被一名老师指导.要求分成g组答辩小组,每组中由m/g个老师,来面试答辩n/g学生,假设g能够被m和n整除.限制条件有:

(1)每个老师不能答辩面试自己指导的学生,自回避原则,必须满足.

(2)存在两个老师相互面试对方学生的情况,要尽可能的少,互回避原则.该条件尽量满足.

(3)每个老师指导的学生,尽量均匀的分散到不同的面试组中,均匀原则.该条件尽量满足.

条件2和3相互冲突,所以要尽量满足,可以看出该问题是一个较为复杂的组合优化问题.针对此类问题,用常规算法求解计算量较大且难以获取最优解[2],较适合用启发式进化算法来解决.

微分进化算法(Differential Evolution algorithm,DE)是一种模拟生物自然化过程搜索全局最优解的随机优化算法,是近年来最著名的进化算法之一[3,4].它具有简单,快速,鲁棒性好,易于实现,控制参数少且搜索能力强等特点,因此被广泛应用于各个领域,尤其是在处理复杂优化问题方面得到了广泛关注[5,6].

DE算法在求解连续变量的函数优化问题时能快速、稳定地收敛到全局最优解[7,8].本文主要研究基于单目标的DE算法在答辩分组中的应用.通过设计合适的染色体编码方式、适应度函数,然后基于DE的进化策略进行初始化种群、变异、交叉、修正等操作,对问题的解进行搜索.最后给出结果并与常规的求解方法进行对比.

1 问题建模分析

1.1 模型假设

为简化模型,对问题中的一些元素作以下约定:

(1)所有参加答辩的学生,按十进制序号升序排序,学生个体在建模中不作区分,认为完全一样.

(2)所有老师按十进制序号升序排序,不同老师个体之间需要区分.

(3)分组结果中每组的先后顺序没有特别要求,可以调换,不影响整体的效果.

(4)为了简便处理,每位老师指导学生人数相同,每一组分配老师学生人数分别相同.

同时约定以下符号:

m:老师总人数.

n:学生总人数.

p:每位老师指导学生人数.

g:分组总数.

s:分组结果中每组参加答辩学生人数.

t:分组结果中每组参加答辩老师人数.

B:分组矩阵,m*n.

C:检验矩阵,m*m.

num:检验矩阵C中不满足老师互回避情况的对数与零元素个数的总和.

为了简化处理,其中人数均为整数,而且有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.分组结果中每组的先后顺序不影响整体的效果.

证明:假设分组中每组的先后顺序影响分组效果,随意变换分组中的先后顺序,每组参与老师学生不变,通过计算变换顺序后的互回避指标,发现任意变化分组的先后顺序,互回避指标不变,评价整体效果的互回避指标与分组结果中每组的先后顺序无关,故与假设矛盾,因此分组结果中每组的先后顺序不影响整体的效果,证毕.

定理2.检验矩阵C可以来评估分组结果的优劣.

证明:由于老师指导学生矩阵A乘以分组矩阵B的转置矩阵是矩阵C,对于矩阵C(i,j),就是老师i指导的学生接受老师j面试的人数.C主对角线元素是0,说明分组结果必须满足老师自回避原则.关于主对角线对称位置的两元素同时不为零说明是满足互回避原则的,矩阵C中每列零元素越少说明学生分布的越均匀.num是检验矩阵C中关于主对角线对称的两元素同时不为零的对数加上每列零元素的个数的总和,可以反馈分组方案满足老师互回避原则的情况以及满足均匀原则的情况信息,因此,检验矩阵C可以评估分组结果的优劣,证毕.

通过例4进一步推导可知，若极限式中有幂指函数地f(x)g(x)，常用换底公式eg(x)lnf(x)将其化为指数函数进行处理。

1.4 答辩分组问题数学模型

根据以上的研究分析,建立答辩分组问题数学模型如下:

2 DE算法解决答辩分组问题

2.1 种群初始化

针对答辩分组问题,采用随机的0/1矩阵构造一个老师矩阵A(如图1)[11,12].矩阵的行属性定义为学生,列属性定义为老师,则矩阵的行数为m*n,列数为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

然后设置种群规模N=10,来构造10个染色体矩阵,即种群矩阵.该矩阵用于表现答辩分组后的结果,问题的最终目标是得到该矩阵的最优解.种群矩阵的行列属性与矩阵A相同,假设老师和学生数都可以被均匀的分到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 优劣个体的交叉策略

为增加干扰参数向量的多样性,经典DE中的交叉机制是:

对于基因j随机生成一个0～1的随机数,如果随机数小于CR那么就将变异后的个体v基因j给交叉后的个体ui,否则将变异前的i种群的j基因给变异后的种群个体ui,交叉后的个体为u.对于答辩分组问题采取行列交叉操作,即随机选取双亲中相对应的一行,将其互换得到两个新的子代个体[4,5].

但是,在标准进化算法的进化后期,当大多数个体聚集在局部最优解时,种群多样性减少,种群不能通过变异和交叉操作产生新的更优个体.为增加种群多样性,加大探索空间,依据前期研究成果[6,7],这里采用一种基于优劣个体交叉策略.该方案中优劣交叉具体是指,在目标向量(父代向量)和变异向量中调整出部分优秀和劣质个体之间完成,其中包括优劣交叉和优优交叉,若种群多样性指标非常小,即大部分个体过度聚集,采用优劣个体间交叉可提高种群多样性;否则,采用优优个体间交叉提高种群的探索能力.

用种群多样性指标η来判断采用哪种交叉策略.该指标受种群中个体之间的距离和适应度值的影响.为计算个体间的距离,首先介绍基因的多样性程度

从个体之间距离的角度计算多样性,用每五个个体(种群大小为100)中随机选择一个作为参照来计算种群多样性程度,然后使用20个值得到均值为最终的多样性程度值ξ.从上面公式(5)中可以知道,ξ的值在(0,1)之间.

另一方面,从适应度值φ来测量种群多样性:

在公式(6)中用φ来表示多样性.σf表示种群个体适应度值的标准偏差,fworst和fbest分别表示种群中最优的和最差的个体适应度值.显然,φ的值也在0和1之间.

结合ξ和φ来计算种群多样性,并在公式(7)中使用η为最终参数表示.

η的值在0到1之间变化,根据ξ和φ,可判断应该使用哪种交叉策略.如果η<ε,即当前种群多样性小于容忍度ε,执行优劣交叉以增加种群多样性.否则,当η≥ε,执行优优交叉来提高种群的探索性.基于我们前期的工作,仿真实验将ε=ε1=0.05作为经验值,更多关于优劣交叉相关参见文献[6,8],在此不再赘述.

2.4 选择操作

选择的后的是要对个体进行适应度函数评价,以此来决定是否在下一代中用候选个体替换当前目标个体.其对应法则如下:

适应度函数是选择下一代种群的一个重要依据,用来评估种群优劣的一个指标,有的适应度函数评价值越大表示个体越优秀,有的则是越小越优秀,要根据具体情况而定,DE算法主要以适应度函数来指导搜索策略.假设适应度最小的为最优解,那么当变异交叉后的U种群的个体适应度比初始种群的适应度小的时候,就将U种群选取为第G+1;反之,则将原来的第G代个体选取为第G+1代[9,10].

2.5 适应度计算

对于答辩分组问题,要求的最优解应当满足每个老师的学生尽可能的分布在多个答辩老师中同时尽量避免两个老师相互面试对方学生的情况,使用检验矩阵C(见公式1)来反馈分组方案中满足老师互回避原则的情况信息(定理2).适应度计算依据定理2中的num的值.

用图1中的矩阵A和图2中的矩阵B代入定义3得到检验矩阵C(如图3).从图3中可以看出,矩阵C主对角线的元素全部为零,说明满足自回避原则,关于主对角线对称的两元素同时不为零的对数为6,矩阵中的非零元素个数为18,因此该分组方案的适应度num为24.

图3 检验矩阵C

2.6 修正操作

在对种群始化,或者变异和交叉时,可能会产生不合法的个体,比如产生了与矩阵A相同行列位置同为1的情况(不满足自回避原则),或者矩阵中某个数变成小数,此时就要把不合法个体修正为合法的染色体.

修正过程既是对个体进行限制条件的验证过程,使得个体中的值为0或1,而且行满足限制条件,列满足限制条件

2.7 总体流程

使用DE求解答辩分组问题步骤如下:

(1)生成初始种群,种群中包含10个体,进化代数G=0.

(2)修正操作,对随机生成的个体依据限制条件进行修正.

(3)开始进化,对种群中每个个体进行交叉,变异和选择操作,得到新一代的个体.

(4)判断是否满足终止进化条件,即是否进化迭代次数达到50代,若不满足则进化到下一代,继续执行(3)中的交叉变异等操作.如果满足终止条件,则停止搜索,算法结束并输出结果.

图4是DE算法流程图,图中G表示代数,NP表示种群大小.

图4 算法总体流程图

3 一般算法解决答辩分组问题

为了与DE算法求解答辩分组问题做对比,给出一般方法的求解过程.一般算法即用常规的程序设计方法,在设计过程中应考虑参数的限制,死循环的处理等问题,用数组和循环来求解该问题.确定已知参数m个老师,n个学生,共分成g组,每组老师个数为m/g,每组学生个数为n/g,根据已知老师进行答辩组分组.

(1)选择老师

随机生成1～m个数的随机排列,每次顺序取两个作为每答辩组的答辩老师,这种老师与老师的组合是随机的,共可以选择g次.

(2)选择学生

逐一遍历每个老师,每次从老师指导的学生中选一名学生进入答辩组,直到选够n/g个为止,这样才能近可能满足均匀原则.迭代到某个老师时,首先将该老师与本组中已分配的答辩老师进行对比,如果没有相同结果,再从该老师的学生中进行选择(遵循自回避原则).

(3)死锁处理

迭代过程中,可能会出现排除自答辩老师组学生,其它学生已全被选取的情况,此时会产生死锁,出现这种情况需要重新进行分组.设置运行次数Runtime,如果死锁就重新开始分组,最多运行10次.算法流程如图5所示.

(4)适应度

为了检验分配方案的均匀性和互回避性,需要计算分配结果的适应度,这里定义适应度由两个指标组成,一个是分配结果中每个答辩组里属于同一个老师的学生个数;另一个是老师互相答辩对方学生的对数,最终适应度等于这两个值之和.

图5 一般算法流程图

4 算法实验测试结果

对于以上两种算法,分别用两组数据测试算法的优劣.程序中用T1,T2,……Tm来表示老师的编号,用T1_1,T1_2,……T1_n来表示同属于T1老师指导的学生编号,依此类推,Tm_n则表示由Tm老师指导的第n个学生.第一组数据:m=6,n=12,g=3,对应的老师指导学生信息如表1.

第二组数据:m=8,n=32,g=4,对应的老师指导学生信息如表2.

表1 6名老师指导12名学生的信息

表2 8名老师指导32名学生的信息

4.1 DE算法测试结果

用DE算法运行第一组数据,初始种群包含10个个体,进化代数为50代,运行结果显示了答辩分组矩阵B对应的10个个体,均为12×6的矩阵,由于篇幅所限,不再一一展开.运行结束后,种群中个体最小的适应度值是20,图6给出了DE算法进化的曲线.在末代种群中,个体1,5,8的适应度均为20,即是理想的答辩分组结果,表3,表4,表5分别给出了他们的分配方案.

图6 DE运行第1组数据进化曲线

表3 个体1对应的分组方案

表4 个体5对应的分组方案

表5 个体8对应的分组方案

从上述三个分组方案中可以看出,DE算法得出的解决方案呈现了多样化的特征.

运行第二组数据,仍然设定初始种群包含10个个体,进化50代,输出10个32×8的矩阵,以此表示答辩分组结果,同时输出这10个分组方案对应的适应度.进化曲线如图7所示,图中显示种群中适应度最小为28,也就是最理想的答辩分组结果.运行结束后,种群中个体1、2的适应度都是28,即他们两种分配方案有同样的适应度,都可以供使用者选择.

图7 DE运行第2组数据进化曲线

个体1和2对应的分组方案如表6和表7所示.

表6 个体1对应的分组方案

表7 个体2对应的分组方案

4.2 一般算法测试结果

一般算法运行一次只能得到一个解,运行第1组数据结果如表8所示,这个结果的适应度为12.

表8 一般算法运行第1组数据的结果

用一般算法运行第2组数据,结果如表9所示,适应度为24.

表9 一般算法运行第2组数据的结果

一般算法在运行数据时,有时会发生死锁的情况,如表10所示,在完成3组分配后,进行第4组分配时遇到了排除自答辩老师没有学生可分配的情况.此时,需要重新运行程序进行分组.

表10 一般算法运行第2组数据时遇到死锁的情况

根据实验结果,死锁发生的概率与测试数据的规模成正比,测试第1组数据(m=6,n=12,g=3)时,程序运行30次,发生死锁的次数为0.测试第2组数据(m=8,n=32,g=4)时,程序运行10次,发生了9次死锁,死锁概率为90%;运行20次时,发生了15次死锁,死锁概率为75%;运行30次,发生了20次死锁,死锁概率为67%.由此可以推断,随着一般算法运行次数增多,死锁的概率会逐渐下降,但是想得到多个分组方案的话,程序至少要运行十次以上.由此可见,一般算法在问题规模较小的情况下输出可行解是快速、高效的,但输出的解不具有进化过程.当问题规模稍大时,输出无效解的概率过大,算法效率明显降低.

5 结果分析

从测试结果来看,两种算法都能解决答辩分组问题,并且都能满足自回避原则,对于互回避原则和均匀原则都能尽量满足.但一般算法运行一次只能得到一个解,只有运行多次才能得到多个解,且这些解不具有进化的过程,不能从所有可能的解当中寻得最优值,在实际应用中难以为决策者提供更全面可行的方案.而DE算法运行一次能得到多个最优解,且这些解是经过N代进化选择的结果.因此,单目标微分进化算法所具备的进化过程使最优解能从众多的备选方案中快速显现,表现出较好的优越性.

由于篇幅所限,只用了两组数据测试,当每增加一位老师时会增加更多的学生,如果学生足够多就能完全满足自回避和互回避条件,但m,n具体增加到多少才能满足条件,还留待以后进行深入探究.

1 李剑,朱延峰,吴畏.学生面试问题的分配策略.数学的实践与认识,2007,37(14):153–160.[doi:10.3969/j.issn.1000-0984.2007.14.020]

2 司守奎,孙玺菁.数学建模算法与应用.北京:国防工业出版社,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 许玉龙,方建安,赵灵东,等.微分进化求解无线传感器网络中的覆盖问题.计算机工程与设计,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 战红,杨建军.基于工序矩阵编码遗传算法的车间作业调度优化.制造业自动化,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

曹莉,许玉龙,李亚威.单目标优劣交叉的微分进化解决答辩分组问题.计算机系统应用,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年河南中医学院博士基金(2015BSJJ-19);2017年河南省科技攻关研究项后(172102210361,172102310536)

2016-12-26;采用时间:2017-01-23