# Advanced Phasmatodea Population Evolution Algorithm for Capacitated Vehicle Routing Problem

Authors: Jiawen Zhuang; Shu-Chuan Chu; Chia-Cheng Hu; Lyuchao Liao; Jeng-Shyang Pan
Journal: Journal of Advanced Transportation
 (2022)

---

## Abstract

Capacitated Vehicle Routing Problem (CVRP) is difficult to solve by the traditional precise methods in the transportation area. The metaheuristic algorithm is often used to solve CVRP and can obtain approximate optimal solutions. Phasmatodea population evolution algorithm (PPE) is a recently proposed metaheuristic algorithm. Given the shortcomings of PPE, such as its low convergence precision, its nature to fall into local optima easily, and it being time-consuming, we propose an advanced Phasmatodea population evolution algorithm (APPE). In APPE, we delete competition, delete conditional acceptance and correspondingevolutionary trend update, and add jump mechanism, history-based searching, and population closing moving. Deleting competition and conditional acceptance and correspondingevolutionary trend update can shorten PPE running time. Adding a jump mechanism makes PPE more likely to jump out of the local optimum. Adding history-based searching and population closing moving improves PPE’s convergence accuracy. Then, we test APPE by CEC2013. We compare the proposed APPE with differential evolution (DE), sparrow search algorithm (SSA), Harris Hawk optimization (HHO), and PPE. Experiment results show that APPE has higher convergence accuracy and shorter running time. Finally, APPE also is applied to solve CVRP. From the test results of the instances, APPE is more suitable to solve CVRP.


---

## Body

## 1. Introduction

The population-based algorithm is a kind of metaheuristic algorithm, and it is widely used in transportation [1, 2]. Particle swarm optimization (PSO) [3, 4], equilibrium optimizer [5, 6], flower pollination algorithm (FPA) [7–9], fish migration optimization (FMO) [10], and quasiaffine transformation evolutionary (QUATRE) [11, 12] are some popular population-based algorithms. PPE, as a novel swarm intelligence algorithm, is proposed by Song [13], and the enlightenment of PPE is from the stick insect population’s evolution process.As a novel population-based algorithm, PPE was introduced in 2020. It has some merits, e.g., the principle of the algorithm is simple and easy to implement. However, there are also some disadvantages, e.g., it is time-consuming, it has low precision, and it falls into the local solution easily. Therefore, the improvement of PPE is a challenging and meaningful study.VRP was proposed by Dantzig and Ramser in 1959 and has been developed for many years [14], and as a branch of VRP, the related research of CVRP was very popular in transportation. CVRP refers to some customers with known demands served by some vehicles with certain capacity limits.CVRP is an important issue. On the one hand, it is a practical problem because many real-world problems can be abstracted into CVRP. For example, in a restaurant, a waiter needs to serve multiple tables to meet customers' order needs. When only one waiter is considered, the problem is abstracted into CVRP. Another example is that the heart of the human body supplies blood to other organs, and the blood vessels are regarded as pathways. After simplification and hypothesis, this process can be modeled as a CVRP. On the other hand, CVRP is also a challenging scientific issue. VRP is an NP-hard problem [15, 16] that is difficult to a use precise algorithm to get the optimal solution in finite time.Many scholars have studied CVRP. In 2006, Wu et al. used a new real number encoding method of PSO for solving VRP [17]. Chen et al. proposed a novel hybrid algorithm for CVRP, and in the hybrid algorithm, discrete PSO searches for optimal results and simulated annealing are used to jump out of the local optimum [18]. In 2009, Ai and Kachitvichyanukul proposed two solution representation methods, namely SR-1 and SR-2, for CVRP [19]. In 2015, Zhang and Lee proposed a routing-directed artificial bee colony algorithm to solve CVRP [20]. In 2019, Altabeeb et al. put forward an improved hybrid firefly algorithm for CVRP, and it was tested by 82 instances [21]. In 2020, Khairy et al. put forward the enhanced group teaching optimization algorithm to solve CVRP, and it was tested by 14 instances with promising time results [22]. In 2021, Fu et al. proposed the parallel equilibrium optimizer algorithm to solve CVRP [23].In this paper, the proposed APPE deletes competition, deletes conditional acceptance and corresponding evolutionary trend update, combines a novel jump mechanism, and adds a history-based searching for population’s position update and the population closing moving method for early phase searching. Then, the algorithms are tested by CEC2013 [24]. We also apply APPE to solve CVRP.The following is the remaining of this paper. The CVRP model is described in section2. Section 3 introduces PPE. APPE is described in section 4. In section 5, the experiments of CEC2013 functions and CVRP are described. In section 6, a conclusion is given.


## 2. CVRP

The objective of CVRP is to minimize the sum of distance. The path taken by each vehicle satisfies the capacity constraint. There is only one warehouse or depot. The model of CVRP is as follows:(1)minfX=∑k=1Kvehicle∑i=0Nc∑j=0Nccijkxijk.s.t.(2)xijk=1if  vehiclekgo from customeritoj,0otherwise,i=1,2,...,Nc;j=1,2,...,Nc;k=1,2,...,Kvehicle,(3)yik=1if  vehiclekserves customeri,0otherwise,i=1,2,...,Nc;k=1,2,...,Kvehicle,(4)∑i=1Ndiyik≤Qk,k=1,2,...,Kvehicle,(5)∑k=1Kytk=1,i=1,2,...,Nc,(6)∑i=1Nxijk=yjk,i=1,2,...,Nc;k=1,2,...,Kvehicle,(7)∑j=1Nxijk=yik,i=1,2,...,Nc;k=1,2,...,Kvehicle,(8)∑i=0Nxitk=∑j=0Nxtjk,t=1,2,...,Nc;k=1,2,...,Kvehicle,(9)∑i,j∈S×Sxijk≤S−1,S⊂1,2,...,N,S≠Φ,k=1,2,...,Kvehicle,where Nc is the customer number, Kvehicle is the vehicle number, cijk is the distance from the ith customer to the jth customer by the kth vehicle, and di is the ith customer’s demand. The kth vehicle’s capacity is Qk.Formula (1) is the objective function. Formulae (2) and (3) describe the decision variables. Formula (4) shows the vehicle’s capacity constraint. Equation (5) guarantees that every customer is served only once. Equations (6) and (7) ensure that one vehicle serves one custom. Equation (8) ensures the continuity of the route so that every vehicle coming in from the customer point would go out from that point, as well as back to the depot. Formula (9) is to eliminate the subloop.


## 3. PPE

PPE is inspired by the evolution process of the stick insect population. PPE initializesNp solutions randomly like other population-based algorithms. Every solution x has two properties, the first property is population number p, and the second property is population growth rate a. ev reflects the current evolution trend.Then, calculate the fitness value, and find the global optimum, which is denoted asgbest. The first k best solutions are stored in Ho, and k is equal to logNp+1.Next, in iteration, the new position is the sum of old position and evolution trend, which is as follows:(10)xt+1=xt+ev,where t is the current generation, and xt means the current solution’s position. Then, calculate new solutions’ fitness and update the global optimum gbest and Ho.When the new solution’s fitness is better, the current solution is absolutely replaced with it. Growth ratea, population quantity p, and population evolution trend ev are updated as follows:(11)at+1=at1+fxt−fxt+1fxt+1,(12)pt+1=at+1∗pt1−pt,(13)evt+1=α∗1−pt+1sHo,xt−xt+pt+1∗evt+β∗pt+1∗m.In equation (13), the population evolution trend ev consists of three parts. In the first part, sHo,xt means the nearest solution to xt in Ho. This part reflects similar evolution. The second part preserves the inertia of evolutionary trends. The final part is the mutation.When the new solution’s fitness is worse, the current solution is conditionally updated by the new solution. If a generated random number in [0, 1] is less than the population numberp, namely acceptance probability, the worse solution is accepted, and growth rate a and population quantity p are conditionally updated as equations (11) and (12). The evolution trend ev will change, irrespective of whether conditional acceptance probabilities are met, as follows:(14)evt+1=sHo,xt−xt∗rand+stt+1∗rdn,(15)stt+1=1tfxt+1−fmint+1fmaxt+1−fmint+1∗ct+1,(16)ct+1=0.99∗ct,where stt+1 controls the exploration range. c initializes to 2, and cis updated by using (16), when the new solution of the algorithm is a worse solution.Competition also affects population evolution trend. When two solutions’ distance is less thanG, competition will occur. Population quantity p and population evolution trend ev are updated in competition as follows:(17)pi=pi+aipi1−pi−pjfxjfxi,(18)evt+1=evt+1+fxj−fxifxjxj−xi,where xj is a random selected solution from Np−1 solution. The distance from xi is less than that from G. PPE’s pseudocode is shown in Figure 1.Figure 1
PPE’s pseudocode.


