# Improved Barebones Particle Swarm Optimization with Neighborhood Search and Its Application on Ship Design

Authors: Jingzheng Yao; Duanfeng Han
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

Barebones particle swarm optimization (BPSO) is a new PSO variant, which has shown a good performance on many optimization problems. However, similar to the standard PSO, BPSO also suffers from premature convergence when solving complex optimization problems. In order to improve the performance of BPSO, this paper proposes a new BPSO variant called BPSO with neighborhood search (NSBPSO) to achieve a tradeoff between exploration and exploitation during the search process. Experiments are conducted on twelve benchmark functions and a real-world problem of ship design. Simulation results demonstrate that our approach outperforms the standard PSO, BPSO, and six other improved PSO algorithms.


---

## Body

## 1. Introduction

Particle swarm optimization (PSO), developed by Kennedy and Eberhart [1], is a new optimization technique inspired by swarm intelligence. Liker other evolutionary algorithms (EAs), PSO is also a population-based stochastic search algorithm, but it does not contain any crossover or mutation operator. During the search process, each particle adjusts its search behavior according to the search experiences of its previous best position (pbest) and the global best position (gbest). Due to its simplicity and easy implementation, PSO has been successfully applied to various practical optimization problems [2–5].However, like other stochastic algorithms, PSO also suffers from premature convergence when handling complex multimodal problems. The main reason is that the attraction search pattern of PSO greatly depends onpbest and gbest. Once these best particles (pbest and gbest) get stuck, all particles in the swarm will quickly converge to the trapped position. In order to enhance the performance of PSO, different versions of PSO have been proposed in the past decades. Shi and Eberhart [6] introduced an inertia weight w into the original PSO to achieve a balance between the global and local search. Reported results show that a linearly decreased w is a parameter setting. Parsopoulos and Vrahaits [7] proposed a unified PSO (UPSO) which is a hybrid algorithm by combining the global and local versions of PSO. In [8], a fully informed PSO, called FIPS, is proposed by employing a modified velocity model. van den Bergh and Engelbrecht [9] used a cooperative mechanism to improve the performance of PSO on multimodal optimization problems. In the standard PSO, particles are attracted by their corresponding previous best particles and the global best particle. This search pattern is a greedy method which may result in premature convergence. To tackle this problem, Liang et al. [10] proposed a comprehensive learning PSO (CLPSO), in which each particle can be attracted by different previous best positions. Computational results on a set of multimodal problems demonstrate the effectiveness of CLPSO. In [11], Wang et al. proposed a new PSO algorithm (NSPSO) to search the neighbors of particles. This can provide more chances of finding better candidate solutions. Simulation studies show that NSPSO outperforms UPSO, FIPS, CPSO-H, and CLPSO. In [12], another version of NSPSO is proposed by employing neighborhood search and diversity enhanced mechanism.Similar to other EAs, the performance of PSO also greatly depends on its control parameters,w, c1, and c2.    The first parameter is known as inertia weight, and the last two are acceleration coefficients. Slight differences of these parameters may result in significantly different performance. To tackle this problem, some PSO variants based on adaptive parameters have been proposed to minimize the dependency of these parameters [13, 14]. Compared to these adaptive PSO algorithms, Kennedy developed a novel PSO called barebones PSO (BPSO) [15], which eliminates the velocity term and does not contain the parameters w, c1, and c2. In BPSO, a Gaussian sampling is used to generate new positions of particles. Empirical studies demonstrate that the performance of BPSO is competitive to the standard PSO and some improved PSO algorithms. Inspired by the idea of BPSO, some new algorithms haven been proposed. In [16], Omran et al. combined BPSO with differential evolution (DE) and the proposed barebones DE (BBDE). The reported results show that BBDE outperforms the standard DE and BPSO and it also achieves promising solutions for unsupervised image classification. Krohling and Mendel [17] introduced Gaussian and Cauchy mutations into BPSO to improve its performance. Experimental studies on a suite of well-known multimodal benchmark functions demonstrate the effectiveness of this approach. Blackwell [18] presented a theoretical analysis of BPSO. A series of experimental trials confirmed that the BPSO situated at the edge of collapse is comparable to other PSO algorithms and that performance can be still further improved with the use of an adaptive distribution. In [19], Wang embedded opposition-based learning (OBL) into BPSO to solve constrained nonlinear optimization problems. In addition, a new boundary search strategy is utilized. Simulation studies on thirteen constrained benchmark functions show that the new approach outperforms PSO, BPSO, and six other improved PSO algorithms.In this paper, we also propose an improved barebones PSO called NSBPSO which employs a global and local neighborhood search strategies to make a balance between exploration and exploitation during the search process. In order to verify the performance of NSBPSO, twelve well-known benchmark functions and a real-world problem on ship design are used in the experiments. Computational results show that our approach outperforms PSO, BPSO, and several other improved PSO variants in terms of the quality of solutions.The rest of the paper is organized as follows. The standard PSO and barebones PSO are given in Section2. In Section 3, our approach NSBPSO is proposed. Experimental studies are presented in Section 4. Section 5 presents a real-world application on ship design. Finally, the work is summarized in Section 6.


## 2. Barebones Particle Swarm Optimization

PSO is a population-based stochastic search algorithm, which simulates the behaviors of fish schooling or birds flocking. Each particle has a velocity and a position vectors. During the search space, a particle dynamically adjusts its velocity to generate a new position as follows:(1)Vi(t+1)=w·Vi(t)+c1·r1·(pbesti-Xi(t))+c2·r2·(gbest-Xi(t)),Xi(t+1)=Xi(t)+Vi(t+1),
where Xi and Vi are the position and velocity vector for the ith particle, respectively. pbesti is the previous best particle of the ith particle and gbest is the global best particle. r1 and r2 are two independently generated random numbers within [0,1]. The parameter w is known as inertia weight. c1 and c2 are acceleration coefficients.A recent study [20] proved that the particles in PSO converge to the weighted position of pbest and gbest as follows:
(2)limt→+∞Xi(t)=c1·pbesti+c2·gbestc1+c2.Based on the convergence characteristic of PSO, Kennedy [15] proposed a new PSO variant called barebones PSO (BPSO), in which each particle only has a position vector and eliminates the velocity vector. Therefore, BPSO does not contain the parameters w, c1, and c2. In BPSO, a new position is updated by Gaussian sampling as follows:
(3)Xi(t+1)=N(gbest+pbesti2,|gbest-pbesti|),
where N(·) indicates a Gaussian distribution with mean (gbest+pbesti)/2 and standard deviation |gbest-pbesti|.


## 3. Barebones PSO with Neighborhood Search

