Architecture‐Deep‐Dive - adylagad/CSCI-561_Genetic-Algorithm GitHub Wiki

Architecture Deep Dive

Complete technical overview of the codebase structure and design patterns.

🏗️ Project Structure


CSCI-561_Genetic-Algorithm/
│
├── main.py # Entry point
├── test_ga.py # Comprehensive test suite
│
├── genetic_algorithm/ # Main package
│ ├── **init**.py
│ │
│ ├── core/ # Core algorithm components
│ │ ├── **init**.py
│ │ ├── algorithm.py # Main GA orchestration
│ │ └── types.py # Type definitions
│ │
│ ├── operators/ # Genetic operators
│ │ ├── **init**.py
│ │ ├── crossover.py # Crossover strategies
│ │ ├── mutation.py # Mutation strategies
│ │ └── selection.py # Selection strategies
│ │
│ ├── initialization/ # Population initialization
│ │ ├── **init**.py
│ │ ├── random_init.py # Random initialization
│ │ └── nearest_neighbor.py # Nearest neighbor init
│ │
│ ├── evaluation/ # Fitness evaluation
│ │ ├── **init**.py
│ │ └── tsp_fitness.py # TSP-specific fitness
│ │
│ └── utils/ # Utility functions
│ ├── **init**.py
│ ├── distance.py # Distance calculations
│ └── io_utils.py # Input/Output
│
├── config/ # Configuration
│ ├── **init**.py
│ ├── ga_config.py # Configuration dataclass
│ └── default_config.json # Default parameters
│
└── input/ # Input files
└── input1.txt # 500 cities dataset

🎨 Design Patterns Used

1. Strategy Pattern

Where: Operators (crossover, mutation, selection)

Why: Easy to swap different algorithms without changing main code

Example:

# Instead of hard-coding one approach:
class GeneticAlgorithm:
    def crossover(self, parent1, parent2):
        # Fixed PMX crossover
        ...

# We use Strategy Pattern:
class GeneticAlgorithm:
    def __init__(self, crossover_strategy: CrossoverStrategy):
        self.crossover_strategy = crossover_strategy

    def crossover(self, parent1, parent2):
        return self.crossover_strategy.crossover(parent1, parent2)

# Now we can easily swap:
ga1 = GeneticAlgorithm(OrderCrossover())    # Use Order Crossover
ga2 = GeneticAlgorithm(PMXCrossover())      # Use PMX Crossover

Benefits:

Add new operators without modifying existing code (Open/Closed Principle)
Easy to A/B test different strategies
Clear separation of concerns

2. Dependency Injection

Where: Main algorithm class

Why: Loose coupling, easy testing, flexibility

Example:

# Dependencies injected via constructor:
def __init__(
    self,
    cities: CityList,
    fitness_evaluator: FitnessEvaluator,
    selection: SelectionStrategy,
    crossover: CrossoverStrategy,
    mutation: MutationStrategy,
    config: GAConfig
):
    # All dependencies provided externally
    ...

Benefits:

Easy to mock for testing
Clear dependencies
Flexibility in configuration

3. Factory Pattern (Implicit)

Where: Initialization strategies

Why: Create different types of initial populations

Example:

# Random initialization factory:
random_init = RandomPopulationInitializer(population_size)
population = random_init.initialize(cities)

# Nearest neighbor initialization factory:
nn_init = NearestNeighborInitializer(population_size)
population = nn_init.initialize(cities)

📦 Core Components

1. GeneticAlgorithm Class

Location: genetic_algorithm/core/algorithm.py

Responsibility: Orchestrate the evolutionary process

class GeneticAlgorithm:
    def run(self) -> GAResult:
        # 1. Initialize population
        population = self.initialize_population()

        # 2. Evolution loop
        for generation in range(self.generations):
            # 3. Evaluate fitness
            fitness = [self.evaluate(ind) for ind in population]

            # 4. Check convergence
            if self.has_converged():
                break

            # 5. Create next generation
            population = self.evolve(population, fitness)

        # 6. Return best solution
        return self.get_best_solution()

Key Methods:

Method	Purpose
`run()`	Main execution loop
`evolve()`	Create next generation
`evaluate()`	Calculate fitness
`has_converged()`	Check stopping criteria
`get_statistics()`	Collect metrics

2. Type System

Location: genetic_algorithm/core/types.py

Responsibility: Define core data types

# Type aliases for clarity:
City = Tuple[int, int, int]        # 3D coordinates
CityList = List[City]              # List of cities
Tour = List[int]                   # Tour as city indices
Population = List[Tour]            # List of tours
FitnessScores = List[float]        # List of fitness values

