Parallel 3-Parent Genetic Algorithm with Application to Routing in Wireless Mesh Networks

Abstract

This chapter proposes a new multi-population global optimization algorithm: the parallel 3-parent genetic algorithm (P3PGA). The performance of the new algorithm was compared with 16 other algorithms based on 30 benchmark functions from the 2014 Congress on Evolutionary Computation test suite. P3PGA was the best-performing algorithm on 14 out of the 30 benchmark functions.

We applied P3PGA to a minimal cost path routing problem in wireless mesh networks. The proposed approach was implemented in MATLAB and simulated for various wireless mesh network sizes and scenarios. We compared its performance on this problem with eight other approaches: Ad hoc On-Demand Distance Vector Routing, Dynamic Source Routing, Genetic Algorithm, Biogeography-Based Optimization, Firefly Algorithm, Ant Colony Optimization, the BAT Algorithm, and Big Bang–Big Crunch algorithm based routing approaches. P3PGA outperformed all other approaches for networks with 1000+ nodes.

1 Introduction

Genetic algorithms (GAs) are widely used computer-based search and optimization algorithms based on the mechanics of natural genetics and natural selection [1,2,3,4,5]. In the decade between 1950 and 1960 many researchers worked on evolutionary systems with the idea that evolution could be used as optimization approach for many engineering problems [4]. J. Holland introduced the concept of genetic algorithm in 1960 [5]. Usually genetic algorithms are based on two-parent genetic processes; however, some literature on multi-parent recombination can also be found in [6,7,8,9]. Mühlenbein and Voigt [6] presented the concept of gene pool recombination (GPR), and applied it to find solutions in a discrete domain. Eiben and Van Kemenade [7] proposed the concept of diagonal crossover as generalization of uniform crossover in GA and applied it to numerical optimization problems. Wu et al. [8] proposed multi-parent orthogonal recombination and applied it to find out the identity of an unknown image contour. The crossover operators used in those areas enabled significant improvements in search ability, although improvements were found to be highly problem dependent. Eiben et al. [9] proposed two multi-parent recombination mechanisms, namely gene scanning and diagonal crossover. They extensively tested their multi-parent algorithm on a variety of problems in numerical optimization, constrained optimization (traveling salesman problem) and constraint satisfaction (graph coloring). Compared to two-parent recombination, their algorithm achieved superior performance in optimizing the first four test functions of De Jong. For other problems the results were mixed; multi-parent crossover sometimes performed better and at times worse than classical two-parent recombination.

The parallel three-parent genetic algorithm presented in this chapter is based upon three-parent genetic processes in medical science and is very different from the approaches available in the literature. In medical science, a three-parent process has been used to prevent mitochondrial diseases in children of mothers with defective mitochondria [10,11,12,13]. In 2015, Dr. John Zhang and his team at the New Hope Fertility Center in New York City replaced the nucleus of a donor’s egg cell with the nucleus of original mother, which was then fertilized with the father’s sperm and implanted in the mother. The child that was subsequently born inherited mitochondrial DNA from the donor, besides nuclear DNA from the father and mother [13]. The concept of this three-parent genetic process is shown in Fig. 1. The P3PGA algorithm is in some respects a mathematical analogy of this practical process.

Fig. 1

3-Parent Process adapted from Zhang et al. [13]

This chapter includes two different but related research investigations. The first is an evaluation of the performance of P3PGA on functions from an established test suite and comparison with other well-known recent algorithms. The second investigation concerns the application of P3PGA to an important and challenging practical problem, namely routing in wireless mesh networks (WMNs) [14].

This chapter is organized into six sections. Section 1 presents the motivation for this work; Section 2 discusses the working of P3PGA algorithm; Section 3 describes the simulation and performance of P3PGA on the 2014 Congress on Evolutionary Computation (CEC-2014) test bench suite compared to 16 other algorithms; Section 4 proposes a P3PGA-based minimal cost route evaluation approach for WMNs; Section 5 presents its implementation and performance on WMNs as well as a performance comparison with eight other algorithms found in the literature; and Sect. 6 summarizes conclusions.

2 P3PGA Algorithm

The Parallel 3-Parent Genetic Algorithm (P3PGA) is a multi-population algorithm in which evolution process takes place on several populations in parallel. It is based upon the single-population three-parent genetic algorithm (3PGA) [15, 16].

