您的位置：山东大学 -> 科技期刊社 -> 《山东大学学报（理学版）》

《山东大学学报(理学版)》 ›› 2024, Vol. 59 ›› Issue (10): 22-29.doi: 10.6040/j.issn.1671-9352.0.2023.236

•   • 上一篇    下一篇

基于双目标的MNSGA-Ⅱ算法求解非线性方程组

李侦瑷(),韦慧*(),陈馨   

  1. 安徽理工大学数学与大数据学院, 安徽 淮南 232001
  • 收稿日期:2023-05-24 出版日期:2024-10-20 发布日期:2024-10-10
  • 通讯作者: 韦慧 E-mail:1936596383@qq.com;weihui@aust.edu.cn
  • 作者简介:李侦瑷(1999—), 女, 硕士研究生, 研究方向为智能优化算法. E-mail: 1936596383@qq.com
  • 基金资助:
    安徽省自然科学基金资助项目(2108085MA14);国家自然科学基金资助项目(11601007)

MNSGA-Ⅱ algorithm based on bi-objective for solving nonlinear equation systems

Zhenai LI(),Hui WEI*(),Xin CHEN   

  1. School of Mathematics and Big Data, Anhui University of Science and Technology, Huainan 232001, Anhui, China
  • Received:2023-05-24 Online:2024-10-20 Published:2024-10-10
  • Contact: Hui WEI E-mail:1936596383@qq.com;weihui@aust.edu.cn

RichHTML

1

PDF (PC)

175

摘要：

通过MONES转换技术将非线性方程组转换为双目标优化问题, 利用MNSGA-Ⅱ算法中的动态拥挤距离策略提高Pareto解集的多样性, 在种群选择过程中动态计算个体的拥挤距离。为了验证算法的性能, 选择30个非线性方程组进行测试, 对比了基于MONES转换技术的NSGA-Ⅱ、动态NSGA-Ⅱ和MNSGA-Ⅱ算法。实验结果表明, 基于MONES转换技术的MNSGA-Ⅱ算法在寻根率和成功率方面更具优势。最后, 将3个算法得到的Pareto前沿进行对比, 且验证本文算法所得Pareto前沿在均匀性和收敛性方面表现较好。

关键词: 非线性方程组, MONES转换技术, 动态拥挤距离, 非支配排序遗传算法

Abstract:

MONES transformation technique is applied to transform the problem of solving nonlinear equation systems into a bi-objective optimization problem, and a dynamic crowding distance strategy of MNSGA-Ⅱ algorithm is included to dynamically calculate individual crowding distance in the process of population selection, which improves the diversity of Pareto front. In order to verify the performance of algorithm, thirty nonlinear equation systems are selected for testing NSGA-Ⅱ, dynamic NSGA-Ⅱ and MNSGA-Ⅱ algorithm based on MONES transformation technique. Experimental results show that MNSGA-Ⅱ algorithm based on MONES transformation technique has a better root-found ratio and success rate. Finally, the Pareto front of three algorithms mentioned above is compared, and the uniformity and convergence of Pareto front of the proposed algorithm performs better than others'.

Key words: nonlinear equation system, MONES transformation technique, dynamic crowding distance, non-dominated sorting genetic algorithm

中图分类号: 

  • O241

图1

MNSGA-Ⅱ算法流程示意图"

表1

30个NES的特征"

方程组 n① Range② LE③ NE④ R⑤ max_gen⑥
F1 20 [-1, 1]n 0 2 2 500
F2 2 [-1, 1]n 1 1 11 500
F3 2 [-1, 1]n 0 2 15 500
F4 2 [-10, 10]n 0 2 13 500
F5 10 [-2, 2]n 0 10 1 500
F6 2 [-1, 1]n 4 1 8 500
F7 2 [0, 1], [-10, 0] 0 2 2 500
F8 2 [0, 1]n 0 2 7 500
F9 5 [-10, 10]n 0 1 3 500
F10 3 [-5, 5], [-1, 3], [-5, 5] 0 3 2 500
F11 2 [-1, 1], [-10, 10] 0 2 4 500
F12 2 [-1, 2]n 0 2 10 500
F13 3 [-0.6, 6], [-0.6, 0.6], [-5, 5] 0 3 12 500
F14 2 [-5, 5]n 0 2 9 500
F15 2 [0.25, 1], [1.5, 2π] 0 2 2 500
F16 2 [0, 2π]n 0 2 13 500
F17 8 [-1, 1]n 1 7 16 500
F18 2 [-2, 2]n 0 2 6 500
F19 20 [-2, 2]n 19 1 2 500
F20 3 [-1, 1]n 0 3 7 500
F21 2 [-2, 2]n 0 2 4 500
F22 2 [-2, 2]n 0 2 6 500
F23 3 [-20, 20]n 0 3 16 500
F24 3 [0, 1]n 0 3 8 500
F25 3 [-3, 3]n 0 3 2 500
F26 2 [-1, -0.1], [-2, 2] 0 2 2 500
F27 2 [-5, 1.5], [0, 5] 0 2 3 500
F28 2 [0, 2],[10, 30] 0 2 2 500
F29 3 [0, 2], [-10, 10], [-1, 1] 0 3 5 500
F30 2 [-2, 2], [0, 1.1] 0 2 4 500

