# Whether and How to Select Inertia and Acceleration of Discrete Particle Swarm Optimization Algorithm: A Study on Channel Assignment

Authors: Min Jin; Xiangyuan Zhong; Xudong Zhao
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

There is recently a great deal of interest and excitement in understanding the role of inertia and acceleration in the motion equation of discrete particle swarm optimization (DPSO) algorithms. It still remains unknown whether the inertia section should be abandoned and how to select the appropriate acceleration in order for DPSO to show the best convergence performance. Adopting channel assignment as a case study, this paper systematically conducts experimental filtering research on this issue. Compared with other channel assignment schemes, the proposed scheme and the selection of inertia and acceleration are verified to have the advantage to channel assignment in three respects of convergence rate, convergence speed, and the independency of the quality of initial solution. Furthermore, the experimental result implies that DSPO might have the best convergence performance when its motion equation includes an inertia section in a less medium weight, a bigger acceleration coefficient for global-search optimum, and a smaller acceleration coefficient for individual-search optimum.


---

## Body

## 1. Introduction

The ever-increasing popularity of mobile communication services gives rise to the need for efficient use of the limited frequency spectrum [1, 2]. The channel assignment problem (CAP) is to obtain a conflict-free channel assignment scheme, which satisfies both the electromagnetic compatibility (EMC) constrains and regional demand for channel. Generally, there are three types of electromagnetic compatibility constraints. The cochannel constraint (CCC) restricts the assignment of the same channel to certain pairs of cells simultaneously. The adjacent channel constraint (ACC) restricts the assignment of channels adjacent in number to adjacent cells simultaneously. The cosite constraint (CSC) specifies that any pair of channels assigned to the same cell must be separated by a certain number.Currently, much effort has been made to solve the CAP, such as neural network (NN), simulated annealing (SA), and genetic algorithm (GA). However, NN based algorithms typically yield only suboptimal solutions. The SA approach, although it may be more flexible, is easily trapped in a local minimum, which cannot escape without spending a lot of computation time [3]. GA can effectively locate the neighborhood of the global optimum, but it has the problem of converging to the optimum itself. In other words, the algorithms mentioned above are not particularly efficient in local search [4, 5]. Particle swarm optimization (PSO) is an intelligent algorithm introduced by [6]. It does not have the complex genetic operator and thus the computation complexity is reduced greatly. Moreover, due to the parallel computation of particle swarms, the convergence speed of PSO is much faster than GA.In [7], a discrete particle swarm optimization (DPSO) based approach is applied to solve the CAP. The particle’s position is defined as an N-dimensional vector to represent the call orderings (N is the total number of calls in the cellular system). The velocity of particle is defined as a sequence of movements from source particle to target particle, which is randomly selected to update the particle’s position according to the preset inertia factor and acceleration factor. This representation describes the distance between particles properly and reflects the mechanism of evolvement. That means the new position is updated by the particle’s inertia position, the particle’s historical best position, and the swarm’s best position. As the swarm’s best acceleration has more influence on the new velocity than the particle’s inertia velocity and historical best acceleration in the motion equation, the global search performs better than the local search. For this reason, a strategy of local search is introduced during the process of iteration to speed up the convergence. However, the computation complexity is increased and more iteration is needed.In whole, there are two major problems in terms of the application of DPSO to CAP. On one hand, the selection of inertia section and acceleration coefficients has a significant effect on the performance in the motion equation. However, some selection experiences in other fields [8–12] may not be suitable for the CAP. On the other hand, the scheme of frequency exhaust assignment (FEA), a call orderings based strategy, can firstly assign channels to the most difficult cells. Thus, FEA has been proved to be an efficient scheme to solve the CAP with large and unevenly distributed traffic demand. In [5], a call orderings based strategy is proposed. From the result of several benchmark instants for CAP, the assigned channel number is disordered, while the channel number for each cell is sorted in ascending manner by FEA.Adopting channel assignment as a case study, this paper systematically conducts experimental filtering research on the selection of inertia and acceleration in the motion equation in order for DPSO to show the best convergence performance. The rest of this paper is organized as follows. Section2 introduces the mathematical model of CAP and the eight well-known benchmark problems. Section 3 describes the proposed channel assignment scheme which integrates the optimal DPSO with the FEA strategy in order to meet the usually large and unevenly distributed channel demand in many regions. With the experiments on the eight well-known benchmark problems, the results of the inertia choice and the acceleration adjustment are deeply analyzed and a comparison between the proposed scheme and other channel assignment schemes is further made in Section 4. A conclusion is given in Section 5.


## 2. Mathematical Formulation and Benchmark Problems

The CAP is specified by the triple (X, D, C), where X is a cell system, D is a demand vector, and C is an n×n symmetric compatibility matrix. Each element di in D represents the number of channels required by cell i. Each element cij in C represents the minimum separation distance between any two frequencies assigned to cell i and cell j. The solution space F is represented as an n×m binary matrix, where m is the total number of available channels and n is the number of cells. Each element fij in the matrix is either 1 or 0 if fij=1 indicates the channel j is assigned to cell i. So, the mathematical formulation is to minimize z under the following constrains:
(1)∑i=1nfi,j=dii∈[1,n],|p-q|⩾ci,jp,q∈[1,z],i,j∈[1,n]whenfp,i=fq,j=1.In order to prove the performance of the algorithm, some well-known benchmark problems are simulated. Table1 is the specific description of the benchmark problems, and all C and D used here can be found in [13].Table 1
Specific description of the benchmark problems.
Instant
Cell
Channel
C
D
1
4
11
C
1
d
1
2
25
73
C
1
d
2
3
21
381
C
3
d
3
4
21
533
C
4
d
3
5
21
533
C
5
d
3
6
21
221
C
3
d
4
7
21
309
C
4
d
4
8
21
309
C
5
d
4


