∎

11institutetext: Rajesh Misra 22institutetext: S.A.Jaipuria College,10 Raja
Naba Krishna Street, Shobhabazar, Kolkata,India
22email<EMAIL_ADDRESS>33institutetext: Kumar S Ray
44institutetext: GLA University,Mathura- 281406,UP,India
44email<EMAIL_ADDRESS>
# Particle Swarm Optimization based on Novelty Search

Rajesh Misra  Kumar S Ray

(Received: date / Accepted: date)

###### Abstract

In this paper we propose a Particle Swarm Optimization algorithm combined with
Novelty Search. Novelty Search finds novel place to search in the search
domain and then Particle Swarm Optimization rigorously searches that area for
global optimum solution. This method is never blocked in local optima because
it is controlled by Novelty Search which is objective free. For those
functions where there are many more local optima and second global optimum is
far from true optimum, the present method works successfully. The present
algorithm never stops until it searches entire search area. A series of
experimental trials prove the robustness and effectiveness of the present
algorithm on complex optimization test functions.

###### Keywords:

Novelty Search Bare-Bones PSO Gaussian distribution Leader particle Novelty
scoreNovelty Threshold

##  1 Introduction

Particle Swarm Optimization has a long history of approximately more than two
decadesKen95 . A ton of variants surrounded in Swarm Optimization domain with
various improvements and applications which often confuse researchers which
algorithm to use and when. Maurice Clerc proposed a variant of PSO in 2011
which provides a standard for the class of particle swarm optimizationCle11
known as SPSO11. The SPSO11Cle11  helps researchers to compare their PSO
variants in terms of performance. In 2013 when Liang et.al lia13  formalized a
strong benchmark function on Real-Parameter Optimization problems. Swarm
intelligence researchers dive into those benchmark suite to test the strength
of their PSO variants.Clerc et .al also tested SPSO11 with that benchmark
suite and provided a baseline for further improvements of PSO problems Zam13 .

Though SPSO11 is earlier algorithm but it performs very well on most of the
objective test functions. On the other hands it performs poor in non-separable
and asymmetrical functions. The guideline for future PSO improvements is that
new PSO algorithms must have the ability to solve non-separable and
asymmetrical functions, with a large number of local minima and a second
global minimum located far from the true optimum.

We compare our algorithm with two very related works - one is Comprehensive
Learning Particle Swarm Optimizer For Global Optimization of Multimodal
Functions(CLPSO)Jj06 and other one is Enhanced comprehensive Learning Particle
Swarm Optimization(ECLPSO)Xi14 .We chose these two works because these two
works are more relevant to our work. The above mentioned works mainly deal
with multi-modal and composition objective test function, which we also
perform. We choose those optimization functions where optimal values are more
diverse and contain high number of false local optima.

Lehman and Stanley proposed the concept of Novelty Search in 2008, where they
formulated an idea of objective-free search Leh08 . The search operation is
based on behavioral novelty. They keep on showing the effectiveness of Novelty
search on various other research worksLeh10 Leh10b . They showed how open-
endness and objective free based search is quite effective and open a new way
of thinking about unknown domain searchLeh11 . Doncieux et. al provided
theoretical explanation of Novelty search in Don19 .

The major problem of PSO and its other variants is that they stuck in local
optima which leads to premature convergence. Once a promising solution found
by one particle of a swarm others gradually jump towards that location and
create stagnation. It does not search the entire area of the search region
finding nearby solution of local or global optimum. This is major concern of
Particle Swarm Optimization algorithms and this is one of the reasons that PSO
fails on those problems where diversity in searching is required. Using
Novelty Search we can easily avoid this problem. Once a novel area of
searching is found we apply PSO on that region to find the global optimum
solution. Then again we search another novel area and apply PSO there. The
search will not stop until there are no novel spaces are left. In this way the
present algorithm never stuck in any local optima because the algorithm is
never driven by best solution so far; rather it is driven by objective free
Novelty search.

In the present algorithm, Novelty Search controls PSO. First novelty search
algorithm finds novel area for searching and then calls PSO to search that
area for global optimum solution. We keep on continue this procedure until no
further novel area is left. This is where the present algorithm differs from
other PSO algorithms. Other PSO algorithms driven by objective; but the
present algorithm is driven by novelty search which is objective free.

What advantages we can get by combining Novelty Search with Particle Swarm
Optimization? Novelty search only check weather the search area is novel or
not. It is not driven by objective. That’s why it never stuck into some
location rather it freely moves around the entire search space. The main cause
of premature convergence is lack of divergence. After the population
converges, it becomes very uniform (all solutions resemble the best one).But
as Novelty search algorithm based on divergence, more diverge means higher
probability of getting selected for PSO search. Novelty search helps to roam
entire search space more quickly than any other evolutionary algorithm. We
consider that advantage in PSO to make it more explorative algorithm.

The paper is organized as follows: Section 2 considers a detail discussion
about novelty search. The basic concepts, general framework of our approach,
Novelty computation of a search region and novelty score calculation are
discussed section 3. Section 4 provides the algorithmic summary and pseducode
of the proposed Novelty Search based PSO algorithm.Section 5 provides detail
experimental studies on benchmark datasets CEC-13. Section 6 provides
Conclusion.

##  2 Quick Introduction to Novelty Search

###  2.1 Basic Idea

In 2008 Joel Lehman and Kenneth O. Stanley Leh08  proposed a new exploration
algorithm which is driven by novelty of search domain. From then this search
method gained quite popularity Leh10 , Leh10b ,Leh11 , Iz19 . The main
objective of their proposed method is to search for novel behavior in
behavioral space instead of specific objective. Even in objective based
problems this search method ignores the objective and look for behavioral
novelty. One benefit we can observe from this algorithm is that it overcomes
the obstacle of deception and provides an open-ended evolution.

In any evolutionary computation, there is one or more fitness function which
measures the progress of the algorithm towards an objective. This fitness
function is also known as objective function. Through deception such objective
functions may prevent the objective from being reach, which is basically the
problem of being trapped into local optima. Objective function themselves
misdirect the search into dead ends which is known as divergenceLehke11 .Such
Novelty Search ignores the objective, search for novel behavior and continues
the search as long as novelty exists in behavioral search space. We have seen
that Novelty Search asymptotically behaves like a uniform random search
process in the behavior spaceDon19  but it is for sure that Novelty search is
not Random Search Leh08  as experimental results shows that Novelty Search is
better than Random search.

Every swarm based algorithms or most of the evolutionary methods which are
objective based faces two most critical problems - Divergence and Convergence
into local optima. There are several approaches exist to tackle those problems
Ma12 , Hu19 .Those methods not only increase the complexity of the algorithm
but sometimes bring additional issues. Novelty search shows that in some
problems by ignoring the objective gives the search to achieve more
explorative power and better convergenceLehke11 .

###  2.2 Novelty Search Algorithm

How Novelty Search works is the main topic in this section. In traditional
evolutionary computing the overall progress is measured by single or multi
objective functions, but in novelty search instead of objective function there
is a novelty metric Lehke11  which basically measures the behavioral novelty
in the search space. Novelty search is not like Exhaustive search,in most of
the practical domains the novel behaviors are limited and reasonable which
help novelty search to find novel behaviors in finite time rather than
searching the entire search area exhaustively.

The novelty metric measures how unique an individual’s behavior is.
Importantly, like the fitness function, this measure must be fitted into the
domain of the search space. There is an archive which keep past behaviors of
other individuals when they are highly novel. The novelty of a newly generated
individual is computed with respect to the archive.The objective is to
identify how far away the new individual is from the rest of the population
and its predecessors in behavior space which is the space of unique behaviors.
This can be called as Sparseness of any point into the behavior space.

One measure of Sparseness at a point is the average distance to the k-nearest
neighbors of that point, where k is a fixed parameter based on experimental
problem. If the average distance to a given point’s nearest neighbors is large
then it is in a sparse area; if it is small then individual is in dense area.
The Sparseness $\mu$ at any point x can be computed as follows –

$\mu(x)=\frac{1}{k}\sum_{i=0}^{k}dist(x,\mu_{i})$ (1)

where $\mu_{i}$ is the ith-nearest neighbor of x with respect to the distance
metric dist. This dist is the behavioral difference between two individuals in
the search space. During the calculation of nearest neighbor current
population and the archive of novel individuals need to be taken into
consideration. Solution candidates from more sparse regions of this behavioral
search space receive higher novelty scores. If novelty is sufficiently high at
the location of a new individual,means above some minimal threshold value
$\mu_{min}$, then the individual is entered into the permanent archive.

The current population plus the archived population jointly produce a broader
sample space for current search;The gradient of search is simply towards what
is new, with no other explicit objective. As we see novelty search is
continuous process so we need to know when it will stop. To stop the search it
is necessary to check whether each individual meets the goal criteria Lehke11
.

Novelty Search is not a Random Walk Lehke11  rather novelty search maximize
novelty based on the use of archive and novelty metric. Novelty search gives a
profound impact on the area of objective based search algorithms like Particle
Swarm Optimization , Genetic Algorithm or other swarm based algorithms. If we
allow particles to roam freely using novelty search and augment it with
efficient yet simple objective function then we can achieve significant
performance improvement by truly avoiding deception problems.

###  2.3 Application Domain

Since the introduction of Novelty search in 2008 by Lehman and Stanley Leh08
novelty search has been applied to a wide range of problems in different
application domains with considerable amount of success. Those are
predominantly in Robotics domain such as - single robot controller Lehke11
Mu12 , controllers for homogeneous Go13  and heterogeneous Go14  domains,
robot morphologies Le14 , plastic neural networks Ri10 . A few applications
outside robotics can also befound like, machine learning Na13 ,En13  and game
content generation Li14 .

Novelty search is also applied with Particle Swarm Optimization to test the
convergence, better performance and applicability on different real world
domains. There are few related works in combination with Novelty search, such
as - Adam Ulrich et.al combine novelty search with particle swarm optimization
and tested CEC 2020 single objective bound-constrained optimization benchmark
functions to show the effectiveness of this hybrid approach Ul21 , David
Martínez-Rodríguez et.al apply PSO with Novelty search in combustion systems
to find out ultra-low emissions and minimum fuel consumption Da23 ,Diana F.
Galvao, et. al. combine Novelty search with PSO and apply that into
Grammatical Swarm to show the performance improvement and also how it avoid
premature convergence,They change the velocity equation with Novelty equation
and instead of $P_{Best}$ , $G_{Best}$ they call those $P_{novel}$ ,
$G_{novel}$ Ga21 . Novelty Search is combined with PSO in Hirad Assimi et.al’s
work and applied in truss optimisation problems and experimental results show
better performance over other state-of-the-art methods As21 , Clara Burgos
Simón et. al propose an idea about applying novelty search in particle swarm
optimization and tested with benchmark CEC 2005 Cl20 .

##  3 Novelty Search based PSO

###  3.1 Basic concepts

The proposed method has two parts. First part is Novelty Search and second
part is PSO algorithm. We do not change anything on PSO algorithm. We design
appropriate Novelty Search algorithm and augment it with existing PSO
algorithm.

###  3.2 General framework

Our novelty search algorithm decides in which region PSO search will be
applied based on novelty of that region. After that decision, PSO search will
initiate. Even if PSO finds better results than in previous iteration, search
will not stop until no novel area is left.

Let’s explain our approach step by step:

First, we decide how many particle will be deployed initially on the
application search area. Suppose, we deployed 5 particles on the application
search region e.g. $P_{1},P_{2},P_{3},P_{4},P_{5}$. We call them Leader
Particles. These five Leader particles will initiate PSO search once they find
novel area for searching. Movement of Leader particles solely based on novelty
search.

