% EOA HW01 - Solving TSP via evolutionary algorithms % František Boháček % 2025
This is a report for hw02 for EOA course on CTU FEE. The goal has been to compare constrained evolutionary algorithms with two approaches:
The report covers the implemented algorithms and the results on problems taken from "Problem Definitions and Evaluation Criteria for the CEC 2006"
One of the methods to solve constrained problems.
Stochastic ranking uses similar structure as bubble sort. It iterates through the population
and swaps to elements when one is better than the other (lower fitness).
But it does that only with probability p. With probability 1 - p it instead compares
the constraint violations of both elements.
Then, the selection takes into account ranking based on the list sorted through stochastic ranking. Generational replacement has been used to easily ensure that the stochastic ranking order is still respected.
Stochastic ranking is implemented in eoa_lib/src/constraints.rs
As second method, NSGA-II has been used to solve the constrained problems. It works based on non-dominated fronts. All elements in one front are not dominated between each other. A dominates B if and only if A is not worse than B in all objectives and A is better than B in at least one objective.
NSGA-II first sorts the elements based on the non dominated fronts. Then, within each front, crowding distance is calculated. Crowding distance is used to discourage solutions that are close to each other. For both selection and replacement the comparison is then done first according to the front number and within same front, according to the crowding distance. Higher crowding distance is preferred.
As part of NSGA-II, tournament selection is used and for replacement, best replacement is used, keeping only the best individuals. Specific parameters of using 5 candidates for tournament selection and probability of 0.99 for choosing the best candidate out of 5.
Multi objective evolution is implemented in eoa_lib/src/multi_objective_evolution.rs
Since the chosen problems are real problems, real representation has been used.
For mutation, the solution is changed with random sample from normal distribution with zero mean. The standard mean has been chosen differently based on the problems.
As for crossover, arithmetical crossover is used.
Arithmetical crossover chooses random \alpha between
0 and 1. Then, the offspring's i-th component is
\alpha \cdot p_{1i} + (1 - \alpha) \cdot p_{2i},
where p_{1i} (p_{2i}) is first (second) parent's i-th
component respectively.
In the default implementation, NSGA-II is not suitable for solving constrained problems. This is because all the feasible individuals will be at 0 in the objective with constraints sum.
Because of this, a very simple idea can arise to make it better - if multiple feasible solutions are sufficiently distant, their constraint function evaluations could also differ if they are allowed to go below zero. That feasible solutions can have higher crowding distances. But this seems to make sense only for cases where there is objective per constraint. Otherwise a constraint that is far below zero would win over and the other constraints might not have chance to get satisfied.
Every problem with given configuration has been ran 10 times. The initialization has been done randomly, but within given bounds different for each problem:
0, 0 50, 500, 0 10, 10-1, -1 1, 10, 0 3, 4First also bounding the crossover result and mutation has been tried, but it turned out it doesn't even help much, so that has been removed. (the method for bounding has been to first try the mutation/crossover maximally 5 times if it's out of bounds and after last try, it has been bounded forcibly)
For stochastic ranking approach, following parameters have been used: arithmetic crossover, normal distribution mutation with probability 0.1, tournament selection with 5 individuals and 0.95 probability of choosing the best one. Weights of 1e9 have been chosen as with 1.0 there have been problems with g11, probably due to very small numbers that were being summed together and rounded.
As for runtime parameters, population had 500 individuals, there are 1000 iterations,
500 parents in each iteration. The number of iterations in stochastic ranking is 2 * population.
Probability of comparing fitness is 0.45. This is all with exception of g11, where different parameters
have been used to so that feasible solution is found. Specifically epsilon has been chosen to be 0.01,
population size 1250, 1000 parents, 500 iterations, 2000 for number of iterations of stochastic
ranking and the probability 0.05. Still, feasible solution has not been found on every run. The results
include only runs where solution has been found.
The following standard deviations have been chosen:
1.00.50.01 / 50 (epsilon divided by 50)0.1For NSGA-II TODO
The following plot compares:
As can be seen, NSGA with multiple objectives behaves worse. This is possibly because the algorithm can lower second and third objective more easily than lowering the first one or lowering all three at the same time. This is then even more visible for allowing the constraints to go under 0. So the simple idea has failed.
TODO add the plot
g11 is special in the regard that it has an
equality condition. Because of that, it can make
sense to compare it with other ones. Here's the result:
As can be observed, g11 cannot be optimized easily
as most of the solutions are going to be infeasible.
Many of the runs, no feasible solutions are found. And
since there is only a small range of values to go to when
in feasible space, it can easily happen mutated solution
again goes outside of feasible space. Because of this, the
p parameter had to be significantly lowered and this leads
to optimizing for feasible solutions more than for better solutions.
Here is a plot with fraction of feasible solutions in iteration for both problems:
Rust has been chosen as the language. There are four subdirectories, eoa_lib, tsp_hw01, constr_hw02 and tsp_plotter.
eoa_lib is the library with the generic operators defined, with random search, local search and evolution
algorithm functions. It also contains the most common representations, perturbations and crossovers for them.
constr_hw02 is the implementation of hw02. It contains the problem definitions and a simple CLI
program to run any of the problems with either stochastic ranking or with MOE.
tsp_plotter plots the graphs. It can now be used forjboth homework.
tsp_hw01 is folder with source of the first folder, kept for my convenience as I keep them in the same repo
and would have to be changing Cargo.toml properly to make sure the build doesn't fail if it's not present.
As part of the work, apart from the standard library, third party libraries have been used, namely (the list is the same as for hw01):
For run instructions, including generation of the plots in this report, see README.md.
LLM has been used similarly to how in HW01. The only thing that changed is that Gemini has also been utilized, not only Claude. (Students got it now for free for a year :))