Hybrid bat algorithm for minimum dominating set problem

Abstract

Graph domination is one of the NP-Complete problems that cannot be solved exactly in polynomial time. Hence, we propose a stochastic approach to tackle the minimum dominating set problem (MDS). The main aim of MDS is to find the minimum number of nodes that covers all other nodes in a graph. Thus, we present the problem in binary sequence to activate a node to be a dominator by setting it to the value of 1, or deactivate it by assigning its value to 0. In this paper, the stochastic search represented by hybrid swarm intelligence algorithm to find the smallest set of nodes that dominate the graph. This method uses population-based approach called bat algorithm (BA) which explore a wide area of the search space, thus it is capable in the diversification procedure. However, population-based algorithms are not good in exploiting the search space in comparison to single-solution based methods, therefore we included simulated annealing (SA) algorithm to balance between exploitation and exploration in order to reach a best possible solution. Our proposed method was experimented on benchmark datasets, which yielded results comparable to the state-of-the-art MDS methods. It can be concluded that the proposed method is an effective solution for MDS problem.

Keywords

Minimum dominating set meta-heuristics hybrid methods bat algorithm simulate annealing

1 Introduction

Optimization procedures work on finding the best possible solution(s) for a given problem, with respect to the objective of the problem, i.e., maximizing or minimizing the given cost function [36]. There are several fields that encounter optimization problems, such as scheduling, planning, engineering, computer science, and medicine. Generally, there are two categories of optimization problems, namely, static and dynamic [35]. In static optimization problems, the main aim is to find the global optima. While, dynamic optimization problems aim to find out the global optima and monitoring the changes that commonly occur during the optimization process of these type of problems. Our proposed study falls in the category of static optimization, and thus it focuses on finding the global optima hopefully the global best solution.

The dominating set (DS) problems are a general class of the optimization problems that are broadly used in wireless networking [6 , 33]. DS refers to those nodes in a particular graph that all other nodes in the same graph are connecting to it. In wireless network, finding the dominating set of the network topology graph is a common approach for clustering the networks [7 , 41]. The DS with minimum number of nodes is denoted as minimum dominating set (MDS). The MDS problem is hard combinatorial problem, classified as NP-Completeness [12], and in general cannot be solved exactly in polynomial time.

In the early 1990s of the last century, computational intelligence (CI) tools and their applications have grown rapidly since its inception at that period [1]. CI tools were firstly limited to neural networks, fuzzy logic and evolutionary computing as well as their hybrid methods [37]. However, in recent year swarm intelligence (SI) which is one of CI classes is broadly used for many domains. SI is the collective behaviour of decentralized and self-organized systems. A classic SI system consists of a population of simple agents which can communicate with each other by acting on their local environments. Though the agents in a swarm follow very simple rules, the interactions between such agents can lead to the emergence of very complicated global behaviour, far beyond the capability of single individual agent [10, 20]. Just to name a few instances in natural systems of SI, it includes, ant foraging, bird flocking, and fish schooling.

The most respected and popular SIAs are particle swarm optimization (PSO) which is inspired by the social behaviour of bird flocking or fish schooling [9], and ant colony optimization (ACO) which mimics the foraging behaviour of ant colony [8]. PSO is commonly used for real-parameter optimization whereas ACO has been effectively applied to solve combinatorial optimization problems. Recently, inspired by echolocation of micro-bats to attack a prey, a novel SIA, called bat algorithm (BA) was proposed in 2010 for efficiently solving complex optimization problems and had received extensive attention [5 , 42].

In this study, we tackle the problem of MDS by proposing SIA called BA that exploit a local search algorithm which is simulated annealing (SA) for the purpose of getting effective search in term of exploration and exploitation.

This paper is organized into six sections, including the current Section which introduced the proposed method and the tackled problem. Section 2 describes the formulation of MDS and the solution representation for the problem. While, Section 3 presents a review on the works done on MDS problem. Thereafter, the proposed model is explained in details in Section 4. Penultimately, we presented and discussed the experimental results in Section 5. Finally, Section 6 concludes the proposed model.

2 Problem description

The formulation of minimum dominating set (MDS) problem in this study is based on the graph theory. The general notation of a graph is G = (V, E) where V is the set of vertices (nodes) and E is the set of edges (links). Two nodes v and u are considered as neighbors if there is an edge between them, i.e., (v, u) ∈ E. A dominating set D is the set of nodes that belong to V and all the other nodes in V have link to D. In the other words, V - D = N are the set of nodes which have a connection to nodes in D, i.e., (D, N) ∈ E. In conclusion, every node not existed in D must be an element of N, and thus, N∩ D = ∅.

