# Adaptive Cat Swarm Optimization Algorithm and Its Applications in Vehicle Routing Problems

Authors: Xiao-Fang Ji; Jeng-Shyang Pan; Shu-Chuan Chu; Pei Hu; Qing-Wei Chai; Ping Zhang
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

This paper proposes a novel hybrid algorithm named Adaptive Cat Swarm Optimization (ACSO). It combines the benefits of two swarm intelligence algorithms, CSO and APSO, and presents better search results. Firstly, some strategies are implemented to improve the performance of the proposed hybrid algorithm. The tracingradius of the cat group is limited, and the random number parameter r is adaptive adjusted. In addition, a scaling factor update method, called a memory factor y, is introduced into the proposed algorithm. They can be learnt very well so as to jump out of local optimums and speed up the global convergence. Secondly, by comparing the proposed algorithm with PSO, APSO, and CSO, 23 benchmark functions are verified by simulation experiments, which consists of unimodal, multimodal, and fixed-dimension multimodal. The results show the effectiveness and efficiency of the innovative hybrid algorithm. Lastly, the proposed ACSO is utilized to solve the Vehicle Routing Problem (VRP). Experimental findings also reveal the practicability of the ACSO through a comparison with certain existing methods.


---

## Body

## 1. Introduction

In recent decades, Evolutionary Computation (EC) has become a very popular research topic, and great progress has been made in both theory and practice. Swarm Intelligence is a part of Evolutionary Computation, which is also one of the research hotspots in the field of evolutionary computing. Many metaheuristic algorithms have been proposed, including but not limited to Differential Evolution (DE) [1–3] Algorithm, Genetic Algorithm (GA) [4, 5], Particle Swarm Optimization (PSO) [6–8], Cat Swarm Optimization (CSO) [9–11], Ant Colony Optimization (ACO) [12–15], and Bat Algorithm (BA) [16, 17]. Some intelligent computing technologies show great promise in many practical application scenarios, for example, wind power [18, 19], vehicle routing problem [20–23], and wireless sensors [24–31]. All above have been successfully in applied evolutionary calculations to improve their performance, and it is also one of the effective methods to solve traffic problems. However, the diversity of algorithms is affected by the “no free lunch” theorem, which has inspired people to propose more valuable algorithms.PSO is considered to have the following advantages: few control times, easy to implement, and convenient to use. However, it is simple to fall into a local maximum stagnation in terms of convergence and search earlier than anticipated. Therefore, avoiding local optimal solutions and accelerating the rate of convergence are two important issues for intelligent algorithms. Later, many variants of PSO were derived. One of them is proposed by Zhan et al. [32], which sets four states according to the distance between particles, and adaptive adjusts parameters.CSO has two submodes which are only suitable for small-scale population optimization. When the population size increases, the convergence rate will be slower. In order to alleviate the previously mentioned disadvantages, it is a crucial balance between population diversity and convergence speed. Through the improved cat swarm algorithm, the parameter adaptability of ACSO can increase the diversity and flexibility of the population.ACSO is an optimization algorithm which aims to improve their convergence and search capabilities for cat swarm and particle swarm algorithms. According to the experimental results, based on the benefits and disadvantages of the APSO and the CSO, ACSO has improved. The CSO is applicable to smaller populations. Due to the evolutionary state strategy, the APSO is suitable to avoid getting trapped in a local optimum. Compared with other evolutionary algorithms, the ACSO shows unparalleled advantages.The paper’s structure is detailed below. Section2 introduces related research works: PSO, APSO, and CSO. ACSO’s adaptive parameter settings are discussed in Section 3. Then, the performances of ACSO, PSO, APSO, and CSO algorithms are verified by using typical 23 benchmark functions. This is shown in Section 4 while applying the algorithm to VRP as described in Section 5. Finally, Section 6 summarizes the work of this paper, and the suggestions are described for future work.


## 2. Related Research Works

In this section, the basic theory of many traditional algorithms will be reviewed briefly, namely, Cat Swarm Optimization (CSO) and Particle Swarm Optimization (PSO) and the deformation of PSO, named Adaptive Particle Swarm Optimization (APSO). APSO has greatly improved convergence speed and search capabilities. By reviewing the APSO and CSO algorithms, we wondered if we could combine the two algorithms to upgrade CSO.


### 2.1. Particle Swarm Optimization

Originally devised in 1995 by Kennedy and Eberhart [6, 33], PSO is inspired by the behaviour socially of swarms of fish and flocks of birds. It has been widely concerned by people and has good development prospects. In the PSO algorithm, the solution in each optimization space is considered as “particles” with neither volume nor mass. All the particles are based on their own cognitive learning, solo flight experience, and companion flight experience. Therefore, when particles seek the best position in the optimized space, their flights are adjusted through information exchange.Population is randomly initialized at first, and then each particle follows the current individual local optimum and the group global optimum to succeed in finding the optimal solution space. While the program is running, each particle implies a point in the decision space and contains two basic information, position and velocity. Particles update velocity and displacement through the following state transition equations:(1)vidt+1=ω⋅vidt+c1⋅r1pbestdt−xidt+c2⋅r2gbestdt−xidt,xidt+1=xidt+vidt+1.The primary PSO is effortless with simply a few adjusted parameters:vidt indicates the velocity value of the ith particle in the D-dimension before update; xidt denotes the position of the ith particle before the update; pbestdt represents the position of the particle in the particle swarm that currently has a locally optimal solution; gbestdt is the global optimal position of the ith particle; ω is the inertial weight of the particle; c1 and c2 also called the acceleration coefficients, for extending the velocity of the cat to move in the solution space and usually set to 2.05; r1 and r2 are two uniform random values uniformly generated in the range of [0, 1].


### 2.2. Adaptive Particle Swarm Optimization

Traditional PSO still has some shortcomings in global search and convergence. The algorithm has attracted the strong interest of many scholars and is committed to improving the performance of the algorithm. APSO, which is suggested by Zhan et al. [32], accelerates the convergence speed even more. The population distribution state of the algorithm includes four evolutionary states, namely, detection, development, convergence, and bounce. In the process of operation, the inertia weight, acceleration factor, and other parameters can be automatically controlled. Therefore, the search efficiency and the convergence speed are effectively improved. As the evolution progresses, particles may cluster together and converge to a local optimum. At this time, an elite learning strategy guides the global optimal particles to escape from local optimum. This algorithm breaks through the PSO, by detecting the distribution information of different populations and using this information to evaluate the evolutionary state, and the steps are shown below:Step 1: the distribution information can use Euclidean distance to describe the average distance between each particlei and other particles:(2)dist=1n−1∑j=1,j≠in∑k=1dxik−xjk2,wheren and d, respectively, represent the population size and dimension.Step 2: compare the distances of globally optimal particlesdg to other particles and calculate the maximum dmax and minimum dmin distances. The “evolutionary factor” f is denoted as follows:(3)f=dg−dmindmax−dmin∈0,1.In the exploration phase, thef value is large; in the exploitation phase, the f value decreases rapidly; after the environment changes, it will reach the convergence phase; as the number of iterations continues to increase, the particles will jump out, causing the f value to become larger. The cycle then repeats itself.Step 3: the four states S1, S2, S3, and S4 are divided byf. With regard to the order, they represent the circumstances of exploration, exploitation, convergence, and jumping-out, respectively. Generally, a larger adaptive weight ω value is set in exploration, and a smaller value is set in exploitation. However, the evolution factor f also shares some characteristics of the inertial weight ω, so ω can follow f change. Four strategies are summarized in Table 1.Table 1
Control strategies forc1 and c2 in four states.
State
Strategy
c
1
c
2
Exploration
Strategy 1
Increase
Decrease
Exploitation
Strategy 2
Increase slightly
Decrease slightly
Convergence
Strategy 3
Increase slightly
Increase slightly
Jumping-out
Strategy 4
Decrease
IncreaseAt the same time, when the denominator is greater than 3.0, the values ofc1 and c2 are standardized:(4)ci=cic1+c23.0,i=1,2.


