# Research on Optimization of Improved Gray Wolf Optimization-Extreme Learning Machine Algorithm in Vehicle Route Planning

Authors: Shijin Li; Fucai Wang
Journal: Discrete Dynamics in Nature and Society
 (2020)

---

## Abstract

With the rapid development of intelligent transportation, intelligent algorithms and path planning have become effective methods to relieve traffic pressure. Intelligent algorithm can realize the priority selection mode in realizing traffic optimization efficiency. However, there is local optimization in intelligence and it is difficult to realize global optimization. In this paper, the antilearning model is used to solve the problem that the gray wolf algorithm falls into local optimization. The positions of different wolves are updated. When falling into local optimization, the current position is optimized to realize global optimization. Extreme Learning Machine (ELM) algorithm model is introduced to accelerate Improved Gray Wolf Optimization (IGWO) optimization and improve convergence speed. Finally, the experiment proves that IGWO-ELM algorithm is compared in path planning, and the algorithm has an ideal effect and high efficiency.


---

## Body

## 1. Introduction

Traffic congestion has become a common problem faced by many cities and even most countries in the world. Traffic congestion will not only increase the waiting time people spend on the road and cause urban traffic paralysis but also aggravate environmental pollution. According to understanding, when vehicles are in traffic jams, gasoline is not fully burned in the engine due to the low speed of the vehicle, resulting in pollutants that are several times higher than that when driving at normal speed. Path planning plays an important role in the urban transportation system. A well-planned transportation system can not only reduce the pressure of urban traffic but also bring great convenience to people’s travel, and it has a great role in improving the urban landscape, enhancing the image of the city, and providing people with a good working and learning environment [1]. The main purpose of path planning is to design a traffic route that best meets the actual needs of travelers, provide travelers with the most time-saving and least expensive route, reduce traffic congestion, improve road traffic conditions, and realize urban traffic continued development [2]. As artificial intelligence plays an increasingly obvious role in traffic forecasting, it can plan the traffic path and greatly reduce the time of congestion on the road.Path planning has been widely used in high technology, daily life, decision management, and other fields [3–6]. According to different classification types, the classification of path planning is also different. When classified according to the degree of mastery of the current path, it is mainly divided into two parts: global path planning and local path planning. As the core of autonomous planning and navigation technology for mobile intelligent vehicles, researchers at home and abroad have done a lot of research in recent years. Mrazovic et al. [7] used big data analysis technology to calculate the current vehicle circulation and parking utilization rate and developed a multivehicle routing algorithm to reduce road congestion caused by parking or specific areas. In this paper, a two-layer local search algorithm (greedy random adaptive) is used to train a large number of historical data collected. Through algorithm optimization comparison and analysis, urban road optimization management and reasonable route planning are realized. Gündüz et al. [8] proposed a new path planning method based on an improved genetic algorithm. The evaluation index and optimization function are given through path length and path energy. The three-dimensional path layer structure is established based on fuzzy neural network, and then the genetic algorithm is used to solve the optimal path. Lin et al. [9] proposed a path optimization algorithm for dynamic programming based on PSO, which adopts multiobjective PSO method and can realize parallel processing of different optimization objectives. Ant colony algorithm adopts a positive feedback mechanism, and the search process converges continuously. It has parallelism and greatly improves the operation efficiency of the algorithm. Heuristic probabilistic search has better global optimization ability. However, the disadvantage of ant colony algorithm is that the computation is large [10]. Mauricio et al. [11] adopted a particle swarm optimization method to solve the nonuniform vehicle routing problem with terminal. Through adaptive inertia weight and local search strategy, a better vehicle route scheme is solved. Experimental results show that this method can effectively save the total delivery cost and the number of vehicles required for distribution. Vareias et al. [12] proposed a random time vehicle routing optimization method, which assigns corresponding time to vehicles to solve the optimization problem. The time-consuming and time-consuming of vehicles in the planned route are evaluated, a time window is set for each vehicle, and a penalty and restraint mechanism is set for vehicles late and early. A two-level solution method is implemented, and the cost of the path is optimized and the time window is decomposed into subwindows to evaluate the optimization effect. Hiraishi [13] proposed a route optimization scheme with passengers as the criteria for judging the vehicle status. The route is planned by judging the passenger status. For example, if the passenger is judged to be tired, a time-consuming route is planned. Saeed et al. [14] used memory storage mode through the optimal route, adaptive decision-making cognitive framework; this method can memorize, store, and optimize the route of vehicle information and update the optimal route mode through continuous learning. These algorithms have a certain ability to intelligently process and optimize information, but they do not evaluate historical time and consumption. The restraint mechanism and real-time road conditions cannot be better evaluated, and the road conditions cannot be predicted in real time. The above-mentioned documents have certain advantages in solving real-time path optimization and have a good prediction effect in a short time.


