# Mutigroup-Based Phasmatodea Population Evolution Algorithm with Mutistrategy for IoT Electric Bus Scheduling

Authors: Yunxiang Zhu; Fengting Yan; Jeng-Shyang Pan; Lei Yu; Yuanfei Bai; Weigang Wang; Chunxia He; Zhicai Shi
Journal: Wireless Communications and Mobile Computing
 (2022)

---

## Abstract

The Phasmatodea population evolution algorithm (PPE) is a novel metaheuristic algorithm proposed in recent years, which simulates the evolutionary trend of stick insect population. In this article, a multigroup-based Phasmatodea population evolution algorithm with mutistrategy (MPPE) is proposed to further improve the overall performance of PPE. During the initialization period, the stick insect population is divided into multiple groups, and the step factor of the flower pollen algorithm is introduced into the population growth model of no more than half of the groups. This makes the population evolution trend diversified and prevents the algorithm from falling into the local optimal solution to a certain extent. In terms of intergroup communication, two communication strategies are adopted to mutate and replace the inferior particles, respectively, which improves the convergence speed and search ability of the algorithm. In the MPPE performance test, we compared it with PPE, five standard algorithms, and other parallel algorithms in CEC 2013 Benchmark Suite. Finally, this algorithm is applied to the IoT based electric bus scheduling for urban waterlogging situation, and the excellent performance of MPPE is verified comprehensively.


---

## Body

## 1. Introduction

Metaheuristic algorithms are inspired by relevant experiences, behaviors, rules, and mechanisms in the fields of physics, chemistry, biology, society, and art [1]. It is a method based on computational intelligence to solve complex optimization problems with the best or satisfactory solution [2–5]. Because it does not depend on specific problems, metaheuristic algorithms can be widely used in industrial production, economic life, military, and other fields [6–9].Metaheuristic algorithms can be roughly divided into three categories according to their sources. The first category is derived from human theory. In recent years, the gaining-sharing knowledge based (GSK) algorithm [10] and the volleyball premier league (VPL) algorithm [11] have been proposed, which simulate the development and activities of human life. The second category comes from biological behavior. Among the novel algorithms are island artificial bee colony (iABC) algorithm [12], monarch butterfly optimization (MBO) [13], moth search algorithm (MSA) [14], Harris hawks optimization (HHO) [15], and so on. The third category is inspired by physical phenomena. Such novel algorithms include thermal exchange optimization (TEO) [16], electrosearch (ES) algorithm [17], and lightning attachment procedure optimization (LAPO) [18]. Since people have obtained a lot of inspiration from the infinite nature, more and more nature-inspired algorithms have been proposed.The Phasmatodea population evolution (PPE) algorithm is a new metaheuristic algorithm proposed in 2020 [19]. Song et al. [20] simplified Phasmatodea population evolution algorithm and applied it to engineering optimization problems. This algorithm is inspired by the evolution trend of stick insect population in the natural environment. The characteristic of stick insect population growth is that it can adapt to a dynamic environment and change autonomously. In the initial stage, there is a favourable growth environment for the population, so it grows exponentially. When the population grows to a certain extent, due to the interference of environmental factors, its growth rate tends to slow down and eventually stops growing.The advantage of the PPE algorithm is that it has relatively good exploratory ability and stability. In terms of application, it is suitable for various engineering optimization problems. So, this algorithm also has a good generalization ability. But it still has some disadvantages. Its evolutionary mechanism will lead to the generation of some poor particles during the early period, and it converges slowly. When solving some problems, its solution tends to be locally optimal rather than globally optimal.To address the shortcomings of the PPE algorithm, we attempt to use parallel method to improve [21, 22]. Predecessors have done a lot of work in parallel optimization algorithm research over the years, such as parallel particle swarm optimization (PPSO) [23], parallel genetic algorithm (PGA) [24], parallel ant colony algorithm (PACO) [25–27], and parallel differential evolution algorithm (PDE) [28]. In this study, we introduce multiple strategies into the parallel approach. First, the stick insect population is divided into several groups, all of which evolve simultaneously. Secondly, the step factor of the flower pollen algorithm is introduced into the population growth model of some groups, and its evolution trend is changed to some extent. The diversity of population evolution mechanism makes the algorithm more capable of global exploration. Finally, we adopt two strategies for intergroup communication to improve the overall performance of PPE. The first strategy is to mutate the particles with poor fitness during the early stage to speed up the convergence of PPE. The second strategy is to randomly replace the best particle with other random particles in all the groups during the late period. It is intended to improve the global exploration accuracy of the algorithm. We made the above improvements to PPE and named it MPPE. In the comparative experiment of CEC 2013 Benchmark Suite, we verify the excellent performance of MPPE algorithm.Public traffic optimization is a hot issue in recent years [29–31]. With the rapid development of new energy technology, electric buses have gradually replaced fuel buses in short-distance transportation and have been popularized in many cities. This change promotes the wide application of intelligent transportation combined on Internet of Things (IoT) technology [32], in which the electric bus scheduling problem has become the focus of many scholars [33–35]. Bus scheduling is a multiobjective combination optimization problem, which has a recognized NP-hard problem. The purpose of this problem is to find an optimal solution in a complex objective function, that is, the best scheduling scheme. The metaheuristic algorithm can effectively calculate the optimal solution in a limited time and space and is not restricted by the problem itself. So, it is suitable for solving this kind of large-scale optimization problem. In recent years, more and more researchers have applied metaheuristic algorithms to bus scheduling [36–38], which proves their effectiveness in solving such problems.However, traditional metaheuristic algorithms often have some limitations for the solution results of the bus scheduling optimization. Novel metaheuristic algorithms are often more suitable for solving such complex optimization problems. In order to verify the effectiveness of the improved PPE algorithm in solving practical applications, we apply the MPPE algorithm to this hot problem for the first time. While solving this problem, we also successfully tried a new method, not limited to classic algorithms. This is to open up new ideas for scholars doing this kind of research. In this article, in addition to comparing MPPE with several original algorithms, we also compare with the recently proposed algorithms that have been used to solve the bus scheduling problem. The final experimental results prove that MPPE we proposed can achieve good results in solving this problem.The main contributions of this article are as follows:(1)
A parallel method is proposed with a two-stage communication strategy(2)
The step size factor of the flower pollen algorithm was introduced into the growth of the stick insect population to achieve the diversity of evolutionary trends(3)
MPPE algorithm has been successfully implemented for the optimization of the IoT electric bus scheduling on rainy days in city, and the result is satisfactoryThe remaining sections of the article are organized as follows. Section2 introduces the relevant formulas of the IoT electric bus scheduling problem and basic principle of PPE. In Section 3, a mutigroup-based Phasmatodea population evolution algorithm with mutistrategy (MPPE) is proposed. In Section 4, we compared MPPE with other algorithms on the benchmark suite and analyzed the performance of this algorithm. In Section 5, MPPE algorithm is applied to the IoT electric bus scheduling. Section 6 concludes the study.


## 2. Related Work

### 2.1. IoT Electric Bus Scheduling Problem

