 Open Access
 Authors : Muhammad Nagy , Yasser Mansour , Sherif Abdelmohsen
 Paper ID : IJERTV9IS030480
 Volume & Issue : Volume 09, Issue 03 (March 2020)
 Published (First Online): 01042020
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
MultiObjective Optimization Methods as a Decision Making Strategy
Muhammad Nagy Department of Architecture Ain Shams University Cairo, Egypt.
Yasser Mansour Department of Architecture Ain Shams University Cairo, Egypt.
Sherif Abdelmohsen Department of Architecture Ain Shams University Cairo, Egypt.
AbstractOne of the most basic concepts in humankinds life is the search for an optimal state. As long as the life continues, seeking for perfection in decision making of many areas is fundamental. The concept of optimization is considered as a main goal for a decision maker (DM) to achieve the best solution or most favorable set of solutions of one or more given criteria. In fact, most of realworld problems involve many correlated and often conflicted objectives that should be maximized or minimized to have the problem solved; such setting creates a harder situation for a DM to define all those contradicting objectives in terms of a one single objective following singleobjective optimization (SOO) approach. To overcome this limitation, multiobjective optimization (MOO) becomes one of the recent optimization approaches to formulate decision making problems in a more realistic manner.
As the ultimate goal of solving MOO problems is to find the optimal set of nondominated solutions, which is called Pareto optimal set of Paretooptimal solutions, using classical methods of exact, heuristics or metaheuristics methods become more complicated and cannot guarantee that those optimal solutions will be found. Therefore, many methods have been developed to facilitate the process of solving MOO problems with respect to the role of DM, due to his authority to give further preference information concerning the Paretooptimal solutions.
To this end, this study introduces a brief definition of MOO problem formulation, representation and solution; including analytical comparison of most common MOO problem solving methods in the literature. Its concluded that MOO methods tree could be classified into four main branches based on DM preference articulation: No preference, Apriori, Interactive, and Aposteriori preferences articulation of DM.
KeywordsMultiobjective optimization; No preference; A priori; Aposteriori; Interactive; ParetoOptimal; Evolutionary Algorithms.

MULTIOBJECTIVE OPTIMIZATION PROBLEM FORMULATION
The first step in performing a MOO is to formulate the problem appropriately. A MOO problem is defined by four parts: a set of decision variables, objective functions, bounds on the decision variables, and constraints. Since objectives can be either minimized or maximized to find a set of optimal solutions that satisfy involved constraints. Hence, we state the MOO problem in its general form as following:
Find the design variable vector
,
which minimizes/ maximizes the objective functions
,m = 1, 2, , M
Subject to
n number of bound(s)
i = 1, 2, , n J number of inequality constraint(s):
j= 1, 2, , J
K number of equality constraint(s):
, k= 1, 2, , K
Referring to the statement of MOO problem, the objective functions or their objective values where m = 1, 2,
, M, form an objective vector , which can be written as:

INTRODUCTION
Multiobjective optimization (MOO), also called many objective, multicriteria, multiattribute, multiperformance, Pareto, or vector optimization, is defined as the procedure for optimizing two or more conflicting objectives simultaneously subject to certain constraints. Mathematically, MOO problem is the problem of finding a vector of decision variables which satisfies a number of constraints and optimizes a vector function whose elements represent the objective functions which are to be either minimized or maximized simultaneously. These functions form a mathematical description of performance criteria which are usually in conflict with each other. Hence, the term optimize means finding such a solution which would give the values of all the objective functions acceptable to the DM.
Or more conveniently as: =
. where T indicates the transposition of the column vector to the row vector.
There are two Euclidean spaces are considered in MOO problems: The design, decision, state, or search space , which is the ndimensional real coordinate space of the design variables in which each coordinate axis corresponds to a component of vector x; The objective, solution, or response space which is the Mdimensional real coordinate space of the objective functions and formed by the objective function values in which each coordinate axis corresponds to a component of vector [1].
For each solution in the first space it gives a certain point in the second space, denoted by: i.e.
which determines a quality of this solution in terms of the objective function values . Its referred to a solution as a design variable vector and a point as the corresponding objective vector
The solutions satisfying both objective functions constraints, and variable bounds constitute a feasible decision variable space S or and it corresponding feasible objective space Z or .


