MULTIOBJECTIVE OPTIMISATION USING GENETIC PROGRAMMING


 
 

MULTIOBJECTIVE OPTIMISATION

    In a multiobjective optimisation problem, there are more than one objective function, each of which may have adiiferent individual optimal solution. If there is sufficient difference in the optimal solutions corresponding to different objectives, the objectives functions are known as conflicting to eachother.
    So in the presence of multiple and conflicting objectives, the resulting optimisation problem givs rise to a set of optimal solutions, instead of a single optimal solution. Multiple optimal solutions exist because no one solutions can be optimal for multiple conflicting objectives.
    Multiobjective optimisation (also called multicriteria optimisation, multiperformance or vector optimisation) can be defined as the problem of finding [Osyczka,1985]:
A vector of decision variables which satisfies constraints and optimises a vector function whose lements represent the objective functions. These functions form a mathematical description of performance criteria which are usually in conflict with each other. Hence, the term "optimise" means finding such a solution which would give the values of all the objective functions acceptable to the designer.

Formally, we can state it as follows :

Find the vector,  x* = [x1*,x2*,.......,xN*] which satisfies :

the M inequality constraints:  Gi (x*) >=0     i=1,2,....,M
the P equality constraints    :  Hi(x*)     =0     i=1,2,....,P
and optimises the vector  function f(x*) = [f1(x*),f2(x*),.....,f3(x*)] (transpose)
where x*=[x1,x2,.....,xN]  (transpose) is the vector of decision variables.
    In other words, we wish to determine from among the set F of all numbers which satisfy (1) & (2) the particular set x1*,x2*,....xK* which yields the optimum values of all the objectives functions.

PARETO OPTIMUM

    x* is pareto optimal if there exists no feasible vextor x* which would decrease some criterion without causing a simultaneous increase in at least one other criterion [Coello,1998]. Pareto optimum almost always gives multiple solutions called non-inferior or non-dominated solutions.
    In other words, for problems having more than one objective functiion (say, Fj, j=1,2,...,M and M>1), any two solutions x(1) and x(2) (having P decision variables each) can have one of the two possibilities- one dominates the other or none dominates the other. A solution x(1) is said to dominate the other solution x(2), if both the following conditions are true [Deb,1999]:
  1. The solution x(1) is no worse than x(2) in all objectives.
  2. The solution x(1) is strictly better than x(2) in atleast one objective.

PARETO FRONT

    The set of all such solutions which are non-dominated constitute the pareto front. These solutions are in the boundary of the design region, or in the locus of the tangent points of the objective functions. In general, it is not easy to find an analytical expression of the line or surface that contains these points, and the normal procedure is to compute the points belonging to the pareto-optimal front and their corresponding function values for each of the objectives. When we have sufficient amount of these, we may proceed to take the final decision.

EXAMPLE

    [Deb,1999]. Consider a design problem in the manufacturing of a car, where cost and accident-rate (a measure of safety) are the two objective functions. Then the minimally accident-rate solution is not with the least cost and that with the least cost is not with the minimum accident rate. Thus here the objectives are conflicting with eachother. Thus there is a set of optimal solutions where noone can be considered to be better than any other with respect to the two objective function values.
    In the figure, one cannot say whether A is better than B or vice-versa. One solution is better than the other on one-objective and worse in the other. However C is not a member of the pareto-optimal set for there exists a solution D which is better than C in both the objective functions. The dotted hyperbola constitutes the pareto-optimal front. A, B ... constitute the non-dominated solutions while C is a dominated solution.


THE CONCEPT OF A PARETO-OPTIMAL FRONT