# An Improved Animal Migration Optimization Algorithm for Clustering Analysis

Authors: Mingzhi Ma; Qifang Luo; Yongquan Zhou; Xin Chen; Liangliang Li
Journal: Discrete Dynamics in Nature and Society
 (2015)

---

## Abstract

Animal migration optimization (AMO) is one of the most recently introduced algorithms based on the behavior of animal swarm migration. This paper presents an improved AMO algorithm (IAMO), which significantly improves the original AMO in solving complex optimization problems. Clustering is a popular data analysis and data mining technique and it is used in many fields. The well-known method in solving clustering problems isk-means clustering algorithm; however, it highly depends on the initial solution and is easy to fall into local optimum. To improve the defects of the k-means method, this paper used IAMO for the clustering problem and experiment on synthetic and real life data sets. The simulation results show that the algorithm has a better performance than that of the k-means, PSO, CPSO, ABC, CABC, and AMO algorithm for solving the clustering problem.


---

## Body

## 1. Introduction

Data clustering is the process of grouping data into a number of clusters. The goal of data clustering is to make the data in the same cluster share a high degree of similarity while being very dissimilar to data from other clusters. It is a main task of exploratory data mining and a common technique for statistical data analysis used in many fields, including machine learning, pattern recognition, image analysis, information retrieval, and bioinformatics. Cluster analysis was originated in anthropology by Driver and Kroeber in 1932 and introduced to psychology by Zubin in 1938 and Tryon in 1939 and famously used by Cattell beginning in 1943 [1] for trait theory classification in personality psychology. Many clustering methods have been proposed; they are divided into two main categories: hierarchical and partitional. The k-means clustering method [2] is one of the most commonly used partitional methods. However, the results of k-means solving the clustering problem highly depend on the initial solution and it is easy to fall into local optimal solutions. Zhang et al. have proposed an improved k-means clustering algorithm called k-harmonic means [3]. But the accuracy of the results obtained by the method is not high enough.In recent years, many studies have been inspired by animal behavior phenomena for developing optimization techniques, such as firefly algorithm (FA) [4], cuckoo search (CS) [5], bat algorithm (BA) [6], artificial bee colony (ABC) [7], and particle swarm optimization (PSO) [8]. Because of its advantages of global, parallel efficiency, robustness, and universality, these bioinspired algorithms have been widely used in constrained optimization and engineering optimization [9, 10], scientific computing, automatic control, and clustering problem [11–21]. Niknam et al. have proposed an efficient hybrid evolutionary algorithm based on combining ACO and SA for clustering problem [15, 16] in 2008. In 1991, Colorni et al. have presented ant colony optimization (ACO) algorithm based on the behavior of ants seeking a path between their colony and a source of food [22]. Then Shelokar et al. and Kao and Cheng have solved the clustering problem using the ACO algorithm [17, 18] in 2004 and 2006. Eberhart and Kennedy have proposed particle swarm optimizer (PSO) algorithm which simulates the movement of organisms in a bird flock or fish school [8] in 1995 and the algorithm also has been adopted to solve this problem by Omran et al. and van der Merwe and Engelbrecht [19, 23] in 2005 and 2003. Kao et al. have presented a hybrid approach according to combination of the k-means algorithm, Nelder-Mead simplex search, and PSO for clustering analysis [14] in 2008. Niknam et al. have presented a hybrid evolutionary algorithm based on PSO and SA (simulated annealing algorithm, 1989 [24]) to solve the clustering problem [13] in 2009. Zou et al. have proposed a cooperative artificial bee colony algorithm to solve the clustering problem and experiment on synthetic and real life data sets to evaluate the performance [11] in 2010. Niknam and Amiri have proposed an efficient hybrid approach based on PSO, ACO, and k-means called PSO-ACO-K approach for clustering analysis [12] in 2010. The artificial bee colony (ABC) algorithm is described by Karaboga [25] in 2005 and it has been adopted to solve clustering problem by Karaboga and Ozturk [20] in 2011. Voges and Pope have used an evolutionary-based rough clustering algorithm for the clustering problem [21] in 2012. Chen et al. have used monkey search algorithm for clustering analysis [26] in 2014.Animal migration algorithm (AMO) is a new bioinspired intelligent optimization algorithm by simulating animal migration behavior proposed by Li et al. [27] in 2013. AMO simulates the widespread migration phenomenon in the animal kingdom, through the change of position, replacement of individual, and finding the optimal solution gradually. AMO has obtained good experimental results on many optimization problems. This paper presents an algorithm to improve the performance of AMO. We proposed a new migration method to modify the performance of AMO, the migration process based on shrinking animals living area operator; this method guarantees AMO rapid convergence to global optimum. By means of selecting the better solution space around the current solution, it improves search ability and accelerates convergence velocity, and it has more chance to find the global optima.The structure of the paper is as follows. In Section2, the traditional method k-means for clustering is presented. In Section 3, the original AMO algorithm is introduced. Section 4 describes our proposed novel approach of migration process. Section 5 elaborates the improved AMO and some biological foundations of animal behaviors are explained. Section 6 illustrates experiments and discusses the results. Section 7 studies the extent of different size of shrinkage coefficient impact of the proposed algorithm. At the end of the paper, we conclude it with future directions and developments with the improved AMO.


