Optimization of multi-variable functions is a classic problem in mathematics and computer science. It involves finding the best variable values (e.g., function minimum or maximum) in a multidimensional space. This approach is widely used in engineering and artificial intelligence.
The goal of this project is to implement a genetic algorithm for optimizing multi-variable functions.
Genetic algorithms (GAs) are a class of optimization algorithms inspired by biological processes such as natural selection and genetics. They are used to find solutions in complex search spaces where traditional optimization methods may be inefficient.
Genetic algorithms operate by simulating the evolution process, where solutions (individuals) "compete" for survival and reproduction in an optimization problem.
Key elements of genetic algorithms:
Chromosomes – A chromosome represents a solution, typically encoded as a vector, bit string, or sequence of numbers/characters.
Genes – The smallest unit of information in a chromosome, representing a feature of the solution.
Population – A set of chromosomes representing different potential solutions. The population is initially generated randomly or based on some predefined rules.
Selection – Selection determines which chromosomes will reproduce. Several methods can be used:
Roulette wheel selection: Individuals are chosen based on their fitness function, where more "fit" individuals have a higher chance of being selected.
Tournament selection: Random individuals are selected, and the best among them is chosen for reproduction.
Best selection: The best individuals from the current generation are retained.
Crossover – After selecting parents, crossover is applied to generate new offspring. Various techniques exist:
Single-point crossover: One division point in the chromosome.
Two-point crossover: Two division points.
Uniform crossover: Each gene is randomly inherited from one of the parents.
Granular crossover: Similar to uniform, but entire blocks of genes are randomly selected.
Mutation – Random modification of genes to introduce diversity and improve solutions.
Elitism – Ensures that the best individuals always survive to the next generation.
Fitness Evaluation – Each chromosome is assessed using a fitness function, which determines how well it solves the optimization problem.
Reproduction Process – The algorithm iterates through multiple generations, applying selection, crossover, mutation, and fitness evaluation, until a satisfactory solution is found.
Python 3.11
tkinter
ttkbootstrap
matplotlib
Implementation of a genetic algorithm for function minimization.
Configurable number of variables.
Binary representation of chromosomes.
Graphical user interface (GUI).
Graph generation of function values across iterations.
Saving results to a file/database.
This project aims to find the minimum/maximum of the Martin and Gaddy function.
self.genes – Encodes the values.
self.fitness – Stores the fitness function value.
decode() – Converts a binary chromosome into real numbers. The first half represents variable X, and the second half represents Y, scaled to the range [-20, 20]:
Normalize the binary number to the range [0,1].
Scale it to [-20, 20].
evaluate() – Decodes the chromosome and computes the fitness function value. Lower fitness values indicate better solutions (for minimization problems).
The Population class generates a set of potential solutions. The Martin and Gaddy function has two variables, so the number of variables is fixed.
population_size – Number of individuals.
precision – Number of bits allocated for each variable.
Tournament selection – Random individuals compete, and the best one is selected.
Best selection – Selects the best individuals.
Roulette wheel selection – If maximizing, total fitness is the sum of all fitness values. For minimization, fitness is inverted, giving lower fitness values higher weights.
Single-point crossover – A single division point in the chromosome.
Two-point crossover – Two division points.
Uniform crossover – Each gene is randomly selected from either parent.
Granular crossover – Like uniform, but selects entire blocks.
Boundary mutation – Flips the first and last gene.
Single-point mutation – Randomly selects and flips a gene.
Two-point mutation – Selects two different genes and flips their values.
Inversion mutation – Selects a random segment and reverses its values.
Iterate through epochs.
Create new_population to store selected and modified individuals.
Apply elitism and add the best individuals.
Generate the new population:
Apply crossover, mutation, inversion.
Evaluate fitness.
Add new individuals.
The GUI, built using tkinter, allows users to configure and interact with the algorithm efficiently.
The program provides visualization of results using:
3D plot with the best solution.
Heatmap and an animated heatmap (GIF) showing the best solutions across epochs.
Fitness function plot.
Event log tracking algorithm operations.
