Permutation-Based Optimization Problems

The pycellga.problems.single_objective.discrete.permutation package provides a set of benchmark problems that involve permutation-based solutions. These problems are particularly useful in evaluating optimization algorithms designed for sequencing and ordering tasks, where the solution is represented as a permutation.

Traveling Salesman Problem (TSP)

The Traveling Salesman Problem (TSP) is a classic optimization problem where the goal is to find the shortest possible route that visits each city exactly once and returns to the origin city. TSP is widely used to evaluate the efficiency of algorithms that handle combinatorial and sequencing problems. This module provides a standard implementation of TSP for testing purposes.

class Tsp(n_var: int = 14)

Bases: AbstractProblem

Represents the Traveling Salesman Problem (TSP).

This class solves the TSP using geographical distances (GEO) for node coordinates.

gen_type

The type of genes used in the problem (permutation in this case).

Type:

GeneType

n_var

The number of nodes in the TSP problem.

Type:

int

xl

The minimum value for each variable (1 in this case, node index starts at 1).

Type:

int

xu

The maximum value for each variable (number of nodes).

Type:

int

__init__(n_var: int = 14)

Initialize the TSP problem with default attributes.

Parameters:

n_var (int, optional) – Number of nodes in the TSP problem (default is 14).

f(x: List[int]) → float

Evaluates the fitness of a given chromosome (route) for the TSP.

Parameters:

x (list) – A list representing the route (chromosome), where each element is a node index.

Returns:

The total distance of the route, rounded to one decimal place.

Return type:

float

geographical_dist(a: List[float], b: List[float]) → float

Computes the geographical distance between two nodes using the geodesic distance.

Parameters:

• a (list) – Coordinates of the first node.

• b (list) – Coordinates of the second node.

Returns:

The geographical distance between the two nodes, rounded to one decimal place.

Return type:

float