基于改进Slime Mold算法的多处理器公平调度
基于改进Slime Mold算法的多处理器公平调度
戴曼丽†和蒋忠义，†
常州大学计算机科学与人工智能学院，常州213164
通信地址应为的作者。
†
这些作者对这项工作做出了同样的贡献。
算法2023，16（10），473；https://doi.org/10.3390/a16100473（注册DOI）
接收日期：2023年9月25日/修订日期：2023.10月4日/接受日期：2024.10月7日
（本文属于《可持续制造的特刊调度理论与算
法》）
1.多处理器系统广泛应用于各种领域，包括医疗系统、智能手机、航空航天和[1]。随着当今社会对高性能、低功耗需求的不断增加，多处理器系统的使用在[2]上得到了极大的推广，导致了对多处理器任务调度问题的广泛研究。本文研究了多处理器上的公平调度问题，旨在在执行多个独立的非抢占任务时，实现跨处理器的平衡平均处理时间。这个问题的动机来自于一个工厂场景，即人们希望通过平衡每辆车的平均里程来将任务分配给运输车辆。该模型也适用于出租车的公平调度问题，确保每辆出租车送货的平均距离相同。日程安排中的公平性问题最初是由Fagin和威廉姆斯·[3]提出的，他们将其抽象为他们研究中的拼车问题。随后，在在线马赫的背景下开始出现公平调度问题
他把它抽象为他们研究中的拼车问题。随后，在在线机器调度的环境中开始出现公平性调度问题。调度问题的目标是最小化机器处理时间的最大和。近年来，人们越来越关注调度中的公平性，特别是在最优实时多处理器调度算法[4]的背景下。关于比例公平调度的研究长期以来一直在操作系统、计算机网络和实时系统[5]等领域进行。比例公平的调度策略主要是基于保持比例的概念
所有任务中的进度率为[6]。由于其平衡系统吞吐量和公平性的能力，比例公平性调度在实践[7]中得到了广泛的应用。确保资源的公平分配会显著影响调度算法的性能。在各种公平调度算法迅速出现的同时，对多处理器公平调度的研究相对有限。已经确定了处理器的作业调度问题是np困难的，保证调度的公平性可以在一定程度上提高处理器资源的利用率。公平性调度问题的典型目标通常是最小化机器上的最大总处理时间。然而，本文将公平性调度目标设置为最小化每个处理器上的平均执行时间。以最大平均处理时间为目标的调度问题可以应用于出租车和快递调度等任务，这些任务需要在短时间内处理大量的调度任务，需要高效、处理时间短的算法。公平的德国
群体智能算法的灵感主要来自于自然环境中生物体的进化以及种群[8]的狩猎、觅食和生存过程。一些常见的群智能算法包括粒子群优化（PSO）[9]、鲸鱼优化算法（WOA）[10]、麻雀搜索算法（SSA）[11]、蝴蝶优化算法（BOA）[12]等。这些群体智能算法已被广泛研究和应用于多个领域，如光伏最大功率点跟踪[13]、多目标优化问题[14]和COVID-19感染预测[15]。他们在解决特定领域的问题方面表现出了良好的表现。Li等人[16]于2020年引入了一种新开发的元启发式算法（SMA），模拟了黏菌在自然觅食过程中的行为和形态变化。与其他智能优化算法相比，黏模算法具有原理简单、调整参数少、优化能力强、易于实现等优点。
黏模算法已成功地应用于许多领域，特别是在工程优化领域。[14]等人提出了一种基于精英非支配排名的多目标黏菌模具算法。他们将黏液模算法应用于求解多目标优化问题，并证明了该算法在求解复杂的多目标问题上是有效的。Gong等[17]提出了一种基于状态自适应黏模模型和分数阶蚂蚁系统（SSMFAS）的混合算法来解决旅行推销问题（TSP）。实验结果表明，该算法在TSP实例上具有更好的竞争力。通过整合混沌映射和不同的演化策略进行整体优化，Chen等人，[18]设计了一种增强的黏菌模具算法，并将其应用于工程优化问题。由Abdel-Basset等人组成的[19]公司将鲸鱼优化算法和黏液模算法相结合，解决了胸部x射线图像分离问题。Gush等[20]利用黏模算法优化光电最优智能逆变器控制系统
本文提出了一种改进的黏模算法来研究多处理器和多任务处理的公平调度问题。通过对黏模算法的深入研究，发现仍存在一定的局限性。例如，种群多样性不够丰富，收敛速度较慢，很容易陷入局部最优解。在SMA的标准迭代过程中，黏菌群的随机初始化降低了种群多样性的潜力。当解决人口收敛到局部最优的问题时，它也缺乏有效的解决方案。标准SMA中的固定边界检查策略使得当黏液模具超过边界时，很难返回到较好的位置。本文对标准黏模算法进行了多策略改进。
本文的主要贡献如下：1。引入了一种基于伯努利混沌映射的反向学习初始化种群策略来增加种群的多样性。 2.柯西突变的引入帮助黏菌种群跳出局部最优解决方案。 3.引入了一种非线性动态边界改进策略，以提高种群的收敛速度。 4.将IMSMA应用于解决多处理器上的公平调度问题，以最小化每个处理器上的平均处理时间。
本文章的组织结构如下。第一节介绍了公平调度问题和黏模算法的研究。第2节描述了一些关于公平日程安排的相关文献。传统的黏液模子算法见第3节。第4节提供了改进的黏液模算法（IMSMA）的详细改进策略。模拟试验方法见第5节。第6节对多处理器上的公平调度问题进行建模，并应用IMSMA进行解决。第7节提供了在多个处理器上进行公平调度的数值实验。结论见第8节。
2.保证资源公平分配的相关工作对调度算法的有效性有显著的影响。在调度问题的领域中，公平性可以用多种方式来定义。有大量的文献致力于定义公平概念和设计具有公平约束[21]的有效算法。Zhong等[22]解决了多云工作流任务的公平调度问题，并提出了一种基于强化学习的算法。针对片上多处理器中的缓存竞争问题，Xiao等人[23]提出了一种考虑公平性的线程协同调度技术。它是基于非合作博弈论。他们希望确保公平的线程调度，以提高整个系统的性能。在具有多核的异构处理器上，Salami等人[24]提出了一个节能的框架来解决公平感知的时间表。该框架同时解决了多核处理器中的公平性和效率问题。对于多过程环境，Mohtasham等人[25]开发了一种公平的资源分配方法
3.标准黏菌模具算法（SMA）受多头天鹅绒真菌的觅食行为启发，建立了相应的数学模型。有三个阶段：接近食物，周围的食物，和抓食物[16]。在接近食物的阶段，黏菌会根据环境中的气味自发地接近食物。展开定律可以用公式表示：
其中X（t + 1）和X (t)分别表示（t第+ 1）和第t次迭代中黏菌的位置。操作“×”表示乘法运算。Xb (t)表示黏液从开始到当前迭代的最适合位置。XA (t)和XB (t)代表在随机选择的种群中黏菌的两个随机位置。r1是一个介于0到1之间的随机数。vb是[−a，a]中的一个任意数量，其中vb的变化模拟了黏菌在接近食物或继续搜索之间的选择。Vc是黏液模的振荡向量，它修改了其搜索轨迹。它的范围从1到零。参数a和选择概率p的确定如下：
黏菌的种群大小用数字i = 1,2，……，N. t表示当前的迭代次数，T为最大迭代次数。S (i)表示第i个黏液模具的适应度得分，DF表示在所有迭代中获得的最佳适应度得分。以下是权重W的更新公式：
其中条件代表适应度值上半部分的黏菌个体；其他人代表剩下的个体。r1是一个介于0到1之间的随机数。bF和wF分别表示当前迭代的最佳和最差适应度得分。操作“×”表示乘法运算。公式中应用对数函数来减慢黏模收缩引起的数值变化速率，稳定收缩频率。条件模拟了黏菌根据食物的数量改变其位置的过程，越高的食物浓度导致附近黏菌的重量越高。已排序的适应度值列表用索引排序来表示。在寻找食物的过程中，黏菌塑造的个体分离了一部分人口，以发现新的领域，并试图找到更好的高质量的解决方案。这就增加了解决方案的可能性。黏液模算法的位置更新公式表示为：
其中，rand表示一个从0到1之间的随机数；ub和lb表示搜索区域的上下边界。操作“×”表示乘法，z表示黏菌个体从种群中分离出来寻找替代食物来源的概率。通常，z被设置为0.03。 4.改进的黏液模具算法（IMSMA）4.1。基于伯努利映射和反向学习的种群初始化策略种群初始化对算法的有效性影响很大。混沌映射方法具有遍历和随机性的特点，适用于可能区域的早期探索，可以增加算法的多样性[18]。常见的混沌映射模型包括帐篷映射[27]和物流映射[28]。与之相比，伯努利映射[29]具有更均匀的分布。因此，本研究将伯努利混沌映射纳入了黏液模算法的种群初始化方法中。方程是
在式(7)中，k表示混沌迭代次数，λ是混沌映射的参数，通常设置为0.4。将生成的混沌序列y映射到解的搜索空间，如式(8)所示。这里，X表示映射在解区间lb内映射的值，ub是黏液模的边界。操作“×”表示乘法运算。此外，相反的学习方法采用了从初始总体中获得反解的思想。通过添加反向解，可以进一步提高种群多样性[30]，提高算法的搜索能力。因此，本研究在将伯努利映射应用于总体后，采用了相反的学习方法。相反的学习方法是提佐什在2005年[31]在群体智能领域提出的一种改进方法。它的概念是在优化过程中根据当前的解生成一个反解。为了为后续的迭代选择最佳的解决方案，其目标
比较了本解和相反解的函数值。以下是生成相反溶液的公式：
在式(9)中，X∗为黏菌种群的反解，lb和ub为黏菌种群搜索空间的最高和最低边界，X为黏菌种群的当前解。然后将得到的反解与原解合并，形成一个新的种群X =（X∗∪X）。根据它们的目标函数值，计算了新种群的适应度值。随后，对适应度值进行排序，并选择种群的前半部分作为初始种群。4.2.柯西分布是柯西突变来自[32]的地方。下面描述了标准柯西分布的概率密度函数：
图1显示了标准高斯分布、标准柯西分布和标准t分布的概率密度函数曲线。通过对曲线的分析，可以观察到，将高斯分布、t分布和柯西分布的比较表明，它更宽、更平坦，并且更慢地趋近于零。此外，与高斯分布和t-分布相比，柯西分布的原点峰更小。这个较小的峰值引导个体使用较少的时间来试图找到最佳的位置[33]。因此，柯西突变表现出更强的扰动，更有利于帮助黏菌种群逃脱局部最优状态。
图1.概率密度函数为堡氏分布、高斯分布和柯西分布。当前最佳解决方案的更新策略如下：
在式（11）中，cauchy (0、1）表示公共cauchy分布。柯西分布的随机生成函数被写成η = tan（π·（ξ−0.5）），其中ξ表示一个从0到1的随机向量。xij表示ith的位置
个体在第j维，xij new代表第i个个体在经历柯西突变后在第j维的新位置。如果在黏液模算法的迭代更新过程中，种群的全局最优解没有更新超过5次迭代，则认为种群可能会停留在其局部最优状态。为了提高逃避区域最优的可能性，采用了柯西突变。定义总体的全局最佳值未被更新的条件是，从当前迭代的最佳位置得到的最佳适应度值ft与全局最佳值fGbest之间的绝对差值小于∆，如下式所示：
其中t为当前迭代数，根据定义，当∆= 0.001时，算法处于局部最优。在这种情况下，黏菌种群利用柯西突变来帮助它逃避局部最优。4.3.非线性动态边界条件传统的SMA在早期迭代中经常遇到黏模位置超过边界的问题。处理边界条件的典型方法是将超过顶边的个体的值设置为顶边界值，并将超过下边界的个体的值设置为下边界值。然而，这种边界条件处理方法不利于算法的收敛性[13]。在本研究中，我们提出了一个非线性的动态边界条件，如下式所示：
其中Xij rand (t)表示随机黏模位置；c1和c2是0和1之间的两个随机数；k1和k2是控制参数k大小的振幅调整系数，k1和k2分别设置为1.5和5。在早期迭代中，当黏液模位置远离全局最优时，k值缓慢下降。超过位置范围的黏模受系数k的影响较大，增强了黏模算法的全局搜索能力。在后期的迭代中，黏液模位置受k值的影响较小，受最佳位置的影响较大，导致局部搜索能力更强，算法收敛速度更快。4.4.IMSMA流程图和伪代码改进的黏液模算法（IMSMA）的流程图如图2所示。首先，利用基于伯努利映射的方向学习策略对黏菌种群进行初始化。随后，计算黏菌的重量(W)和参数a的值。将随机数r与参数z进行了比较。如果r小于z，黏液模具的位置将被更新，使用
如果它有，则认为该算法已收敛到一个全局最优值。在这种情况下，采用柯西突变策略对位置进行更新，并重新计算和更新全局最优值。如果全局最优值在连续5次的跨度内至少改变了一次，则检查是否满足终止条件。如果不满足该条件，则将继续进行迭代。如果满足条件，算法终止，输出最优解和最优适应度值。
图2. IMSMA流程图。改进的黏液模算法（IMSMA）的伪代码如下：步骤1。初始化：T、昏暗、黏菌数量N、z、lb、ub。步骤2。基于伯努利映射反向学习策略，初始化黏菌种群的位置。进行适合度计算并对其进行排序，以找到最佳适应度值bF和最差适应度值wF。步骤3。计算权重W和参数a的值。步骤4。如果rand < z：根据式(6)中的第一个方程，调整黏液模的位置；转到步骤6。另外：更新p、vb、vc；转到步骤5。步骤5。如果r < p：根据式(6)中的第二个公式，调整黏液模的位置；转至步骤6。另外：根据式(6)中的第三个方程，调整黏液模的位置，进入步骤6。
步骤6。根据非线性动态边界条件，修正黏液模的位置。在计算出适应度值后，更新全局最优解。步骤7。如果全局最佳解决方案的变化不超过5次，则对黏菌的位置进行柯西突变；转到步骤6。步骤8。如果不满足终止条件，请转到步骤3。否则：生成最佳答案及其适应度值，并终止该程序。 5.对改进的黏模算法的性能进行了仿真实验。实验环境使用了第11代英特尔®CoreTM i5- 11400H CPU，时钟速度为2.70 GHz（英特尔公司，圣克拉拉，加州，美国），16 GB内存和64位Windows 11操作系统。所使用的编程语言是Python，3.6版本。实验选择了F1到F4四个测试函数。f1和f2是单模态函数，而f3和f4是来自CEC2019基准测试函数的多模态函数。表2提供了关于这四个基准测试功能的详细信息。
利用所选择的四个测试函数来评估了算法的性能，并对本文提出的WOA、BOA、SSA、SMA和IMSMA进行了比较。为了保证实验的公平性，将测试环境和算法参数设置为相同的值。所有智能算法的蜂群大小都固定在30，维数为30，最大迭代次数为500。每个基准函数执行30次后，五种算法的收敛曲线如图3所示
从函数F1的收敛曲线来分析实验结果和算法的收敛曲线，可以看出，IMSMA在260次迭代左右开始收敛，而SMA在280次迭代左右开始收敛。IMSMA的收敛速度稍快一些。从30次实验的最终结果来看，IMSMA达到了平均适应度值1.1214×10−295，可以观察到，甚至更接近理论最优值0。对于函数F2，IMSMA在300次迭代左右开始收敛，且收敛速度最快。从表3中可以明显看出，IMSMA得到的适应度值平均为零，这说明它可以找到最优的结果。对于函数F3，收敛曲线图显示，在前300次迭代中，SSA和BOA比IMSMA具有更好的收敛性能。然而，经过300次迭代后，SSA陷入局部最优，难以逃脱，而BOA的收敛曲线变得更平坦，导致收敛速度较慢。另一方面，IMSMA和SMA快速收敛，并在300次迭代左右找到最优值。比较I
6.用IMSMA 6.1解决多处理器公平调度问题。多处理器公平调度问题模型的建立，任务调度问题已被证明是一个np困难问题。确保调度的公平性可以在一定程度上提高处理器资源的利用率。根据不同的应用程序场景，公平性的定义可能会有所不同。为了实现公平的调度，我们关注每个处理器上的平均处理时间，并旨在最小化每个处理器上的最大平均执行时间，以实现公平的调度。在此基础上，建立了一个多处理器公平调度问题的模型。假设n个作业和m个处理器，让Pij表示在处理器j上执行作业i所需的时间。我们引入了一个二进制变量xij来指示作业i是否在处理器j上运行。计算公式如下：
步骤2。基于伯努利映射反向学习策略，初始化黏菌种群的位置。步骤3。输入多处理器公平调度的目标函数。计算适应度值并对其进行排序，得到最大的适应度值bF和最差的适应度值wF。步骤4。计算权重W和参数a的值。步骤5。如果rand < z：根据式(6)中的第一个方程，调整黏液模的位置；转到步骤7。另外：更新p、vb、vc；转到步骤6。步骤6。如果r < p：根据式(6)中的第二个公式，调整黏液模的位置；转至步骤7。否则：使用公式(6)中的第三个公式确定黏模的位置；转至步骤7。步骤7。根据非线性动态边界条件，修正黏液模的位置。在计算出适应度值后，更新全局最优解。步骤8。如果全球最佳解决方案没有改变超过5次，则对黏菌的位置进行柯西突变；转到第7步。步骤9。如果不满足终止条件，则转至步骤4；否则：生成最佳答案及其适应度值
图4.测试函数的收敛性曲线。根据图4和表4所示的数据，可以得出结论，IMSMA在多处理器上解决公平调度问题的目标函数值最低，表现最好。IMSMA有效地提高了解决多处理器上公平调度问题的效率。 8.结论本文研究了多处理器上的公平调度问题，并在原黏模算法的基础上提出了一种改进的黏模算法（IMSMA）。IMSMA引入了一种基于伯努利映射和反向学习的种群初始化策略，以增强黏菌型的种群多样性。它采用柯西突变策略，便于在算法被困时逃离局部最优。此外，将黏模算法的边界条件修改为非线性动态边界条件，以提高收敛效率和精度。采用两个单模态函数和两个多模态测试函数进行了仿真实验，验证了算法的有效性。结果恶魔
与其他算法相比，具有较好的收敛性能。IMSMA不仅可以用于解决多处理器上的公平调度问题，还可以应用于出租车调度系统和快递调度等各种场景中。作者贡献：概念化出版社，医学博士。和Z.J。；方法论、医学博士。和Z.J。；软件、医学博士。；验证，医学博士。和Z.J。；形式化分析，Z.J。；调查，医学博士。和Z.J。；资源，Z.J.。；数据管理医学。；起草-准备原稿，医学博士。；写作-评论和编辑，医学博士。和Z.J。；可视化、医学博士。；监督，Z.J.。；项目管理，医学博士。；资金收购，医学博士。所有作者均已阅读并同意了该手稿的出版版本。资助：本研究部分由江苏研究生研究实践创新项目资助编号KYCX233076，部分由常州大学研究项目资助编号KYP2202236C，KYP2202735C，部分由江苏数字工程研究中心的关键设备资助编号DT2020720。APC是由常州大学研究公关公司资助
引用1。在雾云计算中使用多目标混合遗传算法的多处理器任务调度。Knowl.-Based的系统。2023, 272, 110563. 2.唐，问。；朱，L.H.。；周，L.；在同构多处理器系统上调度具有最优复制策略的有向无环图。J.平行分布。配置。2020, 138, 115–127. 3.费金；一个公平的拼车调度算法。IBM J. Res。开发人员。1983, 27, 133–139. 4.一种高效的实时多处理器调度算法。J. Converg.影响技术技术。2014, 9, 136. 5.使用分布式加权循环法进行高效和可扩展的多处理器公平调度。ACM签名计划不适用。2009, 44, 65–74. 6.奈尔，P。；在具有冷待机的多处理器系统上进行容错实时公平调度。IEEE跨。可靠的安全。配置。2019, 18, 1718–1732. 7.李z；白Y.；刘J。陈J。张泽。具有全球公平性的自适应比例公平调度。维雷尔。网络网络。2019, 25, 5011–5025. 8.魏、D.、王、Z
23.肖z；陈l；王，B；杜J；李，K.芯片多处理器共享缓存竞争博弈的新型公平感知协同调度。影响科学的科学。2020, 526, 68–85. 24.沙拉米，B.；在异构多核处理器上的公平感知节能调度。IEEE跨。配置。2020, 70, 72–82. 25.Mohtasham，A.；框架：在多过程环境中的公平资源分配。在2015年IEEE第21届并行和分布式系统国际会议（ICPADS）的会议记录上，澳大利亚墨尔本，2015年12月14-17日；pp。601–608. 26.荣格；申J.；洪，J.；j；李；一种使用任务满意度指数的多处理器系统的公平调度算法。《自适应和收敛系统研究国际会议论文集》，波兰克拉科夫，2017年9月20-23日；页。269–274. 27.Kanwal，s；奥斯曼，M.T.B.；Waqar，A.；易卜拉欣，M.；纳瓦兹，F.；Nawaz，Z.；Hamam，一种基于Henon映射、帐篷混沌映射和正交矩阵的有效彩色图像加密。传感器2022、22、4359。 28.张，C.；丁，S.一个随机构型网络ba
