进化算法(evolutionary algorithm, EA)作为一种启发式算法,因其具有较好的全局搜索能力,多用于求解多目标优化问题(multi-objective optimization problems, MOPs)[1]。随着科学技术的发展,出现了许多与实际工程问题有关的昂贵多目标优化问题(expensive many-objective optimization problems, EMOPs)[2-4],如天线优化设计[5]、熔镁炉设计[6]、汽车侧撞试验[7]以及农用拖拉机进气通风系统设计问题等实际问题。采用计算流体动力学和昂贵的实时评估来解决农用拖拉机进气通风的设计问题。汽车侧面抗撞的性能问题用有限元分析来测试,包括车辆重量、加速时间、不同速度下的道路噪声以及车辆的空间等决策变量。然而,这些传统方法都比较费时。代理辅助进化算法(surrogate-assisted evolutionary algorithms, SAEAs)[8]即构建廉价代理模型来近似替代昂贵实验结果,再用模型管理策略选取少部分解进行有限次的真实评估,从而能够较快求解费时问题。因此SAEAs成为求解EMOPs更为有效率的一类方法。

根据代理模型的不同,SAEAs大致可分为两类:一类是采用基于回归的SAEAs,即根据历史数据信息构建代理模型来逼近真实目标函数值,模型输出为个体的预测值。K-RVEA[9]中,构建Kriging模型来近似每个目标函数,选择使用不确定性或基于角度的惩罚距离来确定需要进行真实评估的个体。在KTA2[10]中,改进了强影响点对Kriging模型的干扰,提出一种状态需求的填充采样准则。另一类是基于分类的SAEAs,即放弃构建预测精确信息的模型,考虑构建一种能够区分解是否为值得评估解的分类模型作为代理模型。一般采用径向基函数(radial basis function, RBF)、K最近邻(K-nearest neighbor, KNN)[11]和前馈神经网络(feedforward neural network,FNN)作为代理模型来判断解的类型。在CPS-MOEA[12]中,采用分类模型预测种群中解之间的支配关系,选择非支配解进行真实评估。在CSEA[13]中,采用前馈神经网络预测种群中的个体与参考点之间的支配关系,选择较优个优进行真实计算。REMO算法[14]是一种基于关系模型辅助的多目标高代价演化算法,建立面向不平衡数据的分类器,利用PBI方法的惩罚因子δ,保证正负样本相对平衡。MCEA/D[15]则是一种新的基于分类的SAEAs,利用多个局部分类器来规避问题性的过拟合,最后通过模型管理策略来增强预筛选能力。

基于回归的SAEAs求解低维问题具有高效、精度高等优点,但随着实际问题中目标空间维数和决策空间维度的增多,Kriging模型的复杂度与样本数量呈指数增长,其累积误差会影响预测结果。基于分类的SAEAs对于求解高维问题更具有竞争力,但在求解低维问题时,会存在分类器模型精度不高而导致算法性能不佳等问题。因此,本文针对分类器预测精度不高和模型管理效率低等问题,提出了一种基于自适应采样策略的模糊分类代理辅助进化算法(fuzzy classification surrogate-assisted evolutionary algorithm based on adaptive sampling strategy,FCEA-ASS),用于求解EMOPs。

本文的主要贡献点:

(1)将模糊分类器作为代理模型,保证预测模型的精度,并采用基于转移的密度估计策略提高选择压力,以此兼顾收敛性与多样性。

(2)利用分类器精度信息,设计了一种根据分类精度划分状态的自适应模型管理策略,使用模糊隶属度对具体状态进行针对性设置,能够降低误导搜索方向的可能,提高算法的运行效率。

1 相关工作

1.1 昂贵多目标优化问题

EMOPs即指在优化多目标问题的过程中,由于目标函数为黑盒,通常用耗时的数值模拟或昂贵的物理实验来评估,这会耗费较高的时间或成本。因此,一般构建廉价的代理模型来代替昂贵的物理实验。以最小化问题为例,考虑以下形式的EMOPs:

(1)

式中:x为具有d个决策变量的决策向量;X表示决策空间;fm(x)为目标向量F的第m个目标。

