EP2791827A2

EP2791827A2 - Method for evaluating the solution to a multicriteria optimization problem

Info

Publication number: EP2791827A2
Application number: EP12795756.1A
Authority: EP
Inventors: Klemens WALLNER; Alejandra GARCIA; Adnand DRAGOTI
Original assignee: AVL List GmbH
Current assignee: AVL List GmbH
Priority date: 2011-12-12
Filing date: 2012-11-08
Publication date: 2014-10-22
Also published as: JP5940667B2; AT510328A2; US9760532B2; WO2013087307A2; JP2014533387A; WO2013087307A3; US20140344320A1

Abstract

Solving a multidimensional multicriteria optimization problem is difficult because the correlations and dependencies between solutions, target functions and variation variables can be detected only with difficulty. In order to facilitate this, it is proposed that a model space (1) and a variation space (2) be displayed simultaneously and in interactively linked fashion.

Description

Method for evaluating the solution of a multi-criteria optimization problem

The present invention relates to a method for evaluating the solution of a multi-criteria optimization problem.

When calibrating vehicle control units (xCU), such as an engine control unit ECU or a TCU, on vehicle and component test benches, but also during test drives, the calibration engineer is regularly faced with the task of optimizing a compromise between different target values. Problems in which target values of several objective functions are simultaneously to be optimized depending on a number of restrictions are widespread in practice and in particular in calibration. Examples include the NOx-soot compromise, or the NOx-soot consumption compromise in classic internal combustion engine drives, or the battery damage- consumption compromise in hybrid applications, or the tradeoff between sporty but still comfortable tuning of gearshift operations. In general, in vehicles with drive concepts with automatic transmissions and / or hybridization, more and more conflicting demands are made on the individual components, which must be represented and optimized in the form of a compromise. Such multicriteric optimization problems generally exist if target values of several objective functions are to be optimized simultaneously depending on several restrictions (such as boundary conditions, physical limits, etc.). However, if the objective functions are in conflict with each other, the simultaneous optimization of all objective functions is often a problem. In particular, such multicriteria optimization problems usually can not find unique solutions but only a set of possible multidimensional solution points in a multi-dimensional space a multi-dimensional surface, the so-called Pareto front, which all represent an optimal compromise of the multi-criteria optimization problem. Individual points of this Pareto front therefore represent different, but in each case optimal, compromises between the objective functions. Such multi-criteria optimization problems are known per se and there are also a number of mathematical methods for solving such problems. From EP 2 192 294 A1, for example, a method is known with which an ECU is optimized during operation by means of a multi-criteria optimization problem with respect to an exhaust gas soot consumption compromise. In this case, a single aggregate objective function (AOF) is used, which combines the weighted objective functions into a functional one common solution is the linearly weighted summation of the objective functions described here. Each objective function is assigned a weighting factor. tor, from which a scalar objective function is derived as the sum. In this case, the actual optimization can be carried out using conventional approaches, for example by means of sequential quadratic programming (SQP), an effective, iterative method for nonlinear limited optimization, which is necessary for the desired reduction of the required computing power. However, the meaningfulness of such optimization largely depends on the choice of weighting factors, which in many cases can not be determined reliably in advance, which means that the results of such an optimization are not always satisfactory or even limited to a limited group from the optimization problem is applicable. Another problem with multi-criteria optimization problems is to visualize the solution found and present it in such a way that a simple, meaningful analysis of the solution is possible. Two- and three-dimensional relationships are still detectable by humans. However, as a rule, these are multi-dimensional correlations, with which methods for the evaluation of the results of the multi-criteria optimization must be found, which allow a simple but nevertheless meaningful evaluation. In particular, the task is to select from the compromises found a certain compromise as the ultimate solution of the optimization problem. Here, it is particularly difficult to grasp the relationships between the individual objective functions and the variables in the solution found. There are also known methods and approaches to solve this problem.