## 3. DPSO and FEA Combined Channel Assignment Scheme

### 3.1. FEA

Compared with the method of minimum cost function [14–16], FEA has been proved to be an efficient scheme to solve the CAP with large and unevenly distributed traffic demand [17–19]. Denote the number of available frequencies by z and the total number of calls in the system by m with m=∑i=1ndi. The ordered call list can then be identified with a corresponding vector L which contains m different call numbers described as
(2)L=(li)i∈[1,m],li≠ljfori≠j.FEA starts with the first call in the ordered list. Each call with unsatisfied channel requirement is assigned a channel with the lowest rank so that the assignment satisfies all constraints with previous assignment. The pseudocode illustrating the algorithm of FEA is presented in Algorithm1. After applying FEA, the number of blocked calls c is computed to evaluate the fitness of the ordered list.Algorithm 1:Algorithm of FEA.
Loop (L1) for each callli in list L
Loop (L2) for each frequencyf of all zfrequencies (sorted in increasing order)
If assign the current frequency f to li without violation of any EMC constraints
assignf to li
Else
continue;
End (L2)
End (L1)


### 3.2. DPSO

#### 3.2.1. Position of the Particle

Represent the ordered list ofn calls as the position of the particle by vector X with X=(x1,x2,…,xi,…,xn), where xi∈{1,2,…,n}, and i≠j when xi≠xj.


#### 3.2.2. Velocity of the Particle

The best call ordering is determined by applying FEA to the list and evaluating the number of blocked calls. The velocity, used to update the particle’s position to inflect the call orderings, is defined as transfer to particle’s position. Denote the velocity by vectorV=(v1,v2,…,vi,…,vn), where vi∈{1,2,…,n}.


#### 3.2.3. Sum of Position and Velocity

The sum of position and velocity is denoted asX2=X1+V, where X2 is the new position, X1 is the original position, and V is the velocity. When the particle’s position is updated, if vi≠0, exchange the vith call and the xith call in the list and guarantee the feasibility of new position; else keep the ith call unchanged.


#### 3.2.4. Subtraction of Position and Velocity

The result of subtraction of two positions is velocity, denoted asV=X2-X1. For each dimension of X2 and X1, compare x1,i and x2,i one by one. If they are identical, let vi equal 0; else let vi equal x2,i.


#### 3.2.5. External Multiplication of a Coefficient by a Velocity

The external multiplication of a coefficient by a velocity is represented asV2=c·V1, where c is a constant between 0 and 1. For each dimension v1,i of V1, a uniformly distributed random number between 0 and 1 is generated, denoted as rand. If rand⩾c, v2,i=v1,i; else v2,i=0.


#### 3.2.6. Sum of Velocities