## 2. Thek-Means Clustering Algorithm

The target of data clustering is grouping data into a number of clusters;k-means is one of the simplest unsupervised learning algorithms that solve the clustering problem. It is proposed by MacQueen in 1967 [28]. The procedure follows a simple and easy way to classify a given data set D=x1,x2,…,xn through a certain number of clusters G1,G2,…,GK (assume K clusters) fixed a priori; each data vector is a p-dimensional vector, satisfying the following conditions [29, 30]:(1)
Gi=⌀,i=1,2,…K;(2)
Gi∩Gj=⌀,i,j=1,2,…K,i≠j;(3)
⋃i=1KGi=x1,x2,…,xn.The k-means clustering algorithm is as follows.(1)
Set the number of clustersK and the data set D=x1,x2,…,xn.(2)
Randomly chooseK points c1,c2,…,cK as the cluster centroids from x1,x2,…,xn.(3)
Assign each objectxi to the group that has the closest centroid. The principle of division is as follows: if dxi-ci<dxi-ck, k=1,2,…,K and i≠k. The data xi will be divided into classified collection Gi.(4)
When all objects have been assigned, recalculate the positions of theK centroids c1*,c2*,…,cK*:
(1)ci*=1Gi∑xj∈Gjxj,i=1,2,…,K,
where Gi is the number of the points in the classified collection Gi.(5)
Repeat Steps(2) and (4) until the centroids no longer move.The main idea is to defineK centroids, one for each cluster. These centroids should be placed in a cunning way because of different location causing different result. So the better choice is to place them as much as possible far away from each other. In this study, we will use Euclidian metric as a distance metric. The expression is given as follows:
(2)dxi,cj=∑k=1pxik-cjk2.
Finally, this algorithm aims at minimizing an objective function, in this case a squared error function. The objective function is as follows:
(3)fX,C=∑i=1nmin⁡xi-ck2∣k=1,2,…,K.


## 3. Animal Migration Optimization (AMO)

Animal migration algorithm can be divided into animal migration process and animal updating process. In the migration process, the algorithm simulates how the groups of animals move from current position to a new position. During the population updating process, the algorithm simulates how animals are updated by the probabilistic method.


### 3.1. Animal Migration Process

During the animal migration process, an animal should obey three rules:(1) avoid collisions with your neighbors; (2) move in the same direction as your neighbors; and (3) remain close to your neighbors. In order to define concept of the local neighborhood of an individual, we use a topological ring, as has been illustrated in Figure 1. For the sake of simplicity, we set the length of the neighborhood to be five for each dimension of the individual. Note that, in our algorithm, the neighborhood topology is static and is defined on the set of indices of vectors. If the index of animal is i, then its neighborhood consists of animal having indices i-2,i-1,i,i+1,i+2, if the index of animal is 1, the neighborhood consists of animal having indices NP-1,NP,1,2,3, and so forth. Once the neighborhood topology has been constructed, we select one neighbor randomly and update the position of the individual according to this neighbor, as can be seen in the following formula:
(4)Xi,G+1=Xi,G+δ·Xneiborhood,G-Xi,G,
where Xneiborhood,G is the current position of the neighborhood, δ is produced by using a random number generator controlled by a Gaussian distribution, Xi,G is the current position of ith individual, and Xi,G+1 is the new position of ith individual.Figure 1
The concept of the neighborhood of an animal.


### 3.2. Population Updating Process

During the population updating process, the algorithm simulates how some animals leave the group and some join in the new population. Individuals will be replaced by some new animals with a probabilityPa. The probability is used according to the quality of the fitness. We sort fitness in descending order, so the probability of the individual with best fitness is 1/NP and the individual with worst fitness, by contrast, is 1, and the process can be shown in Algorithm 1.Algorithm 1:Population updating process.
(
1) For  i=1  to  NP  do
(2) For  j=1  to  D  do
(3)   If  rand>Pa  then
(4)    Xi,G+1=Xr1,G+rand⋅(Xbest,G-Xi,G)+rand⋅(Xr2,G-Xi,G)
(5) End If
(6) End For
(7) End ForIn Algorithm1, r1,r2∈[1,…,NP] are randomly chosen integers, r1≠r2≠i. After producing the new solution Xi,G+1, it will be evaluated and compared with the Xi,G, and we choose the individual with a better objective fitness:
(5)Xi=Xi,GiffXi,GisbetterthanfXi,G+1,Xi,G+1otherwise.


## 3.1. Animal Migration Process