Due to the intrinsic randomness, both PSO and EAs suffer from premature convergence when solving complex multimodal problems. Sometimes, the suboptima are near to the global optimum and the neighborhoods of trapped particles may contain the global optimum. For this case, searching the neighbors of particles is beneficial for finding better solutions. Based on this idea, some neighborhood search strategies have been successfully applied to various algorithms.In [11], Wang et al. proposed a new PSO algorithm called PSO with neighborhood search strategies (NSPSO), which utilizes one local and two global neighborhood search strategies. The NSPSO includes two operations. First, for each particle, three trial particles are generated by the above neighborhood search strategies, respectively. Second, the best one among the three trial particles and the current particle is chosen as the new current particle. Simulation studies on twelve unimodal and multimodal benchmark problems show that NSPSO achieves better results than standard PSO and five other improved PSO algorithms.Although NSPSO has shown good search abilities, its performance is still seriously influenced by its control parameters,w, c1, and c2. In [11], NSPSO used an empirical parameter settings, c1=c2=1.49618 and w=0.72984. In order to minimize the effects of the control parameters on the performance of NSPSO, this paper proposes an improved PSO algorithm by combining barebones PSO and the neighborhood search strategies.There are various population topologies, such as ring, wheel, star, Von Neumann, and random. A recent study shows that the complexity of population topology affects the performance of PSO. A population topology with few connections (low complexity) may perform well on multimodal problems, while a highly interconnected population topology may perform well on unimodal problems. In this paper, a ring topology is used by the suggestions of [11].The ring topology assumes that particles are organized as a ring. In [21], a special ring topology is proposed by connecting the indices of particles. For example, the fourth particle P4 is connected by the third one P3 and the fifth one P5. In other words, P3 and P5 are two immediate neighbors of P4. Figure 1 shows the employed ring topology. Based on the ring topology, a k-neighborhood radius is defined, where k is a predefined integer number. For each particle Pi, its k-neighborhood radius consists 2k+1 particles (include itself), which are Pi-k,…,Pi-1,Pi,Pi+1,…,Pi+k. It is obvious that the parameter k satisfies 0≤k≤(N-1)/2. Figure 1 shows the 2-neighborhood radius of P4, where 5 particles are covered by the neighborhood. By the suggestions of [11], k=2 is used in this paper.Figure 1
The ring topology and 2-neighborhood radius.Based on thek-neighborhood radius, a local neighborhood search strategy is proposed. For each particle Pi, a local particle Li is generated as follows [11]:
(4)LXi(t+1)=a1·Xi(t)+a2·pbesti+a3·(Xi1(t)-Xi2(t)),
where Xi1 and Xi2 are the position vectors of two particles, Pi1 and Pi2, randomly selected from the k-neighborhood neighborhood, i1,i2∈[i-k,i+k]∧i1≠i2≠i, a1, a2, a3 are three random numbers within (0,1), and a1+a2+a3=1. In [11], the velocity of Li keeps the same with Pi. Although the velocity mechanism is simple, it may not beneficial for the next flight of Li. Therefore, we use a similar method to generate LVi:
(5)LVi(t+1)=a1·Vi(t)+a2·pbestVi+a3·(Vi1(t)-Vi2(t)),
where pbestVi is the velocity vector of pbesti and Vi1, Vi2 are the velocity vectors of Pi1 and Pi2, respectively.Beside the local neighbor strategy, a global neighborhood search strategy is proposed. For each particlePi, a global particle Gi is generated as follows [11]:
(6)GXi(t+1)=a1·Xi(t)+a2·gbest+a3·(Xi3(t)-Xi4(t)),
where Xi3 and Xi4 are the position vectors of two particles, Pi3 and Pi4, randomly selected from the current swarm, i3,i4∈[1,N]∧i3≠i4≠i, a1, a2, a3 are three random numbers within (0,1), and a1+a2+a3=1. In [11], the velocities of Gi keeps the same with Pi. So, the velocity of Li, Gi, and Pi are the same, but Li (local) and Gi (global) are two different types of particles. Like (5), this paper uses a new method to generate GVi:
(7)LVi(t+1)=a1·Vi(t)+a2·gbestV+a3·(Vi3(t)-Vi4(t)),
where gbestV is the velocity vector of gbest and Vi3, Vi4 are the velocity vectors of Pi3 and Pi4, respectively.After generating two new particlesLi and Gi, a greedy selection mechanism is used. Among Pi, Li, and Gi, we select the best one as the new Pi.In our approach NSBPSO, it embeds the local and global neighborhood search strategies into barebones PSO. The neighborhood search strategies focus on searching the neighbors of particles and provide different search behaviors. The BPSO concentrates on minimizing the dependency of the control parameters (withoutw, c1, and c2). By hybridization of BPSO and the neighborhood strategies, NSBPSO is almost a parameter-free algorithm (except for the probability of the neighborhood search), which achieves a tradeoff between exploration and exploitation.The main steps of NSBPSO are listed as follows.Step 1.
Randomly initialize the swarm, and evaluate the fitness values of all particles.Step 2.
Initializepbest and gbest.Step 3.
For each particlePi, calculate its new position vector Xi according to (3). Evaluate the fitness value of Pi. If needed, update pbesti and gbest.Step 4.
For each particlePi, if r and (0,1)<Pns, where r and (0,1) is a random number within [0,1] and Pns is the probability of conducting neighborhood search, then go to Step 5; otherwise go to Step 6.Step 5.
Generate a local particleLi according to (4) and (5). Generate a local particle Gi according to (6) and (7). Evaluate the fitness values of Li and Gi. Among Pi, Li, and Gi, we select the best one as the new Pi. If needed, update pbesti and gbest.Step 6.
If the stop criterion is satisfied, then stop the algorithm and output the results; otherwise go to Step3.


## 4. Experimental Study

### 4.1. Test Problems