## 2. Gray Wolf Optimization Algorithm Strategies

### 2.1. Standard Wolf Optimization Algorithm

Gray Wolf Optimization (GWO) algorithm is a population intelligence algorithm proposed by Mirjalili Seyedali inspired by gray wolf predation behavior in 2014. The gray wolf pack has a 4-layer hierarchical mechanism ofα, β, δ, and ω. Among them, wolf α is the leader with the best adaptability among the gray wolves. β and δ are the two individuals with the second best fitness. Their task is to assist wolf α in managing the wolf pack and making decisions in the hunting process. ω is the remaining common wolf pack. The predation process is described as follows: first, wolf α leads the gray wolves to search, track, and approach their prey; then, wolves β and δ besiege the prey under the command of wolf α and summon ordinary wolves to attack the prey until they capture the prey. GWO algorithm completes the predation behavior by imitating the predation tasks such as gray wolf surrounding, hunting, and attacking, thus realizing the process of global optimization.


### 2.2. Mathematical Model of GWO

In GWO’s leadership system, wolfα has the highest level, and wolves β and δ led by wolf α are also better individuals. Wolf ω searches paths under wolf α, wolf β, and wolf δ. As ω continuously optimizes the target, while α, β, and δ wolves continuously update the location information, other ω also continuously optimize the target.Assuming that inD-dimensional space, the gray wolf pack Xi,i=1,2,…,N consists of N gray wolves. The GWO algorithm is described as follows:Encirclement stage: after the wolves determine the position of their prey, they first encircle the prey. The mathematical description is as follows:(1)D=C⋅Xpt−Xt,Xt+1=Xpt−A⋅D,whereD is the distance between the gray wolf and its prey; Xpt is the position of the prey after the t-th iteration (the current optimal solution); Xt is the position of the gray wolf (the position of the feasible solution) after the t-th iteration; A and C are coefficient factors, defined as follows:(2)A=2a×r1−a,C=2×r2,wherer1 and r2 are random numbers within [0, 1]; t is the number of iterations of the algorithm; and max is the maximum number of iterations. a=2⟶0 with the increase of iteration times t:(3)a=2−2tmax.Hunting stage: wolfα can quickly find the position of the prey and search for the prey. When wolf α finds the position of the prey, wolves α, β, and δ have a certain understanding of the position of the prey and require ω to approach the position of the prey. This is the prey process of wolves.After the siege phase is completed, wolfα leads wolves β and δ to hunt down their prey. In the process of hunting, the position of individual wolves will move with the escape of prey:(4)X1=Xα−A1C1Xαt−Xt,X2=Xβ−A2C2Xβt−Xt,X3=Xδ−A3C3Xδt−Xt,where Xα, Xβ, and Xδ represent the current positions of wolves α, β, and δ; Xt indicates the current gray wolf position; C1,C2,C3 are random vectors.Update the location of wolfω:(5)Xt+1=X1+X2+X33.By continuously updating the location information,ω wolf continuously updates the location to obtain the optimal location information. The candidate solution in the gray wolf algorithm updates its own position by taking the position information of the leadership level. Candidate solutions are distributed in a random circle defined by the leadership level. From the above formula and schematic diagram, it can be summarized that the optimization process of gray wolf algorithm is to elect wolves α, β, and δ in turn and then use the elected elite individuals to evaluate the possible positions of the prey, and then other individuals in the group randomly update the positions around the prey with reference to the position information of wolves α, β, and δ.


## 2.1. Standard Wolf Optimization Algorithm

