Multi-objective optimization

Driver:

ActiveLearning

Download script:

multi_objective_optimization.py

Many optimization task do not consist of only a single objective \(f(\mathbf{x})\) to be minimized in some domain \(\mathbf{x}\in \mathcal{X}\subset \mathbb{R}^d\), but rather in a set of objectives \(\mathbf{f}(\mathbf{x}) = [f_1(\mathbf{x}), f_2(\mathbf{x}),\dots,f_k(\mathbf{x})]^{\rm T}\) to be minimized together.

A solution \(\mathbf{a} = \mathbf{f}(\mathbf{x}_1)\) is said to dominate another solution \(\mathbf{b} = \mathbf{f}(\mathbf{x}_2)\) if \(a_i \le b_i\) for all \(i \in [1, \dots, k]\) and there exists at least on entry \(j \in [1, \dots, k]\) such that \(a_j < b_j\).

A solution is called Pareto optimal if it is not dominated by any other solution. The set of Pareto optimal solutions is called the Pareto front. The aim of a multi-objective optimization is to find the Pareto front for the set of objectives \(\mathbf{f}(\mathbf{x})\).

We consider an analytic multi-objective optimization problem with \(k=2\) objectives:

\[ \begin{align}\begin{aligned}\text{Minimize } f_1(x_1,x_2) &=& x_1\\\text{Minimize } f_2(x_1,x_2) &=& \frac{g(x_2)}{x_1}\end{aligned}\end{align} \]

It can be shown, that the problem has Pareto-optimal solutions \((x_1, x_2^*)\), where \(x_2^*\) is the globally minimum solution of \(g(x_2)\) and \(x_1\) can take any value [DEB1999].

As an example, we consider the multi-modal function

\[g(x_2) = 20 + (x_2^2 - 10\cos(2\pi x_2))\]

with local minima approximately located at integer values of \(x_2\) and the global minimum at \(g(x_2^* = 0)=10\). That is, the Pareto front is defined as \(f_2 = \frac{10}{f_1}\).

[DEB1999]

Deb, K., “Multi-objective genetic algorithms: Problem difficulties and construction of test problems”. Evolutionary computation, 7(3), pp.205-230 (1999)

import sys,os
import numpy as np
import time
import numpy as np
import matplotlib.pyplot as plt


from jcmoptimizer import Client, Study, Obseravtion
client = Client()


# Definition of the search domain
design_space = [
    {'name': 'x1', 'type': 'continuous', 'domain': (1,4)}, 
    {'name': 'x2', 'type': 'continuous', 'domain': (-1.5,1.5)},    
]

# Creation of the study object with study_id 'multi_objective_optimization'
study = client.create_study(
    design_space=design_space,
    driver="ActiveLearning",
    study_name="Multi-objective optimization",
    study_id="multi_objective_optimization"
)
#Lower and upper reference point for hypervolume definition (see figure)
lower_ref=[0, 0]
upper_ref=[5, 50]

study.configure(
    max_iter = 50,
    surrogates = [
        #A multi-output Gaussian process that learns the dependence of
        #the vectorial model on the design parameters.
        dict(type="GP", name="model_vector", output_dim=2,
             correlate_outputs=False)
    ],
    variables = [
        #Selectors for the values of f1 and f2
        dict(type="SingleSelector", name="f1",
             input="model_vector", select_by_name="model_vector0"),
        dict(type="SingleSelector", name="f2",
             input="model_vector", select_by_name="model_vector1")
    ],
    objectives = [
        #Multi-minimization objective for f1, f2
        dict(type="MultiMinimizer", variables=["f1", "f2"], name="objective",
             lower_reference=lower_ref, upper_reference=upper_ref)
    ]
)

# Evaluation of the black-box function for specified design parameters
def evaluate(study: Study, x1: float, x2: float) -> Observation:

    time.sleep(2) # make objective expensive
    observation = study.new_observation()
    #determine list of the two objective values
    g = 20 + (x2**2 - 10*np.cos(2*np.pi*x2))
    observation.add([x1, g/x1])
    
    return observation

# Run the minimization
study.set_evaluator(evaluate)
study.run()

plt.figure(figsize=(10,5))

#Plot all observations of (f1, f2)
f1 = study.driver.get_observed_values("variable", "f1")
f2 = study.driver.get_observed_values("variable", "f2")
plt.plot(f1["means"], f2["means"], "o", label="Donimated observations")

#Plot the estimate of the Paretro front, i.e. nondominated observations
pf = study.driver.get_state("pareto_front")
nondom_f1, nondom_f2 = np.array(pf["f1"]), np.array(pf["f2"])
plt.plot(nondom_f1, nondom_f2, "o", label="Pareto front estimate")

#Plot analytic Pareto front
X = np.linspace(1, 4, 100)
plt.plot(X, 10/X, "k--", label="Analytic Pareto front")

#Plot nondominated hypervolume
plt.plot(*lower_ref, "rx", label="Lower reference")
plt.plot(*upper_ref, "bx", label="Upper reference")
nondom_f2_aug = np.hstack((upper_ref[1], nondom_f2))
X = [lower_ref[0]] + np.repeat(nondom_f1,2).tolist() + [upper_ref[0]]
nondom_lower = [lower_ref[1]]*len(X)
nondom_upper = np.repeat(nondom_f2_aug, 2).tolist()
plt.fill_between(X, nondom_lower, nondom_upper, alpha=0.2, color="blue",
                 label="Nondominated hypervolume")

plt.xlabel("f1")
plt.ylabel("f2")
plt.legend(loc="upper center")
plt.grid()
plt.savefig("multi_objective_minimization.svg", transparent=True)

client.shutdown_server()

Result of the multi-objective minimization in the \((f_1, f_2)\)-plane.

The blue dots show all observations, whereas the orange dots show nondominated solution, i.e. an estimate of the Pareto front. The dashed line shows the true analytic Pareto front within the domain of \((x_1, x_2)\).

The progress of the study is shown in terms of the nondominated hypervolume (blue shaded area) that is defined by the nondominating observations as well as a lower and upper reference point (red and blue cross).