# New Hybrid Meta-heuristic to optimize the low exploitation of Discrete Adapted Dragonfly Algorithm for solving TSP

Mansour Bahar Athmane Ayoub¹, Ferrahi Kamel Soaïd¹, Salma Samy¹, Sadat Souhail Abdelmouaiz¹, Laouchedi Karim¹, Touahria Miliani Mohamed Yacine¹

a5th year, Computer Systems students, École Nationale Supérieure d'Informatique (ex. INI), Oued Smar, 16309, Algiers, Algeria

## Abstract

Optimization problems drive the use of efficient algorithms. Swarm intelligence algorithms, like the Dragonfly Algorithm (DA), have proven effective. However, the original DA is not adapted for discrete problems like the traveling salesman problem (TSP). Existing adaptations showed limited effectiveness, especially for large instances. To overcome this, a new hybrid meta-heuristic algorithm is proposed. It combines the Discrete Adapted DA with Simulated Annealing Search, resulting in significantly improved efficiency. The algorithm demonstrates promising results on large-scale TSP instances from the TSPLIB data set.

**Keywords:** meta-heuristics, hybridisation, discrete adapted dragonfly, simulated annealing, tsp

## 1. Introduction

Optimization is crucial, adjusting processes or systems to offer the best solutions. Deterministic algorithms provide exact solutions but at a high computational cost, while heuristic algorithms offer efficient near-optimal solutions. Meta-heuristics combine diversification and intensification techniques for improved performance, with trajectory-based and population-based approaches being common [1].

Swarm intelligence algorithms, inspired by biological organisms, solve complex optimization problems through simple interactions [2]. The Dragonfly Algorithm (DA) is a superior swarm intelligence algorithm with different versions for continuous, discrete, and multi-objective optimization [3].

The Traveling Salesman Problem (TSP) requires finding the shortest route visiting all locations once. Exact algorithms become computationally demanding as the problem size increases [4]. Heuristic algorithms like PSO and ACO have succeeded in solving TSP using collective intelligence and optimization methods [5] [6].

Applying the DA to solve TSP is valuable, but adapting it for discrete problems like TSP has been challenging [3]. Previous attempts have shown limited effectiveness for large-scale TSP problems [7]. To overcome these limitations, we propose a novel discretized variant of the DA specifically tailored for TSP, aiming to enhance its performance.

Our study aims to improve the effectiveness of the adapted discrete dragonfly algorithm [7]. We propose a two-step approach for TSP: generating initial solutions using Annealing Search and applying a simulated annealing search to refine the solution. We evaluate our algorithm using benchmark TSP problems and demonstrate its superiority in terms of solution quality and cost compared to existing algorithms [8] [9] [10] [11] [12].

The paper is organized as follows: Section 2 provides an

overview of the traveling salesman problem, the original dragonfly algorithm, the discrete adapted dragonfly algorithm, and the simulated annealing algorithm. Section 3 describes the proposed hybrid algorithm, including details about the data structure employed. Section 4 presents the results, comparison tests, and discussions. Finally, Section 5 concludes the paper and offers future perspectives.

## 2. Problem Formulation

In this section we will define the frame of the problem we are solving, i.e, the traveling salesman problem, as well as expose the algorithms that has been used to solve the problem before, and the algorithms we will hybridise.

### 2.1. *Traveling Salesman Problem*

The traveling salesman problem (TSP) is an NP-hard combinatorial optimization problem [13]. It involves finding the optimal route through a set of cities, visiting each city exactly once, and going back to the starting point, while minimizing the total travel cost. TSP has numerous real-world applications, including delivery services, routing, and robotic automated storage and retrieval systems [14].

### 2.2. *Dragonfly Algorithm*

The dragonfly algorithm [3] is a swarm intelligence-based optimization method. Inspired by the swarming behaviors of dragonflies, it differentiates between their static hunting trait of the swarms and the dynamic migratory trait of the swarms. The former reflects the exploration phase of optimization, where groups explore the search space by rapidly changing paths within a limited area. The latter represents the exploitation phase, as dragonflies migrate together towards a common direction over long distances, they are exploiting a solution. Figure
1 shows the difference between static and dynamic behaviour of dragonflies.

<figure><img src="image_1.png" /><figcaption>Figure 1: Dynamic versus static dragonfly swarms [9]</figcaption></figure>

Dragonfly swarms exhibit five key principles illustrated in Figure 2.

<figure><img src="image_2.png" /><figcaption>Figure 2: Five factors of dragonfly swarms movement [3]</figcaption></figure>

These principles can be adapted to DA algorithm by Equation (1)-(5), and to strike a balance between exploration and exploitation, [9] introduces weight factors (s,a,c,f, and e) for the aforementioned principles. Furthermore, two dragonflies are considered neighbors if their distance is within the neighborhood radius. The algorithm of Dragonfly is shown in Algorithm 1