Gray Wolf Optimization (GWO) algorithm is a population intelligence algorithm proposed by Mirjalili Seyedali inspired by gray wolf predation behavior in 2014. The gray wolf pack has a 4-layer hierarchical mechanism ofα, β, δ, and ω. Among them, wolf α is the leader with the best adaptability among the gray wolves. β and δ are the two individuals with the second best fitness. Their task is to assist wolf α in managing the wolf pack and making decisions in the hunting process. ω is the remaining common wolf pack. The predation process is described as follows: first, wolf α leads the gray wolves to search, track, and approach their prey; then, wolves β and δ besiege the prey under the command of wolf α and summon ordinary wolves to attack the prey until they capture the prey. GWO algorithm completes the predation behavior by imitating the predation tasks such as gray wolf surrounding, hunting, and attacking, thus realizing the process of global optimization.


## 2.2. Mathematical Model of GWO

In GWO’s leadership system, wolfα has the highest level, and wolves β and δ led by wolf α are also better individuals. Wolf ω searches paths under wolf α, wolf β, and wolf δ. As ω continuously optimizes the target, while α, β, and δ wolves continuously update the location information, other ω also continuously optimize the target.Assuming that inD-dimensional space, the gray wolf pack Xi,i=1,2,…,N consists of N gray wolves. The GWO algorithm is described as follows:Encirclement stage: after the wolves determine the position of their prey, they first encircle the prey. The mathematical description is as follows:(1)D=C⋅Xpt−Xt,Xt+1=Xpt−A⋅D,whereD is the distance between the gray wolf and its prey; Xpt is the position of the prey after the t-th iteration (the current optimal solution); Xt is the position of the gray wolf (the position of the feasible solution) after the t-th iteration; A and C are coefficient factors, defined as follows:(2)A=2a×r1−a,C=2×r2,wherer1 and r2 are random numbers within [0, 1]; t is the number of iterations of the algorithm; and max is the maximum number of iterations. a=2⟶0 with the increase of iteration times t:(3)a=2−2tmax.Hunting stage: wolfα can quickly find the position of the prey and search for the prey. When wolf α finds the position of the prey, wolves α, β, and δ have a certain understanding of the position of the prey and require ω to approach the position of the prey. This is the prey process of wolves.After the siege phase is completed, wolfα leads wolves β and δ to hunt down their prey. In the process of hunting, the position of individual wolves will move with the escape of prey:(4)X1=Xα−A1C1Xαt−Xt,X2=Xβ−A2C2Xβt−Xt,X3=Xδ−A3C3Xδt−Xt,where Xα, Xβ, and Xδ represent the current positions of wolves α, β, and δ; Xt indicates the current gray wolf position; C1,C2,C3 are random vectors.Update the location of wolfω:(5)Xt+1=X1+X2+X33.By continuously updating the location information,ω wolf continuously updates the location to obtain the optimal location information. The candidate solution in the gray wolf algorithm updates its own position by taking the position information of the leadership level. Candidate solutions are distributed in a random circle defined by the leadership level. From the above formula and schematic diagram, it can be summarized that the optimization process of gray wolf algorithm is to elect wolves α, β, and δ in turn and then use the elected elite individuals to evaluate the possible positions of the prey, and then other individuals in the group randomly update the positions around the prey with reference to the position information of wolves α, β, and δ.


## 3. Improved Gray Wolf Optimization Algorithm

Gray Wolf Optimization algorithm is a naturally inspired search algorithm, which has good performance and efficiency in solving various optimization problems. The “flame” variable in the process of lateral orientation is an important parameter used by GWO to update the new position of the population. However, the reduction of flame will slow down the convergence speed, thus affecting the quality of the final solution. In order to overcome this shortcoming, a new antilearning (OBL) moth flame algorithm is proposed. In addition, for cross-border moths, a mirror cross-border strategy is adopted to ensure that moths are within the dimension range and improve population diversity.


### 3.1. Antilearning Algorithm