During the animal migration process, an animal should obey three rules:(1) avoid collisions with your neighbors; (2) move in the same direction as your neighbors; and (3) remain close to your neighbors. In order to define concept of the local neighborhood of an individual, we use a topological ring, as has been illustrated in Figure 1. For the sake of simplicity, we set the length of the neighborhood to be five for each dimension of the individual. Note that, in our algorithm, the neighborhood topology is static and is defined on the set of indices of vectors. If the index of animal is i, then its neighborhood consists of animal having indices i-2,i-1,i,i+1,i+2, if the index of animal is 1, the neighborhood consists of animal having indices NP-1,NP,1,2,3, and so forth. Once the neighborhood topology has been constructed, we select one neighbor randomly and update the position of the individual according to this neighbor, as can be seen in the following formula:
(4)Xi,G+1=Xi,G+δ·Xneiborhood,G-Xi,G,
where Xneiborhood,G is the current position of the neighborhood, δ is produced by using a random number generator controlled by a Gaussian distribution, Xi,G is the current position of ith individual, and Xi,G+1 is the new position of ith individual.Figure 1
The concept of the neighborhood of an animal.


## 3.2. Population Updating Process

During the population updating process, the algorithm simulates how some animals leave the group and some join in the new population. Individuals will be replaced by some new animals with a probabilityPa. The probability is used according to the quality of the fitness. We sort fitness in descending order, so the probability of the individual with best fitness is 1/NP and the individual with worst fitness, by contrast, is 1, and the process can be shown in Algorithm 1.Algorithm 1:Population updating process.
(
1) For  i=1  to  NP  do
(2) For  j=1  to  D  do
(3)   If  rand>Pa  then
(4)    Xi,G+1=Xr1,G+rand⋅(Xbest,G-Xi,G)+rand⋅(Xr2,G-Xi,G)
(5) End If
(6) End For
(7) End ForIn Algorithm1, r1,r2∈[1,…,NP] are randomly chosen integers, r1≠r2≠i. After producing the new solution Xi,G+1, it will be evaluated and compared with the Xi,G, and we choose the individual with a better objective fitness:
(5)Xi=Xi,GiffXi,GisbetterthanfXi,G+1,Xi,G+1otherwise.


## 4. The New Migration Process Method

In AMO, algorithm uses migration process and population updating process to find a satisfactory solution. The proposed algorithm used a new migration process by establishing a living area by the leader animal (the individuals with best fitness value) and animals migrate from current locations into this new living area to simulate animal migration process.At first, there areNP animals that live in living area, as shown in Figure 2(a), moving, eating, drinking, reproducing, and so on; some individuals move randomly and their position be updated, and then we calculate the best position of animals by fitness function and record it. But the amount of food or water gradually diminished as the time wore on, as shown in Figure 2(b), and some animals migrate from the current areas which have no food and water to a new area with abundant food and water, as shown in Figure 2(c). In Figure 2, the green parts represent the living areas with abundant food and water; animals can live in these areas. And the yellow parts represent the areas that lack food or water; animals can no longer live in these areas, and they must migrate to a new living area (the green parts in Figure 2(c)). We shrink the living area after a period of time (as shown in Figures 2(a) and 2(c)), and then animals migrate to the new living area ceaselessly. As a rule of thumb, the globally optimal solution always nearby is the current best solution; in IAMO, the animals living area is smaller and smaller (by formula (6)) after each iteration, and the individuals get closer and closer to the globally optimal solution, so we can accelerate the convergence velocity and precision of the algorithm to some extent.Animals migration process.
(a)
TheGth iteration living area
(b)
Animals begin to migrate
(c)
TheG+1th iteration living areaThe boundary of the living area is established by(6)low=Xbest-R,up=Xbest+R,R=ρ·R,
where Xbest is the leader animal (the current best solution), low and up are the lower and upper bound of the living area, R is living area radius, ρ is shrinkage coefficient, ρ∈0,1, and low, up, and R are all 1×D row vector. In general, the original value of R depends on the size of the search space. As iterations go on, a big value of R improves the exploration ability of the algorithm and a small value of R improves the exploitation ability of the algorithm.


## 5. The IAMO Algorithm for Solving Clustering Problem

### 5.1. Initializing the Population

During the initialization process, the algorithm begins with initializing a set ofNP animal positions X1,X2,X3,…,XNP; each animal position Xi is a 1×(K×D)-dimensional vector, where K is the number of clustering center and D is the dimension of the test set GN×D. The cluster centers xi*=xi1,xi2,…,xiD, (i=1,2,…,K), each center xi* is 1×D-dimensional vector, and the lower bound of the centers is the minimum of each column in test set GN×D, namely, ai*=min⁡G1,G2…,GD, and the upper bound of the centers is bi*=max⁡G1,G2…,GD. So we can initialize the position of an individual Xi=x1*,x2*,…, xK*=x11,x12,…,x1D,x21,x22,…,x2D,…,xK1,xK2,…,xKD=x11,x12,…,xKD, and then the lower and upper bounds of the solution space are a=a1*,a2*,…,aK* and b=b1*,b2*,…,bK*.Animals are randomly and uniformly distributed between the prespecified lower initial parameter bounda and the upper initial parameter bound b. So the jth component of the ith vector is as follows:
(7)xi,j=aj+randi,j0,1·bj-aj,i=1,…,NP,j=1,…,K×D,
where randi,j[0,1] is a uniform distribution random number between 0 and 1.


### 5.2. Animals Migration

During the migration process, because of animals hunting, foraging, or drinking in the living area, some parts of the living area are lacking food or water or climate condition change, and some animals migrate from the current living area to the new living area which has abundant food and water or climate condition suitable for living. We assume that there is only one living area, and animals out of the new living area would be migrating into the new living area, as depicted in Section4. We calculate the distance between cluster centers x1*,x2*,⋯,xK* and text data set, then we classify test data set into K categories according to the distance, and, finally, we can obtain the fitness according the fitness function:
(8)fX,G=∑i=1Nmin⁡Gi-xk2∣k=1,2,…,K.According to the fitness function, we obtain the best individualXbest, and the new living area can be established by Xbest and R.


### 5.3. Individuals in Population Updating

During the population updating process, algorithm simulates some animals that are preyed by their enemies or some animals leave the group and some join in the group from other groups or some new animals are born. In IAMO, we assume that the number of available animals is fixed, and every animal will be replaced byPa, as shown in Section 3.2.Specific implementation steps of the improved animals migration optimization algorithm (IAMO) can be shown as in Algorithm2.Algorithm 2:An improved animal’s migration optimization algorithm (IAMO).
(1)Begin
(2) Set the generation counterG, living area radius R, shrinkage coefficient ρ, and randomly initialize Xi
with a population ofNP animals in solution space
(3) Evaluate the fitness for each individualXi, record the best individual Xbest
(4)While stopping criteria is not satisfied do
(5) Establish a new living area bylow=Xbest-R, up=Xbest+R
(6) Animals migrate into the new living area
(7)For  i = 1 to  NP  do
(8)For  j = 1 to  D  do
(9)   Select randomlyr1≠r2≠i
(10)If rand > Pathen
(11)Xi,G+1=Xr1,G+rand⋅(Xbest,G-Xi,G)+rand⋅(Xr2,G-Xi,G)
(12)End If
(13)End For
(14)End For
(15)For  i = 1 to  NP  do
(16)  Evaluate the offspringXi,G+1
(17)If  Xi,G+1 is better than Xi  then
(18)Xi=Xi,G+1
(19)End If
(20)End for
(21)  Memorize the best solution achieved so far
(22)R=R⋅ρ
(23)End while
(24)End


## 5.1. Initializing the Population

During the initialization process, the algorithm begins with initializing a set ofNP animal positions X1,X2,X3,…,XNP; each animal position Xi is a 1×(K×D)-dimensional vector, where K is the number of clustering center and D is the dimension of the test set GN×D. The cluster centers xi*=xi1,xi2,…,xiD, (i=1,2,…,K), each center xi* is 1×D-dimensional vector, and the lower bound of the centers is the minimum of each column in test set GN×D, namely, ai*=min⁡G1,G2…,GD, and the upper bound of the centers is bi*=max⁡G1,G2…,GD. So we can initialize the position of an individual Xi=x1*,x2*,…, xK*=x11,x12,…,x1D,x21,x22,…,x2D,…,xK1,xK2,…,xKD=x11,x12,…,xKD, and then the lower and upper bounds of the solution space are a=a1*,a2*,…,aK* and b=b1*,b2*,…,bK*.Animals are randomly and uniformly distributed between the prespecified lower initial parameter bounda and the upper initial parameter bound b. So the jth component of the ith vector is as follows:
(7)xi,j=aj+randi,j0,1·bj-aj,i=1,…,NP,j=1,…,K×D,
where randi,j[0,1] is a uniform distribution random number between 0 and 1.


## 5.2. Animals Migration

During the migration process, because of animals hunting, foraging, or drinking in the living area, some parts of the living area are lacking food or water or climate condition change, and some animals migrate from the current living area to the new living area which has abundant food and water or climate condition suitable for living. We assume that there is only one living area, and animals out of the new living area would be migrating into the new living area, as depicted in Section4. We calculate the distance between cluster centers x1*,x2*,⋯,xK* and text data set, then we classify test data set into K categories according to the distance, and, finally, we can obtain the fitness according the fitness function:
(8)fX,G=∑i=1Nmin⁡Gi-xk2∣k=1,2,…,K.According to the fitness function, we obtain the best individualXbest, and the new living area can be established by Xbest and R.


## 5.3. Individuals in Population Updating

During the population updating process, algorithm simulates some animals that are preyed by their enemies or some animals leave the group and some join in the group from other groups or some new animals are born. In IAMO, we assume that the number of available animals is fixed, and every animal will be replaced byPa, as shown in Section 3.2.Specific implementation steps of the improved animals migration optimization algorithm (IAMO) can be shown as in Algorithm2.Algorithm 2:An improved animal’s migration optimization algorithm (IAMO).
(1)Begin
(2) Set the generation counterG, living area radius R, shrinkage coefficient ρ, and randomly initialize Xi
with a population ofNP animals in solution space
(3) Evaluate the fitness for each individualXi, record the best individual Xbest
(4)While stopping criteria is not satisfied do
(5) Establish a new living area bylow=Xbest-R, up=Xbest+R
(6) Animals migrate into the new living area
(7)For  i = 1 to  NP  do
(8)For  j = 1 to  D  do
(9)   Select randomlyr1≠r2≠i
(10)If rand > Pathen
(11)Xi,G+1=Xr1,G+rand⋅(Xbest,G-Xi,G)+rand⋅(Xr2,G-Xi,G)
(12)End If
(13)End For
(14)End For
(15)For  i = 1 to  NP  do
(16)  Evaluate the offspringXi,G+1
(17)If  Xi,G+1 is better than Xi  then
(18)Xi=Xi,G+1
(19)End If
(20)End for
(21)  Memorize the best solution achieved so far
(22)R=R⋅ρ
(23)End while
(24)End


## 6. Numerical Simulation Experiments

