A modified artificial bee colony algorithm for load balancing in network-coding-based multicast

Abstract

This paper studies the load balancing optimization problem in network-coding-based multicast and proposes a modified artificial bee colony algorithm (MABC) to address it. MABC is featured with three novel schemes, including a food source initialization scheme, a novel selection scheme and a neighborhood search scheme. The first scheme generates a set of high-quality food source positions, ensuring that the exploration of the search begins with promising areas in the search space. In the second scheme, a nectar source library (NSL) is used to store a set of best solutions found during the iterative search. Each scout bee produces a new food source based on a food source randomly selected from NSL. This helps to generate food sources with high nectar amounts. The last scheme is a neighborhood search scheme to strengthen population diversity and avoid local optima, where a probability vector is maintained and utilized to carry out fine local exploitation. Experimental results demonstrate that the proposed MABC outperforms a number of state-of-the-art evolutionary algorithms with respect to the quality of solutions obtained.

1 Introduction

Nowadays, increasingly more Internet applications require delivery of multimedia streams from one source to a group of receivers, such as interactive gaming, teleconferencing, distance education. Multicast, as a cost-effective point-to-multi-point communication paradigm, is able to provide sufficient support in delivering multimedia applications with stringent quality-of-service (QoS) requirements (Miller 1998; Benslimane 2007). Nevertheless, traditional multicast cannot have theoretical maximal throughput achieved all the time due to the store-and-forward scheme employed (Ford and Fulkerson 2009). This could heavily deteriorate multicast performance when supporting multimedia applications with real-time and high bandwidth requirements.

Network coding (NC) allows complicated mathematical operations performed at intermediate nodes within a communication network (Ahlswede et al. 2000). Data packets coming from different ports can be recombined (encoded) into a new packet when necessary. At receivers, the coded information is decoded so as to obtain the original data sent from the source. It has been reported that NC brings a number of attractive benefits to communication networks, in terms of data delivery security, network failure diagnosis, energy consumption, and so on (Fragouli and Soljanin 2007). In particular, with NC incorporated, multicast is always able to achieve theoretically maximized data rate. Therefore, NC-based multicast has the potential to well support the delivery of one-to-many multimedia streams (Li and Yeung 2003).

With the explosive growth in Internet users, network resources (such as computational, buffer and bandwidth resources) are dramatically consumed, which may seriously affect the performance of network with respect to effective data communication and delivery. Although the infrastructure of Internet is evolving rapidly, demand of end users is increasing even faster. The network traffic thus becomes increasingly heavy. Under such circumstances, it is natural to consider how to meet the demand of end users for better data transmission services with limited network resources. From the point of view of network service providers, they expect to make full use of the network infrastructure and various resources to accommodate as many users as possible and provide them with appropriate QoS guarantees. Generally, a more balanced traffic load helps to gain better utilization of network resources. Load balancing (LB) has been one of the key issues when designing a communication network (Wang and Pavlou 2007).

LB in the context of network-coding-based multicast (NCM) has attracted interests from a number of research groups. Chi et al. (2006) investigate the performance of a number of routing algorithms for NCM and demonstrate that the proposed NCM routing algorithm performs better than the shortest path distribution tree and the maximum-rate distribution tree routing algorithms, regarding LB and resource consumption. Hou et al. (2008) propose an adaptive network coding scheme for code updates in wireless sensor networks, namely AdapCode. AdapCode is able to adaptively change the coding scheme and thus reduce broadcast traffic. Vieira et al. (2012) study the problem of multi-beam satellite LB with network coding and provide enhanced and robust LB scheme to unequal load demands between beams. The core idea of the scheme is to minimize the packet delivery time with traffic demand per beam and channel conditions fully considered. However, all above research is under the assumption that every coding-possible node has to perform packet recombination (i.e., coding operation) no matter whether it is necessary. Since coding requires complex math operations performed, the more the coding operations are needed, the heavier the computational resources are consumed. Fortunately, Kim et al. (2006, 2007a, b) point out that only a subset of coding-possible nodes is sufficient to achieve NCM. It is hence essential to investigate the problem of LB with coding operations necessarily performed. Xing et al. (2016) formulate a LB optimization problem in NCM and develop an improved population-based incremental learning (iPBIL) to solve the problem. It is reported that iPBIL achieves better solution quality than other existing algorithms, such as genetic algorithm, quantum-inspired evolutionary algorithm, univariate marginal distribution algorithm. However, as we have observed in our present work, iPBIL still suffered from weak local exploitation and slowly converged population, even though a flexible probability vector update scheme was proposed for guiding the search to explore promising regions and strengthening the overall performance of the algorithm. A modified artificial bee colony (ABC) algorithm has thus been devised in this paper to tackle the LB optimization problem in NCM (LB-NCM).

Inspired by swarm intelligence, ABC mimics the natural foraging and information sharing behaviors of honey bee colonies (Karaboga 2005). Because it is simple in concept, easy to implement and with fewer control parameters (Karaboga and Basturk 2008), ABC has drawn a lot of academic attention and been successfully applied to various optimization problems. An improved ABC algorithm is proposed to tackle the traveling salesman problem, where loyalty value is introduced to determine the role of each bee (e.g., as an employed or onlooker bee). Also, the algorithm utilizes an opt-2 local search technique to achieve a decent local exploitation performance (Kocer and Akca 2014). Xu et al. (2017) introduce an adaptive hybrid ABC that incorporates Nelder–Mead simplex search into basic ABC for estimating the maximum likelihood of the q-Weibull parameters. A novel ABC based on clustering technique is applied to the paddy rice image classification problem (Wan et al. 2017). Dahan et al. (2017) present an enhanced ABC to select the best combination of QoS-aware web services with user requirements satisfied, where exploration and exploitation are finely controlled. Sundar et al. (2017) study the job-shop scheduling problem with no-wait constraint and develop a hybrid ABC that effectively coordinates various components of the algorithm, such as the initialization phase, the selection procedure, the local search. Kumar and Sahoo (2017) propose a two-step ABC for solving the clustering problem. To gain a balance between global exploration and local exploitation abilities, the authors adopt K-means algorithm to initialize the bee colony and introduce social behaviors of particle swarm into the solution search equation. Xiang et al. (2014) present a multi-elitist ABC for real-parameter optimization, with the idea of particle swarm optimization (PSO) integrated. Guo et al. (2017) propose a hybrid ABC for the community uncover problem in complex networks, where a network dynamic algorithm is adopted to initialize the nectar sources and a heuristic-based searching function is devised to explore the search space. Bai et al. (2017) incorporate an orthogonal learning strategy into the basic ABC algorithm to obtain an appropriate trade-off between exploration and exploitation capabilities for the optimal power flow problem. Shokouhifar and Jalali (2017) successfully combine ABC and simulated annealing (SA) for the simplified factorized symbolic analysis of analog circuits, making use of the advantages of the both.