1.2 基于移位Pareto密度估计的多目标优化

本文使用SPEA2+SDE[16]算法作为优化器,该算法提出基于转移的密度估计策略(shift-based density estimation strategy, SDE),通过改变多样性的方式提高选择压力,同时具有更好的收敛性与分布的多样性。具体步骤:若估计个体p的密度时,SDE通过对比收敛性,p在一个目标上表现比另一个个体q好时,就将q转移到p当前目标位置上,否则q的位置不变。这种策略会将收敛性差的个体在选择过程中快速被淘汰删除,从而提高选择压力。

(2)

式中:D′(p,P)为个体p在种群P中新的密度估计;N为种群个数;dist(p,q′i)为两个体的相似度;q′i为qi转移后的点,qi为另一个对比个体,具体方法如式(3)所示。

(3)

2 基于自适应采样策略的模糊分类代理辅助进化算法

FCEA-ASS算法将多局部幂均值模糊K最近邻分类器(multi-local power means fuzzy K-nearest neighbor classifier, MLPM-FKNN)[17]作为分类代理模型,SPEA2+SDE为优化器,提出一种针对模糊分类器的自适应采样策略,具体的算法步骤如算法1所示。

算法1 FCEA-ASS算法。

输入:种群P,种群总数N,最大迭代次数Fmax;

输出:真实评估的个体Off_p。

① 初始化种群。采用随机生成种群大小为N的初始种群P,进行真实评估后放入Arc。

② 构建分类代理模型。通过帕累托支配关系筛选训练样本来构造模糊分类器。采用十折交叉验证获得分类器的分类准确率。将MLPM-FKNN预测训练样本的隶属度和标签,参与子代预选。

③ 后代生成预选。种群生成2N个后代解,排序并选择前N个较优解。然后将选定的解用作父代解继续产生新的后代解。后代生成预选为重复wmax次。

④ 填充采样准则。采用自适应采样策略,考虑当前种群的收敛性、多样性和不确定性,根据自适应采样策略,得到个体Off_p。

⑤ 环境选择机制。生成下一代的新种群。

2.1 多局部幂均值模糊K最近邻分类器

构建MLPM-FKNN的动机是希望能够克服多量样本的类会主导检验样本预测的这一缺点,这种不足可以通过使用局部平均向量来引导。

构建MLPM-FKNN过程如下。

步骤1 首先计算训练样本和检验样本Q之间的欧几里得距离,并按升序对它们进行排序。Q的K个最近邻nnK为步骤2 使用从K个最近邻中求局部幂均值子样本每个类的

步骤3 计算Q和之间的欧几里得距离。由式(4)和式(5)使用加权距离将隶属度分配给

步骤4 将Q分类到与其具有最高隶属度的相应类ω*。

式(4)为检验样本Q在由K个最近邻表示的类中分配的隶属度,如式(4)所示:

(4)

式中:uij为训练集中第i类中第j个样本的隶属度;c为影响隶属度的模糊强度参数,c>1。

每个表示类中xj的隶属度计算如式(5)所示:

(5)

式中:nj表示属于第j类的邻居数。

幂均值也称为广义均值,是一系列均值的函数。如果x1,x2,…,xn为一组实数,z为一个参数(z∈R),则幂均值Mz可以定义为

(6)

2.2 自适应采样策略

通常模型管理策略会选取少部分较优解进行有限次的真实评估,指导算法进化方向。对于SAEAs,模型管理策略是算法性能提升的关键之一。如何设计模型管理策略才能同时兼顾收敛性和多样性是值得探索的难点,这需要在选取收敛性和多样性较优解的同时,也要选取不确定性较大的解来提高代理模型的全局精度。

本文提出一种基于分类精度Accuracy评估的自适应采样策略,该策略利用模型精度划分3种度量状态,使用模糊隶属度对3种状态进行针对性设置。具体流程图如图1所示。

将隶属度划分正负类。由于0.5在模糊隶属度中的特殊性,所以将隶属度u为0.5作为分类边界,将u≥0.5标记为正类,否则为负类。其中,在正类中u不接近0.5的解归类为不确定性较小的正解;相同地,在负类中u不接近0.5的解则归类为不确定性较小的负解。当u值接近0.5时,认为分类结果在类预测中具有较大不确定性的解。

