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

Bases: AbstractProblem

Represents the Traveling Salesman Problem (TSP).

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

design_variables

Names of the design variables (nodes in this case).

Type:

list

bounds

Bounds for each design variable as (min, max).

Type:

list of tuples

objectives

Objectives for optimization, e.g., “minimize” or “maximize”.

Type:

list

constraints

Constraints for the optimization problem.

Type:

list

Notes

• Uses geographical distance function (GEO) for evaluating routes.

• Example problem: burma14.tsp, with a known minimum distance.

__init__()

Initialize the TSP problem with default attributes.

Uses the ‘burma14’ TSP dataset as an example with 14 nodes.

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

Computes the Euclidean distance between two nodes.

Parameters:

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

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

Returns:

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

Return type:

float

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

gographical_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