# Chemical Reaction Optimization for Minimum Weight Dominating Set

Authors: A. Pritam Khan Boni; B. Md. Rafiqul Islam
Journal: Applied Computational Intelligence and Soft Computing
 (2023)

---

## Abstract

Dominating set of a graph can be defined as the set of vertices that can cover all other vertices of the graph. The minimum weight dominating set (MWDS) is the minimum number of vertices in the dominating set with minimum total weight. In recent times, the chemical reaction optimization algorithm (CRO) has shown its supremacy in solving these types of problems. Therefore in this paper, a novel approach based on CRO has been proposed to solve the MWDS problem. The proposed method uses a repair-based technique to generate a molecule. To make the solution feasible by covering all vertices and to get better results, three supporting operators are implemented along with the CRO operators. Besides this, two repair operators are introduced. In the first repair operator, the searching procedure works based on the scaling properties of vertices, and the second one is a unique method for eliminating common neighbors of vertices of the dominating set. The performance of the proposed method is better than any other existing related algorithms. The performance is measured from different graphs of the benchmark datasets. It can be mentioned that the proposed method takes minimal running time to obtain the minimum weight compared to other benchmark methods.


---

## Body

## 1. Introduction

In graph theory, the dominating set of a graph is the set of vertices that are either members or neighbors of the member vertices. If in dominating set the number of vertices is minimum, then it is called the minimum dominating set (MDS). A minimum weight dominating set (MWDS) is a vulgarized version of the minimum dominating set (MDS). Finding the minimum dominating set with the minimum total weight of the vertices can be defined as the MWDS problem. Here, weight is an associated positive value for every vertex of the graph.The MWDS problem is a rising research topic nowadays due to its immense application area. The study of social networks and influence propagation [1], protein interaction networks [2, 3], design of wireless sensor networks [4], and covering codes [5] are the application areas where the concept of MWDS is used. To construct a backbone for ad-hoc wireless networks, Wang et al. [6] proposed a centralized and distributed algorithm for the MWDS problem. On the other hand, to generate an MWDS for a unit disk graph (UDG), a (5 + ϵ)-approximation algorithm was proposed [7]. However, for the MWDS problem, a (4 + ϵ)-approximation dynamic programming algorithm has been suggested, which is an enormous upsurge as the approximation factor for UDG without smooth weights [8]. In short, it can be said that both mathematical and engineering fields have the importance of the study of the MWDS problem. For example, to lessen the number of full wavelength converters in the deployment of wavelength division multiplexing all-optical networks the MWDS problem is used to solve the sparse wavelength converters placement problem [9]. This problem is also indulged in ad-hoc network problems where the nodes have to be determined and intrusion detection software for squandering detection needs to be installed [10]. MWDS problem is also redesigned for web databases to find an optimal query selection plan [11]. However, many approximation algorithms were introduced for special graphs such as UDG problems [7]. However, for general graphs, it is not applicable, as the time complexity of the approximation algorithm is always less than O (lnn) until P=NP [12]. Thus the heuristic algorithm is widely evaluated for solving the MWDS problem to get high-quality solutions. Since the more data will be generated in real-world problems, the more vertices will be in the graph. To cope with these handsome amounts of data in a minimum time metaheuristic algorithm is inexorable.There are various metaheuristic algorithms that are used in different combinatorial optimization-based problems. In recent times, the mixed-variable differential evolution approach [13], the self-learning discrete Jaya algorithm [14], the two-stage cooperative evolutionary algorithm [15], the cooperative water wave optimization algorithm [16], and the cooperative multistage hyper-heuristic algorithm [17] have helped solve many combinatorial optimization-based problems significantly. Using a self-adaptive differential evolution algorithm [18], the batch-processing machine problem has been solved. On the other hand, the self-learning discrete Jaya algorithm [14] has been used in solving the energy-efficient distributed no-idle flow-shop scheduling problem (FSP) in a heterogeneous factory system (HFS-EEDNIFSP). Besides, the no-wait flow-shop scheduling problem is introduced and solved by implementing a two-stage cooperative evolutionary algorithm [15] with problem-specific knowledge. The no-idle flow shop scheduling problem is also solved using a cooperative water wave optimization algorithm [16] that is hybridized with reinforcement learning. The problems solved using these optimization algorithms are mainly combinatorial-based optimization problems. These algorithms show their supremacy in solving these problems effectively.As MDS and MWDS are both defined as NP-hard problems [19, 20], it is quite hard to find a near-optimal solution for large instances in reasonable CPU time [20]. Thus, for getting an optimal solution to the MWDS problem, methods using metaheuristic algorithms are very much effective [21]. Inspired by this knowledge, many researchers suggested metaheuristic algorithms to obtain a better solution. They proposed different approaches based on various metaheuristic algorithms including binary particle swarm optimization (BPSO) algorithm [22], ant colony optimization (ACO) algorithm [23], hybrid ACO-PP-LS algorithm [24], a randomized population-based iterated greedy approach R-PBIG [25], hybrid tabu search algorithm [21], hybrid memetic algorithm (HMA) [26], and hybrid genetic algorithm (HGA) [24]. However, the efficiencies of existing metaheuristic algorithms are still not up to the mark, especially for hard and large-scale instances [27].Although there are many metaheuristic algorithms that were proposed to solve the MWDS problem, here we are proposing an approach based on the chemical reaction optimization (CRO) algorithm. This algorithm has an efficient and effective gain in solving NP-hard problems [28, 29]. The reason behind the dominance of this algorithm is its flexible architecture for both local and global searches, multiple operators, and the ability to work with variables in both discrete and continuous domains. Islam et al. [30] showed these diversified qualities and robustness of the CRO algorithm in their work. CRO was applied to the different optimization problems [28, 29, 31–45]. In the proposed approach, the population is generated using a ranking-based procedure along with the parameter-based random method. Next, the operators of CRO work on the population. Three new operators are applied as the supporting operators along with the CRO operators. To intensify the search, a new repair operator is used on the best solution obtained after CRO. After that, to the improvement of the obtained results, a common neighbor elimination procedure is applied. Contributions to this work are as follows:(1)
For solving the MWDS problem using CRO, the operators of CRO are redesigned to fit especially for this problem.(2)
A novel population generation procedure is introduced where the parameter-based and ranking-based searching procedures are merged. This combination improves the efficiency of searching in the search space.(3)
After population generation, molecule intensification procedure, a novel operator is introduced which can lead to obtaining a better solution.(4)
Along with the four operators of CRO, three supporting operators such as neighborhood search, local search, and redundant vertices elimination procedure, are designed and applied to make the solution feasible and to obtain better results. Among these operators, the concept of neighborhood search operator is unique which helps to find a minimum weighted neighbor.(5)
We have designed a novel repair operator where three properties of nodes are introduced which are uniquely identified to solve the MWDS problem. This operator can find the minimum weighted node with a maximum number of neighbors in minimum time.(6)
In our proposed method another state-of-the-art repair operator is introduced to eliminate common neighbors of the vertices of dominating set. This operator helps to prevent taking similar nodes into the dominating set which are the neighbors of another node of dominating set.The rest of this paper is organized as follows: The recently developed approaches with their pros and cons are described in Section2. Section 3 describes the chemical reaction optimization algorithm. The proposed technique for solving the MWDS problem using the chemical reaction optimization algorithm is explained in Section 4. Section 5 shows the results of the experiments with proper graphical and tabular representations. The conclusion of our work is delineated in Section 6.


### 1.1. Basic Concept

MWDS is a graph-based problem where it can be related to the set-covering problem [46]. According to the MWDS problem, it is a set of vertices of a large graph that are connected with every other vertex of the graph (i.e., covered all vertices of the graph) and the weight of the set of vertices is minimum.LetG = (V, E) be an undirected graph with V=v1,v2,v3,…,vn being the set of vertices and E=e1,e2,e3,…,em being the set of edges. Each edge e=u,v joins two vertices u and v, and these vertices represent the endpoints of e. In order to acquire the smallest dominating set, we must know the neighbor of any vertex and include those vertices with the greatest number of neighbors.The following equations are used to obtain the minimum weight dominating set, whereN [i] denotes the closed neighbor of vertex i (i.e., Ni=Nicupi), D denotes the dominating set and DinV, omega represents the weight of each vertex, and x is the decision variable, which is set to 1 if the vertex is included in the dominating set; otherwise, it is 0 [12]. For getting the minimum weight dominating set, equation (2) is introduced, and equations (3) and (4) have been used as constraints.(1)Tω=∑v∈Dωvxv,(2)Dmω=minTω,(3)∑k∈Nixk≥1,∀i∈D,(4)xv∈0,1.Here,Tω denotes the total weight of the members of the dominating set and Dmω denotes the minimum weight dominating set.Figure1 shows an example of the MDS problem where the graphs are unweighted. Both Figures 1(a) and 1(b) depict the minimum dominating set. As in Figure 1(a), the vertex set v1,v2 is selected where Nv1=v1,v2,v3,v4,v5,v6 and Nv2=v1,v2,v3,v4 and in Figure 1(b) v1,v4 is selected in which Nv1=v1,v2,v3,v4,v5,v6 and Nv4=v1,v2,v3,v4. Though Figure 1(c) denotes a dominating set, it is not a minimum one as in this set three vertices are selected where the set is v4,v5,v6.Figure 1
An example of a minimum dominating set.
(a)(b)(c)Figure2 shows an example of the MWDS problem where the weights of the graphs are introduced. In Figure 2(b) total weight, Tω1 = (14 × 1 + 10 × 1 + 80 × 0 + 60 × 0 + 75 × 0 + 45 × 0 = 24). In Figure 2(a) the dominating set is {v1,v4} and total weight, Tω2 = (14 × 1 + 10 × 0 + 80 × 0 + 60 × 1 + 75 × 0 + 45 × 0 = 74). Now, Dmow = min ω(Tω1, Tω2) = min (24, 74) = 24, so Figure 2(b) shows the minimum weight dominating set.Figure 2
An example of a minimum weight dominating set.
(a)(b)


## 1.1. Basic Concept

MWDS is a graph-based problem where it can be related to the set-covering problem [46]. According to the MWDS problem, it is a set of vertices of a large graph that are connected with every other vertex of the graph (i.e., covered all vertices of the graph) and the weight of the set of vertices is minimum.LetG = (V, E) be an undirected graph with V=v1,v2,v3,…,vn being the set of vertices and E=e1,e2,e3,…,em being the set of edges. Each edge e=u,v joins two vertices u and v, and these vertices represent the endpoints of e. In order to acquire the smallest dominating set, we must know the neighbor of any vertex and include those vertices with the greatest number of neighbors.The following equations are used to obtain the minimum weight dominating set, whereN [i] denotes the closed neighbor of vertex i (i.e., Ni=Nicupi), D denotes the dominating set and DinV, omega represents the weight of each vertex, and x is the decision variable, which is set to 1 if the vertex is included in the dominating set; otherwise, it is 0 [12]. For getting the minimum weight dominating set, equation (2) is introduced, and equations (3) and (4) have been used as constraints.(1)Tω=∑v∈Dωvxv,(2)Dmω=minTω,(3)∑k∈Nixk≥1,∀i∈D,(4)xv∈0,1.Here,Tω denotes the total weight of the members of the dominating set and Dmω denotes the minimum weight dominating set.Figure1 shows an example of the MDS problem where the graphs are unweighted. Both Figures 1(a) and 1(b) depict the minimum dominating set. As in Figure 1(a), the vertex set v1,v2 is selected where Nv1=v1,v2,v3,v4,v5,v6 and Nv2=v1,v2,v3,v4 and in Figure 1(b) v1,v4 is selected in which Nv1=v1,v2,v3,v4,v5,v6 and Nv4=v1,v2,v3,v4. Though Figure 1(c) denotes a dominating set, it is not a minimum one as in this set three vertices are selected where the set is v4,v5,v6.Figure 1
An example of a minimum dominating set.
(a)(b)(c)Figure2 shows an example of the MWDS problem where the weights of the graphs are introduced. In Figure 2(b) total weight, Tω1 = (14 × 1 + 10 × 1 + 80 × 0 + 60 × 0 + 75 × 0 + 45 × 0 = 24). In Figure 2(a) the dominating set is {v1,v4} and total weight, Tω2 = (14 × 1 + 10 × 0 + 80 × 0 + 60 × 1 + 75 × 0 + 45 × 0 = 74). Now, Dmow = min ω(Tω1, Tω2) = min (24, 74) = 24, so Figure 2(b) shows the minimum weight dominating set.Figure 2
An example of a minimum weight dominating set.
(a)(b)


## 2. Literature Review

In recent years, MWDS has demonstrated its importance in addressing a wide range of social data and network-related issues. Many academics have been drawn to it because it is nearly impossible to work with massive amounts of data in a graph if each vertex should always be traversed one by one using an exact algorithm. As a result, researchers presented algorithms that can be divided into two groups to handle this problem; one of them is approximation algorithms, and another is metaheuristic algorithms [22]. According to Alon et al. [12] if P≠NP then set-cover is inapproximable polynomially within a factor c lnn, where c is a constant and 1>rbinc>rbin 0. The MWDS problem is ambiguous with the set-cover problem in polynomial cases [46]. Therefore, it is also inapproximable for the case when P≠NP.However, several researchers focused on redesigning heuristic algorithms to solve general graphs, more precisely the MWDS problem, to acquire optimal solutions. In recent times, to overcome the MWDS problem, Lin et al. [26] presented a hybrid memetic method. Their first step was the formulation of the MWDS problem as a constrained 0-1 programming problem and then transfigured to an equivocal unconstrained 0-1 problem using an adaptive penalty function. A hybrid memetic algorithm (HMA) was used on this resulting unconstrained 0-1 problem to obtain optimal dominating sets. In this hybrid algorithm, they merged the greedy randomized adaptive construction procedure, a tabu local search procedure, a crossover operator, a population updating method, and a path relinking procedure. Their proposed algorithm had a comparison with RAKA-ACO [23], HGA, ACO-LS, and ACO-PP-LS [24], where the computation time was almost six times faster in HMA. However, for different instances, the average objective function values were not optimal in this algorithm.Another algorithm used by researchers to deal with the MWDS problem isCC2FS. Wang et al. [27] proposed a new form of the configuration checking heuristic algorithm called two-level configuration checking CC2, which they paired with a novel scoring function based on the frequency of vertices being uncovered. This hybrid algorithm is named as CC2FS. According to their intended algorithm, the experimental result was quite mesmerizing. In every instance, this algorithm outperformed any other algorithms. However, another newly generated optimization algorithm, as well as some other versions of configuration checking such as strong configuration checking, was not tested on the MWDS problem according to them. On the other hand, they were not sure enough to get good results according to their experiment in larger graphs.Following the sequence of solving the MWDS problem using a variant of metaheuristic algorithms, in 2018, two methods were introduced. One was a Binary Particle Swarm Optimization (BPSO). In this proposed methodology, Lin and Guan [22] redesigned BPSO for the MWDS problem by combining Tabu search, where tabu search was introduced to enhance the solution quality rapidly. They also used stochastic strategies to prevent premature convergence and diversify the search. According to their experimental result, the average CPU time needed for every instance was far less than previously proposed algorithms, though they did not show their solution as the benchmark as in some cases this algorithm cannot find the best solution. Another algorithmic model for solving the MWDS problem initiated in 2018 was an efficient metaheuristic algorithm. In this model, Albuquerque and Vidal [21] suggested a metaheuristic model, whereas metaheuristic refers to algorithms in which metaheuristic algorithms are linked with mixed-integer programming (MIP) strategies and software [47, 48]. According to their suggested architecture, four strategies were combined to reproduce a novel solution. Tabu search had been initiated for searching the efficient neighborhood, and to promote exploration perturbation had been introduced. The method is introduced as a hybrid tabu search metaheuristic (HTS-DS). In their architecture, they used a node elimination procedure which elapsed more CPU time, though according to their experimental result, the CPU time was much less than other proposed systems as well as their suggested methodology outperforms any other previous architecture.At the beginning of 2019, Yuan et al. [49] came up with a fresh architecture using a hybrid algorithm to solve the minimum total dominating set (MTDS) problem. In this proposed architecture, a local search and genetic algorithm have been merged. Score based heuristic algorithm was generated to enhance the search effectiveness and then a repair-based crossover operation was implemented to get viable solutions. Though this algorithm is better for some instances, it cannot help to get a good result for every instance.In 2020, Shetgaonkar and Singh [50] introduced hybridized method using an artificial bee colony algorithm with the estimation of distribution algorithm (ABC-EDA). In this method, they hybridized the algorithms by merging them and used guided mutation as a repair operator. Albeit of the minimum run time, they could not be able to obtain the minimum weight of the dominating set.


