Page 397 - 《软件学报》2025年第8期

3820 软件学报 2025 年第 36 卷第 8 期

相对苛刻的情况下, 不存在单目标问题的实数解. 在这种情况下, 需要选择多目标优化算法来获得其帕累托最优
解. 本文选择的多目标优化算法是非支配排序遗传算法 (NSGA-II).

3.3.3.1 目标函数归一化
为应用 NSGA-II 算法, 首先需要对目标函数进行归一化处理. 归一化处理的主要目的是消除目标函数之间的
量纲和数值差异, 从而使得算法能够在一个统一的度量空间中对多目标问题进行有效求解. 链上成本和交易时延
具有不同的单位和量纲, 数值变化范围也可能存在较大差异. 这种差异可能会导致 NSGA-II 算法在求解过程中对
某些目标过度关注, 而忽略其他目标. 为解决这个问题, 本文采用归一化方法将这两个目标转换到相同的度量空
间, 使得它们在求解过程中具有相近的权重. 在本问题中, 需要对链上成本和交易时延两个目标进行归一化处理.
具体来说, 本文实际使用的归一化处理方式是线性归一化. 对于目标函数 f i (x), 本文可以使用以下公式 (10)
进行归一化处理:

 min
 f i (x)− f
 i max
 , f i (x) < f i


f =  f max − f min (10)
∗
i  i i

 max
1, f i (x) ⩾ f i

∗
其中, f (x) 表示归一化后的目标函数值, f min 和 f max 分别表示目标函数 f i (x) 的最小值和最大值. 更具体的, 对于等
i i i
待时延, 最小值为 0, 最大值为系统可容忍的平均时延上限 t max . 对于平均计算成本而言, 最小值为 0, 最大值为系统
可容忍的平均计算成本上限 g max .

3.3.3.2 快速非支配排序
快速非支配排序 (fast nondominated sorting, FNS) 是一种经典的多目标排序算法. 借鉴快速排序的思想, 通过
x 1 和 , 满足公式 (11)
分治策略和递归方法, 对解集进行分类和并按照支配关系判定排序. 支配关系指的是对于 x 2
则可以说明 x 1 支配 , 即解 x 2 的所有目标均劣于 .
x 1
x 2

f 1 (x 1 ) ⩽ f 1 (x 2 ) and f 2 (x 1 ) ⩽ f 2 (x 2 ) (11)
算法的最终结果可以将目标种群划分成为若干层, 在同一层内的解不存在支配关系, 不同层之间的节点具备
支配关系. 本文最终的目标应当是最优的支配层, 也被称为帕累托最优解集, 即图 10 中的第 1 层解集.

F 2
第1层解集
第2层解集
第3层解集

F 1
图 10 快速非支配排序结果图

3.3.3.3 拥挤度算子
拥挤度算子 (crowding distance operator, CDO) 是一种用于多目标进化优化算法的算子. 该算子通过计算个体
在目标函数空间中的邻近度来度量其稀疏程度, 从而在搜索空间中保持种群的多样性. CDO 算子的主要功能是在
解空间中分配适当的距离, 以使得种群中的解尽可能地分散. 对于每个目标函数, CDO 算子通过计算每个个体的
左右相邻个体之间的距离, 得到个体的拥挤度值. 传统拥挤度的计算方式为:

f j (x i+1 )− f j (x i−1 )
M ∑
CDO(i) = (12)
f max − f min
j=0 j j