An extension of the m-weak group inverse (or m-WGI) on the set of rectangular matrices is provided to solve some systems of matrix equations. The extension is termed as the W-weighted m-WGI (or W-m-WGI). The W-m-WGI presents a new, wider class of generalized inverses which involves some already defined generalized inverses, such as the m-WGI, W-weighted weak group, and W-weighted Drazin inverse. Basic properties and diverse characterizations are proved for W-m-WGI. Several expressions for computing W-m-WGI are proposed in terms of known generalized inverses and projectors, as well as its limit and integral representations. The W-m-WGI class is utilized to solve some linear matrix equations and express their general solutions. Some new properties of the weighted generalized group inverse and recognized properties of the W-weighted Drazin inverse are obtained as corollaries. Numerical and symbolic test examples are presented to verify the obtained results.
Citation: D. Mosić, P. S. Stanimirović, L. A. Kazakovtsev. The m-weak group inverse for rectangular matrices[J]. Electronic Research Archive, 2024, 32(3): 1822-1843. doi: 10.3934/era.2024083
| [1] | Xuemin Fan, Wenjie Zhang, Lu Xu . Global dynamics of a predator-prey model with prey-taxis and hunting cooperation. Electronic Research Archive, 2025, 33(3): 1610-1632. doi: 10.3934/era.2025076 |
| [2] | Érika Diz-Pita . Global dynamics of a predator-prey system with immigration in both species. Electronic Research Archive, 2024, 32(2): 762-778. doi: 10.3934/era.2024036 |
| [3] | Yuan Tian, Hua Guo, Wenyu Shen, Xinrui Yan, Jie Zheng, Kaibiao Sun . Dynamic analysis and validation of a prey-predator model based on fish harvesting and discontinuous prey refuge effect in uncertain environments. Electronic Research Archive, 2025, 33(2): 973-994. doi: 10.3934/era.2025044 |
| [4] | Jialu Tian, Ping Liu . Global dynamics of a modified Leslie-Gower predator-prey model with Beddington-DeAngelis functional response and prey-taxis. Electronic Research Archive, 2022, 30(3): 929-942. doi: 10.3934/era.2022048 |
| [5] | Miao Peng, Rui Lin, Zhengdi Zhang, Lei Huang . The dynamics of a delayed predator-prey model with square root functional response and stage structure. Electronic Research Archive, 2024, 32(5): 3275-3298. doi: 10.3934/era.2024150 |
| [6] | Xiaowen Zhang, Wufei Huang, Jiaxin Ma, Ruizhi Yang . Hopf bifurcation analysis in a delayed diffusive predator-prey system with nonlocal competition and schooling behavior. Electronic Research Archive, 2022, 30(7): 2510-2523. doi: 10.3934/era.2022128 |
| [7] | Yujia Xiang, Yuqi Jiao, Xin Wang, Ruizhi Yang . Dynamics of a delayed diffusive predator-prey model with Allee effect and nonlocal competition in prey and hunting cooperation in predator. Electronic Research Archive, 2023, 31(4): 2120-2138. doi: 10.3934/era.2023109 |
| [8] | Yichao Shao, Hengguo Yu, Chenglei Jin, Jingzhe Fang, Min Zhao . Dynamics analysis of a predator-prey model with Allee effect and harvesting effort. Electronic Research Archive, 2024, 32(10): 5682-5716. doi: 10.3934/era.2024263 |
| [9] | Ailing Xiang, Liangchen Wang . Boundedness of a predator-prey model with density-dependent motilities and stage structure for the predator. Electronic Research Archive, 2022, 30(5): 1954-1972. doi: 10.3934/era.2022099 |
| [10] | Ruizhi Yang, Dan Jin . Dynamics in a predator-prey model with memory effect in predator and fear effect in prey. Electronic Research Archive, 2022, 30(4): 1322-1339. doi: 10.3934/era.2022069 |
An extension of the m-weak group inverse (or m-WGI) on the set of rectangular matrices is provided to solve some systems of matrix equations. The extension is termed as the W-weighted m-WGI (or W-m-WGI). The W-m-WGI presents a new, wider class of generalized inverses which involves some already defined generalized inverses, such as the m-WGI, W-weighted weak group, and W-weighted Drazin inverse. Basic properties and diverse characterizations are proved for W-m-WGI. Several expressions for computing W-m-WGI are proposed in terms of known generalized inverses and projectors, as well as its limit and integral representations. The W-m-WGI class is utilized to solve some linear matrix equations and express their general solutions. Some new properties of the weighted generalized group inverse and recognized properties of the W-weighted Drazin inverse are obtained as corollaries. Numerical and symbolic test examples are presented to verify the obtained results.
Dealing with optimization problems is maximizing or minimizing objective functions by selecting optimal parameters and schemes under given constraints. From the perspective of objective function, there are two branches of optimization problems, multi-objective problems and single-objective problems. The single-objective problems have a unique objective function and the result is an undisputed optimal solution. Multi-objective problems usually have multiple objective functions, and the result is usually a pareto optimal solution set, which usually requires trade-offs to select the relatively better solution.
From the perspective of decision variables, optimization problems are classified into continuous problems and discrete problems. In continuous problems, the decision variables belong to the field of real numbers. The range of continuum problems is vast, and the literature is rich, covering such hot fields as engineering, medical science, and machine learning [1,2,3]. However, the decision variables are often the elements of an integer set in discrete problems. There are many practical optimization problems in the field of discrete optimization, e.g., the Traveling Salesman Problem (TSP) [4,5,6], Graph Coloring Problem (GCP) [5] and DNA Sequence Design Problem (DSDP) [7]. TSP is classified as an Np problem because its time complexity is O (N!) [8]. Although the solution of TSP is very time-consuming [9], it still has many practical applications in many areas, e.g., DNA Fragment Assembly Problem (DFAP) [10], Job Shop Scheduling Problem (JSP) [11,12] and Vehicle Routing Problem (VRP) [13].
The methods for solving TSP are roughly classified into two categories in literature: deterministic algorithms and nondeterministic algorithms. The deterministic algorithms include, Branch and bound (BnB) [14], Dynamic Programming (DP) [15] and Lagrangian Dual (LD) [16], etc. However, as the size of TSP increases, the performance of such algorithms declines significantly [17]. nondeterministic algorithms are generally referring to approximation algorithms and meta-heuristic algorithms, where meta-heuristic algorithms can solve TSP well in controllable time cost. Numerous meta-heuristic algorithms for solving TSP were put forward in the existing literature. These algorithms usually use discrete operators to reconstruct the original algorithms. For example, Karuna Panwar reconstructed the Gray Wolf Optimizer (GWO) by 2-optimization (2-opt) and hamming distance to solve TSP [6]. Mesut Gunduz proposed a Discrete JAYA algorithm (DJAYA) to solve TSP. In DJAYA, roulette is used to control the behavior of the transformation operator, and two search trend parameters ST1 and ST2 are added to enhance comprehensive optimization ability [18]. Huang et al. put forward a nearest neighbor heuristic information mechanism and obtained Discrete Shuffled Frog-leaping Algorithm (DSFLA). In DSFLA, population diversity is maintained by adopting a reverse roulette strategy, and exploration ability is enhanced by utilizing a separate elite set mechanism [19]. Akhand et al. realized the discreteness of the Discrete Spider Monkey Optimizer (DSMO) by utilizing two new cross operators [20]. To deal with TSP, Cinar et al. put forward Discrete Tree Seed Algorithm (DTSA). In DTSA, a combination of multiple transformation operators is introduced to increase exploration ability, and the final solution is improved by 2-opt [21]. Yongquan Zhou et al combined 3-Opt and 2-Opt to propose a discrete invasive weed optimization algorithm (DIWO) to solve the TSP problem [22], and the team also proposed discrete flower pollination algorithms based on the order-based crossover, pollen discarding behavior and partial behaviors [23]. Although these algorithms have good performance, they still have room for improvement in robustness and time cost. In particular, The TSP is a practical problem with more stringent requirements for robustness and time cost. We hope to propose a new discrete algorithm with stable performance and fast running speed to solve TSP.
We put forward a Discrete Salp Swarm Algorithm (DSSA) for solving TSP. Salp Swarm Algorithm (SSA) is a swarm-based algorithm [24]. It was originally used to solve benchmark and real problems of continuous optimization, and SSA also has satisfactory performance in solving engineering design problems. There are two main reasons for proposing a discrete version of SSA to solve the TSP problem:
(1) There are few pieces of literature on the discretization of SSA, especially on TSP.
(2) The exploration mode of the SSA algorithm is that the leader leads the follower to move, which makes the approach of the whole population towards the optimal solution gradually, which is similar to the common neighborhood search idea in the TSP problem.
Therefore, this paper proposes an improved DSSA based on the properties of TSP, and compares it with many advanced meta-heuristic algorithms on 23 benchmark instances. Experimental results reflect DSSA the effectiveness and robustness in solving TSP. In addition, the application results of DSSA on TSP also illustrate the application prospect of this algorithm in solving discrete optimization problems. The rest is arranged as follows: In Section 2, TSP and the corresponding mathematical model are briefly described. The original SSA is briefly described in Section 3. In section 4, the d-opt operator, TPALS operator and DSSA are introduced. Section 5 proves that DSSA has good performance and robustness in solving TSP through several experiments. Finally, in Section 6, the conclusion is presented.
We can describe TSP as follows, a salesman should pass multiple cities and towns to sell goods. The salesman starts in one city, passes through all the planned cities along the way, and ends his trip in the starting city. And to cut down time costs, the salesman should choose the shortest travel path as far as possible. The main difficulty of the TSP is that there are too many potential travel routes: for symmetric TSP of n cities, there is a total of (n-1)/2! Possible paths. The distance from the ith city to the jth city is calculated using Euclidean distance, as shown in Formula Eq (1) [6]:
| di,j=√(xi−xj)2+(yi−yj)2 | (1) |
The distance from the ith city to the jth city is defined di, j. xi and yi are x coordinate and y coordinate of the ith city, xj and yj are x coordinate and y coordinate of the jth city. To calculate the length of the travel path, we use the f function in Eq (2) [6]:
| min(f)=dn,1+∑n−1k=1dk,k+1 | (2) |
Where n is city numbers. If dj, i and di, j are equivalent(i = 1, 2, …, n), then it is called symmetric TSP. We need to find a least cost Hamiltonian path on a weighted graph in TSP [6].
SSA is a very efficient algorithm which is put forward by Seyedali Mirjalili in 2017, which is inspired by the phenomenon that salps move in a chain when foraging. There is one leader and many followers in salps, where the leader leads swarm to the food position, while followers directly or indirectly follow the leader [24].
The leader position is renew using Formula Eq (3):
| x1,j={Fj+c1((ubj−lbj)c2+lbj)c3>0.5Fj−c1((ubj−lbj)c2+lbj)c3≤0.5 | (3) |
Where x1, j represent the jth dimension leader position and Fj represents the jth dimension food position. ubj represents the jth dimension upper bound, lbj represents the jth dimension lower bound. c2 and c3 are random numbers in [0, 1]. c1 is the key coefficient used to balance exploration and exploitation, its calculation formula is shown in Eq (4):
| c1=2e−(4tT) | (4) |
Where T is maximum iterations and t is current iteration. The followers position is renewed using formula Eq (5):
| xi,j=12(xi,j+xi−1,j)i≥2 | (5) |
Where xi, j represents the jth dimension position of follower i. See 1 for pseudocode about SSA.
| Algorithm 1 The Classical SSA |
| Initialize the salp population xi (i = 1, 2, ..., n) considering ub and lb
while (end condition is not satisfied) calculate the fitness of each salp F = the best salp update c1 by (4) for each salp (xi) if (i = = 1) update the position of the leading salp by (3) else update the position of the follower salp by (5) end if end for amend the salps based on the upper and lower bounds of variables end while return F |
To cut down the time cost of 2-optimization (2-opt), we improved it to obtain a d-optimization (d-opt). 2-opt is a local search algorithm proposed by Croes [25] which is broad applied by researchers to deal with various discrete problems. The core idea of 2-opt is to select i and j, and then reverse the subsequence from i to j. If the path cost becomes smaller, perform this operation; otherwise, keep the original solution. For example, the original solution is A−D−C−B−E. If i = 2 and j = 5 are selected, the original solution is converted to A−E−B−C−D. The algorithm continuously improves the solution by repeating these steps.
The time cost of 2-opt is high for two main reasons: 1) 2-opt traverses all possible i and j (i ≠ j), 2) and calculates the total length of the path in each iteration. d-opt improves the above two disadvantages respectively. Firstly, parameter d is introduced to reduce the traversal scale. Where d represents the minimum distance from i to j selected, only subsequences with a length greater than d are selected to attempt inversion. Secondly, d-opt only calculates the change of path length after inversion, not the total path length. See Algorithm 2 and Algorithm 3 for pseudocode about d-opt.
In order to better integrate the Problem Aware Local Search (PALS) algorithm into DSSA to solve TSP. We improve it to obtain Tsp Problem Aware Local Search (TPALS). PALS is a heuristic algorithm proposed by Alba and Luque in 2007 to solve DNA Fragment Assembly Problem (DFAP) [26]. The solutions of PALS are defined as sequences of ordinal numbers of DNA fragments and replaced the current solution with neighborhood information in each iteration. The neighborhood solution set is obtained by reversing the subsequence from given i to j in the current solution. Unlike 2-opt, the termination condition of PALS is that no better solution exists in the domain solution set.
| Algorithm 2 d-opt (tour, d) |
| tour: Initial solution for i = 1: n-d for j = i+d:n deltaF ← CalculateDeltaF(tour, i, j) if (deltaF < 0) ApplyMovement (tour, I, j) end if end for end for return tour |
| Algorithm 3 CalculateDeltaF(tour, i, j) |
| calculate the path length len
if (i!= 1 and j!= len) deltaF ← dtour[i-1], tour[j] – dtour[i-1], tour[i] + dtour[i], tour[j+1] – dtour[j], tour[j+1] else if (i == 1 and j!= len) deltaF ← dtour[i], tour[j+1] – dtour[j], tour[j+1] + dtour[len], tour[j] – dtour[len], tour[i] else if (i!= 1 and j == len) deltaF ← dtour[i-1], tour[j] – dtour[i-1], tour[i] + dtour[i], tour[1] – dtour[j], tour[1] else if (i == 1 and j == len) deltaF ← dtour[i], tour[j] – dtour[j], tour[i] end if return deltaF |
Two problems need to be overcome in applying PALS to TSP. Firstly, the indicator for evaluating the neighborhood solution set in PALS is contig, so we delete the calculation about contig and take the solution with a shorter path length as the better solution among the neighborhood solutions. Secondly, there is no need to consider the overlap score between the last fragment and the first fragment in DFAP, so we add the calculation of the last path back to the starting point in TPALS. See Algorithm 4 for pseudocode about TPALS, where deltaF is also calculated with Algorithm 3.
SSA was originally put forward to solve continuous problems, while TSP is discrete. Therefore, we use discrete operators to reconstruct the original SSA to solve the TSP. The discrete operators used are d-opt and TPALS mentioned above. To increase the exploration ability, we verify the effectiveness of five classical discrete crossover operators respectively, and introduced the operator with the best performance into DSSA. Each slap in the swarm represents a viable solution to TSP.
| Algorithm 4 TPALS (tour) |
| tour: Initial solution repeat L ← ∅ for i = 1:n-1 for j = i+1:n deltaF ← CalculateDeltaF(tour, i, j) if (deltaF < 0) L ← L ∪ (i, j, deltaF) end if end for end for if L ≠ ∅ (i, j) ← SelectMovement (L) ApplyMovement(tour, i, j) end if until no changes; return tour |
In the proposed method, d-opt is used to update leaders, and the update formula is shown in Eq (6):
| Touri=d−opt(Touri,d) | (6) |
Where Touri represents ith slap. d is a parameter used to control the search intensity of d-opt, and its updating formula is shown in Eq (7):
| d=[n×(dMax−(dMax−dMin)×tT)] | (7) |
Where n is city numbers in TSP. The minimum and maximum value of d are defined as dMax and dMin. T is the maximum iterations and t is the current iteration. [.] is integer function.
We use TPALS and crossover operators to renew the followers position. There are 6 alternative crossover operators in this paper, and the best crossover operator is determined in Experiment 5.1. The update formula of followers is shown in Eq (8):
| Touri=operator(Touri,Touri−1) | (8) |
Where operator is the best crossover operator determined in the experiment.
To enhance the exploration ability, DSSA introduced a mechanism named Second Leader Principle (SPL), whose core idea is that in each iteration, a second leader will appear among followers, and the second leader will also use TPALS to renew the position. The formula of second leader is shown in Eq (9):
| Touri=TPALS(Touri) | (9) |
The formula for calculating the probability of followers becoming the second leader is shown in Eq (10):
| pi=iNi=2,…,n | (10) |
Note that there is only one second leader in each iteration. In Algorithm 5, the pseudo code about DSSA can be obtained.
| Algorithm 5 DSSA |
| Initialize the salp population Touri(i = 1, 2, ..., n)
while (end condition is not satisfied) calculate the fitness of each salp bestTour = the best salp update c1 by (8) for each salp (Touri) if (i = = 1) update the position of the leading salp by (6) else update the position of the follower salp by (8) and (9) end if end for end while return bestTour |
We tested it on 23 benchmark instances of small, medium, and large symmetric TSP to verify the effectiveness of the DSSA [18]. Table 1 provides the relevant information of benchmark instances that appeared in the article. Where the number after the instance name represents the number of cities, for example, Oliver30 indicates that the benchmark instance has 30 cities. All the benchmark functions used in the paper are from TSPLIB.
| Instance | Dimension size | Optimal |
| oliver30 | 30 | 420 |
| att48 | 48 | 33522 |
| eil51 | 51 | 426 |
| berlin52 | 52 | 7542 |
| st70 | 70 | 675 |
| eil76 | 76 | 538 |
| pr76 | 76 | 108159 |
| kroA100 | 100 | 21282 |
| kroB100 | 100 | 22141 |
| kroC100 | 100 | 20749 |
| kroD100 | 100 | 21294 |
| kroE100 | 100 | 22068 |
| eil101 | 101 | 629 |
| lin105 | 105 | 14379 |
| pr124 | 124 | 59030 |
| pr136 | 136 | 96772 |
| kroB150 | 150 | 26130 |
| pr152 | 152 | 73682 |
| u159 | 159 | 42080 |
| pr226 | 226 | 80369 |
| pr264 | 264 | 49135 |
| pr299 | 299 | 48191 |
| pr439 | 439 | 107217 |
DownLoad:
CSV
All methods run 20 times for a comprehensive comparison. Each was run with the set parameters: population number N = 50, iterations number T=D+ΣDi=1, where D is the scale of the problem. The results were analyzed by Best, Avg, Standard deviation (Std) and Relative error (Re). The calculation formula of Re is shown in Eq (10) [18]:
| Re=Avg−optimaloptimal×100% | (10) |
Where Avg is the average value of the best path cost obtained by running the algorithm 20 times, and Optimal is the Optimal path cost of the benchmark instance. All experiments were carried out under the same experimental environment: Intel(R) Core (TM) I510500 3.10 GHz CPU and 16.00 GB RAM, and were programmed on MATLAB R2020b. The parameters of the algorithm used in this article are shown in Table 2.
| Algorithms | Parameters | Values |
| DSSA | Population size | 50 |
| Crossover function | SEC | |
| C1 | ∈ [0.1, 0.9] | |
| DGWO | Population size | 50 |
| Crossover function | 2-opt | |
| ESA | Population size | 50 |
| Successor functions | 2-opt & insertion | |
| Temperature | −supΔf/ln(p) | |
| Cooling constant | 0.95 | |
| GA | Population size | 50 |
| Crossover function | OX | |
| Mutation functions | Insertion & 3-opt | |
| Cross. prob. | 0.95 | |
| Mut. prob | 0.25 | |
| Selection function | Binary tournament | |
| Survior function | Binary tournament | |
| FDA | Population size | 50 |
| Movement functions | 2-opt & 3-opt | |
| Initial A0i | Random number in [0.7, 1.0] | |
| Initial r0i | Random number in [0.0, 0.4] | |
| α & γ | 0.98 | |
| IDGA | Population size | 50 |
| Crossover function | OB & OBX | |
| Mutation functions | Insertion & 3-opt | |
| Cross. prob. | [0.95, 0.9, 0.8, 0.75] | |
| Mut. prob | [0.05, 0.1, 0.2, 0.25] | |
| Selection function | Binary tournament | |
| Survior function | Binary tournament | |
| Migration strat. | Best–Replace–Worst |
DownLoad:
CSV
In order to determine the influence of crossover operators and parameter c1 on DSSA, this experiment studied five crossover operators and five parameter combinations on the 19 benchmark instances. The alternative Crossover operators are Partial-Mapped Crossover (PMX) [27], Order Crossover (OX) [28], position-based Crossover (PBX) [29], Order Based Crossover (OBX) [29] and Subtour Exchange Crossover (SEC) [30]. Table 3 shows the influence of different crossover operators on DSSA performance, in which bold numbers represent best results. From Table 3, When the SEC crossover operator is used, the Re of 19 instances is the smallest among all algorithms, and is less than one percent. In addition, see Table 4 for the Friedman test results of Best and Avg. From Table 4, the rank of DSSA-SEC is the smallest on both Best and Avg, and the p-value is much less than 0.05, which indicates that DSSA-SEC is obviously superior to other algorithms in performance and robustness. Therefore, SEC is regarded as the best crossover operator of DSSA.
| Instance | Algorithm | Best | Avg | Re | Time |
| oliver30 | DSSA-PMX | 420 | 420.1 | 0.02% | 0.43 |
| DSSA-OX | 420 | 420.75 | 0.18% | 0.36 | |
| DSSA-PBX | 420 | 420.05 | 0.01% | 0.47 | |
| DSSA-OBX | 420 | 421.1 | 0.26% | 0.41 | |
| DSSA-SEC | 420 | 420 | 0.00% | 0.46 | |
| att48 | DSSA-PMX | 33522 | 33738.3 | 0.65% | 1.63 |
| DSSA-OX | 33522 | 33817.7 | 0.88% | 1.41 | |
| DSSA-PBX | 33522 | 33706.65 | 0.55% | 1.74 | |
| DSSA-OBX | 33522 | 33866.1 | 1.03% | 1.64 | |
| DSSA-SEC | 33522 | 33564.7 | 0.13% | 1.78 | |
| eil51 | DSSA-PMX | 426 | 430.65 | 1.09% | 1.95 |
| DSSA-OX | 426 | 431.8 | 1.36% | 1.70 | |
| DSSA-PBX | 428 | 433.6 | 1.78% | 2.08 | |
| DSSA-OBX | 428 | 435.4 | 2.21% | 1.97 | |
| DSSA-SEC | 426 | 427.55 | 0.36% | 2.04 | |
| berlin52 | DSSA-PMX | 7542 | 7566.5 | 0.32% | 2.07 |
| DSSA-OX | 7542 | 7708.3 | 2.20% | 1.79 | |
| DSSA-PBX | 7542 | 7577.75 | 0.47% | 2.27 | |
| DSSA-OBX | 7542 | 7646.8 | 1.39% | 2.14 | |
| DSSA-SEC | 7542 | 7542 | 0.00% | 2.14 | |
| st70 | DSSA-PMX | 675 | 679.5 | 0.67% | 4.93 |
| DSSA-OX | 675 | 684.35 | 1.39% | 4.48 | |
| DSSA-PBX | 675 | 680.45 | 0.81% | 5.29 | |
| DSSA-OBX | 675 | 684.85 | 1.46% | 5.33 | |
| DSSA-SEC | 675 | 675.05 | 0.01% | 5.29 | |
| eil76 | DSSA-PMX | 541 | 549 | 2.04% | 6.45 |
| DSSA-OX | 542 | 553.3 | 2.84% | 5.82 | |
| DSSA-PBX | 545 | 554.05 | 2.98% | 6.84 | |
| DSSA-OBX | 538 | 555.25 | 3.21% | 6.91 | |
| DSSA-SEC | 538 | 540.5 | 0.46% | 7.02 | |
| pr76 | DSSA-PMX | 108159 | 108479.2 | 0.30% | 6.38 |
| DSSA-OX | 108280 | 109228.9 | 0.99% | 5.79 | |
| DSSA-PBX | 108159 | 109075.8 | 0.85% | 6.77 | |
| DSSA-OBX | 108309 | 109317.6 | 1.07% | 6.83 | |
| DSSA-SEC | 108159 | 108159 | 0.00% | 6.71 | |
| kroA100 | DSSA-PMX | 21282 | 21334.5 | 0.25% | 14.77 |
| DSSA-OX | 21343 | 21714 | 2.03% | 14.31 | |
| DSSA-PBX | 21378 | 21512.55 | 1.08% | 16.31 | |
| DSSA-OBX | 21282 | 21581.35 | 1.41% | 16.90 | |
| DSSA-SEC | 21282 | 21287.8 | 0.03% | 16.08 | |
| kroB100 | DSSA-PMX | 22141 | 22252.2 | 0.50% | 14.83 |
| DSSA-OX | 22283 | 22629.25 | 2.21% | 14.41 | |
| DSSA-PBX | 22141 | 22507.3 | 1.65% | 16.17 | |
| DSSA-OBX | 22258 | 22543.7 | 1.82% | 16.82 | |
| DSSA-SEC | 22141 | 22159 | 0.08% | 15.91 | |
| kroC100 | DSSA-PMX | 20749 | 20835.95 | 0.42% | 14.71 |
| DSSA-OX | 20853 | 21179.15 | 2.07% | 14.43 | |
| DSSA-PBX | 20749 | 20972.65 | 1.08% | 16.89 | |
| DSSA-OBX | 20749 | 21084.1 | 1.62% | 16.85 | |
| DSSA-SEC | 20749 | 20758 | 0.04% | 15.76 | |
| kroD100 | DSSA-PMX | 21294 | 21378.1 | 0.39% | 15.19 |
| DSSA-OX | 21294 | 21742.25 | 2.11% | 14.44 | |
| DSSA-PBX | 21309 | 21744.3 | 2.11% | 16.12 | |
| DSSA-OBX | 21343 | 21684.8 | 1.84% | 17.13 | |
| DSSA-SEC | 21294 | 21323.45 | 0.14% | 15.45 | |
| kroE100 | DSSA-PMX | 22068 | 22192.5 | 0.56% | 15.04 |
| DSSA-OX | 22111 | 22438 | 1.68% | 14.42 | |
| DSSA-PBX | 22117 | 22423.75 | 1.61% | 16.09 | |
| DSSA-OBX | 22068 | 22452.7 | 1.74% | 17.08 | |
| DSSA-SEC | 22068 | 22100.35 | 0.15% | 15.97 | |
| eil101 | DSSA-PMX | 633 | 643.65 | 2.33% | 15.55 |
| DSSA-OX | 635 | 653.55 | 3.90% | 14.89 | |
| DSSA-PBX | 645 | 654.95 | 4.13% | 17.11 | |
| DSSA-OBX | 647 | 655.7 | 4.24% | 17.47 | |
| DSSA-SEC | 629 | 633.95 | 0.79% | 16.87 | |
| lin105 | DSSA-PMX | 14379 | 14430.4 | 0.36% | 17.08 |
| DSSA-OX | 14379 | 14539.95 | 1.12% | 16.85 | |
| DSSA-PBX | 14379 | 14461.35 | 0.57% | 19.24 | |
| DSSA-OBX | 14379 | 14531.85 | 1.06% | 19.95 | |
| DSSA-SEC | 14379 | 14381.2 | 0.02% | 17.90 | |
| pr124 | DSSA-PMX | 59030 | 59080.4 | 0.09% | 28.45 |
| DSSA-OX | 59030 | 59563.4 | 0.90% | 29.50 | |
| DSSA-PBX | 59030 | 59399.75 | 0.63% | 33.46 | |
| DSSA-OBX | 59030 | 59362.8 | 0.56% | 34.25 | |
| DSSA-SEC | 59030 | 59042.15 | 0.02% | 30.52 | |
| pr136 | DSSA-PMX | 96956 | 97529.15 | 0.78% | 40.27 |
| DSSA-OX | 97609 | 99776.55 | 3.10% | 39.50 | |
| DSSA-PBX | 97270 | 98644.85 | 1.94% | 44.66 | |
| DSSA-OBX | 97889 | 99695.8 | 3.02% | 46.27 | |
| DSSA-SEC | 96772 | 97048.7 | 0.29% | 44.97 | |
| kroB150 | DSSA-PMX | 26141 | 26285.75 | 0.60% | 54.36 |
| DSSA-OX | 26324 | 26905.75 | 2.97% | 54.69 | |
| DSSA-PBX | 26246 | 26679.6 | 2.10% | 60.04 | |
| DSSA-OBX | 26411 | 26732.1 | 2.30% | 63.88 | |
| DSSA-SEC | 26130 | 26176.45 | 0.18% | 59.66 | |
| pr152 | DSSA-PMX | 73682 | 73866.4 | 0.25% | 54.95 |
| DSSA-OX | 74373 | 74739.95 | 1.44% | 57.20 | |
| DSSA-PBX | 73818 | 74193.55 | 0.69% | 63.69 | |
| DSSA-OBX | 73888 | 74405 | 0.98% | 64.94 | |
| DSSA-SEC | 73682 | 73763.6 | 0.11% | 60.20 | |
| u159 | DSSA-PMX | 42080 | 42339.7 | 0.62% | 62.77 |
| DSSA-OX | 42535 | 43654.4 | 3.74% | 66.44 | |
| DSSA-PBX | 42080 | 42998.9 | 2.18% | 73.35 | |
| DSSA-OBX | 42080 | 43154.8 | 2.55% | 75.62 | |
| DSSA-SEC | 42080 | 42132.8 | 0.13% | 65.58 |
DownLoad:
CSV
| Rank & p | DSSA-PMX | DSSA-OX | DSSA-PBX | DSSA-OBX | DSSA-SEC |
| rank (Best) | 2.39 | 3.63 | 3.34 | 3.47 | 2.16 |
| p | 5.999E-05 | ||||
| rank (Avg) | 2.11 | 4.37 | 3.21 | 4.32 | 1.00 |
| p | 3.774E-13 | ||||
DownLoad:
CSV
In this experiment, DSSA was compared with several classical or advanced algorithms (DGWO, DFA, DICA, ESA, GA, IBA, IDGA), which have been taken from recently published work [6,31]. Table 5 shows the performance of eight algorithms on 23 benchmark instances, with the best results in bold. Where "\" indicates that the algorithm has not been tested on related problems in the original literature. As can be seen from Table 5, DSSA achieved the best results in all indicators. On the one hand, from the Best index, DSSA can get the theoretical optimal value in 23 instances, which shows that DSSA has satisfactory performance in solving TSP problems. According to the analysis, this may be due to the SEC operator and d-opt operator which gradually reduces the search range, which to some extent improves the accuracy of the optimal solution. On the other hand, from the Avg index, DSSA can win in all 23 instances, which shows that DSSA has satisfactory robustness in solving TSP problems. This shows that the combination of the TPALS operator and the SPL mechanism provides a certain degree of randomness to the algorithm and effectively avoids the algorithm falling into the local optimal solution. In addition, DSSA is superior to DGWO and slightly inferior to the other six algorithms in the Time index, this indicates that DSSA takes a little longer to solve the TSP problem, which may be due to the fact that both d-opt operator and TPALS operator contain the behavior of searching for the optimal solution of the neighborhood. But as a whole, the Re of these six algorithms is much larger than DSSA. If more than 1% of the instance of Re were considered as failures, 53.8% (7/13) of DGWO, 82.4% (14/17) of DFA, 88.2% (15/17) of DICA, 76.5% (13/17) of ESA, and 88.2% (15/17) of GA failed, 64.7% (11/17) of IBA and 88.2% (15/17) of IDGA failed. In all DSSA cases, the Re is less than 1%.
| Fun | Alg | Avg | Best | Re (%) |
Time | Fun | Alg | Avg | Best | Re (%) |
Time |
| oliver 30 |
DSSA | 420 | 420 | 0.00 | 0.5 | eil 101 |
DSSA | 633.95 | 629 | 0.79 | 16.87 |
| DGWO | \ | \ | \ | \ | DGWO | \ | \ | \ | \ | ||
| DFA | 420 | 420 | 0.00 | 0.4 | DFA | 659 | 643 | 4.77 | 13.3 | ||
| DICA | 420 | 420 | 0.00 | 0.5 | DICA | 663.8 | 644 | 5.53 | 12 | ||
| ESA | 420 | 420 | 0.00 | 0.7 | ESA | 658.4 | 650 | 4.67 | 16.3 | ||
| GA | 422.8 | 420 | 0.67 | 0.2 | GA | 673.8 | 655 | 7.12 | 10.6 | ||
| IBA | 420 | 420 | 0.00 | 0.4 | IBA | 646.4 | 634 | 2.77 | 13.1 | ||
| IDGA | 421.5 | 420 | 0.36 | 0.2 | IDGA | 660.7 | 650 | 5.04 | 11.7 | ||
| att 48 |
DSSA | 33564.7 | 33522 | 0.13 | 1.8 | lin 105 |
DSSA | 14381.2 | 14379 | 0.02 | 17.90 |
| DGWO | 33600 | 33523 | 0.23 | 3.0 | DGWO | 14520 | 14382 | 0.98 | 34.3 | ||
| DFA | \ | \ | \ | \ | DFA | \ | \ | \ | \ | ||
| DICA | \ | \ | \ | \ | DICA | \ | \ | \ | \ | ||
| ESA | \ | \ | \ | \ | ESA | \ | \ | \ | \ | ||
| GA | \ | \ | \ | \ | GA | \ | \ | \ | \ | ||
| IBA | \ | \ | \ | \ | IBA | \ | \ | \ | \ | ||
| IDGA | \ | \ | \ | \ | IDGA | \ | \ | \ | \ | ||
| eil 51 |
DSSA | 427.55 | 426 | 0.36 | 2.04 | pr 124 |
DSSA | 59042.15 | 59030 | 0.02 | 30.52 |
| DGWO | \ | \ | \ | \ | DGWO | 59390.9 | 59030 | 0.61 | 44.4 | ||
| DFA | 430.8 | 426 | 1.13 | 1.6 | DFA | 59404.3 | 59030 | 0.63 | 18.8 | ||
| DICA | 432.3 | 426 | 1.48 | 1.8 | DICA | 59436.9 | 59030 | 0.69 | 19 | ||
| ESA | 431.6 | 426 | 1.31 | 2.1 | ESA | 59593.6 | 59030 | 0.95 | 23.1 | ||
| GA | 440.8 | 427 | 3.47 | 1.7 | GA | 59901 | 59030 | 1.48 | 17.3 | ||
| IBA | 428.1 | 426 | 0.49 | 1.7 | IBA | 59412.1 | 59030 | 0.65 | 18.5 | ||
| IDGA | 434.4 | 426 | 1.97 | 1.2 | IDGA | 59912.8 | 59072 | 1.50 | 17.8 | ||
| berlin 52 |
DSSA | 7542 | 7542 | 0.00 | 2.1 | pr 136 |
DSSA | 97048.7 | 96772 | 0.29 | 44.97 |
| DGWO | \ | \ | \ | \ | DGWO | 99310.5 | 97826 | 2.62 | 74.3 | ||
| DFA | 7542 | 7542 | 0.00 | 2.2 | DFA | 99683.7 | 97716 | 3.01 | 24.1 | ||
| DICA | 7542 | 7542 | 0.00 | 2.5 | DICA | 99583.7 | 97736 | 2.91 | 24 | ||
| ESA | 7542 | 7542 | 0.00 | 2.3 | ESA | 99858.3 | 98499 | 3.19 | 29.5 | ||
| GA | 7542 | 7542 | 0.00 | 2.3 | GA | 100472.4 | 98432 | 3.82 | 23.8 | ||
| IBA | 7542 | 7542 | 0.00 | 2.1 | IBA | 99351.2 | 97547 | 2.67 | 23.4 | ||
| IDGA | 7542 | 7542 | 0.00 | 2.4 | IDGA | 99932.7 | 98532 | 3.27 | 23.7 | ||
| st 70 |
DSSA | 675.05 | 675 | 0.01 | 5.3 | krob 150 |
DSSA | 26176.45 | 26130 | 0.18 | 59.66 |
| DGWO | \ | \ | \ | \ | DGWO | 26756.2 | 26320 | 2.39 | 125.2 | ||
| DFA | 685.3 | 675 | 1.53 | 4.3 | DFA | \ | \ | \ | \ | ||
| DICA | 684.7 | 675 | 1.44 | 4.1 | DICA | \ | \ | \ | \ | ||
| ESA | 682.1 | 675 | 1.05 | 4.5 | ESA | \ | \ | \ | \ | ||
| GA | 709.8 | 675 | 5.16 | 4.2 | GA | \ | \ | \ | \ | ||
| IBA | 679.1 | 675 | 0.61 | 3.9 | IBA | \ | \ | \ | \ | ||
| IDGA | 690.2 | 675 | 2.25 | 4.1 | IDGA | \ | \ | \ | \ | ||
| eil 76 |
DSSA | 540.5 | 538 | 0.46 | 7.0 | pr 152 |
DSSA | 73763.6 | 73682 | 0.11 | 60.20 |
| DGWO | \ | \ | \ | \ | DGWO | 74230 | 73690 | 0.74 | 142.8 | ||
| DFA | 556.8 | 543 | 3.49 | 5.3 | DFA | 74934.3 | 74033 | 1.70 | 32.1 | ||
| DICA | 557.6 | 544 | 3.64 | 5.3 | DICA | 74886.7 | 74052 | 1.63 | 32 | ||
| ESA | 553.7 | 546 | 2.92 | 5.8 | ESA | 74969.5 | 74172 | 1.75 | 39.5 | ||
| GA | 565.4 | 545 | 5.09 | 5.6 | GA | 75658.3 | 74520 | 2.68 | 33.4 | ||
| IBA | 548.1 | 539 | 1.88 | 5.1 | IBA | 74676.9 | 73921 | 1.35 | 31 | ||
| IDGA | 557.7 | 545 | 3.66 | 5.1 | IDGA | 75126.7 | 74249 | 1.96 | 32 | ||
| pr 76 |
DSSA | 108159 | 108159 | 0.00 | 6.7 | u159 | DSSA | 42132.8 | 42080 | 0.13 | 65.58 |
| DGWO | 108900 | 108159 | 0.68 | 13.2 | DGWO | 42563.3 | 42142 | 1.14 | 142.8 | ||
| DFA | \ | \ | \ | \ | DFA | \ | \ | \ | \ | ||
| DICA | \ | \ | \ | \ | DICA | \ | \ | \ | \ | ||
| ESA | \ | \ | \ | \ | ESA | \ | \ | \ | \ | ||
| GA | \ | \ | \ | \ | GA | \ | \ | \ | \ | ||
| IBA | \ | \ | \ | \ | IBA | \ | \ | \ | \ | ||
| IDGA | \ | \ | \ | \ | IDGA | \ | \ | \ | \ | ||
| kroA100 | DSSA | 21287.8 | 21282 | 0.03 | 16.1 | pr 226 |
DSSA | 80446.8 | 80369 | 0.10 | 248.4 |
| DGWO | \ | \ | \ | \ | DGWO | 81153.7 | 80648 | 0.95 | 648.6 | ||
| DFA | 21483.6 | 21282 | 0.95 | 10.3 | DFA | \ | \ | \ | \ | ||
| DICA | 21500.3 | 21282 | 1.03 | 10.8 | DICA | \ | \ | \ | \ | ||
| ESA | 21481.7 | 21282 | 0.94 | 14 | ESA | \ | \ | \ | \ | ||
| GA | 21812.4 | 21350 | 2.49 | 9.9 | GA | \ | \ | \ | \ | ||
| IBA | 21445.3 | 21282 | 0.77 | 10.6 | IBA | \ | \ | \ | \ | ||
| IDGA | 21731.8 | 21345 | 2.11 | 10.7 | IDGA | \ | \ | \ | \ | ||
| kroB100 | DSSA | 22159 | 22141 | 0.08 | 15.9 | pr 264 |
DSSA | 49166.15 | 49135 | 0.06 | 422.8 |
| DGWO | 22444.6 | 22159 | 1.37 | 34.5 | DGWO | \ | \ | \ | \ | ||
| DFA | 22604.8 | 22183 | 2.10 | 11.6 | DFA | 51837 | 50491 | 5.50 | 93 | ||
| DICA | 22599.7 | 22180 | 2.08 | 11.3 | DICA | 51943.6 | 50553 | 5.72 | 94.1 | ||
| ESA | 22602.2 | 22202 | 2.09 | 13.6 | ESA | 52198.5 | 51603 | 6.23 | 102.5 | ||
| GA | 22687.4 | 22176 | 2.47 | 10.7 | GA | 52499.8 | 51712 | 6.85 | 92.1 | ||
| IBA | 22506.4 | 22140 | 1.65 | 11.1 | IBA | 50908.3 | 49756 | 3.61 | 92.5 | ||
| IDGA | 22712.6 | 22208 | 2.59 | 10.7 | IDGA | 52290 | 51653 | 6.42 | 94.5 | ||
| kroC100 | DSSA | 20758 | 20749 | 0.04 | 15.8 | pr 299 |
DSSA | 48286.9 | 48191 | 0.20 | 633.7 |
| DGWO | 21780 | 20749 | 1.58 | 34.4 | DGWO | \ | \ | \ | \ | ||
| DFA | 21096.3 | 20756 | 1.67 | 12.8 | DFA | 49839.7 | 48579 | 3.42 | 149.1 | ||
| DICA | 21103.9 | 20756 | 1.71 | 11.7 | DICA | 49880.3 | 48600 | 3.51 | 150.3 | ||
| ESA | 21170.4 | 20749 | 2.03 | 15.4 | ESA | 50532.3 | 49242 | 4.86 | 158.7 | ||
| GA | 21510.4 | 20861 | 3.67 | 10.2 | GA | 50817.1 | 49659 | 5.45 | 147.6 | ||
| IBA | 21050 | 20749 | 1.45 | 12 | IBA | 49674.1 | 48310 | 3.08 | 147.2 | ||
| IDGA | 21298.7 | 20830 | 2.65 | 11.2 | IDGA | 50513.3 | 49572 | 4.82 | 149.94 | ||
| kroD100 | DSSA | 21323.5 | 21294 | 0.14 | 15.5 | pr 439 |
DSSA | 107562.3 | 107217 | 0.32 | 2261 |
| DGWO | \ | \ | \ | \ | DGWO | 112850.3 | 110415 | 5.25 | 2811 | ||
| DFA | 21683.8 | 21408 | 1.83 | 12.4 | DFA | 115558.2 | 111967 | 7.78 | 202.4 | ||
| DICA | 21666.8 | 21399 | 1.75 | 12.6 | DICA | 115763.1 | 111983 | 7.97 | 203.7 | ||
| ESA | 21726.5 | 21500 | 2.03 | 15.9 | ESA | 116706.9 | 113497 | 8.85 | 206.4 | ||
| GA | 22184.6 | 21492 | 4.18 | 9.7 | GA | 116943.4 | 113576 | 9.07 | 208.4 | ||
| IBA | 21593.4 | 21294 | 1.41 | 11.7 | IBA | 115256.4 | 11153 | 7.50 | 201.9 | ||
| IDGA | 21696.9 | 21582 | 1.89 | 12.1 | IDGA | 116436.1 | 113207 | 8.60 | 205.7 | ||
| kroE100 | DSSA | 22100.4 | 22068 | 0.15 | 16 | \ | \ | \ | \ | \ | \ |
| DGWO | 22131 | 22410 | 1.54 | 34.3 | \ | \ | \ | \ | \ | ||
| DFA | 22413 | 22079 | 1.56 | 11.6 | \ | \ | \ | \ | \ | ||
| DICA | 22453.3 | 22083 | 1.75 | 11.7 | \ | \ | \ | \ | \ | ||
| ESA | 22499.7 | 22099 | 1.96 | 15 | \ | \ | \ | \ | \ | ||
| GA | 22741.3 | 22150 | 3.05 | 9.4 | \ | \ | \ | \ | \ | ||
| IBA | 22349.6 | 22068 | 1.28 | 11.4 | \ | \ | \ | \ | \ | ||
| IDGA | 22721.9 | 22110 | 2.96 | 12.6 | \ | \ | \ | \ | \ |
DownLoad:
CSV
In this experiment, DSSA was compared with several classical or advanced algorithms (IBA, ESA and DFA), which have been taken from recently published work [6,31]. In Table 6, the average number (in thousands) of objective function evaluations required to reach the final solution for each instance is shown, with the best results in bold. From Table 6, on the one hand, the average evaluations number of DSSA is much smaller than the other algorithms, which indicates that DSSA shows better convergence in all 23 instances, on the other hand, the evaluations number of DSSA does not change significantly by orders of magnitude as the size of the problem rises, suggesting that DSSA has advantages in solving TSP on a larger scale. Finally, despite the longest single run time of the DSSA, the overall time cost of solving TSP can be reduced by determining the appropriate evaluations number. Therefore, the DSSA proposed in the paper is a promising approach to solving TSP.
| Instance / Algorithms | DSSA | DFA | ESA | IBA |
| oliver30 | 0.89 | 3.38 | 23.91 | 2.17 |
| eil51 | 8.51 | 17.56 | 85.91 | 15.37 |
| berlin52 | 1.99 | 23.68 | 128.26 | 20.07 |
| st70 | 9.82 | 69.56 | 216.08 | 72.67 |
| eil76 | 19.93 | 164.18 | 262.89 | 91.53 |
| kroA100 | 19.24 | 812.56 | 784.84 | 739.86 |
| kroB100 | 20.29 | 813.68 | 729.83 | 461.05 |
| kroC100 | 14.81 | 835.79 | 726.35 | 872.51 |
| KroD100 | 14.81 | 875.74 | 689.49 | 600.31 |
| KroE100 | 20.89 | 843.72 | 791.76 | 602.94 |
| 3il101 | 32.86 | 617.83 | 598.11 | 512.73 |
| pr124 | 16.92 | 1589.71 | 1446.91 | 1602.51 |
| pr136 | 47.04 | 2763.8 | 2318.2 | 2866.6 |
| pr152 | 23.19 | 4769.37 | 3853.91 | 4853.19 |
| pr264 | 47.13 | 6686.39 | 6096.45 | 6375.46 |
| pr299 | 113.26 | 7016.91 | 6731.23 | 6597.94 |
| pr439 | 278.13 | 8736.28 | 8006.91 | 8346.85 |
DownLoad:
CSV
As a swarm-based algorithm, SSA was put forward to deal with continuous optimization problems of single and multiple objectives. In this paper, we proposed a DSSA for solving TSP. Firstly, we improved 2-opt and PALS into d-opt and TPALS respectively, and added them into DSSA as discrete operators. Secondly, we made a comparative study of five crossover operators, and confirmed that SEC is the best crossover operator of DSSA and introduce it into DSSA. Finally, the proposed DSSA was compared with several advanced algorithms on 23 benchmark examples, and the results showed DSSA possesses satisfactory properties and robustness in solving TSP. In the process of experiment, we found that the SEC operator and d-opt operator which gradually reduced the search range could improve the exploitation ability of the algorithm and help to improve the accuracy of the optimal solution, and the combination of the TPALS operator and the second leader mechanism provided certain randomness to the algorithm, so that the algorithm could avoid falling into the local optimal solution. At the same time, DSSA also exposes the disadvantage of long running time. According to the analysis, it may be because the d-opt operator and TPALS operator both contain the behavior of searching for the optimal solution of the neighborhood. In the future, In the future, we plan to make improvements to address the long running time of DSSA, and we intend to put forward excellent and novel discrete operators for DSSA to deal with DNA fragment assembly problems.
This work is supported by 111 Project (No.D23006), by the National Natural Science Foundation of China (Nos. 62272079, 61972266), Liaoning Revitalization Talents Program (No. XLYC2008017), Natural Science Foundation of Liaoning Province (Nos. 2021-MS-344, 2021-KF-11-03, 2022-KF-12-14), the Postgraduate Education Reform Project of Liaoning Province (No. LNYJG2022493), the Dalian Outstanding Young Science and Technology Talent Support Program (No. 2022RJ08).
On behalf of all authors, the corresponding author states that there is no conflict of interest.
| [1] | A. Ben-Israel, T. N. E. Grevile, Generalized Inverses, Theory and Applications, 2nd edition, Canadian Mathematical Society, Springer, New York, Beflin, Heidelberg, Hong Kong, London, Milan, Paris, Tokyo, 2003. |
| [2] |
R. E. Cline, T. N. E. Greville, A Drazin inverse for rectangular matrices, Linear Algebra Appl., 29 (1980), 53–62. https://doi.org/10.1016/0024-3795(80)90230-X doi: 10.1016/0024-3795(80)90230-X
|
| [3] |
K. M. Prasad, K. S. Mohana, Core-EP inverse, Linear Multilinear Algebra, 62 (2014), 792–802. https://doi.org/10.1080/03081087.2013.791690 doi: 10.1080/03081087.2013.791690
|
| [4] |
D. E. Ferreyra, F. E. Levis, N. Thome, Revisiting the core EP inverse and its extension to rectangular matrices, Quaestiones Math., 41 (2018), 265–281. https://doi.org/10.2989/16073606.2017.1377779 doi: 10.2989/16073606.2017.1377779
|
| [5] |
D. Mosić, Weighted core-EP inverse of an operator between Hilbert spaces, Linear Multilinear Algebra, 67 (2019), 278–298. https://doi.org/10.1080/03081087.2017.1418824 doi: 10.1080/03081087.2017.1418824
|
| [6] |
D. E. Ferreyra, F. E. Levis, N. Thome, Maximal classes of matrices determining generalized inverses, Appl. Math. Comput., 333 (2018), 42–52. https://doi.org/10.1016/j.amc.2018.03.102 doi: 10.1016/j.amc.2018.03.102
|
| [7] |
Y. Gao, J. Chen, Pseudo core inverses in rings with involution, Commun. Algebra, 46 (2018), 38–50. https://doi.org/10.1080/00927872.2016.1260729 doi: 10.1080/00927872.2016.1260729
|
| [8] |
M. Zhou, J. Chen, Integral representations of two generalized core inverses, Appl. Math. Comput., 333 (2018), 187–193. https://doi.org/10.1016/j.amc.2018.03.085 doi: 10.1016/j.amc.2018.03.085
|
| [9] |
R. Behera, G. Maharana, J. K. Sahoo, Further results on weighted core-EP inverse of matrices, Results Math., 75 (2020), 174. https://doi.org/10.1007/s00025-020-01296-z doi: 10.1007/s00025-020-01296-z
|
| [10] |
G. Dolinar, B. Kuzma, J. Marovt, B. Ungor, Properties of core-EP order in rings with involution, Front. Math. China, 14 (2019), 715–736. https://doi.org/10.1007/s11464-019-0782-8 doi: 10.1007/s11464-019-0782-8
|
| [11] |
I. Kyrchei, Determinantal representations of the core inverse and its generalizations with applications, J. Math., 2019 (2019). https://doi.org/10.1155/2019/1631979 doi: 10.1155/2019/1631979
|
| [12] |
H. Ma, P. S. Stanimirović, Characterizations, approximation and perturbations of the core-EP inverse, Appl. Math. Comput., 359 (2019), 404–417. https://doi.org/10.1016/j.amc.2019.04.071 doi: 10.1016/j.amc.2019.04.071
|
| [13] |
K. M. Prasad, M. D. Raj, Bordering method to compute core-EP inverse, Spec. Matrices, 6 (2018), 193–200. https://doi.org/10.1515/spma-2018-0016 doi: 10.1515/spma-2018-0016
|
| [14] |
M. M. Zhou, J. L. Chen, T. T. Li, D. G. Wang, Three limit representations of the core-EP inverse, Filomat, 32 (2018), 5887–5894. https://doi.org/10.2298/FIL1817887Z doi: 10.2298/FIL1817887Z
|
| [15] |
O. M. Baksalary, G. Trenkler, Core inverse of matrices, Linear Multilinear Algebra, 58 (2010), 681–697. https://doi.org/10.1080/03081080902778222 doi: 10.1080/03081080902778222
|
| [16] |
H. Wang, J. Chen, Weak group inverse, Open Math., 16 (2018), 1218–1232. https://doi.org/10.1515/math-2018-0100 doi: 10.1515/math-2018-0100
|
| [17] |
D. E. Ferreyra, V. Orquera, N. Thome, A weak group inverse for rectangular matrices, Rev. R. Acad. Cienc. Exactas Fˊis. Nat. Ser. A Mat., 113 (2019), 3727–3740. https://doi.org/10.1007/s13398-019-00674-9 doi: 10.1007/s13398-019-00674-9
|
| [18] |
D. Mosić, D. Zhang, Weighted weak group inverse for Hilbert space operators, Front. Math. China, 15 (2020), 709–726. https://doi.org/10.1007/s11464-020-0847-8 doi: 10.1007/s11464-020-0847-8
|
| [19] |
N. Liu, H. Wang, The characterizations of WG matrix and its generalized Cayley-Hamilton theorem, J. Math., 2021 (2021). https://doi.org/10.1155/2021/4952943 doi: 10.1155/2021/4952943
|
| [20] |
D. Mosić, P. S. Stanimirović, Representations for the weak group inverse, Appl. Math. Comput., 397 (2021), 125957. https://doi.org/10.1016/j.amc.2021.125957 doi: 10.1016/j.amc.2021.125957
|
| [21] |
H. Wang, X. Liu, The weak group matrix, Aequ. Math., 93 (2019), 1261–1273. https://doi.org/10.1007/s00010-019-00639-8 doi: 10.1007/s00010-019-00639-8
|
| [22] |
H. Yan, H. Wang, K. Zuo, Y. Chen, Further characterizations of the weak group inverse of matrices and the weak group matrix, AIMS Math., 6 (2021), 9322–9341. https://doi.org/10.3934/math.2021542 doi: 10.3934/math.2021542
|
| [23] |
M. Zhou, J. Chen, Y. Zhou, Weak group inverses in proper ∗-rings, J. Algebra Appl., 19 (2020), 2050238. https://doi.org/10.1142/S0219498820502382 doi: 10.1142/S0219498820502382
|
| [24] |
Y. Zhou, J. Chen, M. Zhou, m-weak group inverses in a ring with involution, Rev. R. Acad. Cienc. Exactas Fˊis. Nat. Ser. A Mat., 115 (2021). https://doi.org/10.1007/s13398-020-00932-1 doi: 10.1007/s13398-020-00932-1
|
| [25] |
W. Jiang, K. Zuo, Further characterizations of the m-weak group inverse of a complex matrix, AIMS Math., 7 (2022), 17369–17392. https://doi.org/10.1007/10.3934/math.2022957 doi: 10.1007/10.3934/math.2022957
|
| [26] |
D. E. Ferreyra, S. B. Malik, A generalization of the group inverse, Quaestiones Math., 46 (2023). https://doi.org/10.2989/16073606.2022.2144533 doi: 10.2989/16073606.2022.2144533
|
| [27] |
D. Mosić, P. S. Stanimirović, L. A. Kazakovtsev, Application of m-weak group inverse in solving optimization problems, Rev. R. Acad. Cienc. Exactas Fˊis. Nat. Ser. A Mat., 118 (2024), 13. https://doi.org/10.1007/s13398-023-01512-9 doi: 10.1007/s13398-023-01512-9
|
| [28] |
D. Mosić, D. Zhang, New representations and properties of m-weak group inverse, Results Math., 78 (2023). https://doi.org/10.1007/s00025-023-01878-7 doi: 10.1007/s00025-023-01878-7
|
| [29] |
V. Rakočević, Y. Wei, The representation and approximation of the W-weighted Drazin inverse of linear operators in Hilbert space, Appl. Math. Comput., 141 (2003), 455–470. https://doi.org/10.1016/S0096-3003(02)00267-9 doi: 10.1016/S0096-3003(02)00267-9
|
| [30] |
P. S. Stanimirović, V. N. Katsikis, H. Ma, Representations and properties of the W-Weighted Drazin inverse, Linear Multilinear Algebra, 65 (2017), 1080–1096. https://doi.org/10.1080/03081087.2016.1228810 doi: 10.1080/03081087.2016.1228810
|
| [31] |
M. P. Drazin, Weighted (b, c)-inverses in categories and semigroups, Commun. Algebra, 48 (2020), 1423–1438. https://doi.org/10.1080/00927872.2019.1687712 doi: 10.1080/00927872.2019.1687712
|
| [32] |
P. S. Stanimirović, D. Mosić, H. Ma, New classes of more general weighted outer inverses, Linear Multilinear Algebra, 70 (2022), 122–147. https://doi.org/10.1080/03081087.2020.1713712 doi: 10.1080/03081087.2020.1713712
|
| [33] |
M. P. Drazin, A class of outer generalized inverses, Linear Algebra Appl., 436 (2012), 1909–1923. https://doi.org/10.1016/j.laa.2011.09.004 doi: 10.1016/j.laa.2011.09.004
|
| [34] | C. W. Groetsch, Generalized inverses of linear operators: representation and approximation, in Monographs and Textbooks in Pure and Applied Mathematics, Marcel Dekker, Inc., New York, Basel, 37 (1977). |
| [35] |
X. Liu, Y. Yu, J. Zhong, Y. Wei, Integral and limit representations of the outer inverse in Banach space, Linear Multilinear Algebra, 60 (2012), 333–347. https://doi.org/10.1080/03081087.2011.598154 doi: 10.1080/03081087.2011.598154
|
| [36] |
P. S. Stanimirović, Limit representations of generalized inverses and related methods, Appl. Math. Comput., 103 (1999), 51–68. https://doi.org/10.1016/S0096-3003(98)10048-6 doi: 10.1016/S0096-3003(98)10048-6
|
| [37] |
Y. Wei, D. S. Djordjević, On integral representation of the generalized inverse A(2)T,S, Appl. Math. Comput., 142 (2003), 189–194. https://doi.org/10.1016/S0096-3003(02)00296-5 doi: 10.1016/S0096-3003(02)00296-5
|
| [38] |
G. Maess, Projection methods solving rectangular systems of linear equations, J. Comput. Appl. Math., 24 (1988), 107–119. https://doi.org/10.1016/0377-0427(88)90346-9 doi: 10.1016/0377-0427(88)90346-9
|
| [39] |
Y. Wei, A characterization for the W-weighted Drazin inverse and a Cramer rule for the W-weighted Drazin inverse solution, Appl. Math. Comput., 125 (2002), 303–310. https://doi.org/10.1016/S0096-3003(00)00132-6 doi: 10.1016/S0096-3003(00)00132-6
|
| [40] | S. L. Campbell, C. D. Meyer, Generalized Inverses of Linear Transformations, Pitman, London, 1979. |
| 1. | Xiangwen Yin, Promoting peer learning in education: Exploring continuous action iterated dilemma and team leader rotation mechanism in peer-led instruction, 2023, 31, 2688-1594, 6552, 10.3934/era.2023331 | |
| 2. | Xin Du, Quansheng Liu, Yuanhong Bi, Bifurcation analysis of a two–dimensional p53 gene regulatory network without and with time delay, 2023, 32, 2688-1594, 293, 10.3934/era.2024014 |
D. Mosić, P. S. Stanimirović, L. A. Kazakovtsev. The m-weak group inverse for rectangular matrices[J]. Electronic Research Archive, 2024, 32(3): 1822-1843. doi: 10.3934/era.2024083
| Instance | Dimension size | Optimal |
| oliver30 | 30 | 420 |
| att48 | 48 | 33522 |
| eil51 | 51 | 426 |
| berlin52 | 52 | 7542 |
| st70 | 70 | 675 |
| eil76 | 76 | 538 |
| pr76 | 76 | 108159 |
| kroA100 | 100 | 21282 |
| kroB100 | 100 | 22141 |
| kroC100 | 100 | 20749 |
| kroD100 | 100 | 21294 |
| kroE100 | 100 | 22068 |
| eil101 | 101 | 629 |
| lin105 | 105 | 14379 |
| pr124 | 124 | 59030 |
| pr136 | 136 | 96772 |
| kroB150 | 150 | 26130 |
| pr152 | 152 | 73682 |
| u159 | 159 | 42080 |
| pr226 | 226 | 80369 |
| pr264 | 264 | 49135 |
| pr299 | 299 | 48191 |
| pr439 | 439 | 107217 |
DownLoad:
CSV
| Algorithms | Parameters | Values |
| DSSA | Population size | 50 |
| Crossover function | SEC | |
| C1 | ∈ [0.1, 0.9] | |
| DGWO | Population size | 50 |
| Crossover function | 2-opt | |
| ESA | Population size | 50 |
| Successor functions | 2-opt & insertion | |
| Temperature | −supΔf/ln(p) | |
| Cooling constant | 0.95 | |
| GA | Population size | 50 |
| Crossover function | OX | |
| Mutation functions | Insertion & 3-opt | |
| Cross. prob. | 0.95 | |
| Mut. prob | 0.25 | |
| Selection function | Binary tournament | |
| Survior function | Binary tournament | |
| FDA | Population size | 50 |
| Movement functions | 2-opt & 3-opt | |
| Initial A0i | Random number in [0.7, 1.0] | |
| Initial r0i | Random number in [0.0, 0.4] | |
| α & γ | 0.98 | |
| IDGA | Population size | 50 |
| Crossover function | OB & OBX | |
| Mutation functions | Insertion & 3-opt | |
| Cross. prob. | [0.95, 0.9, 0.8, 0.75] | |
| Mut. prob | [0.05, 0.1, 0.2, 0.25] | |
| Selection function | Binary tournament | |
| Survior function | Binary tournament | |
| Migration strat. | Best–Replace–Worst |
DownLoad:
CSV
| Instance | Algorithm | Best | Avg | Re | Time |
| oliver30 | DSSA-PMX | 420 | 420.1 | 0.02% | 0.43 |
| DSSA-OX | 420 | 420.75 | 0.18% | 0.36 | |
| DSSA-PBX | 420 | 420.05 | 0.01% | 0.47 | |
| DSSA-OBX | 420 | 421.1 | 0.26% | 0.41 | |
| DSSA-SEC | 420 | 420 | 0.00% | 0.46 | |
| att48 | DSSA-PMX | 33522 | 33738.3 | 0.65% | 1.63 |
| DSSA-OX | 33522 | 33817.7 | 0.88% | 1.41 | |
| DSSA-PBX | 33522 | 33706.65 | 0.55% | 1.74 | |
| DSSA-OBX | 33522 | 33866.1 | 1.03% | 1.64 | |
| DSSA-SEC | 33522 | 33564.7 | 0.13% | 1.78 | |
| eil51 | DSSA-PMX | 426 | 430.65 | 1.09% | 1.95 |
| DSSA-OX | 426 | 431.8 | 1.36% | 1.70 | |
| DSSA-PBX | 428 | 433.6 | 1.78% | 2.08 | |
| DSSA-OBX | 428 | 435.4 | 2.21% | 1.97 | |
| DSSA-SEC | 426 | 427.55 | 0.36% | 2.04 | |
| berlin52 | DSSA-PMX | 7542 | 7566.5 | 0.32% | 2.07 |
| DSSA-OX | 7542 | 7708.3 | 2.20% | 1.79 | |
| DSSA-PBX | 7542 | 7577.75 | 0.47% | 2.27 | |
| DSSA-OBX | 7542 | 7646.8 | 1.39% | 2.14 | |
| DSSA-SEC | 7542 | 7542 | 0.00% | 2.14 | |
| st70 | DSSA-PMX | 675 | 679.5 | 0.67% | 4.93 |
| DSSA-OX | 675 | 684.35 | 1.39% | 4.48 | |
| DSSA-PBX | 675 | 680.45 | 0.81% | 5.29 | |
| DSSA-OBX | 675 | 684.85 | 1.46% | 5.33 | |
| DSSA-SEC | 675 | 675.05 | 0.01% | 5.29 | |
| eil76 | DSSA-PMX | 541 | 549 | 2.04% | 6.45 |
| DSSA-OX | 542 | 553.3 | 2.84% | 5.82 | |
| DSSA-PBX | 545 | 554.05 | 2.98% | 6.84 | |
| DSSA-OBX | 538 | 555.25 | 3.21% | 6.91 | |
| DSSA-SEC | 538 | 540.5 | 0.46% | 7.02 | |
| pr76 | DSSA-PMX | 108159 | 108479.2 | 0.30% | 6.38 |
| DSSA-OX | 108280 | 109228.9 | 0.99% | 5.79 | |
| DSSA-PBX | 108159 | 109075.8 | 0.85% | 6.77 | |
| DSSA-OBX | 108309 | 109317.6 | 1.07% | 6.83 | |
| DSSA-SEC | 108159 | 108159 | 0.00% | 6.71 | |
| kroA100 | DSSA-PMX | 21282 | 21334.5 | 0.25% | 14.77 |
| DSSA-OX | 21343 | 21714 | 2.03% | 14.31 | |
| DSSA-PBX | 21378 | 21512.55 | 1.08% | 16.31 | |
| DSSA-OBX | 21282 | 21581.35 | 1.41% | 16.90 | |
| DSSA-SEC | 21282 | 21287.8 | 0.03% | 16.08 | |
| kroB100 | DSSA-PMX | 22141 | 22252.2 | 0.50% | 14.83 |
| DSSA-OX | 22283 | 22629.25 | 2.21% | 14.41 | |
| DSSA-PBX | 22141 | 22507.3 | 1.65% | 16.17 | |
| DSSA-OBX | 22258 | 22543.7 | 1.82% | 16.82 | |
| DSSA-SEC | 22141 | 22159 | 0.08% | 15.91 | |
| kroC100 | DSSA-PMX | 20749 | 20835.95 | 0.42% | 14.71 |
| DSSA-OX | 20853 | 21179.15 | 2.07% | 14.43 | |
| DSSA-PBX | 20749 | 20972.65 | 1.08% | 16.89 | |
| DSSA-OBX | 20749 | 21084.1 | 1.62% | 16.85 | |
| DSSA-SEC | 20749 | 20758 | 0.04% | 15.76 | |
| kroD100 | DSSA-PMX | 21294 | 21378.1 | 0.39% | 15.19 |
| DSSA-OX | 21294 | 21742.25 | 2.11% | 14.44 | |
| DSSA-PBX | 21309 | 21744.3 | 2.11% | 16.12 | |
| DSSA-OBX | 21343 | 21684.8 | 1.84% | 17.13 | |
| DSSA-SEC | 21294 | 21323.45 | 0.14% | 15.45 | |
| kroE100 | DSSA-PMX | 22068 | 22192.5 | 0.56% | 15.04 |
| DSSA-OX | 22111 | 22438 | 1.68% | 14.42 | |
| DSSA-PBX | 22117 | 22423.75 | 1.61% | 16.09 | |
| DSSA-OBX | 22068 | 22452.7 | 1.74% | 17.08 | |
| DSSA-SEC | 22068 | 22100.35 | 0.15% | 15.97 | |
| eil101 | DSSA-PMX | 633 | 643.65 | 2.33% | 15.55 |
| DSSA-OX | 635 | 653.55 | 3.90% | 14.89 | |
| DSSA-PBX | 645 | 654.95 | 4.13% | 17.11 | |
| DSSA-OBX | 647 | 655.7 | 4.24% | 17.47 | |
| DSSA-SEC | 629 | 633.95 | 0.79% | 16.87 | |
| lin105 | DSSA-PMX | 14379 | 14430.4 | 0.36% | 17.08 |
| DSSA-OX | 14379 | 14539.95 | 1.12% | 16.85 | |
| DSSA-PBX | 14379 | 14461.35 | 0.57% | 19.24 | |
| DSSA-OBX | 14379 | 14531.85 | 1.06% | 19.95 | |
| DSSA-SEC | 14379 | 14381.2 | 0.02% | 17.90 | |
| pr124 | DSSA-PMX | 59030 | 59080.4 | 0.09% | 28.45 |
| DSSA-OX | 59030 | 59563.4 | 0.90% | 29.50 | |
| DSSA-PBX | 59030 | 59399.75 | 0.63% | 33.46 | |
| DSSA-OBX | 59030 | 59362.8 | 0.56% | 34.25 | |
| DSSA-SEC | 59030 | 59042.15 | 0.02% | 30.52 | |
| pr136 | DSSA-PMX | 96956 | 97529.15 | 0.78% | 40.27 |
| DSSA-OX | 97609 | 99776.55 | 3.10% | 39.50 | |
| DSSA-PBX | 97270 | 98644.85 | 1.94% | 44.66 | |
| DSSA-OBX | 97889 | 99695.8 | 3.02% | 46.27 | |
| DSSA-SEC | 96772 | 97048.7 | 0.29% | 44.97 | |
| kroB150 | DSSA-PMX | 26141 | 26285.75 | 0.60% | 54.36 |
| DSSA-OX | 26324 | 26905.75 | 2.97% | 54.69 | |
| DSSA-PBX | 26246 | 26679.6 | 2.10% | 60.04 | |
| DSSA-OBX | 26411 | 26732.1 | 2.30% | 63.88 | |
| DSSA-SEC | 26130 | 26176.45 | 0.18% | 59.66 | |
| pr152 | DSSA-PMX | 73682 | 73866.4 | 0.25% | 54.95 |
| DSSA-OX | 74373 | 74739.95 | 1.44% | 57.20 | |
| DSSA-PBX | 73818 | 74193.55 | 0.69% | 63.69 | |
| DSSA-OBX | 73888 | 74405 | 0.98% | 64.94 | |
| DSSA-SEC | 73682 | 73763.6 | 0.11% | 60.20 | |
| u159 | DSSA-PMX | 42080 | 42339.7 | 0.62% | 62.77 |
| DSSA-OX | 42535 | 43654.4 | 3.74% | 66.44 | |
| DSSA-PBX | 42080 | 42998.9 | 2.18% | 73.35 | |
| DSSA-OBX | 42080 | 43154.8 | 2.55% | 75.62 | |
| DSSA-SEC | 42080 | 42132.8 | 0.13% | 65.58 |
DownLoad:
CSV
| Rank & p | DSSA-PMX | DSSA-OX | DSSA-PBX | DSSA-OBX | DSSA-SEC |
| rank (Best) | 2.39 | 3.63 | 3.34 | 3.47 | 2.16 |
| p | 5.999E-05 | ||||
| rank (Avg) | 2.11 | 4.37 | 3.21 | 4.32 | 1.00 |
| p | 3.774E-13 | ||||
DownLoad:
CSV
| Fun | Alg | Avg | Best | Re (%) |
Time | Fun | Alg | Avg | Best | Re (%) |
Time |
| oliver 30 |
DSSA | 420 | 420 | 0.00 | 0.5 | eil 101 |
DSSA | 633.95 | 629 | 0.79 | 16.87 |
| DGWO | \ | \ | \ | \ | DGWO | \ | \ | \ | \ | ||
| DFA | 420 | 420 | 0.00 | 0.4 | DFA | 659 | 643 | 4.77 | 13.3 | ||
| DICA | 420 | 420 | 0.00 | 0.5 | DICA | 663.8 | 644 | 5.53 | 12 | ||
| ESA | 420 | 420 | 0.00 | 0.7 | ESA | 658.4 | 650 | 4.67 | 16.3 | ||
| GA | 422.8 | 420 | 0.67 | 0.2 | GA | 673.8 | 655 | 7.12 | 10.6 | ||
| IBA | 420 | 420 | 0.00 | 0.4 | IBA | 646.4 | 634 | 2.77 | 13.1 | ||
| IDGA | 421.5 | 420 | 0.36 | 0.2 | IDGA | 660.7 | 650 | 5.04 | 11.7 | ||
| att 48 |
DSSA | 33564.7 | 33522 | 0.13 | 1.8 | lin 105 |
DSSA | 14381.2 | 14379 | 0.02 | 17.90 |
| DGWO | 33600 | 33523 | 0.23 | 3.0 | DGWO | 14520 | 14382 | 0.98 | 34.3 | ||
| DFA | \ | \ | \ | \ | DFA | \ | \ | \ | \ | ||
| DICA | \ | \ | \ | \ | DICA | \ | \ | \ | \ | ||
| ESA | \ | \ | \ | \ | ESA | \ | \ | \ | \ | ||
| GA | \ | \ | \ | \ | GA | \ | \ | \ | \ | ||
| IBA | \ | \ | \ | \ | IBA | \ | \ | \ | \ | ||
| IDGA | \ | \ | \ | \ | IDGA | \ | \ | \ | \ | ||
| eil 51 |
DSSA | 427.55 | 426 | 0.36 | 2.04 | pr 124 |
DSSA | 59042.15 | 59030 | 0.02 | 30.52 |
| DGWO | \ | \ | \ | \ | DGWO | 59390.9 | 59030 | 0.61 | 44.4 | ||
| DFA | 430.8 | 426 | 1.13 | 1.6 | DFA | 59404.3 | 59030 | 0.63 | 18.8 | ||
| DICA | 432.3 | 426 | 1.48 | 1.8 | DICA | 59436.9 | 59030 | 0.69 | 19 | ||
| ESA | 431.6 | 426 | 1.31 | 2.1 | ESA | 59593.6 | 59030 | 0.95 | 23.1 | ||
| GA | 440.8 | 427 | 3.47 | 1.7 | GA | 59901 | 59030 | 1.48 | 17.3 | ||
| IBA | 428.1 | 426 | 0.49 | 1.7 | IBA | 59412.1 | 59030 | 0.65 | 18.5 | ||
| IDGA | 434.4 | 426 | 1.97 | 1.2 | IDGA | 59912.8 | 59072 | 1.50 | 17.8 | ||
| berlin 52 |
DSSA | 7542 | 7542 | 0.00 | 2.1 | pr 136 |
DSSA | 97048.7 | 96772 | 0.29 | 44.97 |
| DGWO | \ | \ | \ | \ | DGWO | 99310.5 | 97826 | 2.62 | 74.3 | ||
| DFA | 7542 | 7542 | 0.00 | 2.2 | DFA | 99683.7 | 97716 | 3.01 | 24.1 | ||
| DICA | 7542 | 7542 | 0.00 | 2.5 | DICA | 99583.7 | 97736 | 2.91 | 24 | ||
| ESA | 7542 | 7542 | 0.00 | 2.3 | ESA | 99858.3 | 98499 | 3.19 | 29.5 | ||
| GA | 7542 | 7542 | 0.00 | 2.3 | GA | 100472.4 | 98432 | 3.82 | 23.8 | ||
| IBA | 7542 | 7542 | 0.00 | 2.1 | IBA | 99351.2 | 97547 | 2.67 | 23.4 | ||
| IDGA | 7542 | 7542 | 0.00 | 2.4 | IDGA | 99932.7 | 98532 | 3.27 | 23.7 | ||
| st 70 |
DSSA | 675.05 | 675 | 0.01 | 5.3 | krob 150 |
DSSA | 26176.45 | 26130 | 0.18 | 59.66 |
| DGWO | \ | \ | \ | \ | DGWO | 26756.2 | 26320 | 2.39 | 125.2 | ||
| DFA | 685.3 | 675 | 1.53 | 4.3 | DFA | \ | \ | \ | \ | ||
| DICA | 684.7 | 675 | 1.44 | 4.1 | DICA | \ | \ | \ | \ | ||
| ESA | 682.1 | 675 | 1.05 | 4.5 | ESA | \ | \ | \ | \ | ||
| GA | 709.8 | 675 | 5.16 | 4.2 | GA | \ | \ | \ | \ | ||
| IBA | 679.1 | 675 | 0.61 | 3.9 | IBA | \ | \ | \ | \ | ||
| IDGA | 690.2 | 675 | 2.25 | 4.1 | IDGA | \ | \ | \ | \ | ||
| eil 76 |
DSSA | 540.5 | 538 | 0.46 | 7.0 | pr 152 |
DSSA | 73763.6 | 73682 | 0.11 | 60.20 |
| DGWO | \ | \ | \ | \ | DGWO | 74230 | 73690 | 0.74 | 142.8 | ||
| DFA | 556.8 | 543 | 3.49 | 5.3 | DFA | 74934.3 | 74033 | 1.70 | 32.1 | ||
| DICA | 557.6 | 544 | 3.64 | 5.3 | DICA | 74886.7 | 74052 | 1.63 | 32 | ||
| ESA | 553.7 | 546 | 2.92 | 5.8 | ESA | 74969.5 | 74172 | 1.75 | 39.5 | ||
| GA | 565.4 | 545 | 5.09 | 5.6 | GA | 75658.3 | 74520 | 2.68 | 33.4 | ||
| IBA | 548.1 | 539 | 1.88 | 5.1 | IBA | 74676.9 | 73921 | 1.35 | 31 | ||
| IDGA | 557.7 | 545 | 3.66 | 5.1 | IDGA | 75126.7 | 74249 | 1.96 | 32 | ||
| pr 76 |
DSSA | 108159 | 108159 | 0.00 | 6.7 | u159 | DSSA | 42132.8 | 42080 | 0.13 | 65.58 |
| DGWO | 108900 | 108159 | 0.68 | 13.2 | DGWO | 42563.3 | 42142 | 1.14 | 142.8 | ||
| DFA | \ | \ | \ | \ | DFA | \ | \ | \ | \ | ||
| DICA | \ | \ | \ | \ | DICA | \ | \ | \ | \ | ||
| ESA | \ | \ | \ | \ | ESA | \ | \ | \ | \ | ||
| GA | \ | \ | \ | \ | GA | \ | \ | \ | \ | ||
| IBA | \ | \ | \ | \ | IBA | \ | \ | \ | \ | ||
| IDGA | \ | \ | \ | \ | IDGA | \ | \ | \ | \ | ||
| kroA100 | DSSA | 21287.8 | 21282 | 0.03 | 16.1 | pr 226 |
DSSA | 80446.8 | 80369 | 0.10 | 248.4 |
| DGWO | \ | \ | \ | \ | DGWO | 81153.7 | 80648 | 0.95 | 648.6 | ||
| DFA | 21483.6 | 21282 | 0.95 | 10.3 | DFA | \ | \ | \ | \ | ||
| DICA | 21500.3 | 21282 | 1.03 | 10.8 | DICA | \ | \ | \ | \ | ||
| ESA | 21481.7 | 21282 | 0.94 | 14 | ESA | \ | \ | \ | \ | ||
| GA | 21812.4 | 21350 | 2.49 | 9.9 | GA | \ | \ | \ | \ | ||
| IBA | 21445.3 | 21282 | 0.77 | 10.6 | IBA | \ | \ | \ | \ | ||
| IDGA | 21731.8 | 21345 | 2.11 | 10.7 | IDGA | \ | \ | \ | \ | ||
| kroB100 | DSSA | 22159 | 22141 | 0.08 | 15.9 | pr 264 |
DSSA | 49166.15 | 49135 | 0.06 | 422.8 |
| DGWO | 22444.6 | 22159 | 1.37 | 34.5 | DGWO | \ | \ | \ | \ | ||
| DFA | 22604.8 | 22183 | 2.10 | 11.6 | DFA | 51837 | 50491 | 5.50 | 93 | ||
| DICA | 22599.7 | 22180 | 2.08 | 11.3 | DICA | 51943.6 | 50553 | 5.72 | 94.1 | ||
| ESA | 22602.2 | 22202 | 2.09 | 13.6 | ESA | 52198.5 | 51603 | 6.23 | 102.5 | ||
| GA | 22687.4 | 22176 | 2.47 | 10.7 | GA | 52499.8 | 51712 | 6.85 | 92.1 | ||
| IBA | 22506.4 | 22140 | 1.65 | 11.1 | IBA | 50908.3 | 49756 | 3.61 | 92.5 | ||
| IDGA | 22712.6 | 22208 | 2.59 | 10.7 | IDGA | 52290 | 51653 | 6.42 | 94.5 | ||
| kroC100 | DSSA | 20758 | 20749 | 0.04 | 15.8 | pr 299 |
DSSA | 48286.9 | 48191 | 0.20 | 633.7 |
| DGWO | 21780 | 20749 | 1.58 | 34.4 | DGWO | \ | \ | \ | \ | ||
| DFA | 21096.3 | 20756 | 1.67 | 12.8 | DFA | 49839.7 | 48579 | 3.42 | 149.1 | ||
| DICA | 21103.9 | 20756 | 1.71 | 11.7 | DICA | 49880.3 | 48600 | 3.51 | 150.3 | ||
| ESA | 21170.4 | 20749 | 2.03 | 15.4 | ESA | 50532.3 | 49242 | 4.86 | 158.7 | ||
| GA | 21510.4 | 20861 | 3.67 | 10.2 | GA | 50817.1 | 49659 | 5.45 | 147.6 | ||
| IBA | 21050 | 20749 | 1.45 | 12 | IBA | 49674.1 | 48310 | 3.08 | 147.2 | ||
| IDGA | 21298.7 | 20830 | 2.65 | 11.2 | IDGA | 50513.3 | 49572 | 4.82 | 149.94 | ||
| kroD100 | DSSA | 21323.5 | 21294 | 0.14 | 15.5 | pr 439 |
DSSA | 107562.3 | 107217 | 0.32 | 2261 |
| DGWO | \ | \ | \ | \ | DGWO | 112850.3 | 110415 | 5.25 | 2811 | ||
| DFA | 21683.8 | 21408 | 1.83 | 12.4 | DFA | 115558.2 | 111967 | 7.78 | 202.4 | ||
| DICA | 21666.8 | 21399 | 1.75 | 12.6 | DICA | 115763.1 | 111983 | 7.97 | 203.7 | ||
| ESA | 21726.5 | 21500 | 2.03 | 15.9 | ESA | 116706.9 | 113497 | 8.85 | 206.4 | ||
| GA | 22184.6 | 21492 | 4.18 | 9.7 | GA | 116943.4 | 113576 | 9.07 | 208.4 | ||
| IBA | 21593.4 | 21294 | 1.41 | 11.7 | IBA | 115256.4 | 11153 | 7.50 | 201.9 | ||
| IDGA | 21696.9 | 21582 | 1.89 | 12.1 | IDGA | 116436.1 | 113207 | 8.60 | 205.7 | ||
| kroE100 | DSSA | 22100.4 | 22068 | 0.15 | 16 | \ | \ | \ | \ | \ | \ |
| DGWO | 22131 | 22410 | 1.54 | 34.3 | \ | \ | \ | \ | \ | ||
| DFA | 22413 | 22079 | 1.56 | 11.6 | \ | \ | \ | \ | \ | ||
| DICA | 22453.3 | 22083 | 1.75 | 11.7 | \ | \ | \ | \ | \ | ||
| ESA | 22499.7 | 22099 | 1.96 | 15 | \ | \ | \ | \ | \ | ||
| GA | 22741.3 | 22150 | 3.05 | 9.4 | \ | \ | \ | \ | \ | ||
| IBA | 22349.6 | 22068 | 1.28 | 11.4 | \ | \ | \ | \ | \ | ||
| IDGA | 22721.9 | 22110 | 2.96 | 12.6 | \ | \ | \ | \ | \ |
DownLoad:
CSV
| Instance / Algorithms | DSSA | DFA | ESA | IBA |
| oliver30 | 0.89 | 3.38 | 23.91 | 2.17 |
| eil51 | 8.51 | 17.56 | 85.91 | 15.37 |
| berlin52 | 1.99 | 23.68 | 128.26 | 20.07 |
| st70 | 9.82 | 69.56 | 216.08 | 72.67 |
| eil76 | 19.93 | 164.18 | 262.89 | 91.53 |
| kroA100 | 19.24 | 812.56 | 784.84 | 739.86 |
| kroB100 | 20.29 | 813.68 | 729.83 | 461.05 |
| kroC100 | 14.81 | 835.79 | 726.35 | 872.51 |
| KroD100 | 14.81 | 875.74 | 689.49 | 600.31 |
| KroE100 | 20.89 | 843.72 | 791.76 | 602.94 |
| 3il101 | 32.86 | 617.83 | 598.11 | 512.73 |
| pr124 | 16.92 | 1589.71 | 1446.91 | 1602.51 |
| pr136 | 47.04 | 2763.8 | 2318.2 | 2866.6 |
| pr152 | 23.19 | 4769.37 | 3853.91 | 4853.19 |
| pr264 | 47.13 | 6686.39 | 6096.45 | 6375.46 |
| pr299 | 113.26 | 7016.91 | 6731.23 | 6597.94 |
| pr439 | 278.13 | 8736.28 | 8006.91 | 8346.85 |
DownLoad:
CSV
| Instance | Dimension size | Optimal |
| oliver30 | 30 | 420 |
| att48 | 48 | 33522 |
| eil51 | 51 | 426 |
| berlin52 | 52 | 7542 |
| st70 | 70 | 675 |
| eil76 | 76 | 538 |
| pr76 | 76 | 108159 |
| kroA100 | 100 | 21282 |
| kroB100 | 100 | 22141 |
| kroC100 | 100 | 20749 |
| kroD100 | 100 | 21294 |
| kroE100 | 100 | 22068 |
| eil101 | 101 | 629 |
| lin105 | 105 | 14379 |
| pr124 | 124 | 59030 |
| pr136 | 136 | 96772 |
| kroB150 | 150 | 26130 |
| pr152 | 152 | 73682 |
| u159 | 159 | 42080 |
| pr226 | 226 | 80369 |
| pr264 | 264 | 49135 |
| pr299 | 299 | 48191 |
| pr439 | 439 | 107217 |
| Algorithms | Parameters | Values |
| DSSA | Population size | 50 |
| Crossover function | SEC | |
| C1 | ∈ [0.1, 0.9] | |
| DGWO | Population size | 50 |
| Crossover function | 2-opt | |
| ESA | Population size | 50 |
| Successor functions | 2-opt & insertion | |
| Temperature | −supΔf/ln(p) | |
| Cooling constant | 0.95 | |
| GA | Population size | 50 |
| Crossover function | OX | |
| Mutation functions | Insertion & 3-opt | |
| Cross. prob. | 0.95 | |
| Mut. prob | 0.25 | |
| Selection function | Binary tournament | |
| Survior function | Binary tournament | |
| FDA | Population size | 50 |
| Movement functions | 2-opt & 3-opt | |
| Initial A0i | Random number in [0.7, 1.0] | |
| Initial r0i | Random number in [0.0, 0.4] | |
| α & γ | 0.98 | |
| IDGA | Population size | 50 |
| Crossover function | OB & OBX | |
| Mutation functions | Insertion & 3-opt | |
| Cross. prob. | [0.95, 0.9, 0.8, 0.75] | |
| Mut. prob | [0.05, 0.1, 0.2, 0.25] | |
| Selection function | Binary tournament | |
| Survior function | Binary tournament | |
| Migration strat. | Best–Replace–Worst |
| Instance | Algorithm | Best | Avg | Re | Time |
| oliver30 | DSSA-PMX | 420 | 420.1 | 0.02% | 0.43 |
| DSSA-OX | 420 | 420.75 | 0.18% | 0.36 | |
| DSSA-PBX | 420 | 420.05 | 0.01% | 0.47 | |
| DSSA-OBX | 420 | 421.1 | 0.26% | 0.41 | |
| DSSA-SEC | 420 | 420 | 0.00% | 0.46 | |
| att48 | DSSA-PMX | 33522 | 33738.3 | 0.65% | 1.63 |
| DSSA-OX | 33522 | 33817.7 | 0.88% | 1.41 | |
| DSSA-PBX | 33522 | 33706.65 | 0.55% | 1.74 | |
| DSSA-OBX | 33522 | 33866.1 | 1.03% | 1.64 | |
| DSSA-SEC | 33522 | 33564.7 | 0.13% | 1.78 | |
| eil51 | DSSA-PMX | 426 | 430.65 | 1.09% | 1.95 |
| DSSA-OX | 426 | 431.8 | 1.36% | 1.70 | |
| DSSA-PBX | 428 | 433.6 | 1.78% | 2.08 | |
| DSSA-OBX | 428 | 435.4 | 2.21% | 1.97 | |
| DSSA-SEC | 426 | 427.55 | 0.36% | 2.04 | |
| berlin52 | DSSA-PMX | 7542 | 7566.5 | 0.32% | 2.07 |
| DSSA-OX | 7542 | 7708.3 | 2.20% | 1.79 | |
| DSSA-PBX | 7542 | 7577.75 | 0.47% | 2.27 | |
| DSSA-OBX | 7542 | 7646.8 | 1.39% | 2.14 | |
| DSSA-SEC | 7542 | 7542 | 0.00% | 2.14 | |
| st70 | DSSA-PMX | 675 | 679.5 | 0.67% | 4.93 |
| DSSA-OX | 675 | 684.35 | 1.39% | 4.48 | |
| DSSA-PBX | 675 | 680.45 | 0.81% | 5.29 | |
| DSSA-OBX | 675 | 684.85 | 1.46% | 5.33 | |
| DSSA-SEC | 675 | 675.05 | 0.01% | 5.29 | |
| eil76 | DSSA-PMX | 541 | 549 | 2.04% | 6.45 |
| DSSA-OX | 542 | 553.3 | 2.84% | 5.82 | |
| DSSA-PBX | 545 | 554.05 | 2.98% | 6.84 | |
| DSSA-OBX | 538 | 555.25 | 3.21% | 6.91 | |
| DSSA-SEC | 538 | 540.5 | 0.46% | 7.02 | |
| pr76 | DSSA-PMX | 108159 | 108479.2 | 0.30% | 6.38 |
| DSSA-OX | 108280 | 109228.9 | 0.99% | 5.79 | |
| DSSA-PBX | 108159 | 109075.8 | 0.85% | 6.77 | |
| DSSA-OBX | 108309 | 109317.6 | 1.07% | 6.83 | |
| DSSA-SEC | 108159 | 108159 | 0.00% | 6.71 | |
| kroA100 | DSSA-PMX | 21282 | 21334.5 | 0.25% | 14.77 |
| DSSA-OX | 21343 | 21714 | 2.03% | 14.31 | |
| DSSA-PBX | 21378 | 21512.55 | 1.08% | 16.31 | |
| DSSA-OBX | 21282 | 21581.35 | 1.41% | 16.90 | |
| DSSA-SEC | 21282 | 21287.8 | 0.03% | 16.08 | |
| kroB100 | DSSA-PMX | 22141 | 22252.2 | 0.50% | 14.83 |
| DSSA-OX | 22283 | 22629.25 | 2.21% | 14.41 | |
| DSSA-PBX | 22141 | 22507.3 | 1.65% | 16.17 | |
| DSSA-OBX | 22258 | 22543.7 | 1.82% | 16.82 | |
| DSSA-SEC | 22141 | 22159 | 0.08% | 15.91 | |
| kroC100 | DSSA-PMX | 20749 | 20835.95 | 0.42% | 14.71 |
| DSSA-OX | 20853 | 21179.15 | 2.07% | 14.43 | |
| DSSA-PBX | 20749 | 20972.65 | 1.08% | 16.89 | |
| DSSA-OBX | 20749 | 21084.1 | 1.62% | 16.85 | |
| DSSA-SEC | 20749 | 20758 | 0.04% | 15.76 | |
| kroD100 | DSSA-PMX | 21294 | 21378.1 | 0.39% | 15.19 |
| DSSA-OX | 21294 | 21742.25 | 2.11% | 14.44 | |
| DSSA-PBX | 21309 | 21744.3 | 2.11% | 16.12 | |
| DSSA-OBX | 21343 | 21684.8 | 1.84% | 17.13 | |
| DSSA-SEC | 21294 | 21323.45 | 0.14% | 15.45 | |
| kroE100 | DSSA-PMX | 22068 | 22192.5 | 0.56% | 15.04 |
| DSSA-OX | 22111 | 22438 | 1.68% | 14.42 | |
| DSSA-PBX | 22117 | 22423.75 | 1.61% | 16.09 | |
| DSSA-OBX | 22068 | 22452.7 | 1.74% | 17.08 | |
| DSSA-SEC | 22068 | 22100.35 | 0.15% | 15.97 | |
| eil101 | DSSA-PMX | 633 | 643.65 | 2.33% | 15.55 |
| DSSA-OX | 635 | 653.55 | 3.90% | 14.89 | |
| DSSA-PBX | 645 | 654.95 | 4.13% | 17.11 | |
| DSSA-OBX | 647 | 655.7 | 4.24% | 17.47 | |
| DSSA-SEC | 629 | 633.95 | 0.79% | 16.87 | |
| lin105 | DSSA-PMX | 14379 | 14430.4 | 0.36% | 17.08 |
| DSSA-OX | 14379 | 14539.95 | 1.12% | 16.85 | |
| DSSA-PBX | 14379 | 14461.35 | 0.57% | 19.24 | |
| DSSA-OBX | 14379 | 14531.85 | 1.06% | 19.95 | |
| DSSA-SEC | 14379 | 14381.2 | 0.02% | 17.90 | |
| pr124 | DSSA-PMX | 59030 | 59080.4 | 0.09% | 28.45 |
| DSSA-OX | 59030 | 59563.4 | 0.90% | 29.50 | |
| DSSA-PBX | 59030 | 59399.75 | 0.63% | 33.46 | |
| DSSA-OBX | 59030 | 59362.8 | 0.56% | 34.25 | |
| DSSA-SEC | 59030 | 59042.15 | 0.02% | 30.52 | |
| pr136 | DSSA-PMX | 96956 | 97529.15 | 0.78% | 40.27 |
| DSSA-OX | 97609 | 99776.55 | 3.10% | 39.50 | |
| DSSA-PBX | 97270 | 98644.85 | 1.94% | 44.66 | |
| DSSA-OBX | 97889 | 99695.8 | 3.02% | 46.27 | |
| DSSA-SEC | 96772 | 97048.7 | 0.29% | 44.97 | |
| kroB150 | DSSA-PMX | 26141 | 26285.75 | 0.60% | 54.36 |
| DSSA-OX | 26324 | 26905.75 | 2.97% | 54.69 | |
| DSSA-PBX | 26246 | 26679.6 | 2.10% | 60.04 | |
| DSSA-OBX | 26411 | 26732.1 | 2.30% | 63.88 | |
| DSSA-SEC | 26130 | 26176.45 | 0.18% | 59.66 | |
| pr152 | DSSA-PMX | 73682 | 73866.4 | 0.25% | 54.95 |
| DSSA-OX | 74373 | 74739.95 | 1.44% | 57.20 | |
| DSSA-PBX | 73818 | 74193.55 | 0.69% | 63.69 | |
| DSSA-OBX | 73888 | 74405 | 0.98% | 64.94 | |
| DSSA-SEC | 73682 | 73763.6 | 0.11% | 60.20 | |
| u159 | DSSA-PMX | 42080 | 42339.7 | 0.62% | 62.77 |
| DSSA-OX | 42535 | 43654.4 | 3.74% | 66.44 | |
| DSSA-PBX | 42080 | 42998.9 | 2.18% | 73.35 | |
| DSSA-OBX | 42080 | 43154.8 | 2.55% | 75.62 | |
| DSSA-SEC | 42080 | 42132.8 | 0.13% | 65.58 |
| Rank & p | DSSA-PMX | DSSA-OX | DSSA-PBX | DSSA-OBX | DSSA-SEC |
| rank (Best) | 2.39 | 3.63 | 3.34 | 3.47 | 2.16 |
| p | 5.999E-05 | ||||
| rank (Avg) | 2.11 | 4.37 | 3.21 | 4.32 | 1.00 |
| p | 3.774E-13 | ||||
| Fun | Alg | Avg | Best | Re (%) |
Time | Fun | Alg | Avg | Best | Re (%) |
Time |
| oliver 30 |
DSSA | 420 | 420 | 0.00 | 0.5 | eil 101 |
DSSA | 633.95 | 629 | 0.79 | 16.87 |
| DGWO | \ | \ | \ | \ | DGWO | \ | \ | \ | \ | ||
| DFA | 420 | 420 | 0.00 | 0.4 | DFA | 659 | 643 | 4.77 | 13.3 | ||
| DICA | 420 | 420 | 0.00 | 0.5 | DICA | 663.8 | 644 | 5.53 | 12 | ||
| ESA | 420 | 420 | 0.00 | 0.7 | ESA | 658.4 | 650 | 4.67 | 16.3 | ||
| GA | 422.8 | 420 | 0.67 | 0.2 | GA | 673.8 | 655 | 7.12 | 10.6 | ||
| IBA | 420 | 420 | 0.00 | 0.4 | IBA | 646.4 | 634 | 2.77 | 13.1 | ||
| IDGA | 421.5 | 420 | 0.36 | 0.2 | IDGA | 660.7 | 650 | 5.04 | 11.7 | ||
| att 48 |
DSSA | 33564.7 | 33522 | 0.13 | 1.8 | lin 105 |
DSSA | 14381.2 | 14379 | 0.02 | 17.90 |
| DGWO | 33600 | 33523 | 0.23 | 3.0 | DGWO | 14520 | 14382 | 0.98 | 34.3 | ||
| DFA | \ | \ | \ | \ | DFA | \ | \ | \ | \ | ||
| DICA | \ | \ | \ | \ | DICA | \ | \ | \ | \ | ||
| ESA | \ | \ | \ | \ | ESA | \ | \ | \ | \ | ||
| GA | \ | \ | \ | \ | GA | \ | \ | \ | \ | ||
| IBA | \ | \ | \ | \ | IBA | \ | \ | \ | \ | ||
| IDGA | \ | \ | \ | \ | IDGA | \ | \ | \ | \ | ||
| eil 51 |
DSSA | 427.55 | 426 | 0.36 | 2.04 | pr 124 |
DSSA | 59042.15 | 59030 | 0.02 | 30.52 |
| DGWO | \ | \ | \ | \ | DGWO | 59390.9 | 59030 | 0.61 | 44.4 | ||
| DFA | 430.8 | 426 | 1.13 | 1.6 | DFA | 59404.3 | 59030 | 0.63 | 18.8 | ||
| DICA | 432.3 | 426 | 1.48 | 1.8 | DICA | 59436.9 | 59030 | 0.69 | 19 | ||
| ESA | 431.6 | 426 | 1.31 | 2.1 | ESA | 59593.6 | 59030 | 0.95 | 23.1 | ||
| GA | 440.8 | 427 | 3.47 | 1.7 | GA | 59901 | 59030 | 1.48 | 17.3 | ||
| IBA | 428.1 | 426 | 0.49 | 1.7 | IBA | 59412.1 | 59030 | 0.65 | 18.5 | ||
| IDGA | 434.4 | 426 | 1.97 | 1.2 | IDGA | 59912.8 | 59072 | 1.50 | 17.8 | ||
| berlin 52 |
DSSA | 7542 | 7542 | 0.00 | 2.1 | pr 136 |
DSSA | 97048.7 | 96772 | 0.29 | 44.97 |
| DGWO | \ | \ | \ | \ | DGWO | 99310.5 | 97826 | 2.62 | 74.3 | ||
| DFA | 7542 | 7542 | 0.00 | 2.2 | DFA | 99683.7 | 97716 | 3.01 | 24.1 | ||
| DICA | 7542 | 7542 | 0.00 | 2.5 | DICA | 99583.7 | 97736 | 2.91 | 24 | ||
| ESA | 7542 | 7542 | 0.00 | 2.3 | ESA | 99858.3 | 98499 | 3.19 | 29.5 | ||
| GA | 7542 | 7542 | 0.00 | 2.3 | GA | 100472.4 | 98432 | 3.82 | 23.8 | ||
| IBA | 7542 | 7542 | 0.00 | 2.1 | IBA | 99351.2 | 97547 | 2.67 | 23.4 | ||
| IDGA | 7542 | 7542 | 0.00 | 2.4 | IDGA | 99932.7 | 98532 | 3.27 | 23.7 | ||
| st 70 |
DSSA | 675.05 | 675 | 0.01 | 5.3 | krob 150 |
DSSA | 26176.45 | 26130 | 0.18 | 59.66 |
| DGWO | \ | \ | \ | \ | DGWO | 26756.2 | 26320 | 2.39 | 125.2 | ||
| DFA | 685.3 | 675 | 1.53 | 4.3 | DFA | \ | \ | \ | \ | ||
| DICA | 684.7 | 675 | 1.44 | 4.1 | DICA | \ | \ | \ | \ | ||
| ESA | 682.1 | 675 | 1.05 | 4.5 | ESA | \ | \ | \ | \ | ||
| GA | 709.8 | 675 | 5.16 | 4.2 | GA | \ | \ | \ | \ | ||
| IBA | 679.1 | 675 | 0.61 | 3.9 | IBA | \ | \ | \ | \ | ||
| IDGA | 690.2 | 675 | 2.25 | 4.1 | IDGA | \ | \ | \ | \ | ||
| eil 76 |
DSSA | 540.5 | 538 | 0.46 | 7.0 | pr 152 |
DSSA | 73763.6 | 73682 | 0.11 | 60.20 |
| DGWO | \ | \ | \ | \ | DGWO | 74230 | 73690 | 0.74 | 142.8 | ||
| DFA | 556.8 | 543 | 3.49 | 5.3 | DFA | 74934.3 | 74033 | 1.70 | 32.1 | ||
| DICA | 557.6 | 544 | 3.64 | 5.3 | DICA | 74886.7 | 74052 | 1.63 | 32 | ||
| ESA | 553.7 | 546 | 2.92 | 5.8 | ESA | 74969.5 | 74172 | 1.75 | 39.5 | ||
| GA | 565.4 | 545 | 5.09 | 5.6 | GA | 75658.3 | 74520 | 2.68 | 33.4 | ||
| IBA | 548.1 | 539 | 1.88 | 5.1 | IBA | 74676.9 | 73921 | 1.35 | 31 | ||
| IDGA | 557.7 | 545 | 3.66 | 5.1 | IDGA | 75126.7 | 74249 | 1.96 | 32 | ||
| pr 76 |
DSSA | 108159 | 108159 | 0.00 | 6.7 | u159 | DSSA | 42132.8 | 42080 | 0.13 | 65.58 |
| DGWO | 108900 | 108159 | 0.68 | 13.2 | DGWO | 42563.3 | 42142 | 1.14 | 142.8 | ||
| DFA | \ | \ | \ | \ | DFA | \ | \ | \ | \ | ||
| DICA | \ | \ | \ | \ | DICA | \ | \ | \ | \ | ||
| ESA | \ | \ | \ | \ | ESA | \ | \ | \ | \ | ||
| GA | \ | \ | \ | \ | GA | \ | \ | \ | \ | ||
| IBA | \ | \ | \ | \ | IBA | \ | \ | \ | \ | ||
| IDGA | \ | \ | \ | \ | IDGA | \ | \ | \ | \ | ||
| kroA100 | DSSA | 21287.8 | 21282 | 0.03 | 16.1 | pr 226 |
DSSA | 80446.8 | 80369 | 0.10 | 248.4 |
| DGWO | \ | \ | \ | \ | DGWO | 81153.7 | 80648 | 0.95 | 648.6 | ||
| DFA | 21483.6 | 21282 | 0.95 | 10.3 | DFA | \ | \ | \ | \ | ||
| DICA | 21500.3 | 21282 | 1.03 | 10.8 | DICA | \ | \ | \ | \ | ||
| ESA | 21481.7 | 21282 | 0.94 | 14 | ESA | \ | \ | \ | \ | ||
| GA | 21812.4 | 21350 | 2.49 | 9.9 | GA | \ | \ | \ | \ | ||
| IBA | 21445.3 | 21282 | 0.77 | 10.6 | IBA | \ | \ | \ | \ | ||
| IDGA | 21731.8 | 21345 | 2.11 | 10.7 | IDGA | \ | \ | \ | \ | ||
| kroB100 | DSSA | 22159 | 22141 | 0.08 | 15.9 | pr 264 |
DSSA | 49166.15 | 49135 | 0.06 | 422.8 |
| DGWO | 22444.6 | 22159 | 1.37 | 34.5 | DGWO | \ | \ | \ | \ | ||
| DFA | 22604.8 | 22183 | 2.10 | 11.6 | DFA | 51837 | 50491 | 5.50 | 93 | ||
| DICA | 22599.7 | 22180 | 2.08 | 11.3 | DICA | 51943.6 | 50553 | 5.72 | 94.1 | ||
| ESA | 22602.2 | 22202 | 2.09 | 13.6 | ESA | 52198.5 | 51603 | 6.23 | 102.5 | ||
| GA | 22687.4 | 22176 | 2.47 | 10.7 | GA | 52499.8 | 51712 | 6.85 | 92.1 | ||
| IBA | 22506.4 | 22140 | 1.65 | 11.1 | IBA | 50908.3 | 49756 | 3.61 | 92.5 | ||
| IDGA | 22712.6 | 22208 | 2.59 | 10.7 | IDGA | 52290 | 51653 | 6.42 | 94.5 | ||
| kroC100 | DSSA | 20758 | 20749 | 0.04 | 15.8 | pr 299 |
DSSA | 48286.9 | 48191 | 0.20 | 633.7 |
| DGWO | 21780 | 20749 | 1.58 | 34.4 | DGWO | \ | \ | \ | \ | ||
| DFA | 21096.3 | 20756 | 1.67 | 12.8 | DFA | 49839.7 | 48579 | 3.42 | 149.1 | ||
| DICA | 21103.9 | 20756 | 1.71 | 11.7 | DICA | 49880.3 | 48600 | 3.51 | 150.3 | ||
| ESA | 21170.4 | 20749 | 2.03 | 15.4 | ESA | 50532.3 | 49242 | 4.86 | 158.7 | ||
| GA | 21510.4 | 20861 | 3.67 | 10.2 | GA | 50817.1 | 49659 | 5.45 | 147.6 | ||
| IBA | 21050 | 20749 | 1.45 | 12 | IBA | 49674.1 | 48310 | 3.08 | 147.2 | ||
| IDGA | 21298.7 | 20830 | 2.65 | 11.2 | IDGA | 50513.3 | 49572 | 4.82 | 149.94 | ||
| kroD100 | DSSA | 21323.5 | 21294 | 0.14 | 15.5 | pr 439 |
DSSA | 107562.3 | 107217 | 0.32 | 2261 |
| DGWO | \ | \ | \ | \ | DGWO | 112850.3 | 110415 | 5.25 | 2811 | ||
| DFA | 21683.8 | 21408 | 1.83 | 12.4 | DFA | 115558.2 | 111967 | 7.78 | 202.4 | ||
| DICA | 21666.8 | 21399 | 1.75 | 12.6 | DICA | 115763.1 | 111983 | 7.97 | 203.7 | ||
| ESA | 21726.5 | 21500 | 2.03 | 15.9 | ESA | 116706.9 | 113497 | 8.85 | 206.4 | ||
| GA | 22184.6 | 21492 | 4.18 | 9.7 | GA | 116943.4 | 113576 | 9.07 | 208.4 | ||
| IBA | 21593.4 | 21294 | 1.41 | 11.7 | IBA | 115256.4 | 11153 | 7.50 | 201.9 | ||
| IDGA | 21696.9 | 21582 | 1.89 | 12.1 | IDGA | 116436.1 | 113207 | 8.60 | 205.7 | ||
| kroE100 | DSSA | 22100.4 | 22068 | 0.15 | 16 | \ | \ | \ | \ | \ | \ |
| DGWO | 22131 | 22410 | 1.54 | 34.3 | \ | \ | \ | \ | \ | ||
| DFA | 22413 | 22079 | 1.56 | 11.6 | \ | \ | \ | \ | \ | ||
| DICA | 22453.3 | 22083 | 1.75 | 11.7 | \ | \ | \ | \ | \ | ||
| ESA | 22499.7 | 22099 | 1.96 | 15 | \ | \ | \ | \ | \ | ||
| GA | 22741.3 | 22150 | 3.05 | 9.4 | \ | \ | \ | \ | \ | ||
| IBA | 22349.6 | 22068 | 1.28 | 11.4 | \ | \ | \ | \ | \ | ||
| IDGA | 22721.9 | 22110 | 2.96 | 12.6 | \ | \ | \ | \ | \ |
| Instance / Algorithms | DSSA | DFA | ESA | IBA |
| oliver30 | 0.89 | 3.38 | 23.91 | 2.17 |
| eil51 | 8.51 | 17.56 | 85.91 | 15.37 |
| berlin52 | 1.99 | 23.68 | 128.26 | 20.07 |
| st70 | 9.82 | 69.56 | 216.08 | 72.67 |
| eil76 | 19.93 | 164.18 | 262.89 | 91.53 |
| kroA100 | 19.24 | 812.56 | 784.84 | 739.86 |
| kroB100 | 20.29 | 813.68 | 729.83 | 461.05 |
| kroC100 | 14.81 | 835.79 | 726.35 | 872.51 |
| KroD100 | 14.81 | 875.74 | 689.49 | 600.31 |
| KroE100 | 20.89 | 843.72 | 791.76 | 602.94 |
| 3il101 | 32.86 | 617.83 | 598.11 | 512.73 |
| pr124 | 16.92 | 1589.71 | 1446.91 | 1602.51 |
| pr136 | 47.04 | 2763.8 | 2318.2 | 2866.6 |
| pr152 | 23.19 | 4769.37 | 3853.91 | 4853.19 |
| pr264 | 47.13 | 6686.39 | 6096.45 | 6375.46 |
| pr299 | 113.26 | 7016.91 | 6731.23 | 6597.94 |
| pr439 | 278.13 | 8736.28 | 8006.91 | 8346.85 |