表2

不同算法的寻根率RR和成功率RS"

方程组MONES_NSGA-Ⅱ MONES_DNSGA-Ⅱ MONES_MNSGA-Ⅱ
RR RS RR RS RR RS
F1 0.983 3 0.966 7   0.000 0 0.000 0   0.000 0 0.000 0
F2 0.942 4 0.566 7 0.969 6 0.700 0 0.993 9 0.933 3
F3 0.937 8 0.333 3 0.940 0 0.366 7 0.962 2 0.533 3
F4 0.589 7 0.000 0 0.610 3 0.000 0 0.612 8 0.000 0
F5 0.933 3 0.933 3 1.000 0 1.000 0 1.000 0 1.000 0
F6 1.000 0 1.000 0 0.933 3 0.933 3 1.000 0 1.000 0
F7 1.000 0 1.000 0 1.000 0 1.000 0 1.000 0 1.000 0
F8 0.895 2 0.266 7 0.909 5 0.366 7 0.928 6 0.500 0
F9 0.000 0 0.000 0 0.000 0 0.000 0 0.000 0 0.000 0
F10 0.383 3 0.000 0 0.500 0 0.133 3 0.516 7 0.100 0
F11 1.000 0 1.000 0 1.000 0 1.000 0 1.000 0 1.000 0
F12 0.806 7 0.166 7 0.820 0 0.233 3 0.846 7 0.333 3
F13 1.000 0 1.000 0 1.000 0 1.000 0 1.000 0 1.000 0
F14 0.177 8 0.000 0 0.1852 0.000 0 0.207 4 0.000 0
F15 0.500 0 0.000 0 0.500 0 0.000 0 0.500 0 0.000 0
F16 1.000 0 1.000 0 1.000 0 1.000 0 1.000 0 1.000 0
F17 0.133 3 0.000 0 0.158 3 0.033 3 0.166 7 0.033 3
F18 1.000 0 1.000 0 1.000 0 1.000 0 1.000 0 1.000 0
F19 0.000 0 0.000 0 0.000 0 0.000 0 0.000 0 0.000 0
F20 0.685 7 0.033 3 0.719 0 0.066 7 0.742 9 0.133 3
F21 1.000 0 1.000 0 1.000 0 1.000 0 1.000 0 1.000 0
F22 0.977 8 0.933 3 1.000 0 1.000 0 1.000 0 1.000 0
F23 0.006 3 0.000 0 0.033 3 0.000 0 0.035 4 0.000 0
F24 0.729 2 0.033 3 0.766 7 0.000 0 0.779 2 0.066 7
F25 0.016 7 0.000 0 0.050 0 0.000 0 0.050 0 0.000 0
F26 1.000 0 1.000 0 1.000 0 1.000 0 1.000 0 1.000 0
F27 1.000 0 1.000 0 1.000 0 1.000 0 1.000 0 1.000 0
F28 0.150 0 0.000 0 0.216 7 0.000 0 0.283 3 0.000 0
F29 0.5133 0.000 0 0.566 7 0.066 7 0.640 0 0.033 3
F30 1.000 0 1.000 0 1.000 0 1.000 0 1.000 0 1.000 0
均值 0.678 7 0.474 4   0.696 0 0.496 7   0.708 9 0.522 2

表3

Friedman检验"

算法 RR RS
MONES_NSGA-Ⅱ 2.550 0 2.333 3
MONES_DNSGA-Ⅱ 1.966 7 1.866 7
MONES_MNSGA-Ⅱ 1.483 3 1.716 7

表4

Wilcoxon检验"

MONES_MNSGA-Ⅱ VS RR   RS
R+① R-② p-value③ R+① R-② p-value⑤
MONES_NSGA-Ⅱ 465 0 0.563 0   465 0 0.466 8
MONES_DNSGA-Ⅱ 465 0 0.806 0 420 45 0.809 6

表5

ZDT测试函数及特征"

