一种基于qos目标的微服务系统调度优化方法
技术领域
1.本发明属于云计算环境下软件工程技术领域，涉及一种基于qos(服务质量)目标的微服务系统调度优化方法。
背景技术：2.微服务是近年来极为流行的一种软件架构，在soa架构的基础上实现了去中心化、细粒度划分服务、分布式储存数据的设计，属于云计算环境下软件工程领域的一个新范例。与单片架构相比，微服务通过分布式调度和部署组合成一个完整的系统，可以更好实现敏捷开发，且更易于部署和维护。近年来微服务已经成为优步、netflix、spotify以及amazon等众多重量级厂商的优先选择。实际开发过程中，每个服务都具备多个业务功能相同或相似的服务实例，以确保系统运行的稳定性。毫无疑问这套架构方案在软件开发生命周期内具备着巨大吸引力，但其诸多优势的背后也隐藏着一些问题：在计算资源有限的情况下，微服务冗余部署的调度方案会带来质量层面的风险，如何定义集群调度时的策略，如何根据qos指标做出调度选择，使最终组合出的系统在全局非功能属性上达到最优，这是一个目前很少被研究的问题。该问题本质上是分布式环境下的调度组合方案优化问题。
3.目前的服务计算的研究主要集中在传统的web服务组合问题上。而现有的服务组合问题研究技术中，微服务性能方面的研究大多是针对微服务组合平台的分析，针对微服务的组合调度策略优化研究不多，而借鉴web服务进行组合调度策略优化的研究中，启发式算法性能也有待继续提高。面对微服务粒度小，调度组合数据量大的问题，这些算法存在着优化效率低、需要的控制参数较多、容易陷入局部收敛、解决高维复杂问题时的实现过程十分复杂等问题。例如，本领域常用的蚁群算法是一种模拟蚂蚁觅食行为的启发性智能寻优算法，算法关键步骤包含路径构建与信息素更新。但是该算法的信息素更新方式单一，面对较大规模的对象时，无法取得较好的效果；最大最小蚂蚁系统(max-min ant system,mmas)为国外学者提出的蚁群算法的衍生算法，改进后的算法通过允许表示全局最优的蚂蚁与表示局部最优的蚂蚁均释放信息素来改进信息素更新方式，又通过将蚂蚁路径上的信息素浓度大小限制于规定的最大最小值直接来提高最优解探索可能性与蚂蚁的自领悟能力，使得蚁群算法的信息素改进方法优化。mmas可用于解决各类离散优化问题，但该算法在初期由于信息素堆积过慢导致了效率低下，而微服务具备粒度小、数量多等特征，基于qos目标的微服务系统调度优化问题仅靠mmas等单一算法会出现问题空间爆炸的现象；遗传算法(genetic algorithm,ga)是一种基于模拟物种进化过程的进化来寻找最优解的方法。该算法通过种群选择，交叉和变异自动计算解空间中的最优解。遗传算法具有很高的全局优化能力，并且可以对搜索过程自动调整。同样的，ga虽然可以用于解决微服务组合优化问题，但由于ga在针对微服务组合这一类较复杂的优化问题时，在搜集利用大量网络反馈信息上效率较低,故算法的搜索效果并不理想，目前已经不能单独来很好的解决大规模问题。
技术实现要素：4.本发明的技术解决问题是：克服现有技术的不足，提出一种基于qos目标的微服务系统调度优化方法，能够更高效精确地解决基于qos目标的微服务系统调度优化问题。
5.本发明的技术解决方案是：
6.一种基于qos目标的微服务系统调度优化方法，该方法的步骤包括：
7.第一步：建立微服务系统的调度模型，具体方法为：
8.设编制组合调度方案下的微服务系统的调度模型表示为s，令s＝{ms1,ms2,
…
,msk,
…
msm}，k∈{1,2,
…
,m}，msk表示微服务系统的第k个抽象调度节点，m表示微服务系统的业务功能数量；
9.每个抽象调度节点msk对应一个候选微服务簇，msk＝{ms
k1
，ms
k2
，
…
，ms
ki
，
…
ms
kn
}，i∈{1，2，...，n}，其中ms
ki
代表抽象节点msk的第i个可调度微服务副本，n代表功能相同、质量属性不同的可调度微服务副本的数量；
10.设向量集合msg＝{msgj|j＝{1，2，...，nm}}为该优化问题的决策向量集，其中msgj代表编制组合下的一个调度方案，msgj为m维向量，msgj＝{ms
1q
，ms
2q
，
…
，ms
mq
|q∈{1，2，...，n}}，下标j代表该向量在决策向量集中的索引，ms
mq
表达第m个抽象节点的第q个微服务副本，决策向量的长度对应抽象节点总数，向量元素的值为调度池中微服务副本的离散编码。
11.第二步，设定优化调度目标的计算方式，具体方法为：
12.将微服务系统s的调度模型的qos指标计算方法确立为优化调度目标的计算方式，即决策向量msgi，i∈{1，2，...，nm}的适应度函数f(msgj)；
13.第三步，使用cmma-ga算法针对优化调度目标进行寻优，具体方法为：
14.(1)对种群和参数进行初始化，具体方法为：在编码范围内，随机生成n个决策向量作为cmma-ga算法初始种群，设定算法参数，算法参数包括交叉变异操作部分的最大迭代次数n
ga_max
、交叉概率pc、变异概率pv、算法迭代次数n
cmma-ga_max
、蚂蚁个数m、蚂蚁循环变量mc＝1、禁忌表矩阵tabum×n、代表表现优良的蚂蚁路径的记录表l、表现较差的蚂蚁路径的记录表r；
15.(2)对蚁群进行交叉与变异操作，具体方法为：评估初始种群n个决策向量的适应度函数值，得到适应度最高的前m个向量作为蚂蚁向量，在蚂蚁移动之前，结合遗传算法ga的方法，根据交叉概率pc与变异概率pv对m个蚂蚁向量进行n
ga_max
次迭代更新；
16.(3)对蚁群进行协作学习觅食，具体方法为：在每一轮迭代前生成初始信息素，然后将m个蚂蚁向量根据转移概率进行移动，移动后进行局部信息素更新，一轮迭代完成后再对蚁群向量进行一次协作模仿学习更新并完成信息素的更新；
17.所述的初始信息素的确定方法为：
18.设蚁群中居于前3％的适应度函数值为f
5％
(msgi)，i∈{1,2,
…
,m}，则根据下式生成cmma-ga算法中初始信息素；
19.τ
ij
(t)＝τ
max
+kg×f5％
(msgi)
20.其中，kg为缩放常数，τ
max
为常数，对应于mmas原始策略中初始化信息素的最大选择值；
21.所述的状态转移概率的确定方法为：
22.设t时刻在节点i的蚂蚁数量为bi(t)，则蚂蚁数t时刻路径(i，j)上的信息素浓度为τ
ij
(t)，当t＝0时各路径上的信息素浓度相同，均为τ
ij
(0)＝c(c为常数)，η
ij
表示路径(i，j)上的目可见度。蚂蚁k(k∈1,2,...,m)在搜索过程中依靠状态转移规则来选择下一顶点。p
ijk
(t)表示在t时刻位于节点i上的蚂蚁k选择转移到j节点的概率，概率转移如下式所示：
[0023][0024]
其中，ak＝{k-tabuk}表示蚂蚁k还未访问到的调度节点的某个候选服务，τ
ij
(t)表示微服务实例ms
ki
到ms
k+1,j
之间的信息素强度，η
ij
(t)表示微服务实例ms
ki
到ms
k+1,j
的适应度目标函数，此处α为信息启发因子，β为期望启发因子；
[0025]
所述的局部信息素更新方法为：
[0026]
局部信息素的更新在每个蚂蚁移动结束时根据下式进行更新：
[0027][0028]
其中，τ0为信息素放在每个顶点的初始值；参数是挥发因子，为规定的特殊局部更新规则的值；
[0029]
所述的蚁群协作模仿学习方法为：
[0030]
根据社会认知算法中协作学习思路，“按成绩分组”与“模仿优生”可以提高知识的共享速率。因此在不磨损精确度的情况下，本实施例通过协作学习的方法改进了蚁群寻优策略，进一步提高算法的执行效率。其具体操作如下：
[0031]
i)“优差生”路径分组：设置代表适应度较高的蚂蚁路径记录表l，适应度较低的蚂蚁路径的记录表r。在蚁群完成一次迭代完成之后，选择适应值值排在前g条蚂蚁路径msai(1≤i≤g)∈msg放入优生表l，选择表现最不好的后g条路径放入差生表r。
[0032]
ii)“观察模仿优生”学习：当蚂蚁群体在每一次循环遍历寻找最优路径的过程中，将表l中的g条“优生”的决策向量msai(1≤i≤g)分别依次作为“学习榜样”，再将对应剩余的m-1条决策向量作为学习者路径msbj(j∈(1，2，...i-1，i+1，...m-1)∈msg，学习者路径群体对“学习榜样”msai
(1≤i≤g)
轮流进行g次基因模仿选择，最终生成g条优于其他路径的新路径msni(1≤i≤g)，并用于替换掉差生表r中的决策向量。这样就可以将局部“优点”通过协作学习聚集到这m条蚂蚁路径中。
[0033]
为防止此改进加速算法早熟，可结合ga对每一条经过协作学习程序的染色体进行多点变异操作。
[0034]
所述的改进信息素更新策略方法为：
[0035]
当所有蚂蚁完成一轮觅食后，为避免残留信息素浓度过大影响新的信息需对各路径上的残留信息素进行更新。在本实施例中，进一步提高mmas的全局寻优能力，本发明在蚁
群算法现有信息素更新策略上进行了改进如下式所示；
[0036][0037]
其中，ρ为信息素的挥发因子，信息增量f(s
p
)代表第p只蚂蚁经过路径的适应度函数值，e
l
表示其经过的第l条边，l
p
代表蚂蚁经过的整条路径。这样的更新规则有利于避免局部最优路径信息素迅速堆积，同时增强了随即搜索能力。mmas对信息素τ
ij
(t)的限定在[τ
min
，τ
max
]中，若τ
ij
(t)≥τ
max
，则τ
ij
(t)＝τ
max
；若τ
ij
(t)≤τ
min
，则τ
ij
(t)＝τ
min
，与此同时要保证τ
min
＞0，τ
min
，τ
max
的计算公式如下式所示；
[0038][0039][0040]
其中，f(s
best
)取至今最优，即至今最高适应度函数值；
[0041]
在该信息素更新策略下，“优生”表l的信息素将不断增强，“差生”表r的信息素将不断衰减，根据协同学习思想，整个群体将朝最优前进，因此有效的降低了算法陷入局部最优的概率，提高了整体的寻优能力；
[0042]
(4)反复执行寻找全局最优决策向量，具体方法为：
[0043]
重置禁忌表tabum×n，完成n
cmma-ga_max
轮迭代，输出全局中适应度函数值最高的决策向量，即为最优决策向量；
[0044]
第四步，根据最优决策向量确立微服务系统基于qos的最佳调度方案，具体为：
[0045]
根据最优决策向量的向量元素码元得到对应的微服务副本，再通过编制组合调用将各服务组合成系统。
[0046]
自此，就完成/实现了一种基于qos目标的微服务系统调度优化方法，能够自动高效的提供一套微服务调度组合方案，有效优化微服务系统随机调度质量表现不稳定问题。
[0047]
有益效果
[0048]
(1)本发明明的方法明确了基于qos目标的微服务系统调度优化方法并搭建了微服务质量调度优化的可计算模型s；
[0049]
(2)本发明的方法通过优化计算提供了计算目标，明确了优化目标的计算方式，且提出了cmma-ga优化算法，并给出了cmma-ga算法的实施步骤；
[0050]
(3)本发明的方法通过对cmma-ga算法中种群和参数进行初始化的具体方法，给出了对cmma-ga算法中的蚁群进行交叉与变异操作，以此提高算法在执行初期的收敛速率；
[0051]
(4)本发明的方法通过让cmma-ga算法中的蚁群进行协作学习觅食操作的方法，以此提高算法优化效率，避免算法早熟。
[0052]
(5)本发明的方法给出了蚁群进行协作学习觅食过程中初始信息素、转移概率、局部信息素更新的具体计算方法，并通过改进信息素更新的计算方式来避免残留信息素浓度过大影响新的信息需对各路径上的残留信息素进行更新，同时给出了蚁群协作模仿学习的具体操作，来提高迭代过程中蚁群整体的适应度，从而提高优化效率。
[0053]
(6)本发明的方法阐明了算法寻优的迭代、终止条件，得到了cmma-ga执行结果，即得到了最优决策向量。
[0054]
(7)本发明的方法阐明了如何通过最优决策向量得到最优调度方案。
[0055]
(8)本发明的方法将协作学习思想与遗传算法的交叉变异操作应用到改进的混合最大最小蚁群中，提出了协作的混合改进蚁群遗传算法cmma-ga(collaborative max-min ant-genetic algorithm)，该算法改善了基本mmas算法的不足，并详细说明了该算法在服务组合优化求解时的具体实现步骤，能够对常见微服务系统实现基于qos目标的调度方案自动生成，有效解决微服务系统质量管理方案缺失、调度组合低效问题。
附图说明
[0056]
图1是本发明基于qos目标的微服务系统调度优化方法流程图；
[0057]
图2为微服务系统调度问题示意图；
[0058]
图3协作学习交叉过程。
具体实施方式
[0059]
下面结合附图并举实施例，对本发明进行详细描述。
[0060]
如图1所示，本具体实施的基于qos目标的微服务系统调度优化方法，具体包括：
[0061]
一、决策向量的编码以及优化目标的确立。
[0062]
一个编制组合调度方案下的微服务系统s可表示为s＝{ms1,ms2,
…
,msm},msk是根据业务功能划分的m个抽象调度节点，对应每个抽象节点msk的候选微服务簇ms
ki
集合是ms
ki
＝{ms
k1
,ms
k2
,
…
,ms
kn
}，ms
ki
代表抽象节点msk所具有的功能相同、质量属性不同的i个可调度微服务。则如图2所示，在实际组合中一个真实的调度路径方案可能为m维向量msgi＝{ms
12
,ms
22
,
…
,ms
mn
}，即为优化算法的决策向量。该决策向量的长度(向量维度)对应调度节点总数，向量元素的值为调度池中候选原子微服务的离散编码。本实施例中采用十进制离散编码，每个决策向量对应一种完整的服务调度方案msgi，向量元素值对映节点下微服务ms
ki
的十进制索引编号。
[0063]
系统调度目标是使得系统qos达到最优，本实施例中，qos目标的确定采用以下方式：由于微服务系统的质量受多因素影响，通过线性加权组合多个因素的方式求解qos目标，即为qos(x)＝w1p'+w2t'+w3r'+w4a'，x表示种群个体，即解向量表示的服务组合方案，p',t',r',a'分别表示该解方案对应的组合服务的执行价格、响应时间、可靠性和可用性。本实施例中，设定系统的qos目标为优化目标，即决策向量的适应度计算函数。
[0064]
二、使用cmma-ga算法进行寻优。
[0065]
初始化种群和参数。在上一步骤的编码范围内，随机生成n个调度向量作为cmma-ga算法初始种群，设定算法参数：交叉变异操作部分的最大迭代次数n
ga_max
、交叉概率pc、变异概率pv、算法迭代次数n
cmma-ga_max
、蚂蚁个数m、蚂蚁循环变量mc＝1、禁忌表矩阵tabum×n、代表表现优良的蚂蚁路径的记录表l、表现较差的蚂蚁路径的记录表r。
[0066]
蚁群的交叉与变异操作。评估初始种群n的适应度值，得到适应度最高的前m个向量作为蚂蚁向量，在蚂蚁移动之前，结合遗传算法ga的方法，根据交叉概率pc与变异概率pv对m个蚂蚁向量进行n
ga_max
次迭代更新。
[0067]
本实施例中，交叉操作使用两点交叉。
[0068]
本实施例中，变异操作使用轮盘赌策略。
[0069]
蚁群的协作学习觅食法。在每一轮迭代前生成初始信息素，然后将m个蚂蚁向量根据转移概率进行移动，移动后进行局部信息素更新，一轮迭代完成后再对蚁群向量进行一次协作模仿学习更新并完成信息素的更新。
[0070]
初始信息素计算方式，具体方法如下：
[0071]
设蚁群中居于前3％的适应值f
5％
(msgi)，i∈{1,2,
…
,m}则根据公式1来生成cmma-ga算法中初始信息素。
[0072]
τ
ij
(t)＝τ
max
+kg×f5％
(msgi)
ꢀꢀ
(1)
[0073]
其中kg为缩放常数，τ
max
为常数，对应于mmas原始策略中初始化信息素的最大选择值。
[0074]
本实施例中，状态转移概率计算方法如下：
[0075]
设t时刻在节点i的蚂蚁数量为bi(t)，则蚂蚁数某时刻t在路径(i，j)上的信息素浓度为τ
ij
(t)，当t＝0时各路径上的信息素浓度相同，均为τ
ij
(0)＝c(c为常数)，η
ij
表示路径(i，j)上的目可见度。蚂蚁k,(k＝1,2,...,m)在搜索过程中依靠状态转移规则来选择下一顶点。p
ijk
(t)表示在t时刻位于节点i上的蚂蚁k选择转移到j节点的概率，概率转移满足公式2。
[0076][0077]
在公式2中，ak＝{k-tabuk}表示蚂蚁k还未访问到的调度节点的某个候选服务，τ
ij
(t)表示微服务实例ms
ki
到ms
k+1，j
之间的信息素强度，η
ij
(t)表示微服务实例ms
ki
到ms
k+1，j
的适应度目标函数，此处α为信息启发因子，β为期望启发因子。
[0078]
本实施例中，局部信息素更新方法如下：
[0079]
局部信息素的更新在每个蚂蚁移动结束时根据公式3进行更新。
[0080][0081]
其中τ0为信息素放在每个顶点的初始值；参数是挥发因子，为规定的特殊局部更新规则的值。
[0082]
本发明的蚁群协作模仿学习具体方法如下：
[0083]
根据社会认知算法中协作学习思路，“按成绩分组”与“模仿优生”可以提高知识的共享速率。因此在不磨损精确度的情况下，本实施例通过协作学习的方法改进了蚁群寻优策略，进一步提高算法的执行效率。其具体操作如下：
[0084]
i)“优差生”路径分组：设置代表适应度较高的蚂蚁路径记录表l，适应度较低的蚂蚁路径的记录表r。在蚁群完成一次迭代完成之后，选择评价值排在前g条蚂蚁路径msai(1
≤i≤g)∈msg放入优生表l，选择表现最不好的后g条路径放入差生表r。
[0085]
ii)“观察模仿优生”学习：当蚂蚁群体在每一次循环遍历寻找最优路径的过程中，将表l中的g条“优生”的决策向量msai(1≤i≤g)分别依次作为“学习榜样”，再将对应剩余的m-1条决策向量作为学习者路径msbj(j∈(1，2，...i-1，i+1，...m-1))∈msg，学习者路径群体对“学习榜样”msai(1≤i≤g)轮流进行g次基因模仿选择，最终生成g条优于其他路径的新路径msni(1≤i≤g)，并用于替换掉差生表r中的决策向量。这样就可以将局部“优点”通过协作学习聚集到这m条蚂蚁路径中。
[0086]
图3所示即为模仿观察学习的过程。为防止此改进加速算法早熟，可结合ga对每一条经过协作学习程序的染色体进行多点变异操作，其中服务选择路径发生突变的服务实例个数设o，突变次数设为y。
[0087]
改进信息素更新策略，具体方法如下：
[0088]
当所有蚂蚁完成一轮觅食后，为避免残留信息素浓度过大影响新的信息需对各路径上的残留信息素进行更新。在本实施例中，进一步提高mmas的全局寻优能力，本发明在蚁群算法现有信息素更新策略上进行了改进如式4所示。
[0089][0090]
其中，ρ为信息素的挥发因子，信息增量f(s
p
)代表第
[0091]
p只蚂蚁经过路径的目标函数值，e
l
表示其经过的第l条边，l
p
代表蚂蚁经过的整条路径。这样的更新规则有利于避免局部最优路径信息素迅速堆积，同时增强了随即搜索能力。mmas对信息素τ
ij
(t)的限定在[τ
min
，τ
max
]中，若τ
ij
(t)≥τ
max
，则τ
ij
(t)＝τ
max
；若τ
ij
(t)≤τ
min
，则τ
ij
(t)＝τ
min
，与此同时要保证τ
min
＞0。
[0092]
本文采取的τ
min
，τ
max
的计算公式如式5-6所示。
[0093][0094][0095]
其中f(s
best
)取至今最优。
[0096]
在该信息素更新策略下，“优生”表l的信息素将不断增强，“差生”表r的信息素将不断衰减，根据协同学习思想，整个群体将朝最优前进，因此有效的降低了算法陷入局部最优的概率，提高了整体的寻优能力。
[0097]
(4)重置禁忌表tabum×n，完成n
cmma-ga_max
轮迭代，输出全局适应值最高的决策向量，即为一组最优调度方案。
[0098]
自此，就完成/实现了一种基于qos目标的微服务系统调度优化方法。能够自动高效的提供一套微服务调度组合方案，有效优化微服务系统随机调度质量表现不稳定问题。
[0099]
综上所述，以上仅为本发明的较佳实施例而已，并非用于限定本发明的保护范围。凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。
技术特征：1.一种基于qos目标的微服务系统调度优化方法，其特征在于该方法的步骤包括：第一步：建立微服务系统的调度模型；第二步，设定优化调度目标的计算方式，即将决策向量的适应度函数为微服务系统qos指标的计算方式；第三步，使用cmma-ga算法针对优化调度目标进行寻优；第四步，根据最优决策向量获得微服务系统调度模型基于qos的最佳调度方案。2.根据权利要求1所述的一种基于qos目标微服务系统的调度优化方法，其特征在于：所述的第一步中，建立微服务系统的调度模型的方法为：设编制组合调度方案下的微服务系统的调度模型表示为s，令s＝{ms1，ms2，
…
，ms
k
，
…
ms
m
}，k∈{1，2，...，m}，ms
k
表示微服务系统的第k个抽象调度节点，m表示微服务系统的业务功能数量；每个抽象调度节点ms
k
对应一个候选微服务簇，ms
k
＝{ms
k1
，ms
k2
，
…
，ms
ki
，
…
ms
kn
}，i∈{1，2，...，n}，其中ms
ki
代表抽象节点ms
k
的第i个可调度微服务副本，n代表功能相同、质量属性不同的可调度微服务副本的数量；设向量集合msg＝{msg
j
|j＝{1，2，...，n
m
}}为该优化问题的决策向量集，其中msg
j
代表编制组合下的一个调度方案，msg
j
为m维向量，msg
j
＝{ms
1q
，ms
2q
，
…
，ms
mq
|q∈{1，2，...，n}}，下标j代表该向量在决策向量集中的索引，ms
mq
表达第m个抽象节点的第q个微服务副本，决策向量的长度对应抽象节点总数，向量元素的值为调度池中微服务副本的离散编码。3.根据权利要求1或2所述的一种基于qos目标微服务系统的调度优化方法，其特征在于：所述的第二步中，设定优化调度目标的计算方式为：将微服务系统s的调度模型的qos指标计算方法确立为优化调度目标的计算方式，即决策向量msg
i
，i∈{1，2，...，n
m
}的适应度函数f(msg
j
)。4.根据权利要求3所述的一种基于qos目标的微服务系统调度优化方法，其特征在于：所述的第三步中，使用cmma-ga算法针对优化调度目标进行寻优，具体方法为：(1)对种群和参数进行初始化；(2)对蚁群进行交叉与变异操作；(3)对蚁群进行协作学习觅食；(4)反复执行寻找全局最优决策向量。5.根据权利要求4所述的一种基于qos目标的微服务系统调度优化方法，其特征在于：所述的步骤(1)中，对种群和参数进行初始化的方法为：在编码范围内，随机生成n个决策向量作为cmma-ga算法初始种群，设定算法参数，算法参数包括交叉变异操作部分的最大迭代次数n
ga_max
、交叉概率p
c
、变异概率p
v
、算法迭代次数n
cmma-ga_max
、蚂蚁个数m、蚂蚁循环变量m
c
＝1、禁忌表矩阵tabu
m
×
n
、代表表现优良的蚂蚁路径的记录表l、表现较差的蚂蚁路径的记录表r。6.根据权利要求4或5所述的一种基于qos目标的微服务系统调度优化方法，其特征在于：所述的步骤(2)中，对蚁群进行交叉与变异操作的方法为：评估初始种群n个决策向量的适应度函数值，得到适应度最高的前m个向量作为蚂蚁向量，在蚂蚁移动之前，结合遗传
算法ga的方法，根据交叉概率p
c
与变异概率p
v
对m个蚂蚁向量进行n
ga_max
次迭代更新。7.根据权利要求6所述的一种基于qos目标的微服务系统调度优化方法，其特征在于：所述的步骤(3)中，对蚁群进行协作学习觅食的方法为：在每一轮迭代前生成初始信息素，然后将m个蚂蚁向量根据转移概率进行移动，移动后进行局部信息素更新，一轮迭代完成后再对蚁群向量进行一次协作模仿学习更新并完成信息素的更新。8.根据权利要求6所述的一种基于qos目标的微服务系统调度优化方法，其特征在于：所述的初始信息素的确定方法为：设蚁群中居于前3％的适应度函数值为f
5％
(msg
i
)，i∈{1，2，...，n
m
}，则根据下式生成cmma-ga算法中初始信息素；τ
ij
(t)＝τ
max
+k
g
×
f
5％
(msg
i
)其中，k
g
为缩放常数，τ
max
为常数，对应于mmas原始策略中初始化信息素的最大选择值；所述的转移概率的确定方法为：设t时刻在节点i的蚂蚁数量为b
i
(t)，则蚂蚁数t时刻路径(i，j)上的信息素浓度为τ
ij
(t)，当t＝0时各路径上的信息素浓度相同，均为τ
ij
(0)＝c(c为常数)，η
ij
表示路径(i，j)上的目可见度，蚂蚁k(k∈1，2，...，m)在搜索过程中依靠状态转移规则来选择下一顶点，p
ijk
(t)表示在t时刻位于节点i上的蚂蚁k选择转移到j节点的概率，概率转移如下式所示：其中，a
k
＝{k-tabu
k
}表示蚂蚁k还未访问到的调度节点的某个候选服务，τ
ij
(t)表示微服务实例ms
ki
到ms
k+1，j
之间的信息素强度，η
ij
(t)表示微服务实例ms
ki
到ms
k+1，j
的适应度目标函数，此处α为信息启发因子，β为期望启发因子；所述的局部信息素更新方法为：局部信息素的更新在每个蚂蚁移动结束时根据下式进行更新：其中，τ0为信息素放在每个顶点的初始值；参数是挥发因子；所述的蚁群协作模仿学习方法为：i)“优差生”路径分组：设置代表适应度较高的蚂蚁路径记录表l，适应度较低的蚂蚁路径的记录表r，在蚁群完成一次迭代完成之后，选择适应值值排在前g条蚂蚁路径msa
i
(1≤i≤g)∈msg放入优生表l，选择表现最不好的后g条路径放入差生表r；ii)“观察模仿优生”学习：当蚂蚁群体在每一次循环遍历寻找最优路径的过程中，将表l中的g条“优生”的决策向量msa
i
(1≤i≤g)分别依次作为“学习榜样”，再将对应剩余的m-1条决策向量作为学习者路径msb
j
(j∈(1，2，...i-1，i+1，...m-1)∈msg，学习者路径群体对
“
学习榜样”msai
(1≤i≤g)
轮流进行g次基因模仿选择，最终生成g条优于其他路径的新路径msn
i
(1≤i≤g)，并用于替换掉差生表r中的决策向量；所述的改进信息素更新策略如下式所示；其中，ρ为信息素的挥发因子，信息增量f(s
p
)代表第p只蚂蚁经过路径的适应度函数值，e
l
表示其经过的第1条边，l
p
代表蚂蚁经过的整条路径，mmas对信息素τ
ij
(t)的限定在[τ
min
，τ
max
]中，若τ
ij
(t)≥τ
max
，则τ
ij
(t)＝τ
max
；若τ
ij
(t)≤τ
min
，则τ
ij
(t)＝τ
min
，与此同时要保证τ
min
＞0，τ
min
，τ
max
的计算公式如下式所示；的计算公式如下式所示；其中，f(s
best
)取至今最优，即至今最高适应度函数值。9.根据权利要求4所述的一种基于qos目标的微服务系统调度优化方法，其特征在于：所述的步骤(4)中，反复执行寻找全局最优决策向量的方法为：重置禁忌表tabu
m
×
n
，完成n
cmma-ga_max
轮迭代，输出全局中适应度函数值最高的决策向量，即为最优决策向量。10.根据权利要求4所述的一种基于qos目标的微服务系统调度优化方法，其特征在于：所述的第四步中，根据最优决策向量确立微服务系统基于qos的最佳调度方案的方法为：根据最优决策向量的向量元素码元得到对应的微服务副本，再通过编制组合调用将各服务组合成系统。
技术总结本发明属于云计算环境下软件工程技术领域，涉及一种基于QoS(服务质量)目标的微服务系统调度优化方法。本发明将协作学习思想与遗传算法的交叉变异操作应用到改进的混合最大最小蚁群中，提出了协作的混合改进蚁群遗传算法CMMA-GA(Collaborative MAX-MIN Ant-Genetic Algorithm)，该算法改善了基本MMAS算法的不足，并详细说明了该算法在服务组合优化求解时的具体实现步骤，能够对常见微服务系统实现基于QoS目标的调度方案自动生成，有效解决微服务系统质量管理方案缺失、调度组合低效问题。问题。问题。
技术研发人员：胡晶晶 徐逍君 郝晋 何婉超 管梓宇 许卓凡 杨修齐
受保护的技术使用者：北京理工大学
技术研发日：2022.07.11
技术公布日：2022/11/1
