Practical Evolutionary Algorithms

A practical book on Evolutionary Algorithms that teaches you the concepts and how they’re implemented in practice.

Get the book

Populations in Objective and Decision Space

Dr. Shahin Rostami

2019-07-29

5 min read

Source

Contents Chat Share Follow Download Source

Preamble
Introduction
Populations in Objective and Decision Space
Conclusion

Get access to this section and more

Below is a featured selection from this section. You can access this notebook and more by getting the e-book on Practical Evolutionary Algorithms.

Preamble¶

In [1]:

# used to create block diagrams
%reload_ext xdiag_magic
%xdiag_output_format svg
    
import numpy as np                   # for multi-dimensional containers
import pandas as pd                  # for DataFrames
import plotly.graph_objects as go    # for data visualisation

Introduction¶

In single-objective problems, the objective is to find a single candidate solution which represents the global optimum in the entire search space. Multi-objective problems often involve conflicts between multiple objectives, and as a result, it is unlikely that there exists a single optimal solution. Therefore, the solution to a multi-objective problem cannot be a single candidate solution, but instead a set of candidate solutions which represent the optimum trade-off surface in the objective space. This set is referred to as an approximation set, as it is an approximation of the theoretical optima.

Through the optimisation process in an Evolutionary Multi-Objective Optimisation Algorithm, a population of solutions is iteratively subjected to various operators until termination, at which point this final population (or a sub-set) is determined to be the approximation set.

In [2]:

%%blockdiag
{
    orientation = portrait
    Initialisation -> Evaluation -> "Terminate?" -> Selection -> Variation -> Evaluation
}

We can introduce and describe these concepts through a demonstration, by generating a population of decision variables and using the ZDT1 test function (described in earlier sections) as the objective function.

In [3]:

def ZDT1(x):
    f1 = x[0] # objective 1
    g = 1 + 9 * np.sum(x[1:D] / (D-1))
    h = 1 - np.sqrt(f1/g)
    f2 = g * h # objective 2
    
    return [f1, f2]

We will describe these concepts mathematically and then implement them using Python.

Populations in Objective and Decision Space¶

We will begin by defining a population of size $\mathrm{N}=50$, number of decision variables $\mathrm{D}=30$ where each variable falls between 0 and 1 ($x_d \in [0,1]$), and number of objective values $\mathrm{M}=2$.

In [4]:

N = 50
D = 30
D_lower = np.zeros((1, D))
D_upper = np.ones((1, D))
M = 2

Let's define a population $\mathrm{X}$ of $\mathrm{N}$ candidate solutions.

$$ \mathbf{X} = \langle \mathrm{X}_1,\mathrm{X}_2,\ldots,\mathrm{X}_{\mathrm{N}}\rangle $$

where $\mathrm{N}$ refers to the number of solutions in the population, $\mathrm{X}_{n}$ refers to the $n$-th solution in the population, and $x_{dn}$ refers to the $d$-th decision variable of the $n$-th solution in the population.

$$ \mathrm{X}_{n} = \langle x_{1n},x_{2n},\ldots,x_{\mathrm{D}n} \rangle $$

Let's initialise this population with random decision variables.

In [5]:

X = pd.DataFrame(np.random.uniform(low=D_lower, high=D_upper, size=(N,D)))
X.head(5) # Show only the first 5 solutions

Out[5]:

	0	1	2	3	4	5	6	7	8	9	...	20	21	22	23	24	25	26	27	28	29
0	0.319794	0.210277	0.661202	0.576512	0.919096	0.619627	0.144312	0.492168	0.071444	0.097165	...	0.405698	0.051052	0.711290	0.171101	0.348249	0.513796	0.040979	0.471423	0.234481	0.829264
1	0.928395	0.294284	0.876422	0.875918	0.621227	0.542169	0.516537	0.037377	0.677626	0.574752	...	0.099269	0.805714	0.987050	0.736512	0.303567	0.857652	0.386796	0.569946	0.754361	0.422750
2	0.591736	0.049616	0.280287	0.274745	0.976667	0.549049	0.035575	0.975662	0.990341	0.279058	...	0.264550	0.947580	0.238742	0.402632	0.670565	0.836680	0.198253	0.781914	0.529176	0.090266
3	0.436835	0.396100	0.565627	0.771283	0.953862	0.154900	0.705738	0.213084	0.065187	0.527985	...	0.895271	0.008670	0.582919	0.610688	0.255088	0.826537	0.721399	0.050266	0.617336	0.622337
4	0.843525	0.384967	0.305494	0.784293	0.219973	0.208779	0.278644	0.232406	0.170957	0.848209	...	0.362835	0.778941	0.194864	0.492432	0.560430	0.117204	0.326108	0.768826	0.817604	0.088538

5 rows × 30 columns

Similarly, we will define the corresponding objective values $\mathrm{Y}$ of the population $\mathrm{X}$.

$$ \mathbf{Y} = \langle \mathrm{Y}_1,\mathrm{Y}_2,\ldots,\mathrm{Y}_{\mathrm{N}}\rangle $$

where $\mathrm{N}$ refers to the number of objective value sets, $\mathrm{Y}_{n}$ refers to the $n$-th set of objective values in the population, and $y_{mn}$ refers to the $m$-th objective value of the $n$-th set of objective values in the population.

$$ \mathrm{Y}_{n} = \langle y_{1n},y_{2n},\ldots,y_{\mathrm{M}n} \rangle $$

To generate $\mathrm{Y}$, we will evaluate each solution $\mathrm{X}_{\mathrm{N}}$ using the ZDT1() test function defined above.

In [6]:

Y = np.empty((0, 2))

for n in range(N):
    y = ZDT1(X.iloc[n])
    Y = np.vstack([Y, y])
    
# convert to DataFrame
Y = pd.DataFrame(Y, columns=['f1','f2'])
Y.head(5) # Shows only first 5 sets of objective values

Out[6]:

	f1	f2
0	0.319794	4.280788
1	0.928395	3.408501
2	0.591736	3.852273
3	0.436835	3.949591
4	0.843525	2.962633

Finally, we will visualise each of our 50 solutions in objective space.

In [7]:

fig = go.Figure(layout=dict(xaxis=dict(title='f1'),yaxis=dict(title='f2')))

# This is not how we would normally plot this data.
# Here, it is done this way so that the colours match those in the visualisation below.
for index, row in Y.iterrows():
    fig.add_scatter(x=[row.f1], y=[row.f2],
                    name=f'solution {index+1}', mode='markers')

fig.show()

For completeness, we may also wish to visualise our 50 solutions in the decision space, although it is not very useful at this point.

In [8]:

fig = go.Figure(
    layout=dict(
        xaxis=dict(title='decision variables', range=[1, D]),
        yaxis=dict(title='value')))

for index, row in X.iterrows():
    fig.add_scatter(x=X.columns.values+1, y=row, name=f'solution {index+1}')

fig.show()

Conclusion¶

In this section, we have covered how to generate and visualise a population in the objective space and decision space. We did this using the ZDT1 synthetic test function, according to the specified population size and dimensionality of the objective space and decision space. You will find many different styles of mathematical notation employed to describe populations in the Evolutionary Algorithm literature, however, you should be able to understand them if you learn the ones described in this section.

Exercise

Using the ZDT test suite paper listed in the references, duplicate this notebook but with the focus on ZDT2 instead of ZDT1.

Get access to this section and more

You can access this notebook and more by getting the e-book on Practical Evolutionary Algorithms.

Practical Evolutionary Algorithms

A practical book on Evolutionary Algorithms that teaches you the concepts and how they’re implemented in practice.

Get the book