OBL was first proposed by Tizhoosh in 2005. It is described as follows: suppose the pointX=x1,x2,…,xi,…,xd in d-dimensional space, where x1,x2,…,xi,…,xd∈R and xi∈ai,bi. Its reverse point X˜=x˜1,x˜2,…,x˜i,…,x˜d is defined as follows:(6)x˜i=ai+bi−x˜i.On the basis of GWO, a supplementary functionH based on antilearning strategy is added to speed up the convergence of GWO, and a high-precision solution is obtained. The H function is described as follows:(7)H=A+B−C×rand(8)Mi=H,(9)A=Γ,s>randU,otherwise,(10)B=Θ,s>randL,otherwise,where s=Current number of iterations/Maximum number of iterations, Γ and Θ are the largest and smallest positions of gray wolf respectively, U and L are the upper and lower limits of the search space, C is that optimal flame position in any iteration process, and rand is a random number between (0, 1). Equation (7) is a new form of antilearning. H function generates a new reverse solution according to the reverse position of gray wolf.


### 3.2. Gray Wolf Cross-Border Mirror Strategy

In the GWO optimization process, the gray wolf updates its position according to formula (5), and its position coordinates will cross the border and be continuously placed on the boundary, which not only reduces the diversity of the gray wolf population but also easily makes the algorithm fall into local optimization, thus affecting the optimization performance of the algorithm. In view of this situation, use equation (11) to update the cross-border gray wolf:(11)Xt+1i,j=2Lj−rand×Xt+1i,j,Xt+1i,j≤Lj,2Uj−rand×Xt+1i,j,Xt+1i,j>Uj,where Xt+1i,j is the j-dimensional cross-border position in the i-th gray wolf; Lj and Uj are the value range of the j-th dimension. Repeated operation formula (11) can map Xt+1i,j to the range of dimensions, ensure population diversity, and effectively improve the optimization performance of GWO algorithm.


### 3.3. Steps to Improve Gray Wolf Optimization Algorithm

An Improved Gray Wolf Optimizer (IGWO) is proposed by improving the gray wolf algorithm. The implementation steps of IGWO are summarized as follows:Step 1: set algorithm parameters, including population sizeN, maximum iteration times max, search space dimension dim, search space upper bound U, and lower bound L.Step 2: initialize that population according to the method in Section2.2, p=2∗dim+3.Step 3: calculate and sort the fitness values of gray wolf individuals according to the objective function, find out the individuals with the highest fitness according to the fitness values, and save their positions asXα, Xβ, and Xδ, respectively.Step 4: update the position according to the step size segment step size update mechanism of formulae (4) and (5).Step 5: update the gray wolf population position according to the algorithm designed by formula (11).Step 6: update parametersa, A, and C, where the original linear convergence factor a is changed to exponential nonlinear convergence factor.Step 7: determine whether the maximum number of iterations has been reached, and if so, stop the iteration and output.


## 3.1. Antilearning Algorithm

OBL was first proposed by Tizhoosh in 2005. It is described as follows: suppose the pointX=x1,x2,…,xi,…,xd in d-dimensional space, where x1,x2,…,xi,…,xd∈R and xi∈ai,bi. Its reverse point X˜=x˜1,x˜2,…,x˜i,…,x˜d is defined as follows:(6)x˜i=ai+bi−x˜i.On the basis of GWO, a supplementary functionH based on antilearning strategy is added to speed up the convergence of GWO, and a high-precision solution is obtained. The H function is described as follows:(7)H=A+B−C×rand(8)Mi=H,(9)A=Γ,s>randU,otherwise,(10)B=Θ,s>randL,otherwise,where s=Current number of iterations/Maximum number of iterations, Γ and Θ are the largest and smallest positions of gray wolf respectively, U and L are the upper and lower limits of the search space, C is that optimal flame position in any iteration process, and rand is a random number between (0, 1). Equation (7) is a new form of antilearning. H function generates a new reverse solution according to the reverse position of gray wolf.


## 3.2. Gray Wolf Cross-Border Mirror Strategy

In the GWO optimization process, the gray wolf updates its position according to formula (5), and its position coordinates will cross the border and be continuously placed on the boundary, which not only reduces the diversity of the gray wolf population but also easily makes the algorithm fall into local optimization, thus affecting the optimization performance of the algorithm. In view of this situation, use equation (11) to update the cross-border gray wolf:(11)Xt+1i,j=2Lj−rand×Xt+1i,j,Xt+1i,j≤Lj,2Uj−rand×Xt+1i,j,Xt+1i,j>Uj,where Xt+1i,j is the j-dimensional cross-border position in the i-th gray wolf; Lj and Uj are the value range of the j-th dimension. Repeated operation formula (11) can map Xt+1i,j to the range of dimensions, ensure population diversity, and effectively improve the optimization performance of GWO algorithm.