After randomly distributed over search area, each Leader particle $P_{i}$ will
check novelty of their search region with other particle’s search region. By
search region, we mean to say that a circular area whose center is the Leader
particle’s position and radius r is pre-determined by the application. The
concept of $P_{i}$’s search region is better explained with a diagram shown in
figure-1.

$P_{i}$r  Figure 1: Circular region defined by Leader particle $P_{i}$ with
radius r. $P_{1}$r $P_{2}$r $P_{3}$r $P_{4}$r $P_{5}$r $x$$y$ Figure 2:
Randomly distributed five Leader particles $P_{1},P_{2},P_{3},P_{4},P_{5}$
with radius r in search domain.

In Figure-2, We randomly distribute five Leader particles $P_{1}$ to $P_{5}$
in the two dimensional application search domain. Here, we need to remember
that our experimental optimization test functions are not two dimensional and
most of the times they are either 10,30,50 or more than that. That means it is
not always circle(two dimensional) or sphere (three dimensional) rather it is
N-sphere or Hypersphere in N+1-Dimensional Euclidean space.

For N+1 Euclidean dimensional Space, if the points defines as
($x_{1},x_{2},x_{3},...,x_{N}+1$) that defines the n-space, $S^{N}(r)$, is
represented by the equation –

$r^{2}=\sum_{i=1}^{N+1}(x_{i}-c_{i})^{2}$ (2)

where, c = ($c_{1},c_{2},...c_{N}+1$) is a center point, and r is the radius.

For mathematical representation we mention equation-(2). But for our
experiment we only need the calculation to check weather any N-dimensional
point lies inside, outside or on the boundary of the Hypersphere, which is not
different from calculating the same, with circle. So for simplicity we keep
our discussion in the concept of a circle(in two dimensional problem space) as
per figure-(2).

Now,each $P_{i}$ defines its region based on radius r. Each $P_{i}$ will
initiate PSO search based on its novelty score. Novelty score and all other
related terms are discussed in Novelty of a Search Region section(section 3.3)
.

Once a Leader particle $P_{i}$ finds that, its search region is novel in
comparison with other $P_{j}$’s (Where, j$\neq$i and j = 1 to n) search
region, that leader $P_{i}$ will initiate PSO algorithm to find better
solution of the given optimization problem.

What PSO algorithm will be used and how they will perform, will be discussed
in section 3.3.4 in detail.

But, if any Leader particle $P_{i}$ finds that, its search region is not
enough novel with any other $P_{j}$’s (Where, j$\neq$i and j = 1 to n) search
region, it will not perform any PSO search; rather it will re-compute its
position.

Let us shed some light on what does it mean by not enough novel. It means that
search region is either already searched by other Leader particles or this
Leader particle in some previous iteration. Repeatedly searching the same
region instead of keeping open some other unsearched area is not the purpose
of novelty search. Here, one may argue that, many PSO instances are roaming
around; as there is no modification in PSO then how it eliminates premature
convergence? One thing we need to make clear here, novelty search helps to
jump from one place to another based on their behavioral novelty, and the
premature convergence happens because of lack of diversity, which is not
happening during novelty search. Rather we can ask the question how PSO will
reach into the optimal solution? because inside one Leader particle’s search
region PSO is performing its search. What happens if it gets stuck in local
optima? It will be clear more when we will discuss different categories of
novelty in section 3.3.2.

The major difference here is that, if any leader particle finds better
solution than its earlier iteration the search will not stop there; and the
better solution achieved so far will not communicate with other leader
particles immediately; rather Leader particles store their solution in an
archive and jumps to the next novel location and keep on searching until there
are no novel search region left. By this approach we can explore more and more
unknown territory and will never be stuck in any local optimum valley.

Does it looks like Random Restart of a group of multiple PSO? Lets discuss the
major difference between Random Restart plus some local optimizer and our
approach. In our algorithm a group PSO is used under the name Leader
particles. Those Leader particles control their corresponding PSO groups. They
decide where to search based on novelty. Novelty search is a divergence
algorithm. Novelty search helps our algorithm to cover the unknown territory
much quicker as it is driven by difference between two locations. The more
difference means more suitable for performing the PSO search. Not novel means
no unnecessary search will happen. But in case of random restart it will not
guarantee that same search region will not reappear again. Not only that our
purpose for novelty search is exploration. No number of random restart can
assure the coverage of entire search area no matter how efficient local
optimizer we use.

In PSO, stuck into local optimum for a considerable period of time is the
major concern; especially for those optimization function where there are many
more local valleys and global solution is far from local solution. As PSO is
objective based search method. So any particle finds any so-far-best solution
other particles will automatically jump towards that location without
exploring other areas. Novelty search overcomes this problem as “objective-
free” searching is its inherent nature. No matter what PSO search will result,
Novelty search forces leader particles to keep on searching for any better
results. In this way the present approach becomes better explorative algorithm
than existing PSO methods.

In summary the present algorithm works as follows;
Step 1: Deployment of ”Leader particles” $P_{i}$ into the application search
area.
Step 2: Based on application based radius value ( r ) a circular region is
defined by leader particle $P_{i}$, and $P_{i}$ is positioned at the center of
the search region.
Step 3: Each leader particle $P_{i}$ will compute its novelty score with other
leader particles.
Step 4: if $P_{i}$’s search region is novel compare to other particle’s search
region it will perform PSO search on that search region. A global archive
NS_archive for storing locations is used. NS_archive is a multidimensional
global vector.Each $P_{i}$ stores its location into NS_archive whenever it is
performing its PSO search.
Step 5: if $P_{i}$’s search region is NOT novel compare to other particle’s
search region, $P_{i}$ will re-compute new position without initiating any PSO
search.
Step 6: This process will continue until no “Novel” search area is left in the
application search region.

###  3.3 Novelty of a Search Region

In this section we will discuss how novelty of a region which is identified
and controlled by leader particle $P_{i}$ is computed.

####  3.3.1 Novelty Computation Procedure

First let us clarify why we compute novelty of any region. In simple word
Novel region means that region which is still not searched by any PSO team.
Here by PSO team means , a group of particles whose leader is “Leader Particle
$P_{i}$”. Once $P_{i}$ finds that its current region is not previously
searched by any leader particle and none of the other leader particles
currently holding that region , $P_{i}$ will initiates PSO searching. We
augment novelty search with pso search because novelty search gives PSO more
explorative power. To search unknown territory we need an algorithm which is
not governed by any objective based method. Novelty search is perfectly fit
for that. It is objective free and its simplistic approach helps PSO to search
more diverse area.

Let’s discuss in detail how we compute novelty. After leader particles are
distributed over the application search area, they first compute its region.
Here region means the circular area whose center is leader particle’s
($P_{i}$)’s coordinate position and whose radius (r) of that circular area.
Radius r is obtained from the need of the application. Computation of r is
based on application domain. In our experiment we use a dynamic approach for
computing r. We first use r = 1, a unit value then increment this value by 0.1
as per our need. Larger r value indicates that PSO search takes longer time
and lesser r value means novelty search takes more time to cover the whole
search space. So we try to keep this value moderate. We will calculate the
impact of r-value and find out what will be the best possible value of r for
the algorithm to give best result as our future work.

By referring figure-(1), we see that the center of the circular area hold by
particle $P_{1}$ is $P_{1}$’s coordinate position and r is its radius. Region
is the area - $\pi r^{2}$. We calculate this area for the purpose that when
leader particle initiates PSO search , it randomly distributes particles
inside that area. We need to check that no particle is outside of that area.
For that we use equation- (4), which is the distance between two particles,
$d_{i}$, if $d_{i}>$ r then the particle is outside; reject the particle else
accept the particle.

When every leader particle knows its region it computes its novelty with
respect to other leader particle. Novelty of a leader particle is judged by
its novelty score as stated in section 3.3.2.

We explain the novelty computation as follows; We consider the example of 5
leader particles of figure-(2). Suppose first leader particle $P_{1}$
calculates its novelty. For that, $P_{1}$ first decides whether $P_{1}$ has
already searched that area or any other leader particle searched that area
earlier by calculating novelty score with each of them. We call novelty
calculation between two particles position as ”novelty score(ns)”. $P_{1}$
calculates novelty score(ns) with its previous position and also other
particle’s previous positions one by one. This ns calculation is basically the
distance calculation according to the equation-(4). Once $P_{1}$ gets all the
ns value from $P_{1}$ to previous position of $P_{2},P_{3},P_{4},P_{5}$ and
its own previous position. $P_{1}$ will compute average ns value according to
the equation-(5). All the previous locations where successful PSO search occur
is stored in NS_archive. So each $P_{i}$, after deployment into the search
domain, consult its own position with the locations stored in NS_archive.

If the novelty score(ns) is below “novelty_threshold” value, it indicates that
$P_{1}$’s region is already searched. Therefore there is no point in searching
the same region again. So $P_{1}$ stops calculating novelty score any further
and sends recompute message to itself as shown in the figure-(3). Otherwise no
action is taken and $P_{1}$ moves to next step. The novelty_threshold is
discussed in section 3.3.3. Let us consider that it is a numerical value with
which comparison of ns happens.

In figure-(3), all dashed circles are leader particle’s previous position.We
renamed them as $P_{1}^{\prime},P_{2}^{\prime},P_{3}^{\prime},\\\
P_{4}^{\prime},P_{5}^{\prime}$. Current position of $P_{1}$ is same as
$P_{1}$. Consider that $ns_{1},ns_{2},ns_{3},ns_{4}$ and $ns_{5}$ are novelty
score of $P_{1}$ with the leader particles $P_{1},P_{2},P_{3},P_{4}$ and
$P_{5}$’s previous position respectively. Suppose $ns_{1}$ is below novelty
threshold value $Th_{N}$ then $P_{1}$ sends recompute message to itself as
shown in the figure-(3). This is indicated by a violet colored self loop
marked in $P_{1}$. $recompute(P_{1}^{\prime})$ indicates that $P_{1}$ sends a
recompute message to itself because $P_{1}$ searched this place previously.

$P_{1}$r $ns_{1}$ $ns_{2}$ $ns_{3}$ $ns_{4}$ $ns_{5}$
$recompute(P_{1}^{\prime})$ $P_{1}^{\prime}$r $P_{2}^{\prime}$r
$P_{3}^{\prime}$r $P_{4}^{\prime}$r $P_{5}^{\prime}$r $x$$y$ Figure 3: Novelty
Score checking with the leader particles previous positions.

When $P_{1}$ finds that no particle, not even itself search that area
previously, then it checks whether anyone among $P_{2},P_{3},P_{4}$ and
$P_{5}$ are currently holding the same region. To check that, $P_{1}$ computes
novelty score with $P_{2},P_{3},P_{4}$ and $P_{5}$ one by one. If any novelty
score is below “novelty_threshold” value then $P_{1}$ sends a “recompute”
message to itself as shown in figure-(4), but this time recomputation is done
due to closely overlapping position with other particles.

$P_{1}$r $ns_{2}$ $ns_{3}$ $ns_{4}$ $ns_{5}$ $recompute(P_{1}^{\prime})$
$P_{2}$r $P_{3}$r $P_{4}$r $P_{5}$r $x$$y$ Figure 4: Novelty Score checking
with other leader particles. recompute message is sent to itself.