US Pat. No. 7,921,371 B1 describes a method for visualizing the solution of a multi-dimensional multi-criteria optimization problem. All target values are displayed on parallel, adjacent axes, whereby also the smallest and largest value of the found optimal solution is visualized, which represent the entire possible range of the optimal solutions for a target size. Therefore, the pareto front is represented in the form of parallel axes for the number of target variables. For each target size, there is a fixed target value, also shown in the diagram, with the parallel axes shifted vertically so that the target values all lie on a horizontal line. The upper and lower limits of the individual target variables can now be varied by one user, whereby at the same time all the other axes are also influenced, ie only the solutions that meet the user-selected limits of a target variable are displayed. The user thus has the opportunity to analyze the relationships between the individual target values and thereby to choose a compromise from the set of all possible compromises (Pareto front). WO 01/67395 A1, in turn, discloses a method in which, in a representation of all possible optimal solutions, those are marked (here by a different color), which satisfy a certain user-specified criterion, such as a constraint. The solutions are projected onto two or three-dimensional surfaces in order to be able to recognize connections. Both target variables (dependent variables) and variables (independent variables) are shown. Thus, the amount of solution can be specifically limited and visually displayed, which also allows to analyze and recognize relationships. However, this method only allows to make very general statements and does not allow a detailed analysis of the solution of a multi-criteria optimization problem.

It is therefore an object of the present invention to provide a method for visualizing and analyzing the solution of a multi-criteria optimization problem, which allows a simple but nevertheless detailed evaluation of the solutions found and thus the selection of one of the found, optimal solutions as a solution of the multi-criteria optimization problem.

This object is achieved according to the invention by representing the set of optimal solutions of the multicriteria optimization problem in a model space as a two- or three-dimensional diagram of the objective functions and simultaneously displaying at least one of the objective functions as a function of at least one variation variable in a variation space Model space and the variation space are interactively interconnected by marked for each selected solution in the model space, the solution size underlying the solution in the variation space. This way of processing and presenting the multi-criteria optimization problem by presenting the optimal solutions of the multi-criteria optimization problem together with the variation sizes allows a simple and meaningful graphic analysis of the solutions of the multi-criteria optimization problem with the aim of choosing a solution as the best possible compromise. The coupling of the graphical views of the variation space and the model space results in a particularly high informative value in the analysis of multi-criteria optimization problems. Thus, individual variation quantities can be analyzed with regard to their optimality and dependence on other variables.

In a preferred embodiment, a mathematical model can be used as the objective function, which is determined from a number of measurements of the objective function as a function of the variables. This makes it possible to apply the inventive method practically to any optimization problems.

It is also particularly advantageous to additionally provide a model confidence range in the variation space for the objective function, with which the solutions can be evaluated simultaneously with respect to the respectively associated model confidence range. Overall, it is possible to produce better calibration results in this way, and moreover, the calibration process can be carried out semi-automatically, ie in a cost-effective and time-effective manner, and not least comfortable and reproducible.

The subject invention will be explained below with reference to Figure 1, which shows schematically and by way of example an advantageous embodiment of the invention.

The problem of finding targets that typically optimize multiple target functions concurrently with multiple constraints is called Multi-Criteria Optimization Problems (MOP). The mathematical description of the problem is as follows: min / max (f i (x), f 2 (x), ..., f k (x))

x

(MOP) gi (x) <0 i = l, ..., m

X mm ■ <X <X max

Where f _j (x), where j = 1, ..., k, represents the objective function that should be minimized or maximized. This optimization should take place both under consideration of constraints g, as well as for a limited range x _min , x _{max of} the variables x = {x ₁ , ... x _n }.

The variation quantities x lie in the space of variation, under which one understands the n-dimensional space (n = number of variation quantities), which is spanned by the variation quantities x. The variation quantities x are e.g. during a calibration, the settings, e.g. at the test bench where the calibrator carries out his measurements. Since these variation quantities x represent valid points in the variation space, the calibrator knows that he can adjust the variation quantities x in this range. For this reason, in this variation space, around the variation quantities x, an envelope is laid, which is referred to as design space. The design room thus contains all the variables x valid for the respective application.

If the objective functions, such as most often the case, are in a conflict with each other, it is difficult to minimize all objective functions f _j simultaneously. Therefore, the concept of non-dominant individuals was introduced. A point in the objective function space X ^* is called a non-dominating individual, unless there is a valid solution within the design space for which: a), = 1 k / fi (x) ^ fi (x ^* ) b) 3 each {1 , 2, ..., k} / fj (x) <fj (x) In other words, if there is no way to improve the point in one of the objective functions without worsening one of the others. Usually and as is known, for a multi-criteria optimization problem, not only such a solution exists, but a set of possible solutions called the Pareto front. There are many theoretical approaches to solving such multicriteria optimization problems, but not all known methods provide good approaches to the Pareto front.

