面向多目标演化优化算法的可视分析框架研究

多目标优化问题是生活中常见的一类数值优化问题，存在多个需要同时优化 的目标函数。近年来，演化算法被证实为一种高效可行求解多目标优化问题的方法，通过模拟生物种群的演化过程，演化算法能在一次算法运行后得到一组较为优秀的解。然而，由于演化算法存在的黑盒特性，算法研究者和使用者在使用演化算法求解多目标优化问题时会遇到以下挑战：1）如何全面地评估算法得到的解集；2）如何理解分析单个算法的演化过程；3）如何对比分析多个算法的演化过程。针对上述挑战，已有工作中常用的数值指标和可视化方法仅能从某个特定角度对解集进行评估，无法全面刻画解集特性。此外，对于算法演化过程进行解释和对比分析的相关工作则更为欠缺。可视分析技术以交互式界面为基础，协同人脑与机器智能对数据进行推理分析，在可解释人工智能方向有深入的应用。

本文将可视分析技术应用到多目标优化中，设计实现了面向多目标演化优化算法的可视分析框架。以解决上述三个挑战为目标，本文包含三个子框架研究：

（1）为帮助用户全面地评估演化算法得到的解集，设计实现了面向单算法解集的可视分析子框架。通过调研相关论文结合专家访谈，总结了解集评估的可视分析任务。重点展示解集质量、解在目标上的权衡、决策与目标空间关系。以分析任务为指导，设计了增强平行坐标和参考集密度图等新颖可视化方法和交互。对 NSGA-II 算法在 DDMOP2 问题上解集的案例分析和专家评估确认了框架有效性。

（2）以理解分析单个算法演化过程为目标，设计实现了面向单算法演化过程的可视分析子框架。基于演化过程综述和专家访谈，得到了面向演化过程的可视分析任务。主要关注个体的代际变化和演化算子具体行为。以分析任务为指导，对演化过程进行抽象，设计了多种演化算子可视化和代际视图。通过 SMS-EMOA 算法在 DDMOP2 测试问题上演化过程的案例分析和专家评估验证了框架的实效性。

（3）以对比分析多个演化算法的演化过程为目标，设计实现了面向多算法演化过程的可视分析子框架。基于论文调研和专家访谈，概括了演化过程对比的可视分析任务。旨在找到不同算法演化过程中的相似或不同行为。以分析任务为指导，设计了基于 k 近邻的代际相似度可视化等新颖可视化方法。通过对比多算法在 DTLZ3 问题上演化过程的案例分析和专家评估证实了框架的有效性。

