Genetic algorithm (Preference based solver)

[Wilmar-Smit]

TLDR

• Plans for using a GA for preference based solver of the timetables
• AI usage
• • Only used in the main code snippit and in finding an appropriate library and bouncing ideas off of.

[Wilmar-Smit]

Problem

• We want students to be able to select a timetable based on their time preference as well finding a timetable that works for their needs

Solution

• A simple genetic algorithm. Non-deterministic "good enough" solution is our goal, we want to be able to irrespective of how complicated a problem is return to a user a good output to service all our users.

Decisions

Language decision

• C++
  • We want this to be fast and something that can scale and be tweaked and designed within our skill sets.

Library decision

• openGa
• github
• PDF manual

Positives

• Extremely well documented
• Multi threading (if we have that capability on the server it would be amazing)
• Many ways we could define stopping conditions and optimising etc
• It is one file
  • one hpp file we compile and work with.
• Multi optimisation and single optimisation if we ever want to do crazy things like friday specific time optimisation.

Middle grouns

We need to implement the following

• Not a negative since we get tons of control however other libs define this but those are unproven and untested.

1. population initiation.

void init_genes(
    GeneType& p, 
    const std::function<double(void)>& rnd01
)

2. Evaluation

bool eval_solution(
    const GeneType& p, 
    MiddleCostType& c
)

• Where we do logic for $f(n)$
• middle cost is what we write the $f(n)$ to can be used later apparently

3. Mutation

GeneType mutate(
    const GeneType& p, 
    const std::function<double(void)>& rnd01, 
    double mutation_rate, 
    double shrink_scale
)

• mutation rate => how often we mutate a gene
• We will be able to ignore shrink_scale its for different types of problems

4. Crossover

GeneType crossover(
    const GeneType& X1, 
    const GeneType& X2, 
    const std::function<double(void)>& rnd01
)

• 2 genes and a randomise function
• crossover is set within setup of the ga, same as the mutation rate its just cross over logic is external to this.

AI Example of main for inference

int main() {
    // Instantiate the genetic engine using native vector containers directly
    EA::Genetic<std::vector<int>, std::vector<double>> ga;

    // --- STRAND 1: FUNCTION REGISTRATION ---
    // Registers the function pointers to the genetic operator implementations
    ga.init_genes    = init_genes;
    ga.eval_solution = eval_solution;
    ga.mutate        = mutate;
    ga.crossover     = crossover;

    // --- STRAND 2: ALGORITHM MODES ---
    ga.multi_objective  = true; // Explicitly turn on Multi-Objective mode (NSGA-III)
    ga.objective_number = 2;    // Tells openGA your cost vector contains exactly 2 parameters

    // --- STRAND 3: POPULATION & TIMING GENERATIONS ---
    ga.population_number = 100; // 100 active solutions tracked per generation pool
    ga.generation_number = 500; // Hard loop termination limit

    // --- STRAND 4: PROBABILITY RATES ---
    ga.crossover_rate = 0.85; // 85% probability that selected parent structures undergo a crossover
    ga.mutation_rate  = 0.10; // 10% base probability passed down to mutate individual gene points

    // --- STRAND 5: SYSTEM HYPERPARAMETERS ---
    ga.idle_mutation_rate = 0.25; // Boosts mutation scale automatically if population fitness flatlines
    ga.dynamic_threading  = true; // Automatically spreads evaluations across available CPU cores

    // --- STRAND 6: EXECUTION ---
    std::cout << "Launching genetic optimization engine..." << std::endl;
    ga.solve(); // Blocks main thread execution until generation target is complete
    std::cout << "Optimization loop complete!" << std::endl;

    // --- STRAND 7: RESULTS EXTRACTION ---
    // Pull the final raw results directly out of ga.last_generation using native array indexing
    std::cout << "Best result score 1: " << ga.last_generation.best_middle_cost[0] << std::endl;
    std::cout << "Best result score 2: " << ga.last_generation.best_middle_cost[1] << std::endl;

    return 0;
}

Design decisions

Factors we must assess.

Pure failures

• These immediately make a solution invalid e.g g(n) = 0, short circuits and kills the eval (for performance)

Value of solution

• Functions that determine how well the valid solution performed.