## 4. Advanced PPE

PPE also has shortcomings, such as low convergence precision, high consumption of time, and it falls into local optimum easily. Given the shortcomings of PPE, we propose APPE, which deletes competition, deletes conditional acceptance and correspondingevolutionary trend update, and adds jump mechanism, history-based searching, and population closing moving.


### 4.1. Without Competition

The competition mechanism exists in many algorithms. The imperialist competitive algorithm is based on imperial competition, in which weaker empires collapse and stronger empires take over colonies [25]. In the PPE, the competition mechanism is also considered. When the distance between the two solutions is too close, the population quantity p and population evolution trend ev will be updated. However, when the algorithm converges to the global or local optimal solution, this competition mechanism will affect its convergence tendency. At the same time, the calculation of particle distance takes time. Therefore, we remove the competition mechanism, thus effectively reducing the algorithm’s running time. It is equivalent to deleting the distxj,xi<G part of the PPE pseudo-code.


### 4.2. Without Conditional Acceptance and CorrespondingEvolutionary Trend Update

Some algorithms adopt the method of conditionally accepting a worse solution to improve the algorithm diversity, such as simulated annealing [26, 27]. Similarly, PPE will adopt a worse solution with probability, increasing the algorithm diversity and also increasing the algorithm running time. Therefore, we delete the conditional acceptance and corresponding evolutionary trend update of the PPE to save time consumption and maintain a certain convergence trend. It is equivalent to deleting the fnewx>fx part of the PPE pseudo-code.


### 4.3. Jump Mechanism

We introduce a kind of jump mechanism, increasing the algorithm’s probability of jumping out of local optimum. When the algorithm enters the late iteration, the optimal solution will either keep theINV generation unchanged or the standard deviation of the optimal solution in the INV generation will be less than the threshold value INVGate, and we let the solution jump by the following formula:(19)xnt+1=gbest+tanπr0−0.5∗gbest−xnt,where xnt+1 is a t+1 generation solution modified by the jump mechanism to replace the nth solution. xnt is a selected solution from population. gbest is current generation’s optimal solution. r0 is the random number, and it obeys uniform distribution from 0 to 1. In this paper, we use the jump mechanism to modify Jump Num=5 solutions, i.e., the worst solutions from the second to the sixth. When the probability is greater than rJump and the current population is not less than 8, we delete the worst solution. Moreover, when the number of Ho is more than the current population number, the number of Ho is reset again by k=logNp+1, and the redundant poor solutions are deleted as well.


### 4.4. History-Based Searching

Most swarm intelligence algorithms use the current information to interact with the information of the last generation, and the information before the last generation is lost, however, this information will also affect the convergence performance of the algorithm. Therefore, we design a history-based containerHA, whose capacity is HAnum.If the container is not full, the optimal new solution generated in each round adds to the container, which is the best particle ofxt+1 generated by equation (10). Otherwise, the global optimal solution gbest of the previous generation is used to replace any solution in the container. Meanwhile, in the second half of the iteration, if the random number generated is less than 0.5, the worst new solution generated in each round is used to replace any solution in the container, which is the worst particle of xt+1 generated by equation (10).Based on the above container, we design a history-based searching method, which is used to update the population. The history-based searching formula is as follows:(20)xHA,it+1=xHAbest+r1xit−xHArandom+r2xpt−xqt,where xHAt+1 is a new solution generated by history-based searching method, xHAbest is a solution randomly selected from the top 5 better solutions of HA. xHArandom is randomly selected from HA. xit means the ith solution of the current iteration, and xpt and xpt are the randomly selected solutions from the population that are different from xit. r1 is an indirect random number, and r1=0.1tanπr3−0.5. r2 and r3 are the direct random numbers, and they obey uniform distribution from 0 to 1.In this paper, the population position update of APPE combines PPE’s update with history-based searching, and the detailed equation is as follows:(21)newxit+1=xit+evit,if  tis less than H Anum or,rand is less than<0.5,xHAbest+r1xit−xHArandom,+r2xpt−xqt,otherwise,where t is the current generation. When a random number rand is less than 0.5 or the current generation is no more than HAnum, the population position is updated by equation (10) or equation (20).


### 4.5. Population Closing Moving

Swarm intelligence algorithm in the early stage is mainly exploration. Here, we useHA, and in the first half of the iteration cycle of the algorithm, when the random number is greater than 50%, the whole PPE population is moving toward the HA solution to produce new solutions. The moving formula is as follows:(22)PCMxt+1=xt+step∗xt−xHAt+1,(23)step=2∗rdn1rdn2∗rand,where xt and xHAt+1 are the whole population, rdn1 and rdn2 are random number matrices that follow standard normal distribution, and rand is the random number matrix that follows uniform distribution from 0 to 1. The number of rows in xt, xHAt+1, rdn1, rdn2, and rand matrix is the population size, and the number of columns is the dimension. The ∗ symbol is the multiplication of the corresponding positional elements of the matrix and is neither matrix multiplication nor convolution. Notice that 2∗rdn1 means that every element of the matrix rdn1 is multiplied with 2. Then, we compare the new solution by equation (21)with thenew solutiongenerated by moving method (18) and retain the excellent solution as the new solution.


### 4.6. APPE

In this paper, we combine the above methods to form APPE. The following are the detailed steps of APPE.(1)
Initialization:Np stick insect populations xt are initialized, and p, a, and ev of each stick insect are initialized to 1/Np, 1.1, and 0, respectively. Initialize the parameter k of Ho, and k=logNp+1. Initialize parameter INV=4 of jump mechanism and threshold value INVGate=10−6. Initialize parameter HAnum of history-based archive HA and HAnum=Np. Initialize current iteration t=1 and the maximum iteration MAXGENS. Calculate fitness fxt. Update the global best solution gbest and global best value gbestval. If t=1, initialize Ho with the current best k solutions. The global best solution gbest is put into HA.(2)
Jump mechanism: If the global best solutiongbest has kept the INV generation unchanged and the algorithm enters the late iteration or the standard deviation of the optimal solution in the INV generation is less than the threshold value INVGate, then the jump mechanism is applied. Using (19) to modify worse solutions from the second to the sixth. If a uniform random number is larger than probability rJump and the current population number is not less than 8, then delete the worst solution of PPE population and HA solutions. Moreover, when the number of Ho is more than the current population number, the number of Ho is reset again by k=logNp+1, and the redundant poor solutions are deleted.(3)
Population position updating: In our algorithm, equation (21) is used for position updating. New solution is newxit+1. Calculate fitness fnewxt+1.(4)
Population closing moving: In the first half of the iteration cycle of the algorithm, when the random number is greater than 0.5, the whole PPE population is moving toward theHA solution, and new solutions PCMxt+1 are generated by equation (22). Calculate fitness fPCMxt+1. Then, compare the new solution generated by equation (22) with the new solution generated by equation (21), the good one is reserved as current iteration’s new solution.(5)
HA and Ho update: IfHA is not full, HA is filled one-by-one with optimal new solution of each round. If t>HAnum, the gbest of each round replaces the random one solution of HA. When the number of iterations is more than half, the algorithm has a 50% chance of randomly replacing one of the HA solutions with the worst new solution per round. Update the global best solution gbest and the global best value gbestval. If t>1, the current best k solutions are comparing with the corresponding solution of Ho, the good ones replaces the solution in Ho.(6)
Absolutely accept: When the new solution’s fitness is better than that of the old one, accept it, and updatep, a, and ev of each stick insect by equations (11)–(13).(7)
Parameter border check: Ifpi≤0, ai≤0, or ai>4, reinitialize the corresponding stick insect.(8)
Termination: Steps 2 to 7 are repeated until reaching the maximum generation. Finally, record the best fitnessgbestval and the best solution gbest.


### 4.7. Setting for CVRP