### 2.3. Cat Swarm Optimization

CSO is a heuristic global optimization method which was first presented by Taiwan scholar Chu et al. in 2006 [9]. CSO was proposed based on imitating the behaviour of cat. It has been analyzed that cats always spend most of their time to observe the surrounding environments first instead of hunting. Before the hunt, they alternate between moving slowly and staying at a location in a stationary state. This is called the seeking mode. Another submode is called the tracing mode. The CSO algorithm relies on the cooperation of these two states to obtain the optimal solution. Similar to PSO, every cat has its own velocity and position. MR defines how many cats in the overall cat group enter the seeking mode and how many cats enter the tracing mode. Flag is identifying which mode the cat is in. The optimal solution is a fitness value FS, representing the cat’s accommodation to the function of fitness and the best position of the cat that has been obtained. The algorithm’s specific stages are as follows:(i)
Initial population, each cat has D-dimensional coordinate values(ii)
Initialize the speed for randomizing the position of each dimension(iii)
According to the mixture ratio MR, the population is randomly divided into seeking and tracing modes(iv)
On the basis of the cat’s flag bit, perform the corresponding position update on the cat(v)
Evaluate and record the fitness function value of each cat and keep the cat with the best fitness(vi)
Terminate the algorithm if the conditions are met; otherwise, return to step three


#### 2.3.1. Seeking Model

The mode in which cats look around to find targets is called the seeking mode. There are four key parameters:Seeking Memory Pool (SMP) defines the search memory size of each cat, which is representative of the position features that the cat has sought out.Seeking Range of the Selected Dimension (SRD) represents the change rate of the selected area, and the change range of each dimension is determined by the SRD change domain.Counts of Dimension to Change (CDC) refers to the number of dimensions that a single cat will mutate in the future. Its value is a random value between 0 and the maximum dimension.Self-Position Consideration (SPC) is a Boolean valued variable, which indicates whether the position of the cat is about to move includes the position that has passed.The process is described below:(i)
Makej = SMP, which represents copy the cat’s current position. In case, the value of SPC is true, let j = SMP−1, and then return to the current position as a candidate solution.(ii)
For each individual copy in the memory pool, according to the size of the CDC, randomly add or subtract SRD percentage to the current value, and the old value is replaced by the updated value.(iii)
Calculate the values of the fitness functionFS of all solutions that are candidates in the memory pool.(iv)
If all fitness function valuesFS are not completely equal, calculate the selection probability of each candidate solution by equation (5).(v)
The candidate point with the highest fitness value is selected from the memory pool to replace the current cat position, thereby completing the cat position update:(5)Pi=FSi−FSbFSmax−FSmin,where0<i<j.If the fitness function finds the minimum solution of the problem, letFSb = FSmax; otherwise, FSb = FSmin.


#### 2.3.2. Tracing Model

The state mode when tracing the target after finding it is called the tracing mode. This action can be briefly described in three steps.The process is as follows:(i)
Update the velocities of each dimension according to (6), the best position that the entire cat group passes, that is, the optimal solution currently found:(6)vidt+1=vidt+r⋅c⋅xbestdt−xidt,d=1,2,3,…,m.(ii)
Check whether the velocities are within the maximum velocity range.(iii)
According to (7), update the cat’s position:(7)xidt+1=xidt+vidt+1.


## 2.1. Particle Swarm Optimization

Originally devised in 1995 by Kennedy and Eberhart [6, 33], PSO is inspired by the behaviour socially of swarms of fish and flocks of birds. It has been widely concerned by people and has good development prospects. In the PSO algorithm, the solution in each optimization space is considered as “particles” with neither volume nor mass. All the particles are based on their own cognitive learning, solo flight experience, and companion flight experience. Therefore, when particles seek the best position in the optimized space, their flights are adjusted through information exchange.Population is randomly initialized at first, and then each particle follows the current individual local optimum and the group global optimum to succeed in finding the optimal solution space. While the program is running, each particle implies a point in the decision space and contains two basic information, position and velocity. Particles update velocity and displacement through the following state transition equations:(1)vidt+1=ω⋅vidt+c1⋅r1pbestdt−xidt+c2⋅r2gbestdt−xidt,xidt+1=xidt+vidt+1.The primary PSO is effortless with simply a few adjusted parameters:vidt indicates the velocity value of the ith particle in the D-dimension before update; xidt denotes the position of the ith particle before the update; pbestdt represents the position of the particle in the particle swarm that currently has a locally optimal solution; gbestdt is the global optimal position of the ith particle; ω is the inertial weight of the particle; c1 and c2 also called the acceleration coefficients, for extending the velocity of the cat to move in the solution space and usually set to 2.05; r1 and r2 are two uniform random values uniformly generated in the range of [0, 1].


## 2.2. Adaptive Particle Swarm Optimization

Traditional PSO still has some shortcomings in global search and convergence. The algorithm has attracted the strong interest of many scholars and is committed to improving the performance of the algorithm. APSO, which is suggested by Zhan et al. [32], accelerates the convergence speed even more. The population distribution state of the algorithm includes four evolutionary states, namely, detection, development, convergence, and bounce. In the process of operation, the inertia weight, acceleration factor, and other parameters can be automatically controlled. Therefore, the search efficiency and the convergence speed are effectively improved. As the evolution progresses, particles may cluster together and converge to a local optimum. At this time, an elite learning strategy guides the global optimal particles to escape from local optimum. This algorithm breaks through the PSO, by detecting the distribution information of different populations and using this information to evaluate the evolutionary state, and the steps are shown below:Step 1: the distribution information can use Euclidean distance to describe the average distance between each particlei and other particles:(2)dist=1n−1∑j=1,j≠in∑k=1dxik−xjk2,wheren and d, respectively, represent the population size and dimension.Step 2: compare the distances of globally optimal particlesdg to other particles and calculate the maximum dmax and minimum dmin distances. The “evolutionary factor” f is denoted as follows:(3)f=dg−dmindmax−dmin∈0,1.In the exploration phase, thef value is large; in the exploitation phase, the f value decreases rapidly; after the environment changes, it will reach the convergence phase; as the number of iterations continues to increase, the particles will jump out, causing the f value to become larger. The cycle then repeats itself.Step 3: the four states S1, S2, S3, and S4 are divided byf. With regard to the order, they represent the circumstances of exploration, exploitation, convergence, and jumping-out, respectively. Generally, a larger adaptive weight ω value is set in exploration, and a smaller value is set in exploitation. However, the evolution factor f also shares some characteristics of the inertial weight ω, so ω can follow f change. Four strategies are summarized in Table 1.Table 1
Control strategies forc1 and c2 in four states.
State
Strategy
c
1
c
2
Exploration
Strategy 1
Increase
Decrease
Exploitation
Strategy 2
Increase slightly
Decrease slightly
Convergence
Strategy 3
Increase slightly
Increase slightly
Jumping-out
Strategy 4
Decrease
IncreaseAt the same time, when the denominator is greater than 3.0, the values ofc1 and c2 are standardized:(4)ci=cic1+c23.0,i=1,2.


## 2.3. Cat Swarm Optimization

