~ruther/ctu-fee-eoa (c67cbe05b263f3d2f59d9217d0e112ff23b43d74): codes/report.md

% EOA HW02 - Solving constrained problems using evolutionary algorithms % František Boháček % 2025

#Intro

This is a report for hw02 for EOA course on CTU FEE. The goal has been to compare constrained evolutionary algorithms with two approaches:

Using stochastic ranking,
Using multi objective evaluation with the original fitness as first objective and weighted sum of constraints as second argument.

The report covers the implemented algorithms and the results on problems taken from "Problem Definitions and Evaluation Criteria for the CEC 2006"

#Used algorithms

#Stochastic ranking

This is one method to solve constrained problems. Stochastic ranking first sorts the individuals based on a stochastic sorting. Then, those ranked individuals are put to a tournament selection with their new rankings, instead of using their original evaluation.

Similar algorithms structure as bubble sort is utilized. 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.

Generational replacement has been used to easily ensure that the stochastic ranking order is still respected during replacement. It would also be possible to use other replacement strategies, but then the stochastic ranking would have to run twice after the offsprings are made.

Stochastic ranking is implemented in eoa_lib/src/constraints.rs.

#Unconstrained multi objective evolution (NSGA-II)

As a second method, NSGA-II has been used to solve the constrained problems. It is mainly designed to solve multi-objective problems. But the constraint problem can be mapped to it by making the original objective the first objective and weighted sum of constraints as second objective. 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. To obtain the first front, non-dominates solutions are obtained from the whole population. Then they are removed and the process is repeated to get second front and so on.

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 from both original population and newly made offsprings. 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. Note that at first the author has used the original evolution function as base, but later realized it's wrong. In NSGA-II, the whole population has to be reevaluated after offsprings are made. The original function evaluated offsprings only to save on count of function evaluations. But that meant two different front sortings were being compared in the replacement, one for the current population and the other for offsprings. Consider population.evaluate(); offsprings.evaluate(); vs population.append(offsprings).evaluate(), where in case of NSGA-II evaluate() means to obtain the non-dominated fronts and crowding distances.

#Used operators

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 deviation has been chosen differently based on the problem.

As for crossover, arithmetical crossover is utilized. 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.

#Making NSGA-II behave better for constrained problems

In the default implementation, NSGA-II is not so suitable for solving constrained problems. This is because all the feasible individuals will be at 0 in the objective with constraints sum and each front will have only one feasible candidate.

#Custom solution

To overcome the limitations, a solution of using an archive of feasible solutions is proposed. The idea of archive is similar to the SPEA2 algorithm, but the solutions kept in it are different. Specifically it has been chosen that the archive will have only feasible solutions. The archive has a fixed size and it contains the best known solutions (based on the original problem objective). After each iteration it's updated, joining the previous archive and new population and leaving only the best feasible candidates.

Then, during pairing/crossover infesiable solutions might get replaced. The logic is as follows:

If only one of the parents is infeasible, replace it with a feasible with probability $p_1$
If both parents are infesiable, replace the first one with probability $p_{21}$ and then, if the first one is replaced, replace the second one with probability $p_{22}$.

The probabilities were chosen as: $p_1 = 0.4, p_{21} = 0.6, p_{22} = 0.3$. The idea behind these particular values has been to have majority of pair with at least one feasible solution.

In the code this is implemented as a crossover wrapper, because it was the easiest, even though logically it would make more sense to put this to pairing step. But the implementation for pairing step is that it produces indices in the original population. Because of that it is not possible to add new individuals. The implementation is located in src/constr_hw02/feasible_crossover_wrapper.rs

#Using NSGA-II for constrained problems

NSGA-II can be modified for constrained problems. While the idea is mainly that multiple objectives are used and on top of that, there are constraints, the idea can be expanded to the problem that's solved here. Specifically still the two objectives can be used, but the definition of i dominates j is changed as follows, let's say we have solutions i and j, solution i constraint-dominates j if any of the following holds:

Solution i and j are both feasible and solution i dominates j.
Solution i is feasible and solution j is not.
Solutions i and j are both infesiable, but each constraint is violated less by i than by j.

It would be possible to use just one objective function, being the original objective, but then we no longer have a multi objective problem.

This is implemented along with NSGA-II at src/eoa_lib/multi_objective_evolution.rs.

#Results

Every configuration has been ran 20 times to accomodate for inherent randomness. The initialization has been done randomly, uniformly within bounds given in the definitions of the problems. Later in the algorithm run, the bounds are also enforced. Specifically for crossover and mutation. When mutation or crossover produce results out of bounds, the operation is retried five times. If all produce results out of bounds, the result is forcibly bounded. This has been done because some problems, such as g04 were escaping the bounds and finding different optima, much lower than the originally reported optima. It is hasn't been check if this is because there are really better optima out of bounds or if there is a numerical instability causing this. None of the best candidate evaluations contain infeasible solutions. This is also why some of the graphs start only after few function evaluations, because a feasible solution has not been found until that evaluation.

For stochastic ranking approach, following parameters have been used: tournament selection with 5 individuals and 0.95 probability of choosing the best one. All weights have been chosen as 1.0.

Arithmetic crossover is used. The offsprings mutate with probability of 0.1. Mutation uses a sample from normal distribution with mean of 0.0 and standard deviation given according to the following table:

g04 - 1.0
g05 - 10.0
g06 - 1.0
g08 - 0.5
g09 - 1.0
g11 - 0.01 (epsilon is 0.00015)
g24 - 0.1