## 3. Chemical Reaction Optimization

The inspiration for the chemical reaction optimization algorithm comes from the behavior of chemical reactions. It is a population-based metaheuristic optimization algorithm. The property of a chemical reaction is to transform any unstable molecule into a stable one by a natural process. This process is similar to a step-wise search for optimization problems [51].Like other metaheuristics, the CRO algorithm consists of three stages. They are the initialization, iteration, and termination stages [32]. The initialization stage promotes the initial population besides the parameters such as population size (Pop-Size), kinetic energy loss rate (KElossRate), MoleColl, Buffer, initial kinetic energy (InitialKE), and two thresholds (α and β).The initialization stage begins with the initialization of the different parameters [51]. In the iteration step, one elementary reaction from four runs in each iteration. A random number b between 0 and 1 determines whether the reaction operator is unimolecular or not. If b>rbin MoleColl, there is a unimolecular reaction otherwise, there is a bimolecular reaction. At the end of each iteration, we have to identify the conclusion principle. The last step controls when the conclusion principle of the iteration step is fulfilled. In the final stage, the algorithm aborts, and the premier solution is the outcome.The unimolecular collision has two types of reactions which are on-wall ineffective collision and decomposition. Similarly, the intermolecular collision has two reaction operators, which are intermolecular ineffective collision and synthesis.The molecules in CRO have several parameters, some of which are optional to the basic operations. Table1 depicts the different parameters of CRO.Table 1
Parameters of CRO.
No.SymbolAlgorithmic definition1PopSizeThe number of molecules in a population or simply the population size2KELossRateThe loss rate of kinetic energy (KE) during the reaction3MoleCollA parameter varying between 0 and 1 decides whether the chemical reaction is unimolecular or intermolecular4BufferThe initial energy in the surroundings5InitialKEThe initial energy6α and βTwo parameters controlling the intensification and diversification7Number of hits (NumHit)The total number of hits a molecule has taken8Minimum structure (MinStruct)The molecule structure that has minimum potential energy9MinimumPE (MinPE)When a molecule attains its MinStruct, MinPE is its corresponding PE10Minimum hit number (MinHit)It is the number of hits when a molecule has MinStruct. It is an abstract notation of the time when MinStruct is achieved


## 4. MWDS Using Chemical Reaction Optimization

The chemical reaction optimization algorithm (CRO) is used in this study to get a minimum weighted dominating set. Initial values for different CRO parameters are introduced at the preliminary stage, and populations are produced. Following initialization, one of the four operators is used to begin the iteration process to acquire a better solution from solution space. To attain a better solution, we also used repair operators besides the operators of CRO. The iteration process runs until the termination criteria are met. After termination, the repair operator and integer linear programming (ILP) are used to obtain the further minimum weighted solution. The workflow of the proposed architecture to find the minimum weight dominating set is as follows:(1)
Initially from the data file, the graph structure has evolved and then the initial population has been generated(2)
Molecule intensification procedure has been applied to every molecule of the population to obtain the initial minimum weighted dominating set(3)
Based on the comparison of a random number between 0 and 1 and the parameter value of molecule collision rate (MoleColl), one or more molecule(s) has/have been selected(4)
Based on the condition of decomposition (for a single molecule) or synthesis (for more than one molecule) operator has been chosen and new molecule(s) are found(5)
Local search procedure is applied to the newly found molecule(s) to cover up all the vertices(6)
If the fitness value of generated molecule is better than the original molecule then the original one is replaced with the up-to-date molecule in the population set(7)
Otherwise, the original molecule remains in the population set(8)
Steps 3 to 7 to be repeated till it is unworthy for termination condition(9)
Repair operator is applied on the molecules found from early steps(10)
Common neighbor elimination procedure is applied to eliminate common neighbors of vertices that are the members of dominating set


### 4.1. Generation of Population

The technique of obtaining a feasible solution to the MWDS problem from search space can be divided into three approaches. These approaches are penalty-based procedure [21], preserving-based approach [24], and repair-based approach [49]. From these three approaches to obtain the feasible population, repair based approach is initiated in our proposed method. The technique of generating a molecule is divided into three distinct stages. The first stage of this technique is to obtain a feasible solution based on the cost of the node and the second one is to obtain a feasible solution based on the weight of the node and the degree of the node. Finally, the solutions of both of these stages are merged. This merging process occurs based on the similarity between taken nodes. If the nodes are taken in both solutions then the nodes are kept as the member of the dominating set.The representation of a solution (molecule) in our proposed architecture is based on 0 and 1. If any vertex is taken as the member of dominating set, then in the molecule, it is represented by the value 1 and reported as an active node. Otherwise, the value with 0 is represented as an inactive node. Figure3 shows the molecule representation.Figure 3
Example of a molecule.The final feasible molecule according to the representation in Figure3 is generated after processing three stages of molecule generation which are the initial stage, middle stage, and final stage. The population set is generated by the iteration of this process twenty times as the taken population size of this work is twenty.


#### 4.1.1. Initial Stage

Primarily, the vertices with minimum weight are considered by comparing cost with a specific value with the help of randomness. If the cost of any vertex is less than the difference between the average costμ and the product of epsilon ∈ and the standard deviation σ of the cost then the vertex is selected randomly. Here, epsilon ∈ is a new parameter that is introduced in the initial stage of the population generation method to obtain better random molecules for further operation. The cost is calculated as follows:(5)ci=ωidi.Here,ci, ωi, and di refer to the cost, weight, and degree of vertex i, respectively.After this procedure, to make the solution feasible by covering all vertices and reducing search space, the properties of vertices are checked. The vertex of minimum weight and maximum uncovered neighbors properties is the highly prioritized vertex to count as the member of dominating set. The priority of the vertex depends on the probability score, which is calculated as follows:(6)Pi=PCi∑j∈NiPCjHere,Pi refers to the probability score and PCi denotes the probable cost of vertex i. PCj is the probable cost of neighboring vertices of vertex i. The probability cost of vertex i is determined as follows:(7)PCi=di×∑j∈Niωjωi.After the initial process to cover up the uncovered nodes, priority-based nodes are selected randomly from the first 30% of highly prioritized nodes if the ratio of the number of vertices and the number of edges is greater than the constant value of 0.3. Otherwise, the nodes are selected based on the percentage of the ratio. For example, if there is a sample graph with 500 vertices and 20000 edges, then the ratio is500/20000=0.025. According to the delineation of the process, the active nodes are chosen from the first 2.5% of highly prioritized nodes. After the selection process, the highly dominating nodes are considered active nodes. Despite selecting highly dominating nodes, it cannot be able to cover all the nodes. Again, to find a feasible solution, the nodes that are not covered are picked as spared nodes and put in a list. From this list, active nodes are selected randomly until all nodes are covered. Algorithm 1 shows the initial stage of the population generation procedure.Algorithm 1: The initial stage of population generation.
Input: properties of graphs.Output: feasible solution.(1)
M⟵∅(2)
fori⟵0to lenVdo(3)
ifci<μ−ϵ×σand random value ≥ 0.5 then(4)
Mi⟵1(5)
end(6)
else(7)
Mi⟵0(8)
end(9)
end(10)
Calculate the probability score using equation (6)(11)
Select high prioritized node based on the probability score(12)
Create a list of spared nodes(13)
Select nodes from spared nodes until all nodes are covered


#### 4.1.2. Middle Stage

In this stage, to minimize the computational time for large graphs we check for the node with zero, one, and two degrees. The node with zero degree means the node is not connected with any other nodes and automatically will be the member of dominating set. The node with degree one means the node is connected with only one neighbor. Hence from these two nodes which one is minimum weighted is taken as the member of dominating set. The node with two degrees is referred to as the triangle node. These types of the node have two neighbors. From these three nodes, one node is selected as the member of dominating set based on weight. The minimum weighted node is taken as the dominating member. To take the node into dominating set the property of neighbors are also checked to determine whether the neighbor nodes are the member of dominating set or not. Let,q, r and p are three nodes and q,r∈Np and p is the node with minimum weight, so, if D is the dominating set, D′ is the dominated set and p∉D′ then, p∈D. These nodes are taken in a molecule as a permanent node.After accomplishing this procedure there are some nodes to be covered that still remain uncovered. From the list of the uncovered nodes, the size of common nodes is checked which technique helps to find the nodes that can cover the maximum number of nodes. If for all of the uncovered nodes the total number of uncovered neighbor nodes is one then the node with minimum weight is taken as the member of dominating set. After this process, if any of the nodes remains uncovered then the neighbor node with a minimum weight of the uncovered node is taken as the member of the dominating set. Algorithm2 shows the initial stage of the population generation procedure.Algorithm 2: The second stage of population generation.
Input: properties of graphs.Output: feasible solution.(1)
M⟵∅(2)
Add nodes with zero degree, one degree, and two degrees as active nodes into M.(3)
foruc≠∅do//uc refers to the list of uncovered nodes(4)
forvi∈ucdo(5)
cn⟵Nvi∩uc; //cn refers to the list of common nodes between the neighbor node of vi and the list of uncovered nodes(6)
ifcn≠∅then(7)
pn⟵vi; //pn is the probable member of dominating set(8)
cnl⟵cn; //cn is the list of the common node(9)
Len⟵lencn(10)
end(11)
else(12)
Continue(13)
end(14)
end(15)
ifLen≠∅then(16)
ML⟵maxLen; //ML is the maximum size from all the common nodes’ size(17)
ifML>1then(18)
Mvm⟵1; //vm is the node that can cover the maximum number of uncovered nodes(19)
end(20)
else(21)
ifωi>ωNithen(22)
Mvi⟵1(23)
end(24)
else(25)
MvNi⟵1(26)
end(27)
end(28)
end(29)
else(30)
Find uncovered nodes.(31)
Find the minimum weighted nodevmin associated with uncovered nodes.(32)
Mvmin⟵1(33)
end(34)
end


#### 4.1.3. Final Stage

In this stage, two different techniques of generating molecules are merged together to obtain feasible molecules for searching using CRO. The nodes which are common in both molecules are considered active nodes. This procedure can make the molecule infeasible. To make this molecule feasible, a local search procedure has been applied and finally, the molecule is prepared for deployment in the searching paradigm. The whole process from the initial stage to the final stage works twenty times to generate twenty different molecules as members of the population.


### 4.2. Molecule Intensification Procedure

After generating molecules, to intensify searching, a molecule intensification procedure is introduced. Every molecule has gone through this procedure to find the optimal or best solution so far. This procedure is also a ranking-based system of the nodes. After the production of the molecules, some nodes are the neighbors of the neighbors, of active nodes. Initially, they are not considered active nodes deliberately. However, there is some chance to get an optimal solution or intensified searching space for taking those nodes. For the selection of the nodes for which the molecules will be optimal, the molecules have been made infeasible intentionally by removing active nodes, which are low-ranked based on equation (7). The size of the neighbors of each node is counted based on the list of low-ranked nodes. Then for each node, the cost is calculated as follows: (8)ci=LNCNiωi.Here,ci refers to cost, and LNCNi refers to the length of the uncovered neighbors of the vertex i from the low-ranked list. From these vertices, the cost with the maximum value is selected as active nodes. This process is iterated till all the vertices are covered.


### 4.3. Operator Design

In the proposed method, four operators of CRO and three supportive operators have been designed to solve the MWDS problem. The delineation of operators is as in the following subsections.


#### 4.3.1. Neighborhood Search Operator

A small amount of change occurs due to the reaction of both on-wall ineffective collision and intermolecular ineffective collision, which is similar to the local search of any other evolutionary algorithms. The inspiration for the neighborhood search operator comes from this concept. In this operator, the neighbor node with minimum weight has been searched from any active nodes. An active node is picked randomly, and the searching occurs among all neighbor nodes inclusive of the active node for the lowest weight. If the active node is not the lowest weighted, then the lowest-weighted neighbor is activated, the active node becomes deactivated, and the process terminates. Otherwise, the same procedure occurs to find another active node randomly. This process runs until obtaining a molecule different from the given one. The final termination occurs due to the unavailability of any new node after checking all active nodes. Algorithm3 shows the neighborhood search procedure.Algorithm 3: Neighborhood search.
Input: one molecule, MOutput: updated molecule, M′(1)
Count total active nodesTn(2)
total search,Sn⟵0(3)
whileTruedo(4)
An active nodeVi has been chosen randomly from the molecule(5)
ωmin⟵ωi(6)
Vprev⟵Vi for j∈Nido(7)
ifωj<ωminthen(8)
ωmin⟵ωjVtaken⟵Vj(9)
end(10)
end(11)
Sn⟵Sn+1(12)
ifVprev≠Vtakenthen(13)
M′taken⟵1(14)
M′prev⟵0(15)
break(16)
end(17)
ifTn = Snthen(18)
break(19)
end(20)
else(21)
continue(22)
end(23)
endFigure4 depicts the search procedure of the neighborhood search operator.Figure 4
Illustration of a neighborhood search operator.


#### 4.3.2. Local Search Procedure

After using neighborhood search on on-wall ineffective collision, intermolecular ineffective collision, decomposition, or synthesis, some vertices of a molecule can be uncovered, and the solution becomes infeasible. To make the solution feasible by covering all the uncovered vertices, a technique suggested by Potluri and Singh [24] has been used in our method. They proposed four greedy approaches for searching a node from the set of vertices. From these four approaches, the assimilation of the fourth approach occurs in our system due to its better performance than the other three approaches. The greedy approach follows the following equation to calculate the value of a vertex vi:(9)gi=di×∑j∈Niωjωi.Here,∑j∈Niωj denotes the summation of all uncovered neighbors of a single vertex vi, ωi represents the weight, and di is the degree of vi.The calculation of greedy values of every uncovered vertex takes place by using equation (9). Then a vertex is activated if gi≥δ×maxgi;∀vi∈NC. Here, NC represents the set of uncovered vertices, and δ is a controlling parameter for obtaining a better vertex. The procedure runs until all vertices are covered. Algorithm 4 shows the local search procedure.Algorithm 4: Local search.
Input: infeasible molecule, MOutput: feasible molecule, M′(1)
whileNC≠∅do(2)
Calculate the greedy value forvi∈NC(3)
gall⟵greedy values of vi∈NC(4)
gmax⟵maxgi(5)
forgv∈galldo(6)
ifgv≥δ×gmaxthen(7)
M′gv⟵1(8)
break(9)
end(10)
else(11)
continue(12)
end(13)
end(14)
Check for uncovered vertices(15)
updateNC(16)
end


