Multi-Objective Differential Evolution Algorithm for Solving Engineering Problems

INTRODUCTION

Evolutionary Algorithms (EAs) are some of the most widely used algorithm for solving Multi-objective Optimization Problems (MOPs). EAs are applied to a wide range of problems from science to engineering design problems. They are powerful optimization algorithms for solving complex real-world MOPs in a single run. The primary reason why a problem has a multi-objective formulation is that it is not possible to have a single solution that optimizes all objectives. Therefore, an algorithm that gives a large number of alternative solutions lying on or near the Pareto-optimal front is of great practical value. In multi-objective optimization, there may not exist a solution that is best with respect to all objectives, instead, there are equally good solutions that are known as Pareto optimal solutions (Deb, 2001). A Pareto optimal set of solutions is such that when we go from any one point to another in the set, at least one objective function improves and at least one other worsens (Babu and Jehan, 2003). Neither of the solutions dominates over each other and all the sets of decision variables on the Pareto are equally good. Evolutionary algorithms have the ability to find multiple Pareto optimal solutions in one single simulation run because of their population-approach. There are two goals in multi-objective optimization. The goals are to discover solutions as close to the Pareto-front as possible and to find solutions as diverse as possible in the obtained non-dominated front.

Several studies have extended evolutionary algorithm to solve multi-objective numerical optimization problems (Deb, 2001; Deb et al., 2002; Madavan, 2002; Babu and Jehan, 2003; Xue et al., 2003; Rakesh and Babu, 2005; Babu et al., 2005; Robic and Filipic, 2005; Santana-Quintero and Coello, 2005; Fan et al., 2006; Reddy and Kumar, 2007). Over the past decade, a number of Multi-objectives Evolutionary Algorithms (MOEAs) have been suggested (Deb, 2001). Recently, researchers have extended Differential Evolution (DE) which is a family of EA to solve MOPs. It has been successfully used in solving single objective problems. Differential evolution is a very simple population-based, stochastic function minimizer and very powerful at the same time. DE handles continuous, discrete and integer variables. In terms of constraints, DE can handle multiple constraints. It has the advantages of simple structure, ease of use, speed and robustness. It does not make use of some probability distribution function in order to introduce variations into the population but instead, it uses the difference between randomly selected factors (individuals) as source of random variation for a third vector (individual), referred to as the target vector. Hence, the trial solutions which will compete with the parent solution are generated by adding the weighted difference vectors to the target vector.

Pareto Differential Evolution (PDE) proposed by (Abbass and Sarker, 2002) was the first algorithm to extend DE to MOPs. The PDE was compared to SPEA (Zitzler and Thiele, 1999) on two test problems and PDE was found to outperform it. Other studies by Madavan (2002), Xue et al. (2003) and Robic and Filipic (2005) have proposed Pareto Differential Evolution Approach (PDEA), Multi-Objective Differential Evolution (MODE) and Differential Evolution for Multi-Objective Optimization (DEMO), respectively. All these algorithms perform well on test problems.

Multi-Objective Differential Evolution (MODE) was proposed by Babu and Jehan (2003) and Babu et al. (2005). In the algorithm, the dominated solutions are removed from the population in each generation. Only the non-dominated solutions are allowed to undergo DE operations of mutation, crossover and selection. So, at each generation, the population size reduces. The offspring are placed into the population if they dominate the parents. The algorithm worked well on the test problems but the number of non-dominated solutions generated was few. The dominated solutions that are removed from the population initially can still be improved using the DE operations. During mutation stage, they may be combined with other vectors to produce offspring that may replace them instead of just removing them. In this way, at the end of the generation, the number of non-dominated solutions is increased with quality members giving wider Pareto optimal fronts. In the original DE with single objective, most of the initially generated solutions are infeasible. They undergo mutation and crossover before they are improved to be feasible. In the same way, the solutions in each generation should be allowed to mutate, recombine and undergo crossover. The solutions in the final generation are the only ones to be checked for domination. Therefore, domination check is done once instead of doing it in all the generations thereby reducing the number of function evaluation.

The algorithm proposed by Fan et al. (2006) is implemented by modifying the selection scheme of DE. In their selection scheme, the trial population is compared with its counterpart in the current population. If the trial candidate dominates the current population member it will survive from the tournament selection to the population of the next generation and replaces the current population otherwise the current population is retained. They suggest that if the trial solution is worse than the target solution in any one of the objectives, it should be discarded.

A new DE algorithm for Multi-Objective Optimization Problems (MOOPs) is proposed in this study and it is called multi-objective differential evolution algorithm (MDEA). The DE algorithm proposed is based on the existing DE algorithm proposed by Price and Storn (1997). The only difference is its implementation of multi-objectives.

MULTI-OBJECTIVE DIFFERENTIAL EVOLUTION ALGORITHM (MDEA)

MDEA combines the advantages of algorithm by Fan et al. (2006) and Babu and Jehan (2003) while overcoming the shortcomings of the algorithms. In this way, MDEA runs faster with more quality Pareto optimal solutions. The description of the MDEA is as follows. The vectors are randomly generated to create initial vectors and solutions to the problem. The generated solutions are allowed to undergo mutation, crossover and selection for the number of generations chosen. The solutions that evolve in the final generation are checked for domination and the dominated solutions are removed. The selection procedure of MDEA is similar to (Fan et al., 2006). The trial solution survives to the next generation if its objective function is better or equal in all the objectives to the target solution. MDEA will produce many non-dominated solutions on the Pareto front than the algorithm by Fan et al. (2006) and Babu and Jehan (2003). Moreover, the algorithm by Fan et al. (2006) has not been modified to handle constraints except bound constraints. MDEA can handle multiple constraints. If any of the constraints is violated, a high value (10⁸) is added to the objective function to make the solution infeasible (Deb, 2001). In this way, the solution will not be selected when compared with other solutions because of high value. MDEA uses a constant population structure like traditional DE. The final population is the same like the initial population. So the number of non dominated solutions are less than or equal to population size. This is an excellent advantage of MDEA over algorithms by Fan et al. (2006) and Babu and Jehan (2003). Though the proposed MDEA can be used on any strategy, the strategy used in this study is DE/rand/1/bin which is the most widely used of all the ten strategies of DE.

