genetic-algorithm

A simple implementation of a Genetic Algorithm (GA) written in C++. This project demonstrates how an optimization algorithm inspired by natural evolution can learn the parameters of a straight line by repeatedly evolving a population of candidate solutions.

The example learns the linear equation:

y = kx + b

from a small set of training data.

---

What is a Genetic Algorithm?

A Genetic Algorithm (GA) is a population-based optimization algorithm inspired by Charles Darwin's theory of natural selection.

Instead of using calculus or gradients, a Genetic Algorithm searches for good solutions through evolution.

Each candidate solution is treated as an individual (or chromosome). The population gradually improves over multiple generations by keeping the best individuals, combining their traits, and introducing small random mutations.

For a linear model:

y = kx + b

the chromosome contains:

• k = slope
• b = intercept

At each generation the algorithm:

1. Creates or maintains a population of candidate lines.
2. Measures how well each line fits the training data.
3. Selects the best-performing individuals.
4. Combines parents to create offspring (crossover).
5. Randomly mutates some offspring.
6. Repeats until the population converges to a good solution.

---

Example

Training data:

x	y
1	3
2	5
3	7
4	9
5	11
6	13

The hidden equation is:

y = 2x + 1

Initially, every individual starts with random values of

k
b

Most of these random lines fit the data poorly.

After many generations of selection, crossover, and mutation, the population gradually evolves toward

k ≈ 2
b ≈ 1

which perfectly fits the data.

---

Features

• Beginner-friendly implementation
• Demonstrates Genetic Algorithms step by step
• Evolves the slope and intercept of a line
• Uses tournament selection
• Uses crossover and mutation
• Includes elitism to preserve the best solution
• Prints training progress over multiple generations
• No external libraries required
• Well-commented and easy to understand

---

Project Structure

.
├── genetic_algorithm.cpp
└── README.md

---

Compilation

Compile using g++:

g++ genetic_algorithm.cpp -std=c++17 -O2 -o genetic_algorithm

Run the program.

Windows

genetic_algorithm.exe

Linux / macOS

./genetic_algorithm

---

Sample Output

Generation   1 | k = 1.7348 | b = 4.9182 | MSE = 18.5312
Generation  10 | k = 2.3246 | b = 0.2751 | MSE = 1.3725
Generation  20 | k = 2.0987 | b = 0.8421 | MSE = 0.1424
Generation  30 | k = 2.0184 | b = 0.9726 | MSE = 0.0058
Generation  40 | k = 2.0021 | b = 0.9984 | MSE = 0.0001

---------------------------------------
Final Best Line
---------------------------------------

y = 2.0000x + 1.0000

Mean Squared Error: 0.0000

---

How the Algorithm Works

1. Create a random population of candidate lines.
2. Measure the Mean Squared Error (MSE) for every individual.
3. Convert error into a fitness score.
4. Select the fittest individuals using tournament selection.
5. Generate children using crossover.
6. Apply random mutations.
7. Preserve the best individual (elitism).
8. Repeat for many generations.

---

Formula Used

Linear Model:

ŷ = kx + b

Mean Squared Error:

MSE = (1/n) Σ(ŷ - y)²

Fitness Function:

Fitness = 1 / (1 + MSE)

where

• k = slope
• b = intercept
• ŷ = predicted output
• y = actual output

Smaller error results in a higher fitness score, making an individual more likely to reproduce.

---

Evolution Process

 Random Population
        │
        ▼
 Evaluate Fitness
        │
        ▼
  Select Parents
        │
        ▼
    Crossover
        │
        ▼
     Mutation
        │
        ▼
 Next Generation
        │
        └───────────────┐
                        ▼
                     Repeat

Over many generations, the population gradually evolves better-fitting lines.

---

Advantages

• Does not require gradients or derivatives
• Can optimize non-differentiable objective functions
• Explores many candidate solutions simultaneously
• Less likely to become trapped in poor local solutions
• Applicable to many optimization problems

---

Limitations

• Usually slower than Gradient Descent
• Requires evaluating many candidate solutions
• No guarantee of finding the global optimum
• Performance depends on parameters such as population size and mutation rate

---

Common Applications

• Feature Selection
• Hyperparameter Optimization
• Neural Architecture Search
• Scheduling Problems
• Route Optimization
• Game AI
• Robotics
• Engineering Design
• Evolutionary Computing

---

Learning Objectives

This project demonstrates:

• Genetic Algorithms
• Evolutionary Computing
• Population-Based Optimization
• Fitness Functions
• Mean Squared Error (MSE)
• Tournament Selection
• Crossover
• Mutation
• Elitism
• Machine Learning Optimization

---

Requirements

• C++17 or later
• GCC / g++
• Any standard C++ compiler

---

License

This project is licensed under the MIT License.