#### 4.3.3. Redundant Vertices Elimination

If any vertexvi is a member of dominating set and all of its neighbors inclusive of the vertex are the neighbors of one or more members of dominating set, then the vertex is defined as the redundant vertex. Removal of redundant vertices can minimize the total weight of the dominating set. Thus the redundant vertices with maximum weights have been removed from the molecule to obtain the minimum weighted solution. If R is a set of redundant vertices where vi∈R and ωi is maximum, then vi is removed from the molecule, and then further redundant vertices are checked and removed. This process runs until the removal of all the redundant vertices. The procedure for eliminating redundant vertices has been shown in Algorithm 5.Algorithm 5: Redundant vertices elimination.
Input: molecule, MOutput: updated molecule, M′(1)
whileR≠∅do(2)
ωmax⟵0(3)
veliminate⟵0(4)
forrv∈Rdo(5)
ifωmax<ωrvthen(6)
ωmax⟵ωrv(7)
veliminate⟵rv(8)
end(9)
else(10)
continue(11)
end(12)
end(13)
M′⟵0 Check for redundant vertices(14)
updateR(15)
end


#### 4.3.4. On-Wall Ineffective Collision

It is a unimolecular reaction. So in this operator, initially, a molecule has been selected randomly. Then the molecule is modified to generate a new optimal molecule. Primarily, a random selection of a position from the molecule takes place for propagating the latest molecule. If the node of the randomly selected position is active, then the position changes according to the neighborhood search operator. Otherwise, the inactive node becomes active. Finally, for any uncovered nodes, the nodes are covered using the local search procedure. Likewise, for any redundant nodes, the redundant vertices elimination procedure takes place to eradicate redundancy. Figure5 depicts the MWDS problem’s on-wall ineffective collision, where M denotes the molecule (i.e., solution) and M′ denotes the newly created molecule after applying both neighborhood and local search. The procedure of on-wall ineffective collision is shown in Algorithm 6.Figure 5
Illustration of on-wall ineffective collision.Algorithm 6: On-wall ineffective collision.
Input: one molecule, MOutput: updated molecule, M′(1)
CopyM to M′(2)
Randomly select a positioni from M′(3)
ifM′i=1then(4)
Run neighborhood search operator(5)
end(6)
else(7)
M′i⟵1(8)
end(9)
Run the local search.(10)
Run redundant vertices elimination.


#### 4.3.5. Decomposition

It is also a unimolecular reaction where the molecule can be divided into two or more. To find a better solution for the MWDS problem, the search happens in the search space according to this reaction by dividing the parent molecule into two. Both two new molecules inherit a portion from the parent molecule. The parent molecule is divided from the middle. Then the first portion of the parent molecule becomes the first portion of the first child molecule, and the other portion of the parent molecule becomes the last portion of another child molecule. Then for both molecules, uncovered vertices are covered using a local search procedure. Figure6 shows the decomposition procedure. Here, in the first child molecule M1′, the first portion is similar to the first portion of the parent molecule, and in the second child molecule M2′, the last portion is the same as the last portion of the parent molecule. Algorithm 7 depicts the working procedure of decomposition.Figure 6
Illustration of decomposition.Algorithm 7: Decomposition.
Input: one molecule, MOutput: updated molecules, M1′ and M2′(1)
fori⟵0to lenV/2 do(2)
M1′i⟵Mi(3)
end(4)
Run a local search onM1′(5)
fori⟵lenV/2 to lenVdo(6)
M2′i⟵Mi(7)
end(8)
Run the local search onM2′


#### 4.3.6. Intermolecular Ineffective Collision

It is a multimolecular reaction operator where two or more parent molecules can react with each other and generate new molecule(s) where the change in the new molecule is little. This operator searches locally in search space such as the on-wall ineffective collision. In the proposed method, two molecules are used to generate new molecules by implementing this operator. A single position (i.e., vertex) from both parent molecules is considered randomly. Then the values from both positions are interchanged in child molecules. Then uncovered nodes are covered, and redundant vertices are removed from both child molecules. Figure7 depicts the intermolecular ineffective collision where M1 and M2 are the parent molecules and M1′ and M2′ are denoted as child molecules. Algorithm 8 shows the working procedure of intermolecular ineffective collision.Figure 7
Illustration of intermolecular ineffective collision.Algorithm 8: Intermolecular ineffective collision.
Input: two molecules, M1 and M2Output: updated molecules, M1′ and M2′(1)
CopyM1 to M1′(2)
CopyM2 to M2′(3)
Select a vertexvi from M1 randomly(4)
Select a vertexvj from M2 randomly(5)
M1′i⟵M2j(6)
M2′j⟵M1i(7)
Run a local search onM1′(8)
Run redundant vertices elimination onM1′(9)
Run the local search onM2′(10)
Run redundant vertices elimination onM2′


#### 4.3.7. Synthesis

It is also a multimolecular reaction operator. In this operator, the amalgamation of two molecules generates a child molecule to obtain a better offspring. Let, there are two moleculesM1 and M2 in the population set. If any vertex in both parent molecules is active, then the vertex remains active in the child molecule M′. Other vertices of the child molecule become inactive. Then local search procedure is applied to the child molecule to obtain a feasible solution. Figure 8 shows the illustration of the synthesis reaction, and Algorithm 9 depicts the working procedure of synthesis.Figure 8
Illustration of synthesis.Algorithm 9: Synthesis.
Input: two molecules, M1 and M2Output: updated molecule, M′(1)
fori⟵0to lenVdo(2)
ifM1i=1 and M2i=1then(3)
M′i⟵1(4)
end(5)
else(6)
M′i⟵0(7)
end(8)
end(9)
Run the local search onM′


### 4.4. Operator Selection

Some comparisons occur to select one of the four operators of CRO for the MWDS problem. The intermolecular collision occurred based on the comparison between a random value and MoleColl. If the random value between 0 and 1 is less than MoleColl, then the collision is unimolecular. Otherwise, the reaction is intermolecular. If it is unimolecular, then the collision can be an on-wall ineffective collision or decomposition. The decision of on-wall or decomposition reaction comes from the following equation.(10)hit_diff>α.Here,hit_diff refers hit difference of the selected molecule. If equation (10) is satisfied, decomposition occurs. Otherwise, we get an on-wall ineffective collision. In the same manner, synthesis or intermolecular ineffective reaction can occur if the random value is greater than the value of MoleColl. The decision of synthesis or intermolecular ineffective reaction is taken based on the following equation:(11)KE≤β.Here, KE is the kinetic energy of the molecule. If the kinetic energy of all molecules is less than or equal toβ, then synthesis occurs. Otherwise, the reaction is an intermolecular ineffective collision. To get rid of the local minima synthesis is triggered based on the parameter values.By following this approach, better offspring is found in which the number of vertices is minimum. Then using the repair operator and ILP, the offspring is checked for a better solution. If the offspring is better than the previous one then the candidate solution is updated, and the vertices of the candidate solution are taken as the member of the minimum weighted dominating set.The reaction operators of CRO for the MWDS problem have been triggered based on the parameter values of Table2, and an optimal solution has been obtained. The proposed flowchart of the CRO algorithm of the MWDS problem is shown in Figure 9.Table 2
Initialization of parameters for proposed MWDS_CRO algorithm.
ParametersInitialized valuesEpsilonϵ0.9Deltaδ1.45Total iteration100Initial population size20KELossRate0.1MoleColl0.1Energy buffer0Hit_diff0Alphaα10000Betaβ1000Kinetic energy (KE)100Figure 9
Flowchart of CRO for MWDS problem.


### 4.5. Repair Operator

After using CRO operators with other supporting operators, there are some operations to obtain a better solution from the search space. As in the local search procedure, minimum weighted nodes are bound to inherit the solution; the search space is confined and cannot search for a further better solution. Alongside this drawback, there is another pitfall. In previous searching procedures, the properties of nodes are not updated after including the best node. Thus nodes are included every time by using old properties. For example, let a vertexv1 is taken as the best active node in the solution and the neighbors of v1 are v6, v8, and v9. If v8 be the second-best node with the highest greedy value then this node is taken as the active node in the solution. But as v8 is already dominated by v1, by eliminating this, a better solution can be obtained.To get rid of the aforementioned problems, a new repair operator has been proposed in our method with some other properties of nodes. As the feasible solution has been obtained from the CRO operators to apply repair operator on the solution, the solution is converted into an infeasible solution by uncovering some vertices. Forty percent (40%) of vertices with maximum weights from the dominating set are removed intentionally to make the infeasible solution. Then to find the better solution vertices are searched based on three properties. The properties of a vertexvi are the weight of the vertex, uncovered neighbors of the vertex, and the ratio of weight and uncovered neighbor nodes. Then these properties are scaled based on minimum or maximum values of corresponding properties according to the following equations: (12)–(14).(12)Sωi=ωminωi.(13)SNCNi=NCNiNCNmax,(14)Sri=rminri.Here,ωi refers to the weight of the uncovered node vi and ωmin is the node with minimum weight from all uncovered nodes. S represents the scaled property, NCNi represents the number of total uncovered neighbors of the node vi, and NCNmax represents the maximum number of all uncovered neighbors. The ratio ri of the node vi is calculated as follows:(15)ri=ωiNCNi.All these three properties of a vertex are considered by combining these properties. To make the solution feasible based on these properties, if any vertex has two or more uncovered neighbors, the vertex with the maximum aggregated value of the properties is selected as an active vertex. Otherwise, the vertex is selected as active based on weight. If the weight is minimum then the vertex becomes active. This procedure terminates when all the vertices are covered. The operator can find the minimum weighted node with the maximum number of neighbor nodes which helps obtain a better solution in minimal time.Figure10 shows the procedure of the repair operator. Let after using all of the previous operators on the graph of Figure 10 the selected nodes are 1, 3, and 6 and the dominating set is 1,3,6. The weights of these three nodes are 6, 12, and 5 and the total weight is 23. As the nodes with maximum weights are removed, nodes 1 and 3 are removed from the dominating set and 6 remains in the dominating set. Now, three properties of uncovered nodes are checked. After removing nodes 1 and 3, nodes 1, 2, 3, and 5 become uncovered. The weights of these four nodes are 6, 10, 12, and 5, and the total number of uncovered neighbors of these four nodes are 1, 2, 2, and 1. Here, from the four uncovered nodes, the minimum weight is 5, and the maximum number of uncovered neighbors is 2. Now according to equation (12), the values of nodes 1, 2, 3, and 5 are 5/6=0.83, 5/10=0.5, 5/12=0.417, and 5/5=1. According to equation (13), the values of nodes 1, 2, 3, and 5 are 1/2=0.5, 2/2=1, 2/2=1, and 1/2=0.5 =. The ratios according to equation (15) are 6/1=6, 10/2=5, 12/2=6, and 5/1=5. According to equation (14), the values of nodes 1, 2, 3, and 5 are 5/6=0.83, 5/5=1, 5/6=0.833, and 5/5=1. The combined values of these three properties for nodes 1, 2, 3, and 5 are 2.16, 2.5, 2.25, and 2.5. Here the values of nodes 2 and 5 are maximum which is 2.5 for both cases. So for the first iteration from nodes 2 and 5, one of them is selected randomly. Then to cover up all the nodes, another node is selected. Finally, the minimum weighted dominating set is found, which is 2,5,6 and the weight of this set is 20. The weight of the previous set was 23. So it is clear that repair operator helps to provide better results.Figure 10
Illustration of repair operator.


### 4.6. Common Neighbor Elimination

This method eliminates nodes that are common in the neighbor of any node and dominating set based on total weights. The process iterates for every node in a graph. In this process, the intersection between dominating set and the neighbor of a node has been produced for obtaining the total weight of the nodes of the intersection set. If the total weight of the intersection set is greater than the weight of the node then the node becomes an active node. Then the nodes of the intersection set have been deactivated by checking the covering condition. If any node becomes uncovered then it remains active. Finally, nodes in the intersection set have been removed from dominating set one by one by checking the objective value. If the objective value decreases then the molecule is updated with a new molecule, otherwise, it remains the same. Algorithm10 demonstrates the procedure of eliminating neighbor members of dominating set.Algorithm 10: Common neighbor elimination.
Input: one molecule, list of neighbors N, dominating set D, the weight of vertices.Output: updated molecule.(1)
forNvi∈Ndo(2)
CN⟵Nvi∩D;// CN refers to the list of common neighbors between the neighbor node of vi and dominating set(3)
Tω⟵∑ωvj∈CN(4)
ifTω>ωvithen(5)
Mvi⟵1forvj∈CNdo(6)
Mvj⟵0(7)
Check the feasibility of the molecule.(8)
ifinfeasiblethen(9)
Mvj⟵1(10)
end(11)
else(12)
check the objective value of both the previous and updated molecule.(13)
ifinfeasiblethen(14)
f⟵0(15)
end(16)
else(17)
f⟵1(18)
end(19)
end(20)
end(21)
end(22)
iff=1then(23)
updated molecule⟵ molecule with minimum objective value.(24)
end(25)
else(26)
continue.(27)
end(28)
end


## 4.1. Generation of Population

The technique of obtaining a feasible solution to the MWDS problem from search space can be divided into three approaches. These approaches are penalty-based procedure [21], preserving-based approach [24], and repair-based approach [49]. From these three approaches to obtain the feasible population, repair based approach is initiated in our proposed method. The technique of generating a molecule is divided into three distinct stages. The first stage of this technique is to obtain a feasible solution based on the cost of the node and the second one is to obtain a feasible solution based on the weight of the node and the degree of the node. Finally, the solutions of both of these stages are merged. This merging process occurs based on the similarity between taken nodes. If the nodes are taken in both solutions then the nodes are kept as the member of the dominating set.The representation of a solution (molecule) in our proposed architecture is based on 0 and 1. If any vertex is taken as the member of dominating set, then in the molecule, it is represented by the value 1 and reported as an active node. Otherwise, the value with 0 is represented as an inactive node. Figure3 shows the molecule representation.Figure 3
Example of a molecule.The final feasible molecule according to the representation in Figure3 is generated after processing three stages of molecule generation which are the initial stage, middle stage, and final stage. The population set is generated by the iteration of this process twenty times as the taken population size of this work is twenty.


### 4.1.1. Initial Stage