A pseudocode for the proposed P3PGA approach is as given in the listing below in Algorithm 1. In this algorithm we initially create several populations of equal size: these are called 2-parent populations. To generate a 3-parent population from a 2-parent population we applied the “mitochondrial change” to each individual by adding a small random number to each gene of each individual in the population. The fittest individual (best solution) within a population is called the local elite of that specific population. The best of all local elites is called the global elite. All genes for all individuals in all the populations are moved towards the corresponding gene of the global best candidate solution with low probability. This guides every candidate solution towards the global best solution.

Algorithm 1: P3PGA algorithm

begin

Generate NP populations each of size N candidates randomly, every candidate consisting of NG genes;

for gen = 1:Number of generations do

for i = 1:NP do

Effect Mitochondrial Change to i th 2-parent (2-P) population to Generate an i th 3-Parent (3-P) population   Combine the 2-P and 3-P populations and select the N best individuals.   Find and record the globally best solution.   Generate a new 2-P population using general genetic process (using GA)

(a) Select fit individuals for recombining/breeding.    (b) With high probability recombine parents/perform cross-over.    (c) With low probability mutate offspring.    (d) Select the N best individuals from among parents and offspring...

Check bounds violation and correct if needed.

end for (i)

Check the fitness of all the individuals of all the populations and select/update the globally best gbest candidate and its fitness;

for i = 1: NP do

for j = 1: N do

for k = 1: NG do

With a fixed small probability replace gene k of individual j in population i with (individual(j,k) + gbest(j,k))/2;

end for (k)

end for (j)

end for (i)

end for (gen) end

For the better understanding of the algorithm, we describe its operation on a very simple example where we wish to search a 4-digit quantity such that the sum of 4 digits is maximal, given that each digit is an integer between 0 and 9 (the obvious answer is 9999). We proceed in such a way that the reader will be able to track progress towards this solution as the algorithm progresses. The algorithm parameters are chosen as shown in Table 1.

Table 1 Parameter values for illustrative example of P3PGA

Step 1

Randomly create 3 two-parent populations, where each population consists of three candidate solutions and each candidate solution is an array of four digits (genes) having the form (d ₁, d ₂, d ₃, d ₄):

• TwoParentPop(1): [(3,6,1,7), (5,2,6,3), (4,6,5,3)]

• TwoParentPop(2): [(5,3,6,2), (5,6,7,8), (8,2,7,6)]

• TwoParentPop(3): [(7,4,5,1), (5,6,1,3), (3,8,4,9)]

We may rewrite these three populations in matrix format, for example:

$$ {\mathrm{TwoParentPop}}(1)=\left[\begin{array}{l@{\quad}l@{\quad}l@{\quad}l}3 & 6 & 1 & 7\\ 5 & 2 & 6 & 3 \\ 4 & 6 & 5 & 3\\ \end{array}\right] $$

TwoParentPop(2) and TwoParentPop(3) may be expressed similarly as

$$ {\mathrm{TwoParentPop}}(2)=\left[\begin{array}{l@{\quad}l@{\quad}l@{\quad}l}5 & 3 & 6 & 2\\ 5 & 6 & 7 & 8 \\ 8 & 2 & 7 & 6\end{array}\right] $$

and

$$ {\mathrm{TwoParentPop}}(3)=\left[\begin{array}{l@{\quad}l@{\quad}l@{\quad}l}7 & 4 & 5 & 1\\ 5 & 6 & 1 & 3\\ 3 & 8 & 4 & 9\end{array}\right] $$

Step 2

For each gene of every individual in each of the populations, effect a mitochondrial change by adding a random number to each gene. In our case, each gene change is generated as a uniformly distributed random integer between −2 and 2. This may be implemented by generating a change matrix for each population, adding the change matrix to the population matrix, and truncating so that the gene values remain within the range from 0 to 9. For example, suppose the change matrix for the first population is given by:

$$ {\mathrm{Change}}(1)=\left[\begin{array}{l@{\quad}l@{\quad}l@{\quad}l}2 & 0 & -2 & 1\\ 1 & -1 & 2 & 1\\ 0 & 2 & 2 & 2\end{array}\right] $$

Let us further assume that the randomly generated mitochondrial changes for the second and third populations are as given below:

$$ {\mathrm{Change}}(2)=\left[\begin{array}{l@{\quad}l@{\quad}l@{\quad}l}-2 & 0 & -1 & 1\\ 1 & 2 & 2 & -1\\ 0 & 2 & 2 & 2\\ \end{array}\right];\quad {\mathrm{Change}}(3)=\left[\begin{array}{l@{\quad}l@{\quad}l@{\quad}l}-2 & 0 & -1 & 2\\ 1 & 2 & 2 & -1\\ 0 & 1 & -2 & 2\\ \end{array}\right] $$

Using 2-parent population and Change matrices for each population we compute the 3-parent populations as follows:

$$ 3\mbox{\_}{\mathrm{Parent}}\mbox{\_}{\mathrm{Population}}(n)=\kern0.75em 2\mbox{\_}{\mathrm{Parent}}\mbox{\_}{\mathrm{Population}}(n)\kern0.75em +\kern0.75em {\mathrm{Change}}(n) $$

Whenever this formula produces an entry in 3_Parent_Population(n) that is less than 0 or greater than 9, it is replaced with 0 or 9, respectively.

Step 3

The three-parent populations are then combined with their corresponding two-parent populations to form populations that are twice as large. In our example, these combined populations are given by three 6 × 3 matrices (matrix rows are separated by semicolons)

• Population 1: [3 6 1 7; 5 2 6 3; 4 6 5 3; 5 6 0 8; 6 1 8 4; 4 8 7 5]

• Population 2: [5 3 6 2; 5 6 7 8; 8 2 7 6; 3 3 5 3; 6 8 9 7; 8 4 9 8]

• Population 3: [7 4 5 1; 5 6 1 3; 3 8 4 9; 5 4 4 3; 6 8 3 2; 3 9 2 9]

We choose the three individuals for each population with highest fitness, which are then sorted in decreasing order of fitness. Table 2 shows the results of this operation.

Table 2 Populations, individuals, and their Fitness

Step 4

The conventional genetic algorithm operations of recombination (crossover) and mutation are now performed within the resulting populations.

• Step 4a. Usually fitness of an individual is used as selection criterion for crossover. Various selection strategies may be used, including roulette wheel selection, stochastic universal sampling, truncation selection, tournament selection, and so on (interested reader may refer to [17,18,19] for details). We have used stochastic universal sampling (SUS) for selection of parents for recombination. In our example, we may suppose that individuals 1 and 3 in population 1 are selected, and a crossover operation is performed on the two individuals with high probability (usually between 0.75 and 0.9). A typical example of a crossover operation is shown in Fig. 2.

• The operation shown is a single-point crossover with crossover point after first gene. Crossover can be single point, two point, or n-point. If crossover does not take place, then both individuals are passed on as offspring.

• Step 4b. Following crossover, mutation is performed. In the case of real-valued genes, one way to perform mutation involves replacing the current gene with a randomly generated value from within the universe of discourse of that gene with a low probability. Both the probability of mutating a gene (mutation rate) and the distribution of changes for each mutated gene must be specified. For example, the change may be determined as a uniform random number in an interval [−a, a]. In our example, we have taken a = 2 and the mutated genes are rounded off to the nearest integer.

• Step 4c. Following crossover and mutation, the offspring are grouped together with their parents for each population, and the three fittest from each population are chosen as the next generation. Note each generation of each population always has the same number of individuals (equal to N, which is one of the algorithm’s basic parameters). Let us assume that the individuals 4 8 7 5 and 5 6 0 8 were selected for recombination assuming the crossover point was after first two genes. Thus, the combination produced two offspring, i.e., 4 8 0 8 and 5 6 7 5. Let us further assume that individual 6 1 8 4 was passed as it is as an offspring. Let us further assume that the mutation operator mutated first offspring to 4 8 0 7, second offspring to 5 8 7 5, and the third offspring to 6 0 8 4. Replacing the weaker parents with the stronger offspring produces the results as shown in Table 3.

• Step 4d. Compute elites (local best) and global best:

Fig. 2

Single-point crossover operation

Table 3 Evolving new population after crossover and mutation