CSO is a heuristic global optimization method which was first presented by Taiwan scholar Chu et al. in 2006 [9]. CSO was proposed based on imitating the behaviour of cat. It has been analyzed that cats always spend most of their time to observe the surrounding environments first instead of hunting. Before the hunt, they alternate between moving slowly and staying at a location in a stationary state. This is called the seeking mode. Another submode is called the tracing mode. The CSO algorithm relies on the cooperation of these two states to obtain the optimal solution. Similar to PSO, every cat has its own velocity and position. MR defines how many cats in the overall cat group enter the seeking mode and how many cats enter the tracing mode. Flag is identifying which mode the cat is in. The optimal solution is a fitness value FS, representing the cat’s accommodation to the function of fitness and the best position of the cat that has been obtained. The algorithm’s specific stages are as follows:(i)
Initial population, each cat has D-dimensional coordinate values(ii)
Initialize the speed for randomizing the position of each dimension(iii)
According to the mixture ratio MR, the population is randomly divided into seeking and tracing modes(iv)
On the basis of the cat’s flag bit, perform the corresponding position update on the cat(v)
Evaluate and record the fitness function value of each cat and keep the cat with the best fitness(vi)
Terminate the algorithm if the conditions are met; otherwise, return to step three


### 2.3.1. Seeking Model

The mode in which cats look around to find targets is called the seeking mode. There are four key parameters:Seeking Memory Pool (SMP) defines the search memory size of each cat, which is representative of the position features that the cat has sought out.Seeking Range of the Selected Dimension (SRD) represents the change rate of the selected area, and the change range of each dimension is determined by the SRD change domain.Counts of Dimension to Change (CDC) refers to the number of dimensions that a single cat will mutate in the future. Its value is a random value between 0 and the maximum dimension.Self-Position Consideration (SPC) is a Boolean valued variable, which indicates whether the position of the cat is about to move includes the position that has passed.The process is described below:(i)
Makej = SMP, which represents copy the cat’s current position. In case, the value of SPC is true, let j = SMP−1, and then return to the current position as a candidate solution.(ii)
For each individual copy in the memory pool, according to the size of the CDC, randomly add or subtract SRD percentage to the current value, and the old value is replaced by the updated value.(iii)
Calculate the values of the fitness functionFS of all solutions that are candidates in the memory pool.(iv)
If all fitness function valuesFS are not completely equal, calculate the selection probability of each candidate solution by equation (5).(v)
The candidate point with the highest fitness value is selected from the memory pool to replace the current cat position, thereby completing the cat position update:(5)Pi=FSi−FSbFSmax−FSmin,where0<i<j.If the fitness function finds the minimum solution of the problem, letFSb = FSmax; otherwise, FSb = FSmin.


### 2.3.2. Tracing Model

The state mode when tracing the target after finding it is called the tracing mode. This action can be briefly described in three steps.The process is as follows:(i)
Update the velocities of each dimension according to (6), the best position that the entire cat group passes, that is, the optimal solution currently found:(6)vidt+1=vidt+r⋅c⋅xbestdt−xidt,d=1,2,3,…,m.(ii)
Check whether the velocities are within the maximum velocity range.(iii)
According to (7), update the cat’s position:(7)xidt+1=xidt+vidt+1.


## 2.3.1. Seeking Model

The mode in which cats look around to find targets is called the seeking mode. There are four key parameters:Seeking Memory Pool (SMP) defines the search memory size of each cat, which is representative of the position features that the cat has sought out.Seeking Range of the Selected Dimension (SRD) represents the change rate of the selected area, and the change range of each dimension is determined by the SRD change domain.Counts of Dimension to Change (CDC) refers to the number of dimensions that a single cat will mutate in the future. Its value is a random value between 0 and the maximum dimension.Self-Position Consideration (SPC) is a Boolean valued variable, which indicates whether the position of the cat is about to move includes the position that has passed.The process is described below:(i)
Makej = SMP, which represents copy the cat’s current position. In case, the value of SPC is true, let j = SMP−1, and then return to the current position as a candidate solution.(ii)
For each individual copy in the memory pool, according to the size of the CDC, randomly add or subtract SRD percentage to the current value, and the old value is replaced by the updated value.(iii)
Calculate the values of the fitness functionFS of all solutions that are candidates in the memory pool.(iv)
If all fitness function valuesFS are not completely equal, calculate the selection probability of each candidate solution by equation (5).(v)
The candidate point with the highest fitness value is selected from the memory pool to replace the current cat position, thereby completing the cat position update:(5)Pi=FSi−FSbFSmax−FSmin,where0<i<j.If the fitness function finds the minimum solution of the problem, letFSb = FSmax; otherwise, FSb = FSmin.


## 2.3.2. Tracing Model

The state mode when tracing the target after finding it is called the tracing mode. This action can be briefly described in three steps.The process is as follows:(i)
Update the velocities of each dimension according to (6), the best position that the entire cat group passes, that is, the optimal solution currently found:(6)vidt+1=vidt+r⋅c⋅xbestdt−xidt,d=1,2,3,…,m.(ii)
Check whether the velocities are within the maximum velocity range.(iii)
According to (7), update the cat’s position:(7)xidt+1=xidt+vidt+1.


## 3. Adaptive Cat Swarm Optimization

This paper proposes a new cat swarm algorithm with adaptive strategy based on the traditional APSO and CSO algorithms. This improvement does not only advance the efficiency and convergence of the algorithm but also maintains an understanding of the uniformity of the distribution. The specific content and innovations can be summarized as follows.


### 3.1. Increase Adaptive Parameters

Based on the parameter self-adaptation, the operation process of random numbers is adjust, and an adaptive strategy is add. In the early stage of iteration, the cat swarm can obtain strong global optimization ability:(8)rk=1−ck+1·rand·ick·MaxIter,k=1,2,i<MaxIter2.Make the particle swarm converge to the optimal position later in the iteration:(9)rk=1−ck+1⋅1+rand⋅ick⋅MaxIter,k=1,2,i≥MaxIter2.When the initial values ofc1 and c2 are set relatively small, add them to limit the generation of negative values, in order to avoid negative numbers:(10)r1=r2=rand,r1≤0,r2≤0.Change equations (8)–(10) are beneficial to the global search ability at the early stage of particle iteration, local refinement in later iterations, and to improve the accuracy of the solution.


### 3.2. A Radius Range is Added to the Search Position

When the distance betweenxid and gbestd is less than the radius, then toward the individual xid to gbestd. However, when the distance between xid and pbestd is less than the radius, just deviate it from pbestd. The value of the elements is defined by the following equations:(11)vidt+1=ω⋅vidt+c1⋅r1⋅pbestdt−xidt+c2⋅r2⋅gbestdt−xidt+f⋅Fi+e⋅Ei,(12)f=0.1−i⋅0.2MaxIter,e=2⋅rand,Fi=gbestdt−xidt,dist2gbest≤radius,Ei=pbestdt+xidt,dist2pbest≤radius,where f and e show the weights attracted toward the global optimal solution and the weights away from the local optimal solution, respectively. Fi and Ei indicate the food sources of the ith individual and the enemy of the ith individual.


### 3.3. Increase Memory Factory