[1] FILIPIČ B, TUŠAR T. Visualization in Multiobjective Optimization[C]//Proceedings of the Genetic and Evolutionary Computation Conference Companion. 2019: 951-974.
[2] INSELBERG A, DIMSDALE B. Parallel Coordinates: A Tool for Visualizing Multi-Dimensional Geometry[C]//Proceedings of the IEEE Conference on Visualization. 1990: 361-378.
[3] LI M, ZHEN L, YAO X. How to Read Many-Objective Solution Sets in Parallel Coordinates [Educational Forum][J]. IEEE Computational Intelligence Magazine, 2017, 12(4): 88-100.
[4] PRYKE A, MOSTAGHIM S, NAZEMI A. Heatmap Visualization of Population Based Multi Objective Algorithms[C]//Proceedings of the International Conference on Evolutionary Multi-Criterion Optimization. 2007: 361-375.
[5] KOOOCHAKSARAEI R H, MENEGHINI I R, COELHO V N, et al. A New Visualization Method in Many-Objective Optimization with Chord Diagram and Angular Mapping[J]. Knowledge-Based Systems, 2017, 138: 134-154.
[6] HOFFMAN P, GRINSTEIN G, MARX K, et al. DNA Visual and Analytic Data Mining[C]// Proceedings of the IEEE Conference on Visualization. 1997: 437-441.
[7] IBRAHIM A, RAHNAMAYAN S, MARTIN M V, et al. 3D-RadVis: Visualization of Pareto Front in Many-Objective Optimization[C]//Proceedings of the IEEE Congress on Evolutionary Computation. 2016: 736-745.
[8] TALUKDER A K A, DEB K. PaletteViz: A Visualization Method for Functional Understanding of High-Dimensional Pareto-Optimal Data-Sets to Aid Multi-Criteria Decision Making[J]. IEEE Computational Intelligence Magazine, 2020, 15(2): 36-48.
[9] TUŠAR T, FILIPIČ B. Visualization of Pareto Front Approximations in Evolutionary Multiobjective Optimization: A Critical Review and the Prosection Method[J]. IEEE Transactions on Evolutionary Computation, 2014, 19(2): 225-245.
[10] BLASCO X, HERRERO J M, SANCHIS J, et al. A New Graphical Visualization of N-Dimensional Pareto Front for Decision-Making in Multiobjective Optimization[J]. Information Sciences, 2008, 178(20): 3908-3924.
[11] DEB K, THIELE L, LAUMANNNS M, et al. Scalable Multi-Objective Optimization Test Problems[C]//Proceedings of the IEEE Congress on Evolutionary Computation: Vol. 1. 2002: 825-830.
[12] WALKER D J, EVESON R, FIELDSEND J E. Visualizing Mutually Nondominating Solution Sets in Many-Objective Optimization[J]. IEEE Transactions on Evolutionary Computation, 2012, 17(2): 165-184.
[13] DE FREITAS A R, FLEMING P J, GUIMARAES F G. Aggregation Trees for Visualization and Dimension Reduction in Many-Objective Optimization[J]. Information Sciences, 2015, 298: 288-314.
[14] MASAFUMI Y, TOMOHIRO Y, TAKESHI F. Study on Effect of MOGA with Interactive Island Model using Visualization[C]//Proceedings of the IEEE Congress on Evolutionary Computation. 2010: 1-6.
[15] KUDO F, YOSHIKAWA T. Knowledge Extraction in Multi-Objective Optimization Problem Based on Visualization of Pareto Solutions[C]//Proceedings of the IEEE Congress on Evolutionary Computation. 2012: 1-6.
[16] VALDÉS J J, BARTON A J. Visualizing High Dimensional Objective Spaces for Multi-Objective Optimization: A Virtual Reality Approach[C]//Proceedings of the IEEE Congress on Evolutionary Computation. 2007: 4199-4206.
[17] LOWE D, TIPPING M. Neuroscale: Novel Topographic Feature Extraction using RBF Networks[C]. Advances in Neural Information Processing Systems, 1996, 9.
[18] AGRAWAL G, BLOEBAUM C, LEWIS K. Intuitive Design Selection using Visualized N-Dimensional Pareto Frontier[C]//Proceedings of the AIAA/ASME/ASCE/AHS/ASC Structures, Structural Dynamics and Materials Conference. 2005: 1813.
[19] ANG K H, CHONG G, LI Y. Visualization Technique for Analyzing Non-Dominated Set Comparison[C]//Proceedings of the Asia-Pacific Conference on Simulated Evolution and Learning: Vol. 1. 2002: 36.
[20] ODAYASHI S, SASAKI D. Visualization and Data Mining of Pareto Solutions using Self-Organizing Map[C]//Proceedings of the International Conference on Evolutionary Multi-Criterion Optimization. 2003: 796-809.
[21] WALKER D J, EVERSON R M, FIELDSEND E J. Visualisation and Ordering of Many-Objective Populations[C]//Proceedings of the IEEE Congress on Evolutionary Computation. 2010: 1-8.
[22] KOPPEN M, YOSHIDA K. Visualization of Pareto-Sets in Evolutionary Multi-Objective Optimi-zation[C]//Proceedings of the International Conference on Hybrid Intelligent Systems. 2007: 156-161.
[23] FIELDSEND J, EVERSON R. Visualising High-Dimensional Pareto Relationships in Two-Dimensional Scatterplots[C]//Proceedings of the International Conference Evolutionary Multi-Criterion Optimization. 2013: 558-572.
[24] TRAWINSKI K, CHICA M, PANCHO D P, et al. mograms: A Network-Based Methodology for Visualizing the Set of Nondominated Solutions in Multiobjective Optimization[J]. IEEE Transactions on Cybernetics, 2017, 48(2): 474-485.
[25] WALKER D J, CRAVEN M J. Identifying Good Algorithm Parameters in Evolutionary Multi-and Many-Objective Optimisation: A Visualisation Approach[J]. Applied Soft Computing, 2020, 88: 105902.
[26] DE LORENZO A, MEDVET E, TUŠAR T, et al. An Analysis of Dimensionality Reduction Techniques for Visualizing Evolution[C]//Proceedings of the Genetic and Evolutionary Computation Conference Companion. 2019: 1864-1872.
[27] BORG I, GROENEN P J. Modern Multidimensional Scaling: Theory and Applications[M]. Springer Science & Business Media, 2005.
[28] WALTER M J, WALKER D J, CRAVEN M J. Visualising Population Dynamics to Examine Algorithm Performance[J]. IEEE Transactions on Evolutionary Computation, 2022, 26(6): 1501-1510.
[29] WALTER M J, WALKER D J, CRAVEN M J. Visualising Evolution History in Multi-and Many-Objective Optimisation[C]//Proceedings of the International Conference on Parallel Problem Solving from Nature. 2020: 299-312.
[30] DE SILVA V, TENENBAUM J B. Sparse Multidimensional Scaling using Landmark Points[R]. Technical Report, Stanford University, 2004.
[31] WALTER M J, WALKER D J, CRAVEN M J. An Explainable Visualisation of the Evolutionary Search Process[C]//Proceedings of the Genetic and Evolutionary Computation Conference Companion. 2022: 1794-1802.
[32] LI K, WANG R, ZHANG T, et al. Evolutionary Many-Objective Optimization: A Comparative Study of the State-of-The-Art[J]. IEEE Access, 2018, 6: 26194-26214.
[33] ZITZLER E, THIELE L. Multiobjective Optimization using Evolutionary Algorithms - A Comparative Case Study[C]//Proceedings of the International Conference on Parallel Problem Solving from Nature. 1998: 292-301.
[34] COELLO COELLO C A, REYES SIERRA M. A Study of the Parallelization of a Coevolutionary Multi-objective Evolutionary Algorithm[C]//Proceedings of the Mexican International Conference on Artificial Intelligence. 2004: 688-697.
[35] VAN VELDHUIZEN D A, LAMONT G B, et al. Evolutionary Computation and Convergence to a Pareto Front[C]/Late Breaking Papers at the Genetic Programming. 1998: 221-228.
[36] SCHOTT J R. Fault Tolerant Design using Single and Multicriteria Genetic Algorithm Optimization[D]. Massachusetts Institute of Technology, 1995.
[37] ZITZLER E, DEB K, THIELE L. Comparison of Multiobjective Evolutionary Algorithms: Empirical Results[J]. Evolutionary Computation, 2000, 8(2): 173-195.
[38] TIAN Y, SI L, ZHANG X, et al. Evolutionary Large-Scale Multi-Objective Optimization: A Survey[J]. ACM Computing Surveys, 2021, 54(8).
[39] FALCÓN-CARDONA J G, COELLO C A C. Indicator-Based Multi-Objective Evolutionary Algorithms: A Comprehensive Survey[J]. ACM Computing Surveys, 2020, 53(2): 1-35.
[40] COELLO C A C. Evolutionary Algorithms for Solving Multi-Objective Problems[M]. Springer, 2007.
[41] DEB K, AGRAWAL R B, et al. Simulated Binary Crossover for Continuous Search Space[J]. Complex Systems, 1995, 9(2): 115-148.
[42] DEB K, BEYER H G. Self-Adaptive Genetic Algorithms with Simulated Binary Crossover[J]. Evolutionary Computation, 2001, 9(2): 197-221.
[43] KEIM D, ANDRIENKO G, FEKETE J D, et al. Visual Analytics: Definition, Process, and Challenges[M]. Springer, 2008.
[44] 陈为, 沈则潜, 陶煜波, 等. 数据可视化[M]. 电子工业出版社, 2019.
[45] MUNZNER T. A Nested Model for Visualization Design and Validation[J]. IEEE Transactions on Visualization and Computer Graphics, 2009, 15(6): 921-928.
[46] MUNZNER T. Visualization Analysis and Design[M]. CRC press, 2014.
[47] SEDLMAIR M, MEYER M, MUNZNER T. Design Study Methodology: Reflections from the Trenches and the Stacks[J]. IEEE Transactions on Visualization and Computer Graphics, 2012, 18(12): 2431-2440.
[48] ENDERT A, RIBARSKY W, TURKAY C, et al. The State of the Art in Integrating Machine Learning into Visual Analytics[J]. Computer Graphics Forum, 2017, 36(8): 458-486.
[49] HOHMAN F M, KAHNG M, PIENTA R, et al. Visual Analytics in Deep Learning: An Interrogative Survey for the Next Frontiers[J]. IEEE Transactions on Visualization and Computer Graphics, 2018, 25(8): 2674-2693.
[50] YUAN J, CHEN C, YANG W, et al. A Survey of Visual Analytics Techniques for Machine Learning[J]. Computational Visual Media, 2021, 7: 3-36.
[51] ANDRIENKO N, ANDRIENKO G, MIKSCH S, et al. A Theoretical Model for Pattern Discovery in Visual Analytics[J]. Visual Informatics, 2021, 1(1): 23-42.
[52] TZENG F Y, MA K L. Opening the Black Box - Data Driven Visualization of Neural Networks[C]. MUHLBACHER T, PIRINGER H, GRATZL S, et al. Opening the Black Box: Strategies for Increased User Involvement in Existing Algorithm Implementations[J]. IEEE Transactions on Visualization and Computer Graphics, 2019, 20(12): 1643-1652.
[53] WANG Z J, TURKO R, SHAIKH O, et al. CNN Explainer: Learning Convolutional Neural Networks with Interactive Visualization[J]. IEEE Transactions on Visualization and Computer Graphics, 2021, 27(2): 1396-1406.
[54] LIU D, CUI W, JIN K, et al. DeepTracker: Visualizing the Training Process of Convolutional Neural Networks[J]. ACM Transactions on Intelligent Systems and Technology, 2018, 10(1): 1-25.
[55] LIU M, SHI J, CAO K, et al. Analyzing the Training Processes of Deep Generative Models[J]. IEEE Transactions on Visualization and Computer Graphics, 2018, 24(1): 77-87.
[56] KAHNG M, THORAT N, HORNG D, et al. GAN Lab: Understanding Complex Deep Generative Models using Interactive Visual Experimentation[J]. IEEE Transactions on Visualization and Computer Graphics, 2019, 25(1): 310-320.
[57] GAO L, SHAO Z, LUO Z, et al. TransforLearn: Interactive Visual Tutorial for the Transformer Model[J]. IEEE Transactions on Visualization and Computer Graphics, 2024, 30(1): 891-901.
[58] JIN Z, WANG X, CHENG F, et al. ShortcutLens: A Visual Analytics Approach for Exploring Shortcuts in Natural Language Understanding Dataset[J]. IEEE Transactions on Visualization and Computer Graphics, 2023: 1-15.
[59] YEH C, CHEN Y, WU A, et al. AttentionViz: A Global View of Transformer Attention[J]. IEEE Transactions on Visualization and Computer Graphics, 2024, 30(1): 262-272.
[60] SHAO Z, SUN S, ZHAO Y, et al. Visual Explanation for Open-domain Question Answering with BERT[J]. IEEE Transactions on Visualization and Computer Graphics, 2023: 1-18.
[62] CAWLEY G C, TALBOT N L. On Over-fitting in Model Selection and Subsequent Selection Bias in Performance Evaluation[J]. The Journal of Machine Learning Research, 2010, 11: 2079-2107.
[63] RASCHKA S. Model Evaluation, Model Selection, and Algorithm Selection in Machine Learning[A]. 2018.
[64] KOTTHOFF L, THORNTON C, HOOS H H, et al. Auto-WEKA: Automatic Model Selection and Hyperparameter Optimization in WEKA[J]. Automated Machine Learning: Methods, Systems, Challenges, 2019: 81-95.
[65] ZHANG J, WANG Y, MOLINO P, et al. Manifold: A Model-Agnostic Framework for Interpretation and Diagnosis of Machine Learning Models[J]. IEEE Transactions on Visualization and Computer Graphics, 2019, 25(1): 364-373.
[66] GLEICHER M, BARVE A, YU X, et al. Boxer: Interactive Comparison of Classifier Results[J]. IEEE Transactions on Visualization and Computer Graphics, 2020, 39(3): 181-193.
[67] PISTER A, BUONO P, FEKETE J D, et al. Integrating Prior Knowledge in Mixed-Initiative Social Network Clustering[J]. IEEE Transactions on Visualization and Computer Graphics, 2021, 27(2): 1775-1785.
[68] XIE T, MA Y, KANG J, et al. FairRankVis: A Visual Analytics Framework for Exploring Algorithmic Fairness in Graph Mining Models[J]. IEEE Transactions on Visualization and Computer Graphics, 2022, 28(1): 368-377.
[69] CHOO J, LIU S. Explainable Deep Learning[J]. IEEE Computer Graphics and Applications, 2018, 38(04): 84-92.
[70] La Rosa B, BLASILLI G, BOURQUI R, et al. State of the Art of Visual Analytics for eXplainable Deep Learning[J]. Computer Graphics Forum, 2023, 42(1): 319-355.
[71] YE Y, HUANG R, ZENG W. VISAtlas: An Image-based Exploration and Query System for Large Visualization Collections via Neural Image Embedding[J]. IEEE Transactions on Visu-alization and Computer Graphics, 2022: 1-15.
[72] MURUGESAN S, MALIK S, DU F, et al. DeepCompare: Visual and Interactive Comparison of Deep Learning Model Performance[J]. IEEE Computer Graphics and Applications, 2019, 39(5): 47-59.
[73] ZENG H, HALEEM H, PLANTAZ X, et al. CNNComparator: Comparative Analytics of Convolutional Neural Networks[C]. Proceedings of the Workshop on Visual Analytics for Deep Learning. 2017.
[74] XUAN X, ZHANG X, KWON O H, et al. VAC-CNN: A Visual Analytics System for Comparative Studies of Deep Convolutional Neural Networks[J]. IEEE Transactions on Visualization and Computer Graphics, 2022, 28(6): 2326-2337.
[75] WANG Q, MING Y, JIN Z, et al. ATMSeer: Increasing Transparency and Controllability in Automated Machine Learning[C]. Proceedings of the ACM CHI Conference on Human Factors in Computing Systems. 2019: 1-12.
[76] ONO J P, CASTELO S, LOPEZ R, et al. PipelineProfiler: A Visual Analytics Tool for the Exploration of AutoML Pipelines[J]. IEEE Transactions on Visualization and Computer Graphics, 2021, 27(2): 390-400.
[77] MA Y, FAN A, HE J, et al. A Visual Analytics Framework for Explaining and Diagnosing Transfer Learning Processes[J]. IEEE Transactions on Visualization and Computer Graphics, 2021, 27(2): 1385-1395.
[78] YANG W, LI Z, LIU M, et al. Diagnosing Concept Drift with Visual Analytics[C]. IEEE Conference on Visual Analytics Science and Technology. 2020.
[79] KIM H, CHOJ J, LEE C, et al. PIVE: Per-Iteration Visualization Environment for Real-Time Interactions with Dimension Reduction and Clustering[C]. AAAI Conference on Artificial Intelligence. 2017: 1001-1009.
[80] BLACK J, DEB K. Pymoo: Multi-Objective Optimization in Python[J]. IEEE Access, 2020, 8: 89497-89509.
[81] TIAN Y, CHENG R, ZHANG X, et al. PlatEMO: A MATLAB Platform for Evolutionary Multi-Objective Optimization [Educational Forum][J]. IEEE Computational Intelligence Magazine, 2017, 12(4): 73-87.
[82] VAN DER MAATEN L, HINTON G. Visualizing Data using t-SNE.[J]. Journal of Machine Learning Research, 2008, 9(11).
[83] MCINNES L, HEALY J, MELVILLE J. UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction[A]. 2018.
[84] LIU S, MALJOVEC D, WANG B, et al. Visualizing High-Dimensional Data: Advances in the Past Decade[J]. IEEE Transactions on Visualization and Computer Graphics, 2016, 23(3): 1249-1268.
[85] CAMPELLO R J, MOULAVI D, SANDER J. Density-Based Clustering Based on Hierarchical Density Estimates[C]. Pacific-Asia Conference on Knowledge Discovery and Data Mining. 2013: 160-172.
[86] BOSTOCK M, OGIEVETSYY V, HEER J. D3: Data-Driven Documents[J]. IEEE Transactions on Visualization and Computer Graphics, 2011, 17(12): 2301-2309.
[87] HE C, TIAN Y, WANG H, et al. A Repository of Real-World Datasets for Data-Driven Evolutionary Multiobjective Optimization[J]. Complex & Intelligent Systems, 2020, 6(1): 189-197.
[88] DEB K, PRATAP A, AGARWAL S, et al. A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197.
[89] ZHANG Q, LI H. MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition[J]. IEEE Transactions on Evolutionary Computation, 2007, 11(6): 712-731.
[90] BEUME N, NAUJOKS B, EMMERICH M. SMS-EMOA: Multiobjective Selection Based on Dominated Hypervolume[J]. European Journal of Operational Research, 2007, 181(3): 1653-1669.
[91] GLEICHER M. Considerations for Visualizing Comparison[J]. IEEE Transactions on Visualization and Computer Graphics, 2018, 24(1): 413-423.
[92] Shneiderman B. The Eyes Have it: A Task by Data Type Taxonomy for Information Visualizations[C]. IEEE Symposium on Visual Languages. 1996: 336-343.
[93] MÜLLER M. Dynamic Time Warping[J]. Information Retrieval for Music and Motion, 2007: 69-84.
[94] KAMADA T, KAWAI S. An Algorithm for Drawing General Undirected Graphs[J]. Information Processing Letters, 1989, 31(1): 7-15.
[95] MCINNES L, HEALY J, ASTELS S, et al. HDBSCAN: Hierarchical Density Based Clustering[J]. J. Open Source Softw., 2017, 2(11): 205.
[96] LIU S, XIAO J, JIANG J, et al. Visual Diagnosis of Tree Boosting Methods[J]. IEEE Transactions on Visualization and Computer Graphics, 2017, 24(1): 163-173.
[97] YUAN J, XIANG S, XIA J, et al. Evaluation of Sampling Methods for Scatterplots[J]. IEEE Transactions on Visualization and Computer Graphics, 2021, 27(2): 1720-1730.
[98] BREUNIG M M, KRIEGEL H P, NG R T, et al. LOF: Identifying Density-Based Local Outliers[C]. Proceedings of the ACM SIGMOD International Conference on Management of Data. 2000: 93-104.
[99] YUAN Y, XU H, WANG B, et al. A New Dominance Relation-Based Evolutionary Algorithm for Many-Objective Optimization[J]. IEEE Transactions on Evolutionary Computation, 2015, 19(1): 16-37.
[100] TIAN Y, HE C, CHENG R, et al. A Multistage Evolutionary Algorithm for Better Diversity Preservation in Multiobjective Optimization[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2019, 51(9): 5880-5894.
[101] YANG X, ZOU J, JANG S, et al. A Fuzzy Decision Variables Framework For Large-Scale Multiobjective Optimization[J]. IEEE Transactions on Evolutionary Computation, 2021, 27 (3): 445-459.
[102] DEB K, JAIN H. An Evolutionary Many-Objective Optimization Algorithm using Reference-Point-Based Nondominated Sorting Approach, Part I: Solving Problems with Box Constraints[J]. IEEE Transactions on Evolutionary Computation, 2013, 18(4): 577-601.
[103] XIANG Y, ZHOU Y, LI M, et al. A Vector Angle-Based Evolutionary Algorithm for Unconstrained Many-Objective Optimization[J]. IEEE Transactions on Evolutionary Computation, 2016, 21(1): 131-152.