Global best (g_best) candidate solution after one generation is: “6 8 9 7” with fitness values of 30 (6 + 8 + 9 + 7 = 30). The computation of elite (local best) is for better understanding of the algorithm only. For better code efficiency we can directly compute global best from the evolved generations. However, for algorithm 2, which is based upon algorithm 1, computation of elites (local best of each population) is essential (Table 4).

Table 4 Local best (elites) and global best

Step 5

After a predetermined number of generations, with a given probability we replace ith gene of every individual with a gene whose value is the average value of the ith gene of individual and ith gene of g_best, i.e.,

$$ {\mathrm{individual}}(i)\kern0.75em \leftarrow \left({\mathrm{individual}}\ (i)\kern0.75em +{\mathrm{g}}_{\mathrm{best}}(i)\right)/2 $$

Table 5 summarizes the results of first iteration of computer implementation of example using the P3PGA algorithm.

Table 5 First iteration and corresponding output of each major step of computer implementation of P3PGA for the example under consideration

Continuing further execution of the program we find that our algorithm reached the best result in about 15 iterations. Figure 3 shows number of generations (iterations) versus fitness for our example.

Fig. 3

Generation number versus fitness of globally best result for simple P3PGA example

3 Simulated Performance, Results, and Discussion

We implemented the proposed P3PGA algorithm in MATLAB on a Core i7 @ 2.2GHz based laptop with 8GB RAM and tested its performance on 30 functions from the CEC-2014 test bench. To evaluate the performance of P3PGA we used N = 10 populations and NC = 20 candidate solutions. Our P3PGA results were compared to results obtained from CEC-2014 for 16 other algorithms: the United Multi-Operator Evolutionary Algorithms (UMOEAS) [20], LSHADE [21], Differential Evolution with Replacement Strategy (RSDE) [22], Memetic Differential Evolution Based on Fitness Euclidean-Distance Ratio (FERDE) [23], Partial Opposition-Based Adaptive Differential Evolution Algorithms (POBL_ADE) [24], Differential Evolution strategy based on the Constraint of Fitness values classification (FCDE) [25], Mean-Variance Mapping Optimization (MVMO) [26], RMA-LSCh-CMA [27], Bee-Inspired Algorithm for Optimization (OptBees) [28], Simultaneous Optimistic Optimization (SOO) [29], SOO+ Bound Optimization BY Quadratic Approximation (SOO + BOBYQA) [29], Fireworks Algorithm with Differential Mutation (FWA-DM) [30], algorithm Based on Covariance Matrix Leaning and Searching Preference (CMLSP) [31], Gaussian Adaptation Based Parameter Adaptation for Differential Evolution (GaAPADE) [32], Non-Uniform Mapping in Real-Coded Genetic Algorithms (NRGA) [33], and DE_b6e6rlwithrestart [34]. The MATLAB code for the compared algorithms and the link to algorithm performance results may be obtained from http://www.ntu.edu.sg/home/EPNSugan/index_files/CEC2014/CEC2014.htm. For P3PGA we conducted 20 trials for each of the 30 functions, and took the mean error of all 20 trials as the performance measure.

The performance of P3PGA along with 16 other algorithms is given in Table 6 (see Appendix 1). Results of the comparison between algorithms are summarized in Table 7. P3PGA gave the unmatched best performance for 12 functions (f5, f9, f10, f11, f14, f15, f16, f19, f21, f24, f25, and f27) (Table 8). For f3 the performance of P3PGA was equaled by UMOEAS, RSDE, FCDE, DE_ b6e6rlwithrestart, LSHADE, MVMO, FWA-DM, and GaAPADE algorithm; and for f8 P3PGA’s performance was matched by UMOEAS, FERDE, DE_b6e6rlwithrestart, GaAPADE, LSHADE, MVMO, OptBees, and RMA-LSCh-CMA. Altogether, P3PGA was the top-ranked algorithm, while UMOEAS was second.

Table 7 Comparative performance of P3PGA on CEC-2014 benchmarks

Table 8 Number of functions for which P3PGA gave the best performance

4 P3PGA for Minimal Cost Route Evaluation