MULTIOBJECTIVE OPTIMIZATION PROBLEM REPRESENTATION
In MOO, where there is more than one objective, each objective has its own fitness landscape, as variations in objective values with changes in design variable values are likely to be different for different objectives (see Fig.1). For many problems, objectives compete with each other, so that solutions that improve values of one objective might worsen values in another. Therefore, it is less clear which solutions are better than others, as the solution that results in the highest peak in the fitness landscape for one objective might result in the lowest peak in the fitness landscape for the other objective and vice versa. In such cases, the optimality of a solution is determined using the concept of dominance [2].

MULTIOBJECTIVE OPTIMIZATION PROBLEM SOLUTION In real life, its rarely and ideal to find a single solution that simultaneously optimizes all objective functions of a MOO problem. Therefore, the definition of optimality has different meaning in this case. A MOO problem solution is to find good
compromises or tradeoffs of conflicting objective functions in an optimal manner, rather than finding a single solution.
Fig. 1. Illustration of the relationship between (a) the fitness landscape of objective 1, (b) the fitness landscape for objective 2 and (c) the Pareto frontier
Fig. 2. Graphical depiction (mapping) of (a) a decision space onto (b) an objective space, where both objectives are to minimized
From this front, a DM (be it a human or an algorithm) can finally choose the configurations that, in his opinion, suit best.
Mathematically, the most commonly adopted definition of optimality for MOO problems is that originally proposed by Francis Ysidro Edgeworth and later generalized by Vilfredo Pareto using the term Pareto optimality [3]. Unlike SOO problems, where the superiority (optimality) of a solution over other solutions is easily determined by comparing their objective function values, in MOO problems, the goodness (optimality) of a solution is determined by the concept of dominance. For a given a set of solutions in the design space, where the set of all possible combinations of design variables exists, the nondominated solution set is a set of all solutions that are not dominated by any other member of the solution set. The nondominated set of the entire feasible design space is called the Pareooptimal set which represents a complete set of Paretooptimal Solutions. Paretooptimal solutions are tradeoff solutions for which any improvement in one objective results in worsening of at least one other objective. The boundary defined by the set of all points (Paretooptimal points) mapped from the Paretooptimal set to the feasible objective space is called the Paretooptimal front or Pareto frontier. The previous terms will be detailed in the following subsections.

Pareto Dominance
The concept of domination is illustrated in Fig. 3. A solution
is said to dominate the other
solution (denoted by
), if both the following conditions are true:

The solution is no worse than in all objectives Thus, the solutions are compared based on their objective function values (or location of the corresponding points and on the objective space).

The solution is strictly better than in at least one objective.
This definition could be mathematically represented as follows:
Fig. 3. The concept of domination illustrated in a minimization problem of two objective functions


Pareto Optimal Solution
The phrase Paretooptimal solution is taken to mean with respect to the entire design variable space unless otherwise specified. In other words, is called Paretooptimal solution, if there exists no feasible vector x which would improve some criterion without causing a simultaneous worsening in at least one other objective.
A solution is a Paretooptimal solution with respect , if and only if:
there is no for which, Dominates,

Pareto Optimal Set
Pareto optimal solutions are those solutions within the design space whose corresponding objective vector components cannot be all simultaneously improved. These solutions are also termed noninferior, admissible, or efficient solutions, with the entire set represented by . Their corresponding vectors are termed nondominated; selecting a vector(s) from this vector set (the Pareto front set .) implicitly indicates acceptable Paretooptimal solution. These solutions may have no apparent relationship besides their membership in the Pareto optimal set. They form the set of all solutions whose associated vectors are nondominated; Pareto optimal solutions are classified as such based on their evaluated functional values. Mathematically, for a given MOO problem , the Paretooptimal set , is defined as:

Pareto Frontier
Nondominated vectors of entire Paretooptimal set are collectively known as the Paretooptimal front or Pareto frontier when they are plotted in the objective space. In general, its not easy to find an analytical expression of the line or surface that contains these Pareto Frontier points and, in most cases, it turns out to be impossible.
The normal procedure to generate the Pareto frontier is to compute many solutions in and their corresponding points in . When theres a sufficient number of these, then its
possible to determine the nondominated points and to produce the pareto frontier.
Mathematically, for a given MOO problem , and Pareto optimal set , the Pareto frontier is defined as:

Weak Pareto Optimality
A solution is a weak Paretooptimal if there is no such that for .

Strict Pareto Optimality
A solution is strictly Paretooptimal if there is no such that for .

Special Solutions and Points
There are some related definitions of special solutions which are often used in MOO algorithms. The following subsection provides some discussion about them.

Ideal Design Vector & Ideal Objective Vector
For each M conflicting objective functions, there exists one different optimal solution. An objective vector constructed with these individual optimal objective values constitutes the ideal objective vector
Let be a vector of design
variables which optimizes (either minimizes or maximizes) the mth objective function . This vector is called ideal solution or ideal design vector. To determine this solution, the minimum (or maximum) attainable objective values for all objective functions should be found separately. Assuming this minimum (or maximum) of each mth objective function could be found as:
Then, the vector is the ideal objective vector for a MOO problem
In general, corresponds to a nonexistent solution, because the minimum solution for each function need not be the same solution. is used as a reference solution that solutions closer to it are better. Moreover, many algorithms require the knowledge of the lower bound on each objective function to normalize objective values in a common range.
The only way a corresponds to a feasible solution is when the minimal solutions to all objective functions are identical. In this case, the objectives are not conflicting to each other and the minimum solution to any objective function would be the only optimal solution to the MOO problem. [4]

Utopian Objective Vector
The ideal objective vector denotes an array of the lower bound of all objective functions. This means that for every objective function there exists at least one solution in the feasible search space sharing an identical value with the corresponding element in the ideal solution. Some algorithms may require a solution which has an objective value strictly better than (and not equal to) that of any solution in the design space. For this purpose, the utopian objective vector is defined as follows:
A utopian objective vector has each of its components marginally smaller than that of the ideal objective vector, or with for all i = 1, 2, , M.

Nadir Objective Vector
Unlike the ideal objective vector which represents the lower bound of each objective in the entire feasible search space, the nadir objective vector represents the upper bound of each objective in the entire Paretooptimal set and not in the entire search space. A nadir objective vector must not be confused with worst objective vectors marked as W in Figure found by using the worst feasible function values in the entire search space.
Although the ideal objective vector is easy to compute (except in complex multimodal objective problems), the nadir objective vector is difficult to compute in practice. However, for wellbehaved problems, the nadir objective vector can be derived from ideal objective vector by using the payoff table method. For two objectives, if
And
are coordinates of the minimum solutions of respectively, in the objective space, then the nadir vector can be estimated as:
The nadir objective vector may represent an existent or a nonexistent solution, depending in the convexity and continuity of the Paretooptimal set. In order to normalize each objective in the entire range of the Paretooptimal region, the knowledge of nadir and ideal objective vectors can be used as follows:
Fig. 4. Multiobjective optimization methods
the DM is a person who can give further preference information concerning the Pareto optimal solutions., many approaches have
Fig. 5. Multiobjective optimization methods classified based on the existence of DM preferences


MULTIOBJECTIVE OPTIMIZATION METHODS
The ultimate goal of solving a MOO problem is to identify Paretooptimal solutions. To achieve this goal, using exact, heuristics or metaheuristic methods become more complicated and cannot guarantee that those optimal solutions will be found. As the DM is a person who can give further preference information concerning the Paretooptimal solutions., many approaches have been developed with respect to his role to facilitate the process of solving MOO problems. Figure is dividing them into four main categories as shown in Fig. 5 [5] [6] [7].

