Simplified Phasmatodea population evolution algorithm for optimization

Suppose there are Np solutions in the n-dimensional space, and each solution is represented by x, and x is a point in the n-dimensional space, that is, \(x=[x_1,x_2,\ldots ,x_n]\). We regard a solution x as a stick insect population, assuming that it has certain autonomous decision-making ability. Each population has two attributes: population quantity and growth rate, \(p_i (1 \le i \le Np)\) represents the quantity of the i-th population (solution), and \(a_i\) means the growth rate of the i-th population.

First, randomly generate Np populations (solutions) x, and the population quantity of each population x is calculated byFor later use, the population quantity \(p_i\) of the i-th population is initialized to a decimal in Eq. (4). In addition, the growth rate a of each population is set to a fixed value of 1.1, which means that all populations have a good survival state in the initial situation, and then as the environment changes (the population position x changes), the quantity of populations will change.

Based on the introduction in “Inspiration”, for population x, its evolution process is more similar to the dominant population with similar living environment and closer distance, and it is not necessarily able to achieve convergent evolution to the global optimal population. This is not only due to the barrier of the geographical environment, but also because the characteristics of the global optimal population cannot make the population x find a better position in the current area.

Therefore, this article selects k historical optimal solutions to guide the movement of the surrounding solutions, stored in Ho, \(Ho = [x_{h1},\ldots ,x_{hi},\ldots , x_{hk}]\). Among them, \(x_{hi}\) is the i-th optimal solution that has appeared, \(x_{h1}\) is the optimal solution of all the solutions that have appeared, and \(x_{h2}\) is the optimal solution that has appeared only after \(x_{h1}\). If a total of Np solutions are generated, then the number of k isHo uses the Np solutions generated by the initialization process to select k optimal solutions, and its fitness value is stored in the corresponding array.

Ho is used to store the best first k solutions in the past search process, and the judgment of the quality of the solution is obtained by calculating the fitness value. Ho is used to store the nearest optimal solution to guide the movement of other solutions around.

After the population is initialized, the population position needs to be updated. After the update of the population position \(x^t\) at time t, it will move to a new position \(x^t+1\) and in a new environment, this position change is represented by the evolution trend ev. The position update formula isFor Eq. (6), ev is the evolutionary trend of stick insect populations. After the population position changes, it is necessary to re-evaluate all populations, update the global optimal solution gbest and k optimal solutions Ho.

The update of the population trend mainly includes three parts. The first two parts choose different ways to update according to the comparison of the quality before and after the trend update. The third part uses the population competition model to update. The first two parts represent the choice of the autonomous decision-making strategy of the population, there are two kinds, and the third part represents the mutual influence between the population.

The first is the update of the first two parts, which mainly use the characteristics of population growth model, convergent evolution and path dependence. After the population position is updated, the updated population is evaluated. If it is better than before, then the first part of the population trend update is performed, otherwise the second part of the population trend update method is performed.

The first part first updates the population quantity, and the update equation isAfter using Eq. (7) to update p, the population trend ev needs to be updated. The update method mainly contains three parts.

The first is the convergence to the nearest optimal, and secondly, because the previous evolutionary trend \(ev^t\) has obtained better results, then the next update is more likely to continue the previous evolutionary trend, which is called path dependence. Path dependence is similar to the greedy algorithm, which seeks the next position by continuing the previous movement trend. The underlying assumption is that the environment changes monotonously in a certain direction. Finally, there are mutations within the population. Therefore, the update equation of population trend is as follows:For Eq. (8), A represents the degree of approach to the nearest optimal, and the calculation formula isFor Eq. (9), \(s(Ho,x^t)\) is used to find the historical optimal solution that is closest to \(x^t\) in Ho, c is the coefficient of the influence degree of the nearest optimal solution on the current population, usually less than 1, which is a fixed value of 0.2 in this article. m represents the mutation of the population in some dimensions, first randomly select w dimension \((w \le n)\), then use the standard normal distribution to generate a random number. Finally, an n-dimensional mutation vector m is formed by \(m=m (Ub-Lb) \times 0.2\), Lb is the lower limit and Ub is the upper limit of n-dimensional space, \(Lb = [lb_1,\ldots ,lb_n]\), \(Ub = [ub_1,\ldots ,ub_n]\).

The second part is that the population position does not obtain a better value after the previous update, then the population will no longer maintain the original trend, but tend to the nearest optimal solution, and at the same time produce unpredictable disturbances. However, before this, the population has a certain probability to maintain the relatively poor situation after the update, so as to have the opportunity to jump out of the current area. In the process, the population size will change according to Eq. (7).