The Internet of Things based electric bus under the intelligent bus system is equipped with multisensor, high precision positioning, and wireless communication technology. This multitechnical fusion can detect the passenger flow and the consumption in the course of driving. In addition, passengers at the station can receive real-time bus scheduling information. This includes the estimated arrival time of next bus and the departure time interval for a certain period of time. When the same type of bus operates on the same section of the road, its total mileage and number of stations are fixed, the fare is uniform throughout the journey, and the time to reach each station during the journey is roughly equal. For these basic conditions, we can do the following analysis of the bus scheduling problem in this case.When only one-way operation of the electric bus is considered, the departure time of the first and last bus is fixed. Then, the day is divided into five time periods; each time period of passenger flow is different. Passenger flow is usually calculated by GPS positioning and IC card records. After the first bus leaves, the bus company should consider the departure interval of the next bus, which is different for each time period. The motivation of the IoT electric bus scheduling is to balance the interests of the company and passengers [39], which makes the setting of the departure interval fully consider the company’s profit and the patience of passengers. This is a multiobjective minimization problem. Therefore, the usual approach is to apply a weight to the company benefit and passenger benefit coefficient, respectively. In this case, decision-makers can balance the relationship between these two weights according to the actual situation. The objective function model can be represented by the following equation:(1)FΔtk=w1Q1D∑k=1KTkΔtk+w2Q2∑k=1K∑j=1JmkukjΔtk22,where the first item of the equation represents the cost consumption of the company and the second is the loss factor of passengers. w1 and w2 represent two weights, and the sum of these two values is equal to 1. Q1 is the cost of each bus per kilometer distance, including the electricity consumed, the loss of vehicle equipment, and the salary of bus drivers. Q2 is the patience loss of a unit of time for each passenger waiting at the station. D is the total distance of one-way bus operation, divided into K time periods. k indicates the current time period, Tk is the length of the current time period, Δtk is the departure interval of the kth time period, J is the total number of sites, j is the number of the current site, mk is the total number of departures in the kth time period, and ukj is the arrival rate of passengers at station j in the kth time period.In solving a practical optimization problem, in addition to the objective function, the corresponding constraints should also be considered. The constraint of this bus scheduling problem is that the bus company must be in a profitable state. In other words, the company’s operating income should be greater than the cost, to ensure that the company does not lose money. The equation for its constraint is(2)n×∑k=1K∑j=1JukJ∑k=1KTk/ΔTk＞Q1D.Using the above equation, if the turnover of bus company is below cost, an additional time is added to the bus departure interval as set out in the current system until the turnover is not less than the cost.According to the above introduction, the complexity of this problem mainly depends on the number of sites and time periods. With a series of data such as cost and passenger flow, this nonlinear problem is dynamic and difficult to solve by conventional methods.


### 2.2. Phasmatodea Population Evolution Algorithm

The basic principle of the Phasmatodea population evolution algorithm is that the movement of the solution in multidimensional space simulates the evolutionary trend of stick insect population. In a dynamic environment, each stick insect population is self-determining and is assigned two properties: growth rate and size. The growth trend of population is similar to the logistic regression model. During the initialization phase, solutionsx of Np populations are randomly generated, and the size of each x is computed as follows:(3)pi=1Np.In addition,h historically optimal solutions were selected to lead the search of the other solutions, and the number of h is(4)h=logNp+1.These historically optimal solutions are stored inho, ho = [xk1,…, xki,…, xkh]. The initialized generated Np solutions select h local optimal values through ho and store their fitness values. These local optimal solutions will direct other solutions throughout the population.During the iterative update phase, the evolutionary trend of the population is represented byevt, the position of the t-th evolution of the population is xt, and then the position obtained by the next evolution is xt+1. The position update equation is(5)xt+1=xt+evt.After the position is updated, the global optimal valuesGbest and h optimal solutions ho of the population are calculated. Evolutionary trend evt is divided into three parts. The first two parts use convergent evolutionary and path-dependent population growth models. If the quality of the updated solution is better than before, the first part of the update is adopted, and the update equation is(6)evtt+1=1−pt+1A+pt+1evtt+m,where pt+1 represents the population size of the next iteration, and its update formula is(7)pt+1=at+1pt1−pt,where a represents growth rate, which is set to 1.1 at the beginning, and A indicates the degree of closest to the optimal value, calculated as follows:(8)A=sho,xt−xt·c,where s (ho, xt) is to find the closest historically optimal solution xt in ho. c is a coefficient of the extent to which the most recent optimal solution affects the current population, ranging from 0 to 1. m represents the population mutation in a partial dimension.If the quality of the solution after the position update is worse, the update method of Part 2 will be used instead of Part 1. The second part is called convergence evolution, which tends to the most recent local optimal solution. The update equation is(9)evtt+1=rand·A+st·N,where N is the n-dimensional random factor generated by the normal distribution. The value of st is set to 0.1 × (Ub − Lb).The third part describes the model of population competition under environmental intervention. When populationsxi and xj are competing with each other, the population size of xi is(10)pi=pi+aipi1−pi−fxjfxipj,where xj is randomly selected and different from xi. Calculate the distance between xi and xj; then compare it to the set threshold TH. TH is calculated as follows:(11)TH=Ub−Lb×0.1×MaxGen+1−tMaxGen,where Ub and Lb represent upper and lower boundaries. MaxGen represents the maximum number of iterations. t is the current iteration. If the distance between xi and xj is less than TH, the two populations begin to compete each other, and the evolutionary trend update equation is(12)evtt+1=evtt+1+fxj−fxifxjxj−xi.Among them, if the population is too small or it is growing abnormally, the solution will be replaced by a new population.According to the formulas above, the pseudocode of PPE is shown in Figure1.Figure 1
The pseudocode of PPE.


## 2.1. IoT Electric Bus Scheduling Problem

The Internet of Things based electric bus under the intelligent bus system is equipped with multisensor, high precision positioning, and wireless communication technology. This multitechnical fusion can detect the passenger flow and the consumption in the course of driving. In addition, passengers at the station can receive real-time bus scheduling information. This includes the estimated arrival time of next bus and the departure time interval for a certain period of time. When the same type of bus operates on the same section of the road, its total mileage and number of stations are fixed, the fare is uniform throughout the journey, and the time to reach each station during the journey is roughly equal. For these basic conditions, we can do the following analysis of the bus scheduling problem in this case.When only one-way operation of the electric bus is considered, the departure time of the first and last bus is fixed. Then, the day is divided into five time periods; each time period of passenger flow is different. Passenger flow is usually calculated by GPS positioning and IC card records. After the first bus leaves, the bus company should consider the departure interval of the next bus, which is different for each time period. The motivation of the IoT electric bus scheduling is to balance the interests of the company and passengers [39], which makes the setting of the departure interval fully consider the company’s profit and the patience of passengers. This is a multiobjective minimization problem. Therefore, the usual approach is to apply a weight to the company benefit and passenger benefit coefficient, respectively. In this case, decision-makers can balance the relationship between these two weights according to the actual situation. The objective function model can be represented by the following equation:(1)FΔtk=w1Q1D∑k=1KTkΔtk+w2Q2∑k=1K∑j=1JmkukjΔtk22,where the first item of the equation represents the cost consumption of the company and the second is the loss factor of passengers. w1 and w2 represent two weights, and the sum of these two values is equal to 1. Q1 is the cost of each bus per kilometer distance, including the electricity consumed, the loss of vehicle equipment, and the salary of bus drivers. Q2 is the patience loss of a unit of time for each passenger waiting at the station. D is the total distance of one-way bus operation, divided into K time periods. k indicates the current time period, Tk is the length of the current time period, Δtk is the departure interval of the kth time period, J is the total number of sites, j is the number of the current site, mk is the total number of departures in the kth time period, and ukj is the arrival rate of passengers at station j in the kth time period.In solving a practical optimization problem, in addition to the objective function, the corresponding constraints should also be considered. The constraint of this bus scheduling problem is that the bus company must be in a profitable state. In other words, the company’s operating income should be greater than the cost, to ensure that the company does not lose money. The equation for its constraint is(2)n×∑k=1K∑j=1JukJ∑k=1KTk/ΔTk＞Q1D.Using the above equation, if the turnover of bus company is below cost, an additional time is added to the bus departure interval as set out in the current system until the turnover is not less than the cost.According to the above introduction, the complexity of this problem mainly depends on the number of sites and time periods. With a series of data such as cost and passenger flow, this nonlinear problem is dynamic and difficult to solve by conventional methods.


## 2.2. Phasmatodea Population Evolution Algorithm

