> For the complete documentation index, see [llms.txt](https://finch-1.gitbook.io/version0.0.1/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://finch-1.gitbook.io/version0.0.1/examples/traveling-salesman-problem.md).

# Traveling Salesman Problem

### Introduction

This guide demonstrates how to use the Finch library to solve the Traveling Salesman Problem (TSP) using genetic algorithms. The TSP is a classic optimization problem in computer science and operations research. It asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?"

Genetic algorithms are a class of optimization techniques inspired by the process of natural selection. They are particularly well-suited for complex problems like the TSP, where finding the exact solution becomes computationally infeasible as the number of cities increases.

### Table of Contents

1. Background
2. Problem Setup
3. Code Implementation
4. Code Breakdown
5. Running the Example
6. Customization Options
7. Conclusion

### Background

#### The Traveling Salesman Problem (TSP)

The TSP is NP-hard, meaning that as the number of cities increases, the time required to find the optimal solution grows exponentially. For this reason, heuristic methods like genetic algorithms are often used to find good (but not necessarily optimal) solutions in a reasonable amount of time.

#### Genetic Algorithms

Genetic algorithms work by maintaining a population of potential solutions (individuals) and evolving them over generations. The key components are:

1. **Encoding**: Representing solutions as "individuals"
2. **Fitness Function**: Evaluating how good a solution is
3. **Selection**: Choosing individuals for reproduction
4. **Crossover**: Combining parent solutions to create offspring
5. **Mutation**: Introducing small random changes to maintain diversity

### Problem Setup

For this example, we'll solve a TSP instance with the following parameters:

* Number of cities: 20
* City coordinates: Randomly generated in a 2D space

### Code Implementation

Here's the complete code for our TSP solver using Finch:

```python
import numpy as np
from Finch.generic import Environment, Individual, Layer
from Finch.layers.universal_layers import Populate, SortByFitness, CapPopulation
from Finch.selectors import RandomSelection, RankBasedSelection
from Finch.layers.array_layers import ArrayPool
import matplotlib.pyplot as plt
import sys

sys.setrecursionlimit(10000)
# Define the number of cities and their coordinates
NUM_CITIES = 20
CITIES = np.random.rand(NUM_CITIES, 2)  # Random 2D coordinates for cities

# Calculate distances between all pairs of cities
DISTANCES = np.sqrt(((CITIES[:, np.newaxis, :] - CITIES[np.newaxis, :, :]) ** 2).sum(axis=2))

def calculate_total_distance(route):
    return sum(DISTANCES[route[i], route[(i + 1) % NUM_CITIES]] for i in range(NUM_CITIES))

# Define the fitness function (we want to minimize the total distance)
def fitness_function(individual):
    return -calculate_total_distance(individual.item)

# Create the gene pool
pool = ArrayPool(gene_array=np.arange(NUM_CITIES), fitness_function=fitness_function, length=NUM_CITIES, unique=True)

# Custom crossover operator for TSP (Order Crossover - OX)
class OrderCrossover(Layer):
    def __init__(self, selection_function, families, children):
        super().__init__(application_function=self.crossover, selection_function=selection_function, repeat=families)
        self.children = children

    def crossover(self, parents):
        for _ in range(self.children):
            parent1, parent2 = parents
            # Choose two random crossover points
            a, b = sorted(np.random.choice(NUM_CITIES, 2, replace=False))
            # Create a child with a segment from parent1
            child = [-1] * NUM_CITIES
            child[a:b] = parent1.item[a:b]
            # Fill the remaining positions with cities from parent2
            parent2_cities = [city for city in parent2.item if city not in child[a:b]]
            for i in range(NUM_CITIES):
                if child[i] == -1:
                    child[i] = parent2_cities.pop(0)
            # Add the child to the population
            self.environment.add_individuals([Individual(item=np.array(child), fitness_function=fitness_function)])

# Custom mutation operator for TSP (2-opt mutation)
class TwoOptMutation(Layer):
    def __init__(self, selection_function, mutation_rate=0.1):
        super().__init__(application_function=self.mutate_all, selection_function=selection_function)
        self.mutation_rate = mutation_rate

    def mutate_all(self, individuals):
        for individual in individuals:
            if np.random.random() < self.mutation_rate:
                self.mutate(individual)

    def mutate(self, individual):
        route = individual.item
        # Choose two random points
        i, j = sorted(np.random.choice(NUM_CITIES, 2, replace=False))
        # Reverse the segment between i and j
        route[i:j+1] = route[i:j+1][::-1]
        individual.item = route

# Define the layers
layers = [
    Populate(population=100, gene_pool=pool),
    OrderCrossover(selection_function=RankBasedSelection(amount_to_select=2, factor=2).select, families=8, children=2),
    TwoOptMutation(selection_function=RandomSelection(percent_to_select=0.1).select, mutation_rate=0.1),
    SortByFitness(),
    CapPopulation(max_population=100)
]

# Create and compile the environment
env = Environment(layers=layers, verbose_every=100)
env.compile()

# Evolve the population
env.evolve(generations=10000)

# Get the best solution
best = env.best_ever
best_route = best.item
best_distance = -best.fitness

print(f"Best route found: {best_route}")
print(f"Total distance: {best_distance}")

# Plot the best route
plt.figure(figsize=(10, 10))
plt.scatter(CITIES[:, 0], CITIES[:, 1], c='red', s=50)
for i in range(NUM_CITIES):
    plt.annotate(str(i), (CITIES[i, 0], CITIES[i, 1]))
for i in range(NUM_CITIES):
    start = best_route[i]
    end = best_route[(i + 1) % NUM_CITIES]
    plt.plot([CITIES[start, 0], CITIES[end, 0]], [CITIES[start, 1], CITIES[end, 1]], 'b-')
plt.title(f"Best TSP Route (Distance: {best_distance:.2f})")
plt.show()

# Plot the fitness history
env.plot()
```

### Code Breakdown

Let's break down the key components of this TSP solver:

#### 1. Imports and Initial Setup

```python
import numpy as np
from Finch.generic import Environment, Individual, Layer
from Finch.layers.universal_layers import Populate, SortByFitness, CapPopulation
from Finch.selectors import RandomSelection, RankBasedSelection
from Finch.layers.array_layers import ArrayPool
import matplotlib.pyplot as plt
import sys

sys.setrecursionlimit(10000)

NUM_CITIES = 20
CITIES = np.random.rand(NUM_CITIES, 2)
```

This section imports necessary modules and sets up the problem parameters. We're using NumPy for numerical operations, Finch for the genetic algorithm framework, and Matplotlib for visualization.

#### 2. Distance Calculation

```python
DISTANCES = np.sqrt(((CITIES[:, np.newaxis, :] - CITIES[np.newaxis, :, :]) ** 2).sum(axis=2))

def calculate_total_distance(route):
    return sum(DISTANCES[route[i], route[(i + 1) % NUM_CITIES]] for i in range(NUM_CITIES))
```

We pre-calculate distances between all pairs of cities for efficiency. The `calculate_total_distance` function computes the total length of a given route.

#### 3. Fitness Function

```python
def fitness_function(individual):
    return -calculate_total_distance(individual.item)
```

The fitness function returns the negative of the total route distance. We use negative because Finch maximizes fitness by default, and we want to minimize the distance.

#### 4. Gene Pool

```python
pool = ArrayPool(gene_array=np.arange(NUM_CITIES), fitness_function=fitness_function, length=NUM_CITIES, unique=True)
```

We use an `ArrayPool` to represent our solutions. Each "gene" is a city index, and we ensure uniqueness to avoid visiting cities multiple times.

#### 5. Custom Genetic Operators

**Order Crossover (OX)**

```python
class OrderCrossover(Layer):
    # ... (implementation details)
```

This crossover operator is designed for permutation problems like TSP. It preserves the relative order of cities from both parents while creating a valid offspring.

**2-Opt Mutation**

```python
class TwoOptMutation(Layer):
    # ... (implementation details)
```

This mutation operator improves routes by reversing segments, which can eliminate route crossings. It's particularly effective for TSP as it can make significant improvements with a single operation.

#### 6. Evolutionary Layers

```python
layers = [
    Populate(population=100, gene_pool=pool),
    OrderCrossover(selection_function=RankBasedSelection(amount_to_select=2, factor=2).select, families=8, children=2),
    TwoOptMutation(selection_function=RandomSelection(percent_to_select=0.1).select, mutation_rate=0.1),
    SortByFitness(),
    CapPopulation(max_population=100)
]
```

This section defines the evolutionary process:

1. Initialize population
2. Apply crossover to create offspring
3. Apply mutation to introduce variations
4. Sort individuals by fitness
5. Cap the population size

#### 7. Evolution and Results

```python
env = Environment(layers=layers, verbose_every=100)
env.compile()
env.evolve(generations=10000)

best = env.best_ever
best_route = best.item
best_distance = -best.fitness
```

Here we create the evolutionary environment, run the evolution for 10,000 generations, and extract the best solution found.

#### 8. Visualization

```python
# Plot the best route
plt.figure(figsize=(10, 10))
# ... (plotting code)
plt.show()

# Plot the fitness history
env.plot()
```

This section visualizes the best route found and plots the fitness history over generations.

### Running the Example

To run this TSP solver:

1. Ensure you have Finch and its dependencies (NumPy, Matplotlib) installed.
2. Copy the entire code into a Python file (e.g., `tsp_solver.py`).
3. Run the script: `python tsp_solver.py`

The script will evolve TSP solutions and display:

* The best route found and its total distance
* A plot of the best route on a map of the cities
* A graph showing how the fitness (route length) improved over generations

### Customization Options

You can experiment with:

* Changing the number of cities (`NUM_CITIES`)
* Adjusting population size and number of generations
* Modifying selection methods or their parameters
* Tuning crossover and mutation rates
* Implementing additional TSP-specific operators

### Conclusion

This example demonstrates how to use Finch to solve the Traveling Salesman Problem using genetic algorithms. It showcases:

* Problem representation for permutation problems
* Custom genetic operators tailored for TSP
* The flexibility of Finch in implementing complex optimization algorithms

By understanding and modifying this example, you can apply similar techniques to other optimization problems or explore different genetic algorithm strategies using the Finch library.


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://finch-1.gitbook.io/version0.0.1/examples/traveling-salesman-problem.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.