A Genetic Algorithm (GA) implementation that evolves action sequences capable of solving simplified 2D Mario levels. Instead of searching for a path directly, the algorithm evolves chromosomes representing Mario's movement decisions and optimizes them using evolutionary operators until a playable solution emerges.
This project demonstrates how evolutionary computation can solve sequential decision-making problems through population-based optimization, fitness-driven selection, crossover, and mutation.
The objective is to evolve an agent that reaches the end of a Mario level while avoiding enemies, collecting rewards, and maximizing its fitness.
Each chromosome represents a sequence of Mario actions. Through multiple generations, the population gradually improves until individuals consistently complete the level or converge to high-quality solutions.
The implementation includes:
- Population initialization.
- Fitness evaluation based on game progress and rewards.
- Weighted parent selection.
- Genetic crossover.
- Mutation with configurable probability.
- Iterative evolution until convergence.
The environment is a simplified side-scrolling Mario game where Mario always progresses toward the right side of the map.
| Symbol | Description |
|---|---|
_ |
Empty ground |
G |
Goomba (ground enemy) |
L |
Lakitu (air enemy) |
M |
Mushroom (bonus reward) |
Mario starts at the leftmost tile and the goal is to reach the rightmost tile.
Each gene stores one action.
| Gene | Action |
|---|---|
0 |
Move right |
1 |
Jump while moving right |
2 |
Duck while moving right |
A chromosome is therefore a fixed-length string of actions, for example:
001101201001...
This chromosome completely defines Mario's behavior inside one level.
Initial Population
│
▼
Fitness Evaluation
│
▼
Parent Selection
│
▼
Crossover
│
▼
Mutation
│
▼
Next Generation
│
▼
Termination Check
The algorithm continuously evolves populations until a stopping criterion is satisfied.
A population of randomly generated chromosomes is created.
Each chromosome has:
- Fixed chromosome length.
- Random action encoding.
- Independent initialization.
The population size is configurable, allowing experimentation with different evolutionary settings.
Fitness measures how successful a chromosome is inside the Mario environment.
The evaluation rewards:
- Progress toward the goal.
- Successfully finishing the level.
- Collecting mushrooms.
- Efficient movement.
The evaluation penalizes:
- Dying early.
- Unnecessary jumps.
- Inefficient behavior.
Conceptually,
Fitness =
Progress Reward
+ Finish Bonus
+ Mushroom Bonus
- Jump Penalty
This encourages chromosomes that are both successful and efficient.
Individuals are selected according to their fitness scores.
Higher-fitness chromosomes have a greater probability of producing offspring, preserving stronger genetic material while maintaining diversity within the population.
Selected parents exchange genetic information to generate offspring.
The crossover operator combines action sequences from both parents into new chromosomes capable of inheriting successful behaviors from multiple solutions.
Mutation randomly modifies genes with a configurable probability.
Examples include changing:
0 → 1
1 → 2
2 → 0
Mutation prevents premature convergence and helps the population explore new regions of the search space.
Evolution stops when one of the following conditions is met:
- A chromosome successfully solves the level.
- Fitness improvement converges.
- Maximum number of generations is reached.
The fitness function is designed to balance exploration and exploitation.
Rewards
- Reaching farther positions.
- Completing the level.
- Collecting mushrooms.
Penalties
- Dying before reaching the goal.
- Excessive jumping.
- Inefficient action sequences.
This reward structure produces chromosomes that solve levels using fewer unnecessary actions.
evolutionary-algorithm/
│
├── attachments/ # Game environment and helper classes
├── levels/ # Mario level definitions (.txt)
├── outputs/ # Generated plots and experiment results
├── main.py # Evolutionary algorithm entry point
├── game.py # Mario simulator and fitness evaluation
├── genetic_algorithm.py # GA operators
├── utils.py # Utility functions
└── README.md
Folder names may vary slightly depending on the repository version.
git clone https://github.com/alirezas9/evolutionary-algorithm.git
cd evolutionary-algorithmpip install -r requirements.txtpython main.pyThe algorithm evolves populations and reports the best chromosome together with its fitness score.
Typical configurable hyperparameters include:
| Hyperparameter | Purpose |
|---|---|
| Population Size | Number of chromosomes in each generation |
| Chromosome Length | Number of actions per chromosome |
| Mutation Rate | Probability of mutating a gene |
| Crossover Rate | Probability of crossover |
| Maximum Generations | Evolution budget |
| Elitism | Preserve top-performing individuals |
These parameters can be tuned to study convergence behavior and solution quality.
The implementation allows comparing different evolutionary strategies by measuring convergence across generations.
Possible experiments include:
- Population size comparison.
- Mutation rate sensitivity.
- Crossover strategy comparison.
- Elitism vs. non-elitism.
- Fitness evolution over generations.
Typical metrics:
- Best fitness.
- Average fitness.
- Success rate.
- Number of generations until convergence.
The project can visualize evolutionary progress by plotting fitness over generations.
- Best fitness.
- Mean population fitness.
- Convergence behavior.
These plots help analyze optimization dynamics and detect premature convergence or stagnation.
| Gene Sequence |
|---|
00110120100112010120... |
The chromosome is executed sequentially inside the Mario simulator until Mario either reaches the goal or loses.
- Evolutionary Algorithms
- Genetic Algorithms
- Population-Based Optimization
- Fitness Engineering
- Selection Strategies
- Crossover Operators
- Mutation Operators
- Convergence Analysis
- Python
- Object-Oriented Programming
- NumPy
- Matplotlib (for convergence visualization)
- Adaptive mutation rates.
- Multi-point crossover operators.
- Tournament and rank-based selection.
- Dynamic chromosome lengths.
- Procedural Mario level generation.
- Reinforcement Learning hybrid initialization.
- Parallel fitness evaluation for faster evolution.
- Genetic Algorithm implemented from scratch.
- Configurable evolutionary operators and hyperparameters.
- Modular fitness evaluation through a Mario game simulator.
- Suitable for experimentation with evolutionary optimization techniques.
This repository is intended for educational and research purposes.