Warning
This page is located in archive. Go to the latest version of this course pages. Go the latest version of this page.

Local search 1

The goal of this lab exercise is an implementation of a simple local search algorithm, first for binary representation. This algorithm will serve us as one of the baseline algorithms in later comparisons, and also its parts will be useful in evolutionnary algorithms.

We do not specify any particular programming language for the implementation. Choose what suits you best. But remember that the course instructors are able to help you only in Python, Julia, Java, and C; in other languages, you will have to help yourself.

You are supposed to come up with your own implementation of the tasks below. You can probably find many libraries for EA in each language, but for educational reasons, here we require your own work. Please read Rules of independent work.

Fitness functions

Implement the following fitness (objective) functions. They will serve us as optimization problems to be solved.

For binary chromosomes

For binary representation we assume that $x_i$ denotes $i$th bit of chromosome, $D$ is the length of the chromosome (if not stated otherwise).

OneMax

OneMax is a basic function, easy to optimize. It serves as a sanity check of your algorithm. (If your algorithm does not work on this function, it will hardly work on more demanding ones.)

$f_{OneMax}(\mathbf{x}) = \sum_{i=1}^D x_i$

LABS

LABS (Low-Autocorrelation binary sequence) is very hard binary problem. We assume a sequence $S=(s_1,\dots,s_D)$ where $s_i=\pm 1$ (i.e., you will have to replace all 0s in chromosome with -1). Autocorrelations of sequence $S$ are defined as

$C_k(S) = \sum_{i=1}^{D-k}s_is_{i+k}$.

Then, the “energy” of sequence $S$ (to be minimized) is defined as

$f_{LABS}(S) = E(S) = \sum_{k=1}^{D-1}C_k^2(S)$.

For vectors of real numbers

For real-valued representation we assume that $x_i$ denotes $i$th item of the real number vector. $D$ is the length of the vector (if not stated otherwise).

Sphere

Sphere is a basic, easy to optimize function of real arguments. Again, it serves as a sanity check of your algorithm. (If your algorithm does not work on this function, it will hardly work on more demanding ones.)

$f_{Sphere}(\mathbf{x}) = \sum_{i=1}^D (x_i-o_i)^2$,

where $\mathbf{o}=(o_1,\dots,o_D)$ is the offset of the function, and here it is also the optimum of the function.

Rosenbrock

Rosebrock's function is harder to optimize:

$f_{Rosenbrock}(\mathbf{x}) = \sum_{i=1}^{D-1} \left[ 100(x_{i+1}-x_i^2)^2 + (1-x_i)^2 \right]$

Perturbation

Implement a perturbation operation for binary representation. The operator should decide independently for each bit, whether it will be inverted or not. It is thus possible to invert more than 1 bit during a single perturbation operation.

Parameter Probability of inversion of a single bit
Input Binary chromosome
output Perturbed binary chromosome

Think about and decide whether you will modify the chromosome data structure directly, or whether you will return its perturbed copy.

Bin->real Mapping

Implement a function to transform binary string to vector of real numbers (such that we can use binary representation to solve problems with real representation).

Parameter Lower and upper bound of all coordinates in real space
Input Binary chromosome
Output Vector of real numbers

Based on the lower and upper bounds, the function shall know how many items $D$ of the real vector we expect. If the binary chromosome has the length of $L$, than each real number shall be encoded using $L/D$ bits. Use these bits and the corresponding lower and upper bound to compute the real number.

Implement the algorithm of local search with first improving stratgegy for binary representation.

Parameter Objective (fitness) function to be minimized
Parameter Perturbation operator we want to use
Parameter Termination conditions
Input Initial solution (binary vector)
Output Best solution found during optimization (binary vector and its fitness)
Output Statistics of the optimization run

Try to apply your algorithm to all the above fitness functions, and plot the progress of optimization using the returned statistics.

courses/a0m33eoa/labs/week_02.txt · Last modified: 2022/09/21 10:14 by xposik