In terms of the numerical optimization, a considerable amount of researchers have been devoted to the development of various ABCs. For example, Gao et al. (2015a) propose a Gaussian-distribution-based solution search equation that is able to exploit the hidden information at the onlooker phase, and a parameter adaptation strategy and a fitness-based neighborhood scheme are used to enhance the exploration at the employed bee phase. Xiang and An (2015) propose a combinatorial solution search equation for accelerating the convergence of ABC. Besides, the authors integrate a chaotic search technique into the scout bee phase for avoiding local optima. Karaboga and Gorkemli (2014) strengthen the local search capability of ABC by making use of the best solution among the neighborhoods. Gao et al. (2015b) develop a variant ABC based on information learning. Inspired by the division of labor and the cooperation in human history, the authors devise a clustering-partition-based multi-population management technique and two information exchange mechanisms for facilitating the overall performance of the proposed ABC. Liu et al. (2015) present a modified ABC with enhanced convergence and searching performance. In order to carry out fine exploitation, the proposed ABC incorporates the previous best solution into the employed bee phase and the global best solution into the onlooker bee phase, respectively. Besides, in the scout bee phase, food sources are updated so as to keep population diversity at a relatively high level. Zhou et al. (2017) integrate the neighborhood search technique into the evolutionary framework of ABC for achieving a balanced global exploration and local exploitation. Song et al. (2017) introduce a novel ABC with local exploitation enhanced, where random and current best solutions are utilized by the solution search equation and a step-size-tunable objective function value is designed. Li et al. (2017) develop a novel gene recombination operator for accelerating convergence behaviors of a number of ABCs, where a proportion of promising solutions are selected to produce candidate solutions.

Apart from continuous optimization, an increasing amount of research efforts have been dedicated to binary optimization problems. The sigmoid function is commonly used for converting continuous values to binary ones. Marinakis et al. (2009) propose a discrete ABC (DABC) with the greedy randomized adaptive search procedure (GRASP) incorporated. Singhal et al. (2015) improve the performance of the basic ABC by three modifications, including a dissimilarity-based binary solution generation scheme, an elite-guided intelligent scout bee phase, and a swap-move-based local search procedure. Kashan et al. (2012) develop a discrete version of ABC algorithm, called DisABC. A new differential expression is devised to produce offspring solutions by making use of the Jaccard coefficient rather than the arithmetic subtraction operation. Hancer et al. (2015) propose a modified discrete ABC algorithm (MDisABC) based on DisABC (Kashan et al. 2012). Different from the latter, MDisABC employs three neighbors to generate a mutant solution and recombines it with the current solution for offspring generation. This, to a certain extent, helps improve the search ability. Kiran and Gündüz (2014) devise a binary ABC (referred to as binABC), with the XOR-based operation introduced to the solution-updating equation. Later on, Kiran (2015) extends his previous work by developing the so-called ABCbin, where the obtained food source position is converted to binary values before the objective function evaluation. Zhang and Zhang (2017) present a binary-coded ABC (BABC) for addressing the spanning tree construction problem in vehicular ad hoc networks (VANETs). The authors introduce a two-element variation technique to keep the number of edges in a binary string unchanged.

In this paper, the LB-NCM problem is investigated. To address it, we present a modified ABC with three performance-enhancing schemes. The first scheme is a food source initialization scheme, where a number of food sources with high nectar amounts are produced by repeatedly recombining an all-one vector and a randomly generated solution via two-point crossover. This scheme is able to provide the initial bee colony with sufficient high-quality food sources, which helps to guide the exploration toward promising regions. The second one is a selection scheme based on nectar source library (NSL) in the scout bee phase, with a number of best-so-far food source positions stored in a NSL. When an employed bee becomes a scout, it then randomly picks up one of the positions from NSL and produces a new position of food source based on the selected one. It helps to generate high-quality food sources and thus improve the global exploration. In the third scheme, a novel neighborhood search scheme is developed to maintain diversification and enhance local exploitation, where for each food source, a probability vector is constructed by two food source positions, namely the current solution and the global best solution. This scheme helps to achieve a better trade-off between global exploration and local exploitation during the evolution. A large number of computer simulations have been conducted, and the results show that the proposed algorithm achieves the best performance than a set of state-of-the-art evolutionary algorithms in terms of the best solution obtained.

2 Problem description

In this paper, we use a directed graph $G = (V, E)$ to represent a communication network, where V and E are the node set and link set, respectively. Let |E| be the cardinality of E, i.e., the number of links in E. Number every link in E, and let the ith link be denoted by $e_{i} \in E$. Link $e_{i}$ is associated with a maximum bandwidth $B_\mathrm{m}(i)$ and a currently occupied bandwidth $B_\mathrm{c}(i)$, where $B_\mathrm{c}(i) \le B_\mathrm{m}(i)$. In NCM, a source node $s \in V$ expects to deliver data information to a set of receives $T = \{t_{1}$, $t_{2},{\ldots },t_{d}\}$, with a bandwidth $R_{s\rightarrow T}$.

If an intermediate node has more than one incoming link, it is referred to as mergingnode (Kim et al. 2007a). In a communication network, only merging nodes are capable of recombining data information received from different incoming ports, i.e., performing coding operations. To support a NCM is to find a subgraph in G, with bandwidth requirement and constraints met. The subgraph is called NCM subgraph and represented by $G_{s\rightarrow T}$. Such a subgraph is composed of a number of paths, with each path from the source to one of the receivers. Besides, those terminating at the same receiver are referred to as link-disjoint paths since they cannot share any common link (Kim et al. 2007a).