The basic principle of the Phasmatodea population evolution algorithm is that the movement of the solution in multidimensional space simulates the evolutionary trend of stick insect population. In a dynamic environment, each stick insect population is self-determining and is assigned two properties: growth rate and size. The growth trend of population is similar to the logistic regression model. During the initialization phase, solutionsx of Np populations are randomly generated, and the size of each x is computed as follows:(3)pi=1Np.In addition,h historically optimal solutions were selected to lead the search of the other solutions, and the number of h is(4)h=logNp+1.These historically optimal solutions are stored inho, ho = [xk1,…, xki,…, xkh]. The initialized generated Np solutions select h local optimal values through ho and store their fitness values. These local optimal solutions will direct other solutions throughout the population.During the iterative update phase, the evolutionary trend of the population is represented byevt, the position of the t-th evolution of the population is xt, and then the position obtained by the next evolution is xt+1. The position update equation is(5)xt+1=xt+evt.After the position is updated, the global optimal valuesGbest and h optimal solutions ho of the population are calculated. Evolutionary trend evt is divided into three parts. The first two parts use convergent evolutionary and path-dependent population growth models. If the quality of the updated solution is better than before, the first part of the update is adopted, and the update equation is(6)evtt+1=1−pt+1A+pt+1evtt+m,where pt+1 represents the population size of the next iteration, and its update formula is(7)pt+1=at+1pt1−pt,where a represents growth rate, which is set to 1.1 at the beginning, and A indicates the degree of closest to the optimal value, calculated as follows:(8)A=sho,xt−xt·c,where s (ho, xt) is to find the closest historically optimal solution xt in ho. c is a coefficient of the extent to which the most recent optimal solution affects the current population, ranging from 0 to 1. m represents the population mutation in a partial dimension.If the quality of the solution after the position update is worse, the update method of Part 2 will be used instead of Part 1. The second part is called convergence evolution, which tends to the most recent local optimal solution. The update equation is(9)evtt+1=rand·A+st·N,where N is the n-dimensional random factor generated by the normal distribution. The value of st is set to 0.1 × (Ub − Lb).The third part describes the model of population competition under environmental intervention. When populationsxi and xj are competing with each other, the population size of xi is(10)pi=pi+aipi1−pi−fxjfxipj,where xj is randomly selected and different from xi. Calculate the distance between xi and xj; then compare it to the set threshold TH. TH is calculated as follows:(11)TH=Ub−Lb×0.1×MaxGen+1−tMaxGen,where Ub and Lb represent upper and lower boundaries. MaxGen represents the maximum number of iterations. t is the current iteration. If the distance between xi and xj is less than TH, the two populations begin to compete each other, and the evolutionary trend update equation is(12)evtt+1=evtt+1+fxj−fxifxjxj−xi.Among them, if the population is too small or it is growing abnormally, the solution will be replaced by a new population.According to the formulas above, the pseudocode of PPE is shown in Figure1.Figure 1
The pseudocode of PPE.


## 3. Proposed Method

In this study, we propose multigroup-based Phasmatodea population evolution algorithm with multiple strategies, including a two-stage parallel communication strategy and the introduction of step factor, which improve the PPE algorithm in many aspects.


### 3.1. Parallel Strategy

In the previous research on the improvement of optimization algorithm, the parallel method is often taken into account [40]. The parallel method can effectively improve the global exploration ability of the algorithm through population division. In this study, we divide stick insect populations into multiple groups, make each group evolve in parallel, and implement a two-stage intergroup communication strategy at each iteration. The first stage of communication is to accelerate the convergence of PPE by mutating the worst particles in each group to the best particles in some dimensions. The second stage is to improve the search accuracy of PPE by randomly replacing the best particles with random particles from each group. To balance the convergence speed and global exploration accuracy, we use the first strategy for the first half of the iterations and the second strategy for the second half.In the first communication strategy, the particles with the worst fitness values in each group are mutated individually, and the mutation is close to the current global optimal particles. The equation for the mutation is as follows:(13)Xd=totalbestd×m+n×rand,where Xd represents the position of the particle after the d-dimensional mutation, totalbestd is the position of the current global optimal particle of the d-dimensional, rand is a random number of 0-1. m and n are parameters that control the degree to which the mutant particle approaches the global optimal particle. In general, m, n ∈ (0, 1), and the sum of m and n is 1. In order to make mutant particles close to the current global optimal particles, the value of m should be set larger. In this article, we set m to 0.8 and n to 0.2. In this way, the positions of mutated particles are randomly distributed near the current global optimal position.In the second communication strategy, some random particles are replaced with the current global optimal particles. The specific operation is to randomly generate indexes of the positions of some particles ranging from 1 to the total number of particles per group, and then replace these particles with the current global optimal particles in each group corresponding to these indexes. Finally, the fitness values of the replaced particles are updated.Figure2 shows the above introduction of proposed two-stage parallel communication strategy. This parallel strategy combines two different methods, which leads to closer communication between groups. Therefore, what we expect is to make the algorithm more stable in the process of search.Figure 2
Two-stage communication strategy.


### 3.2. Step Factor of the Flower Pollen Algorithm

The flower pollen algorithm simulates the pollination of flowering plants [41–43], which is divided into global pollination and local pollination. This study was inspired by global pollination, which simulates the process by a flying insect carries pollen from one flowering plant over a distance to another. The equation of pollen position movement for global pollination is(14)xit+1=xit+Levy×xit−gt,where gt is the current global optimum. Levy represents the flight of flying insects in global pollination, which is calculated as follows:(15)Levy=sinπr/2×λΓrπ×si+r,where Γr is the gamma function, the distribution is valid for the large steps of s > 0. In this article, we set r to 1.5. As the position index i changes, so does the value of Levy, which indicates the degree of influence of global pollination can be seen as a step factor. In order to allow the population of stick insect to evolve with different growth trends and prevent algorithms from tending to locally optimal solutions when solving some optimization problems, we add the step factor Levy to the population growth model of stick insect in some groups. This method mainly changes the degree of influence of convergence evolution in (6), so that the original influence factor c was replaced by a changing step factor Levy. The equation after the change of A is(16)A=sho,xt−xt·Levy·γ,where γ indicates the scaling factor that controls step Levy. If the value of Levy is too large, it will inevitably break the evolutionary rule of the population, at which point the γ will narrow the Levy when it exceeds a certain range.


### 3.3. Multigroup-Based Phasmatodea Population Evolution Algorithm with Multistrategy

According to the introduction of the above two-stage communication strategy and step factor of the flower pollen algorithm, we propose the multigroup-based Phasmatodea population evolution algorithm with multistrategy and named it as MPPE. The flowchart for this method is shown in Figure3. Figure 4 shows the pseudocode of MPPE. In the initialization stage, the stick insect population is divided into several groups, and each group has the same population size. Then, the initial solution and position of each group were generated according to the initialization method of PPE. In the update iteration stage, no more than half of the groups are introduced into the population growth model with step factor Levy, and the remaining groups are updated in the original method. After each group completes an iteration update at the same time, the two-stage intergroup communication strategy described above will be carried out according to the number of iterations. The solution obtained after each intergroup communication will be the current global optimal solution.Figure 3
The entire phases of the proposed method.Figure 4
The pseudocode of MPPE.This research is based on a parallel method, and multiple strategies are implemented on the basis of multiple groups in parallel. The diversity of population evolution trends can be used to find the best particles through communication between groups. In general, the limitations of a single strategy cannot achieve the effect of algorithm improvement. Only the combination of multiply strategies can work together.


## 3.1. Parallel Strategy

In the previous research on the improvement of optimization algorithm, the parallel method is often taken into account [40]. The parallel method can effectively improve the global exploration ability of the algorithm through population division. In this study, we divide stick insect populations into multiple groups, make each group evolve in parallel, and implement a two-stage intergroup communication strategy at each iteration. The first stage of communication is to accelerate the convergence of PPE by mutating the worst particles in each group to the best particles in some dimensions. The second stage is to improve the search accuracy of PPE by randomly replacing the best particles with random particles from each group. To balance the convergence speed and global exploration accuracy, we use the first strategy for the first half of the iterations and the second strategy for the second half.In the first communication strategy, the particles with the worst fitness values in each group are mutated individually, and the mutation is close to the current global optimal particles. The equation for the mutation is as follows:(13)Xd=totalbestd×m+n×rand,where Xd represents the position of the particle after the d-dimensional mutation, totalbestd is the position of the current global optimal particle of the d-dimensional, rand is a random number of 0-1. m and n are parameters that control the degree to which the mutant particle approaches the global optimal particle. In general, m, n ∈ (0, 1), and the sum of m and n is 1. In order to make mutant particles close to the current global optimal particles, the value of m should be set larger. In this article, we set m to 0.8 and n to 0.2. In this way, the positions of mutated particles are randomly distributed near the current global optimal position.In the second communication strategy, some random particles are replaced with the current global optimal particles. The specific operation is to randomly generate indexes of the positions of some particles ranging from 1 to the total number of particles per group, and then replace these particles with the current global optimal particles in each group corresponding to these indexes. Finally, the fitness values of the replaced particles are updated.Figure2 shows the above introduction of proposed two-stage parallel communication strategy. This parallel strategy combines two different methods, which leads to closer communication between groups. Therefore, what we expect is to make the algorithm more stable in the process of search.Figure 2
Two-stage communication strategy.