A single Aggregate Objective Function (AOF), such as described in EP 2 192 294 A1, is probably the most intuitive approach to solve multi-criteria optimization problems. By contrast, evolutionary algorithms for multicriteria optimization do not require any weighting or a priori information, so that these methods have been increasingly used in recent years and in particular have proven to be effective and robust methods. Specifically genetic algorithms - based on selection, recombination and mutation - were used to achieve a continuous approach to a desired target. They are easy to apply to a wide range of problems and are very robust in the search for global optima, even if there are a variety of local optima. In multicriteria optimization, conflicting requirements are searched for in a set of compromise solutions that approximate the best possible solutions. The quality of an approximation can be quantified by the volume dominated by it in the target space, the S metric. Maximizing the S-metric is a desirable goal and, at the same time, sufficient scalar replacement of the original objective function. A genetic algorithm uses these within the selection and thus achieves excellent results, especially when more than three goals have to be optimized where other multicriteria genetic algorithms fail. The currently most popular genetic algorithm for determining the Pareto front is the Non-Dominated Sorting Genetic Algorithm (NSGA-II), which has proven to be extremely efficient, especially for the determination of a global optimum. NSGA-II is a high-performance, elitist algorithm that prioritizes non-dominating individuals and preserves the diversity of solutions. The algorithm creates an initial population within the vector of variational magnitudes x and approaches iteratively in an iterative process that is based on selection,

Crossing and mutation operations are closer to each new generation by favoring non-dominant individuals (elitism) until a solution criterion is met. Such genetic algorithms are by nature relatively computationally intensive, but also easy to parallelize for today's multi-core processors and distributed computer structures. Since these algorithms are known per se, they will not be discussed in more detail here, especially since the chosen method for the solution of the multi-criteria optimization has no influence on the preparation and analysis of the results according to the invention.

In order to be able to evaluate the result of the multi-criteria optimization (independent of the selected solution algorithm), a special type of processing and representation of the variables used is used. This evaluation based on a graphical analysis is described below.

The peculiarity of the visual presentation lies in a split representation of model space 1 and variation space 2, as shown in FIG. The model space 1 is the k-dimensional space, which is spanned by the k target functions (χ), j = 1, ..., k. In examples 1, for example f ₂ (x) "NOX" and f ₃ (x) "Fuel Consumption" The illustration of the design space game of FIG. Three-dimensional space, the fi through the objective functions (x) "Smoke", is spanned. the valid range 3 in which the solutions can move is contained in this model space 1. The Pareto front 4 contains the solutions found for the multi-criteria optimization problem within this valid range 3. If the model space 1 has a dimension larger than three, then the Model space 1 can also be represented by several two- or three-dimensional representations of the k dimensions of the model space.These dimensions of the k dimensions in the two- or three-dimensional representations can be made dependent on the multi-criteria optimization problem and the preference of the user is represented by a number of two or three-dimensional representations of objective functions f _j (x) and variation quantities x In Place. In the example of Figure 1, the objective function is f ₃ (x) each represented as a function of the three varying sizes x-ι "exhaust gas temperature" x ₂ "EGR rate" and x ₃ "rail pressure". However, any combinations of objective functions f _j (x) and variation quantities x are conceivable here. The objective functions f _j (x) can be known functions of the variables x. However, it is also conceivable that an objective function f _j (x) is a mathematical model that is determined from measurements or experiments. In this case, measurements are carried out on the object of the multi-criteria optimization problem, eg on an internal combustion engine, a drive train, a transmission, a vehicle, etc., for example on corresponding test benches or in the course of test drives. In this case, the desired objective functions f _{j are} measured as a function of the variables x and possibly other variables. Mathematical models of the objective functions f _j are then created from these measured variables. There are also a number of known methods with which the best possible coverage can be achieved with as few measurements as possible to get good mathematical models. Possible models include a polynomial regression model, a fast neural network or an intelligent neural network. Because of this approach, additional measurements, ie real measurements, will not necessarily be 100% accurate on this model. The methods for determining the models therefore also provide a model confidence interval indicating the bandwidth in which further measurements are likely to move. This means that a model with a slim model confidence range fits relatively well on the measurements made and has accordingly good explanatory power. The closer the model confidence interval, the better the models fit the measurements, and the more likely the model-determined solutions to the multi-criteria optimization problem will actually yield the sought-after values. Of course, well-known objective functions (χ) can also have a model confidence range, which in turn indicates how exactly an objective function f _j agrees with a real measurement. The model confidence range is thus a measure of the accuracy of the model or a target function with respect to real measurements. In the variation space 2, therefore, the model confidence ranges 5 can also be shown in the individual diagrams, for example in the form of an upper and lower limit as shown in FIG.