# Result type:
@dataclass
class GAResult:
    best_tour: Tour
    best_fitness: float
    best_cost: float
    statistics: Dict[str, Any]

Benefits:

Type checking catches errors early
Self-documenting code
Better IDE support

3. Configuration System

Location: config/ga_config.py

Responsibility: Manage algorithm parameters

@dataclass
class GAConfig:
    # Population parameters
    population_size: int = 500

    # Evolution parameters
    mutation_rate: float = 0.02
    number_of_generations: int = 3500

    # Convergence settings
    convergence_threshold: int = 500

    # I/O settings
    input_file: str = "input/input1.txt"

    @classmethod
    def from_json(cls, filepath: str) -> 'GAConfig':
        # Load from JSON file
        ...

Usage:

# Default config:
config = GAConfig()

# From JSON:
config = GAConfig.from_json("config/custom_config.json")

# Programmatic:
config = GAConfig(
    population_size=1000,
    mutation_rate=0.05
)

🔄 Data Flow

Complete Execution Flow

main.py
  │
  ├→ 1. Load config
  │    GAConfig.from_json()
  │
  ├→ 2. Read input
  │    read_input_file()
  │    └→ Returns: List[(x,y,z)]
  │
  ├→ 3. Initialize components
  │    ├→ FitnessEvaluator
  │    ├→ SelectionStrategy
  │    ├→ CrossoverStrategy
  │    ├→ MutationStrategy
  │    └→ PopulationInitializer
  │
  ├→ 4. Create GA
  │    GeneticAlgorithm(cities, operators, config)
  │
  ├→ 5. Run evolution
  │    ga.run()
  │    │
  │    ├→ Initialize population
  │    │    [random tours]
  │    │
  │    ├→ For each generation:
  │    │    │
  │    │    ├→ Evaluate fitness
  │    │    │    └→ fitness = 1 / tour_cost
  │    │    │
  │    │    ├→ Select parents
  │    │    │    └→ Roulette wheel selection
  │    │    │
  │    │    ├→ Crossover
  │    │    │    └→ Order crossover
  │    │    │
  │    │    ├→ Mutate
  │    │    │    └→ Swap mutation
  │    │    │
  │    │    └→ Elitism (keep best)
  │    │
  │    └→ Return GAResult
  │
  └→ 6. Display results
       format_output(result)

Data Transformations

Input File → Cities → Tours → Fitness → Selection → New Tours
   (I/O)    (Parse) (Init)   (Eval)     (Breed)     (Next Gen)

[Text]   → [(x,y,z)] → [0,1,2..](/adylagad/CSCI-561_Genetic-Algorithm/wiki/0,1,2..) → [0.001, ..] → [(p1,p2)] → [1,0,2..](/adylagad/CSCI-561_Genetic-Algorithm/wiki/1,0,2..)

🧩 Component Interactions

Initialization Phase

PopulationInitializer
         │
         ├→ Random Strategy
         │   └→ shuffle(range(num_cities))
         │
         └→ Nearest Neighbor Strategy
             └→ greedy construction from each city

Evolution Phase

Selection Strategy ──┐
                     ├→ Parent Pairs
Crossover Strategy ──┤
                     ├→ Offspring
Mutation Strategy ───┤
                     └→ Next Generation

Evaluation Phase

Tour [0,1,2,3...]
    │
    ├→ Distance Calculator
    │   └→ Σ distance(city[i], city[i+1])
    │
    └→ Fitness Calculator
        └→ 1 / total_distance

🎯 SOLID Principles

Single Responsibility Principle (SRP)

Each class has one job:

TSPFitnessEvaluator    → Only evaluates fitness
SwapMutation           → Only performs mutation
OrderCrossover         → Only does crossover
GeneticAlgorithm       → Only orchestrates

Open/Closed Principle (OCP)

Open for extension, closed for modification:

# Adding new crossover WITHOUT modifying existing code:

class CycleCrossover(CrossoverStrategy):
    def crossover(self, parent1: Tour, parent2: Tour) -> Tour:
        # New implementation
        ...

# Use it:
ga = GeneticAlgorithm(crossover=CycleCrossover())

Liskov Substitution Principle (LSP)

Any CrossoverStrategy can replace another:

def create_ga(crossover: CrossoverStrategy):
    return GeneticAlgorithm(crossover=crossover)

# All work identically:
ga1 = create_ga(OrderCrossover())
ga2 = create_ga(PMXCrossover())
ga3 = create_ga(CycleCrossover())  # Custom one

Interface Segregation Principle (ISP)

Small, focused interfaces:

class CrossoverStrategy(ABC):
    @abstractmethod
    def crossover(self, parent1: Tour, parent2: Tour) -> Tour:
        pass
    # Only one method - focused interface

class MutationStrategy(ABC):
    @abstractmethod
    def mutate(self, tour: Tour) -> Tour:
        pass
    # Separate interface for mutation

Dependency Inversion Principle (DIP)

Depend on abstractions, not concretions:

class GeneticAlgorithm:
    def __init__(
        self,
        crossover: CrossoverStrategy,  # Abstract
        mutation: MutationStrategy      # Abstract
    ):
        # Depends on interfaces, not concrete implementations

🧪 Testing Architecture

Location: test_ga.py

Structure:

class TestUtilityFunctions(unittest.TestCase):
    # Test distance, I/O functions

class TestTypes(unittest.TestCase):
    # Test type definitions

class TestConfiguration(unittest.TestCase):
    # Test GAConfig

class TestInitialization(unittest.TestCase):
    # Test RandomPopulationInitializer, NearestNeighborInitializer

class TestFitnessEvaluation(unittest.TestCase):
    # Test TSPFitnessEvaluator

class TestSelection(unittest.TestCase):
    # Test RouletteWheelSelection

class TestCrossover(unittest.TestCase):
    # Test OrderCrossover, PMXCrossover

class TestMutation(unittest.TestCase):
    # Test SwapMutation

class TestGeneticAlgorithm(unittest.TestCase):
    # Integration tests for GeneticAlgorithm

Coverage: 40+ tests covering all components

📊 Performance Considerations

Time Complexity

Component	Complexity	For 500 cities
Distance calc	O(1)	Constant
Fitness eval	O(n)	500 operations
Selection	O(p)	500 operations
Crossover	O(n)	500 operations
Mutation	O(1)	Constant
Generation	O(p·n)	250,000 ops
Full run	O(g·p·n)	~437M ops

Where:

n = cities (500)
p = population (500)
g = generations (3500)

Space Complexity

Component	Space	For 500 cities
City list	O(n)	1,500 ints
Population	O(p·n)	250,000 ints
Fitness	O(p)	500 floats
Total	O(p·n)	~1MB

Optimization Techniques

Elitism: Keep best solutions without re-evaluation
Caching: Store city distances (if needed)
Early stopping: Convergence detection
Vectorization: NumPy for batch operations (future)

🔍 Code Quality Measures

Type Safety

# Every function has type hints:
def crossover(self, parent1: Tour, parent2: Tour) -> Tour:
    ...

# Every variable has clear type:
cities: CityList = read_input_file(filename)
population: Population = initializer.initialize(cities)

Documentation

class OrderCrossover(CrossoverStrategy):
    """
    Order Crossover (OX) operator.

    Preserves relative order of cities from parents while avoiding
    duplicates. Well-suited for TSP.

    Algorithm:
        1. Select random substring from parent1
        2. Copy to offspring
        3. Fill remaining positions with parent2's order

    Example:
        parent1: [1,2,3,4,5]
        parent2: [5,4,3,2,1]
        offspring: [4,5,3,2,1] (preserves [3] from p1, order from p2)
    """

Error Handling

def read_input_file(filepath: str) -> CityList:
    if not os.path.exists(filepath):
        raise FileNotFoundError(f"Input file not found: {filepath}")

    try:
        # Read file
        ...
    except Exception as e:
        logger.error(f"Error reading file: {e}")
        raise

🚀 Extension Points

Adding New Crossover

# 1. Create new class:
class CycleCrossover(CrossoverStrategy):
    def crossover(self, parent1: Tour, parent2: Tour) -> Tour:
        # Implement cycle crossover
        ...

# 2. Use it:
crossover = CycleCrossover()
ga = GeneticAlgorithm(crossover=crossover, ...)

Adding New Initialization

# 1. Create new class:
class ChristofideInit(PopulationInitializer):
    def initialize(self, cities: CityList) -> Population:
        # Implement Christofides algorithm
        ...

# 2. Use it:
init = ChristofideInit(population_size=500)
population = init.initialize(cities)

Adding New Selection

# 1. Create new class:
class TournamentSelection(SelectionStrategy):
    def select(self, population: Population,
               fitness: FitnessScores) -> Tuple[Tour, Tour]:
        # Implement tournament selection
        ...

# 2. Use it:
selection = TournamentSelection(tournament_size=5)
ga = GeneticAlgorithm(selection=selection, ...)

📚 Further Reading

Custom Operators Tutorial - Create your own operators
API Reference - Complete API documentation
Performance Tuning - Optimization guide

Ready to extend? → Custom Operators Tutorial