The result of sum of two velocities is a new velocity, denoted asV=V1+V2. The new velocity is defined by the equation:
(3)vi={v1,i,v1,i≠0,v2,i=0v1,i,v1,i≠0,v2,i≠0,rand<0.5(i=1,2,…n)v2,i,others.


#### 3.2.7. Motion Equation

Since the peculiarity of CAP, a motion equation is proposed based on [20], in which the inertia section is determined by experience and the coefficients are adjusted finely. Here, is the motion equation
(4)V=wV+c1(Xpbest-X)+c2(Xgbest-X),(5)X=X+V,
where Xpbest is the particle’s historical best position, Xgbest is the swarm’s best position, w is the inertia weight, and c1 and c2 are learning factors. When w equals 0, the inertia section is canceled.With the encoding scheme of call orderings, the upper defined operations can guarantee the feasibility of particle’s position. Meanwhile, the formulation still reflects the optimal mechanism for PSO.


#### 3.2.8. Stopping Criteria

The stopping criterion for DPSO is that the best call ordering meeting all requirements (the number of blocked calls is 0 after applying FEA) is found or the max number of iteration is reached. If the max number is reached and the optimal solution is not found, the algorithm does not converge.


### 3.3. Flowchart of DPSO and FEA Combined Channel Assignment Scheme

The working principle and steps of DPSO and FEA combined channel assignment scheme are described as follows.Step 1.
Input parameters. The parameters are divided into two categories. One is the parameters of PSO, including the size of particle swarm, denoted bysize, the maximum number of iterations, denoted by iteration, inertia weight, denoted by w, and learning factors, denoted by c1 and c2. The other is the parameters of CAP, including the number of cells in cellular system, denoted by N, the number of channels, denoted by M, the matrix of EMC, denoted by C, and the demand vector, denoted by d.Step 2.
Initialize the position and velocity of particles randomly. If the number of calls isn, the initial position is an n dimension vector which represents a randomly ordered call list; and the initial velocity is also an n dimension vector where the ith component vi equals rand(n+1). rand(n+1) is a random number between (0,1].Step 3.
Evaluate the fitness of each particle in the swarm. After applying FEA, the number of blocked calls is computed and the fitness is evaluated. Each particle’s current position and fitness is stored inpbest, and the best of all pbests is stored in gbest. If the stopping criteria are met, output the call ordering represented by gbest and stop the algorithm.Step 4.
Update the velocity and position of each particle by (4) and (5).Step 5.
Evaluate the fitness of each particle in the swarm by computing the number of blocked calls.Step 6.
Compare the fitness of each particle with itspbest. If the current fitness is better, update its pbest with the particle’s current position.Step 7.
Compare each particle’spbest with the swarm’s gbest, update gbest.Step 8.
If the stopping criteria are met, output the call orderings represented bygbest and stops the algorithm, else go to Step 4.


## 3.1. FEA

Compared with the method of minimum cost function [14–16], FEA has been proved to be an efficient scheme to solve the CAP with large and unevenly distributed traffic demand [17–19]. Denote the number of available frequencies by z and the total number of calls in the system by m with m=∑i=1ndi. The ordered call list can then be identified with a corresponding vector L which contains m different call numbers described as
(2)L=(li)i∈[1,m],li≠ljfori≠j.FEA starts with the first call in the ordered list. Each call with unsatisfied channel requirement is assigned a channel with the lowest rank so that the assignment satisfies all constraints with previous assignment. The pseudocode illustrating the algorithm of FEA is presented in Algorithm1. After applying FEA, the number of blocked calls c is computed to evaluate the fitness of the ordered list.Algorithm 1:Algorithm of FEA.
Loop (L1) for each callli in list L
Loop (L2) for each frequencyf of all zfrequencies (sorted in increasing order)
If assign the current frequency f to li without violation of any EMC constraints
assignf to li
Else
continue;
End (L2)
End (L1)


## 3.2. DPSO

### 3.2.1. Position of the Particle

Represent the ordered list ofn calls as the position of the particle by vector X with X=(x1,x2,…,xi,…,xn), where xi∈{1,2,…,n}, and i≠j when xi≠xj.


### 3.2.2. Velocity of the Particle

The best call ordering is determined by applying FEA to the list and evaluating the number of blocked calls. The velocity, used to update the particle’s position to inflect the call orderings, is defined as transfer to particle’s position. Denote the velocity by vectorV=(v1,v2,…,vi,…,vn), where vi∈{1,2,…,n}.


### 3.2.3. Sum of Position and Velocity

The sum of position and velocity is denoted asX2=X1+V, where X2 is the new position, X1 is the original position, and V is the velocity. When the particle’s position is updated, if vi≠0, exchange the vith call and the xith call in the list and guarantee the feasibility of new position; else keep the ith call unchanged.


### 3.2.4. Subtraction of Position and Velocity

The result of subtraction of two positions is velocity, denoted asV=X2-X1. For each dimension of X2 and X1, compare x1,i and x2,i one by one. If they are identical, let vi equal 0; else let vi equal x2,i.


### 3.2.5. External Multiplication of a Coefficient by a Velocity

The external multiplication of a coefficient by a velocity is represented asV2=c·V1, where c is a constant between 0 and 1. For each dimension v1,i of V1, a uniformly distributed random number between 0 and 1 is generated, denoted as rand. If rand⩾c, v2,i=v1,i; else v2,i=0.


### 3.2.6. Sum of Velocities

The result of sum of two velocities is a new velocity, denoted asV=V1+V2. The new velocity is defined by the equation:
(3)vi={v1,i,v1,i≠0,v2,i=0v1,i,v1,i≠0,v2,i≠0,rand<0.5(i=1,2,…n)v2,i,others.


### 3.2.7. Motion Equation

Since the peculiarity of CAP, a motion equation is proposed based on [20], in which the inertia section is determined by experience and the coefficients are adjusted finely. Here, is the motion equation
(4)V=wV+c1(Xpbest-X)+c2(Xgbest-X),(5)X=X+V,
where Xpbest is the particle’s historical best position, Xgbest is the swarm’s best position, w is the inertia weight, and c1 and c2 are learning factors. When w equals 0, the inertia section is canceled.With the encoding scheme of call orderings, the upper defined operations can guarantee the feasibility of particle’s position. Meanwhile, the formulation still reflects the optimal mechanism for PSO.


### 3.2.8. Stopping Criteria

The stopping criterion for DPSO is that the best call ordering meeting all requirements (the number of blocked calls is 0 after applying FEA) is found or the max number of iteration is reached. If the max number is reached and the optimal solution is not found, the algorithm does not converge.


## 3.2.1. Position of the Particle

Represent the ordered list ofn calls as the position of the particle by vector X with X=(x1,x2,…,xi,…,xn), where xi∈{1,2,…,n}, and i≠j when xi≠xj.


## 3.2.2. Velocity of the Particle

The best call ordering is determined by applying FEA to the list and evaluating the number of blocked calls. The velocity, used to update the particle’s position to inflect the call orderings, is defined as transfer to particle’s position. Denote the velocity by vectorV=(v1,v2,…,vi,…,vn), where vi∈{1,2,…,n}.


## 3.2.3. Sum of Position and Velocity

The sum of position and velocity is denoted asX2=X1+V, where X2 is the new position, X1 is the original position, and V is the velocity. When the particle’s position is updated, if vi≠0, exchange the vith call and the xith call in the list and guarantee the feasibility of new position; else keep the ith call unchanged.


## 3.2.4. Subtraction of Position and Velocity

The result of subtraction of two positions is velocity, denoted asV=X2-X1. For each dimension of X2 and X1, compare x1,i and x2,i one by one. If they are identical, let vi equal 0; else let vi equal x2,i.


## 3.2.5. External Multiplication of a Coefficient by a Velocity

The external multiplication of a coefficient by a velocity is represented asV2=c·V1, where c is a constant between 0 and 1. For each dimension v1,i of V1, a uniformly distributed random number between 0 and 1 is generated, denoted as rand. If rand⩾c, v2,i=v1,i; else v2,i=0.


## 3.2.6. Sum of Velocities

The result of sum of two velocities is a new velocity, denoted asV=V1+V2. The new velocity is defined by the equation:
(3)vi={v1,i,v1,i≠0,v2,i=0v1,i,v1,i≠0,v2,i≠0,rand<0.5(i=1,2,…n)v2,i,others.


## 3.2.7. Motion Equation

Since the peculiarity of CAP, a motion equation is proposed based on [20], in which the inertia section is determined by experience and the coefficients are adjusted finely. Here, is the motion equation
(4)V=wV+c1(Xpbest-X)+c2(Xgbest-X),(5)X=X+V,
where Xpbest is the particle’s historical best position, Xgbest is the swarm’s best position, w is the inertia weight, and c1 and c2 are learning factors. When w equals 0, the inertia section is canceled.With the encoding scheme of call orderings, the upper defined operations can guarantee the feasibility of particle’s position. Meanwhile, the formulation still reflects the optimal mechanism for PSO.


## 3.2.8. Stopping Criteria

The stopping criterion for DPSO is that the best call ordering meeting all requirements (the number of blocked calls is 0 after applying FEA) is found or the max number of iteration is reached. If the max number is reached and the optimal solution is not found, the algorithm does not converge.


## 3.3. Flowchart of DPSO and FEA Combined Channel Assignment Scheme

The working principle and steps of DPSO and FEA combined channel assignment scheme are described as follows.Step 1.
Input parameters. The parameters are divided into two categories. One is the parameters of PSO, including the size of particle swarm, denoted bysize, the maximum number of iterations, denoted by iteration, inertia weight, denoted by w, and learning factors, denoted by c1 and c2. The other is the parameters of CAP, including the number of cells in cellular system, denoted by N, the number of channels, denoted by M, the matrix of EMC, denoted by C, and the demand vector, denoted by d.Step 2.
Initialize the position and velocity of particles randomly. If the number of calls isn, the initial position is an n dimension vector which represents a randomly ordered call list; and the initial velocity is also an n dimension vector where the ith component vi equals rand(n+1). rand(n+1) is a random number between (0,1].Step 3.
Evaluate the fitness of each particle in the swarm. After applying FEA, the number of blocked calls is computed and the fitness is evaluated. Each particle’s current position and fitness is stored inpbest, and the best of all pbests is stored in gbest. If the stopping criteria are met, output the call ordering represented by gbest and stop the algorithm.Step 4.
Update the velocity and position of each particle by (4) and (5).Step 5.
Evaluate the fitness of each particle in the swarm by computing the number of blocked calls.Step 6.
Compare the fitness of each particle with itspbest. If the current fitness is better, update its pbest with the particle’s current position.Step 7.
Compare each particle’spbest with the swarm’s gbest, update gbest.Step 8.
If the stopping criteria are met, output the call orderings represented bygbest and stops the algorithm, else go to Step 4.


## 4. Filtering Experiments and Result Analysis

### 4.1. Inertia Choice and Acceleration Adjustment

The algorithm is written in C#. In order to prove the performance of the algorithm, some well-known benchmark problems are simulated, which can be found in [13]. The efficiency of algorithm is evaluated by the convergence rate (CR) and the convergence speed (CS). The CR is defined as the number of times that the optimum solution is found by executing the algorithm 100 times. The CS is defined as the average number of iteration that the optimum solution is found by executing the algorithm 100 times. Generally, the selection of inertia and acceleration in motion equation and whether to include inertia may affect the algorithm’s performance greatly. In this simulation, the algorithm is performed and evaluated without inertia and with inertia. The value of the inertia weight and the learning factors (namely the acceleration coefficients) c1, c2 are also determined based on these two conditions by experiment.


#### 4.1.1. Without Inertia (w=0 in (4))

A group of coeffiecient pairs between[0,1] is selected to determine the best acceleration coefficients c1, c2 by applying this algorithm to single benchmark Problem 8. Table 2 is the CR and CS of Problem 8.Table 2
CS and CR of Problem 8 without inertia.
c
1
c
2
0.0
0.2
0.4
0.6
0.8
1.0
0.0
CR
68
100
100
100
100
67
CS
48.68
1.65
1.45
1.42
1.39
50.17
0.2
CR
100
100
100
100
100
68
CS
2.24
2.01
1.59
1.22
1.39
48.68
0.4
CR
100
100
100
100
100
75
CS
2.81
1.66
1.47
1.39
1.3
38.25
0.6
CR
100
100
100
100
100
76
CS
2.2
2.12
1.37
1.52
1.31
36.76
0.8
CR
100
100
100
100
100
67
CS
2.88
3.1
1.61
1.59
1.19
50.17
1.0
CR
66
100
100
100
100
70
CS
51.66
24.87
26.4
5.56
5.59
45.7From Table2, we can draw two conclusions. One is the algorithm cannot reach 100% CR when c2 equals 1.0. The other is, when c1 keeps constant, the CS becomes faster as c2 increases. When c2 equals 0.8, the CS is fastest. However, the situation is invalid in two marginal cases (0.0 and 1.0). When c2 keeps constant, the selection of c1 has no certain impact on CS. When c1 equals 0.4, the average number of iteration is smallest (1.455) except for c2 equals 0.0 and 1.0. When the coefficients c1/c2 select 0.8/0.8, the best CS is obtained (1.19).As the result is obtained by only one benchmark problem, we select a group of coefficients pairs between[0.2,0.8], apply these coefficients to all benchmark problems (except for the simple Problem 1 and 2) and execute all the 6 problems for 5 trials to obtain the best average CS under different coefficients. The CS of each problem under different coefficient is shown in Figure 1 and the average CS of Problem 8 for each trial is listed in Table 3.Table 3
Average CS of Problem 8 without inertia.
c
1
/
c
2
Trial
1
2
3
4
5
avg
0.2/0.2
1.28
1.19
1.17
1.23
1.23
1.22
0.2/0.4
1.25
1.14
1.17
1.13
1.22
1.18
0.2/0.6
1.17
1.17
1.18
1.12
1.20
1.17
0.2/0.8
1.18
1.16
1.27
1.27
1.29
1.23
0.4/0.2
1.15
1.22
1.21
1.23
1.27
1.21
0.4/0.4
1.22
1.16
1.12
1.13
1.18
1.16
0.4/0.6
1.20
1.16
1.19
1.21
1.17
1.19
0.4/0.8
1.18
1.27
1.26
1.19
1.26
1.23
0.6/0.2
1.37
1.31
1.19
1.32
1.33
1.30
0.6/0.4
1.23
1.20
1.24
1.27
1.18
1.22
0.6/0.6
1.26
1.14
1.27
1.23
1.19
1.22
0.6/0.8
1.16
1.19
1.22
1.24
1.14
1.19
0.8/0.2
1.51
1.68
1.53
1.75
1.55
1.60
0.8/0.4
1.38
1.23
1.33
1.36
1.41
1.34
0.8/0.6
1.23
1.14
1.20
1.19
1.37
1.23
0.8/0.8
1.21
1.21
1.27
1.19
1.17
1.21Figure 1
Average CS of all problems.From Figure1, we can conclude the following three conclusions. First, for complex problems, like Problems 5 and 8 which are denoted as blue and purple lines, when c2 keeps constant, the average number of iteration increases as c1 increases. While c2 equals 0.8, this situation is different. Second, for complex problems like Problem 5 and 8, when c1 keeps constant, the number of iteration decreases as c2 increases. Third, for other simple problems, the feature is not obvious as the number of iteration is smaller. From Table 3, we can conclude the following two conclusions. First, for all the benchmark problems, when the coefficient pair c1/c2 selects 0.4/0.4, the least average number of iteration (1.16) is obtained. Second, the largest average number of iteration (1.60) is obtained when c1 equals 0.8 and c2 equals 0.2. The same conclusion that the average number of iteration increases as c1 increases when c2 keeps constant is obtained as the conclusion obtained from Figure 1.Thus, for single benchmark problem and all benchmark problems, the algorithm performs best when the coefficient pairc1/c2 selects 0.2/0.8 and w equals 0. This selection means that the convergence speed can be improved by choosing bigger acceleration coefficient to control the global-search optimum and choosing smaller acceleration coefficient to control the individual-search optimum without inertia section in motion equation for CAP.


#### 4.1.2. With Inertia (w≠0 in (4))

From the results obtained above, the acceleration coefficientsc1, c2 are set to be 0.2 and 0.8, respectively. A group of coefficients between [0,1] are selected to determine the best inertia weight w by applying this algorithm to all benchmark problems. Table 4 is the result for average CS obtained when w equals 0.0, 0.2, 0.4, 0.6, 0.8, and 1.0, respectively.Table 4
CS of all problems with inertia.
w
Benchmark problem
1
2
3
4
5
6
7
8
0.0
1.00
1.00
1.32
1.31
1.83
1.05
1.00
1.37
0.2
1.00
1.00
1.11
1.02
1.35
1.02
1.00
1.27
0.4
1.00
1.00
1.11
1.03
1.35
1.01
1.00
1.21
0.6
1.00
1.00
1.23
1.06
1.37
1.03
1.00
1.27
0.8
1.00
1.00
1.15
1.07
1.63
1.02
1.00
1.33
1.0
1.00
1.00
1.33
1.18
1.72
1.04
1.01
1.45From Table4, when w equals 0.4, the algorithm performs best for all benchmark problems and does better than it performs when w equals 0.0 (without inertia).In summary, in the simulation, this algorithm defines a motion equation with inertia section and whenw, c1, and c2 select 0.4, 0.2, and 0.8, respectively, the algorithm performs best. Besides, the swarm size of this algorithm is 10 and the max number of iteration is set to be 150 in the simulation.


### 4.2. Comparison of CS and CR

The quality of initial solution has an important influence on the CR and the CS for DPSO. To eliminate the initial solution’s impact and evaluate the algorithm’s performance objectively, we compute the results with one time and more than one time of iteration respectively, and compare these results with the results obtained from the latest literatures where literature [5] is based on DPSO, literature [21] is based on culture algorithm, and literature [22] is based on genetic algorithm. Table 5 is the result.Table 5
Comparison of CS and CR.
Method
Benchmark Problem
1
2
3
4
5
6
7
8
One
CS#
1
1
1.11
1.03
1.35
1.01
1
1.21
CR%
100
100
100
100
100
100
100
100
>one
CS#
1
1.4
2
3
3.44
4
2.6
3
CR%
100
100
100
100
100
100
100
100
[6]
CS#
1
5
30
40
55
60
50
60
CR%
100
100
100
100
100
100
100
100
[18]
CS#
1
2
2
2
2.25
2.75
3.52
4
CR%
100
100
100
100
100
100
100
100
[19]
CS#
1
2284.6
34.7
12.0
—
136.5
20.2
1977.0
CR%
100
100
100
100
—
100
100
98The result shows that the proposed algorithm achieves 100 percent convergence rate for all benchmark problems. In the experiment, for simple problems, like Problems 1, 2, and 7, the optimum can be obtained by only one time of iteration. Even for the complex problems like Problems 5 and 8, the algorithm achieves a fast convergence speed. Excluding the impact of initial population on the algorithm, 100 percent convergence rate is still achieved for all benchmark problems and the optimum solution is obtained after 5 times of iteration at most.The result is better than that in [5], where the new velocity is defined as sequential sum of three movement components in the motion equation. For this reason, extra computation is needed and the movement will influence each other, which slows down the CS. The result is also better than culture algorithm and genetic algorithm based approaches which proves that the DPSO and FEA combined scheme with the selection of inertia and acceleration is an efficient approach for CAP.


## 4.1. Inertia Choice and Acceleration Adjustment

The algorithm is written in C#. In order to prove the performance of the algorithm, some well-known benchmark problems are simulated, which can be found in [13]. The efficiency of algorithm is evaluated by the convergence rate (CR) and the convergence speed (CS). The CR is defined as the number of times that the optimum solution is found by executing the algorithm 100 times. The CS is defined as the average number of iteration that the optimum solution is found by executing the algorithm 100 times. Generally, the selection of inertia and acceleration in motion equation and whether to include inertia may affect the algorithm’s performance greatly. In this simulation, the algorithm is performed and evaluated without inertia and with inertia. The value of the inertia weight and the learning factors (namely the acceleration coefficients) c1, c2 are also determined based on these two conditions by experiment.


### 4.1.1. Without Inertia (w=0 in (4))

A group of coeffiecient pairs between[0,1] is selected to determine the best acceleration coefficients c1, c2 by applying this algorithm to single benchmark Problem 8. Table 2 is the CR and CS of Problem 8.Table 2
CS and CR of Problem 8 without inertia.
c
1
c
2
0.0
0.2
0.4
0.6
0.8
1.0
0.0
CR
68
100
100
100
100
67
CS
48.68
1.65
1.45
1.42
1.39
50.17
0.2
CR
100
100
100
100
100
68
CS
2.24
2.01
1.59
1.22
1.39
48.68
0.4
CR
100
100
100
100
100
75
CS
2.81
1.66
1.47
1.39
1.3
38.25
0.6
CR
100
100
100
100
100
76
CS
2.2
2.12
1.37
1.52
1.31
36.76
0.8
CR
100
100
100
100
100
67
CS
2.88
3.1
1.61
1.59
1.19
50.17
1.0
CR
66
100
100
100
100
70
CS
51.66
24.87
26.4
5.56
5.59
45.7From Table2, we can draw two conclusions. One is the algorithm cannot reach 100% CR when c2 equals 1.0. The other is, when c1 keeps constant, the CS becomes faster as c2 increases. When c2 equals 0.8, the CS is fastest. However, the situation is invalid in two marginal cases (0.0 and 1.0). When c2 keeps constant, the selection of c1 has no certain impact on CS. When c1 equals 0.4, the average number of iteration is smallest (1.455) except for c2 equals 0.0 and 1.0. When the coefficients c1/c2 select 0.8/0.8, the best CS is obtained (1.19).As the result is obtained by only one benchmark problem, we select a group of coefficients pairs between[0.2,0.8], apply these coefficients to all benchmark problems (except for the simple Problem 1 and 2) and execute all the 6 problems for 5 trials to obtain the best average CS under different coefficients. The CS of each problem under different coefficient is shown in Figure 1 and the average CS of Problem 8 for each trial is listed in Table 3.Table 3
Average CS of Problem 8 without inertia.
c
1
/
c
2
Trial
1
2
3
4
5
avg
0.2/0.2
1.28
1.19
1.17
1.23
1.23
1.22
0.2/0.4
1.25
1.14
1.17
1.13
1.22
1.18
0.2/0.6
1.17
1.17
1.18
1.12
1.20
1.17
0.2/0.8
1.18
1.16
1.27
1.27
1.29
1.23
0.4/0.2
1.15
1.22
1.21
1.23
1.27
1.21
0.4/0.4
1.22
1.16
1.12
1.13
1.18
1.16
0.4/0.6
1.20
1.16
1.19
1.21
1.17
1.19
0.4/0.8
1.18
1.27
1.26
1.19
1.26
1.23
0.6/0.2
1.37
1.31
1.19
1.32
1.33
1.30
0.6/0.4
1.23
1.20
1.24
1.27
1.18
1.22
0.6/0.6
1.26
1.14
1.27
1.23
1.19
1.22
0.6/0.8
1.16
1.19
1.22
1.24
1.14
1.19
0.8/0.2
1.51
1.68
1.53
1.75
1.55
1.60
0.8/0.4
1.38
1.23
1.33
1.36
1.41
1.34
0.8/0.6
1.23
1.14
1.20
1.19
1.37
1.23
0.8/0.8
1.21
1.21
1.27
1.19
1.17
1.21Figure 1
Average CS of all problems.From Figure1, we can conclude the following three conclusions. First, for complex problems, like Problems 5 and 8 which are denoted as blue and purple lines, when c2 keeps constant, the average number of iteration increases as c1 increases. While c2 equals 0.8, this situation is different. Second, for complex problems like Problem 5 and 8, when c1 keeps constant, the number of iteration decreases as c2 increases. Third, for other simple problems, the feature is not obvious as the number of iteration is smaller. From Table 3, we can conclude the following two conclusions. First, for all the benchmark problems, when the coefficient pair c1/c2 selects 0.4/0.4, the least average number of iteration (1.16) is obtained. Second, the largest average number of iteration (1.60) is obtained when c1 equals 0.8 and c2 equals 0.2. The same conclusion that the average number of iteration increases as c1 increases when c2 keeps constant is obtained as the conclusion obtained from Figure 1.Thus, for single benchmark problem and all benchmark problems, the algorithm performs best when the coefficient pairc1/c2 selects 0.2/0.8 and w equals 0. This selection means that the convergence speed can be improved by choosing bigger acceleration coefficient to control the global-search optimum and choosing smaller acceleration coefficient to control the individual-search optimum without inertia section in motion equation for CAP.


### 4.1.2. With Inertia (w≠0 in (4))

From the results obtained above, the acceleration coefficientsc1, c2 are set to be 0.2 and 0.8, respectively. A group of coefficients between [0,1] are selected to determine the best inertia weight w by applying this algorithm to all benchmark problems. Table 4 is the result for average CS obtained when w equals 0.0, 0.2, 0.4, 0.6, 0.8, and 1.0, respectively.Table 4
CS of all problems with inertia.
w
Benchmark problem
1
2
3
4
5
6
7
8
0.0
1.00
1.00
1.32
1.31
1.83
1.05
1.00
1.37
0.2
1.00
1.00
1.11
1.02
1.35
1.02
1.00
1.27
0.4
1.00
1.00
1.11
1.03
1.35
1.01
1.00
1.21
0.6
1.00
1.00
1.23
1.06
1.37
1.03
1.00
1.27
0.8
1.00
1.00
1.15
1.07
1.63
1.02
1.00
1.33
1.0
1.00
1.00
1.33
1.18
1.72
1.04
1.01
1.45From Table4, when w equals 0.4, the algorithm performs best for all benchmark problems and does better than it performs when w equals 0.0 (without inertia).In summary, in the simulation, this algorithm defines a motion equation with inertia section and whenw, c1, and c2 select 0.4, 0.2, and 0.8, respectively, the algorithm performs best. Besides, the swarm size of this algorithm is 10 and the max number of iteration is set to be 150 in the simulation.


## 4.1.1. Without Inertia (w=0 in (4))

A group of coeffiecient pairs between[0,1] is selected to determine the best acceleration coefficients c1, c2 by applying this algorithm to single benchmark Problem 8. Table 2 is the CR and CS of Problem 8.Table 2
CS and CR of Problem 8 without inertia.
c
1
c
2
0.0
0.2
0.4
0.6
0.8
1.0
0.0
CR
68
100
100
100
100
67
CS
48.68
1.65
1.45
1.42
1.39
50.17
0.2
CR
100
100
100
100
100
68
CS
2.24
2.01
1.59
1.22
1.39
48.68
0.4
CR
100
100
100
100
100
75
CS
2.81
1.66
1.47
1.39
1.3
38.25
0.6
CR
100
100
100
100
100
76
CS
2.2
2.12
1.37
1.52
1.31
36.76
0.8
CR
100
100
100
100
100
67
CS
2.88
3.1
1.61
1.59
1.19
50.17
1.0
CR
66
100
100
100
100
70
CS
51.66
24.87
26.4
5.56
5.59
45.7From Table2, we can draw two conclusions. One is the algorithm cannot reach 100% CR when c2 equals 1.0. The other is, when c1 keeps constant, the CS becomes faster as c2 increases. When c2 equals 0.8, the CS is fastest. However, the situation is invalid in two marginal cases (0.0 and 1.0). When c2 keeps constant, the selection of c1 has no certain impact on CS. When c1 equals 0.4, the average number of iteration is smallest (1.455) except for c2 equals 0.0 and 1.0. When the coefficients c1/c2 select 0.8/0.8, the best CS is obtained (1.19).As the result is obtained by only one benchmark problem, we select a group of coefficients pairs between[0.2,0.8], apply these coefficients to all benchmark problems (except for the simple Problem 1 and 2) and execute all the 6 problems for 5 trials to obtain the best average CS under different coefficients. The CS of each problem under different coefficient is shown in Figure 1 and the average CS of Problem 8 for each trial is listed in Table 3.Table 3
Average CS of Problem 8 without inertia.
c
1
/
c
2
Trial
1
2
3
4
5
avg
0.2/0.2
1.28
1.19
1.17
1.23
1.23
1.22
0.2/0.4
1.25
1.14
1.17
1.13
1.22
1.18
0.2/0.6
1.17
1.17
1.18
1.12
1.20
1.17
0.2/0.8
1.18
1.16
1.27
1.27
1.29
1.23
0.4/0.2
1.15
1.22
1.21
1.23
1.27
1.21
0.4/0.4
1.22
1.16
1.12
1.13
1.18
1.16
0.4/0.6
1.20
1.16
1.19
1.21
1.17
1.19
0.4/0.8
1.18
1.27
1.26
1.19
1.26
1.23
0.6/0.2
1.37
1.31
1.19
1.32
1.33
1.30
0.6/0.4
1.23
1.20
1.24
1.27
1.18
1.22
0.6/0.6
1.26
1.14
1.27
1.23
1.19
1.22
0.6/0.8
1.16
1.19
1.22
1.24
1.14
1.19
0.8/0.2
1.51
1.68
1.53
1.75
1.55
1.60
0.8/0.4
1.38
1.23
1.33
1.36
1.41
1.34
0.8/0.6
1.23
1.14
1.20
1.19
1.37
1.23
0.8/0.8
1.21
1.21
1.27
1.19
1.17
1.21Figure 1
Average CS of all problems.From Figure1, we can conclude the following three conclusions. First, for complex problems, like Problems 5 and 8 which are denoted as blue and purple lines, when c2 keeps constant, the average number of iteration increases as c1 increases. While c2 equals 0.8, this situation is different. Second, for complex problems like Problem 5 and 8, when c1 keeps constant, the number of iteration decreases as c2 increases. Third, for other simple problems, the feature is not obvious as the number of iteration is smaller. From Table 3, we can conclude the following two conclusions. First, for all the benchmark problems, when the coefficient pair c1/c2 selects 0.4/0.4, the least average number of iteration (1.16) is obtained. Second, the largest average number of iteration (1.60) is obtained when c1 equals 0.8 and c2 equals 0.2. The same conclusion that the average number of iteration increases as c1 increases when c2 keeps constant is obtained as the conclusion obtained from Figure 1.Thus, for single benchmark problem and all benchmark problems, the algorithm performs best when the coefficient pairc1/c2 selects 0.2/0.8 and w equals 0. This selection means that the convergence speed can be improved by choosing bigger acceleration coefficient to control the global-search optimum and choosing smaller acceleration coefficient to control the individual-search optimum without inertia section in motion equation for CAP.


## 4.1.2. With Inertia (w≠0 in (4))

From the results obtained above, the acceleration coefficientsc1, c2 are set to be 0.2 and 0.8, respectively. A group of coefficients between [0,1] are selected to determine the best inertia weight w by applying this algorithm to all benchmark problems. Table 4 is the result for average CS obtained when w equals 0.0, 0.2, 0.4, 0.6, 0.8, and 1.0, respectively.Table 4
CS of all problems with inertia.
w
Benchmark problem
1
2
3
4
5
6
7
8
0.0
1.00
1.00
1.32
1.31
1.83
1.05
1.00
1.37
0.2
1.00
1.00
1.11
1.02
1.35
1.02
1.00
1.27
0.4
1.00
1.00
1.11
1.03
1.35
1.01
1.00
1.21
0.6
1.00
1.00
1.23
1.06
1.37
1.03
1.00
1.27
0.8
1.00
1.00
1.15
1.07
1.63
1.02
1.00
1.33
1.0
1.00
1.00
1.33
1.18
1.72
1.04
1.01
1.45From Table4, when w equals 0.4, the algorithm performs best for all benchmark problems and does better than it performs when w equals 0.0 (without inertia).In summary, in the simulation, this algorithm defines a motion equation with inertia section and whenw, c1, and c2 select 0.4, 0.2, and 0.8, respectively, the algorithm performs best. Besides, the swarm size of this algorithm is 10 and the max number of iteration is set to be 150 in the simulation.


## 4.2. Comparison of CS and CR

The quality of initial solution has an important influence on the CR and the CS for DPSO. To eliminate the initial solution’s impact and evaluate the algorithm’s performance objectively, we compute the results with one time and more than one time of iteration respectively, and compare these results with the results obtained from the latest literatures where literature [5] is based on DPSO, literature [21] is based on culture algorithm, and literature [22] is based on genetic algorithm. Table 5 is the result.Table 5
Comparison of CS and CR.
Method
Benchmark Problem
1
2
3
4
5
6
7
8
One
CS#
1
1
1.11
1.03
1.35
1.01
1
1.21
CR%
100
100
100
100
100
100
100
100
>one
CS#
1
1.4
2
3
3.44
4
2.6
3
CR%
100
100
100
100
100
100
100
100
[6]
CS#
1
5
30
40
55
60
50
60
CR%
100
100
100
100
100
100
100
100
[18]
CS#
1
2
2
2
2.25
2.75
3.52
4
CR%
100
100
100
100
100
100
100
100
[19]
CS#
1
2284.6
34.7
12.0
—
136.5
20.2
1977.0
CR%
100
100
100
100
—
100
100
98The result shows that the proposed algorithm achieves 100 percent convergence rate for all benchmark problems. In the experiment, for simple problems, like Problems 1, 2, and 7, the optimum can be obtained by only one time of iteration. Even for the complex problems like Problems 5 and 8, the algorithm achieves a fast convergence speed. Excluding the impact of initial population on the algorithm, 100 percent convergence rate is still achieved for all benchmark problems and the optimum solution is obtained after 5 times of iteration at most.The result is better than that in [5], where the new velocity is defined as sequential sum of three movement components in the motion equation. For this reason, extra computation is needed and the movement will influence each other, which slows down the CS. The result is also better than culture algorithm and genetic algorithm based approaches which proves that the DPSO and FEA combined scheme with the selection of inertia and acceleration is an efficient approach for CAP.


## 5. Conclusion

Adopting the channel assignment on the eight well-known benchmark problems as a case study, this paper systematically conducts experimental filtering research on the selection of inertia and acceleration in the motion equation of DPSO. A channel assignment scheme integrating the optimal DPSO with frequency exhaust assignment (FEA) strategy was proposed to meet the usually large and unevenly distributed channel demand in many regions. Compared with other channel assignment schemes, the proposed scheme with the optical inertia weight and acceleration coefficients achieves 100 percent convergence rate for all benchmark problems and the convergence speed is faster than others without dependence on the quality of initial solution. For cellular systems with high number of cells, this proposed scheme with the optical inertia weight and acceleration coefficients can also be efficiently applied to find the exact solution in an acceptable time of computation. Furthermore, the filtering result on the eight well-known benchmark problems demonstrates that the optimal inertia weight is 0.4 and the two optimal acceleration coefficients are 0.2 and 0.8, respectively. This result implies that DSPO might be of the best convergence performance when its motion equation includes an inertia section in a less medium weight, a bigger acceleration coefficient for global-search optimum, and a smaller acceleration coefficient for individual-search optimum.



---

*Source: 758906-2014-01-05.xml*