All of the algorithm was programmed in MATLAB R2008a, numerical experiment was set up on AMD Athlon(tm)II *4 640 processor and 2 GB memory.The experimental results comparing the IAMO clustering algorithm with six typical stochastic algorithms including the PSO [31], CPSO [32], ABC [20], CABC [11], AMO [27], and k-means algorithms are provided for two artificial data sets and eight real life data sets (Iris, teaching assistant evaluation (TAE), wine, seeds, StatLog (heart), Hagerman’s survival, balance scale, and Wisconsin breast cancer) which are selected from the UCI machine learning repository [33].Artificial Data Set One
(
N
=
250, d=3,andK=5). This is a three-featured problem with five classes, where every feature of the classes was distributed according to Class 1-Uniform (85, 100), Class 2-Uniform (70, 85), Class 3-Uniform (55, 70), Class 4-Uniform (40, 55), and Class 5-Uniform (25, 40) [12, 14]. The data set is illustrated in Figure 3.Figure 3
The distribution image of Art1.Artificial Data Set Two
(
N
=
600, d=2,andK=4). This is a two-featured problem with four unique classes. A total of 600 patterns were drawn from four independent bivariate normal distributions, where classes were distributed according to
(9)N2μ=mimi,Σ=0.50.050.050.5,
where i=1,2,3,4,…>4, m1=-3, m2=0, m3=3, and m4=6.μ and Σ are mean vector and covariance matrix, respectively [12, 14]. The data set is illustrated in Figure 4.Figure 4
The distribution image of Art2.Iris Data
(
N
=
150, d=4,andK=3). This data set with 150 random samples of flowers from theIris speciessetosa,versicolor, andvirginica collected by Anderson [34]. From each species, there are 50 observations for sepal length, sepal width, petal length, and petal width in cm. This data set was used by Fisher [35] in his initiation of the linear-discriminant-function technique [11, 12, 33].Teaching Assistant Evaluation
(
N
=
151, d=5,andK=3). The data consist of evaluations of teaching performance over three regular semesters and two summer semesters of 151 teaching assistant (TA) assignments at the Statistics Department of the University of Wisconsin-Madison. The scores were divided into 3 roughly equal-sized categories (“low,” “medium,” and “high”) to form the class variable [33].Wine Data
(
N
=
178, d=13,andK=3). This is the wine data set, which is also taken from MCI laboratory. These data are the results of a chemical analysis of wines grown in the same region in Italy but derived from three different cultivars. The analysis determined the quantities of 13 constituents found in each of the three types of wines. There are 178 instances with 13 numeric attributes in wine data set. All attributes are continuous. There is no missing attribute value [11, 12, 33].Seeds Data
(
N
=
210, d=7,andK=3). This data set consists of 210 patterns belonging to three different varieties of wheat: Kama, Rosa, and Canadian. From each species, there are 70 observations for area A, perimeter P, compactness C (C=4*pi*A/P2), length of kernel, width of kernel, asymmetry coefficient, and length of kernel groove [33].StatLog (Heart) Data
(
N
=
270, d=13,andK=2). This data set is a heart disease database similar to a database already present in the repository (heart disease databases) but in a slightly different form [33].Hagerman’s Survival
(
N
=
306, d=3,andK=2). The data set contains cases from a study that was conducted between 1958 and 1970 at the University of Chicago’s Billings Hospital on the survival of patients who had undergone surgery for breast cancer. It records two survival status patients with the age of patient at time of operation, patient’s year of operation, and number of positive axillary nodes detected [33].Balance Scale Data
(
N
=
625, d=4,andK=3). This data set was generated to model psychological experimental results. Each example is classified as having the balance scale tip to the right, to the left, or balanced. The attributes are the left weight, the left distance, the right weight, and the right distance. The correct way to find the class is the greater of (left-distance * left-weight) and (right-distance * right-weight). If they are equal, it is balanced [33].Wisconsin Breast Cancer
(
N
=
683, d=9,andK=2). It consists of 683 objects characterized by nine features: clump thickness, cell size uniformity, cell shape uniformity, marginal adhesion, single epithelial cell size, bare nuclei, bland chromatin, normal nucleoli, and mitoses. There are two categories in the data: malignant (444 objects) and benign (239 objects) [11, 12, 33].Here we set the parameters of AMO and IAMO as follows. The population size of the AMO and IAMO is 100. In IAMO, the original living area radiusR=0.3b-a and shrinkage coefficient ρ=0.92. For the PSO, inertia weight w=0.729, acceleration coefficients c1=2, c2=2, and population size M=100. The population size of the CPSO is 20. The population size of the ABC and CABC are 50 and 10, respectively. In order to compare with other algorithms, the maximum generations of all algorithms are 100.For every data set, each algorithm is applied 20 times individually with random initial solution. For the Art1 and Art2 data set, once the randomly generated parameters are determined, the same parameters are used to test the performance of three algorithms. We ranked each algorithm according to the mean result. The results are kept four digits after the decimal point. The mean value, the best value, the worst value, the standard deviation, and the rank value are recorded in Tables1, 2, 3, 4, 5, 6, 7, 8, 9, and 10.Table 1
Results obtained by the algorithms for 20 different runs on Art1 data.
Algorithm
Mean
Best
Worst
Standard deviation
Rank
k-means
2106.6059
1720.7627
2456.0468
358.8518
7
PSO
1991.3796
1721.6508
2448.1993
192.7566
5
CPSO
1860.5699
1718.6937
2417.5543
305.7752
4
ABC
1718.5496
1718.2939
1718.9832
0.1955
3
CABC
1718.4434
1718.2544
1720.3302
0.5488
2
AMO
2062.1954
1974.4561
2199.1275
54.8921
6
IAMO
1718.2540
1718.2538
1718.2540
1.0990
e
-
05
1Table 2
Results obtained by the algorithms for 20 different runs on Art2 data.
Algorithm
Mean
Best
Worst
Standard deviation
Rank
k-means
644.2100
514.6623
896.4104
181.1884
7
PSO
514.7965
513.9191
523.8308
2.3765
5
CPSO
513.9046
513.9035
513.9085
1.3621
e
-
03
4
ABC
513.9037
513.9035
513.9045
3.2720
e
-
04
3
CABC
513.9037
513.9035
513.9696
1.5235
e
-
04
2
AMO
525.0879
516.1389
546.2325
8.4842
6
IAMO
513.9035
513.9035
513.9035
9.3111
e
-
06
1Table 3
Results obtained by the algorithms for 20 different runs onIris data.
Algorithm
Mean
Best
Worst
Standard deviation
Rank
k-means
102.8412
99.4582
123.4678
8.7805
7
PSO
98.3345
96.6567
104.2224
2.2431
5
CPSO
96.9721
96.6580
97.5211
2.966
e
-
01
4
ABC
96.6659
96.6566
96.7547
2.1388
e
-
02
3
CABC
96.6561
96.6555
96.6599
1.1685
e
-
03
2
AMO
99.0055
97.0751
100.5484
1.1202
6
IAMO
96.6555
96.6555
96.6555
1.2155
e
-
06
1Table 4
Results obtained by the algorithms for 20 different runs on TAE data.
Algorithm
Mean
Best
Worst
Standard deviation
Rank
k-means
1533.5441
1503.9418
1605.1206
29.7491
7
PSO
1501.5895
1490.2455
1529.2453
16.3170
6
CPSO
1499.8073
1492.1980
1532.4523
17.4859
5
ABC
1491.4434
1490.9775
1492.4754
0.5128
3
CABC
1491.3099
1490.9276
1497.3575
2.7356
2
AMO
1499.0215
1493.3564
1509.4512
6.8524
4
IAMO
1491.0900
1490.9321
1492.5707
0.4482
1Table 5
Results obtained by the algorithms for 20 different runs on wine data.
Algorithm
Mean
Best
Worst
Standard deviation
Rank
k-means
17853.2412
16374.4353
18484.3458
1003.6327
7
PSO
16307.0584
16302.8364
16314.0563
5.8844
5
CPSO
16304.9829
16299.0526
16312.1291
5.9887
3
ABC
16305.6668
16299.1970
16321.9535
9.8439
4
CABC
16292.1982
16292.1858
16292.2094
1.0563
e
-
02
2
AMO
16359.7965
16319.9935
16400.5533
30.0025
6
IAMO
16292.1855
16292.1849
16292.1862
5.0627
e
-
04
1Table 6
Results obtained by the algorithms for 20 different runs on seeds data.
Algorithm
Mean
Best
Worst
Standard deviation
Rank
k-means
313.4977
313.1428
313.7343
2.6879
e
-
01
5
PSO
326.5250
318.3185
335.2944
6.0131
7
CPSO
312.1138
311.9116
312.3788
0.2
899
4
ABC
312.0382
311.8520
312.2110
6.7210
e
-
02
3
CABC
311.7980
311.7980
311.7982
1.4865
e
-
04
2
AMO
319.3922
313.8100
327.9267
3.1572
6
IAMO
311.7980
311.7980
311.7980
3.3686
e
-
05
1Table 7
Results obtained by the algorithms for 20 different runs on StatLog (heart) data.
Algorithm
Mean
Best
Worst
Standard deviation
Rank
k-means
10695.7851
10682.5524
10703.8544
8.2080
6
PSO
10760.0684
10644.8965
11024.2641
25.9460
7
CPSO
10651.1354
10624.2168
10747.7609
55.0264
4
ABC
10627.4760
10626.7154
10629.6472
1.0354
3
CABC
10622.9904
10622.9824
10623.6762
1
.
7830
e
-
0
2
2
AMO
10675.1758
10658.6325
10696.1824
17.6918
5
IAMO
10622.9824
10622.9824
10622.9825
5.0093
e
-
05
1Table 8
Results obtained by the algorithms for 20 different runs on Hagerman’s survival data.
Algorithm
Mean
Best
Worst
Standard deviation
Rank
k-means
2640.1277
2610.5245
3180.5211
126.7500
7
PSO
2567.4479
2566.9899
2569.1620
0.9587
6
CPSO
2567.3233
2566.9889
2567.8257
0.4578
5
ABC
2566.9892
2566.9888
2566.9895
2.3919
e
-
04
2
CABC
2566.9903
2566.9888
2566.9955
2.8709
e
-
03
3
AMO
2566.9985
2566.9907
2567.0096
9.1598
e
-
03
4
IAMO
2566.9888
2566.9888
2566.9888
2.3022
e
-
06
1Table 9
Results obtained by the algorithms for 20 different runs on balance scale data.
Algorithm
Mean
Best
Worst
Standard deviation
Rank
k-means
1426.7522
1423.8570
1433.8423
3.1208
5
PSO
1430.1546
1426.4237
1447.6403
9.3451
7
CPSO
1424.8260
1423.5525
1425.5460
0.9048
4
ABC
1423.9238
1423.8308
1425.9821
4
.
5
45
2
e
-
02
3
CABC
1423.9109
1423.8206
1425.2445
1.4053
e
-
0
2
2
AMO
1429.1499
1427.9670
1430.8177
1.1641
6
IAMO
1423.8204
1423.8204
1423.8204
4.9763
e
-
06
1Table 10
Results obtained by the algorithms for 20 different runs on cancer data.
Algorithm
Mean
Best
Worst
Standard deviation
Rank
k-means
2981.2564
2976.4687
2988.4277
4.8661
5
PSO
3001.2685
2969.7475
3114.3658
63.9370
6
CPSO
2964.8268
2964.4167
2965.2941
0.3773
3
ABC
2965.5369
2964.9734
2966.4785
0.8081
4
CABC
2964.4138
2964.3870
2964.5222
6.0177
e
-
02
2
AMO
3001.6328
2974.0974
3050.9651
32.7322
7
IAMO
2964.3870
2964.3870
2964.3870
2.2260
e
-
05
1Tables1–10 show that IAMO is very precise than other algorithms in solving the ten data sets. As seen from the results, the IAMO algorithm provides the best value and small standard deviation in comparison with other methods. For the Art1 and Art2 data set in Tables 1 and 2 which were randomly generated, IAMO obtained the best mean and smallest standard deviation compared to other algorithms. The mean value of IAMO obtained is 1718.2540 in solving Art1, while ABC and CABC obtained 1718.5496 and 1718.4434, and IAMO gives 4 orders of magnitude better than ABC and CABC. Same to solving Art2, IAMO obtained 513.9035, while CPSO, ABC, and CABC obtained 513.9046, 513.9037, and 513.9037, respectively, but the standard deviation of IAMO is at least 2 orders of magnitude better than them. ForIris data set, the mean value, the optimum value, and the worst value of IAMO are all 96.6555 and the standard deviation is 1.2155e-06 which revealed the robustness of IAMO. CABC also sought the best solution 96.6555, but the standard deviation is bigger than IAMO when the best solutions of AMO, PSO, CPSO, ABC, and k-means are 97.0751, 96.6567, 96.6580, 96.6566, and 99.4582, respectively. Table 4 shows the results of algorithms on the TAE data set. The mean value of IAMO is 1491.0900 which is smaller than that of AMO, PSO, CPSO, ABC, CABC, and k-means within 20 runs. For wine data set, IAMO reached the mean value 16292.1855 while CABC reached the mean value 16292.1982. The best value and worst value of IAMO are 16292.1849 and 16292.1862, which are also better than 16292.1858 and 16292.2094 obtained by CABC, and the standard deviation value of IAMO is also the smallest one. Table 6 provides the results of algorithms on the seeds data set; the IAMO algorithm and CABC algorithm are superior to those obtained by the others. Although IAMO and CABC reached the same mean value 311.7980, the standard deviation of IAMO is 1 order of magnitude better than CABC. On StatLog (heart) data set results given in Table 7, IAMO gets the best value is 10622.9824 and the same as CABC, while the mean values of the two algorithms are 10622.9824 and 10622.9904, so the IAMO is better than CABC algorithm. For Hagerman’s survival data set, the optimum value 2566.9888 can be obtained by IAMO, ABC, and CABC, but the standard deviations of ABC and CABC are 2.3919e-04 and 2.8709e-03 which is worse than that of 2.3022e-06 obtained by IAMO. The standard deviation of PSO is a little bigger than that of CPSO. For balance scale data set in Table 9, as seen from the results, the mean, best, and worst ones are all 1423.8204, which reflect the stable characteristics of IAMO. The three best algorithms in this test data are IAMO, CABC, and ABC, and the best results of them are 1423.8204, 1423.8206, and 1423.8308. For Wisconsin breast cancer data set in Table 10, the mean value, the best value, and the worst value are all 2964.3870 which are obviously superior to k-means, PSO, CPSO, ABC, and AMO.As seen from Table1 to Table 10, we can conclude that although the convergence rate is not quick enough at the beginning of the iteration compared to ABC and CABC, the final results are the best compared to other algorithms in all test data sets. The most results of ABC and CABC are better than PSO and CPSO, and the k-means algorithm is the worst for most of test data sets.Figures5, 6, 7, 8, 9, 10, 11, 12, 13, and 14 show the convergence curves of different data sets for various algorithms. Figures 15 and 16 show the original data distribution ofIris data set and the clustering result by IAMO algorithm.Figure 5
The convergence curve of the Art1 data.Figure 6
The convergence curve of the Art2 data.Figure 7
The convergence curve of theIris data.Figure 8
The convergence curve of the TAE data.Figure 9
The convergence curve of the wine data.Figure 10
The convergence curve of the seeds data.Figure 11
The convergence curve of the heart data.Figure 12
The convergence curve of the survival data.Figure 13
The convergence curve of the balance scale data.Figure 14
The convergence curve of the cancer data.Figure 15
TheIris data distribution.Figure 16
TheIris data clustering result.