Particles learn from each other to obtain the most informative information in their respective fields. For each searcher, a memory factory is added, and each particle gives a lower memory weight to the previous position. For the purpose of updating the historical best position of each searcher, higher memory weight is referenced to update the current position:(13)xidt+1=12y⋅xidt+1−y⋅xidt−1+y⋅vidt+1+1−y⋅vidt.To better explain the process of ACSO, the complete flow chart is shown in Figure1. Firstly, randomly initialize each cat. Then, calculate the fitness value. Finally, make its parameters adaptive adjusted in the tracing mode.Figure 1
The complete flow chart of ACSO.The pseudocode of ACSO seeking mode function is exhibited in Algorithm1.Algorithm 1: ACSO seeking mode.
CreateN cats
Initialize related parameters
Calculate the fitness of each cat
Divides cats into two mode based onflag
SMP = the search memory pool size
if
flag = = 0 then
fori = 1 to SMPdo
fitness = fobj(catCopy(i).Posi)
end for
else
fori = 2 to SMPdo
fitness = fobj(catCopy(i).Posi)
end for
end ifThe pseudocode of ACSO tracing mode function is exhibited in Algorithm2.Algorithm 2: ACSO tracing mode.
while
t < = Maxiteration do
Adaptive adjustment parameterr by equations (8)∼(10)
Compare the distance between Cat.Posi and cat’s gbest.Posi and pbest.Posi
Dist2gbest = distances (Cat.Posi, gbest.Posi)
ifDist2gbest < = radiusthen
F = gbest.Posi − Cat.Posi
else
F = 0
end if
Dist2pbest = distances (Cat.Posi, pbest.Posi)
ifDist2pbest < = radiusthen
E = pbest.Posi + Cat.Posi
else
E = 0
end if
Update the position and velocity by equations (11) and (12)
end while
return gbest


## 3.1. Increase Adaptive Parameters

Based on the parameter self-adaptation, the operation process of random numbers is adjust, and an adaptive strategy is add. In the early stage of iteration, the cat swarm can obtain strong global optimization ability:(8)rk=1−ck+1·rand·ick·MaxIter,k=1,2,i<MaxIter2.Make the particle swarm converge to the optimal position later in the iteration:(9)rk=1−ck+1⋅1+rand⋅ick⋅MaxIter,k=1,2,i≥MaxIter2.When the initial values ofc1 and c2 are set relatively small, add them to limit the generation of negative values, in order to avoid negative numbers:(10)r1=r2=rand,r1≤0,r2≤0.Change equations (8)–(10) are beneficial to the global search ability at the early stage of particle iteration, local refinement in later iterations, and to improve the accuracy of the solution.


## 3.2. A Radius Range is Added to the Search Position

When the distance betweenxid and gbestd is less than the radius, then toward the individual xid to gbestd. However, when the distance between xid and pbestd is less than the radius, just deviate it from pbestd. The value of the elements is defined by the following equations:(11)vidt+1=ω⋅vidt+c1⋅r1⋅pbestdt−xidt+c2⋅r2⋅gbestdt−xidt+f⋅Fi+e⋅Ei,(12)f=0.1−i⋅0.2MaxIter,e=2⋅rand,Fi=gbestdt−xidt,dist2gbest≤radius,Ei=pbestdt+xidt,dist2pbest≤radius,where f and e show the weights attracted toward the global optimal solution and the weights away from the local optimal solution, respectively. Fi and Ei indicate the food sources of the ith individual and the enemy of the ith individual.


## 3.3. Increase Memory Factory

Particles learn from each other to obtain the most informative information in their respective fields. For each searcher, a memory factory is added, and each particle gives a lower memory weight to the previous position. For the purpose of updating the historical best position of each searcher, higher memory weight is referenced to update the current position:(13)xidt+1=12y⋅xidt+1−y⋅xidt−1+y⋅vidt+1+1−y⋅vidt.To better explain the process of ACSO, the complete flow chart is shown in Figure1. Firstly, randomly initialize each cat. Then, calculate the fitness value. Finally, make its parameters adaptive adjusted in the tracing mode.Figure 1
The complete flow chart of ACSO.The pseudocode of ACSO seeking mode function is exhibited in Algorithm1.Algorithm 1: ACSO seeking mode.
CreateN cats
Initialize related parameters
Calculate the fitness of each cat
Divides cats into two mode based onflag
SMP = the search memory pool size
if
flag = = 0 then
fori = 1 to SMPdo
fitness = fobj(catCopy(i).Posi)
end for
else
fori = 2 to SMPdo
fitness = fobj(catCopy(i).Posi)
end for
end ifThe pseudocode of ACSO tracing mode function is exhibited in Algorithm2.Algorithm 2: ACSO tracing mode.
while
t < = Maxiteration do
Adaptive adjustment parameterr by equations (8)∼(10)
Compare the distance between Cat.Posi and cat’s gbest.Posi and pbest.Posi
Dist2gbest = distances (Cat.Posi, gbest.Posi)
ifDist2gbest < = radiusthen
F = gbest.Posi − Cat.Posi
else
F = 0
end if
Dist2pbest = distances (Cat.Posi, pbest.Posi)
ifDist2pbest < = radiusthen
E = pbest.Posi + Cat.Posi
else
E = 0
end if
Update the position and velocity by equations (11) and (12)
end while
return gbest


## 4. Experiment and Result Analysis

This segment is predominantly to verify the efficient performance of the projected algorithm, and 23 mathematical optimization functions were performed for the purpose of comparing the ACSO with PSO, APSO, and CSO. These typical test equations are listed in Tables2–4 used by many scholars [34]. Three of these elements need to be declared, Space, Dim, and Fmin, which denotes the boundary of function’s search space, the dimension of the function, and the optimal solution, respectively.Table 2
Unimodal benchmark functions.
Function
Space
D
im
F
min
F
1
x
=
∑
i
=
1
n
x
i
2
[−100, 100]
30
0
F
2
x
=
∑
i
=
1
n
x
i
+
∏
i
=
1
n
x
i
[−10, 10]
30
0
F
3
x
=
∑
i
=
1
n
∑
j
−
1
i
x
j
2
[−100, 100]
30
0
F
4
x
=
max
i
x
i
,
1
≤
i
≤
n
[−100, 100]
30
0
F
5
x
=
∑
i
=
1
n
−
1
100
x
i
+
1
−
x
i
2
2
+
x
i
−
1
2
[−30, 30]
30
0
F
6
x
=
∑
i
=
1
n
x
i
+
0.5
2
[−100, 100]
30
0
F
7
x
=
∑
i
=
1
n
i
x
i
4
+
random
0,1
[−1.28, 1.28]
30
0Table 3
Multimodal benchmark functions.
Function
Space
Dim
F
min
F
8
x
=
∑
i
=
1
n
−
x
i
sin
x
i
[−500, 500]
30
−12569
F
9
x
=
∑
i
=
1
n
x
i
2
−
10
cos
2
π
x
i
+
10
[−5.12, 5.12]
30
0
F
10
x
=
−
20
exp
−
0.2
1
/
n
∑
i
=
1
n
x
i
2
−
exp
1
/
n
∑
i
=
1
n
cos
2
π
x
i
+
20
+
e
[−32, 32]
30
0
F
11
x
=
1
/
4000
∑
i
=
1
n
x
i
2
−
∏
i
=
1
n
cos
x
i
/
i
+
1
[−600, 600]
30
0
F
12
x
=
π
/
n
10
sin
π
y
1
+
∑
i
=
1
n
−
1
y
i
−
1
2
1
+
10
sin
2
π
y
i
+
1
+
y
n
−
1
2
+
∑
i
=
1
n
u
x
i
,
10,100,4
y
i
=
1
+
x
i
+
1
/
4
u
x
i
,
a
,
k
,
m
=
k
x
i
−
a
m
x
i
>
a
0
−
a
<
x
i
<
a
k
−
x
i
−
a
m
x
i
<
−
a
[−50, 50]
30
0
F
13
x
=
0.1
sin
2
3
π
x
1
+
∑
i
=
1
n
x
i
−
1
2
1
+
sin
2
3
π
x
i
+
1
+
x
n
−
1
2
1
+
sin
2
2
π
x
n
+
∑
i
=
1
n
u
x
i
,
10,100,4
[−50, 50]
30
0Table 4
Fixed-dimension multimodal benchmark functions.
Function
Space
Dim
F
min
F
14
x
=
1
/
500
∑
j
=
1
25
1
/
j
+
∑
i
=
1
2
x
i
−
a
i
j
6
−
1
[−65, 65]
2
1
F
15
x
=
∑
i
=
1
11
a
i
−
x
1
b
i
2
+
b
i
x
2
/
b
i
2
+
b
i
x
3
+
x
4
2
[−5, 5]
4
0.00030
F
16
x
=
4
x
1
2
−
2.1
x
1
4
+
1
/
3
x
1
6
+
x
1
x
2
−
4
x
2
2
+
4
x
2
4
[−5, 5]
2
−1.0316
F
17
x
=
x
2
−
5.1
/
4
π
2
x
1
2
+
5
/
π
x
1
−
6
2
+
10
1
−
1
/
8
π
cos
x
1
+
10
[−5, 5]
2
0.398
F
18
x
=
1
+
x
1
+
x
2
+
1
2
19
−
14
x
1
+
3
x
1
2
−
14
x
2
+
6
x
1
x
2
+
3
x
2
2
×
30
+
2
x
1
−
3
x
2
2
×
18
−
32
x
1
+
12
x
1
2
+
48
x
2
−
36
x
1
x
2
+
27
x
2
2
[−2, 2]
2
3
F
19
x
=
−
∑
i
=
1
4
c
i
exp
−
∑
j
=
1
3
a
i
j
x
j
−
p
i
j
2
[1, 3]
3
−3.86
F
20
x
=
−
∑
i
=
1
4
c
i
exp
−
∑
j
=
1
6
a
i
j
x
j
−
p
i
j
2
[0, 1]
6
−3.32
F
21
x
=
−
∑
i
=
1
5
X
−
a
i
X
−
a
i
T
+
c
i
]
−
1
[0, 10]
4
−10.1532
F
22
x
=
−
∑
i
=
1
7
X
−
a
i
X
−
a
i
T
+
c
i
−
1
[0, 10]
4
−10.4028
F
23
x
=
−
∑
i
=
1
10
X
−
a
i
X
−
a
i
T
+
c
i
−
1
[0, 10]
4
−10.5363


