Evolutionary Algorithms

Introduction

This repository consists of three implementations of evolutionary algorithms:

• Genetic Algorithm for Traveling Salesman Problem
• Evolution Strategies
• Ant Systems

Description

Genetic Algorithm for Traveling Salesman Problem

Algorithm

1. Create an initial population of P chromosomes (parents population).
2. Evaluate the cost (the total distance to be traveled) of each individual.
3. Choose n * P parents from the current population via proportional selection, where n - (0,1].
4. Select randomly two parents to create offspring using crossover operator.
5. Repeat the Step 4 until n * P offspring are generated.
6. Apply mutation operators for changes in randomly selected offspring.
7. Replace old parent population with the best (of minimum cost) P individuals selected from the combined population of parents and offspring.
8. If the maximum number of generations (T_max) were performed, then stop the algorithm; otherwise go to the Step 2.

The selection criteria, crossover and mutation are the major operators but cross-over plays the most important role. In the presented solution the Cycle Crossover Operator (CX) is applied.

Tasks

1. Implement the described GA algorithm to solve the traveling salesman problem. A map of cities provided by a tutor x = [0, 3, 6, 7, 15, 12, 14, 9, 7, 0], y = [1, 4, 5, 3, 0, 4, 10, 6, 9, 10]; N = 10, and the GA parameters: P = 250, n = 0.8, p_m = 0.2, T_max = 1000. What was the minimal total distance traveled? What is the sequence of cities to be visited ensuring the minimal total distance traveled? Show the results in a graphic form (as a network of connections).
2. Investigate the influence of parameters P, n and p_m on the mean minimal total distance traveled calculated for 10 trials. Change the values of P within a set {100, 300, 500}, n - {0.5, 0.7, 0.9} and p_m - {0.1, 0.3, 0.5}.

Evolution Strategies

Algorithm

The structure of chromosome representing an individual is a pair of float vectors v = (x, σ). The first vector, x ∈ Rⁿ, represents here a point in the n-dimensional search space and the second vector σ ∈ Rⁿ₊ is the vector of standard deviations. The main idea behind ES was to introduce a mechanism for a self-adaptation of the control parameters. This is achieved by applying the genetic operators to the object variable x, and to the strategy parameter σ. The mutation operator works by adding a normally distributed random vector r = N(0, σ) with a mean of zero and covariance matrix diag(σ²) to the object variable x^(t+1) = x^(t) + r and the strategy parameter is updated as follows σ^(t+1) = σ^(t) * exp(r_σ1) · exp(r_σ2), where superscript (t) denotes iteration t, r_σ1 is a single realization of zero-mean gaussian variable with variance τ₁². The r_σ1 = N(0, τ₁) = τ₁ · N(0, 1) and r_σ2 = N(0, τ₂²I) = τ₂ · N(0, 1) is a single realization of zero-mean gaussian variable with covariance matrix τ₂²I, where I denotes identity matrix. Parameters τ₁ and τ₂ usually are chosen as follows: τ₁ = 1 / sqrt(2n), τ₂ = 1 / sqrt(2 * sqrt(n)).

The acceptance of offspring x^(t+1) is determined by the level of its fitness f(x^(t+1)). The evolution strategies evolved into two mature approaches denoted as (µ + λ) - ESs and (µ, λ) - ESs. The (µ + λ) strategy selects the µ best solutions from the union of parents and offsprings. In contrast, in the (µ, λ) strategy the best µ offsprings a selected from λ (λ > µ) descendants to replace the parents (the life of each individual is limited to only one generation).

Denoting the population in iteration t as P_µ^(t) = {v₁, v₂, ... , v_µ} the evolution strategies method can be summarized in the following steps:

1. Set iteration index, t = 0. Initialize P_µ⁽⁰⁾.
2. Evaluate P_µ⁽⁰⁾.
3. Perform reproduction of P_µ^(t) to R_λ^(t).
4. Perform mutation of R_λ^(t) to O_λ^(t).
5. Evaluate O_λ^(t).
6. Select (O_λ^(t) ∪ Q) to P_µ^(t+1).
7. Update iteration index, t = t + 1.
8. If termination condition is not satisfied go to the Step 3.

In the (µ, λ) strategy Q = ∅ and in the (µ + λ) strategy Q = P_µ^(t). In the third step, the individuals from µ parents are reproduced to λ individuals in the set R_λ^(t) by independently random drawn individuals from P_µ^(t). As the termination condition usually pre-set number of iteration or achieving of pre-set value of the cost function is used.

Task

Write a computer program to solve the optimization problem provided by a tutor using the Evolution Strategy. Implement both, (µ, λ) and (µ + λ) approaches. As the population varying operator only mutation should be used. Evaluate the influence of the ES parameters (number of individuals, number of offspring, selection and crossover method, etc.) on the performance and the time of computations.