The proposed MDEA methodology can be summarized in the following pseudo code steps:

The steps above are followed, using the pseudo code below, to code the algorithm in MATLAB 7.0 (The MathWorks Inc., USA) and is executed on a 1.7GHz, 2GB RAM PC and tested on some test problems below to demonstrate its ability to solve MOPs.

The Pseudo Code for Multi-Objective Differential Evolution Algorithm (MDEA):

*Initialize the values of D, NP, Cr, F, k (number of objective functions) and maximum generation (MAXGEN)

*input the boundary constraints of the problem

*Initialize all the vectors of the population randomly

*remove the dominated solutions from the last generation using naïve and slow method proposed by Deb (2001) print the results

EVALUATION AND RESULTS

Test problems: Deb (1999) suggested systematic ways of developing test problems for multi-objective optimization. Zitzler et al. (2000) followed these steps and suggested well known 6 test problems. Five of the test problems (ZDT1, ZDT2, ZDT3, ZDT4 and ZDT5) which are common benchmark domains used in literatures (Deb et al., 2002; Madavan, 2002; Xue et al., 2003), are chosen for evaluating the performance of our methods. These test problems have no constraints. Each of them illustrates a different class of problems. All the problems have two objectives, f₁(x) and f₂(x) which are minimized. The description of the test functions are shown in Table 1.

Performance measures: The common trend in the development of many successful solution methodologies, including multi-objective evolutionary algorithms is to compare these in terms of their performance on various test problems. In a multi-objective optimization, there are two goals unlike single-objective optimization. The two goals are; discover solutions as close to the Pareto-optimal solutions as possible and find solutions as diverse as possible in the obtained non-dominated front. A good multi-objective evolutionary algorithm will be known if both goals are satisfied (Deb, 2001). Therefore, there is a need to have at least two performance metrics for adequately evaluating both goals of multi-objective optimization. One performance metric evaluates the progress towards the Pareto-optimal front and the other evaluates the spread of solutions. Many performance metrics have been proposed in the literatures. The descriptions of three common metrics used are given below though in this study, two performance metrics will be used to evaluate MDEA. They are convergence metric Υ and diversity metric Δ.

Convergence metric Υ: This metric measures the distance between the obtained non-dominated front, Q and the set, P* of the Pareto-optimal solutions. It is defined as:

(1)

where, Q is the number of non-dominated vectors found by the algorithm being analyzed and d_i is the Euclidean distance (in the objective space) between the obtained non dominated front Q and the nearest member in the true Pareto front P.

Table 1:	Test problems used in this study

Generational Distance (GD): This metric measures the average distance of the solutions of Q obtained from the set P* of the Pareto-optimal solutions. It is defined as:

(2)

where, d_i is the Euclidean distance (measure in the objective space) between non-dominated front Q and the nearest member in the true Pareto-front P. It should be noted that an algorithm having a small value of GD is better.

Diversity metric Δ: This metric measures the extent of spread achieved using the non-dominated solutions. It is defined as:

(3)

where, d_i is the Euclidean distance (measured in the objective space) between consecutive solutions in the obtained non-dominated front Q and is the average of these distances. The parameter d_f and d_l are the Euclidean distances between the extreme solutions of the Pareto front P* and the boundary solution of the obtained front Q. Also an algorithm having a smaller value of diversity metric Δ is better.

Cantilever design problem: MDEA is further tested on an engineering design problem of cantilever design (Deb, 2001). Figure 1 shows a schematic representation of a cantilever beam. Figure 1 presents the end load P, the length l and the diameter d. The problem has 2 decision variables of diameter (d) and length (l). The beam will carry an end load P. There are 2 conflicting objectives that should be minimized; the weight f₁ and end deflection f₂. Minimizing the weight, f₁, will result in an optimum solution that will have small dimensions of d and l. If the dimensions are small, the beam will not be adequately rigid and the end deflection of the beam will be large. If on the other hand, the beam is minimized for end deflection, the dimensions of the beam will be large, thereby making the weight of the beam to be large.

Fig. 1:	A schematic representation of a cantilever beam

There are 2 constraints in this design problem. They are; the maximum stress, σ_max is less than the allowable strength S_y and the end deflection, δ is smaller than a specified limit of δ_max. The constrained optimization problem is formulated as follows:

Objective function 1: Minimization of weight

(4)

Objective function 2: Minimization of end deflection

(5)

The objective functions 2 are subjected to the following constraints:

Constraint 1: Maximum stress

The maximum stress should be less than the allowable strength, S_y:

(6)

Constraint 2: End deflection

The end deflection, δ should be smaller than a specified limit of δ_max

(7)

Bound constraints:

(8)

(9)

where, ρ, P, d and l are the density, force, diameter and length respectively. The maximum stress is calculated as follows:

(10)

The following parameter values are used:

ρ = 7800 kg m^-3, P = 1000 N, E = 207 GPa, S_y= 300 MPa and δ_max= 5 mm