In the figure -(4), $P_{1}$ to $P_{5}$ all leader particle’s position are
updated. Now they are in different positions than figure-(2). $P_{1}$ computes
novelty score with all the leader particles one by one, as we can see
$ns_{1},ns_{2},ns_{3},ns_{4}$ and $ns_{5}$. But $ns_{4}$ shows that particle
$P_{4}$ is too close to particle $P_{1}$. Their searching region is largely
overlapping. As searching the almost same region by two leader particle is not
meaningful, $P_{1}$ sends a recompute message to itself. we can see a violet
colored arrow from $P_{1}$ to $P_{1}$ indicating the re-computation of
position.

Here, two scenario can happen during ns calculation. one is - sequential ,
that means first $P_{1}$ calculates its ns then $P_{2}$, $P_{3}$,$P_{4}$, and
$P_{5}$. If that happen then $P_{1}$ only need to compute ns with the previous
positions of all the leader particles including itself by consulting
NS_archive table. No need to compute ns with current positions of all the
leader particles. Second one is - parallel, if the environment allows all the
particles parallel computation then $P_{1}$ will check NS_archive table for
the current position of all other leader particles during its ns calculation.

Once all the novelty score is calculated, leader particle calculates average
of all the novelty score. As per our above figure particle $P_{1}$ calculates
average of $ns_{2},ns_{3},ns_{4}$ and $ns_{5}$ as follows.

$N_{i}=\sum_{j=1}^{n}\frac{ns_{j}}{n-1}$ (3)

where $j\neq i$ and n is the number of leader particles.

Now this average of novelty score($N_{i}$) is called novelty of $P_{i}$.

By calculating average of all novelty score gives us the indication weather
$P_{i}$ will search that region or not. After calculating the novelty value,
$P_{i}$ will check whether this $N_{i}$ is above the
“novelty_threshold”($Th_{N}$) boundary. If $N_{i}$ $\geq$ $Th_{N}$ then the
region holds by leader particle $P_{i}$ is novel enough to initiate PSO search
else $P_{i}$ will again recompute its position.

####  3.3.2 Novelty score calculation

Novelty score, calculated between two particles, indicates how close two
regions are. Basically it is the Euclidean distance between two leader
particles. If two leader particles are too close that means two regions are
mostly overlap. Two highly overlapped region means two PSO teams performing
their search operation on that region where most of the area is common.
Searching the same area by two PSO teams wasted the searching capability of
swarm particles of both of the teams. If leader particles $P_{i}$ are in
enough distance it means they are enough novel and searching the unsearched
area is quite justified. The formula for Euclidean distance between two leader
particles in a multidimensional environment is as follows -

$d_{i}^{2}=\sum_{v=1}^{dim}(X_{vi}-X_{vj})^{2}$ (4)

where, $d_{i}$ is the distance between particle $P_{i}$ and $P_{j}$. $v=1$ to
$dim$ is the dimension which depends on application. $X_{vi}$ and $X_{vj}$ is
the coordinate positions of particle $P_{i}$ and $P_{j}$.

In figure-(5), $d_{1}$ is the distance between $P_{1}$ and $P_{2}$. Distance
is calculated based on two dimensional search space.

$P_{1}$r $P_{2}$r $d_{1}$
$d_{1}=\sqrt{(X_{2}-X_{1})^{2}-(Y_{2}-Y_{1})^{2}}$$x$$y$ Figure 5: Distance
between two regions $P_{1}$ and $P_{2}$ in a 2 dimensional search
space.$d_{1}=\sqrt{(X_{2}-X_{1})^{2}-(Y_{2}-Y_{1})^{2}}$

As distance clearly influence novelty, so how much closeness is novel and how
much is not is a matter of discussion. There are several stages of novelty.

Let us discuss novelty score scenario one by one.

  * •

Case 1: [ d $\geq$ 2*r ] : When distance(d) between two regions is grater than
or equal to twice of radius(r) of the region than this two region is perfectly
distinct, highly novel and good candidates for PSO searching. So both $P_{1}$
and $P_{2}$ will initiate PSO searching. Figure -(6) showing this Case 1.

$P_{1}$$P_{2}$r r $d_{1}$ $2*r$Case 1: When $d_{1}\geq 2*r$$x$$y$Completely
Novel area for $P_{1}$ and $P_{2}$ Figure 6: Two regions at 2*r distance apart
are perfect candidates for PSO searching.

  * •

Case 2: [ r $\leq$ d $\leq$ 2*r ] : If the distance d is higher than the
radius(r) but lower than the 2*r then though there is some common area for
searching but still a lot of area is different and needs searching. The exact
scenario is shown in figure-(7).

$P_{1}$$P_{2}$r r Case 2: When r $\leq$ $d_{1}$ $<$ 2*r $d_{1}$
$<2*r$$x$$y$$P_{1}\cap P_{2}<50\%$Novel area for $P_{2}$ $>50\%$Novel area for
$P_{1}$ $>50\%$ Figure 7: Two regions are overlapped. This less than $50\%$
Common area is redundant region for searching.

  * •

Case 3: [ d = r ] : If the distance d is exactly same as radius(r) of the
region, that means $50\%$ search region is matched. So we are left with other
$50\%$ which is unique and need to be searched. Now it is upto the application
whether we will continue to search that area or not. In general thinking, it
will be good if we initiate PSO search on that $50\%$ search region. This is
$50\%$ novelty condition which is good condition for PSO search. This scenario
is shown in figure-(8).

$P_{1}$$P_{2}$Case 3: When $d_{1}=r$ r r $d_{1}$ $r$$x$$y$$P_{1}\cap
P_{2}=50\%$Novel area for $P_{2}$ $=50\%$Novel area for $P_{1}$ $=50\%$ Figure
8: Two regions of $P_{1}$ and $P_{2}$ are overlapped exactly $50\%$. So both
$P_{1}$ and $P_{2}$ left with $50\%$ unsearched unique area.

  * •

Case 4: [ 0 $<$ d $<$ r ] : If the distance d is less than the radius(r) of
the region, that means more than $50\%$ search region is matched between two
leader particles. So we are left with very less amount of search region which
is unique. As the novel region is very less than either we recompute a new
position by leaving this region unsearched or we keep on performing PSO search
on this area. Here novelty_threshold($Th_{N}$) is required, which will
determine what we will do. This case is shown in figure-(9).

$P_{1}$$P_{2}$Case 4: When 0 $<$ d $<$ r r r $d_{1}$
$r_{2}$$r_{1}$$x$$y$$P_{1}\cap P_{2}$ $\gg$ $50\%$ and $d_{1}$ is $\ll$
$r_{1}$ and $r_{2}$Novel area for $P_{2}$ $\ll$ $50\%$Novel area for $P_{1}$
$\ll$ $50\%$ Figure 9: Two regions of $P_{1}$ and $P_{2}$ are overlapped more
than $50\%$. So both $P_{1}$ and $P_{2}$ left with very less unsearched unique
area.

  * •

Case 5: [ d = 0 ] : If the region holds by the leader particles completely
overlap with each other then there will be no novel region left. So no need of
initiating PSO search in that region.Basically one of them will search that
area and other leader particle will move to other region by re-computing its
position. Complete overlapping is very rare thing to occur, because we need to
remember that positions are distributed randomly in the application search
area. So it is very much unlikely that two random numbers are same. So this
case which is shown in figure-(10) is very uncommon incident.

$P_{1}$$P_{2}$Case 5: When d = 0 r r $d_{1}=0$ $2*r$$x$$y$$P_{1}\cap P_{2}$ =
$100\%$No Novel area left for $P_{1}$ and $P_{2}$! Figure 10: Two regions of
$P_{1}$ and $P_{2}$ are completely overlapped. So both $P_{1}$ and $P_{2}$
left with zero unsearched unique area.

By observing all possible novelty cases, we can represent them in a tabular
form as shown in Table-1.

Table 1: Tabular representation of different novelty cases and their categories. Case Number | Condition | Novelty Percentage | Category | Remark
---|---|---|---|---
1 | d $\geq$ 2*r | 100% | Highly Novel | Perfect for PSO search
2 | r $<$ d $<$ 2*r | 51 - 99% | Moderately Novel | Good for PSO search
3 | d = r | 50% | Typically Novel | OK for PSO search
4 | 0 $<$ d $<$ 2*r | 1 - 49% | Low Novel | Less Likely for PSO search
5 | d = 0 | 0% | Not Novel | Not for PSO search

After careful consideration of all possible novelty cases, we come to a
formula for calculating average novelty score for particle $P_{i}$ that is
$ns_{i}$ is as follows -

$ns_{i}=(\frac{d_{i}}{2*r})*100$ (5)

Now we come to the point where we need novelty threshold value. It is totally
based on application. Clearly from the table -1, if we set very low value of
novelty threshold like case -4 (1-49%) that means we allow two PSO team to
search closely. If our application demand closeness we can set low novelty
threshold value. If two regions are highly novel like case-1(100%) as per
table-1, that signifies that these two regions are not overlapping so both the
leader particle can initiate searching.

So initially, having moderate threshold value is good for exploration, when
there is vast area unsearched. And if we keep decreasing novelty threshold
value as time passes more rigorous search will happen which include boundary
areas of region. If we set $Th_{N}$ is high(closely 100%) then the following
scenario like the figure-(11) will happen. We can see the triangle shaped area
is left unsearched. Like this many more fragments of search area will be left
unsearched. The problem of setting high $Th_{N}$ value creates many small
unsearched fragments that is why decreasing the threshold improves the
situation and left no unsearched area also makes our algorithm more diverse.

One important point here is when we stop novelty search? In our experiment we
keep on performing novelty search until all the Leader particle’s novelty
score according to the equation-(5) is in ”Low Novel” category as per table
-1. This gives us excellent results in more complex multidimensional and
multi-modal functions.

$P_{1}$$P_{2}$$P_{3}$$x$$y$Triangle shaped unsearched region Figure 11: Two
regions of $P_{1}$ and $P_{2}$ are completely overlapped. So both $P_{1}$ and
$P_{2}$ left with zero unsearched unique area.

####  3.3.3 Novelty Threshold

This novelty_threshold or $Th_{N}$ value is pre-determined by the application.
A simple idea behind novelty_threshold is how much close two PSO teams will
search? There is no point of searching the same place by two different PSO
teams. So obviously one PSO team will be withdrawn from that region and
replaced to some other search area. If $Th_{N}$ value is very low then two PSO
team will search very closely and almost same place, and if the $Th_{N}$ value
is very high then two PSO team will be far away and lots of search area will
be unsearched. So we will keep this threshold value in a moderate level so
that entire area will be searched properly and no area is left unsearched.

####  3.3.4 Variant of Particle Swarm Optimization used in our algorithm

We can use any variant of particle swarm optimization algorithm for our
method. Every PSO algorithm has two parts; one exploration and another
exploitation. Exploration helps pso to search more diverse area where as
exploitation helps to go deeper if any promising search area found. According
to the latest benchmark test optimization functions lia13  most of the PSO
variants suffers when the test function becomes complex, non-seperable and
asymmetrical. The latest standard for PSO algorithm which is known as
”SPSO11”Cle11 , also fails to deliver promising performance on those functions
where there is huge number of local minima and second global minimum is far
from first true optimum Zam13  .

Choosing a variant which is good in terms of ”Exploitation” is a perfect fit
for our method, because novelty search do the ”Exploration” part far better
than any other algorithm. Once Novelty search finds out a location for
performing PSO search, any good exploitive PSO will do the job.

In our case we took BareBones-PSO variant developed by Kennedy Ken03 . The
reason behind this is its simplicity. This method is Velocity free, and its
particles positions are based on Gaussian distribution. Its simplified
position equation is as follows -

$\small x_{ij}(t+1)\sim
N\biggl{(}\frac{pbest_{ij}(t)+gbest_{j}(t)}{2},|pbest_{ij}(t)-gbest_{j}(t)|\biggr{)}$
(6)

