Högskolan i Skövde

Most evolutionary many-objective optimization (EMaO) algorithms start with a description of a number of the predefined set of reference points on a unit simplex. So far, most studies have used the Das and Dennis's structured approach for generating well-spaced reference points. Due to the highly structured nature of the procedure, this method cannot produce an arbitrary number of points, which is desired in an EMaO application. Although a layer-wise implementation has been suggested, EMO researchers always felt the need for a more generic approach. Motivated by earlier studies, we introduce a metric for defining well-spaced points on a unit simplex and propose a number of viable methods for generating such a set. We compare the proposed methods on a variety of performance metrics such as hypervolume (HV), deviation in triangularized simplices, distance of the closest point pair, and variance of the geometric means to nearest neighbors in up to 15-D spaces. We show that an iterative improvement based on Riesz s-energy is able to effectively find an arbitrary number of well-spaced points even in higher-dimensional spaces. Reference points created using the proposed Riesz s-energy method for a number of standard combinations of objectives and reference points as well as a source code written in Python are available publicly at https://www.egr.msu.edu/coinlab/blankjul/uniform. © 1997-2012 IEEE.

The ultimate goal of multiobjective optimization is to help a decision maker (DM) identify solution(s) of interest (SOI) achieving satisfactory tradeoffs among multiple conflicting criteria. This can be realized by leveraging DM's preference information in evolutionary multiobjective optimization (EMO). No consensus has been reached on the effectiveness brought by incorporating preference in EMO (either a priori or interactively) versus a posteriori decision making after a complete run of an EMO algorithm. Bearing this consideration in mind, this article: 1) provides a pragmatic overview of the existing developments of preference-based EMO (PBEMO) and 2) conducts a series of experiments to investigate the effectiveness brought by preference incorporation in EMO for approximating various SOI. In particular, the DM's preference information is elicited as a reference point, which represents her/his aspirations for different objectives. The experimental results demonstrate that preference incorporation in EMO does not always lead to a desirable approximation of SOI if the DM's preference information is not well utilized, nor does the DM elicit invalid preference information, which is not uncommon when encountering a black-box system. To a certain extent, this issue can be remedied through an interactive preference elicitation. Last but not the least, we find that a PBEMO algorithm is able to be generalized to approximate the whole PF given an appropriate setup of preference information.

Practical multi-criterion decision making not only involves the articulation of preferences in the objective space, but also a consideration of how the variables impact these preferences. Trend mining is a recently proposed visualization technique that offers the decision maker a quick overview of the variables' effect on the structure of the objective space and easily discover interesting variable trends. The original trend mining approach relies on a set of predefined reference directions along which an interestingness score is measured for each variable. In this paper, we relax this requirement by automating the approach to find optimal reference directions that maximize the interestingness for each variable. Additional extensions include the use of an Achievement Scalarizing Function (ASF) for ranking solutions along a given reference direction, and an updated interestingness score formulation for more appropriately handling discrete variables. We demonstrate the working of the extended approach on DTLZ2 and WFG2 benchmarks for up to five objectives and on a biobjective engineering design problem. The results show that the ability of the proposed approach to detect variable trends in high dimensional objective spaces is heavily dependent on the quality of the solutions used. 

Most of the recently proposed evolutionary many-objective optimization (EMO) algorithms start with a number of predefined reference points on a unit simplex. These algorithms use reference points to create reference directions in the original objective space and attempt to find a single representative near Pareto-optimal point around each direction. So far, most studies have used Das and Dennis’s structured approach for generating a uniformly distributed set of reference points on the unit simplex. Due to the highly structured nature of the procedure, this method does not scale well with an increasing number of objectives. In higher dimensions, most created points lie on the boundary of the unit simplex except for a few interior exceptions. Although a level-wise implementation of Das and Dennis’s approach has been suggested, EMO researchers always felt the need for a more generic approach in which any arbitrary number of uniformly distributed reference points can be created easily at the start of an EMO run. In this paper, we discuss a number of methods for generating such points and demonstrate their ability to distribute points uniformly in 3 to 15-dimensional objective spaces.

Purpose

Stochastic simulation is a popular tool among practitioners and researchers alike for quantitative analysis of systems. Recent advancement in research on formulating production systems improvement problems into multi-objective optimizations has provided the possibility to predict the optimal trade-offs between improvement costs and system performance, before making the final decision for implementation. However, the fact that stochastic simulations rely on running a large number of replications to cope with the randomness and obtain some accurate statistical estimates of the system outputs, has posed a serious issue for using this kind of multi-objective optimization in practice, especially with complex models. Therefore, the purpose of this study is to investigate the performance enhancements of a reference point based evolutionary multi-objective optimization algorithm in practical production systems improvement problems, when combined with various dynamic re-sampling mechanisms.

Design/methodology/approach

Many algorithms consider the preferences of decision makers to converge to optimal trade-off solutions faster. There also exist advanced dynamic resampling procedures to avoid wasting a multitude of simulation replications to non-optimal solutions. However, very few attempts have been made to study the advantages of combining these two approaches to further enhance the performance of computationally expensive optimizations for complex production systems. Therefore, this paper proposes some combinations of preference-based guided search with dynamic resampling mechanisms into an evolutionary multi-objective optimization algorithm to lower both the computational cost in re-sampling and the total number of simulation evaluations.

Findings