## 3.2. Step Factor of the Flower Pollen Algorithm

The flower pollen algorithm simulates the pollination of flowering plants [41–43], which is divided into global pollination and local pollination. This study was inspired by global pollination, which simulates the process by a flying insect carries pollen from one flowering plant over a distance to another. The equation of pollen position movement for global pollination is(14)xit+1=xit+Levy×xit−gt,where gt is the current global optimum. Levy represents the flight of flying insects in global pollination, which is calculated as follows:(15)Levy=sinπr/2×λΓrπ×si+r,where Γr is the gamma function, the distribution is valid for the large steps of s > 0. In this article, we set r to 1.5. As the position index i changes, so does the value of Levy, which indicates the degree of influence of global pollination can be seen as a step factor. In order to allow the population of stick insect to evolve with different growth trends and prevent algorithms from tending to locally optimal solutions when solving some optimization problems, we add the step factor Levy to the population growth model of stick insect in some groups. This method mainly changes the degree of influence of convergence evolution in (6), so that the original influence factor c was replaced by a changing step factor Levy. The equation after the change of A is(16)A=sho,xt−xt·Levy·γ,where γ indicates the scaling factor that controls step Levy. If the value of Levy is too large, it will inevitably break the evolutionary rule of the population, at which point the γ will narrow the Levy when it exceeds a certain range.


## 3.3. Multigroup-Based Phasmatodea Population Evolution Algorithm with Multistrategy

According to the introduction of the above two-stage communication strategy and step factor of the flower pollen algorithm, we propose the multigroup-based Phasmatodea population evolution algorithm with multistrategy and named it as MPPE. The flowchart for this method is shown in Figure3. Figure 4 shows the pseudocode of MPPE. In the initialization stage, the stick insect population is divided into several groups, and each group has the same population size. Then, the initial solution and position of each group were generated according to the initialization method of PPE. In the update iteration stage, no more than half of the groups are introduced into the population growth model with step factor Levy, and the remaining groups are updated in the original method. After each group completes an iteration update at the same time, the two-stage intergroup communication strategy described above will be carried out according to the number of iterations. The solution obtained after each intergroup communication will be the current global optimal solution.Figure 3
The entire phases of the proposed method.Figure 4
The pseudocode of MPPE.This research is based on a parallel method, and multiple strategies are implemented on the basis of multiple groups in parallel. The diversity of population evolution trends can be used to find the best particles through communication between groups. In general, the limitations of a single strategy cannot achieve the effect of algorithm improvement. Only the combination of multiply strategies can work together.


## 4. Experiment and Discussion

To test the optimization effect of MPPE, we conduct two comparative experiments. The first set of experiments is compared with PPE algorithm and five standard metaheuristic algorithms. The second is compared with other parallel metaheuristic algorithms. In this article, we select CEC 2013 Benchmark Suite to test the optimization problems of all algorithms. CEC 2013 Benchmark Suite is composed of 28 classic functions and has been widely used in experiments to test the performance of algorithms, wheref1∼f5 are single-mode functions, f6∼f20 are basic multimode functions, and f21∼f28 are combination functions. These optimization problems have a common search range of −100 to 100, with minimum values increasing from −1400 to 1400.All experiments in this article are completed in MATLAB R2020b. The experimental equipment is a laptop computer with 2.60 GHz CPU, 16 g memory, and 64-bit Win10 system. Generally speaking, a larger population size and number of iterations can make the optimization result of the algorithm better. To ensure fair comparison and fully reflect the performance of these algorithms, we set the population of all algorithms to 100, the dimension to 30, and the number of function evaluations to 200,000. Each algorithm is independently experimented with 20 averages as an optimization result.These experiments mainly compare the exploration accuracy and convergence performance of algorithms and implemented appropriate nonparametric hypothesis tests [44, 45]. In order to further analyze the proposed algorithm, we discuss the time complexity of MPPE in the last part of this section.


### 4.1. Compared to Standard Algorithms

