Published: 21 April 2024

Binary rat swarm optimizer algorithm for computing independent domination metric dimension problem

Iqbal M. Batiha1
Basma Mohamed2
1Department of Mathematics, Al Zaytoonah University of Jordan, Amman, 11733, Jordan
1Nonlinear Dynamics Research Center (NDRC), Ajman University, Ajman, 346, United Arab Emirates
2Mathematics and Computer Science Department, Menoufia University, Shebin Elkom, 32511, Egypt
Corresponding Author:
Iqbal M. Batiha
Article in Press
Views 11
Reads 7
Downloads 22

Abstract

In this article, we look at the NP-hard problem of determining the minimum independent domination metric dimension of graphs. A vertex set B of a connected graph G(V,E) resolves G if every vertex of G is uniquely recognized by its vector of distances to the vertices in B. If there are no neighboring vertices in a resolving set B of G, then B is independent. Every vertex of G that does not belong to B must be a neighbor of at least one vertex in B for a resolving set to be dominant. The metric dimension of G, independent metric dimension of G, and independent dominant metric dimension of G are, respectively, the cardinality of the smallest resolving set of G, the minimal independent resolving set, and the minimal independent domination resolving set. We propose the first attempt to use a binary version of the Rat Swarm Optimizer Algorithm (BRSOA) to heuristically calculate the smallest independent dominant resolving set of graphs. The search agent of BRSOA are binary-encoded and used to identify which one of the vertices of the graph belongs to the independent domination resolving set. The feasibility is enforced by repairing search agent such that an additional vertex created from vertices of G is added to B, and this repairing process is repeated until B becomes the independent domination resolving set. Using theoretically computed graph findings and comparisons to competing methods, the proposed BRSOA is put to the test. BRSOA surpasses the binary Grey Wolf Optimizer (BGWO), the binary Particle Swarm Optimizer (BPSO), the binary Whale Optimizer (BWOA), the binary Gravitational Search Algorithm (BGSA), and the binary Moth-Flame Optimization (BMFO), according to computational results and their analysis.

Highlights

  • Recognizing the NP-hard problem of determining the minimum independent domination metric dimension of graphs.
  • Proposing a first attempt to use a binary version of the Rat Swarm Optimizer Algorithm (BRSOA) to heuristically calculate the smallest independent dominant resolving set of graphs.
  • Using theoretically computed graph findings and comparisons to competing methods, the proposed BRSOA is put to the test, which has confirmed its superiority over the binary Grey Wolf Optimizer (BGWO), the binary Particle Swarm Optimizer, the binary Whale Optimizer, the binary Gravitational Search Algorithm, and the binary Moth-Flame Optimization.

1. Introduction

Independent graph dominance numbers have recently been introduced in [1]. Robot navigation [2-4], network discovery and verification [5], localization of wireless sensor networks [6], combinatorial optimization [7], and applications to pharmaceutical chemistry [8] are only a few areas where metric dimension is used. Domination theory is applied in wireless communication networks [9], electrical networks [10], Backbone based routing [11], or spine based routing [12, 13] and chemical structures [14]. The independent domination set with the minimum cardinality is a logical choice for usage in any network type for information transmission.

2. Problem description

Let d(u,v) be the shortest path between two vertices u, vV(G) in the connected graph G=(V, E). If the representation rvB=(d(v, x1), d(v,x2), ... , d(v, xk)) is unique for every vV(G), then the ordered vertex set B={x1,x2,...,xk}V(G) is a resolving set of G. If every vertex of V\B has at least one neighbor that belongs to B, then B is a dominating resolving set of G. A dominating resolving set B is independent if no two vertices in B are adjacent.

Let Card(X) stand for the cardinality of a set X. The metric dimension of G, denoted as dim(G), the domination metric dimension of G, denoted as Ddim(G), and the independent domination metric dimension of G, denoted as γir(G), are as follows:

dim(G)=min{Card(B): B is a resolving set of G},

Ddim(G)=min{Card(B): B is a domination resolving set of G},

γir(G)=min{Card(B): B is an independent dominating resolving set of G}.

Example 2.1. The set B={v2,v4,v6} is a minimal resolving set for the friendship graph Fr7 given in Fig. 1, and hence dim(Fr7)=3. Here, B is also a minimal domination resolving set since every vertex of VB has at least one neighbor that belongs to B. For example, v3 is adjacent to v1and v2. Also, v5 adjacent to v1 and v4. In the same regard, v7 adjacent to v1 and v6. Also, v1adjacent to v2, v3, v4, v5, v6 and v7, and so Ddim(Fr7)=3. On the other hand, B is also independent domination resolving set of Fr7. The set B={v2,v4,v6} is a minimal independent domination resolving set of Fr7, so γir (Fr7)=3.

Fig. 1Friendship graph Fr7

Friendship graph Fr7

Three elements are combined in the independent domination metric dimension problem: independent, dominance, and metric dimension of graphs. Integer programming is used to discuss the difficulty of determining the metric dimension of a graph G [8]. Let D=[dij] be the distance matrix of G, dij=d(vi, vj) for 1i, jn. For xi{0, 1}, 1in, the function F is defined by F(x1,x2,..., xn)=x1+x2+···+xn.

Minimizing F subject to the n2 constraints di1-dj1x1+di2-dj2x2++din-djnxn>0 is equivalent to finding a basis in the sense that if x1', x2',,xn' is a set of values for which F reaches its minimum, for 1i<jn. Then B={vi, xi'=1} is a basis for G and conversely, if B={vi1,vi2,,vin} is a basis for G and if we define:

xs'=1, s=ij, j, 1jk,0, otherwise,

then F(x1',x2',,xn') is a minimum subject to the given constraints.

Both the metric dimension problem and the dominant set problem are NP-complete [15, 16]. As a result, the independent domination metric dimension γir(G) is a typical NP-complete problem that involves determining if γir(G)K for a given graph G and input K. The remaining part of the paper is structured as follows: A literature review is presented in Section 3. In Section 4, the Rat Swarm Optimizer Algorithm is introduced. The BRSOA for calculating the independent domination metric dimension is provided in Section 5. Results of calculations are reported in Section 6. Section 7 presents the conclusion and recommendations for future work.

3. Literature review

For a number of graphs in the literature, the metric dimension, domination metric dimension, and independent domination metric dimension are all theoretically specified. Following is a brief summary of the key recently discovered theoretical metric dimension results [17-25]. The metric dimension of subdivisions of several graphs, including the Lilly graph, the Tadpole graph, and the special trees star tree, bistar tree, and coconut tree is determined theoretically in [17], the bary centric subdivision of Möbius ladders and the generalized Petersen multigraphs in [18], trapezoid network, Z-(Pn) network, open ladder network, tortoise network in [19], French windmill graph and Dutch windmill graph in [20], total graph of path power three and four in [21], two types of bicyclic graphs in [22], Mobius Ladder in [23], power of paths and complement of paths in [24], and Kayak Paddles graph and Cycles with chord in [25].

Theoretically, the independent metric dimensions are identified in [26, 27]. Cartesian product and corona of graphs are determined in [26], finite projective planes, finite biplanes in [27] and Titanium dioxide nanotube in [28]. The independent domination metric dimensions of the path graph, cycle graph, friendship graph, helm graph, and fan graph are determined theoretically in [1]. In [29, 30], the dominant metric dimension is found theoretically. The Path graph, cycle graph, star graph, complete graph, and complete bipartite graph are determined in [29], the corona product graph of G and H is studied whenever H is a path graph, and the cycle graph, complete bipartite graph, complete graph, and star graph are determined in [30]. The connected domination metric dimensions of the complete graph, path graph, and cycle graph are determined theoretically in [31]. To compute the metric dimension problem heuristically, however, only a small number of algorithms have been presented [32-34]. For determining the metric dimension of numerous classes of graph instances, such as pseudo-Boolean, crew scheduling, and graph coloring, a genetic algorithm has been proposed in [32]. A limited number of distinct individuals with the same objective value, the binary representation, frozen gene mutation, and the caching technique were all used. Infeasible individuals are changed by the addition of the required nodes in order to become feasible. In [33], Particle Swarm Optimization is used for determining the metric dimension where an infeasible particle is mended by adding some vertices until the particle becomes feasible and a real-valued vector of vertices is converted to a binary-valued vector using a linear function. The Particle Swarm Optimization is tested by computing the metric dimension of hypercube graphs. In order to enhance the current upper bounds in [34], a variable neighborhood search method has been suggested for tackling metric dimension and minimal doubly resolving set problems. The metric dimension problem and the minimal doubly resolving set problem are divided into a series of sub problems with an auxiliary objective function as the foundation for the variable neighborhood search method. Additionally, the equivalent new integer linear programming formulations for both problems are suggested. The connected domination metric dimension problem is resolved here by encoding and adapting the operations of the equilibrium optimization algorithm. Using theoretically computed graph results, the proposed binary equilibrium optimization algorithm is put to the test and contrasted with competing techniques. Also see more details in the literature [35-38], and some future notions may be applied to some applications like [39-41]. In the binary forms of the metaheuristics, a transfer function plays a crucial role, according to Mirjalili and Lewis in [42]. It has a major effect on both the balance between exploration and exploitation and the avoidance of local optima. In 2013, Sharafi et al. [43] altered the definition of the velocity vector to the probability of mutation in each cat dimension, introduced a transfer function to the tracking mode of the cat swarm algorithm, and converted the continuous cat swarm algorithm into a discrete binary cat swarm algorithm. A binary variant of the bat technique, which is likewise a probability value that uses a transfer function to convert velocity data to updated positions, was proposed by Mirjalili et al. [44] in 2014. A discrete binary bat method (BINBA) was proposed by Sabba and Chikhi [45] in the same year to solve binary space optimization problems.

4. Rat swarm optimizer (RSO) algorithm

4.1. Inspiration

Long-tailed, medium-sized rodents with different sizes and weights include rats. Black rats and brown rats are the two main species of rat. In the family of rats, male rats are referred to as bucks and female rats as does. In general, rats are naturally socially intelligent. They train one another and engage in a variety of sports, including boxing, chasing, jumping, and tumbling. Rats are social, territorial creatures that coexist in households with both males and females. Rats are frequently quite aggressive in their behavior, which may cause the demise of some animals. This work's primary motive for pursuing and fighting with prey is this aggressive behavior. Rat chasing and hunting behaviors are mathematically modeled in this study in order to create the RSO algorithm and carry out optimization.

4.2. Mathematical model and optimization algorithm

This section explains the chasing and fighting behaviors of rats. The suggested RSO algorithm is then described.

4.2.1. Chasing the prey

Rats are typically sociable creatures that hunt their prey in packs using social agonistic behavior. The position of the prey must be known by the optimal search agent in order to mathematically define this behavior. With regard to the best search agent found thus far, the other search agents can update their places. In this mechanism, the following equations are proposed:

1
P=A.Pix+C.Prx-Pix,

where Pix is the best optimal solution and Prx defines the placements of the rats. But here's how the A and C parameters are determined:

2
A=R-x×RMaxIteration,

where x=0,1,2,...,MaxIteration, and:

3
C=2.rand .

Thus, R and C are independent random variables with ranges of [1, 5] and [0, 2], respectively. Over the course of iterations, the parameters A and C lead to better exploration and exploitation.

4.2.2. Fighting with prey

The following equation has been developed to quantitatively define the interaction of rats with prey:

4
Pix+1=Prx-P,

where the revised next position of the rat is defined by Pix+1. It changes other solutions’ positions and saves the best solution and comparing search agents based on which one is the best. The parameters can be changed to obtain a different number of locations relative to the current position, as indicated in Eqs. (2) and (3). But this idea can also be expanded in an n-dimensional setting. As a result, the altered value of parameters A and C ensures exploration and exploitation. The best response is saved using the fewest operators via the suggested RSO technique.

5. Binary rat swarm optimizer algorithm for independent dominant metric dimension

Because it maintains a population of solutions and explores a wide region to find the optimum global solution, the Rat Swarm Optimizer Algorithm can solve difficult optimization problems with several locally optimal solutions. This benefit enables a binary variant of the approach to be applied to the dominant independent metric dimension problem. Using position vectors located within the continuous real domain, search agents can navigate the search space in the continuous form of RSOA. By using an S-shaped transfer function to turn the continuous variable RSOA into a binary one, we may convert it to binary values. Position changes in discrete binary search space necessitate flipping between 0 and 1. The initialization phase makes use of the subsequent equation. Transfer function merits particular consideration and investigation since it plays a significant role in the discrete RSO algorithm:

5
Obinaryij=1, rand()>0.5,0, else,

where rand() refers to a random number between 0 and 1. To convert continuous values to binary ones, a transfer function is used. The sigmoid function (S) is applied as follows in this study:

6
S=11+e-10xd,

where S is the function output and xd denotes the continuous-valued location at dimension d. To create a binary value, use the equation below:

7
SAbinaryij=1, rand<S,0, otherwise.

Table 1Parameter setting with search agents 30 for all algorithms

Algorithms
Parameter name
Value
BRSOA
Number of generations
Control parameter (R)
Constant parameter C
Number of runs
1000
[1, 5]
[0, 2]
20
BWOA
a1
a2
Number of runs
Decreasing from 2 to 0
Decreasing from –1 to –2
20
BPSO
C1
C2
Inertia weight (w)
Number of runs
Increasing linearly from 0.5 to 2.5
Decreasing linearly from 2.5 to 0.5
0.8
20
BGSA
Gravitational constant
Alpha coefficient
100
20
BGWO
Control parameter (a)
[2, 0]
BMFO
Convergence constant
Logarithmic spiral
Number of runs
[−1, −2]
0.75
20

The proposed algorithm deals with the dominant independent resolving set problem as an optimization problem where it searches for the best solution, so each search agent can be represented as a one-dimensional vector SAbinaryij=(SAi1, SAi2,..., SAij), for which SA binaryij is a binary-valued position vector if the j-th element of the vector has a value of 1, it means that vertex j belongs to B. If every vV(G) has a distinct representation r(v|B), then B is an independent dominant resolving set. The value of a binary-valued position vector is produced by computing the value of the S-shaped transfer function. In the BRSOA algorithm, when a search agent is not feasible as an independent dominant resolving set, that search agent is repaired by adding a vertex from V\B. This repair is applied until that object becomes an independent dominant resolving set.

The algorithm represents each solution (individual) in the population as a string of binary in which 1 means that the independent dominant resolving set will be chosen, then the corresponding value will be “1”, and if the independent dominant resolving set is not selected, then the corresponding value will be “0”. The pseudo-code in Algorithm 1.

Table 2Algorithm 1: Pseudo-code of BRSOA

Input: The rat population Pi (i=1,2,,n)
Output: The optimal solution agent
1: Procedure RSOA
2: Initialize the parameters A, C and R
3: Evaluate the initial population and select the one with the best fitness value.
4: Prx The best search agent
5: while (xMaxIteration) do
6: for each search agent do
7: Update the position of current search agent using Eq. (4)
8: Convert each SAi into binary using the S-shaped transfer function in SAbinaryij
9: Calculate the fitness of each SAbinaryij
10: Update the new position of the search agent using Eq. (7)
11: end for
12: Update parameters A, C and R
13: Verify if any search agents exist that extend beyond the specified search space, and then modify them
14: Evaluate the fitness of each search agent
15: Update Prif a better solution becomes available than the previously optimal option
16: Convert each SAi into binary using the S-shaped transfer function in SAbinaryij
17: Calculate the fitness of each SAbinaryij
18: Update the new position of the search agent using Eq. (7)
19: Compare the fitness values of each search agent and choose the best candidate
20: Set x=x+1
21: end while
22: return search agent with best fitness value
23: end procedure

5.1. Experimental results

This section uses theoretically generated graph findings to evaluate the proposed BRSOA. On a path graph, a cycle graph, a fan graph, a ladder graph and a circular ladder graph, the proposed BRSOA is compared to the BWOA, BPSO, BGSA, BGWO and BMFO. The code was implemented in MATLAB 2021b, and the algorithm tests and comparisons were carried out using a Windows 10 Ultimate 64-bit operating system with an Intel Core i7 running at 16 GB of RAM, a 1TBHDD + 1TBSSD hard drive. Table 1 displays the parameter setting values.

All algorithms have been run 20 times for each graph and the results are summarized in Tables 3-6. The tables are organized as follows: The first three columns contain the number of nodes N, the number of edges M, the independent domination resolving number γcr, the CPU time (t) used to indicate the exactly independent domination resolving number and iteration: The average number of iterations for finishing the algorithms to achieve the best solution, respectively.

It should be noted, based on Table 3, that when computing connected domination resolving number for path graph Pn, 4n19, then the BRSOA has reached an optimal solution.

Table 3Comparison between BRSOA, BWOA, BPSO, BGSA, BGWO and BMFO for computing connected domination resolving number for path graph Pn, 4≤n≤19

N
M
γir
t (sec)
Iteration
BRSOA
BWOA
BPSO
BGSA
BGWO
BMFO
4
3
2
16.3
1
2 52.7
2
2
36.4
1
2 24.5
1
2 29.2
1
2 46.7
1
5
4
γir
t (sec)
Iteration
3 35.8
2
3 87.3
8
3 51.9
5
3 31.2
3
3 49.1
4
3
73.5
6
6
5
γir
t (sec)
Iteration
3 58.4 5
3
132.9 22
3
86.1
13
3
72.8 9
3 83.4 11
3 109.6 18
7
6
γir
t (sec)
Iteration
4 83.7 7
4
175.2 35
4
155.9
25
4
126.9 16
4 68.3 19
4 148.1 26
8
7
γir
t (sec)
Iteration
4 105.2 10
4 258.3
47
4 236.3 42
4 178.1 28
4 194.9 32
4 215.4 53
9
8
γir
t (sec)
Iteration
5 121.8 17
5 389.5 69
5 311.6 50
5 202.8 35
5 243.1 41
5 298.3 59
10
9
γir
t (sec)
Iteration
5 156.4 31
5 478.1 78
5 382.2 36
5 274.5 29
5 299.3 56
5 385.9 45
11
10
γir
t (sec)
Iteration
6 194.2 22
6 535.7 93
6 447.8 48
6 351.4 56
6 367.9 75
6 457.4 63
12
11
γir
t (sec)
Iteration
6 229.1 27
6 589.2 71
6 513.1 39
6 415.9 64
6 406.5 47
6 529.3 82
13
12
γir
t (sec)
Iteration
7 283.4 35
7 711.9 105
7 599.5 31
7 501.3 82
7 484.2 63
7 591.7 59
14
13
γir
t (sec)
Iteration
7 372.9 45
7 794.4 93
7 678.4 58
7 604.8 69
7 567.9 108
7 673.5 74
15
14
γir
t (sec)
Iteration
8 307.2 41
8 881.7 62
8 794.5 84
8 647.3 95
8 685.2 81
8 757.9 103
16
15
γir
t (sec)
Iteration
8 356.6 29
8 1013.5 118
8 937.4 95
8 705.9 49
8 779.1 54
8 869.5 73
17
16
γir
t (sec)
Iteration
9 328.5 16
9 1183.9 78
9 1021.8 110
9 802.4 56
9 895.3 64
9 957.3 81
18
17
γir
t (sec)
Iteration
9 411.8 34
9 1357.2 103
9 1109.3 62
9 896.7 78
9 961.5 89
9 1034.6 88
19
18
γir
t (sec)
Iteration
10 443.3 25
10 1562.4 99
10 1239.7 76
10 975.3 62
10 1198.4 70
10 1156.1 91

Table 4Comparison between BRSOA, BWOA, BPSO, BGSA, BGWO and BMFO for computing connected domination resolving number for cycle graph Cn, 4≤n≤15, BRSOA has reached an optimal solution

N
M
γir
t (sec)
Iteration
BRSOA
BWOA
BPSO
BGSA
BGWO
BMFO
4
4
2 25.4
1
2 61.8 3
2 42.7 2
2 32.9 1
2 37.2 1
2 43.5 2
5
5
γir
t (sec)
Iteration
2 34.8 1
2 79.3 7
2 56.2 3
2 48.2 2
2 54.9
2
2 63.6 3
6
6
γir
t (sec)
Iteration
3 61.7 3
3 104.8 19
3 73.8 8
3 59.7 6
3 68.3 9
3 81.4 13
7
7
γir
t (sec)
Iteration
3 80.9 6
3 135.6 42
3 97.5 17
3 91.3 15
3 87.1 23
3 108.7 34
8
8
γir
t (sec)
Iteration
4 104.2 14
4 176.9 56
4 91.7 31
4 118.2 24
4 128.6 38
4 137.9 48
9
9
γir
t (sec)
Iteration
4 129.1 11
4 211.2 73
4 116.4 45
4 173.9 36
4 159.4 24
4 172.1 53
10
10
γir
t (sec)
Iteration
5 146.3 26
5 267.9 109
5 174.8 82
5 198.4
61
5 182.1 49
5 207.2 74
11
11
γir
t (sec)
Iteration
5 188.9 37
5 341.6 81
5 229.4 89
5 224.3 75
5 216.1 56
5 283.9 103
12
12
γir
t (sec)
Iteration
6 207.5 24
6 419.2 134
6 367.8 52
6 268.1 69
6 289.4 48
6 342.6 82
13
13
γir
t (sec)
Iteration
6 173.9 32
6 485.7 159
6 442.9 78
6 309.7 83
6 351.9 72
6 407.2 113
14
14
γir
t (sec)
Iteration
7 228.6 21
7 562.1 183
7 499.5 93
7 375.2 56
7 412.5 54
7 488.1 66
15
15
γir
t (sec)
Iteration
7 294.1 17
7 739.8 201
7 617.3 72
7 476.8 54
7 532.5 69
7
761.4 75

Table 5Comparison between BRSOA, BWOA, BPSO, BGSA, BGWO and BMFO for computing connected domination resolving number for friendship graph Frn, 3≤n≤25, BRSOA has reached an optimal solution

N
M
γir
t (sec)
Iteration
BRSOA
BWOA
BPSO
BGSA
BGWO
BMFO
3
3
1 11.9 1
1 29.6 2
1 18.2 1
1 16.3 1
1 22.4 1
1 32.8 2
5
6
γir
t (sec)
Iteration
2 16.8 1
2 47.9 7
2 35.8 4
2 28.4 3
2 31.9 2
2 46.7 5
7
9
γir
t (sec)
Iteration
3 34.5 6
3 83.1 25
3 72.7 16
3 46.2 7
3 57.8 13
3 89.5 11
9
12
γir
t (sec)
Iteration
4 56.7 9
4 139.8 44
4 96.8 35
4 71.5 16
4 81.9 21
4 127.4 32
11
15
γir
t (sec)
Iteration
5 95.4 16
5 215.3 59
5 83.9 28
5 107.9 25
5 111.3 38
5 185.9 44
13
18
γir
t (sec)
Iteration
6 143.6 28
6 294.1 39
6 154.7 49
6 185.6 42
6 125.4 30
6 248.7 73
15
21
γir
t (sec)
Iteration
7 197.1 43
7 376.9 64
7 236.3 73
7 248.4 32
7 221.8 49
7 367.3 57
17
24
γir
t (sec)
Iteration
8 262.7 36
8 456.3 75
8 298.2 109
8 293.7 58
8 306.7 74
8 433.9 86
19
27
γir
t (sec)
Iteration
9 311.3 21
9 563.9 117
9 374.8 64
9 389.5 70
9 412.5 85
9 524.8 104
21
30
γir
t (sec)
Iteration
10 352.9 28
10 657.4 159
10 458.9 86
10 479.3 55
10 464.9 78
10 561.2 123
23
33
γir
t (sec)
Iteration
11 388.7 19
11 689.5 208
11 534.2 78
11 515.7
67
11 527.2 61
11 598.5 82
25
36
γir
t (sec)
Iteration
12 296.2 14
12 774.8 186
12 592.8 91
12 588.4 45
12 596.3 82
12 634.3 97

Table 6Comparison between BRSOA, BWOA, BPSO, BGSA, BGWO and BMFO for computing connected domination resolving number for triangular snake graph Tn, 3≤n≤31, BRSOA has reached an optimal solution.

N
M
γir
t (sec)
Iteration
BRSOA
BWOA
BPSO
BGSA
BGWO
BMFO
3
3
1 10.5 1
1 26.3 4
1 20.8 2
1 19.6 1
1 27.3 1
1 25.2 3
5
6
γir
t (sec)
Iteration
2 18.2 1
2 63.7 9
2 46.2 3
2 28.4 2
2 31.9 3
2 46.7 6
7
9
γir
t (sec)
Iteration
3 41.4 5
3 99.3 31
3 87.2 15
3 58.9 10
3 74.1 8
3 95.4 19
9
12
γir
t (sec)
Iteration
4 59.8 12
4 161.7 38
4 103.5 25
4 41.6 18
4 91.2 21
4 117.5 32
11
15
γir
t (sec)
Iteration
5 76.3 16
5 208.1 45
5 174.2 41
5 89.3 27
5 124.9 38
5 154.6 50
13
18
γir
t (sec)
Iteration
6 105.9 11
6 246.3 71
6 211.9 62
6 137.6 44
6 192.8 56
6 204.5 78
15
21
γir
t (sec)
Iteration
7 189.3 37
7 297.5 93
7 287.1 51
7 201.8 49
7 274.9 74
7 297.3 86
17
24
γir
t (sec)
Iteration
8 256.4 24
8 406.2 59
8 358.3 45
8 287.9 76
8 326.2 60
8 382.9 147
19
27
γir
t (sec)
Iteration
9 317.8 40
9 485.9 133
9 402.4 49
9 346.3 83
9 398.7 67
9 459.3 95
21
30
γir
t (sec)
Iteration
10 383.6 19
10 517.4 106
10 467.2 208
10 398.2 53
10 456.8 104
10 562.4 203
23
33
γir
t (sec)
Iteration
11 437.9 13
11 593.5 181
11 538.9 169
11 443.9 62
11 523.5 77
11 623.8 122
25
36
γir
t (sec)
Iteration
12 393.2 15
12 649.2 93
12 592.6 103
12 562.8 116
12 587.2 159
12 692.3 181
27
39
γir
t (sec)
Iteration
13 431.8 29
13 737.5 84
13 678.2 178
13 642.7 96
13 675.9 113
13 728.9 79
29
42
γir
t (sec)
Iteration
14 490.3 21
14 821.9 138
14 731.7 217
14 703.5 71
14 765.8 85
14 784.1 193
31
45
γir
t (sec)
Iteration
15 356.9 14
15 879.3 186
15 812.6 204
15 786.9 82
15 807.6 99
15 843.7 161

6. Comparison

To further demonstrate the excellence of proposed BRSOA, we choose BWOA, BPSO, BGSA, BGWO and BMFO algorithms to conduct experiments under the same conditions and compared the results. The results on graphs are shown in Tables 3-6, which indicate that proposed BRSOA algorithm, outperforms other algorithms on graphs, reaching 443.3 sec in BRSOA, 1562.4 sec in BWOA, 1239.7 sec in BPSO, 975.3 sec in BGSA, 1198.4 sec in BGWO, 1156.1 sec in BMFO for path graph and 294.3 sec in BRSOA, 739.8 sec in BWOA, 617.3 sec in BPSO, 476.8 sec in BGSA, 532.5 sec in BGWO and 761.4 sec in BMFO for cycle graph and 296.2 sec in BRSOA, 774.8 sec in BWOA, 592.8 sec in BPSO, 588.4 sec in BGSA, 596.3sec in BGWO, and 634.3 sec in BMFO for friendship graph and 356.9 sec in BRSOA, 879.3 sec in BWOA, 812.6 sec in BPSO, 786.9 sec in BGSA, 807.6 sec in BGWO and 843.7 sec in BMFO for triangular snake graph. It proves the correctness and superiority of proposed BRSOA. Figs. 2, 3, 4 and 5 show the superiority of the proposed BRSOA on the BWOA, BPSO, BGSA, BGWO and BMFO according to the independent domination resolving number.

Fig. 2The superiority of BRSOA on the BWOA, BPSO, BGSA, BGWO and BMFO

The superiority of BRSOA on the BWOA, BPSO, BGSA, BGWO and BMFO

Fig. 3The superiority of BRSOA on the BWOA, BPSO, BGSA, BGWO and BMFO

The superiority of BRSOA on the BWOA, BPSO, BGSA, BGWO and BMFO

Fig. 4The superiority of BRSOA on the BWOA, BPSO, BGSA, BGWO and BMFO

The superiority of BRSOA on the BWOA, BPSO, BGSA, BGWO and BMFO

Fig. 5The superiority of BRSOA on the BWOA, BPSO, BGSA, BGWO and BMFO

The superiority of BRSOA on the BWOA, BPSO, BGSA, BGWO and BMFO

7. Conclusions

In this paper, a binary variant of the basic Rat Swarm Optimizer Algorithm (BRSOA) is adapted for determining the minimum independent domination resolving set of graphs and compared to BWOA, BPSO, BGSA, BGWO and BMFO. Comparisons were performed on the graphs: path graph, cycle graph, friendship graph and triangular snake graph. Experimental results and their analysis confirmed the superiority of the proposed BRSOA for solving the independent domination metric dimension problem. For further work in the future, we plan to compute other variants of metric dimension by other metaheuristic algorithms and compare them with competitive algorithms.

References

  • T. Mazidah, Dafik, Slamin, I. H. Agustin, and R. Nisviasari, “Resolving independent domination number of some special graphs,” in Journal of Physics: Conference Series, Vol. 1832, No. 1, p. 012022, Mar. 2021, https://doi.org/10.1088/1742-6596/1832/1/012022
  • S. Khuller, B. Raghavachari, and A. Rosenfeld, “Landmarks in graphs,” Discrete Applied Mathematics, Vol. 70, No. 3, pp. 217–229, Oct. 1996, https://doi.org/10.1016/0166-218x(95)00106-2
  • R. Manjusha and A. S. Kuriakose, “Metric dimension and uncertainty of traversing robots in a network,” International Journal on Applications of Graph Theory in Wireless Ad Hoc Networks and Sensor Networks, Vol. 7, No. 2/3, pp. 1–9, Sep. 2015, https://doi.org/10.5121/jgraphoc.2015.7301
  • B. Mohamed, “Metric dimension of graphs and its application to robotic navigation,” International Journal of Computer Applications, Vol. 184, No. 15, pp. 1–3, Jun. 2022, https://doi.org/10.5120/ijca2022922090
  • Z. Beerliova et al., “Network discovery and verification,” IEEE Journal on Selected Areas in Communications, Vol. 24, No. 12, pp. 2168–2181, Dec. 2006, https://doi.org/10.1109/jsac.2006.884015
  • M. Idrees, H. Ma, M. Wu, A. R. Nizami, M. Munir, and S. Ali, “Metric dimension of generalized Möbius ladder and its application to WSN localization,” Journal of Advanced Computational Intelligence and Intelligent Informatics, Vol. 24, No. 1, pp. 3–11, Jan. 2020, https://doi.org/10.20965/jaciii.2020.p0003
  • A. Sebő and E. Tannier, “On metric generators of graphs,” Mathematics of Operations Research, Vol. 29, No. 2, pp. 383–393, May 2004, https://doi.org/10.1287/moor.1030.0070
  • G. Chartrand, L. Eroh, M. A. Johnson, and O. R. Oellermann, “Resolvability in graphs and the metric dimension of a graph,” Discrete Applied Mathematics, Vol. 105, No. 1-3, pp. 99–113, Oct. 2000, https://doi.org/10.1016/s0166-218x(00)00198-0
  • J. L. Hurink and T. Nieberg, “Approximating minimum independent dominating sets in wireless networks,” Information Processing Letters, Vol. 109, No. 2, pp. 155–160, Dec. 2008, https://doi.org/10.1016/j.ipl.2008.09.021
  • A. H. Karbasi and R. E. Atani, “Application of dominating sets in wireless sensor networks,” International Journal of Security and Its Applications, Vol. 7, No. 4, pp. 185–202, 2013.
  • B. Das and V. Bharghavan, “Routing in ad-hoc networks using minimum connected dominating sets,” in ICC’97 – International Conference on Communications, Vol. 1, pp. 376–380, Mar. 2024, https://doi.org/10.1109/icc.1997.605303
  • B. Das, R. Sivakumar, and V. Bharghavan, “Routing in ad hoc networks using a spine,” in 6th International Conference on Computer Communications and Networks, pp. 34–39, Nov. 2023, https://doi.org/10.1109/icccn.1997.623288
  • R. Sivakumar, P. Sinha, and V. Bharghavan, “CEDAR: a core-extraction distributed ad hoc routing algorithm,” IEEE Journal on Selected Areas in Communications, Vol. 17, No. 8, pp. 1454–1465, Jan. 1999, https://doi.org/10.1109/49.779926
  • D. Vukičević and A. Klobučar, “K-Dominating sets on linear benzenoids and on the infinite hexagonal grid,” Croatica Chemica Acta, Vol. 80, No. 2, pp. 187–191, Jun. 2007.
  • M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman and Company, 1979.
  • S. Imran et al., “Computing the metric dimension of gear graphs,” Symmetry, Vol. 10, No. 6, p. 209, Jun. 2018, https://doi.org/10.3390/sym10060209
  • B. Mohamed and M. Amin, “The metric dimension of subdivisions of Lilly graph, tadpole graph and special trees,” Applied and Computational Mathematics, Vol. 12, No. 1, pp. 9–14, Mar. 2023, https://doi.org/10.11648/j.acm.20231201.12
  • M. Imran, M. K. Siddiqui, and R. Naeem, “On the metric dimension of generalized Petersen multigraphs,” IEEE Access, Vol. 6, pp. 74328–74338, Jan. 2018, https://doi.org/10.1109/access.2018.2883556
  • B. Mohamed and M. Amin, “Domination number and secure resolving sets in cyclic networks,” Applied and Computational Mathematics, Vol. 12, No. 2, pp. 42–45, May 2023, https://doi.org/10.11648/j.acm.20231202.12
  • P. Singh, S. Sharma, S. K. Sharma, and V. K. Bhat, “Metric dimension and edge metric dimension of windmill graphs,” AIMS Mathematics, Vol. 6, No. 9, pp. 9138–9153, Jan. 2021, https://doi.org/10.3934/math.2021531
  • S. Nawaz, M. Ali, M. A. Khan, and S. Khan, “Computing metric dimension of power of total graph,” IEEE Access, Vol. 9, pp. 74550–74561, Jan. 2021, https://doi.org/10.1109/access.2021.3072554
  • A. Khan, G. Haidar, N. Abbas, M. U. I. Khan, A. U. K. Niazi, and A. U. I. Khan, “Metric dimensions of bicyclic graphs,” Mathematics, Vol. 11, No. 4, p. 869, Feb. 2023, https://doi.org/10.3390/math11040869
  • M. Munir, A. R. Nizami, Z. Iqbal, and H. Saeed, “Metric dimension of the Mobius ladder,” Ars Combinatoria, Vol. 135, pp. 249–256, Oct. 2017.
  • M. M. Alholi, O. A. Abughneim, and H. A. Ezeh, “Metric dimension of some path related graphs,” Global Journal of Pure and Applied Mathematics, Vol. 3, No. 2, pp. 149–157, 2017.
  • A. Ahmad, M. Bača, and S. Sultan, “Computing the metric dimension of kayak paddles graph and cycles with chord,” Proyecciones (Antofagasta), Vol. 39, No. 2, pp. 287–300, Apr. 2020, https://doi.org/10.22199/issn.0717-6279-2020-02-0018
  • B. Suganya and S. Arumugam, “Independent resolving sets in graphs,” AKCE International Journal of Graphs and Combinatorics, Vol. 18, No. 2, pp. 106–109, May 2021, https://doi.org/10.1080/09728600.2021.1963643
  • L. Tang, S. Zhou, J. Chen, and Z. Zhang, “Metric dimension and metric independence number of incidence graphs of symmetric designs,” Discrete Applied Mathematics, Vol. 291, pp. 43–50, Mar. 2021, https://doi.org/10.1016/j.dam.2020.12.001
  • S. Prabhu, T. Flora, and M. Arulperumjothi, “On independent resolving number of TiO2 [m, n] nanotubes,” Journal of Intelligent and Fuzzy Systems, Vol. 35, No. 6, pp. 6421–6425, Dec. 2018, https://doi.org/10.3233/jifs-181314
  • L. Susilowati, I. Sa’Adah, R. Z. Fauziyyah, A. Erfanian, and Slamin, “The dominant metric dimension of graphs,” Heliyon, Vol. 6, No. 3, p. e03633, Mar. 2020, https://doi.org/10.1016/j.heliyon.2020.e03633
  • R. P. Adirasari, H. Suprajitno, and L. Susilowati, “The dominant metric dimension of corona product graphs,” Baghdad Science Journal, Vol. 18, No. 2, pp. 0349–349, Jun. 2021, https://doi.org/10.21123/bsj.2021.18.2.0349
  • Ahmed Mohammed Naji and N. D. Soner, “Resolving connected domination in graphs,” International Journal of Mathematical Combinatorics, Vol. 4, pp. 129–136, Jan. 2015.
  • J. Kratica, V. Kovačević-Vujčić, and M. Čangalović, “Computing the metric dimension of graphs by genetic algorithms,” Computational Optimization and Applications, Vol. 44, No. 2, pp. 343–361, Dec. 2007, https://doi.org/10.1007/s10589-007-9154-5
  • D. T. Murdiansyah and Adiwijaya, “Computing the metric dimension of hypercube graphs by particle swarm optimization algorithms,” in Advances in Intelligent Systems and Computing, pp. 171–178, Dec. 2016, https://doi.org/10.1007/978-3-319-51281-5_18
  • N. Mladenović, J. Kratica, V. Kovačević-Vujčić, and M. Čangalović, “Variable neighborhood search for metric dimension and minimal doubly resolving set problems,” European Journal of Operational Research, Vol. 220, No. 2, pp. 328–337, Jul. 2012, https://doi.org/10.1016/j.ejor.2012.02.019
  • B. Mohamed, L. Mohaisen, and M. Amin, “Binary equilibrium optimization algorithm for computing connected domination metric dimension problem,” Scientific Programming, Vol. 2022, pp. 1–15, Oct. 2022, https://doi.org/10.1155/2022/6076369
  • B. Mohamed, L. Mohaisen, and M. Amin, “Computing connected resolvability of graphs using binary enhanced Harris Hawks optimization,” Intelligent Automation and Soft Computing, Vol. 36, No. 2, pp. 2349–2361, Jan. 2023, https://doi.org/10.32604/iasc.2023.032930
  • B. Mohamed and M. Amin, “A hybrid optimization algorithms for solving metric dimension problem,” International Journal on Applications of Graph Theory in wireless Ad Hoc Networks and Sensor Networks, Vol. 15, No. 1/2, pp. 1–10, Jun. 2023, https://doi.org/10.5121/jgraphoc.2023.15201
  • B. Mohamed, “A comprehensive survey on the metric dimension problem of graphs and its types,” International Journal of Theoretical and Applied Mathematics, Vol. 9, No. 1, pp. 1–5, Jul. 2023, https://doi.org/10.11648/j.ijtam.20230901.11
  • I. M. Batiha, S. A. Njadat, R. M. Batyha, A. Zraiqat, A. Dababneh, and S. Momani, “Design fractional-order PID controllers for single-joint robot arm model,” International Journal of Advances in Soft Computing and its Applications, Vol. 14, No. 2, pp. 97–114, Aug. 2022, https://doi.org/10.15849/ijasca.220720.07
  • H. M. Paiva, W. S. Keller, and L. G. R. Da Cunha, “Blood-glucose regulation using fractional-order PID control,” Journal of Control, Automation and Electrical Systems, Vol. 31, No. 1, pp. 1–9, Dec. 2019, https://doi.org/10.1007/s40313-019-00552-0
  • H. Al-Zoubi, H. Alzaareer, A. Zraiqat, T. Hamadneh, and W. Al-Mashaleh, “On ruled surfaces of coordinate finite type,” WSEAS Transactions on Mathematics, Vol. 21, pp. 765–769, Nov. 2022, https://doi.org/10.37394/23206.2022.21.87
  • S. Mirjalili and A. Lewis, “S-shaped versus V-shaped transfer functions for binary Particle Swarm Optimization,” Swarm and Evolutionary Computation, Vol. 9, pp. 1–14, Apr. 2013, https://doi.org/10.1016/j.swevo.2012.09.002
  • Y. Sharafi, M. A. Khanesar, and M. Teshnehlab, “Discrete binary cat swarm optimization algorithm,” in 2013 3rd IEEE International Conference on Computer, Control and Communication (IC4), pp. 1–6, Sep. 2013, https://doi.org/10.1109/ic4.2013.6653754
  • S. Mirjalili, S. M. Mirjalili, and X.-S. Yang, “Binary bat algorithm,” Neural Computing and Applications, Vol. 25, No. 3-4, pp. 663–681, Dec. 2013, https://doi.org/10.1007/s00521-013-1525-5
  • S. Sabba and S. Chikhi, “A discrete binary version of bat algorithm for multidimensional knapsack problem,” International Journal of Bio-Inspired Computation, Vol. 6, No. 2, p. 140, Jan. 2014, https://doi.org/10.1504/ijbic.2014.060598

About this article

Received
27 February 2024
Accepted
05 April 2024
Published
21 April 2024
Keywords
optimization
metaheuristics
swarm-intelligence
rat swarm optimizer
Acknowledgements

The authors have not disclosed any funding.

Data Availability

The datasets generated during and/or analyzed during the current study are available from the corresponding author on reasonable request.

Author Contributions

Iqbal M. Batiha: conceptualization, methodology, software, validation, formal analysis, investigation data curation. Basma Mohamed: conceptualization, methodology, software, validation, formal analysis, investigation, data curation.

Conflict of interest

The authors declare that they have no conflict of interest.