A simple Python library for solving optimization problems using metaheuristic algorithms. This library provides clean and modular implementations of popular metaheuristics with built-in support for common optimization problems and rich visualization capabilities. The project was crated as a tutorial for undergrad students on metaheuristic algorithms and good programming practices.
- Multiple Algorithms: Implementations of Hill Climbing, Simulated Annealing, Genetic Algorithm, Particle Swarm Optimization, and Tabu Search
- Diverse Problems: Built-in support for Travelling Salesman Problem (TSP), Knapsack, Job Scheduling, and continuous function optimization
- Extensible Architecture: Abstract base classes make it easy to add new algorithms and problems
- Rich Visualizations: Convergence plots, population dynamics, algorithm comparisons, and solution animations
- CSV Data Support: Load and save problem instances in a consistent CSV format
- Performance Tracking: Detailed history tracking with iteration times, fitness evolution, and custom metrics
This project uses uv for dependency management. To get started:
# Clone the repository
git clone https://github.com/yourusername/metaheuristics.git
cd metaheuristics
# Install dependencies (requires Python 3.12+)
uv sync
# Activate the virtual environment
source .venv/bin/activate # Linux/macOS
# or
.venv\Scripts\activate # Windows- Python >= 3.12
- NumPy >= 2.3.4
- Matplotlib (for visualizations)
from algorithms.genetic_algorithm import GeneticAlgorithm
from problems.function_optimization import get_function
from visualization.convergence_plot import ConvergencePlot
# 1. Define the problem
problem = get_function('rastrigin', dimensions=10)
# 2. Create the algorithm
ga = GeneticAlgorithm(
problem=problem,
max_iterations=100,
population_size=50,
crossover_rate=0.8,
mutation_rate=0.1,
random_seed=42,
verbose=True
)
# 3. Run optimization
best_solution, best_fitness = ga.run()
print(f"Best fitness: {best_fitness}")
print(f"Best solution: {best_solution}")
# 4. Visualize results
viz = ConvergencePlot()
viz.visualize(ga.get_history())
viz.show()All algorithms inherit from MetaheuristicAlgorithm base class and share a common interface.
Simple local search algorithm that iteratively moves to better neighboring solutions.
from algorithms.hill_climbing import HillClimbing
hc = HillClimbing(problem, max_iterations=1000, step_size=0.1)
best_solution, best_fitness = hc.run()Probabilistic technique that accepts worse solutions early to escape local optima.
from algorithms.simulated_annealing import SimulatedAnnealing
sa = SimulatedAnnealing(
problem,
max_iterations=1000,
initial_temperature=100.0,
cooling_rate=0.95
)
best_solution, best_fitness = sa.run()Evolution-inspired algorithm using selection, crossover, and mutation.
from algorithms.genetic_algorithm import GeneticAlgorithm
ga = GeneticAlgorithm(
problem,
max_iterations=100,
population_size=50,
crossover_rate=0.8,
mutation_rate=0.1
)
best_solution, best_fitness = ga.run()Swarm intelligence algorithm where particles explore the solution space.
from algorithms.particle_swarm import ParticleSwarmOptimization
pso = ParticleSwarmOptimization(
problem,
max_iterations=100,
swarm_size=30,
inertia_weight=0.7,
cognitive_param=1.5,
social_param=1.5
)
best_solution, best_fitness = pso.run()Local search enhanced with memory structures to avoid revisiting solutions.
from algorithms.tabu_search import TabuSearch
ts = TabuSearch(
problem,
max_iterations=1000,
tabu_tenure=10,
neighborhood_size=20
)
best_solution, best_fitness = ts.run()from problems.tsp import TSPProblem, create_random_instance
# From coordinates
problem = TSPProblem.from_coordinates([
(0, 0), (1, 2), (3, 1), (2, 3)
])
# From CSV file
problem = TSPProblem.from_file('data/tsp_instances/small_cities.csv')
# Random instance
problem = create_random_instance(n_cities=30, seed=42)from problems.knapsack import KnapsackProblem, create_random_instance
# From arrays
problem = KnapsackProblem(
values=[15, 20, 30],
weights=[10, 15, 25],
capacity=40
)
# From CSV file
problem = KnapsackProblem.from_file('data/knapsack_instances/medium_instance.csv')
# Random instance
problem = create_random_instance(n_items=50, capacity_ratio=0.5, seed=42)from problems.scheduling import JobShopProblem, create_random_instance
# Define jobs: [(machine_id, processing_time), ...]
jobs = [
[(0, 10), (1, 8), (2, 5)], # Job 0
[(1, 12), (0, 6), (2, 9)], # Job 1
[(2, 7), (1, 5), (0, 4)] # Job 2
]
problem = JobShopProblem(jobs)
# Random instance
problem = create_random_instance(n_jobs=10, n_machines=5, seed=42)
# Get detailed schedule information
solution = problem.random_solution()
info = problem.get_solution_info(solution)
print(f"Makespan: {info['makespan']}")
print(f"Utilization: {info['utilization']:.2%}")See docs/SCHEDULING.md for detailed scheduling documentation.
Classic continuous optimization benchmark functions.
from problems.function_optimization import get_function
# Available functions: sphere, rastrigin, rosenbrock, ackley, griewank, schwefel
problem = get_function('rastrigin', dimensions=10, bounds=(-5.12, 5.12))Available benchmark functions:
- Sphere: Unimodal, convex (optimum: 0)
- Rastrigin: Highly multimodal (optimum: 0)
- Rosenbrock: Narrow valley (optimum: 0)
- Ackley: Many local optima (optimum: 0)
- Griewank: Multimodal (optimum: 0)
- Schwefel: Deceptive (optimum: 0)
from visualization.convergence_plot import ConvergencePlot
viz = ConvergencePlot(figsize=(10, 6))
viz.visualize(algorithm.get_history())
viz.show()from visualization.comparison_plot import compare_algorithms
histories = [ga.get_history(), pso.get_history(), sa.get_history()]
labels = ['Genetic Algorithm', 'PSO', 'Simulated Annealing']
compare_algorithms(
histories,
labels,
comparison_type='all', # Options: 'convergence', 'final', 'time', 'all'
save_path='comparison.png'
)from visualization.population_plot import PopulationPlot
# For population-based algorithms (GA, PSO)
viz = PopulationPlot()
viz.visualize(ga.get_history(), plot_type='diversity')
viz.show()from visualization.solution_animation import SolutionAnimation
# Animate optimization progress
anim = SolutionAnimation(problem, interval=100)
anim.create_animation(algorithm.get_history())
anim.save('optimization.gif')Here's a complete example comparing multiple algorithms on the TSP:
from problems.tsp import create_random_instance
from algorithms.genetic_algorithm import GeneticAlgorithm
from algorithms.particle_swarm import ParticleSwarmOptimization
from algorithms.simulated_annealing import SimulatedAnnealing
from visualization.comparison_plot import compare_algorithms
# Create problem
problem = create_random_instance(n_cities=20, seed=42)
# Configure algorithms
algorithms = {
'GA': GeneticAlgorithm(
problem, max_iterations=200, population_size=50,
crossover_rate=0.8, mutation_rate=0.1, random_seed=42
),
'PSO': ParticleSwarmOptimization(
problem, max_iterations=200, swarm_size=30,
inertia_weight=0.7, random_seed=42
),
'SA': SimulatedAnnealing(
problem, max_iterations=200, initial_temperature=100.0,
cooling_rate=0.95, random_seed=42
)
}
# Run all algorithms
results = {}
for name, algo in algorithms.items():
print(f"\nRunning {name}...")
solution, fitness = algo.run()
results[name] = {
'solution': solution,
'fitness': fitness,
'history': algo.get_history()
}
print(f"{name} - Best fitness: {fitness:.4f}")
# Compare results
compare_algorithms(
[results[name]['history'] for name in ['GA', 'PSO', 'SA']],
['GA', 'PSO', 'SA'],
comparison_type='all',
save_path='tsp_comparison.png'
)metaheuristics/
├── algorithms/ # Metaheuristic algorithm implementations
│ ├── base.py # Abstract base class for algorithms
│ ├── hill_climbing.py
│ ├── simulated_annealing.py
│ ├── genetic_algorithm.py
│ ├── particle_swarm.py
│ └── tabu_search.py
├── problems/ # Optimization problem definitions
│ ├── base.py # Abstract base class for problems
│ ├── tsp.py # Traveling Salesman Problem
│ ├── knapsack.py # 0-1 Knapsack Problem
│ ├── scheduling.py # Job Shop Scheduling Problem
│ └── function_optimization.py # Continuous benchmark functions
├── visualization/ # Plotting and animation tools
│ ├── base.py # Base visualizer class
│ ├── convergence_plot.py
│ ├── comparison_plot.py
│ ├── population_plot.py
│ └── solution_animation.py
├── utils/ # Utility functions
│ ├── helpers.py # General helper functions
│ ├── metrics.py # Performance metrics
│ └── data_loader.py # CSV data loading/saving
├── data/ # Problem instance data files (CSV)
│ ├── knapsack_instances/
│ ├── tsp_instances/
│ └── README.md # Data format documentation
├── examples/ # Usage examples
│ └── scheduling_example.py
├── notebooks/ # Jupyter notebooks for experiments
├── docs/ # Additional documentation
│ └── SCHEDULING.md # Job Shop Scheduling guide
├── solutions/ # Saved solutions
└── main.py # Entry point
To create a new algorithm, extend the MetaheuristicAlgorithm base class:
from algorithms.base import MetaheuristicAlgorithm
import numpy as np
class MyAlgorithm(MetaheuristicAlgorithm):
def __init__(self, problem, max_iterations=1000, **kwargs):
super().__init__(problem, max_iterations, **kwargs)
self.my_param = kwargs.get('my_param', 1.0)
def initialize(self):
"""Initialize algorithm state."""
self.current_solution = self.problem.random_solution()
self.current_fitness = self.problem.evaluate(self.current_solution)
self.update_best(self.current_solution, self.current_fitness)
def step(self):
"""Perform one iteration."""
# Your optimization logic here
new_solution = self._generate_neighbor(self.current_solution)
new_fitness = self.problem.evaluate(new_solution)
if new_fitness < self.current_fitness: # For minimization
self.current_solution = new_solution
self.current_fitness = new_fitness
self.update_best(new_solution, new_fitness)
# Log iteration data
self.log_iteration(current_fitness=self.current_fitness)
def _generate_neighbor(self, solution):
"""Generate a neighboring solution."""
# Implementation depends on your algorithm
passTo create a new problem, extend the OptimizationProblem base class:
from problems.base import OptimizationProblem
import numpy as np
class MyProblem(OptimizationProblem):
def __init__(self, **kwargs):
super().__init__(name="My Problem", minimize=True)
# Your problem-specific initialization
self.bounds = (-10, 10) # For continuous problems
def evaluate(self, solution):
"""Evaluate fitness of a solution."""
# Return the objective function value
return np.sum(solution ** 2) # Example: sphere function
def random_solution(self):
"""Generate a random valid solution."""
return np.random.uniform(self.bounds[0], self.bounds[1], size=10)
def is_valid(self, solution):
"""Check if solution is valid."""
# Check constraints
return np.all(solution >= self.bounds[0]) and np.all(solution <= self.bounds[1])This library uses CSV format for all data files. See data/README.md for detailed format specifications.
Contributions are welcome! Please feel free to submit a Pull Request. For major changes, please open an issue first to discuss what you would like to change.
# Clone the repository
git clone https://github.com/yourusername/metaheuristics.git
cd metaheuristics
# Install dependencies
uv sync
# Run examples
python examples/scheduling_example.pyThis project is open source and available under the MIT License.
- Gendreau, M., & Potvin, J. Y. (Eds.). (2010). Handbook of metaheuristics. Springer.
- Luke, S. (2013). Essentials of metaheuristics. Lulu.
- Talbi, E. G. (2009). Metaheuristics: from design to implementation. John Wiley & Sons.
This library implements well-established metaheuristic algorithms from the optimization research community. It is designed for educational purposes, research, and practical optimization tasks.
Author: Barbara Klaudel Version: 0.1.0 Python: >= 3.12