A given dataset contains a series of N = 101 measurements of input i_n and output o_n of a certain system f which can be modeled using the following function: o = a(i² - b * cos(cπi)). Find values of the parameters a, b and c using the Evolution Strategies method, minimizing the mean square error between o and o. Generate the initial population according to uniform distribution −10 ≤ a, b, c ≤ 10, 0 ≤ σ_a, σ_b, σ_c ≤ 10.

Ant Systems

Algorithm

Ant System is one of many variants of ant colony optimization algorithms. In this approach solutions are constructed by moving m artificial ants on the problem graph. The ants build a tour visiting n = N cities using a stochastic decision rule presented later. After a complete tour is constructed the artificial ants deposit the pheromone trail (update a variable associated with each arc). The amount of pheromone τ_ij(t) deposed in iteration t on arc (i, j) represents the desirability to move from city i to city j. The quantity of pheromone deposed by every ant is proportional to the quality of the solution found. The internal memory of each ant contains the list of already visited cities and is used to identify the details of the chosen path. By exploiting its memory an ant k can build a set of feasible solutions.

The ant decision in node i is based on a decision table A_i = [a_ij(t)]_[Ni] obtained using the following rule: a_ij(t) = (τ_ij(t))^α * (η_ij)^β / sum_l∈Ni^k ((τ_ij(t))^α * (η_ij)^β), ∀j ∈ N_i, where τ_ij is the amount of pheromone on arc (i, j) at time t, η_ij = 1/d_ij, N_i is the set of neighbors cities of city i, N_i^k ⊆ N_i is a set of neighbor cities of city i that ant k has not visited yet, and α and β are control parameters.

The ant k chooses to go from city i to city j ∈ N_i^k with probability p_ij^k = a_ij(t) / sum_l∈Ni^ka_ij(t). After all m ants have completed their tour the deposition and evaporation of pheromone mechanism is started. This mechanism can be described by the formula τ_ij(t + 1) = (1 − ρ)τ_ij(t) + ∆τ_ij(t), where ρ ∈ [0, 1] is the pheromone evaporation coefficient, and the total quantity of pheromone ∆τ_ij(t) deposed on arc (i, j) is specified by ∆τ_ij(t) = sum_k=1^m∆τ_ij^k(t). The quantity of pheromone ∆τ_ij^k(t) deposed by ant k on arc (i, j) (that it has used) is equal to 1 / L^k(t) if (i, j) ∈ T^k(t) else 0, where L^k(t) is the length of the tour T^k(t) made by the k-th ant.

Before the start of the optimization algorithm a small amount of pheromone τ⁰ > 0 is deposed on all arcs τ_ij^k(0) = τ₀. A good choice for parameter values is m = n, α = 1, β = 5 and ρ = 0.5 but the optimal set depends on the investigated problem.

Tasks

1. Write a computer program simulating the ants colony behavior in an environment where the nest and the food are separated by a double, asymmetric bridge.
2. Implement the Ant System to solve the traveling salesman problem. Use a map of cities provided by a tutor, m = N = 10, the maximum number of tours Tmax = 200. What was the minimal total distance traveled? What is the sequence of cities to be visited ensuring the minimal total distance traveled? Show the results in a graphic form (as a network of connections).

Installation

Windows specific black magic

1. Download desired Python 2.7 version and install these modules.

   pip2 install numpy matplotlib

2. Follow this guide to install desired toolchain MinGW. Note that CMake 3.16 comes with great opportunity to lose developer's mind under Windows. A nice feature that prevents CMake from working was added there. One cannot include sh.exe in the path. To solve this issue simply use one of newer versions (3.17 was tested and worked quite nicely).

3. Using MSYS2 shell execute following commands in the desired directory.

   git clone https://github.com/SzymonZos/Evolutionary-Algorithms.git
   cd Evolutionary-Algorithms
   git submodule update --init --recursive

4. Then run following commands using cmd from Evolutionary-Algorithms directory.

   mkdir build
   cd build
   cmake -G "MinGW Makefiles" ..
   cmake --build .

5. Choose desired built binary and run it.

Normal operating systems

1. Install Python 2.7 using your package manager. Unfortunately Python 3 does not cooperate well.

2. Run following commands. Note that default system generator, compiler and build type are chosen in this way. To change this behavior, proceed with standard CMake command -D.

   pip2 install numpy matplotlib
   git clone https://github.com/SzymonZos/Evolutionary-Algorithms.git
   cd Evolutionary-Algorithms
   git submodule update --init --recursive
   mkdir build
   cd build
   cmake ..
   cmake --build .