Non-Dominated Sorting Genetic Algorithm (NSGA-II)

Code by TomMakesThings

_{November 2021}

The aim of this project is to solve the following multi-objective optimisation problem using the elitist non-dominated sorting genetic algorithm (NSGA-II)

$min\{f_{1}, f_{2}\}$

$f_{1} = \frac{(\frac{x_{1}}{2})^2 \text{+} (\frac{x_{2}}{4})^2 \text{+} (x_{3})^2}{3}$

$f_{2} = \frac{(\frac{x_{1}}{2} - 1)^2 \text{+} (\frac{x_{2}}{4} - 1)^2 \text{+} (x_{3} - 1)^2}{3}$

For $-4.0 \le x_{1}, x_{2}, x_{3} \le 4.0$

Encoding

The decision variables for each individual $x_{1}, x_{2}, x_{3}$ are set up for minimization with gray coding. This is an encoding in which adjacent numbers have a single digit differing by 1.

Population Initialisation and Evaluation

A population of 25 individuals is created and each is assigned a random 10-bit string when initialized. They are then evaluated to determine their fitness. First the gray code values are converted to real values within the range $[-4, 4]$ using equation:

$x_{i} = a_{i} + (b_{i} - a_{i}) \times \frac{c_{i}}{2^l - 1}$

_where:

• _{$a_{i}$ is the lower bound $-4$}
• _{$b_{i}$ is the upper bound $4$}
• _{$c_{i}$ is the integer value of the gray code}
• _{$l$ is the length of each gene}

Then using the decoded values, $f_{1}$ and $f_{2}$ are calculated.

Individuals are sorted into fronts using the efficient non-dominated sorting algorithm. First the population is copied, then sorted based on $f_{1}$. If the $f_{1}$ are equal, then sort on $f_{2}$. The first solution is assigned to front 1. All further solutions are compared the current front, starting with front 1. If they are dominated by at least 1 solution in the current front, a new front is created with this individual. Otherwise check the next front. If all fronts are checked, a new front is created containing this individual.

Once the individuals are separated into fronts, the crowding distance for individuals in each front is calculated. Solutions at the end of each front are assigned infinite distance, while those in between are assigned the average side length of its two neighbouring solutions.

Mate Selection

Pairs of parents are selected through binary tournament selection until 25 offspring are produced. For each selected parent, two individuals are randomly selected from the population to compete. An individual is chosen if it dominates the other. If they are in the same front, the individual with the largest crowding distance is selected. If these are also equal, the selected individual is randomly chosen.

Crossover and Mutation

Uniform crossover is applied to parent pairs at a chance of 0.9. If no crossover occurs, parents’ genes are directly transferred to resulting offspring. Mutation is applied to the created offspring at a chance inversely proportionate to the chromosome size, i.e.

$p = \frac{1}{L}$.

Selection

Parents and offspring populations are combined and sorted into fronts using non-dominated sorting. Individuals are assigned a crowding distance and individuals within each front are sorted by crowding distance in descending order. Fronts are combined into a list in ascending order, and the top 25 individuals are selected for the next population.

Evolution

The algorithm is run for 30 generations causing the individuals to converge towards the Pareto frontier. This is the shape formed by the optimal solutions in the objective space. In this case it is convex as this is a minimisation problem. To evaluate performance across generations, hypervolume is calculated using the worst objective values as a reference point.

1. Click here to download the repository contents
2. Extract the Jupyter notebook from the ZIP
3. Import the notebook into Colab