Primarily, the vertices with minimum weight are considered by comparing cost with a specific value with the help of randomness. If the cost of any vertex is less than the difference between the average costμ and the product of epsilon ∈ and the standard deviation σ of the cost then the vertex is selected randomly. Here, epsilon ∈ is a new parameter that is introduced in the initial stage of the population generation method to obtain better random molecules for further operation. The cost is calculated as follows:(5)ci=ωidi.Here,ci, ωi, and di refer to the cost, weight, and degree of vertex i, respectively.After this procedure, to make the solution feasible by covering all vertices and reducing search space, the properties of vertices are checked. The vertex of minimum weight and maximum uncovered neighbors properties is the highly prioritized vertex to count as the member of dominating set. The priority of the vertex depends on the probability score, which is calculated as follows:(6)Pi=PCi∑j∈NiPCjHere,Pi refers to the probability score and PCi denotes the probable cost of vertex i. PCj is the probable cost of neighboring vertices of vertex i. The probability cost of vertex i is determined as follows:(7)PCi=di×∑j∈Niωjωi.After the initial process to cover up the uncovered nodes, priority-based nodes are selected randomly from the first 30% of highly prioritized nodes if the ratio of the number of vertices and the number of edges is greater than the constant value of 0.3. Otherwise, the nodes are selected based on the percentage of the ratio. For example, if there is a sample graph with 500 vertices and 20000 edges, then the ratio is500/20000=0.025. According to the delineation of the process, the active nodes are chosen from the first 2.5% of highly prioritized nodes. After the selection process, the highly dominating nodes are considered active nodes. Despite selecting highly dominating nodes, it cannot be able to cover all the nodes. Again, to find a feasible solution, the nodes that are not covered are picked as spared nodes and put in a list. From this list, active nodes are selected randomly until all nodes are covered. Algorithm 1 shows the initial stage of the population generation procedure.Algorithm 1: The initial stage of population generation.
Input: properties of graphs.Output: feasible solution.(1)
M⟵∅(2)
fori⟵0to lenVdo(3)
ifci<μ−ϵ×σand random value ≥ 0.5 then(4)
Mi⟵1(5)
end(6)
else(7)
Mi⟵0(8)
end(9)
end(10)
Calculate the probability score using equation (6)(11)
Select high prioritized node based on the probability score(12)
Create a list of spared nodes(13)
Select nodes from spared nodes until all nodes are covered


### 4.1.2. Middle Stage

In this stage, to minimize the computational time for large graphs we check for the node with zero, one, and two degrees. The node with zero degree means the node is not connected with any other nodes and automatically will be the member of dominating set. The node with degree one means the node is connected with only one neighbor. Hence from these two nodes which one is minimum weighted is taken as the member of dominating set. The node with two degrees is referred to as the triangle node. These types of the node have two neighbors. From these three nodes, one node is selected as the member of dominating set based on weight. The minimum weighted node is taken as the dominating member. To take the node into dominating set the property of neighbors are also checked to determine whether the neighbor nodes are the member of dominating set or not. Let,q, r and p are three nodes and q,r∈Np and p is the node with minimum weight, so, if D is the dominating set, D′ is the dominated set and p∉D′ then, p∈D. These nodes are taken in a molecule as a permanent node.After accomplishing this procedure there are some nodes to be covered that still remain uncovered. From the list of the uncovered nodes, the size of common nodes is checked which technique helps to find the nodes that can cover the maximum number of nodes. If for all of the uncovered nodes the total number of uncovered neighbor nodes is one then the node with minimum weight is taken as the member of dominating set. After this process, if any of the nodes remains uncovered then the neighbor node with a minimum weight of the uncovered node is taken as the member of the dominating set. Algorithm2 shows the initial stage of the population generation procedure.Algorithm 2: The second stage of population generation.
Input: properties of graphs.Output: feasible solution.(1)
M⟵∅(2)
Add nodes with zero degree, one degree, and two degrees as active nodes into M.(3)
foruc≠∅do//uc refers to the list of uncovered nodes(4)
forvi∈ucdo(5)
cn⟵Nvi∩uc; //cn refers to the list of common nodes between the neighbor node of vi and the list of uncovered nodes(6)
ifcn≠∅then(7)
pn⟵vi; //pn is the probable member of dominating set(8)
cnl⟵cn; //cn is the list of the common node(9)
Len⟵lencn(10)
end(11)
else(12)
Continue(13)
end(14)
end(15)
ifLen≠∅then(16)
ML⟵maxLen; //ML is the maximum size from all the common nodes’ size(17)
ifML>1then(18)
Mvm⟵1; //vm is the node that can cover the maximum number of uncovered nodes(19)
end(20)
else(21)
ifωi>ωNithen(22)
Mvi⟵1(23)
end(24)
else(25)
MvNi⟵1(26)
end(27)
end(28)
end(29)
else(30)
Find uncovered nodes.(31)
Find the minimum weighted nodevmin associated with uncovered nodes.(32)
Mvmin⟵1(33)
end(34)
end


### 4.1.3. Final Stage

In this stage, two different techniques of generating molecules are merged together to obtain feasible molecules for searching using CRO. The nodes which are common in both molecules are considered active nodes. This procedure can make the molecule infeasible. To make this molecule feasible, a local search procedure has been applied and finally, the molecule is prepared for deployment in the searching paradigm. The whole process from the initial stage to the final stage works twenty times to generate twenty different molecules as members of the population.


## 4.1.1. Initial Stage

Primarily, the vertices with minimum weight are considered by comparing cost with a specific value with the help of randomness. If the cost of any vertex is less than the difference between the average costμ and the product of epsilon ∈ and the standard deviation σ of the cost then the vertex is selected randomly. Here, epsilon ∈ is a new parameter that is introduced in the initial stage of the population generation method to obtain better random molecules for further operation. The cost is calculated as follows:(5)ci=ωidi.Here,ci, ωi, and di refer to the cost, weight, and degree of vertex i, respectively.After this procedure, to make the solution feasible by covering all vertices and reducing search space, the properties of vertices are checked. The vertex of minimum weight and maximum uncovered neighbors properties is the highly prioritized vertex to count as the member of dominating set. The priority of the vertex depends on the probability score, which is calculated as follows:(6)Pi=PCi∑j∈NiPCjHere,Pi refers to the probability score and PCi denotes the probable cost of vertex i. PCj is the probable cost of neighboring vertices of vertex i. The probability cost of vertex i is determined as follows:(7)PCi=di×∑j∈Niωjωi.After the initial process to cover up the uncovered nodes, priority-based nodes are selected randomly from the first 30% of highly prioritized nodes if the ratio of the number of vertices and the number of edges is greater than the constant value of 0.3. Otherwise, the nodes are selected based on the percentage of the ratio. For example, if there is a sample graph with 500 vertices and 20000 edges, then the ratio is500/20000=0.025. According to the delineation of the process, the active nodes are chosen from the first 2.5% of highly prioritized nodes. After the selection process, the highly dominating nodes are considered active nodes. Despite selecting highly dominating nodes, it cannot be able to cover all the nodes. Again, to find a feasible solution, the nodes that are not covered are picked as spared nodes and put in a list. From this list, active nodes are selected randomly until all nodes are covered. Algorithm 1 shows the initial stage of the population generation procedure.Algorithm 1: The initial stage of population generation.
Input: properties of graphs.Output: feasible solution.(1)
M⟵∅(2)
fori⟵0to lenVdo(3)
ifci<μ−ϵ×σand random value ≥ 0.5 then(4)
Mi⟵1(5)
end(6)
else(7)
Mi⟵0(8)
end(9)
end(10)
Calculate the probability score using equation (6)(11)
Select high prioritized node based on the probability score(12)
Create a list of spared nodes(13)
Select nodes from spared nodes until all nodes are covered


## 4.1.2. Middle Stage

In this stage, to minimize the computational time for large graphs we check for the node with zero, one, and two degrees. The node with zero degree means the node is not connected with any other nodes and automatically will be the member of dominating set. The node with degree one means the node is connected with only one neighbor. Hence from these two nodes which one is minimum weighted is taken as the member of dominating set. The node with two degrees is referred to as the triangle node. These types of the node have two neighbors. From these three nodes, one node is selected as the member of dominating set based on weight. The minimum weighted node is taken as the dominating member. To take the node into dominating set the property of neighbors are also checked to determine whether the neighbor nodes are the member of dominating set or not. Let,q, r and p are three nodes and q,r∈Np and p is the node with minimum weight, so, if D is the dominating set, D′ is the dominated set and p∉D′ then, p∈D. These nodes are taken in a molecule as a permanent node.After accomplishing this procedure there are some nodes to be covered that still remain uncovered. From the list of the uncovered nodes, the size of common nodes is checked which technique helps to find the nodes that can cover the maximum number of nodes. If for all of the uncovered nodes the total number of uncovered neighbor nodes is one then the node with minimum weight is taken as the member of dominating set. After this process, if any of the nodes remains uncovered then the neighbor node with a minimum weight of the uncovered node is taken as the member of the dominating set. Algorithm2 shows the initial stage of the population generation procedure.Algorithm 2: The second stage of population generation.
Input: properties of graphs.Output: feasible solution.(1)
M⟵∅(2)
Add nodes with zero degree, one degree, and two degrees as active nodes into M.(3)
foruc≠∅do//uc refers to the list of uncovered nodes(4)
forvi∈ucdo(5)
cn⟵Nvi∩uc; //cn refers to the list of common nodes between the neighbor node of vi and the list of uncovered nodes(6)
ifcn≠∅then(7)
pn⟵vi; //pn is the probable member of dominating set(8)
cnl⟵cn; //cn is the list of the common node(9)
Len⟵lencn(10)
end(11)
else(12)
Continue(13)
end(14)
end(15)
ifLen≠∅then(16)
ML⟵maxLen; //ML is the maximum size from all the common nodes’ size(17)
ifML>1then(18)
Mvm⟵1; //vm is the node that can cover the maximum number of uncovered nodes(19)
end(20)
else(21)
ifωi>ωNithen(22)
Mvi⟵1(23)
end(24)
else(25)
MvNi⟵1(26)
end(27)
end(28)
end(29)
else(30)
Find uncovered nodes.(31)
Find the minimum weighted nodevmin associated with uncovered nodes.(32)
Mvmin⟵1(33)
end(34)
end


## 4.1.3. Final Stage

In this stage, two different techniques of generating molecules are merged together to obtain feasible molecules for searching using CRO. The nodes which are common in both molecules are considered active nodes. This procedure can make the molecule infeasible. To make this molecule feasible, a local search procedure has been applied and finally, the molecule is prepared for deployment in the searching paradigm. The whole process from the initial stage to the final stage works twenty times to generate twenty different molecules as members of the population.


## 4.2. Molecule Intensification Procedure

After generating molecules, to intensify searching, a molecule intensification procedure is introduced. Every molecule has gone through this procedure to find the optimal or best solution so far. This procedure is also a ranking-based system of the nodes. After the production of the molecules, some nodes are the neighbors of the neighbors, of active nodes. Initially, they are not considered active nodes deliberately. However, there is some chance to get an optimal solution or intensified searching space for taking those nodes. For the selection of the nodes for which the molecules will be optimal, the molecules have been made infeasible intentionally by removing active nodes, which are low-ranked based on equation (7). The size of the neighbors of each node is counted based on the list of low-ranked nodes. Then for each node, the cost is calculated as follows: (8)ci=LNCNiωi.Here,ci refers to cost, and LNCNi refers to the length of the uncovered neighbors of the vertex i from the low-ranked list. From these vertices, the cost with the maximum value is selected as active nodes. This process is iterated till all the vertices are covered.


## 4.3. Operator Design

In the proposed method, four operators of CRO and three supportive operators have been designed to solve the MWDS problem. The delineation of operators is as in the following subsections.


### 4.3.1. Neighborhood Search Operator

A small amount of change occurs due to the reaction of both on-wall ineffective collision and intermolecular ineffective collision, which is similar to the local search of any other evolutionary algorithms. The inspiration for the neighborhood search operator comes from this concept. In this operator, the neighbor node with minimum weight has been searched from any active nodes. An active node is picked randomly, and the searching occurs among all neighbor nodes inclusive of the active node for the lowest weight. If the active node is not the lowest weighted, then the lowest-weighted neighbor is activated, the active node becomes deactivated, and the process terminates. Otherwise, the same procedure occurs to find another active node randomly. This process runs until obtaining a molecule different from the given one. The final termination occurs due to the unavailability of any new node after checking all active nodes. Algorithm3 shows the neighborhood search procedure.Algorithm 3: Neighborhood search.
Input: one molecule, MOutput: updated molecule, M′(1)
Count total active nodesTn(2)
total search,Sn⟵0(3)
whileTruedo(4)
An active nodeVi has been chosen randomly from the molecule(5)
ωmin⟵ωi(6)
Vprev⟵Vi for j∈Nido(7)
ifωj<ωminthen(8)
ωmin⟵ωjVtaken⟵Vj(9)
end(10)
end(11)
Sn⟵Sn+1(12)
ifVprev≠Vtakenthen(13)
M′taken⟵1(14)
M′prev⟵0(15)
break(16)
end(17)
ifTn = Snthen(18)
break(19)
end(20)
else(21)
continue(22)
end(23)
endFigure4 depicts the search procedure of the neighborhood search operator.Figure 4
Illustration of a neighborhood search operator.


### 4.3.2. Local Search Procedure

After using neighborhood search on on-wall ineffective collision, intermolecular ineffective collision, decomposition, or synthesis, some vertices of a molecule can be uncovered, and the solution becomes infeasible. To make the solution feasible by covering all the uncovered vertices, a technique suggested by Potluri and Singh [24] has been used in our method. They proposed four greedy approaches for searching a node from the set of vertices. From these four approaches, the assimilation of the fourth approach occurs in our system due to its better performance than the other three approaches. The greedy approach follows the following equation to calculate the value of a vertex vi:(9)gi=di×∑j∈Niωjωi.Here,∑j∈Niωj denotes the summation of all uncovered neighbors of a single vertex vi, ωi represents the weight, and di is the degree of vi.The calculation of greedy values of every uncovered vertex takes place by using equation (9). Then a vertex is activated if gi≥δ×maxgi;∀vi∈NC. Here, NC represents the set of uncovered vertices, and δ is a controlling parameter for obtaining a better vertex. The procedure runs until all vertices are covered. Algorithm 4 shows the local search procedure.Algorithm 4: Local search.
Input: infeasible molecule, MOutput: feasible molecule, M′(1)
whileNC≠∅do(2)
Calculate the greedy value forvi∈NC(3)
gall⟵greedy values of vi∈NC(4)
gmax⟵maxgi(5)
forgv∈galldo(6)
ifgv≥δ×gmaxthen(7)
M′gv⟵1(8)
break(9)
end(10)
else(11)
continue(12)
end(13)
end(14)
Check for uncovered vertices(15)
updateNC(16)
end


### 4.3.3. Redundant Vertices Elimination

If any vertexvi is a member of dominating set and all of its neighbors inclusive of the vertex are the neighbors of one or more members of dominating set, then the vertex is defined as the redundant vertex. Removal of redundant vertices can minimize the total weight of the dominating set. Thus the redundant vertices with maximum weights have been removed from the molecule to obtain the minimum weighted solution. If R is a set of redundant vertices where vi∈R and ωi is maximum, then vi is removed from the molecule, and then further redundant vertices are checked and removed. This process runs until the removal of all the redundant vertices. The procedure for eliminating redundant vertices has been shown in Algorithm 5.Algorithm 5: Redundant vertices elimination.
Input: molecule, MOutput: updated molecule, M′(1)
whileR≠∅do(2)
ωmax⟵0(3)
veliminate⟵0(4)
forrv∈Rdo(5)
ifωmax<ωrvthen(6)
ωmax⟵ωrv(7)
veliminate⟵rv(8)
end(9)
else(10)
continue(11)
end(12)
end(13)
M′⟵0 Check for redundant vertices(14)
updateR(15)
end


### 4.3.4. On-Wall Ineffective Collision

It is a unimolecular reaction. So in this operator, initially, a molecule has been selected randomly. Then the molecule is modified to generate a new optimal molecule. Primarily, a random selection of a position from the molecule takes place for propagating the latest molecule. If the node of the randomly selected position is active, then the position changes according to the neighborhood search operator. Otherwise, the inactive node becomes active. Finally, for any uncovered nodes, the nodes are covered using the local search procedure. Likewise, for any redundant nodes, the redundant vertices elimination procedure takes place to eradicate redundancy. Figure5 depicts the MWDS problem’s on-wall ineffective collision, where M denotes the molecule (i.e., solution) and M′ denotes the newly created molecule after applying both neighborhood and local search. The procedure of on-wall ineffective collision is shown in Algorithm 6.Figure 5
Illustration of on-wall ineffective collision.Algorithm 6: On-wall ineffective collision.
Input: one molecule, MOutput: updated molecule, M′(1)
CopyM to M′(2)
Randomly select a positioni from M′(3)
ifM′i=1then(4)
Run neighborhood search operator(5)
end(6)
else(7)
M′i⟵1(8)
end(9)
Run the local search.(10)
Run redundant vertices elimination.