where let’s
$\rho$ = $|$$pbest_{ij}(t)$ \- $gbest_{j}(t)$$|$ and
$\sigma=\frac{pbest_{ij}(t)+gbest_{j}(t)}{2}$

then $\rho$ is the mean of $pbest_{ij}(t)$ and $gbest_{j}(t)$ and $\sigma$ is
standard deviation of $pbest_{ij}(t)$ and $gbest_{j}(t)$ and N( $\sigma,\rho$
) is the Gaussian Distribution $\sigma$ and $\rho$. $pbest_{ij}(t)$ and
$gbest_{j}(t)$ are as usual pso terms of local best position and global best
position at time t.

Discussing a lot more things about Bare Bones PSO like maximum iterations and
number of restarts etc are not the objective of our paper. Please follow Ken03
, Pan08 , Tim11  for more information about Bare Bones PSO and its Theoretical
analysis.

After Novelty Search, when leader particle calls Bare-Bones PSO, it is upto
Bare-Bones PSO which will generate a group of random particles on that region
controlled by leader particle. As the search region is comparably small than
other PSO variants then its search become faster and deeper.

After the completion of search if global best position is below fitness
threshold value ($Th_{f}$) then that position will be kept in record, that is
in the PSO_archive. This PSO_archive gives us the optimum value achieved by
our algorithm and it is a global table. Initially it looks that this
PSO_archive is huge table with million of values as the algorithm runs on high
number of iterations, but in practice this table does not store every PSO
particles iterations value , its just keep best achieved PSO result on each
successful novelty search iteration. In number of iterations novelty search is
much lesser than PSO search. Thats why this PSO_archive table is finite and
easily traceable.

So, simultaneously all the leader particles will perform their PSO search( if
not re-computing its position) and keep their best achieved position into the
global PSO_archive table. There is another approach we can perform,instead of
storing the result after PSO search, we define a new parameter Gbest where we
keep the best achieved result so far. Whenever, a Leader particles finishes
its PSO search it will compare its newly-founded result with Gbest, if it is
better than Gbest, Gbest will be updated with newly founded value and Leader
particle will move on to the next novel location else no updation needed. We
try both of them (PSO_archive,Gbest) in our experiment. PSO_archive gives us
the trajectory of each Leader particles where as Gbest gives us the exact
optimum value and helps us to get rid of maintaining a global table and
finding the result later.

Algorithm-(4) clearly explain the workings of Bare-Bones PSO algorithm.

$P_{1}$$x$$y$Swarm particles inside the region of $P_{1}$ Figure 12: Inside of
a region of leader particle $P_{1}$ where a group of particles are searching
for global solution.

In the figure-(12), a typical region of leader particle $P_{1}$ is shown. Here
$P_{1}$ calls Bare-Bone PSO and red dots are swarm particles generated
randomly inside the region of $P_{1}$. They keep on searching that region
until they converge to some solution.

##  4 Algorithmic summary

The Novelty Search based Particle Swarm Optimization Algorithm(NSPSO) is
represented in pseuducode as follows - see in page -(12).

There are 4 algorithms. NSPSO(), NC(),NS() and BBPSO() All of them are quite
self-explanatory.

NSPSO() algorithm is the main algorithm. NSPSO() algorithm calls Novelty
Computation(NC()) algorithm for every iteration by every leader particles.
After NC() returns novelty value(N) to the NSPSO(), NSPSO() calls PSO search
algorithm BBPSO() if novelty value is grater than threshold value ($Th_{N}$).
If not then NSPSO() calls RECOMP() function which randomly select positions
inside the application search region.

Algorithm NC() calls Novelty Score Calculation algorithm NS() every time it is
required for every leader particles current position and their previous
positions.

Algorithm 1 Novelty-Search-PSO Algorithm

1:procedure NSPSO()

2: —————————————-Initialization Phase————————————————————————-

3: $\text{Particle P}\leftarrow\text{n}$ $\triangleright$ [n : Number of
particles.]

4: $\text{PositionTable PT(n)}\leftarrow\text{NULL}$ $\triangleright$ [PT :
Position Table holds the position after performing PSO search.]

5: $\text{P(n)}\leftarrow\text{Random Positions RAND()}$ $\triangleright$
[RAND() : Randomly define n number of positions for n particles.]

6: $\text{F(n)}\leftarrow\text{CALL FIT(P(n))}$ $\triangleright$ [FIT(P(n)) :
Compute Fitness function for n particles based on applications.]

7: $\text{PBEST(n,P)}\leftarrow\text{NULL}$ $\triangleright$ [PBEST(n,P) : It
holds best achieved fitness value and position after PSO search.]

8: $\text{RT(n)}\leftarrow\text{NULL}$ $\triangleright$ [RT(n) : Re
computation Table.]

9: for $\text{i}\leftarrow 1$ to n do

10: $\text{N(i)}\leftarrow\text{CALL NC(P(i),n)}$ $\triangleright$ [NC() :
Novelty Computation algorithm.]

11: $\text{PBEST(i,P(i))}\leftarrow\text{(i,P(i))}$ $\triangleright$
[PBEST(i,P(i)) : It holds initial position of P(i).]

12: end for

13: —————————————-Main Algorithm Phase———————————————————————-

14: for $\text{itr}\leftarrow 1$ to MaxIterations do $\triangleright$
[MaxIterations : Maximum number of iterations.]

15: for $\text{i}\leftarrow 1$ to n do

16: if N(i) $>=$ $Th{{}_{n}}$ then $\triangleright$ [$Th{{}_{n}}$ : Novelty
Threshold value determined by the application.]

17: $\text{bp}\leftarrow\text{CALL PSO\\_SEARCH(P(i))}$ $\triangleright$
[PSO_SEARCH() : Calling PSO algorithm with particle P(i).]

18: if FIT(bp) $\leq$ FIT(PBEST(P(i))) then

19: $\text{PBEST(i,P(i))}\leftarrow\text{(i,bp)}$ $\triangleright$ [Update
PBEST if new best position is better than old best position.]

20: end if

21: $\text{PT(i)}\leftarrow\text{P(i)}$

22: $\text{P(i)}\leftarrow\text{CALL RECOMP(P(i))}$ $\triangleright$ [RECOMP()
: Redistribute particle to a new position.]

23: else

24: $\text{P(i)}\leftarrow\text{CALL RECOMP(P(i))}$

25: end if

26: end for

27: for $\text{i}\leftarrow 1$ to n do

28: $\text{N(i)}\leftarrow\text{CALL NC(P(i),P(n))}$ $\triangleright$
[Calculate new novelty value for the new positions.]

29: end for

30: end for

31:end procedure

Algorithm 2 Novelty Computation Algorithm

1:procedure NC(P(i),n)

2: $\text{N}\leftarrow\text{0}$ $\triangleright$ [N : Novelty value of
particle P(i). ]

3: $\text{j}\leftarrow\text{0}$

4: ——————————-Novelty Checking for Previously Searched Positions—————————————–

5: while PT(j) $\neq$ 0 do

6: $\text{tmp}\leftarrow\text{CALL NS(P(i),PT(j))}$ $\triangleright$ [NS() :
Novelty Score Calculating function.]

7: if tmp $<$ $Th{{}_{n}}$ then

8: $\text{RT(i)}\leftarrow\text{ "true"}$ $\triangleright$ [Send
”recomputation” message to itself.]

9: Break $\triangleright$ [This position is searched previously so leave
immediately and recompute current position.]

10: end if

11: $\text{j}\leftarrow\text{j+1}$

12: end while

13: ——————————-Novelty Checking for Current Positions——————————————————-

14: $\text{j}\leftarrow\text{0}$ $\triangleright$ [Re initializing local
variable j.]

15: if RT(i) $==$ ”true” then $\triangleright$ [Particle P(i) receive
”recomputation” message.]

16: $\text{N}\leftarrow 0$ $\triangleright$ [Forcefully making novelty score
of P(i) very low.]

17: else

18: while j $\leq$ n do

19: $\text{tmp}\leftarrow\text{CALL NS(P(i),P(j))}$ $\triangleright$
[Calculate Novelty Score for all other particles.]

20: if tmp $<$ $Th{{}_{n}}$ then

21: $\text{RT(j)}\leftarrow\text{ "true"}$ $\triangleright$ [Send
”recomputation” message to Other particles.]

22: end if

23: $\text{N}\leftarrow\text{N+tmp}$ $\triangleright$ [Summing Novelty Score
for all the particles.]

24: $\text{j}\leftarrow\text{j+1}$

25: end while

26: $\text{N}\leftarrow\text{N$/$(n-1)}$ $\triangleright$ [Averaging the
Novelty Score for the particles P(i).]

27: end if

28: Return(N)

29:end procedure

Algorithm 3 Novelty Score Calculation Algorithm

1:procedure NS(P(i),P(k))

2: $\text{ns}\leftarrow\text{0}$

3: $\text{d}\leftarrow\text{0}$

4: $\text{a}\leftarrow\text{P(i)}$

5: $\text{b}\leftarrow\text{P(k)}$ $\triangleright$ [d: distance variable]

6: $\text{d}\leftarrow\ \sqrt{\sum_{i=1}^{dimension}\ (a_{i}^{2}-b_{i}^{2})}$
$\triangleright$ [Computing Euclidean Distance for multidimensional points.]

7: if d $\geq$ 2*r then $\triangleright$ [r : radius value of the PSO region
determined by applications.]

8: $\text{ns}\leftarrow 100$ $\triangleright$ [P(i) gets 100% novelty.]

9: else

10: $\text{ns}\leftarrow(\frac{d}{2*r})*100$ $\triangleright$ [In all other
cases P(i) gets ”ns” novelty according to this formula.]

11: end if

12: Return (ns)

13:end procedure

Algorithm 4 PSO_SEARCH Algorithm

1:procedure BBPSO(P(i))

2: ————————-We Use Bare Bones Particle Swarm Optimization Algorithm—————————–

3: $\ P_{n}\ \leftarrow\text{n}$ $\triangleright$ [Randomly initialize n
particles inside the circular region centered by P(i).]

4: $\ f_{n}\ \leftarrow\text{NULL}$ $\triangleright$ [$f_{n}$ : Holds fitness
values of all the particles.]

5: for $\text{i}\leftarrow 1$ to n do

6: $\ f_{i}\ \leftarrow\text{CALL FIT}(P_{i})$ $\triangleright$ Every particle
P(i) computing its Fitness.]

7: $\ P_{Best_{i}}\ \leftarrow P_{i}$ $\triangleright$ [In initialization
phase Every Particle $P_{i}$’s position is $P_{Best}$.]

8: end for

9: $\ G_{Best}\ \leftarrow{\\{P_{i}\mid f_{i}(P_{i})\text{ is minimum}\\}}$
$\triangleright$ [$G_{Best}$ holds best particles position among all
$P_{Best}$.]

10: while $\ (G_{Best}\ $ $\leq$ $\ Th_{f})\ $ or (itr $\leq$ MaxItr) do
$\triangleright$ [$Th_{f}$ : Fitness Threshold value determined by the
application.]

11: for $\text{i}\leftarrow 1$ to n do

12: $m=\frac{G_{Best}+P_{Best}}{2}$ $\triangleright$ [m : Mean of $G_{Best}$
and $P_{Best}$.]

13: $sd=\lvert G_{Best}-P_{Best}\rvert$ $\triangleright$ [sd : Standard
Deviation of $G_{Best}$ and $P_{Best}$.]

14: $\ newP_{i}\ \leftarrow N(m,sd)$ $\triangleright$ [N(m,sd) : Gaussian
Distribution of Mean and Standard Deviation.]