(1)Accuracy≥75%为高精度状态。未评估的解根据隶属度值按降序排列,选取隶属度较大的解。

(2)35%≤Accuracy<75%为中精度状态。首先,正类根据隶属度值按升序排列,取隶属度接近0.5不确定性大的正解;其次,负类根据隶属度值按降序排列,取隶属度接近0.5不确定性大的负解;最后,正解与负解合并进行真实评估。其中,选取不确定性大的解是为了提高模型的准确性。

(3)Accuracy<35%为低精度状态。未评估的解随机排列,并不选取解。

在考虑划定状态的阈值时,经过大量试验证明35%与75%作为阈值是最合理的。算法在MaF1～MaF6测试集与WFG1～WFG9测试集上均独立运行20次,分别取平均值,平均精度如图2所示。由图2可知,模型优化开始时的精度较低,精度随着迭代次数的增加而提高。原因是早期训练数据集数量较小,无法反映解之间的真实关系,难以做出正确的预测。

3 算法有效性实验

3.1 对比算法

(1)REMO[14]:一种基于关系模型辅助的多目标高代价演化算法,提出基于罚函数边界法的自适应种群划分策略和多目标关系模型下概率“投票-打分”策略。

(2)CPS-MOEA[12]:一种基于分类的代理辅助进化算法,使用两个归档集训练分类回归树,最后选择新的候选个体,保留正解。

(3)CSEA[13]:使用人工神经网络来预测支配关系,将不确定性与支配关系作为模型管理策略的关键。

(4)MCEA/D[15]:一种新的基于分类的SAEAs,构建基于SVM的分类器,利用多个局部分类器来规避问题的过拟合,通过模型管理策略增强预筛选能力。

3.2 MaF与WFG测试集

为了验证本文所提算法针对EMOPs的有效性,选用两个广泛应用的多目标优化问题测试集MaF和WFG。其中WFG测试问题的复杂程度更高,处理起来更具有挑战性,能够提供更有效的依据来评估优化算法在各种不同测试集上的表现性能。WFG测试集的属性包括可分性或不可分性、单峰或多峰、PF形状为凸或非凸、无偏差参数或有偏差参数。

3.3 参数设置

(1)所有算法参数设置:种群大小N=50,最大迭代次数为500。其中FCEA-ASS算法K=3,z=3,c=2,wmax=30。

(2)在MaF[18]与WFG[19]的测试集上,使用目标M为3、4、6、8,决策变量D为12、13、15、17的测试问题。利用以上测试函数来验证算法性能,如表1、表2所示。

(3)为了保证公平性,参与实验的所有算法特定参数都严格遵循原始文献中的设置。所有仿真测试均在PlatEMO上进行。对于每个测试问题,每个算法独立执行20次,并使用反向世代距离IGD指标[20]进行综合评估,IGD值越小算法的综合性能越好。

3.4 算法有效性实验

表1为5种算法在MaF1～MaF6测试集上进行20次独立运行所获得的IGD的对比结果。由表1可以看出,FCEA-ASS算法在目标为3、4、6、8的共计24个MaF测试函数上,取得16个全局最优结果。其中FCEA-ASS算法在MaF3的各个维度上均取得了最佳结果,在MaF1和MaF3上优势最大,说明算法针对解决具有反转PF和凹型PF多模态特征问题时具有优势。

FCEA-ASS算法在求解MaF2、MaF4、MaF5、MaF6时,在每个测试集上只获得了两组最优结果,MCEA/D和CSEA算法则几乎占据了剩余维度测试问题的优势。FCEA-ASS对于具有偏好特征的问题求解效率不高,因为采用简单的帕累托支配关系筛选样本的方式优势不大,同时不能快速定位偏好区域,从而在这类问题上表现一般。