### 4.3.5. Decomposition

It is also a unimolecular reaction where the molecule can be divided into two or more. To find a better solution for the MWDS problem, the search happens in the search space according to this reaction by dividing the parent molecule into two. Both two new molecules inherit a portion from the parent molecule. The parent molecule is divided from the middle. Then the first portion of the parent molecule becomes the first portion of the first child molecule, and the other portion of the parent molecule becomes the last portion of another child molecule. Then for both molecules, uncovered vertices are covered using a local search procedure. Figure6 shows the decomposition procedure. Here, in the first child molecule M1′, the first portion is similar to the first portion of the parent molecule, and in the second child molecule M2′, the last portion is the same as the last portion of the parent molecule. Algorithm 7 depicts the working procedure of decomposition.Figure 6
Illustration of decomposition.Algorithm 7: Decomposition.
Input: one molecule, MOutput: updated molecules, M1′ and M2′(1)
fori⟵0to lenV/2 do(2)
M1′i⟵Mi(3)
end(4)
Run a local search onM1′(5)
fori⟵lenV/2 to lenVdo(6)
M2′i⟵Mi(7)
end(8)
Run the local search onM2′


### 4.3.6. Intermolecular Ineffective Collision

It is a multimolecular reaction operator where two or more parent molecules can react with each other and generate new molecule(s) where the change in the new molecule is little. This operator searches locally in search space such as the on-wall ineffective collision. In the proposed method, two molecules are used to generate new molecules by implementing this operator. A single position (i.e., vertex) from both parent molecules is considered randomly. Then the values from both positions are interchanged in child molecules. Then uncovered nodes are covered, and redundant vertices are removed from both child molecules. Figure7 depicts the intermolecular ineffective collision where M1 and M2 are the parent molecules and M1′ and M2′ are denoted as child molecules. Algorithm 8 shows the working procedure of intermolecular ineffective collision.Figure 7
Illustration of intermolecular ineffective collision.Algorithm 8: Intermolecular ineffective collision.
Input: two molecules, M1 and M2Output: updated molecules, M1′ and M2′(1)
CopyM1 to M1′(2)
CopyM2 to M2′(3)
Select a vertexvi from M1 randomly(4)
Select a vertexvj from M2 randomly(5)
M1′i⟵M2j(6)
M2′j⟵M1i(7)
Run a local search onM1′(8)
Run redundant vertices elimination onM1′(9)
Run the local search onM2′(10)
Run redundant vertices elimination onM2′


### 4.3.7. Synthesis

It is also a multimolecular reaction operator. In this operator, the amalgamation of two molecules generates a child molecule to obtain a better offspring. Let, there are two moleculesM1 and M2 in the population set. If any vertex in both parent molecules is active, then the vertex remains active in the child molecule M′. Other vertices of the child molecule become inactive. Then local search procedure is applied to the child molecule to obtain a feasible solution. Figure 8 shows the illustration of the synthesis reaction, and Algorithm 9 depicts the working procedure of synthesis.Figure 8
Illustration of synthesis.Algorithm 9: Synthesis.
Input: two molecules, M1 and M2Output: updated molecule, M′(1)
fori⟵0to lenVdo(2)
ifM1i=1 and M2i=1then(3)
M′i⟵1(4)
end(5)
else(6)
M′i⟵0(7)
end(8)
end(9)
Run the local search onM′


## 4.3.1. Neighborhood Search Operator

A small amount of change occurs due to the reaction of both on-wall ineffective collision and intermolecular ineffective collision, which is similar to the local search of any other evolutionary algorithms. The inspiration for the neighborhood search operator comes from this concept. In this operator, the neighbor node with minimum weight has been searched from any active nodes. An active node is picked randomly, and the searching occurs among all neighbor nodes inclusive of the active node for the lowest weight. If the active node is not the lowest weighted, then the lowest-weighted neighbor is activated, the active node becomes deactivated, and the process terminates. Otherwise, the same procedure occurs to find another active node randomly. This process runs until obtaining a molecule different from the given one. The final termination occurs due to the unavailability of any new node after checking all active nodes. Algorithm3 shows the neighborhood search procedure.Algorithm 3: Neighborhood search.
Input: one molecule, MOutput: updated molecule, M′(1)
Count total active nodesTn(2)
total search,Sn⟵0(3)
whileTruedo(4)
An active nodeVi has been chosen randomly from the molecule(5)
ωmin⟵ωi(6)
Vprev⟵Vi for j∈Nido(7)
ifωj<ωminthen(8)
ωmin⟵ωjVtaken⟵Vj(9)
end(10)
end(11)
Sn⟵Sn+1(12)
ifVprev≠Vtakenthen(13)
M′taken⟵1(14)
M′prev⟵0(15)
break(16)
end(17)
ifTn = Snthen(18)
break(19)
end(20)
else(21)
continue(22)
end(23)
endFigure4 depicts the search procedure of the neighborhood search operator.Figure 4
Illustration of a neighborhood search operator.


## 4.3.2. Local Search Procedure

After using neighborhood search on on-wall ineffective collision, intermolecular ineffective collision, decomposition, or synthesis, some vertices of a molecule can be uncovered, and the solution becomes infeasible. To make the solution feasible by covering all the uncovered vertices, a technique suggested by Potluri and Singh [24] has been used in our method. They proposed four greedy approaches for searching a node from the set of vertices. From these four approaches, the assimilation of the fourth approach occurs in our system due to its better performance than the other three approaches. The greedy approach follows the following equation to calculate the value of a vertex vi:(9)gi=di×∑j∈Niωjωi.Here,∑j∈Niωj denotes the summation of all uncovered neighbors of a single vertex vi, ωi represents the weight, and di is the degree of vi.The calculation of greedy values of every uncovered vertex takes place by using equation (9). Then a vertex is activated if gi≥δ×maxgi;∀vi∈NC. Here, NC represents the set of uncovered vertices, and δ is a controlling parameter for obtaining a better vertex. The procedure runs until all vertices are covered. Algorithm 4 shows the local search procedure.Algorithm 4: Local search.
Input: infeasible molecule, MOutput: feasible molecule, M′(1)
whileNC≠∅do(2)
Calculate the greedy value forvi∈NC(3)
gall⟵greedy values of vi∈NC(4)
gmax⟵maxgi(5)
forgv∈galldo(6)
ifgv≥δ×gmaxthen(7)
M′gv⟵1(8)
break(9)
end(10)
else(11)
continue(12)
end(13)
end(14)
Check for uncovered vertices(15)
updateNC(16)
end


## 4.3.3. Redundant Vertices Elimination

If any vertexvi is a member of dominating set and all of its neighbors inclusive of the vertex are the neighbors of one or more members of dominating set, then the vertex is defined as the redundant vertex. Removal of redundant vertices can minimize the total weight of the dominating set. Thus the redundant vertices with maximum weights have been removed from the molecule to obtain the minimum weighted solution. If R is a set of redundant vertices where vi∈R and ωi is maximum, then vi is removed from the molecule, and then further redundant vertices are checked and removed. This process runs until the removal of all the redundant vertices. The procedure for eliminating redundant vertices has been shown in Algorithm 5.Algorithm 5: Redundant vertices elimination.
Input: molecule, MOutput: updated molecule, M′(1)
whileR≠∅do(2)
ωmax⟵0(3)
veliminate⟵0(4)
forrv∈Rdo(5)
ifωmax<ωrvthen(6)
ωmax⟵ωrv(7)
veliminate⟵rv(8)
end(9)
else(10)
continue(11)
end(12)
end(13)
M′⟵0 Check for redundant vertices(14)
updateR(15)
end


## 4.3.4. On-Wall Ineffective Collision

It is a unimolecular reaction. So in this operator, initially, a molecule has been selected randomly. Then the molecule is modified to generate a new optimal molecule. Primarily, a random selection of a position from the molecule takes place for propagating the latest molecule. If the node of the randomly selected position is active, then the position changes according to the neighborhood search operator. Otherwise, the inactive node becomes active. Finally, for any uncovered nodes, the nodes are covered using the local search procedure. Likewise, for any redundant nodes, the redundant vertices elimination procedure takes place to eradicate redundancy. Figure5 depicts the MWDS problem’s on-wall ineffective collision, where M denotes the molecule (i.e., solution) and M′ denotes the newly created molecule after applying both neighborhood and local search. The procedure of on-wall ineffective collision is shown in Algorithm 6.Figure 5
Illustration of on-wall ineffective collision.Algorithm 6: On-wall ineffective collision.
Input: one molecule, MOutput: updated molecule, M′(1)
CopyM to M′(2)
Randomly select a positioni from M′(3)
ifM′i=1then(4)
Run neighborhood search operator(5)
end(6)
else(7)
M′i⟵1(8)
end(9)
Run the local search.(10)
Run redundant vertices elimination.


## 4.3.5. Decomposition

It is also a unimolecular reaction where the molecule can be divided into two or more. To find a better solution for the MWDS problem, the search happens in the search space according to this reaction by dividing the parent molecule into two. Both two new molecules inherit a portion from the parent molecule. The parent molecule is divided from the middle. Then the first portion of the parent molecule becomes the first portion of the first child molecule, and the other portion of the parent molecule becomes the last portion of another child molecule. Then for both molecules, uncovered vertices are covered using a local search procedure. Figure6 shows the decomposition procedure. Here, in the first child molecule M1′, the first portion is similar to the first portion of the parent molecule, and in the second child molecule M2′, the last portion is the same as the last portion of the parent molecule. Algorithm 7 depicts the working procedure of decomposition.Figure 6
Illustration of decomposition.Algorithm 7: Decomposition.
Input: one molecule, MOutput: updated molecules, M1′ and M2′(1)
fori⟵0to lenV/2 do(2)
M1′i⟵Mi(3)
end(4)
Run a local search onM1′(5)
fori⟵lenV/2 to lenVdo(6)
M2′i⟵Mi(7)
end(8)
Run the local search onM2′


## 4.3.6. Intermolecular Ineffective Collision

It is a multimolecular reaction operator where two or more parent molecules can react with each other and generate new molecule(s) where the change in the new molecule is little. This operator searches locally in search space such as the on-wall ineffective collision. In the proposed method, two molecules are used to generate new molecules by implementing this operator. A single position (i.e., vertex) from both parent molecules is considered randomly. Then the values from both positions are interchanged in child molecules. Then uncovered nodes are covered, and redundant vertices are removed from both child molecules. Figure7 depicts the intermolecular ineffective collision where M1 and M2 are the parent molecules and M1′ and M2′ are denoted as child molecules. Algorithm 8 shows the working procedure of intermolecular ineffective collision.Figure 7
Illustration of intermolecular ineffective collision.Algorithm 8: Intermolecular ineffective collision.
Input: two molecules, M1 and M2Output: updated molecules, M1′ and M2′(1)
CopyM1 to M1′(2)
CopyM2 to M2′(3)
Select a vertexvi from M1 randomly(4)
Select a vertexvj from M2 randomly(5)
M1′i⟵M2j(6)
M2′j⟵M1i(7)
Run a local search onM1′(8)
Run redundant vertices elimination onM1′(9)
Run the local search onM2′(10)
Run redundant vertices elimination onM2′


## 4.3.7. Synthesis

It is also a multimolecular reaction operator. In this operator, the amalgamation of two molecules generates a child molecule to obtain a better offspring. Let, there are two moleculesM1 and M2 in the population set. If any vertex in both parent molecules is active, then the vertex remains active in the child molecule M′. Other vertices of the child molecule become inactive. Then local search procedure is applied to the child molecule to obtain a feasible solution. Figure 8 shows the illustration of the synthesis reaction, and Algorithm 9 depicts the working procedure of synthesis.Figure 8
Illustration of synthesis.Algorithm 9: Synthesis.
Input: two molecules, M1 and M2Output: updated molecule, M′(1)
fori⟵0to lenVdo(2)
ifM1i=1 and M2i=1then(3)
M′i⟵1(4)
end(5)
else(6)
M′i⟵0(7)
end(8)
end(9)
Run the local search onM′


## 4.4. Operator Selection

Some comparisons occur to select one of the four operators of CRO for the MWDS problem. The intermolecular collision occurred based on the comparison between a random value and MoleColl. If the random value between 0 and 1 is less than MoleColl, then the collision is unimolecular. Otherwise, the reaction is intermolecular. If it is unimolecular, then the collision can be an on-wall ineffective collision or decomposition. The decision of on-wall or decomposition reaction comes from the following equation.(10)hit_diff>α.Here,hit_diff refers hit difference of the selected molecule. If equation (10) is satisfied, decomposition occurs. Otherwise, we get an on-wall ineffective collision. In the same manner, synthesis or intermolecular ineffective reaction can occur if the random value is greater than the value of MoleColl. The decision of synthesis or intermolecular ineffective reaction is taken based on the following equation:(11)KE≤β.Here, KE is the kinetic energy of the molecule. If the kinetic energy of all molecules is less than or equal toβ, then synthesis occurs. Otherwise, the reaction is an intermolecular ineffective collision. To get rid of the local minima synthesis is triggered based on the parameter values.By following this approach, better offspring is found in which the number of vertices is minimum. Then using the repair operator and ILP, the offspring is checked for a better solution. If the offspring is better than the previous one then the candidate solution is updated, and the vertices of the candidate solution are taken as the member of the minimum weighted dominating set.The reaction operators of CRO for the MWDS problem have been triggered based on the parameter values of Table2, and an optimal solution has been obtained. The proposed flowchart of the CRO algorithm of the MWDS problem is shown in Figure 9.Table 2
Initialization of parameters for proposed MWDS_CRO algorithm.
ParametersInitialized valuesEpsilonϵ0.9Deltaδ1.45Total iteration100Initial population size20KELossRate0.1MoleColl0.1Energy buffer0Hit_diff0Alphaα10000Betaβ1000Kinetic energy (KE)100Figure 9
Flowchart of CRO for MWDS problem.


## 4.5. Repair Operator

