Multiobjective Policy Search and Optimization

Lecture

Mon., Feb. 26

Credit

I borrow heavily from

Lecture 9 of S.D. Sudhoff’s course “Engineering Analysis and Design Using Genetic Algorithms” taught at Purdue

Motivation

Today

  1. Motivation

  2. Multiobjective optimization

  3. Implementation

  4. Wrapup

Enriching our notation

Single-objective policy search

Using this notation, we want to \(\min / \max g(a)\), subject to constraints.

In other words, we want a single solution that scores the best according to \(g(a)\).

Objectives can be hard to combine

Sometimes, combining objectives into a single function is difficult.

  1. Operating a reservoir to maximize power generation, minimize flood risk, and supply water to a city.
  2. Designing a levee to balance cost, financial flood risk, ecological impact, and human safety.
  3. Your examples?

Addressing multiple, sometimes-competing, needs is often called “multi-criteria decision analysis”

Multiobjective optimization

Today

  1. Motivation

  2. Multiobjective optimization

  3. Implementation

  4. Wrapup

Goals

Goal: find a set of solutions that are not dominated by any other solution

We call this the Pareto front or Pareto set.

Mathematical formulation

\[ \begin{align} & \min / \max f_m(x), & \quad m = 1, 2, \ldots, M \\ \text{subject to} \quad &g_j(x) \leq 0, &\quad j = 1, 2, \ldots, J \\ &h_k(x) = 0, &\quad k = 1, 2, \ldots, K \\ &x_i^{(L)} \leq x_i \leq x_i^{(U)}, &\quad i = 1, 2, \ldots, N \end{align} \]

What’s new?

  • \(M\) objective functions
  • Lots of notation for constraints

Dominance

  1. Single-objective: goodness of solution defined by objective function
  2. Multiobjective: goodness of solution defined by dominance
  3. Definition: \(a_1\) dominates \(a_2\) if:
    1. \(a_1\) is no worse than \(a_2\) in all objectives
    2. \(a_1\) is strictly better than \(a_2\) in at least one objective

Dominance example

Code 
let
    points = [(2, 2), (1, 4), (4, 1), (3, 3), (5, 2)]
    p = plot(;
        xlims=(0, 5.5),
        ylims=(0, 5.5),
        xlabel=L"$f_1$ (Maximize)",
        ylabel=L"$f_2$ (Minimize)",
        legend=false,
        xticks=[],
        yticks=[],
        margin=10Plots.mm,
        aspect_ratio=:equal,
        size=(500, 500),
    )
    for (idx, point) in enumerate(points)
        plot!(
            [0, point[1]],
            [point[2], point[2]];
            color=:black,
            alpha=0.5,
            label=false,
            style=:dash,
        )
        plot!(
            [point[1], point[1]],
            [0, point[2]];
            color=:black,
            alpha=0.5,
            label=false,
            style=:dash,
        )
        scatter!([point[1]], [point[2]]; label=false, markersize=15, color=:orange)
        annotate!(point[1] - 0.25, point[2] + 0.25, text("$idx", 14, :left))
    end
    p
end
  • 1 vs 2: 1 dominates
  • 1 vs 5: 5 dominates
  • 1 vs 4: neither dominates

Smith et al. (2022)

Goals of multiobjective optimization

  1. Find solutions as close to Pareto front as possible
  2. Find solutions as diverse as possible (since infinite points lie along the Pareto front but we can only sample a finite number)

Implementation

Today

  1. Motivation

  2. Multiobjective optimization

  3. Implementation

  4. Wrapup

Weighted sum

We can scalarize the multiobjective problem into a single-objective problem by using a weighted sum:

\[ \min F(x) =\sum_{m=1}^M w_m f_m(x) \] subject to the same constraints as before.

  • Strength: simple
  • Weakness: have to choose weights
  • Opportunity: can vary weights to explore Pareto front
  • Threat: may miss parts of the Pareto front

Weighted sum: convex and nonconvex

Figure 1: From Sudhoff slides.

Genetic algorithms

  1. GAs operate on a set (“population” or “generation”) of solutions
  2. Inspired by evolution: the best solutions are more likely to survive and reproduce
  3. At each time step, compute a fitness score for each solution based on objectives and diversity
  4. Use this score to select solutions for reproduction (crossover)
  5. Add noise (mutation) to the next “generation”
  6. Many algorithms! We won’t try to keep track of them all.

A population of solutions

What do we get at the end?

  1. A set of solutions that are not dominated by any other solution
  2. Each represents
    1. a different tradeoff between objectives
    2. a different part of the Pareto front

One interpretation of multi-objective optimization is that it maps out the trade-offs between objectives.

Figure 5 of Kasprzyk et al. (2013)

Checking convergence

Genetic / algorithms are not exact methods. They rely on heuristics to decide a solution is “good enough” even if it’s not a global optimum. However, we can and should test our solutions for convergence and quality.

  1. Repeat the optimization with different initial conditions (“random seeds”). Do results change?
  2. Use diagnostics like hypervolume to measure how much of the Pareto front we’ve found.
  3. Compare to other methods (e.g., weighted sum) to see if we’re missing parts of the Pareto front.
  4. Compare solutions to human-generated benchmarks.

Wrapup

Today

  1. Motivation

  2. Multiobjective optimization

  3. Implementation

  4. Wrapup

Key ideas

  1. Policy search
  2. Multiobjective optimization
  3. Genetic algorithms

How many objectives do we need?

There are drawbacks to adding more objectives:

  • Computational cost (exponentially more solutions needed)
  • Conceptual complexity
  • Difficulty communicating results

so we want as few as possible. Thus, combining objectives into a single function is often a good idea, when appropriate.

Logistics

  • Wednesday: read Zarekarizi et al. (2020)
  • Friday: lab on multiobjective optimization

References

Kasprzyk, J. R., Nataraj, S., Reed, P. M., & Lempert, R. J. (2013). Many objective robust decision making for complex environmental systems undergoing change. Environmental Modelling & Software, 42, 55–71. https://doi.org/10.1016/j.envsoft.2012.12.007
Smith, S., Southerby, M., Setiniyaz, S., Apsimon, R., & Burt, G. (2022). Multiobjective optimization and Pareto front visualization techniques applied to normal conducting rf accelerating structures. Physical Review Accelerators and Beams, 25(6), 062002. https://doi.org/10.1103/PhysRevAccelBeams.25.062002
Zarekarizi, M., Srikrishnan, V., & Keller, K. (2020). Neglecting uncertainties biases house-elevation decisions to manage riverine flood risks. Nature Communications, 11(1, 1), 5361. https://doi.org/10.1038/s41467-020-19188-9