表2为5种算法在WFG1～WFG9测试集上进行20次独立运行所获得的IGD的对比结果。从表2可以看出,在测试集WFG中,算法FCEA-ASS在目标为3、4、6、8的共计36个WFG测试函数上,取得29个全局最优结果。其中FCEA-ASS在WFG4、WFG6、WFG7、WFG8、WFG9的各个维度上均取得了最佳结果。对于WFG1、WFG2和WFG3测试问题,FCEA-ASS算法仅取得6组最佳结果,CESA算法排第2位。尤其对于3和4目标的WFG1测试函数,FCEA-ASS略逊于CSEA,原因是CSEA预定义的参考向量可以帮助快速定位区域,而FCEA-ASS靠非支配关系还是很难准确定位大致前沿区域。

图3可视化了5个算法在3目标MaF2上的解集分布图。从图3可以看出,FCEA-ASS是收敛性和分布性最好的算法,该算法采用基于转移的密度估计策略,提高了选择压力,有效兼顾多样性与收敛性,并配合自适应采样策略正确引导了算法的进化方向。图4可视化了5个算法在3目标MaF4和6目标MaF5上IGD的变化趋势。从图4可以看出,只有算法FCEA-ASS的IGD最小。综上所述,能够证明该算法具有较强的优势,是所有算法中取得最佳结果次数最多的算法。

WFG2问题的帕累托前沿(Pareto front,PF)是不连续的。WFG3是一个退化问题,算法在这类测试问题上表现一般,WFG4与WFG9为两类多模态问题,FCEA-ASS取得了较优的表现,这说明自适应采样策略能够提高算法的运行效率,使得算法的局部搜索能力增强。图5可视化了5种算法在3目标WFG3和8目标WFG8上IGD的变化趋势,能够明显看出FCEA-ASS的IGD为最佳。所提算法使用模糊分类器作为代理模型,采用基于转移的密度估计策略兼顾收敛性与多样性,设计自适应采样策略能够提高算法的整体性能。结合算法在两种测试集上的表现,都证明了所提算法在求解昂贵多目标优化问题时,具备较强的竞争力。

3.5 算法时间复杂度对比分析

对算法的运行效率进行进一步分析,图6记录了5种不同算法单独运行20次求解MaF和WFG系列测试问题的平均耗时。从图6可以看出,FCEA-ASS算法比REMO和CSEA的运行时间短,但比CPS-MOEA算法运行时间长,FCEA-ASS与MCEA/D算法平均运行时间相似。但综合考虑FCEA-ASS算法在MaF、WFG测试集上均能够获得更好的优化结果,耗时都在20 s之内是可以接受的,且所提算法对于不同类型的问题的求解时间不会随着问题类型的变化而变化。综上所述,本文提出的FCEA-ASS算法时间复杂度低,具有良好、稳定的求解性能和较高的算法运行效率。

3.6 策略有效性分析

将MLPM-FKNN作为代理辅助模型,使用传统的模型管理策略求解问题,将其算法命名为FCEA。且FCEA算法与FCEA-ASS算法进行了对比实验,比较结果如表3所示。表3提供了两种算法在求解M=8、D=17时15个测试集的IGD均值和标准差。从表3可以看出所提FCEA-ASS算法的优势,证明了所提算法的竞争力。

3.7 实际工程优化测试

为了验证FCEA-ASS算法在实际问题中的有效性,本节在汽车侧面碰撞设计和驾驶室设计[21]案例上进行了仿真实验,并与多个经典算法进行了对比。汽车侧面碰撞设计问题为4个目标和7个决策变量。涉及最小化汽车重量、平均速度下司机所受到的冲击载荷等目标。同时驾驶室设计问题涉及9个目标和7个决策变量。包括汽车空间、燃油经济性、加速时间及不同速度下的道路噪声等。5种算法进行20次重复实验,单次500次评估后得到的IGD均值如表4所示,通过实验结果证明算法FCEA-ASS具备一定的竞争力和优势。

4 结论

本文提出一种自适应采样策略的模糊分类代理辅助进化算法FCEA-ASS。首先,该算法使用多局部幂均值模糊K最近邻分类器作为代理模型,利用精度信息进行模型管理,降低时间复杂度的同时保证了采样的准确度;其次,采用基于转移的密度估计策略,兼顾收敛性与多样性;最后,自适应采样策略依据隶属度标签和分类精度,针对不同状态的分类器,采取有针对性的采样策略。经过数值仿真分析表明,所提算法具有一定的竞争力,特别是在处理具有退化特征和多模态特征问题具有明显优势,在解决EMOPs上具有广阔的应用前景,同时还具有实际工程应用价值。