After using CRO operators with other supporting operators, there are some operations to obtain a better solution from the search space. As in the local search procedure, minimum weighted nodes are bound to inherit the solution; the search space is confined and cannot search for a further better solution. Alongside this drawback, there is another pitfall. In previous searching procedures, the properties of nodes are not updated after including the best node. Thus nodes are included every time by using old properties. For example, let a vertexv1 is taken as the best active node in the solution and the neighbors of v1 are v6, v8, and v9. If v8 be the second-best node with the highest greedy value then this node is taken as the active node in the solution. But as v8 is already dominated by v1, by eliminating this, a better solution can be obtained.To get rid of the aforementioned problems, a new repair operator has been proposed in our method with some other properties of nodes. As the feasible solution has been obtained from the CRO operators to apply repair operator on the solution, the solution is converted into an infeasible solution by uncovering some vertices. Forty percent (40%) of vertices with maximum weights from the dominating set are removed intentionally to make the infeasible solution. Then to find the better solution vertices are searched based on three properties. The properties of a vertexvi are the weight of the vertex, uncovered neighbors of the vertex, and the ratio of weight and uncovered neighbor nodes. Then these properties are scaled based on minimum or maximum values of corresponding properties according to the following equations: (12)–(14).(12)Sωi=ωminωi.(13)SNCNi=NCNiNCNmax,(14)Sri=rminri.Here,ωi refers to the weight of the uncovered node vi and ωmin is the node with minimum weight from all uncovered nodes. S represents the scaled property, NCNi represents the number of total uncovered neighbors of the node vi, and NCNmax represents the maximum number of all uncovered neighbors. The ratio ri of the node vi is calculated as follows:(15)ri=ωiNCNi.All these three properties of a vertex are considered by combining these properties. To make the solution feasible based on these properties, if any vertex has two or more uncovered neighbors, the vertex with the maximum aggregated value of the properties is selected as an active vertex. Otherwise, the vertex is selected as active based on weight. If the weight is minimum then the vertex becomes active. This procedure terminates when all the vertices are covered. The operator can find the minimum weighted node with the maximum number of neighbor nodes which helps obtain a better solution in minimal time.Figure10 shows the procedure of the repair operator. Let after using all of the previous operators on the graph of Figure 10 the selected nodes are 1, 3, and 6 and the dominating set is 1,3,6. The weights of these three nodes are 6, 12, and 5 and the total weight is 23. As the nodes with maximum weights are removed, nodes 1 and 3 are removed from the dominating set and 6 remains in the dominating set. Now, three properties of uncovered nodes are checked. After removing nodes 1 and 3, nodes 1, 2, 3, and 5 become uncovered. The weights of these four nodes are 6, 10, 12, and 5, and the total number of uncovered neighbors of these four nodes are 1, 2, 2, and 1. Here, from the four uncovered nodes, the minimum weight is 5, and the maximum number of uncovered neighbors is 2. Now according to equation (12), the values of nodes 1, 2, 3, and 5 are 5/6=0.83, 5/10=0.5, 5/12=0.417, and 5/5=1. According to equation (13), the values of nodes 1, 2, 3, and 5 are 1/2=0.5, 2/2=1, 2/2=1, and 1/2=0.5 =. The ratios according to equation (15) are 6/1=6, 10/2=5, 12/2=6, and 5/1=5. According to equation (14), the values of nodes 1, 2, 3, and 5 are 5/6=0.83, 5/5=1, 5/6=0.833, and 5/5=1. The combined values of these three properties for nodes 1, 2, 3, and 5 are 2.16, 2.5, 2.25, and 2.5. Here the values of nodes 2 and 5 are maximum which is 2.5 for both cases. So for the first iteration from nodes 2 and 5, one of them is selected randomly. Then to cover up all the nodes, another node is selected. Finally, the minimum weighted dominating set is found, which is 2,5,6 and the weight of this set is 20. The weight of the previous set was 23. So it is clear that repair operator helps to provide better results.Figure 10
Illustration of repair operator.


## 4.6. Common Neighbor Elimination

This method eliminates nodes that are common in the neighbor of any node and dominating set based on total weights. The process iterates for every node in a graph. In this process, the intersection between dominating set and the neighbor of a node has been produced for obtaining the total weight of the nodes of the intersection set. If the total weight of the intersection set is greater than the weight of the node then the node becomes an active node. Then the nodes of the intersection set have been deactivated by checking the covering condition. If any node becomes uncovered then it remains active. Finally, nodes in the intersection set have been removed from dominating set one by one by checking the objective value. If the objective value decreases then the molecule is updated with a new molecule, otherwise, it remains the same. Algorithm10 demonstrates the procedure of eliminating neighbor members of dominating set.Algorithm 10: Common neighbor elimination.
Input: one molecule, list of neighbors N, dominating set D, the weight of vertices.Output: updated molecule.(1)
forNvi∈Ndo(2)
CN⟵Nvi∩D;// CN refers to the list of common neighbors between the neighbor node of vi and dominating set(3)
Tω⟵∑ωvj∈CN(4)
ifTω>ωvithen(5)
Mvi⟵1forvj∈CNdo(6)
Mvj⟵0(7)
Check the feasibility of the molecule.(8)
ifinfeasiblethen(9)
Mvj⟵1(10)
end(11)
else(12)
check the objective value of both the previous and updated molecule.(13)
ifinfeasiblethen(14)
f⟵0(15)
end(16)
else(17)
f⟵1(18)
end(19)
end(20)
end(21)
end(22)
iff=1then(23)
updated molecule⟵ molecule with minimum objective value.(24)
end(25)
else(26)
continue.(27)
end(28)
end


## 5. Experimental Results

In this section, experimental results of CRO on given datasets are reported. The proposed CRO was run on a computer with a 2.7 GHz Intel Core i5 processor and 8 GB of RAM. The algorithm was run using python 3.7. Firstly, we introduce the used benchmark datasets. Then, we describe the method for setting the parameter values. Finally, computational results and comparisons are reported.


### 5.1. Dataset

In our proposed system two types of benchmark datasets were used which were used by different researchers to solve the MWDS problem using heuristic algorithms [21–24, 27]. The benchmark data are of two types (TI and TII), and another class is BHOSLIB. These datasets can be found in [21]. Each vertex weight of the type I is randomly generated in between 20 to 70. For the instances in type II, the weight of vertex i is randomly generated in (1, degreei2), where degreei is the degree of vertex i. Both types I and II have 53 groups. There are 10 instances (the names of these 10 instances are n_m_0 to n_m_9) in each group. Instances with the same number of vertices (n) are classified as the same group. On the other hand, the complement graphs of the remaining instances in the BHOSLIB dataset were taken as useable graphs for the MWDS problem. To obtain the weights of the nodes of graphs, for each node, it is calculated as ωi=i%200+1. Here, ωi refers to the weight of a single node i.


### 5.2. Setting Parameters

Because the initialization of parameters in CRO is not guaranteed, obtaining an appropriate parameter value for the optimal molecule is a difficult process. In our study, we strive to discover the best molecule with the smallest weight by adjusting various factors, and we provide the findings for several parameter sets. In the population generation stage, a new parameterϵ is introduced. Figure 11 shows the tuning results of this parameter on some graph data of the TI instance. Besides this, Figures 12–14 refer to the different parameter tuning results of CRO which are the kinetic energy, alpha, and beta tuning. In all the graphs X-axis represents the total weight of the dominating set, and the Y-axis represents the parameter values. From the results of tuning, the parameter values are shown in Table 2.Figure 11
Epsilonϵ tuning.Figure 12
Kinetic energy (KE) tuning.Figure 13
Alphaα tuning.Figure 14
Betaβ tuning.


### 5.3. Performance Analysis

To analyze the performance of the proposed algorithm the minimum weights of the dominating set and the run time of the algorithm were considered. The existing related algorithms used different CPUs and different programming languages to obtain the output. Thus to compare the running time we implemented the HTS-DS approach in our implementation environment. As the HTS-DS approach obtained the best time compared with other algorithms, we show only the comparison between the proposed CRO-based method and the HTS-DS approach.The comparison regarding minimum weights between MWDS_CRO with other algorithms has been shown in Tables3–7. These tables depict the outcomes for types TI, TII, and BHOSLIB datasets, respectively. For both types TI and TII, the instances are divided into two classes which are small and medium particle instances (SMPI) and large particle instances (LPI). Here, the graphs with (50–250) nodes are classified as SMPI class while the others are represented as LPI class. Table 3 illustrates the minimum weights of class SMPI of type TI which are obtained after the implementation of different algorithms. Here, V and E refer to the number of vertices and edges in a graph. The outcome regarding weights of different algorithms of LPI class from TI type can be obtained from Table 4. Tables 5 and 6 refer to the minimum weights of various algorithms of classes SMPI and LPI of type TII. Table 7 shows the comparison of performance between HTS-DS and MWDS_CRO for the BHOSLIB dataset.Table 3
Type TI class SMPI-comparison of MWDS_CRO for various parameters with recent state-of-the-art algorithms.
VECC2 FSFBPSOHTS-DSABC-EDAMWDS_CROBest known5050531.3531.3531.3531.3531.3531.3100370.9370.98370.9370.9370.9370.9250175.7175.7175.7175.7175.7175.750094.994.994.994.994.994.975063.363.1663.163.163.163.1100041.541.541.541.541.541.51001001061.01062.991061.01061.41061.01061.0250618.9619.48618.9621.1618.9618.9500355.6355.74355.6355.8355.6355.6750255.8255.95255.8258.0255.8255.81000203.6203.6203.6205.2203.6203.62000107.4107.88107.4107.9107.4107.41501501580.51585.711580.51583.81580.51580.52501218.21223.311218.21223.21218.21218.2500744.6747.45744.6747.5744.6744.6750546.1548.15546.1549.2546.1546.11000432.9433.93432.8434.8432.8432.82000240.8241.47240.8243.7240.8240.83000166.9167.53166.9169.3166.9166.92002501910.41918.821909.71916.71909.71909.75001232.81239.711232.81243.41232.81232.8750911.2918.47911.2924.2911.2911.21000724.0727.09723.5729.0723.5723.52000412.7415.46412.9417.9412.9412.73000292.8294.03292.8298.1292.8292.82502502633.42649.732633.02647.02633.02633.05001805.91813.031805.91817.91805.91805.97501362.21375.321361.91382.61361.91361.910001091.11099.651090.11107.71089.91089.92000621.9625.41621.9628.6621.6621.63000447.9452.45448.0457.1448.0447.95000289.5291.18289.6297.4289.5289.5Table 4
Type TI class LPI-comparison of MWDS_CRO for various parameters with recent state-of-the-art algorithms.
VECC2 FSFBPSOHTS-DSABC-EDAMWDS_CROBest known3003003178.63203.623175.43193.03175.43175.45002438.12453.572435.62461.32435.62435.67501854.61870.81853.91876.01853.81853.810001495.01506.561494.11516.71494.01494.02000862.5871.89862.4878.8862.4862.43000624.3628.24624.4636.8624.1624.15000406.1409.08406.3417.7406.1406.15005005305.75392.455304.75370.75304.75304.710003607.83659.873608.63652.13607.63607.320002181.02210.282177.82225.02176.82176.850001043.31054.881044.21073.51042.31042.310000587.2594.32587.2605.8587.2587.280010007663.47771.527655.07755.77655.07655.020004982.15060.734991.75079.14987.34982.150002441.22470.382435.82492.22432.62432.6100001395.61417.161395.11440.01393.71393.71000100010585.310785.3710574.410766.410574.410574.450003671.83713.223662.73757.43656.63656.6100002109.02132.762102.22180.82099.82099.8150001521.51542.641521.91573.61519.71519.7200001203.61215.981205.61242.11200.91200.9Table 5
Type TII class SMPI-comparison of MWDS_CRO for various parameters with recent state-of-the-art algorithms.
VECC2 FSFBPSOHTS-DSABC-EDAMWDS_CROBest known505060.860.860.860.860.860.810090.390.390.390.390.390.3250146.7146.7146.7146.7146.7146.7500179.9179.9179.9179.9179.9179.9750171.1171.1171.1171.1171.1171.11000146.5146.5146.5146.5146.5146.5100100123.5123.5123.5123.5123.5123.5250209.2209.23209.2209.6209.2209.2500305.7305.72305.7305.7305.7305.7750384.5384.5384.5384.5384.5384.51000427.3427.3427.3427.3427.3427.32000550.6550.6550.6550.6550.6550.6150150184.5184.59184.5184.5184.5184.5250232.8233.04232.8233.1232.8232.8500349.5349.68349.5349.5349.5349.5750452.4452.4452.4452.8452.4452.41000547.2547.2547.2547.2547.2547.22000720.1720.1720.1720.1720.1720.13000792.4792.48792.4792.4792.4792.4200250271.7272.06271.7271.7271.7271.7500386.7386.77386.7386.8386.7386.7750497.1497.15497.1497.3497.1497.11000596.8597.21596.8597.3596.8596.82000884.6884.63884.6884.6884.6884.630001019.21019.451019.21022.41019.21019.2250250306.1306.79306.0306.1306.0306.0500440.7441.72440.7440.8440.7440.7750567.4568.63567.4568.2567.4567.41000668.6669.26668.6669.5668.6668.620001007.01007.911007.01010.21007.01007.030001250.61251.571250.61250.61250.61250.650001464.21464.21464.21464.21464.21464.2Table 6
Type TII class LPI-comparison of MWDS_CRO for various parameters with recent state-of-the-art algorithms.
VECC2 FSFBPSOHTS-DSABC-EDAMWDS_CROBest known300300369.9370.63369.9369.9369.9369.9500477.8478.32477.8478.4477.8477.8750613.3614.73613.3613.9613.3613.31000737.9738.93737.7738.1737.7737.720001093.81094.231093.81095.21093.81093.830001358.51359.571358.51361.31358.51358.550001682.71683.21682.71682.71682.71682.7500500623.6627.24623.6623.7623.6623.61000899.8904.24899.6901.6899.6899.620001363.31373.331362.21367.31362.21362.250002333.72335.412326.62342.12326.62326.6100003211.53211.83211.53214.53211.53211.580010001104.31113.031103.91104.51103.91103.920001632.31641.871630.81636.11630.81630.850002878.52901.622876.62888.12876.02876.1100004105.64107.194104.04121.54102.14102.8100010001237.71249.71237.51239.41237.51237.550003178.73206.73180.03194.43172.93172.9100004711.84733.584709.94748.14704.54704.8150005874.25896.915862.45897.65856.45856.4200006662.16681.646657.96691.56655.16655.1Table 7
BHOSLIB-comparison of MWDS_CRO for various parameters with the recent state-of-the-art algorithm.
InstancesHTS-DSMWDS_CROBest knownNameVEAvgT (s)AvgT (s)—frb30-15-145017827212.041.6212.08.12212.0frb30-15-245017874242.014.32242.04.56242.0frb30-15-345017809175.021.67175.05.51175.0frb30-15-445017831166.014.57166.02.23166.0frb30-15-545017794160.017.3160.03.59160.0frb35-17-159527856274.044.55274.010.76274.0frb35-17-259527847208.018.17208.03.02208.0frb35-17-359527931201.019.61201.06.63201.0frb35-17-459527842286.052.87286.013.33286.0frb35-17-559528143295.012.74295.02.41295.0frb40-19-176041314262.020.22262.05.60262.0frb40-19-276041263243.080.41243.012.51243.0frb40-19-376041095250.078.71250.016.06250.0frb40-19-476041605249.171.87249.014.18249.0frb40-19-576041619272.063.69272.010.87272.0frb45-21-194559186328.076.98328.013.96328.0frb45-21-294558624259.287.38259.022.34259.0frb45-21-394558245233.0132.06233.030.53233.0frb45-21-494558549399.079.67399.019.49399.0frb45-21-594558579312.592.06312.020.79312.0frb50-23-1115080072261.0159.38261.037.11261.0frb50-23-2115080851277.0161.75277.038.93277.0frb50-23-3115081068281.0125.9281.025.07281.0frb50-23-4115080258265.0191.06265.040.58265.0frb50-23-5115080035404.3108.5408.012.10404.0frb53-24-1127294227229.086.89229.07.99229.0frb53-24-2127294289298.0348.12298.052.68298.0frb53-24-3127294127182.0212.98182.041.26182.0frb53-24-4127294308189.0284.44189.058.56189.0frb53-24-5127294226204.078.23204.016.21204.0frb56-25-11400109676229.0107.66229.012.90229.0frb56-25-21400109401319.0145.09319.039.02319.0frb56-25-31400109379336.0163.23336.048.88336.0frb56-25-41400110038265.0169.65265.051.09265.0frb56-25-51400109601411.4128.27408.032.88408.0frb59-26-11534126555262.6192.54262.054.39262.0frb59-26-21534126163386.6159.25383.033.74383.0frb59-26-31534126082246.7348.38246.092.40246.0frb59-26-41534127011248.0357.5248.086.66248.0frb59-26-51534125982288.0396.44288.498.23288.0frb100-404000572774350.0963.58350.0181.16350.0Tables8 and 9 demonstrate the run times for all instances of types TI and TII successively for every individual algorithm.Table 8
Type TI-run time comparison in second of MWDS_CRO with the recent state-of-the-art algorithm.
VEHTS-DSMWDS_CRO50500.420.361000.420.362501.101.075002.011.817501.822.2510002.593.011001000.640.902501.611.015002.932.137503.253.1810006.895.39200012.9313.411501501.611.012501.930.775009.631.2475022.472.79100026.004.14200025.0414.66300030.0826.792002501.931.195006.421.5875025.0411.56100025.0419.92200025.6816.04300023.1112.092502503.531.385007.701.8175026.3218.20100025.3621.26200026.9616.62300024.4026.53500025.041.333003004.171.585005.141.0875024.083.29100027.934.78200028.572.49300030.501.26500026.001.925005008.673.17100033.388.69200034.677.29500034.996.481000031.784.25800100016.696.16200045.907.80500045.588.961000044.627.261000100027.938.02500050.4012.561000051.0413.651500052.009.682000057.4610.28Table 9
Type TII-run time comparison in second of MWDS_CRO with the recent state-of-the-art algorithm.
VEHTS-DSMWDS_CRO50500.320.131000.320.122500.130.105000.130.087500.130.0810000.320.071001000.640.242500.320.235000.320.267500.640.2610000.640.2820000.960.241501501.610.472500.960.325000.960.397501.280.4010001.280.3920001.610.4530002.570.432002501.610.565001.280.567501.280.4710001.610.5120001.930.6230003.210.612502503.530.795002.250.907502.250.8910002.250.6920003.531.0130004.491.1250007.060.973003004.171.205002.891.547502.891.3610003.211.7820003.532.0030004.821.8250008.991.505005008.991.0610006.421.8920007.702.88500010.912.681000027.294.07800100013.809.29200013.1612.80500034.6724.341000069.0220.651000100028.258.06500053.299.1210000100.1513.1715000117.1710.1820000178.4812.87From the tables, it is clear that the average results, as well as the run times for different instances of the proposed algorithm, are better than all other existing related algorithms.Table10 shows the total number of the best-known results obtained by each algorithm for every dataset. For example, the CC2 FS algorithm has the best-known results in 24 instances out of 32 instances in the data set type TI, class-SMPI. Here, ′−′ denotes the comparison of results with respect to best-known results that are not available for CC2 FS, FBPSO, and ABC-EDA algorithms for the BHOSLIB dataset. In the column with the caption “improvement%” we compute the results as follows:(16)Improvement%=TBR_MWDS_CRO−TBR_HTS−DSTS×100,where TBR_MWDS_CRO means the total number of best-known results by the MWDS_CRO method and TBR_HTS−DS denotes the total number of best-known results by HTS-DS, and TS is the total number of instances of the respective data set. We considered HTS-DS for comparisons because this algorithm is a state-of-the-art method.Table 10
Comparison of results with respect to best-known results.
Data setNo. of instancesCC2 FSFBPSOHTS-DSABC-EDAMWDS_CROImprovement (%)TI-SMPI32245276309.38TI-LPI2130601961.9TII-SMPI3231143220320TII-LPI21801622123.81BHOSLIB41——33—3914.63In Table11, we have shown the comparison in average time improvement for all the test datasets. The time improvement in % has been computed using by using the following equation:(17)Timeimprovementin%=AvgTHTS−DS−AvgTMWDS_CROAvgTHTS−DS×100,where AvgTHTS−DS refers to the average running time in second(s) for HTS-DS and AvgTMWDS_CRO denotes the average running time in second(s) for MWDS_CRO. Here we have considered the time of HTS-DS and MWDS-CRO algorithms. Since these two algorithms have the best-known results for most of the instances of all datasets. Our method improves average computational time by 92.97% for the TI-SMPI dataset which is the highest compared to all datasets, whereas the lowest improvement is 71.43% which is for the TII-SMPI dataset.Table 11
Comparison in average time improvement for datasets.
Data setNo. of instancesAvg T (s) in HTS-DSAvg T (s) in the proposed methodAvg T (s) improvementImprovement in (%)TI-SMPI3210.950.7710.1892.97TI-LPI2132.456.2226.2380.83TII-SMPI321.610.461.1571.43TII-LPI2133.326.8726.4579.38BHOSLIB41144.6231.42113.278.27Table12 shows the outcome for different components of the Type TI dataset. According to the table, it is clear that from the basic CRO operators, the best outcome is obtained for most instances. However, there are some instances in which the best results cannot be found after the basic CRO operators. In these cases, repair operators and common neighbor elimination procedure work to obtain the best results.Table 12
Type TI comparison of MWDS_CRO for different components.
VERanking based populationWithout repair operator and common neighbor eliminationWithout common neighbor eliminationWith repair operators and common neighbor elimination5050555.7531.3531.3531.3100427.6370.9370.9370.9250217.0175.7175.7175.7500148.894.994.994.975092.963.163.163.1100062.641.541.541.51001001189.41090.01061.01061.0250765.5618.9618.9618.9500480.5355.6355.6355.6750346.1255.8255.8255.81000293.7203.6203.6203.62000167.1107.4107.4107.41501501760.61580.51580.51580.52501466.31218.21218.21218.2500983.6744.6744.6744.6750753.7546.1546.1546.11000591.5432.8432.8432.82000344.8240.8240.8240.83000252.3166.9166.9166.92002502234.61909.71909.71909.75001588.41308.41238.21232.87501240.91038.6911.2911.210001022.4912.8723.5723.52000578.3412.7412.7412.73000429.9344.6312.2292.82502503030.52812.82633.02633.05002303.22108.01805.91805.97501861.21421.71361.91361.910001486.61242.21089.91089.92000891.4621.6621.6621.63000657.7447.9447.9447.95000452.2289.5289.5289.53003004221.63456.53223.93175.45003040.22652.72556.42435.67502256.61853.81853.81853.810002052.41816.21652.41494.020001240.7862.4862.4862.430001080.7624.1624.1624.15000623.7406.1406.1406.15005009852.46121.35702.15304.710006045.74087.33607.33607.320003668.02176.82176.82176.850003351.71624.21218.61042.310000867.2587.2587.2587.2800100012232.68765.47655.07655.020008668.05246.74982.14982.150004612.22432.62432.62432.6100001890.91393.71393.71393.71000100018656.812231.710574.410574.450006221.33656.63656.63656.6100004152.62099.82099.82099.8150002051.31519.71519.71519.7200001621.51200.91200.91200.9The time complexity of metaheuristic algorithms for searching the global optimal solution cannot be determined because these algorithms do not guarantee the finding of the global optimal solution within a given time limit. The metaheuristic algorithms such as CRO, GA, PSO, and ACO have no predefined end. Some metaheuristics need a few hundred or thousand iterations (with a big computational effort for each iteration) to obtain good or best results, while others need several million iterations (with only a tiny computational effort for each iteration).In the proposed algorithm, the CRO performed 100 iterations in one run. Moreover, in one full iteration, the algorithm performs 20 evaluations (popSize = 20). So, the number of evaluations in one run is100×20=2000. After performing the basic CRO operators, the obtained solutions went through repair operators and a common neighbor elimination procedure. Both of these methods run 1 time on the solution to obtain the best solution. For repair operator time complexity is On and for the common neighbor elimination procedure it is Omn. Here, n refers to the total number of nodes in a graph and m refers to the total number of neighbors of any node. So finally the total number of evaluations is 100×20+1=2001.


