Page 36 - Fister jr., Iztok, Andrej Brodnik, Matjaž Krnc and Iztok Fister (eds.). StuCoSReC. Proceedings of the 2019 6th Student Computer Science Research Conference. Koper: University of Primorska Press, 2019
P. 36
sible space, written mathematically as x ∈ Ω. In our ticle x i as follows:
case, the feasible space Ω is determined by the upper and
lower bounds of their corresponding problem variables. x i = xmax + xmin − xi. (4)
Classification is a process of labeling data based on some at- Opposition-based learning phase in OVCPSO consists of
tributes to the right type of information or to the right class. calculating opposite particles swarm X then creating an
Clustering is a process of searching for centers of groups so union between original and opposite swarm of particle as
called clusters that have very similar data instances. With X = X ∪ X . And the last step of opposition-based learn-
clustering, we can find cluster centers that can be used for ing phase is to select N best particles based on the fitness
classification. The K-means algorithm is one of the most values of particles in X that will present our new swarm
well known algorithms for clustering [9]. Unfortunately, it of particles. The OVCPSO algorithm has velocity clamping
has two major defects: (1) the number of clusters must be operator that repairs the velocity of particles if the velocity
known in advance, and (2) bad initial centers of clusters can exceeds some maximum velocity.
degrades the performance. Because of those defects, many
meta-heuristic algorithms have been used for clustering, like One of the the variations of PSO algorithm that we used
Big Bang–Big Crunch Algorithm (BBBCA) [8], Black Hole in our work is Mutated Centered Unified Particle Swam
(BH) [7], Gravitational Search Algorithm (GSA) [6], and Optimization (MCUPSO) algorithm described in [20]. The
many others. MCUPSO algorithm uses two additional operators that are
centering and mutation. Centering operator was described
The rest of the paper is organized as follows: In Section 2 in the CPSO algorithm [12] and mutation operator was de-
PSO algorithms used in our work are presented. Section 3 fined in Mutated Particle Swarm Optimization (MPSO) al-
defines the clustering problem and presents some fitness gorithm [17]. Both operators are executed at the end of the
function suitable for clustering with PSO algorithms. Sec- algorithm generation. The MCUPSO algorithm has a new
tion 4 shows the results of two experiments: The former equation for velocity updating defined as:
based on usage of various fitness functions, while the lat-
ter compares different algorithms for classification based on vi(t+1) = ω(t+1) × vi(t) ⊗ r3 (5)
clustering. Finally, in Section 5, we conclude our paper with + c1 × r1 ⊗ xp(tb),i − xi(t)
summarizing the performed work and provide some direc-
tions for feature work. + c2 × r2 ⊗ x(gtb) − xi(t) ⊗ (1 − r3) ,
2. PARTICLE SWARM OPTIMIZATION where r3 is a D component vector with uniform random
numbers ∈ [0, 1].
PSO is an optimization algorithm for solving problems which
solutions variables are elements of R. The basic PSO algo- Because of the bad performance of the PSO algorithm on
rithm was presented by Kennedy and Eberhart in 1995 [10]. multi-modal OPs, authors in [11] developed a PSO algo-
Individual in PSO algorithms is presented as a particle that rithm called Comprehensive Learning Particle Swarm Op-
has current position, personal best position and velocity. In timizer (CLPSO) algorithm which overcomes this problem.
each generation the PSO algorithm goes over the whole pop- The CLPSO algorithm uses the basic PSO algorithm with
ulation and for each particle first updates it’s velocity based additional comprehensive learning phase, where comprehen-
on the following expression: sive learning phase uses all personal best positions for up-
dating particles velocity. Particle velocity is update based
vi(t+1) = ω(t+1) × vi(t) + c1 × r1 ⊗ xp(tb),i − x(it) on:
+ c2 × r2 ⊗ x(gtb) − x(it) ,
(2) vi(t+1) = ω(t+1) × vi(t) + c × r ⊗ z − xi(t) , (6)
where ⊗ represents element wise multiplication, r1 and r2 where c is user defined value, r is randomly uniform dis-
tributed vector with number of components equal to num-
have uniform random distributed values with D components ber of components in the solution and z is vector that is
∈ [0, 1], ω(t+1) is an inertia weight, vi(t) is a vector represent- composed from different personal best positions.
ing i-th particle velocity at time t and vi(t+1) represents new
velocity for particle i. Factors c1 and c2 represent social and In our implementation, we added solution repairing opera-
tor that is executed after the position of particle in updated.
cognitive learning rates respectively. After the velocity up- Solution repairing is done based on mirroring back the com-
ponents of the solution that are out of the allowed search
dating is done, the updating of particle position takes place space back into the search space. Mirroring of bad compo-
nents is based on modulo operation.
as follows:
xi(t+1) = x(it) + vi(t+1) . (3)
After particle updates its position, the personal best po- 3. CLUSTERING OPTIMIZATION
sition, and the global best positions are update based on
fitness value. Clustering is one of the most important data analysis tech-
niques that involves analysis of multivariate data. It is a
Opposition-base learning and velocity clamping are two fun- method of unsupervised machine learning for pattern recog-
damental phases of Opposition-Based Particle Swarm Opti- nition, data mining, supervised machine learning, image anal-
mization with Velocity Clamping algorithm (OVCPSO) de- ysis, bioinformatics, prediction, etc. Result of clustering
fined in [16]. In the OVCPSO algorithm, opposition-based optimization is centers of clusters, where instances of one
learning phase [19] is used for calculating the opposite par- cluster have maximum similarity between each other and
StuCoSReC Proceedings of the 2019 6th Student Computer Science Research Conference 36
Koper, Slovenia, 10 October
case, the feasible space Ω is determined by the upper and
lower bounds of their corresponding problem variables. x i = xmax + xmin − xi. (4)
Classification is a process of labeling data based on some at- Opposition-based learning phase in OVCPSO consists of
tributes to the right type of information or to the right class. calculating opposite particles swarm X then creating an
Clustering is a process of searching for centers of groups so union between original and opposite swarm of particle as
called clusters that have very similar data instances. With X = X ∪ X . And the last step of opposition-based learn-
clustering, we can find cluster centers that can be used for ing phase is to select N best particles based on the fitness
classification. The K-means algorithm is one of the most values of particles in X that will present our new swarm
well known algorithms for clustering [9]. Unfortunately, it of particles. The OVCPSO algorithm has velocity clamping
has two major defects: (1) the number of clusters must be operator that repairs the velocity of particles if the velocity
known in advance, and (2) bad initial centers of clusters can exceeds some maximum velocity.
degrades the performance. Because of those defects, many
meta-heuristic algorithms have been used for clustering, like One of the the variations of PSO algorithm that we used
Big Bang–Big Crunch Algorithm (BBBCA) [8], Black Hole in our work is Mutated Centered Unified Particle Swam
(BH) [7], Gravitational Search Algorithm (GSA) [6], and Optimization (MCUPSO) algorithm described in [20]. The
many others. MCUPSO algorithm uses two additional operators that are
centering and mutation. Centering operator was described
The rest of the paper is organized as follows: In Section 2 in the CPSO algorithm [12] and mutation operator was de-
PSO algorithms used in our work are presented. Section 3 fined in Mutated Particle Swarm Optimization (MPSO) al-
defines the clustering problem and presents some fitness gorithm [17]. Both operators are executed at the end of the
function suitable for clustering with PSO algorithms. Sec- algorithm generation. The MCUPSO algorithm has a new
tion 4 shows the results of two experiments: The former equation for velocity updating defined as:
based on usage of various fitness functions, while the lat-
ter compares different algorithms for classification based on vi(t+1) = ω(t+1) × vi(t) ⊗ r3 (5)
clustering. Finally, in Section 5, we conclude our paper with + c1 × r1 ⊗ xp(tb),i − xi(t)
summarizing the performed work and provide some direc-
tions for feature work. + c2 × r2 ⊗ x(gtb) − xi(t) ⊗ (1 − r3) ,
2. PARTICLE SWARM OPTIMIZATION where r3 is a D component vector with uniform random
numbers ∈ [0, 1].
PSO is an optimization algorithm for solving problems which
solutions variables are elements of R. The basic PSO algo- Because of the bad performance of the PSO algorithm on
rithm was presented by Kennedy and Eberhart in 1995 [10]. multi-modal OPs, authors in [11] developed a PSO algo-
Individual in PSO algorithms is presented as a particle that rithm called Comprehensive Learning Particle Swarm Op-
has current position, personal best position and velocity. In timizer (CLPSO) algorithm which overcomes this problem.
each generation the PSO algorithm goes over the whole pop- The CLPSO algorithm uses the basic PSO algorithm with
ulation and for each particle first updates it’s velocity based additional comprehensive learning phase, where comprehen-
on the following expression: sive learning phase uses all personal best positions for up-
dating particles velocity. Particle velocity is update based
vi(t+1) = ω(t+1) × vi(t) + c1 × r1 ⊗ xp(tb),i − x(it) on:
+ c2 × r2 ⊗ x(gtb) − x(it) ,
(2) vi(t+1) = ω(t+1) × vi(t) + c × r ⊗ z − xi(t) , (6)
where ⊗ represents element wise multiplication, r1 and r2 where c is user defined value, r is randomly uniform dis-
tributed vector with number of components equal to num-
have uniform random distributed values with D components ber of components in the solution and z is vector that is
∈ [0, 1], ω(t+1) is an inertia weight, vi(t) is a vector represent- composed from different personal best positions.
ing i-th particle velocity at time t and vi(t+1) represents new
velocity for particle i. Factors c1 and c2 represent social and In our implementation, we added solution repairing opera-
tor that is executed after the position of particle in updated.
cognitive learning rates respectively. After the velocity up- Solution repairing is done based on mirroring back the com-
ponents of the solution that are out of the allowed search
dating is done, the updating of particle position takes place space back into the search space. Mirroring of bad compo-
nents is based on modulo operation.
as follows:
xi(t+1) = x(it) + vi(t+1) . (3)
After particle updates its position, the personal best po- 3. CLUSTERING OPTIMIZATION
sition, and the global best positions are update based on
fitness value. Clustering is one of the most important data analysis tech-
niques that involves analysis of multivariate data. It is a
Opposition-base learning and velocity clamping are two fun- method of unsupervised machine learning for pattern recog-
damental phases of Opposition-Based Particle Swarm Opti- nition, data mining, supervised machine learning, image anal-
mization with Velocity Clamping algorithm (OVCPSO) de- ysis, bioinformatics, prediction, etc. Result of clustering
fined in [16]. In the OVCPSO algorithm, opposition-based optimization is centers of clusters, where instances of one
learning phase [19] is used for calculating the opposite par- cluster have maximum similarity between each other and
StuCoSReC Proceedings of the 2019 6th Student Computer Science Research Conference 36
Koper, Slovenia, 10 October