在未来的工作中,将算法FCEA-ASS扩展到解决具有高维约束的复杂多目标优化问题中,继续探索更有效的模型管理策略,尝试解决更多的昂贵现实问题,发挥实际应用价值。

参考文献：

[1] 郑金华. 多目标进化算法及其应用[M]. 北京: 科学出版社, 2007.ZHENG J H. Multi objective evolutionary algorithm and its applications [M]. Beijing: Science Press, 2007.

[2] FAN X Z, LI K, TAN K C. Surrogate assisted evolutionary algorithm based on transfer learning for dynamic expensive multi-objective optimisation problems[C]∥2020 IEEE Congress on Evolutionary Computation (CEC). Piscataway:IEEE, 2020: 1-8.

[3] 邓传义, 孙超利, 刘晓彤, 等. 惯性分组和重叠特征选择辅助的昂贵大规模优化算法[J]. 郑州大学学报(工学版), 2023, 44(5): 32-39.DENG C Y, SUN C L, LIU X T, et al. An inertial grouping and overlapping feature selection assisted algorithm for expensive large-scale optimization problems[J]. Journal of Zhengzhou University (Engineering Science), 2023, 44(5): 32-39.

[4] WANG R Y, ZHOU Y E, CHEN H N, et al. A surrogate-assisted many-objective evolutionary algorithm using multi-classification and coevolution for expensive optimization problems[J]. IEEE Access, 2021, 9: 159160-159174.

[5] 温文吉. 克里金代理模型和多目标优化算法在天线设计中的应用[D]. 镇江: 江苏科技大学, 2020.WEN W J. Application of Kriging proxy model and multi-objective optimization algorithm in antenna design[D]. Zhenjiang: Jiangsu University of Science and Technology, 2020.

[6] 郭单. 数据与模型驱动的复杂工业过程智能优化方法及应用研究[D]. 沈阳: 东北大学, 2019. GUO D. Research on intelligent optimization method and application of complex industrial process driven by data and model[D]. Shenyang: Northeastern University, 2019.

[7] DEB K, JAIN H. An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part Ⅰ: solving problems with box constraints[J]. IEEE Transactions on Evolutionary Computation, 2014, 18(4): 577-601.

[8] GU Q H, WANG Q, LI X X, et al. A surrogate-assisted multi-objective particle swarm optimization of expensive constrained combinatorial optimization problems[J]. Knowledge-Based Systems, 2021, 223: 107049.

[9] CHUGH T, JIN Y C, MIETTINEN K, et al. A surrogate-assisted reference vector guided evolutionary algorithm for computationally expensive many-objective optimization[J]. IEEE Transactions on Evolutionary Computation, 2018, 22(1): 129-142.

[10] SONG Z S, WANG H D, HE C, et al. A Kriging-assisted two-archive evolutionary algorithm for expensive many-objective optimization[J]. IEEE Transactions on Evolutionary Computation, 2021, 25(6): 1013-1027.

[11] KELLER J M, GRAY M R, GIVENS J A. A fuzzy K-nearest neighbor algorithm[J]. IEEE Transactions on Systems, Man, and Cybernetics, 1985, SMC-15(4): 580-585.

[12] ZHANG J Y, ZHOU A M, ZHANG G X. A classification and Pareto domination based multiobjective evolutionary algorithm[C]∥2015 IEEE Congress on Evolutionary Computation (CEC). Piscataway: IEEE, 2015: 2883-2890.

[13] PAN L Q, HE C, TIAN Y, et al. A classification-based surrogate-assisted evolutionary algorithm for expensive many-objective optimization[J]. IEEE Transactions on Evolutionary Computation, 2019, 23(1): 74-88.

[14] HAO H, ZHOU A M, QIAN H, et al. Expensive multiobjective optimization by relation learning and prediction[J]. IEEE Transactions on Evolutionary Computation, 2022, 26(5): 1157-1170.