A wireless mesh network (WMN) can be mathematically represented as a set of “nodes” or points in the two-dimensional plane. These nodes represent the positions of clients, routers, and gateways that receive and retransmit communications signals. Naturally, the devices represented by nodes all have limited communication range. In order to send a signal from a source node to a destination node, a route (or path) consisting of intermediate nodes must be found such that the signal from the source node can be successively received and retransmitted until it reaches the destination node. The process of determining the end-to-end route between a source node and a destination node is referred to as “routing.” An optimal route will be one that minimizes cost, where cost is defined in terms of a routing metric. There are many possible routing metrics that appear in the literature, including minimum hop count, per hop Round Trip Time (RTT) [35], Per-Hop Packet Pair Delay (PktPair) [36], Expected Transmission Count (ETX) [37], Expected Transmission Time (ETT), Weighted Cumulative ETT (WCETT) [38], Expected Transmission on a Path (ETOP) [39], Effective Number of Transmission (ENT) and Modified Expected Number of Transmissions (mETX) [40], Metric of Interference and Channel Switching (MIC) [41], Bottleneck Link Capacity (BLC) path metric [42], cross layer link quality and congestion aware (LQCA) metric [43], and interference aware low overhead routing metric [44]. In this chapter, we use an integrated link cost function to evaluate route cost: for details see [45].

The adapted P3PGA algorithm that was used for finding optimal routes for WMNs is outlined in Algorithm 2 below. The algorithm follows all the steps of the general P3PGA algorithm described in Algorithm 1 in the previous section. These steps are described in more detail in the following paragraphs.

The first step in the algorithm is to determine initial populations of possible routes. This is done by means of an adjacency matrix, which is a (number of nodes) by (number of nodes) square matrix of 0’s and 1’s. The (i,j)th entry of the matrix is 1 if nodes i and j have a possible connection, and 0 otherwise. Using the adjacency matrix a set of route populations is generated, where each population has the same number of routes. These are the initial 2-parent populations. Next, we generate a 3-parent population from each of the current 2-parent populations and combine these two populations as in Algorithm 1. The new population is evolved from the old population using the crossover approach as given in [46]. Each 3-parent population is obtained by applying the following rules to all routes in the 2-parent population:

• (a) Beginning with second node, check the location of the ND^th node of the local elite in the current path, where ND is defined so that nodes 2…ND-1 of the local elite are not in the current path, but ND is in the current path.

• (b) If the ND^th node lies in first half of the current path, then follow the steps as given below:

  • I. Retain nodes of current individual up to ND and call it partial route1.

  • II. From the elite extract all nodes from the node after “ND” to the terminal node and call it partial route2.

  • III. Combine partial route1 and partial route2 to form a new path.

• (c) If the “ND^th” node of the local elite lies in the second half of the current path, then follow the steps as given below:

  • I. Retain the local elite up to “ND” and call it partial route1.

  • II. From the current path extract all nodes from the node after “ND” to the terminal node and call it partial route2.

  • III. Combine partial route1 and partial route2 to form a new route.

For example, in a WMN, let node number 1 represent the source node and node number 10 represent the terminal node. Suppose that the following two-parent population of routes exists between source and terminal node:

$$ 2\hbox{-} {\mathrm{parent}}\ {\mathrm{population}}\;1:\left[1\;4\;5\;8\;9\;10;1\;3\;2\;7\;12\;8\;11\;9\;10;1\;6\;7\;4\;13\ 12\;5\;9\;10\right] $$

In this population the local elite (shortest path) is: 1 4 5 8 9 10

Since the local elite is the fittest route (minimal cost path as per hop count method) we would not apply mitochondrial change to this elite route.

In the second route (2-parent route 2) we find that node 8 is the first node in the route that is shared with the local elite. This node lies in the second half of 2-parent route 2. Hence, we would retain the local elite up to node 8 and denote it as partial route 1:

$$ {\mathrm{Partial}}\ {\mathrm{route}}\;1:\left[1\;4\;5\;8\right] $$

From the current route (2-parent route 2), we extract all nodes starting from the node after 8 up to the terminal node, and denote it as partial route 2:

$$ {\mathrm{Partial}}\ {\mathrm{route}}\;2:\left[11\;9\;10\right] $$

After combining partial route 1 and partial route 2 we get a new 3-parent route:

$$ 3\hbox{-} {\mathrm{parent}}\ {\mathrm{route}}\;1:\left[1\;4\;5\;8\;11\;9\;10\right] $$

Similarly, we make the mitochondrial change in 2-parent route 3 as follows. We first identify that the first node in the route that is shared with the elite is node 4, which lies in the first half of the current route. So we retain current route up to node 4 and denote it as partial route 1:

$$ {\mathrm{Partial}}\ {\mathrm{route}}\;1:\left[1\;6\;7\;4\right] $$

From the elite we extract all nodes after node 4 up to the terminal node, and denote it as partial route 2.

$$ {\mathrm{Partial}}\ {\mathrm{route}}\;2:\left[5\;8\;9\;10\right] $$

After combining partial route 1 and partial route 2 we obtain a second 3-parent route as follows:

$$ 3\hbox{-} {\mathrm{parent}}\ {\mathrm{route}}\;2:\left[1\;6\;7\;4\;5\;8\;9\;10\right] $$

We combine the 2-parent routes with the newly evolved 3-parent routes into a single combined population:

$$ \left[1\ 4\;5\;8\;9\;10;\kern0.5em 1\;3\;2\;7\;12\;8\;11\;9\;10;\kern0.5em 1\;6\;7\;4\;13\;12\;5\;9\;10;1\;4\;5\;11\;9\;10;\right.\\{}\left.1\;6\;7\;4\;5\;8\;9\;10\right] $$

The algorithm then evaluates the fitness of all routes in this combined population, dropping the weaker individuals and retaining the fittest N individuals, thus maintaining a constant population size.

Once this is completed, the standard genetic processes of crossover and mutation can be performed just as demonstrated in Algorithm 1, to obtain optimal solutions for all populations. The optimum of these local optima gives the current global optimum, which may then be used to update the routing table entry for the given source and destination node, so that subsequent data transfer between these two nodes may take place on the minimal cost routes. Being parallel in nature the convergence time of this algorithm is expected to be quite small.

Algorithm 2: P3PGA approach for dynamic optimal cost route evaluation

Begin

/* Adjacency matrix: matrix of neighbor nodes of each node */ /* Variables:  pop_mat: Populations of routes;  path_mat: Matix whose rows are the routes in a given population;  NP: Number of populations,  N: Number of routes per population  Path_nodes: Number of nodes in a route. */ Calculate N routes using adjacency matrix. Evaluate fitness of all routes in all populations. Determine the local best routes ℓbest(i), i = 1…NP for all populations i. Record the global best (gbest) route from amongst all the local best routes; for Gen = 1: Number of Generations do

for pop = 1: NP do

/* 3 Parent Population generation starts */   3P_path = pop_mat(pop).path_mat

local_elite = ℓbest(pop)   for i = 1:N do    SE = number of nodes in local_elite

if 3P_path(i) ! = local_elite then

for j = 2:SE-1 do

LOE = location of local_elite(j) in 3P_Path(i).      if LOE > 0       if LOE > path_mid then /* path_mid = half of ith path*/        partial_route1 = first j nodes of local_elite        partial_route2 = nodes from LOE+1 to target node in 3P_path(i)       else        partial_route1 = first LOE nodes of 3P_path(i)        partial_route2 = nodes from j + 1 to target node in local_elite       end if       new_3P_path = concatenation of partial_route1 and partial_route2       Append new_3P_path to 3P_path       Break

end if

end for (j)

end if

end for (i) /* 3 Parent Population generation Ends */

/* Generation of 2-parent population from 3-parent population starts */   Evaluate fitness of all paths in 3P_path, sort from best to worst and select the N best paths   Select the fit paths for recombining/breeding;   With high probability recombine parents/perform cross-over.   With low probability mutate paths.   Evaluate fitness and select local_best.   Replace weak paths by stronger paths keeping the path_mat size fixed at N;   pop_mat(pop).path_mat = 3P_Path;  end for (pop) /*Generation of 2 Parent Population from 3 Parent Population Ends */  From amongst the NP local best candidates select the global best candidate gbest;

/*move all routes of all populations towards global best*/   for i = 1:NP do    for j = 1:N do

for k = 1:Path_nodes(j) do      With a given probability replace kth node of jth route with a node of gbest using combination operation.     end for (k)

end for (j)   end for (i)

end for (gen)

5 Implementation and Performance of the Proposed Approach