### 4.1. Experimental Results

For verifying the results, CSO, APSO, and PSO are used to compare with the proposed ACSO algorithm. 23 benchmark functions are used to evaluate the performance of ACSO for real-parameter optimization. Usually, the benchmark function is also described as a mathematical test function. The mathematical test function used illustrates its 2D version in Figures2–4. The relevant test parameters are listed in Table 5. In order to achieve a fair competition, for each test function, we tested 10 times for each optimization algorithm to get the average and standard deviation. The population size of each algorithm is set to 100, and the maximum number of iterations is 500. Subsequently, Table 6 illustrates the comparison of four algorithms on average (Ave) and standard deviation (Std).Figure 2
2D versions of unimodal benchmark functions: (a) F1; (b) F2; (c) F3; (d) F4; (e) F5; (f) F7.
(a)
(b)
(c)
(d)
(e)
(f)Figure 3
2D versions of multimodal benchmark functions: (a) F9; (b) F10; (c) F11; (d) F13.
(a)
(b)
(c)
(d)Figure 4
2D versions of fixed-dimensional multimodal benchmark functions: (a) F14; (b) F15; (c) F17; (d) F21.
(a)
(b)
(c)
(d)Table 5
Parameter setting of each algorithm.
Algorithm
Main parameter setting
PSO
VelMin = −6, VelMax = 6,c = 2.5, w = 0.9
APSO
VelMin = −6, VelMax = 6,c1 = c2 = 2.5, w = 0.9, status = “S1”
CSO
SRD = 0.9, MR = 0.3, RangeMin = −30, RangeMax = 30, VelMin = −6, VelMax = 6, c = 1.05,w = 0.6
ACSO
SRD = 0.9, MR = 0.3, RangeMin = −30, RangeMax = 30, VelMin = −6, VelMax = 6,c1 = c2 = 1.05, w = 0.6, status = “S1,” radius = 50Table 6
The statistical results of the algorithms.
Function
PSO
APSO
CSO
ACSO
Average
Standard deviation
Average
Standard deviation
Average
Standard deviation
Average
Standard deviation
F1
4.66 × 104
3.94 × 103
1.46 × 101
7.28 × 100
2.43 × 10−33
3.80 × 10−33
1.62 × 10−48
2.76 × 10−48
F2
3.74 × 1033
6.42 × 1033
4.55 × 101
1.60 × 101
1.50 × 10−19
2.59 × 10−19
4.40 × 10−24
6.61 × 10−24
F3
7.92 × 104
2.85 × 104
5.29 × 103
3.68 × 102
6.36 × 10−27
1.10 × 10−26
45.04 × 10−46
8.73 × 10−46
F4
6.91 × 101
6.46 × 100
3.74 × 100
4.14 × 10−1
2.92 × 10−16
5.06 × 10−16
1.33 × 10−25
2.31 × 10−25
F5
1.83 × 1010
3.53 × 109
7.23 × 103
2.91 × 103
2.88 × 101
3.86 × 10−2
2.84 × 101
1.70 × 10−5
F6
3.89 × 104
1.03 × 104
2.59 × 101
1.52 × 101
2.51 × 100
1.14 × 10−1
3.65 × 100
2.08 × 10−1
F7
2.16 × 109
5.53 × 108
1.09 × 103
4.58 × 102
8.37 × 10−6
6.77 × 10−6
1.58 × 10−6
1.71 × 10−6
F8
−5.69 × 102
4.06 × 101
−1.17 × 103
8.78 × 101
1.22 × 1039
2.12 × 1039
−6.88 × 102
5.27 × 102
F9
4.91 × 104
2.63 × 103
3.19 × 102
4.51 × 101
0
0
0
0
F10
2.12 × 101
6.89 × 10−2
1.77 × 101
4.12 × 100
8.88 × 10−16
0
8.88 × 10−16
0
F11
1.09 × 101
1.31 × 100
4.87 × 10−1
1.09 × 10−1
0
0
0
0
F12
5.97 × 109
2.74 × 109
5.88 × 100
3.74 × 100
2.04 × 10−1
1.67 × 10−1
4.24 × 10−1
5.79 × 10−2
F13
1.13 × 1010
3.68 × 109
2.33 × 101
1.45 × 101
1.30 × 100
5.53 × 10−1
2.68 × 10−4
1.74 × 10−6
F14
1.26 × 101
4.37 × 100
1.33 × 100
5.74 × 10−1
4.33 × 100
2.33 × 100
1.12 × 100
1.38 × 10−1
F15
1.79 × 10−2
1.64 × 10−2
1.01 × 10−3
4.60 × 10−5
8.14 × 10−4
3.56 × 10−4
3.51 × 10−4
2.22 × 10−6
F16
1.53 × 104
2.61 × 104
−1.03 × 100
0
−1.03 × 101
7.17 × 10−4
−1.02 × 100
9.85 × 10−3
F17
1.83 × 100
2.34 × 100
3.98 × 10−1
0
4.02 × 10−1
7.39 × 10−3
3.98 × 10−1
2.97 × 10−5
F18
1.27 × 108
2.06 × 108
3.00
5.44 × 10−16
3.00 × 100
8.84 × 10−4
3.43 × 100
5.22 × 10−1
F19
−2.07 × 10−33
3.58 × 10−33
−3.86 × 100
3.14 × 10−16
−3.72 × 100
1.07 × 10−1
−2.99 × 100
5.14 × 10−1
F20
0
0
−6.59 × 10−1
5.79 × 10−1
−1.85 × 100
7.13 × 10−1
−1.33 × 100
1.54 × 10−1
F21
−3.59 × 10−2
2.85 × 10−2
−3.47 × 100
1.41 × 100
−2.14 × 100
8.35 × 10−1
−1.02 × 101
6.80 × 10−9
F22
−1.91 × 10−2
1.40 × 10−2
−1.04 × 101
1.78 × 10−15
−3.66 × 100
1.04 × 100
−1.04 × 101
3.90 × 10−7
F23
−1.10 × 10−2
1.89 × 10−3
−7.83 × 100
4.69 × 100
−3.00 × 100
7.05 × 10−1
−1.05 × 101
1.38 × 10−7


