Dots Simulation using Genetic Algorithm - Part 1

This blog post details a captivating project using a genetic algorithm (GA) to simulate dots navigating toward a target while avoiding obstacles. The GA mimics natural selection, iteratively improving a population of dots based on their proximity to the target.

Genetic Algorithm Implementation:

The GA follows these standard steps:

1. Initialization: Randomly generates an initial population of dots.
2. Evaluation: A fitness function assesses each dot's performance based on its distance from the target.
3. Selection: The fittest dots are chosen as parents for the next generation.
4. Crossover: Genetic information (movement directions) from two parents is combined to create offspring. (Note: This project initially uses replication for simplicity; crossover will be added later.)
5. Mutation: Minor random changes are introduced into offspring's movement directions to maintain diversity.
6. Replacement: The previous generation is replaced with the offspring.
7. Elitism: The best-performing dots from the previous generation are preserved in the next generation.
8. Iteration: Steps 2-7 are repeated for a specified number of generations.

Simulation Overview:

The simulation visualizes a population of dots evolving to reach a red square target. Each dot's movement is determined by its "genes" (a sequence of movement directions). Through selection, mutation, and replication, the population adapts, improving its ability to reach the target while navigating around black rectangular obstacles.

Key Simulation Components:

1. Dots: Agents with movement directions (chromosomes) and a fitness score based on target proximity.
2. Fitness Function: Calculates fitness based on distance to the target, rewarding shorter paths.
3. Population: A collection of dots evolving over generations.
4. Genetic Algorithm: Drives the evolutionary process, selecting fit individuals and introducing variation.
5. Obstacles: Black rectangles challenging the dots' navigation.
6. Goal: A red square target that the dots aim to reach.

Project Setup (Python with Pygame):

The project uses Pygame for visualization. Key global variables control the simulation's parameters (population size, mutation rate, etc.). A Dot class represents individual dots, managing their position, movement, and fitness.

Initial Simulation (Single Dot):

The initial code simulates a single dot moving randomly until it exits the screen boundaries. This serves as a foundational step before introducing a population and the GA.

Population Simulation:

A Population class manages the group of dots. The update method moves the dots and checks for collisions with obstacles. The simulation now displays multiple dots moving simultaneously.

Adding Obstacles and the Goal:

Obstacle and Goal classes are introduced to represent obstacles and the target, respectively. Collision detection is implemented, causing dots to "die" upon collision. The simulation now includes a red target square and a black rectangular obstacle.

Implementing the Genetic Algorithm (Replication):

The get_fitness method in the Dot class calculates fitness. The Population class gains generate_next_generation and select_best_dots methods to implement selection, replication (initially instead of crossover), mutation, and elitism. The simulation now shows the population evolving over generations.

Future Enhancements:

Future blog posts will cover:

• Distinguishing elite dots visually.
• Adding more complex obstacles.
• Implementing crossover for more sophisticated offspring generation.
• Displaying a "Reached" message when a dot reaches the target.

The complete code (up to this point) is available on GitHub. Experiment with the code and share your findings! Join the AICraftsLab Discord community to connect with other AI enthusiasts.

The above is the detailed content of Dots Simulation using Genetic Algorithm - Part 1. For more information, please follow other related articles on the PHP Chinese website!