How we package the data we give the GA

• In terms of jsons that are converted to structs then jsons again before being sent

Data package

• Events
  • Event ID string
  • Event number int
  • module code string
  • eventDay enum {monday through sunday}
  • event_start int(minutes from midnight)
  • event_end integer (minutes from midnight )
• Module grouping
  • module code string
  • number_Occur int
    • this is simply for different groups for instance cos132 has 2 groups a student needs to attend all 3, however can attend any group in order being 1 -> 2 -> 3. which is why event number is required in events for instance.
  • events vector<events>
    • the list of events with this module as a code.
• GaData
  • modules vector<Module_Grouping>
  • targetTime int
    • Minutes from midnight this is used in the eval function

Pure failure functions

C(n) Count constraint

• This evaluates
  • Correct number of occurrences of a module
    • As provided by number_Occur it checks that the module appears the correct number of times.
    • Ensures that all modules modules occur as many times as they should 20 events expected => 20 occur
    • It can also do pattern check listed below simultaneously

P(n) pattern constraint.

• This evaluates
  • Correct pattern adhered to for each module
    • 3 events expected must find each 1 -> 2 -> 3 irrespective of the group (for instance)
    • We can also maybe add the restriction of same group as an option in the GaData for a user to decide
    • This pairs well inside of C(n) since once we find the occurrences of a module to be standard, we can check if they conform to our expectations.

Pre-optimisation

• We can optimise this by providing the chromosome type ordered (may effect GA randomness)
• This means we can pre-calulate
  • Each modules start
  • Each modules end
    • thus interval
  • Then a step so when checking we dont do O(n) traversal for each module we know they are group thus when we hit a new module code we can evaluate correctness
• Short circuit involving P(n) -> if we detect a value twice immediately exit.

O(n) overlap constraint.

• The hardest one to do (most inefficient)
• Basically checks
  • Events on same day? events at same time ? fail else pass
• This is because it needs to evaluate with all of the modules for overlap

Pre-optimisation

• hash map (really un-optimised if done per eval)

  • Put events into format day&&Time (maybe a struct)
  • Check all active events
  • If key day and time exisists -> collision -> fails else -> continue.
  • Problem only for events over several slots but that would be the same for 2D bit map

• 2D BIT map

  • We make a grid of times we know lectures to run for instance 7 30 -> 8 30

{
std::vector<std::vector<bool>> 
//(an insane optimisation from std vec is if you make a bool array it works with individual bits instead of a bool == byte)
}

• Days = rows, slots = cols

  • Then we do an max o(n) pass through of the events.
  • Simple function finds which slot the events take up.
  • once located a slot we make it true (some value occupies this slot)
  • when we find that there are 2 events in one slot we kill it (short circuit return 0).
  • extremely efficient in terms of memory and speed

• Which means its actually more efficient than the other 2 lol.

Solution value function

V(n) value function

• This is how we deep a solution to be good.

1. mean
   • Simplest is mean of all the active times selected in the array (how close is it to the time we want).
     • Slight optimisation using the 2D bit map we can on our o(n) pass from start to finish we can already start working this out somewhat in terms of calculating means etc
     • If the bit map fails it wont make any difference but if it doesn't fail then we don't have to do another O(n) pass through.
2. RMSD
   • calculate the average distance between a set of values and a specific target
   • Treats outliers poorly
3. MAD
   • Mean absolute deviation
   • Average distance between each point and a central reference point
   • Not harsh on outliers

Diagram

graph LR
    Start(["Start f(n)"]) --> C_n{"c(n) Count Constraint"}
    
    C_n -- Pass --> P_n{"p(n) Pattern Constraint"}
    P_n -- Pass --> H_n{"h(n) Overlap Constraint"}
    H_n -- Pass --> V_n["v(n) Value Function"]
    
    C_n -- Fail --> Penalty["Assign Penalty Score"]
    P_n -- Fail --> Penalty
    H_n -- Fail --> Penalty
    
    Penalty --> Exit(["Exit evaluation"])
    V_n --> Exit

Loading

Final optimisation

• It would be a perfect world if the CP-sat working solution could be provided before starting the GA, we provide that as an init solution along with several random variations of it such that we can at least return a working solution even if we could not optimise it further in the GA