| 1. |
- Andersson, Martin, 1981-
(författare)
-
A bilevel approach to parameter tuning of optimization algorithms using evolutionary computing : Understanding optimization algorithms through optimization
- 2018
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Most optimization problems found in the real world cannot be solved using analytical methods. For these types of difficult optimization problems, an alternative approach is needed. Metaheuristics are a category of optimization algorithms that do not guarantee that an optimal solution will be found, but instead search for the best solutions using some general heuristics. Metaheuristics have been shown to be effective at finding “good-enough” solutions to a wide variety of difficult problems. Most metaheuristics involve control parameters that can be used to modify how the heuristics perform its search. This is necessary because different problems may require different search strategies to be solved effectively. The control parameters allow for the optimization algorithm to be adapted to the problem at hand. It is, however, difficult to predict what the optimal control parameters are for any given problem. The problem of finding these optimal control parameter values is known as parameter tuning and is the main topic of this thesis. This thesis uses a bilevel optimization approach to solve parameter tuning problems. In this approach, the parameter tuning problem itself is formulated as an optimization problem and solved with an optimization algorithm. The parameter tuning problem formulated as a bilevel optimization problem is challenging because of nonlinear objective functions, interacting variables, multiple local optima, and noise. However, it is in precisely this kind of difficult optimization problem that evolutionary algorithms, which are a subclass of metaheuristics, have been shown to be effective. That is the motivation for using evolutionary algorithms for the upper-level optimization (i.e. tuning algorithm) of the bilevel optimization approach. Solving the parameter tuning problem using a bilevel optimization approach is also computationally expensive, since a complete optimization run has to be completed for every evaluation of a set of control parameter values. It is therefore important that the tuning algorithm be as efficient as possible, so that the parameter tuning problem can be solved to a satisfactory level with relatively few evaluations. Even so, bilevel optimization experiments can take a long time to run on a single computer. There is, however, considerable parallelization potential in the bilevel optimization approach, since many of the optimizations are independent of one another. This thesis has three primary aims: first, to present a bilevel optimization framework and software architecture for parallel parameter tuning; second, to use this framework and software architecture to evaluate and configure evolutionary algorithms as tuners and compare them with other parameter tuning methods; and, finally, to use parameter tuning experiments to gain new insights into and understanding of how optimization algorithms work and how they can used be to their maximum potential. The proposed framework and software architecture have been implemented and deployed in more than one hundred computers running many thousands of parameter tuning experiments for many millions of optimizations. This illustrates that this design and implementation approach can handle large parameter tuning experiments. Two types of evolutionary algorithms, i.e. differential evolution (DE) and a genetic algorithm (GA), have been evaluated as tuners against the parameter tuning algorithm irace. The as pects of algorithm configuration and noise handling for DE and the GA as related to the parameter tuning problem were also investigated. The results indicate that dynamic resampling strategies outperform static resampling strategies. It was also shown that the GA needs an explicit exploration and exploitation strategy in order not become stuck in local optima. The comparison with irace shows that both DE and the GA can significantly outperform it in a variety of different tuning problems.
|
|
| 2. |
- Bandaru, Sunith, et al.
(författare)
-
Data mining methods for knowledge discovery in multi-objective optimization : Part A - Survey
- 2017
-
Ingår i: Expert systems with applications. - : Elsevier. - 0957-4174 .- 1873-6793. ; 70, s. 139-159
-
Forskningsöversikt (refereegranskat)abstract
- 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.
|
|
| 3. |
- Bandaru, Sunith, et al.
(författare)
-
Data mining methods for knowledge discovery in multi-objective optimization : Part B - New developments and applications
- 2017
-
Ingår i: Expert systems with applications. - : Elsevier. - 0957-4174 .- 1873-6793. ; 70, s. 119-138
-
Tidskriftsartikel (refereegranskat)abstract
- 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.
|
|
| 4. |
- Bandaru, Sunith, et al.
(författare)
-
Development, analysis and applications of a quantitative methodology for assessing customer satisfaction using evolutionary optimization
- 2015
-
Ingår i: Applied Soft Computing. - : Elsevier. - 1568-4946 .- 1872-9681. ; 30, s. 265-278
-
Tidskriftsartikel (refereegranskat)abstract
- Consumer-oriented companies are getting increasingly more sensitive about customer's perception of their products, not only to get a feedback on their popularity, but also to improve the quality and service through a better understanding of design issues for further development. However, a consumer's perception is often qualitative and is achieved through third party surveys or the company's recording of after-sale feedback through explicit surveys or warranty based commitments. In this paper, we consider an automobile company's warranty records for different vehicle models and suggest a data mining procedure to assign a customer satisfaction index (CSI) to each vehicle model based on the perceived notion of the level of satisfaction of customers. Based on the developed CSI function, customers are then divided into satisfied and dissatisfied customer groups. The warranty data are then clustered separately for each group and analyzed to find possible causes (field failures) and their relative effects on customer's satisfaction (or dissatisfaction) for a vehicle model. Finally, speculative introspection has been made to identify the amount of improvement in CSI that can be achieved by the reduction of some critical field failures through better design practices. Thus, this paper shows how warranty data from customers can be utilized to have a better perception of ranking of a product compared to its competitors in the market and also to identify possible causes for making some customers dissatisfied and eventually to help percolate these issues at the design level. This closes the design cycle loop in which after a design is converted into a product, its perceived level of satisfaction by customers can also provide valuable information to help make the design better in an iterative manner. The proposed methodology is generic and novel, and can be applied to other consumer products as well.
|
|
| 5. |
- Bandaru, Sunith, et al.
(författare)
-
Generalized higher-level automated innovization with application to inventory management
- 2015
-
Ingår i: European Journal of Operational Research. - : Elsevier. - 0377-2217 .- 1872-6860. ; 243:2, s. 480-496
-
Tidskriftsartikel (refereegranskat)abstract
- This paper generalizes the automated innovization framework using genetic programming in the context of higher-level innovization. Automated innovization is an unsupervised machine learning technique that can automatically extract significant mathematical relationships from Pareto-optimal solution sets. These resulting relationships describe the conditions for Pareto-optimality for the multi-objective problem under consideration and can be used by scientists and practitioners as thumb rules to understand the problem better and to innovate new problem solving techniques; hence the name innovization (innovation through optimization). Higher-level innovization involves performing automated innovization on multiple Pareto-optimal solution sets obtained by varying one or more problem parameters. The automated innovization framework was recently updated using genetic programming. We extend this generalization to perform higher-level automated innovization and demonstrate the methodology on a standard two-bar bi-objective truss design problem. The procedure is then applied to a classic case of inventory management with multi-objective optimization performed at both system and process levels. The applicability of automated innovization to this area should motivate its use in other avenues of operational research.
|
|
| 6. |
- Bandaru, Sunith, et al.
(författare)
-
Metaheuristic Techniques
- 2017
-
Ingår i: Decision Sciences. - Boca Raton : CRC Press. - 9781466564305 - 9781482282566 ; , s. 693-750
-
Bokkapitel (refereegranskat)
|
|
| 7. |
- Bandaru, Sunith, et al.
(författare)
-
On the Performance of Classification Algorithms for Learning Pareto-Dominance Relations
- 2014
-
Ingår i: Proceedings of the 2014 IEEE Congress on Evolutionary Computation (CEC). - : IEEE Press. - 9781479914883 - 9781479966264 ; , s. 1139-1146
-
Konferensbidrag (refereegranskat)abstract
- Multi-objective evolutionary algorithms (MOEAs)are often criticized for their high-computational costs. Thisbecomes especially relevant in simulation-based optimizationwhere the objectives lack a closed form and are expensive toevaluate. Over the years, meta-modeling or surrogate modelingtechniques have been used to build inexpensive approximationsof the objective functions which reduce the overall number offunction evaluations (simulations). Some recent studies however,have pointed out that accurate models of the objective functionsmay not be required at all since evolutionary algorithms onlyrely on the relative ranking of candidate solutions. Extendingthis notion to MOEAs, algorithms which can ‘learn’ Paretodominancerelations can be used to compare candidate solutionsunder multiple objectives. With this goal in mind, in thispaper, we study the performance of ten different off-the-shelfclassification algorithms for learning Pareto-dominance relationsin the ZDT test suite of benchmark problems. We considerprediction accuracy and training time as performance measureswith respect to dimensionality and skewness of the training data.Being a preliminary study, this paper does not include results ofintegrating the classifiers into the search process of MOEAs.
|
|
| 8. |
- Bandaru, Sunith, et al.
(författare)
-
Temporal Innovization : Evolution of Design Principles Using Multi-objective Optimization
- 2015
-
Ingår i: Proceedings of the 8th International Conference on Evolutionary Multi-Criterion Optimization (EMO 2015). - Cham : Springer International Publishing Switzerland. - 9783319159331 - 9783319159348 ; , s. 79-93
-
Konferensbidrag (refereegranskat)abstract
- Multi-objective optimization yields multiple solutions each of which is no better or worse than the others when the objectives are conflicting. These solutions lie on the Pareto-optimal front which is a lower-dimensional slice of the objective space. Together, the solutions may possess special properties that make them optimal over other feasible solutions. Innovization is the process of extracting such special properties (or design principles) from a trade-off dataset in the form of mathematical relationships between the variables and objective functions. In this paper, we deal with a closely related concept called temporal innovization. While innovization concerns the design principles obtained from the trade-off front, temporal innovization refers to the evolution of these design principles during the optimization process. Our study indicates that not only do different design principles evolve at different rates, but that they start evolving at different times. We illustrate temporal innovization using several examples.
|
|
| 9. |
- Bernedixen, Jacob
(författare)
-
Automated Bottleneck Analysis of Production Systems : Increasing the applicability of simulation-based multi-objective optimization for bottleneck analysis within industry
- 2018
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Manufacturing companies constantly need to explore new management strategies and new methods to increase the efficiency of their production systems and retain their competitiveness. It is of paramount importance to develop new bottleneck analysis methods that can identify the factors that impede the overall performance of their productionsystems so that the optimal improvement actions can be performed. Many of the bottleneck-related research methods developed in the last two decades are aimed mainly at detecting bottlenecks. Due to their sole reliance on historical data and lackof any predictive capability, they are less useful for evaluating the effect of bottleneck improvements.There is an urgent need for an efficient and accurate method of pinpointing bottlenecks, identifying the correct improvement actions and the order in which these should be carried out, and evaluating their effects on the overall system performance. SCORE (simulation-based constraint removal) is a novel method that uses simulation based multi-objective optimization to analyze bottlenecks. By innovatively formulating bottleneck analysis as a multi-objective optimization problem and using simulation to evaluate the effects of various combinations of improvements, all attainable, maximum throughput levels of the production system can be sought through a single optimization run. Additionally, post-optimality frequency analysis of the Pareto-optimal solutions can generate a rank order of the attributes of the resources required to achieve the target throughput levels. However, in its original compilation, SCORE has a very high computational cost, especially when the simulation model is complex with a large number of decision variables. Some tedious manual setup of the simulation based optimization is also needed, which restricts its applicability within industry, despite its huge potential. Furthermore, the accuracy of SCORE in terms of convergence in optimization theory and correctness of identifying the optimal improvement actions has not been evaluated scientifically.Building on previous SCORE research, the aim of this work is to develop an effective method of automated, accurate bottleneck identification and improvement analysis that can be applied in industry.The contributions of this thesis work include:(1) implementation of a versatile representation in terms of multiple-choice set variables and a corresponding constraint repair strategy into evolutionary multi-objective optimization algorithms;(2) introduction of a novel technique that combines variable screening enabled initializationof population and variable-wise genetic operators to support a more efficient search process;(3) development of an automated setup for SCORE to avoid the tedious manual creation of optimization variables and objectives;(4) the use of ranking distance metrics to quantify and visualize the convergence and accuracy of the bottleneck ranking generated by SCORE.All these contributions have been demonstrated and evaluated through extensive experiments on scalable benchmark simulation models as well as several large-scale simulation models for real-world improvement projects in the automotive industry.The promising results have proved that, when augmented with the techniques proposed in this thesis, the SCORE method can offer real benefits to manufacturing companies by optimizing their production systems.
|
|
| 10. |
- Blank, Julian, et al.
(författare)
-
Generating Well-Spaced Points on a Unit Simplex for Evolutionary Many-Objective Optimization
- 2021
-
Ingår i: IEEE Transactions on Evolutionary Computation. - : IEEE. - 1089-778X .- 1941-0026. ; 25:1, s. 48-60
-
Tidskriftsartikel (refereegranskat)abstract
- 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.
|
|
