{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Preamble" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [], "source": [ "# used to create block diagrams\n", "%reload_ext xdiag_magic\n", "%xdiag_output_format svg\n", " \n", "import numpy as np # for multi-dimensional containers\n", "import pandas as pd # for DataFrames\n", "import plotly.graph_objects as go # for data visualisation\n", "\n", "# Optional Customisations\n", "import plotly.io as pio # to set shahin plot layout\n", "pio.templates['shahin'] = pio.to_templated(go.Figure().update_layout(\n", " legend=dict(orientation=\"h\",y=1.1, x=.5, xanchor='center'),\n", " margin=dict(t=0,r=0,b=40,l=40))).layout.template\n", "pio.templates.default = 'shahin'\n", "pio.renderers.default = \"notebook_connected\" # remove when running locally" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Introduction\n", "\n", "In mathematics, optimisation is concerned with the selection of optimal solutions to objective functions. An objective function consists of input arguments referred to as problem variables (or genotype) which are computed by one or many mathematical functions to determine the objective value (or phenotype).\n", "\n", "Real-world optimisation problems are divided into one (in the case of single-objective optimisation) or many (in the case of multi-objective optimisation) objective functions in order to be optimised by an optimisation algorithm. The difficulty of convergence can be reduced by the bounding of problem variables as this reduces the size of the search domain.\n", "\n", "In order to determine an Evolutionary Algorithm's robustness when solving problems consisting of multiple objectives, its performance must be assessed on the optimisation of synthetic test functions which are created for the purpose of testing. These problems may also be used to systematically compare two or more Evolutionary Algorithms." ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "%%blockdiag\n", "{\n", " orientation = portrait\n", " \"Problem Variables\" -> \"Test Function\" -> \"Objective Values\"\n", " \"Test Function\" [color = '#ffffcc']\n", "}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Synthetic test functions are typically:\n", "\n", "- **Intentionally difficult**, meaning they are designed to include optimisation difficulties which are present in real-world problems. \n", "- **Scalable**, meaning they can be configured with a different number of problem variables and objectives.\n", "- **Computationally efficient**, meaning they are faster to execute than a real-world problem. This is desirable when benchmarking an Evolutionary Algorithm.\n", "\n", "In contrast, real-world problems which have been encapsulated within an objective function in order to be used by an optimiser are often computationally expensive and have long execution times. This is because synthetic test functions are often mathematical equations which aim to cause difficulty for an optimiser when searching for problem variables that produce optimal objective values, whereas real-world problems often involve computationally expensive simulations in order to arrive at the objective values.\n", "\n", "Put simply, using a real-world problem to evaluate the performance of a newly proposed Evolutionary Algorithm only allows us to determine if an algorithm is good at solving that single problem. What we're interested in is analysing how Evolutionary Algorithms perform when encountering various difficulties that appear in multi-objective problems, and how they compare to each other." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# The ZDT1 test function" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We will be using a synthetic test problem throughout this notebook called ZDT1. It is part of the ZDT test suite, consisting of six different two-objective synthetic test problems. This is quite an old test suite, easy to solve, and very easy to visualise. " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Mathematically, the ZDT11 two-objective test function can be expressed as:\n", "\n", "\n", "\\begin{aligned}\n", "f_1(x_1) &= x_1 \\tag{1} \\\\\n", "f_2(x) &= g \\cdot h \\\\\n", "g(x_2,\\ldots,x_{\\mathrm{D}}) &= 1 + 9 \\cdot \\sum_{d=2}^{\\mathrm{D}} \\frac{x_d}{(D-1)}\\\\\n", "h(f_1,g) &= 1 - \\sqrt{f1/g}\n", "\\end{aligned}\n", "\n", "\n", "where $x$ is a solution to the problem, defined as a vector of $D$ decision variables.\n", "\n", "$$\n", "x= \\langle x_{1},x_{2},\\ldots,x_{\\mathrm{D}} \\rangle \\tag{2}\n", "$$\n", "\n", "and all decision variables fall between $0$ and $1$.\n", "\n", "$$\n", "0 \\le x_d \\le 1, d=1,\\ldots,\\mathrm{D} \\tag{3}\n", "$$\n", "\n", "For this bi-objective test function, $f_1$ is the first objective, and $f_2$ is the second objective. This particular objective function is, by design, scalable up to any number of problem variables but is restricted to two problem objectives.\n", "\n", "Let's start implementing this in Python, beginning with the initialisation of a solution according to Equations 2 and 3. In this case, we will have 30 problem variables $\\mathrm{D}=30$." ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[0.9204285 0.94911763 0.58171075 0.86276293 0.74091143 0.76786472\n", " 0.32042083 0.99105863 0.82828293 0.41936616 0.43302201 0.3502152\n", " 0.52507767 0.02871106 0.21002611 0.14115373 0.54289036 0.0767823\n", " 0.67900898 0.54012128 0.70848884 0.92282082 0.56027323 0.93871461\n", " 0.06385584 0.597213 0.53146707 0.27110393 0.95440343 0.01783687]\n" ] } ], "source": [ "D = 30\n", "x = np.random.rand(D)\n", "print(x)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now that we have a solution to evaluate, let's implement the ZDT1 synthetic test function using Equation 1." ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [], "source": [ "def ZDT1(x):\n", " f1 = x # objective 1\n", " g = 1 + 9 * np.sum(x[1:D] / (D-1))\n", " h = 1 - np.sqrt(f1 / g)\n", " f2 = g * h # objective 2\n", " \n", " return [f1, f2]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Finally, let's invoke our implemented test function using our solution $x$ from earlier." ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[0.9204284983552486, 3.5113646524980835]\n" ] } ], "source": [ "objective_values = ZDT1(x)\n", "print(objective_values)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now we can see the two objective values that measure our solution $x$ according to the ZDT1 synthetic test function, which is a minimisation problem." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Performance in Objective Space\n", "\n", "We will be discussing desirable characteristics in multi-objective solutions, but for now, let's plot some randomly initialised solutions against an optimal set of solutions for ZDT1. This is a synthetic test function, and as such the authors have provided us with a way to calculate the optimal set.\n", "\n", "$$\n", "f_2 = 1 - \\sqrt{f_1} \\tag{4}\n", "$$\n", "\n", "Let's use this to generate 20 ideal sets of objective values." ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
f1f2
00.0000001.000000
10.0526320.770584
20.1052630.675557
30.1578950.602640
40.2105260.541169
50.2631580.487011
60.3157890.438049
70.3684210.393023
80.4210530.351114
90.4736840.311753
100.5263160.274524
110.5789470.239114
120.6315790.205281
130.6842110.172830
140.7368420.141605
150.7894740.111477
160.8421050.082337
170.8947370.054095
180.9473680.026671
191.0000000.000000
\n", "
" ], "text/plain": [ " f1 f2\n", "0 0.000000 1.000000\n", "1 0.052632 0.770584\n", "2 0.105263 0.675557\n", "3 0.157895 0.602640\n", "4 0.210526 0.541169\n", "5 0.263158 0.487011\n", "6 0.315789 0.438049\n", "7 0.368421 0.393023\n", "8 0.421053 0.351114\n", "9 0.473684 0.311753\n", "10 0.526316 0.274524\n", "11 0.578947 0.239114\n", "12 0.631579 0.205281\n", "13 0.684211 0.172830\n", "14 0.736842 0.141605\n", "15 0.789474 0.111477\n", "16 0.842105 0.082337\n", "17 0.894737 0.054095\n", "18 0.947368 0.026671\n", "19 1.000000 0.000000" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "true_front = np.empty((0, 2))\n", "\n", "for f1 in np.linspace(0, 1, num=20):\n", " f2 = 1 - np.sqrt(f1)\n", " true_front = np.vstack([true_front, [f1, f2]]) \n", "\n", "true_front = pd.DataFrame(true_front, columns=['f1', 'f2']) # convert to DataFrame\n", "true_front" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now we can plot them to have an idea of the shape of the true front for ZDT1 in objective space." ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "text/html": [ " \n", " " ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/html": [ "
\n", " \n", " \n", "
\n", " \n", "
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "fig = go.Figure(layout=dict(xaxis=dict(title='f1'),yaxis=dict(title='f2')))\n", "\n", "fig.add_scatter(x=true_front.f1, y=true_front.f2, mode='markers')\n", "\n", "fig.show()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "To wrap things up, let's generate 50 objective values using the ZDT1 objective function created above. We achieve this by passing in 50 randomly initialised sets of problem variables." ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
f1f2
00.9697112.900818
10.7319992.945158
20.1444583.793344
30.3371954.329990
40.7679393.841221
\n", "
" ], "text/plain": [ " f1 f2\n", "0 0.969711 2.900818\n", "1 0.731999 2.945158\n", "2 0.144458 3.793344\n", "3 0.337195 4.329990\n", "4 0.767939 3.841221" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "objective_values = np.empty((0, 2))\n", "\n", "for i in range(50):\n", " x = np.random.rand(D)\n", " y = ZDT1(x)\n", " objective_values = np.vstack([objective_values, y])\n", "\n", "# convert to DataFrame\n", "objective_values = pd.DataFrame(objective_values, columns=['f1', 'f2'])\n", "objective_values.head()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now we will plot the objective values of our randomly initialised solutions on top of a plot of the true front, this will give us some idea of the difference in performance between the two sets.\n", "
" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
\n", " \n", " \n", "
\n", " \n", "
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "fig = go.Figure(layout=dict(xaxis=dict(title='f1'), yaxis=dict(title='f2')))\n", "\n", "fig.add_scatter(x=objective_values.f1, y=objective_values.f2,\n", " name='Solutions', mode='markers')\n", "\n", "fig.add_scatter(x=true_front.f1, y=true_front.f2, name='True Front')\n", "\n", "fig.show()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Conclusion\n", "\n", "In this section, we introduced the concept of synthetic test functions along with ZDT1, a popular and relatively easy example. We expressed the concept mathematically and then made a direct implementation using Python. We then generated a set of 50 solutions, calculated the objective values for each one, and plotted the objective space using a scatter plot.\n", "\n", "There are many suites of synthetic test functions in the literature, some to read about are ZDT, DTLZ, CEC09, and WFG Toolkit." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", "

Exercise

\n", "

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

\n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", "
\n", "
\n", "
1. \n", "

E. Zitzler, K. Deb, and L. Thiele. Comparison of Multiobjective Evolutionary Algorithms: Empirical Results. Evolutionary Computation, 8(2):173-195, 2000

\n", "
2. \n", "
\n", "
" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.7.7" }, "nikola": { "category": "practical-evolutionary-algorithms", "date": "2019-07-25 11:54:36 UTC+01:00", "description": "", "link": "", "slug": "synthetic-objective-functions-and-zdt1", "tags": "", "title": "Synthetic Objective Functions and ZDT1", "type": "text" } }, "nbformat": 4, "nbformat_minor": 4 }