This paper shows the performance enhancements of the reference-point based algorithm, R-NSGA-II, when augmented with three different dynamic resampling mechanisms with increasing degrees of statistical sophistication, namely, time-based, distance-rank and optimal computing buffer allocation, when applied to two real-world production system improvement studies. The results have shown that the more stochasticity that the simulation models exert, the more the statistically advanced dynamic resampling mechanisms could significantly enhance the performance of the optimization process.

Originality/value

Contributions of this paper include combining decision makers’ preferences and dynamic resampling procedures; performance evaluations on two real-world production system improvement studies and illustrating statistically advanced dynamic resampling mechanism is needed for noisy models.

In Simulation-based Evolutionary Multi-objective Optimization, the number of simulation runs is very limited, since the complex simulation models require long execution times. With the help of preference information, the optimization result can be improved by guiding the optimization towards relevant areas in the objective space with, for example, the Reference Point-based NSGA-II algorithm (R-NSGA-II). Since the Pareto-relation is the primary fitness function in R-NSGA-II, the algorithm focuses on exploring the objective space with high diversity. Only after the population has converged closeto the Pareto-front does the influence of the reference point distance as secondary fitness criterion increase and the algorithm converges towards the preferred area on the Pareto-front.In this paper, we propose a set of extensions of R-NSGA-II which adaptively control the algorithm behavior, in order to converge faster towards the reference point. The adaption can be based on criteria such as elapsed optimization time or the reference point distance, or a combination thereof. In order to evaluate the performance of the adaptive extensions of R-NSGA-II, a performance metric for reference point-based EMO algorithms is used, which is based on the Hypervolume measure called the Focused Hypervolume metric. It measures convergence and diversity of the population in the preferred area around the reference point. The results are evaluated on two benchmark problems ofdifferent complexity and a simplistic production line model.

Real-world optimization problems typically involve multiple objectives to be optimized simultaneously under multiple constraints and with respect to several variables. While multi-objective optimization itself can be a challenging task, equally difficult is the ability to make sense of the obtained solutions. In this two-part paper, we deal with data mining methods that can be applied to extract knowledge about multi-objective optimization problems from the solutions generated during optimization. This knowledge is expected to provide deeper insights about the problem to the decision maker, in addition to assisting the optimization process in future design iterations through an expert system. The current paper surveys several existing data mining methods and classifies them by methodology and type of knowledge discovered. Most of these methods come from the domain of exploratory data analysis and can be applied to any multivariate data. We specifically look at methods that can generate explicit knowledge in a machine-usable form. A framework for knowledge-driven optimization is proposed, which involves both online and offline elements of knowledge discovery. One of the conclusions of this survey is that while there are a number of data mining methods that can deal with data involving continuous variables, only a few ad hoc methods exist that can provide explicit knowledge when the variables involved are of a discrete nature. Part B of this paper proposes new techniques that can be used with such datasets and applies them to discrete variable multi-objective problems related to production systems. 

The first part of this paper served as a comprehensive survey of data mining methods that have been used to extract knowledge from solutions generated during multi-objective optimization. The current paper addresses three major shortcomings of existing methods, namely, lack of interactiveness in the objective space, inability to handle discrete variables and inability to generate explicit knowledge. Four data mining methods are developed that can discover knowledge in the decision space and visualize it in the objective space. These methods are (i) sequential pattern mining, (ii) clustering-based classification trees, (iii) hybrid learning, and (iv) flexible pattern mining. Each method uses a unique learning strategy to generate explicit knowledge in the form of patterns, decision rules and unsupervised rules. The methods are also capable of taking the decision maker's preferences into account to generate knowledge unique to preferred regions of the objective space. Three realistic production systems involving different types of discrete variables are chosen as application studies. A multi-objective optimization problem is formulated for each system and solved using NSGA-II to generate the optimization datasets. Next, all four methods are applied to each dataset. In each application, the methods discover similar knowledge for specified regions of the objective space. Overall, the unsupervised rules generated by flexible pattern mining are found to be the most consistent, whereas the supervised rules from classification trees are the most sensitive to user-preferences. 

In simulation-based Evolutionary Multi-objective Optimization the number of simulation runs is very limited, since the complex simulation models require long execution times. With the help of preference information, the optimization result can be improved by guiding the optimization towards relevant areas in the objective space, for example with the R-NSGA-II algorithm [9], which uses a reference point specified by the decision maker. When stochastic systems are simulated, the uncertainty of the objective values might degrade the optimization performance. By sampling the solutions multiple times this uncertainty can be reduced. However, resampling methods reduce the overall number of evaluated solutions which potentially worsens the optimization result. In this article, a Dynamic Resampling strategy is proposed which identifies the solutions closest to the reference point which guides the population of the Evolutionary Algorithm. We apply a single-objective Ranking and Selection resampling algorithm in the selection step of R-NSGA-II, which considers the stochastic reference point distance and its variance to identify the best solutions. We propose and evaluate different ways to integrate the sampling allocation method into the Evolutionary Algorithm. On the one hand, the Dynamic Resampling algorithm is made adaptive to support the EA selection step, and it is customized to be used in the time-constrained optimization scenario. Furthermore, it is controlled by other resampling criteria, in the same way as other hybrid DR algorithms. On the other hand, R-NSGA-II is modified to rely more on the scalar reference point distance as fitness function. The results are evaluated on a benchmark problem with variable noise landscape.