化验室资源调度优化的改进型克隆选择算法

顾伟伟, 张栋良

(上海电力大学 自动化工程学院, 上海 200090)

化验室调度的目的是将待化验的化验单及样品分配到合适的设备,以此来提高共享资源的利用率,使得整个流程更加高效。化验室资源调度问题本质上是一个组合优化[1]问题,针对原先的动态规划法[2],其处理大规模复杂优化问题时存在不足,建模较为复杂,计算速度也较慢。目前智能算法如神经网络[3]、遗传算法[4]、模拟退火[5]等在调度问题上的应用越来越广泛。近年来,研究人员提出了各种优化算法[6-14]以解决调度问题。高阳阳等人[15]在克隆选择算法中设计了新的移民算子进行多种群交流,提高了搜索效率;宋丹等人[16]将克隆选择算法与模糊非基因信息搜索策略相结合,改善了算法搜索能力及算法精度;周炳海和顾佳颖[17]在免疫克隆选择算法中引入了新的邻域搜索算子和种群更新算子,提高了算法的搜索效率。

传统的克隆选择算法与其他智能算法一样,容易陷入局部最优、早熟收敛等问题。本文在克隆选择算法的基础上,引入了多种群协同进化的思想,以提高种群的多样性;设计了新的克隆选择算子,增加了个体的多样性;提出了自适应变异算子,能加快局部搜索速度,提升全局搜索能力。

1 化验室调度数学模型

化验室处理化验单的问题可表述为:有j个化验单(一个化验单可含多种样品)在某一台设备上化验检测,已知各类样品的化验时间和各样品在各设备上化验检测的次序约束,合理地安排样品所使用的设备以及化验单检测顺序,可使化验检测流程效率达到最优。为建立化验室调度模型,作如下假设。

(1) 某一时刻在每台设备上都只能对某个化验单的某个样品进行化验且是非抢占的,允许有设备空闲。

(2) 不同化验单的样品可以同时在不同的设备上化验。

(3) 一台设备不能同时化验两个样品。

(4) 化验单的优先级是相同的。

目标函数化验完成最小时间Tm为

(1)

式中:Zjt——二进制量;

t——化验单化验完成时间。

Zjt取值为1,反之为0,其中化验单数量j和时间t的取值范围j=1,2,3,…,J,t=1,2,3,…,T。

约束条件如下:

(2)tcjh≤tsj(h+1)为样品的化验顺序约束,表示第h个样品的化验完成时间小于第h+1个样品的化验开始时间。其中:tcjh为第j个化验单的第h个样品的化验完成时间;tsjh为第j个化验单的第h个样品的化验开始时间。

(3)tcjh≤Tm表示一个化验单的化验时间总小于整个化验流程所花费的时间。

(4)tcjh=tsjh+pijh表示样品在一台设备上化验过程中不会被中断。其中,Pijh为第j个化验单的第h个样品在机器i上的化验时间。

2 改进型克隆选择算法

2.1 具体步骤和流程

免疫算法通过模拟生物免疫原理,将实际求解问题当作抗原,结合基因进化机理,是一种鲁棒性好、搜索能力强的新型智能算法。它具有一般免疫系统的特征,采用群体搜索策略,通过迭代计算,最终以较大概率得到问题的最优解。标准免疫算法在计算迭代过程中也容易陷入局部最优解及早熟收敛等不足。本文在标准免疫算法的基础上提出了改进型克隆选择算法,引入多种群协同进化思想,提高了种群的多样性;引入克隆选择算子和自适应变异算子,提高了算法的搜索效率,加快了算法的收敛速度。算法的具体步骤如下。

步骤1 识别待优化的目标函数。

步骤2 随机生成初始抗体群P,初始抗体群由n个子群体Pn构成,确定初始参数。

步骤3 计算各抗体群中抗体适应度F及浓度C,基于亲和度A排序,选择优质抗体放入记忆库中。

步骤4 计算每个抗体期望的繁殖概率Pr,根据繁殖概率对抗体进行选择克隆操作。

步骤5 对不同种群中的抗体进行移民操作,前一个种群的劣质抗体由后一个种群中的优质抗体取代。

