Page 111 - 《软件学报》2021年第12期

王静莲 等:软硬件节能原理深度融合之绿色异构调度算法 3775

3: Do in parallel for each island /*Obtain coarse-grained model, one of the parallel models*/
4: ι=ι+1;
5: Do in parallel /*Obtain master-slave model, another parallel model*/
6: Evaluate genome fitness on the dynamic equation (Eq.(7)) in the current subpopulation:
+
Γ(Ch r (τ))(r∈R ,Ch r (τ)∈Ξ(τ));
+
7: Sort the individuals fitness: Γ(Ch r (τ))(r∈R ,Ch r (τ)∈Ξ(τ)), and save the fittest individual Ch elite (ι)
in the external memory;
8: Perform local search strategies to ensure the Cesaro average convergence of the irreducible
aperiodic Markov chain of the population sequence;
9: Perform clonal operation;
10: Perform gene operations, such as crossover and mutation defined as Section 2.3;
11: End Do in parallel
12: If ι=τ (migration interval) then
13: Create Ψ δ for the current subpopulation;
14: Send Ψ δ to the neighboring subpopulation;
15: Receive Ψ δ from the neighboring subpopulation;
16: Construct the founding subpopulation Ξ;
17: Select Θ individuals into Ξ;
τ
18: Replace the subpopulation Ψ δ with Ψ ;
δ
19: End If
20: End Do in parallel
21: End While
22: Output the best individual.
2.5 算法时间复杂度分析

设在每一代进化中,种群 FeaNonPop 和 ModNonPop 的规模都为θ,克隆倍数为 з,变量的维数为£,约束维数
为 Ћ,目标函数维数为 m,则:
• 在每次克隆种群 ModNonPop 所用的复杂度为 O(зθ);
• 交叉操作所需复杂度为 O(£зθ/2);
• 变异操作所需复杂度为 O(£зθ);
• 计算种群 Pop 基因亲和度值的时间复杂度为 O(£зθ);
• 合并种群 ModNonPop 所需复杂度为 O(£θ+Ћθ+mθ);
• 修正种群 Pop 中个体模因值所需复杂度为 O(3m(з+1)θ+2Ћ(з+1)θ);
2 2
• 选取并更新可行非支配解集所需复杂度为 O((2з+6+mз+2m)θ+m(з+2) θ +(з+2)(m+1)θlog 2 ((з+2)θ));
2 2
• 选取并更新非支配解集所需复杂度为 O((m+1)(з+1)θ+θ+m(з+1) θ +(m+1)(з+1)θlog 2 ((з+1)θ)).
因此,算法 GHSA_di/II 的复杂度为多项式时间(polynomial time).
3 仿真实验及结果

实验在山东省高性能计算中心进行,中心拥有先进异构集群、存储和网络资源,可满足日益增长的云研究
及应用服务需求.同时,中心长期为各种数据密集应用提供服务,可就多种输入实例展开绿色驱动调度研究,以
保证其实际通用性.具体包括如下配置.
• 曙光天潮高性能计算集群;