# Novel Metaheuristic Based on Iterated Constructive Stochastic Heuristic: Dhouib-Matrix-3 (DM3)

Authors: Souhail Dhouib
Journal: Applied Computational Intelligence and Soft Computing
 (2021)

---

## Abstract

This paper presents a new metaheuristic named Dhouib-Matrix-3 (DM3) inspired by our recently developed constructive stochastic heuristic Dhouib-Matrix-TSP2 (DM-TSP2) and characterized by only one parameter: the number of iterations. The proposed metaheuristic DM3 is an iterative algorithm in which every iteration is based on two relay hybridization techniques. At first, the constructive stochastic heuristic DM-TSP2 starts by generating a different initial basic feasible solution and then each solution is intensified by the novel procedure Far-to-Near which exchanges far cities by closer ones using three perturbation techniques: insertion, exchange, and 2-opt. Experimental results carried out on the classical travelling salesman problem using the well-known TSP-LIB benchmark instances demonstrate that our approach DM3 outclasses the simulated annealing algorithm, the genetic algorithm, and the cellular genetic algorithm. Furthermore, the proposed DM3 is statistically concurrent to the hybrid simulated annealing cellular genetic algorithm. Nevertheless, DM3 is easier to implement and needs only one parameter to identify (the maximum number of iterations).


---

## Body

## 1. Introduction

In real-world industry, decision makers are daily confronted with several complicated combinatorial optimization problems such as the scheduling problem, the transportation problem, the knapsack problem, the travelling salesman problem (TSP), and so on. In order to help the decision maker to solve these kinds of problems, there are two major categories of optimization algorithms: the exact and the approximative methods. The first category of algorithms is unable to solve complex problems in that it is characterized by the huge consumption of computational time, whereas the second category, namely, the approximative methods, tries to find a balance between time consumption and quality of the generated solution by partially searching the space of solutions.Actually, the approximative methods gather heuristics as well as metaheuristics. The heuristics are dedicated to specific optimization problems, whereas the metaheuristics are more flexible in a way that they can solve several complex optimization problems (by offering acceptable solutions but without guaranteeing finding the optimality).In this context, tremendous research works are developed in order to prove the efficiency of metaheuristics in the resolution of NP-hard problems. The majority of metaheuristics are stimulated from the collective behavior of creatures in nature. The genetic algorithm (GA) was designed in [1] and was proven as a very successful optimization technique especially with its various variants such as those in [2, 3]. The harmony search (HS) algorithm is based on the search of the best of harmonics, which was firstly introduced in [4]. The artificial bee colony (ABC) is inspired by honey bee mating, which was proposed in [5]. The firefly algorithm (FA) is an optimization algorithm depicted in [6] and invigorated from lights and radiance of fireflies. In [7], the spider monkey algorithm was proposed, which is a swarm-based method that takes benefits from spider monkeys in nature.There are many other population-based algorithms, namely,the grey wolf optimizer (GWO) illustrated in [8]which was inspired from the hierarchy and the hunting process of grey wolves in forests. An improved version of GWO was proposed in [9] in which the biological evolution and the survival of the strongest in the nature’s updating are included in the basic WGO. The bird mating optimizer (BMO) is an evolutionary algorithm designed in [10] and dedicated for continuous optimization problems and invigorated by bird species strategies along the mating season. In 2016, the whale optimization algorithm (WOA) was firstly introduced in [11], and it is based on the behavior of whales in nature. An improved version of WOA was depicted in [12]. The farmland fertility algorithm (FFA) inspired from farmland behavior in nature was presented in [13], and improved FFA was proposed in [14]. The African vultures optimization algorithm (AVOA) was illustrated in [15], which is based on the navigation and foraging behaviors of African vultures.Nevertheless, all these metaheuristics have several parameters that must be fixed before starting the resolution process such as the size of the tabu search memory, the number of neighbourhoods, the initial and the final temperatures, the size of populations, the number of iterations, and so on. In reality, the performance of any metaheuristic is dependent on the best equilibration between all its parameters, and for that, an exhaustive sensitive analysis needs to be done for each parameter. Consequently, in order to simplify this issue, we propose in this paper a new metaheuristic entitled Dhouib-Matrix-3 (DM3) which is characterized by only one parameter: the number of iterations.The proposed metaheuristic DM3 hybridizes in iterated structure a stochastic heuristic with a local search method. For that, our stochastic heuristic Dhouib-Matrix-TSP2 (DM-TSP2) is used to explore different initial basic feasible solutions [16]. DM-TSP2 is a column-row method, and it is characterized by its simplicity and rapidity. Furthermore, our novel local search method Far-to-Near (FtN) is designed in order to exploit each solution generated by DM-TSP2 (see Figure 1).Figure 1
The proposed metaheuristic DM3.Actually, FtN helps to guide the search by affecting far cities to their neighbours. It allows for each city to test its connected nodes and generates a new solution using three perturbation techniques: insertion, exchange, and 2-opt. The FtN procedure accepts any new solution which is not so far from the optimal solution.Hence, DM3 drives the search space through two steps in an iterated structure (see Figure2). At first, it rapidly generates a good initial basic feasible solution using the stochastic heuristic DM-TSP2; then, it intensifies this initial solution using the original procedure, namely, the FtN.Figure 2
The exploration of the solution space through DM3.The performance of the proposed metaheuristic DM3 is proved through its application on the standard travelling salesman problem (TSP). In fact, TSP deals with finding a shortest distanced between n cities that are visited once except the starting city which will be visited twice because it has been already the last visited city. TSP is mathematically formulated as in equation (1) which indicates that dij denotes the distance between city i and city j while xij presents a binary variable (xij = 1 if city i is connected to city j; otherwise, xij = 0):(1)minimize:∑i=1n∑j=1ndijxijsubject to:∑j=1nxij=1,i=1,…,n,∑i=1nxij=1,j=1,…,n,xij=0or1,i=1,…,n,j=1,…,n.This paper is organized as follows. The next section provides all the details about the stochastic constructive heuristic DM-TSP2. Section3 describes the new proposed metaheuristic DM3. Section 4 depicts the numerical application of the proposed method DM3 on TSP-LIB instances with comparison to other developed metaheuristics from the literature. Finally, the conclusion and further work will be given in Section 5.