In an arbitrary NCM subgraph, extra bandwidth consumption incurs in all occupied links. Each of them costs identical bandwidth, $B_{s\rightarrow T}$, for delivering NCM data. So, if for receiver $t_{k}$ there are R link-disjoint paths, the total bandwidth between s and $t_{k}$ is $R \cdot B_{s\rightarrow T}$, where R is an integer. In network G, each link is associated with bandwidth utilization ratio (BUR), namely the ratio of consumed bandwidth to the maximum bandwidth. Let BUR of link $e_{i}$ and the number of link-disjoint paths be denoted by $\psi _{i}$ and $\theta$, respectively. Let $\rho _{1}(s$, $t_{k}),{\ldots },\rho _{\theta }(s$, $t_{k}$) be the link sets of link-disjoint paths from s to $t_{k}$, and let $\gamma (s, t_{k})$ be the achievable bandwidth from s to $t_{k} \in T$ in $G_{s\rightarrow T}$, respectively.

Actually, the smaller the average BUR is, the more the network traffic load is balanced. The LB optimization problem concerned in the paper is to find a NCM subgraph $G_{s\rightarrow T}$, where the average BUR is minimized and a number of constraints are satisfied.

Minimize:

$$\begin{aligned} \Psi (G)=\left( \sum _{i\in \left| E \right| } {\psi _i }\right) /\left| E \right| , \end{aligned}$$

(1)

where

$$\begin{aligned} \psi _i= & {} (B_{s\rightarrow T} \cdot \varepsilon _i +B_\mathrm{c} (i))/B_\mathrm{m} (i) \end{aligned}$$

(2)