* separation, used to prevent its static collision with its neighbours. Where $X_i$, and $X_j$ are the current dragonfly's position and the j-th neighbour's position respectively.

$$S_i = - \sum_j X_i - X_j \qquad (1)$$

* alignment, matches a dragonfly velocity to that of its neighbours. Where $V_j$ is the j-th neighbour's velocity

$$A_i = \frac{\sum_j V_j}{N} \qquad (2)$$

* cohesion, is a dragonfly tendency towards the centre of the neighbourhood.

$$C_i = \frac{\sum_j X_j}{N} - X_i \qquad (3)$$

* attraction to food, represents a dragonfly's attraction towards a food source. Where $X^+$ is the food source's position

$$F_i = X^+ - X_i \qquad (4)$$

* distraction from enemies, represents a dragonfly's repulsion from an enemy source. Where $X^-$ is the enemy's position

$$E_i = X^- + X_i \qquad (5)$$

To guide the updating of each dragonfly's position with these factors, three vectors are used:

* step vector, determines the direction of the movement. Where $S_i$, $A_i$, $C_i$, $F_i$, and $E_i$ are the separation, alignment, cohesion, food factor, and enemy factors of the i-th dragonfly respectively, s, a, c, f, and e are the separation, alignment, cohesion, food factor, and enemy factor's weights respectively, $w$ is the inertia weight, and $t$ is the current iteration counter

$$\Delta X_i^{t+1} = (sS_i + aA_i + cC_i + fF_i + eE_i) + w\Delta X_i^t \qquad (6)$$

* position vector, allows the movement in the search space by updating the actual position using the step vector to define the direction of movement

$$X_i^{t+1} = X_i^t + \Delta X_i^{t+1} \qquad (7)$$

* levy vector, is a random walk employed to increase the stochasticity and exploration of the algorithm. Where $d$ is the dimension of the position vectors

$$X_i^{t+1} = X_i^t + \text{Levy}(d) * X_i^t \qquad (8)$$

Algorithm 1 Dragonfly Algorithm

1: Initialize the population's position randomly;

2: Initialize the step vectors;

3: **while** end conditions not reached **do**

4: Calculate the objective values of all dragonflies;

5: Update the food source and the enemy;

6: Update the weights;

7: Calculate the factors using (1)-(5);

8: Update radius of the neighbourhoods;

9: **if** dragonfly has one or more neighbours **then**

10: Update step vector using (6);

11: Update position vector using (7);

12: **else**

13: Update position vector using (8);

14: **end if**

15: Check and correct new positions based on upper and lower bounds;

16: **end while**
## 2.3. Related Works

### 2.3.1. Discrete Adapted Dragonfly Algorithm

The adapted discrete Dragonfly Algorithm (DA) [7] customizes the original DA algorithm for solving the Traveling Salesman Problem (TSP) using the following steps:

* A potential solution is represented by a TSP path, which serves as the position of a search agent.

* The equations for calculating the five factors (Separation, Alignment, Cohesion, Food Attraction, Enemy Dispersion), the step vector, and the position vector in DA are modified to be compatible with the path representation.

* The five factors, step vector, and position vector are computed using the swap sequence technique [15].

The pseudo-code for the adapted discrete DA [7] is provided and detailed in Algorithm 2.

**Algorithm 2 Discrete Adapted Dragonfly Algorithm for TSP**

1. Initialize the population's positions with random TSP paths;

2. Initialize the step vectors with random swap sequences;

3. **while** end conditions not reached **do**

4. Calculate the objective values of all dragonflies;

5. Update the food source and the enemy;

6. Update the weights;

7. Calculate the factors using (9)-(13);

8. Update step vector using (14);

9. Update position vector using (15);

10. **end while**

The Equations used in this discrete adapted algorithm are slightly different from the ones in original dragonfly algorithm since it is adapted to discrete problems such as TSP. The five previous factors as well as the step and position vectors are now as follows:

* separation factor, here $X_i$, $X_j$ are the current and the j-th neighbour agent's position, and $N$ is the total number of neighbours. The O-minus operator is to produce a swap sequence, the O-plus operator is to merge two swap sequences, and Inv() is to inverse a swap sequence [38]

$$S_i = \text{inv}(\oplus_{j=1}^{N} X_i \ominus X_j) \qquad (9)$$

* alignment factor, here $Vavg$ represents the step vector of the neighbor with the closest fitness to the average fitness in the neighborhood.

$$A_i = V_{avg} \qquad (10)$$

* cohesion factor, here $Xavg$ is the position of the neighbour having the fitness closest to $Vavg$

$$C_i = X_{avg} \ominus X_i \qquad (11)$$

* attraction to food factor, here $Xf$ is the food source's position

$$F_i = X_f \ominus X_i \qquad (12)$$