## 2. The Dhouib-Matrix-TSP2 Method (DM-TSP2)

In [16], we designed and developed the novel heuristic DM-TSP2 which is a stochastic constructive algorithm based on several rules in order to orient the search path. DM-TSP2 is inspired from our deterministic heuristic, namely, Dhouib-Matrix-TSP1 (DM-TSP1), proposed in [17]. The robustness of DM-TSP1 was proven under fuzzy environments in [18–20] and neutrosophic domains in [21, 22].DM-TSP2 is composed of four simple phases and characterized by its rapidity: it needs onlyn iterations to find a good initial basic feasible solution (even the optimal). Figure 3 depicts the general body of the DM-TSP2 algorithm in which K represents the number of the nearest nodes (K is a positive integer). All the details concerning the stepwise application of DM-TSP2 on several examples are exposed in [16, 23].Figure 3
The general body of the DM-TSP2 algorithm.In order to explain the stochastic heuristic DM-TSP2, here is a stepwise application on TSP withK = 2 and 4 × 4 distance matrix presented in Figure 4. To solve this problem, the heuristic DM-TSP2 needs only four simple iterations to generate the optimal or near-optimal solution.(2)∞12131412∞97139∞1014710∞.Figure 4
The 4 × 4 distance matrix.The first step is to compute the standard deviation which will be presented at the last column (see Figure5). Next, select the K highest elements (K = 2, so the values 5.67 and 5.12 are selected) and randomly choose one of them. Let us assume that 5.12 is randomly selected; then, find the K minimal elements in row 4 (which correspond to 7 and 10) and randomly choose one of them (let us assume the element at position d42 with the value of 7).Figure 5
The 4 × 4 distance matrix.Next, insert cities 4 and 2 in List-cities {4-2} and discard their corresponding columns (see Figure6).Figure 6
Discarding columns 2 and 4.Hence, select theK smallest elements for rows 4 and 2 which are equal to 10 and 14 for row 4 and equal to 12 and 9 for row 2. Then, for row 4, choose randomly a value, say 10. Similarity, for row 2, select 12. Now, find the minimal element which is equal to 10 at position d43. So, insert city 3 in List-cities {3-4-2} and discard column 3 (see Figure 7).Figure 7
Discarding column 3.There is only one element in column 3 and in column 2, so select the smallest which is 12 at positiond21, insert city 1 in List-cities {3-4-2-1}, and discard column 1 (see Figure 8).Figure 8
Discarding column 1.Now, there is no more column to discard. So, to generate the initial basic feasible solution, a cycle is needed to be obtained from List-cities {3-4-2-1}. Therefore, we must translate one by one the positions of all cities before city 1 at right with the respected order. Hence, city 3 is translated after city 1. Then, similarly, city 4 and city 2 are added to List-cities {1-3-4-2}. Finally, complete List-cities with city 1 at the end position {1-3-4-2-1}.DM-TSP2 is a very simple and fast stochastic heuristic. It needs only 4 iterations (where 4 represents the number of cities) to generate an initial basic feasible solution. In order to perform DM-TSP2, a guided repetitive structure is needed and for that we design and develop the metaheuristic DM3.


