Growth Optimizer for the Travelling Salesman Problem

Introduction

The Traveling Salesman Problem (TSP) is a classic NP-hard combinatorial optimization problem where the goal is to find the shortest possible route that visits each city exactly once and returns to the origin city. This implementation explores the application of the Growth Optimizer, a novel metaheuristic algorithm inspired by human learning and reflection mechanisms, to solve symmetric TSP instances.

Background

The Growth Optimizer (GO) algorithm, introduced by Zhang et al. (original paper), draws inspiration from human societal growth patterns. It uses dual mechanisms of learning (exploring the solution space by analyzing gaps between solutions) and reflection (refining solutions based on past experiences) to iteratively improve solutions.

Tested TSP Instances

This implementation has been tested on the following TSPLIB instances:

• att48
• berlin52
• eil51
• eil76
• eil101
• lin105
• pr76
• rat99
• kroD100
• st70

Installation

# Clone the repository
git clone https://github.com/kareem-ghazi/growth-optimizer-tsp
cd growth-optimizer-tsp

# Install dependencies
pip install -r requirements.txt

Algorithm Details

The Growth Optimizer for TSP works as follows:

1. Initialization

   • Define the optimization problem and set algorithm parameters.
   • Generate initial random population of candidate solutions.

2. Main Optimization Loop

   • Ranking Phase:

     • Sort all solutions by quality (best to worst)
     • Identify current best solution

   • Learning Phase (for each solution):

     • Select better and worse solutions as references
     • Compute learning adjustments from these references
     • Update current solution while respecting bounds
     • Track global best solution

   • Reflection Phase (for each solution):

     • Refine solution using one of three methods:
       1. Keep current values
       2. Guided improvement using top solutions
       3. Random rebuild (low probability)
     • Update global best solution

3. Termination

   • Stop when maximum evaluations reached
   • Return best solution found

Parameter Tuning

Key parameters affecting performance:

• P1: Controls the societal hierarchy division of the population (recommended: 5)
• P2: Controls the probability of an individual retaining knowledge even if its cost is higher (recommended: 0.001)
• P3: The probability of reflection (recommended: 0.3)
• population_size: Size of the population (recommended: 30-100)
• max_fes: Maximum function evaluations (recommended: number of dimensions x 10,000).

License

This project is released under the MIT license.