Multi-objective combinatorial optimization problems
A method of solving a multi-objective combinatorial optimization problem (MOCOP) is to aggregate the
objective functions into a single utility function. In spsann, the aggregation
is performed using the weighted sum method, which incorporates in the weights the preferences of
the user regarding the relative importance of each objective function.
The weighted sum method is affected by the relative magnitude of the different function values. The
objective functions implemented in spsann have different units and orders of magnitude.
The consequence is that the objective function with the largest values may have a numerical dominance
during the optimization. In other words, the weights may not express the true preferences of the user,
resulting that the meaning of the utility function becomes unclear because the optimization will favour the
objective function which is numerically dominant.
A reasonable solution to avoid the numerical dominance of any objective function is to scale the objective
functions so that they are constrained to the same approximate range of values. Several
function-transformation methods can be used for this end and spsann has four of them available.
The upper-lower-bound approach requires the user to inform the maximum (nadir point) and minimum
(utopia point) absolute function values. The resulting function values will always range between 0 and 1.
The upper-bound approach requires the user to inform only the nadir point, while the utopia
point is set to zero. The upper-bound approach for transformation aims at equalizing only the upper bounds
of the objective functions. The resulting function values will always be smaller than or equal to 1.
In most cases, the absolute maximum and minimum values of an objective function cannot be calculated
exactly. If the user is uncomfortable with guessing the nadir and utopia points, there an option
for using numerical simulations. It consists of computing the function value for many random system
configurations. The mean function value obtained over multiple simulations is used to set the nadir point,
while the the utopia point is set to zero. This approach is similar to the upper-bound approach, but the
function values will have the same orders of magnitude only at the starting point of the optimization.
Function values larger than one are likely to occur during the optimization. We recommend the user to avoid
this approach whenever possible because the effect of the starting configuration on the optimization as a
whole usually is insignificant or arbitrary.
The upper-lower-bound approach with the minimum and maximum attainable values of the objective
functions that compose the MOCOP, also known as the Pareto minimum and maximum values, is the most
elegant solution to scale the objective functions. However, it is the most time consuming. It works as
follows:
Optimize a sample configuration with respect to each objective function that composes the MOCOP;
Compute the function value of every objective function that composes the MOCOP for every optimized
sample configuration;
Record the minimum and maximum absolute function values attained for each objective function that
composes the MOCOP -- these are the Pareto minimum and maximum.
For example, consider ACDC, a MOCOP composed of two objective functions: CORR and
DIST. The minimum absolute attainable value of CORR is obtained when the sample configuration
is optimized with respect to only CORR, i.e. when the evaluator and generator objective functions
are the same (see the intersection between the second line and second column in the table below). This is
the Pareto minimum of CORR. It follows that the maximum absolute attainable value of CORR is
obtained when the sample configuration is optimized with regard to only DIST, i.e. when the
evaluator function is difference from the generator function (see the intersection between the first row
and the second column in the table below). This is the Pareto maximum of CORR. The same logic
applies for finding the Pareto minimum and maximum of DIST.
|
Evaluator |
Generator |
|
|
|
DIST |
CORR |
|
DIST |
0.5 |
8.6 |
|
CORR |
6.4 |
0.3 |