Based on the above description, the probability that the population accepts a poor solution is set to \(p_i\), that is, the quantity of current population. And the population trend update formula in the second part isFor Eq. (10), rand represents an n-dimensional random vector generated using a uniform distribution, and each dimension is between 0 and 1, and B represents an n-dimensional random vector generated using a standard normal distribution. st is initially set to \((Ub-Lb) \times 0.1\), and with each iteration of the algorithm, st is updated to \(st=st \times 0.99\).

The third part is the impact of the competition between populations on the evolution trend of the population. The population competition model refers to Eq. (3), and a simple modification is made here. The revised formula isWhen the population \(x_i\) is competing with \(x_j\), the population quantity of \(x_i\) is calculated using Eq. (11). Compared to Eq. (3), both \(n_1\) and \(n_2\) are 1, and \(s_1\) is calculated as the ratio of the fitness values between the \(x_i\) and \(x_j\).

Where \(x_i\) is the current population, \(x_j\) is randomly selected from other \(Np-1\) populations, and then the distance between the two populations needs to be judged and compared with a given threshold G. The calculation formula for G isFor Eq. (12), \(Max\_gen\) means the number of iterations, and t represents the current number of iterations. The threshold G will become smaller and smaller as the number of iterations increases.

If the distance between the current population \(x_i\) and other randomly selected population \(x_j\) is less than the threshold G, then it is considered that the two populations have competed. Competition will have an impact on the evolution trend of the current population \(x_i\), which is described by the following formulaIn addition, when the population is too small or the population growth rate exceeds the normal range, the solution needs to be eliminated, and a new population is generated to replace, indicating that the current stick insect population disappears due to poor adaptability to the environment.

Based on the above statement, the pseudo-code of the PPE is shown in Algorithm 1.

