1 Introduction

A mobile ad hoc network (MANET) is composed of self-organizing mobiles in dynamic topology networks. All nodes cooperatively maintain network connectivity without the aid of any fixed infrastructure unit. The communication between two nodes is carried out either directly or with the help of intermediate nodes which belong to the same network (Wang et al. 2001). Currently, MANETs are very popular due to the no-restricted mobility and feasible deployment (Sesay et al. 2004).

Multicasting is one type of services in MANETs (Oliveira and Pardalos 2005). With the growing of distributed multimedia application, the efficient and effective support of QoS (i.e., Quality of Service) has became more and more crucial for MANETs. The basic purpose of QoS routing is to find paths with better QoS. Typical QoS properties include the end-to-end delay, packet loss probability, delay jitter, available bandwidth and so on. In general, these QoS properties can be classified into three categories: additive metrics (e.g. end-to-end delay), multiplicative metrics (e.g. packet loss probability), and concave metrics (e.g. available bandwidth) (Yen et al. 2011). And there is a balance when we design a network architecture. First, some constraints of QoS have to be taken into consideration, which make QoS routing more complex than a regular one. Second, resource utilization is the most important metric for the efficiency of a routing network, which affects both the QoS and occupied resources of a routing (Wang et al. 2001). Therefore, the key issue in the design of a network is how to efficiently manage the resources and meet the requirements of QoS during each connection.

Routing problems can be divided into the unicast and multicast routing. The unicast routing is to find a feasible path between a single source and a single destination. Meanwhile, the multicast routing aims to find a tree structure, which is used for efficiently delivering the same data stream to different destinations in a network simultaneously. More importantly, in a QoS routing, some QoS constrains are added to the entire tree. Thus, the object of multicast routing problem is to compute a tree structure, called the multicast tree, which has a minimal communication resources and meets QoS requirements (Peng and Li 2013). Like many other networks designs, the updating rule of “choosing the best” strategy has a detrimental impact on the outcome (Wang et al. 2012). Thereby, an optimization algorithm is necessary. The QoS multicast routing problem is also called the steiner tree problem, which is a typical NP-complete problem (Wang and Crowcroft 1996). It means this problem cannot be solved optimally with a polynomial time complexity, which is very crucial for application in the real world. Therefore, providing QoS guarantees for data traffic and minimizing the cost of whole network on multicast routing are significant challenges.

As the QoS multicast routing problem has draw more and more attentions, many researchers have used different methods to solve this problem. Ratnasamy et al. (2006) have tried to modify the existing algorithms to satisfy QoS constraints by best effort forwarding. But these algorithms cannot guarantee a multicast tree for QoS constraints. Some researchers have used swarm intelligence algorithms to solve this problem, such as genetic algorithms (GA) (Peng and Li 2013; Hwang et al. 2000), bee life-based algorithms (Salim and Abdelhamid 2013). Those algorithms first analyze the fitness of tree structures based on the whole network topology, and then optimize those tree structures by some meta-heuristic operators. But a weak robustness and low efficiency of local search still limit the performances of those algorithms.

Recently, more and more researchers focus on the self-organization capability of a species of plasmodium, which is a ‘vegetative’ phase of Physarum. This plasmodium shows an amazing intelligence in foraging, which can produce a robust protoplasmic network for connecting food sources in order to deliver nutrients to all its body effectively (Nakagaki et al. 2000). Moreover, biological experiments have shown that the plasmodium has the ability to form a self-adaptive and high efficient network without central control mechanism (Adamatzky 2009). The self-organization of Physarum is what MANETs need. Taking the self-organization capability of Physarum, a new crossover scheme is proposed in this paper. Based on the multi-constrained genetic algorithmic approaches, we aim to optimize the cost and QoS property metrics simultaneously. Utilizing Physarum model, our proposed scheme can enhance the robustness and local search ability of genetic algorithms. Simulation results demonstrate that the proposed scheme improves the efficiency and robustness of genetic algorithms.

The organization of this paper is as follows. Sect. 2 introduces the related work including the formulation of multicast routing problem, some typical genetic algorithms and the original Physarum network model. Section 3 proposes the hybrid algorithm through optimizing traditional crossover schemes of genetical algorithms based on the Physarum network model. Section 4 provides some experiments to estimate the effectiveness of proposed hybrid algorithm and analyzes the parameters of modified Physarum network model. Finally, Sect. 5 concludes this paper.

2 Related work

Section 2.1 first formulates the multicast routing problem. And Sect. 2.2 describes the basic idea of traditional algorithms and genetic algorithms for the multicast routing problem. Sect. 2.3 presents the main mechanism of original Physarum networks model.

2.1 Formulation of multicast routing problem