In this part, we compared MPPE with PPE, PSO [46], SCA [47], WOA [48], GWO [49], and GSK [10]. Table 1 lists the parameter settings for these algorithms. Table 2 shows the comparison results in 28 benchmark functions. It shows that MPPE can achieve satisfactory results in most optimization problems. Among them, the optimal value obtained by the optimization of f1, f5, and f10 are their actual minimum value. In comparison with PPE, except for f1 and f5, which have achieved the minimum of the function together, optimal values are better in 18 functions and equal in 7 functions, and only f13 is worse. In addition, the optimization effects of MPPE on single-mode problems and multimode problems are significantly improved. It can be inferred that these improvement strategies make the algorithm no longer tend to the local optimal solution when solving most problems. Compared with PSO, the optimization effect of PSO is not worse than that of MPPE in some functions. However, as a classic swarm intelligence algorithm, PSO has been recognized as a drawback of premature convergence, so it is easier to tend to local optimal solutions when solving practical problems. For example, its optimization effects in f4, f15, and f23 are far behind that of MPPE, and its stability is not good. In comparison with SCA and WOA, MPPE has great advantages, with better results in almost all function optimizations than these two algorithms. In the comparison of GWO, MPPE algorithm is superior in the optimization of most single-mode and multimode problems, but poor in the optimization of combinatorial problems. This is because GWO algorithm has a better result in solving these problems from its clustering cooperation mechanism. Overall, MPPE is better than GWO at solving most problems. In comparison with GSK, it can be seen that the overall optimization effect of GSK is slightly better than that of MPPE. But in the optimization of some multimode problems, MPPE performs significantly better.Table 1
Parameter settings of seven algorithms.
AlgorithmParameter settingsMPPENp = 100, groups = 5PPENp = 100, c = 0.2PSONp = 100, c1 = 2, c2 = 2, inertia constant from 0.8 to 0.2SCANp = 100WOANp = 100GWONp = 100GSKNp = 100, kf = 0.5, kf = 0.9, p = 0.1, K = 10Table 2
Optimization results for MPPE, PPE, PSO, SCA, WOA, GWO, and GSK over CEC 2013.
FunctionMPPEPPEPSOSCAWOAGWOGSKf1−1.40E + 03−1.40E + 03−1.40E + 031.13E + 04−1.40E + 03−6.66E + 02−1.40E + 03f22.61E + 064.51E + 061.84E + 071.47E + 083.84E + 071.66E + 072.57E + 05f33.62E + 087.31E + 081.32E + 083.86E + 101.75E + 104.38E + 09−1.20E + 03f4−2.06E + 023.36E + 036.75E + 043.45E + 045.27E + 042.77E + 046.43E + 02f5−1.00E + 03−1.00E + 03−1.00E + 031.45E + 03−8.91E + 02−2.95E + 02−1.00E + 03f6−8.33E + 02−8.33E + 02−8.20E + 02−9.17E + 01−7.74E + 02−7.64E + 02−8.85E + 02f7−7.20E + 02−6.95E + 02−7.57E + 02−6.07E + 02−1.61E + 02−7.49E + 02−8.00E + 02f8−6.79E + 02−6.79E + 02−6.79E + 02−6.79E + 02−6.79E + 02−6.79E + 02−6.79E + 02f9−5.69E + 02−5.69E + 02−5.78E + 02−5.60E + 02−5.62E + 02−5.81E + 02−5.63E + 02f10−5.00E + 02−4.99E + 02−4.99E + 021.21E + 03−4.13E + 02−2.65E + 02−5.00E + 02f11−3.87E + 02−3.52E + 02−3.77E + 02−4.18E + 011.04E + 02−3.08E + 02−2.66E + 02f12−2.76E + 02−4.46E + 00−2.20E + 028.75E + 012.10E + 02−1.77E + 02−1.30E + 02f131.29E + 021.79E + 021.72E + 021.91E + 022.96E + 02−1.98E + 01−2.88E + 01f149.02E + 021.15E + 032.59E + 037.06E + 035.07E + 032.93E + 035.93E + 03f153.46E + 034.22E + 037.13E + 037.63E + 035.61E + 033.80E + 037.38E + 03f162.01E + 022.01E + 022,02E + 022.03E + 022.02E + 022.03E + 022.02E + 02f173.38E + 023.79E + 023.62E + 027.84E + 029.25E + 024.54E + 024.74E + 02f186.23E + 026.74E + 026.32E + 029.04E + 029.73E + 026.45E + 025.80E + 02f195.03E + 025.07E + 025.03E + 023.95E + 035.67E + 022.03E + 035.13E + 02f206.15E + 026.15E + 026.15E + 026.14E + 026.15E + 026.12E + 026.13E + 02f211.09E + 031.09E + 031.00E + 032.61E + 031.09E + 031.54E + 031.00E + 03f222.24E + 032.48E + 035.05E + 038.58E + 037.12E + 033.91E + 035.04E + 03f235.67E + 035.69E + 035.77E + 038.83E + 037.62E + 035.52E + 038.02E + 03f241.28E + 031.28E + 031.29E + 031.32E + 031.31E + 031.25E + 031.20E + 03f251.42E + 031.44E + 031.41E + 031.43E + 031.42E + 031.37E + 031.41E + 03f261.40E + 031.47E + 031.48E + 031.41E + 031.53E + 031.53E + 031.40E + 03f272.42E + 032.28E + 032.29E + 032.70E + 032.63E + 032.09E + 031.67E + 03f282.52E + 034.69E + 033.47E + 034.04E + 035.41E + 032.63E + 031.70E + 03Bold values represent the best results relative to other comparison methods.The comparison of these seven algorithms shows that MPPE can achieve better or equal results than other six algorithms in the optimization results of 14 functions. Table3 counts the number of the best results obtained by each of the seven algorithms on three types of functions and their rankings. As can be seen from the rankings, the optimization performance of MPPE in this benchmark suite is second only to GSK. MPPE is overall better than other five classic algorithms. It should be emphasized that MPPE performs best in multimode functions.Table 3
Statistics of optimization results of seven algorithms on three types of functions.
AlgorithmSingle-modeMultimodeCombinationWinsRankingGSK475161MPPE392142GWO03363PSO22154PPE22045WOA11026SCA01017Table4 shows the results of Wilcoxon signed rank-sum test between MPPE and other six algorithms at a significant level of 0.05. The “+” symbol in the table indicates the optimization results in 28 functions of MPPE is better than that algorithm. The meaning of the “−” symbol is the optimization results of MPPE is worse than that algorithm. The “≈” symbol indicates that the optimization results almost have no difference. R+ and R− both represent the sum of ranks calculated by comparing all differences. p value records the significance of MPPE compared to each algorithm. “Sig.” represents the significance level of MPPE compared to each algorithm. It can be concluded that the optimization results of MPPE is only significantly better than SCA, and there is no significant difference from the other five algorithms. From the perspective of rank-sum, in the comparison between MPPE and PPE, SCA, and WOA, R+ is significantly greater than R−. Compared with GSK, R+ is worse than R−.Table 4
The results of Wilcoxon signed rank-sum test between MPPE and other six algorithms.
AlgorithmR+R−p value+≈−Sig.MPPE versus PPE340210.631891≈MPPE versus PSO2541240.591477≈MPPE versus SCA40000.0352430+MPPE versus WOA39100.332350≈MPPE versus GWO307930.461738≈MPPE versus GSK1722060.819712≈Figure5 shows the convergence performance of seven algorithms in different benchmark functions. We select the experimental results of two single-mode functions, two multimode functions, and two combination functions to compare the convergence performance of these algorithms from multiple perspectives. To make the comparison more obvious, we set the minimum fitness ordinate to log scale. It shows that MPPE has a fast convergence speed and is not prone to premature convergence. Compared with PPE, the convergence curve of MPPE has a faster downward trend during the early period, and the convergence in the later period improves the search accuracy more obviously. The convergence speeds of GWA, WOA, and SCA in the optimization of these functions are slow. The convergence performance of PSO is unstable. GSK converges better than MPPE in the optimization of f2 but falls into the local optimal solution early in the optimization of f14. Therefore, MPPE’s comprehensive convergence performance in the optimization of these functions is better than the other six algorithms.Figure 5
Convergence performance of seven algorithms. (a)f2, (b) f4, (c) f14, (d) f17, (e) f22, and (f) f26.
(a)(b)(c)(d)(e)(f)


### 4.2. Compared to Parallel Algorithms

To further verify the overall performance of MPPE, three parallel algorithms are selected to compare with this algorithm. These algorithms are PPSO [50], PWOA [51], and MMSCA [52]. The specific parameter settings are shown in Table 5. These algorithms were also compared on 28 functions of CEC 2013 and the experimental results of MPPE remain unchanged. Table 6 shows the optimization results of the four algorithms. MPPE can achieve the best results in the optimization of 20 functions, with multimode functions accounting for a large proportion. The results of PWOA and MMSCA are worse than MPPE in most functions, but PPSO can achieve better optimization results in 7 functions. Though the intergroup communication strategy of PPSO can avoid premature convergence to a certain extent, it still has the drawback of decreased accuracy when solving complex problems. Therefore, its overall optimization performance is worse than MPPE.Table 5
Parameter settings of four parallel algorithms.
AlgorithmParameter settingsMPPENp = 100, groups = 5PPSONp = 100, groups = 5, c1 = 2, c2 = 2, inertia constant from 0.8 to 0.2,PWOANp = 100, groups = 5MMSCANp = 100, groups = 5Table 6
Optimization results for MPPE, PPSO, PWOA, and MMSCA over CEC 2013.
FunctionMPPEPPSOPWOAMMSCAf1−1.40E + 03−1.40E + 03−1.39E + 036.77E + 03f22.61E + 068.09E + 053.71E + 077.42E + 07f33.62E + 086.52E + 081.31E + 102.02E + 10f4−2.06E + 02−7.43E + 024.75E + 042.81E + 04f5−1.00E + 03−1.00E + 03−8.88E + 026.56E + 02f6−8.33E + 02−8.43E + 02−7.71E + 02−4.33E + 02f7−7.20E + 02−7.08E + 02−5.93E + 02−6.68E + 02f8−6.79E + 02−6.79E + 02−6.79E + 02−6.79E + 02f9−5.69E + 02−5.72E + 02−5.67E + 02−5.62E + 02f10−5.00E + 02−5.00E + 02−3.41E + 027.27E + 02f11−3.87E + 02−1.01E + 02−3.99E + 01−6.81E + 01f12−2.76E + 02−4.21E + 011.90E + 023.62E + 01f131.29E + 021.49E + 022.30E + 021.51E + 02f149.02E + 023.39E + 033.78E + 036.74E + 03f153.46E + 034.22E + 035.69E + 037.21E + 03f162.01E + 022.01E + 022.02E + 022.02E + 02f173.38E + 024.81E + 028.25E + 027.39E + 02f186.23E + 025.61E + 027.88E + 028.55E + 02f195.03E + 025.06E + 025.35E + 023.22E + 03f206.15E + 026.15E + 026.15E + 026.14E + 02f211.09E + 031.03E + 031.18E + 032.33E + 03f222.24E + 035.61E + 035.12E + 037.56E + 03f235.67E + 036.22E + 036.53E + 038.58E + 03f241.28E + 031.29E + 031.30E + 031.31E + 03f251.42E + 031.43E + 031.42E + 031.42E + 03f261.40E + 031.51E + 031.48E + 031.41E + 03f272.42E + 032.40E + 032.66E + 032.62E + 03f282.52E + 033.86E + 035.09E + 033.74E + 03Bold values represent the best results relative to other comparison methods.Table7 shows the statistics of optimization results of four algorithms on three types of functions. MPPE ranks first with the most wins compared to the other three parallel algorithms. Especially in the optimization results of multimode and combination problems, MPPE occupies a significant advantage.Table 7
Statistics of optimization results of four algorithms on three types of functions.
AlgorithmSingle-modemultimodeCombinationWinsRankingMPPE3116201PPSO462122MMSCA02133PWOA01124Table8 shows the results of Wilcoxon signed rank-sum test between MPPE and the other three algorithms. In these sets of statistical results, the advantages of MPPE for the other three parallel algorithms are not significant. Therefore, we can at least infer that in this benchmark suite test, there is no obvious gap in the optimization results of MPPE compared to most algorithms under the parameter settings of this experiment.Table 8
The results of Wilcoxon signed rank-sum test between MPPE and the other three algorithms.
AlgorithmR+R−p value+=−Dec.MPPE versus PPSO2451250.871387≈MPPE versus PWOA39100.392350≈MPPE versus MMSCA39600.0672440≈Figure6 shows convergence performance of the four parallel algorithms. We select three multimode and combination functions, respectively, for analysis. From the comparison of convergence speed, both MMSCA and PWOA are significantly slower than MPPE. PPSO and MPPE are similar in the early stage, but PPSO has a slower convergence rate in the late period. We can infer from this that MPPE is more likely to get rid of the local optimal solution and continue to seek the global minimum in the late period. Therefore, its overall convergence performance is better than the other three parallel algorithms.Figure 6
Convergence performance of four parallel algorithms. (a)f4, (b) f14, (c) f17, (d) f22, (e) f23, and (f) f26.
(a)(b)(c)(d)(e)(f)