Nopreference Articulation Methods
No articulation of preference information method is used only when the DM is not available, suh as the cases of online optimization where the tasks that need to be solved quickly in
a time span between ten milliseconds to a few minutes [8]. These methods provide only one solution to get computed.
An example of these methods is the socalled global criterion method that aims to minimize the distance to the ideal objective vector.
Different metrics can be used in this evaluation such as – metric. The metric , , is a norm metric on
, defined by , where the norm is defined by .
Minimize
where:

When , its a maximum metric and it becomes a nonsmooth optimization problem.

When , the solution obtained is a Paretooptimal solution.

When , the solution obtained is a weakly Pareto optimal solution.


APriori Preference Articulation Method
This approach is based on a prior articulation of preferences. It requires DM to reach an assent about the relative importance (weight) of each objective. The preferences of DM are then used in a technique called scalarization, i.e. aggregation of multiple objectives, that converts a MOO problem into a SOO problem which can be solved using a variety of solution approaches.
However, in many applications, it is difficult for DM to devise a satisfactory weighting scheme for scalarization, because some features of a problem are not fully understood during the early stages of decision making. Moreover, some objectives may be formulated in complex mathematical forms that are difficult for nonanalysts to understand. Indeed, some objectives are qualitative like aesthetic, cultural or other realms that are expensive to get quantified.
Weighted Sum Method (shown in Fig. 6) is considered one of this method examples. Its based on scalarization of a set of multiple objectives into a single objective by adding each objective premultiplied by a DM supplied weight
. Then, a weight of an objective is chosen in proportion to the relative importance of the objective.
Above, the are weights given by the DM representing the relative importance of the objectives. If weight it means that the DM appreciates improvement on objective more than on objective .
Fig. 6. Weighted sum method to solve minimization problem of two functions
Minimize:
Where:
,
Subject to:
n number of bound(s)
i = 1, 2, , n
J number of inequality constraint(s)
j= 1, 2, , J
K number of equality constraint(s) , k= 1, 2, , K

Interactive (Prgressive) Preference Articulation Method This approach is based on an interactive (or progressive) articulation of preferences, in which the DMs preferences are refined and incorporated into the search process. During each iteration of the process, DM is presented a (typically small) subset of nondominated solutions, and based on these solutions they provide local information about his preferences for objectives. Then a SOO problem is formulated and solved. Solutions to this problem are used by DM to improve his understanding of the problem and to adjust his preferences, which can be used to form a new problem. This process repeats until DM is satisfied.
Although these methods can be used to encourage the participation of DM, there is no guarantee that an acceptable solution will be reached, and even if such a solution is identified, it cannot be guaranteed to be Paretooptimal.
Interactive decision making has become popular during the past several decades, and a large number of methods have been developed in the literature. This is partly due to the more intensive involvement of DM in the process of searching for alternative solutions. This process can lead to more satisfactory final decisions (compared to prior approaches). However, interactive methods are often based on the generation of a small number of alternatives and they therefore may overlook important nondominated solutions. One of popular examples of this method is satisficing trade off analysis method and method of steuer.

