Particle Swarm Optimization And Its Application On Clustering

Many optimization problems have been widely used in economic planning, engineering design, manufacturing, transportation, information processing, and other fields, while optimization problem is the problem of finding the best one from numerous feasible solutions. To solve these problems effectively will not only have very significant meaning for entire society, but also bring great economic benefits. As perspective of mathematics, the objective of optimization is to solve the optimization problem and the specific method for which is called optimization method. Traditional optimization methods, such as Newton, iterative method are based on mathematics and normally strict in the description of the problem. For example, the objective function and constraints of the problems must be continuously differentiable. With the development of advanced manufacturing technology as well as the increasing amount of information, the practical optimization problems have being become more complex. So that, the traditional optimization methods reveal its several drawbacks. Therefore, it is an urgent need to explore new optimization methods.Evolutionary algorithm (EA) has been become popular for optimization problem, because of its simple concept and being easy to implement. Especially, it has obtained good results in terms of convergence speed and accuracy. In last decades, many population-based algorithms have been proposed and improved, e.g., Genetic Algorithm, Differential Evolution, Particle Swarm Optimization, Ant Colony Optimization, Artificial Bee Colony, Cat Swarm Optimization, etc.Particle swarm optimization (PSO) is one of evolutionary algorithms. It simulates bird flocking or fish schooling behavior to achieve a self-evolution system. PSO can search automatically the optimum solution in the vector space. Since PSO has few parameters and is easily used in practical applications. Up today, many PSO variants have been proposed and been presented, they have obtained good results in experiments of benchmark tests and real-world problems. Despite PSO has acquired its effectiveness and efficiency in solving complex problems. However, PSO still has some main drawbacks such as premature convergence, being easily trapped into local optima and low accuracy rate. These drawbacks have imposed the restrictions on wider applications of the PSO to real-world optimization problems. Therefore, the abilities of good accuracy rate and avoiding local optima are two important and appealing tasks in the study of PSO. Up to date, a number of variants of PSO algorithms have been developed so far in order to achieve these two goals. However, its performance is still unsatisfactory for recent real-world optimization problems with high complexity and large scale.In research on EA as well as PSO in particular, one of the most important methods is to balance well between its two abilities of exploitation and exploration. Local search and global search strategies affect two above abilities of exploitation and exploration, respectively. So that, research on improving and selecting local search and global search strategies is the major issues in the research.In this dissertation, the studies focus on improving PSO to overcome its drawbacks. Moreover, to highlight the advantages of PSO, its applications on data clustering and image segmentation based on clustering method are also researched and presented.This dissertation makes some following major contributions:(1) Two methods of improved PSO are proposed. The main methodology used to improve the performance of PSO is to enhance the abilities of exploitation and exploration, and their balance as well.Attracted by neighbourhood topology of particles, various methods via this technique have been presented. J. Kennedy tested on four neighbourhood topologies, namely, Circles, Wheels, Stars, and Random edges, to guide the flight of particles. R. Mendes et al. proposed the fully informed particle swarm (called FIPS) to make the individuals fully informed. J. Liang et al. proposed a comprehensive learning particle swarm optimizer (called CLPSO). Md Nasir et al. proposed a method called dynamic neighbourhood learning particle swarm optimizer (DNLPSO), which was improved from the idea of CLPSO. Furthermore, H. Wang et al. presented a diversity enhanced particle swarm optimization with neighbourhood search algorithm (named DNSPSO), in which the neighbourhood search of local and global strategies were utilized with diversity mechanism. By using an improved neighbourhood search of DNSPSO, D. C. Tran et al. proposed an enhanced particle swarm optimization with diversity and neighbourhood search approach (called EPSODNS). By combining neighbourhood search with Cauchy mutation an approach AMPSONS was presented by D. C. Tran et al. As well as employing the diversity-guided method, several methods of improved PSO have been proposed. In the literature, Y. Gong et al. proposed a method called an efficient resource allocation scheme based on particle swarm optimization (RA-PSO), where particles search for optimal solutions by learning from themselves and their neighbourhood using the comprehensive learning strategy. Aiming to enhance the performance of PSO on complex problems, such as multi-modal, L. Wang et al. proposed a multi-layer PSO method (MLPSO) consisting of global MLPSO and local MLPSO by increasing the swarm layers from two to multiple layers. These above improvement methods achieved good results, however it is still unsatisfactory, especially for complex practical problems.In these two proposed methods, the above techniques of neighbourhood search, multi-layer search, diversity and adaptive mechanism are improved and are employed to improve PSO, and two proposed algorithms are as follows:1) The first method is called Diversity Enhanced PSO with Adaptive Neighbourhood Search (ANSPSO). In this method, two strategies of local and global neighbourhood search are adaptively selected to implement. By using this adaptive method the exploitation and exploration abilities are balanced better. By that way, the performance of optimization algorithm is improved. In addition, in order to enhance the exploration ability, the diversity mechanism is utilized in this method. To evaluate the performance of the proposed method, two sets of benchmark functions are used, namely thirteen classical functions and twenty eight functions of CEC 2013. The experimental results indicate that the proposed method acquires good performance on two sets of numerical benchmark functions in comparing with other methods.ii) The second PSO variant proposed in this dissertation is built based on two adaptive mechanisms and is called Adaptive PSO with Multi-layer and Neighbourhood Search (APSOMNS). In this algorithm, aiming to enhance its performance on multi-modal optimization problems the multi-layer search strategy is used. Similar to the ANSPSO algorithm, the adaptive mechanism of local multi-layer search and global multi-layer search is also utilized. Apart from the adaptive multi-layer search mechanism, in this method still employ the adaptive mechanism of neighbourhood search described in the ANSPSO algorithm. By using two adaptive mechanisms described as above, the algorithm performance is improved. Two sets of benchmark functions are also used to evaluate the performance of the proposed APSOMNS algorithm. The experiment results are conducted show that the proposed APSOMNS algorithm is superior to other comparative PSO-based algorithms.2) Three algorithms of PSO’s application on data clustering.In this contribution, three clustering algorithms are proposed by incorporating PSO into K-means clustering method.Clustering is deemed one of the most difficult and challenging problems in machine learning, particularly due to its unsupervised nature. From an optimization perspective, it can be formally considered as a particular kind of grouping problem. Clustering is an unsupervised classification technique which partitions a set of objects in such a way that objects in the same clusters are more similar to one another than the objects in different clusters according to certain predefined criterion. Hierarchical and partitioning methods are the most popular clustering techniques. Hierarchical clustering finds a sequence of partitions where the algorithm starts from one group with all objects and is executed until singletons groups are found, or vice versa, whereas partitioning clustering directly divides data objects into some fixed number of clusters by using a suitable objective function. One of advantages of partitioning method is its ability to manipulate large datasets. In this dissertation, the research focuses on the partitioning method. When the number of clusters is known a prior, clustering may be formulated as distribution of objects in multi-dimensional space among groups in such a way that objects in the same cluster are more similar in some sense than those in different clusters, which involves minimization of some extrinsic optimization criterion.K-means clustering algorithm developed by Hartigan is one of the most popular and widely used clustering techniques because it is easy to implement and is efficient, with linear time complexity. However, it suffers from two major drawbacks. First, the performance of K-means algorithm is highly dependent on the initial values of cluster centroids. Second, the objective function of the K-means is non-convex and it may contain many local minima. Thus in the process of minimizing objective function, the solution might easily converge to a local minimum rather than a global minimum. In order to overcome these drawbacks, many algorithms have been developed over the years for clustering. To enhance the performance of K-means, various clustering methods based on K-means have been presented to overcome these drawbacks.Under this assumption, a large number of evolutionary algorithms for solving clustering problems have been proposed in the literature. These algorithms are based on the optimization of one or some objective functions (also called fitness function) that guides the evolutionary search.In the last decades, various clustering methods based on evolutionary algorithms have been designed for clustering problems and have shown to be promising alternatives [90]. Unlike K-means, EAs simultaneously optimize a population of candidate solutions, which gives them the ability to escape from local optima and to overcome sensitivity to initial points as well. Various EA-based clustering algorithms have been developed such as genetic algorithm, differential evolution, ant colony optimization, artificial bee colony, and particle swarm optimization (PSO).i) The first algorithm is called ANSPSO with K-means (ANSPSO-KM), where ANSPSO is the first improved PSO variant that this dissertation proposes. ANSPSO-KM is to solve the clustering problems, where the number of clusters known a priori. By incorporating with PSO, the K-means clustering algorithm is overcome its drawbacks such as easy trapped into local optima and sensitive to initial points. The performance of ANSPSO-KM is proven by experiments conducted on fourteen benchmark datatsets, where four artificial and ten real-world datasets. The experiments show that the proposed ANSPSO-KM obtained promising results. The experimental results also prove the effectiveness and efficiency of PSO on introducing to K-means for data clustering.ii) Similar to ANSPSO-KM, the second algorithms for data clustering is named APSOMNS with K-means (called APSOMNS-KM). It is for data clustering with number of clusters known in advance. The evaluation of the algorithm performance uses the fourteen benchmark datasets. Through the experimental results, it can be seen that the proposed APSOMNS-KM clustering algorithm is superior to other comparative clustering algorithms,iii) In fact, the number of clusters in actual clustering problems is often unknown. That is more difficult for clustering methods. The third algorithm proposed in the dissertation focuses on this kind of clustering problems. The algorithm is called PSO with K-means for dynamic clustering (DCPSONS). In this algorithm, the idea presented by M.G.H. Omran et al. and R.J. Kuo et al. is improved, where the binary PSO was first used to find the number of clusters, K-means was then applied to refine the centroid of the chosen clusters. Further, aim to improve the performance of PSO, the proposed DCPSONS approach still employs the neighbourhood search strategy and diversity mechanism, and combine with K-means clustering method. Thus, DCPSONS can automatically determine the optimal number of clusters and cluster the data set with minimal user interference.The performance of this algorithm is also verified by using fourteen benchmark datasets. The experimental results achieved from the proposed DCPSONS algorithm demonstrate higher accuracy rate in terms of cluster number as well as classification quality in comparison with other algorithms.3) Four algorithms of PSO’s application on image segmentation.The methodology of these proposed algorithms is to use the clustering method for building algorithms.Image segmentation is used to distinguish object from their background or to partition an image into related regions. It is defined as the process of subdividing an image into its constituent parts and extracting desired parts. The goal of segmentation is to simplify and/or change the representation of an image into something that is more meaningful and easier to analyze. Image segmentation is typically used to locate objects and boundaries (lines, curves, etc) in images. More precisely, image segmentation is the process of assigning a label to every pixel in an image such that pixels with the same label share certain characteristics. It is a fundamental component in many computer vision applications.There are various methods for image segmentation in the literature. The existing methods of image segmentation can be roughly divided into some following areas:threshold, edge detection, region splitting & merging and segmentation methods based on clustering algorithms such as K-means, FCM, IT2FCM, etc. The applicability of clustering methodology to the image segmentation problem was recognized over some decades ago, and the paradigms underlying the initial pioneering efforts are still in use today. Among them, segmentation methods based on clustering algorithms are to partition the similar regions of an image into one class as much as possible, and divided the dissimilar regions into different categories through certain criteria. In this dissertation, the research also focus on clustering algorithms to design segmentation algorithms.i) The first algorithm is a Hybrid Approach of Generalized FCM and PSO for Image Segmentation and is called GFCM-PSO. It is built based on incorporation if PSO and Fuzzy C-means (FCM). This method is to segment images, which are heavily corrupted by noise. In the GFCM-PSO algorithm, the PSO algorithm is introduced to GFCM algorithm proposed by H. Zhang. The experiments conducted by GFCM and some comparative algorithms on synthetic, Berkeley and real images show that the proposed method achieved better results and images with higher quality.ii) The second algorithm for image segmentation is the Fast Generalized FCM with PSO for Image segmentation and is called FGFCM-PSO. This method is built for images, which are corrupted by noise. The noise used in the experiments is Gaussian and salt&pepper and is generated by Matlab. The proposed algorithm is designed based on the ideas of FGFCM proposed by W. Cai et al. and S-FCM proposed by F. Zhao et al. In S-FCM algorithm proposed by F. Zhao et al., the membership degree values are modified for all data points in image X are modified during each iteration step. F. Zhao et al. pointed out that if the biggest membership degree value of xi, is close to 0.5, this data point may be located in the boundary of some clusters. However, S-FCM algorithm’s sensitivity to the factor β that affects the relationship between HCM’s fast convergence speed and FCM’s good clustering performance, in the proposed method, the factor β is calculated based on Gaussian distribution. According to FGFCM, firstly, the new image ζ, is formed. Then PSO is introduced into FCM and is applied on new image ζ to segment image, where the membership degree values um is modified by using optimal-selection-based strategy improved from S-FCM.The experimental results conducted on synthetic, Berkeley and real images indicate that the proposed method acquired good performance on image segmentation,iii) The third algorithm is to apply the proposed DCPSONS clustering, that is built for dynamic clustering, to segment image, where the number of segments (or clusters) unavailable. The results achieved from the proposed algorithm on synthetic and nature images are better than other comparative methods in terms of accuracy on cluster number and the quality of segmented image.iv) The fourth algorithm for image segmentation is designed based on the Interval Type-2 Fuzzy C-means (IT2FCM) method and PSO and is called IT2FCM-PSO. IT2FCM is a clustering algorithm, which is appropriate to uncertain problems. It was designed based on Type-2 Fuzzy set and Fuzzy C-means. The Type-2 Fuzzy set, an extension of Type-1 Fuzzy set, has a secondary membership to define the possibilities of the primary membership. Thus, the performance of Type-2 Fuzzy set to handle uncertainties is enhanced. In addition, Interval Iype-2 Fuzzy C-means (IT2FCM) developed a step in the clustering method in which footprint of uncertainty (FOU) was created for the fuzzifier using two parameters m1 and m2 for handling of uncertainty, making clustering more efficiently. In this algorithm, PSO is introduced to IT2FCM to aim to overcome and enhance the performance of IT2FCM. The experimental results demonstrate a good performance of the proposed IT2FCM-PSO algorithm in comparing with other image segmentation methods.In general, the advantages of improved PSO are used for designing the proposed PSO-based algorithms in the dissertation. The experiments on numerical optimization problems as well as applications on data clustering and image segmentation have proven the effectiveness and efficiency of the techniques on improving PSO.