|
Why it Matters
The initial thoughts of an intelligent reader new to multi-objective optimization might go roughly as follows. ‘OK, so it is good to have a set of non-dominated points, but maybe these will appear if we simply look at all the points visited by a single optimization run anyway. If not, then we can simply run single-objective optimization many times, but with different penalty coefficients, and thereby get a good collection of points on the Pareto front.’
It turns out that both of these ideas are very over-optimistic. The first is almost a non-starter when we examine it on real problems, and the second, though going in a direction which does yield fruit, is hopelessly inefficient in its natural formulation. The point is, having recognized that Pareto fronts are good to have, far more valuable to the problem solver or designer than a single solution to a simplified and different problem, the basic algorithmic machinery provided by the portfolio of single-objective optimization research, though rich in capability and ingenuity, is not suited to the task of efficiently finding good approximations to the Pareto front of a multi-objective problem
Illustrating, on a generic two-objective problem scenario, the impoverished solution set(s) available to pure single-objective optimization approaches.
Figure 2 helps us reason about this. In Figure 2 we again plot the Pareto optimal points of a hypothetical two-objective optimization problem, in this case labeling the axes with “probability of failure” and “cost”, respectively, thus hinting at just part of the immense proportion of real-world problems which can only be properly handled by a multi-objective approach. The meandering arrows each sketch the progress of a single-objective (penalty-function based) approach. The parameters guiding the search of the purple arrow, for example, are likely to find, at best, the purple Pareto optimal points; a similar story applies for the orange arrow. Meanwhile, the green arrow is not necessarily likely to find any Pareto optimal points not found anyway by the purple and orange arrows; this is because the section of the Pareto front which seems to be on its path is concave, and these points are not optima for the ‘green’ search. Instead, assuming the underlying optimizer is a good one, it will find the points touching the green tangent line. There are many ifs and buts which should really qualify this simple illustration, but the broad message is true. A single search with a penalty function is likely to leave lots of Pareto optimal points undiscovered, and therefore inaccessible to the problem-solver. These include maybe ideal solutions to the problem, but, despite the pedigree of the single-objective method used, remain lost. Repeated single-objective runs each with a different penalty function will, however, have some chance of yielding a picture of the Pareto front, but note that this picture will often be very patchy and sparse. Finding points in concave regions is very much in the lap of the Gods, while the fact that this involves several runs of the single-objective method reveals burdensome time complexity, and this onus is exponentially increased as we raise the number of objectives beyond two, which is very common indeed in real-world applications.
Further, it is instructive to consider the great depth of assumptions inherent in any single-objective penalty-based approach. Without missing the point, let’s assume the intention in such an approach is to treat each objective as equally important. We might then imagine such a search would be ideally directed at what happens to be a concave region in Figure 2, since points here are between the extremes of both objectives (and for other reasons, as we already know, hard for single-objective optimization to find in the first place). However, even this simple goal of equal weighting needs very careful parameterization of the penalty function. To see this, suppose we expect cost to vary between $1M and $5M, and probability of failure to vary from 0 to 1. For single objective optimization to weight these equally, we would do the equivalent of multiplying the probability objective by around 4M, and expect that to facilitate a search in the direction of the green arrow in Figure 2. However, returning to real life, and in particular the a priori unknown nature and position of the Pareto front, the balance of probabilities would have it that such a search will always end up going in entirely the wrong direction and focusing on a single extreme of just one of the objectives. In one problem instance, for example, the Pareto optimal points in Figure 2 may range from 0.9 to 0.95 on the vertical axis, and all the way from $1M to $5M on the horizontal axis. The unwise penalty setting in such a case will have left us stuck in the bottom left corner, finding only high-cost solutions. The main point here is that the success of a penalty-function approach is sensitive to many factors, most of which are completely unknown beforehand. Even the conceptually simple goal we set above, of finding a single-objective function which treats each objective as equally important, is almost never achievable in practice – the situation is of course even worse when we want to coerce a penalty function into expressing more complex goals, which is often the case. However, a ‘proper’ multi-objective optimization approach simply steps aside from all such sensitivities, naturally treating each objective as an equal. This brings its own issues, but of a much more agreeable nature: no longer need we fear completely missing the target; instead, the problem-solver is facilitated by a full map of the target area, and then needs to work further with her advanced multi-objective optimizer to zoom in on the fruitful areas.
To end this section we underline the fact that all this matters by considering again the typical structures of real-world problems. It is very rare indeed that a real-world problem has only one objective. For example, the classic traveling salesperson problem (TSP) is the Drosophila melanogaster of single-objective optimization research (Lawler et al, 1985), but its real-world counterparts are hardly ever true single-objective problems. If we consider the eponymous case, where the problem is really to find the shortest route between cities for a traveling hawker, the different visits along that route will invariably have different priorities (in terms of likeliness to buy the goods), and an ultimately much longer than optimal route may be greatly favoured since it puts our salesman in Denver at just the right time to buy a lavish lunch for a potentially big buyer. When it does seem to be the case that one objective is all we need, this is often a cost measure, which tries to sum up in dollars and cents the total cost of a design. But we all know very well that this is always a gross simplification; the cheaper it is to make our VLSI chip, the more we may have to pay out in the future for replacements and lost business. The more fuel payload we save from a cleverly optimized route for our Saturn probe, the less opportunity we have to steer it away from trouble (and thus save billions of dollars) when it goes off course.
|
