The OPTLSO Procedure

Multiobjective Optimization

Many practical optimization problems involve more than one objective criterion, so the decision maker needs to examine trade-offs between conflicting objectives. For example, for a particular financial model you might want to maximize profit while minimizing risk, or for a structural model you might want to minimize weight while maximizing strength. The desired result for such problems is usually not a single solution, but rather a range of solutions that can be used to select an acceptable compromise. Ideally each point represents a necessary compromise in the sense that no single objective can be improved without worsening at least one remaining objective. The goal of PROC OPTLSO in the multiobjective case is thus to return to the decision maker a set of points that represent the continuum of best-case scenarios. Multiobjective optimization is performed in PROC OPTLSO whenever more than one objective function of type MIN or MAX exists. For an example, see Multiobjective Optimization.

Mathematically, multiobjective optimization can be defined in terms of dominance and Pareto optimality. For a k-objective minimizing optimization problem, a point x is dominated by a point y if $f_ i(x)$ $\geq$ $f_ i(y)$ for all i = 1,…,k and $f_ j(x)$ > $f_ j(y)$ for some j = 1,…,k.

A Pareto-optimal set contains only nondominated solutions. In Figure 3.2, a Pareto-optimal frontier is plotted with respect to minimization objectives $f_1(x)$ and $f_2(x)$ along with a corresponding population of 10 points that are plotted in the objective space. In this example, point a dominates $\{ e,f,k\}$ , b dominates $\{ e,f,g,k\}$ , c dominates $\{ g,h,k\}$ , and d dominates $\{ k,i\}$ . Although c is not dominated by any other point in the population, it has not yet converged to the true Pareto-optimal frontier. Thus there exist points in a neighborhood of c that have smaller values of $f_1$ and $f_2$ .

Figure 3.2: Pareto-Optimal Set

In the constrained case, a point x is dominated by a point y if $\theta (x)$ > $\epsilon$ and $\theta (y)$ < $\theta (x)$ , where $\theta (x)$ denotes the maximum constraint violation at point x and FEASTOL= $\epsilon ;$ thus feasibility takes precedence over objective function values.

Genetic algorithms enable you to attack multiobjective problems directly in order to evolve a set of Pareto-optimal solutions in one run of the optimization process instead of solving multiple separate problems. In addition, local searches in neighborhoods around nondominated points can be conducted to improve objective function values and reduce crowding. Because the number of nondominated points that are encountered might be greater than the total population size, PROC OPTLSO stores nondominated points in an archived set $\mathcal{N}$ ; you can specify the PARETOMAX= option to control the size of this set.

Although it is difficult to verify directly that a point lies on the true Pareto-optimal frontier without using derivatives, convergence can indirectly be measured by monitoring movement of the population with respect to $\mathcal{N}$ , the current set of nondominated points. A number of metrics for measuring convergence in multiobjective evolutionary algorithms have been suggested, such as the generational distance by Van Veldhuizen (1999), the inverted generational distance by Coello Coello and Cruz Cortes (2005), and the averaged Hausdorff distance by Schütze et al. (2012). PROC OPTLSO uses a variation of the averaged Hausdorff distance that is extended for general constraints.

Distance between sets is computed in terms of the distance between a point and a set, which in turn is defined in terms of the distance between two points. The distance measure used by PROC OPTLSO for two points x and y is calculated as

$d(x,y)=|\theta (x) - \theta (y)| + \sum _{i=1}^ k |f_ i(x) - f_ i(y)|$

where $\theta (x)$ denotes the maximum constraint violation at point x. Then the distance between a point x and a set ${\mathcal{A}}$ is defined as

$d(x,{\mathcal{A}}) = \min _{y \in {\mathcal{A}}} d(x,y)$

Let ${\mathcal{F}}_ j$ denote the set of all nondominated points within the current population at the start of generation j. Let ${\mathcal{N}}_ j$ denote the set of all nondominated points at the start of generation j. At the beginning of each generation, ${\mathcal{F}}_ j \subseteq {\mathcal{N}}_ j$ is always satisfied. Then progress made during iteration j+1 is defined as

$\text {Progress}(j+1) = \dfrac {1}{|{\mathcal{F}}_{j}|} \sum _{x\in {\mathcal{F}}_ j}^{} d(x,{\mathcal{N}}_{j+1})$

Because $d(x,{\mathcal{N}}_{j+1})=0$ whenever $x \in {\mathcal{F}}_ j \cap {\mathcal{F}}_{j+1}$ , the preceding sum is over the set of points in the population that move from a status of nondominated to dominated. In this case, the progress made is measured as the distance to the nearest dominating point.