APosteriori Preference Preference Articulation Method This approach is based on a posterior articulation of preferences. It does not require the intensive participation of DM during the process of generating alternatives. Instead, the application of this approach depends on methods that can be used to generate a diverse set of Pareto optimal solutions that are evenly distributed on the Pareto frontier; these solutions are subsequently presented to DM who make a final decision about the problem by examining and negotiating about the merits of alternatives.
The major difficulties to apply this approach are: First, it not easy to develop solution methods that can effectively generate the Pareto frontier. Traditionally, prior articulation methods have been used to generate the Pareto optimal solutions by systematically adjusting the associated parameters (e.g., preference weights) in order to yield
Drawbacks
Do not take into account which problem is solved.
Example
Global criterion method.
Apriori Methods
Definition
Methods where the DM articulates preferences before optimization.
Idea
Benefits
Computed PO solutions are based on the preferences of the DM (no unnecessary solutions).
Drawbacks
It may be difficult for the DM to express preferences before he has seen any solutions.
Example
Weighted Sum Method.
Interactive (Progressive) Methods
Definition
Methods that allow the DM to guide the search by alternating optimization and preference articulation iteratively
Idea
– Solution process is iterative:
– Solution process ends when the DM is satisfied with the PO solution obtained.
Benefits
Drawbacks
Example
Satisficing tradeoff analysis method.
Aposteriori Methods
Definition
Methods where the DM articulates preferences after optimization.
Idea
Benefits
Drawbacks
Example
MOEAs.

Ask first the preferences of the DM, then optimize using the preferences.

Only such PO solutions are produced that are of interest to the DM.

Initialization: compute some PO solution(s).

Show PO solution(s) to the DM.

Is the DM satisfied? If no, ask the DM to give new preferences. Otherwise, stop. A most preferred solution has been found.

Compute new PO solution(s) by taking into account new preferences. Go to step 2.

Only such solutions are computed that are of interest to the DM.

DM is able to steer the solution process with his/her preferences.

DM can learn about the interdependences between the conflicting objectives trough the solutions obtained based on the preferences which helps adjusting the preferences.

DM has to invest a lot of time in the solution process.

High influence of the DM on the process is needed.

If computing PO solutions takes time, DM does not necessarily remember what happened in the early phases.

Compute different PO solutions, then DM selects the most preferred one.

Approximation of the PO set (or part of it) is provided.

Well suited for problems with 2 objectives since the PO solutions can be easily visualized for the DM.

Understanding of the whole PO set.

Approximating the PO set often time consuming.

DM has to choose the most preferred solution among large number of solutions.

Visualization of the solutions for high number of objectives.
Drawbacks
Do not take into account which problem is solved.
Example
Global criterion method.
Apriori Methods
Definition
Methods where the DM articulates preferences before optimization.
Idea
Benefits
Computed PO solutions are based on the preferences of the DM (no unnecessary solutions).
Drawbacks
It may be difficult for the DM to express preferences before he has seen any solutions.
Example
Weighted Sum Method.
Interactive (Progressive) Methods
Definition
Methods that allow the DM to guide the search by alternating optimization and preference articulation iteratively
Idea
– Solution process is iterative:
– Solution process ends when the DM is satisfied with the PO solution obtained.
Benefits
Drawbacks
Example
Satisficing tradeoff analysis method.
Aposteriori Methods
Definition
Methods where the DM articulates preferences after optimization.
Idea
Benefits
Drawbacks
Example
MOEAs.

Ask first the preferences of the DM, then optimize using the preferences.

Only such PO solutions are produced that are of interest to the DM.

Initialization: compute some PO solution(s).

Show PO solution(s) to the DM.

Is the DM satisfied? If no, ask the DM to give new preferences. Otherwise, stop. A most preferred solution has been found.

Compute new PO solution(s) by taking into account new preferences. Go to step 2.

Only such solutions are computed that are of interest to the DM.

DM is able to steer the solution process with his/her preferences.

DM can learn about the interdependences between the conflicting objectives through the solutions obtained based on the preferences which helps adjusting the preferences.

DM has to invest a lot of time in the solution process.

High influence of the DM on the process is needed.

If computing PO solutions takes time, DM does not necessarily remember what happened in the early phases.

Compute different PO solutions, then DM selects the most preferred one.

Approximation of the PO set (or part of it) is provided.

Well suited for problems with 2 objectives since the PO solutions can be easily visualized for the DM.

Understanding of the whole PO set.

Approximating the PO set often time consuming.

DM has to choose the most preferred solution among large number of solutions.

Visualization of the solutions for high number of objectives.
different solutions. The problem with this approach, however, is that it may overlook important solutions, especially when the Pareto front contains concave, and/or discontinuous sections. Second, the existence of a large number of non dominated solutions will impose a substantial cognitive burden on DM who must somehow select a solution from the multitude of alternatives.
An important advantage of the posterior approach is also clear: a full representation of the Pareto front can present the true multiobjective structure of the problem, which may lead to a better decision. If an intuitive and userfriendly decision support tool is available, stakeholders can concentrate on examining and negotiating tradeoffs among interesting solutions. This approach may also foster a wider participation from stakeholders because they may be able to find niche solutions that are beneficial to their view of a problem and its resolution.
Multiobjective optimization evolutionary algorithms (MOEAs) are one of the most used examples of applying a posteriori preference articulation. MOEAs are often classified into three main groups: aggregationbased, dominancebased and performance indicatorbased algorithms. Aggregation based algorithms decompose MOO problem into a number of singleobjective subproblems and subsequently solve them simultaneously. One of the commonly used aggregation based MOEA algorithms is MOEA/D.
Dominancebased algorithms are the most common type of MOEAs in the literature and are based on the Pareto dominancebased evaluation of individuals. A commonly used dominancebased MOEAs is NSGAII. Finally, indicatorbased algorithms use an indicator function (a measure of the area dominated by the Pareto optimal front) to gauge the quality of the population in an MOEA.
Over the past few decades MOEAs have been increasingly used in practice due to advantages such as, a set of representative Pareto optimal solutions can be obtained in a single run, multiple local, discrete, and nonconvex Pareto optimal fronts and different types of variables, objective functions, and constraints can be easily handled. However, they are also equally criticized for their lack of convergence proof, being computationally very expensive and the need to set a number of algorithm parameters such population size etc.


CONCLUSION
Throughout the brief overview of the methods available in the literature of MOO, this research concludes 4 main classifications of those methods presented with a brief explanation of the method definition, idea, benefits, drawbacks, and examples. Table. 1 provides a summary of each of the four main classifications. This could provide an overview to researchers and practitioners about the field of MOO as a whole and thereby promote its utilization among the industries.
TABLE I.
No preference
Definition
Methods where the DM is not available
Idea
Compute some PO solution.
Benefits
Fast methods as one PO solution is enough and there is no communication needed with the DM.

REFERENCES

D. Kalyanmoy, Multiobjective optimization using evolutionary algorithms: an introduction, KanGAL, Indian Institute of Technology Kanpur, February 2011.

Maier. H .R. et al, Introductory Overview: Optimization Using Evolutionary Algorithms and Other Metaheuristics, Environmental Modelling & Software, vol. 114, pp. 195213, April 2019.

A. Ajith, J. Lakhmi, Evolutionary Multiobjective Optimization, Advanced Information and Knowledge Processing (AI&KP), Springer, London, 2005.

D. Kalyanmoy, Multiobjective optimization using evolutionary algorithms, Wiley interscience series in systems and optimization, John Wiley & Sons, Ltd, England, 2001.

M. Annelies De, O. Catheline, O. Jos Van, C. Dirk, Towards sustainable biomassforbioenergy supply chains by trading off between multiple objectives, Young Researchers Conference – Biomass. World Sustainable Energy Days, Wels, Austria, 2005.

D. W. O. Ladislas, Multiobjective optimization: history and promise, Third ChinaJapanKorea Joint Symposium on Optimization of Structural and Mechanical Systems, vol. 2, January 2004.

C. Judyta, B. W. Neil, Multicriteria optimization in architectureal design goaloriented methods and computaional morphogenisis, shapes of logic everything what surround us can be described, Oficyna Wydawnicza Politechniki Wrocawskiej, Wrocaw, Poland, 2016.

W. Thomas, Global optimization algorithms: theory and application, 2009, selfpublished.