A network is usually represented as an undirected graph \(G = (V,E)\), where \(V = \{ {v_1},{v_2},\ldots ,{v_n}\}\) denotes a set of nodes representing routers or switches and \(E =\{{e_{ij}} = ({v_i},{v_j}) | {v_i},{v_j} \in V,i \ne j\}\) denotes a set of edges representing physical or logical connectivity between nodes. In a multicast routing, there are a source node and destination nodes. Let a node \(s \in V\) stand for the source and a set \(DE \subseteq V - \{ s\}\) represent the set of destinations. And then a multicast tree can be denoted as T(s, DE), which is a connected sub-graph of G and covers node s and every node in DE. The path from a node s to any destination node \(d \in DE\) is denoted as \({p_T}(s,d)\). And the object of multicast routing problem is to find a T(s, DE) with a minimal cost, which has a set of paths with acceptable QoS metrics.

As introduced in Sect. 1, QoS metrics can be classified into three categories, i.e., additive metrics, multiplicative metrics and concave metrics. And additive and multiplicative metrics can be deal with in the same way in our algorithm. For simplifying the QoS routing problem, we focus on additive metrics (e.g. end-to-end delay) and concave metrics (e.g. available bandwidth). Furthermore, the cost is the most important property for the effectiveness of a routing, thus our research focuses on the bandwidth-delay constrained least-cost multicast routing problem.

The delay of a path from a node s to any destination d in DE, denoted by \(delay({p_T}(s,d))\), is defined as the sum of delays in the \({p_T}(s,d)\), i.e., \(delay({p_T}(s,d))=\sum \nolimits _{e \in {p_T}(s,d)} {delay(e)}\). Meanwhile, the bandwidth of a path from a node s to any destination node d in DE, denoted by \(bandwidth({p_T}(s,d))\), is defined as the minimum of bandwidth along the path, i.e., \(bandwidth({p_T}(s, d))= \min \{ bandwidth(e)|e \in {p_T}(s,d)\}\). And, according to existing studies in Hwang et al. (2000); Lu and Zhu 2013), we unify the cost of a multicast tree as the sum of costs in the tree, i.e., \(cost(T) = \sum \nolimits _{e \in T} {cost(e)}\), for comparing the effectiveness of different GAs. Moreover, the delay and bandwidth of a multicast tree T are defined as Eqs. (1) and (2), respectively.

$$\begin{aligned} delay(T(s,DE))= & {} \max \{delay({p_T}(s,d))|d \in DE\} \end{aligned}$$
(1)
$$\begin{aligned} bandwidth(T(s,DE))= & {} \min \{bandwidth({p_T}(s,d))|d \in DE\} \end{aligned}$$
(2)

Let \({\varDelta _d}\) be the upper bound of delay constraint and \({\varDelta _b}\) be the lower bound of bandwidth constraint for every path. And the bandwidth-delay constrained least-cost multicast routing problem is defined as Eq. (3). We aim to minimize the cost under the condition of bandwidth-delay constraints.

$$\begin{array}{ll} \min & cost(T)\\ st.& \left\{ \begin{array}{ll} delay(T) \le \varDelta_d\\ bandwidth(T) \ge \varDelta_b \end{array} \right. \end{array}$$
(3)

2.2 Algorithms for solving the multicast routing problem

There are two main approaches, namely, exact methods and heuristics, for solving the QoS multicast routing problem. Exact methods are usually based on mathematical programming, among which the dynamic programming (Chow 1991) and branch-and-bound (Salama et al. 1997) are the two most prevailing exact methods for QoS multicast routing. However, due to the high computational complexity, those exact methods are only viable for small-scale problems (Yin et al. 2014). With the development of networks, heuristics are the mostly approaches for the QoS multicast routing problem.

Capturing the features of genetic evolution, GA is a powerful tool for solving NP-complete problems. By setting an appropriate maximal iterative steps of GA, an approximate optimal solution can be obtained within a reasonable time. In genetic algorithms, candidate solutions are coded as chromosomes. Moreover, the idea of natural selection and genetic operators, such as the crossover and mutation, are employed for searching better chromosomes. Many researchers have applied GAs to solve the multicast routing problem with various coding and genetic operators (Peng and Li 2013; Hwang et al. 2000; Lu and Zhu 2013; Karthikeyan and Baskar 2015; Mahmoud et al. 2014). In the following, we will take some typical genetic algorithms [i.e., GAMRA (Hwang et al. 2000), EEGA (Lu and Zhu 2013), ISGSA (Zhang et al. 2009)] as examples to describe the solving process of different genetic algorithms for the multicast routing problem.

To deal with the end-to-end delay constraint, Hwang et al. (2000) have proposed an optimized GA, denoted as GAMRA, where a routing table that stores some paths with acceptable delays, has to be constructed first. But constructing such a routing table needs a lot of time. And the crossover operator of GAMRA is a classical two-point crossover, which leads to a weak robustness and lower convergence rate. Wang et al. (2001) have proposed that it is helpful to reserve the same links of two parent chromosomes for the convergence of genetic algorithm. And GAISA (Zhang et al. 2009) and EEGA (Lu and Zhu 2013) have applied this idea to optimizing their crossover operators. Because the same links of parent chromosomes may be in some separated connected components, different schemes have been proposed to reconnect those connected components, in GAISA and EEGA. For GAISA, the reconnection is building a random path from destination nodes, which are separated with the source node, to the connected component including the source node. And for EEGA, two separated components are reconnected by the least-delay path. Although different genetic algorithms have been proposed to solve the multicast routing problem, weak robustness and a lower efficiency of local search capability still limit the performances of genetic algorithms. And making use of knowledge of experts or data, mathematic models are valid methods for improve performances of algorithms (Yu et al. 2011, 2014, 2015).

In order to compare the effectiveness and robustness of different algorithms, some measurements are defined as follows. \(S_{min}\), \(S_{average}\) and \(S_{variance}\) stand for the minimum, average, and variance of results, respectively. Results are all based on C times repeated computations in order to wipe off the computational fluctuation. For example, \(S_{min}\) is calculated as \(\min \{ {S_{i,steps(k)}},i = 1,2,\ldots ,C\}\), where \(S_{i,steps(k)}\) represents the optimal solution of the multicast routing problem in the k step for the ith time computation.

2.3 Original Physarum model

Physarum has shown an amazing intelligent and self-organization capability. For example, Tero et al. have reported that Physarum is cultivated to simulate the Tokyo rail system on a substrate (Tero et al. 2010). And the network generated by Physarum has a strong robustness, great fault tolerance and high transport effectiveness on the transportation (Watanabe et al. 2011). And Nakegaki et al. have shown that Physarum has the ability to find the minimum-length solution between two points in a maze (Nakagaki et al. 2000).

The Physarum network model is inspired by the maze-solving experiment (Nakagaki et al. 2000). Tero et al. have captured the positive feedback mechanism of Physarum in foraging, and built the Physarum network model (PM) (Tero et al. 2007). In addition, The model, designed for solving maze problems, has been used for the network design (Liu et al. 2013) and complex problems solving (Liu et al. 2014). Moreover, this model can be used for building multicast trees in our study.

The main idea of Physarum network model is summarized as follows. We assume the edges of a network are pipelines with fluid inside. \({Q_{ij}}\) and \({D_{ij}}\) stand for the flux and conductivity of a pipeline respectively, which connects nodes i and j. When the conductivity of a pipeline is enhancing, the flux in the pipeline will be enhanced correspondingly, vice versa.

In detail, we use a node s and a set DE to present the inlet and outlets of flux respectively. According to the Kirchhoff\('\)s law, the flux of input at the node s is equal to the total flux of output at all noes in DE. And, at any other nodes, the sum of flux flowing in is equal to the sum of flux flowing out. This process can be represented in Eq. (4) where N stands for the cardinality of set DE.

$$\begin{aligned} \sum \limits _i {{Q_{ij}}} = \left\{\begin{array}{ll} I_{0}\times (N-1),&\quad j == s\\ -I_{0},&\quad j \in DE\\ 0,&\quad others \end{array} \right.\end{aligned}$$
(4)

In each iterative step, \({Q_{ij}}\) and \({p_i}\) can be calculated according to Poiseuille\('\)s law based on Eqs. (4) and (5), where \({L_{ij}}\) represents the length of pipeline contacting nodes i and j, and \({p_i}\) represents the pressure of node i. Equation (6) is called adapted equation. As the iteration going on, the conductivities of pipelines adapt to the flux based on Eq. (6). Then, the conductivities will feed back to the flux based on Eq. (5) at the next iterative step. Two typical functions of f(Q) are shown in Eqs. (7) and (8) based on Tero et al. 2007.

$$\begin{aligned} {Q_{ij}}= & {} \frac{D_{ij}}{L_{ij}}|{p_i} - {p_j}| \end{aligned}$$
(5)
$$\begin{aligned} \frac{d{D_{ij}}}{dt}= & {} f(|{Q_{ij}}|) - {D_{ij}} \end{aligned}$$
(6)
$$\begin{aligned} f(Q)= & {} Q^u,\quad u>0 \end{aligned}$$
(7)
$$\begin{aligned} f(Q)= & {} \frac{(1 + \alpha ){Q^u}}{1 + \alpha {Q^u}}, \quad u > 1,\alpha > 0 \end{aligned}$$
(8)

After above processes, an iterative step is completed. This process will continue a loop iteration until the terminal condition is satisfied. After the loop iteration, based on the positive feedback mechanism between the conductivity and flux, critical pipelines will be reserved, and others will disappear. Finally, we obtain a Physarum spanning tree.

3 Genetic algorithm for the multicast routing problem

In this section, a modified physarum networks model is proposed in Sect. 3.1 first. And then, Sect. 3.2 introduces a new crossover scheme based on PM for the multicast routing problem. Finally, Sect. 3.3 presents the genetic algorithms with the proposed crossover scheme.

3.1 A modified Physarum networks model for multicast routing problem

In the original Physarum model, an equation system should be solved by the Gaussian elimination at every iterative step in the original Physarum model, i.e., each iteration runs in \(O(N^3)\). Assuming the maximal iteration of Physarum model is G. For an iterative algorithm, an overall computational complexity, \(O(G \times {N^3})\), is too high. In Liu et al. (2015), an approximate expression of \(p_i\) is derived as Eq. (9) to reduce the computational complexity.

$$\begin{aligned} {p_i}^{t + 1} = \left\{ {\begin{array}{ll} \frac{{{I_0} + \sum \nolimits _j {\frac{{{D_{ij}}}}{{{L_{ij}}}}({p_j}^t)} }}{{\sum \nolimits _j {\frac{{{D_{ij}}}}{{{L_{ij}}}}} }},&\,{v_i \in DE}\\ 0,&{v_i} = = s\\ \frac{{{\sum }_j {\frac{{{D_{ij}}}}{{{L_{ij}}}}({p_j}^t)} }}{{\sum \nolimits _j {\frac{{{D_{ij}}}}{{{L_{ij}}}}} }},&\,otherwise \end{array}} \right. \end{aligned}$$
(9)

But in our numerical experiments, the pressures calculated by Eq. (9) fluctuate violently and cannot converge sometimes. Based on Eqs. (9), (10) is used to eliminate the fluctuation of pressures, where \(\lambda\) controls the fluctuations of pressures and conductivities.

$$\begin{aligned} {p_i}^{t + 1} = \left\{\begin{array}{ll}{\frac{{{I_0} + \sum \nolimits _j{\frac{{{D_{ij}}}}{{{L_{ij}}}}({p_j}^t)} }}{{\sum \nolimits _j{\frac{{{D_{ij}}}}{{{L_{ij}}}}} }}*\lambda + (1 - \lambda)*{p_i}^t},&{v_i \in DE}\\ 0,&{v_i == s}\\ \frac{{\sum \nolimits _j{\frac{{{D_{ij}}}}{{{L_{ij}}}}({p_j}^t)} }}{{\sum \nolimits _j{\frac{{{D_{ij}}}}{{{L_{ij}}}}} }}*\lambda + (1 - \lambda)*{p_i}^t,&\,{otherwise} \end{array}\right. \end{aligned}$$
(10)

And the adapted equation in our paper is represented in Eq. (11), where k is a parameter relative to the amplitude of conductivities in the Physarum network.

$$\begin{aligned} {D_{ij}}^{t + 1} = \frac{{D_{ij}^t + Q_{ij}^t}}{k} \end{aligned}$$
(11)

Based on Eqs. (5) and (10), the adapted equation is equivalent to Eq. (12). And Eqs. (4) and (5) in the original Physarum networks model do not have to be solved.

$$\begin{aligned} D_{ij}^{t + 1} = \frac{{{L_{ij}}D_{ij}^t + D_{ij}^t|p_i^t - p_j^t|}}{k} \end{aligned}$$
(12)

By setting more than one destination node, i.e., \(|DE| > 1\), the Physarum network model can find the shortest paths from the source node to every destination node in DE simultaneously. Therefore, in the multicast routing problem, PM can be used for building multicast trees. The detailed description of modified Physarum network model for the shortest path tree is shown in Algorithm 1.

figure a

3.2 A new crossover scheme based on PM for multicast routing problems

Generally speaking, there are two main genetic operators in a genetic algorithm. The first is the crossover operator and the other is the mutation operator. These two genetic operators allow genetic algorithms to search for the global optimum based on an evolutionary process. In an evolution process, the crossover operator is the main way by which chromosomes exchange informations. And the major purpose of mutation operator is to help algorithms avoid falling into the local optimum. Thereby the crossover operator plays a key role in searching better chromosomes. In the crossover operator, two chromosomes with greater fitness values are selected from the chromosomes pool as parent chromosomes. And the crossover operator combines these genes in the parent chromosomes into new ones. In other words, it is one of genetic operators in which the genotypes of two selected parent chromosomes are merged to generate new offsprings. The new offsprings will be put back into the chromosomes pool. Furthermore, the mutation operator is one kind of random change of genes in chromosomes. The mutation operator aims to extend the search range and reduce the possibility of falling into the local optimum. Through these operators, new offsprings with a higher fitness will be produced.

Fig. 1
figure 1

An example of PMcrossover operation. The numbers in edges denote cost and delay respectively. a, b are selected as parent chromosomes. And the common links of selected parent chromosomes are reserved in the offspring chromosome as shown in (c). But the source and destination nodes are not in a connected component with reserved links only. Therefore, Physarum model builds the necessary links to reconnect source and destination. a Parent chromosome A. b Parent chromosome B. c A new offspring which is generated by parent chromosomes A and B based on PMcrossover nodes

Full size image

For overcoming the shortcomings of GAs, a universal scheme is proposed for optimizing the crossover operator of GAs, taking advantages of PM. The new crossover operator is called PMcrossover. And the novel hybrid algorithms with PMcrossover (denoted as PMGAs) are used for solving the multicast routing problem. The main idea of PMcrossover is to reserve the common links between parent chromosomes and integrate the offspring by PM based on the reserved links. Other parts of PMGAs are same as the original ones. An example of crossover process is shown in Fig. 1. The details of PMcrossover are described as follows.

First, for utilizing PM, a new graph, denoted as NG, needs to be created with the same topological structure as the network graph in the multicast routing problem. Because GAs may generate some unadaptable chromosomes, which do not satisfy the constraints. There are two strategies to fit for different GAs. For the GAs, which do not generate unadaptable chromosomes, such as GAMRA (Hwang et al. 2000), \({L_{ij}}\) in NG is set equating to the delay of \({e_{ij}}\). For others, such as EEGA (Lu and Zhu 2013), ISGSA (Zhang et al. 2009), \({L_{ij}}\) in NG is set equating to the product of cost and delay of \({e_{ij}}\).

And then, PMcrossover selects the same links of parent chromosomes and reserves them in the offspring chromosomes. According to the definition of fitness function, the selected parent chromosomes with higher fitness values are more likely to satisfy the constraints and have lower costs. Therefore, it is helpful to reserve the same links of two parent chromosomes for the convergence of algorithms. Because these same links may be in some separated sub-trees, PM is used to transform these sub-trees into a multicast tree. In order to reserve the same links in PM model, the length of reserved links is set to 0 in NG. And then, inputting the graph NG, source and destinations into PM, a complete multicast tree will be constructed. Algorithm 2 describes detailed steps of PMcrossover operator in PMGAs.

figure b

3.3 Genetic algorithms with PMcrossover operator

In order to decrease the searching space and improve the effectiveness of genetic algorithms. A refining operator is employed to deal with the bandwidth constraint (Wang et al. 2001). The links with a bandwidth less than the QoS requirement will be removed by the refining operator. On the one hand, if the source and all destinations are not in a connected component in a refined graph, all paths in a network cannot satisfy the bandwidth constraint, which means the bandwidth constraint should be relaxed. On the other hand, if the source node and all destination nodes are in a connected component, the paths in a refined graph must satisfy the bandwidth constraint. The flow chart of typical genetic algorithms with the PMcrossover and refining operator is shown in Fig. 2.

Figure 2 shows that the new proposed PMcrossover scheme only changes the crossover part of original genetic algorithms. As mentioned above, different genetic algorithms have different crossover operators. For verifying the universality of our proposed crossover scheme, we integrate PMcrossover into three different genetic algorithms [i.e., GAMRA (Hwang et al. 2000), EEGA (citealt2Lu2013) ISGSA (Zhang et al. 2009)] and estimate the efficiency in the next section.

Fig. 2
figure 2

The flow chart of typical PMGAs

Full size image

4 Experiments

Section 4.1 introduces the datasets used in this paper. And Sect. 4.2 shows and analyzes the results of different algorithms on these datasets. Parameters analysis is shown in Sect. 4.3, for a better performance. Finally, Sect. 4.4 reports the complexity analysis of PMcrossover.

4.1 Datasets

In order to estimate the effectiveness of PMcrossover scheme, we implement GAMRA, EEGA, ISGSA and their updating algorithms on four datasets. The first dataset (denoted as D1) is a 20-node random graph which is constructed based on Hwang et al. (2000). In D1, costs and delays of links are uniformly distributed between 0.3 and 1. The second (denoted as D2) is shown in Fig. 1, which is cited from Lu and Zhu (2013). For verifying the scalability of PMcrossover scheme, the third dataset (denoted as D3) is adopted. D3 is a synthetic graph generated by the Salama graph generator (Salama 1996), where there are 50 nodes and costs of links are generated between 3 and 10. Moreover, for comparing with other meta-heuristic algorithms, we implement EEGA, ISGSA and their updated algorithms on the fourth dataset (denoted as D4), which is came from Salim and Abdelhamid (2013) and constructed by the network simulatorFootnote 1. The details and thresholds of D1, D2, D3 and D4 are shown in the “Appendix”.

All experiments are under the same environment, i.e., all parameters of PMGAs are same as these of original GAs. And the results on D1, D2 and D3 in our experiments are based on 50 repeated experiments in order to wipe off the computational fluctuation. For comparing with the algorithms in Salim and Abdelhamid (2013), some results on D4 are based on ten repeated experiments.

4.2 Experimental analyze

Figure 3 reports the \({S_{\min }}\), \({S_{average}}\) and \({S_{\mathrm{var}iance}}\) of results calculated by PM-GAMRA and original GAMRA (Hwang et al. 2000) on D1. Although these two GAs can find approximate optimal solutions, \({S_{\min }}\) and \({S_{average}}\) of PM-GAMRA are less than that of original GAMRA, which means that PM-GAMRA has a stronger ability to exploit the optimal solution. Moreover, \({S_{\mathrm{var}iance}}\) of PM-GAMRA is less than that of GAMRA, which shows that the PM-GAMRA has a stronger robustness.

Fig. 3
figure 3

Comparing costs of results of PM-GAMRA and GAMRA on D1. a, b report the average, minimum and variance of cost, respectively. Compared with GAMRA, PM-GAMRA shows a better search ability and a stronger robustness

Full size image

As EEGA and ISGSA may generate unadaptable solutions in the evolution, we compare the costs and delays of results simultaneously. Figure 4a, b show \({S_{\min }}\), \({S_{average}}\) and \({S_{\mathrm{var}iance}}\) of costs and delays respectively, where \({S_{\min }}\), \({S_{average}}\) and \({S_{\mathrm{var}iance}}\) of PM-EEGA and PM-ISGSA are less than those of EEGA and ISGSA in both costs and delays. These results show that the PMcrossover scheme can strength the searching ability for finding the optimal solution and improve the robustness of original GAs.

Fig. 4
figure 4

Comparing results of GAs and PMGAs on D2. a, b report the cost and delay comparisons, respectively. Compared with GAs, PMGAs can find better solutions with stronger robustness

Full size image
Fig. 5
figure 5

The averages of delays and costs calculated by GAs and PMGAs on D2 are plotted in (a, b) respectively. Results show that delay and cost averages of PMGs have a higher descent rate than those of GAs

Full size image
Fig. 6
figure 6

The variances of delays and costs calculated by GAs and PMGAs on D2 are plotted in (a, b), respectively. Results indicate that PMGAs have a lower variances than those of GAs, which means that PMGAs have a stronger robustness

Full size image

In order to further verify the accuracy and robustness of PMGAs, Figs. 5 and 6 plot averages and variances of costs and delays with the increment of generations in the convergent process. Results show that the averages and variances of PM-EEGA and PM-ISGSA decrease more obviously than those of EEGA and ISGSA. In detail, in the earlier iteration, there is slight difference between averages of PMGAs and GAs. The initial delays of PM-EEGA and PM-ISGSA are even higher than those of EEGA and ISGSA. With the increment of generations, the averages of PM-EEGA and PM-ISGSA are less than that of EEGA and ISGSA. PM-EEGA and PM-ISGSA exhibit a better accuracy. Furthermore, the variances of PM-EEGA and PM-ISGSA are also less than those of EEGA and ISGSA, which indicates that PM-EEGA and PM-ISGSA have much stronger robustness.

Fig. 7
figure 7

Comparison costs of results on D3. Results show that PMcrossover can reduce the average cost of results and enhance the robustness of GAs

Full size image

To demonstrate the scalability of PMcrossover scheme, we implement four GAs (i.e., EEGA, PM-EEGA, ISGSA, PM-ISGSA) on D3 with the same parameters setting. For a better performance, parameters are set based on Table 1. Figure 7 shows that \({S_{\min }}\) and \({S_{average}}\) of PM-GAMRA, PM-EEGA, PM-ISGSA are all less than that of original ones. Furthermore, \({S_{\mathrm{var}iance}}\) of PM-GAMRA and PM-ISGSA are less than half those of GAMRA and ISGSA. Although \({S_{\mathrm{var}iance}}\) of PM-EEGA is higher than that of EEGA, the difference is too slight to have an effect on the performance of algorithms. These results indicate that GAs with PMcrossover exhibit more stronger ability to find optimal solutions. And PMcrossover scheme still work well when the scale of problem is increasing.

Table 1 Parameters setting of GAs
Full size table

For further verifying the effectiveness of proposed scheme and comparing with other meta-heuristic algorithms, we implement EEGA, ISGSA and their updated algorithms on D4 and add a new constraint on jitter, which is also a typical QoS property. In this paper, the jitter of a path (denoted as \(jitter({p_T}(s,d))\)) and the jitter of a tree (denoted as jitter(T)) are defined as Eqs. (13) and (14) respectively. Some meta-heuristic algorithms (i.e., BLA (bees life-based algorithm) (Salim and Abdelhamid 2013), BA (bees algorithm) (Pham et al. 2006), MBO (marriage in honey bees optimization algorithm) (Abbass 2001) are used to compare the efficiency with our proposed methods. And the fitness values of those algorithms (as listed in Fig. 8a) are extracted from Salim and Abdelhamid (2013) directly. Moreover, the fitness and property values in Table 2 are calculated based on D4 and topological structures of best results shown in Salim and Abdelhamid (2013), which are generated by those algorithms.

$$\begin{aligned} jitter({p_T}(s,d))= & {} \sum \nolimits _{e \in {p_T}} {jitter(e)} \end{aligned}$$
(13)
$$\begin{aligned} jitter(T)= & {} \max \{jitter({p_T}(s,d))|d \in DE\}\end{aligned}$$
(14)
$$\begin{aligned} f(T)= & {} {w_1}{f_c}(T)+{w_2}{f_d}(T)+{w_3}{f_j}(T)+{w_4}{f_b}(T) \end{aligned}$$
(15)

As the fitness function is an important part of GA, we retain the original fitness functions, when algorithms run, and calculate new fitness values based on Eq. (14) for a fair comparison. In Eq. (14), \({f_c}(T)\), \({f_d}(T)\), \({f_j}(T)\) and \({f_b}(T)\) stand for the cost, delay, jitter, bandwidth of a multicast tree T, respectively. Meanwhile, \(w_i\) represents the objective weighting coefficient. The objective weighting coefficients and thresholds of constraints are set based on Salim and Abdelhamid (2013).

Table 2 Fitness and property values of best results generated by different algorithms on D4. The best values of properties are emphasized by boldtype
Full size table
Fig. 8
figure 8

The averages and variances of fitness calculated by different algorithms on D4 are plotted in (a, b) respectively. The average fitness values of GAs and PMGAs are lower than those of other algorithms. And the gap between variances of PMGAs and GAs is significant

Full size image

Table 2 lists the fitness value, cost, delay, jitter and bandwidth of the best multicast trees generated by different algorithms. As shown in Table 2, BLA, EEGA and PM-EEGA converge to the multicast tree with the lowest cost. Meanwhile, ISGAS and PM-ISGAS converge to the multicast tree with the lowest fitness value.

To further compare the efficiencies of those algorithms, the averages and variances of fitness values, which are generated by 10 repeated experiments, are calculated and shown in Fig. 8a, b respectively. Although the averages of EEGA and ISGSA are close to those of their updated algorithms, variances of EEGA, ISGSA and those of their updated algorithms have a significant difference. As shown in Fig. 8b, variances of PM-EEGA and PM-ISGSA are much lower than those of EEGA and ISGSA. It means PMcrossover still can enhance the robustness of original algorithms, when the original algorithms can find optimal solutions.

4.3 Parameters analysis

As mentioned in Sect. 3.1, there are two parameters, \(\lambda\) and k, which affect the amplitude of conductivities in the Physarum network. In order to further analyze the convergence rate of Physarum model, we run this model with different \(\lambda\) and k values. Because the computational time is affected by computing environments which are hard to be fully controlled, we use iterative steps instead of computational time to compare the convergence rate. We remark the iterative steps with different k and \(\lambda\) values on D2 and D3. The iterative steps are recorded when the terminal condition is satisfied. In this paper, the terminal condition is that iterative steps beyond the maximal iterative steps or Eq. (16) is satisfied (Zhang et al. 2014), where \({{D}_{ij}}^t\) stands for \({D}_{ij}\) at iterative step t. And the maximal iterative steps are set as 10000 and 50000 when the model runs on D2 and D3 respectively.

$$\begin{aligned} Max \{|{D^t}_{ij} - {D^{t - 1}}_{ij}||\forall i,j\} <10^{-6} \end{aligned}$$
(16)
Fig. 9
figure 9

Iterative steps of physarum model with different \(\lambda\) and k. Based on those results, best parameters setting of Physarum model can be obtained. a, b report the iterative steps of physarum model with the increment of \(\lambda\) under different k value on D2 and D3 respectively

Full size image

As shown in Fig. 9, iterative steps of Physarum model are more sensitive to \(\lambda\) rather than k. The relationship between k and iterative steps is simple. The higher k is, the lower iterative steps are. But if k is too high, conductivities in the Physarum networks will fall sharply, which may lead to the disappearance of some crucial links. For the parameter \(\lambda\), 0.l is a special value. When \(\lambda\) is equal to 0.1, iterative steps reach the maximal iterative steps, except when k is equal to 1.2. It means, in most situations, the Physarum model cannot converge when the iterative steps reach the maximal iterative steps. As shown in Fig. 9a, the higher \(\lambda\) is, the higher iterative steps are. But in Fig. 9b, iterative steps have a decline at the final stage with the increment of \(\lambda\). And the reason of this decline is that \(\lambda\) is too high, which results in slight amplitudes of conductivities. Thereby some redundant links have not been cut, when Eq. (16) is satisfied.

Comparing iterative steps between Fig. 9a, b, the average of iterative steps arises from 3348.7 to 13963, but the minimum of iterative steps just arises from 1669 to 1726. Although the average of iterative steps has a significant rise, the minimum of iterative steps rises slightly. These results suggest the modified Physarum model with a better parameters setting has a good ability to adapt to the increment of problem scales.

4.4 Complexity analysis of PMcrossover

Computational complexities of GAs with different coding schemes and genetic operators are hardly described uniformly. Hence, we just focus on the computational complexities of crossover operators. For a comparison, we analyze the crossover operators of EEGA, GAMRA, ISGSA and PMcrossover. All experiments are implemented on Matlab 2012b, with Pentium(R) Dual-Core CPU E5700 and 1.8 GB RAM.

  • PMcrossover: Let N, E be the numbers of nodes and edges in a network respectively, and IT be the iterative steps of Physarum model. First, PMcrossover spends O(E) time units on selecting common links between parent chromosomes. In the iterative stage, O(N) time units are used for calculating the pressure at every node based on Eq. (10). After that, O(E) time units are spent on calculating the conductivities of links based on Eq. (12). And then PMcrossover goes to the next iteration. Thereby the total computational complexity of PMcrossover is represented in Eq. (17).

    $$\begin{aligned} O(E) + O(IT \times (E + N)) = O(IT \times (E + N)) \end{aligned}$$
    (17)

  • The crossover operator of GAMRA: Let L be the number of destinations. First, two chromosomes with larger fitness values are picked. After that, O(1) time units are used for selecting star and end points of portion to be exchanged. And then changing the selected portion between two chromosomes spends at most O(L) time units. Thereby the complexity of such crossover operator is measured by Eq. (18).

    $$\begin{aligned} O(1) + O(L) = O(L) \end{aligned}$$
    (18)

  • The crossover operator of ISGSA: There are three steps in the processing of crossover operator. First, operator reserves the same links of parent chromosomes, which spends O(E) time units. And then, operator adds links randomly from destinations, which are separated by the source node, to the connected component including the source node. This step needs at most O(E) time units. In the third step, excrescent links are deleted, and \(O(N^2)\) time units are spent on the this step. Thereby the complexity of such crossover operator is represented by Eq. (19).

    $$\begin{aligned} O(E) + O(E)+ O(N^2)=O(E+N^2) \end{aligned}$$
    (19)

  • The crossover operator of EEGA: The crossover operator of EEGA also spends O(E) time units on selecting the common links between parent chromosomes. We assume that there are S sub-trees with just the common links between parent chromosomes. And then at most \(S-1\) least-delay paths need to be found to connect these sub-trees. In the worst situation, the operator needs \(O(N^2)\) time units to find a least-delay path. Thereby the complexity of such crossover operator is represented in Eq. (20).

    $$\begin{aligned} O(E) + O((S-1)\times (N^2)) \end{aligned}$$
    (20)

Although the crossover operator of GAMRA has the lowest computational complexity, the GAMRA spends a lot of time on constructing the routing table. Therefore, it is less significant to compare GAMRA with others. However, we present the time complexity of these crossover operators. The actual situations are more complex. For further analyzing the computational cost of PMcrossover scheme, we show the extra computational cost (denoted as ECC) and the improvement-ratio (denoted as IR) of PMGAs in the evolutionary process on D2, simultaneously. Based on definitions in Huang and Lee (2007), the \(IR_{i}\) is measured by Eq. (21), where \(S_{average}^i\) and \(\widehat{S}_{average}^i\) stand for the average cost of results at the ith generation of GAs and their updating algorithms respectively. And the \(ECC_{i}\) is defined as Eq. (22), where \(S_{time}^i\) and \(\widehat{S}_{time}^i\) represent for computational cost which GAs and PMGAs spend on the ith generation respectively. And the computational cost is defined as the time spending on computation in scends.

$$\begin{aligned} IR_{i}= & {} \frac{{(S_{average}^i - \widehat{S}_{average}^i)}}{{S_{average}^i}} \end{aligned}$$
(21)
$$\begin{aligned} ECC_{i}= & {} \widehat{S}_{time}^i - S_{time}^i \end{aligned}$$
(22)
Fig. 10
figure 10

The dynamic changes of IR and ECC. a, b show the ECC and IR of PM-EEGA and PM-ISGSA on D2 respectively. ECC values of PM-ISGSA and PM-EEGA both descent with the increment of generations. Comparing with IR of PM-EEGA, IR of PM-ISGSA declines quickly with the increment of generations. Results suggest the efficiency of PMGAs has the significant improvement for GAs

Full size image

Figure 10 shows the IR and ECC of PM-EEGA and PM-ISGSA on D2, respectively. ECC values of PM-ISGSA and PM-EEGA both are higher at the initial stage and then show a downtrend. Meanwhile, IR values of PM-ISGSA and PM-EEGA also have a rise at the initial stage. The main difference between PM-ISGSA and PM-EEGA is the decline rate of IR with the increment of generations. In detail, IR of PM-EEGA descends slightly while IR of PM-ISGSA descends rapidly. At the final stage, IR of PM-EEGA is still higher while IR of PM-ISGSA is not so remarkable, compared with the initial stage. Because PMGAs can find the optimal solution with a fewer generations, their computational costs can be reduced by setting a lower maximal generation. Based on above observations, we can conclude that PMcrossover has the significant improvement for GAs.

5 Conclusion

Inspired by Physarum polycephalum forming an optimized network in foraging food sources, a genetic algorithm based on the modified Physarum network was proposed to solve the multicast routing NP-complete problem. In the proposed PMGA, a new crossover operator was presented, which can improve the effectiveness of GA. Some experiments on four datasets were used to verify the efficiency of proposed method. Moreover, for further improving the efficiency of PMGA, the original Physarum network model is modified by simplifying the calculation of pressures in Physarum networks. Furthermore, parameters analyses indicate that the modified Physarum model with a better parameters setting has a better scalability.