In practical, MDS is the problem of figuring out a minimum number of nodes in graph that dominates the others. The dominating set has connections to all graph nodes. In the problem instances of MDS, two nodes are considered connected if and only if they reside in the range of each other. Our study tackles MDS in connected graph (no node isolated) as shown in Fig. 1.

Fig.1

Connected graph.

In this study, the solution represented as a binary string that has length equals the number of nodes in the targeted graph as shown in Table 1. The bit that has a value of 1 means that node is one of the dominating set elements. Whilst, the node of value 0 means that node is not in the set D, but it belongs to N. Consequently, the solution that carries a minimum value represents the final solution of the problem. The optimal solution for the graph shown in Fig. 1 is represented by activating the nodes B and C as shown below.

Table 1

Binary representation for MDS of Fig. 1

A	B	C	D	E	F	G	H
0	0	1	1	0	0	0	0

To evaluate the solution according to the aforementioned MDS properties, we used the fitness function shown in Equation 1. $f (x) = \sum_{i = 1}^{n} x_{i} + Uncovered (x)$ (1) where n is the number of nodes (the size of the solution), and the first term of the equation implies the dominating set size. While, the last part of the function represents the nodes that reside out of the dominating set coverage. The proposed method invokes this function for every solution creation.

3 Related work

Finding the minimum number of nodes in graph is a hard combinatorial problem, classified as NP-Complete problem [12]. Many studies have been devoted to find MDS in minimum time complexity, which triggered by the work of finding the MDS in a tournament [26]. This work was followed by dedicated researches that proposed various approaches attempting to reduce the complexity [3 , 39]. Recently, MDS solved with minimum complexity based on membrane computing approach [25]. However, considering MDS with high dimensionality pose a combinatorial problem that cannot be solved in deterministic polynomial time. Consequently, a lot of research studies trended to solve MDS based on stochastic and approximation approaches. Recently, MDS has been solved based on stochastic search techniques, such as genetic algorithm [16], simulated annealing [2], and ant colony algorithm [17].

To achieve high degree of exploration in ant colony optimization (ACO) for MDS, Ho et al. proposed to use a technique borrowed from genetic algorithm called tournament selection [17]. Instead of always following the standard mechanism of selecting the next solution component, an ant would make its decision based on the outcome of a tournament among randomly selected allowable components. The frequency of the tournament selection is controlled by a probability measure. The use of tournament selection is coupled with an iteration-best pheromone update. Consequently, this method produces new solutions based on the intensive pheromone paths and the tournament selection mechanism according to a defined probability. They found the enhanced ant colony optimization could yield better solutions than genetic algorithm using fewer numbers of iterations. Yet, constructing a new solution for MDS based on the search history only such as in the case of ACO will exploit long time to find the best possible solution, due to the MDS is a binary problem.

In the context of stochastic algorithms, a hybrid genetic algorithm based on new fitness function proposed to tackle MDS, which is named HGA-MDS [16]. The search process in HGA-MDS invokes an accurate intensification schemes beside the GA search methodology in order to achieve high quality solutions. The intensification process in HGA-MDS goes through three different stages. In the first stage, they used a local search that works on adding or deleting nodes from the best solution found so far in order to improve its quality. Thereafter, a filtering procedure is used to refine the best solution by eliminating unnecessary nodes. In consequence, it reduces the dominating set in the best solution without losing the coverage. In the final stage of the intensification, they performed a procedure called elite dominating sets inspiration. This one works on saving the visited dominating sets (DS), and then, a trial solutions x^core is defined as the intersection of the best dominating sets in DS. If the number of nodes involved in x^core is less than that in x^best by at least two, then the zero position in x^core which gives the highest node-degree is updated to be one. This mechanism is continued until the number of nodes involved in x^core becomes less than that in x^best by one. The proposed HGA-MDS yielded promising results over 18 graph instances.

Recently, genetic algorithm implemented in parallel scheme to address the MDS problem [14]. This study was concerned about two essential objectives. Firstly, an investigation about the performance of the parallel genetic algorithm for the MDS is studied, which has been proved to produce desired solution. While, the second objective focused on formulating the genetic operators to fit the parallel scheme. These operators include selection, crossover, and mutation. Selecting solutions in the proposed genetic algorithm was based on two techniques which are tournament and roulette-wheel selections. Thereafter, a crossover of two types which are uniform and one-point has been applied to produce new solutions. Finally, a standard mutation process is performed to avoid losing good genes in the processed chromosome.

