 |
|
The multi-objective optimization problem can be expressed as follow:
and it is obvious that in general the solution is not unique if the functions are not linearly dependent. With the introduction of the Pareto dominance concept it is possible to divide any group of solutions into two subgroups: the "dominated" and the "non dominated" one.
Solutions belongings to the second group are the "efficient" solutions, i.e. the ones for which it is not possible to increase any objective value without deteriorating the values of the remaining objectives.
In more formal terms and in the case of maximization problems it is possible to say that the solution
dominates 
if the following relation is true:
Classical optimization algorithms are capable, under strict continuity and derivability hypothesis, of finding the optimal value only in the single objective case and therefore the problem of finding the group of non dominated solutions (the Pareto Set) is reduced to several single objective optimization where the objective becomes a weighted combination of the objectives called utility function Obj:
Where is the vector of variables and 
are the weights for the objectives 
A more sophisticated and effective way to transform a multi-objective problem into a single-objective problem is the use of an Utility Function that is not a simple weighted sum of objectives but that is a non-linear combination of the objectives, i.e. the weights are not constant but are given as a monotone function of the objective value as necessary when comparing objectives of totally different nature like cost and performances. In the following figure the meaning of Total Utility is clarified.
While traditional optimization algorithm do need the use of an utility function, the particular structure of GA can face the multi-objective optimization problem in a more direct way developing populations in which the diversities follow the conflicting objectives.
Pareto-GA algorithms mainly differ from classical GA in the selection process even though other specific operators might be constructed.
A quick review of Pareto-GA techniques is given in the following.
An effective way of maintaining diversity in the population able to follow the conflicting objectives can be the use of Local Selection schema based on the Pareto dominance concept. In this case the population is placed on a toroidal grid and the members of the local tournament are chosen by means of a random walk in the neighborhoods of the given grid point.
the dominant individual (in a multi objective sense) of a tournament defined by a local random walk is selected.
When a multi objective optimization task must be performed the fitness differences can be substituted with the differences of the respective scalar products of the finesses vector in the direction given by the fitness of the individual to be reproduced :
where 
, 
and
.
The selection of individuals i1 and i2 can be done using any available selection schema.
In this way global information about the fitness landscape are retained in the whole population while each individual maintain and improve their specialization through the evolution.
A variant of this schema is the one that uses an approach more close to a Nash equilibrium concept as follow:
