2017 RISP International Workshop on Nonlinear Circuits,Communications and Signal Processing (NCSP'17)
Guam, USA, February 28th to March 3rd, 2017

K-means Algorithm using Improved Fireﬂy Algorithm
Masaki Takeuchi1 , Thomas Ott2 , Haruna Matsushita3 , Yoko Uwate1 and Yoshifumi Nishio1
1 : Department of Electrical and Electronic Engineering, Tokushima University
2-1 Minami-Josanjima, Tokushima, 770–8506, Japan
E-mail: {masaki, uwate, nishio}@ee.tokushima-u.ac.jp
2 : Zurich University of Applied Sciences
Einsiedlerstrasse 31a, 8820 Waedenswil, Switzerland
E-mail: thomas.ott@zhaw.ch3 : Department of Electronics and Information Engineering, Kagawa University
2217-20 Hayashi-cho, Takamatsu, Kagawa, 761-0396, Japan
E-mail: haruna@eng.kagawa-u.ac.jp

Abstract
In 2011, K-means algorithm combined Fireﬂy Algorithm has
been proposed by Mr. Senthilnath. This clustering algorithm
has obtained better results than K-means algorithm and theother algorithms combined bio-inspired algorithm. In thisstudy, we propose a new clustering algorithm; K-means algorithm combined improved Fireﬂy Algorithm. One parameterof our proposed algorithm is changed when the assignment
does not change. We compare K-means algorithm, K-means
algorithm combined Fireﬂy Algorithm and our proposed algorithm using simple model. Numerical experiments show
our proposed algorithm is more efﬁcient algorithm than theother algorithms.
1. Introduction
A clustering is a popular data analysis technique and isused for data analysis, image analysis, data mining and theother ﬁelds of science and engineering. The goal of clustering is to ﬁnd homogeneous groups of data points in a data set.
Each group is called a cluster and each object can be deﬁned
as a relations between objects belong in the same group arestronger than a relations between objects belong in the different group. K-menas algorithm is one of the most famous clustering method and is used if the number of clusters is known
and the clusters tend to be spherical. In this algorithm, we
can ﬁnd K cluster centers (each object is assigned to the closest cluster center). In other words, this algorithm can ﬁnd theminimum sum of distances between the object and the clustercenter it belongs. This means that the clustering is one of a
optimization problems.
Mr. Senthilnath et. al. [1] had proposed a new clustering algorithm combined K-means algorithm and Fireﬂy Algorithm

and numerical experiments have indicated that it is more efﬁcient algorithm than the others. Fireﬂy Algorithm (FA) has
been proposed by Mr. Yang in 2007 and is based on the idealized behavior of the ﬂashing characteristics of ﬁreﬂy [2].
FA is a efﬁcient optimization algorithm because it has a deterministic component and a random component. Almost allalgorithms having only the deterministic component are local
search algorithms, for which there is a risk of being trapped
at local optima. However, the random component makes it
possible to escape from such local optima.
In this paper, we propose a new clustering algorithm combined K-means algorithm and Improved FA. In our proposed
algorithm, one parameter is changed when the assignment
does not change. We compare the conventional K-means algorithm, K-means algorithm combined the conventional FAand our proposed algorithm using simple model. Numericalexperiments indicate that our proposed algorithm is more efﬁcient algorithm than the other algorithms.
2. The Conventional Methods
In this section, we explain the conventional K-means algorithm and Fireﬂy Algorithm (FA).
2.1 K-means algorithm
K-menas clustering is one of the most famous clustering
method and is used if the number of clusters is known andthe clusters tend to be spherical. The goal of this clustering is
to ﬁnd cluster centers and each object is assigned to the closest cluster center. Therefore this clustering is a optimization
problem because we need to ﬁnd the minimum sum of Euclidean distances between the cluster centers and the objects.

- 225 -

Algorithm 1 The conventional Fireﬂy Algorithm
Objective function f (x), x = (x1 , ..., xd )T
Initialize a population of ﬁreﬂies xi (i = 1, 2, ..., n)while t < M axGeneration dofor i = 1 to n, all n ﬁreﬂies dofor j = 1 to n, all n ﬁreﬂies doLight intensity Ii at xi is determined by f (xi )if Ii > Ij thenMove ﬁreﬂy i towards j in all d dimensions
end ifAttractiveness varies with distance r via exp[−γr]Evaluate new solutions and update light intensity
end forj
end fori
Rank the ﬁreﬂies and ﬁnd the current best
end while
Postprocess results and visualization• Attractiveness is proportional to brightness; thus, for any
two ﬂashing ﬁreﬂies, the less brighter one will movetowards the brighter one. Both the attractiveness andbrightness stared above decrease as their distance increases. If no one is brighter than a particular ﬁreﬂy,
it moves randomly.
• The brightness or light intensity of a ﬁreﬂy is affected ordetermined by the landscape of the objective function tobe optimized.
Attractiveness of ﬁreﬂy β is deﬁned by
2= (β0 − βmin )e−γrij + βmin ,1γ = √ ,L|Xmax − Xmin |,
L =
2
β

(2)
(3)
(4)

where γ is the light absorption coefﬁcient, βmin is the miniThis clustering is solved using K-means algorithm and this mum value of β, β is the attractiveness at r = 0, and r
0ij
ij
algorithm is composed of the following four steps:
is the distance between any two ﬁreﬂies i and j at xi and xj .
• Initialize all cluster centers and objects. The number of L means the average scale for the problem. The movement
cluster centers and all objects are predeﬁned. All cluster of the ﬁreﬂy i is attracted to another more attractive ﬁreﬂy j,
and is determined bycenters generate randomly in search space.
xi = xi + β(xj − xi ) + αi ,• Assignments. Each object is assigned to only the closest
cluster center.
• Calculates cluster centers. The places of each cluster
center move to mean of each group object.
• Iterate assignment and calculate steps until the assignments no longer change.

i = (random − 0.5)L,

where xi is the position vector of ﬁreﬂy i, random is a uniform random number distributed in [0, 1] and α(t) is the randomization parameter. The parameter α(t) is deﬁned by
α(t) = α(0)The objective function of clustering is deﬁned by
J=NK 
|ck − on | ,2(1)k=1 n=1

where K is the number of cluster centers, N is the number ofobjects, ck is the position vector of cluster center k and on isthe position vector of object n.
2.2 The Conventional Fireﬂy Algorithm (FA)
FA has been developed by Yang and it was based on theidealized behavior of the ﬂashing characteristics of ﬁreﬂies[2]. Many active researchers have paid attention to FA [3, 4]
The conventional FA idealizes these ﬂashing characteristics
using the following three rules:• All ﬁreﬂies are unisex so that one ﬁreﬂy is attracted toother ﬁreﬂies regardless of their sex.

(5)
(6)

10−4
0.9

t/tmax,(7)

where t is the number of iteration.
Algorithm 1 shows pseudo code of the conventional FA forminimum optimization problems.
3. K-means algorithm combined FA
The clustering algorithm combined K-means algorithm
and the conventional FA has been proposed in 2011 by Mr.
Senthilnath et. al [1]. In this algorithm, the position vectorof ﬁreﬂy i xi is (c1 , c2 , ..., cK ), that is, each ﬁreﬂy has theplaces of all cluster centers. The attractiveness of each ﬁreﬂy
is deﬁned by objective function (Eq. (7)). Numerical experiments have indicated that this algorithm is more efﬁcient algorithm than K-means algorithm and other algorithms using
well known typical benchmark data sets.
Algorithm 2 shows pseudo code of K-means algorithm
combined FA.

- 226 -Algorithm 2 K-means algorithm combined FA
Initialize a population of ﬁreﬂies xi (i = 1, 2, ..., Nf )Initialize a cluster centers ck (k = 1, 2, ..., Nc )Initialize a objects on (n = 1, 2, ..., No )while t < M axGeneration do
Each object is assigned the closest cluster center
calculate Ji (i = 1, 2, ..., N f )Light intensity Ii is determined by Jiif Ii > Ij thenMove ﬁreﬂy i towards j
end ifFind the current best
end while
Postprocess results and visualization

100532620

14200100

Figure 1: simple modal we used
4. K-means algorithm combined Improved FA

α(0)new=iα(0)i − Vα(0)i100

75
Success rate [%]K-means algorithm sometimes converges to a local minimum from a starting position of the search. K-means algorithm combined FA also has this disadvantage. Therefore, ourpurpose of this study is to remove this disadvantage. In ourproposed algorithm, each ﬁreﬂy has their own value of α(0)and we set all values of α(0) to 1.0 at the same time of initializing a population of ﬁreﬂies. In the case of a ﬁreﬂy i, if theassignment of all objects does not change, the value of α(0)of ﬁreﬂy i decreases. We deﬁne the minimum value of α(0)is 0.0.
, the assignment changes(8), otherwise

50

25
K-means algorithm
K-means algorithm combined the conventional FA
K-menas algorithm combined Improved FA0100200300

400500Maximum number of iterations of algorithm

The parameter V is predeﬁned certain value. In the case ofα(0) = 1.0, a ﬁreﬂy moves relatively randomly. This makes Figure 2: Comparison of three algorithms using simple modal
the ﬁreﬂy easier to escape a local minimum. In the case ofα(0) = 0.0, a ﬁreﬂy does not move randomly, which makes success we deﬁned is that all objects are assigned at correct
the ﬁreﬂy easier to converge.
cluster.
Figure 2 shows numerical experimental results when theparameter V = 0.1 We assume that our proposed algorithm
5. Numerical Experiments
is more efﬁcient algorithm than the other two algorithms. OurWe compare the conventional K-means algorithm, K- proposed algorithm and K-means algorithm combined themenas algorithm combined the conventional FA and our pro- conventional FA are more efﬁcient algorithm when the maxposed algorithm using simple model we deﬁned.
imum number of iterations of algorithm is more than about
We explain the simple model (see Fig. 1). We set the num- 70. Our proposed algorithm is more efﬁcient algorithm whenber of dimensions is 2, each dimension range is [0, 100], the the maximum number of iterations of algorithm is more thannumber of clusters is 6 and the number of objects is 120 (20 about 300.
objects are belong to one cluster). Each ideal cluster center
Next, we focus on the parameter V . We set the value ofis predeﬁned at (30, 30), (70, 70), (10, 80), (90, 20), (50, V to 0.1, 0.2 and 0.3 and compare success rate (see Fig. 3).
90) and (70, 70). Each object is re-generated around ideal As increasing the parameter V , success rate goes up quickly
cluster center by simulate, the distances from the objects to until the maximum number of iterations of algorithm is 100.
the allocated cluster centers are within 10. We set β0 = 1.0, On the other hand, when the maximum number of iterations
βmin = 0.1 and Nf = 20. Each numerical experiment is of algorithm is from 500 to 700, we hard to determine which
run 300 and we compare success rate of each algorithm. The value is better than others according to this graph. Therefore,- 227 -100

10075
Success rate [%]Success rate [%]

7550
V=0.1
V=0.3

V=0.2
V=0.4

only last assignment
last two assignment
last three assignment
last four assignment

2525050

0100

200

300

400

500

600

700

Figure 3: Comparison of the parameter V

100200

300

400

500

600

700

Maximum number of iterations of algorithm

Maximum number of iterations of algorithm

Figure 4: Comparison of the right time to decrease the parameter α(0)Table 1: The average, maximum and minimum values of success rate from 500 to 700
value of V average maximum minimum
0.188.490.7
84.3
87.2
91.7
82.7
0.2
0.3
86.1
88.3
83.3
0.4
85.4
89.3
81.0

tend to converge. Numerical experiments have indicated thatour proposed algorithm is more efﬁcient algorithm than othertwo algorithms.
In future work, we try to improve our proposed algorithm
and apply more complex problems.
Acknowledgment

we summarize a average, miximum and minimum values ofsuccess rate in Tab. 1. In the case of average and minimum
values, algorithm set V = 0.1 performs better. In the case of
maximum value, algorithm set V = 0.2 performs better. We
assume that V = 0.1 is the most suitable value.
Finally, we focus on the right time to decrease the parameter α(0). From here, we decrease the parameter α(0) when
the new assignment is the same as only the last assignment.
We change the right time to decrease the parameter α(0)when the new assignment is the same as the last two, threefour or ﬁve assignment (see Fig 4). We assume that the righttime to decrease the parameter α(0) is when the new assignment is the same as the last assignment. Success rates until
the maximum number of iterations of algorithm is about 100
are almost same. On the other hand, when maximum numberof iterations of algorithm is from 300, the case of only last
assignment obtains better result than the others.
6. Conclusion
In this study, we have proposed a new clustering algorithm; K-means algorithm combined improved Fireﬂy Algorithm. In our proposed algorithm, one parameter is changed
when the assignment does not change. In our proposed algorithm, at the beginning of the search, all ﬁreﬂies move relatively randomly. This mean ﬁreﬂy easy to escape from alocal minimum. As increasing iteration of algorithm, ﬁreﬂy

This work was partly supported by JSPS Grant-in-Aid for
Challenging Exploratory Research 26540127.
References[1] J. Senthilnath, S.N. Omkar and V. Mani, “Clustering
using Fireﬂy Algorithm: Performance Study”, Swarmand Evolutionary Computation 1, pp. 164–171, 2011.
[2] X.S. Yang, Nature-Inspired Metaheuristic Algorithms
Second Edition, Luniver Press, 2010.
[3] S. Lukasik and S. Zak, “Fireﬂy Algorithm for Continuous Constrained Optimization Tasks”, ComputationalCollective Intelligence. Semantic Web, Social Networks
and Multiagent Systems, Vol. 5796 of the Series Lecture
Notes in Computer Science, pp. 97–106, 2009.
[4] H. Matsushita, “Fireﬂy Algorithm with DynamicallyChanging Connections”, Proceedings of International
Symposium on Nonlinear Theory and its Application (NOLTA’14), pp. 906–909, 2014.
[5] J. Kennedy and R. Eberhart, “Particle Swarm Optimization”, Proceedings of the International Conference on
Neural Networks, pp. 1942–1948, 1995.

- 228 -