## 3.3. Steps to Improve Gray Wolf Optimization Algorithm

An Improved Gray Wolf Optimizer (IGWO) is proposed by improving the gray wolf algorithm. The implementation steps of IGWO are summarized as follows:Step 1: set algorithm parameters, including population sizeN, maximum iteration times max, search space dimension dim, search space upper bound U, and lower bound L.Step 2: initialize that population according to the method in Section2.2, p=2∗dim+3.Step 3: calculate and sort the fitness values of gray wolf individuals according to the objective function, find out the individuals with the highest fitness according to the fitness values, and save their positions asXα, Xβ, and Xδ, respectively.Step 4: update the position according to the step size segment step size update mechanism of formulae (4) and (5).Step 5: update the gray wolf population position according to the algorithm designed by formula (11).Step 6: update parametersa, A, and C, where the original linear convergence factor a is changed to exponential nonlinear convergence factor.Step 7: determine whether the maximum number of iterations has been reached, and if so, stop the iteration and output.


## 4. Extreme Learning Machine (ELM)

Professor Huang et al. [15] proposed the Extreme Learning Machine in 2006. ELM algorithm is an improved new algorithm based on SLFN. The biggest advantage of ELM algorithm over traditional SLFN algorithm is that it does not need to update the parameters in training, such as the weight between the input layer and the hidden layer and the threshold value of hidden layer neurons. Once the number of hidden layer nodes is determined, ELM algorithm can obtain a unique global optimal solution with good generalization and general approximation capability.Extreme Learning Machine is a kind of single-hidden layer feedforward neural network (SLFN), which has been widely concerned and applied because of its fast convergence and fast learning ability and good nonlinear classification ability.Setn different training samples xi,yi, of which the k-th input x=x1,x2,…,xNT∈RN corresponds to the output y=y1,y2,…,ymT∈Rm, set the number of input layer nodes of the network as N, set the number of hidden layer nodes as M, and the activation function is expressed as gx; then the unified model of SLFN is(12)∑j=1Mβjgxi=∑j=1Mβjgwj⋅xi+bj=yi,i=1,…,n,where wj represents the j-th weight of the input layer and the hidden layer, b is the node bias of the hidden layer, g⋅ is the excitation function of the hidden layer, the output of the output layer is y=y1,y2,…,ymT∈Rm, the expected output is e=e1,e2,…,emT∈Rm, w=wij represents the connection weight between neurons and neurons (i and j, resp., represent the serial numbers of neurons in the input layer and the hidden layer), and β=βij represents the connection weight between neurons and neurons (i and j, resp., represent the serial numbers of neurons in the hidden layer and the output layer). Then the output of each sample is(13)y=gw1x+b1gw2x+b2,…,gwmx+bmβi+bi.The equation is expressed as(14)hx=gw1x+b1gw2x+b2,…,gwmx+bm.H (x) refers to the response of all neurons in the hidden layer to the input vector x and calculates the output:(15)y=hx⋅βi+bi.The system output forN samples is(16)Y=H⋅β+bi.The error function is defined as(17)E=T−Y=T−H⋅β+bi,where ⋅ represents norm. The above is the basic mathematical reasoning process of a single-hidden layer feedforward neural network. All its parameter values are continuously updated, and the thresholds and weights of both the hidden layer and the output layer will be optimized.


## 5. Experimental Scheme