测试函数 公式 决策空间 PF特征
ZDT1 $\begin{aligned}& f_1(\boldsymbol{X})=x_1 \\& f_2(\boldsymbol{X})=g(\boldsymbol{X})\left(1-\sqrt{f_1 / g(\boldsymbol{X})}\right) \\& g(\boldsymbol{X})=1+9 \cdot\left(\sum_{i=2}^n x_i\right) /(n-1)\end{aligned}$ n=30 xi∈[0, 1] 凸型连续
ZDT2 $\begin{aligned}& f_1(\boldsymbol{X})=x_1 \\& f_2(\boldsymbol{X})=g(\boldsymbol{X})\left(1-\left(f_1 / g(\boldsymbol{X})\right)^2\right) \\& g(\boldsymbol{X})=1+9 \cdot\left(\sum_{i=2}^n x_i\right) /(n-1)\end{aligned}$ n=30 xi∈[0, 1] 凹型连续
ZDT3 $\begin{aligned}& f_1(\boldsymbol{X})=x_1 \\& f_2(\boldsymbol{X})=g(\boldsymbol{X})\left(1-\sqrt{f_1 / g(\boldsymbol{X})}-f_1 / g(\boldsymbol{X}) \cdot \sin \left(10 \pi x_1\right)\right) \\& g(X)=1+9 \cdot\left(\sum_{i=2}^n x_i\right) /(n-1)\end{aligned}$ n=30 xi∈[0, 1] 凸型不连续

图2

3种算法求解ZDT1测试函数所得PF"

图3

3种算法求解ZDT2测试函数所得PF"

图4

3种算法求解ZDT3测试函数所得PF"