* distraction from enemies factor, here $Xe$ is the enemy's position, and distraction() is a procedure that examines each city in $Xe$ and $Xi$, and if a city is found to be in the same position in both paths, it replaces that city with a randomly chosen city different from the one replaced [9]

$$E_i = \text{distraction}(X_e, X_i) \qquad (13)$$

* step vector of direction, here the O-plus operand represents the merging of two swap sequences. This operation combines all the swap operators from the first swap sequence with all the swap operators from the second swap sequence, resulting in a single swap sequence.

$$\Delta X_{t+1} = (sS_i \oplus aA_i \oplus cC_i \oplus fF_i \oplus eE_i) \oplus w\Delta X_t \qquad (14)$$

* position vector, here O-plus operand means that we apply the swap sequence $\Delta(X_t+1)$ to the path $X_t$

$$X_i^{t+1} = X_t \oplus \Delta X_{t+1} \qquad (15)$$

### 2.3.2. Simulated Annealing Search with Non-Monotonic Cooling for TSP

Simulated annealing is a popular meta-heuristic algorithm used for combinatorial optimization problems like the Traveling Salesman Problem (TSP). It mimics the annealing process in metallurgy, gradually exploring solutions with random changes based on a probability function. The algorithm adjusts a temperature parameter to escape local optima and explore the search space effectively. A variant, non-monotonic cooling [16], increases the acceptance of sub-optimal solutions after a certain number of iterations to avoid getting trapped as shown in Algorithm 3. The algorithm has three main equations, mainly to update the temperature, as described below:

* Acceptance probability, is set to accept sub-optimal solutions; where $\Delta$ is the new cost, and $T$ is the current temperature

$$p = e^{-\frac{\Delta T}{T}} \qquad (16)$$

* Increasing of Temperature, this operation is meant to avoid local-optimums; where $\beta$ is the augmentation rate

$$T = T + \beta * T \qquad (17)$$

* Decreasing of Temperature; this operation is meant to advance in the SA process, where $\alpha$ is the cooling rate

$$T = \alpha * T \qquad (18)$$
**Algorithm 3** Simulated Annealing with non-monotonic cooling
for TSP

1: Set the initial tour and its cost as the best tour and the best cost;
2: **while** number of iterations not reached **do**
3: Generate a neighbor of the current tour;
4: Calculate the cost of the new tour;
5: **if** the new tour has a lower cost **then**
6: Update the current tour and its cost with the new tour and its cost;
7: **if** the new cost is lower than the best cost **then**
8: Update the best tour and its cost;
9: **else**
10: calculate the probability of acceptance using (16);
11: **if** a randomly generated number is less than the acceptance probability **then**
12: Update the current tour and its cost with the new tour and its cost;
13: Reset the counter for iterations without improvement;
14: **else**
15: Increment the counter for iterations without improvement;
16: **end if**
17: Reset the counter for iterations without improvement;
18: **end if**
19: **end if**
20: **if** number of iterations without improvement reaches the threshold **then**
21: Update the temperature using (17);
22: **else**
23: Update the temperature using (18);
24: **end if**
25: **if** the temperature falls below the minimum temperature **then**
26: Stop the local search;
27: **end if**
28: **end while**
29: Add the starting city to the best tour to complete the cycle;
30: Return the best solution found;

# 3. Proposed solution

## 3.1. Hybridisation Scheme

Since the Adaptive Discrete DA (ADDO) is well suited for the exploration phase but much less for the exploitation, we decided to boost its exploitation with a specified meta-heuristic. The meta-heuristic chosen is Simulated Annealing with non-monotonic cooling because it gave us best performance for solving TSP than other meta-heuristics such as Ant Colony ACO, Genetic Algorithms GAO, and Taboo Search, as well as quickly converging. The hybridisation schemes followed is a **High Level Relay hybrid algorithm**, as shown in Figure 3

<figure><img src="image_3.png" /><figcaption>Figure 3: High Level Relay hybridisation scheme</figcaption></figure>

## 3.2. Data Structures

To implement an algorithm that realises the hybridisation of discrete adaptive DA with non-monotonic cooling SA, we need to encode our graph and the solutions of the graph to solve the TSP, and thus, we need to define two main data structures to use.

### 3.2.1. Graph of Cities

One of the easiest way to represent a weighted non directed graph is to use a square Matrix where an index represents a city in the graph, and an element (i,j) represents the weight of the arc that connect the i-th city to the j-th city; the diagonal is set to zero to not loop over the same city. In TSP, we call this matrix a distance matrix.

### 3.2.2. A path of cities

A path in TSP is considered a solution, we can represent a solution using a list of cities to show the order of visit of each city, the index of each city is equivalent to the indexes of rows and columns of the distance matrix.

## 3.3. Description of the Hybridisation

