Overview#
This notebook demonstrates almost everything you can do with Paref, from applying an existing MOO algorithm to a bbf to constructing your own MOO algorithm tailored to the problem, using a practical example.
Setup#
Let us imagine the following situation: We have a blackbox function (bbf) that we want to optimize multicriterially or, synonymously, multiobjectively (multi objective optimization, MOO). In other words, we are searching for the bbf Pareto front. The bbf can represent a machine for which we can set certain parameters (vector \(x \in D\), where D represents the domain of the problem, which we also call design space) and which then reacts measurably via certain target variables (vector \(y \in T\), where T represents the co-domain of the problem, which we also call target space). Or the bbf represents a simulation model, where we can also define specifications x for its design and obtain responses y through simulation.
In our example here, we choose as bbf the mathematical test function Zitzler-Deb-Thiele N.1 (ZDT-2, reference: Deb, Kalyan; Thiele, L.; Laumanns, Marco; Zitzler, Eckart (2002). “Scalable multi-objective optimization test problems”. Proceedings of the 2002 IEEE Congress on Evolutionary Computation. Vol. 1. pp. 825–830. doi:10.1109/CEC.2002.1007032). In the further course of our example, however, we assume that we do not know this function (which makes it a bbf). We can only “test” the bbf qua function calls in places we choose.
This approach offers the following advantage: ZDT-2 is not only defined analytically, but we also know (analytically) its Pareto front. Thus, we can immediately compare our results with the expected results and see how well our new approach works.
What Paref offers#
In many cases, the general MOO problem is formulated as “find the Pareto front” and not specified more clearly. Many MOO algorithms are accordingly designed to do just that: They identify Pareto-optimal points (i.e. points on the Paretofront), but they do not guarantee the user any further properties (e.g. to identify co-domain corner points of the Paretofront). The package paref now allows exactly that: besides the general property “identified points are Pareto-optimal”, paref users can specify
further properties of the Paretofront to be identified and construct MOO algorithms based on those defined properties. On a top level, this works as follows: - properties of Pareto points are reflected by Pareto reflections or, more generally, by sequences of such - Paref provides a library of such (partly customizable) including a description of what properties are targeted - applying an existing MOO to a blackbox
function and a sequence by using the apply_to_sequence method results in an algorithmic search for Pareto points satsfying those properties (with mathematical guarantees)
This example#
In this example we exploit all the functionality Paref provides, from implementing a blackbox function and apply an existing Paref MOO algorithm reflecting some properties all the way to construct our own problem specific MOO algorithm. Concrete we will do the following:
Implement a blackbox function (ZDT-2)
Apply one of Parefs’ MOO algorithms to the blackbox function
Apply an MOO algorithm to some Pareto reflection in order to target a certain property of Pareto points
Implement a Pareto reflection targeting some property
Implement a sequence of Pareto reflections targeting some properties
Apply an MOO algorithm to a sequence
Construct a new MOO algorithm from a sequence
Define and implement a blackbox function#
We first need to define how many dimensions our domain (Design Space) and co-domain (Target Space) have. In our example (ZDT-2) we want to map 5 Design Space dimensions to 2 Target Space dimensions. Second, we must define how it can retrieve function values at selected points, i.e. we must declare calls to our bbf. Those four information, i.e. - assignment of vector of design variables to vector of target values (here given by ZDT-2) implemented in the __call__ method - dimension of design
space (here 5) - dimension of target space (here 2) - design space definition (here \([0,1]^{10}\))
must be implemented in Parefs` BlackboxFunction interface.
CAUTION: by default, the evaluations of the blackbox function must be
stored in the ``self._evaluations``variable and must be of the form [x,y]
where x is a one dimensional numpy array representing the design vector
and y a one dimensional numpy array representing
the corresponding target vector!
The corresponding code looks like this:
[1]:
import numpy as np
from paref.black_box_functions.design_space.bounds import Bounds
from paref.interfaces.moo_algorithms.blackbox_function import BlackboxFunction
class ZDT2(BlackboxFunction):
def __call__(self, x: np.ndarray) -> np.ndarray:
n = len(x)
f1 = x[0]
g = 1 + 9 / (n - 1) * np.sum(x[1:])
h = 1 - (f1 / g) ** 2
f2 = g * h
y = np.array([f1, f2])
self._evaluations.append([x, y]) # store evaluation
return y
@property
def dimension_design_space(self) -> int:
return 5
@property
def dimension_target_space(self) -> int:
return 2
@property
def design_space(self) -> Bounds:
return Bounds(upper_bounds=np.ones(self.dimension_design_space),
lower_bounds=np.zeros(self.dimension_design_space))
We then initialize an instance of this bbf.
[2]:
bbf = ZDT2()
The Pareto front of ZDT-2 looks as follows:
[3]:
# This code is exclusively to visualize our results
import plotly.graph_objects as go
pareto_points_of_bbf = [
i * np.eye(1, bbf.dimension_design_space, 0)[0]
for i in np.arange(0, 1, 0.01)
]
pareto_front_of_bbf = np.array([bbf(point) for point in pareto_points_of_bbf])
bbf.clear_evaluations()
data = [
go.Scatter(x=pareto_front_of_bbf.T[0],
y=pareto_front_of_bbf.T[1],
name='Real Pareto front',
line=dict(width=4)),
]
fig = go.Figure(data=data)
fig.update_layout(title="Pareto front of ZDT-2",
width=600,
height=600,
plot_bgcolor='rgba(0,0,0,0)',
legend=dict(
x=0.2,
y=0.9,
))
fig.show()
Note that in general we are not able to calculate the Pareto front. In this particular case, we can and use this knowledge in order to validate our results.
Apply a MOO algorithm to blackbox function#
Applying an MOO algorithm in Paref is simply given by calling the algorithm to - a blackbox function (implemented in the BlackboxFunction interface) and - a stopping critera indicating when the algorithm should terminate.
There are essentially two types of MOO algorithms implemented in Paref: - generic MOO algorithms (mainly minimizers) which are not tailored to some user defined properties but used when constructing a tailored MOO algorithm from a (sequence of) Pareto reflection(s) - tailored MOO algorithms which target certain properties of Pareto points
Let’s make it concrete for our example: From our bbf ZDT-2 we want to identify Pareto-optimal solutions that represent the co-domain corners of the Pareto front. This property gives us an answer to the question “in which target area are there Pareto-optimal trade-offs of our bbf at all?”. This is a quite typical questions that arise in the context of a bbf MOO. Let’s get down to work and see how all these considerations transfer into code….
First, with initialize some stopping criteria. In our case, we choose the MaxIterationsReached which tells the algorithm to stop after a defined number max_iterations of iterations is reached.
[ ]:
from paref.moo_algorithms.stopping_criteria.max_iterations_reached import MaxIterationsReached
stopping_criteria = MaxIterationsReached(max_iterations=12)
Next, we initialize the MOO algorithm targeting our desired properties of Pareto points: the FindEdgePoints algorithm.
[ ]:
from paref.moo_algorithms.multi_dimensional.find_edge_points import FindEdgePoints
moo_find_edge_points = FindEdgePoints(min_required_evaluations=20)
At last, we simply apply the algorithm to the blackbox function and the stopping criteria.
[ ]:
moo_find_edge_points(blackbox_function=bbf,
stopping_criteria=stopping_criteria)
[ ]:
# This code is exclusively to visualize our results
#y = pareto_front_of_bbf.T[1]
data = [
go.Scatter(x=pareto_front_of_bbf.T[0],
y=pareto_front_of_bbf.T[1],
name='Real Pareto front',
line=dict(width=4)),
go.Scatter(x=bbf.pareto_front.T[0],
y=bbf.pareto_front.T[1],
name='Determined Pareto points',
mode="markers",
marker=dict(size=10)),
]
fig = go.Figure(data=data)
fig.update_layout(title="Pareto front of ZDT-2",
width=600,
height=600,
plot_bgcolor='rgba(0,0,0,0)',
legend=dict(
x=0.2,
y=0.9,
))
fig.show()
#bbf.clear_evaluations()
NOTE: while the lower right corner is determined quite well, the MOO algorithm struggles
to determine the upper left corner.
This is because the underlying optimization algorithm does not approximate the bbf
close enough. This is quite common in MOO problems.
Identify Pareto points with defined properties by using Pareto reflections#
If an additional property of Pareto points (reflected by some Pareto reflection) is targeted, we may simply call the apply_to_sequence method of any MOO algorithm to the blackbox function, stopping criteria and the corresponding Pareto reflection in order to include this property.
Let’s make it concrete for our example: From our bbf ZDT-2 we want to determine the edge Pareto points of the Pareto front but restricted to a certain area. Here, we choose the area as \((-\infty,0.5]\times (-\infty,10]\), i.e. we demand the maximal \(y_1\) resp. \(y_2\) value of Pareto points to be \(0.5\) resp. \(10\).
This is a quite typical constrained that arises in the context of a bbf MOO.
Paref provides an implementation of a Pareto reflection corresponding to that property: the RestrictByPoint Pareto reflection. Lets initialize that reflection:
[ ]:
from paref.pareto_reflections.restrict_by_point import RestrictByPoint
restrict_by_point = RestrictByPoint(restricting_point=np.array([0.5, 5]),
nadir=10 * np.ones(2))
Now, we simply apply the FindEdgePoint algorithm to that Pareto reflection:
[ ]:
moo_find_edge_points.apply_to_sequence(
blackbox_function=bbf,
sequence_pareto_reflections=restrict_by_point,
stopping_criteria=stopping_criteria)
[ ]:
# This code is exclusively to visualize our results
data = [
go.Scatter(x=pareto_front_of_bbf.T[0],
y=pareto_front_of_bbf.T[1],
name='Real Pareto front',
line=dict(width=4)),
go.Scatter(x=bbf.pareto_front.T[0],
y=bbf.pareto_front.T[1],
name='Determined Pareto points',
mode="markers",
marker=dict(size=10)),
]
fig = go.Figure(data=data)
fig.update_layout(title="Pareto front of ZDT-2",
width=600,
height=600,
plot_bgcolor='rgba(0,0,0,0)',
legend=dict(
x=0.2,
y=0.9,
))
fig.show()
bbf.clear_evaluations()
Customize Pareto reflections to user defined properties#
If there does not exist an explicit Pareto reflection targeting our property, we may also use some of the (customazible) Pareto reflections provided by Paref and customize it to our targeted property.
For example, we may be interested in the ‘’knee point’’ between two points, i.e. the point which is closest to the lower left corner characterized by those two points (=minimum of components). This Pareto reflection can be specified be using the MinimizeWeightedNormToUtopia Pareto reflection. The implementation looks as follows:
[ ]:
from paref.pareto_reflections.minimize_weighted_norm_to_utopia import MinimizeWeightedNormToUtopia
class FindKneePoint2D(MinimizeWeightedNormToUtopia):
def __init__(self, point_1: np.ndarray, point_2: np.ndarray):
min_components = np.min(np.array([point_1, point_2]), axis=1)
self.utopia_point = min_components
self.potency = 2
self.scalar = np.ones(2)
@property
def dimension_domain(self) -> int:
return 2
find_knee_point = FindKneePoint2D(np.array([1, 0]), np.array([0, 1]))
In order to apply some MOO to that that reflection (in order to target the ‘’knee point’’ property), we choose some generic MOO algorithm (i.e. some MOO which is not tailored to some properties) which can handle the FindKneePoint2D reflection.
CAUTION: the codomain dimension of the Pareto reflection (``dimension_codomain`` property) must
be a supported target space dimensions of the MOO (``supported_target_space_dimensions``)
The codomain dimension of the above Pareto reflection is 1:
[ ]:
find_knee_point.dimension_codomain
In this example, we choose the DifferentialEvolutionMinimizer. This MOO exploits the fact that the underlying bbf is very cheap to sample (for a generic MOO algorithm which is tailored to expensive bbf see for example the GPRMinimizer) and yields typically much better results but needs much more evaluations of the blackbox function.
[ ]:
from paref.moo_algorithms.minimizer.differential_evolution_minimizer import DifferentialEvolutionMinimizer
generic_moo = DifferentialEvolutionMinimizer()
Notice that the codomain dimension of the Pareto reflection is supported by the MOO:
[ ]:
print(
f"Codomain dimension is supported: {find_knee_point.dimension_codomain in generic_moo.supported_codomain_dimensions}"
)
Again, we simply apply the MOO to the Pareto reflection by calling its apply_to_sequence method:
[ ]:
generic_moo.apply_to_sequence(blackbox_function=bbf,
stopping_criteria=MaxIterationsReached(2),
sequence_pareto_reflections=find_knee_point)
[ ]:
# This code is exclusively to visualize our results
data = [
go.Scatter(x=pareto_front_of_bbf.T[0],
y=pareto_front_of_bbf.T[1],
name='Real Pareto front',
line=dict(width=4)),
go.Scatter(x=bbf.pareto_front.T[0],
y=bbf.pareto_front.T[1],
name='Determined Pareto points',
mode="markers",
marker=dict(size=10)),
]
fig = go.Figure(data=data)
fig.update_layout(title="Pareto front of ZDT-2",
width=600,
height=600,
plot_bgcolor='rgba(0,0,0,0)',
legend=dict(
x=0.2,
y=0.9,
))
fig.show()
bbf.clear_evaluations()
Implement a sequence of Pareto reflections#
Not lets assume you want to determine the knee point of the whole Pareto front, i.e. the knee point between the edge points. This requires to first determine the edge points and then the knee point between them. This can be implemented in a sequence of Pareto reflections:
A sequence of Pareto reflections a Pythonic way of representing multiple Pareto reflections. Accordingly, with sequences of Pareto reflections we can iteratively target several properties of Pareto points. In order to implement such a sequence you need to implement the SequenceParetoReflectionsinterface or implement one of the generic sequences.
In detail, this requires to implement the next(blackbox_function: BlackboxFunction)->Optional[ParetoReflection] method. This method decides which Pareto reflection is used in the next iteration and returns None if the sequence is finished.
In our example, lets first target the Pareto point in the upper left corner than the lower right corner and then the knee point characterized by that corners and move to the next Pareto reflection if the search converged. The corresponding code looks as follows:
[ ]:
from paref.interfaces.sequences_pareto_reflections.sequence_pareto_reflections import SequenceParetoReflections
from paref.pareto_reflections.find_edge_points import FindEdgePoints
from paref.interfaces.pareto_reflections.pareto_reflection import ParetoReflection
from typing import Optional
class FindKneePointSequence2D(SequenceParetoReflections):
def __init__(self):
self.iter = 0 # count at which Pareto reflection we are
def next(
self,
blackbox_function: BlackboxFunction) -> Optional[ParetoReflection]:
# move to the next Pareto reflection if search converged
if len(blackbox_function.y) >= 2:
if np.linalg.norm(blackbox_function.y[-1] -
blackbox_function.y[-2]) < 1e-1:
self.iter += 1 # move to next Pareto reflection if search converged
if self.iter == 0:
return FindEdgePoints(
dimension_domain=2,
dimension=0,
) # search for upper left corner
if self.iter == 1:
return FindEdgePoints(
dimension_domain=2,
dimension=1,
) # search for lower right corner
if self.iter == 2:
# determine found corner points of Pareto front
edge_points = np.argmin(blackbox_function.y, axis=1)
return FindKneePoint2D(point_1=blackbox_function.y[edge_points[0]],
point_2=blackbox_function.y[
edge_points[1]]) # search knee point
if self.iter == 3:
return None # stop if knee point approximately found
find_knee_point_sequence = FindKneePointSequence2D()
Apply a Moo algorithm to a sequence of Pareto reflections#
Find `here <>`__ a list of all (generic) sequences Paref provides.
Applying an MOO to some sequence works in the same way as applying an MOO to a Pareto reflection (see above), i.e. by calling the apply_to_sequence method.
Here is the code where we apply the generic MOO DifferentialEvolutionMinimizer to our FindKneePointsSequence2D sequence:
[ ]:
stopping_criteria = MaxIterationsReached(10)
generic_moo.apply_to_sequence(
blackbox_function=bbf,
stopping_criteria=stopping_criteria,
sequence_pareto_reflections=find_knee_point_sequence)
[ ]:
# This code is exclusively to visualize our results
data = [
go.Scatter(x=pareto_front_of_bbf.T[0],
y=pareto_front_of_bbf.T[1],
name='Real Pareto front',
line=dict(width=4)),
go.Scatter(x=bbf.pareto_front.T[0],
y=bbf.pareto_front.T[1],
name='Determined Pareto points',
mode="markers",
marker=dict(size=10)),
]
fig = go.Figure(data=data)
fig.update_layout(title="Pareto front of ZDT-2",
width=600,
height=600,
plot_bgcolor='rgba(0,0,0,0)',
legend=dict(
x=0.2,
y=0.9,
))
fig.show()
bbf.clear_evaluations()
Construct a new Paref MOO algorithm#
In the last step, we turn our sequence into a problem tailored MOO algorithm (targeting the knee point property): This is simply done by implementing the sequence_of_pareto_reflections(self) property of some (generic) MOO algorithm.
NOTE: the sequence is only initialized *once* if the algorithm is called"
In our example, we choose the generic MOO DifferentialEvolutionMinimizer. The code looks as follows:
[ ]:
from typing import List
class FindKneePoint2DMOO(DifferentialEvolutionMinimizer):
@property
def sequence_of_pareto_reflections(self) -> SequenceParetoReflections:
return FindKneePointSequence2D()
@property
def supported_codomain_dimensions(self) -> List[int]:
# the sequence if only defined if the blackbox function is has two dimensional target space
return [2]
Lets apply this algorithm once again to our ZDT-1 bbf:
[ ]:
find_knee_point_moo = FindKneePoint2DMOO()
find_knee_point_moo(blackbox_function=bbf,
stopping_criteria=MaxIterationsReached(10))
[ ]:
# This code is exclusively to visualize our results
data = [
go.Scatter(x=pareto_front_of_bbf.T[0],
y=pareto_front_of_bbf.T[1],
name='Real Pareto front',
line=dict(width=4)),
go.Scatter(x=bbf.pareto_front.T[0],
y=bbf.pareto_front.T[1],
name='Determined Pareto points',
mode="markers",
marker=dict(size=10)),
]
fig = go.Figure(data=data)
fig.update_layout(title="Pareto front of ZDT-2",
width=600,
height=600,
plot_bgcolor='rgba(0,0,0,0)',
legend=dict(
x=0.2,
y=0.9,
))
fig.show()
bbf.clear_evaluations()
And that’s it! You constructed your own problem tailored MOO algorithm.