15: $\ newf_{i}\ \leftarrow\text{CALL FIT}(newP_{i})$ $\triangleright$
[$newf_{i}$ : New Fitness is Calculated based on $newP_{i}$.]

16: if $newf_{i}$ $<$ $f_{i}$ then $\triangleright$ [Less then symbol($<$)
used for minimization problems.]

17: $\ P_{Best_{i}}\ \leftarrow newP_{i}$

18: end if

19: $\ P_{i}\ \leftarrow newP_{i}$ $\triangleright$ [New Position is updated.]

20: end for

21: $\ G_{Best}\ \leftarrow{\\{P_{i}\mid f_{i}(P_{i})\text{ is minimum}\\}}$
$\triangleright$ [$G_{Best}$ updated based on new positions.]

22: end while

23: if $f(G_{Best})$ $<$ $Th_{f}$ then $\triangleright$ [If achieved
$G_{Best}$ is better than fitness Threshold value return $G_{Best}$.]

24: $\text{Return}(G_{Best})$

25: end if

26:end procedure

##  5 Experimental Result and Analysis.

###  5.1 Experimental Setting.

The proposed Novelty Search based Particle Swarm Optimization algorithm
approach is tested by MatLab 2015a on a 64 bit PC with Intel i5 processor with
3 GHz speed.

###  5.2 Benchmark Setting.

For our testing purpose we choose mainly mulimodal test functions and few
unimodal problems. Our main objective is to check the performance of our
algorithm NSPSO in complex environment where global optima is far from local
optima and there are multiple local optima. We use two unimodal function and
14 multimodal benchmark functions Jj06 ,Xi14 ,Xi19 ,Co03 ,Ji19 .

All the functions are tested on 10 and 30 dimensions. Experimental test
metrics are as follows –

  1. 1.

Running times : 25 times

  2. 2.

Population size : 40

  3. 3.

Maximal fitness evaluations (MaxFES) : 5000 * D * 60

D is used as dimension of the problem. The above test metrics are used for all
the comparative algorithms like CLPSO or ECLPSO but for NSPSO we use following
metrics which are same as above except population size.

  1. 1.

Running times : 25 times

  2. 2.

Population size : 25

  3. 3.

Maximal fitness evaluations (MaxFES) : 5000 * D * 60

  4. 4.

Number of Leader Particles : 7

We can divided the functions according to their properties into four groups :
Unimodal Functions,Unrotated Multimodal Functions, Rotated Multimodal Function
and Composition Functions.

The formulas and properties of all the test functions are described as follows
–

Group A: Umimodal and Simple Multimodal Functions:

1\. Sphere Function

$f_{1}(x)=\sum_{i=1}^{D}(x_{i})^{2}$ (7)

2\. Rosenbrock’s Function

$f_{2}(x)=\sum_{i=1}^{D-1}(100(x_{i}^{2}-x_{i+1})^{2}+(x_{i}-1)^{2})$ (8)

The first function is quite easy to solve and no need to discuss any detail
here. But the second function is a multimodal function. We put this
Rosenbrock’s function here in Group A because it is simple mutimodal function.
Most of the algorithms which solve Sphere function can also solve Rosenbrock’s
function.

Group B:Unrotated Multimodal Functions:

3\. Ackley’s Function

$\displaystyle
f_{3}(x)=-20exp\left(-0.2\sqrt{\frac{1}{D}\sum_{i=1}^{D}x_{i}^{2}}\right)$ (9)
$\displaystyle-exp\left(\frac{1}{D}\sum_{i=1}^{D}\cos(2\pi x_{i})\right)+20+e$

4\. Griewank’s Function

$\displaystyle
f_{4}(x)=\sum_{i=1}^{D}\frac{x_{i}^{2}}{4000}-\prod_{i=1}^{D}\cos\left(\frac{x_{i}}{\sqrt{i}}\right)+1$
(10)

5\. Weierstrass’s Function

$\displaystyle
f_{5}(x)=\sum_{i=1}^{D}\left(\sum_{k=0}^{max}\left[a^{k}\cos(2\pi
b^{k}(x_{i}+0.5))\right]\right)$ (11)
$\displaystyle-D\sum_{k=0}^{max}\left[a^{k}\cos(2\pi b^{k}.0.5)\right],$
$\displaystyle a=0.5,b=3,max=20.$

6\. Rastrigin’s Function

$\displaystyle f_{6}(x)=\sum_{i=1}^{D}\left(x_{i}^{2}-10\cos(2\pi
x_{i})+10\right)$ (12)

7\. Noncontinuous Rastrigin’s Function

$\displaystyle f_{7}(x)=\sum_{i=1}^{D}\left(y_{i}^{2}-10\cos(2\pi
y_{i})+10\right)$ (13) $\displaystyle
y_{i}=\begin{cases}x_{i},&|x_{i}|<\frac{1}{2}\\\
\frac{round(2x_{i})}{2},&|x_{i}|\geq\frac{1}{2}\\\ \text{for
i}=1,2,...D.\end{cases}$

8\. Schwefel’s Function

$\displaystyle f_{8}(x)=418.9829\times
D-\sum_{i=1}^{D}x_{i}\sin\left(|x_{i}|^{\frac{1}{2}}\right)$ (14)

In this six multimodal functions, Ackley’s function has many local optima and
one optimum basin. Griewank’s Function is more difficult problem in lower
dimension than higher. Weierstrass’s Function is continuous but also
differentiable on some set of points. Rastirgin function is one of the best
function because of high number of local optima, our algorithm is perfect for
this type of testing function. Noncontinuous Rastrigin’s Function contains
same number of local optima and it is a good candidate for our test purpose.
Another excellent function is Schwefel’s Function which has deep local optima
and far form global optima.

Group C: Rotated Multimodal Functions : For Rotation, we need an orthogonal
matrix M. To create orthogonal matrix we use Salomon’s method Sa19 . The
original variable x is left multiplied by M to get the new rotated variable y
= M * x. This y should be used to calculate fitness value f –

$M=\begin{bmatrix}m_{11}&m_{12}&...&m_{1D}\\\ m_{21}&m_{2}2&...&m_{2D}\\\
...&...&...&...\\\ m_{D1}&m_{D2}&...&m_{DD}\end{bmatrix}$ (15)

x = $\left[x_{1},x_{2},...,x_{D}\right]^{T}$ and y =
$\left[y_{1},y_{2},...,y_{D}\right]^{T}$ then

$\displaystyle y_{i}=m_{i1}x_{1}+m_{i2}x_{2}+...+m_{iD}x_{D},$ (16)
$\displaystyle i=1,2,...D.$

9\. Rotated Ackley’s function

$\displaystyle
f_{9}(x)=-20exp\left(-0.2\sqrt{\frac{1}{D}\sum_{i=1}^{D}y_{i}^{2}}\right)$
(17) $\displaystyle-exp\left(\frac{1}{D}\sum_{i=1}^{D}\cos(2\pi
y_{i})\right)+20+e,\textbf{y = M * x}$

10\. Rotated Griewank’s function

$\displaystyle
f_{10}(x)=\sum_{i=1}^{D}\frac{y_{i}^{2}}{4000}-\prod_{i=1}^{D}\cos\left(\frac{y_{i}}{\sqrt{i}}\right)+1,\textbf{y
= M * x}$ (18)

11.Rotated Weierstrass’s Function

$\displaystyle
f_{11}(x)=\sum_{i=1}^{D}\left(\sum_{k=0}^{max}\left[a^{k}\cos(2\pi
b^{k}(y_{i}+0.5))\right]\right)$ (19)
$\displaystyle-D\sum_{k=0}^{max}\left[a^{k}\cos(2\pi b^{k}.0.5)\right],$
$\displaystyle a=0.5,b=3,max=20,\textbf{y = M * x}$

12\. Rotated Rastrigin’s Function

$\displaystyle f_{12}(x)=\sum_{i=1}^{D}\left(y_{i}^{2}-10\cos(2\pi
y_{i})+10\right),\textbf{y = M * x}$ (20)

13\. Rotated Noncontinuous Rastrigin’s Function

$\displaystyle f_{13}(x)=\sum_{i=1}^{D}\left(z_{i}^{2}-10\cos(2\pi
z_{i})+10\right)$ (21) $\displaystyle
z_{i}=\begin{cases}y_{i},&|y_{i}|<\frac{1}{2}\\\
\frac{round(2y_{i})}{2},&|y_{i}|\geq\frac{1}{2}\\\ \text{for
i}=1,2,...D.,\textbf{y = M * x}\end{cases}$

14\. Rotated Schwefel’s Function

$\displaystyle f_{14}(x)=418.9829\times D-\sum_{i=1}^{D}z_{i}$ (22)
$\displaystyle
z_{i}=\begin{cases}y_{i}\sin\left(|y_{i}|^{\frac{1}{2}}\right),&|y_{i}|\text{if}\leq
500\\\ 0.001\left(|y_{i}|-500\right)^{2},&|y_{i}|>500\\\ \text{for
i}=1,2,...D.,\textbf{y = M * x}\\\ \end{cases}$

y = y’ + 420.96, y’ = M * (x - 420.96)

As we know Rotated Schwefel’s Function has better results in the search range
$[-500,500]^{D}$, so $z_{i}$ set in portion to the square distance between
$y_{i}$ and the bound.

Group D: MMO function: We choose three Multimodal Multiobjective Optimization
functions from CEC19 Ji19 . We can choose other functions from latest CEC,
like CEC2021 or CEC2022, but CEC19 gives us those functions which will be best
tested for our algorithm. Multimodal multi-objective functions may have more
than one Pareto Optimal Sets(PSs) corresponding to the same Pareto Front(PF).
Entire test suit contains test problems with different characters such as
problems with different shape of PSs and PFs, coexistence of local and global
PSs, scalable number of PSs, decision variables and objectives. For our
test,MMF1, MMF7 and MMF11 is chosen Ji19 .

1\. MMF1 : This is Convex, Non-Liner function containing Pareto Optimal Front
and a scalable number of Pareto sets.

$\displaystyle f_{15}(x)=\begin{cases}f_{15}^{1}=|x_{1}-2|\\\
f_{15}^{2}=1-\sqrt{|x_{1}-2|}+2(x_{2}-\sin(6\pi|x_{1}-2|\\\ +\pi))^{2}\\\
\end{cases}$ (23)

Its search space is - $x_{1}\in[1,3],x_{2}\in[-1,1]$.
Its global PSs are -

