shamonia/genetic_algorithm

This is an implementation of a genetic algorithm in Python. The genetic algorithm is a search algorithm that is inspired by the process of natural selection. It is used to solve optimization problems by iteratively improving a population of candidate solutions.

Fitness Function

The fitness function is used to evaluate the quality of a candidate solution. It takes an array of integers and floats as input, and can be defined with bounds for each input. In our implementation, we have used a simple fitness function that calculates the sum of the inputs.

Genetic Algorithm

The genetic algorithm works by iteratively improving a population of candidate solutions. Each candidate solution is represented by a chromosome, which is a sequence of bits. The genetic algorithm consists of the following steps:

1. Initialize the population: Create an initial population of candidate solutions by randomly generating chromosomes.
2. Evaluate the fitness of each candidate solution: Use the fitness function to evaluate the quality of each candidate solution.
3. Select parents for mating: Use tournament selection to select two parents for mating.
4. Create offspring through crossover: Use two-point crossover to create two offspring from the parents.
5. Mutate the offspring: Introduce random mutations to the offspring.
6. Add the offspring to the new population: Add the offspring to the new population of candidate solutions.
7. Replace the old population with the new population: Replace the old population with the new population of candidate solutions.
8. Repeat steps 2-7 for a fixed number of generations.

Implementation Details

In our implementation, we have used the following parameters:

POPULATION_SIZE: The number of candidate solutions in each generation.

1. MIN_CHROMOSOME_LENGTH: The minimum length of a chromosome.
2. MAX_CHROMOSOME_LENGTH: The maximum length of a chromosome.
3. TOURNAMENT_SIZE: The number of candidate solutions to consider in each tournament selection.
4. MUTATION_RATE: The probability of introducing a random mutation to a bit in a chromosome.
5. MUTATION_RATE_INCREASE: The amount by which to increase the mutation rate after each generation.
6. NUM_GENERATIONS: The number of generations to run the genetic algorithm for. We have also defined the following functions:

fitness: The fitness function that evaluates the quality of a candidate solution. tournament_selection: The function that performs tournament selection to select parents for mating. two_point_crossover: The function that performs two-point crossover to create offspring from parents. mutation: The function that introduces random mutations to offspring.

Usage

To run the genetic algorithm, simply run the following command in the terminal:

python GA.py

This will run the genetic algorithm with the default parameters. If you want to change the parameters, you can modify the variables at the top of the genetic_algorithm.py file.

Conclusion

The genetic algorithm is a powerful optimization algorithm that can be used to solve a wide range of problems. In this implementation, we have shown how to use the genetic algorithm to solve an optimization problem with bounds on the inputs. This implementation can be easily extended to solve other optimization problems by defining a suitable fitness function.