Common questions and answers about the GA TSP Solver.

A professional genetic algorithm framework for solving the Traveling Salesman Problem. Built with software engineering best practices for learning and experimentation.

An optimization technique inspired by evolution. It creates a "population" of solutions that evolve over generations to find better solutions. See GA Explained for details.

The Traveling Salesman Problem asks: "What's the shortest route visiting all cities exactly once?" See TSP Overview.

No! This is a completely refactored version created after the assignment. The original submission was a simple procedural implementation. This version demonstrates advanced software engineering. See README for full academic integrity notice.

# 1. Clone repository
git clone https://github.com/adylagad/CSCI-561_Genetic-Algorithm.git
cd CSCI-561_Genetic-Algorithm

# 2. Run
python main.py

See Quick Start Tutorial for details.

• Python 3.7 or higher
• That's it! (Uses only standard library)

Default settings (500 cities):

• Quick config: ~1 minute
• Balanced config: ~3-5 minutes
• High quality config: ~15-20 minutes

Yes! Create a file with:

<number_of_cities>
<x1> <y1> <z1>
<x2> <y2> <z2>
...

Then:

config = GAConfig(input_file="path/to/your/data.txt")

For most cases, don't change anything. Defaults work well.

If you must:

1. Faster: Reduce number_of_generations to 1000
2. Better quality: Increase population_size_multiplier to 2.0
3. Stuck in local optima: Increase mutation_rate to 0.05

See Configuration Reference.

Default: 0.02 (2%)

• Too low (0.01): May get stuck
• Just right (0.02-0.05): Good balance ✅
• Too high (0.10+): Too chaotic

Formula: 5-10 × number_of_cities

For 500 cities:

• Minimum: 2500
• Recommended: 3500 ✅
• Maximum: 5000+

Or use convergence_threshold to auto-stop.

Use Nearest Neighbor!

It's almost always better:

• Creates much better initial solutions
• Converges ~30% faster
• Final quality is usually better

Only use Random if you want unbiased initial population.

Checklist:

1. Run longer: Increase number_of_generations
2. More diversity: Increase population_size_multiplier
3. Better init: Use NearestNeighborInitializer
4. Different operators: Try PMXCrossover

See Performance Tuning.

Symptoms: Cost stays high, no improvement

Solutions:

1. Check operators are initialized correctly
2. Verify fitness calculation (lower cost = higher fitness)
3. Try different crossover operator
4. Increase mutation rate

Quick fixes:

1. Reduce number_of_generations to 1000
2. Set population_size_multiplier to 0.5
3. Lower convergence_threshold to 100

config = GAConfig(
    population_size_multiplier=0.5,
    number_of_generations=1000,
    convergence_threshold=100
)

Problem: Python can't find the module

Solution: Make sure you're in the project root:

cd CSCI-561_Genetic-Algorithm
python main.py  # Not in subdirectory!

Benchmarks:

• Random tour: ~150,000 (terrible)
• Greedy: ~65,000 (ok)
• Good GA: ~48,000 (good) ✅
• Excellent GA: ~46,000 (excellent)
• Theoretical best: ~45,000 (unknown)

If you get below 50,000, you're doing well!

Because it's a heuristic!

GA finds good solutions, not guaranteed optimal ones.

For 500 cities:

• Finding the optimal is computationally impossible
• GA gets within 1-5% of optimal in minutes
• That's incredibly good!

Yes! Set random seed:

import random
random.seed(42)

# Now results are reproducible
result = ga.run(cities, tour_size)

See Custom Operators Tutorial.

Quick example:

from genetic_algorithm.core.interfaces import MutationOperator

class MyMutation(MutationOperator):
    def mutate(self, tour: Tour) -> Tour:
        # Your implementation
        mutated = tour.copy()
        # ... modify mutated ...
        return mutated

# Use it:
mutation = MyMutation()
ga = GeneticAlgorithm(mutation=mutation, ...)

Yes, with modifications!

The framework is designed for TSP but can be adapted:

1. Different fitness: Change FitnessEvaluator
2. Different representation: Modify Tour type
3. Different operators: Create custom crossover/mutation

python test_ga.py

Add your own tests:

def test_my_operator(self):
    operator = MyOperator()
    result = operator.apply(input_data)
    self.assertIsNotNone(result)

genetic_algorithm/
├── core/          # Main algorithm
├── operators/     # Crossover, mutation, selection
├── initialization/# Population initialization
├── evaluation/    # Fitness calculation
└── utils/         # Helper functions

See Architecture Deep Dive.

• Strategy Pattern: Pluggable operators
• Dependency Injection: Loose coupling
• SOLID Principles: Clean design

1. Fork the repository
2. Create a feature branch
3. Make your changes
4. Add tests
5. Submit pull request

Learning path:

1. Read GA Explained - Understand basics
2. Try Quick Start Tutorial - Run the code
3. Read TSP Overview - Understand the problem
4. Experiment with parameters
5. Try Custom Operators Tutorial

Required:

• Basic syntax (functions, classes, loops)
• Lists and dictionaries
• Importing modules

Helpful:

• Type hints
• Object-oriented programming
• Dataclasses

Core concepts:

• Genetic algorithms (see GA Explained)
• TSP problem (see TSP Overview)
• Fitness functions
• Population-based search

Advanced concepts:

• Selection pressure
• Exploration vs exploitation
• Local vs global optima
• Convergence

Causes:

1. Stuck in local optimum
2. Parameters too conservative
3. Operator bugs

Solutions:

1. Increase mutation rate (try 0.05)
2. Increase population size
3. Use different crossover
4. Check operator implementations

Problem: Plateaus very early, poor diversity

Solutions:

1. Increase population_size_multiplier
2. Increase mutation_rate
3. Decrease selection pressure (use tournament selection)

Expected! GA is stochastic (random).

Solutions:

1. Run multiple times, average results
2. Set random seed for reproducibility
3. Increase generations for stability

1. Use Nearest Neighbor initialization (huge impact!)
2. Run longer (increase generations)
3. Increase population (better exploration)

1. Decrease population size (multiplier to 0.5)
2. Reduce generations (to 1000)
3. Use simpler operators (OrderCrossover)

# Test operator directly
operator = MyOperator()
result = operator.apply(test_input)

# Verify result
assert len(result) == len(test_input)
assert set(result) == set(test_input)

configs = [
    GAConfig(mutation_rate=0.01),
    GAConfig(mutation_rate=0.05),
    GAConfig(mutation_rate=0.10)
]

for config in configs:
    ga = GeneticAlgorithm(config, ...)
    result = ga.run(cities, tour_size)
    print(f"Mutation {config.mutation_rate}: Cost = {result.best_cost}")

In this wiki:

• GA Explained - Algorithm basics
• TSP Overview - Problem details
• Performance Tuning - Optimization
• Custom Operators - Extensions

External resources:

• Genetic Algorithm textbooks
• TSP problem research papers
• Online GA tutorials

1. Check Troubleshooting
2. Review Configuration Reference
3. Open an issue on GitHub

Didn't find your answer? → Troubleshooting