## 3. The Proposed Metaheuristic: Dhouib-Matrix-3 (DM3)

The proposed metaheuristic DM3 iterates in a sequential manner two techniques: the stochastic constructive method DM-TSP2 and the novel procedure FtN. In fact, the iterated algorithms were widely used in literature. The author [24] implemented the variable neighbourhood descent with an iterated local search algorithm in order to solve the TSP with hotel selection. The author [25] also optimized the weighted vertex colouring problem using an iterated local search algorithm with two new neighbour structures. In [26], the author solved the capacitated vehicle routing problems using the iterated local search algorithm with path-relinking method. In [27] generated an iterated local search metaheuristic with large-scale neighbour technique to solve the TSP. In [28], a hybrid multistart iterated local search algorithm was designed with two new compact mixed integer programming formulations with the aim of minimizing the weighted feedback vertex set problem. In [29], a new mathematical programming formulation was generated, and an iterated local search method was in order to minimize the sum of the travelling and the waiting times at the depot. Cacchiani et al. [30] developed an iterated local search algorithm to solve the pollution TSP that looks for generating a Hamiltonian cycle which optimizes a function of driver costs and fuel consumption (which depends on load, speed, and distance). In [31], the iterated local search was used with the variable neighbourhood descent to solve the multivehicle inventory routing problem by minimizing the total cost of storage and transportation. In [32], an iterated local search metaheuristic was designed using a novel perturbation technique for the split delivery vehicle routing problem. In [33], the periodic vehicle routing problem was solved with time windows using a multistart iterated local search algorithm.This paper is focused on proposing a novel metaheuristic entitled DM3 in an iterated structure. DM3 starts by generating a constructive realizable solution using DM-TSP2. Subsequently, the procedure FtN will intensify the solution generated by DM-TSP2 using three different perturbation techniques. Next, the value ofK will be modified (where K represents the number of the nearest nodes, so K is always a positive integer), and the process will be iterated again (see Figure 9).Figure 9
The general body of the proposed metaheuristic DM3.In reality, the procedure FtN is proposed with the intention of organizing the intensification research path. The main idea of this procedure is to eliminate every far neighbour node. As it is detailed in [19, 20], DM-TSP2 is a constructive method which uses in the beginning the rule of the nearest cities with some perturbations. Therefore, after the affectation of some cities, this rule (nearest cities at first) cannot be applied since the nearest cities have been already affected in the first steps of the process. Thus, after the application of DM-TSP2, the proposed procedure FtN will be launched with three perturbation techniques, namely, insertion, exchange, and 2-opt, in order to generate a neighbour solution from the current one.FtN subsequently applies three perturbation techniques for all the nodes and not randomly (see Figure10). It starts by selecting one by one the last inserted cities (in the proposed realizable solution generated by DM-TSP2) and then applying for each selected city the three perturbation techniques (insertion, exchange, and 2-opt) using the nearest K nodes. For example, if the insertion technique is selected, K = 3 and the node 5 is chosen so the FtN procedure will insert city 5 at position of one city from its three nearest cities (K = 3).Figure 10
The general body of the proposed local search metaheuristic FtN.Regarding the acceptation criterion, FtN selects the best neighbour solution and then accepts it only if it is not far than phi (φ) percent from the best solution where φ=1+5/2=0.1618 represents the golden ratio (GR). φ represents the unique solution for the equation x2=x+1 with the characteristic of φ2=φ+1and1/φ=φ−1.In nature, patterns of GR appear especially in the proportions of body dimensions, the spiral arrangement of shell, the arrangement of leaves (phyllotaxis), and additional plant parts. GR has been also used by artists, architects, music composers, decision makers, and scientists in order to analyse a model proportion of natural objects as systems such as investing in financial markets (several technical analyses use GR to handle price level).


## 4. Results and Discussion for a TSP-LIB Problem