### 4.2. Experiment Analysis

From Figures5–7, solution quality and speed of PSO, APSO, CSO, and ACSO under 23 benchmark functions can be obtained. The horizontal axis in the figures stand for the maximum number of iterations during program execution and along the vertical axis are the corresponding fitness values. They are the simulation results of unimodal, multimodal, and fixed-dimensional multimodal mathematical test functions.Figure 5
Simulation results for unimodal benchmark functions: (a) F1; (b) F2; (c) F3; (d) F4; (e) F5; (f) F7.
(a)
(b)
(c)
(d)
(e)
(f)Figure 6
Simulation results for multimodal benchmark functions: (a) F9; (b) F10; (c) F11; (d) F13.
(a)
(b)
(c)
(d)Figure 7
Simulation results for fixed-dimension multimodal benchmark functions: (a) F14; (b) F15; (c) F17; (d) F21.
(a)
(b)
(c)
(d)The unimodal function is a continuous function with only one extreme point in the domain; in other words, it has only one global optimum and no local optimum, so these algorithms are used to benchmark it. The performance of ACSO is superior to PSO, APSO, and ACSO. From Figure5, because they contain only one global optimal solution, they have faster search convergence in the function.The multimodal function is a function that contains multiple locally or globally optimal solutions, the purpose of which is to detect whether the test algorithm avoids local optimums. Relatively speaking, the improved algorithm is better than other algorithms, as shown in Figure6. Premature stagnation of the optimal solution appears in F9 and F11. ACSO is better than other algorithms in the benchmark function of F10 and F13. However, the PSO algorithm is known to have the shortcoming of premature convergence in dealing with multimodal optimization problems, owing to the lack of enough momentum for particles to do exploration or exploitation when the algorithm is nearing its end, so it is the worst solution curve.In the fixed-dimensional multimodal function, Figure7 shows the curves of simulation results by all four algorithms, where the curves of APSO, CSO, and ACSO are almost overlapped in F17. From Table 6 and Figures 5–7, observing ACSO, not only can they avoid getting trapped in a local optimum but they can also converge quickly and eventually finding a global optimal solution. Therefore, we conclude that the proposed algorithms are noticeably superior to other comparison algorithms.


## 4.1. Experimental Results

For verifying the results, CSO, APSO, and PSO are used to compare with the proposed ACSO algorithm. 23 benchmark functions are used to evaluate the performance of ACSO for real-parameter optimization. Usually, the benchmark function is also described as a mathematical test function. The mathematical test function used illustrates its 2D version in Figures2–4. The relevant test parameters are listed in Table 5. In order to achieve a fair competition, for each test function, we tested 10 times for each optimization algorithm to get the average and standard deviation. The population size of each algorithm is set to 100, and the maximum number of iterations is 500. Subsequently, Table 6 illustrates the comparison of four algorithms on average (Ave) and standard deviation (Std).Figure 2
2D versions of unimodal benchmark functions: (a) F1; (b) F2; (c) F3; (d) F4; (e) F5; (f) F7.
(a)
(b)
(c)
(d)
(e)
(f)Figure 3
2D versions of multimodal benchmark functions: (a) F9; (b) F10; (c) F11; (d) F13.
(a)
(b)
(c)
(d)Figure 4
2D versions of fixed-dimensional multimodal benchmark functions: (a) F14; (b) F15; (c) F17; (d) F21.
(a)
(b)
(c)
(d)Table 5
Parameter setting of each algorithm.
Algorithm
Main parameter setting
PSO
VelMin = −6, VelMax = 6,c = 2.5, w = 0.9
APSO
VelMin = −6, VelMax = 6,c1 = c2 = 2.5, w = 0.9, status = “S1”
CSO
SRD = 0.9, MR = 0.3, RangeMin = −30, RangeMax = 30, VelMin = −6, VelMax = 6, c = 1.05,w = 0.6
ACSO
SRD = 0.9, MR = 0.3, RangeMin = −30, RangeMax = 30, VelMin = −6, VelMax = 6,c1 = c2 = 1.05, w = 0.6, status = “S1,” radius = 50Table 6
The statistical results of the algorithms.
Function
PSO
APSO
CSO
ACSO
Average
Standard deviation
Average
Standard deviation
Average
Standard deviation
Average
Standard deviation
F1
4.66 × 104
3.94 × 103
1.46 × 101
7.28 × 100
2.43 × 10−33
3.80 × 10−33
1.62 × 10−48
2.76 × 10−48
F2
3.74 × 1033
6.42 × 1033
4.55 × 101
1.60 × 101
1.50 × 10−19
2.59 × 10−19
4.40 × 10−24
6.61 × 10−24
F3
7.92 × 104
2.85 × 104
5.29 × 103
3.68 × 102
6.36 × 10−27
1.10 × 10−26
45.04 × 10−46
8.73 × 10−46
F4
6.91 × 101
6.46 × 100
3.74 × 100
4.14 × 10−1
2.92 × 10−16
5.06 × 10−16
1.33 × 10−25
2.31 × 10−25
F5
1.83 × 1010
3.53 × 109
7.23 × 103
2.91 × 103
2.88 × 101
3.86 × 10−2
2.84 × 101
1.70 × 10−5
F6
3.89 × 104
1.03 × 104
2.59 × 101
1.52 × 101
2.51 × 100
1.14 × 10−1
3.65 × 100
2.08 × 10−1
F7
2.16 × 109
5.53 × 108
1.09 × 103
4.58 × 102
8.37 × 10−6
6.77 × 10−6
1.58 × 10−6
1.71 × 10−6
F8
−5.69 × 102
4.06 × 101
−1.17 × 103
8.78 × 101
1.22 × 1039
2.12 × 1039
−6.88 × 102
5.27 × 102
F9
4.91 × 104
2.63 × 103
3.19 × 102
4.51 × 101
0
0
0
0
F10
2.12 × 101
6.89 × 10−2
1.77 × 101
4.12 × 100
8.88 × 10−16
0
8.88 × 10−16
0
F11
1.09 × 101
1.31 × 100
4.87 × 10−1
1.09 × 10−1
0
0
0
0
F12
5.97 × 109
2.74 × 109
5.88 × 100
3.74 × 100
2.04 × 10−1
1.67 × 10−1
4.24 × 10−1
5.79 × 10−2
F13
1.13 × 1010
3.68 × 109
2.33 × 101
1.45 × 101
1.30 × 100
5.53 × 10−1
2.68 × 10−4
1.74 × 10−6
F14
1.26 × 101
4.37 × 100
1.33 × 100
5.74 × 10−1
4.33 × 100
2.33 × 100
1.12 × 100
1.38 × 10−1
F15
1.79 × 10−2
1.64 × 10−2
1.01 × 10−3
4.60 × 10−5
8.14 × 10−4
3.56 × 10−4
3.51 × 10−4
2.22 × 10−6
F16
1.53 × 104
2.61 × 104
−1.03 × 100
0
−1.03 × 101
7.17 × 10−4
−1.02 × 100
9.85 × 10−3
F17
1.83 × 100
2.34 × 100
3.98 × 10−1
0
4.02 × 10−1
7.39 × 10−3
3.98 × 10−1
2.97 × 10−5
F18
1.27 × 108
2.06 × 108
3.00
5.44 × 10−16
3.00 × 100
8.84 × 10−4
3.43 × 100
5.22 × 10−1
F19
−2.07 × 10−33
3.58 × 10−33
−3.86 × 100
3.14 × 10−16
−3.72 × 100
1.07 × 10−1
−2.99 × 100
5.14 × 10−1
F20
0
0
−6.59 × 10−1
5.79 × 10−1
−1.85 × 100
7.13 × 10−1
−1.33 × 100
1.54 × 10−1
F21
−3.59 × 10−2
2.85 × 10−2
−3.47 × 100
1.41 × 100
−2.14 × 100
8.35 × 10−1
−1.02 × 101
6.80 × 10−9
F22
−1.91 × 10−2
1.40 × 10−2
−1.04 × 101
1.78 × 10−15
−3.66 × 100
1.04 × 100
−1.04 × 101
3.90 × 10−7
F23
−1.10 × 10−2
1.89 × 10−3
−7.83 × 100
4.69 × 100
−3.00 × 100
7.05 × 10−1
−1.05 × 101
1.38 × 10−7