In Algorithm 1, rd means a random number generated using a uniform distribution, and the range is 0–1. The dist function is used to calculate the Euclidean distance between two n-dimensional vectors. Algorithm code is exposed on the website (https://​github.​com/​Spacewe-outlook/​PPE).

Based on the previous introduction, this section tests the performance of the proposed PPE. This article uses benchmark functions to test the performance of the PPE and analyzes the performance of the PPE algorithm in different dimensions.

There are many test functions for related algorithms, but there are some common test suites in the CEC competition. This paper uses CEC2014 [24] benchmark suites for testing. All the benchmark functions include 3 unimodal functions (F1–F3), 13 simple multimodal functions (F4–F16), 6 mixed functions (F17–F22) and 8 composition functions (F23–F30).

To show the performance of the proposed PPE algorithm more objectively and truthfully, the more classic PSO [20] and GA [15] algorithms are selected in the manuscript, and then several other algorithms proposed in recent years are selected, including the GSA algorithm in 2009 [40] and the GWO algorithm in 2014 [29], Social Learning Particle Swarm Optimization (SLPSO) algorithm in 2015 [7], BOA [1] and ASO [53] algorithms in 2019. The parameter settings of related algorithms are shown in Table 1.

Table 1 shows the parameter settings of different algorithms and the number of solutions Np generated in each iteration.

After determining the algorithm to be compared with and the parameters of the corresponding algorithm, for a fairer comparison, it is also necessary to ensure that different algorithms perform the same function evaluation times. Therefore, the function evaluation times of all algorithms in this article are 40,000. The dimension is 30, each different algorithm is run 30 times on different functions and the average value is recorded. The overall performance of each different algorithm compared with the PPE was measured at a significant level \(\alpha \) = 0.05 under the Wilcoxon’s sign rank test. The results are shown in Table 4.

Table 2 is the test results of the proposed PPE and other algorithms on 30 benchmark functions. The symbol \((<)\) means that the algorithm does not perform as well as the PPE on the current benchmark function. And the symbol \((=)\) means that the two algorithms perform similarly on the current benchmark function. And the symbol \((>)\) means that the PPE performs poorly. In the last row of the table, the comparison results on all functions are summarized.

Shown in Table 4 are the Wilcoxon’s sign rank test results of each algorithm compared with the PPE algorithm at a significant level of 0.05. The symbol \((+)\) indicates that the performance of the algorithm under the current benchmark function is significantly worse than that of the PPE algorithm, the symbol \((-)\) indicates that the performance of the current algorithm is stronger than the PPE algorithm, and the symbol \((\approx )\) indicates that there is no significant difference between the performance of the current algorithm and the PPE algorithm.

For Table 2, the overall performance of the PPE on the 30 functions of CEC2014 is better than SLPSO, GA, SA, BOA, GSA, GWO algorithms, and similar to the overall performance of PSO and ASO algorithms. Compared with SA algorithm, the performance of PPE on 25 benchmark functions is better than SA algorithm. Compared with the PSO, the PPE only has better performance on 16 benchmark functions than the PSO, and cannot achieve an overwhelming advantage. At the same time, the performance of the PPE is better than that of the ASO on only 15 benchmark functions. Due to the randomness of the algorithm test, the PPE cannot achieve an overwhelming advantage.

To compare the performance of different algorithms on different types of benchmark functions more clearly, this paper sorts out the data in Table 2, finds out which algorithm obtains the optimal solution for each benchmark function, and summarizes according to the type of benchmark function. The results are shown in Table 3.

Table 3 shows and compares the performance of the algorithm on different types of benchmark functions.

Table 3 compares how many functions the current algorithm has achieved the best results in each type of function compared to all other algorithms.

In Table 3, the PPE has achieved the best solution among all algorithms on seven functions, and at the same time, stronger than all other algorithms. The BOA algorithm performs well on the composition function, which is stronger than other algorithms, but the effect is worse than other algorithms on other types of functions.

For meta-heuristic algorithms, it is not only necessary to compare the final results of different algorithms, but also to consider the convergence of the algorithm. Algorithms with different convergence speeds may eventually obtain similar results, so this article shows the convergence of the proposed PPE algorithm, as shown in Figs. 1 and 2.

Due to space limitations, only partial results are shown here. The type of the selected functions are different, the performance of the algorithms are also different, and all the test results are displayed on the website (https://​github.​com/​Spacewe-outlook/​PPE).

In Figs. 1 and 2, the horizontal axis is the number of function evaluations. To show the difference between different curves more clearly, the vertical axis is \(Log(f - f*)\). f represents the final result obtained by the algorithm on a benchmark function. \(f*\) represents the minimum value of the current benchmark function.

In Fig. 1, the final results of the PPE algorithm on the benchmark functions F1 and F3 are better than other algorithms, but in the early stage of algorithm execution, the PPE algorithm’s convergence speed is slower than other algorithms. The final results of the PPE algorithm on the benchmark functions F5 and F10 are worse than other algorithms, but in the early stage of the algorithm execution, the convergence speed of the algorithm is better than that of the PSO, GWO, and GSA algorithms.

According to Fig. 2, the proposed PPE algorithm has continuous convergence ability on the benchmark functions F17 and F20. In the later stage of the algorithm execution, the proposed PPE algorithm is not easy to fall into a local optimum compared to other algorithms, but the convergence speed is slower. The PPE algorithm has better performance on the benchmark function F21, and the final result is slightly better than all other algorithms, but the performance on the benchmark function F30 is more general.

Compared with other algorithms, the PPE algorithm has a downward trend within the given evaluation times. Compared with other algorithms, most of them no longer continue to converge, and the convergence curve tends to be stable in the later stage. It can be seen that it cannot find a better result and falls into a local optimum.

Since the number of the nearest optimal solutions in the PPE algorithm is calculated by Eq. (5), when Np is equal to 20, k is 3.

In the case of keeping Np equal to 20, this paper tests whether the number of the nearest optimal solutions will affect the convergence speed of the algorithm and how it will affect. This article selected several different results, and the test results are shown in Fig. 3.

It can be seen from Fig. 3 that when k is different, the convergence curve of the PPE algorithm is also different. For the benchmark function F2, when k is smaller, the algorithm converges faster and the result is the best. As k increases, the performance of the algorithm keeps getting worse. For the benchmark functions F6 and F14, the smaller the k, the faster the algorithm converges, but the final results of different k are closer. But for the benchmark function F19, the smaller the k, the faster the algorithm converges, but the final result is not as good as when k is larger. It can be seen that when k is relatively small, it is helpful for the rapid convergence of the algorithm, but the diversity of the solution cannot be fully guaranteed, and it is still possible to fall into a local optimum.

Since the above test mainly uses a benchmark function with a dimension of 30 for testing, in practical applications, the dimension of the optimization problem is not necessarily 30. Therefore, to show the performance of the PPE algorithm more comprehensively, it is necessary to display and analyze the performance of the algorithm in different dimensions. The comparison results are shown in Figs. 4 and 5.

According to Fig. 4, the performance of the PPE algorithm on the 10-, 30-, 50- and 100-dimensional benchmark function F1 is better than other algorithms. On the F3, the PPE algorithm can obtain better results when the dimension is relatively low, but when the dimension is 100, the algorithm performance is worse than the GA and ASO algorithms. The performance of the algorithm PPE on the benchmark functions F6 and F7 is worse than the ASO and PSO algorithms.

According to Fig. 5, the PPE algorithm benchmark functions F14, F17, F18, and F29 have achieved good results, but they do not have advantages in every dimension. On the benchmark function F14, the PPE algorithm has a poor effect when the dimension is 10. But the effect is better when the dimension becomes higher. The PPE algorithm has certain advantages in different dimensions on the benchmark function F29, but it is worse than the BOA algorithm.

To show the internal changes of the PPE algorithm more clearly, this paper selects the benchmark functions F1 and F8 to visualize the internal changes of the PPE algorithm during the execution of the algorithm. The results are shown in Figs. 6 and 7.

Figure 6 shows the characteristics of different aspects of the algorithm PPE in the process of iterating 1000 times on the benchmark function F1.

The first picture is a three-dimensional map of the function F1 in two dimensions.

According to Algorithm 1, since the PPE algorithm will first judge whether a better solution can be obtained after the population position is updated, if a better solution is obtained, the first part will be executed, otherwise the second part will be executed. Therefore, the fourth picture compares the ratio of the number of times the first part and the second part are executed to the total number of times in the entire iteration process. Therefore, the fourth picture compares the ratio of the number of times the first part and second part is executed to the total number of times.

It can be seen from the fourth figure that in the six test results, the ratio of PPE algorithm obtaining better results on the benchmark function F1 is higher than the ratio of obtaining worse results.

Figure 7 shows the internal changes of the PPE algorithm when iterating on the benchmark function F8. Different from Fig. 6, according to the fourth picture of Fig. 7, the ratio of the PPE algorithm to obtain a worse position in the whole iterative process is higher than that of a better position. According to the second picture, the worst fitness values obtained by Np populations have not gradually improved and the fluctuations are relatively stable, and the best fitness values have also converged slowly.

Welding beam design problem is a basic and classic engineering optimization problem, often used to test the performance of optimization algorithms. This problem is a minimization problem, which minimizes the manufacturing cost of the welded beam [9].

Four variables need to be considered when optimizing this problem, including thickness of weld (h), height of the bar (t), length of the clamped bar (l) and thickness of the bar (b). In addition to this, multiple constraints need to be considered, the mathematical representation is as followsBased on the above description, this paper uses different algorithms to test, the results are shown in Table 5.

This problem is also a minimization engineering problem often used to test optimization algorithms. This problem requires minimizing the weight of tension and compression springs [41]. The three variables to be considered in the problem optimization process are the diameter of the wire (d), mean coil diameter (D) and the number of the active coils (N). In addition to this, multiple constraints need to be considered, the mathematical representation of the problem is as followsCombined with the above description of the problem, this paper uses related algorithms to test the problem, the results are shown in Table 6. Compared with other algorithms, the best value obtained by the PPE algorithm is better than other algorithms.

The goal of the pressure vessel design problem is to minimize the total cost of the cylindrical pressure vessel. Variables to consider include the shell thickness (\(T_s\)), the thickness of the head (\(T_h\)), the inner radius (R), the section length of the vessel (L). In addition to this, multiple constraints need to be considered, the mathematical representation is as followsThis article uses the engineering problem to test the PPE and other algorithms, the results are shown in Table 7. Compared with other algorithms, the PPE algorithm can obtain better results, but it is not as stable as the GWO algorithm. Since the algorithm is not specifically designed for the above application problems, the performance gap between PPE algorithm and GWO, ASO and other algorithms is not obvious. Based on the above comparison results, although the proposed PPE algorithm does not have an overwhelming advantage on a specific problem, it still has similar performance compared with existing algorithms.

This paper uses the Drone logistics hub location model proposed in [35] to test the proposed PPE algorithm.

This model considers the situation where the drone logistics hub serves the surrounding villages. Each village is in charge of a logistics hub, and each logistics hub is responsible for multiple villages. The location of the drone logistics hub is selected considering the location of the surrounding villages and the population size and the difficulty of transportation from the current location to the village. The objective function constructed by the model iswhere N means the number of villages, k means the k-th village, \(cp_k\) is represented as the population of the k-th village, \(R_k\) means the radius of a village, and \(H_k\) represents the straight-line distance from a village to the nearest logistics hub. \(L2_k\) is the same as \(H_k\), and \(L1_k\) represents the land distance from the current village to the nearest logistics hub. This paper randomly generates several models. The two-dimensional area simulated by the model is 50,000 m \(\times \) 50,000 m. The village size and population are randomly generated. The radius of the village ranges from 200 to 900, and the village population ranges from 300 to 3000.

Table 8 is the test results of different algorithms when using different models. Table 8 is the test results of different algorithms when using different models, M means the number of models, D means the number of drone hubs, and N means the number of villages generated. And the number of iterations is 1000.

In Table 8, the algorithm can get better results than other algorithms in the two generated models, and the generated results are shown in Fig. 8.