Pareto dominance

Fishburn (1971) has suggested strengthening the Pareto principle to require that removing a Pareto dominated alternative from Y does not change the social choice set. He calls this condition the reduction principle, RP. 

Use of relaxed forms of dominance Some researchers have proposed the use of relaxed forms of Pareto dominance as a way of regulating convergence of a MOEA. Laumanns et al (2002) proposed the so-called C-dominance. This mechanism acts as an archiving strategy to ensure both properties of convergence towards the Pareto-optimal set and properties of diversity among the solutions found. Several modem MOEAs have adopted the concept of f-dominance (see for example... 

A multi-criteria optimization problem generally consists of n decision variables, m constraints, and k evaluation functions. Thereby the evaluation functions can be in conflict with each other, making it difficult to find the global optimum. To find this optimum, the solution space /I C R is created by the decision variables x = (xi, , x ) of the decision space Q with the objective function vector F O A The objective function vector F x) = (/ j(x), , / (x), X e O is optimized considering the constraints / (—x) > 0 = 1,... m x Q (Muschalla 2006). The individual fitness value of each fitness function then can be processed by the evaluation function in different ways. This can be done by a scalarization method or a Pareto dominance-based approach. 

For the evaluation of multiple fitness functions without reducing the fitness functions to a single value in order to avoid the above disadvantages, the Pareto Dominance approach is applicable. This approach is based on the principle that one solution dominates another solution if they are equal in each property (fitness function), but at least one property is better. Mathematically, the concept of Pareto dominance can be described as follows for a minimization problem (Muschalla 2006) ... 

Pareto dominance Check each generation for Pareto dominance and sort individuals ac cording to their domination level. 

When tackling a multi-objective problem by GAs, various approaches to fitness definition may be adopted Fonseca (1995). In what follows we will resort to the so called Pareto-based methods Goldberg (1989) once a population of chromosomes has been created, these are ranked according to the Pareto dominance criterion by looking at the /-dimensional space of the fitnessesfi U), i = Firstly,... 

Figure 3 shows the Pareto dominance front obtained by the genetic algorithm at convergence after 10 generations the circle represents the original network with... 

IfZ) > q or D probability pair with the allocation rule . iq> D> q the order quantity q leads to the probability pair [1,1] for the supplier and retailer. Hence, q Pareto dominates q under the case oi q> D > q . In summary, the order quantity q is Pareto optimal. 

Fonseca and Fleming (1993) proposed a modification of the simple genetic algorithm (SGA) at the selection level. The basic concepts of the proposed MOGA are the ranking based on the Pareto dominance and sharing function. The Pareto dominance-based rank is the same as one plus the number that certain individual dominates... 

Figure 3. Multi-objective ranking based on the Pareto dominance...

Uses the concept of the Pareto dominance in order to assign scalar fitness values to individuals. 

The varianee equation provides a valuable tool with whieh to draw sensitivity inferenees to give the eontribution of eaeh variable to the overall variability of the problem. Through its use, probabilistie methods provide a more effeetive way to determine key design parameters for an optimal solution (Comer and Kjerengtroen, 1996). From this and other information in Pareto Chart form, the designer ean quiekly foeus on the dominant variables. See Appendix XI for a worked example of sensitivity analysis in determining the varianee eontribution of eaeh of the design variables in a stress analysis problem. 

Plotting this data as a Pareto chart gives Figure 3. It shows that the load is the dominant variable in the problem and so the stress is very sensitive to changes in the load, but the dimensional variables have little impact on the problem. Under conditions where the standard deviation of the dimensional variables increased for whatever reason, their impact on the stress distribution would increase to the detriment of the contribution made by the load if its standard deviation remained the same. 

When optimizing multiple objectives, usually there is no best solution that has optimal values for all, and oftentimes competing, objectives. Instead, some compromises need to be made among various objectives. If a solution A is better than another solution B for every objective, then solution UB is dominated by A. If a solution is not dominated by any other solution, then it is a nondominated solution. These nondominated solutions are called Pareto-optimal solutions, and very good compromises for a multiobjective optimization problem can be chosen among this set of solutions. Many methods have been developed and continue to be developed to find Pareto-optimal solutions and/or their approximations (see, for example, references (50-52)). Notice that solutions in the Pareto-optimal set cannot be improved on one objective without compromising another objective. 

In contrast to single-objective problems where optimization methods explore the feasible search space to find the single best solution, in multi-objective settings, no best solution can be found that outperforms all others in every criterion (3). Instead, multiple best solutions exist representing the range of possible compromises of the objectives (11). These solutions, known as non-dominated, have no other solutions that are better than them in all of the objectives considered. The set of non-dominated solutions is also known as the Pareto-front or the trade-off surface. Figure 3.1 illustrates the concept of non-dominated solutions and the Pareto-front in a bi-objective minimization problem. 

Pareto-ranking. The individuals list of scores is subjected to a Pareto-ranking procedure to set the rank of each individual. According to this procedure the rank of an individual is set to the number of individuals that dominate it incremented by 1, thus, non-dominated individuals are assigned rank order 1. 

Secondary population update. Efficiency scores are initially used to update the Pareto-archive. The current Pareto-archive is erased and a subset of the current working population that favours individuals with high efficiency score, i.e. low domination rank and high chromosome graph diversity, takes its place. Note that the size of the secondary population selected is limited by a user-supplied parameter. The secondary population mechanism has been designed specifically to preserve good solutions, non-dominated or dominated but substantially structurally unique, from all... 

Fig. 2 Pareto ranking and dominance for a two-objective problem, minimising/ and/2. A non-dominated individual is one for which there is no other individual that is better in all objectives. In Pareto ranking, an individual s rank corresponds to the number of individuals in the current population by which it is dominated. Solutions A and B are given rank 0 since they are nondominated, whereas solution C is given rank 2 since it is dominated by both A and B...

Figure 5.15. Pareto optimality. The filled circles represent rank zero or nondominated solutions for functions fl and /2. Point C is rank 1 because it is dominated by point B. (Permission as in Fig. 5.14.)...

Deb, K., Mohan, M. and Mishra, S. (2005). Evaluating the f-domination based multiobjective evolutionary algorithm for a quick computation of Pareto-optimal solutions. Evolutionary Computation 13(4), pp. 501-525. 

Fig. 4.12 Plots of non-dominated solutions obtained with NSGA-II-JG after 240,000 -300,000 function evaluations (fn. evals.) and for NSGA-II for 320,000 - 400,000 fn. evals. for the ZDT4 problem. Note that /j and I2 extend over [0, 1] (global Pareto set) for NSGA-II-JG only after about 300,000 function evaluations, and do not show this characteristic for NSGA-II...

Return to an uncrowded base point periodically (so as to generate a more continuous Pareto set, by locally exploring around uncrowded points in the non-dominated set)... 

Knowles, J. D. and Come, D. W. (2000). Approximating the non-dominated front using the Pareto archived evolution strategy, Evol. Comput., 8, pp. 149-172. 

---