## 4.2. Experiment Analysis

From Figures5–7, solution quality and speed of PSO, APSO, CSO, and ACSO under 23 benchmark functions can be obtained. The horizontal axis in the figures stand for the maximum number of iterations during program execution and along the vertical axis are the corresponding fitness values. They are the simulation results of unimodal, multimodal, and fixed-dimensional multimodal mathematical test functions.Figure 5
Simulation results for unimodal benchmark functions: (a) F1; (b) F2; (c) F3; (d) F4; (e) F5; (f) F7.
(a)
(b)
(c)
(d)
(e)
(f)Figure 6
Simulation results for multimodal benchmark functions: (a) F9; (b) F10; (c) F11; (d) F13.
(a)
(b)
(c)
(d)Figure 7
Simulation results for fixed-dimension multimodal benchmark functions: (a) F14; (b) F15; (c) F17; (d) F21.
(a)
(b)
(c)
(d)The unimodal function is a continuous function with only one extreme point in the domain; in other words, it has only one global optimum and no local optimum, so these algorithms are used to benchmark it. The performance of ACSO is superior to PSO, APSO, and ACSO. From Figure5, because they contain only one global optimal solution, they have faster search convergence in the function.The multimodal function is a function that contains multiple locally or globally optimal solutions, the purpose of which is to detect whether the test algorithm avoids local optimums. Relatively speaking, the improved algorithm is better than other algorithms, as shown in Figure6. Premature stagnation of the optimal solution appears in F9 and F11. ACSO is better than other algorithms in the benchmark function of F10 and F13. However, the PSO algorithm is known to have the shortcoming of premature convergence in dealing with multimodal optimization problems, owing to the lack of enough momentum for particles to do exploration or exploitation when the algorithm is nearing its end, so it is the worst solution curve.In the fixed-dimensional multimodal function, Figure7 shows the curves of simulation results by all four algorithms, where the curves of APSO, CSO, and ACSO are almost overlapped in F17. From Table 6 and Figures 5–7, observing ACSO, not only can they avoid getting trapped in a local optimum but they can also converge quickly and eventually finding a global optimal solution. Therefore, we conclude that the proposed algorithms are noticeably superior to other comparison algorithms.


## 5. Adaptive Cat Swarm Algorithm Application in Vehicle Routing Problem

In this segment, the projected algorithm is connected to Vehicle Routing Problem (VRP). One of the fundamental problems in logistics has always been VRP, with the core link being cargo distribution. It was originally proposed by Dantzig and Ramser in 1959 [35]. Traditionally, VRP refers to the location of the distribution center that is known, the coordinate requirements and position of every customer, and finding the best route under precise constraints for visiting each customer, with the requirement of the lowest cost in transportation. The VRP has been studied for many years in the fields of mathematics and computer science. It also has the characteristics of nonlinearity, nonconvexity, complexity, and constraints and is difficult to coordinate with each other. In reality, its procedure of solution is quite complicated; therefore, there are certain advantages to solving the issue using an intelligent heuristic algorithm. Many scholars have devoted themselves to solving this problem and its derivative problems. The best known results for VRP have been obtained using Tabu Search (TS) [36, 37] or Simulated Annealing (SA) [38, 39]. In the present paper, VRP is chosen as the application objective of the ACSO algorithm to validate the algorithm’s practicability further.


### 5.1. Description of Constraints

(i)
The total cargo carried by each vehicle must meet its maximum load limit
(ii)
Each vehicle may serve multiple customers, but each customer can only be served by one vehicle
(iii)
Vehiclek should go to the next customer i or returns to the distribution center immediately after serving customer j


### 5.2. Definition of Parameters

The vehicle routing problem is defined on a directed networkG=V,E with a vertex set V=vii=0,1,2,3,…,n, where v0 represents a distribution center, v1,v2,v3,…,vn indicates the set of customers in a directed graph, E=vi,vjvi,vj∈V,i≠j is an edge set, and cij represents the attribute value of each edge.(i)
N=1,2,3,…,n is the collection of all customers(ii)
K=1,2,3,…,k is the collection of all delivery vehicles(iii)
c0 is the unit distance cost(iv)
dij is the distance between the two points i and j(v)
cij is the transportation cost from point i to point j and cij = c0dij(vi)
ri is the customer demands for goods(vii)
W is the maximum load capacity(viii)
Sk is the set of customer points for vehicle k service(14)xijk=1,if vehiclekdepart fromitoj,i,j∈N,0,otherwise,xik=1,if customeriis served by vehiclek,i∈N,k∈K,0,otherwise.The objectives and restrictions of the VRP are then described as follows:(15)minc=∑i=0N∑j=0N∑k=1Kcijxijk,(16)∑i=0N∑k=1Kxijk=1,j∈N,(17)∑i=1N∑j=0Nrixijk≤W,k∈K,(18)∑i=1Nxijk=∑j=1Nxjik,k∈K,(19)∑i,j∈Nxijk=Sk−1,k∈K.In VRP problems, as can be seen from the above model, equation (15) is a multimode function that belongs to the test function, aiming to minimize the objective function with least vehicle distribution cost. The level of distribution costs is the basic requirement for whether the economic benefits of the distribution process are maximized.In a process with supply and demand in existence, formulas (16)–(19) denote the following: equation (16) demonstrates that this condition of constraint ensures a visit to the customer. Only one vehicle is allowed to supply each customer; equation (17) is a cargo flow constraint, requiring the load of the vehicle that cannot exceed the maximum load; equation (18) indicates that the continuity of the vehicle allocation process is constrained; that is, it must start from this point after serving customer i; equation (19) represents that each vehicle is restricted from having no subloops in the path.


### 5.3. Analysis of Experimental Results

