How do Evolutionary Algorithms differ from each other?
Meet the Evolutionary Algorithm Playground, an interactive web app to compare Genetic Algorithm and Particle Swarm methods
Evolutionary Computing is the collective name for a range of problem-solving techniques based on principles of biological evolution, such as natural selection and genetic inheritance. [1]
Two of these methods are Genetic Algorithms and Particle Swarm Optimization.
The Genetic Algorithm (GA) is based on the evolutionary theory developed by Charles Darwin. Through generations, selection, crossover, mutation and elitism processes are applied to the population to find the fittest individual.
Particle Swarm Optimization (PSO) is a computational method which is based on the concept of swarms, such as fish shoals and bird flocks. It iteratively searches for the fittest individual within the cluster.
Both algorithms are applied to optimization problems. An optimization problem is a problem of finding the best solution from all feasible solutions. According to the problem, the best solution can be the arguments which maximize or minimizes the output of an objective function. Examples of maximization quantities are profits, performance, sales, growth, etc. Minimization quantities can be losses, material spending, and many others.
With this in mind, the Evolutionary Algorithm Playground was developed:
https://evolutionary-algorithm-playground.streamlit.app/
It is an entirely Python-based web app which allows users to tweak varying parameters and see how the algorithms perform. The algorithms were built from scratch using Numpy. The application was developed using Streamlit.
The objective of the app is to improve the understanding of bio-inspired algorithms in a friendly and interactive way.
Let’s take a look at the algorithms.
Genetic Algorithm
The search interval (set by the user) is converted to a binary representation (the number of representation bits is also set by the user). A new population is randomly built. Beyond the number of representation bits, it also considers the number of individuals and the dimension of the problem (both set by the user). The population is evaluated by the test function and the selection, crossover, mutation and elitism procedures are executed. This is iteratively repeated until the number of generations is reached.
In the Evolutionary Algorithm Playground, the following methods are implemented:
Selection:
- Roulette;
- Log Roulette: in this approach, the roulette probabilities are processed by a log function. It reduces the difference between the individual’s scores, enabling higher diversity to the population;
- Tournament;
Crossover:
- Single Point
Mutation:
- Single Point — Method A: this approach runs through every individual. It evaluates every bit of the individual and inverts it if a randomly generated number is larger the mutation probability (previously set by the user). This approach allows multiple mutations per individual;
- Single Point — Method B: in this approach, a number of individuals are selected. The number of individuals is the size of the population multiplied by the mutation probability (previously set by the user). Later, a randomly generated bit position is inverted;
Elitism:
A number of individuals (given by the size of the population multiplied by the elitism probability) will remain to the next generation. This is the most near-optimal individuals. The same number of individuals will be discarded. This is the less optimal individuals.
Particle Swarm Optimization
A population is built within the search interval (set by the user). Differently from the Genetic Algorithm, the population is continuous. It also considers the number of individuals and the dimension of the problem (both set by the user).
The individuals of the swarm-like population will be individually evaluated through the test function. After the evaluation, they will move according to the cognitive and social speeds. The speed is also influenced by an inertia weight (set by the user), which normally decreases through the evolutionary process. The cognitive speed is influenced by the Self Trust Parameter and the social speed is influenced by the Social Trust Parameter.
This is iteratively repeated until the number of generations is reached.
Individuals who scaped the maximum interval range are be clipped to the interval’s limits.
If you want to collaborate with the project, feel free to reach out.
Project Code:
My LinkedIn Profile:
[1] A.E. Eiben, James E Smith, Introduction to Evolutionary Computing (2003), Springer-Verlag Berlin Heidelberg
