基于樽海鞘群优化差分进化算法的实验室预约模型

张 慧,王麒翔,侯小毛,闫喜红

(太原师范学院 1.教务部;2.数学与统计学院,山西 晋中,030619; 3.山西大学 环境与资源学院,山西 太原,030006;4.湖南大学 信息科学与工程学院,湖南 长沙,410151)

实验室资源及设备的高效利用是学校实验室管理水平的重要体现。近年来,关于实验室开放管理及实验设备的全天候使用成为实验室管理的研究热点,通过对实验室开放及学生的预约来实现实验设备的高效应用。在实验室预约研究中,传统方式是由实验室上传实验设备开放时间供预约者竞争预约,先预约先得的模式[1],这种预约方式实现了实验室预约的功能,但其在实验项目满足度和实验设备受益面来看并不高。在实验预约过程中,除了将实验设备分配给预约者,还需要策略地干预,保证学生专业与所预约实验的匹配度[2],以及学生对预约实验的信誉值。

当前的实验室预约研究中,大多是提前收齐学生的预约需求,再结合实验室开放时间、实验设备使用时间、实验项目的专业权重等数据,从中提取特征构建实验室预约优化的样本数据,然后采用智能算法进行预约方案寻优。

作为一种智能算法,差分进化算法具有比贪婪算法、最优预约规则算法更高的非确定性多项式求解能力,求解的效率更高。因此,本文尝试引入差分进化算法用于实验室预约方案生成。然而,传统差分进化算法存在容易陷入局部极小值的问题,因此无法有效适应不规模的预约方案生成。采用樽海鞘群算法(Salp swarm algorithm,SSA)对差分进化(Differential evolution,DE)算法进行参数优化,提出了一种SSA-DE算法,增强了差分进化算法的预约方案求解性能,提升了实验项目满足度和实验设备的受益面指标值。

因此,本文尝试引入差分进化算法用于实验室预约方案生成。采用樽海鞘群算法(Salp swarm algorithm,SSA)对差分进化算法(Differential evolution,DE)进行参数优化,提出了一种SSA-DE算法,增强了差分进化算法的预约方案求解性能,提升了实验项目满足度和实验设备的受益面指标值。

1 实验室预约数学模型

实验室预约主要是解决设备、时间及预约者的协调调度问题,从实验室预约角度来看,结合多篇文献[5,6],提取了影响实验室预约程度较大的6个因素,具体见表1。

表1 实验室预约影响因素

从6个因素里面选择合适的解,来满足实验室预约,这6个因素之间内部存在着相互制约的关系,如同时段内只能预约一个实验室,且教师只能指导一门课,一台设备只能一个预约者使用,同类型的设备使用率尽量均衡。设备的连续使用时间等,在这些约束条件下,要从6个维度中选择优秀解并不容易,因此采用智能算法求解6个解空间是明智选择。

在实验室预约过程中,除了以上的硬性条件限制之外,还有很多软性条件。实验室预约过程中,有可能造成临近上课,学生未上课且未取消预约的情况,这就造成了实验设备利用率不高的情况。因此,学生信誉值也是预约需要考量的点,而且考虑到各专业需求。实验项目的权重也存在着差异,如何在预约过程中将学生的专业与项目做权重限定,对实验室真正全面预约发展有着重要意义。因此项目权重和预约者信誉等因素将纳入到表1中的D和E特征中。

在实验室预约建模过程中,可以考虑从需求满足度和受益面两个目标去进行解空间的智能寻优。设第i个实验项目的实验人数为pi和限定人数为vi,第i个实验项目的总设备数量和教师要求达成度分别为mi和ti,第j个预约者的信誉值为cj,第i个实验对第j个预约者的专业权重为aij,则第i个实验项目的满足度为

zi=(pi-vi)×aij×ti×cj

(1)

第i个实验项目的受益面指标为

wi=w0+vi×aij×ti×cj

(2)

式中:w0=0,vi≤mi。

实验室预约的模型建立就是采用最小的代价达到项目满足度要求和扩大受益面。

2 差分进化算法的改进

2.1 差分进化算法

假设DE算法的群体规模为N,单个体的维度为D,F为差分缩放因子,F∈[0,2],差分交叉速率CR,个体运动范围[Umin,Umax],其中个体i的j维特征是[7]

xij=Umin+rand×(Umax-Umin)

(3)

式中:i=1,2,…,N,j=1,2,…,D,rand∈(0,1)随机数。

(4)

式中:r1、r2和r3为第G代生成的个体,满足条件i≠r1≠r2≠r3。

个体交叉操作满足式(5)[9]

(5)

(6)

式中:f为适应度函数。

不断进化,输出最优适应度个体,直至达到停止条件。在DE求解过程中,F和CR参数对DE的求解性能影响较大,特别是F值,实际操作时一般靠经验设置,或者采用动态调整策略设定F,动态调整方式为[11]

(7)

式中:Fmin=0,Fmax=2。

2.2 樽海鞘群算法

设D为空间维数,N为樽海鞘群规模,SSA算法的领队位置更新方法为[12]

(8)

(9)

式中:l表示当前迭代次数,L表示最大迭代次数。

追随者位置更新[15]

(10)

式中:v0是速度初值

(11)