In order to verify the effectiveness of ACSO algorithm to solve VRP, experiments were performed using MATLAB R2018b software. The simulation environment is the processor Inter (R) Core (TM) i7-8550U CPU @1.80 GHz 2.00 GHz, PC with Win10 operating system. The iteration is set as 300, and the statistical results of the algorithms used to solve VRP and the three algorithms of CSO, APSO, and PSO are recorded in Table7.Table 7
Comparison of optimal value and running time.
Case
ACSO
CSO
APSO
PSO
Best cost
Time (s)
Best cost
Time (s)
Best cost
Time (s)
Best cost
Time (s)
n14-k4
327.0238
105.9069
350.1766
91.4349
366.7308
93.6879
484.7995
93.8249
n20-k7
356.696
120.8684
374.5871
94.1607
383.2518
97.4590
554.6471
97.5232
n25-k5
489.5978
115.6802
527.2954
91.9872
543.6339
95.5831
695.325
95.8131
n30-k5
612.4174
121.0953
702.9065
94.8490
658.8413
100.1747
960.6692
93.3821
n40-k6
691.7631
137.0174
989.472
98.0159
917.9026
109.4481
1537.5096
94.3153The case column denotes various calculation examples, the Best Cost column represents the optimal value solution, and the Time/s column is representative of the whole time of the running of the algorithm. Through the comparison of the above experiments, it can be seen intuitively, compared with CSO, APSO, and PSO algorithms, the ACSO algorithm has achieved better results and has certain advantages. According to the results of this ACSO algorithm, however, as the number of nodes in the transmission network increases, it will lead to an increase in the time consumed during operation. To a certain extent, it shows that the algorithm still has room for improvement.Table8 presents the optimal consequence of ACSO according to the case n20-k7. Seven vehicles set off from the distribution center, each of them found an optimal path under specific constraints, traversing twenty customers to meet the customer’s cargo needs. Here, zero point represents the distribution center, and numbers from one to twenty denote the customer number. Simultaneously, the optimal path graph is shown in Figure 8. “Star” in the figure represents the distribution center, and “Point” indicates the coordinates of the location of the customer point.Table 8
Optimal consequence of ACSO.
Vehicle number
Delivery route
1
0-15-9-0
2
0-10-16-4-0
3
0-17-2-11-20-0
4
0-7-19-18-8-0
5
0-14-1-13-0
6
0-6-5-0
7
0-12-3-0Figure 8
The path graph corresponding to the optimal value of ACSO.


## 5.1. Description of Constraints

(i)
The total cargo carried by each vehicle must meet its maximum load limit
(ii)
Each vehicle may serve multiple customers, but each customer can only be served by one vehicle
(iii)
Vehiclek should go to the next customer i or returns to the distribution center immediately after serving customer j


## 5.2. Definition of Parameters

The vehicle routing problem is defined on a directed networkG=V,E with a vertex set V=vii=0,1,2,3,…,n, where v0 represents a distribution center, v1,v2,v3,…,vn indicates the set of customers in a directed graph, E=vi,vjvi,vj∈V,i≠j is an edge set, and cij represents the attribute value of each edge.(i)
N=1,2,3,…,n is the collection of all customers(ii)
K=1,2,3,…,k is the collection of all delivery vehicles(iii)
c0 is the unit distance cost(iv)
dij is the distance between the two points i and j(v)
cij is the transportation cost from point i to point j and cij = c0dij(vi)
ri is the customer demands for goods(vii)
W is the maximum load capacity(viii)
Sk is the set of customer points for vehicle k service(14)xijk=1,if vehiclekdepart fromitoj,i,j∈N,0,otherwise,xik=1,if customeriis served by vehiclek,i∈N,k∈K,0,otherwise.The objectives and restrictions of the VRP are then described as follows:(15)minc=∑i=0N∑j=0N∑k=1Kcijxijk,(16)∑i=0N∑k=1Kxijk=1,j∈N,(17)∑i=1N∑j=0Nrixijk≤W,k∈K,(18)∑i=1Nxijk=∑j=1Nxjik,k∈K,(19)∑i,j∈Nxijk=Sk−1,k∈K.In VRP problems, as can be seen from the above model, equation (15) is a multimode function that belongs to the test function, aiming to minimize the objective function with least vehicle distribution cost. The level of distribution costs is the basic requirement for whether the economic benefits of the distribution process are maximized.In a process with supply and demand in existence, formulas (16)–(19) denote the following: equation (16) demonstrates that this condition of constraint ensures a visit to the customer. Only one vehicle is allowed to supply each customer; equation (17) is a cargo flow constraint, requiring the load of the vehicle that cannot exceed the maximum load; equation (18) indicates that the continuity of the vehicle allocation process is constrained; that is, it must start from this point after serving customer i; equation (19) represents that each vehicle is restricted from having no subloops in the path.


## 5.3. Analysis of Experimental Results

In order to verify the effectiveness of ACSO algorithm to solve VRP, experiments were performed using MATLAB R2018b software. The simulation environment is the processor Inter (R) Core (TM) i7-8550U CPU @1.80 GHz 2.00 GHz, PC with Win10 operating system. The iteration is set as 300, and the statistical results of the algorithms used to solve VRP and the three algorithms of CSO, APSO, and PSO are recorded in Table7.Table 7
Comparison of optimal value and running time.
Case
ACSO
CSO
APSO
PSO
Best cost
Time (s)
Best cost
Time (s)
Best cost
Time (s)
Best cost
Time (s)
n14-k4
327.0238
105.9069
350.1766
91.4349
366.7308
93.6879
484.7995
93.8249
n20-k7
356.696
120.8684
374.5871
94.1607
383.2518
97.4590
554.6471
97.5232
n25-k5
489.5978
115.6802
527.2954
91.9872
543.6339
95.5831
695.325
95.8131
n30-k5
612.4174
121.0953
702.9065
94.8490
658.8413
100.1747
960.6692
93.3821
n40-k6
691.7631
137.0174
989.472
98.0159
917.9026
109.4481
1537.5096
94.3153The case column denotes various calculation examples, the Best Cost column represents the optimal value solution, and the Time/s column is representative of the whole time of the running of the algorithm. Through the comparison of the above experiments, it can be seen intuitively, compared with CSO, APSO, and PSO algorithms, the ACSO algorithm has achieved better results and has certain advantages. According to the results of this ACSO algorithm, however, as the number of nodes in the transmission network increases, it will lead to an increase in the time consumed during operation. To a certain extent, it shows that the algorithm still has room for improvement.Table8 presents the optimal consequence of ACSO according to the case n20-k7. Seven vehicles set off from the distribution center, each of them found an optimal path under specific constraints, traversing twenty customers to meet the customer’s cargo needs. Here, zero point represents the distribution center, and numbers from one to twenty denote the customer number. Simultaneously, the optimal path graph is shown in Figure 8. “Star” in the figure represents the distribution center, and “Point” indicates the coordinates of the location of the customer point.Table 8
Optimal consequence of ACSO.
Vehicle number
Delivery route
1
0-15-9-0
2
0-10-16-4-0
3
0-17-2-11-20-0
4
0-7-19-18-8-0
5
0-14-1-13-0
6
0-6-5-0
7
0-12-3-0Figure 8
The path graph corresponding to the optimal value of ACSO.


## 6. Conclusions

In the study, based on the benefits of CSO and APSO, an Adaptive Cat Swarm Optimization (ACSO) algorithm is proposed. Through the cat swarm behaviour in the tracing mode, there is an adaptive adjustment to its parameters. The effectiveness of it has been tested through 23 benchmark functions. This experimental result indicates that ACSO has excellent performance than other existing heuristics in the process of exploration and exploitation.In the end, ACSO is applied to VRP. Numerical assessments on four algorithms (ACSO, CSO, APSO, and PSO) reveal that the best result comes from the proposed ACSO algorithm, which further confirms the practicability and effectiveness of the algorithm. However, during the course of the algorithm, because the evolutionary state needs to be evaluated based on the distance to adjust the adaptive parameters in the tracing mode, it requires much more processing time to make related parameter adjustments. Therefore, the future work is to reduce the running time of the algorithm more reasonably without affecting the group to find the optimal solution.



---

*Source: 1291526-2020-04-21.xml*