Application Of Bacterial Foraging Optimization Algorithm In Clustering

Optimization problem has been widely used in different areas. Traditional optimization methods are originally adopted to solve optimization problems in engineering applications. Swarm intelligent algorithms were proposed in the1980s to make up the shortcomings of traditional algorithms which cannot address optimization problems with the increasing of complexity. Among all swarm intelligent algorithms, genetic algorithm(GA), ant colony optimization(ACO) algorithm, particle swarm optimization(PSO) algorithm and artificial fish swarm(AFS) algorithm are inspired by higher living creatures, while bacteria foraging optimization(BFO) algorithm is a novel optimization algorithm proposed in2002by mimicking foraging behavior of microorganism searching for food source.Clustering is a significant data mining technology, which is capable of efficiently extracting valuable information needed. The basic principles and concepts of clustering are introduced in detail in this dissertation, especially K-means clustering method. The main researches of this paper refer to the improvement of BFO algorithm and combination of BFO algorithm and K-means clustering method, as follows:Aimed at improving the K-means method, modified K-means method based on BFO was proposed in this paper, namely K-BFO algorithm, in which the basic idea is taking advantages of global searching abilities of BFO algorithm to determine the initial cluster center for avoiding the weakness of choosing the initial cluster center randomly in K-means algorithm. There are three advantages of the novel algorithm:(1) Insensitivity to datasets with various kinds and sizes of data;(2) Characteristic of concurrency for high convergence speed;(3) Dealing with clustering of data in high dimensions;(4) By comparison with PSO based clustering algorithm, K-BFO algorithm possesses simply process for easy understanding, which can obtain better clustering results.The BFO algorithm is improved in this paper, includes three aspects:(1) To overcome the low searching speed generated by random direction of chemotaxis operation in the basic BFO, improved BFO algorithm was presented by moving the individuals to the optimum, or moving to a random direction if the bacteria group without the current optimum for enhancing the direction selection.(2) In the reproduction operation of basic BFO algorithm, fitness is sorted in accordance with average fitness of individual locations after carried out the chemotaxis operation, which may not only eliminate bacteria with good fitness, but also reduce optimization precision of the algorithm. Hence BFO algorithm is improved. Sorting by the best fitness values according to all the individual locations, which can ensure that the optimal bacteria with the best fitness value in the next generation can be retained, and then improve the algorithm convergence speed. Half of bacteria with low fitness are replaced by the half of bacteria with high fitness in the reproduction operation, which leads to a decline in population diversity. Therefore, differential evolution of ideas with floating-point coding in global optimization are adopted in this paper, use the differences of the parent individuals to produce the offspring after the chemotaxis operation. Experiments embody the improved BFO algorithm of high performance.(3) The adaptive probability of migration is used in the operation of elimination and dispersal, which avoids the loss of the outstanding individual.The improved BFO algorithm is applied to the clustering of UCI datasets. Experimental results showed that the algorithm are improved in precision and efficiency, researches will be focus on solving optimization problems in engineering practice in future.