This paper proposes a new multi-population-based social optimization technique called Parallel Social Group Optimization (PSGO). The algorithm is inspired by the learning behaviour of humans in different groups. In this algorithm, we consider the complete process of human interaction within the group and outside the group. We implement the proposed algorithm in MATLAB and tested it on 30 standard benchmark functions. For performance analysis purposes, we compare the PSGO algorithm with other recent 16 algorithms. The PSGO algorithm outperformed the other 16 algorithms on 4 standard benchmark functions. None of the other algorithms could match this performance. In addition, for functions f1,f2, f3,f4,f5, and f7of standard benchmark functions it produced the best performance but this performance was equalled by a few other algorithms also. Further, we propose a PSGO-based dynamic route evaluation approach for Wireless Mesh Networks (WMNs). We implemented the PSGO-based routing approach in MATLAB and compared it with 9 soft computing and hard computing-based approaches namely AODV, DSR, ACO, BBO, BAT, Firefly, BBBC, GA, and SGO. On over 1500 dynamic node network situations, the PSGO-based routing technique outscored all other 9 algorithms.
Research Article
Parallel Social Group Optimization (Psgo): Performance and Its Application to Routing in Wmn’s
https://doi.org/10.21203/rs.3.rs-1955795/v1
This work is licensed under a CC BY 4.0 License
Version 1
posted
You are reading this latest preprint version
PSGO
WMN
Soft Computing
Hard Computing
AODV
BBBC
GA
NIC is an interdisciplinary method that integrates technology and science with other disciplines like physics, chemistry, biology, evolutionary computation, mathematics, and engineering. Nature-inspired computing techniques consider nature as an element and use them for randomness and provide different solutions for different optimization problems in the real world. These approaches are beneficial in nature as they improve the convergence from local optima to global optima. The social group optimization (SGO) algorithm is a meta-heuristic approach that is inspired by an individual's group interactions in a group to tackle complicated issues. The fitness value of everyone is used to track their knowledge. The process includes two stages: the improving Phase and acquiring Phase. They enhance knowledge by connecting with the best person (best solution) in the improving Phase. In contrast, in the acquiring Phase, individuals connect with randomly selected people and the best person at the same time to acquire information. Related work in this area discusses many other human-inspired approaches like SELO (Social development and learning optimization)[1], TLBO (Teaching-Learning Based Optimization)[2], MSGO (Modified Social Group Optimization) [3], 3-PGA(3-Parent Genetic Algorithm)[4],and Group Counselling Optimization (GCO) [5].
This article proposes a new Parallel Social Group Optimization (PSGO) algorithm. PSGO is a multi-population-based algorithm. This algorithm is an extension of the Social Group Optimization algorithm. The major contribution of this paper is as below:
- Proposed PSGO algorithm and tested its performance on standard CEC benchmark functions.
- Proposed a minimal cost route evaluation approach to wireless mesh networks and compared its performance with 9 other routing approaches.
This paper is organized into 6 Sections. Section 1 of the paper presents the introduction of the paper. Section 2 purposes the PSGO algorithm. Section 3 presents the simulation and performance of PSGO algorithm on standard benchmark functions and compares its performance with other 16 algorithms. Section 4 proposes PSGO based minimal route cost evaluation approach. Section 5 presents the implementation and performance of the proposed approach for WMNs. The performance of the proposed approach is compared with the other 9 routing approaches. Section 6 concludes the paper.
Parallel Social group optimization considers a multi-population paradigm that helps to find optimal solutions. The proposed algorithm is the extension of the social group optimization (SGO) algorithm. This algorithm is based on the learning behaviour of individuals in the groups. (Fig. 1 Proposed Parallel Social Group Optimization Algorithm)shows the pictorial representation of the proposed work.
The parallel social group optimization algorithm is based upon the learning process of humans in groups. In this algorithm, we created different groups of humans. Humans can learn by interacting with the persons in the group and the expert outside the group. The suggested algorithm operates in four stages: the Self-Learning Phase, the Improving Phase, the Acquiring Phase, and the Combination Phase. The self-learning phase defines a phase where a person’s individual knowledge is calculated based on their own experience, the knowledge acquired from external sources like books, media, etc. This phase computes the information which is gained by an individual through their efforts. The improving Phase helps an individual to enhance the knowledge within the group. In the Acquiring Phase, the best person from Phase 1 is considered along with all the members of the group, and mutual interaction is done. Another important parameter is the self-improvement parameter which calculates the knowledge of an individual through their experience with life. Once the local best is calculated from each mentioned population, all these local bests are used as an input to evaluate a single global best among all of them, which will help enhance the knowledge of the entire population with the best possible results. All this process where the best among all is considered is called the combination phase. The pseudocode of the proposed work is shown in Table 1
|
PSGO algorithm |
|---|
|
Begin |
|
Generate GP Populations randomly. Each group should have N Individuals, and each individual should have G Genes. Evaluate each individual's fitness in every group and select g_best (group best) and global_best candidate solutions. |
|
For iter = 1 to max_number_of_iterations /*Self-Learning Phase starts*/ For i = 1 to GP For j = 1 to N |
|
New_Pop(i,j) = New_Pop(i,j) + random_number // random_number could be and small positive or negative random number End For Pop(i) = New_pop(i) End For /* Self-Learning Phase ends*/ |
|
Check bounds and violations and update the individuals if needed. Evaluate each individual's fitness in every group and update g_best (group best) and global_best candidate solutions if needed. |
|
/* Improving Phase starts*/ For i = 1 to GP For j = 1 to N |
|
New_Pop(i,j) = c.*pop(i,j) + rand(size(pop(i,j))).*(g_best- pop(i,j)); // here c is self-improvement parameter and it should be between 0 to 1 End For Pop(i) = New_pop(i) End For /* Improving Phase ends */ |
|
Check bounds and violations and update the individuals if needed. Evaluate each individual's fitness in every group and update g_best (group best) and global_best candidate solutions if needed. /* Acquiring Phase starts */ For i = 1 to GP For j = 1 to N Select a partner randomly from ith group Fc = Fitness of current individual in group. Fp = Fitness of partner If Fc < Fp New_Pop(i,j) = pop(i,j) + rand(size(pop(i,j))* (pop(i,j) - partner) + rand(size(pop(i,j)) * (g_best- pop(i,j)); Else New_Pop(i,j) = pop(i,j) - rand(size(pop(i,j))* (pop(i,j) - partner) + rand(size(pop(i,j)) * (g_best- pop(i,j)); End for End for /* Acquiring phase ends*/ Check bounds and violations and update the individuals if needed. Evaluate each individual's fitness in every group and update g_best (group best) and global_best candidate solutions if needed. |
|
Select a trainer randomly from all local bests. /* Combination Phase starts*/ For i = 1 to GP For j = 1 to N For k = 1 to Genes With the specific probability update kth gene of jth individual and ith population using following Pop(j,k) = Pop(j,k)/2 + trainer(k) /2 End For End For End For /* Combination Phase ends*/ Check bounds and violations and update the individuals if needed. Evaluate each individual's fitness in every group and update g_best (group best) and global_best candidate solutions if needed. End for End |
Table 2defines the symbols used in the pseudo code along with its description and the values considered for the implementation purpose.
|
Parameter Description |
Symbols |
Values |
|---|---|---|
|
Number of populations |
GP |
20 |
|
Number of dimensions of each population |
D |
10 |
|
Termination criteria (Self-improvement) |
C |
0.25 |
|
Genes value |
\({d}_{j}(j=1..3)\) |
0 thru 9 |
To understand the algorithm in a better way, we have considered a simple example for finding three digits numbers with the largest sum. The number of digits is between (0 to 9), so the highest three-digit number will be (9 9 9). The stepwise formation of this algorithm can be seen below:
Problem Statement
Find the largest sum of 3-digit numbers.
Solution
To solve the problem mentioned above, we need to get the largest sum using 3 digits for the set of real numbers. The following steps are considered for the required solution.
Step 1
We considered 4 different populations of 4 different persons with 3 randomized genetic values. A random population is generated in the 1st Iteration as discussed below
Iteration = 1
Generate population randomly
Population 1:\([ 1, 4, 5; 2, 2, 7; 3 ,5 , 1; 8, 1 , 6]\)
Population 2:\([ 3, 4, 7; 4, 8, 1; 6, 2, 3; 5, 3, 2 ]\)
Population 3:\([ 4, 7, 2 ; 6 , 9, 3 ; 3 , 5, 7; 6 , 2 , 1]\)
Population 4:\([ 8 , 2 , 1 ; 3 , 2 , 1 ; 4 , 8 , 9 ; 9 , 8, 7]\)
These populations can also be written as
$$Population 1=\left[\begin{array}{c}\begin{array}{ccc}1& 4& 5\\ 2& 2& 7\\ 3& 5& 1\\ 8& 1& 6\end{array}\end{array}\right]$$
$$Population 2=\left[\begin{array}{c}\begin{array}{ccc}3& 4& 7\\ 4& 8& 1\\ 6& 2& 3\\ 5& 3& 2\end{array}\end{array}\right]$$
$$Population 3=\left[\begin{array}{c}\begin{array}{ccc}4& 7& 2\\ 6& 9& 3\\ 3& 5& 7\\ 6& 2& 1\end{array}\end{array}\right]$$
$$Population 4=\left[\begin{array}{c}\begin{array}{ccc}8& 2& 1\\ 3& 2& 1\\ 4& 8& 9\\ 9& 8& 7\end{array}\end{array}\right]$$
Step 2
Select the local best with the highest fitness value from each Population. In Iteration 1, 4 random populations are generated. Now each gene value of every person will be summed up to find out the fitness value of the elite person in every Population. Here as it shows that in population 4, an individual with (9,8,7) genetic value results as the elite one
A simple demonstration of how the elite value is calculated for a single population can be seen in Table 3
|
Population No. |
Individual No. |
Individual |
Fitness no. |
|---|---|---|---|
|
1 |
1 |
\(1, 4, 5\) |
10 |
|
2 |
\(2, 2, 7\) |
11 |
|
|
3 |
\(3 ,5 , 1\) |
9 |
|
|
4 |
\(8, 1 , 6\) |
15 |
Moving on to the next step, a self-improvement parameter is considered which helps an individual to prove his /her knowledge by its own experience.
Step 3
It computes the Self-improvement parameter where an experience of a person is calculated using the following formula
$$Population = Curren{t}_{population} \pm rando{m}_{number}$$
Step 4
In this step, we construct a change matrix. It may be possible that the level of significance of an individual's genetic value is not satisfactory then in that case we can optimize the significant value by adding 1 unit and subtracting 1 unit randomly. Hence the following change matrix is imposed on every Population.
Change Matrix for population 1 =\([1, 1, -1; -1 , 1, -1; -1, -1, 1; 1, -1, -1]\)
Change Matrix for population 2 =\([-1 , -1 , 1; -1 , 1, -1; 1, 1, -1; 1, -1, -1]\)
Change Matrix for population 3=\([1, -1, -1 ; -1 , 1, -1 ; 1 , 1, -1 ;1, -1, -1]\)
Change Matrix for population 4 =\([-1 , -1 , 1 ; 1, -1, -1; 1, 1, -1; -1 , 1, 1]\)
It can also be written as shown below
$$Change matrix for Population 1 \left[\begin{array}{c}\begin{array}{ccc}1& 1& -1\\ -1& 1& -1\\ -1& -1& 1\\ 1& -1& 1\end{array}\end{array}\right]$$
Step 5
Once the change matrix is formulated, the current Population is added/subtracted with the help of the change matrix to develop the .
If the new Population which is generated is better than the existing one, then the new will be replaced with the exiting Population otherwise the existing group will be considered for further steps.
$$New Population = Population + Change Matrix$$
$$New Population 1=\left[\begin{array}{c}\begin{array}{ccc}1& 4& 5\\ 2& 2& 7\\ 3& 5& 1\\ 8& 1& 6\end{array}\end{array}\right]\pm \left[\begin{array}{c}\begin{array}{ccc}1& 1& -1\\ -1& 1& -1\\ -1& -1& 1\\ 1& -1& 1\end{array}\end{array}\right]$$
$$New Population 2=\left[\begin{array}{c}\begin{array}{ccc}3& 4& 7\\ 4& 8& 1\\ 6& 2& 3\\ 5& 3& 2\end{array}\end{array}\right]\pm \left[\begin{array}{c}\begin{array}{ccc}-1& -1& 1\\ -1& 1& -1\\ 1& 1& -1\\ 1& -1& -1\end{array}\end{array}\right]$$
$$New Population 3=\left[\begin{array}{c}\begin{array}{ccc}4& 7& 2\\ 6& 9& 3\\ 3& 5& 7\\ 6& 2& 1\end{array}\end{array}\right] \pm \left[\begin{array}{c}\begin{array}{ccc}1& -1& -1\\ -1& 1& -1\\ 1& 1& -1\\ 1& -1& -1\end{array}\end{array}\right]$$
$$New Population 4=\left[\begin{array}{c}\begin{array}{ccc}8& 2& 1\\ 3& 2& 1\\ 4& 8& 9\\ 9& 8& 7\end{array}\end{array}\right] \pm \left[\begin{array}{c}\begin{array}{ccc}-1& -1& 1\\ 1& -1& -1\\ 1& 1& -1\\ -1& 1& 1\end{array}\end{array}\right]$$
After the addition of the change matrix, the newly generated Population is as follows:
$$New Population 1= \left[2 , 5 , 4; 1 , 3, 6; 2 , 4, 2 ; 9, 0, 5\right]$$
$$New Population 2=[2 , 3, 8; 3, 9, 0; 7, 3, 2; 6, 2, 1]$$
$$New Population 3= [5, 6, 1; 5, 10, 2; 4, 6, 6 ; 7, 1, 0]$$
$$New Population 4= [ 7, 1, 2; 4, 1, 0; 5, 9, 8 ; 8, 9, 8]$$
Step 6 \(:\) To generate a whole new bunch of population the \(Population 1\) and\(New Population 1\) will be combined.
$$Population 1= [ 1, 4, 5; 2, 2, 7; 3 ,5 , 1; 8, 1 , 6; 2 , 5 , 4; 1 , 3, 6; 2 , 4, 2 ; 9, 0, 5]$$
$$Population 2= [ 3, 4, 7; 4, 8, 1; 6, 2, 3; 5, 3, 2 ; 2 , 3, 8; 3, 9, 0; 7, 3, 2; 6, 2, 1 ]$$
$$Population 3= [ 4, 7, 2 ; 6 , 9, 3 ; 3 , 5, 7; 6 , 2 , 1; 5, 6, 1; 5, 10, 2; 4, 6, 6 ; 7, 1, 0 ]$$
$$Population 4=[8 , 2 , 1 ; 3 , 2 , 1 ; 4 , 8 , 9 ; 9 , 8, 7; 7, 1, 2; 4, 1, 0; 5, 9, 8 ; 8, 9, 8]$$
Once the populations have been updated now, the stages of the algorithms will be implemented. The improving Phase is the initial step of calculating the best among a group of people. As the proposed algorithm is a multi-population algorithm, in this case, multiple groups will be performing this step and will identify one individual with a fitness value.
Step 7: Improving Phase
Using the self-improvement \(c\), old population \(X\), and the best fitness value population \({X}_{best}\),
$${X}_{new}=cX+r\left({X}_{best}-X\right) \left(Eq 1\right)$$
\(\) provides the update on the existing Population through the Improving Phase. Here self-improvement parameter is 0.1. Randomly generated number r ranges between (0,1).
$$Population 1: [ 1, 4, 5; 2, 2, 7; 3 ,5 , 1; 8, 1 , 6] \left(0.5\right)$$
$$Population 2: [ 3, 4, 7; 4, 8, 1; 6, 2, 3; 5, 3, 2 ]\left(0.3\right)$$
$$Population 3: [ 4, 7, 2 ; 6 , 9, 3 ; 3 , 5, 7; 6 , 2 , 1] \left(0.6\right)$$
Figure 2 shows the pictorial representation of the Improvising phase, where every person in the group (in black) will interact with the best person(in red) to enhance their knowledge.
We have considered Population 1 for this example and have implemented the above-mentioned equation as follows
\({X}_{new}(\) Population1\()=0.1*(\text{1,4},5)+0.5(7, -3 , 1); 0.1*(\text{2,2},7)+0.5(6,-\text{1,1}); 0.1*(\text{3,5},1)+0.5(5,-\text{4,5})\)
Similarly, for populations 2,3, and 4 same will be followed.
$${X}_{new}Population 2: [ 3, 4, 7; 4, 8, 1; 6, 2, 3; 5, 3, 2 ]$$
$${X}_{new}Population 3: [ 4, 7, 2 ; 6 , 9, 3 ; 3 , 5, 7; 6 , 2 , 1]$$
$${X}_{new}Population 4: [ 8 , 2 , 1 ; 3 , 2 , 1 ; 4 , 8 , 9 ; 9 , 8, 7]$$
Step 8
Now once the is generated, then comes Phase 2 i.e Acquiring phase(Fig. 3). In this every person in the group will talk to their peer, and the best person obtained from the Improving Phase. This process will help an individual to gain more knowledge. The below-mentioned formula will be used to calculate the interaction between the person and peer.
$${Person to partner or peer =X-X}_{p}$$
Once it is calculated, the Population generated from Improving stage will be added to \({X-X}_{p}\)for generating a new population which combines both Phase 1 and Phase 2.
The formula to implement the acquiring Phase is as follows:
$${X}_{new}=X+r1{(X-X}_{p} )+r2 \left({X}_{best}-X\right) ( Eq. 2)$$
$$Acquiring phase new Population 1= [ 1, 4, 5; 2, 2, 7; 3 ,5 , 1; 8, 1 , 6; 2 , 5 , 4; 1 , 3, 6; 2 , 4, 2 ; 9, 0, 5;$$
$$\text{3.6,0.4,1};3.2, 0.2, 0.7; \text{2.8,0.5,2.6} ]$$
$$Acquiring phase new Population 2= [ 3, 4, 7; 4, 8, 1; 6, 2, 3; 5, 3, 2 ; 2 , 3, 8; 3, 9, 0; 7, 3, 2;$$
$$6, 2, 1;\text{0.4,0.8,1.9}; \text{0.6,0.8,1.5}; \text{0.5,0.6,1.7} ]$$
$$Acquiring phase new Population 3= [ 4, 7, 2 ; 6 , 9, 3 ; 3 , 5, 7; 6 , 2 , 1; 5, 6, 1; 5, 10, 2; 4, 6, 6 ;$$
$$7, 1, 0;\text{1.6,1.9,0.8}; \text{2.1,2.9,0.7};\text{0.6,4.4,1.3} ]$$
$$Acquiring phase new Population 4=[8 , 2 , 1 ; 3 , 2 , 1 ; 4 , 8 , 9 ; 9 , 8, 7; 7, 1, 2; 4, 1, 0; 5, 9, 8 ; 8, 9, 8;\text{1,1.4,1.3};\text{1.5,1.4,1.3};\text{1.4,0.8,0.9}]$$
Step 9
Using the Eq. 2, every population has been updated in the acquiring phase. Hence local best is obtained using these 2 phases.
Step 10
The next step combines old and new population by adding new population generated from improving phase + acquiring phase new population. Once the new Population is generated then among those 12 individuals of every population select best 4 among them.
$$Population 1= [ 1, 4, 5; 2, 2, 7; 3 ,5 , 1; 8, 1 , 6; 2 , 5 , 4; 1 , 3, 6; 2 , 4, 2 ; 9, 0, 5;$$
$$\text{3.6,0.4,1};3.2, 0.2, 0.7; \text{2.8,0.5,2.6} ;\text{4,5},4.5; 4.5, 0.5, 10; \text{6.5,5.5,1.5}]$$
$$Population 2= [ 3, 4, 7; 4, 8, 1; 6, 2, 3; 5, 3, 2 ; 2 , 3, 8; 3, 9, 0; 7, 3, 2; 6, 2, 1;$$
$$\text{0.4,0.8,1.9}; \text{0.6,0.8,1.5}; \text{0.5,0.6,1.7};\text{3.4,9.8,2.2};\text{6.3,2.3,4.5};\text{5.3,1.8,3.8} ]$$
$$Population 3= [ 4, 7, 2 ; 6 , 9, 3 ; 3 , 5, 7; 6 , 2 , 1; 5, 6, 1; 5, 10, 2; 4, 6, 6 ; 7, 1, 0;$$
$$\text{1.6,1.9,0.8}; \text{2.1,2.9,0.7};\text{0.6,4.4,1.3};\text{4,11.2,3.2};\text{6,4.4,6.4};\text{6,6.2,2.2} ]$$
$$Population 4=[8 , 2 , 1 ; 3 , 2 , 1 ; 4 , 8 , 9 ; 9 , 8, 7; 7, 1, 2; 4, 1, 0; 5, 9, 8 ; 8, 9, 8;$$
$$\text{1,1.4,1.3};\text{1.5,1.4,1.3};\text{1.4,0.8,0.9};\text{9.2,3.2,2.2};\text{4,2},0.6;\text{4.2,9.2,10.6}]$$
Step 11
In this step, among the populations generated throughout all the steps, the best 4 individuals in each population with the best genetic values will be filtered out as shown below. This method defines that multiple populations are considered where all the 10 steps we have discussed help to generate local best among each population. Now among the local best, the global best person needs to be identified.
Select the top 4 in each population. The digits in bold show the best individuals with good genetic values.
$$Population 1= [ 1, 4, 5; 2, 2, 7; 3 ,5 , 1; 8, 1 , 6; 2 , 5 , 4; 1 , 3, 6; 2 , 4, 2 ; 9, 0, 5; \text{3.6,0},1;$$
$$3, 0, 0; \text{3,0},3 ;\text{4,5},5; 5, 0, 9; \text{7,6},2]$$
$$Population 2= [ 3, 4, 7; 4, 8, 1; 6, 2, 3; 5, 3, 2 ; 2 , 3, 8; 3, 9, 0; 7, 3, 2;$$
$$6, 2, 1;\text{0,1},2;\text{0,0},2; \text{1,1},1; \text{3,9},2;\text{6,2},5;\text{5,2},4]$$
$$Population 3= [ 4, 7, 2 ; 6 , 9, 3 ; 3 , 5, 7; 6 , 2 , 1; 5, 6, 1; 5, 9, 2; 4, 6, 6 ;$$
$$7, 1, 0; \text{2,2},1;\text{2,3},2;\text{1,4},1;\text{4,9},3;\text{6,4},6;\text{6,6},2]$$
$$Population 4=[8 , 2 , 1 ; 3 , 2 , 1 ; 4 , 8 , 9 ; 9 , 8, 7; 7, 1, 2; 4, 1, 0; 5, 9, 8 ; 8, 9, 8;$$
$$\text{1,1},1;\text{2,1},1;\text{1,1},1;\text{8,3},2;\text{4,2},1;\text{4,9},9]$$
The bold digits show that in each population there are 4 individuals with good genetic values as shown below. Among all these, the newly generated population (8,9,8) in Population 4 with the highest genetic value is 25 is declared as the Global best person.
$$Population 1=[\text{8,1},6; 9, 0, 5 ; 5, 0, 9 ; 7, 6, 2;]$$
$$Population 2=[3, 4, 7; 4, 8, 1 ; 2, 3, 8; 3, 9, 2]$$
$$Population 3=[6, 9, 3 ; 3, 5, 7; 4, 9, 3 ; 6, 4, 6 ]$$
$$Population 4=[ 9, 8, 7; 5, 9, 8, 8, 9, 8, 4, 9 , 9]$$
Using 4 different random populations of 4 individuals with 3 genes, the best person with the elite genetic value among the local populations is known as the Global best solution: [8 9 8]. Because it’s a parallel approach the convergence rate can be considered less with optimal route cost.
Figure 5 shows a tabular representation of all the major steps of PSGO in the 1st iteration with an output of all the populations in every stage.
Here we have round off the values ≥ and ≤ .05
The proposed approach is implemented on MATLAB with system configuration Intel®Core™i3-2328M [email protected] with 4.00GB RAM. The testing is done on CEC 2014 TEST Benchmark functions and compared with 16 other algorithms.
Table 4 shows the simulation results and performance analysis of the proposed PSGO approach and 16 other algorithms on the CEC-2014 test Benchmark functions. The 16 algorithms which were used for comparative analysis are [6][7] [8] [9][10] [11][12][13][14] [15] [16][17] [18][19][20]. The structure considered for testing all the algorithms on 30 functions is as follows: "25 sets of trial"," dimension considered 10," and for performance analysis, "Mean Square Error" (MSE) is used in every function. The mentioned approach was tested on 30 functions starting from (f1 to f30). The simulation results show that the proposed approach performed better in 4 functions. F19, f22, f23, and f27 are where PSGO's performance is declared as the winner compared to the other 16 algorithms. It gave an equal best performance with other algorithms for f1,f2, f3,f4,f5 and f7 functions. RMA-LSCh-CMA resulted best for 7 functions when compared with other algorithms (f3,f4,f5,f6,f11,f12 and f16).LSHADE produced effective results for 9 functions. PSGO showed the best results for 10 functions in total (f1,f2,f3,f4,f5,f7,f19,f22,f23 and f27), including individual performance and joint performance.
3.1 Simulation and Performance Discussions
The performance of the proposed PSGO algorithm is evaluated in MATLAB for 30 benchmark functions(See Table 5). The performance analysis of the proposed approach is compared with 16 other algorithms. The above table shows the comparative analysis of PSGO with other algorithms. This summarizes the performance of each algorithm in terms of the number of functions obtained by mean square error. The table consists of 5 columns. The first column states the list of algorithms that are compared with the proposed PSGO. Column 2 defines the count of functions where best performances are observed. Column 3 named “B” displays the number of functions with the best performance and equal results i.e., jointly winners. Column 4 “C” shows the total number of the best-performed functions. Based on columns A, B, and C, the ranking of each algorithm is obtained.
The rank column shows that PSGOs were declared the winner for 4 test functions. It was declared a joint winner in 6 functions and ranked in the first position. LSHADE and UMOEAS are ranked in 2nd position. The simulation results show that LSHADE performed best for 5 test functions with unique results whereas UMOEAS’s analysis is best for only 1 test function. The count where these two algorithms were declared as joint winners are 4 and 8. The total count of their performance is 9 and are ranked at 2nd position as mentioned in the
|
Algorithm |
A |
B |
C |
Rank |
|---|---|---|---|---|
|
PSGO |
4 |
6 |
10 |
1 |
|
LSHADE |
5 |
4 |
9 |
2 |
|
UMOEAS |
1 |
8 |
9 |
2 |
|
RMA-LSCh-CMA |
3 |
4 |
7 |
3 |
|
DE b6e6rlwithrestart |
2 |
5 |
7 |
3 |
|
SOO + BOBYQA |
0 |
5 |
5 |
4 |
|
MVMO |
1 |
4 |
5 |
4 |
|
GaAPADE |
1 |
4 |
5 |
5 |
|
SOO |
0 |
4 |
4 |
6 |
|
CMLSP |
1 |
3 |
4 |
6 |
|
RSDE |
0 |
3 |
3 |
7 |
|
FCDE |
0 |
3 |
3 |
7 |
|
FERDE |
0 |
2 |
2 |
8 |
|
OptBees |
0 |
1 |
1 |
9 |
|
POBL _ADE |
1 |
0 |
1 |
9 |
|
FWA-DM |
0 |
1 |
1 |
9 |
A = defines the number of test functions where the algorithm’s best performance is observed
B = defines the number of test functions where the algorithm’s best performance is jointly equal to other algorithms
C = defines the total number of test functions with the best performance.
The below table shows the number of functions where PSGO gave the best performance. For the test functions like f19,f22,f23, and f27, Parallel Social Group Optimization is declared a winner. For other 9 test functions like f1,f2,f3,f4,f5,and f7 the proposed approached is considered as a joint winner. Thus, we find that the proposed approach gave the best performance for the overall 9 functions out of 30.
|
List of functions where PSGO was declared as a winner |
f19, f22, f23 and f27 |
|---|---|
|
List of functions where PSGO was declared as the mutual winner |
f1, f2, f3,f4,f5 and f7 |
In this section, we propose a new Parallel SGO-based technique for optimal route evaluation in WMNs. Routing in a wireless mesh network is a challenging issue. A path is established between the source and destination node for communication. The work proposed can be utilized for finding optimized route costs. PSGO can be implemented in any proactive routing approach. The routing process works in two phases: Route discovery and data transmission. In the case of route discovery, the optimal path is discovered among the available routes. Mesh networks should identify optimized routes in the given time duration or constraints. Once the first phase is completed, the next phase starts. Transmission of the data processing continues up till a given time constraint or prior to any variation in the structure of the network is identified for the chosen path. The mentioned phases behave in a looping form i.e., repeated. Due to this repetition, each time a new path is discovered. Computing the minimal route cost path with dynamic nature and for given time constraints becomes a challenging issue for routing techniques. To provide the solution to these complexities, there is a need for soft computing approaches that provides optimized minimal route cost within the given time constraints. In most of the cases, the shortest path discovered earlier is not valid to compute, and hence, these exact paths should be replaced with the near shortest path. This will result in discovering effective paths with minimal cost under given time constraints and a dynamic environment.
To calculate the minimal cost path for appropriate route selection in wireless mesh networks, a wide variety of routing metrics can be considered. It evaluates each path's cost and helps select or predict the best path among all. The information is saved in the routing table for further use. These metrics help improve the latency rate, cost, bandwidth, and reliability, which helps upgrade the quality of communication. The proposed Routing Metrics [34][35] implemented in WMN are divided as follows.
-
Hop count (related to the no. of hops in a network)
-
Link Quality (considers the connection quality in WMN)
-
Load-Dependent (determines the load rate dependent on nodes and network)
-
Multi-channel Metrics
The Hop count metric, whose functionality is to determine the no. of hops in a network, is considered one of the historical metrics used in Routing Information Protocol during the establishment of the internet.
|
Metrics |
|
|---|---|
|
Link- Quality |
ETX (Expected Transmission Count) [12] |
|
ETT (Expected Transmission Time) [13] |
|
|
ELP (expected Link Performance) |
|
|
RTT (Per-Hop Round Trip Time) |
|
|
PPD (Per-Hop Packet Pair Delay) |
|
|
ML (Minimum Loss) [14] |
|
|
Multi-Channel |
WCETT (Weighted Cumulative ETT) |
|
MIC (Metric of Interference and Channel Switching) [15] |
|
|
EETT (Exclusive Expected Transmission Time) [18] |
|
|
iAWARE[17] |
|
|
mETX(Modified ETX) [16] |
|
|
ENT (Effective Number of Transmission) [16] |
|
|
Load- Dependent |
DBEXT (Distribution-based Expected Transmission Count) |
|
BATD (Bottleneck Aware Routing Metrics) |
Our work calculates the cost of a path using the Fuzzy based (ILC)technique. The architecture of ILC is shown in Figure
The pseudo-code of the PSGO-based routing approach can be seen as below
To examine the performance of PSGO based approach to calculate the minimal route cost path in the wireless mesh network, the implementation of the proposed work is carried out in MATLAB. The implementation and comparative analysis are done among 9 existing approaches. We ran simulations on different dynamic node scenarios i.e., 500, 1000, 2000,3000, and 4000 client WMN. We omitted the results from WMNs having up to 1,000 nodes for simplicity, as the suggested PSGO approach performs better on larger networks. Table 7 shows the architectural design of several Client WMN node scenarios.
Table 7: Client Wireless Mesh Network node scenarios
5.1 Comparative performance of 2000 node client WMNs
The proposed Parallel Social Group Optimization approach's performance is compared with 7 existing approaches (see Table 8 and Fig. 6). We have considered 2.0, 2.2,2.4,2.6,2.8,3.0,3.2,3.4,3.6, and 3.8 seconds timing constrain for 2000 network node scenario. For testing purposes, 20×20 sets of trials are conducted. For given trials, the results shown by PSGO based routing approach outperformed ACO, DSR, AODV, BAT, BBO, GA, BBBC, SGO, and FA 89 times out of 200 trials. SGO on the other hand produced results 48 times in total. Firefly generated optimal routes 9 times excluding 7 times similar routes.BAT produced 28 times optimized routes including the equal route for some time constraints. BBO discovered the route 4 times in total for (2.0 and 2.2) time constraints. For other timelines, it failed to discover any route. Here "A = 1, B = 2, C = 3” defines that similar route cost was generated by the other approaches. PSGO came out as a prevailing method with the highest path discovery and minimal path value within the entire evaluation The result obtained shows that the novel approach gave better results than the existing approaches and hence is successful in finding an optimized route cost path.
|
Performance of 2000 Nodes Client Wireless Mesh Network |
||||||||||
|---|---|---|---|---|---|---|---|---|---|---|
|
Time Constraints |
||||||||||
|
Algorithm |
2 |
2.2 |
2.4 |
2.6 |
2.8 |
3 |
3.2 |
3.4 |
3.6 |
3.8 |
|
AODV |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
|
ACO |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
|
DSR |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
|
BBO |
1 + A |
B |
- |
- |
- |
- |
- |
- |
- |
- |
|
BBBC |
A |
2 + B |
3 |
- |
1 |
1 + A |
- |
- |
- |
- |
|
FA |
1 |
2 |
2 |
1 + B |
1 |
A |
1 |
C |
1 |
A |
|
GA |
2 |
1 + B |
1 |
3 + B |
2 |
1 + A |
3 |
C |
1 |
A |
|
BAT |
3 |
1 |
3 |
2 + B |
3 |
3 |
2 |
1 + C |
3 |
1 + A |
|
SGO |
4 |
4 |
5 |
4 |
4 |
5 |
5 |
6 |
4 |
7 |
|
PSGO |
8 |
8 |
6 |
8 |
9 |
9 |
9 |
10 |
11 |
11 |
A = 1,B = 2,C = 3 means equal optimal routes discovered
“---” defines failed to discover any path
5.2 Comparative performance of 3000 node client WMN
For the time constraints, 4.0,4.5,5.0,5.5,6.0,6.5,7.0,7.5,8.0 and 8.5 in 3000 node scenarios, the performance of Parallel Social Group Optimization can be seen 94 times better than other 9 approaches. SGO, on the other hand, is placed in the second position by generating the optimal route 43 times. Firefly was able to figure out the optimal route cost path 17 times in total within given units of time. ACO, AODV, and DSR failed to generate a minimal route cost path in most of the time constraints. GA generated optimal routes 22 times followed by BAT (21times). These approaches were successful in route discovery but produced similar results in a few of the time constraints. The overall graphical representation shows that PSGO successfully generated a minimal route cost path among the other 9 existing approaches (see Fig. 7 and Table 9).
|
Performance of 3000 Nodes Client Wireless Mesh Network |
|||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
|
Time Constraints |
|||||||||||
|
Algorithm |
4 |
4.5 |
5 |
5.5 |
6 |
6.5 |
7 |
7.5 |
8 |
8.5 |
|
|
ACO |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
|
|
AODV |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
|
|
BAT |
3 |
2 |
2 |
3 |
1 |
1 + B |
2 |
1 |
2 |
B |
|
|
BBBC |
A |
1 + A |
2 |
2 + A |
- |
1 |
C |
1 + A |
- |
- |
|
|
BBO |
A |
A |
1 |
- |
- |
- |
- |
- |
- |
- |
|
|
DSR |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
|
|
FA |
1 |
2 |
1 |
A |
2 |
B |
2 + C |
2 |
1 |
- |
|
|
GA |
4 |
1 |
1 |
1 + A |
2 |
1 |
1 + C |
2 + A |
2 |
1 + B |
|
|
PSGO |
7 |
8 |
8 |
9 |
9 |
11 |
9 |
11 |
10 |
12 |
|
|
SGO |
4 |
5 |
5 |
4 |
6 |
4 |
3 |
2 |
5 |
5 |
|
A = 1,B = 2,C = 3 means equal optimal routes discovered
“---” defines failed to discover any path
5.3 Comparative performance of 4000 node client WMN
The CWMNs (Client Wireless Mesh Network) for 4000 nodes are represented graphically in Table 10and Fig. 8along with 10 techniques under the provided time restrictions of 5.5, 6.0, 6.5, 7.0, 8.0, 8.5, 9.0, 9.5, and 10.0 seconds. PSGO beat ACO, DSR, AODV, BAT, BBO, GA, BBBC, SGO, and Firefly during deployment and results analysis. The fact that ACO, DSR, and AODV were unable to determine the path because the number of nodes increased suggests that those three techniques are ineffective for larger networks. Over the course of 200 trials, PSGO surpasses SGO 111 times, Firefly 16 times when equal paths are included, BAT 19 times, and BBO 3 times when the same route discovery, "B = 2," is excluded. In the allotted time, the best routes were developed 18 times by GA and 12 times by BBBC. It demonstrates how PSGO's efficiency increases as it is applied to a wider network with higher time limitations, producing the ideal shortest path.
|
Performance of 4000 Nodes Client Wireless Mesh Network |
||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
Time Constraints |
||||||||||||
|
Algorithm |
5 |
5.5 |
6 |
6.5 |
7 |
7.5 |
8 |
8.5 |
9 |
9.5 |
10 |
|
|
ACO |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
|
|
AODV |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
|
|
BAT |
2 |
2 |
2 |
2 |
A |
1 |
2 |
1 |
2 |
1 |
1 + A |
|
|
BBBC |
A |
1 |
1 |
2 |
1 |
C |
1 |
- |
A |
1 |
- |
|
|
BBO |
1 |
2 |
B |
- |
- |
- |
- |
- |
- |
- |
- |
|
|
DSR |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
- |
|
|
FA |
1 + A |
1 |
1 + B |
1 |
2 + A |
1 |
1 |
- |
1 + A |
2 |
- |
|
|
GA |
1 |
1 |
1 |
1 |
1 + A |
2 + C |
2 |
2 |
A |
1 |
A |
|
|
PSGO |
10 |
9 |
8 |
10 |
13 |
10 |
9 |
11 |
9 |
10 |
12 |
|
|
SGO |
4 |
4 |
5 |
4 |
2 |
3 |
5 |
6 |
7 |
5 |
6 |
|
A = 1,B = 2,C = 3 means equal optimal routes discovered
“---” defines failed to discover any path
This paper proposes a novel computation-based technique that is motivated by nature. The method that is being suggested is called Parallel Social Group Optimization (PSGO). The social group optimization method is expanded in PSGO. The proposed algorithm operates across multiple populations. The self-learning phase, improving phase, acquiring phase, and combining phase are the four phases that the algorithm goes through. For the simulation purpose we applied the proposed work in MATLAB and tested it on 30 benchmark functions. The PSGO algorithm's performance was compared to that of 16 current algorithms. On 10 benchmark functions, the suggested algorithm outperforms another existing algorithm, according to the compared results. Additionally, we developed a dynamic shortest route evaluation method for WMNs based on PSGO. On various dynamic network node contexts, the suggested technique was assessed to 9 alternative routing approaches. We evaluated how well the suggested technique performed in comparison to the ACO, DSR, AODV, BAT, BBO, Firefly, GA, BOA, and SGO approaches. From the results, we observed that the PSGO algorithm is more suitable as compared to other approaches on the networks consisting of more than 1500 dynamic node scenarios.
- M. Kumar, A. J. Kulkarni, and S. C. Satapathy, “Socio evolution & learning optimization algorithm: A socio-inspired optimization methodology,” Futur. Gener. Comput. Syst., vol. 81, pp. 252–272, 2018, doi: 10.1016/j.future.2017.10.052.
- W. Li, Y. Fan, and Q. Xu, “Teaching-Learning-Based Optimization Enhanced with Multiobjective Sorting Based and Cooperative Learning,” IEEE Access, vol. 8, pp. 65923–65937, 2020, doi: 10.1109/ACCESS.2020.2984272.
- A. Naik, S. C. Satapathy, and A. Abraham, “Modified Social Group Optimization—a meta-heuristic algorithm to solve short-term hydrothermal scheduling,” Appl. Soft Comput. J., 2020, doi: 10.1016/j.asoc.2020.106524.
- A. Kalra, S. Kumar, and S. S. Walia, “ANN system identification for rapid battery charger using parallel 3 parent genetic algorithm,” Int. J. Innov. Technol. Explor. Eng., 2019, doi: 10.35940/ijitee.I1079.0789S19.
- M. A. Eita and M. M. Fahmy, “Group counseling optimization,” Appl. Soft Comput. J., vol. 22, pp. 585–604, 2014, doi: 10.1016/j.asoc.2014.03.043.
- S. M. Elsayed, R. A. Sarker, and D. L. Essam, “United multi-operator evolutionary algorithms,” 2014, doi: 10.1109/CEC.2014.6900237.
- F. Zhao, L. Zhao, L. Wang, and H. Song, “A collaborative LSHADE algorithm with comprehensive learning mechanism,” Appl. Soft Comput. J., 2020, doi: 10.1016/j.asoc.2020.106609.
- Z. Zeng, M. Zhang, Z. Hong, H. Zhang, and H. Zhu, “Enhancing differential evolution with a target vector replacement strategy,” Comput. Stand. Interfaces, 2022, doi: 10.1016/j.csi.2022.103631.
- B. Y. Qu, J. J. Liang, J. M. Xiao, and Z. G. Shang, “Memetic differential evolution based on fitness Euclidean-distance ratio,” 2014, doi: 10.1109/CEC.2014.6900476.
- Z. Hu, Y. Bao, and T. Xiong, “Partial opposition-based adaptive differential evolution algorithms: Evaluation on the CEC 2014 benchmark set for real-parameter optimization,” 2014, doi: 10.1109/CEC.2014.6900489.
- F. S. Rahman, Israjuddin, N. Hariyanto, and C. W. Liu, “Swarm-based mean-variance mapping optimization for optimal placement of energy storage with synthetic inertia control on a low inertia power grid,” IET Gener. Transm. Distrib., 2021, doi: 10.1049/gtd2.12196.
- D. Molina, B. Lacroix, and F. Herrera, “Influence of regions on the memetic algorithm for the CEC’2014 Special Session on Real-Parameter Single Objective Optimisation,” 2014, doi: 10.1109/CEC.2014.6900536.
- R. Solgi and H. A. Loáiciga, “Bee-inspired metaheuristics for global optimization: a performance comparison,” Artif. Intell. Rev., 2021, doi: 10.1007/s10462-021-10015-1.
- M. Valko, A. Carpentier, and R. Munos, “Stochastic simultaneous optimistic optimization,” 2013.
- G. H. Negri, M. S. M. Cavalca, J. de Oliveira, C. J. F. Araújo, and L. A. Celiberto, “Evaluation of Nonlinear Model-Based Predictive Control Approaches Using Derivative-Free Optimization and FCC Neural Networks,” J. Control. Autom. Electr. Syst., 2017, doi: 10.1007/s40313-017-0327-x.
- C. Yu, J. Li, and Y. Tan, “Improve enhanced fireworks algorithm with differential mutation,” 2014, doi: 10.1109/SMC.2014.6973918.
- L. Chen, Z. Zheng, H. L. Liu, and S. Xie, “An evolutionary algorithm based on Covariance Matrix Leaning and Searching Preference for solving CEC 2014 benchmark problems,” 2014, doi: 10.1109/CEC.2014.6900594.
- D. Xie, L. Ding, X. Du, Y. Hu, and S. Wang, “Self-adaptive pseudo-parallel differential evolution algorithm,” J. Comput. Inf. Syst., 2012.
- K. Deb, Y. D. Dhebar, and N. V. R. Pavan, “Non-uniform mapping in binary-coded genetic algorithms,” 2013, doi: 10.1007/978-81-322-1038-2_12.
- R. Poláková, J. Tvrdik, and P. Bujok, “Controlled restart in differential evolution applied to CEC2014 benchmark functions,” 2014, doi: 10.1109/CEC.2014.6900632.
Table 4 is available in the Supplementary Files section.
No competing interests reported.
- Table4.png
Table 4: Comparative analysis of proposed PSGO algorithm with 16 other algorithms on CEC-2014 Benchmark function