In order to confirm the performance of the proposed metaheuristic DM3, twelve standard benchmark instances taken from TSP-LIB (with up to 200 nodes) are used which are the most challenging instances for the travelling salesman problem (olivre30, chn31, eil51, berlin52, eil76, ktpa100, pr107, bier127, ch130, pr136, pr152, and kroa200). Note that the results found by the proposed method DM3 are compared to the results found by the simulated annealing (SA), the genetic algorithm (GA), the cellular genetic algorithm (CGA), and the hybrid simulated cellular genetic algorithm (SCGA) presented in [34].The numerical experiments are conducted using a laptop computer with the following characteristics: Windows 10 Pro, Intel Core i5 2.5 GHz, and 8 GB in RAM. The program is coded in Python programming language using NumPy and Matplotlib libraries. With the intention of comparing the results, we execute DM3 in a multiple run composed of thirty iterations with a time limit equal to 60 seconds if the number of nodes is less than 100 and 180 seconds otherwise.Table1 summarizes the results obtained by the proposed method DM3 and the other metaheuristics for the TSP-LIB instances. The deviation error (DE) percentage is calculated by DE = (best–optimal)/optimal) × 100 where best reports the best solution obtained by DM3 and optimal presents the optimal solution reported in TSP-LIB. The deviation error (DE) ranges from 00.00% to 01.01% when the number of cities varies from 30 to 200.Table 1
Results found by DM3 and other metaheuristics applied on TSP-LIB instances.
InstanceOptimalSAGACGASCGADM3BestREBestREBestREBestREBestREoliver304204251.124241.224240.894240.894200.00chn3115377154870.72154514.69153780.00153780.00153770.00eil514264382.734407.634392.954290.674270.23berlin52754278994.7376859.2678133.5975440.0375420.00eil765385716.1357515.155624.465471.705400.37kroa10021282219853.302209415.89215441.23212850.02212820.00pr10744303459833.794516211.49445790.62443020.00443030.00bier1271182821285158.6512621312.211235784.481182940.011188390.47ch130611065427.07649312.9563503.9361831.2061690.97pr136967721047858.2810537214.211020485.45967950.02967900.02pr15273682758012.887699312.68748891.64736840.00740890.55kroa200293683240610.343419723.38317258.03295330.56296661.01Figure11 depicts the variation of the DE indicator for DM3 and other metaheuristics when the TSP size (number of nodes) increases from 30 to 200 nodes. We can conclude that when the number of nodes is less than 100, the proposed method can generate the optimal or the near-optimal solution in a computational time less than 60 seconds. However, the percentage of deviation error (DE) will increase depending on the TSP-LIB instance size (number of nodes).Figure 11
Trend of the metaheuristic DM3 when the number of nodes increases.As shown in Figure11, we can easily conclude that SCGA and DM3 are significatively better than SA, GA, and CGA for all the instances. Furthermore, the total RE for all instances confirm that the generated solutions by DM3 and SCGA are very close (where their corresponding RE values are 3.39 and 3.54) and better than those generated by SA, GA, and CGA (where their corresponding RE values are, respectively, 55.17, 127.22, and 33.43).Numerically, DM3 is so close to SCGA (respectively, 3.39 and 3.54), and we cannot make comparison between them. However, we can compare their distribution through the Mann–WhitneyU nonparametric test using the IBM SPSS Statistics software. This test will take into account the variation of the results using the RE indicator. We will test the following null hypothesis: “the distribution of RE is the same, so DM3 and SCGA are equal,” and the alternative hypothesis: “their distribution is not equal, so DM3 is different from SCGA.” We will fix also the significance risk level at 0.05%. The corresponding p value is equal 0.514 (see Figure 12) which is not less than 0.05, and we fail to reject the null hypothesis. Thus, DM3 and SCGA are statistically equal (same distribution).Figure 12
Comparing DM3 with SCGA using the Mann–WhitneyU test through IBM SPSS Statistics software.As shown in Figure13, a comparison of DM3 with SA, GA, CGA, and SCGA metaheuristics is given. These results show that we can affirm that for the RE indicator, the results found by DM3 (on all the instances tested in this work) are better than those found by the other methods except the SCGA metaheuristic which is statistically equal to DM3.Figure 13
Box plots for comparing DM3 with SA, GA, CGA, and SCGA.Table2 shows the graphical representation of the best solution found by DM3 for several TSP-LIB problems: (a) chn31, (b) pr107, (c) bier127, (d) pr136, (e) ch130, and (f) pr152.Table 2
Solutions found by the proposed metaheuristic DM3.
(a) chn31(b) pr107(c) bier127(d) pr136(e) ch130(f) pr152


## 5. Conclusion

This paper describes a new metaheuristic named Dhouib-Matrix-3 (DM3) characterized by only one parameter: the number of iterations. This method hybridizes the stochastic constructive method Dhouib-Matrix-TSP2 (DM-TSP2) with an original method named the Far-to-Near in an iterated structure. In fact, each iteration in DM3 starts by generating a good initial solution through the method DM-TSP2; then, this realizable solution will be intensified using the novel procedure Far-to-Near by the means of three different perturbation techniques.The performance of the proposed metaheuristic DM3 is tested on well-known TSP-LIB instances. The computational results show that the novel method DM3 is very competitive, and it outclasses the simulated annealing algorithm, the genetic algorithm, and the cellular genetic algorithm and is statistically concurrent to the hybrid simulated cellular genetic algorithm. Further research will deal with the adaptation of the proposed method DM3 to generate Pareto nondominated set solutions for multiobjective travelling salesmen problem.



---

*Source: 7761993-2021-12-27.xml*