Maximum point quadratic function

Determined with genetic algorithm

---

About it

This project finds the maximum value for a given quadratic function using the genetics algorithms.

It provides both a cli and gui and outputs all the intermediary steps in the process.

While the scope of this projects is to find the maximum point of a quadratic function, the algorithm can be used for any other function, by changing the codification method and the fitness function.

---

How to use it

For this project there are some dependencies that must be installed. You can opt for having a virtual environment for managing them, case in which you have to run this snippet:

python3 -m venv venv
source venv/bin/activate
pip3 install -r requirements.txt

After that, by running the the code you would have to choose which interface you want the project to be run in.

For the cli you have to manually adjust the parameters from the main before running the app. In the graphic interface, the parameters can be change at the runtime.

---

How it works

The algorithm first need all the parameters set, which are:

• population_size: int - how big the population will be
• generations: int - for how many generations the app will run
• lower_bound: float - lower bound for x values
• upper_bound: float - upper bound for x values
• precision: int - how many digits for floating representation
• function arguments: list[float] - the coefficients for the quadratic function
• combination_rate: float - the probability for combining two cromosomes (from 0 to 1)
• mutation_rate: float - the probability for a cromosome to mutate (from 0 to 1)

For generating the next generation, the algorithm uses the following steps:

NOTE: That to have a maximum point in a quadratic function, the first coefficient must be negative.

Codification

For the genetic algorithm to work, the cromosomes must be codified in a way that the algorithm can understand. In this case, the cromosomes are represented as a list of binary values, where each value represents a bit of the x value. The number of bits is determined by the precision parameter.

For a given precision the algorithm will need

$$ \lceil \log2((\text{upper-bound} - \text{lower-bound}) \times 10^{\text{precision}}) \rceil $$

bits to represent the x value in binary.

For a more information about encoding and decoding check this: resource.

---

Selection

For the selection process, the algorithm uses the elitist selection method. This method selects the best cromosomes from the current population and propagate it to the next generation.

---

Crossover

The crossover process is done by selecting pairs of cromosomes from the current population and combining them to create two new cromosomes. The probability for this to happen is determined by the combination_rate parameter. The best cromosome from the current generation is excluded from this process.

The combination reffers to chosing a single point from the binary represenattion and swapping the values from that point.

---

Mutation

The mutation process is done by selecting cromosomes from the current population and changing a random bit from it. The probability for this to happen is determined by the mutation_rate parameter.

---

Tech specs

The graphical interface is made using tkinter and the graph

The GUI provides 4 buttons:

• Next - it iterates a generation and updates all labels
• Auto - it iterates all generation until it is stopped and updates all labels
• Reset - creates a new population with the saved inputs and starts again from generation 1
• Go to generation - jump to a given generation without updating the labels

The app features a menu settings tab from which all parameters can be changed.

NOTE: It is a very computationally expensive process, so it is not recommended to use a big population size or a big number of generations. This only affects the big jumps made with the Go to generation button.

The app is not using a reactive framework. All the updates are done using __update prefixed methods.