### 5.4. Statistical Significance Test

The statistical significance of MWDS_CRO over other algorithms is shown in this subsection by showing Wilcoxon signed-rank test. From Tables13 and 14, it is clear that MWDS_CRO is more significant than any other algorithms for both TI and TII instances. For the Wilcoxon test, for both instances, the value of the significance level is 0.05, and the hypothesis is two-tailed.Table 13
Wilcoxon signed-rank test for TI instances.
MWDS_CRO and CC2 FSMWDS_CRO and FBPSOMWDS_CRO and HTS-DSMWDS_CRO and ABC-EDAW value31.5000Mean difference2139.511311.643647.311345.55Sum of positive ranks403.511761531128Sum of negative ranks31.5000Z value−4.0219−6.0308−3.6214−5.9683Mean (W)217.558876.5564Standard deviation (W)46.2597.521.1294.5Sample size (N)29481747p value<0.00001<0.000010.0003<0.00001ResultSignificantSignificantSignificantSignificantTable 14
Wilcoxon signed-rank test for TII instances.
MWDS_CRO and CC2 FSMWDS_CRO and FBPSOMWDS_CRO and HTS-DSMWDS_CRO and ABC-EDAW value0000Mean difference4057.21461.059461.651837.74Sum of positive ranks10578021496Sum of negative ranks0000Z value−3.2958−5.4424−2.2014−4.8599Mean (W)52.5390—248Standard deviation (W)15.9371.66—51.03Sample size (N)1439631p value0.00096<0.00001—<0.00001ResultSignificantSignificant—SignificantDue to the insufficient sample size of MWDS_CRO and HTS-DS in Table11 for the type TII instance, mean (W), standard deviation (W), and p value can not be calculated. Thus the significance of the result cannot be shown as the significance of the result depends on the p value. If the p value is less than 0.05 then the result is significant.


## 5.1. Dataset

In our proposed system two types of benchmark datasets were used which were used by different researchers to solve the MWDS problem using heuristic algorithms [21–24, 27]. The benchmark data are of two types (TI and TII), and another class is BHOSLIB. These datasets can be found in [21]. Each vertex weight of the type I is randomly generated in between 20 to 70. For the instances in type II, the weight of vertex i is randomly generated in (1, degreei2), where degreei is the degree of vertex i. Both types I and II have 53 groups. There are 10 instances (the names of these 10 instances are n_m_0 to n_m_9) in each group. Instances with the same number of vertices (n) are classified as the same group. On the other hand, the complement graphs of the remaining instances in the BHOSLIB dataset were taken as useable graphs for the MWDS problem. To obtain the weights of the nodes of graphs, for each node, it is calculated as ωi=i%200+1. Here, ωi refers to the weight of a single node i.


## 5.2. Setting Parameters

Because the initialization of parameters in CRO is not guaranteed, obtaining an appropriate parameter value for the optimal molecule is a difficult process. In our study, we strive to discover the best molecule with the smallest weight by adjusting various factors, and we provide the findings for several parameter sets. In the population generation stage, a new parameterϵ is introduced. Figure 11 shows the tuning results of this parameter on some graph data of the TI instance. Besides this, Figures 12–14 refer to the different parameter tuning results of CRO which are the kinetic energy, alpha, and beta tuning. In all the graphs X-axis represents the total weight of the dominating set, and the Y-axis represents the parameter values. From the results of tuning, the parameter values are shown in Table 2.Figure 11
Epsilonϵ tuning.Figure 12
Kinetic energy (KE) tuning.Figure 13
Alphaα tuning.Figure 14
Betaβ tuning.


## 5.3. Performance Analysis