1 FUJITA H , CIMR D . Computer aided detection for fibrillations and flutters using deep convolutional neural network[J]. Information Sciences, 2019, 486, 231- 239.
doi: 10.1016/j.ins.2019.02.065
2 ZHAO J , XU Y T , FUJITA H . An improved non-parallel Universum support vector machine and its safe sample screening rule[J]. Knowledge-Based Systems, 2019, 170, 79- 88.
doi: 10.1016/j.knosys.2019.01.031
3 WU S , WANG H J . A modified Newton-like method for nonlinear equations[J]. Computational and Applied Mathematics, 2020, 39 (3): 238.
doi: 10.1007/s40314-020-01283-8
4 WANG X F , JIN Y F H , ZHAO Y L . Derivative-free iterative methods with some Kurchatov-type accelerating parameters for solving nonlinear systems[J]. Symmetry, 2021, 13 (6): 943.
doi: 10.3390/sym13060943
5 YUAN G L , LI T T , HU W J . A conjugate gradient algorithm for large-scale nonlinear equations and image restoration problems[J]. Applied Numerical Mathematics, 2020, 147, 129- 141.
doi: 10.1016/j.apnum.2019.08.022
6 WANG K , GONG W Y , LIAO Z W , et al. Hybrid niching-based differential evolution with two archives for nonlinear equation system[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2022, 52 (12): 7469- 7481.
doi: 10.1109/TSMC.2022.3157816
7 ALGELANY A M , EL-SHORBAGY M A . Chaotic enhanced genetic algorithm for solving the nonlinear system of equations[J]. Computational Intelligence and Neuroscience, 2022, 2022, 1376479.
8 PAN L Q , ZHAO Y , LI L H . Neighborhood-based particle swarm optimization with discrete crossover for nonlinear equation systems[J]. Swarm and Evolutionary Computation, 2022, 69, 101019.
doi: 10.1016/j.swevo.2021.101019
9 NOBAHARI H , NASROLLAHI S . A terminal guidance algorithm based on ant colony optimization[J]. Computers and Electrical Engineering, 2019, 77, 128- 146.
doi: 10.1016/j.compeleceng.2019.05.012
10 GAO W F , LUO Y T , XU J W , et al. Evolutionary algorithm with multiobjective optimization technique for solving nonlinear equation systems[J]. Information Sciences, 2020, 541, 345- 361.
doi: 10.1016/j.ins.2020.06.042
11 SONG W , WANG Y , LI H X , et al. Locating multiple optimal solutions of nonlinear equation systems based on multiobjective optimization[J]. IEEE Transactions on Evolutionary Computation, 2014, 19 (3): 414- 431.
12 DEB K , PRATAP A , AGRAWAL S , et al. A fast and elitist multiobjective genetic algorithm: NSGA-Ⅱ[J]. IEEE Transactions on Evolutionary Computation, 2002, 6 (2): 182- 197.
doi: 10.1109/4235.996017
13 GONG W Y , WANG Y , CAI Z H , et al. A weighted biobjective transformation technique for locating multiple optimal solutions of nonlinear equation systems[J]. IEEE Transactions on Evolutionary Computation, 2017, 21 (5): 697- 713.
doi: 10.1109/TEVC.2017.2670779
14 JI J Y , WONG M L . Decomposition-based multiobjective optimization for nonlinear equation systems with many and infinitely many roots[J]. Information Sciences, 2022, 610, 605- 623.
doi: 10.1016/j.ins.2022.07.187
15 LIANG Z P , WU T C , MA X L , et al. A dynamic multiobjective evolutionary algorithm based on decision variable classification[J]. IEEE Transactions on Cybernetics, 2022, 52 (3): 1602- 1615.
doi: 10.1109/TCYB.2020.2986600
16 ZHANG K , SHEN C N , LIU X M , et al. Multiobjective evolution strategy for dynamic multiobjective optimization[J]. IEEE Transactions on Evolutionary Computation, 2020, 24 (5): 974- 988.
doi: 10.1109/TEVC.2020.2985323
17 WANG J H , LIANG G X , ZHANG J . Cooperative differential evolution framework for constrained multiobjective optimization[J]. IEEE Transactions on Cybernetics, 2018, 49 (6): 2060- 2072.
18 LUO B, ZHENG J H, XIE J L, et al. Dynamic crowding distance: a new diversity maintenance strategy for MOEAs[C]//2008 Fourth International Conference on Natural Computation. New York: IEEE, 2008: 580-585.
19 LIAO Z W , GONG W Y , WANG L , et al. A decomposition-based differential evolution with reinitialization for nonlinear equations systems[J]. Knowledge-Based Systems, 2020, 191, 105312.
doi: 10.1016/j.knosys.2019.105312
20 廖作文, 龚文引, 王凌. 基于改进环拓扑混合群体智能算法的非线性方程组多根联解[J]. 中国科学: 信息科学, 2020, 50 (3): 396- 407.
LIAO Zuowen , GONG Wenyin , WANG Ling . A hybrid swarm intelligence with improved ring topology for nonlinear equations[J]. Scientia Sinica Informationis, 2022, 50 (3): 396- 407.
21 GONG W Y , WANG Y , CAI Z H , et al. Finding multiple roots of nonlinear equation systems via a repulsion-based adaptive differential evolution[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2018, 50 (4): 1499- 1513.
[1] 房明磊,丁德凤,王敏,盛雨婷. 一种求解非线性方程组的改进Shamanskii-like Levenberg-Marquardt算法[J]. 《山东大学学报(理学版)》, 2023, 58(8): 118-126.
[2] 崔建斌,姬安召,鲁洪江,王玉风,何姜毅,许泰. Schwarz Christoffel变换数值解法[J]. 山东大学学报（理学版）, 2016, 51(4): 104-111.
[3] 王洋. 求解一类非线性方程组的Newton-PLHSS方法[J]. J4, 2012, 47(12): 96-102.
[4] 陈 蓓 . 求解Toeplitz矩阵特征值反问题的不精确牛顿方法[J]. J4, 2008, 43(9): 89-93 .
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] 江雪莲,石洪波*. 产生式与判别式组合分类器学习算法[J]. J4, 2010, 45(7): 7 -12 .
[2] 彭艳芬,李宝宗,刘天宝 . 有机气体麻醉活性的构效关系研究[J]. J4, 2006, 41(5): 148 -150 .
[3] 杨伦，徐正刚，王慧*，陈其美，陈伟，胡艳霞，石元，祝洪磊，曾勇庆*. RNA干扰沉默PID1基因在C2C12细胞中表达的研究[J]. J4, 2013, 48(1): 36 -42 .
[4] 刘艳萍,吴群英. 优化权重下高斯序列最大值几乎处处中心极限定理[J]. 山东大学学报（理学版）, 2014, 49(05): 50 -53 .
[5] 杜吉祥1,2,余庆1,翟传敏1. 基于稀疏性约束非负矩阵分解的人脸年龄估计方法[J]. J4, 2010, 45(7): 65 -69 .
[6] 戴珍香,李曙光,亓兴勤 . 波分复用星形单跳网中3信道的传输调度问题[J]. J4, 2007, 42(2): 46 -50 .
[7] 刘海英 马成刚 王志平. 刺图乘积上的Graham猜想[J]. J4, 2009, 44(8): 25 -30 .
[8] 于少伟. 基于云理论的新的不确定性推理模型研究[J]. J4, 2009, 44(3): 84 -87 .
[9] 郭 磊,于瑞林,田发中 . 一类常规跳变系统的最优控制[J]. J4, 2006, 41(1): 35 -40 .
[10] 周娟,郭卫华,宗美娟,韩雪梅,王仁卿 . 房干村不同植被下可培养细菌多样性研[J]. J4, 2006, 41(6): 161 -167 .
版权所有 © 2018 《山东大学学报(理学版)》编辑部　
地址: 山东省济南市山大南路27号山东大学中心校区（250100）　电话: +86-0531-88366917　E-mail: xblxb@sdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发