### 4.3. Analysis of Algorithm Complexity

The maximum time complexity of PPE is described asO (p · n · I), where p is the total number of stick insect populations, n is the dimension of the problem, and I is the maximum number of iterations. MPPE adopted a parallel method on the basis of PPE, and each iteration is accompanied by the simultaneous evolution of each group of populations. So, the maximum time complexity of MPPE can be described as O ((p1 · n + p2 · n + · · · + pg · n) · I), where pi is the population size of the ith group and g is the number of groups. Since the number of populations in each group is equal to p/g, the maximum complexity of MPPE is described as O (p · n · I).Although the amount of calculation added by the intergroup communication strategy does not exceed the maximum time complexity, the actual running time of MPPE has increased considerably compared to PPE.


## 4.1. Compared to Standard Algorithms

In this part, we compared MPPE with PPE, PSO [46], SCA [47], WOA [48], GWO [49], and GSK [10]. Table 1 lists the parameter settings for these algorithms. Table 2 shows the comparison results in 28 benchmark functions. It shows that MPPE can achieve satisfactory results in most optimization problems. Among them, the optimal value obtained by the optimization of f1, f5, and f10 are their actual minimum value. In comparison with PPE, except for f1 and f5, which have achieved the minimum of the function together, optimal values are better in 18 functions and equal in 7 functions, and only f13 is worse. In addition, the optimization effects of MPPE on single-mode problems and multimode problems are significantly improved. It can be inferred that these improvement strategies make the algorithm no longer tend to the local optimal solution when solving most problems. Compared with PSO, the optimization effect of PSO is not worse than that of MPPE in some functions. However, as a classic swarm intelligence algorithm, PSO has been recognized as a drawback of premature convergence, so it is easier to tend to local optimal solutions when solving practical problems. For example, its optimization effects in f4, f15, and f23 are far behind that of MPPE, and its stability is not good. In comparison with SCA and WOA, MPPE has great advantages, with better results in almost all function optimizations than these two algorithms. In the comparison of GWO, MPPE algorithm is superior in the optimization of most single-mode and multimode problems, but poor in the optimization of combinatorial problems. This is because GWO algorithm has a better result in solving these problems from its clustering cooperation mechanism. Overall, MPPE is better than GWO at solving most problems. In comparison with GSK, it can be seen that the overall optimization effect of GSK is slightly better than that of MPPE. But in the optimization of some multimode problems, MPPE performs significantly better.Table 1
Parameter settings of seven algorithms.
AlgorithmParameter settingsMPPENp = 100, groups = 5PPENp = 100, c = 0.2PSONp = 100, c1 = 2, c2 = 2, inertia constant from 0.8 to 0.2SCANp = 100WOANp = 100GWONp = 100GSKNp = 100, kf = 0.5, kf = 0.9, p = 0.1, K = 10Table 2
Optimization results for MPPE, PPE, PSO, SCA, WOA, GWO, and GSK over CEC 2013.
FunctionMPPEPPEPSOSCAWOAGWOGSKf1−1.40E + 03−1.40E + 03−1.40E + 031.13E + 04−1.40E + 03−6.66E + 02−1.40E + 03f22.61E + 064.51E + 061.84E + 071.47E + 083.84E + 071.66E + 072.57E + 05f33.62E + 087.31E + 081.32E + 083.86E + 101.75E + 104.38E + 09−1.20E + 03f4−2.06E + 023.36E + 036.75E + 043.45E + 045.27E + 042.77E + 046.43E + 02f5−1.00E + 03−1.00E + 03−1.00E + 031.45E + 03−8.91E + 02−2.95E + 02−1.00E + 03f6−8.33E + 02−8.33E + 02−8.20E + 02−9.17E + 01−7.74E + 02−7.64E + 02−8.85E + 02f7−7.20E + 02−6.95E + 02−7.57E + 02−6.07E + 02−1.61E + 02−7.49E + 02−8.00E + 02f8−6.79E + 02−6.79E + 02−6.79E + 02−6.79E + 02−6.79E + 02−6.79E + 02−6.79E + 02f9−5.69E + 02−5.69E + 02−5.78E + 02−5.60E + 02−5.62E + 02−5.81E + 02−5.63E + 02f10−5.00E + 02−4.99E + 02−4.99E + 021.21E + 03−4.13E + 02−2.65E + 02−5.00E + 02f11−3.87E + 02−3.52E + 02−3.77E + 02−4.18E + 011.04E + 02−3.08E + 02−2.66E + 02f12−2.76E + 02−4.46E + 00−2.20E + 028.75E + 012.10E + 02−1.77E + 02−1.30E + 02f131.29E + 021.79E + 021.72E + 021.91E + 022.96E + 02−1.98E + 01−2.88E + 01f149.02E + 021.15E + 032.59E + 037.06E + 035.07E + 032.93E + 035.93E + 03f153.46E + 034.22E + 037.13E + 037.63E + 035.61E + 033.80E + 037.38E + 03f162.01E + 022.01E + 022,02E + 022.03E + 022.02E + 022.03E + 022.02E + 02f173.38E + 023.79E + 023.62E + 027.84E + 029.25E + 024.54E + 024.74E + 02f186.23E + 026.74E + 026.32E + 029.04E + 029.73E + 026.45E + 025.80E + 02f195.03E + 025.07E + 025.03E + 023.95E + 035.67E + 022.03E + 035.13E + 02f206.15E + 026.15E + 026.15E + 026.14E + 026.15E + 026.12E + 026.13E + 02f211.09E + 031.09E + 031.00E + 032.61E + 031.09E + 031.54E + 031.00E + 03f222.24E + 032.48E + 035.05E + 038.58E + 037.12E + 033.91E + 035.04E + 03f235.67E + 035.69E + 035.77E + 038.83E + 037.62E + 035.52E + 038.02E + 03f241.28E + 031.28E + 031.29E + 031.32E + 031.31E + 031.25E + 031.20E + 03f251.42E + 031.44E + 031.41E + 031.43E + 031.42E + 031.37E + 031.41E + 03f261.40E + 031.47E + 031.48E + 031.41E + 031.53E + 031.53E + 031.40E + 03f272.42E + 032.28E + 032.29E + 032.70E + 032.63E + 032.09E + 031.67E + 03f282.52E + 034.69E + 033.47E + 034.04E + 035.41E + 032.63E + 031.70E + 03Bold values represent the best results relative to other comparison methods.The comparison of these seven algorithms shows that MPPE can achieve better or equal results than other six algorithms in the optimization results of 14 functions. Table3 counts the number of the best results obtained by each of the seven algorithms on three types of functions and their rankings. As can be seen from the rankings, the optimization performance of MPPE in this benchmark suite is second only to GSK. MPPE is overall better than other five classic algorithms. It should be emphasized that MPPE performs best in multimode functions.Table 3
Statistics of optimization results of seven algorithms on three types of functions.
AlgorithmSingle-modeMultimodeCombinationWinsRankingGSK475161MPPE392142GWO03363PSO22154PPE22045WOA11026SCA01017Table4 shows the results of Wilcoxon signed rank-sum test between MPPE and other six algorithms at a significant level of 0.05. The “+” symbol in the table indicates the optimization results in 28 functions of MPPE is better than that algorithm. The meaning of the “−” symbol is the optimization results of MPPE is worse than that algorithm. The “≈” symbol indicates that the optimization results almost have no difference. R+ and R− both represent the sum of ranks calculated by comparing all differences. p value records the significance of MPPE compared to each algorithm. “Sig.” represents the significance level of MPPE compared to each algorithm. It can be concluded that the optimization results of MPPE is only significantly better than SCA, and there is no significant difference from the other five algorithms. From the perspective of rank-sum, in the comparison between MPPE and PPE, SCA, and WOA, R+ is significantly greater than R−. Compared with GSK, R+ is worse than R−.Table 4
The results of Wilcoxon signed rank-sum test between MPPE and other six algorithms.
AlgorithmR+R−p value+≈−Sig.MPPE versus PPE340210.631891≈MPPE versus PSO2541240.591477≈MPPE versus SCA40000.0352430+MPPE versus WOA39100.332350≈MPPE versus GWO307930.461738≈MPPE versus GSK1722060.819712≈Figure5 shows the convergence performance of seven algorithms in different benchmark functions. We select the experimental results of two single-mode functions, two multimode functions, and two combination functions to compare the convergence performance of these algorithms from multiple perspectives. To make the comparison more obvious, we set the minimum fitness ordinate to log scale. It shows that MPPE has a fast convergence speed and is not prone to premature convergence. Compared with PPE, the convergence curve of MPPE has a faster downward trend during the early period, and the convergence in the later period improves the search accuracy more obviously. The convergence speeds of GWA, WOA, and SCA in the optimization of these functions are slow. The convergence performance of PSO is unstable. GSK converges better than MPPE in the optimization of f2 but falls into the local optimal solution early in the optimization of f14. Therefore, MPPE’s comprehensive convergence performance in the optimization of these functions is better than the other six algorithms.Figure 5
Convergence performance of seven algorithms. (a)f2, (b) f4, (c) f14, (d) f17, (e) f22, and (f) f26.
(a)(b)(c)(d)(e)(f)