In addition, the study of Giap and Ha [14] proposed a new fitness function that takes in account the dominator and the dominated vertices as shown below: $Fit = {\begin{matrix} k^{2} / d, & d > 0 \\ 0, & d = 0 \end{matrix}$ (2) where k is the number of dominated vertices and d is the size of dominating set.

The main feature that characterizes the parallel genetic algorithm from the conventional one is the population migration. In the study of Giap and Ha, three different types of population migration have been used, namely, master-slave, single distributed population, and multi-deme population. However, they concluded that single distributed population is perform better than the others for all the tackled graph instances which vary from 100 to 2150 vertices.

The problem of finding MDS is tackled effectively using population-based algorithms as mentioned earlier in the case of ACO and GA algorithms. However, further studies on MDS have been conducted based on local search algorithms [2]. This method works in two phases, firstly, a stochastic local search (SLS) method is built to find local solutions next to given solutions. Then, a simulated annealing (SA) algorithm is invoked to enhance the solution of SLS with the ability of escaping from local optima. This method attempts to create effective solutions form the given one using three different procedures, i.e., Node-reduction, Node-addition, and Node-swapping. The accuracy of this method evaluated based on two test cases adopted from two independent studies [4, 34]. The authors found their proposed local search able to perform better than HGA-MDS, due to the effective manner that used to create neighbor solutions in the local search algorithm.

Generally, there are three different variants of dominating set in graph theory that have been solved via stochastic algorithms, which are minimum weight dominating set (MWDS) [19, 31], minimum connected dominating set (MCDS) [18], and MDS [2 , 17]. Tackling MDS might aid to solve MWDS as the later looking for the dominating set that carries minimum weight, therefore, finding MDS constitute the first step of solving MWDS. Similarly, figuring out the MDS in a graph and then finding the nodes that connect the existed MDS will lead to produce MCDS. In consequence, targeting MDS to best possible solution will aid to solve the other variants effectively, and thus we aim to solve the MDS rather than the other two variants.

Practically, all meta-heuristic algorithms that use population of solutions are capable to explore the problem space efficiently. Recently, Yang proposed an algorithm called bat algorithm (BA) based on the echolocation features of microbats [42]. BA uses a frequency-tuning technique to increase the diversity of the solutions in the population, while at the same time it uses the automatic zooming to try to balance exploration and exploitation during the search process by mimicking the variations of pulse emission rates and loudness of bats when searching for prey. In practical, BA uses random walks to avoid trapping local optima, which has been proven in the continuous domain. However, dealing with binary problem as MDS requires an intensive local search to achieve best possible solution [2]. Hence, in the current study we hybridized BA with SA to achieve an intensive search alongside the diversity feature of BA.

4 Proposed method

This section presents the experimental design based on the analysis obtained from the theoretical study in the literature review, where MDS-methods have been reviewed. This study achieves the research objectives through developing a hybridized method based on swarm intelligence behavior represented by bat algorithm. The proposed model solves the MDS problem as shown in Fig. 2.

Fig.2

The proposed hybrid Bat Algorithm.

In 2010, Yang developed a bio-inspired algorithm called bat algorithm (BA) based on the echolocation behavior of bats [42]. The echolocation capability of the micro-bats is fascinating as these bats can find their prey and discriminate different types of insects even in complete darkness. The BA mimics the micro-bats behavior which is drawn in the following three rules:

All bats use echolocation to sense distance, and they also know the difference between food/prey and background barriers.

Each bat flies randomly at position x_i and velocity v_i with a frequency f_min, varying wavelength λ and loudness A0 to search for prey. They can automatically adjust the wavelength (or frequency) of their emitted pulses and adjust the rate of pulse emission r ∈ [0, 1], depending on the proximity of their target.

Although the loudness can vary in many ways, BA assumes that the loudness varies from a large (positive) A0 to a minimum constant value A_min.

Based on the aforementioned rules, BA uses three parameters that control the search process, which are the frequency, pulse rate, and loudness. In practice, the frequency reside in specific range [f_min, f_max] which corresponds to a wavelength range [λ_min, λ_max]. In this study, we followed the original setting of the BA which proposed to set the frequency in the range [0, f_max], where f_max =100. The pulse rate varies from zero where no pulses at all to one as a maximum rate of pulses.

In BA, the pulse rate and the loudness are dynamic variables which must be updated iteratively as shown in Equations 3 and 4. Once a bat finds its prey, the pulse rate is increased while the loudness is decreased. The loudness can be set at any value that suits the problem. $A_{i}^{t + 1} = α A_{i}^{t}$ (3) $r_{i}^{t + 1} = r_{i}^{0} [1 - exp (- γ t)]$ (4) where the constant α and γ are similar to the cooling scheduler in the simulated annealing algorithm. Typically, the values of these two constants are equivalent. In our study, we followed the experimental value of the standard BA which is 0.9.

Practically, in a d-dimensional search each bat is associated with a velocity $v_{i}^{t}$ and a location $x_{i}^{t}$ , at iteration t. Among all the bats, there exists a current best solution x^*. Hence, the aforementioned rules can be translated into updating equations that leads the search process to the best solution. These equations can be mapped as follows: $f_{i} = f_{\min} + (f_{\max} - f_{\min}) β$ (5) $v_{i}^{t} = v_{i}^{t - 1} + (x_{i}^{t} - x^{*}) f_{i}$ (6) $x_{i}^{t} = x_{i}^{t - 1} + v_{i}^{t}$ (7) where β is a random number drawn from a uniform distribution in the period [0,1]. Here, x^* is the current global best solution which is located after comparing all the solutions.

Generally, BA resembles the global search of the particle swarm algorithm and the local search of the simulated annealing. Where, BA performs local search step using random walk as follows: $x^{'} = x + ɛ A^{t}$ (8) where ɛ is a random number vary between -1 and 1, and A^t is the average loudness of all the bats at the current iteration.

The proposed method attempts to establish an integral model that has effective ability in the search process. Due to the fact that population based algorithms which BA one of them are incompetent in exploiting the search space excellently as the single-based algorithms do, this study uses a local search algorithm. Though BA perform random walk as local search, it is not adequate to exploit the local neighborhood of the MDS problem. Thus, it incorporates local search algorithm named simulated annealing (SA) [21] to complement the search process as shown in Algorithm 1. SA has been selected in this work due to its excellent search ability in various domains. Simulated Annealing mimics the physical process of heating a material and then gradually dropping the temperature to decrease defects, thus minimizing the system energy. This algorithm avoids sticking in local optima by accepting worse solutions sometimes. Thus, SA is a general case of Hill Climbing Algorithm (HCA). Where, the latter accepts best solutions only, while SA accepts best moves always as well as accepts worse moves with respect to following criterion: ${exp}^{(- Δ S / T)} > R$ (9) where ΔS is the energy difference between the current and new solutions, while T represents the current temperature, and R is a random number between one and zero.

Simulated annealing is a single-based meta heuristic method that start the search by an initial solution then updates it iteratively. In each iteration, SA create new solution which is neighbor to the current one. The process of creating new solution is performed using specific procedure called neighborhood structure (NS) as shown in Algorithm 2.

The cooling scheduler of SA works on decreasing the temperature till reaching the frozen status, where the annealing process stops. In this study, we implement the popular scheduler “geometric cooling”, which is set to be performed after number of iterations. The geometric cooling consists of multiplying the previous temperature by a predefined cooling factor T * α as shown in line 17 of Algorithm 2. The values of the SA parameters in our study are given in Table 2.

Table 2

Simulated annealing parameters

Parameter	Value
n	20
T	1
α	0.99
stop	1e-8

The first parameter n in the table represent the epoch length of decreasing the temperature. The next one T is the starting temperature of the annealing process. While, α is the decremental factor which is applied periodically each n iteration. Finally, the stop parameter is the temperature level of stopping the annealing process.

In the context of local search process, our proposed method performs it within specific probability called local search rate (lr) which has been set experimentally to 20%. Limiting the local search procedure to lower ratio would not give enough space to exploit the problem space. On the other hand, allowing a lot of local search would lead to premature convergence to some local optima. Hence, the experiment shows that 20% is suitable ratio of performing the local search procedure for the MDS problem.

5 Experimental results

The proposed model in this study has been implemented on some instances of MDS problem. Each instance is given in the form of graph that has specific number of vertices and edges. The MDS raises in the area of network clustering, where the MDS corresponds to cluster heads in network clustering. Hence, the connection between each two nodes depend on the transmission range of the nodes. Hence, the euclidean distance between two nodes v and u must be less than the transmission range to be connected.

In this study, we created the graph instances of MDS that used in the literature. In specific, we created eight network graphs which are shown in Table 3.

Table 3
Graph instances

Graph Id #Nodes Range Area

G1 400 210–240 3000 X 3000

G2 350 200–230 2500 X 2500

G3 300 180–220 2000 X 2000

G4 250 130–160 1500 X 1500

G5 200 100–160 1000 X 1000

G6 200 70–120 700 X 700

G7 100 80–120 600 X 600

G8 80 60–120 400 X 400

Graph Id	#Nodes	Range	Area
G1	400	210–240	3000 X 3000
G2	350	200–230	2500 X 2500
G3	300	180–220	2000 X 2000
G4	250	130–160	1500 X 1500
G5	200	100–160	1000 X 1000
G6	200	70–120	700 X 700
G7	100	80–120	600 X 600
G8	80	60–120	400 X 400

Based on the directions of Bettstetters [4], we used random uniform distribution to generate the graph instances. In each graph instance, all the nodes have the same transmission range. For the purpose of experimenting the algorithm stability, we run each graph instance for ten times then we reported the statistics of the overall executions as shown in Table 4.

Table 4

Performance comparison of HBA and SAMDS

Graph instance		HBA			SAMDS
Graph Id	Range	Min.	Avg.	Std.	Min.	Avg.	Std.
G1	210	72	73.3	0.948	75	80.1	3.10
	220	70	71.0	0.816	73	79.2	3.18
	230	64	64.0	0.0	71	74.1	2.22
	240	58	59.3	0.674	63	68.8	2.98
G2	200	58	58.9	0.316	62	67.7	2.64
	210	53	55.0	1.054	59	63.2	2.53
	220	51	51.8	0.632	53	56.7	1.66
	230	45	47.1	1.370	51	54.5	2.14
G3	180	44	45.7	0.948	49	54.8	2.6
	190	44	44.4	0.516	47	51.4	1.98
	200	41	41.1	0.316	43	46.6	1.67
	210	37	37.7	0.823	40	44.7	2.12
	220	33	34.1	0.567	39	41.7	1.69
G4	130	49	50	0.666	54	57.1	1.62
	140	42	42.6	0.699	47	50.5	2.21
	150	37	37.9	0.316	43	46.5	1.82
	160	31	32.6	1.712	39	42.5	2.46
G5	100	36	36.7	0.483	41	34.1	1.55
	110	30	30.8	0.421	36	38.5	1.57
	120	26	26.3	0.483	30	32.3	1.39
	130	23	24.2	0.632	27	29.1	1.45
	140	22	23.0	0.666	25	26.7	1.29
	150	19	20.3	0.823	22	24.8	1.54
	160	18	18.0	0.0	20	22.5	1.15
G6	70	34	35.4	0.843	35	39.9	2.09
	80	28	28.2	0.421	29	33.5	1.73
	90	25	26.0	0.666	25	29.2	1.94
	100	21	21.8	0.421	20	24.2	1.70
	110	17	17.7	0.483	18	21.4	1.93
	120	15	16.2	0.788	15	19.5	1.43
G7	80	19	19.0	0.0	19	21.6	1.42
	90	18	18.0	0.0	17	19.2	1.58
	100	14	14.4	0.516	14	15.8	0.89
	110	12	12.3	0.483	12	13.5	0.89
	120	11	11.0	0.0	11	13.05	1.05
G8	60	16	16.0	0.0	16	17.4	0.94
	70	13	13.3	0.483	14	15.3	0.98
	80	10	10.6	0.516	11	12.8	1.11
	90	9	9.6	0.516	9	10.5	0.89
	100	8	8.4	0.516	8	9.7	0.66
	110	6	6.9	0.316	7	7.92	0.69
	120	6	6.7	0.483	6	7.65	0.81

The experiment has been executed using Dell machine of 8 Gb of the RAM and an intel core i7 CPU of 2.1 GHz. The operating system is Windows and the programming language used in this experiment is Matlab 2013.

The results reported in the Table 4 are based on three metrics which are minimum cost (Min cost), average cost (Avg cost), and standard deviation (Std). The minimum cost reports the quality of the best solution that gained through the runs. While, the average cost shows the median quality of the solutions gained during the experimental runs. Finally, the standard deviation shows the amount of variation among the yielded solutions. The values in the minimum cost field shows the size of the dominating set of the tackled graph. Obviously, the size of the dominating set is getting less at higher ranges as the connectivity of the nodes is increased. Fig. 3 shows the impact of the range on the solution quality.

Fig.3

The range impact on the solution quality for the eight graph instances.

For the purpose of proving the performance of our algorithm, we compared with a hybrid meta-heuristic method and simulated annealing algorithm which are reported in the literature review [2, 16]. We show the experimental performance of our algorithm in comparison to hybrid genetic algorithm that invokes three intensification procedures which are local search, filtering, and elite dominating sets inspiration, as shown in Table 5. In addition, Fig. 4 provides a comparison with another hybrid genetic algorithm and ant colony algorithm from the study of Potluri and Singh [30]. Also, we compared our experimental results to the simulated annealing that invokes a stochastic local search as shown in Table 4.

Table 5

Performance comparison of HBA and HGA-MDS

Graph instance		HBA			HGA-MDS
Graph Id	Range	Min.	Avg.	Std.	Min.	Avg.	Std.
G2	200	58	58.9	0.316	64	80.66	15.11
	210	53	55.0	1.054	59	73.04	4.242
	220	51	51.8	0.632	51	57.00	3.861
	230	45	47.1	1.370	49	54.95	4.097
G5	100	36	36.7	0.483	38	41.25	2.468
	110	30	30.8	0.421	33	36.8	1.542
	120	26	26.3	0.483	26	28.55	1.538
	130	23	24.2	0.632	25	27.05	1.316
	140	22	23.0	0.666	22	24.30	1.260
	150	19	20.3	0.823	20	21.40	0.994
	160	18	18.0	0.0	19	20.50	1.0513
G8	60	16	16.0	0.0	15	15.75	0.444
	70	13	13.3	0.483	12	13.30	0.7326
	80	10	10.6	0.516	10	11.65	1.089
	90	9	9.6	0.516	8	8.05	0.223
	100	8	8.4	0.516	7	7.90	0.307
	110	6	6.9	0.316	6	6.00	0.0
	120	6	6.7	0.483	5	5.55	0.5104

Fig.4

Performance comparison of HBA, HGA, and ACO. (a) Node range of 150 units. (b) Node range of 200 units. (c) Node range of 250 units.

In Table 4, HBA stand for hybrid bat algorithm which is used in this study for MDS problem. While, SAMDS is the simulated annealing that used for MDS in the study of Hedar and Ismail [2]. The HBA reveals smaller dominating set for the whole graphs tackled in this study. Moreover, it shows less variation overall the experimental runs.

In Fig. 4, the comparison is based on the average of 10 runs on unit disk graphs instances. These graphs consist of three instances of 50, 100, and 250 nodes placed in an area of size 1000 × 1000 units. For the comparison purposes, we selected the same range values of [30], which are 150, 200, and 250 as shown in Figs. 4 a, b, and c respectively. This comparison shows variable performance of the compared algorithm, where HBA outperforms the other for graphs of 50, and 100 nodes at the range value 200. Also, HBA produced smaller MDS than ACO in the graph of 250 nodes at range of 150. While, ACO and HGA obtained smaller MDS than HBA for the other graph instances.

In the context of performance comparison, we compare our algorithm with a hybrid genetic algorithm which is abbreviated as HGA-MDS [16] as shown in Table 5.

Table 5 shows the results of HBA and HGA-MDS for three graph instances as the latter addressed them only. Obviously, the HBA is more stable than HGA as it reveals less values for the standard deviation. However, the HGA shows smaller dominating sets for the eighth graph instance, where the number of nodes is less than 100. While, the HBA could outperform the HGA in the other graph instances, where smaller dominating sets have been produced.

Overall, the hybrid swarm intelligence proposed in this study revealed less number of dominator nodes roughly for the all tackled instances. A comparison with other studies in terms of solutions quality has been done to show the difference of our output than the others. In comparison to the hybrid genetic algorithm, our method is inferior in some ranges of the eighth graph instance only. However, our algorithm shows more stability over all the experimental runs.

6 Conclusion

Graph domination is one of the NP-Complete problems that cannot be solved exactly in polynomial time. Hence, we tackled this type of problems using a stochastic approach. This type of approaches can be categorized into two groups, i.e., population based and solo-based methods. Each of these types characterize by an effective search feature. The solo-based methods have effectiveness ability in exploiting the search space, while the population based methods are better in exploring the search space. Hence, we hybridized these techniques for the purpose of producing robust search method. The proposed algorithm tested on benchmark data set and yielded a better result in comparison to the literature methods. Thus, we conclude that the proposed method is an effective solution for MDS problem.

References

Alba

and Dorronsoro

, The exploration/exploitation tradeoff in dynamic cellular genetic algorithms, Evolutionary Computation, IEEE Transactions on9(2) (2007), 126–142.

Hedar

A.-R.

and Ismail

, Simulated annealing with stochastic local search for minimum dominating set problem, International Journal of Machine Learning and Cybernetics3(2) (2012), 97–109.

Bansal

and Umboh

S.W.

, Tight approximation bounds for dominating set on graphs of bounded arboricity, Information Processing Letters122 (2017), 21–24.

Bettstetter

, On the minimum node degree and connectivity of a wireless multihop network, In Proceedings of the 3rd ACM International Symposium on Mobile ad hoc Networking and Computing, ACM, 2002, pp. 80–91.

Bora

T.C.

, Coelho

L.D.S.

and Lebensztajn

, Bat-inspired optimization approach for the brushless dc wheel motor problem, IEEE Transactions on Magnetics48(2) (2012), 947–950.

Boria

, Murat

and Paschos

V.T.

, The probabilistic minimum dominating set problem, Discrete Applied Mathematics (2016).

Butenko

, Cheng

, Oliveira

C.A.

and Pardalos

, A new heuristic for the minimum connected dominating set problem on ad hoc wireless networks, Springer, 2004, pp. 61–73.

Dorigo

and Gambardella

L.M.

, Ant colony system: A cooperative learning approach to the traveling salesman problem, IEEE Transactions on Evolutionary Computation1(1) (1997), 53–66.

Eberhart

R.C.

and Kennedy

, A new optimizer using particle swarm theory, In Proceedings of the Sixth International Symposium on Micro Machine and Human Science, New York, NY, volume 1, 1995, pp. 39–43.

10.

Engelbrecht

A.P.

, Fundamentals of computational swarm intelligence, John Wiley & Sons, 2006.

11.

Erciyes

, Dagdeviren

, Cokuslu

and Ozsoyeller

, Graph theoretic clustering algorithms in mobile ad hoc networks and wireless sensor networks, Appl Comput Math6(2) (2007), 162–180.

12.

GareyM

and Johnson

, Computer and in tractability: Aguide to the theory of np-completeness, 1979.

13.

Gaspers

, Kratsch

and Liedloff

, Exponential time algorithms for the minimum dominating set problem on some graph classes, In Scandinavian Workshop on Algorithm Theory, Springer, 2006, pp. 148–159.

14.

Giap

C.N.

and Ha

D.T.

, Parallel genetic algorithm for minimum dominating set problem, In 2014 International Conference on Computing, Management and Telecommunications (ComManTel), 2014, pp. 165–169.

15.

Han

, Zone-based virtual backbone formation in wireless ad hoc networks, Ad Hoc Networks7(1) (2009), 183–200.

16.

Hedar

A.-R.

and Ismail

, Hybrid genetic algorithm for minimum dominating set problem, In International Conference on Computational Science and Its Applications, Springer, 2010, pp. 457–467.

17.

C.K.

, Singh

Y.P.

and Ewe

H.T.

, An enhanced ant colony optimization metaheuristic for the minimum dominating set problem, Applied Artificial Intelligence20(10) (2006), 881–903.

18.

Jovanovic

and Tuba

, Ant colony optimization algorithm with pheromone correction strategy for the minimum connected dominating set problem, Comput Sci Inf Syst10(1) (2013), 133–149.

19.

Jovanovic

, Tuba

and Simian

, Ant colony optimization applied to minimum weight dominating set problem, In Proceedings of the 12th WSEAS International Conference on Automatic Control, Modelling and Simulation, World Scientific and Engineering Academy and Society (WSEAS), 2010, pp. 322–326.

20.

Kennedy

, Kennedy

J.F.

, Eberhart

R.C.

and Shi

, Swarm intelligence, Morgan Kaufmann, 2001.

21.

Kirkpatrick

, Gelatt

C.D.

, Vecchi

M.P.

, et al., Optimization by simmulated annealing, Science220(4598) (1983), 671–680.

22.

Kuhn

and Wattenhofer

, Constant-time distributed dominating set approximation, Distributed Computing17(4) (2005), 303–310.

23.

Kumar

, Aggarwal

and Rawat

T.K.

, Bat algorithm: Application to adaptive infinite impulse response system identification, Arabian Journal for Science and Engineering41(9) (2016), 3587–3604.

24.

Lin

C.R.

and Gerla

, Adaptive clustering for mobile wireless networks, IEEE Journal on Selected areas in Communications15(7) (1997), 1265–1275.

25.

Mahmood

A.A.

, Maroosi

and Muniyandi

R.C.

, Membrane computing to enhance time efficiency of minimum dominating set, Mathematics in Computer Science10(2) (2016), 249–261.

26.

Megiddo

and Vishkin

, On finding a minimum dominating set in a tournament, Theoretical Computer Science61(2-3) (1988), 307–316.

27.

Nacher

J.C.

and Ochiai

, Analytical solution for the size of the minimum dominating set in complex networks, International Journal of Modeling, Simulation, and Scientific Computing08(01) (2017), 1750005.

28.

Nakamura

R.Y.M.

, Pereira

L.A.M.

, Costa

K.A.

, Rodrigues

, Papa

J.P.

and Yang

X.S.

, Bba: A binary bat algorithm for feature selection, In 2012 25th SIBGRAPI Conference on Graphics, Patterns and Images, 2012, pp. 291–297.

29.

Nieberg

and Hurink

, A ptas for the minimum dominating set problem in unit disk graphs, In International Workshop on Approximation and Online Algorithms, Springer, 2005, pp. 296–306.

30.

Potluri

and Singh

, Two hybrid meta-heuristic approaches for minimum dominating set problem, Swarm, Evolutionary, and Memetic Computing, 2011, pp. 97–104.

31.

Potluri

and Singh

, Hybrid metaheuristic algorithms for minimum weight dominating set, Applied Soft Computing13(1) (2013), 76–88.

32.

Rodrigues

, Pereira

L.A.

, Nakamura

R.Y.

, Costa

K.A.

, Yang

X.-S.

, Souza

A.N.

and Papa

J.P.

, A wrapper approach for feature selection based on bat algorithm and optimum-path forest, Expert Systems with Applications41(5) (2014), 2250–2258.

33.

Samuel

, Zhuang

and Preiss

, Dtn based dominating set routing for manet in heterogeneous wireless networking, Mobile Networks and Applications14(2) (2009), 154–164.

34.

Sanchis

L.A.

, Experimental analysis of heuristic algorithms for the dominating set problem, Algorithmica33(1) (2002), 3–18.

35.

Talbi

E.-G.

, A taxonomy of hybrid metaheuristics, Journal of Heuristics8(5) (2002), 541–564.

36.

Talbi

E.-G.

, Metaheuristics: From design to implementation, volume 74. John Wiley & Sons, 2009.

37.

Tettamanzi

A.G.

and Tomassini

, Soft computing: Integrating evolutionary, neural, and fuzzy systems, Springer Science & Business Media, 2013.

38.

Tharakeshwar

, Seetharamu

and Prasad

B.D.

, Multiobjective optimization using bat algorithm for shell and tube heat exchangers, Applied Thermal Engineering110 (2017), 1029–1038.

39.

Wakabayashi

and Kikuchi

, Solving the minimum dominating set problem with instance-specific hardware on fpgas, In Proceedings 2005 IEEE International Conference on Field-Programmable Technology, IEEE, 2005, pp. 69–76.

40.

Wang

, Wang

and Li

X.-Y.

, Distributed low-cost backbone formation for wireless ad hoc networks, In Proceedings of the 6th ACM International Symposium on Mobile ad hoc Networking and Computing, ACM, 2005, pp. 2–13.

41.

, Dai

, Gao

and Stojmenovic

, On calculating power-aware connected dominating sets for efficient routing in ad hoc wireless networks, Journal of Communications and Networks4(1) (2002), 59–70.

42.

Yang

X.-S.

, A new metaheuristic bat-inspired algorithm, Springer, 2010, pp. 65–74.

Hybrid bat algorithm for minimum dominating set problem

Abstract

Keywords

1 Introduction

2 Problem description

Table 3 Graph instances Graph Id #Nodes Range Area G1 400 210–240 3000 X 3000 G2 350 200–230 2500 X 2500 G3 300 180–220 2000 X 2000 G4 250 130–160 1500 X 1500 G5 200 100–160 1000 X 1000 G6 200 70–120 700 X 700 G7 100 80–120 600 X 600 G8 80 60–120 400 X 400

References

Table 3
Graph instances

Graph Id #Nodes Range Area

G1 400 210–240 3000 X 3000

G2 350 200–230 2500 X 2500

G3 300 180–220 2000 X 2000

G4 250 130–160 1500 X 1500

G5 200 100–160 1000 X 1000

G6 200 70–120 700 X 700

G7 100 80–120 600 X 600

G8 80 60–120 400 X 400