In this paper, a directed graphG=V,E is defined for urban intersections to represent the key intersection conditions of the city, as shown in Figure 1, where V=v1,v2,…,vn represents N key intersections in the city and E=e1,e2,…,em represents all roads in the city, totaling m roads. The traffic flow between each key intersection is expressed by matrix D=dij,1≤i,j≤n, where dij represents the number of vehicles from stations vi to vj. However, the cost matrix C=cij,1≤i,j≤n, of vehicles passes between intersections. It shows that cij represents the cost of vehicles arriving at vj from station vi, which generally refers to time or distance. Because time is proportional to distance when the vehicle speed is the same, the cost is the same regardless of time or distance. However, if there is no road between station vi and station vj, cij is defined as a large number. For example, c01=6,c10=4 means that the two reintersections communicate at different times and the road conditions between the two intersections are different.Figure 1
Abstract diagram of the route of the key intersection of urban traffic at a certain moment.In Figure1, the passing time before different intersections in the city at a certain moment shows different passing time at different times, different seasons, and different months, different time points in the day show different passing time, and the road conditions show different, specifically showing congestion, slow movement, and smooth flow. In Figure 1, the traffic conditions of different roads back and forth are shown, and the numbers represent specific locations. The number between location and location represents the cost that can be done between locations and generally refers to the time or cost that can be done.Through the relevant statistical analysis of GPS data, the longitude and latitude of different sections at different times and the road conditions of the current map are analyzed. Relevant statistics and analysis are carried out on longitude, latitude, and geographic information in GPS data, vehicle information at different time points of road sections in GPS data is counted, key intersections are numbered, and the sorted data are described in Table1.Table 1
Statistical table of road conditions of vehicles.
Road IDVehicles IDRoad length (m)Entry timeLeave timeSpeed (km/h)Road condition315478.608 : 03 : 1808 : 04 : 2332.632181242.812 : 52 : 0012 : 54 : 1023.2211211254.421 : 18 : 1521 : 20 : 1525.139128521.310 : 57 : 0610 : 59 : 1010.513675613.218 : 47 : 5918 : 50 : 239.21...The above is the statistics of a certain point in time, and the road condition information is usually counted every 5 minutes. Generally, the statistical results of the current real-time road conditions can be divided into three states: blockage, slow travel, and comfort. 1, 2, and 3 are used, respectively. The threshold judgment criteria are as follows: blockage is less than 12 km/h, slow travel is 12∼25 km/h, and unblocked is greater than 25 km/h. The data in Table1 is obtained through raw data statistics. Road ID denotes the number of the road in the map; vehicle ID denotes the number of the vehicle; road section length denotes the actual length of a road section; entry time denotes the start time when the vehicle enters the road section; departure time denotes the end time when the vehicle leaves the road section; speed denotes general passing calculated by dividing the length of the road segment by the time; road conditions denotes classify road conditions by speed.Through the gray wolf algorithm to predict the key intersections of urban traffic, predicting the key routes through different intersections is the focus of this paper. In order to be able to predict the optimal route from the starting point to the ending point and to predict different intersections, Figure2 compares the prediction effects of different routes.Figure 2
Comparison of IGWO-ELM route and optimal route in Figure2.The optimal route in Figure2 is the route selection when the current key route is unblocked, which is referred to herein as the optimal route. The route selection recommended by IGWO-ELM algorithm is basically in high agreement with the optimal route in terms of route, but this is the actual route selection, considering the road conditions at different times. IGWO-ELM algorithm is ideal in execution effect, which shows that the algorithm has a good execution effect. In order to reflect the performance effect of the algorithm, the comparison effect between PSO and GWO algorithms is shown in Figure 3.Figure 3
Comparisons of three algorithms under different route.In Figure3, compared with the time under different paths, the time of IGWO-ELM algorithm in practical application is close to the theoretical value. PSO and GWO algorithms may have differences in running time. In some paths, the running efficiency of the two algorithms is the same, sometimes PSO is better than GWO, and the time efficiency of the two algorithms alternates.


## 6. Conclusion

This paper proposes an improved gray wolf algorithm to be applied to urban traffic path planning. Reasonable traffic path planning can improve traffic operation efficiency and save a lot of time. The basic gray wolf algorithm is easy to fall into local optimization, and it is difficult to obtain global total optimization. The gray wolf algorithm is improved through the antilearning model; thus, the actual global optimization is achieved. Finally, the experimental comparison shows that IGWO-ELM algorithm has obvious advantages in execution efficiency and time. Considering the comparative advantage of IGWO-ELM algorithm in efficiency, different time points or seasonal points will be used as research objects in the later period. The historical data are trained to predict the traffic planning for a period of time in the future, and the vehicles are reasonably planned to alleviate the traffic congestion.



---

*Source: 8647820-2020-10-06.xml*