## 4.2. Compared to Parallel Algorithms

To further verify the overall performance of MPPE, three parallel algorithms are selected to compare with this algorithm. These algorithms are PPSO [50], PWOA [51], and MMSCA [52]. The specific parameter settings are shown in Table 5. These algorithms were also compared on 28 functions of CEC 2013 and the experimental results of MPPE remain unchanged. Table 6 shows the optimization results of the four algorithms. MPPE can achieve the best results in the optimization of 20 functions, with multimode functions accounting for a large proportion. The results of PWOA and MMSCA are worse than MPPE in most functions, but PPSO can achieve better optimization results in 7 functions. Though the intergroup communication strategy of PPSO can avoid premature convergence to a certain extent, it still has the drawback of decreased accuracy when solving complex problems. Therefore, its overall optimization performance is worse than MPPE.Table 5
Parameter settings of four parallel algorithms.
AlgorithmParameter settingsMPPENp = 100, groups = 5PPSONp = 100, groups = 5, c1 = 2, c2 = 2, inertia constant from 0.8 to 0.2,PWOANp = 100, groups = 5MMSCANp = 100, groups = 5Table 6
Optimization results for MPPE, PPSO, PWOA, and MMSCA over CEC 2013.
FunctionMPPEPPSOPWOAMMSCAf1−1.40E + 03−1.40E + 03−1.39E + 036.77E + 03f22.61E + 068.09E + 053.71E + 077.42E + 07f33.62E + 086.52E + 081.31E + 102.02E + 10f4−2.06E + 02−7.43E + 024.75E + 042.81E + 04f5−1.00E + 03−1.00E + 03−8.88E + 026.56E + 02f6−8.33E + 02−8.43E + 02−7.71E + 02−4.33E + 02f7−7.20E + 02−7.08E + 02−5.93E + 02−6.68E + 02f8−6.79E + 02−6.79E + 02−6.79E + 02−6.79E + 02f9−5.69E + 02−5.72E + 02−5.67E + 02−5.62E + 02f10−5.00E + 02−5.00E + 02−3.41E + 027.27E + 02f11−3.87E + 02−1.01E + 02−3.99E + 01−6.81E + 01f12−2.76E + 02−4.21E + 011.90E + 023.62E + 01f131.29E + 021.49E + 022.30E + 021.51E + 02f149.02E + 023.39E + 033.78E + 036.74E + 03f153.46E + 034.22E + 035.69E + 037.21E + 03f162.01E + 022.01E + 022.02E + 022.02E + 02f173.38E + 024.81E + 028.25E + 027.39E + 02f186.23E + 025.61E + 027.88E + 028.55E + 02f195.03E + 025.06E + 025.35E + 023.22E + 03f206.15E + 026.15E + 026.15E + 026.14E + 02f211.09E + 031.03E + 031.18E + 032.33E + 03f222.24E + 035.61E + 035.12E + 037.56E + 03f235.67E + 036.22E + 036.53E + 038.58E + 03f241.28E + 031.29E + 031.30E + 031.31E + 03f251.42E + 031.43E + 031.42E + 031.42E + 03f261.40E + 031.51E + 031.48E + 031.41E + 03f272.42E + 032.40E + 032.66E + 032.62E + 03f282.52E + 033.86E + 035.09E + 033.74E + 03Bold values represent the best results relative to other comparison methods.Table7 shows the statistics of optimization results of four algorithms on three types of functions. MPPE ranks first with the most wins compared to the other three parallel algorithms. Especially in the optimization results of multimode and combination problems, MPPE occupies a significant advantage.Table 7
Statistics of optimization results of four algorithms on three types of functions.
AlgorithmSingle-modemultimodeCombinationWinsRankingMPPE3116201PPSO462122MMSCA02133PWOA01124Table8 shows the results of Wilcoxon signed rank-sum test between MPPE and the other three algorithms. In these sets of statistical results, the advantages of MPPE for the other three parallel algorithms are not significant. Therefore, we can at least infer that in this benchmark suite test, there is no obvious gap in the optimization results of MPPE compared to most algorithms under the parameter settings of this experiment.Table 8
The results of Wilcoxon signed rank-sum test between MPPE and the other three algorithms.
AlgorithmR+R−p value+=−Dec.MPPE versus PPSO2451250.871387≈MPPE versus PWOA39100.392350≈MPPE versus MMSCA39600.0672440≈Figure6 shows convergence performance of the four parallel algorithms. We select three multimode and combination functions, respectively, for analysis. From the comparison of convergence speed, both MMSCA and PWOA are significantly slower than MPPE. PPSO and MPPE are similar in the early stage, but PPSO has a slower convergence rate in the late period. We can infer from this that MPPE is more likely to get rid of the local optimal solution and continue to seek the global minimum in the late period. Therefore, its overall convergence performance is better than the other three parallel algorithms.Figure 6
Convergence performance of four parallel algorithms. (a)f4, (b) f14, (c) f17, (d) f22, (e) f23, and (f) f26.
(a)(b)(c)(d)(e)(f)


