دانلود رایگان ترجمه مقاله تجسم (دیداری سازی) و متریک عملکرد در بهینه سازی چند منظوره (نشریه IEEE 2015)

تجسم (دیداری سازی) و متریک عملکرد در بهینه سازی چند منظوره

Visualization and Performance Metric in Many-Objective Optimization

Abstract

Visualization of population in a high-dimensional objective space throughout the evolution process presents an attractive feature that could be well exploited in designing many-objective evolutionary algorithms (MaOEAs). In this paper, a new visualization method is proposed. It maps individuals from a high-dimensional objective space into a 2-D polar coordinate plot while preserving Pareto dominance relationship, retaining shape and location of the Pareto front, and maintaining distribution of individuals. From it, a decision-maker can observe the evolution process, estimate location, range, and distribution of Pareto front, assess quality of the approximated front and tradeoff between objectives, and easily select preferred solutions. Furthermore, its applications can be scalable to any dimensions, handle a large number of individuals on front, and simultaneously visualize multiple fronts for comparison. Based on this visualization tool, a performance metric, named polar-metric, is designed. The convergence of the approximate front is measured by radial values of all population members on that front. Meanwhile, the diversity performance is mainly determined by niche count of each subregion in a high-dimensional objective space. Experimental results show that it can provide a comprehensive and reliable comparison among MaOEAs.

۱ Introduction

MANY real-world multiobjective optimization problems (MOPs) involve more than three conflicting objectives, which are commonly referred to as many-objective optimization problems (MaOPs). Visualization of population in a high-dimensional objective space throughout the evolution process presents an opportunity that could be well exploited in designing many-objective evolutionary algorithms (MaOEAs). High-quality visualization tools can provide accurate shape, location, and range of the approximate Pareto front, reflect tradeoffs between objectives, observe the evolution process, assess the quality of the approximated front, and help decisionmakers select their preferred solutions [1]. In low-dimensional spaces with two or three objectives, scatter plot shows the location, distribution, and shape of the obtained approximate front, where each axis directly represents one objective. From scatter plot, a decision-maker can easily make choices and select preferred solutions if so desired. However, due to the curse of dimensionality, it is no longer an option in high-dimensional objective spaces.

Naturally, we thought about developing strategies to reduce the number of objectives while preserving as much information of all objectives as possible. If the number of objectives is reduced to be two or three, then we can easily visualize the approximate Pareto front by a scatter plot. For instance, Brockhoff and Zitzler [2] first identified conflict and nonconflict relationships between each pair of objectives and then combine nonconflicting objectives into one objective. Saxena et al. [3] presented a principal component analysis and maximum variance unfolding based framework for linear and nonlinear objective reduction algorithms, respectively. Lygoe et al. [4] exploited local harmony between objectives to reduce dimensionality by clustering the Pareto-optimal front and apply a rule-based principal component analysis including preference articulation for potential objective reduction. However, there are many problems whose objectives cannot be further reduced. Moreover, in some problems, eliminating a very small number of objectives does not help for visualization.

In this paper, there are many visualization approaches designed for viewing high-dimensional data. The first type of methods, including various forms of parallel coordinates [5] and heatmaps [6], represents each high-dimensional solution on a parallel coordinate system. For an M-dimensional objective space, the whole parallel coordinate system contains M parallel axes, each of which corresponds to one objective. This method can only retain the original objective values of solutions. In order to provide information about the tradeoff relationships between objectives for a decision-maker, it requires the objectives of interest to be positioned adjacent to each other. However, the number of comparisons among different adjacent objectives would grow exponentially with the number of objectives. In addition, it is not able to show the contour information of a given approximate Pareto front [1]. The second type of methods, including Buddle chart [7], radial coordinate visualization (RadViz) [8], self-organizing maps (SOMs) [9], Sammon mapping [10], and neuroscale [11], constructs the mapping from a highdimensional objective space into a 2-D space while preserving local distances between each pair of solutions in a highdimensional space. From the 2-D space, decision-makers can easily determine their preferred solutions. However, these mapping approaches often inadvertently lose some critical information in the mapped 2-D space. Furthermore, in the mapped 2-D space, it is still not intuitive to discover the shape of the approximate front and tradeoffs between objectives. Based on the above discussions, it remains difficult to visualize Pareto front approximations using present technologies. An effective visualization method is needed to provide accurate and comprehensive information for the approximate Pareto front in high-dimensional objective spaces.

On the other hand, there is no performance metric specifically designed for comparison of MaOEAs in highdimensional MaOPs. In this paper, there are many effective performance metrics used to compare multiobjective evolutionary algorithms (MOEAs) in low-dimensional MOPs. Most of these metrics are originally designed for low-dimensional problems. Even so, Okabe et al. [12] have showed that many metrics may fail to truly reflect the quality of solution sets and some metrics work only for bi-objective optimization problems. When comes to high-dimensional objective spaces, these metrics cannot perform faithfully as in the low-dimensional spaces. In [13], we have applied an ensemble method for comparison of MaOEAs as any performance metric alone cannot quantify the performance of an MaOEA comprehensively. Although this ensemble method has shown its powerful ability in providing a comprehensive measure, it still uses multiple metrics mainly designed for low-dimensional MOPs. Therefore, in high-dimensional objective space, performance metric ensemble based on existing performance metrics cannot provide convincing comparison results. There still needs a comprehensive study to reveal the strengths and weaknesses of the underlying MaOEAs.