Problems With More Than One Goal
Most optimization problems in textbooks have one number to minimize. Real design problems rarely do. A car should be light and also safe in a crash. An investment portfolio should have high expected return and low risk. A neural network for a phone should be accurate and also fast. Improving one of these goals usually makes another one worse.
When objectives conflict, there is no single best solution. There is a set of solutions, each representing a different compromise, and the job of the optimizer changes from finding one answer to mapping out that set so a person can choose from it. This is multi-objective optimization, and evolutionary algorithms have become one of the main ways to do it.
Pareto Dominance and the Pareto Front
The central concept comes from the economist Vilfredo Pareto. A solution A dominates a solution B if A is at least as good as B on every objective and strictly better on at least one. If A is lighter and equally safe, B has no reason to exist. If A is lighter but B is safer, neither dominates the other, and both are legitimate options.
The solutions that no other feasible solution dominates are called Pareto optimal. Plotted in objective space, they form the Pareto front: for two objectives, a curve showing the best possible value of one objective for each value of the other. Every point on the front is a trade-off where improving one goal requires giving up some of the other. Every point behind the front is simply worse than some point on it.
Why Not Just Add the Objectives Together
The obvious shortcut is to combine the objectives into one, for example 0.7 times cost plus 0.3 times weight, and optimize that. This weighted sum approach is common and sometimes fine, but it has two problems.
The first is that the weights have to be chosen before seeing any solutions, and people are bad at saying in advance how many dollars a kilogram is worth. The second is mathematical. A weighted sum can only reach points on the convex parts of the Pareto front. If the front has a concave section (bulging in the wrong direction), no choice of weights will ever produce solutions there, even though they may be the most balanced options available. Other scalarization methods, like the epsilon-constraint method (optimize one objective while constraining the others below thresholds), avoid the second problem but still produce only one solution per run.
Why Populations Fit This Problem
Evolutionary algorithms work with a population of solutions, and a Pareto front is a population of solutions. A single run can therefore approximate the whole front at once, instead of needing one run per trade-off. The first attempt was David Schaffer’s VEGA in 1985, which selected parts of the population according to each objective separately. In 1989, David Goldberg suggested ranking individuals by Pareto dominance instead, and most later algorithms build on that idea.
A multi-objective evolutionary algorithm has two goals of its own. The solutions should converge toward the true front, and they should spread out evenly along it, so the decision maker sees the full range of options and not a cluster of nearly identical ones.
NSGA-II
Kalyanmoy Deb and colleagues published NSGA-II in IEEE Transactions on Evolutionary Computation in 2002. It is one of the most cited papers in evolutionary computation, and it is still the default algorithm people reach for with two or three objectives.
It combines three ideas. First, fast non-dominated sorting: the population is divided into layers. The first layer contains all solutions that nobody dominates. Remove them, and the non-dominated solutions among the rest form the second layer, and so on. Lower layers are better. The paper’s contribution was a sorting procedure that runs in O(MN²) time for M objectives and N individuals, faster than the earlier approach.
Second, crowding distance. Within a layer, solutions are compared by how isolated they are: for each objective, the algorithm measures the gap between a solution’s two neighbors on the front. A solution in a sparse region has a large crowding distance and is preferred over one in a crowded region. Solutions at the extremes of the front get infinite distance, so they are always kept. This keeps the population spread along the front without extra parameters.
Third, elitism. Parents and offspring are merged into one pool of size 2N, sorted into layers, and the best N survive. Layers are added whole until one does not fit, and that last layer is cut using crowding distance. Good solutions found earlier are never lost.
Other Approaches: Indicators and Decomposition
Not every algorithm uses dominance ranking as its main tool. SPEA2 (Zitzler, Laumanns and Thiele, 2001) uses a fitness based on how many solutions each individual dominates and is dominated by, plus a density estimate. MOEA/D, from Qingfu Zhang and Hui Li in 2007, breaks the multi-objective problem into many single-objective subproblems, each with a different weight vector, and solves them together, with neighboring subproblems sharing information. It avoids dominance sorting altogether and works well on problems where the front has a regular shape.
Indicator-based algorithms optimize a quality measure of the whole set directly. The most important measure is the hypervolume, introduced by Zitzler and Thiele: the volume of objective space dominated by the solution set, bounded by a reference point. A larger hypervolume means the set is both closer to the front and more spread out. SMS-EMOA selects solutions by their contribution to the hypervolume. The downside is cost, because computing the hypervolume becomes expensive as the number of objectives grows.
Many Objectives
Once there are four or more objectives, the setting is usually called many-objective optimization, and dominance stops working well. With many objectives, almost any two random solutions are better than each other on at least one objective, so most of the population is mutually non-dominated. The first layer contains nearly everyone, sorting provides almost no selection pressure, and crowding distance does a poor job of spreading solutions in high-dimensional objective space.
Deb and Himanshu Jain proposed NSGA-III in 2014 to address this. It keeps non-dominated sorting but replaces crowding distance with a set of reference points spread uniformly over a normalized hyperplane in objective space. Each solution is associated with its nearest reference direction, and the algorithm tries to keep at least one solution near each direction. The authors tested it on problems with 3 to 15 objectives. Visualizing the results becomes a problem in itself at that point, and methods like parallel coordinate plots are used to show them.
Where It Gets Used
Engineering design is the classic domain: aircraft wing shapes trading drag against structural weight, or car bodies balancing crashworthiness and mass. In energy systems, planners trade cost against emissions and reliability. In finance, Markowitz’s mean-variance portfolio theory is a two-objective problem at heart, and evolutionary methods extend it with realistic constraints like minimum lot sizes and limits on the number of assets.
Machine learning uses it more and more. Neural architecture search often treats accuracy and inference latency or model size as separate objectives. NSGA-Net (Lu and colleagues, 2019) applied NSGA-II directly to this, returning a front of architectures from small and fast to large and accurate. Fairness research treats predictive accuracy and fairness metrics as competing objectives. In Python, the pymoo library by Julian Blank and Kalyanmoy Deb implements NSGA-II, NSGA-III, MOEA/D and many others.
Choosing a Solution From the Front
The algorithm hands back a set, but someone eventually has to build one car. That final choice is called multi-criteria decision making, and it is where human preferences come back in. One common approach is to look for knee points, places on the front where a small gain in one objective would cost a large loss in another. Another is to let the decision maker state preferences interactively and focus the search on the region they care about. Either way, the preferences are applied after the options are known.
Reflection
Multi-objective optimization does not decide how much one goal is worth compared to another. It shows every trade-off that is actually available and leaves the choice to the people who own the problem. Weighted sums make that choice before any results exist, often without anyone noticing. A Pareto front puts the price of every compromise in front of the decision maker, and that is a large part of why engineers use it.
By: Max Johnson B.
Deja una respuesta