步骤6 从已更新后的抗体中,将M个亲和度高的解保留下来,组成记忆库。

步骤7 终止条件判断,满足就结束,不满足则跳转到步骤3。

改进型克隆选择算法流程如图1所示。

2.2 编码及初始抗体群

以随机的方式生成初始抗体群。初始抗体群由n个子群体构成。在初始抗体子群中,根据化验设备数量、样品数量来限制生成抗体的取值范围。采用单层实数编码表示各解,各抗体表示对化验单合理分配设备与辅助资源以及确定化验单样品化验顺序的调度方案。 设置初始参数如下:最大迭代数为Gmax,种群数为Npop,交叉概率为θc,变异概率为θm等。

图1 改进型克隆选择算法

2.3 抗体评价

亲和度是指分配方案与目标函数的匹配程度,可作为评估每一个可行解的衡量指标。亲和度越大,表示抗体适应度越高,抗体浓度越低。其中,抗体与抗原之间的匹配程度由适应度表示,抗体与抗体间的相似程度由浓度表示。其计算公式分别为

(2)

(3)

(4)

式中:fi——抗体与抗原间的适应度;

ti——各个抗体的完成时间;

Ci——抗体i的浓度;

N——抗体数量;

j——除了抗体i之外的抗体;

nj——抗体j的数量;

Si,j——群体中抗体i和抗体j的相似程度;

Ki,j——抗体i和抗体j中基因编码相同的位数;

L——抗体的长度。

若Ki,j/L≤0.6,则表示两个抗体没有相似性,取Si,j=0;反之,则表示两个抗体具有相似性,取Si,j=1。

2.4 克隆竞争扩增

根据亲和度大小筛选出种群中的优势抗体,将其放入记忆库,并对其进行概率克隆。抗体选择克隆的策略主要由抗体适应度和浓度决定。本文在此基础上提出了抗体克隆选择算子,尽可能选择适应度大的抗体来保证潜力较大的抗体得以繁殖,选择浓度低的抗体来扩大搜索空间。选择概率公式为

(5)

式中:Pcs(i)——第i个抗体的期望选择概率;

λ——多样性评价指数,每个子抗体群都会获得一个随机生成的λ,取值范围为[0.3,0.7]。

2.5 自适应变异

根据自适应变异算子对克隆合并后的抗体群进行变异操作,降低部分适应度小于平均适应度的抗体变异概率,提高部分适应度高于平均水平的抗体变异概率,以此来获得具有高潜力的优质抗体,从而加快算法收敛速度。

(6)

式中:P′v——变异自适应概率;

Pv——原来的自适应概率;

f′——进行变异操作的抗体适应度;

fmax——适应度最大值;

favg——适应度平均值。

2.6 移民操作

首先确定n(n为自然数)个初始种群,通过移民算子实现优质抗体传递,计算每个抗体的亲和度,将第n个种群的优质抗体替换掉第n+1个种群的劣质抗体。

2.7 种群重组及记忆库更新

将未进行变异操作的原抗体与已变异的抗体合并重组得到抗体群。比较种群中两代抗体的适应度大小,由优质抗体替换掉劣质抗体,完成记忆库更新。

2.8 算法终止判断

若迭代次数达到上限,则终止算法,输出最优解。

3 仿真实验与分析

为了测试改进型克隆选择算法的性能,选择3个基准测试函数进行了仿真测试。仿真实验在MATLAB 2017a上进行,运行环境为Windows 10系统下Intel(R) Core(TM) i5-3230M处理器,8 G内存,2.6 GHz。最后与文献[8]中的混合免疫算法和文献[15]中的非支配克隆选择算法以及标准免疫算法进行了对比实验与分析。

由于寻优结果具有一定的随机性,也为了测试的公平和客观,所以每种算法独立运行30次,并取平均值作为分析的依据。

3.1 Griewank函数

(7)

Griewank函数具有大量的局部极小值且为均匀规则分布,在点xi=(0,0,…,0)处取得全局最小值为零。在高维情况下全局最优解的搜索容易陷入局部最优中,故变异率Pm设置不能过小,否则无法保证群体的多样性,而且会使找到峰值的概率降低。算法参数设置如下:免疫个体数目NP=100,最大免疫代数G=200,变异率Pm=0.7,激励度系数β=1.5,相似度阈值Δ=0.2,反馈因子r=0.6。