The Hybrid Algorithm consists of three essential parts: We first initialize initial solutions using simulated annealing with non-monotonic cooling. These solutions are then passed to the adapted dragonfly algorithm for exploitation. The final result obtained is again passed through simulated annealing to further improve the solution. Initialising a first population with SA will give us a well chosen population that can converge quickly instead of a random initialisation; since it will reduce the search space of exploration to a smaller space that contains best solutions. We then take advantage of the exploration of discrete adapted DA to search for the best solution within the new search space. Once found; this solution is again exploited with non-monotonic cooling SA to optimise it even more and find a more
precise result. The Simulated Annealing with non-monotonic cooling is then executed (n+1) times, where n is the number of dragonflies. The corresponding algorithm for the hybridisation is shown in Algorithm 4.

**Algorithm 4** Hybrid Discrete Adapted Dragonfly & Annealing Search with non-monotonic cooling for TSP

1: /* Generate an initial population of dragonflies with Simulated Annealing with non-monotonic cooling */

2: **for** individual in population **do**

3: **if** it's in the first half of the population **then**

4: Create a random initial tour and apply Simulated Annealing with non-monotonic cooling to it;

5: **else**

6: Create a tour using Nearest Neighbor and apply Simulated Annealing with non-monotonic cooling to it;

7: **end if**

8: Add the tour to the population;

9: **end for**

10: Initialize the best solution as the first tour in the population;

11: /* Explore the solutions with Discrete Adaptive Dragonfly */

12: **while** number of iterations not reached **do**

13: **for** dragonflies in the population **do**

14: Calculate the objective values of all dragonflies;

15: Update the food source and the enemy;

16: Update the weights;

17: Calculate the factors using (9)-(13);

18: Update step vector using (14);

19: Update position vector using (15);

20: Apply local search to the updated position;

21: Update the current dragonfly in the population with the new position;

22: **if** the new position has a smaller distance than the best solution **then**

23: Update the best solution with the new position;

24: **end if**

25: **end for**

26: **end while**

27: Return the best solution found by Discrete Adapting Dragonfly;

28: /* Exploit the solution with Simulated Annealing */

29: Apply Simulated Annealing on the solution found to optimize it more;

30: Return the solution found by Simulated Annealing;

The objective function used in TSP is the cost of a path, the cost is calculated by adding the distances of each two successive cities, we add to it the distance from the last city to the starting city in order to close the cycle. As for the positions of dragonflies, they are updated with the same way in the original adapted discrete DA [7] using the Equations (9)-(13) shown before to calculate the five factors of separation, alignment, cohesion, food attraction, and enemy dispersion, as well as Equations (14)-(15) to update the position of each dragonfly.

## 4. Tests and Results

After discussing the technical implementation details of our solution, we proceed to the testing phase. This part of the article aims to evaluate the algorithm's performance by conducting various tests. These tests not only enhance the solution's quality by optimizing the technique's parameters for a specific data set but also compare its efficiency and execution time to other techniques introduced in previous studies addressing the traveling salesman problem.

### 4.1. Testing Plan

For the testing plan we will use 20 different TSP instances which are (burma14, ulysses16, gr17, gr21, ulysses22, bays29, swiss42, berlin52, st70, pr76, gr96, kroA100, lin105, pr107, gr229, gr666) in order to asset the performance of our hybridisation scheme and compare it to other well-known heuristics and meta heuristics (Taboo Search, Simulated Annealing, Ant Colony Optimization and Genetic Algorithm). For the performance we will use the metric with the formula:

$$P = \left(1 - \frac{D - D_c}{D_c}\right) 100\% \qquad (19)$$

Where P is the performance to be calculated, D is the best found distance, and D_c is the best known distance for the given instance.

### 4.2. Execution Environment

The tests were performed on a i5 11th generation CPU with 16Gb of RAM. The benchmarks used are 20 data sets of different complexity, all taken from TSPLIB.

### 4.3. Parameter Tuning

In this program, we have two categories of parameters, ones for the adapted discrete DA and ones for the non-monotonic cooling SA.

In our case, we want to give priority to the exploration of DA, thus in this paper, we will focus on finding the optimal number of dragonflies and number of iterations to do. The parameter tuning shown below was performed on the swiss42 and gr17 data sets respectively for the number of iterations and the number of dragonflies to use in the exploration phase i.e in the adapted discrete DA part.

<figure><img src="image_4.png" /><figcaption>Figure 4: Variation of cost and time with the number of DA iterations</figcaption></figure>
<figure><img src="image_5.png" /><figcaption>Figure 5: Variation of cost and time with the number of dragonfly</figcaption></figure>

From Figures 4 and 5 we can conclude; firstly, that the num-
ber of iterations doesn't affect the performances much, and
that's because of the good search space that the SA gave us
at first, thus, iterating much over a reduced space won't be much
beneficial. And secondly, that the number of dragonflies help
find better solutions, but a larger population means greater com-
putational costs. However, for 15 dragonflies, we can find op-
timal solutions with lower costs. For the weights of the five
factors of DA, since they are constants we can give them values
depending on the results we would like to have, we have chosen
to use these values :