We adopt the SR-1 method for solution representation, which means that the dimension of the PPE’s particle isn + 2 m [19]. The first n dimensions of the solution are related to the customer, and each dimension represents the corresponding customer. The smaller the value of this dimension, the higher the priority of the customer. Thus, the priority list of the customer can be obtained. The last dimension of 2 m represents the coordinates of m vehicles. According to the distance of coordinates, the priority matrix of vehicles for each customer can be obtained. Arrange customer points to vehicle route one byone according to customer priority order. For a customer point, which vehiclepath it is arranged into is determined by the vehicle priority matrix.According to the priority order of vehicles, arrange a customer point into thevehicle path with higher priority. If the current vehicle path meets thecapacity constraint, arrange the customer in this vehicle path. If the currentvehicle path exceeds the capacity constraint, place the customer in the lowerpriority vehicle path. Then, the corresponding path is formed. The example of SR-1 is as shown in Figure 2.Figure 2
SR-1 method example.We use some local searching methods to optimize the routes. These methods are divided into inter-route optimization and intra-route optimization. Inter-route optimization mainly consists of three-point communication and deleting-adding communication, and the search time is the sum of the instance’s points and vehicles. Three-point communication refers to the random selection of three paths in the solution. A point of each path is randomly selected, and the points of the path are exchanged in the order of 3, 1, and 2. If the newly generated three paths are better than the original three paths, then the original path will be replaced [28]. Deleting-adding communication refers to the random selection of two paths in the solution, with a point randomly selected in each path. One of the paths deletes the selected points and adds the selected points to the other path. If the new two paths are better than the original two paths, then the original path is replaced [29]. Intra-route optimization consists of path scrambling, path inversion, and path 2-point swapping. The number of executions of these methods is the square of the number of points in each path of the solution. Path scrambling refers to the random rearrangement of paths, except the starting and ending points, which are rearranged using the randperm function of Matlab. If the generated new path is better than the best solution, then it replaces the original best solution, and the next searching will still change the original path, however, the comparison object is the best solution. Path inversion means that two points of the path are selected each time, and then the paths between the two points are rearranged in the reverse order. If the new solution produced is good, then retain it as the best solution for the next search [28]. Path 2-point swapping means that two points of the path are selected each time, and then the two points are exchanged. If the new solution produced is good, then retain it as the best solution for the next search [28].


## 4.1. Without Competition

The competition mechanism exists in many algorithms. The imperialist competitive algorithm is based on imperial competition, in which weaker empires collapse and stronger empires take over colonies [25]. In the PPE, the competition mechanism is also considered. When the distance between the two solutions is too close, the population quantity p and population evolution trend ev will be updated. However, when the algorithm converges to the global or local optimal solution, this competition mechanism will affect its convergence tendency. At the same time, the calculation of particle distance takes time. Therefore, we remove the competition mechanism, thus effectively reducing the algorithm’s running time. It is equivalent to deleting the distxj,xi<G part of the PPE pseudo-code.


## 4.2. Without Conditional Acceptance and CorrespondingEvolutionary Trend Update

Some algorithms adopt the method of conditionally accepting a worse solution to improve the algorithm diversity, such as simulated annealing [26, 27]. Similarly, PPE will adopt a worse solution with probability, increasing the algorithm diversity and also increasing the algorithm running time. Therefore, we delete the conditional acceptance and corresponding evolutionary trend update of the PPE to save time consumption and maintain a certain convergence trend. It is equivalent to deleting the fnewx>fx part of the PPE pseudo-code.


## 4.3. Jump Mechanism

We introduce a kind of jump mechanism, increasing the algorithm’s probability of jumping out of local optimum. When the algorithm enters the late iteration, the optimal solution will either keep theINV generation unchanged or the standard deviation of the optimal solution in the INV generation will be less than the threshold value INVGate, and we let the solution jump by the following formula:(19)xnt+1=gbest+tanπr0−0.5∗gbest−xnt,where xnt+1 is a t+1 generation solution modified by the jump mechanism to replace the nth solution. xnt is a selected solution from population. gbest is current generation’s optimal solution. r0 is the random number, and it obeys uniform distribution from 0 to 1. In this paper, we use the jump mechanism to modify Jump Num=5 solutions, i.e., the worst solutions from the second to the sixth. When the probability is greater than rJump and the current population is not less than 8, we delete the worst solution. Moreover, when the number of Ho is more than the current population number, the number of Ho is reset again by k=logNp+1, and the redundant poor solutions are deleted as well.


## 4.4. History-Based Searching

Most swarm intelligence algorithms use the current information to interact with the information of the last generation, and the information before the last generation is lost, however, this information will also affect the convergence performance of the algorithm. Therefore, we design a history-based containerHA, whose capacity is HAnum.If the container is not full, the optimal new solution generated in each round adds to the container, which is the best particle ofxt+1 generated by equation (10). Otherwise, the global optimal solution gbest of the previous generation is used to replace any solution in the container. Meanwhile, in the second half of the iteration, if the random number generated is less than 0.5, the worst new solution generated in each round is used to replace any solution in the container, which is the worst particle of xt+1 generated by equation (10).Based on the above container, we design a history-based searching method, which is used to update the population. The history-based searching formula is as follows:(20)xHA,it+1=xHAbest+r1xit−xHArandom+r2xpt−xqt,where xHAt+1 is a new solution generated by history-based searching method, xHAbest is a solution randomly selected from the top 5 better solutions of HA. xHArandom is randomly selected from HA. xit means the ith solution of the current iteration, and xpt and xpt are the randomly selected solutions from the population that are different from xit. r1 is an indirect random number, and r1=0.1tanπr3−0.5. r2 and r3 are the direct random numbers, and they obey uniform distribution from 0 to 1.In this paper, the population position update of APPE combines PPE’s update with history-based searching, and the detailed equation is as follows:(21)newxit+1=xit+evit,if  tis less than H Anum or,rand is less than<0.5,xHAbest+r1xit−xHArandom,+r2xpt−xqt,otherwise,where t is the current generation. When a random number rand is less than 0.5 or the current generation is no more than HAnum, the population position is updated by equation (10) or equation (20).


## 4.5. Population Closing Moving

Swarm intelligence algorithm in the early stage is mainly exploration. Here, we useHA, and in the first half of the iteration cycle of the algorithm, when the random number is greater than 50%, the whole PPE population is moving toward the HA solution to produce new solutions. The moving formula is as follows:(22)PCMxt+1=xt+step∗xt−xHAt+1,(23)step=2∗rdn1rdn2∗rand,where xt and xHAt+1 are the whole population, rdn1 and rdn2 are random number matrices that follow standard normal distribution, and rand is the random number matrix that follows uniform distribution from 0 to 1. The number of rows in xt, xHAt+1, rdn1, rdn2, and rand matrix is the population size, and the number of columns is the dimension. The ∗ symbol is the multiplication of the corresponding positional elements of the matrix and is neither matrix multiplication nor convolution. Notice that 2∗rdn1 means that every element of the matrix rdn1 is multiplied with 2. Then, we compare the new solution by equation (21)with thenew solutiongenerated by moving method (18) and retain the excellent solution as the new solution.


## 4.6. APPE

In this paper, we combine the above methods to form APPE. The following are the detailed steps of APPE.(1)
Initialization:Np stick insect populations xt are initialized, and p, a, and ev of each stick insect are initialized to 1/Np, 1.1, and 0, respectively. Initialize the parameter k of Ho, and k=logNp+1. Initialize parameter INV=4 of jump mechanism and threshold value INVGate=10−6. Initialize parameter HAnum of history-based archive HA and HAnum=Np. Initialize current iteration t=1 and the maximum iteration MAXGENS. Calculate fitness fxt. Update the global best solution gbest and global best value gbestval. If t=1, initialize Ho with the current best k solutions. The global best solution gbest is put into HA.(2)
Jump mechanism: If the global best solutiongbest has kept the INV generation unchanged and the algorithm enters the late iteration or the standard deviation of the optimal solution in the INV generation is less than the threshold value INVGate, then the jump mechanism is applied. Using (19) to modify worse solutions from the second to the sixth. If a uniform random number is larger than probability rJump and the current population number is not less than 8, then delete the worst solution of PPE population and HA solutions. Moreover, when the number of Ho is more than the current population number, the number of Ho is reset again by k=logNp+1, and the redundant poor solutions are deleted.(3)
Population position updating: In our algorithm, equation (21) is used for position updating. New solution is newxit+1. Calculate fitness fnewxt+1.(4)
Population closing moving: In the first half of the iteration cycle of the algorithm, when the random number is greater than 0.5, the whole PPE population is moving toward theHA solution, and new solutions PCMxt+1 are generated by equation (22). Calculate fitness fPCMxt+1. Then, compare the new solution generated by equation (22) with the new solution generated by equation (21), the good one is reserved as current iteration’s new solution.(5)
HA and Ho update: IfHA is not full, HA is filled one-by-one with optimal new solution of each round. If t>HAnum, the gbest of each round replaces the random one solution of HA. When the number of iterations is more than half, the algorithm has a 50% chance of randomly replacing one of the HA solutions with the worst new solution per round. Update the global best solution gbest and the global best value gbestval. If t>1, the current best k solutions are comparing with the corresponding solution of Ho, the good ones replaces the solution in Ho.(6)
Absolutely accept: When the new solution’s fitness is better than that of the old one, accept it, and updatep, a, and ev of each stick insect by equations (11)–(13).(7)
Parameter border check: Ifpi≤0, ai≤0, or ai>4, reinitialize the corresponding stick insect.(8)
Termination: Steps 2 to 7 are repeated until reaching the maximum generation. Finally, record the best fitnessgbestval and the best solution gbest.


