import random import matplotlib.pyplot as plt import math
goal = (15, 15)
population_size = 20 # Number of individuals in the population num_generations = 50 # Number of generations to run the algorithm mutation_rate = 0.2 # Probability of mutation
def initialize_population(): """ Initialize the population with random positions within a 20x20 grid. Each individual is represented as a tuple (x, y) where x and y are float values. """ return [(random.uniform(0, 20), random.uniform(0, 20)) for _ in range(population_size)]
def fitness_function(position): """ Fitness function that calculates the negative distance to the goal. A negative value is returned because we are minimizing the distance to the goal.
Args:
position (tuple): A tuple representing the position (x, y).
Returns:
float: The negative distance to the goal.
"""
x, y = position
return -math.sqrt((x - goal[0])**2 + (y - goal[1])**2) # Negative because closer is better
def select_parents(population, fitness): """ Select two parents from the population using roulette wheel selection based on their fitness.
Args:
population (list): The list of individuals in the population.
fitness (list): The list of fitness values corresponding to the population.
Returns:
tuple: A tuple containing two selected parents.
"""
total_fitness = sum(fitness)
probabilities = [f / total_fitness for f in fitness]
parents = random.choices(population, weights=probabilities, k=2)
return parents
def crossover(parent1, parent2): """ Perform crossover between two parents to create a child. The crossover here is the average of the x and y coordinates of the parents.
Args:
parent1 (tuple): The first parent position (x, y).
parent2 (tuple): The second parent position (x, y).
Returns:
tuple: The child position (x, y) generated by crossover.
"""
x1, y1 = parent1
x2, y2 = parent2
child_x = (x1 + x2) / 2
child_y = (y1 + y2) / 2
return (child_x, child_y)
def mutate(position): """ Perform mutation on an individual by making small random changes to its position.
Args:
position (tuple): The individual position (x, y).
Returns:
tuple: The mutated position (x, y).
"""
if random.random() < mutation_rate:
x, y = position
x += random.uniform(-1, 1) # Small random change in x
y += random.uniform(-1, 1) # Small random change in y
x = max(0, min(x, 20)) # Ensure the position stays within bounds
y = max(0, min(y, 20)) # Ensure the position stays within bounds
return (x, y)
return position
def genetic_algorithm(): """ Run the genetic algorithm to find the optimal path to the goal. It evolves a population over multiple generations using selection, crossover, and mutation. """ population = initialize_population() best_path = []
for generation in range(num_generations):
fitness = [fitness_function(individual) for individual in population]
best_individual = population[fitness.index(max(fitness))] # Get the best individual
best_path.append(best_individual)
print(f"Generation {generation + 1}: Best Fitness = {max(fitness):.2f}")
# Create next generation
new_population = []
for _ in range(population_size // 2): # Select parents and create children
parent1, parent2 = select_parents(population, fitness)
child1 = mutate(crossover(parent1, parent2))
child2 = mutate(crossover(parent2, parent1))
new_population.extend([child1, child2])
population = new_population
# After all generations, plot the best path
plot_path(best_path)
def plot_path(path): """ Plot the path followed by the robot as it evolves towards the goal.
Args:
path (list): A list of positions representing the path taken by the robot.
"""
x_vals, y_vals = zip(*path)
plt.figure(figsize=(8, 8))
plt.plot(x_vals, y_vals, marker="o", label="Path")
plt.scatter(*goal, color="red", label="Goal")
plt.xlim(0, 20)
plt.ylim(0, 20)
plt.title("Robot Path to Goal")
plt.xlabel("X")
plt.ylabel("Y")
plt.legend()
plt.grid()
plt.show()
if name == "main": genetic_algorithm() # Run the genetic algorithm to find the path