## 7. Living Area Radius Evaluation

The performance and results of the proposed algorithms are greatly affected by the size of living area. At the beginning of the iteration, a big value ofR improves the exploration ability of the algorithm and; at the end of iteration, a small value of R improves the exploitation ability of the algorithm. We adopted a fixed shrinking coefficient ρ=0.92 to change the living area radius after each iteration, as shown in formula (6). To study the extent of R impacts on the proposed algorithm, we selected Art1 data set andIris data set, using different ρ to evaluate the performance of the proposed algorithm.Figure17 shows the results of an experiment on Art1; we can conclude that if we choose ρ between 0.6 and 0.9, it has a better convergence precision than that of ρ=0.99 or ρ=0.40. If we choose ρ=0.40, IAMO algorithm plunges into local optima, and if we choose ρ=0.99, the IAMO algorithm has a very low convergence rate. And likewise in Figure 18, forIris test data set, IAMO algorithm quickly converged at global optimum before 30 iterations if we choose ρ=0.80, while IAMO could not escape from poor local optima and to global optimum if we choose ρ=0.70, ρ=0.60, or ρ=0.40. So the best ρ for solvingIris data set must exist between 0.7 and 0.99.Figure 17
The convergence curve of the Art1 with differentρ.Figure 18
The convergence curve of theIris with different ρ.The results suggest that a properρ can greatly improve the algorithm convergence velocity and convergence precision, and an improper ρ may lead the IAMO fall into local optimum.


## 8. Conclusions

In this paper, to improve the deficiencies of the AMO algorithm, we improved the algorithm by using a new migration method based on shrinking animals living area. By 10 typical standard test data sets simulation, the results show that IAMO algorithm generally has strong global searching ability and local optimization ability and can effectively avoid the deficiencies that conventional algorithms easily fall into local optimum. IAMO has improved the convergence precision of AMO and rank 1st in all test data sets; therefore, it is very practical and effective to solve clustering problems. At last, how to define a proper and unified radius of living area needs to be considered in subsequent work.



---

*Source: 194792-2015-01-05.xml*