In order to verify the performance of our approach, there are twelve well-known benchmark problems used in the following experiments [10]. According to the properties of these problems, they are divided into two three types: unimodal problems (f1–f2), unrotated multimodal problems (f3–f8), and rotated multimodal problems (f9–f12). For rotated problems, the original variable x is left multiplied by the orthogonal matrix M to get the new rotated variable y=M*x. For all test problems, they are to be minimized and their global optima are zero. The specific descriptions of these problems are presented in Table 1.Table 1
The twelve benchmark problems.
Problems
D
Search range
f
1
(
x
)
=
∑
i
=
1
D
x
i
2
30
[−100, 100]
f
2
(
x
)
=
∑
i
=
1
D
-
1
[
100
(
x
i
2
-
x
i
+
1
)
2
+
(
x
i
-
1
)
2
]
30
[−2.048, 2.048]
f
3
(
x
)
=
-
20
exp
(
-
0.2
1
D
∑
i
=
1
D
x
i
2
)
-
exp
(
1
D
∑
i
=
1
D
cos
(
2
π
x
i
)
)
+
20
+
e
30
[−32.768, 32.768]
f
4
(
x
)
=
∑
i
=
1
D
x
i
2
4000
-
∏
i
=
1
D
cos
(
x
i
i
)
+
1
30
[−600, 600]
f
5
(
x
)
=
∑
i
=
1
D
(
∑
k
=
0
k
max
[
a
k
cos
(
2
π
b
k
(
x
i
+
0.5
)
)
]
)
-
D
∑
k
=
0
k
max
[
a
k
cos
(
2
π
b
k
·
0.5
)
]
a
=
0.5
,
b
=
3
,
k
max
=
20
30
[−0.5, 0.5]
f
6
(
x
)
=
∑
i
=
1
D
(
x
i
2
-
10
cos
(
2
π
x
i
)
+
10
)
30
[−5.12, 5.12]
f
7
(
x
)
=
∑
i
=
1
D
(
y
i
2
-
10
cos
(
2
π
y
i
)
+
10
)
y
i
=
{
x
i
,
|
x
i
|
<
1
2
round
(
2
x
i
)
2
,
|
x
i
|
≥
1
2
30
[−5.12, 5.12]
f
8
(
x
)
=
418.9829
·
D
-
∑
i
=
1
D
(
x
i
sin
(
|
x
i
|
)
)
30
[−500, 500]
f
9
(
x
)
=
-
20
exp
(
-
0.2
1
D
∑
i
=
1
D
y
i
2
)
-
exp
(
1
D
∑
i
=
1
D
cos
(
2
π
y
i
)
)
+
20
+
e
y
=
M
*
x
30
[−32.768, 32.768]
f
10
(
x
)
=
∑
i
=
1
D
y
i
2
4000
-
∏
i
=
1
D
cos
(
y
i
i
)
+
1
y
=
M
*
x
30
[−600, 600]
f
11
(
x
)
=
∑
i
=
1
D
(
∑
k
=
0
k
max
[
a
k
cos
(
2
π
b
k
(
y
i
+
0.5
)
)
]
)
-
D
∑
k
=
0
k
max
[
a
k
cos
(
2
π
b
k
·
0.5
)
]
y
=
M
*
x
30
[−0.5, 0.5]
f
12
(
x
)
=
∑
i
=
1
D
(
y
i
2
-
10
cos
(
2
π
y
i
)
+
10
)
y
=
M
*
x
30
[−5.12,  5.12]


### 4.2. Effects of the ParameterPns

The main contribution of this paper is to minimize the effects of the control parameters and improve the performance of BPSO. Although NSBPSO eliminates the control parameters,w, c1, and c2, it introduces two new parameters k and Pns. The parameter k is the size of neighborhood radius. The ring population topology used in this paper assumes that particles are connected by their indices. Although P2 and P3 are two neighbors of P1, they may not be the nearest one to P1 (Euclidean distance). So, the size of the neighborhood radius does not affect the selection of particles in the local neighborhood search. Our empirical studies also confirm it (here we do not list the results of NSBSO with different k-neighborhood radius). According to the suggestions of [11], k is set to 2 in this paper.The parameterPns controls the probability of conducting neighborhood search. A larger Pns will result in more neighborhood search operations, while a smaller Pns will have less. This may affect the performance of NSBPSO. To investigate the effects of Pns, this section presents an experimental study. In the experiment, the Pns is set to 0.0, 0.1, 0.3, 0.5, 0.7, and 1.0, respectively. The performance of NSBPSO with different Pns is compared.For other parameters of NSBPSO, we use the following settings by the suggestions of [10]. The population size N is set to 40. When the number of fitness evaluations (FEs) reaches the maximum value MAX_FEs, the algorithm stops running. In the experiment, MAX_FEs is set to 2.0e+05. For each test problem, NSBPSO is run 30 times and the mean fitness error values are reported.Table2 presents the computational results of NSBPSO under different Pns, where “Mean” represents the mean fitness error values. The best results among the comparison are shown in boldface. As seen, the performance of NSBPSO is not sensitive to the parameter Pns. A smaller (Pns<0.3) or larger (Pns>0.5) value of Pns almost achieves similar results. For Pns=0.0, NSBPSO is equal to the original BPSO, because the neighborhood search operations are not conducted. For this case, the algorithm shows poor performance and falls into local minima on most test functions. When Pns=0.1, NSBPSO significantly outperforms NSBPSO with Pns=0.0. It demonstrates that the neighborhood search strategies are very effective. Even if we use a small Pns, NSBPSO can also obtain promising results.Table 2
Results achieved by NSBPSO with differentPns.
Problems
P
ns
=
0.0
P
ns
=
0.1
P
ns
=
0.3
P
ns
=
0.5
P
ns
=
0.7
P
ns
=
1.0
Mean
Mean
Mean
Mean
Mean
Mean
f
1
3.60
E
-
87
1.47
E
-
285
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
f
2
1.84
E
+
01
1.81
E
+
01
2.01
E
+
01
2.08
E
+
01
2.13
E
+
01
2.23
E
+
01
f
3
1.12
E
-
14
5.89
E
-
16
5.89
E
-
16
5.89
E
-
16
5.89
E
-
16
5.89
E
-
16
f
4
9.86
E
-
03
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
f
5
5.65
E
-
05
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
f
6
3.38
E
+
01
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
f
7
2.50
E
+
01
0.00
E
+
00
0.00
E
+
00
0.0
0
E
+
00
0.00
E
+
00
0.00
E
+
00
f
8
2.13
E
+
03
1.80
E
+
03
1.01
E
+
03
2.78
E
+
03
2.63
E
+
03
4.17
E
+
03
f
9
1.90
E
+
00
5.89
E
-
16
5.89
E
-
16
5.89
E
-
16
5.89
E
-
16
5.89
E
-
16
f
1
0
2.95
E
-
02
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
f
1
1
7.95
E
+
00
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
f
1
2
6.07
E
+
01
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00The value ofPns does not affect the performance of NSBPSO, and Pns>0 is applicable for all test problems. In this paper, Pns=0.3 is used in the following experiments.Figure2 presents the convergence processes of NSBPSO with different Pns. Although different Pns of NSBPSO can find the global optimum on the majority of test functions, they show different convergence characteristics. For problem f1, larger Pns converges faster than smaller Pns. For problem f2, Pns=0.1 converges fastest than other values. For f8, Pns=0.3 shows the fastest convergence speed.The convergence curves of NSBPSO with differentPns.
(a)
f
1
(b)
f
2
(c)
f
3
(d)
f
4
(e)
f
8
(f)
f
9
(g)
f
10
(h)
f
11


### 4.3. Comparison of NSBPSO with Other PSO Algorithms

In this section, experiments are conducted to compare nine PSO algorithms including the proposed NSBPSO on the 12 test problems. The involved algorithms are listed as follows.(1)
standard PSO,(2)
barebones PSO (BPSO),(3)
unified PSO (UPSO) [7],(4)
fully informed PSO (FIPS) [8],(5)
cooperative PSO (CPSO-H) [9],(6)
comprehensive learning PSO (CLPSO) [10],(7)
adaptive learning PSO (APSO) [13],(8)
pSO with neighborhood search (NSPSO) [11],(9)
our approach (NSBPSO).For the sake of fair comparison, we use the same settings for the same parameters. For all algorithms, the population sizeN is set to 40, and the maximum number of fitness evaluations (MAX_FEs) is set to 2.0e+05. For standard PSO, w is linearly decreased from 0.9 to 0.4, and c1=c2=1.49618. For NSPSO, the probability of neighborhood search Pns is set to 0.3. The parameter settings of UPSO, CPSO-H, FIPS, and CLPSO are described in [10]. For NSPSO and APSO, the same parameters are used by the literature [11, 13], respectively. For each test problem, each algorithm is conducted 30 times and the mean fitness error values are reported.Table3 lists the comparison results of NSBPSO with other eight PSO algorithms, where “Mean” represents the mean fitness error values. The best results are shown in boldface. From the results, it can be seen that NSBPSO outperforms PSO, BPSO, and FIPS on all test problems. UPSO and APSO perform better than NSBPSO on f2, while NSBPSO achieves better results for the rest 11 problems. CPSO-H obtains better solution than NSBPSO on f2, while NSBPSO outperforms CPSO-H on 10 problems. For problem f6, both NSBPSO and CPSO-H can find the global optimum. NSPSO performs better than NSBPSO on f2, while NSBPSO outperforms NSPSO on 4 problems. Both of them can converge to the global optimum on 7 problems.Table 3
Results achieved by the nine PSO algorithms.
Algorithms
f
1
f
2
f
3
f
4
f
5
f
6
f
7
f
8
f
9
f
10
f
11
f
12
Mean
Mean
Mean
Mean
Mean
Mean
Mean
Mean
Mean
Mean
Mean
Mean
PSO
9.78
E
-
30
2.93
E
+
01
3.94
E
-
14
8.13
E
-
03
1.30
E
-
04
2.90
E
+
01
2.97
E
+
01
1.10
E
+
03
2.80
E
-
01
1.64
E
-
01
6.66
E
-
01
9.90
E
+
00
BPSO
3.60
E
-
87
1.84
E
+
01
1.12
E
-
14
9.86
E
-
03
5.65
E
-
05
3.38
E
+
01
2.50
E
+
01
2.13
E
+
03
1.90
E
+
00
2.95
E
-
02
7.95
E
+
00
6.07
E
+
01
UPSO
4.17
E
-
87
1.51
E
+
01
1.22
E
-
15
1.66
E
-
03
9.60
E
+
00
6.59
E
+
01
6.34
E
+
01
4.84
E
+
03
1.00
E
+
00
7.76
E
-
02
2.61
E
+
00
1.52
E
+
01
FIPS
2.69
E
-
12
2.45
E
+
01
4.81
E
-
07
1.16
E
-
06
1.54
E
-
01
7.30
E
+
01
6.08
E
+
01
2.05
E
+
03
2.25
E
-
15
1.70
E
-
01
5.93
E
-
14
1.20
E
+
01
CPSO-H
1.16
E
-
113
7.08
E
+
00
4.93
E
-
14
3.63
E
-
02
7.82
E
-
15
0.00
E
+
00
1.00
E
-
01
1.08
E
+
03
1.36
E
+
00
1.20
E
-
01
4.35
E
+
00
2.67
E
+
01
CLPSO
1.46
E
-
14
2.01
E
+
01
0.00
E
+
00
3.14
E
-
10
3.45
E
-
07
4.85
E
-
10
4.36
E
-
10
1.27
E
-
12
3.65
E
-
05
4.50
E
-
02
3.72
E
-
10
5.97
E
+
00
APSO
9.60
E
-
66
1.83
E
+
01
1.09
E
-
14
1.20
E
-
02
4.77
E
-
02
6.27
E
+
00
2.27
E
+
00
2.13
E
+
03
1.22
E
+
00
1.38
E
-
02
8.40
E
+
00
7.09
E
+
01
NSPSO
0.00
E
+
00
4.08
E
+
00
5.89
E
-
16
0.00
E
+
00
6.72
E
-
13
0.00
E
+
00
0.00
E
+
00
1.07
E
+
03
9.55
E
-
13
0.00
E
+
00
1.54
E
-
13
0.00
E
+
00
NSBPSO
0.00
E
+
00
2.01
E
+
01
5.89
E
-
16
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
1.01
E
+
03
5.89
E
-
16
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00From the comparison of BPSO and PSO, BPSO outperforms PSO on 6 problems, while PSO achieves better results than BPSO for the rest 6 problems. The results demonstrate that the performance of BPSO is similar to PSO on these problems. Compared to PSO, BPSO is more competitive, because BPSO does not contain any control parameter (except for the population size), while PSO employs empirical parameter settings. By hybridization of BPSO (or PSO) and the neighborhood search, NSBPSO (or NSPSO) achieves significantly improvements on the performance of BPSO (or PSO). Compared to NSPSO, NSBPSO not only achieves better results, but also has less control parameters.In order to compare the performance differences between NSBPSO and the other eight PSO algorithms, we conduct the Wilcoxon signed-rank test by the suggestions of [22]. Table 4 shows the P-values achieved by the Wilcoxon test. The P values below 0.05 are shown in boldface. As shown, NSBPSO is significantly better than all other algorithms except for CLPSO and NSPSO. Though NSBPSO is not significantly better than them, it outperforms them in the majority of test problems.Table 4
Results of Wilcoxon signed-rank test between NSBPSO and other eight PSO algorithms.
NSBPSO versus
P values
PSO
4.88
E
-
04
BPSO
6.05
E
-
03
UPSO
6.35
E
-
03
FIPS
1.17
E
-
02
CPSO-H
4.88
E
-
04
CLPSO
6.54
E
-
02
APSO
6.35
E
-
03
NSPSO
3.75
E
-
01


## 4.1. Test Problems

In order to verify the performance of our approach, there are twelve well-known benchmark problems used in the following experiments [10]. According to the properties of these problems, they are divided into two three types: unimodal problems (f1–f2), unrotated multimodal problems (f3–f8), and rotated multimodal problems (f9–f12). For rotated problems, the original variable x is left multiplied by the orthogonal matrix M to get the new rotated variable y=M*x. For all test problems, they are to be minimized and their global optima are zero. The specific descriptions of these problems are presented in Table 1.Table 1
The twelve benchmark problems.
Problems
D
Search range
f
1
(
x
)
=
∑
i
=
1
D
x
i
2
30
[−100, 100]
f
2
(
x
)
=
∑
i
=
1
D
-
1
[
100
(
x
i
2
-
x
i
+
1
)
2
+
(
x
i
-
1
)
2
]
30
[−2.048, 2.048]
f
3
(
x
)
=
-
20
exp
(
-
0.2
1
D
∑
i
=
1
D
x
i
2
)
-
exp
(
1
D
∑
i
=
1
D
cos
(
2
π
x
i
)
)
+
20
+
e
30
[−32.768, 32.768]
f
4
(
x
)
=
∑
i
=
1
D
x
i
2
4000
-
∏
i
=
1
D
cos
(
x
i
i
)
+
1
30
[−600, 600]
f
5
(
x
)
=
∑
i
=
1
D
(
∑
k
=
0
k
max
[
a
k
cos
(
2
π
b
k
(
x
i
+
0.5
)
)
]
)
-
D
∑
k
=
0
k
max
[
a
k
cos
(
2
π
b
k
·
0.5
)
]
a
=
0.5
,
b
=
3
,
k
max
=
20
30
[−0.5, 0.5]
f
6
(
x
)
=
∑
i
=
1
D
(
x
i
2
-
10
cos
(
2
π
x
i
)
+
10
)
30
[−5.12, 5.12]
f
7
(
x
)
=
∑
i
=
1
D
(
y
i
2
-
10
cos
(
2
π
y
i
)
+
10
)
y
i
=
{
x
i
,
|
x
i
|
<
1
2
round
(
2
x
i
)
2
,
|
x
i
|
≥
1
2
30
[−5.12, 5.12]
f
8
(
x
)
=
418.9829
·
D
-
∑
i
=
1
D
(
x
i
sin
(
|
x
i
|
)
)
30
[−500, 500]
f
9
(
x
)
=
-
20
exp
(
-
0.2
1
D
∑
i
=
1
D
y
i
2
)
-
exp
(
1
D
∑
i
=
1
D
cos
(
2
π
y
i
)
)
+
20
+
e
y
=
M
*
x
30
[−32.768, 32.768]
f
10
(
x
)
=
∑
i
=
1
D
y
i
2
4000
-
∏
i
=
1
D
cos
(
y
i
i
)
+
1
y
=
M
*
x
30
[−600, 600]
f
11
(
x
)
=
∑
i
=
1
D
(
∑
k
=
0
k
max
[
a
k
cos
(
2
π
b
k
(
y
i
+
0.5
)
)
]
)
-
D
∑
k
=
0
k
max
[
a
k
cos
(
2
π
b
k
·
0.5
)
]
y
=
M
*
x
30
[−0.5, 0.5]
f
12
(
x
)
=
∑
i
=
1
D
(
y
i
2
-
10
cos
(
2
π
y
i
)
+
10
)
y
=
M
*
x
30
[−5.12,  5.12]


## 4.2. Effects of the ParameterPns

The main contribution of this paper is to minimize the effects of the control parameters and improve the performance of BPSO. Although NSBPSO eliminates the control parameters,w, c1, and c2, it introduces two new parameters k and Pns. The parameter k is the size of neighborhood radius. The ring population topology used in this paper assumes that particles are connected by their indices. Although P2 and P3 are two neighbors of P1, they may not be the nearest one to P1 (Euclidean distance). So, the size of the neighborhood radius does not affect the selection of particles in the local neighborhood search. Our empirical studies also confirm it (here we do not list the results of NSBSO with different k-neighborhood radius). According to the suggestions of [11], k is set to 2 in this paper.The parameterPns controls the probability of conducting neighborhood search. A larger Pns will result in more neighborhood search operations, while a smaller Pns will have less. This may affect the performance of NSBPSO. To investigate the effects of Pns, this section presents an experimental study. In the experiment, the Pns is set to 0.0, 0.1, 0.3, 0.5, 0.7, and 1.0, respectively. The performance of NSBPSO with different Pns is compared.For other parameters of NSBPSO, we use the following settings by the suggestions of [10]. The population size N is set to 40. When the number of fitness evaluations (FEs) reaches the maximum value MAX_FEs, the algorithm stops running. In the experiment, MAX_FEs is set to 2.0e+05. For each test problem, NSBPSO is run 30 times and the mean fitness error values are reported.Table2 presents the computational results of NSBPSO under different Pns, where “Mean” represents the mean fitness error values. The best results among the comparison are shown in boldface. As seen, the performance of NSBPSO is not sensitive to the parameter Pns. A smaller (Pns<0.3) or larger (Pns>0.5) value of Pns almost achieves similar results. For Pns=0.0, NSBPSO is equal to the original BPSO, because the neighborhood search operations are not conducted. For this case, the algorithm shows poor performance and falls into local minima on most test functions. When Pns=0.1, NSBPSO significantly outperforms NSBPSO with Pns=0.0. It demonstrates that the neighborhood search strategies are very effective. Even if we use a small Pns, NSBPSO can also obtain promising results.Table 2
Results achieved by NSBPSO with differentPns.
Problems
P
ns
=
0.0
P
ns
=
0.1
P
ns
=
0.3
P
ns
=
0.5
P
ns
=
0.7
P
ns
=
1.0
Mean
Mean
Mean
Mean
Mean
Mean
f
1
3.60
E
-
87
1.47
E
-
285
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
f
2
1.84
E
+
01
1.81
E
+
01
2.01
E
+
01
2.08
E
+
01
2.13
E
+
01
2.23
E
+
01
f
3
1.12
E
-
14
5.89
E
-
16
5.89
E
-
16
5.89
E
-
16
5.89
E
-
16
5.89
E
-
16
f
4
9.86
E
-
03
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
f
5
5.65
E
-
05
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
f
6
3.38
E
+
01
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
f
7
2.50
E
+
01
0.00
E
+
00
0.00
E
+
00
0.0
0
E
+
00
0.00
E
+
00
0.00
E
+
00
f
8
2.13
E
+
03
1.80
E
+
03
1.01
E
+
03
2.78
E
+
03
2.63
E
+
03
4.17
E
+
03
f
9
1.90
E
+
00
5.89
E
-
16
5.89
E
-
16
5.89
E
-
16
5.89
E
-
16
5.89
E
-
16
f
1
0
2.95
E
-
02
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
f
1
1
7.95
E
+
00
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
f
1
2
6.07
E
+
01
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00The value ofPns does not affect the performance of NSBPSO, and Pns>0 is applicable for all test problems. In this paper, Pns=0.3 is used in the following experiments.Figure2 presents the convergence processes of NSBPSO with different Pns. Although different Pns of NSBPSO can find the global optimum on the majority of test functions, they show different convergence characteristics. For problem f1, larger Pns converges faster than smaller Pns. For problem f2, Pns=0.1 converges fastest than other values. For f8, Pns=0.3 shows the fastest convergence speed.The convergence curves of NSBPSO with differentPns.
(a)
f
1
(b)
f
2
(c)
f
3
(d)
f
4
(e)
f
8
(f)
f
9
(g)
f
10
(h)
f
11


## 4.3. Comparison of NSBPSO with Other PSO Algorithms

In this section, experiments are conducted to compare nine PSO algorithms including the proposed NSBPSO on the 12 test problems. The involved algorithms are listed as follows.(1)
standard PSO,(2)
barebones PSO (BPSO),(3)
unified PSO (UPSO) [7],(4)
fully informed PSO (FIPS) [8],(5)
cooperative PSO (CPSO-H) [9],(6)
comprehensive learning PSO (CLPSO) [10],(7)
adaptive learning PSO (APSO) [13],(8)
pSO with neighborhood search (NSPSO) [11],(9)
our approach (NSBPSO).For the sake of fair comparison, we use the same settings for the same parameters. For all algorithms, the population sizeN is set to 40, and the maximum number of fitness evaluations (MAX_FEs) is set to 2.0e+05. For standard PSO, w is linearly decreased from 0.9 to 0.4, and c1=c2=1.49618. For NSPSO, the probability of neighborhood search Pns is set to 0.3. The parameter settings of UPSO, CPSO-H, FIPS, and CLPSO are described in [10]. For NSPSO and APSO, the same parameters are used by the literature [11, 13], respectively. For each test problem, each algorithm is conducted 30 times and the mean fitness error values are reported.Table3 lists the comparison results of NSBPSO with other eight PSO algorithms, where “Mean” represents the mean fitness error values. The best results are shown in boldface. From the results, it can be seen that NSBPSO outperforms PSO, BPSO, and FIPS on all test problems. UPSO and APSO perform better than NSBPSO on f2, while NSBPSO achieves better results for the rest 11 problems. CPSO-H obtains better solution than NSBPSO on f2, while NSBPSO outperforms CPSO-H on 10 problems. For problem f6, both NSBPSO and CPSO-H can find the global optimum. NSPSO performs better than NSBPSO on f2, while NSBPSO outperforms NSPSO on 4 problems. Both of them can converge to the global optimum on 7 problems.Table 3
Results achieved by the nine PSO algorithms.
Algorithms
f
1
f
2
f
3
f
4
f
5
f
6
f
7
f
8
f
9
f
10
f
11
f
12
Mean
Mean
Mean
Mean
Mean
Mean
Mean
Mean
Mean
Mean
Mean
Mean
PSO
9.78
E
-
30
2.93
E
+
01
3.94
E
-
14
8.13
E
-
03
1.30
E
-
04
2.90
E
+
01
2.97
E
+
01
1.10
E
+
03
2.80
E
-
01
1.64
E
-
01
6.66
E
-
01
9.90
E
+
00
BPSO
3.60
E
-
87
1.84
E
+
01
1.12
E
-
14
9.86
E
-
03
5.65
E
-
05
3.38
E
+
01
2.50
E
+
01
2.13
E
+
03
1.90
E
+
00
2.95
E
-
02
7.95
E
+
00
6.07
E
+
01
UPSO
4.17
E
-
87
1.51
E
+
01
1.22
E
-
15
1.66
E
-
03
9.60
E
+
00
6.59
E
+
01
6.34
E
+
01
4.84
E
+
03
1.00
E
+
00
7.76
E
-
02
2.61
E
+
00
1.52
E
+
01
FIPS
2.69
E
-
12
2.45
E
+
01
4.81
E
-
07
1.16
E
-
06
1.54
E
-
01
7.30
E
+
01
6.08
E
+
01
2.05
E
+
03
2.25
E
-
15
1.70
E
-
01
5.93
E
-
14
1.20
E
+
01
CPSO-H
1.16
E
-
113
7.08
E
+
00
4.93
E
-
14
3.63
E
-
02
7.82
E
-
15
0.00
E
+
00
1.00
E
-
01
1.08
E
+
03
1.36
E
+
00
1.20
E
-
01
4.35
E
+
00
2.67
E
+
01
CLPSO
1.46
E
-
14
2.01
E
+
01
0.00
E
+
00
3.14
E
-
10
3.45
E
-
07
4.85
E
-
10
4.36
E
-
10
1.27
E
-
12
3.65
E
-
05
4.50
E
-
02
3.72
E
-
10
5.97
E
+
00
APSO
9.60
E
-
66
1.83
E
+
01
1.09
E
-
14
1.20
E
-
02
4.77
E
-
02
6.27
E
+
00
2.27
E
+
00
2.13
E
+
03
1.22
E
+
00
1.38
E
-
02
8.40
E
+
00
7.09
E
+
01
NSPSO
0.00
E
+
00
4.08
E
+
00
5.89
E
-
16
0.00
E
+
00
6.72
E
-
13
0.00
E
+
00
0.00
E
+
00
1.07
E
+
03
9.55
E
-
13
0.00
E
+
00
1.54
E
-
13
0.00
E
+
00
NSBPSO
0.00
E
+
00
2.01
E
+
01
5.89
E
-
16
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00
1.01
E
+
03
5.89
E
-
16
0.00
E
+
00
0.00
E
+
00
0.00
E
+
00From the comparison of BPSO and PSO, BPSO outperforms PSO on 6 problems, while PSO achieves better results than BPSO for the rest 6 problems. The results demonstrate that the performance of BPSO is similar to PSO on these problems. Compared to PSO, BPSO is more competitive, because BPSO does not contain any control parameter (except for the population size), while PSO employs empirical parameter settings. By hybridization of BPSO (or PSO) and the neighborhood search, NSBPSO (or NSPSO) achieves significantly improvements on the performance of BPSO (or PSO). Compared to NSPSO, NSBPSO not only achieves better results, but also has less control parameters.In order to compare the performance differences between NSBPSO and the other eight PSO algorithms, we conduct the Wilcoxon signed-rank test by the suggestions of [22]. Table 4 shows the P-values achieved by the Wilcoxon test. The P values below 0.05 are shown in boldface. As shown, NSBPSO is significantly better than all other algorithms except for CLPSO and NSPSO. Though NSBPSO is not significantly better than them, it outperforms them in the majority of test problems.Table 4
Results of Wilcoxon signed-rank test between NSBPSO and other eight PSO algorithms.
NSBPSO versus
P values
PSO
4.88
E
-
04
BPSO
6.05
E
-
03
UPSO
6.35
E
-
03
FIPS
1.17
E
-
02
CPSO-H
4.88
E
-
04
CLPSO
6.54
E
-
02
APSO
6.35
E
-
03
NSPSO
3.75
E
-
01


## 5.  Application on Ship Design

### 5.1. Problem Description

This section investigates the performance of our approach NSBPSO for a conceptual ship design. The original optimization statements are presented in [23, 24]. The ship design optimization problem used in this paper has six design variables, three objectives, and 9 inequality constraints. The design variables are length (L), beam (B), depth (D), draft (T), block coefficient (CB), and speed in knots (Vk). The ship design problem aims to minimize transportation cost (Tc) and lightship weight (Ls) and maximize annual cargo (Ac) [24]:
(8)Minimize{Tc,Ls}MaximizeAc,
where Tc=CA/Ac, Ac=(DWT-Fc-DWTM)·RTPA, and Ls=Ws+Wo+Wm. The specific model definition is described in Table 5 [25]. The search ranges of the six variables L, B, D, T, CB, and Vk are listed in Table 6.Table 5
Model definition of the ship design problem.
Parameter
Definition
Parameter
Definition
Steel weight (Ws)
0.034
L
1.7
B
0.7
D
0.4
C
B
0.5
Port cost (CP)
6.3DWT0.8
Outfit weight (Wo)
1.0
L
0.8
B
0.6
D
0.4
C
B
0.5
Fuel carried (Fc)
D
c(Ds+0.5)
Displacement (Δ)
1.025LBTCB
Misc. deadweight (DWTM)
2.0DWT0.5
Machinery weight (Wm)
0.17P0.9
Cargo deadweight (DWTc)
DWT−Fc− DWTM
Capital cost (Cc)
0.2Cs
Port days (Dp)
2 (DWTc/HR + 0.5)
Running cost (CR)
40000DWT0.3
Round trips per year (RTPA)
350/(Ds+Dp)
Daily cost (Dc)
(
0.19
·
24
·
P
/
1000
)
+
0.2
Voyage cost (CV)
(CF+CP) RTPA
Handling rate (HR)
8000 (t/day)
Round trip miles (RTM)
5000 (nm)
Fuel price (FP)
100 (£/t)
Sea days (Ds)
RTM/24Vk
Power (P)
Δ
2
V
k
3
3
/
(
a
+
b
F
n
)
Fuel cost (CF)
1.05
D
C
D
S
F
P
Froude number (Fn)
V
/
g
L
,
V
=
0.5144
V
k
g
9.8065
Annual cost (CA)
(DWTC)  RTPA
KB
0.53T
K
G
1.0
+
0.52
D
BMT
(0.085CB− 0.002)B2/(TCB)
Ship cost (Cs)
1.3 (2000Ws0.85 + 3500 Wo+ 2400 P0.8)Table 6
Search ranges of the six design variables.
1
50
≤
L
≤
274.32
10
≤
T
≤
11.71
20
≤
B
≤
32.31
0.63
≤
C
B
≤
0.75
13
≤
D
≤
25
11
≤
V
k
≤
20There are 9 inequality constraints listed as follows:(9)6-LB≤0,LD-15≤0,LT-19≤0,T-0.45DWT0.31≤0,T-0.7D+0.7≤0,DWT-500000≤0,25000-DWT≤0,Fn-0.32≤0,0.07B-KB-BMT+KG≤0.


### 5.2. Constraint Handling

In order to deal with the constraints, an adaptive penalty method is employed by the suggestions of [19]. Let f(x) be the objective function (Tc, Ls, or Ac). The fitness evaluation function F(x) is defined by
(10)F(x)={f(x),ifxisfeasible,f¯(x)+∑j=1mkj·CVj,otherwise,
where m is the number of inequality constraints, CVj=min{0,cj(x)} is the constraint violation for the jth constraint, cj(x) is the jth constraint, f¯(x) is the mean objective function value in the current swarm, and kj is a penalty coefficient defined as follows:
(11)kj=|f(x)|·CVj¯(x)∑i=1m[CVi¯(x)]2,
where CVj¯(x) is the average violation of the jth constraint for all particles in the swarm.


### 5.3. Computational Results

The ship design problem is a multiobjective optimization problem which has three objectives. By the suggestions of [24, 25], this paper only considers single objective optimization. Therefore, the whole problem is divided into three single objective optimization problems: (1) minimize transportation cost (Tc), (2) minimize lightship weight (Ls), and (3) maximize annual cargo (Ac).In this section, we conduct three series of experiments for the three single optimization problems. In order to verify the performance of our approach NSBPSO, we compare it with four other algorithms. The involved algorithms are listed as follows:(1)
parsons and Scott’s method [24],(2)
standard PSO,(3)
barebones PSO (BPSO),(4)
PSO with neighborhood search (NSPSO),(5)
our approach (NSBPSO).To have a fair comparison, the same parameter settings are used for common parameters. For all algorithms, the population size and the maximum number of fitness evaluations (MAX_FEs) are set to 100 and1.0e+06. For standard PSO, w is linearly decreased from 0.9 to 0.4 and c1=c2=1.49618. For NSBPSO and NSPSO, Pns is set to 0.3. For each optimization problem, each algorithm is run 10 times and the best results among these runs are presented.Tables7–9 show the computational results for the three problems. For Table 7, NSBPSO achieves the minimal transportation cost among the five algorithms; but it also obtains the minimal value of annual cargo. For the objective of Tc, NSBPSO is the best among the five algorithms, however, it could not obtain the best results for all three objectives. For annual cargo Ac, Parsons and Scott’s [24] method is the best. Tables 8 and 9 can also get similar conclusions. The results demonstrate that NSBPSO shows better performance than the other three algorithms for single objective optimization problem of the ship design. When considering all objectives, we cannot conclude which algorithm is the best. To perfectly solve this problem, we may use multiobjective optimization algorithms. Figures 3, 4, and 5 present the convergence curves of PSO, BPSO, NSPSO, and NSBPSO for the three single objective problems. For minimizing transportation cost, NSBPSO shows faster convergence speed at the last stage of the evolution. For minimizing lightship weight, NSBPSO converges faster than other three PSO algorithms. For maximizing annual cargo, both NSBPSO and NSPSO show similar convergence characteristics.Table 7
Computational results for minimizing transportation cost.
Objective
Parsons and Scott [24]
PSO
BPSO
NSPSO
NSBPSO
Transportation cost (Tc)
8.377
8.213
8.195
8.176
8.162
Lightship weight (Ls)
9029.0
8420.1
8486.3
8452.8
8355.2
Annual cargo (Ac)
551265
509078
508069
505738
503261
L
193.86
190.63
191.72
193.04
192.36
B
32.31
30.15
30.13
29.57
29.34
D
15.73
15.54
15.49
15.42
15.39
T
11.71
11.64
11.50
11.51
11.48
C
B
0.681
0.729
0.730
0.730
0.730
V
k
14.00
12.25
12.32
12.21
12.48Table 8
Computational results for minimizing lightship weight.
Objective
Parsons and Scott [24]
PSO
BPSO
NSPSO
NSBPSO
Transportation cost (Tc)
9.474
9.374
9.341
9.325
9.286
Lightship weight (Ls)
5240.3
5019.9
4946.6
4932.6
4809.2
Annual cargo (Ac)
386500
371960
369257
366855
361372
L
150.73
155.32
154.59
155.7
152.8
B
25.12
24.36
24.42
24.78
22.87
D
13.84
14.43
14.18
13.02
13.92
T
10.39
10.76
10.62
10.38
10.57
C
B
0.750
0.693
0.69
0.705
0.750
V
k
14.00
13.62
13.78
13.29
13.25Table 9
Computational results for maximizing annual cargo.
Objective
Parsons and Scott [24]
PSO
BPSO
NSPSO
NSBPSO
Transportation cost (Tc)
10.294
10.884
11.308
11.59
12.213
Lightship weight (Ls)
12436
12558.2
12694.5
12757.4
12769.2
Annual cargo (Ac)
700533
706405
737952
741928
753137
L
222.49
235.86
231.95
235.27
238.2
B
32.31
32.20
32.32
32.14
32.31
D
15.73
16.60
17.29
16.62
15.73
T
11.71
11.42
11.70
11.70
11.71
C
B
0.750
0.720
0.750
0.750
0.750
V
k
18.00
18.09
18.73
18.68
18.89Figure 3
The convergence curves of PSO, BPSO, NSPSO and NSBPSO for minimizing transportation cost.Figure 4
The convergence curves of PSO, BPSO, NSPSO, and NSBPSO for minimizing lightship weight.Figure 5
The convergence curves of PSO, BPSO, NSPSO, and NSBPSO for maximizing annual cargo.


## 5.1. Problem Description

This section investigates the performance of our approach NSBPSO for a conceptual ship design. The original optimization statements are presented in [23, 24]. The ship design optimization problem used in this paper has six design variables, three objectives, and 9 inequality constraints. The design variables are length (L), beam (B), depth (D), draft (T), block coefficient (CB), and speed in knots (Vk). The ship design problem aims to minimize transportation cost (Tc) and lightship weight (Ls) and maximize annual cargo (Ac) [24]:
(8)Minimize{Tc,Ls}MaximizeAc,
where Tc=CA/Ac, Ac=(DWT-Fc-DWTM)·RTPA, and Ls=Ws+Wo+Wm. The specific model definition is described in Table 5 [25]. The search ranges of the six variables L, B, D, T, CB, and Vk are listed in Table 6.Table 5
Model definition of the ship design problem.
Parameter
Definition
Parameter
Definition
Steel weight (Ws)
0.034
L
1.7
B
0.7
D
0.4
C
B
0.5
Port cost (CP)
6.3DWT0.8
Outfit weight (Wo)
1.0
L
0.8
B
0.6
D
0.4
C
B
0.5
Fuel carried (Fc)
D
c(Ds+0.5)
Displacement (Δ)
1.025LBTCB
Misc. deadweight (DWTM)
2.0DWT0.5
Machinery weight (Wm)
0.17P0.9
Cargo deadweight (DWTc)
DWT−Fc− DWTM
Capital cost (Cc)
0.2Cs
Port days (Dp)
2 (DWTc/HR + 0.5)
Running cost (CR)
40000DWT0.3
Round trips per year (RTPA)
350/(Ds+Dp)
Daily cost (Dc)
(
0.19
·
24
·
P
/
1000
)
+
0.2
Voyage cost (CV)
(CF+CP) RTPA
Handling rate (HR)
8000 (t/day)
Round trip miles (RTM)
5000 (nm)
Fuel price (FP)
100 (£/t)
Sea days (Ds)
RTM/24Vk
Power (P)
Δ
2
V
k
3
3
/
(
a
+
b
F
n
)
Fuel cost (CF)
1.05
D
C
D
S
F
P
Froude number (Fn)
V
/
g
L
,
V
=
0.5144
V
k
g
9.8065
Annual cost (CA)
(DWTC)  RTPA
KB
0.53T
K
G
1.0
+
0.52
D
BMT
(0.085CB− 0.002)B2/(TCB)
Ship cost (Cs)
1.3 (2000Ws0.85 + 3500 Wo+ 2400 P0.8)Table 6
Search ranges of the six design variables.
1
50
≤
L
≤
274.32
10
≤
T
≤
11.71
20
≤
B
≤
32.31
0.63
≤
C
B
≤
0.75
13
≤
D
≤
25
11
≤
V
k
≤
20There are 9 inequality constraints listed as follows:(9)6-LB≤0,LD-15≤0,LT-19≤0,T-0.45DWT0.31≤0,T-0.7D+0.7≤0,DWT-500000≤0,25000-DWT≤0,Fn-0.32≤0,0.07B-KB-BMT+KG≤0.


## 5.2. Constraint Handling

In order to deal with the constraints, an adaptive penalty method is employed by the suggestions of [19]. Let f(x) be the objective function (Tc, Ls, or Ac). The fitness evaluation function F(x) is defined by
(10)F(x)={f(x),ifxisfeasible,f¯(x)+∑j=1mkj·CVj,otherwise,
where m is the number of inequality constraints, CVj=min{0,cj(x)} is the constraint violation for the jth constraint, cj(x) is the jth constraint, f¯(x) is the mean objective function value in the current swarm, and kj is a penalty coefficient defined as follows:
(11)kj=|f(x)|·CVj¯(x)∑i=1m[CVi¯(x)]2,
where CVj¯(x) is the average violation of the jth constraint for all particles in the swarm.


## 5.3. Computational Results

The ship design problem is a multiobjective optimization problem which has three objectives. By the suggestions of [24, 25], this paper only considers single objective optimization. Therefore, the whole problem is divided into three single objective optimization problems: (1) minimize transportation cost (Tc), (2) minimize lightship weight (Ls), and (3) maximize annual cargo (Ac).In this section, we conduct three series of experiments for the three single optimization problems. In order to verify the performance of our approach NSBPSO, we compare it with four other algorithms. The involved algorithms are listed as follows:(1)
parsons and Scott’s method [24],(2)
standard PSO,(3)
barebones PSO (BPSO),(4)
PSO with neighborhood search (NSPSO),(5)
our approach (NSBPSO).To have a fair comparison, the same parameter settings are used for common parameters. For all algorithms, the population size and the maximum number of fitness evaluations (MAX_FEs) are set to 100 and1.0e+06. For standard PSO, w is linearly decreased from 0.9 to 0.4 and c1=c2=1.49618. For NSBPSO and NSPSO, Pns is set to 0.3. For each optimization problem, each algorithm is run 10 times and the best results among these runs are presented.Tables7–9 show the computational results for the three problems. For Table 7, NSBPSO achieves the minimal transportation cost among the five algorithms; but it also obtains the minimal value of annual cargo. For the objective of Tc, NSBPSO is the best among the five algorithms, however, it could not obtain the best results for all three objectives. For annual cargo Ac, Parsons and Scott’s [24] method is the best. Tables 8 and 9 can also get similar conclusions. The results demonstrate that NSBPSO shows better performance than the other three algorithms for single objective optimization problem of the ship design. When considering all objectives, we cannot conclude which algorithm is the best. To perfectly solve this problem, we may use multiobjective optimization algorithms. Figures 3, 4, and 5 present the convergence curves of PSO, BPSO, NSPSO, and NSBPSO for the three single objective problems. For minimizing transportation cost, NSBPSO shows faster convergence speed at the last stage of the evolution. For minimizing lightship weight, NSBPSO converges faster than other three PSO algorithms. For maximizing annual cargo, both NSBPSO and NSPSO show similar convergence characteristics.Table 7
Computational results for minimizing transportation cost.
Objective
Parsons and Scott [24]
PSO
BPSO
NSPSO
NSBPSO
Transportation cost (Tc)
8.377
8.213
8.195
8.176
8.162
Lightship weight (Ls)
9029.0
8420.1
8486.3
8452.8
8355.2
Annual cargo (Ac)
551265
509078
508069
505738
503261
L
193.86
190.63
191.72
193.04
192.36
B
32.31
30.15
30.13
29.57
29.34
D
15.73
15.54
15.49
15.42
15.39
T
11.71
11.64
11.50
11.51
11.48
C
B
0.681
0.729
0.730
0.730
0.730
V
k
14.00
12.25
12.32
12.21
12.48Table 8
Computational results for minimizing lightship weight.
Objective
Parsons and Scott [24]
PSO
BPSO
NSPSO
NSBPSO
Transportation cost (Tc)
9.474
9.374
9.341
9.325
9.286
Lightship weight (Ls)
5240.3
5019.9
4946.6
4932.6
4809.2
Annual cargo (Ac)
386500
371960
369257
366855
361372
L
150.73
155.32
154.59
155.7
152.8
B
25.12
24.36
24.42
24.78
22.87
D
13.84
14.43
14.18
13.02
13.92
T
10.39
10.76
10.62
10.38
10.57
C
B
0.750
0.693
0.69
0.705
0.750
V
k
14.00
13.62
13.78
13.29
13.25Table 9
Computational results for maximizing annual cargo.
Objective
Parsons and Scott [24]
PSO
BPSO
NSPSO
NSBPSO
Transportation cost (Tc)
10.294
10.884
11.308
11.59
12.213
Lightship weight (Ls)
12436
12558.2
12694.5
12757.4
12769.2
Annual cargo (Ac)
700533
706405
737952
741928
753137
L
222.49
235.86
231.95
235.27
238.2
B
32.31
32.20
32.32
32.14
32.31
D
15.73
16.60
17.29
16.62
15.73
T
11.71
11.42
11.70
11.70
11.71
C
B
0.750
0.720
0.750
0.750
0.750
V
k
18.00
18.09
18.73
18.68
18.89Figure 3
The convergence curves of PSO, BPSO, NSPSO and NSBPSO for minimizing transportation cost.Figure 4
The convergence curves of PSO, BPSO, NSPSO, and NSBPSO for minimizing lightship weight.Figure 5
The convergence curves of PSO, BPSO, NSPSO, and NSBPSO for maximizing annual cargo.


## 6. Conclusions

Barebones PSO (BPSO) is a new variant of PSO which eliminates the velocity term. Although some reported results show that BPSO is better than PSO, it still gets stuck when solving complex multimodal problems. In order to enhance the performance of BPSO, this paper proposes an improved version called BPSO with neighborhood search (NSBPSO). The new approach embeds one local and one global neighborhood search strategies into the original BPSO to achieve a tradeoff between exploration and exploitation. Compared to other improved PSO algorithms, NSBPSO is almost parameter-free algorithm except for the probability of neighborhood search(Pns).Experimental studies are conducted on twelve well-known benchmark problems, including unimodal, multimodal, and rotated multimodal problems. Computational results show that the parameterPns does not affect the performance of NSBPSO. When Pns>0, NSBPSO can obtain good performance. Another comparison demonstrates that NSBPSO performs better than, or at least comparable to, several other state-of-the-art PSO algorithms. Compared to PSO with neighborhood search (NSPSO), our approach NSBPSO not only achieves better results, but also has less control parameters.For the ship design problem, NSBPSO performs better than other three algorithms when optimizing a single objective. When considering all three objectives, we cannot determine which algorithm is the best. Because one algorithm only achieves better results than other algorithms on one or two objectives. To tackle this problem, we can use multiobjective optimization algorithms to optimize the three objectives at the same time. This will be investigated in the future work.



---

*Source: 175848-2013-02-13.xml*