Warning

This page is located in archive.

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.

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

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 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]$

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.

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