Create a genetic algorithm in Python to solve the problem of finding the largest shape…
- User
Create a genetic algorithm in Python to solve the problem of finding the largest shape that can be made from a single 1 metre line.
- Assistant
Certainly! Let's tackle the problem of finding the largest shape (in terms of area) that can be made from a single 1-meter line using a Genetic Algorithm (GA) in Python.
Problem Definition
Given a fixed perimeter of 1 meter, we aim to find the shape that maximizes the enclosed area. According to the isoperimetric theorem, among all shapes with a given perimeter, the circle has the largest area. However, since we're aiming to solve this using a GA, we'll explore discrete approximations (like polygons) to approach this optimal solution.
Approach
-
Representation (Chromosome):
- We'll represent each shape as a polygon with a fixed number of vertices (e.g., 20 vertices for a 20-sided polygon).
- Each vertex can be defined by an angle or coordinates, but to simplify, we'll use angular increments to define the shape.
-
Constraints:
- The sum of the edge lengths must equal 1 meter.
- The polygon must be closed (vertices connect back to the starting point).
-
Fitness Function:
- The fitness of a shape is its area. Our goal is to maximize this area.
-
Genetic Operations:
- Selection: Choose the top-performing individuals based on fitness.
- Crossover: Combine parts of two parent shapes to produce offspring.
- Mutation: Introduce small random changes to shapes to maintain genetic diversity.
Implementation
Below is a Python implementation of the Genetic Algorithm to solve this problem. We'll use libraries like
numpyfor numerical operations andmatplotlibfor visualization.import numpy as np import matplotlib.pyplot as plt from matplotlib.patches import Polygon import random # Genetic Algorithm Parameters POPULATION_SIZE = 100 GENERATIONS = 500 MUTATION_RATE = 0.01 NUM_VERTICES = 20 # Number of vertices in the polygon # Helper Functions def generate_initial_population(): population = [] for _ in range(POPULATION_SIZE): # Random angles between 0 and 2*pi, sorted to ensure convexity angles = np.sort(np.random.uniform(0, 2 * np.pi, NUM_VERTICES)) # Random radii, normalized to have perimeter 1 radii = np.random.uniform(0.1, 1.0, NUM_VERTICES) shape = np.column_stack((radii * np.cos(angles), radii * np.sin(angles))) population.append(shape) return population def calculate_perimeter(shape): perimeter = 0 for i in range(len(shape)): perimeter += np.linalg.norm(shape[i] - shape[i - 1]) return perimeter def normalize_shape(shape): perimeter = calculate_perimeter(shape) if perimeter == 0: return shape return shape / perimeter def calculate_area(shape): # Using Shoelace formula x = shape[:, 0] y = shape[:, 1] return 0.5 * np.abs(np.dot(x, np.roll(y, 1)) - np.dot(y, np.roll(x, 1))) def fitness(shape): return calculate_area(shape) def selection(population): # Sort population based on fitness (descending) sorted_population = sorted(population, key=lambda x: fitness(x), reverse=True) # Select top 50% return sorted_population[:POPULATION_SIZE // 2] def crossover(parent1, parent2): # Single point crossover point = random.randint(1, NUM_VERTICES - 1) child1 = np.vstack((parent1[:point], parent2[point:])) child2 = np.vstack((parent2[:point], parent1[point:])) return child1, child2 def mutate(shape): for i in range(NUM_VERTICES): if random.random() < MUTATION_RATE: # Small perturbation delta_radius = np.random.normal(0, 0.05) delta_angle = np.random.normal(0, 0.1) r = np.linalg.norm(shape[i]) theta = np.arctan2(shape[i,1], shape[i,0]) r = max(0.1, r + delta_radius) theta = (theta + delta_angle) % (2 * np.pi) shape[i] = [r * np.cos(theta), r * np.sin(theta)] return shape def create_next_generation(selected_population): next_generation = selected_population.copy() while len(next_generation) < POPULATION_SIZE: parent1, parent2 = random.sample(selected_population, 2) child1, child2 = crossover(parent1, parent2) child1 = mutate(child1) child2 = mutate(child2) child1 = normalize_shape(child1) child2 = normalize_shape(child2) next_generation.extend([child1, child2]) return next_generation[:POPULATION_SIZE] def genetic_algorithm(): population = generate_initial_population() best_shape = None best_fitness = -1 fitness_history = [] for generation in range(GENERATIONS): # Normalize all shapes population = [normalize_shape(shape) for shape in population] # Evaluate fitness fitness_values = [fitness(shape) for shape in population] generation_best_fitness = max(fitness_values) generation_best_shape = population[np.argmax(fitness_values)] if generation_best_fitness > best_fitness: best_fitness = generation_best_fitness best_shape = generation_best_shape fitness_history.append(best_fitness) print(f"Generation {generation + 1}: Best Fitness = {best_fitness:.6f}") # Selection selected = selection(population) # Create next generation population = create_next_generation(selected) return best_shape, fitness_history def plot_shape(shape, title="Best Shape"): plt.figure(figsize=(6,6)) polygon = Polygon(shape, closed=True, fill=True, edgecolor='r', alpha=0.5) plt.gca().add_patch(polygon) plt.xlim(-1.5, 1.5) plt.ylim(-1.5, 1.5) plt.gca().set_aspect('equal', adjustable='box') plt.title(title) plt.show() def plot_fitness_history(fitness_history): plt.figure(figsize=(10,5)) plt.plot(fitness_history) plt.xlabel('Generation') plt.ylabel('Best Fitness (Area)') plt.title('Fitness Evolution') plt.grid(True) plt.show() # Run the Genetic Algorithm best_shape, fitness_history = genetic_algorithm() # Plot the best shape plot_shape(best_shape, title=f"Best Shape with Area: {best_fitness:.6f}") # Plot fitness history plot_fitness_history(fitness_history)Explanation
-
Initialization:
- We generate an initial population of random shapes (polygons) with a specified number of vertices.
- Each shape is represented by its (x, y) coordinates.
-
Perimeter Normalization:
- Each shape's perimeter is calculated, and the shape is normalized so that its perimeter is exactly 1 meter.
-
Fitness Calculation:
- The fitness of each shape is its area, calculated using the Shoelace formula.
-
Selection:
- We select the top 50% of the population based on fitness to be parents for the next generation.
-
Crossover:
- We perform single-point crossover between pairs of parents to produce offspring.
-
Mutation:
- Each vertex of the offspring has a small chance to mutate by slightly changing its radius and angle.
-
Next Generation:
- The next generation is created by combining the selected parents and the newly generated offspring until the population size is maintained.
-
Termination:
- The algorithm runs for a predefined number of generations, keeping track of the best shape found.
-
Visualization:
- The best shape and the evolution of fitness over generations are plotted for analysis.
Notes and Improvements
- Shape Representation: The current implementation uses polar coordinates (radius and angle) for vertices. Depending on the desired complexity, more sophisticated representations (like angles between vertices) can be used.
- Convexity: The algorithm does not enforce convexity, which may lead to self-intersecting polygons. Ensuring convex shapes can be an improvement.
- Adaptive Parameters: Parameters like mutation rate, population size, and number of vertices can be tuned or made adaptive based on performance.
- Termination Criteria: Instead of a fixed number of generations, the algorithm can terminate when improvement falls below a threshold.
Running the Code
To run the code:
-
Ensure you have Python installed (preferably version 3.6 or higher).
-
Install necessary libraries if you haven't already:
pip install numpy matplotlib -
Save the code to a file, e.g.,
genetic_algorithm_shape.py. -
Run the script:
python genetic_algorithm_shape.py
You should see the evolution of the fitness over generations and the visualization of the best shape found by the algorithm.
Conclusion
This Genetic Algorithm provides a method to approximate the optimal shape with the largest area for a given perimeter by evolving a population of candidate shapes over successive generations. While the circle is mathematically the optimal shape, GAs offer flexibility to explore and approximate solutions in more complex or constrained scenarios where analytical solutions might not be straightforward.
-