* Attraction factor, we want our dragonflies to follow the best solution, but yet without getting to close in order to give priority to exploration the reduces search space, so we initialize it at 0.5

* Dispersion factor, we want to escape all the bad solutions in order to avoid local optima and give more importance to exploration, so we initialize it at 0.8

* Randomness factor. Factor of changing a given solution by randomly swapping two cities given a probability (can generate a worst solution) = 0.1

* Local search probability, is the probability of doing a local search (with swapping the cities, as in original adapted discrete DA), we initialize to a relatively small value to give more priority to exploration than exploitation with DA, we initialize it at 0.05

As for the parameters of SA, the optimal parameters for solving TSP are already known from previous tests we made on the performance of SA for solving TSP, we have found the optimal values of parameters as follows :

* Initial Temperature = 1000

* Minimal Temperature = $1e^{-12}$

* Cooling rate alpha = 0.99

* Augmentation rate beta = 0.1

* Number of iterations without augmentation = 1000

* Number of iterations of the algorithm = 20000

4.4. Comparative Study

In this comparative study, we aim to evaluate and compare
the performance of our solution to various algorithms on differ-
ent data sets mentioned before. The algorithms under investi-
gation are selected based on their relevance and applicability to
the problem domain. The data sets used in the study are care-
fully chosen to represent diverse characteristics and complexi-
ties. To ensure a fair comparison, we will employ rigorous ex-
perimental design and statistical analysis techniques. The eval-
uation process will involve running the selected algorithms on
each data set, collecting and analyzing the results, and drawing
meaningful conclusions based on the observed performance dif-
ferences. The comparisons are all detailed in the tables below.
We start with Table 1 that shows the percentage of precision of
our hybrid algorithm in finding the best solution over 20 known
TSPLIB data sets. Then, the Table 2 that shows a contrast be-
tween known meta heuristics in finding the optimal cost of our
test data sets. And finally, a contrast in the execution time of
our hybrid algorithm ADDO-SA with the other algorithms. By
conducting this study, we seek to gain insights into the strengths
and weaknesses of our solution across different data set scenar-
ios.
<table><caption>Table 1: Performance for the hybridisation for 20 TSP Instances</caption><thead><tr><td>Instance</td><td>Cost</td><td>Best Know Cost</td><td>Performance</td><td>Time Execution</td></tr></thead><tbody><tr><td>burma14</td><td>3323</td><td>3323</td><td>100%</td><td>0.14</td></tr><tr><td>ulysses16</td><td>6859</td><td>6859</td><td>100%</td><td>0.17</td></tr><tr><td>gr17</td><td>2085</td><td>2085</td><td>100%</td><td>0.18</td></tr><tr><td>gr21</td><td>2707</td><td>2707</td><td>100%</td><td>0.27</td></tr><tr><td>ulysses22</td><td>7013</td><td>7013</td><td>100%</td><td>0.29</td></tr><tr><td>bays29</td><td>2020</td><td>2020</td><td>100%</td><td>0.78</td></tr><tr><td>swiss42</td><td>1273</td><td>1273</td><td>100%</td><td>1.54</td></tr><tr><td>berlin52</td><td>7542</td><td>7542</td><td>100%</td><td>2.93</td></tr><tr><td>st70</td><td>696</td><td>675</td><td>97.04%</td><td>8.57</td></tr><tr><td>pr76</td><td>109625</td><td>108159</td><td>98.64%</td><td>12.28</td></tr><tr><td>gr96</td><td>57127</td><td>55209</td><td>96.52%</td><td>33.35</td></tr><tr><td>kroA100</td><td>22631</td><td>21282</td><td>93.66%</td><td>35.59</td></tr><tr><td>lin105</td><td>15278</td><td>14379</td><td>93.74%</td><td>42.23</td></tr><tr><td>pr107</td><td>45164</td><td>44303</td><td>98.05%</td><td>50.39</td></tr><tr><td>gr120</td><td>7276</td><td>6942</td><td>96.05%</td><td>218.45</td></tr><tr><td>ch150</td><td>6875</td><td>6528</td><td>94.67%</td><td>219.65</td></tr><tr><td>rat195</td><td>2396</td><td>2323</td><td>96.85%</td><td>648.20</td></tr><tr><td>kroA200</td><td>31490</td><td>29368</td><td>92.77%</td><td>872.71</td></tr><tr><td>gr229</td><td>136486</td><td>134602</td><td>98.6%</td><td>1263.6</td></tr><tr><td>gr666</td><td>297005</td><td>294358</td><td>99.1%</td><td>1612.71</td></tr></tbody></table>
<table><caption>Table 2: Comparison of cost Algorithms for 20 TSP Instances</caption><thead><tr><th>Instance</th><th>ADDO</th><th>EADDO</th><th>SA</th><th>TS</th><th>ACO</th><th>GA</th><th>ADDO+SA</th><th>Best Known Cost</th></tr></thead><tbody><tr><td>burma14</td><td>4562</td><td>3323</td><td>3323</td><td>3323</td><td>3841</td><td>3323</td><td>3323</td><td>3323</td></tr><tr><td>ulysses16</td><td>9665</td><td>6922</td><td>6875</td><td>7276</td><td>7943</td><td>7063</td><td>6859</td><td>6859</td></tr><tr><td>gr17</td><td>4722</td><td>2135</td><td>2088</td><td>2218</td><td>2178</td><td>2098</td><td>2085</td><td>2085</td></tr><tr><td>gr21</td><td>6620</td><td>2758</td><td>2707</td><td>3001</td><td>3003</td><td>2997</td><td>2707</td><td>2707</td></tr><tr><td>ulysses22</td><td>12198</td><td>7183</td><td>7316</td><td>7013</td><td>7287</td><td>7287</td><td>7013</td><td>7013</td></tr><tr><td>bays29</td><td>5752</td><td>2095</td><td>2051</td><td>2169</td><td>2134</td><td>2452</td><td>2020</td><td>2020</td></tr><tr><td>swiss42</td><td>2834</td><td>1407</td><td>1416</td><td>1349</td><td>1401</td><td>1934</td><td>1273</td><td>1273</td></tr><tr><td>berlin52</td><td>22205</td><td>7863</td><td>7809</td><td>8455</td><td>8181</td><td>11844</td><td>7542</td><td>7542</td></tr><tr><td>st70</td><td>3410</td><td>748</td><td>784</td><td>784</td><td>770</td><td>1584</td><td>696</td><td>675</td></tr><tr><td>pr76</td><td>150781</td><td>119486</td><td>119842</td><td>122156</td><td>131607</td><td>290339</td><td>109625</td><td>108159</td></tr><tr><td>gr96</td><td>81007</td><td>63597</td><td>63046</td><td>65942</td><td>63947</td><td>178902</td><td>57127</td><td>55209</td></tr><tr><td>kroA100</td><td>191387</td><td>23713</td><td>25648</td><td>30840</td><td>24698</td><td>89641</td><td>22631</td><td>21282</td></tr><tr><td>lin105</td><td>36480</td><td>15832</td><td>17866</td><td>21608</td><td>16935</td><td>60317</td><td>15278</td><td>14379</td></tr><tr><td>pr107</td><td>62752</td><td>47707</td><td>45825</td><td>55106</td><td>46060</td><td>227314</td><td>45164</td><td>44303</td></tr><tr><td>gr120</td><td>50021</td><td>8006</td><td>8175</td><td>11975</td><td>8352</td><td>27069</td><td>7276</td><td>6942</td></tr><tr><td>ch150</td><td>52814</td><td>7634</td><td>7579</td><td>27474</td><td>7075</td><td>32594</td><td>6875</td><td>6528</td></tr><tr><td>rat195</td><td>4030</td><td>2824</td><td>2737</td><td>2860</td><td>2557</td><td>14222</td><td>2396</td><td>2323</td></tr><tr><td>kroA200</td><td>373938</td><td>33764</td><td>34940</td><td>150993</td><td>34543</td><td>214020</td><td>31490</td><td>29368</td></tr><tr><td>gr229</td><td>179819</td><td>160238</td><td>158230</td><td>168298</td><td>158680</td><td>874123</td><td>136486</td><td>134602</td></tr><tr><td>gr666</td><td>423710</td><td>325558</td><td>365086</td><td>392681</td><td>353146</td><td>4120857</td><td>297005</td><td>294358</td></tr></tbody></table>
<table><caption>Table 3: Comparison of time execution of Algorithms for 20 TSP Instances</caption><thead><tr><th>Instance</th><th>ADDO</th><th>EADDO</th><th>SA</th><th>TS</th><th>ACO</th><th>GA</th><th>ADDO+SA</th></tr></thead><tbody><tr><td>burma14</td><td>0.13</td><td>0.11</td><td>0.017</td><td>0.018</td><td>0.031</td><td>0.19</td><td>0.14</td></tr><tr><td>ulysses16</td><td>0.14</td><td>0.185</td><td>0.0180</td><td>0.025</td><td>0.035</td><td>0.21</td><td>0.17</td></tr><tr><td>gr17</td><td>0.148</td><td>0.28</td><td>0.0180</td><td>0.03</td><td>0.039</td><td>0.22</td><td>0.18</td></tr><tr><td>gr21</td><td>0.16</td><td>0.45</td><td>0.019</td><td>0.059</td><td>0.055</td><td>0.25</td><td>0.27</td></tr><tr><td>ulysses22</td><td>0.17</td><td>0.52</td><td>0.02</td><td>0.067</td><td>0.058</td><td>0.26</td><td>0.29</td></tr><tr><td>bays29</td><td>0.21</td><td>1.34</td><td>0.024</td><td>0.156</td><td>0.093</td><td>0.34</td><td>0.78</td></tr><tr><td>swiss42</td><td>0.30</td><td>4.92</td><td>0.027</td><td>0.47</td><td>0.16</td><td>0.49</td><td>1.54</td></tr><tr><td>berlin52</td><td>0.36</td><td>10.53</td><td>0.031</td><td>0.76</td><td>0.24</td><td>0.65</td><td>2.93</td></tr><tr><td>st70</td><td>0.50</td><td>35.92</td><td>0.039</td><td>0.99</td><td>0.42</td><td>0.90</td><td>8.57</td></tr><tr><td>pr76</td><td>0.53</td><td>49.07</td><td>0.041</td><td>1.03</td><td>0.48</td><td>1.02</td><td>12.28</td></tr><tr><td>gr96</td><td>0.72</td><td>101.2</td><td>0.05</td><td>1.32</td><td>0.77</td><td>1.30</td><td>17.65</td></tr><tr><td>kroA100</td><td>0.75</td><td>143.49</td><td>0.051</td><td>1.35</td><td>0.83</td><td>1.34</td><td>25.59</td></tr><tr><td>lin105</td><td>0.79</td><td>180.6</td><td>0.052</td><td>1.40</td><td>0.91</td><td>1.40</td><td>42.23</td></tr><tr><td>pr107</td><td>155</td><td>350.4</td><td>0.053</td><td>0.82</td><td>0.94</td><td>1.44</td><td>50.39</td></tr><tr><td>gr120</td><td>0.96</td><td>534.4</td><td>0.059</td><td>1.59</td><td>1.15</td><td>1.71</td><td>118.45</td></tr><tr><td>ch150</td><td>1.39</td><td>697</td><td>0.07</td><td>1.94</td><td>1.77</td><td>2.33</td><td>189.65</td></tr><tr><td>rat195</td><td>2.32</td><td>978</td><td>0.087</td><td>2.51</td><td>2.88</td><td>3.31</td><td>348.20</td></tr><tr><td>kroA200</td><td>2.42</td><td>1365</td><td>0.088</td><td>2.63</td><td>2.99</td><td>3.41</td><td>472.71</td></tr><tr><td>gr229</td><td>3.17</td><td>2143</td><td>0.093</td><td>2.99</td><td>3.88</td><td>4.09</td><td>663.61</td></tr><tr><td>gr666</td><td>52.94</td><td>3945</td><td>0.32</td><td>10.40</td><td>31.40</td><td>24.88</td><td>712.71</td></tr></tbody></table>
## 4.5. Discussion of the results