As for runtime parameters, population had 250 individuals, each iteration generated 125 offsprings out of 125 parents. There were 1250 iterations, The number of iterations in stochastic ranking is 2 * population. Probability of comparing fitness in stochastic ranking is 0.45 for most problems. For g04 it was set to 0.65, because that led to significantly better results. For g05, it is 0.2, because with 0.45 usually no feasible solution has been found.

To get the percentage deviation from the optimal value, because of negative values, the formula has been changed. Specifically in cases when the optimal value is below zero and the values cross zero, near zero the deviation would be zero. Because of that, in cases where optimal value is negative, the function has been shifted up by $-2 \cdot o$, where o is the optimal value. New optimal value is $o_{n} = -o$ and the data do not cross zero. Then the formula for deviation is $(x_{n} - o_{n}) / o_{n}$

First here is a chosen problem's percentage deviation, specifically of g09. This is one of the haarder problems, using 7 variables and 4 constraints.

Comparison of best candidates so far for g09. {latex-placement="H"}

The graph depicts the average values and it can be observed that at the beginning, the variance is very large, but it's getting consistent in further iterations. That means the algorithms are working roughly as they should, prefering better candidates.

\newpage

#Comparing the approaches

The following plot compares:

Stochastic ranking (S-Rank)
NSGA-II
NSGA-II with multiple objectives (NSGA-II Multi)
NSGA-II improved - customized archive (NSGA-II Improved)
NSGA-II constrain-optimized tournament (NSGA-II Constr)

Multiple targets have been chosen: 0.1 %, 0.5 %, 1 %, 5 %, 10 % and the value is increased every time a target is hit in any of the runs. The result is divided by all the runs. This has been collected from all used problems: g04, g05, g06, g08, g09, g11 and g24. Some of those problems are quite simple, using just 2D and 2 constraints, while some of them use more variables and more constraints.

Probability of success among all problems and ran instances. For targets: 0.1 %, 0.5 %, 1 %, 5 %, 10 %. {latex-placement="H"}

As can be observed, stochastic ranking is achieving lower success rates next to NSGA Multi and NSGA Constrained. This could be because of wrong parameter selection. It can be hard to balance the probability of comparing the objective and constraints, too high values lead to no feasible solutions, whereas too low mean the function is not optimized as well.

NSGA multi is capable of catching up with S-Rank, despite the low number of feasible solutions it's capable to find, as can be observed in the next section. The reason that it behaves worse than the NSGA-II could be because of the multiple objectives, where it tries to minimize all of them. That way it might happen it minimizes mainly the objective function, but not the constraints. Or one of the constraints and not the other(s).

Improved NSGA seems to behaves the best. This could be because it does not only prioritize feasible solutions, it prioritizes good feasible solutions. When we already do find a good feasible solution, there is much more potential for making it even better.

NSGA constr is capable of finding more feasible solutions compared to NSGA, at least early in the run (see the next section), but it does produce worse results, suggesting that it prefers feasible solutions even if they aren't as good. This really is the case when looking at the conditions.

#Comparing g11 with g06

g11 is special in the regard that it has an equality condition that is harder to satisfy. So here only g11 is compared with g06. A fraction of feasible solutions for each iteration has been obtained, as well as average constraint violation.

Here is a plot with fraction of feasible solutions in iteration for both problems:

#Comparing feasibility in the population

One important metric is how many individuals in the population are actually feasible. Because this can differ quite a lot for different problems, two graphs are shown here, one each for a single problem.

Here is the graph for g06, that's one of the easier problems, 2D function, with two lower than constraints.

Then g11, that's also only 2D, but the constraint is an equality function. Equality is harder to satisfy, because the area of feasible solutions is smaller. And through the mutation it's much more probable to leave the feasible area than to stay inside of it.

\newpage

Fraction of feasible solutions in g06 over time. {latex-placement="H"} {latex-placement="H"}

\newpage

As can be seen from the graphs, the NSGA-II multi approach is not so well, this could be because it tries to mostly optimize the original function and/or only one of the constraints. This is because it can get more reward for doing so and the third objective can be left above zero, leading to infesiable candidates. Still, it does produce some feasible candidates as can be seen from the previous results, it's just that they do not stay in the population for longer.

What is worth noting is the NSGA. For g06 it is capable of reaching population full of feasible candidates, but for g11, the feasible solutions oscillate and stay lower than a half of the population.

The srank converges to a given point which is what we would expect, because although it's depending on randomness, in the end the swaps are applied a lot of times, 'cancelling out' the randomness.

Both proposed improved NSGA and NSGA with constraint handling are capable of reaching full population of feasible candidates. As for the proposed improvement, the population can sometimes lose feasible candidates, this is because of the inherent randomness. NSGA with constraint dominance on the other hand stays on 100 %, this is presumably because feasible solutions are always prioritized to the non-feasible ones based on the rules.

#Tasks done above minimal requirements

1 point - Multi-objective approach with more objectives
1 point - Improve NSGA with archive
1 point - Comparison on more complex problems
1 point - NSGA-II with modified tournament operator (constrained domination)

#Code structure

Rust has been chosen as the language. There are four subdirectories, eoa_lib, tsp_hw01, constr_hw02, tsp_plotter and py_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_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. tsp_plotter plots the graphs of hw01 only.

py_plotter for the second homework a python plotter has been utilized for simplicity. It uses numpy, pandas and matplotlib.

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):

nalgebra for working with vertices and matrices,
plotters for plotting
rand
rand_distr
thiserror for easing work with errors
serde, serde_json for loading json files
csv for loading csv files

#Running the algorithms

For run instructions, including generation of the plots in this report, see README.md.

#Usage of LLM

LLM has been used similarly to how in HW01. The only thing that changed is that Gemini has also been utilized, not only Claude. (there was an offer for students to get it for free for a year :))