![](https://csdnimg.cn/release/download_crawler_static/89362192/bg1.jpg)
A social learning particle swarm optimization algorithm
for scalable optimization
Ran Cheng
a
, Yaochu Jin
a,b,
⇑
a
Department of Computing, University of Surrey, Guildford, Surrey GU2 7XH, United Kingdom
b
College of Information Sciences and Technology, Donghua University, Shanghai 201620, China
article info
Article history:
Received 19 October 2013
Received in revised form 5 August 2014
Accepted 16 August 2014
Available online 2 September 2014
Keywords:
Social learning
Particle swarm optimization
Large-scale optimization
Computational efficiency
Scalability
abstract
Social learning plays an important role in behavior learning among social animals. In
contrast to individual (asocial) learning, social learning has the advantage of allowing
individuals to learn behaviors from others without incurring the costs of individual
trials-and-errors. This paper introduces social learning mechanisms into particle swarm
optimization (PSO) to develop a social learning PSO (SL-PSO). Unlike classical PSO variants
where the particles are updated based on historical information, including the best solu-
tion found by the whole swarm (global best) and the best solution found by each particle
(personal best), each particle in the proposed SL-PSO learns from any better particles
(termed demonstrators) in the current swarm. In addition, to ease the burden of parameter
settings, the proposed SL-PSO adopts a dimension-dependent parameter control method.
The proposed SL-PSO is first compared with five representative PSO variants on 40
low-dimensional test functions, including shifted and rotated test functions. The scalability
of the proposed SL-PSO is further tested by comparing it with five state-of-the-art
algorithms for large-scale optimization on seven high-dimensional (100-D, 500-D, and
1000-D) benchmark functions. Our comparative results show that SL-PSO performs well
on low-dimensional problems and is promising for solving large-scale problems as well.
Ó 2014 Elsevier Inc. All rights reserved.
1. Introduction
Particle Swarm Optimization (PSO) is one powerful and widely used swarm intelligence paradigm introduced by Kennedy
and Eberhart in 1995 for solving optimization problems [43]. In PSO, it is assumed that each particle is able to memorize the
best position found in history, i.e., the best position that has ever been found by the whole swarm, termed global best, and the
best position that has ever been found by each particle, known as personal best. To find the global optimum of the optimi-
zation problem, the particles learn from the personal best and global best positions. Specifically, the learning mechanisms in
the canonical PSO can be summarized as follows:
V
i
ðt þ 1Þ¼
x
V
i
ðtÞþc
1
R
1
ðtÞðpbest
i
ðtÞX
i
ðtÞÞ þ c
2
R
2
ðtÞðgbestðtÞX
i
ðtÞÞ; ð1Þ
X
i
ðt þ 1Þ¼X
i
ðtÞþV
i
ðt þ 1Þ; ð2Þ
http://dx.doi.org/10.1016/j.ins.2014.08.039
0020-0255/Ó 2014 Elsevier Inc. All rights reserved.
⇑
Corresponding author at: Department of Computing, University of Surrey, Guildford, Surrey GU2 7XH, United Kingdom. Tel.: +44 1483686037; fax: +44
1483686051.
E-mail address: yaochu.jin@surrey.ac.uk (Y. Jin).
Information Sciences 291 (2015) 43–60
Contents lists available at ScienceDirect
Information Sciences
journal homepage: www.elsevier.com/locate/ins
![](https://csdnimg.cn/release/download_crawler_static/89362192/bg2.jpg)
where t is the generation number, V
i
ðtÞ and X
i
ðtÞ represent the velocity and position of the i-th particle, respectively;
x
is
termed inertia weight [71], c
1
and c
2
are the acceleration coefficients [20], R
1
ðtÞ and R
2
ðtÞ are two vectors randomly gener-
ated within ½0; 1
n
, with n being the dimension of the search space; pbest
i
ðtÞ and gbestðtÞ denote the personal best of the i-th
particle and the global best of the swarm, respectively.
Although PSO has witnessed rapid developments over the past decades and has been successfully applied to a number of
applications, e.g., water distribution network design [56], resource allocation [24], task assignment [30], maximum power
point tracker for photovoltaic system [36], optimal control [67], DNA sequence compression [100] and reconstruction of gene
regulatory network [60], image processing [69], text clustering [6] and many others [75,34,52], its performance is still
unsatisfying when the optimization problem has a large number of local optima or when the optimization problem is
high-dimensional and non-separable [87]. The poor performance of PSO can largely be attributed to its weak robustness
to various problem structures [84]. In order to enhance the search performance of the canonical PSO, numerous PSO variants
have been proposed, which can be roughly divided into the following five categories.
The first category adopts an adaptive control strategy of the parameters in PSO. As shown in (1),
x
; c
1
and c
2
are the three
control parameters in PSO.
x
, called the inertia weight, was introduced as a constant in [72] and an adaptive parameter in
[73]. Another important modification of
x
is the introduction of fuzzy inference [74]. Adaptation strategies for tuning the
acceleration coefficients, c
1
and c
2
, have also been proposed [64,11]. Apart from adapting
x
; c
1
and c
2
, additional parameters
to help regulate these three parameters have also been introduced [95,33].
Hybrid PSO algorithms, which can be categorized into the second category of PSO variants, combine PSO with other
search strategies, such as genetic algorithms [65,39,80], differential evolution [39], and ant colony optimization [70]. Other
specific search operators have also been incorporated into PSO, including mutation operators [29,51,61], local search oper-
ators [83,86], and some nature-inspired operators as well, such as the niching PSO [5], culture-based PSO [13] and the aging
theory inspired PSO (ALC-PSO) [8].
The third category of PSO variants introduces new topological structures in neighborhood control to enhance swarm
diversity, thereby alleviating premature convergence [76,41]. Several topological structures have been proposed [44], e.g.,
the ring topology and the von Neumann topology. In [53], a fully informed PSO (FIPS) was developed, where the update
of each particle is based on the historical best positions of several neighbors instead of gbest or pbest. Another representative
example is the comprehensive learning PSO (CLPSO) introduced in [49], where particles update each decision variable by
learning from different historical personal best positions. More recently, a distance-based locally informed particle swarm
optimizer has been proposed to tackle multi-modal problems [63].
Multi-swarm PSO belongs to the fourth category. The main idea behind multi-swarm PSO variants is to enhance swarm
diversity by exchanging information between different swarms. For example, the dynamic multi-swarm PSO (DMS-PSO) [48]
was proposed with a dynamically changing neighborhood structure. In [81], a cooperative multi-swarm PSO (CPSO) is pro-
posed to solve large-scale optimization problems by dividing the decision variables into several sub-components. Similarly,
the recently proposed cooperative coevolving PSO (CCPSO2) for large-scale optimization adopts the multi-swarm paradigm
as well [46]. Additional multi-swarm PSO variants have been reported in [2,92,19,10].
The fifth category of PSO variants is designed to perform effective search using limited computational cost and memory
usage. Unlike the first four categories, these PSO variants aim to simplify PSO to enhance its robustness by taking into
account the constraints of the device on which the PSO is running, rather than introducing additional mechanisms to
enhance the search performance for specific problems. Most PSO variants in this category are based on a probabilistic model.
The earliest model-based PSO was proposed by Kennedy [42], called the Bare Bones PSO (BBPSO), which uses Gaussian dis-
tributions instead of the velocity equation to update the particle positions. In [99], a simplified intelligent single particle
optimization (ISPO) was proposed to explore the search space using a single particle instead of a swarm, and some further
discussions on the ISPO can also be found in a recently published literature [35].In[77], a fitness estimation strategy has
been introduced based on the relationship between the positions of the particles to reduce the required number of fitness
evaluations. Most recently, a competitive swarm optimizer based on pairwise competition between particles was reported
[9], which has been shown to perform effectively for large scale optimization problems and needs much less memory com-
pared to the standard PSO.
PSO algorithms are often believed to be different from other population-based meta-heuristics in that PSO does not adopt
an explicit selection mechanism. However, as pointed out in [7,58], most PSO variants can also be captured by a generic
framework that is valid for almost all population-based meta-heuristics including evolutionary algorithms such as genetic
algorithms (GAs) and swarm intelligence algorithms such as PSO. A slight difference lies in the fact that most PSO algorithms
apply selection implicitly, e.g. by updating the personal best solutions and the global best solution only. While evolutionary
algorithms such as GAs perform selection by comparing a list of solutions for multiple times, PSO compares solutions pair-
wise. As suggested in [9,58], pairwise comparison in selection can not only reduce memory usage, but also make it easier to
adopt a compact encoding.
This paper proposes a new PSO variant by further modifying the implicit selection mechanism in PSO, where neither a
global best solution nor personal best solutions will be stored. Instead, the swarm is sorted according to the fitness of the
particles and all particles except for the best one will be updated by learning from any particle whose fitness is better. In
a sense, selection in the proposed algorithm is implicitly performed in the sorting process.
Learning and imitating the behaviors of better individuals in the population, which is known as social learning, can widely
be observed among social animals. Social learning, different from individual (asocial) learning, has the advantage of allowing
44 R. Cheng, Y. Jin / Information Sciences 291 (2015) 43–60
![](https://csdnimg.cn/release/download_crawler_static/89362192/bg3.jpg)
individuals to learn behaviors from others without incurring the costs of individual trial and error, which is able to accelerate
learning rates [45], especially when the target (behavior) to learn is complex. More specifically, individual learning is a
process of trial and error, whilst social learning is to take advantage of mechanisms such as imitation, enhancement and
conditioning [27].
Due to the appealing properties of social learning, it is quite natural to apply the social learning mechanisms to popula-
tion-based stochastic optimization. In 2011, Oca and Stutzle proposed an incremental social learning framework, which
consists of a growing population of agents that learn socially when they become part of the main group and learn individ-
ually when they are already part of it [57]. To the best of our knowledge, this is the earliest attempt to explicitly apply social
learning mechanism to optimization. However, the proposed framework is very generic and does not involve any concrete
social learning mechanism such as imitation, which plays an important role in natural social learning. Moreover, the
proposed framework is not able to work independent of an existing optimizer [15], e.g., a PSO variant.
In this paper, we introduce social learning mechanisms into PSO, resulting in a substantially different PSO variant, which is
termed social learning PSO (SL-PSO). Unlike most PSO variants, SL-PSO is performed on a sorted swarm. Instead of learning
from the historical best positions, the particles learn from any better particles (demonstrators) in the current swarm. To ease
the burden of parameter setting, a dimension-dependent parameter control strategy has been suggested in the proposed SL-PSO
to enhance its robustness to the search dimensionality (the number of decision variables) of the problem to be optimized.
The rest of this paper is organized as follows. Section 2 describes the proposed SL-PSO in detail, together with an analysis
of time complexity and a proof of convergence. In Section 3, the performance of the SL-PSO is examined by comparing its
performance with a few widely reported optimization algorithms on low-dimensional and large-scale optimization prob-
lems. Finally, conclusions are drawn in Section 4.
2. A social learning particle swarm optimizer
In the following, a brief account of the sociological background for the proposed SL-PSO will be given. Then, a detailed
description of SL-PSO will be provided together with an analysis of the computational complexity and a convergence proof.
2.1. Sociological background
In 1921, some British birds were first seen to open milk bottles in the small town of Swaythling. In the following 25 years,
such observations had been continually reported from numerous other sites spreading all over the Great Britain and even
some other areas in the European continent. This is the first evidence of social learning [22], where the birds are believed
to learn to open milk bottles by observations and interactions with other birds, instead of learning by themselves [28].
During the past decades, various mechanisms have been proposed and discussed in social learning theory, e.g., stimulus
enhancement and local enhancement [27], observational conditioning [54], contagion [93] and social facilitation [3]. Among
these mechanisms, the most interesting social learning mechanism is imitation, which is considered to be distinctive from
other social learning mechanisms [94], because imitation, which operates across a whole community, could lead to popula-
tion-level similarities of behavior such as culture or tradition [85]. Such population-level similarities may imply convergence
of a dynamic system, thus providing its essential applicability in an evolutionary algorithm.
In [14], the authors had a detailed discussion about different definitions of imitation, among which Mitchell’s definition is
considered to be the most applicable one across animals and machines [55], in which imitation is considered to be a proce-
dure to make a similar (but not exactly the same) copy of a model. In [85], imitation is described as a procedure of an imitator
copying part of a behavior from a demonstrator via observation.
In the following, we present a few new learning mechanisms inspired from social learning to replace the updating rules in
the canonical PSO.
2.2. Algorithm description
Without loss of generality, we consider the following minimization problem:
min f ¼ f ðXÞ;
s:t: X 2X;
ð3Þ
where XR
n
is the feasible solution set, n denotes the dimensionality of the search space, i.e., the number of decision vari-
ables, which are the behaviors to learn in the context of social learning.
2.2.1. The overall framework
Like the classical PSO, the proposed SL-PSO initializes a swarm PðtÞ containing m particles, where m is the swarm size and
t is the generation index. For each particle i in PðtÞ, it holds a randomly initialized decision vector (behavior vector) X
i
ðtÞ,
which represents a candidate solution to the optimization problem described in (3). As a reward feedback from the environ-
ment, every particle will be assigned with a fitness value calculated from the objective function f ðXÞ. The swarm is then
sorted according to an increasing order of the particles’ fitness values. Consequently, each particle (except for the one with
R. Cheng, Y. Jin / Information Sciences 291 (2015) 43–60
45
![](https://csdnimg.cn/release/download_crawler_static/89362192/bg4.jpg)
the best fitness value) will correct its behaviors by learning from those particles (demonstrators) which have better fitness
values. The general framework illustrating the above procedure is shown in Fig. 1.
2.2.2. Swarm sorting and behavior learning
It can be seen from Fig. 1 that, apart from fitness evaluations, the most important components in SL-PSO are swarm sorting
and behavior learning. For an easy description of the behavior learning mechanisms, the swarm is first sorted according to the
particles’ fitness values. Then, each particle i (an imitator), except for the best one, will learn from its corresponding demon-
strators. Note that in each generation, a particle could serve as an demonstrator for different imitators more than once. In a
sorted swarm, for any imitator (particle i, where 1 6 i < m), its demonstrators can be any particle k that satisfies i < k 6 m,
refer to Fig. 2. For example, for particle 1, particles 2, 3, ..., m can be its demonstrators, while for particle (m-1), only particle
m can be its demonstrator. As a result, particle 1 (the worst one) can never be a demonstrator and particle m (the best one)
will never be an imitator. That is, the best particle in the current swarm will not be updated.
Inspired by social learning mechanism, an imitator will learn the behaviors of different demonstrators [13] in the follow-
ing manner:
X
i;j
ðt þ 1Þ¼
X
i;j
ðtÞþ
D
X
i;j
ðt þ 1Þ; if p
i
ðtÞ 6 P
L
i
;
X
i;j
ðtÞ; otherwise;
(
ð4Þ
where X
i;j
ðtÞ is the j-th dimension of particle i’s behavior vector in generation t, with i 2f1; 2; 3; ...; mg and
j 2f1; 2; 3; ...; ng;
D
X
i;j
ðt þ 1Þ is the behavior correction. Taking into account the fact that in a society, the motivation to learn
Fig. 1. Main components of the proposed SL-PSO.
tseBtsroW
Swarm before sorting
Swarm after sorting
Sort according to fitness values
Demonstrators
Fig. 2. Swarm sorting and behavior learning in SL-PSO. At first, the swarm is sorted according to the fitness values; then each particle (except for the best
one) learns from its demonstrators which have better fitness values.
46 R. Cheng, Y. Jin / Information Sciences 291 (2015) 43–60
![](https://csdnimg.cn/release/download_crawler_static/89362192/bg5.jpg)
from better individuals may vary from individual to individual (typically, better individuals are less willing to learn from
others), we define a learning probability P
L
i
for each particle i. The precise definition of the learning probability will be dis-
cussed later on. As a result, particle i will learn (correct its behavior vector) only if a randomly generated probability p
i
sat-
isfies 0 6 p
i
ðtÞ 6 P
L
i
6 1. In detail,
D
X
i;j
ðt þ 1Þ is generated as follows:
D
X
i;j
ðt þ 1Þ¼r
1
ðtÞ
D
X
i;j
ðtÞþr
2
ðtÞI
i;j
ðtÞþr
3
ðtÞ C
i;j
ðtÞ; ð5Þ
with
I
i;j
ðtÞ¼X
k;j
ðtÞX
i;j
ðtÞ;
C
i;j
ðtÞ¼X
j
ðtÞX
i;j
ðtÞ:
(
ð6Þ
In the above updating mechanisms inspired from social learning, the behavior correction
D
X
i;j
ðt þ 1Þ consists of three
components. The first component
D
X
i;j
ðtÞ is the same as the inertia component in the canonical PSO, while the other two com-
ponents are different. In the second component, instead of learning from pbest as done in the canonical PSO, particle i learns
from any of its demonstrators. Specifically, the j-th element in the behavior vector of particle i; X
i;j
ðtÞ imitates X
k;j
ðtÞ, which is
the j-th element in the behavior vector of particle k (demonstrator of particle i). Note that i < k 6 m, and k is generated inde-
pendently for each element j, refer to Fig. 2. Consequently, particle i may learn from different demonstrators in the current
swarm. Since this component is inspired from the imitation behavior in natural social learning, it is denoted as imitation com-
ponent. Likewise, particle i does not learn from gbest either; instead, it learns from the collective behavior of the whole
swarm, i.e., the mean behavior of all particles in the current swarm, denoted by
X
j
ðtÞ, where X
j
ðtÞ¼
P
m
i¼1
X
j
i
m
. Since this com-
ponent induces a swarm-level conformity [93], it is denoted as the social influence component, and correspondingly, the con-
trol parameter
is denoted as the social influence factor. For simplicity, the three control parameters in classical PSO (
x
; c
1
and c
2
) have been replaced with three random coefficients r
1
ðtÞ; r
2
ðtÞ and r
3
ðtÞ, which will be randomly generated within
½0; 1 once the updating strategy is performed.
2.3. Dimension-dependent parameter control
In the proposed SL-PSO, there are three parameters that need to be defined, i.e., the swarm size m, the learning probability
P
L
i
, and the social influence factor
. As discussed in Section 1, the robustness of a PSO algorithm can be enhanced by adopting
adaptive parameter control, such that it could be applied to different problems without laborious parameter fine-tunings. It
has been found that the performance of most PSO variants is more sensitive to the search dimensionality of the optimization
problem than other widely used evolutionary algorithms [82], we suggest a dimension-dependent parameter control strat-
egy for the proposed SL-PSO as a guideline. It should be pointed out that this parameter control strategy has been suggested
based on pilot empirical studies, nevertheless, its effectiveness has been verified on 47 test functions, refer to Section 3.
The first parameter to be determined is the swarm size m. We recommend that the swarm size m be determined as a
function of the search dimensionality in the following form:
m ¼ M þ
n
10
jk
; ð7Þ
where M is the base swarm size for the SL-PSO to work properly. It has been empirically shown that a small swarm size is
usually sufficient for uni-modal optimization problems while a bigger swarm size is required for multi-modal optimization
problems for more intensive exploration [25,1]. As in real-world applications it is difficult to know in advance whether a
problem is uni-modal or multi-modal, we suggest M ¼ 100 in this work.
The idea for setting the learning probability P
L
i
is also inspired from natural social learning. As previously mentioned,
within a swarm, the better the fitness a particle has, the less likely the particle will learn from others. Meanwhile, the more
complex the behavior is, the less likely a particle tends to successfully learn the behavior. Generally speaking, the perfor-
mance of most meta-heuristic algorithms degrades as the search dimensionality of the optimization problem increases, in
particular when there exist strong correlations between the decision variables. Thus, we assume that the higher the search
dimensionality is, the more difficult it is to solve the problem, and therefore, the less likely a particle is willing to learn from
others. Based on such an assumption, we recommend a inversely proportional relationship between the learning probability
and the problem dimensionality.
Based on the discussions above, the following learning probability has been adopted:
P
L
i
¼ 1
i 1
m
a
logðd
n
M
eÞ
; ð8Þ
where the radix component 1
i1
m
indicates that the learning probability is inversely proportional to the particle index i in a
sorted swarm, meaning that the higher the fitness of a particle is, the lower the learning probability will be. Meanwhile, the
exponent component
a
log d
n
M
e
indicates that the learning probability is inversely proportional to the search dimensionality,
such that a better swarm diversity would be maintained for large-scale problems due to the reduced learning rate, and the
a
logðÞ function is used to smoothen the influence of
n
M
. Empirically, we recommend the coefficient
a
< 1, and in this work,
a
¼ 0:5 has been used.
R. Cheng, Y. Jin / Information Sciences 291 (2015) 43–60
47