SCUBA DIVER OPTIMIZATION ALGORITHM (SDOA)

SCUBA DIVER OPTIMIZATION ALGORITHM A NOVEL METAHEURISTICS ALGORITHM IN SOLVING TRAVELLING SALESMAN PROBLEM

% ======================================================================= %

SCUBA DIVER OPTIMIZATION ALGORITHM (SDOA)

A NOVEL METAHEURISTICS ALGORITHM IN SOLVING TRAVELLING SALESMAN PROBLEM

% ----------------------------------------------------------------------- %

Summary:

The Scuba Diver Optimization Algorithm (SDOA) is novel a population-based metaheuristic inspired by the behavioural and physiological dynamics of scuba divers in open-water environments. Each agent (diver) performs a depth-regulated search controlled by four core diving parameters:

• Depth level

• Tank pressure / Oxygen consumption

• Bottom-time local search

• Ascent-based exploitation and recovery

SDOA balances global exploration and local exploitation by dynamically adjusting solution diversity through oxygen-guided thresholds. High oxygen levels favour deep exploratory dives with large perturbations, whereas reduced oxygen shifts the divers toward intensive local search, controlled ascent, or full reset. This adaptive regulation enables SDOA to avoid premature convergence, maintain population diversity, and accelerate convergence toward high-quality solutions.

Key Mechanisms:

1. Oxygen Decay:

Controls stage transition from exploration to exploitation.

O_i(t) = O_i(t-1) * exp(-alpha * t / t_max)

2. Depth Stages:

Five behavioural modes determined by oxygen thresholds:

D1 → D2 → D3 → D4 → Reset

3. Exploration (Descent):

Depth-proportional perturbations for wide search-space coverage.

4. Bottom-Time Local Search:

Intensive improvement using 2-opt and controlled mutation.

5. Ascent Phase:

Applied when no progress occurs, helping escape local optima.

6. Communication:

Divers at the same depth share solutions with a “buddy”

if the buddy exhibits better fitness.

7. Reset Condition:

Very low oxygen triggers reinitialization using a heuristic tour.

Advantages:

• Strong diversification during early iterations.

• Gradual, oxygen-driven intensification.

• Robust avoidance of local optima.

• High scalability for large TSP instances (N > 2000).

• Faster convergence compared to ACO, ABC, and GA.

Application:

In the Traveling Salesman Problem (TSP), each diver represents a tour. Exploration uses random swap-based perturbations, local search applies 2-opt neighbourhoods, and ascent reverts to earlier or global-best tours.

NOTE: to run the code download TSP problems from TSPLIB95

Reference:

S. M. Almufti, "SCUBA DIVER OPTIMIZATION ALGORITHM: A Novel Metaheuristics Algorithm in Solving Travelling Salesman Problem"

International Journal of Applied Mathematics, Vol. 38, No. 9s, 2025.

DOI: 10.12732/ijam.v38i9s.790

© Saman M. Almufti — 2025

% ======================================================================= %