[15] SONODA T, NAKATA M. Multiple classifiers-assisted evolutionary algorithm based on decomposition for high-dimensional multiobjective problems[J]. IEEE Transactions on Evolutionary Computation, 2022, 26(6): 1581-1595.

[16] LI M Q, YANG S X, LIU X H. Shift-based density estimation for Pareto-based algorithms in many-objective optimization[J]. IEEE Transactions on Evolutionary Computation, 2014, 18(3): 348-365.

[17] KUMBURE M M, LUUKKA P, COLLAN M. An enhancement of fuzzy K-nearest neighbor classifier using multi-local power means[C]∥Proceedings of the 2019 Conference of the International Fuzzy Systems Association and the European Society for Fuzzy Logic and Technology (EUSFLAT 2019). Paris: Atlantis Press, 2019: 83-90.

[18] CHENG R, LI M Q, TIAN Y, et al. A benchmark test suite for evolutionary many-objective optimization[J]. Complex &Intelligent Systems, 2017, 3(1): 67-81.

[19] HUBAND S, HINGSTON P, BARONE L, et al. A review of multiobjective test problems and a scalable test problem toolkit[J]. IEEE Transactions on Evolutionary Computation, 2006, 10(5): 477-506.

[20] ISHIBUCHI H, MASUDA H, TANIGAKI Y, et al. Modified distance calculation in generational distance and inverted generational distance[C]∥The 8th International Conference of Evolutionary Multi-criterion Optimization. Cham: Springer, 2015: 110-125.

[21] TANABE R, ISHIBUCHI H. An easy-to-use real-world multi-objective optimization problem suite[J]. Applied Soft Computing, 2020, 89: 106078.

Fuzzy Classification Surrogate-assisted Evolutionary Algorithm Based on Adaptive Sampling Strategy

LI Erchao, WU Yu

(College of Electrical and Information Engineering, Lanzhou University of Technology, Lanzhou 730050, China)

Abstract：In order to solve the problem of low management efficiency of classification surrogate-assisted evolutionary algorithms based on fuzzy classification and how to effectively reduce the number of real function evaluations, in this study a fuzzy classification surrogate-assisted evolutionary algorithm was proposed based on an adaptive sampling strategy. Firstly, in the algorithm the agent model was constructed by screening samples through the Pareto dominance relationship. Then, the selection pressure was improved by using a transfer-based density estimation strategy, which balanced convergence and diversity. At the same time, ten-fold cross-validation was used to obtain accuracy information to divide the states. Finally, an adaptive model management strategy was designed. Considering the convergence, diversity, and uncertainty of the current population, targeted sampling methods was adopted according to different accuracy states. The algorithm could ensure overall performance while rationally reducing the number of real evaluations. To verify the performance of the proposed algorithm, it was compared with four other algorithms on the MaF and WFG test sets and real-world engineering problems of automotive side impact design and driving cabin design. The experimental results showed that the proposed algorithm, which could prove that the algorithm had good competitiveness in solving expensive multi-objective optimization problems with the limited number of real evaluations.

Keywords：surrogate-assisted evolutionary algorithm; surrogate model; expensive many-objective optimization problems; model management

中图分类号：TP18

文献标志码：A

doi：10.13705/j.issn.1671-6833.2025.02.010

收稿日期：2024-10-24;修订日期：2024-12-16

基金项目：国家自然科学基金资助项目(62063019);甘肃省自然科学基金资助项目(24JRRA173)

作者简介：李二超(1980—),男,河北保定人,兰州理工大学教授,博士,博士生导师,主要从事人工智能、多目标优化、机器人控制等研究,E-mail:lecstarr@163.com。

引用本文：李二超,吴煜. 基于自适应采样策略的模糊分类代理辅助进化算法[J].郑州大学学报(工学版),2025,46(2):51-59.(LI E C,WU Y. Fuzzy classification surrogate-assisted evolutionary algorithm based on adaptive sampling strategy [J].Journal of Zhengzhou University(Engineering Science),2025,46(2):51-59.)

文章编号：1671-6833(2025)02-0051-09