$$\begin{aligned} \varepsilon _i= & {} \left\{ {\begin{array}{ll} 1,&{}\quad e_i \in G_{s\rightarrow T} \\ 0,&{}\quad \mathrm{otherwise,} \\ \end{array}} \right. \end{aligned}$$

(3)

subject to:

$$\begin{aligned} B_{s\rightarrow T} +B_\mathrm{c} (i)\le & {} B_\mathrm{m} (i),\quad \forall i=1,\ldots ,\left| E \right| \end{aligned}$$

(4)

$$\begin{aligned} \gamma (s,t_k )= & {} \theta \cdot B_{s\rightarrow T} ,\quad \forall t_k \in T\end{aligned}$$

(5)

$$\begin{aligned} \rho _i (s,t_k )\cap \rho _j (s,t_k )= & {} \varnothing ,\quad \forall i,j=1,\ldots ,\theta ,i\ne j. \end{aligned}$$

(6)

Objective (1) defines the objective is the minimization of the average BUR; Eq. (2) specifies the BUR of link $e_{i}$, where factor $\varepsilon _{i}$ is given in Eq. (3); the summation of $B_{s\rightarrow T}$ and $B_\mathrm{c}(i)$ cannot exceed $B_\mathrm{m}(i)$, as shown in Constraint (4); the achievable bandwidth between s and $t_{k}$ is defined in Eq. (5); the link-disjoint constraint is shown in Constraint (6).

3 Basic ABC algorithm

ABC is a population-based stochastic search meta-heuristic inspired by the foraging behavior of honey bee swarm (Karaboga 2005). There are three classes of artificial bees in the colony: employed bees, onlookers and scouts. Employed bees are placed on the food sources where they make collections and calculate the nectar amounts. Onlookers get the nectar information from employed bees via watching waggle dances and choose food sources with probabilities. When a food source is abandoned, the associated employed bee becomes a scout so as to explore a new food source. For an arbitrary food source, its position and nectar amount represent a solution to the optimization problem concerned and the fitness of this solution, respectively. Better food sources will attract more bees. ABC consists of four phases, including initialization, employed bee, onlooker bee and scout bee phases.

3.1 Initialization phase

In the initialization phase, a set of $N_{p}$ food source positions are randomly produced. Let $X_{i} = (x_{i1}, x_{i2},{\ldots }, x_{iD})$ be the position of the ith food source, where D is the dimension of decision variables. Originally, the jth locus of $X_{i}$, $x_{ij}$, is calculated by Eq. (7).

$$\begin{aligned} x_{ij} =x_j^{\min } +R(0,1)\cdot (x_j^{\max } -x_j^{\min } ), \end{aligned}$$

(7)

where R(0,1) is a randomly generated number in the range of (0, 1), and $x_j^{\max }$ and $x_j^{\min }$ are the predefined upper and lower bounds of the jth locus, respectively. Note that the above initialization method is designed for generating continuous decision variables. After the initialization, cycles of the search processes of the employed bees, onlookers and scouts are repeated for the purpose of food source improvement.

3.2 Employed bee phase

Each food source is associated with only one employed bee. Each employed bee finds a new position of food source, $V_{i} = (v_{i1}, v_{i2},{\ldots }, v_{iD})$, in the neighborhood of $X_{i}$, according to Eq. (8).

$$\begin{aligned} v_{ij} =x_{ij} +R(-1,1)\cdot (x_{ij} -x_{kj} ), \end{aligned}$$

(8)

where $j \in \{1,{\ldots },D\}$ and $k \in \{1,{\ldots },N_{p}\}$ are both randomly selected indices; k and i are different; R(− 1,1) is randomly generated in the range of [− 1,1].

Then, $V_{i}$ will be evaluated and compared to $X_{i}$. If the new food source offers higher nectar amount than the old one, the corresponding employed bee will memorize $V_{i}$; otherwise, $X_{i}$ is retained.

3.3 Onlooker bee phase

After all employed bees complete the search processes, the employed bees will perform waggle dance so that the onlookers are able to share the information about the positions of food sources and the corresponding nectar amounts with them. For an arbitrary onlooker bee in the hive, the probability of selecting the ith food source, ${ pf}_{i}$, is calculated by Eq. (9), where ${ fit}_{i}$ is the nectar amount of the ith food source. It is clear that food sources with richer nectar amounts (i.e., higher fitness) will be selected with higher probabilities. Once an onlooker chooses a food source, e.g., $X_{k}$, a new position of food source, e.g., $V_{k}$, is randomly generated within the neighborhood of $X_{k}$ according to Eq. (8). Between $X_{k}$ and $V_{k}$, the winner will be retained.

$$\begin{aligned} pf_i =\frac{fit_i }{\sum _{i=1}^{{N}_p } {fit_i } }. \end{aligned}$$

(9)

3.4 Scout bee phase

If a position cannot be improved within a predefined number of cycles, that food source will be abandoned and the corresponding employed bee becomes a scout. The scout will randomly generate a new food source according to Eq. (7). It is noted that the predefined number of cycles is a control parameter, known as the limit for abandonment.

3.5 ABC for combinatorial optimization

For combinatorial optimization, Eqs. (10) and (11) are usually adopted to convert continuous decision variables to discrete ones, where the position of food source $X_{i}$ is denoted by ($y_{i1}$, $y_{i2},{\ldots }, y_{iD}$) (Marinakis et al. 2009).

$$\begin{aligned} \mathrm{sig}(x_{ij} )= & {} \frac{1}{1+\exp (-x_{ij} )} \end{aligned}$$

(10)

$$\begin{aligned} y_{ij}= & {} \left\{ {\begin{array}{ll} 1,&{} \quad \hbox { if }R\hbox {(0,1)}<\mathrm{sig}(x_{ij} ) \\ 0,&{}\quad \hbox { otherwise.} \\ \end{array}} \right. \end{aligned}$$

(11)

4 A modified ABC algorithm for LB-NCM

We first introduce the solution representation and fitness evaluation and then describe the three performance-enhancing schemes in detail. In the end, the overall structure of the proposed algorithm is given.

4.1 Solution representation and fitness evaluation

The binary link state (BLS) representation has been widely adopted when tackling NCM-related optimization problems, e.g., LB-NCM problem (Xing et al. 2016), multi-objective NCM routing problems (Ahn and Yoo 2012; Xing and Qu 2013), network coding resource minimization problems (Kim et al. 2007a, b; Xing et al. 2010; Xing and Qu 2011). So, BLS-based solution representation is also used in this paper.

BLS is based on graph decomposition (GD), where for an arbitrary merging node, each of its incoming links is associated with a binary variable indicating if this link is active (Kim et al. 2007a). The GD method has each merging node in network G decomposed into a group of auxiliary nodes and links, clearly illustrating all possibilities for information flows to pass by. To be specific, if there is a merging node with $n_\mathrm{inc}$ incoming links and $n_\mathrm{out}$ outgoing links, this node is decomposed into $n_{inc}$ incoming auxiliary (IA) nodes and $n_\mathrm{out}$ outgoing auxiliary (OA) nodes. Besides, a directional auxiliary link is generated from each of the $n_\mathrm{inc}$ IA nodes to each of the $n_\mathrm{out}$ OA nodes. Last but not least, those links originally connected with the merging node are redirected to their corresponding incoming and outgoing auxiliary nodes, respectively. After GD, network G is converted to network $G_\mathrm{GD}$. In BLS-based solution representation, a string of binary variables is used to represent a solution, where each variable is associated with one of auxiliary links in all decomposed merging nodes. If a variable is set to ‘0,’ it means the corresponding auxiliary link is inactive and does not allow any information to pass; otherwise, this link is active and information flows can pass. Hence, solution X corresponds to a unique decomposed graph $G_\mathrm{GD}(X)$. To evaluate X, we first validate if a feasible NCM subgraph can be found from $G_\mathrm{GD}(X)$. If yes, the average BUR in $G_\mathrm{GD}(X)$ is calculated as the fitness value of X (more details can be found in Sect. 2); otherwise, X is assigned with a positive value that is sufficiently large. As the objective of the problem concerned in this paper is to be minimized, a smaller average BUR indicates that the corresponding solution has a better fitness.

4.2 Food source initialization

As aforementioned, food sources are usually randomly generated in the initialization phase, e.g., (Karaboga and Gorkemli 2014; Gao et al. 2015a, b; Liu et al. 2015; Zhou et al. 2017; Song et al. 2017; Li et al. 2017). In addition, there are a few more methods for food source initialization. Kumar and Sahoo (2017) generate initial food source positions by using a multi-step K-means algorithm. Shokouhifar and Jalali (2017) adopt a ranking algorithm to initialize food sources for honey bees. Moreover, a logistic-equation-based chaotic scheme is used in the initialization phase (Xiang and An 2015). However, all the above initialization methods are not directly applicable to discrete optimization as they are only for numerical or problem-specific optimization.

Fig. 1

Pseudo-code of the FSI scheme

As for binary optimization, randomly generating food sources is also commonly used in the initialization, e.g., Kashan et al. 2012; Kiran and Gündüz 2014. Besides, Hancer et al. (2015) produce food sources, with the probability of generating ‘0’ at each dimension set to 0.75. Kiran (2015) first creates an all ‘0’ binary string (e.g., ‘0...0’) and then randomly selects some bits and sets them to ‘1.’ Nevertheless, most of the approaches above may not be appropriate for initializing food sources when addressing the LB-NCM problem as it is highly problem specific and constrained. In other words, if the above initialization approaches were used, most of the food sources may be infeasible, i.e., with very low nectar amounts. This would mislead the bees to intensify the exploration over poor food sources and thus achieve deteriorated optimization performance.

In order to provide bees with high-quality food sources at the beginning of the search, this paper proposes an effective food source initialization (FSI) scheme to provide the initial exploration with a group of promising food sources. Different from the existing initialization approaches, the basic idea of the FSI scheme is to generate $N_{p}$ food source positions by simply repeating two-point crossover operation on an all-one solution and a randomly generated solution, where $N_{p}$ is an integer. The all-one solution, i.e., ‘11...1,’ is always able to produce a feasible NCM subgraph for the network coding resource optimization (Kim et al. 2007b), and it also applies to the LB-NCM problem as the two problems have identical hard constraints regarding the expected data rate and link-disjoint paths. With more auxiliary links activated, it is more likely to find a feasible NCM subgraph from the corresponding decomposed graph $G_\mathrm{GD}$. Partially exchanging the all-one solution and a random solution helps to produce feasible food source positions, with an appropriate level of population diversity preserved.

Let $X_\mathrm{ALL} = (1, {\ldots }, 1)$ and $X_\mathrm{RND} = (x_{1}, {\ldots }, x_{D})$ be the all-one solution and a randomly generated solution, respectively. Let the set of initial food source positions be by FS. We denote the two resultant offspring solutions after crossover by $X_\mathrm{OFF1}$ and $X_\mathrm{OFF2}$, respectively. The pseudo-code of the FSI scheme is shown in Fig. 1. Note that in two-point crossover, two crossover points are randomly selected each time and the string pieces between them are swapped between the two original solutions (Kim et al. 2007b).

It is well known that high-quality initial solutions help to guide the search to explore promising areas in the search space. The FSI scheme can provide a set of feasible solutions to ABC, which is helpful for bees to access food sources with sufficient nectar amounts, and thus outstanding optimization performance is more likely to be achieved.

4.3 NSL-based selection scheme in the scout bee phase

As mentioned in Sect. 3.4, an employed bee has to leave the food source it is exploring if no improvement happens within a predefined number of cycles. In this case, the bee becomes a scout and will fly to a new food source position for exploration. In the original ABC algorithm, a scout bee generates a new food source based on Eq. (7). Unfortunately, to generate random food sources may not always be effective and could have a negative impact on the optimization performance. Therefore, a number of researchers have been devoted to designing new behaviors of scout bees for enhancing performance of ABCs. For example, a multi-swap method is introduced by Sundar et al. (2017), where a new food source is generated by performing multiple random swaps on the selected food source. Kumar and Sahoo (2017) apply Hooke-and-Jeeves-based classical search mechanisms to generate a new position of food source in place of the old one. In order to avoid stagnation and prematurity, a chaotic search technique is adopted for generating high-quality food sources (Xiang and An 2015). For an abandoned food source, Liu et al. (2015) set its location as the center and produce a random position within a predefined radius as the new food source. Moreover, Singhal et al. (2015) simply replace the abandoned food source with the best-so-far solution to strengthen the exploitation. Nevertheless, the methods above are based on problem-specific information and they cannot be adopted in our algorithm.

As the LB-NCM problem is highly constrained, randomly generated food source positions could be misleading and have computational efforts wasted if the corresponding food sources have quite low nectar amounts, e.g., they are infeasible. Actually, those high-quality food sources found during the search can be used to generate new food sources. We improve the scout bee phase by introducing a food source selection scheme based on nectar source library (NSL). This NSL-based selection (NSL-S) scheme stores $N_{p}$ historically best food sources during the evolution in NSL and updates NSL when better food sources are found. In the initialization phase, NSL is set to the set of initial food source positions FS. Let $X_{1}, \ldots , X_{Np}$ be the food source positions in the kth cycle, where $k = 1, {\ldots }, C_\mathrm{max}$ and $C_\mathrm{max}$ is the maximum number of cycles.

Fig. 2

Pseudo-code of the NSL update process in cycle k

Figure 2 illustrates the pseudo-code of the NSL update process in Cycle k. Each scout produces a new food source position based on a selected food source in NSL. By making use of historically best solutions, the NSL-S scheme helps to explore areas where promising solutions reside, which not only diversifies the food sources, but also strengthens the global exploration.

4.4 Neighborhood search scheme

As known, neighborhood search has a significant impact on the optimization behavior of ABCs (Karaboga 2005; Karaboga and Basturk 2008). It is thus of vital importance to develop effective methods to exploit neighboring areas of promising food sources. So far, an increasing amount of research attention has been dedicated to improving the neighborhood search process. Xiang et al. (2014) maintain an archive that stores the elite solutions found during the evolution. In the employed bee phase, an elite solution is randomly selected from the archive and used for exploitation. Gao et al. (2015a) develop a Gaussian search equation and a fitness-based neighborhood mechanism to enhance the ability of the neighborhood search. Karaboga and Gorkemli (2014) propose that, for a certain solution, the best solution among its neighbors and itself is embedded into the solution search equation at the onlooker bee phase. Zhou et al. (2017) make use of the global best solution in the process of neighborhood search. Song et al. (2017) present a novel solution search equation based on information of the objective function values and the global best solution.

Although the neighborhood search methods above have demonstrated their effectiveness, they are for continuous optimization problems. Wang et al. (2012) propose a modified binary differential evolution algorithm (NMBDE), where a probability estimation operator (PEO) is devised for diversity preservation. PEO extracts information from parent individuals and uses it to build multiple probability distribution models (PDMs) at each cycle. Let the ith solution denoted by $X_i^{\tau {-}1} =(x_{i,1}^{\tau {-}1} ,\ldots ,x_{i,D}^{\tau {-}1} )$ at cycle $\tau -1$, where $x_{i,k}^{\tau {-}1}$ is the value at dimension k. Let $P(X_i^\tau )=(p_{i1}^\tau ,\ldots ,p_{iD}^\tau )$ denote the PDM of $X_i^{\tau }$, where $p_{ij}^\tau$ is the probability of generating ‘1’ at dimension j. PDM $P(X_i^\tau )$ is defined in Eq. (12).

$$\begin{aligned} \left\{ {\begin{array}{l} {p}_{{ij}}^{\tau } =\frac{1}{1+\exp ^{-2b(\beta -0.5)/(1+2\varphi )}} \\ \beta =x_{r1,j}^{\tau {-}1} +\varphi \left( x_{r2,j}^{\tau {-}1} -x_{r3,j}^{\tau {-}1} \right) , \\ \end{array}} \right. \end{aligned}$$

(12)

where b is a positive number for tuning the range and shape of the PDM, called bandwidth factor. If set properly, b helps achieve efficient search and maintain population diversity simultaneously; $\beta$ contains the information extracted from three randomly chosen solutions at Cycle $\tau -1$, namely $x_{r1,j}^{\tau {-}1}$, $x_{r2,j}^{\tau {-}1}$ and $x_{r3,j}^{\tau {-}1}$; $\varphi$ is a scaling factor, selected in the range of [0, 2].

It has been reported that PEO helps to achieve a balance between global exploration and local exploitation when addressing the numerical optimization and multi-dimensional knapsack problems. Nevertheless, randomly selected solutions are very likely to produce low-quality food sources for the LB-NCM problem. This is because, without sufficient guidance, the ABC algorithm may not be able to locate promising regions in the search space. Inspired by PEO (Wang et al. 2012), this paper proposes a novel neighborhood search (NS) scheme, where we also build PDMs and sample them for exploration of new food source positions. However, instead of using three random solutions, the proposed NS scheme redefines variable $\beta$, by making use of $X_i^{\tau {-}1}$ and the best-so-far food source position $X_{\mathrm{b}}^{\tau {-}1} =(x_{b1}^{\tau {-}1} ,\ldots ,x_{bD}^{\tau {-}1} )$, as defined in Eq. (13).

$$\begin{aligned} \left\{ {\begin{array}{l} {p}_{{ij}}^\tau =\frac{1}{1+\exp ^{-2b(\beta -0.5)/(1+2\varphi )}} \\ \beta =x_{ij}^{\tau {-}1} +\varphi \left( x_{bj}^{\tau {-}1} -x_{ij}^{\tau {-}1} \right) . \\ \end{array}} \right. \end{aligned}$$

(13)

The constructed PDM $P(X_i^\tau )$ is utilized to generate a new food source $V_i^\tau =(v_{i1}^\tau ,\ldots ,v_{iD}^\tau )$, according to Eq. (14).

$$\begin{aligned} v_{ij}^\tau =\left\{ {\begin{array}{ll} 1, &{}\quad \mathrm{Rnd}<p_{ij}^\tau \\ 0, &{}\quad \mathrm{otherwise,} \\ \end{array}} \right. \end{aligned}$$

(14)

where Rnd is a randomly generated number in the range of (0,1). Note that, to generate a new position for the ith food source $X_i^{\tau {-}1}$, the basic ABC algorithm randomly modifies one dimension, while the proposed NS scheme regenerates all dimensions based on Eq. (14).

Fig. 3

Pseudo-code of the proposed MABC

The NS scheme implicitly makes use of the features extracted from both the ith food source and the global best food source. Each resultant food source is no longer dependent on any single food source, but two different ones. This provides the bees with opportunities to explore new areas which may be far away from those known sources, hence enhancing the global exploration. Moreover, the generated food sources inherit features of two different sources, helping to preserve population diversity.

4.5 The overall procedure of the proposed MABC

The proposed MABC is based on DisABC (Kashan et al. 2012), with three performance-enhancing schemes including the FSI initialization scheme, the NSL-S scheme and the NS scheme.

Let ${ counter}_{i}$ and limit be the consecutive number of cycles that the ith food source cannot be improved and the predefined number of cycles for abandoning any food source, respectively. Let the position of the ith food source denoted by $X_{i}$. The pseudo-code of the proposed MABC is shown in Fig. 3. The search stops when a predefined number of cycles are finished.

For the LB-NCM problem concerned in this paper, let O(f) be the time complexity for evaluating a food source. Assume the number of food sources is $N_{p}$ and the maximum number of cycles is $G_{\mathrm{max}}$. The original ABC has a time complexity of O(($f \cdot N_{p}+ f \cdot N_{p}) \cdot G_{\mathrm{max}})=O(f \cdot N_{p} \cdot G_{\mathrm{max}})$ (Wang et al. 2014; Shokouhifar and Jalali 2017). Although there are some differences in each phase, the original ABC and the proposed MABC share with each other the same evolutionary framework, i.e., both of them are composed of the initialization, the employed bee, the onlooker bee and the scout bee phases. On the other hand, when addressing the LB-NCM problem, the food source evaluation is the most time-consuming operation in each cycle. Compared to it, the computational overhead caused by the NSL-S scheme and the NS scheme is too trivial to take into account. The computational cost of the two schemes can thus be ignored. Therefore, the time complexity of MABC is still the same as the original ABC, i.e., $O(f \cdot N_{p} \cdot G_{\mathrm{max}})$.

5 Performance evaluation

First of all, all test instances are introduced. Then, we explain the rationale why DisABC is chosen for solving the LB-NCM problem by comparing the performance of three widely used ABCs. After that, we study the effectiveness of the three performance-enhancing schemes. Last but not least, the proposed MABC is compared with a number of state-of-the-art algorithms based on evolutionary and swarm intelligence with respect to the overall optimization performance.

5.1 Test instances

There are 24 benchmark instances, including 12 fixed networks (n-copy and n-hybrid networks) and 12 randomly generated networks. They have been widely adopted for performance evaluation when addressing NCM routing problems, e.g., (Kim et al. 2007b; Xing et al. 2016; Wang et al. 2016). Information on each instance and its parameters is shown in Table 1.

Table 1 Test instances and their parameters

In all experiments, we assume all links have an identical maximum bandwidth, i.e., 100Mbps. For each link in G, the consumed bandwidth prior to NCM is uniformly distributed in the range of [1, 50] Mbps. To support a NCM data transmission, the bandwidth consumption of each occupied link is 30Mbps. All experiments were run on a Windows XP computer with Intel(R) Core(TM) E8400 3.0 GHz, 2 GB RAM. For performance comparison, each algorithm is run 20 times on each instance.

5.2 Performance comparison of three ABCs

The original ABC algorithm was proposed for continuous optimization problems (Karaboga 2005). To tackle binary optimization problems, a number of variant ABCs have been developed. Among them, three ABCs have attracted increasingly more research attention, including DABC (Marinakis et al. 2009), binABC (Kiran and Gündüz 2014) and DisABC (Kashan et al. 2012). The proposed ABC is a variant of DisABC (Kashan et al. 2012). In this subsection, we evaluate three variants of ABC and show why DisABC is selected, as listed below.

• DABC: the hybrid discrete artificial bee colony (ABC) algorithm (Marinakis et al. 2009). In DABC, the neighborhood search generates a new food source by using a neural network function sigmoid to convert continuous decision variables to discrete ones, as introduced in Sect. 3.5.

• binABC: the XOR-based binary ABC algorithm (Kiran and Gündüz 2014). Different from DABC, binABC does not need a conversion from continuous decision variables to discrete ones. It uses an XOR logic operator instead of the vector subtraction operator.

• DisABC: the discrete ABC algorithm (Kashan et al. 2012). DisABC develops a new differential expression to replace the vector subtraction operator that is typically utilized in the original ABC. It measures dissimilarity between binary vectors for generating new food sources.

Table 2 Results of mean and SD (best results are in bold)

We compare the three ABCs above regarding the mean and standard deviation (SD) on 12 selected test instances in Table 1. The population size for each ABC is 20, i.e., there are 10 employed bees and 10 onlookers. The predefined number of cycles for abandoning food source, limit, is set to 5. We set the predefined maximum number of cycles to 200.

Table 3 Results of mean and SD (best results are in bold)

Table 2 shows the results of mean value and SD. One may notice that for any instance the differences among the mean values seem to be trivial. For example, in 7-copy network, the mean values, 0.4670, 0.4766 and 0.4668, are quite close to each other. As mentioned in Sect. 4.1, the fitness value is defined as the average BUR of a given network. Even a slight difference in average BUR will be significantly amplified if considering the entire network bandwidth resources. It is clearly seen that DisABC performs the best as it achieves the smallest mean value in most of the instances. This is why we adapt DisABC for the LB-NCM problem.

5.3 The effectiveness of the three schemes

As mentioned above, we develop three new schemes for enhancing the optimization performance of the proposed MABC, including the FSI scheme in Sect. 4.2, the NSL-S scheme in Sect. 4.3 and the NS scheme in Sect. 4.4. To investigate the effectiveness of the three schemes above, we compare four variants of DisABC on 12 selected networks:

• DisABC: the original DisABC proposed by Kashan et al. (2012).

• DisABC1: DisABC with the FSI scheme.

• DisABC2: DisABC1 with the NSL-S scheme.

• MABC: DisABC2 with the NS scheme.

The population size, the limit and the predefined maximum number of cycles are set to 20, 5 and 200, respectively. In MABC, we set the scaling factor $\varphi = 0.5$; if node size of a network is smaller than 50, the bandwidth factor b is set to 6; otherwise, we set b to 8.

Table 3 shows the mean and SD obtained by the four algorithms. It is clearly seen that DisABC is the worst of all. DisABC1 outperforms DisABC in each instance. This is because the FSI scheme can produce a group of sufficiently good solutions for the search to begin with, which guides the bees to explore promising food sources. Moreover, one can see that DisABC2 achieves better optimization performance than DisABC1. With the nectar source library integrated, best-so-far solutions found during the evolution are utilized to generate new food sources surrounding them. Hence, promising areas can be repeatedly explored and the optima are more likely to appear. In addition, MABC is the best among the four algorithms in terms of the mean and SD. In MABC, the novel neighborhood search scheme generates new food sources by sampling probability distribution model of two high-quality solutions, which helps not only to discover unknown areas for exploration, but also to keep an appropriate level of food source diversity. If emphasizing on each instance, one can easily find that mean value is gradually improved, indicating the effectiveness of each scheme. To support the above findings, we show the convergence curves and box plots of the four ABCs on 6 selected networks in Figs. 4 and 5, respectively. It is obvious that each of the three proposed schemes contributes to the performance improvement of DisABC.

Fig. 4

Convergence curves of the four ABCs. a 15-Copy. b 15-Hybrid(3). c Rnd-2. d Rnd-3. e Rnd-5. f Rnd-7

Fig. 5

Box plots of the four ABCs. a 15-Copy. b 15-Hybrid(3). c Rnd-2. d Rnd-3. e Rnd-5. f Rnd-7

Table 4 Results of mean and SD (best results are in bold)

5.4 The overall performance evaluation

In order to thoroughly investigate the overall performance of the proposed MABC, we compare it with eight state-of-the-art evolutionary and swarm-intelligence-based algorithms regarding the best solutions obtained and the computational time. These algorithms and their parameter settings are described as below.

• (1) iPBIL: the improved population-based incremental learning (PBIL) for the LB-NCM problem (Xing et al. 2016). iPBIL maintains a probability vector (PV) and generates a population of samples based on the PV. iPBIL records a set of best-so-far samples and uses a proportion of them to update the PV at each generation. Set the mutation probability $p_\mathrm{m }= 0.02$, the learning rate $\alpha = 0.1$, and the probability variance $\sigma = 0.05$.

• (2) BPSO: the binary particle swarm optimization algorithm (Liu et al. 2016). BPSO developed a new adaptive inertia weight strategy, which enables the search process smoothly shifted from exploration-oriented search to exploitation-oriented search by linearly tuneable inertia weights. We set population size $N = 20$, the upper bound $W_\mathrm{upper}= 1$, the lower bound $W_\mathrm{lower} =0.4$, $\rho = 0.9$, $c_{1} = 2$, $c_{2} = 2$, and particle maximum velocity $V_\mathrm{max} = 6$.

• (3) NBDE: the self-adaptive binary differential evolution (DE) algorithm (Banitalebi et al. 2016). Based on the DE framework and the measurement of dissimilarity, NBDE uses an adaptive mechanism to generate new trial solutions and a chaotic technique to tune the parameter values. We have the population size $N = 20$, the mutant control parameter $F = 0.5$, the bandwidth factor $b = 6$, and the crossover constant $\mathrm{CR} = 0.7$.

• (4) IFFOA: the improved fruit fly optimization algorithm (Meng and Pan 2017). IFFOA proposes a parallel search process to balance global exploration and local exploitation and a vertical crossover operator to avoid stagnation. We set the fruit fly swarm size $N = 4$, the neighbor size of bee $S = 5$, the randomly selected bits length $L = 10$, and the probabilities of performing cooperation $p_\mathrm{co} = 0.7$, $p_{c1} = 0.2$, $p_{c2} = 0.6$.

• (5) mSFLA: the modified shuffled frog leaping algorithm (Dalavi et al. 2016). mSFLA introduces two weight factors to the local search equation of the basic SFLA, which helps to widen the search ability and avoid premature convergence. Set the frog population size $F = 20$, the number of memeplexes $m = 4$, the number of frogs in each memeplex $n = 5$, the number of local searches LS = 5, $C_{1} = 1$, $C_{2} = 0.95$, and $w = 0.95$.

• (6) MDisABC: the modified discrete ABC algorithm (a variant of DisABC) (Hancer et al. 2015). For each solution, MDisABC first builds a mutant solution by using three of its neighbors and then produces a new food source position by recombining the mutant and the solution itself. The crossover rate $p_\mathrm{c}$ is set to 0.25.

• (7) BABC: the binary-coded ABC algorithm for addressing the spanning tree construction problem (Zhang and Zhang 2017). BABC performs better than Kruskal’s algorithm in terms of quality of the best spanning tree obtained in roadside-to-vehicle communication networks.

• (8) ABCbin: the continuous ABC for binary optimization (Kiran 2015). Each food source position is converted to a binary vector before it is evaluated. It has been reported that ABCbin outperforms a number of existing ABCs with respect to the solution quality and robustness.

• (9) MABC: the proposed ABC in this paper.

For all algorithms, we set the predefined number of iterations 200. For all ABC algorithms, we set the number of food sources $N_{p} = 10$ and the limit for abandoning a food source ${ limit} = 5$. For MABC, we have the scaling factor $\varphi = 0.5$ and the bandwidth factor $b = 6$ if a network has 50 nodes or less; otherwise, $b = 8$. The stopping condition is the predefined number of iterations is evolved.

The mean values and SDs of the best fitness values obtained by the nine algorithms are given in Table 4. Obviously, MABC performs the best as it is always able to obtain the smallest mean and promising SD in each instance. With the FSI scheme in Sect. 4.2, MABC begins the exploration with a set of food sources with high nectar amounts so that promising areas in the search space can be located rapidly at the beginning of the evolution and it thus helps to achieve decent optimization results.

In addition, in the NSL-S scheme, a NSL is maintained to store historical best food sources found cycle by cycle. For a scout, a food source is randomly selected from NSL and used to produce a new position of food source that is very likely to be of high quality since it is a neighbor of an elite solution. Besides, the NS scheme is able to diversify the search over different areas in the search space, hence helping to enhance global exploration and diversity preservation simultaneously. Therefore, with the three schemes, MABC has more opportunity to reach global optima and gain excellent performance. Figure 6 illustrates the box plot of the nine algorithms in six selected instances. One can easily see that MABC outperforms the other eight algorithms.

Fig. 6

Box plot of all algorithms. a 15-Copy. b 31-Hybrid(5). c Rnd-3. d Rnd-8. e Rnd-10. f Rnd-12

We compare the best fitness values obtained by the algorithms using Student’s t test in Table 5, where two-tailed t test with 38 degrees of freedom at a level of significance 0.05 is utilized. Obviously, the proposed MABC is the best among all algorithms for comparison when solving the LB-NCM problem. In addition, the Friedman test is also used for algorithm performance comparison. With all 24 instances considered, the average rankings of the nine algorithms are shown in Table 6. One can easily observe that MABC achieves the best optimization performance.

Table 5 t test results for all algorithms

Table 6 Rankings of all algorithms

When an algorithm is evaluated, the average computational time (ACT) is an important performance indicator. Table 7 shows the ACT values of all algorithms for comparison. It can be seen that MABC obtains a relatively large ACT in each instance.

Table 7 ACT values of all algorithms (sec.)

As the LB-NCM problem studied in this paper is highly problem specific and constrained, there are much more infeasible solutions than feasible ones in the search space. To evaluate an infeasible solution is less computationally expensive than to evaluate a feasible one. This is because we have two steps when calculating the nectar amount for a food source X, where the first step consumes almost all the computational efforts for evaluating X. The first step is to validate if a feasible NCM subgraph $G_\mathrm{GD}(X)$ can be found, where receiver nodes are checked one after another with respect to the achievable bandwidth. As long as a receiver cannot meet the achievable bandwidth requirement, food source X is regarded as infeasible and the evaluation stops immediately. On the contrary, a food source is regarded as feasible only if all receivers have been checked in terms of the achievable bandwidth. Hence, it is why infeasible solution evaluation consumes less computational time. In addition, with the number of receivers increasing, the average computational time for evaluating an infeasible solution becomes smaller and smaller than that for a feasible one. In particular, in instances with more receivers, evaluating an infeasible solution consumes significantly less average computational time than evaluating a feasible one.

Then, we discuss why the proposed MABC is so computationally costly, compared with the other ABCs. In fact, MABC generates much more feasible solutions during the evolution. This is because of the food source initialization (FSI) scheme, the nectar-source-library-based selection (NSL-S) scheme and the neighborhood search (NS) scheme. The FSI scheme is devised based on the problem-specific domain knowledge. Hence, it is able to generate sufficient number of feasible food sources at the beginning of the evolution, which helps to guide the search to locate promising areas in the search space. With plenty of feasible solutions in the initial population, feasible food sources are more likely to appear during the evolution. On the other hand, the NSL-S scheme maintains a nectar source library (NSL) that stores $N_{p}$ historically best food sources found during the evolution. If an employed bee becomes a scout bee, the NSL-S scheme randomly selects a food source from NSL for it. Then, this scout bee becomes an employed bee again. Note that it will not directly fly to the food source selected for it. (Otherwise, the population diversity is lost rapidly.) Instead, it will fly to explore a new food source that is generated based on the selected food source and the best-so-far food source by using the NS scheme. As the two food sources are of high quality, the new food source should be of good quality as it inherits promising attributes from them. Therefore, the NSL-S scheme and the NS scheme also help to generate feasible solutions. With more feasible solutions evaluated, it is rationale that the evolution of MABC is slower than the other ABCs for comparison. In order to support our explanation, we collect the average percentage of the feasible solutions generated during the evolution, as shown in Table 8. It is clearly seen that MABC generates much more feasible solutions, compared with MDisABC, BABC and ABCbin.

In summary, MABC is capable of efficiently exploring promising areas for food sources with higher nectar amounts and hence sufficient feasible solutions can be produced. Besides, it takes longer time to evaluate a feasible solution than an infeasible one. More feasible solutions definitely require more expensive computational cost. On the other hand, the waste of considerable amount of ACT in each instance reflects that MABC is working properly.

Table 8 Average percentage of the feasible solutions obtained (%)

6 Conclusions

In this paper, we investigate the load balancing optimization problem in multicast based on network coding. A modified artificial bee colony algorithm (MABC) is developed, with three extensions including the food source initialization (FSI) scheme, the NSL-based selection (NSL-S) scheme and the neighborhood search (NS) scheme. The FSI scheme can produce feasible food sources by repeatedly performing two-point crossover on two solutions, which helps the search to begin with promising areas at the beginning of the evolution. The second extension maintains a nectar source library (NSL) storing the best-so-far food sources found. NSL provides scout bees with high-quality food sources, which, to a certain extent, has the global exploration ability of MABC enhanced. In the NS scheme, for each food source, a probability vector (PV) is built by extracting statistical information from two food sources. The PV is sampled to generate a new food source position which helps to achieve balanced global exploration and local exploitation. The three extensions have shown to be able to greatly improve the overall performance of the proposed algorithm. Experimental results show that MABC outperforms a number of well-known evolutionary algorithms in terms of the solution quality.