## 4.7. Setting for CVRP

We adopt the SR-1 method for solution representation, which means that the dimension of the PPE’s particle isn + 2 m [19]. The first n dimensions of the solution are related to the customer, and each dimension represents the corresponding customer. The smaller the value of this dimension, the higher the priority of the customer. Thus, the priority list of the customer can be obtained. The last dimension of 2 m represents the coordinates of m vehicles. According to the distance of coordinates, the priority matrix of vehicles for each customer can be obtained. Arrange customer points to vehicle route one byone according to customer priority order. For a customer point, which vehiclepath it is arranged into is determined by the vehicle priority matrix.According to the priority order of vehicles, arrange a customer point into thevehicle path with higher priority. If the current vehicle path meets thecapacity constraint, arrange the customer in this vehicle path. If the currentvehicle path exceeds the capacity constraint, place the customer in the lowerpriority vehicle path. Then, the corresponding path is formed. The example of SR-1 is as shown in Figure 2.Figure 2
SR-1 method example.We use some local searching methods to optimize the routes. These methods are divided into inter-route optimization and intra-route optimization. Inter-route optimization mainly consists of three-point communication and deleting-adding communication, and the search time is the sum of the instance’s points and vehicles. Three-point communication refers to the random selection of three paths in the solution. A point of each path is randomly selected, and the points of the path are exchanged in the order of 3, 1, and 2. If the newly generated three paths are better than the original three paths, then the original path will be replaced [28]. Deleting-adding communication refers to the random selection of two paths in the solution, with a point randomly selected in each path. One of the paths deletes the selected points and adds the selected points to the other path. If the new two paths are better than the original two paths, then the original path is replaced [29]. Intra-route optimization consists of path scrambling, path inversion, and path 2-point swapping. The number of executions of these methods is the square of the number of points in each path of the solution. Path scrambling refers to the random rearrangement of paths, except the starting and ending points, which are rearranged using the randperm function of Matlab. If the generated new path is better than the best solution, then it replaces the original best solution, and the next searching will still change the original path, however, the comparison object is the best solution. Path inversion means that two points of the path are selected each time, and then the paths between the two points are rearranged in the reverse order. If the new solution produced is good, then retain it as the best solution for the next search [28]. Path 2-point swapping means that two points of the path are selected each time, and then the two points are exchanged. If the new solution produced is good, then retain it as the best solution for the next search [28].


## 5. Experiment and Application