Based on the obtained results, it is evident that our solution consistently outperformed other meta heuristics in each data set, demonstrating a consistently high performance across all instances. The worst performance observed among the compared algorithms was 92.77%, highlighting the superiority of our solution.

Furthermore, our solution consistently achieved the best-known solution for small instances, indicating its effectiveness in finding optimal or near-optimal solutions. This showcases the strength of our algorithm in handling and solving complex optimization problems.

In contrast, the Adaptive Discrete Dragonfly Optimization algorithm (ADDO) exhibited poor performance compared to other algorithms. To address this issue, the Enhanced Adaptive Discrete Dragonfly Optimization algorithm (EADDO) was developed to enhance the former algorithm's performance for exploitation. However, the execution time of EADDO became excessively long for large instances, rendering it impractical for real-world applications.

This is where our algorithm proves advantageous. By combining the exploration capabilities of the Dragonfly algorithm with the exploitation and execution efficiency of Simulated Annealing, our algorithm achieves exceptional results within reasonable time frames. It strikes a balance between exploration and exploitation, allowing for efficient and effective optimization on large instances.

Overall, the comparative analysis highlights the superiority of our algorithm in terms of performance and efficiency compared to other meta heuristics. Its ability to provide excellent results for a wide range of instances, including both small and large problems, positions it as a promising solution for various real-world optimization challenge