To evaluate the comparative performance of the proposed P3PGA-based minimal cost route evaluation approach for WMNs, we implemented all the approaches in MATLAB and simulated for 100, 500, 1000, 2000, and 2500 node client WMNs. Parameters for the different WMNs are shown in Table 9. For each WMN, node locations were randomly generated within the specified area. To evaluate the performance of all approaches on 100, 500, 1000, and 2000 node client WMNs we conducted 10 trial sets, one set for a given timing constraint. On 2500 node client WMNs we considered 17 trial sets. For all networks, each trial set consists of 20 trials: to test algorithm performance in a dynamic environment, the node locations were randomly regenerated for each trial. In total, 1340 trials were conducted.

Table 9 Architectural details of client WMNs used in simulations

5.1 Comparative Performance of 100 Node Client WMNs

For 100 node client WMNs we evaluated the performance of nine approaches. The unmatched performances of all the nine approaches are shown in Table 10 and Fig. 4. Table 10 shows the total performance (matched and unmatched) of nine approaches. From the results, we observe that ACO and DSR are unreliable protocols for the given network scenarios because most of the time these protocols failed to discover any feasible routes between source-terminal pair. Being a proactive approach, the BAT approach successfully discovered feasible routes but failed to produce an unmatched optimal cost route in any of the trials.

Table 10 Comparative performance of P3PGA on 100 node client WMNs

Fig. 4

Comparative unmatched best performance of 100 node client WMNs

Table 10 shows that for the timing constraint of 0.1 second, AODV produced a minimum cost route 7 + 5 = 12 times, where the first operand (7) indicates that 7 times AODV generated an unmatched optimal cost route, and the second operand (5) indicates that 5 times other algorithms obtained the same minimum cost (in this case, the other algorithms are GA, BBBC, FA, and P3PGA). The second and third place algorithms were BBBC (5 + 5 = 10 times) and P3PGA (3 + 5 = 8 times).

For the timing limit of 0.2 second, P3PGA produced minimum cost route 8 + 2 = 10 times, AODV 6 + 2 = 8 times, BBBC 3 + 2 = 5 times, and BBO produced minimum cost route 1 + 2 = 3 times. Figure 4 shows that for 100 node networks and for timing constraints less than 0.5 s (except 0.2 s) AODV performs better than all other algorithms. For timing constraint of 0.5 and 0.6 s the performance of GA is best. For timing constraint of 0.7 s BBBC and P3PGA both give best performance. As the timing constraint is further increased, more computing time is allocated to the P3PGA algorithm, so that results improve with increasing timing constraint. In terms of producing optimal cost routes, for timing constraints of 0.2, 0.8, 0.9, and 1.0 s, P3PGA algorithm outscores all other algorithms.

5.2 Comparative Performance of 500 Node Client WMNs

For 500 node client WMNs we evaluated the performance of all given 9 optimal route evaluation approaches. The performance results of the all approaches are given in Table 11 and Fig. 5. Figure 5 shows the unmatched performance of all nine approaches and Table 11 shows the total performance of all considered approaches. From results we observe that on the given WMN scenario up to 3.5 s timing constraints the AODV routing protocol outperforms all its competitors. But after 3.5 s all other approaches also started to perform. On the timing constraint of 4.0 s P3PGA produced minimum cost route 9 + 2 = 11 times, AODV 6 times, BBBC 1 + 2 = 3 times, Firefly 1 + 2 = 3 times, and GA produced minimum cost route 1 + 2 = 3 times only. With 5 s timing limit P3PGA generated minimum cost route 10 times, AODV 4 times, GA 2 times, BBO 1 time, and BBBC produced minimum cost route 3 times.

Table 11 Comparative performance of P3PGA on 500 node client WMNs

Fig. 5

Comparative unmatched best performance of 500 node client WMNs for different timing constraints

5.3 Comparative Performance of 1000 Node Client WMNs

Table 12 and Fig. 6 present the simulated performance for 1000 node client WMNs. From the performance we observe that DSR and ACO approaches failed to discover the route for the given timing constraint in any of the trial sets. Up to 2 s timing limits AODV also failed to discover any of the routes. As shown in Fig. 6, P3PGA outperforms other 8 approaches for the timing constraints of 0.5, 1.0, 1.5, 2.5, and 3.0 s. With timing constraint of 2.0 s P3PGA and BBBC gave the same best performance. Further, we also observed that after the 3.0 s timing constraint the performance of AODV improved considerably to the extent that it outperformed all other 8 approaches. Hence, for the given WMN scenarios AODV is unsuitable approach if the network size is 1000 node with allowable computing time less than 2 s. If timing constraint could be relaxed beyond 3 s, then the AODV gives the best performance.

