====== 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.

<WRAP center round important 100%>
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.
</WRAP>


<WRAP center round tip 100%>
**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 [[help:common:plagiarism_cheating|Rules of independent work]].
</WRAP>


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

<WRAP center round download 60%>
{{ :courses:a0m33eoa:cviceni:onemax.txt |Test data}}
</WRAP>



** 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)$.

<WRAP center round download 60%>
{{ :courses:a0m33eoa:cviceni:labs.txt |Test data}}
</WRAP>

==== 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.

<WRAP center round download 60%>
{{ :courses:a0m33eoa:cviceni:sphere.txt |Test data}}
</WRAP>


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

<WRAP center round download 60%>
{{ :courses:a0m33eoa:cviceni:rosenbrock.txt |Test data}}
</WRAP>



===== 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.


<WRAP center round download 60%>
{{ :courses:a0m33eoa:cviceni:bin2real.zip |Test data}}
</WRAP>

===== Local search =====
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.