In this section, we utilized CEC2013 to test our proposed algorithm, as shown in Table1. APPE experiment results are shown in Tables 2–13. Then, the CVRP results are as shown in Tables 14–15. These are the results APPE compares with DE, SSA, PSO, and PPE. We also compare APPE with some existing work in Tables 6–19.Table 1
Benchmark functions of CEC2013 (Test APPE’s performance).
No.TypeOptimumNo.TypeOptimumF1Unimodal−1400F15BasicMultimodal100F2−1300F16200F3−1200F17300F4−1100F18400F5−1000F19500F6BasicMultimodal−900F20600F7−800F21Composition700F8−700F22800F9−600F23900F10−500F241000F11−400F251100F12−300F261200F13−200F271300F14−100F281400Table 2
Comparison of the best result of 51 runs on 10D in 28 benchmark functions.
FunDESSAHHOPPEAPPEF1739.7907401.5480221.5277E-060F23699523.58916892.6651675269.8416924.656268.614074F3588747385.113.387693468959621174894.97030.000959781F47128.473988.325787833.35511121.045168.06974F550.3104039.125728.5511E-051.05729E-11F668.950870.01099234.2165618.1355E-061.07889E-09F755.716415.079947.665967.275980.44489F820.198320.138520.161820.132620.2161F97.21382.784025.17371.908820.822382F1078.528040.24396913.607270.1357690.0270174F1146.21143.9798429.02325.1115E-062.69438E-11F1255.753915.919324.941914.92454.9748F1361.567223.585637.874616.09058.16871F14761.0059635.1763369.54088137.240412.39519F151162.7414515.11843208.5453225.1287458.76209F160.7801440.1903840.2609760.102840.679173F1789.5563119.021741.663810.44375.15832F1891.6757431.0386934.025712.898619.6821F1911.14840.3515823.3190640.06063830.348941F203.608323.117283.226221.835061.2217F21454.7408200306.5969100.0283400.1939F221287.114178.2702291.1866515.4041914.11783F231497.5974765.85882986.5552973.788553271.18111F24184.698132.6267124.3565138.2729105.7783F25173.5373208.2578219.6212132.3753109.5371F26168.4389119.8991132.0062119.9186105.9698F27560.8726312.6709415.0833307.2788301.8725F28476.735100734.1271100.0221100W/D/L0/0/283/0/251/0/276/0/2220/0/8Table 3
Comparison of the mean result of 51 runs on 10D in 28 benchmark functions.
FunDESSAHHOPPEAPPEF11416.57871.605E-13811.94169.9958E-062.675E-14F210084933.05197537.9456878233.5178209.70766115.1032F331186374831529093317255467596116898667944921.1013F412971.23537083.665115628.6068641.8292702.1065F583.72381.226E-13398.33620.000375394.16834E-10F6116.016812.8841107.456418.62647.63911F778.735884.1336105.4137.946216.6702F820.332720.347220.316820.330320.4067F98.943737.228688.713244.846413.76595F10181.50712.21159178.78060.6279550.206199F1169.368316.837973.72860.2545393.49337F1279.657959.281480.433238.903217.5971F1380.036762.532397.056236.264229.1881F141314.4366371.44281017.8572354.5957286.6114F151529.77661120.4131872.7005715.37291080.2465F161.134410.6617320.7479680.3575941.15523F17125.390684.223996.260511.337819.3253F18129.3592139.697695.317831.900640.797F1935.14231.96173150.01350.8069230.900422F203.974653.730393.972933.019312.82778F21507.7433396.2685413.4744388.4232400.1939F221603.7803544.84181458.3753362.7106296.2929F231842.08911518.76861649.84811124.13411095.8663F24223.9939221.1283226.6401216.8546198.7732F25216.4075222.4582228.3634212.0031192.7499F26196.4968197.3708232.3701161.1619154.8035F27629.3467562.4606638.4348393.6886387.5239F28746.0777699.0044912.4083578.1929344.4934W/D/L0/0/281/0/271/0/278/0/2018/0/10Table 4
Comparison of the standard deviation result of 51 runs on 10D in 28 benchmark functions.
FunDESSAHHOPPEAPPEF1336.292311.1409E-13840.79066.8679E-067.3986E-14F23591008.967126630.8174663751.7743253.97336050.4934F3101719441635713194846440050561832524053551542.55F43315.336883588.5032250.98706404.5624745.7658F517.89965.4962E-14321.91830.000185964.76424E-10F622.9635818.244956.8119927.84178.28299F712.451839.820638.7768719.445213.3872F80.06483980.06605830.08030620.0847760.0790714F90.4899281.43371.171971.46011.48489F1049.445431.39021120.77780.3649350.115752F118.127739.7768328.79590.6844812.17383F129.147227.300931.862115.42187.28016F138.7624522.190828.248711.371210.3039F14162.82672204.7426238.51942141.844190.2989F15136.11119289.33376279.989294.5977301.37034F160.1785960.3073420.2260420.1850980.212344F1713.7023545.171126.95610.5959987.21938F1815.412628.0324824.99268.609157.23762F1919.65141.16874239.76250.3284380.509409F200.1563750.262370.3413580.4153010.609363F2125.6676928.0327524.768658.841343.21555E-14F22139.6671261.2185414.21438178.3056182.963F23142.08612346.663349.63326388.70003494.49528F249.18618713.3951517.4001216.2122932.52391F2514.018084.6037863.63916515.4136432.96771F267.59763556.2449864.9427434.5517441.58459F2722.3715885.942889.9454333.960941.40027F28130.9133265.645689.81761225.5822191.5919W/D/L12/0/161/0/272/0/265/0/238/0/20Table 5
Comparison of the average running time result of 51 runs on 10D in 28 benchmark functions.
FunDESSAHHOPPEAPPEF10.7274365310.82878591.156850427.181155740.671487292F20.7910509040.9248536351.34395427.200132870.70339359F30.7748873430.9070824241.298661657.213059810.790544096F40.7636150470.9032574611.301241197.148540950.386089429F50.7640201710.8875316241.269403917.261793160.686430051F60.7269798040.8449204471.168956547.28062070.670751492F70.8941484611.0401955141.609014547.411897310.803711176F80.8555799471.0187263751.544195057.221933550.322570457F92.2198339762.6417048354.920325948.677495072.310656547F100.7733728860.8917853631.286161397.276501890.668267453F110.8166518650.9620519611.47699697.275901960.746390108F120.8437913840.996919121.514431257.497118570.609939676F130.839976190.984042011.485910377.38283660.510813414F140.8227895350.9438987391.476548967.283915740.582743498F150.8297171690.9572121751.481875127.387181680.461557804F161.834200292.1801531144.00384328.255445751.247958082F170.7816333940.9074792761.369328767.242346320.577252965F180.795143790.9329338551.422435967.203003380.388129488F190.7439866080.8624466311.276234147.295076050.715902753F200.8015603510.9167309061.43201297.306891160.494742363F211.0653217251.2630618471.989974947.577307830.883767925F221.1592165511.3201341822.282462037.585814110.931372729F231.1685612781.3484617512.306425767.610827380.817745671F242.5716084243.0247796025.67088388.990849362.541635441F252.5911452333.0133620065.710975138.914839092.597728576F262.7847301843.3230312246.209881499.097191492.571828318F272.7458373393.2615299556.119411559.109133972.372727906F281.2885573141.5233473162.5968397.629356411.087740337W/D/L3/0/250/0/280/0/280/0/2825/0/3Table 6
Comparison of the best result of 51 runs on 30D in 28 benchmark functions.
FunDESSAHHOPPEAPPEF120965.51172.2737E-133115.09873.4641E-052.2737E-13F2184302669.7556561.90242409000.721551822.0836796.10533F39930487222010402522.9241298679581427779211979.52113F447671.138417895.280541958.6448436.4169277.24218F52736.18584.5475E-13845.642180.001221542.01521E-09F62192.63672.59305371.839710.3045441.69745E-05F7326.5177107.2508227.729545644.620639.1504F820.850520.742820.704220.811920.7702F936.672327.555934.163623.381715.4945F102740.00710.0640834544.297080.07026746.77581E-08F11475.354593.52546342.58215.12217.9093F12536.0034303.4593288.8458251.734972.63182F13477.1505333.4405499.8886261.1692190.6686F146284.60221787.29562549.475766.94606431.50235F156306.84342999.23993353.07792500.50425525.0534F161.640390.2675070.8224580.1935881.58162F171008.295287.815323.72143.634665.20754F181102.4916350.691487.3008174.6342156.3594F1943694.729389.84876342.974352.917892.43391F2014.52112.680114.509713.86549.58436F212801.7822100929.77219100.2957100F226985.88461760.62134701.2418592.84675362.0814F237504.10033830.26333760.24523520.52783135.9944F24325.3054282.8699307.7325251.8537234.3891F25336.8065291.219310.1113308.9248270.7536F26216.1884200.0521204.6498200.0465200.0016F271365.8604936.365591246.5007945.20441746.8349F283662.60683003717.7686100.27997100W/D/L0/0/282/0/261/0/274/0/2422/0/6Table 7
Comparison of the mean result of 51 runs on 30D in 28 benchmark functions.
FunDESSAHHOPPEAPPEF132193.56196.5537E-139711.91218.1178E-054.6812E-13F2368242452.82081301.22179774792.83096187.31126305.9182F37.10045E + 116984479959.77373E + 1343447067431758287.64F475322.053628653.093752077.4646930.9191330.2804F54522.4741.0867E-112695.52440.001954015.23523E-08F63552.496130.1751758.403959.19026.12643F7747.6163211.4113108509.308894.805284.0757F820.954620.92220.900520.944320.9755F939.27633.91539.548730.82124.7972F104134.02670.2117341991.41490.441580.0650486F11579.6098240.4308584.391628.126333.9158F12628.6948511.8694606.0292353.5071183.0126F13624.5928440.3657701.2616379.6572266.1043F147069.16582731.9094328.81021243.08581814.8754F157431.22374754.64434829.55913951.55326617.3184F162.492941.251221.569210.7450322.49028F171262.8753652.2582666.931562.4704108.3917F181269.4583702.0829684.1028287.4171300.5752F19167474.771919.3424354.86656.468735.63526F2014.901814.758914.837714.679712.2536F213210.8721364.22931623.5516315.6636320.9034F227723.81743374.47726251.95551336.6024940.461F238097.50945851.25576602.76445180.48456658.3955F24334.942303.6476339.2056286.0378263.803F25353.4227314.6729343.4621348.9108297.3444F26241.288363.4894384.4514315.0175200.0092F271428.77731254.88791429.86481145.826927.6687F284413.0773213.39134978.16593248.566690.8847W/D/L0/0/281/0/271/0/279/0/1917/0/11Table 8
Comparison of the standard deviation results of 51 runs on 30D in 28 benchmark functions.
FunDESSAHHOPPEAPPEF13909.092452.4761E-133561.67642.2148E-051.5362E-13F274221490.37941488.2689397375.81816426.96683074.86122F37.20796E + 1110655944573.23802E + 1435894429985733576.72F48466.662614475.097933760.44355309.98961143.5652F5755.383391.8485E-111543.13810.000504025.65084E-08F6640.6405524.74721147.089425.22446.49659F7393.6556106.0421271133.151219.810726.8212F80.04912540.05731010.07189020.05322190.0504813F91.15583.411882.122932.95273.79688F10540.800160.114618984.780420.2203420.0490094F1144.5748875.69394105.74537.267759.97949F1240.49799134.3097119.101153.3342850.99063F1346.126776.2290486.9933248.5520540.97781F14262.46923535.39708819.82348236.311611441.8054F15271.96764730.40653835.72922627.96769417.02913F160.3206080.5472210.430010.3000760.346913F17107.2886136.1497.299827.7440721.66193F1878.052688126.310583.3382653.9248741.8762F1967584.435325.634793353.46272.113751.76896F200.1142220.5290390.2315210.2825590.684561F21172.348796.53369301.7930472.477985.50782F22269.7388869.43735845.09278295.70899339.5195F23243.52231856.053851075.8917756.675461221.6536F244.0869339.67898818.723316.0253714.32264F254.96939211.8376516.502421.2016313.09351F268.45801566.5776764.7704582.447040.005305383F2727.630268109.7561575.8238282.79767989.73993F28269.106141467.6047630.94737773.56802916.4915W/D/L11/0/171/0/270/0/287/0/219/0/19Table 9
Comparison of the average running time result of 51 runs on 30D in 28 benchmark functions.
FunDESSAHHOPPEAPPEF12.7338098782.654370044.170978921.87217392.407070994F23.2380937763.283683665.5226788922.18061763.242242859F33.3875444083.449857815.7978001322.19865482.802126447F43.0339381182.989337815.0489591521.83321921.460134582F53.0607705783.055567574.9629518422.22944682.630876359F62.9121885572.896672594.502341822.18734983.894232227F74.5858079164.731270619.0565428123.58092114.413959241F83.9544712064.070662237.3325540822.91746461.585859245F917.0568929818.906026540.039849135.277172912.41038709F103.3346386733.298205115.433928222.27564342.716332702F113.4442129143.488151265.9963584422.30468793.0724273F123.9813179334.038490177.2672799322.8860672.921447771F133.9769718414.007293057.1055856622.98367651.930308529F143.6857800823.674975356.6027683522.71891492.713648625F153.8301015223.860781746.6552520922.84908061.75100859F1613.4532651514.783775329.286875831.70409658.918082525F173.1475157163.215496385.0803039122.19238512.652192106F183.5000813333.595703555.8372695122.34677611.447078869F193.0118894863.045116994.6626267721.98629493.609727229F203.6701955293.777163286.9257292322.3901391.774093445F215.84823226.2726192910.551872724.36385564.451286106F226.2329056576.5132334712.121765324.74531435.447029629F236.7910291717.0867931713.323621825.18820664.829456082F2420.0996206922.232415743.216407137.709773214.63043557F2520.083876422.415029242.326073237.724848114.5165233F2621.6766521724.59526446.701052339.209725424.28157111F2721.2382378624.265919446.054719538.934331115.58041748F288.2594791298.9604721616.544483926.67935656.434003169W/D/L3/0/251/0/270/0/280/0/2824/0/4Table 10
Comparison of the best result of 51 runs on 50D in 28 benchmark functions.
FunDESSAHHOPPEAPPEF168441.68776.8212E-134421.53189.1774E-051.13687E-12F2796828451.2897706.1727754539.42311976.79114810.9289F34.11102E + 1136730944.54500933989364993978.43218012.379F4103396.92733164.341656242.6043233.6512428.55484F59117.133172.2907E-09991.739750.002290622.2956E-07F66066.862429.1158444.751439.71670.128249F7321.5459796.81021282.55983370.8556556.4843F821.048721.05120.960121.025721.0471F970.051649.870665.890648.080639.9872F108540.849960.0394587760.253670.8570533.88815E-05F111120.4763382.0615591.09969.9343262.6823F121157.4674587.01751695.9241461.6641204.9601F131132.7369640.2518953.41855566.5412421.8479F1412375.23433470.87895201.69471011.18591039.3238F1513171.17876238.72387676.889955808.511511569.9181F162.682480.6898051.272950.5461512.42801F172686.1285502.0316782.54144112.7755155.0626F182698.9651987.4102870.71601451.2733360.0513F19466278.764724.3778912.661677.49997.79172F2024.444821.948623.697521.814818.6627F215875.3627836.44251831.4087836.4425100F2213466.99145826.12747811.750431936.86121064.7735F2314407.61678117.391489107.614157311.615538301.79767F24432.5152371.4055415.414327.2399310.6605F25488.8236387.3883412.8656434.7963380.0998F26296.6734440.0132469.8953200.2743200.0272F272321.10441775.59012151.73051692.66551292.2378F287644.27444006451.9363474.57092400W/D/L0/0/283/0/251/0/277/0/2118/0/10Table 11
Comparison of the mean result of 51 runs on 50D in 28 benchmark functions.
FunDESSAHHOPPEAPPEF180496.62751.2528E-129600.28180.000176493.49487E-11F211700224412226137.48192268997.54042717.04400359.6315F34.40463E + 1213695739072.04922E + 1139203771469788181.12F4136314.937953168.68869134.0056674.85221286.1218F515201.55391.821E-081625.46420.003747271.4891E-06F67949.010972.5883902.915986.285935.1058F71086.8641192.468511581.7115116.533583.5833F821.135321.131721.117521.117721.1504F972.94165.247473.297257.876152.102F1010371.62310.2023451961.6691.520740.0368955F111327.7597547.3071745.3906110.059393.4338F121336.68871014.754916.3933570.8822412.2794F131324.4015956.33051168.9616725.9276536.2261F1413453.77465825.04967675.38361963.85422825.8275F1514290.10248553.1910356.58287728.055612892.3516F163.285181.833192.272071.23823.31238F173020.4296981.10951024.8344146.7249226.2728F183053.12011155.85841096.2182593.7946627.5738F191429662.2649.6272624.759113.258612.7787F2024.878924.383524.48524.091421.9659F217181.9716998.96023051.678948.5251870.4084F2214742.48347413.621410468.55073276.63932423.8416F2315334.056710546.075112655.704110424.390213606.4302F24464.8197391.9212470.8258373.7801342.4159F25502.6936415.216459.7346504.9336408.2602F26368.9144470.2997495.343411.5417283.8361F272446.81662076.07092433.07262107.72861650.236F288778.85275148.50579186.80975936.96571470.4027W/D/L0/0/282/0/261/0/277/0/2118/0/10Table 12
Comparison of the standard deviation result of 51 runs on 50D in 28 benchmark functions.
FunDESSAHHOPPEAPPEF15405.613773.9217E-132679.95054.1786E-057.0273E-11F2170612616.4824253.49489445562.681007133.92179412.3457F33.2854E + 1215575684394.01457E + 1137901685094471867.3F411084.6385911809.08845827.04834184.5265668.48665F52116.939951.7468E-08324.030130.000840211.5852E-06F6955.6089131.5493456.938132.670418.3843F7525.9039679.7054713589.323221.0432614.1085F80.03635170.03642290.04818150.03655930.042277F91.363034.678543.154563.724365.71436F10882.7476010.115331607.185730.2563660.024425F1181.15735892.0294370.6830820.8464815.7099F1264.758226116.4017997.1328456.8378296.05942F1377.218129183.093294.73355869.596966.06756F14326.0089251029.61851404.319399.016542150.2895F15393.289928960.325271506.75168942.05543609.042346F160.2394730.611870.5319210.3504570.371027F17146.22569147.649475.29795214.7480836.31978F18125.6735346.14270979.74849771.5115894.5146F19322868.221116.59071522.03312.106744.34599F200.12890.4828460.1292660.6316141.0936F21362.66356142.9595313.42278140.9302306.9437F22365.404341019.46871239.58645838.119891044.5246F23367.2028511354.964561416.922881245.352061138.12779F2411.0723913.6328938.7183525.2712618.62976F257.70408717.4849735.6405836.5749719.04745F2626.4841114.235411.83787105.9412110.0795F2744.650405136.27279144.65187159.38326122.3399F28416.13563120.0947991.68671988.114381868.8146W/D/L12/0/163/0/251/0/275/0/237/0/21Table 13
Comparison of the average running time result of 51 runs on 50D in 28 benchmark functions.
FunDESSAHHOPPEAPPEF15.3719384164.573838237.2337746138.10382244.446575594F27.1574039126.6208921111.354052639.16768537.158186551F37.8394305257.324653412.523664739.99190876.214457253F46.4844704335.9152630810.114791638.586793.307264696F56.1597038355.542994139.1463345237.61492044.968641435F66.3003080085.606799829.292129437.63527796.911794831F711.1065635910.729694720.460301141.507548910.88083133F89.3182023928.7087423716.483935639.61875093.878486443F946.0506586548.7456533101.38965875.438067232.79673965F107.5274852046.7248545311.900874340.01265356.521356616F117.3035164576.6544737811.937005740.1833416.179351049F129.5968612699.0908646517.175283742.21320786.93119691F139.7435976889.146690317.101758242.40660134.65911769F147.8890167597.2592571513.82857640.84114376.670441894F158.8248590598.1970059515.696377841.28554324.436260716F1635.4342622538.018275878.910185266.16345923.73375013F176.5457398045.8166114910.414802338.02075765.578457125F188.3490488147.8249258414.379608439.11495673.9553397F196.8635194275.9380142610.386895837.85260687.639078567F208.7411598437.8535453715.066755438.947573.508262818F2115.6195341816.293831329.242428745.274796711.12546115F2215.0937012615.330371829.686162345.109411413.92498259F2317.7496397718.332734735.495124647.359737711.49145802F2455.7721878661.9013014118.54703881.909734439.63127379F2552.6046178663.011092116.42561782.033089239.2314303F2657.5152777370.9420056132.96979486.658899458.37427563F2756.1019322569.4253279129.13472285.36287542.25193263F2821.4554307624.320450146.965632951.963444418.04838259W/D/L1/0/274/0/240/0/280/0/2823/0/5Table 14
Comparison of the best result of 10 runs in CVRP instances.
InstancesBKVDESSAPSOPPEAPPEA-n32-k5784794.4865787.0819787.2024787.0819787.0819A-n33-k5661678.0007662.2642673.1471662.2642662.1101A-n33-k6742746.125742.6933742.6933742.6933742.6933A-n34-k5778787.6693786.437786.437786.7965786.437A-n36-k5799808.5726802.1318802.1318802.1318802.1318A-n37-k5669688.7647672.7407672.7407672.5174672.5174A-n37-k6949960.1145956.8075966.0936957.0298957.0298A-n38-k5730747.4928738.0118734.4416734.4416733.9458A-n39-k5822836.0773829.4541829.5219829.5219829.5219A-n39-k6831841.5609833.2046835.2518835.2518835.2518A-n44-k7937955.3702943.4791948.8242952.5564943.6351A-n45-k6944984.3388959.2347994.68528970.79579945.3614A-n45-k711461186.5591159.73151165.8121170.02751153.0785A-n46-k7914942.1947921.7679921.8017918.1274918.1274A-n48-k710731134.0151095.25641106.68351100.39261094.9122A-n53-k710101098.8151042.86051054.97871030.82441045.9452A-n54-k711671226.5471184.69261188.7671196.20871182.8441A-n55-k910731135.4311082.85271082.92221088.24121078.39A-n60-k914081434.6271364.66541386.02941369.9731379.077A-n61-k910351182.3161071.53841147.62171080.87251104.0151A-n62-k812901372.6831348.81741339.64251338.64791331.7414A-n63-k1013151384.931352.9511363.36551345.45331323.9144A-n63-k916341725.0111661.52731701.09251692.28551639.9246A-n64-k914021501.9431425.87111446.12631424.92941433.2557A-n65-k911771267.511201.8951260.81511186.67361208.8699A-n69-k911681243.5831183.3331198.71751190.58651183.0729A-n80-k1017641911.0731828.14811828.87611831.72241823.0898W/D/L0/0/2710/0/173/0/248/0/1918/0/9Table 15
Comparison of the mean result of 10 runs in CVRP instances.
InstancesBKVDESSAPSOPPEAPPEA-n32-k5784802.3796791.6953789.5103794.8186788.8223A-n33-k5661684.0878675.9522678.5661671.0078665.5313A-n33-k6742754.7865747.2399745.6267744.6511743.8523A-n34-k5778792.6542792.4126792.1176792.9502788.4026A-n36-k5799816.6452808.0167810.3682811.9299807.2603A-n37-k5669700.4381689.2895687.5505683.889678.6079A-n37-k6949981.1734970.0739974.8255970.9061967.2458A-n38-k5730758.8868749.0006751.4792741.9858740.0858A-n39-k5822847.8701837.9498844.841833.7223833.781A-n39-k6831852.229838.8618838.0234836.9315836.5501A-n44-k7937978.7361962.6828969.9482967.2578951.4784A-n45-k69441021.858997.99431038.82071034.7167999.428A-n45-k711461200.7891182.06181184.32411185.38441164.4213A-n46-k7914964.4004940.755950.2408941.6035933.0219A-n48-k710731144.8621109.32741112.95791116.98831103.2999A-n53-k710101106.0721064.17321073.40991063.43561057.0531A-n54-k711671245.6381204.7711228.51661231.24751202.2122A-n55-k910731150.6911106.44841113.9591117.22831095.4729A-n60-k914081443.3061396.05821406.68681408.44231395.4768A-n61-k910351206.6941160.02951190.20041139.9451146.3305A-n62-k812901388.0591360.92441356.50611363.70381345.357A-n63-k1013151412.9461385.11111393.8131372.86071348.2184A-n63-k916341743.691690.84341735.5731727.21441695.1167A-n64-k914021518.6391463.52271463.54761448.96181450.4584A-n65-k911771306.9291244.36241283.9021257.61031239.5486A-n69-k911681269.9331208.99721228.66951216.9341203.1344A-n80-k1017641929.8621864.35961874.98041868.44581852.7933W/D/L0/0/272/0/250/0/273/0/2422/0/5Table 16
Comparison of the best result of 10 runs of APPE with the algorithms proposed by Korayem et al.
InstanceOptimumKmeansFnOKmeansFnPKmeansFnRAPPEA-n33-k6742828754754742.6933A-n34-k5778792822839786.437A-n36-k5799814846846802.1318A-n39-k6831868856837835.2518A-n60-k913541395142114231373.4651A-n62-k812881366132913291346.9532B-n31-k5672684672672676.0884B-n34-k5788793817817790.9678B-n39-k5549571564566553.1565B-n41-k6829845920877836.7407B-n44-k7909940954944932.0102B-n50-k7741765783774745.16B-n50-k813121348135913611341.876W/D/L0/0/132/0/112/0/1111/0/2Table 17
Comparison of the best result of 20 runs of APPE with the algorithms in Yan et al.
InstanceCO-HSPSOGAAPPEA-n32-k5807829818797.7186A-n33-k5669705674680.4111A-n34-k5790832821786.437A-n39-k6852872866842.8981W/D/L1/0/30/0/40/0/43/0/1Table 18
Comparison of the best and mean results of 10 runs of APPE with the algorithms in Zhao et al.
InstanceQDE/BestQDE/MeanQEA/BestQEA/MeanDE/BestDE/MeanAPPE/BestAPPE/MeanP-n76-k4718728718728746765615.72618622.3824P-n76-k5740751740751803813643.98732664.62492A-n32-k5784810835861910924787.08189788.26212A-n33-k5707716707716724735662.2642664.95601A-n33-k6785787785787857872742.69326743.77421W/D/L1/0/40/0/50/0/50/0/50/0/50/0/54/0/15/0/0Table 19
Comparison of the mean result of 10 runs of APPE with the algorithms in Khairy et al.
InstanceGAACOGTOAPPEA-n32-k5812.9982.5901.7790.3117A-n33-k5674.9787.7746.7667.0751A-n34-k5803.4911.8862.8790.7029A-n36-k5839.31008903.3809.091A-n39-k6894.91085975.9835.5559A-n46-k7987.812061138932.0442A-n80-k101987236924701840.5895X-n106-k1428897304503192827751.5143X-n129-k1833893380984171030742.9103X-n143-k721664226743997917318.072X-n167-k1028347288594820522904.9479X-n209-k1642587422867008033887.9638W/D/L0/0/120/0/120/0/1212/0/0Three types of functions are included in CEC2013, as shown in Table1. The first type is the unimodal function, which tests the exploitation ability. The second is the basic multimodal function, which tests the exploration ability. The third type is the composition function, which is composed by the above-mentioned function, representing the challenging problems. The search range is [−100, 100] for each dimension.