$\displaystyle\text{PS's are :}\begin{cases}x_{1}=x_{1}\\\
x_{2}=\sin(6\pi|x_{1}-2|+\pi)\end{cases}$

where $1\leq x_{1}\leq 3$,
Its global PFs are –

$\displaystyle\text{PF's are :}f_{2}=1-\sqrt{f_{1}}$

where $0\leq f_{1}\leq 1$.

2\. MMF7 : This is Convex, Non-Liner function containing Pareto Optimal Front
but no pareto sets.

$\displaystyle f_{16}(x)=\begin{cases}f_{16}^{1}=|x_{1}-2|\\\
f_{16}^{2}=1-\sqrt{|x_{1}-2|}+\\{x_{2}-[0.3|x_{2}-2|^{2}\cdot\\\
\cos(24\pi|x_{1}-2|+4\pi)+0.6|x_{1}-2|]\cdot\\\
\sin(6\pi|x_{1}-2|+\pi)\\}^{2}\\\ \end{cases}$ (24)

Its search space is - $x_{1}\in[1,3],x_{2}\in[-1,1]$.
Its global PSs are -

$\displaystyle\text{PS's are :}\begin{cases}x_{1}=x_{1}\\\
x_{2}=[0.3|x_{2}-2|^{2}\cdot\\\
\cos(24\pi|x_{1}-2|+4\pi)+0.6|x_{1}-2|]\cdot\\\
\sin(6\pi|x_{1}-2|+\pi)\end{cases}$

where $1\leq x_{1}\leq 3$.
Its global PFs are –

$\displaystyle\text{PF's are :}f_{2}=1-\sqrt{f_{1}}$

where $0\leq f_{1}\leq 1$.

3\. MMF11 : This is Convex, Liner function containing Pareto Optimal Front,
scalable pareto sets and also coexistence of global and local pareto sets.

$\displaystyle f_{17}(x)=Min\begin{cases}f_{17}^{1}=x\\\
f_{17}^{2}=\frac{g(x_{2})}{x_{1}}\end{cases}$ (25)

Where,

$\displaystyle
g(x)=2-exp\left[-2log(2)\cdot\left(\frac{x-0.1}{0.8}\right)^{2}\right]\cdot\sin^{6}(n_{p}\pi
x)$

where $n_{p}$ is total number of global and local PSs.
Its search space is - $x_{1}\in[0.1,1.1],x_{2}\in[0.1,1.1]$.
Its global PSs are -

$x_{2}=\frac{1}{2n_{p}},x_{1}\in[0.1,1.1].$

its $i^{th}$ local PS is –

$x_{2}=\frac{1}{2n_{p}}+\frac{1}{n_{p}}\cdot(i-1),x_{1}\in[0.1,1.1].$

Where, i = 1,2,3,…,$n_{p}$.
its global PF is –

$f_{17}^{2}=\frac{g\left(\frac{1}{2n_{p}}\right)}{f_{1}},f_{1}\in[0.1,1.1].$

Its local PF is –

$f_{17}^{2}=\frac{g\left(\frac{1}{2n_{p}}+\frac{1}{n_{p}}\cdot(i-1)\right)}{f_{1}},f_{1}\in[0.1,1.1].$

Where, i = 1,2,3,…,$n_{p}$.

###  5.3 Parameter Settings for the involved PSO and other algorithms

We will perform experiment on five state-of-the-art algorithms and compare
their performance with our proposed algorithm. Among the five algorithms,
three are particle swarm optimization algorithm which are combined with
novelty search NSBur20 ,NdPSOGal15  and other one is PSONovEUl21  and two
algorithms are CLPSO and ECLPSO algorithm Xi14 ,Jj06  respectively which are
different hybrid PSO methods best known for their high performance in
multimodal test functions. The algorithms and their parameter settings are
listed below –

  1. 1.

Novelty Swarm (NS) Bur20

  2. 2.

Novelty Driven PSO (NdPSO) Gal15

  3. 3.

Novelty Search in PSO (PSONovE) Ul21

  4. 4.

Comprehensive Learning PSO(CLPSO) Ji19

  5. 5.

Extended Comprehensive Learning PSO(ECLPSO) Xi14

  6. 6.

Novelty Search PSO (NsPSO)

We did not find too many algorithms where novelty search and PSO is combined.
The NS, NDPSO and PSONovE methods are among them. So we choose them as the
competitor algorithms. and CLPSO and ECLPSO are the best so far algorithms on
multi modal multi objective environment. In our experiment we perform
sequential implementation. How the system will behave when parallel run will
be implemented will be another interesting observation. Here in serial
implementation, First leader particle perform its Novelty calculation, updates
NS_archive table. Then second leader particle and then third, so on.

Table 2 lists down global optima, search ranges and initialization range for
the test functions.

Table 2: Global Optima, Search Range and Initialization Range of 17 Benchmark Functions. Functions Number | x* | f(x*) | Search Range | Initialization Range
---|---|---|---|---
$f_{1}$ | ${0}^{D}$ | 0 | $[-100,100]^{D}$ | $[-100,50]^{D}$
$f_{2}$ | ${1}^{D}$ | 0 | $[-2.048,2.048]^{D}$ | $[-2.048,2.048]^{D}$
$f_{3}$ | ${0}^{D}$ | 0 | $[-32.768,32.768]^{D}$ | $[-32.768,16]^{D}$
$f_{4}$ | ${0}^{D}$ | 0 | $[-600,600]^{D}$ | $[600,200]^{D}$
$f_{5}$ | ${0}^{D}$ | 0 | $[-0.5,0.5]^{D}$ | $[-0.5,0.2]^{D}$
$f_{6}$ | ${0}^{D}$ | 0 | $[-5.12,5.12]^{D}$ | $[-5.12,2]^{D}$
$f_{7}$ | ${0}^{D}$ | 0 | $[-5.12,5.12]^{D}$ | $[-5.12,2]^{D}$
$f_{8}$ | ${420.96}^{D}$ | 0 | $[-500,500]^{D}$ | $[-500,500]^{D}$
$f_{9}$ | ${0}^{D}$ | 0 | $[-32.768,32.768]^{D}$ | $[-32.768,16]^{D}$
$f_{10}$ | ${0}^{D}$ | 0 | $[-600,600]^{D}$ | $[600,200]^{D}$
$f_{11}$ | ${0}^{D}$ | 0 | $[-0.5,0.5]^{D}$ | $[-0.5,0.2]^{D}$
$f_{12}$ | ${0}^{D}$ | 0 | $[-5.12,5.12]^{D}$ | $[-5.12,2]^{D}$
$f_{13}$ | ${0}^{D}$ | 0 | $[-5.12,5.12]^{D}$ | $[-5.12,2]^{D}$
$f_{14}$ | ${420.96}^{D}$ | 0 | $[-500,500]^{D}$ | $[-500,500]^{D}$
$f_{15}$ | $[0,0]^{D}$ | [0,0] | $[1,3]^{D},[-1,1]^{D}$ | $[-100,100]^{D}$
$f_{16}$ | $[0,0]^{D}$ | [0,0] | $[1,3]^{D},[-1,1]^{D}$ | $[-100,100]^{D}$
$f_{17}$ | $[0,1]^{D}$ | [0,1] | $[0.1,1.1]^{D},[0.1,1.1]^{D}$ | $[-10,10]^{D}$

###  5.4 Experimental Results and Discussions

####  5.4.1 Result for the 10-D Problems

Table - 3 represents mean and variances of 25 runs of the five algorithms on
seventeen test functions with D value is 10. Best results are shown in bold.
We also conducted nonparametric Wilcoxon rank test to show that our NsPSO’s
result is statistically different from other algorithms. There is a h-value in
the table which indicates the result of t-tests. The h =1 refers the
performance of two algorithms are statistically different with 95% certainty.
The h = 0 means performance of two algorithms are not different.

Table 3: Comparative results for the 10 dimensional problems. Algorithms | Group A | Group A | Group B | Group B
---|---|---|---|---
functions $-->$ | $f_{1}$ | $f_{2}$ | $f_{3}$ | $f_{4}$
CLPSO | 5.15e-029 $\pm$ 2.16e-028 | 2.46e+000 $\pm$ 1.70e+000 | 4.32e-014 $\pm$ 2.5e-01402 | 4.56e-003 $\pm$ 4.81e-003
ECLPSO | 1.00e-97 $\pm$ 3.10e-96 | 2.70e+000 $\pm$ 1.50e+000 | 3.55e-015 $\pm$ 0 | 0 $\pm$ 0
NdPSO | 9.32e-010 $\pm$ 5.12e-018 | 6.46e+000 $\pm$ 4.25e+000 | 7.32e-004 $\pm$ 4.5e-012 | 5.56e-001 $\pm$ 2.21e-001
NS | 8.17e-012 $\pm$ 2.16e-022 | 8.21e+000 $\pm$ 7.25e+000 | 7.23e-002 $\pm$ 6.5e-022 | 4.56e-001 $\pm$ 3.82e-001
PSONovE | 1.87e-052 $\pm$ 1.26e-032 | 2.21e+000 $\pm$ 1.85e+000 | 6.53e-012 $\pm$ 3.1e-024 | 2.56e-021 $\pm$1.27e-001
NsPSO | 1.27e-089 $\pm$ 1.64e-053 | 3.33e+000 $\pm$ 1.78e+000 | 1.93e-022 $\pm$ 0 | 0 $\pm$ 0
h | 1 | 1 | 1 | 0
Algorithms | Group B | Group B | Group B | Group B
functions $-->$ | $f_{5}$ | $f_{6}$ | $f_{7}$ | $f_{8}$
CLPSO | 0 $\pm$ 0 | 0 $\pm$ 0 | 0 $\pm$ 0 | 0 $\pm$ 0
ECLPSO | 0 $\pm$ 0 | 0 $\pm$ 0 | 0 $\pm$ 0 | 0 $\pm$ 0
NdPSO | 2.25e-021 $\pm$ 1.28e-031 | 4.36e-022 $\pm$ 2.25e-34 | 2.22e-024 $\pm$ 1.5e-22 | 2.36e-031 $\pm$ 3.31e-051
NS | 1.95e-011 $\pm$ 0.98e-051 | 1.21e+20 $\pm$ 1.14e+000 | 2.23e-022 $\pm$ 4.5e-072 | 2.26e-021 $\pm$ 4.52e-061
PSONovE | 0.25e-021 $\pm$ 0.38e-067 | 1.41e+000 $\pm$ 1.15e+000 | 1.53e-065 $\pm$ 1.12e-024 | 1.56e-041 $\pm$1.87e-021
NsPSO | 0 $\pm$ 0 | 0.13e-20 $\pm$ 1.78e+000 | 0 $\pm$ 0 | 0 $\pm$ 0
h | 0 | 0 | 0 | 0
Algorithms | Group C | Group C | Group C | Group C
functions $-->$ | $f_{9}$ | $f_{10}$ | $f_{11}$ | $f_{12}$
CLPSO | 3.65e-005 $\pm$ 1.57e-004 | 4.50e-002 $\pm$ 3.08e-002 | 3.72e-010 $\pm$ 4.40e-010 | 5.97e+000 $\pm$ 2.88e+000
ECLPSO | 3.55e-15 $\pm$ 0 | 2.22e-17 $\pm$ 4.53e-17 | 3.25e-025 $\pm$ 4.13e-20 | 2.27e+000 $\pm$ 4.47e+000
NdPSO | 5.65e-017 $\pm$ 4.28e-011 | 2.46e-10 $\pm$ 4.25e-12 | 7.22e-024 $\pm$ 9.2e-022 | 7.57e-031 $\pm$ 9.22e-021
NS | 6.95e-001 $\pm$ 529e-05 | 8.21e-25 $\pm$ 9.25e-053 | 7.75e-032 $\pm$ 7.89e-032 | 4.26e-031 $\pm$ 6.86e-041
PSONovE | 2.65e-027 $\pm$ 2.38e-014 | 4.41e-55 $\pm$ 3.85e-30 | 2.23e-052 $\pm$ 3.5e-064 | 7.57e-071 $\pm$9.87e-08
NsPSO | 1.37e-025 $\pm$ 0 | 1.13e-022 $\pm$ 1.28e-20 | 1.13e-023 $\pm$ 1.20e-13 | 3.15e+000 $\pm$ 5.3e+000
h | 1 | 1 | 1 | 1
Algorithms | Group C | Group C | Group D | Group D
functions $-->$ | $f_{13}$ | $f_{14}$ | $f_{15}$ | $f_{16}$
CLPSO | 5.44e+000 $\pm$ 1.39e+000 | 1.14e+002 $\pm$ 1.28e+002 | 1.22e-012 $\pm$ 2.3e-011 | 2.56e+000 $\pm$ 4.82e+000
ECLPSO | 2.01e+000 $\pm$ 3.78e+000 | 1.06e+003 $\pm$ 1.44e+002 | 0.25e-025 $\pm$ 0 | 1.89e+000 $\pm$ 1.26e+000
NdPSO | 4.25e+021 $\pm$ 5.28e+033 | 6.26e+002 $\pm$ 8.25e+002 | 7.22e-002 $\pm$ 4.3e-082 | 5.26e+001 $\pm$ 4.21e+001
NS | 6.25e+011 $\pm$ 4.82e+21 | 3.21e+002 $\pm$ 5.26e+06 | 6.273e-002 $\pm$ 8.2e-075 | 4.99e+001 $\pm$ 3.32e+001
PSONovE | 5.55e+051 $\pm$ 7.38e+027 | 2.88e+004 $\pm$ 1.35e+003 | 6.86e-011 $\pm$ 4.1e-034 | 2.88e+001 $\pm$5.77e+001
NsPSO | 1.16e+000 $\pm$ 4.72e+000 | 3.13e+000 $\pm$ 1.38e+001 | 0 $\pm$ 0 | 1.11e+000 $\pm$ 0.89e+000
h | 1 | 1 | 1 | 1
Algorithms | Group D |
functions $-->$ | $f_{17}$ |
CLPSO | 4.23e-023 $\pm$ 6.89e-45 |
ECLPSO | 1.26e-24 $\pm$ 2.4e-42 |
NdPSO | 11.25e-021 $\pm$ 13.22e-031 |
NS | 9.95e-011 $\pm$ 11.78e-051 |
PSONovE | 10.25e-051 $\pm$ 9.66e-027 |
NsPSO | 1.19e-027 $\pm$ 0.72e-20 |
h | 1 |

As we observe the Table -(3), we clearly understand for Group A unimodal
functions our NsPSO failed to provide best results. But certainly its comes
second and third respectively in comparison with so far best multimodal PSO
algorithms like CLPSO or ECLPSO. NsPSO outperform existing other Novelty
Search plus PSO hybrid algorithms. Our algorithm is designed for more robust
and with more exlorative power. Though the Rosenbrock’s function is multimodal
but due to novelty search our algorithm perform more exploration. Later we can
improve by tuning parameters of novelty search such that it can perform much
better on other unimodal functions.

For unrotated multimodal functions in Group B other than Rastrigin function
our algorithm provide best results. Due to vast search region and more local
optima novelty search provide better exploration than other algorithms. The
h-value is 0 whenever NsPSO achieves same results as other algorithms. In case
of function $f_{5}$, though our algorithms beats other Novelty search PSO
versions but it fails to converge into global optima.

In case of rotated multimodal functions in Group C, other than rotated
rastrigin function, NsPSO outperforms all algorithms. Rotation makes problems
more difficult but instead of that difficulty NsPSO shows quite promising
performance in case of large local optima and global optima is far away. The
more diverse the search region is, NsPSO will perform better than existing
algorithms.

Again for more difficult valley in MMO problems in Group D, NsPSO perform
best. Here, one thing to observe we use very low number of PSO particles,
NdPSO or NS or PSONovE algorithms uses higher values. And sometimes if we
increase number of Leader particles NsPSO gives even better results, but as it
is stochastic algorithm we keep mean and standard deviation values of 25 runs.
It indicates that better tuning of the parameters of NsPSO will give better
performance.

####  5.4.2 Result for the 30-D Problems

Same experiment is also done on 30 dimensional problems and their results are
shown in Table - (4). In the case of Unimodal functions CLPSO beats everyone.
NsPSO shows good performance and highest among other novelty search based PSO
methods. If we increase the number of iteration then there is a high chances
that NsPSO beats everyone.

When dimension increases complexity of the problems simultaneously increases.
But NsPSO still be high performing and far better then other PSO methods.As we
can see in some cases like function $f_{6}$ it fails to be the best yet it
keeps it top performance.

In Group C rotated multimodal functions, NsPSO shows remarkable results. In
case of Rotated Rastrigin function NsPSO doesn’t show good performance similar
to D=10 case. Also in case of Rotated Schwefel’s function CLPSO shows better
performance. Rotated Schwefel’s function is complex function, though our
algorithm unable to beat CLPSO; but it shows competitive results in terms of
other algorithms.

In one of the multimodal multiobjective function $f_{16}$ where there is no
pareto sets and global optima is far away, our algorithm performs well in
D=10, but fails to achieve best performance in D=30.

Comparing the performance of all the algorithms, we can see that ECLPSO and
NsPSO performing far better than other hybrid PSO algorithms specially in
multimodal complex situation where there are more valleys and global optima is
distributed throughout search space.

####  5.4.3 Discussion

According to our experiment and analyzing the results of NsPSO, we can
conclude that for unimodal problems our algorithm does not perform best. But
we need to keep in mind that novelty search is divergence algorithm. Purpose
of augmenting novelty search with PSO is to help PSO roam around entire search
space, not to stuck in local valley or falls into the trap false convergence.
Multimodal functions and multiodal multiobjective functions hold lot more
difficult region in terms of false local valley , far away global optima and
high number of local optima. NsPSO successfully overcome this and shows
promising performance in 30 dimension as well as 10 dimension problems. NsPSO
is certinly not solve-all solution rather its focus is mainly multimodal-
multiobhetive domain. During Novel area search, we use Low-novel
category(Table - 1) for search. We categorized novelty for this purpose, NsPSO
started from Highly-novel region and keep on continue its search until it
finds Low-novel. We use Bare-Bone PSO for its simplicity though it is an old
method. We can use other top performing stand alone PSO method but the
computational cost will increase and may impose significant impact in the
performance. Thus other PSO might be an interesting avenue to follow.

Table 4: Comparative results for the 30 dimensional problems. Algorithms | Group A | Group A | Group B | Group B
---|---|---|---|---
functions $-->$ | $f_{1}$ | $f_{2}$ | $f_{3}$ | $f_{4}$
CLPSO | 4.46e-014 $\pm$ 1.73e-014 | 2.46e+000 $\pm$ 1.70e+000 | 0 $\pm$ 0 | 3.146e-010 $\pm$ 4.64e-010
ECLPSO | 2.02e-92 $\pm$ 1.22e-96 | 2.12e+000 $\pm$ 3.18e+000 | 0 $\pm$ 0 | 3.19e-010 $\pm$ 2.24e-010
NdPSO | 9.27e-012 $\pm$ 3.12e-012 | 7.42e+000 $\pm$ 4.25e+000 | 7.22e-20 $\pm$ 5.5e-022 | 2.56e-001 $\pm$ 5.22e-001
NS | 2.13e-016 $\pm$ 4.16e-023 | 8.31e+002 $\pm$ 4.25e+002 | 6.23e-052 $\pm$ 4.5e-012 | 2.56e-03 $\pm$ 3.42e-002
PSONovE | 4.27e-032 $\pm$ 6.86e-031 | 5.21e+002 $\pm$ 2.85e+001 | 6.78e-022 $\pm$ 3.1e-02 | 2.66e-011 $\pm$1.27e-001
NsPSO | 2.87e-019 $\pm$ 2.54e-023 | 3.31e+000 $\pm$ 4.28e+000 | 0 $\pm$ 0 | 2.2e-015 $\pm$ 3.18e-012
h | 1 | 1 | 0 | 1
Algorithms | Group B | Group B | Group B | Group B
functions $-->$ | $f_{5}$ | $f_{6}$ | $f_{7}$ | $f_{8}$
CLPSO | 3.45e-007 $\pm$ 1.94e-007 | 4.85e-010 $\pm$ 3.63e-010 | 4.36e-010 $\pm$ 2.44e-010 | 2.27e-012 $\pm$ 8.79e-13
ECLPSO | 4.33e-007 $\pm$ 1.89e-007 | 1.98e-011 $\pm$ 2.78e-10 | 4.34e-10 $\pm$ 1.22e-010 | 1.11e-012 $\pm$ 3.89e-13
NdPSO | 8.25e-011 $\pm$ 5.28e-011 | 6.36e-012 $\pm$ 4.25e-10 | 6.62e-014 $\pm$ 2.5e-12 | 3.33e-011 $\pm$ 4.31e-011
NS | 6.95e-011 $\pm$ 5.58e-051 | 6.21e-10 $\pm$ 4.14e-000 | 4.23e-012 $\pm$ 4.5e-012 | 4.26e-011 $\pm$ 6.32e-011
PSONovE | 7.15e-011 $\pm$ 6.28e-017 | 4.41e-012 $\pm$ 3.65e-012 | 7.53e-015 $\pm$ 4.12e-014 | 4.56e-011 $\pm$4.27e-011
NsPSO | 1.78e-009 $\pm$ 2.89e-009 | 2.13e-12 $\pm$ 3.75e-010 | 3.12e-12 $\pm$ 4.72e-12 | 0.45e-012 $\pm$ 0.11e-10
h | 0 | 0 | 0 | 0
Algorithms | Group C | Group C | Group C | Group C
functions $-->$ | $f_{9}$ | $f_{10}$ | $f_{11}$ | $f_{12}$
CLPSO | 3.43e-004 $\pm$ 1.91e-004 | 7.04e-010 $\pm$ 1.25e-011 | 3.07e+000 $\pm$ 1.61e+000 | 3.56e+001 $\pm$ 4.59e+000
ECLPSO | 3.15e-04 $\pm$ 0.78e-004 | 5.22e-11 $\pm$ 1.23e-11 | 2.25e+000 $\pm$ 1.13e+000 | 1.27e+000 $\pm$ 4.24e+000
NdPSO | 5.25e-017 $\pm$ 7.29e-015 | 5.46e-10 $\pm$ 8.25e-12 | 7.67e+014 $\pm$ 9.32e+012 | 7.57e+011 $\pm$ 9.32e+011
NS | 6.35e-001 $\pm$ 5.56e-11 | 8.21e-15 $\pm$ 6.25e-013 | 6.75e+012 $\pm$ 7.19e+012 | 5.26e+011 $\pm$ 6.66e+011
PSONovE | 2.25e-017 $\pm$ 4.28e-016 | 4.61e-15 $\pm$ 5.15e-10 | 5.13e+012 $\pm$ 3.56e+014 | 7.17e+011 $\pm$1.87e+10
NsPSO | 2.14e-015 $\pm$ 1.14e-015 | 2.63e-012 $\pm$ 1.08e-11 | 1.43e+000 $\pm$ 1.0e+000 | 2.15e+020 $\pm$ 3.2e+020
h | 1 | 1 | 1 | 1
Algorithms | Group C | Group C | Group D | Group D
functions $-->$ | $f_{13}$ | $f_{14}$ | $f_{15}$ | $f_{16}$
CLPSO | 3.77e+001 $\pm$ 5.56e+000 | 1.70e+003 $\pm$ 1.86e+002 | 3.25e-011 $\pm$ 1.3e-010 | 5.56e+000 $\pm$ 4.2e+000
ECLPSO | 2.22e+001 $\pm$ 4.28e+001 | 2.61e+001 $\pm$ 2.42e+001 | 1.25e-015 $\pm$ 1.89e-015 | 1.19e+001 $\pm$ 3.46e+001
NdPSO | 5.65e+011 $\pm$ 7.27e+013 | 6.92e+013 $\pm$ 9.75e+013 | 3.82e-012 $\pm$ 4.2e-012 | 5.39e+001 $\pm$ 6.27e+001
NS | 6.89e+012 $\pm$ 5.22e+11 | 5.21e+012 $\pm$ 5.21e+012 | 6.214e-012 $\pm$ 8.7e-012 | 2.99e+002 $\pm$ 3.42e+002
PSONovE | 7.25e+011 $\pm$ 7.28e+011 | 3.82e+001 $\pm$ 5.32e+001 | 2.82e-011 $\pm$ 5.11e-011 | 3.82e+002 $\pm$4.77e+002
NsPSO | 2.72e+001 $\pm$ 4.28e+001 | 2.53e+000 $\pm$ 3.38e+002 | 1.02e-010 $\pm$ 3.82e-010 | 2.71e+001 $\pm$ 3.29e+001
h | 1 | 1 | 1 | 1
Algorithms | Group D |
functions $-->$ | $f_{17}$ |
CLPSO | 2.45e-013 $\pm$ 4.22e-13 |
ECLPSO | 1.56e-14 $\pm$ 3.4e-14 |
NdPSO | 10.25e-011 $\pm$ 11.22e-011 |
NS | 5.25e-011 $\pm$ 10.28e-011 |
PSONovE | 3.75e-011 $\pm$ 5.26e-011 |
NsPSO | 0.89e-012 $\pm$ 1.72e-12 |
h | 1 |

##  6 Conclusion

In this paper we propose a particle swarm optimization algorithm augmented
with novelty search. We devise a method where PSO can successfully search
entire area of the search region and never stuck in any local optima. The
benefit of this algorithm is for more complex functions where multiple local
and global optima exist and the solutions are highly distributed throughout
the search region. The present algorithm provides superior results.

Through our experiment we have seen that NsPSO may not perform well in all
kind of optimization problems. Though it is not designed to solve all problems
but its main focus to solve multi objective multi modal complex functions.

The present algorithm is robust and dynamic because it has two parts one
novelty search, which searches the novel area for searching and other is PSO
algorithm. Now if any one wishes to use PSO variants other than BBPSO the
present method will work successfully and provide superior results.

NsPSO shows high performance on fourteen functions out of seventeen. It shows
significant capability to search on complex domain and overcome the problem of
locally stuck in false region.

## References

  * (1) Kennedy, J. Eberhart, R,(1995).Particle Swarm Optimization._Proceedings of IEEE International Conference on Neural Networks_.1942–1948.
  * (2) Maurice Clerc.,(2011).Standard Particle Swarm Optimisation._hal-00764996¿_.
  * (3) Liang, JJ and Qu, BY and Suganthan, PN and Hernández-Díaz, Alfredo G.(2013).Problem definitions and evaluation criteria for the CEC 2013 special session on real-parameter optimization._Computational Intelligence Laboratory, Zhengzhou University, Zhengzhou, China and Nanyang Technological University, Singapore, Technical Report_.281–295.201212.34.
  * (4) Zambrano-Bigiarini, Mauricio and Clerc, Maurice and Rojas, Rodrigo.(2013).Standard particle swarm optimisation 2011 at cec-2013: A baseline for future pso improvements._2013 IEEE Congress on Evolutionary Computation_.2337–2344.IEEE
  * (5) Lehman, Joel and Stanley, Kenneth O.(2008).Exploiting open-endedness to solve problems through the search for novelty._ALIFE_.329–336.Citeseer.
  * (6) Lehman, Joel and Stanley, Kenneth O.(2010).Revising the evolutionary computation abstraction: minimal criteria novelty search._Proceedings of the 12th annual conference on Genetic and evolutionary computation_.103–110.
  * (7) Lehman, Joel and Stanley, Kenneth O.(2010).Efficiently evolving programs through the search for novelty._Proceedings of the 12th annual conference on Genetic and evolutionary computation_.837–844.
  * (8) Lehman, Joel and Stanley, Kenneth O.(2011).Novelty search and the problem with objectives._Genetic programming theory and practice IX_.37–56.Springer.
  * (9) Doncieux, Stephane and Laflaquière, Alban and Coninx, Alexandre.(2019).Novelty search: a theoretical perspective._Proceedings of the Genetic and Evolutionary Computation Conference_.99–106.Springer.
  * (10) Burgos-Simón, Clara and Cortés, Juan-Carlos and Hidalgo, José-Ignacio and Martınez-Rodrıguez, David and Villanueva, Rafael-J.(2020)Novelty Swarm, the Implementation of Novelty Search in the Particle Swarm Optimization Algorithm._Proceedings of the Genetic and Evolutionary Computation Conference_.99–106.Springer.
  * (11) Galvao, Diana F and Lehman, Joel and Urbano, Paulo.(2015)Novelty-driven particle swarm optimization._International Conference on Artificial Evolution (Evolution Artificielle)_.177–190.Springer.
  * (12) Kennedy, James.(2003)Bare bones particle swarms._Proceedings of the 2003 IEEE Swarm Intelligence Symposium. SIS’03 (Cat. No. 03EX706)_.80–87.IEEE.
  * (13) Pan, Feng and Hu, Xiaohui and Eberhart, Russ and Chen, Yaobin.(2008)An analysis of bare bones particle swarm._2008 IEEE Swarm Intelligence Symposium_.1–5.IEEE.
  * (14) Blackwell, Tim.(2011)A study of collapse in bare bones particle swarm optimization._IEEE Transactions on Evolutionary Computation_.16.354–372.IEEE.
  * (15) J. Lehman and K. O. Stanley.(2011) Abandoning Objectives: Evolution Through the Search for Novelty Alone._Evolutionary Computation_.19.189–223.doi: 10.1162/EVCO_a_00025.
  * (16) Ma Gang, Zhou Wei, Chang Xiaolin.(2012) A novel particle swarm optimization algorithm based on particle migration._Applied Mathematics and Computation_.218.6620-6626.ISSN 0096-3003.doi: 10.1016/j.amc.2011.12.032.
  * (17) Kashif Hussain, Mohd Najib Mohd Salleh.(2019) Metaheuristic research: a comprehensive survey._Artificial Intelligence Review_.52.2191–2233.https://doi.org/10.1007/s10462-017-9605-z.
  * (18) Iztok Fister, Andres Iglesias, Akemi Galvez, Javier Del Ser, Eneko Osaba, Iztok Fister, Matjaž Perc, Mitja Slavinec.(2019)Novelty search for global optimization._Applied Mathematics and Computation_.347.865-881.ISSN 0096-3003.https://doi.org/10.1016/j.amc.2018.11.052.
  * (19) Mouret JB, Doncieux S.(2012)Encouraging behavioral diversity in evolutionary robotics: an empirical study._Evolutionary Computation_.20(1).91-133.doi: 10.1162/EVCO_a_00048. Epub 2011 Dec 2. PMID: 21838553.
  * (20) Gomes, J., Urbano, P. Christensen, A.L.(2013)Evolution of swarm robotics systems with novelty search._Swarm Intelligence_.7.115–144 (2013).doi: https://doi.org/10.1007/s11721-013-0081-z.
  * (21) J. Gomes, P. Mariano, and A. L. Christensen.(2014)Avoiding convergence in cooperative coevolution with novelty search._International Conference on Autonomous Agents and Multiagent Systems (AAMAS)_.1149 - 1156.IFAAMAS.
  * (22) J. Lehman and K. O. Stanley.(2011).Evolving a diversity of virtual creatures through novelty search and local competition._Genetic and Evolutionary Computation Conference (GECCO)_.211-218.ACM Press.
  * (23) S. Risi, C. E. Hughes, and K. O. Stanley.(2010).Evolving plastic neural networks with novelty search.._Adaptive Behavior_.18(6).470-491.
  * (24) E. Naredo and L. Trujillo.(2013).Searching for novel clustering programs._Genetic and Evolutionary Computation Conference (GECCO)_.1093 - 1100.ACM Press.
  * (25) E. Naredo and L. Trujillo and and Y. Martiez.(2013).Searching for novel classifiers._Genetic Programming (EuroGP)_.volume 7831 of LNCS.145-156.Springer.
  * (26) A. Liapis, G. N. Yannakakis, and J. Togelius.(2014).Constrained novelty search: A study on game content generation._Evolutionary Computation_.
  * (27) A. Ulrich, A. Viktorin, M. Pluhacek, T. Kadavy and J. Krnavek.(2021).Novelty Search in Particle Swarm Optimization._IEEE Symposium Series on Computational Intelligence (SSCI)_.pp 1-8. doi: 10.1109/SSCI50451.2021.9660131.
  * (28) David Martínez-Rodríguez, Ricardo Novella, Gabriela Bracho, Josep Gomez-Soriano, Cassio Fernandes, Tommaso Lucchini, Augusto Della Torre, Rafael-J. Villanueva, J. Ignacio Hidalgo.(2023).A particle swarm optimization algorithm with novelty search for combustion systems with ultra-low emissions and minimum fuel consumption._Applied Soft Computing_.Vol-143.ISSN 1568-4946. doi:10.1016/j.asoc.2023.110401.
  * (29) Galvao, D.F., Lehman, J., Urbano, P.(2016).Novelty-Driven Particle Swarm Optimization._International Conference on Artificial Evolution (Evolution Artificielle)_.pp 177-190. doi: https://doi.org/10.1007/978-3-319-31471-6_14.
  * (30) Assimi, Hirad and Neumann, Frank and Wagner, Markus and Li, Xiaodong.(2021).Novelty particle swarm optimisation for truss optimisation problems._Association for Computing Machinery_.pp 67-68. doi: 10.1145/3449726.3459572.
  * (31) Clara Burgos Simón,Juan C. Cortés,Ignacio Hidalgo,David Martínez-Rodríguez and Rafael Jacinto Villanueva.(2020).Novelty Swarm, the Implementation of Novelty Search in the Particle Swarm Optimization Algorithm._preprint : Rafael Jacinto Villanueva’s Lab_.pp 541-555. doi.org/10.13140/RG.2.2.26660.01924.
  * (32) J.J.Liang,A.K.Qin,P.N.Suganthan,S.Baskar.(2006).Comprehensive Learning Particle Swarm Optimizer For Global Optimization of Multimodal Functions._IEEE Transactions on Evolutionary Computation_.Vol-10.
  * (33) Xiang Yu,Xueqing Zhang.(2014). Enhanced Comprehensive Learning Particle Swarm Optimization._Applied Mathematics and Computation_.pp-265-276,https://doi.org/10.1016/j.amc.2014.05.044.
  * (34) Xin Yao, Yong Liu and Guangming Lin.(1999). Evolutionary programming made faster._IEEE Transactions on Evolutionary Computation_.Vol-3,pp-82-102,doi: 10.1109/4235.771163.
  * (35) S. C. Esquivel and C. A. C. Coello.(2003). On the use of particle swarm optimization with multimodal functions._The 2003 Congress on Evolutionary Computation_.Vol-2,pp-1130-1136,doi: 10.1109/CEC.2003.1299795.
  * (36) Jing Liang B Y Qu D W Gong Cai Tong Yue.(2019). Problem Definitions and Evaluation Criteria for the CEC 2019 Special Session on Multimodal Multiobjective Optimization.Affiliation: Zhengzhou University. DOI: 10.13140/RG.2.2.33423.64164.
  * (37) Ralf Salomon.(1996). Re-evaluating genetic algorithm performance under coordinate rotation of benchmark functions. A survey of some theoretical and practical aspects of genetic algorithms.Affiliation: Biosystems. Vol -39,Issue 3, DOI: https://doi.org/10.1016/0303-2647(96)01621-8.
  * (38) A. Ulrich, A. Viktorin, M. Pluhacek, T. Kadavy and J. Krnavek.(2021). Novelty Search in Particle Swarm Optimization _IEEE Symposium Series on Computational Intelligence (SSCI)_. pp: 1-8.DOI: 10.1109/SSCI50451.2021.9660131..