图2为函数F1的收敛曲线。表1为Griewank函数的仿真结果。

图2 函数F1的收敛曲线

表1 Griewank函数的仿真结果

由图2可以看出,改进型克隆选择算法的收敛速度优于另外3种算法,收敛的最优值也较为接近理论最优值。结合表1数据可知,改进型克隆选择算法具有较高的求解精度,高维数时改进型克隆选择算法寻优性能相对于标准免疫算法已有较大提升,平均质量稍高于其他算法。

3.2 Rastrigin函数

(8)

Rastrigin函数是一个多维多峰函数,在点xi=(0,0,…,0)处取得全局最小值为零,局部极小值比Griewank函数更为集中,通常被用来测试算法的脱困能力。激励度系数的选取不宜过大,优秀抗体容易被过早抑制,导致收敛速度过快,无法脱困。算法参数设置如下:免疫个体数目NP=100,最大免疫代数G=200,变异率Pm=0.6,激励度系数β=0.9,相似度阈值Δ=0.25,反馈因子r=0.5。

图3为函数F2的收敛曲线。表2为Rastrigin函数的仿真结果。

由图3可看出,标准免疫算法在高维Rastrigin函数中易陷入局部最优。表2仿真结果显示,改进型克隆选择算法在精度上有较大提升,表现出较好的全局收敛能力。

图3 函数F2收敛曲线

表2 Rastrigin函数的仿真结果

3.3 Resonbrock函数

(9)

Resonbrock函数是一个多维病态二次单峰函数,在抛物线顶点xi=(1,1,…,1)处取得全局最小值为零,空间内走势平缓,收敛到全局最优难度较大。反馈因子r取较小值时,会导致多种群间信息交流过于激烈,使得收敛速度过快,无法找到最优解。算法参数设置如下:免疫个体数目NP=100,最大免疫代数G=200,变异率Pm=0.6,激励度系数β=0.9,相似度阈值Δ=0.25,反馈因子r=0.3。

图4为函数F3的收敛曲线。表3为Resonbrock函数的仿真结果。

图4 函数F3的收敛曲线

表3 Resonbrock函数的仿真结果

由图4可以看出,本文算法收敛速度优于改进的混合免疫算法,低于改进型非支配克隆选择算法,寻优精度略高于改进的混合免疫算法和标准免疫算法。

图5为化验室高度仿真甘特图。仿真过程中,共采用10个化验单,每个化验单有9个样品,在化验室有10台设备的情况下得到的全局最优解。图5中标识83的长方形表示第8个化验单的第3个样品在6#设备上化验。利用本文算法仿真得出的化验完成时间最小的最优解为1 063 min,所有化验单化验完毕。

图5 化验室调度仿真甘特图

4种算法的仿真结果比较如表4所示。

表4 4种算法的仿真结果比较

由表4可以看出:本文算法的平均计算时间最短,为28 s,具有较高的搜索质量;改进型混合免疫算法的平均计算时间次之,为32 s;标准免疫算法平均计算时间最慢,为45 s。此外,本文算法的平均迭代次数为72次,改进型混合免疫算法的平均迭代次数为101次,改进型非支配克隆选择算法的平均迭代次数为123次,表明本文算法的收敛速度在4种算法中具有一定优越性,能在算法运行的较早期收敛,证明了本文算法的可行性和可靠性。

4 结 语

针对化验室调度资源优化问题,提出了一种改进型克隆选择算法。该算法的特点在于:将多种群协同进化的思想引入免疫算法,能有效克服种群多样性下降的问题;为了增加个体多样性,提出了克隆选择算子,优先选择亲和度大、浓度低的抗体进行克隆操作;提出了自适应变异算子,能加快局部搜索速度,避免算法陷入局部最优。

采用改进型克隆选择算法对化验室调度策略进行了优化,并在MATLAB上进行了仿真实验。结果表明,与其他算法相比,本文所提算法表现最优,具有较高的收敛精度和良好的稳定性,证明了算法的可行性和有效性。