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

3774 Journal of Software 软件学报 Vol.32, No.12, December 2021

Ch * ()ι Γ = C {Ch 1 ( ),Chι 2 (),...,Chι ε ( ),...,Chι θι ()}ι
( )
Γ = C (Ch ι 1 ( )) ... Γ + + C (Ch ι ε ( )) ... Γ + + C (Ch θι ( )) ι (9)
( )
1 з
2
ι
ε
{Ch 1 1 ( ),Chι = 1 2 ( ),...,Chι 1 ε ( ),...,Chι 1 1 з ( )} ... {Chι + + 1 θι ( ),Chι θι ( ),...,Chι θι ( ),...,Ch θι ( )}ι
()
()
()
()
这里: Γ C (Ch i ( )) {Chι 1 i ( ),Chι = i 2 ( ),...,Chι ε i ( ),...,Chι i зi ( )},iι 1,2,..., ( );θ = ι зi ∈ [1,m 是可调节参数,表示克隆概率;m c 是
]
c
克隆概率上限;зi=1 代表不对 Ch i (ι)进行克隆操作.
在 GHSA_di/II 算法中,对每个仿生个体采用一致的克隆概率 з,使得优化过程中的可行非支配解集规模几
乎成倍上升,保持个体多样性同时,还可加速群体收敛.具体如公式(10)所示:
з
2
1
Ch * ( ) {Chι = 1 1 ( ),Chι 1 2 ( ),...,Chι 1 з ( )} ... {Chι + + θι ( ),Chι θι ( ),...,Chι θι ( )}ι (10)
( )
( )
( )
与克隆相反,选择操作将种群个体划分为非劣解或劣解,且只有非劣解可进入下一代.对于任何仿生个体
**
#
#
Ch (ι)∈Ch (ι),如果 Ch (ι)满足公式(11)称为非劣解,否则是劣解:
¬∃ δ ϖ # ( )ι δ # ( )(ι ≠ κ = 1,2,..., ;θ ϖ = 1,2,..., ) δ ∈з ** ( ) : (ι ∀ ∈i {1,..., }:m i (δ f # ( ))ι i (δ ≥ f κ ϖ # ( )))ι (11)
κ
而对仿生种群的选择操作Γ S ,可定义为公式(12):
Ch *** ()ι Γ = S (Ch ** ( ))ι
#
Γ S ({Ch ι 1 1# ( ),Ch 1 2# ( ),...,Ch 1 з # ( )} ... {Ch+ ι θι ( ),Ch θ 2# ( ) ι ( ),...,Ch θι ( )})
=
1#
ι
ι
ι +
ι
з
( )
( )
(12)
ι
ι
ι
2#
ι
Γ = S ({Ch ι 1 1# ( ),Ch 1 2# ( ),...,Ch 1 з # ( ),...,Ch θ 1# ( ) ι ( ),Ch θι ( ),...,Ch з ( θι) ()})ι
#
( )
{Ch ι = # ( ),Ch ι # ( ),...,Ch ι # ( ),...,Ch # ( )}ι
s
( )
1 2 ε θι
**
其中, Ch # ()ι (ε=1,…,θs(ι))表示仿生种群 Ch (ι)中的非劣个体,θs(ι)是非劣个体的数目.通常,协同进化系统根据
ε
当代个体的约束偏离值选取可行解集,然后根据个体的目标函数值选取可行非劣解集进行个体选择.
而 GHSA_di/II 算法可依据第 2.1 节定义的进化动力信息直接在种群中选取非劣仿生个体,算法的效率极大
提升.
与此同时,采用不同的基因交叉、变异策略,可有助于种群多样性保持及仿生个体间协同或信息交换.
GHSA_di/II 算法对仿生个体种群的基因操作Γ G 可定义为公式(13);
Ch ** ()ι Γ = G (Ch * ( ))ι
ι
Γ = G ({Ch ι 1 1 ( ),Ch ι 1 2 ( ),...,Ch ι 1 з ( )} ... {Ch 1 θι ( ),Ch θι ( ),...,Ch θ з ( ) ι ( )})ι
+
ι +
2
( )
( )
(13)
{Γ = (Ch 1 ( ))ι + Γ (Ch 2 ( )) ...ι + Γ + (Ch з ( ))} ... {ι + Γ+ (Ch 1 ( ))ι + Γ (Ch 2 ( )) ...ι + Γ + (Ch з ( ))}ι
( )
( )
()
G 1 G 1 G 1 G θι G θι G θι
ι
ι
+
{Ch ι= 1# ( ),Ch 2# ( ),...,Ch з # ( )} ... {Ch 1# ( ),Ch 2# ( ),...,Ch з # ( )}
ι
ι
ι +
1 1 1 θι θ ( )ι θ s ( )ι
( )
通常,协同进化系统模拟二进交叉(SBX cross-over)算子或多项式变异(polynomial mutation)算子.在 GHSA_
di/II 算法中,交叉点或变异点的选取同样可依据第 2.1 节定义的进化动力信息.
2.4 融合非传统主从式和粗粒度的多层次并行化设计及算法描述
目前,通用多核微处理器与定制加速协处理器混合体系已成为千万亿次高性能计算机一种发展趋势,因而,
为适于调度服务器的众核处理器超混合硬件体系,GHSA_di/II 算法采用非传统主从式和粗粒度相融合的多层
次并行与分布式设计.
一方面,依照粗粒度模型,算法将整个进化群体划分成若干子群(第 3 步),子群被分配到不同节点上进行相
关的协同进化模拟计算,并适时采取有效的迁移策略(第 12 步~第 19 步);另一方面,在每一个节点上,大量的进化
动力方程(如遗传算法的适应度函数或人工免疫算法的抗原)计算采用 CPU-GPU 非传统的主从式模型(第 5 步~
第 11 步).这里,主服务器是 CPU,而在 GPU 众核上大量执行的并行线程可看作客户端.
GHSA_di/II algorithm.
1: Initialize the iteration (ι) and the subpopulation Ξ () {= Chι ( ),Chι (),...,Chι ( ),...,Chι ( )},ι
1 2 ε θ
each subpopulation of Θ individuals;
2: While (ι<ι max ) and (other termination criteria are not satisfied)