## 4.3. Analysis of Algorithm Complexity

The maximum time complexity of PPE is described asO (p · n · I), where p is the total number of stick insect populations, n is the dimension of the problem, and I is the maximum number of iterations. MPPE adopted a parallel method on the basis of PPE, and each iteration is accompanied by the simultaneous evolution of each group of populations. So, the maximum time complexity of MPPE can be described as O ((p1 · n + p2 · n + · · · + pg · n) · I), where pi is the population size of the ith group and g is the number of groups. Since the number of populations in each group is equal to p/g, the maximum complexity of MPPE is described as O (p · n · I).Although the amount of calculation added by the intergroup communication strategy does not exceed the maximum time complexity, the actual running time of MPPE has increased considerably compared to PPE.


## 5. MPPE Applicating in IoT Electric Bus Scheduling

In this optimization algorithm applied to the bus scheduling experiment for urban waterlogging situation, the bus operating time is set to 6 am–9 pm, the total number of kilometers one way to 10 km, and the number of stations to 10; each site is namedS1 to S10. The data simulation of passenger flow is shown in Table 9.Table 9
Passenger flow in different time periods.
Period of timeS1S2S3S4S5S6S7S8S9S106:00–9:004011013173391061110920129:00–12:00410651071541178615110733812:00–16:0017732502898100138126101616:00–19:0014472154254177138162250902319:00–21:00706235484794133118In this experiment, MPPE was compared with PPE, PSO, SCA, and MCSCA [53]. In the search process, all algorithms find their current optimal solutions through each iteration. The optimal solution is the minimum value of the objective function of IoT electric bus scheduling. The position corresponding to the best solution is the time interval of bus departure in each time period. Therefore, these algorithms are all feasible in solving this problem, but their results are usually different.In the parameter settings, bothQ1 and Q2 are set to 1. The maximum number of iterations for each algorithm is set to 100. The population size of all algorithms is set to 30. This is because in solving practical problems, it is necessary to set a small number of iterations and populations to improve efficiency. The value of the bus departure time interval in each time period is accurate to one decimal place, and their range is controlled in 0–10. All the algorithms are run 10 times in this experiment. Finally, we calculate the average result, worst result, and best result of these algorithms. To make the experimental results more convincing, we set the weights w1 and w2 to three different groups of values. They are as follows: (1) w1 = 0.7 and w2 = 0.3, (2) w1 = 0.5 and w2 = 0.5, and (3) w1 = 0.3 and w2 = 0.7.Tables10 to 12 show the comparison of fitness values and solutions of these algorithms under different weights. Figures 7 to 9 show the convergence performance of these algorithms.Table 10
Comparison of results inw1 = 0.7 and w2 = 0.3.
AlgorithmAverage resultBest resultWorst resultScheduling schemeSCA2920.642893.122995.92(2.3 2.7 5.5 2.8 3.5)MCSCA2944.072878.632995.92(2.1 3.5 7.4 5.1 3.2)PSO2968.772895.503180.31(3.1 5.5 1.6 3.0 3.3)PPE2868.472866.522873.99(2.4 3.1 5.6 3.3 5.0)MPPE2866.752865.772868.36(2.5 3.1 5.6 3.3 4.6)Bold values represent the best results relative to other comparison methods.Table 11
Comparison of results inw1 = 0.5 and w2 = 0.5.
AlgorithmAverage resultBest resultWorst resultScheduling schemeSCA3238.803176.373288.67(2.9 4.3 4.2 3.1 3.2)MCSCA3291.973184.373296.17(2.0 3.6 5.0 3.7 3.3)PSO3905.683151.465526.75(8.2 8.2 7.9 1.5 9.6)PPE3139.953138.583141.18(2.5 3.0 4.6 3.2 4.0)MPPE3138.573137.833139.24(1.6 2.0 3.8 2.1 3.2)Bold values represent the best results relative to other comparison methods.Table 12
Comparison of results inw1 = 0.3 and w2 = 0.7.
AlgorithmAverage resultBest resultWorst resultScheduling schemeSCA3102.842912.693382.02(2.2 3.3 5.0 3.6 3.2)MCSCA3129.382937.533382.02(1.4 1.8 2.5 2.6 3.2)PSO4269.702925.666325.52(8.6 9.5 7.8 3.7 3.6)PPE2884.012883.212885.38(3.0 3.3 4.4 3.4 3.9)MPPE2882.872882.412883.75(2.2 2.5 3.5 2.7 3.2)Bold values represent the best results relative to other comparison methods.Figure 7
Convergence performances inw1 = 0.7 and w2 = 0.3.Figure 8
Convergence performances inw1 = 0.5 and w2 = 0.5.Figure 9
Convergence performances inw1 = 0.3 and w2 = 0.7.The above three sets of experiments show that the MPPE can perform better in different weight selection, and its average results are better than the other three algorithms in all three cases. From the point of view of the optimal value, although the three results of MPPE are slightly smaller than PPE, MPPE also has better stability. Compared with MPPE, PSO, MCSCA, and SCA all have a big gap. In terms of convergence performance, MPPE has a faster convergence rate in the early stage. Compared to PPE, MPPE almost find the optimal value before 20 iterations, and PPE tends to end convergence in the middle of iterations. Although PSO also has a fast convergence rate in the early stage, it does not perform well in the later stage and tends to fall into local optimum.In summary, the MPPE algorithm can effectively solve the IoT electric bus rainy days scheduling problem. This is mainly reflected in the fast convergence speed and good optimization accuracy. The result of the solution is also relatively stable, and it is not prone to large deviations. From the perspective of people’s experience, the scheduling scheme optimized by this algorithm is also reasonable.In order to analyze the relationship between the weight setting and the optimization result, we only use the MPPE algorithm to solve this problem and test all possible weight combinations. Table13 lists the rankings of the optimization results of all weight combinations and their corresponding scheduling schemes. The experimental results show that the theoretically best combination of weights is w1 = 0.1 and w2 = 0.9, because they achieve the best average results. However, decision-makers should make corresponding adjustments to the setting of weights based on actual conditions.Table 13
Ranking of average optimization results of MPPE under different weight combinations.
Weight combinationsAverage resultScheduling schemeRankingw1 = 0.1, w2 = 0.91861.91(5.1 6.0 9.6 6.7 8.6)1w1 = 0.9, w2 = 0.11890.99(2.7 2.9 3.4 2.9 3.2)2w1 = 0.8, w2 = 0.22494.98(3.3 3.9 7.3 4.2 6.7)3w1 = 0.2, w2 = 0.82518.76(2.5 2.7 3.5 3.8 3.2)4w1 = 0.7, w2 = 0.32866.75(2.5 3.1 5.6 3.3 4.6)5w1 = 0.3, w2 = 0.72882.87(2.2 2.5 3.5 2.7 3.2)6w1 = 0.6, w2 = 0.43070.65(1.9 2.4 4.6 2.6 3.8)7w1 = 0.4, w2 = 0.63079.02(2.1 2.4 3.8 2.6 3.2)8w1 = 0.5, w2 = 0.53138.57(1.6 2.0 3.8 2.1 3.2)9


## 6. Conclusions

According to the limitations of the PPE algorithm, this research made improvements based on multiple groups and multiple strategies. The experiments of the benchmark CEC 2013 proved that our proposed MPPE algorithm has good convergence speed and optimization accuracy. In addition, we apply this algorithm to the IoT electric bus scheduling problem and achieve a smaller loss value compared to PPE, PSO, SCA, and MCSCA algorithm.However, the MPPE algorithm still has shortcomings, which is mainly reflected in its long actual running time. In future research, we will consider this shortcoming and make further improvements. At the same time, some representative novel metaheuristic algorithms, such as MBO, SMA, GSK, and HHO, can also be used to solve optimization problems similar to bus scheduling. In the next step, we will consider combining these novel algorithms and expanding this type of optimization problem.



---

*Source: 1500646-2022-01-31.xml*