# 5. Conclusion and Future Work

Swarm intelligence algorithms excel in solving complex optimization problems by leveraging the collective behavior of search agents. The dragonfly algorithm, drawing inspiration from dragonflies' swarming behaviors, surpasses other swarm intelligence algorithms across different applications. Given its success, utilizing the dragonfly algorithm for the traveling salesman problem (TSP) is a promising endeavor. Although a binary version of the algorithm has been introduced, adapting it for discrete problems like TSP remains a challenge. In our prior research, we proposed a tailored discrete adapted dragonfly algorithm for TSP. However, its effectiveness on larger TSP problems is currently limited and calls for further improvement. In this paper, we propose a new hybrid meta-heuristic that combines the adapted discrete dragonfly algorithm with non-monotonic cooling annealing search. Our algorithm improves the effectiveness of the adapted discrete DA presented in [7] by enhancing its exploitation phase through SA initialization. Experimental results on different TSP instances demonstrate superior solutions compared to discrete DA, annealing search SA, Ant Colony ACO, Genetic Algorithms GAO, Taboo

Search, and Enhanced Adapted Discrete DA [9]. Our algorithm also achieves optimal or near-optimal solutions on various benchmark TSP problems.

For future work, the proposed algorithm can be parallelised with threads or GPU in order to make it converge and obtain results quicker. We also look further to use the new algorithm in real-world applications in scheduling and network routing.

