Prediction of Pareto Dominance Using Nearest Neighbor Method Based on Decision Space Transformation
-
摘要: 为提高在决策空间运用最近邻方法预测多目标优化Pareto支配性的精度，提出一种基于决策空间变换的最近邻预测方法.在分析目标函数与决策分量相关性的基础上，提出属性变化趋势模型的构造方法，建立低计算成本的属性趋势代理模型.通过属性趋势模型引入决策空间到目标空间的映射知识，对多目标问题的决策空间进行变换，使决策空间的最近邻更有效反映目标空间的最近邻.选取具有不同相关系数特征的典型多目标优化问题，进行Pareto支配性预测的可对比实验，结果表明在新空间中运用最近邻方法可显著提高分类准确性.Abstract: In this paper, nearest neighbor prediction is used to decide Pareto dominance of candidate solutions in expensive multi-objective optimization. For improving the accuracy of predicting Pareto dominance in decision space, a transformation method of decision space is proposed. Based on correlation analysis of objective functions and decision attributes, computationally efficient attribute tendency models of objective functions are set up. These models are used to re-construct the decision space such that the knowledge of objective space is introduced and the neighborhood relation in decision space can more effectively reflect that in the original objective space. Experiments of Pareto dominance prediction are carried out on a group of typical multi-objective optimization problems. The results indicate that the prediction of Pareto dominance using the proposed method is more accurate and efficient than the existing methods.
-
Key words:
- Tendency model /
- space transformation /
- nearest neighbor method /
- Pareto dominance
-
-
图 1 决策空间的线性化过程(圆点表示原样本点的分布, 三角表示经过趋势模型$y=g (x_i)$映射后的样本点
Fig. 1 The linearization process of decision space (Circles are the original sample points and triangles are the mapped sample points by the trend model $y=g (x_i)$.)
表 1 测试函数的决策属性与目标属性的相关系数
Table 1 Correlation coefficient of decision attribute and objective attribute of test function
测试函数 f1 (x) f2 (x) f3 (x) ZDT1 n=10 (1, 0, 0, 0, …) (-0.59, 0.27, 0.27, 0.27, …) n=30 (1, 0, 0, 0, …) (-0.79, 0.11, 0.11, 0.11, …) ZDT3 n=3 (1, 0, 0) (-0.28, 0.65, 0.65) n=10 (1, 0, 0, 0, …) (-0.49, 0.25, 0.25, …) ZDT6 n=3 (0.47, 0, 0) (0.02, 0.69, 0.69) n=10 (0.48, 0, 0, 0, …) (0.02, 0.69, 0.69) KUR n=3 (0.02, 0, -0.01) (0.02, 0.02, 0.02) UF1 n=15 (0.92, 0, -0.07, 0, -0.07, 0, …) (-0.51, -0.11, 0, -0.12, …) DTLZ2 n=10 (-0.64, -0.64, 0.01, -0.01, …) (-0.64, 0.64, 0.01, 0.01, …) (0.94, 0, 0, 0.01, 0, …) DTLZ4 n=10 (-0.64, -0.64, 0.01, -0.01, …) (-0.64, 0.64, 0.01, 0, -0.01, …) (0.94, -0.01, 0, 0.01, 0, …) 
下载: 导出CSV
表 2 变换前后的最近邻分类误差
Table 2 Nearest neighbor classification error before and after transformation
测试函数 按目标分类的误差均值 按目标分类的最大误差 f1 (x) f2 (x) f3 (x) f1 (x) f2 (x) f3 (x) ZDT1 原空间 0.1516 0.4302 0.5115 1.3159 变换后 0.0013 0.1725 0.0074 0.9304 ZDT3 原空间 0.0437 0.446 0.1837 1.7126 变换后 0.0011 0.3282 0.0042 1.5289 ZDT6 原空间 0.1047 0.1873 0.6864 1.8303 变换后 0.0031 0.0765 0.0454 0.4374 KUR 原空间 0.6601 5.7885 2.2948 23.423 变换后 0.2909 1.6843 1.6411 4.6841 UF1 原空间 0.1985 0.1753 0.8847 1.0659 变换后 0.0753 0.068 0.2736 0.4554 DTLZ2 原空间 0.2314 0.2368 0.2344 1.0053 0.8732 1.0964 变换后 0.0624 0.0569 0.0471 0.3102 0.1942 0.199 DTLZ4 原空间 0.2072 0.2431 0.2459 0.8283 0.7537 0.895 变换后 0.0582 0.0724 0.0488 0.2478 0.2178 0.0488
下载: 导出CSV
表 3 Pareto支配性预测的平均精度
Table 3 Average precision of Pareto dominance prediction
测试函数 方法 n Pareto支配性(%) 总体正确 非支配类 支配类 不可比类 ZDT1 DSTNN 10 92.32 81.7 88.61 96.64 ENNC 64.79 40.58 42.3 74.88 ESNNC 83.23 70.32 75.24 88.31 GP 88.76 65.55 65.55 90.21 DSTNN 30 90.85 71.2 81.51 95.2 ENNC 54.32 17.36 23.26 63.41 ESNNC 68.9 37.49 40.28 80.54 GP 73.41 32.97 32.97 84.49 ZDT3 DSTNN 3 93.13 80.47 93.14 97.19 ENNC 76.84 75.54 69.03 79.2 ESNNC 68.82 56.95 68.85 72.26 GP 57.73 54.6 54.6 59.48 DSTNN 10 83.29 71.53 77.56 88.69 ENNC 59.33 34.81 38.61 70.03 ESNNC 77.86 72.05 66.85 84.12 GP 71.1 54.2 54.2 78.56 ZDT6 DSTNN 3 95.94 89.83 95.59 99.36 ENNC 53.68 42.23 48.88 55.9 ESNNC 49.78 43.06 49.49 52.97 GP 52.96 36.92 36.92 66.89 DSTNN 10 91.43 87.77 93.58 92.33 ENNC 44.3 37.8 47.55 46.1 ESNNC 64.86 66.12 60.53 66.44 GP 48.88 47.03 47.03 50.82 DTLZ2 DSTNN 10 86.49 43.89 66.87 89.66 ENNC 54.89 17.24 17.42 58.87 ESNNC 90.92 22.68 28.41 95.31 GP 89.5 12 12 96.75 DTLZ4 DSTNN 10 85.39 50.14 74.64 88.55 ENNC 53.74 16.93 20.42 57.23 ESNNC 72.23 48.38 44.56 79.99 GP 70.87 9.51 9.51 76.65 UF1 DSTNN 10 86.14 71.9 84.17 91.64 ENNC 60.08 54.86 50.23 65.76 ESNNC 60.84 65.23 70.69 71.49 GP 57.7 61.53 61.53 51.61 KUR DSTNN 3 85.43 79.73 86.79 89.87 ENNC 46.47 53.95 56.71 34.54 ESNNC 50.73 52.88 55.39 45.02 GP 44.19 41.79 41.79 47.76
下载: 导出CSV
-
[1] 公茂果, 焦李成, 杨咚咚, 马文萍.进化多目标优化算法研究.软件学报, 2009, 20(2):271-289 doi: 10.3724/SP.J.1001.2009.00271Gong Mao-Guo, Jiao Li-Cheng, Yang Dong-Dong, Ma Wen-Ping. Research on evolutionary multi-objective optimization algorithms. Journal of Software, 2009, 20(2):271-289 doi: 10.3724/SP.J.1001.2009.00271 [2] 詹炜.求解高维多目标优化问题的流形学习算法研究[博士学位论文], 中国地质大学, 中国, 2013.Zhan Wei. Research on Manifold Learning Algorithm for High-Dimensional Multi-objective Optimization Problems[Ph.D. dissertation], China University of Geosciences, China, 2013. [3] Tesch M, Schneider J, Choset H. Expensive multiobjective optimization for robotics. In:Proceedings of the 2013 IEEE International Conference on Robotics and Automation. Karlsruhe, Germany:IEEE, 2013. 973-980 [4] Douguet D. e-LEA3D:a computational-aided drug design web server. Nucleic Acids Research, 2010, 38(Suppl 2):W615-W621 https://www.researchgate.net/publication/44575457_e-LEA3D_A_computational-aided_drug_design_web_server [5] Zhang Q F, Liu W D, Tsang E, Virginas B. Expensive multiobjective optimization by MOEA/D with Gaussian process model. IEEE Transactions on Evolutionary Computation, 2010, 14(3):456-474 doi: 10.1109/TEVC.2009.2033671 [6] Palar P S, Tsuchiya T, Parks G T. A comparative study of local search within a surrogate-assisted multi-objective memetic algorithm framework for expensive problems. Applied Soft Computing Journal, 2016, 43:1-19 doi: 10.1016/j.asoc.2015.12.039 [7] Rosales-Pérez A, Coello C A C, Gonzalez J A, Reyes-Garcia C A, Escalante H J. A hybrid surrogate-based approach for evolutionary multi-objective optimization. In:Proceedings of the 2013 IEEE Congress on Evolutionary Computation (CEC). Cancun, Mexico:IEEE, 2013. 2548-2555 [8] Akhtar T, Shoemaker C A. Multi objective optimization of computationally expensive multi-modal functions with RBF surrogates and multi-rule selection. Journal of Global Optimization, 2016, 64(1):17-32 doi: 10.1007/s10898-015-0270-y [9] Montemayor-García G, Toscano-Pulido G. A study of surrogate models for their use in multiobjective evolutionary algorithms. In:Proceedings of the 8th International Conference on Electrical Engineering Computing Science and Automatic Control (CCE). Merida, Mexico:IEEE, 2011. 1-6 [10] Guo G Q, Li W, Yang B, Li W B, Yin C. Predicting Pareto dominance in multi-objective optimization using pattern recognition. In:Proceedings of the 2nd International Conference on Intelligent System Design and Engineering Application (ISDEA). Sanya, China:IEEE, 2012. 456-459 [11] Guo G Q, Yin C, Yan T S, Li W. Nearest neighbor classification of Pareto dominance in multi-objective optimization. In:Proceedings of the 5th International Conference on Advanced Computational Intelligence (ICACI). Nanjing, China:IEEE, 2012. 328-331 [12] 郭观七, 尹呈, 曾文静, 李武, 严太山.基于等价分量交叉相似性的Pareto支配性预测.自动化学报, 2014, 40(1):33-40 http://www.aas.net.cn/CN/abstract/abstract18264.shtmlGuo Guan-Qi, Yin-Cheng, Zeng Wen-Jing, Li Wu, Yan Tai-Shan. Prediction of Pareto dominance by cross similarity of equivalent components. Acta Automatica Sinica, 2014, 40(1):33-40 http://www.aas.net.cn/CN/abstract/abstract18264.shtml [13] 陈志旺, 白锌, 杨七, 黄兴旺, 李国强.区间多目标优化中决策空间约束、支配及同序解筛选策略.自动化学报, 2015, 41(12):2115-2124 http://www.aas.net.cn/CN/abstract/abstract18784.shtmlChen Zhi-Wang, Bai Xin, Yang Qi, Huang Xing-Wang, Li Guo-Qiang. Strategy of constraint, dominance and screening solutions with same sequence in decision space for interval multi-objective optimization. Acta Automatica Sinica, 2015, 41(12):2115-2124 http://www.aas.net.cn/CN/abstract/abstract18784.shtml [14] 盛骤, 谢式千, 潘承毅.概率论与数理统计.北京:高等教育出版, 2005.Sheng Zhou, Xie Shi-Qian, Pan Cheng-Yi. Probability and Mathematical Statistics. Beijing:Higher Education Press, 2005. [15] 田作华, 陈学中, 翁正新.工程控制基础.北京:清华大学出版社, 2007.Tian Zuo-Hua, Chen Xue-Zhong, Weng Zheng-Xin. Control Engineering Construction. Beijing:Tsinghua University Press, 2007. [16] Zitzler E, Deb K, Thiele L. Comparison of multiobjective evolutionary algorithms:empirical results. Evolutionary Computation, 2000, 8(2):173-195 doi: 10.1162/106365600568202 [17] Kursawe F. A variant of evolution strategies for vector optimization. Parallel Problem Solving from Nature. Berlin:Springer, 1991. [18] Deb K, Thiele L, Laumanns M, Zitzler E. Scalable multi-objective optimization test problems. In:Proceedings of the 2002 IEEE Congress on Evolutionary Computation (CEC). Honolulu, USA:IEEE, 2002. 825-830 [19] Li H, Zhang Q F. Multiobjective optimization problems with complicated Pareto sets, MOEA/D and NSGA-II. IEEE Transactions on Evolutionary Computation, 2009, 13(2):284-302 doi: 10.1109/TEVC.2008.925798 期刊类型引用(29)
1. 李倩，聂简，黄鸿殿，孔庆宇，奔粤阳. 基于大脑海马认知机理的主从式AUV协同定位方法. 中国惯性技术学报. 2024(01): 27-33 . 
百度学术2. 游雄，李科，田江鹏，杨剑，余岸竹，贾奋励. 机器地图信息加工模型. 武汉大学学报(信息科学版). 2024(04): 516-526 . 百度学术3. 高昊，王仁茂. 基于类脑仿生的环境感知技术. 舰船电子对抗. 2024(05): 42-46+55 . 百度学术4. 陈荟慧，钟委钊. 基于人机协作的高质量城市图像采集方法. 应用科学学报. 2023(05): 801-814 . 百度学术5. 朱祥维，沈丹，肖凯，马岳鑫，廖祥，古富强，余芳文，高柯夫，刘经南. 类脑导航的机理、算法、实现与展望. 航空学报. 2023(19): 6-38 . 百度学术6. 于乃功，廖诣深. 基于鼠脑内嗅—海马认知机制的移动机器人空间定位模型. 生物医学工程学杂志. 2022(02): 217-227 . 百度学术7. 刘溢，阳加远，张驰. 一种基于RTX的移动机器人实时控制平台. 电子技术与软件工程. 2022(08): 169-172 . 百度学术8. 于子航，王改云. 基于路径积分强化的机器人目标导向运动控制. 计算机仿真. 2022(07): 412-415+516 . 百度学术9. 董卫华，刘毅龙，黑巧松，杨天宇. 泛地图空间认知理论与方法研究框架. 武汉大学学报(信息科学版). 2022(12): 2007-2014 . 百度学术10. 阮晓钢，李鹏，朱晓庆，刘鹏飞. 基于目标导向行为和空间拓扑记忆的视觉导航方法. 计算机学报. 2021(03): 594-608 . 百度学术11. 赵辰豪，吴德伟，韩昆，代传金. 无环境信息下多尺度网格细胞群空间表征模型. 系统工程与电子技术. 2021(03): 814-822 . 百度学术12. 阮晓钢，柴洁，武悦，张晓平，黄静. 基于海马体位置细胞的认知地图构建与导航. 自动化学报. 2021(03): 666-677 . 本站查看13. 冀俊忠，刘金铎，邹爱笑，杨翠翠. 一种融合多源信息的脑效应连接网络蚁群学习算法. 自动化学报. 2021(04): 864-881 . 本站查看14. 万刚，武易天. 地图空间认知的数学基础. 测绘学报. 2021(06): 726-738 . 百度学术15. 洪涛，史涛，任红格. 一种改进型RatSLAM算法构建认知地图的研究. 现代计算机. 2021(21): 47-52 . 百度学术16. 韩昆，吴德伟，来磊. 类脑导航中基于差分Hebbian学习的网格细胞构建模型. 系统工程与电子技术. 2020(03): 674-679 . 百度学术17. 黄宜庆，王正刚，王徽，葛愿. 基于边缘梯度算法的多移动机器人协作地图构建. 信息与控制. 2020(01): 62-68 . 百度学术18. 于乃功，廖诣深，郑相国. 一种基于海马位置细胞选择机制的空间认知模型. 生物医学工程学杂志. 2020(01): 27-37 . 百度学术19. 胡小平，毛军，范晨，张礼廉，何晓峰，韩国良，范颖. 仿生导航技术综述. 导航定位与授时. 2020(04): 1-10 . 百度学术20. 于乃功，冯慧，廖诣深，郑相国. 一种基于感知速度与感知角度的网格野计算模型. 生物医学工程学杂志. 2020(05): 863-874 . 百度学术21. 晁丽君，熊智，杨闯，华冰，王雅婷，刘建业. 无人飞行器三维类脑SLAM自主导航方法. 飞控与探测. 2020(05): 35-43 . 百度学术22. 张孝伍. 图上的概率分布及位置方向信息的表征方法. 青岛理工大学学报. 2019(01): 113-121 . 百度学术23. 方略，何洪军. 基于鼠脑海马位置细胞与Q学习面向目标导航. 生物信息学. 2019(01): 31-38 . 百度学术24. 王均，凌有铸，王静. 基于特征融合的仿生SLAM算法研究. 安徽工程大学学报. 2019(02): 26-33 . 百度学术25. 刘建业，杨闯，熊智，赖际舟，熊骏. 无人机类脑吸引子神经网络导航技术. 导航定位与授时. 2019(05): 52-60 . 百度学术26. 韩昆，吴德伟，来磊，杨林. 自主导航条件下网格细胞放电模型. 电子科技大学学报. 2019(05): 711-716 . 百度学术27. 丛明，邹强，刘冬，杜宇. 定位细胞认知机理启发的机器人导航研究综述. 机械工程学报. 2019(23): 1-12 . 百度学术28. 邹强，丛明，刘冬，杜宇. 仿鼠脑海马的机器人地图构建与路径规划方法. 华中科技大学学报(自然科学版). 2018(12): 83-88 . 百度学术29. 吴德伟，何晶，韩昆，李卉. 无人作战平台认知导航及其类脑实现思想. 空军工程大学学报(自然科学版). 2018(06): 33-38 . 百度学术其他类型引用(29)
-
图(1) / 表(3)
计量
- 文章访问数: 1992
- HTML全文浏览量: 218
- PDF下载量: 724
- 被引次数: 58