Table 12 Comparative performance of P3PGA on 1000 node client WMNs

Fig. 6

Comparative performance of 1000 node client WMNs

5.4 Comparative Performance of 2000 Node Client WMNs

We simulated the performance of all the nine approaches on the timing constraints of 1.0, 1.5, 2.0, 2.5, 3.0, 3.5, 4.0, 4.5, 5.0, and 5.5 s. The performance results of all approaches are shown in Fig. 7 and Table 13. The results clearly indicate the supremacy of P3PGA approach over all other approaches for every timing constraint.

Fig. 7

Comparative unmatched best performance of 2000 node client WMNs

Table 13 Comparative performance of P3PGA on 2000 node client WMNs

5.5 Comparative Performance of 2500 Node Client WMNs

We also evaluated the performance of all nine approaches on 2500 node client WMNs. To test the performance of all approaches we considered 17 trial sets with each set consisting of 20 trials. Here we have considered more trial sets as compared to the previous network scenarios because the network is larger and here is the need to evaluate the performance of the network on larger timing constraints also. The simulation results of all approaches are shown in Table 14 and Fig. 8. From the results we observe that the P3PGA approach outperforms all other approaches on all the timing constraints. We also observed that AODV, DSR, and ACO approaches fail to discover the route in any of the trial set. Table 15 shows that out of 340 trials, P3PGA has given the best unmatched performance 188 times, BBBC 65 times, and GA produced the best performance 69 times.

Table 14 Comparative performance of P3PGA on 2500 node client WMNs

Fig. 8

Comparative performance of 2500 node client WMNs

Table 15 Overall comparative performance of P3PGA

5.6 Overall Performance Considering all Networks

In order to evaluate the performance of all 9 approaches, overall we conducted total of 1140 trials. The overall performance of the 9 approaches are given in Fig. 9 and Table 15. From the simulation results, we observe that out of total number of 1140 trials P3PGA provided the unmatched best optimal cost route 478 times, AODV 221 times, BBBC 176 times, GA 133 times, Firefly 41 times, BBO 3 times, and DSR produced optimal cost routes only 2 times. 86 times multiple approaches produced the same best performance. Also, the ACO and BAT approaches failed to produce the optimal cost route in any of the trial sets. Figure 9 shows that as the size of the WMN becomes 1000 node P3PGA algorithm gives best performance but the margin is small. As the WMN size increases to 2000 nodes and above, P3PGA gives the best performance with a very large performance lead over its counterparts.

Fig. 9

Comparative performance of all approaches

6 Conclusions

This chapter proposes a new nature inspired, P3PGA-based multi-population global optimization algorithm. The proposed algorithm extended the 3PGA approach by adding the parallel evolution behavior. We implemented the proposed algorithm in MATLAB, simulated its performance on 30 benchmark functions from CEC-2014, and compared its performance with 16 other algorithms. P3PGA gave the best unmatched performance for 12 functions out of the 30 benchmark functions. On two other functions the best performance of P3PGA was equaled by some of the other algorithms. Hence, overall out of the 30 functions of CEC-2014 test suite, P3PGA gave the best performance on 14 functions. The performance of P3PGA was followed by UMOEAS, which gave unmatched best performance on one function and equaled best performance on eight functions totaling nine functions with best performance. LSHADE algorithm followed on the third place.

This chapter also proposed a P3PGA-based new optimal cost or near shortest route evaluation approach for WMNs. The approach was compared with eight other approaches, namely AODV, DSR, BBBC, ACO, BBO, BAT, GA, and Firefly-based optimal cost route evaluation approaches. From the simulation results we conclude that the proposed approach is very suitable for large WMNs with sizes greater than 1000 nodes.

The authors further suggest that the proposed P3PGA algorithm can be used in other applications such as for rule base extraction from numerical data for the fuzzy logic-based systems and for identification of fuzzy and ANN models from the given training data set.

Appendix 1: Algorithm Performance Results

Table 6 CEC-2014 Benchmark performance of various algorithms

Table 6 (continued

Table 20 Table 6