Multi-objective optimization

Multi-objective optimization (or programming),^[1][2] also known as multi-criteria or multi-attribute optimization, is the process of simultaneously optimizing two or more conflicting objectives subject to certain constraints.

Multiobjective optimization problems can be found in various fields: product and process design, finance, aircraft design, the oil and gas industry, automobile design, or wherever optimal decisions need to be taken in the presence of trade-offs between two conflicting objectives. Maximizing profit and minimizing the cost of a product; maximizing performance and minimizing fuel consumption of a vehicle; and minimizing weight while maximizing the strength of a particular component are examples of multi-objective optimization problems.

If a multiobjective problem is well formed, there should not be a single solution that simultaneously minimizes each objective to its fullest. In each case we are looking for a solution for which each objective has been optimized to the extent that if we try to optimize it any further, then the other objective(s) will suffer as a result. Finding such a solution, and quantifying how much better this solution is compared to other such solutions (there will generally be many) is the goal when setting up and solving a multiobjective optimization problem.

Introduction

In mathematical terms, the multiobjective problem can be written as:

${\displaystyle {\begin{aligned}\min _{x}&\left[\mu _{1}(x),\mu _{2}(x),\dots ,\mu _{n}(x)\right]^{T}&\\s.t.&\\g(x)&\leq 0\\h(x)&=0\\x_{l}\leq &x\leq x_{u}\end{aligned}}}$ 

where ${\displaystyle \mu _{i}}$  is the ${\displaystyle i}$ -th objective function, ${\displaystyle g}$  and ${\displaystyle h}$  are the inequality and equality constraints, respectively, and ${\displaystyle x}$  is the vector of optimization or decision variables. The solution to the above problem is a set of Pareto points. Pareto solutions are those for which improvement in one objective can only occur with the worsening of at least one other objective. Thus, instead of a unique solution to the problem (which is typically the case in traditional mathematical programming), the solution to a multiobjective problem is a (possibly infinite) set of Pareto points.

A design point in objective space ${\displaystyle \mu ^{*}}$  is termed Pareto optimal if there does not exist another feasible design objective vector ${\displaystyle \mu }$  such that ${\displaystyle \mu _{i}\leq \mu _{i}^{*}}$  for all ${\displaystyle i\in \left\{{1,2,...,n}\right\}}$ , and ${\displaystyle \mu _{j}<\mu _{j}^{*}}$  for at least one index of ${\displaystyle j}$ , ${\displaystyle j\in \left\{{1,2,...,n}\right\}}$ .

Solution Methods

• Constructing a single aggregate objective function (AOF)

This is perhaps the most intuitive approach to solving the multiobjective problem. The basic idea is to combine all of the objective functions into a single functional form, called the AOF. A well-known combination is the weighted linear sum of the objectives. One specifies scalar weights for each objective to be optimized, and then combines them into a single function that can be solved by any single-objective optimizer (such as SQP, pattern search etc.). Clearly, the solution obtained will depend on the values (more precisely, the relative values) of the weights specified. For example, if we are trying to maximize the strength of a machine component and minimize the production cost, and if we specify a higher weight for the cost objective compared to the strength, our solution will be one that favors lower cost over higher strength. Thus, it may be noticed that the weighted sum method is essentially subjective, in that a decision manager (DM) needs to supply the weights. The objective way of solving multiobjective problems requires a Pareto-compliant ranking method, favouring non-dominated solutions, as seen in current multiobjective evolutionary approaches such as NSGA-II and SPEA2. Here, no weights are required and thus no a priori information on the problem is needed. ^[3]

• Normal Boundary Intersection (NBI) method ^[4][5]
• Normal Constraint (NC) method.
• Multiobjective Optimization Evolutionary Algorithms (MOEA).^[6][7][8]

Evolutionary algorithms are very popular approaches in multiobjective optimization. Nowadays, most evolutionary optimizers apply Pareto-based ranking schemes. Genetic algorithms such as the Non-dominated Sorting Genetic Algorithm-II (NSGA-II) and Strength Pareto Evolutionary Approach 2 (SPEA-2) have become standard approaches, although some schemes based on particle swarm optimization and simulated annealing are significant.

• PGEN (Pareto surface generation for convex multiobjective instances)^[9]
• IOSO (Indirect Optimization on the basis of Self-Organization)

See also

• Multidisciplinary design optimization
• Pareto efficiency
• Goal Programming

References

1. Steuer, R.E. (1986). Multiple Criteria Optimization: Theory, Computations, and Application. New York: John Wiley & Sons, Inc. ISBN 047188846X.
2. Sawaragi, Y. (1985). Theory of Multiobjective Optimization (vol. 176 of Mathematics in Science and Engineering). Orlando, FL: Academic Press Inc. ISBN 0126203709. {{cite book}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)
3. Deb, K.: Multi-Objective Optimization using Evolutionary Algorithms. Wiley, 2002.
4. I. Das and J. E. Dennis. Normal-Boundary Intersection: A New Method for Generating the Pareto Surface in Nonlinear Multicriteria Optimization Problems. SIAM Journal on Optimization, 8:631–657, 1998.
5. Normal-Boundary Intersection: An Alternate Method For Generating Pareto Optimal Points In Multicriteria Optimization Problems
6. Deb, K. Multi-Objective Optimization using Evolutionary Algorithms John Wiley & Sons, 2001.
7. Coello Coello, C. A.; Lamont, G. B. & Van Veldhuizen, D. A. Evolutionary Algorithms for Solving Multi-Objective Problems Springer, 2007.
8. Das, S.; Panigrahi, B. K. Multi-objective Evolutionary Algorithms, Encyclopedia of Artificial Intelligence, (Eds. J. R. Rabuñal, J. Dorado & A. Pazos), Idea Group Publishing, 3:1145 – 1151, 2008.
9. D. Craft, T. Halabi, H. Shih, and T. Bortfeld. Approximating convex Pareto surfaces in multiobjective radiotherapy planning. Medical Physics, 33(9):3399–3407, 2006.

• M.Ehrgott. Multicriteria optimization. Springer 2005. ISBN 978-3-540-21398-7

External links

• PISA A Platform and Programming Language Independent Interface for (Multiobjective) Search Algorithms; includes implementations of various algorithms (SPEA2, NSGA-II), and many problems (processor design, ZDT, DTLZ, and WFG test suites)
• ParadisEO is a C++ framework dedicated to the reusable design of metaheuristics for multi-objective optimization.
• Practical multiobjective optimization
• jMetal jMetal is an object-oriented Java-based framework aimed at facilitating the development of metaheuristics for solving multi-objective optimization problems.
• Multiobjective Optimization of SLA-aware Service Composition
• NIMBUS is web form based interactive multiobjective optimization system for differentiable and nondifferentiable problems.
• BiSNET/e: A Cognitive Sensor Networking Architecture with Evolutionary Multiobjective Optimization
• SymbioticSphere: A Biologically-inspired Architecture Network Systems with Evolutionary Multiobjective Optimization
• Evolutionary Multiobjective Optimization by Robin Gruna, the The Wolfram Demonstrations Project