# Acknowledgements

Thanks to Pr. BESSEDIK Malika & Mr. KECHID Amine for their constructive comments and suggestions, and for giving us this opportunity to do this research through the Module of Combinatorial Optimisation.

# References

[1] Yang, X.S. Nature-Inspired Optimization Algorithms; Academic Press: Cambridge, MA, USA, 2020.

[2] Slowik, A.; Kwasnicka, H. Nature inspired methods and their industry applications—Swarm intelligence algorithms. IEEE Trans. Ind. Inform. 2017, 14, 1004–1015.

[3] Mirjalili, S. Dragonfly algorithm: A new meta-heuristic optimization technique for solving single-objective, discrete, and multi-objective problems. Neural Comput. Appl. 2015, 27, 1053–1073.

[4] Gutin, G.; Punnen, A.P. The Traveling Salesman Problem and Its Variations; Springer Science & Business Media: Berlin/Heidelberg, Germany, 2006; Volume 12.

[5] Zhi, X.H.; Xing, X.; Wang, Q.; Zhang, L.; Yang, X.; Zhou, C.; Liang, Y. A discrete PSO method for generalized TSP problem. In Proceedings of the 2004 International Conference on Machine Learning and Cybernetics (IEEE Cat. No. 04EX826), Shanghai, China, 26–29 August 2004; IEEE: Piscataway, NJ, USA, 2004; Volume 4, pp. 2378–2383.

[6] Yang, J.; Shi, X.; Marchese, M.; Liang, Y. An ant colony optimization method for generalized TSP problem. Prog. Nat. Sci. 2008, 18, 1417–1422.

[7] Emambocus, B.A.S.; Jasser, M.B.; Amphawan, A. A discrete adapted dragonfly algorithm for solving the traveling salesman problem. In Proceedings of the 2021 Fifth International Conference on Intelligent Computing in Data Sciences (ICDS), Fez, Morocco, 20–22 October 2021; IEEE: Piscataway, NJ, USA, 2021; pp. 1–6.

[8] Yang, J.; Shi, X.; Marchese, M.; Liang, Y. An ant colony optimization method for generalized TSP problem. Prog. Nat. Sci. 2008, 18, 1417–1422.

[9] Emambocus, B. A. S., Jasser, M. B., Amphawan, A., & Mohamed, A. W. (2022). An Optimized Discrete Dragonfly Algorithm Tackling the Low Exploitation Problem for Solving TSP. Mathematics, 10(19), 3647.

[10] Yao, X.S.; Ou, Y.; Zhou, K.Q. TSP solving utilizing improved ant colony algorithm. J. Phys. Conf. Ser. 2021, 2129, 012026.

[11] Wei, B.; Xing, Y.; Xia, X.; Gui, L. A novel particle swarm optimization with genetic operator and its application to tsp. Int. J. Cogn. Inform. Nat. Intell. 2021, 15, 1–17.

[12] Rokbani, N.; Kumar, R.; Abraham, A.; Alimi, A.M.; Long, H.V.; Priyadarshini, I.; Son, L.H. Bi-heuristic ant colony optimization-based approaches for traveling salesman problem. Soft Comput. 2021, 25, 3775–3794.

[13] Gutin, G.; Punnen, A.P. The Traveling Salesman Problem and Its Variations; Springer Science& Business Media: Berlin/Heidelberg, Germany, 2006; Volume 12.

[14] Foumani, M.; Moeini, A.; Haythorpe, M.; Smith-Miles, K. A cross-entropy method for optimising robotic automated storage and retrieval systems. Int. J. Prod. Res. 2018, 56, 6450–6472.

[15] Wang, K.P.; Huang, L.; Zhou, C.G.; Pang, W. Particle swarm optimization for traveling salesman problem. In Proceedings of the 2003 International Conference on Machine Learning and Cybernetics (IEEE Cat. No. 03EX693), Xi'an, China, 5 November 2003; Volume 3, pp. 1583–1585.

[16] A Comparison of Cooling Schedules for Simulated Annealing (Artificial Intelligence). (n.d.). What-When-How.com.