To analyze the performance of the proposed algorithm the minimum weights of the dominating set and the run time of the algorithm were considered. The existing related algorithms used different CPUs and different programming languages to obtain the output. Thus to compare the running time we implemented the HTS-DS approach in our implementation environment. As the HTS-DS approach obtained the best time compared with other algorithms, we show only the comparison between the proposed CRO-based method and the HTS-DS approach.The comparison regarding minimum weights between MWDS_CRO with other algorithms has been shown in Tables3–7. These tables depict the outcomes for types TI, TII, and BHOSLIB datasets, respectively. For both types TI and TII, the instances are divided into two classes which are small and medium particle instances (SMPI) and large particle instances (LPI). Here, the graphs with (50–250) nodes are classified as SMPI class while the others are represented as LPI class. Table 3 illustrates the minimum weights of class SMPI of type TI which are obtained after the implementation of different algorithms. Here, V and E refer to the number of vertices and edges in a graph. The outcome regarding weights of different algorithms of LPI class from TI type can be obtained from Table 4. Tables 5 and 6 refer to the minimum weights of various algorithms of classes SMPI and LPI of type TII. Table 7 shows the comparison of performance between HTS-DS and MWDS_CRO for the BHOSLIB dataset.Table 3
Type TI class SMPI-comparison of MWDS_CRO for various parameters with recent state-of-the-art algorithms.
VECC2 FSFBPSOHTS-DSABC-EDAMWDS_CROBest known5050531.3531.3531.3531.3531.3531.3100370.9370.98370.9370.9370.9370.9250175.7175.7175.7175.7175.7175.750094.994.994.994.994.994.975063.363.1663.163.163.163.1100041.541.541.541.541.541.51001001061.01062.991061.01061.41061.01061.0250618.9619.48618.9621.1618.9618.9500355.6355.74355.6355.8355.6355.6750255.8255.95255.8258.0255.8255.81000203.6203.6203.6205.2203.6203.62000107.4107.88107.4107.9107.4107.41501501580.51585.711580.51583.81580.51580.52501218.21223.311218.21223.21218.21218.2500744.6747.45744.6747.5744.6744.6750546.1548.15546.1549.2546.1546.11000432.9433.93432.8434.8432.8432.82000240.8241.47240.8243.7240.8240.83000166.9167.53166.9169.3166.9166.92002501910.41918.821909.71916.71909.71909.75001232.81239.711232.81243.41232.81232.8750911.2918.47911.2924.2911.2911.21000724.0727.09723.5729.0723.5723.52000412.7415.46412.9417.9412.9412.73000292.8294.03292.8298.1292.8292.82502502633.42649.732633.02647.02633.02633.05001805.91813.031805.91817.91805.91805.97501362.21375.321361.91382.61361.91361.910001091.11099.651090.11107.71089.91089.92000621.9625.41621.9628.6621.6621.63000447.9452.45448.0457.1448.0447.95000289.5291.18289.6297.4289.5289.5Table 4
Type TI class LPI-comparison of MWDS_CRO for various parameters with recent state-of-the-art algorithms.
VECC2 FSFBPSOHTS-DSABC-EDAMWDS_CROBest known3003003178.63203.623175.43193.03175.43175.45002438.12453.572435.62461.32435.62435.67501854.61870.81853.91876.01853.81853.810001495.01506.561494.11516.71494.01494.02000862.5871.89862.4878.8862.4862.43000624.3628.24624.4636.8624.1624.15000406.1409.08406.3417.7406.1406.15005005305.75392.455304.75370.75304.75304.710003607.83659.873608.63652.13607.63607.320002181.02210.282177.82225.02176.82176.850001043.31054.881044.21073.51042.31042.310000587.2594.32587.2605.8587.2587.280010007663.47771.527655.07755.77655.07655.020004982.15060.734991.75079.14987.34982.150002441.22470.382435.82492.22432.62432.6100001395.61417.161395.11440.01393.71393.71000100010585.310785.3710574.410766.410574.410574.450003671.83713.223662.73757.43656.63656.6100002109.02132.762102.22180.82099.82099.8150001521.51542.641521.91573.61519.71519.7200001203.61215.981205.61242.11200.91200.9Table 5
Type TII class SMPI-comparison of MWDS_CRO for various parameters with recent state-of-the-art algorithms.
VECC2 FSFBPSOHTS-DSABC-EDAMWDS_CROBest known505060.860.860.860.860.860.810090.390.390.390.390.390.3250146.7146.7146.7146.7146.7146.7500179.9179.9179.9179.9179.9179.9750171.1171.1171.1171.1171.1171.11000146.5146.5146.5146.5146.5146.5100100123.5123.5123.5123.5123.5123.5250209.2209.23209.2209.6209.2209.2500305.7305.72305.7305.7305.7305.7750384.5384.5384.5384.5384.5384.51000427.3427.3427.3427.3427.3427.32000550.6550.6550.6550.6550.6550.6150150184.5184.59184.5184.5184.5184.5250232.8233.04232.8233.1232.8232.8500349.5349.68349.5349.5349.5349.5750452.4452.4452.4452.8452.4452.41000547.2547.2547.2547.2547.2547.22000720.1720.1720.1720.1720.1720.13000792.4792.48792.4792.4792.4792.4200250271.7272.06271.7271.7271.7271.7500386.7386.77386.7386.8386.7386.7750497.1497.15497.1497.3497.1497.11000596.8597.21596.8597.3596.8596.82000884.6884.63884.6884.6884.6884.630001019.21019.451019.21022.41019.21019.2250250306.1306.79306.0306.1306.0306.0500440.7441.72440.7440.8440.7440.7750567.4568.63567.4568.2567.4567.41000668.6669.26668.6669.5668.6668.620001007.01007.911007.01010.21007.01007.030001250.61251.571250.61250.61250.61250.650001464.21464.21464.21464.21464.21464.2Table 6
Type TII class LPI-comparison of MWDS_CRO for various parameters with recent state-of-the-art algorithms.
VECC2 FSFBPSOHTS-DSABC-EDAMWDS_CROBest known300300369.9370.63369.9369.9369.9369.9500477.8478.32477.8478.4477.8477.8750613.3614.73613.3613.9613.3613.31000737.9738.93737.7738.1737.7737.720001093.81094.231093.81095.21093.81093.830001358.51359.571358.51361.31358.51358.550001682.71683.21682.71682.71682.71682.7500500623.6627.24623.6623.7623.6623.61000899.8904.24899.6901.6899.6899.620001363.31373.331362.21367.31362.21362.250002333.72335.412326.62342.12326.62326.6100003211.53211.83211.53214.53211.53211.580010001104.31113.031103.91104.51103.91103.920001632.31641.871630.81636.11630.81630.850002878.52901.622876.62888.12876.02876.1100004105.64107.194104.04121.54102.14102.8100010001237.71249.71237.51239.41237.51237.550003178.73206.73180.03194.43172.93172.9100004711.84733.584709.94748.14704.54704.8150005874.25896.915862.45897.65856.45856.4200006662.16681.646657.96691.56655.16655.1Table 7
BHOSLIB-comparison of MWDS_CRO for various parameters with the recent state-of-the-art algorithm.
InstancesHTS-DSMWDS_CROBest knownNameVEAvgT (s)AvgT (s)—frb30-15-145017827212.041.6212.08.12212.0frb30-15-245017874242.014.32242.04.56242.0frb30-15-345017809175.021.67175.05.51175.0frb30-15-445017831166.014.57166.02.23166.0frb30-15-545017794160.017.3160.03.59160.0frb35-17-159527856274.044.55274.010.76274.0frb35-17-259527847208.018.17208.03.02208.0frb35-17-359527931201.019.61201.06.63201.0frb35-17-459527842286.052.87286.013.33286.0frb35-17-559528143295.012.74295.02.41295.0frb40-19-176041314262.020.22262.05.60262.0frb40-19-276041263243.080.41243.012.51243.0frb40-19-376041095250.078.71250.016.06250.0frb40-19-476041605249.171.87249.014.18249.0frb40-19-576041619272.063.69272.010.87272.0frb45-21-194559186328.076.98328.013.96328.0frb45-21-294558624259.287.38259.022.34259.0frb45-21-394558245233.0132.06233.030.53233.0frb45-21-494558549399.079.67399.019.49399.0frb45-21-594558579312.592.06312.020.79312.0frb50-23-1115080072261.0159.38261.037.11261.0frb50-23-2115080851277.0161.75277.038.93277.0frb50-23-3115081068281.0125.9281.025.07281.0frb50-23-4115080258265.0191.06265.040.58265.0frb50-23-5115080035404.3108.5408.012.10404.0frb53-24-1127294227229.086.89229.07.99229.0frb53-24-2127294289298.0348.12298.052.68298.0frb53-24-3127294127182.0212.98182.041.26182.0frb53-24-4127294308189.0284.44189.058.56189.0frb53-24-5127294226204.078.23204.016.21204.0frb56-25-11400109676229.0107.66229.012.90229.0frb56-25-21400109401319.0145.09319.039.02319.0frb56-25-31400109379336.0163.23336.048.88336.0frb56-25-41400110038265.0169.65265.051.09265.0frb56-25-51400109601411.4128.27408.032.88408.0frb59-26-11534126555262.6192.54262.054.39262.0frb59-26-21534126163386.6159.25383.033.74383.0frb59-26-31534126082246.7348.38246.092.40246.0frb59-26-41534127011248.0357.5248.086.66248.0frb59-26-51534125982288.0396.44288.498.23288.0frb100-404000572774350.0963.58350.0181.16350.0Tables8 and 9 demonstrate the run times for all instances of types TI and TII successively for every individual algorithm.Table 8
Type TI-run time comparison in second of MWDS_CRO with the recent state-of-the-art algorithm.
VEHTS-DSMWDS_CRO50500.420.361000.420.362501.101.075002.011.817501.822.2510002.593.011001000.640.902501.611.015002.932.137503.253.1810006.895.39200012.9313.411501501.611.012501.930.775009.631.2475022.472.79100026.004.14200025.0414.66300030.0826.792002501.931.195006.421.5875025.0411.56100025.0419.92200025.6816.04300023.1112.092502503.531.385007.701.8175026.3218.20100025.3621.26200026.9616.62300024.4026.53500025.041.333003004.171.585005.141.0875024.083.29100027.934.78200028.572.49300030.501.26500026.001.925005008.673.17100033.388.69200034.677.29500034.996.481000031.784.25800100016.696.16200045.907.80500045.588.961000044.627.261000100027.938.02500050.4012.561000051.0413.651500052.009.682000057.4610.28Table 9
Type TII-run time comparison in second of MWDS_CRO with the recent state-of-the-art algorithm.
VEHTS-DSMWDS_CRO50500.320.131000.320.122500.130.105000.130.087500.130.0810000.320.071001000.640.242500.320.235000.320.267500.640.2610000.640.2820000.960.241501501.610.472500.960.325000.960.397501.280.4010001.280.3920001.610.4530002.570.432002501.610.565001.280.567501.280.4710001.610.5120001.930.6230003.210.612502503.530.795002.250.907502.250.8910002.250.6920003.531.0130004.491.1250007.060.973003004.171.205002.891.547502.891.3610003.211.7820003.532.0030004.821.8250008.991.505005008.991.0610006.421.8920007.702.88500010.912.681000027.294.07800100013.809.29200013.1612.80500034.6724.341000069.0220.651000100028.258.06500053.299.1210000100.1513.1715000117.1710.1820000178.4812.87From the tables, it is clear that the average results, as well as the run times for different instances of the proposed algorithm, are better than all other existing related algorithms.Table10 shows the total number of the best-known results obtained by each algorithm for every dataset. For example, the CC2 FS algorithm has the best-known results in 24 instances out of 32 instances in the data set type TI, class-SMPI. Here, ′−′ denotes the comparison of results with respect to best-known results that are not available for CC2 FS, FBPSO, and ABC-EDA algorithms for the BHOSLIB dataset. In the column with the caption “improvement%” we compute the results as follows:(16)Improvement%=TBR_MWDS_CRO−TBR_HTS−DSTS×100,where TBR_MWDS_CRO means the total number of best-known results by the MWDS_CRO method and TBR_HTS−DS denotes the total number of best-known results by HTS-DS, and TS is the total number of instances of the respective data set. We considered HTS-DS for comparisons because this algorithm is a state-of-the-art method.Table 10
Comparison of results with respect to best-known results.
Data setNo. of instancesCC2 FSFBPSOHTS-DSABC-EDAMWDS_CROImprovement (%)TI-SMPI32245276309.38TI-LPI2130601961.9TII-SMPI3231143220320TII-LPI21801622123.81BHOSLIB41——33—3914.63In Table11, we have shown the comparison in average time improvement for all the test datasets. The time improvement in % has been computed using by using the following equation:(17)Timeimprovementin%=AvgTHTS−DS−AvgTMWDS_CROAvgTHTS−DS×100,where AvgTHTS−DS refers to the average running time in second(s) for HTS-DS and AvgTMWDS_CRO denotes the average running time in second(s) for MWDS_CRO. Here we have considered the time of HTS-DS and MWDS-CRO algorithms. Since these two algorithms have the best-known results for most of the instances of all datasets. Our method improves average computational time by 92.97% for the TI-SMPI dataset which is the highest compared to all datasets, whereas the lowest improvement is 71.43% which is for the TII-SMPI dataset.Table 11
Comparison in average time improvement for datasets.
Data setNo. of instancesAvg T (s) in HTS-DSAvg T (s) in the proposed methodAvg T (s) improvementImprovement in (%)TI-SMPI3210.950.7710.1892.97TI-LPI2132.456.2226.2380.83TII-SMPI321.610.461.1571.43TII-LPI2133.326.8726.4579.38BHOSLIB41144.6231.42113.278.27Table12 shows the outcome for different components of the Type TI dataset. According to the table, it is clear that from the basic CRO operators, the best outcome is obtained for most instances. However, there are some instances in which the best results cannot be found after the basic CRO operators. In these cases, repair operators and common neighbor elimination procedure work to obtain the best results.Table 12
Type TI comparison of MWDS_CRO for different components.
VERanking based populationWithout repair operator and common neighbor eliminationWithout common neighbor eliminationWith repair operators and common neighbor elimination5050555.7531.3531.3531.3100427.6370.9370.9370.9250217.0175.7175.7175.7500148.894.994.994.975092.963.163.163.1100062.641.541.541.51001001189.41090.01061.01061.0250765.5618.9618.9618.9500480.5355.6355.6355.6750346.1255.8255.8255.81000293.7203.6203.6203.62000167.1107.4107.4107.41501501760.61580.51580.51580.52501466.31218.21218.21218.2500983.6744.6744.6744.6750753.7546.1546.1546.11000591.5432.8432.8432.82000344.8240.8240.8240.83000252.3166.9166.9166.92002502234.61909.71909.71909.75001588.41308.41238.21232.87501240.91038.6911.2911.210001022.4912.8723.5723.52000578.3412.7412.7412.73000429.9344.6312.2292.82502503030.52812.82633.02633.05002303.22108.01805.91805.97501861.21421.71361.91361.910001486.61242.21089.91089.92000891.4621.6621.6621.63000657.7447.9447.9447.95000452.2289.5289.5289.53003004221.63456.53223.93175.45003040.22652.72556.42435.67502256.61853.81853.81853.810002052.41816.21652.41494.020001240.7862.4862.4862.430001080.7624.1624.1624.15000623.7406.1406.1406.15005009852.46121.35702.15304.710006045.74087.33607.33607.320003668.02176.82176.82176.850003351.71624.21218.61042.310000867.2587.2587.2587.2800100012232.68765.47655.07655.020008668.05246.74982.14982.150004612.22432.62432.62432.6100001890.91393.71393.71393.71000100018656.812231.710574.410574.450006221.33656.63656.63656.6100004152.62099.82099.82099.8150002051.31519.71519.71519.7200001621.51200.91200.91200.9The time complexity of metaheuristic algorithms for searching the global optimal solution cannot be determined because these algorithms do not guarantee the finding of the global optimal solution within a given time limit. The metaheuristic algorithms such as CRO, GA, PSO, and ACO have no predefined end. Some metaheuristics need a few hundred or thousand iterations (with a big computational effort for each iteration) to obtain good or best results, while others need several million iterations (with only a tiny computational effort for each iteration).In the proposed algorithm, the CRO performed 100 iterations in one run. Moreover, in one full iteration, the algorithm performs 20 evaluations (popSize = 20). So, the number of evaluations in one run is100×20=2000. After performing the basic CRO operators, the obtained solutions went through repair operators and a common neighbor elimination procedure. Both of these methods run 1 time on the solution to obtain the best solution. For repair operator time complexity is On and for the common neighbor elimination procedure it is Omn. Here, n refers to the total number of nodes in a graph and m refers to the total number of neighbors of any node. So finally the total number of evaluations is 100×20+1=2001.


## 5.4. Statistical Significance Test

The statistical significance of MWDS_CRO over other algorithms is shown in this subsection by showing Wilcoxon signed-rank test. From Tables13 and 14, it is clear that MWDS_CRO is more significant than any other algorithms for both TI and TII instances. For the Wilcoxon test, for both instances, the value of the significance level is 0.05, and the hypothesis is two-tailed.Table 13
Wilcoxon signed-rank test for TI instances.
MWDS_CRO and CC2 FSMWDS_CRO and FBPSOMWDS_CRO and HTS-DSMWDS_CRO and ABC-EDAW value31.5000Mean difference2139.511311.643647.311345.55Sum of positive ranks403.511761531128Sum of negative ranks31.5000Z value−4.0219−6.0308−3.6214−5.9683Mean (W)217.558876.5564Standard deviation (W)46.2597.521.1294.5Sample size (N)29481747p value<0.00001<0.000010.0003<0.00001ResultSignificantSignificantSignificantSignificantTable 14
Wilcoxon signed-rank test for TII instances.
MWDS_CRO and CC2 FSMWDS_CRO and FBPSOMWDS_CRO and HTS-DSMWDS_CRO and ABC-EDAW value0000Mean difference4057.21461.059461.651837.74Sum of positive ranks10578021496Sum of negative ranks0000Z value−3.2958−5.4424−2.2014−4.8599Mean (W)52.5390—248Standard deviation (W)15.9371.66—51.03Sample size (N)1439631p value0.00096<0.00001—<0.00001ResultSignificantSignificant—SignificantDue to the insufficient sample size of MWDS_CRO and HTS-DS in Table11 for the type TII instance, mean (W), standard deviation (W), and p value can not be calculated. Thus the significance of the result cannot be shown as the significance of the result depends on the p value. If the p value is less than 0.05 then the result is significant.


## 6. Conclusion

More research on the MWDS problem is unavoidable because it has a wide range of practical applications, including data mining, the study of social networks and influence transmission, protein interaction networks, and covering codes. Due to its NP-hardness, this problem cannot be solved in a limited time using an exact algorithm. Thus implementation of a metaheuristic algorithm can obtain the proper solution. To cope with the issue, in this experiment, CRO based model has been proposed to solve the MWDS problem where population generates based on ranking. Then the population is intensified by applying the molecule intensification procedure. Then CRO operators work on the generated population. Besides CRO operators, the coordination of three supporting operators helps to eradicate infeasibility and redundancy from the up-to-date population. The further procurement of better offspring depends on the repair operator and the common neighbor elimination procedure. To prove the supremacy of our model, we compare the results with other well-known related algorithms, and the significance test is also provided. From the significance tests and comparison results, it is clear that our proposed model outperforms the other related existing algorithms.



---

*Source: 9640807-2023-01-11.xml*