(12)

令t=1,v0=0,则式(10)变为[16]

(13)

对比Fd与X的适应度,保存较大者为樽海鞘群算法优化结果。

2.3 基于SSA-DE的实验室预约流程

在DE算法的实验室预约方案求解中,差分缩放因子F的设定不再采用式(7)的自适应策略,而是采用樽海鞘群算法来对F值进行优化,根据优化结构得到的F值来进行DE预约训练。

在SSA-DE运算过程中,首先需要获得实验室设备、实验时间、预约者的实验申请记录等样本特征,并将这些特征进行初始化后构建差分进化个体,以实验项目的满足度为适应度,然后执行SSA-DE算法的预约方案生成策略,具体流程如图1所示。

图1 基于SSA-DE的实验室预约流程

3 实例仿真

基于樽海鞘优化的差分进化实验室预约实例仿真从3个不同层面进行仿真,仿真数据集来自于某大学实验中心,选取了一个月的实验室预约情况进行仿真,实验人员不超过200人,实验设备申请记录共800条,每个实验室包含一种设备,具体实验设备样本如表2所示。首先,差异化设置预约人员规模,验证不同规模数据下的预约性能;其次分别采用DE算法和SSA-DE算法进行实验室预约性能仿真,验证SSA算法对DE实验室预约的性能影响。

表2 实验室设备样本

3.1 不同数量规模的预约仿真

差异化设置实验室设备数量及预约人员数量,验证SSA-DE算法对不同预约规模下的预约性能适应度。

图2展示了SSA-DE算法用于实验室4种实验设备的预约的空间解结果,从图看出,不同预约人数规模下的SSA-DE算法获得的预约方案结果分层明显,当预约人数为50人时,3D打印机、激光雕刻机、数控车床和普通车床的预约方案结果分别为46、25、23和37种;当预约人数为100人,4类设备的预约方案结果分别为27、15、12和19种;预约人数为150人时,4类设备的预约结果分别为21、10、8和12种;预约人数为200人时,4类设备的预约结果分别为16、3、3和9种,这表明随着预约对象的增多,在实验设备数量不变的情况下,SSA-DE算法生成的预约方案结果数量下降明显。而在预约人数相等的情况下,SSA-DE算法在4种设备生成的预约结果数量也存在着较大差异,其中3D打印机设备的预约方案最多,普通车床次之,数控车床最少。

图2 不同预约规模下的SSA-DE预约解

结合设备疲劳度、均衡度、学生信誉值和专业权重等因素,对于各生成的预约方案进行评价,以从候选方案中选择最佳实验方案。

从图3(a)可以看出,在预约人数为50时,虽然4种设备的预约解数量差异较大,但是在这些预约解集合中,均能找到受益面指标较大的预约解,4类设备的最优受益面指标值均在9.5以上;而在预约人数为100时,设备1的最优受益面指标值约为9.8,略高于其他3种设备的最优值;在预约人数为150和200时,设备2和设备3的预约解数量锐减,但是在其少量的预约解集合中,仍能找到受益值大于9.2的预约解,而设备1和设备4均能获得9.6以上的受益面指标所对应的最优解。这说明虽然预约解数量会随着预约者规模的上升而下降,但是SSA-DE算法仍能找到受益面较高的预约解,在实际应用时,只需要获得一个最优解即可,因此SSA-DE算法在应对不同预约者规模时,仍表现出了较高的实验室预约性能。

图3 不同预约规模不同预约解的受益面指标

3.2 SSA对DE算法的预约性能影响

分别采用DE算法和SSA-DE算法进行预约仿真,验证2种算法在不同预约者规模下的预约解数量和受益面指标。

从表3可以看出,在相同预约者规模下,DE算法所生成的实验室预约解方案数量远小于SSA-DE算法,尤其是在预约者人数为200时,对于设备2和设备3,DE算法仅能提供1种预约方案。这说明经过SSA优化后,DE算法对于实验室预约方案求解的能力提升了,生成的预约解集合越大,越能够获得更优的预约方案。

从表4可知,通过求解DE算法和SSA-DE算法所寻找的预约解受益面指标值,获得了2种算法预约解的最大受益面指标值,在预约者规模数量为50人时,两者的最大受益面指标值比较接近,均在0.92以上,而当预约者规模数量增加,DE算法的受益面指标下降明显,而SSA-DE算法仅略微下降,在预约者规模数量为200人时,两者的最大受益面指标值差距达到了1.0,这说明经过SSA优化之后,其预约解的受益面指标性能得到了较大提升,从而提升了DE算法的实验室预约求解质量。

表3 DE和SSA-DE的预约解数量

表4 DE和SSA-DE的受益面最大值

4 结束语

本文通过对实验室开放时间、预约者预约记录和实验设备等特征提取,采用动态差分进化算法对特征样本进行训练,并采用樽海鞘群算法对动态差分算法关键参数进行优化求解,最后生成了受益面指标较高的预约分配方案。所提模型可以根据输入的约束条件自动进行生成最优的预约方案,有助于大幅提升高校实验室的管理效率。后续研究将进一步从动态差分进化算法的优化角度展开研究,考虑用更多的智能算法进行改进,以进一步提高动态差分进化算法的实验室预约性能。