The special feature of this type of representation is that the objective functions (χ) in the model space 1 and the Pareto front 4 are represented as a set of possible optimal solutions of the multi-criteria optimization problem together with the variables x and therefore can also be analyzed together. The representation in the variation space 2 is interactively adapted to a selection of a point in the model space 1. For this example, a crosshair 6 is provided. With the example, an interesting point 7 of the Pareto front 4, or the valid area 3, is selected. In the variation space 2, the crosshair 6 automatically marks the variation quantities x for this punk 7 in the model space 1. At the same time, the respective values of the variables x at this point can also be indicated, as indicated in FIG. 1. Likewise, the model trust area 5 can be represented so that the user additionally receives information about how trustworthy the underlying objective function _fj (or mathematical model) is on this point. Once determined models can of course be used for later tasks.

The coupling of the graphical views of Variationsraum 2 and Modellraum 1 results in a particularly high informative value in the analysis of multi-criteria optimization problems. Thus, individual variation quantities x can be evaluated not only with regard to their optimality and dependence on other variables x, but also simultaneously with respect to the respectively associated model confidence range 5. Thus, the possible to analyze the solution set in detail in order to find the best possible compromise between the objective functions (χ).

However, this type of representation also allows the analysis of the effects of changes in the specification of the constraints g, and / or the range x _min , x _ma x of the variables x. Such changes lead to other solutions that can then be easily compared directly. For this purpose, it can be provided, for example, to change the limits of the range of variation variables x, for example by means of a slider in the variation space 2, whereby the representation of the solution in the model space 1 can change at the same time. It could also be provided to filter the solutions in the model space 1 such that only those that fulfill certain areas of one or more variables x are displayed. The coupled presentation and the interactivity of the presentation make such influences easier to grasp.

Due to the complexity of the calculations required in this context, it is advantageous to structure the software architecture of the method according to the invention so that complex tasks can be parallelized. As a result, individual tasks can be executed in parallel on different processors or on different computers. This distributed multi-criteria optimization allows the user to carry out his optimization tasks in a high-quality, high-performance manner in an arbitrarily scalable, distributed system. In addition, with the coupled visualization of variation space 2 and model space 1, this increase in performance enables significantly increased informative value in the analysis of multi-criteria optimization problems.

A possible sequence of a calibration of an engine control unit ECU of an internal combustion engine with respect to the NOx-soot consumption will be described below as an example

described multi-criteria optimization. First, a number of measurements are performed on the internal combustion engine, wherein the target variables of the target functions f _j (x) NOx, soot and consumption depending on the variables x, eg exhaust gas temperature, EGR rate, rail pressure, are measured. The number and the amount of measurements can be predetermined, eg by a given Design of Experiment. The measurements are used to determine mathematical models and model confidence regions 5 for the objective functions f _j (x). Then the multicriteria optimization problem for optimizing the objective functions f _j (x) can be solved and the solution in the split representation of model space 1 and variation space 2 can be analyzed. In this case, the calibrator can examine various optimal solutions of the pareto-front 4 with regard to the underlying variation variables x and the model confidence region 5. From these possible optimal solutions, the calibrator then determines one of the solutions as the best possible compromise. Here, the experience of the calibrator plays a major role. In addition to the model confidence ranges and the Dependencies of the variables x are also the values of additional model channels that have not been optimized as target functions, as well as the robustness of the settings, eg whether the models in the vicinity of the optimum changes greatly, low influenceability due to component tolerances, etc., are taken into account. This can be repeated for all operating points required for the calibration (eg speed, torque, load) of the internal combustion engine. For a calibration, a predetermined number of operating points, eg ten to twenty operating points, are generally required.

Claims

claims

1 . Method for evaluating the solution of a multi-criteria optimization problem for j = 1,..., K of variance variables x-dependent objective functions (χ), where the set of optimal solutions of the multi-criteria optimization problem in a model space (1) is a two- or three-dimensional diagram the j = 1, ..., k target functions f _j (x) are shown and at the same time in a variation space (2) at least one of the objective functions f _j (x) is represented as a function of at least one variation variable (x) and the model space ( 1) and the variation space (2) are interactively connected to one another by marking for each selected solution in the model space (1) the solution variable (x) on which the solution is based in the variation space (2).

2. The method according to claim 1, characterized in that as a target function f _j (x) a mathematical model is used which is determined from a number of measurements of the objective function f _j (x) as a function of the variables (x).

3. The method according to claim 1 or 2, characterized in that in the variation space (2) for the objective function f _j (x) additionally a model confidence region (5) is shown.