### 5.1. Experiment Setting

In this experiment, we compare APPE with DE, SSA, HHO, and PPE. Each algorithm has 100 solutions, i.e.,ps=100, with Dim=10,30,50. Each algorithm has 51 independent runs in each benchmark, and Maxgen equal to 10000×Dim/ps. The parameter setting is as follows: for DE, F=2, CR=0.9, and it uses DE/rand/1/bin. For HHO, β=1.5. For SSA, the number of producers accounts for 20%, SD=20, and ST=0.8. For PPE, k=logNp+1, p, a, and ev of each stick insect are initialized to 1/Np, 1.1, and 0, and G=ub−lbMaxgen+1−t/Maxgen/10. For APPE, INV=4, INVGate=10−6, JumpNum=5, rJump=0.05, HAnum=Np=ps, and other parameters are the same as the PPE.The qualitative metric uses the convergence curve, and the quantitative measure comprises the best, mean, standard deviation, and average running time of the specific benchmark functions.


### 5.2. Experiment Test

Table2 is the best experimental result of APPE with Dim=10, which is the best of 51 runs. Table 3 is the mean experimental result of APPE with Dim=10, which is the mean of 51 runs. Table 4 is the standard deviation experimental result of APPE with Dim=10, which is the standard deviation of 51 runs. Table 5 is the time experimental result of APPE with Dim=10, which is the average running time of each algorithm in 51 runs. Similarly, Tables 6–9 are the result of Dim=30, and Tables 10–13 are the result of Dim=50. We use fitness error f−foptimum for simplicity. We also use W/D/L to record each algorithm’s win/draw/loss number in 28 benchmark functions from Tables 2–13. Under a benchmark function test, if the algorithm has the best performance (minimum fitness value), then W adds one. If the algorithm is equal to other algorithms (with the same fitness value), then D adds one. Otherwise (the algorithm's fitness value is not minimum), L adds one. Figure 3 shows the convergence curves of APPE, and the dimension is 10. APPE compares with DE, SSA, HHO, and PPE.Figure 3
APPE’s convergence curve with the dimension of 10.As shown in Tables2, 6, 10, APPE’s W/D/L of the best experimental result are 20/0/8, 22/0/6, 18/0/10, respectively. It indicates that APPE can search better solutions and is more likely to jump out of local solutions. From Tables 3, 7, 11, APPE’s W/D/L of mean experimental result are 18/0/10, 17/0/11, 18/0/10, respectively. It means that APPE has a higher convergence accuracy. As shown in Tables 4, 8, 12, APPE’s W/D/L of standard deviation experimental result are 8/0/20, 9/0/19, 7/0/21, respectively. Compared with other algorithms in these tables, it can be seen that APPE has moderate convergence stability. From Tables 5, 9, 13, APPE’s W/D/L of time experimental result are 25/0/3, 24/0/4, 23/0/5, respectively. It shows that the running time of APPE is relatively short compared with other algorithms. Therefore, the convergence precision and running time of APPE are quite well.As shown in Figure3, the convergence accuracy of APPE at the beginning of iteration is at a general level. In the middle of iteration, many algorithms are in a stable convergence state, which is similar to falling into the local optimum, while APPE still continues to search at this time, which has a certain exploration ability and can jump out of the local optimum. In the latter part of iteration, it enters the stable convergence stage like many algorithms. In Figure 3, APPE’s convergence curve is basically at the bottom, i.e., the convergence precision is the best. In addition, APPE convergence curve obviously has a steep slope of decline, i.e., APPE can get a better solution faster.


### 5.3. Applying for CVRP

In this section, we apply APPE for solving CVRP. We use instances from [30, 31] to test APPE’s performance. We compare APPE with DE, SSA, PSO, and PPE. For more effectively, we run 10 times for getting more reliable data. The BKV item means the best-known value of instance. The particles are 50. The iteration is 1000. The setting of DE, PPE, and APPE are the same as aforementioned. For SSA, the number of the producers accounts for 20%, SD=20, and ST=0.8. For PSO, ω=0.8, and c1=c2=2. We also use W/D/L to record each algorithm’s win/draw/loss number in instances from Tables 14–19, and the compared fitness value is the sum of distances here. The CVRP experiment is shown in Tables 14 and 15.In Table14, obviously, the performance of APPE searching for the global optimum is better than that of the comparison algorithms. Most of the instances obtain solutions close to BKV. Similarly, in Table 15, APPE has a better convergence accuracy for CVRP than the contrast algorithms. Figure 4 is the best route result of A-n32-k5 solved by APPE. It has 5 routes, and its fitness is 787.0819 that is close to BKV. It is proved that APPE can effectively solve CVRP.Figure 4
The best route result of the A-n32-k5 by APPE.We also compare APPE with some existing results. Table16 is the comparison results of APPE with the results of Korayem et al. [32]. The setting is consistent with [32] that the population is 20, the maximum generations are 500, and each instance runs 10 times. In Table 16, the convergence precision of APPE is better than KmeansFnO, KmeansFnP, and KmeansFnR that are all cluster-first route-second methods, and they combine k-means with gray wolf optimizer [32]. Table 17 shows the comparison results of APPE with the results of Yan et al. [33]. The setting is consistent with [33], and each instance runs 20 times. In Table 17, the convergence precision of APPE is better than the constraint optimization harmony search (CO-HS) of [33], PSO, and GA, and three comparison algorithm's data comes from [33]. Table 18 shows the comparison results of APPE with the results of Zhao et al. [34]. The setting is consistent with [34] that the population is 200, the maximum generations are 500, and each instance is run 10 times. It can be seen from Table 18 that APPE is superior to quantum DE (QDE), quantum evolution algorithm (QEA), and DE in both best and mean performance, with data from [34]. Table 19 shows the results of APPE and the work of Khairy et al. [22]. The setting is consistent with [22] that the population is 40, the maximum generations are 1000, and each instance is run 10 times. In Table 19, the convergence accuracy of APPE is significantly better than GA, ant colony optimization (ACO), and group teaching optimization (GTO), with data from [22].


## 5.1. Experiment Setting

In this experiment, we compare APPE with DE, SSA, HHO, and PPE. Each algorithm has 100 solutions, i.e.,ps=100, with Dim=10,30,50. Each algorithm has 51 independent runs in each benchmark, and Maxgen equal to 10000×Dim/ps. The parameter setting is as follows: for DE, F=2, CR=0.9, and it uses DE/rand/1/bin. For HHO, β=1.5. For SSA, the number of producers accounts for 20%, SD=20, and ST=0.8. For PPE, k=logNp+1, p, a, and ev of each stick insect are initialized to 1/Np, 1.1, and 0, and G=ub−lbMaxgen+1−t/Maxgen/10. For APPE, INV=4, INVGate=10−6, JumpNum=5, rJump=0.05, HAnum=Np=ps, and other parameters are the same as the PPE.The qualitative metric uses the convergence curve, and the quantitative measure comprises the best, mean, standard deviation, and average running time of the specific benchmark functions.


## 5.2. Experiment Test

Table2 is the best experimental result of APPE with Dim=10, which is the best of 51 runs. Table 3 is the mean experimental result of APPE with Dim=10, which is the mean of 51 runs. Table 4 is the standard deviation experimental result of APPE with Dim=10, which is the standard deviation of 51 runs. Table 5 is the time experimental result of APPE with Dim=10, which is the average running time of each algorithm in 51 runs. Similarly, Tables 6–9 are the result of Dim=30, and Tables 10–13 are the result of Dim=50. We use fitness error f−foptimum for simplicity. We also use W/D/L to record each algorithm’s win/draw/loss number in 28 benchmark functions from Tables 2–13. Under a benchmark function test, if the algorithm has the best performance (minimum fitness value), then W adds one. If the algorithm is equal to other algorithms (with the same fitness value), then D adds one. Otherwise (the algorithm's fitness value is not minimum), L adds one. Figure 3 shows the convergence curves of APPE, and the dimension is 10. APPE compares with DE, SSA, HHO, and PPE.Figure 3
APPE’s convergence curve with the dimension of 10.As shown in Tables2, 6, 10, APPE’s W/D/L of the best experimental result are 20/0/8, 22/0/6, 18/0/10, respectively. It indicates that APPE can search better solutions and is more likely to jump out of local solutions. From Tables 3, 7, 11, APPE’s W/D/L of mean experimental result are 18/0/10, 17/0/11, 18/0/10, respectively. It means that APPE has a higher convergence accuracy. As shown in Tables 4, 8, 12, APPE’s W/D/L of standard deviation experimental result are 8/0/20, 9/0/19, 7/0/21, respectively. Compared with other algorithms in these tables, it can be seen that APPE has moderate convergence stability. From Tables 5, 9, 13, APPE’s W/D/L of time experimental result are 25/0/3, 24/0/4, 23/0/5, respectively. It shows that the running time of APPE is relatively short compared with other algorithms. Therefore, the convergence precision and running time of APPE are quite well.As shown in Figure3, the convergence accuracy of APPE at the beginning of iteration is at a general level. In the middle of iteration, many algorithms are in a stable convergence state, which is similar to falling into the local optimum, while APPE still continues to search at this time, which has a certain exploration ability and can jump out of the local optimum. In the latter part of iteration, it enters the stable convergence stage like many algorithms. In Figure 3, APPE’s convergence curve is basically at the bottom, i.e., the convergence precision is the best. In addition, APPE convergence curve obviously has a steep slope of decline, i.e., APPE can get a better solution faster.


## 5.3. Applying for CVRP

In this section, we apply APPE for solving CVRP. We use instances from [30, 31] to test APPE’s performance. We compare APPE with DE, SSA, PSO, and PPE. For more effectively, we run 10 times for getting more reliable data. The BKV item means the best-known value of instance. The particles are 50. The iteration is 1000. The setting of DE, PPE, and APPE are the same as aforementioned. For SSA, the number of the producers accounts for 20%, SD=20, and ST=0.8. For PSO, ω=0.8, and c1=c2=2. We also use W/D/L to record each algorithm’s win/draw/loss number in instances from Tables 14–19, and the compared fitness value is the sum of distances here. The CVRP experiment is shown in Tables 14 and 15.In Table14, obviously, the performance of APPE searching for the global optimum is better than that of the comparison algorithms. Most of the instances obtain solutions close to BKV. Similarly, in Table 15, APPE has a better convergence accuracy for CVRP than the contrast algorithms. Figure 4 is the best route result of A-n32-k5 solved by APPE. It has 5 routes, and its fitness is 787.0819 that is close to BKV. It is proved that APPE can effectively solve CVRP.Figure 4
The best route result of the A-n32-k5 by APPE.We also compare APPE with some existing results. Table16 is the comparison results of APPE with the results of Korayem et al. [32]. The setting is consistent with [32] that the population is 20, the maximum generations are 500, and each instance runs 10 times. In Table 16, the convergence precision of APPE is better than KmeansFnO, KmeansFnP, and KmeansFnR that are all cluster-first route-second methods, and they combine k-means with gray wolf optimizer [32]. Table 17 shows the comparison results of APPE with the results of Yan et al. [33]. The setting is consistent with [33], and each instance runs 20 times. In Table 17, the convergence precision of APPE is better than the constraint optimization harmony search (CO-HS) of [33], PSO, and GA, and three comparison algorithm's data comes from [33]. Table 18 shows the comparison results of APPE with the results of Zhao et al. [34]. The setting is consistent with [34] that the population is 200, the maximum generations are 500, and each instance is run 10 times. It can be seen from Table 18 that APPE is superior to quantum DE (QDE), quantum evolution algorithm (QEA), and DE in both best and mean performance, with data from [34]. Table 19 shows the results of APPE and the work of Khairy et al. [22]. The setting is consistent with [22] that the population is 40, the maximum generations are 1000, and each instance is run 10 times. In Table 19, the convergence accuracy of APPE is significantly better than GA, ant colony optimization (ACO), and group teaching optimization (GTO), with data from [22].


## 6. Conclusions

We propose APPE that deletes competition and conditional acceptance and corresponding evolutionary trend update for shortening the algorithm’s running time. It also adds a jump mechanism, history-based searching, and population closing moving for making PPE more likely to jump out of the local optimum and improving PPE’s convergence accuracy. Then, we test APPE by CEC2013, which compares with DE, SSA, HHO, and PPE. Experiment results show that APPE has higher convergence accuracy and shorter running time. Finally, APPE is applied to solve CVRP. From the test results of instances, APPE is more powerful to solve CVRP than DE, SSA, PSO, and PPE. We also compare our algorithm with some existing work. The results show that APPE is able to solve CVRP.In the future, APPE can be improved by hybrid other algorithm, such as Flower Pollination Algorithm,Harmony Search [35] and adding cubic chaotic mapping [36], a version of multi-objective APPE can be proposed by referring to inverse model [37]. APPE can also be applied to other fields, such as power system problems [38, 39], wireless sensor network problems [39, 40], dispatching system of public transit vehicles [41, 42], traffic forecasting [43], sensor ontology matching [44, 45], feature selection [46], surrogate approach [47, 48], and deep learning [49, 50].



---

*Source: 9241112-2022-03-20.xml*