Multidimensional particle swarm optimization and applications in data clustering and image retrieval
Moncef Gabbouj · 2010
Particle swarm optimization (PSO) was introduced by Kennedy and Eberhart in 1995 as a population based stochastic search and optimization process. The natural behavior of a bird flock when searching for food is simulated through the movements of the individuals (particles or living organisms) in the flock. The goal is to converge to the global optimum of some multidimensional function. PSO is conceptually related to other evolutionary algorithms such as Genetic Algorithms, Genetic Programming, Evolution Strategies, and Evolutionary Programming. In this talk, we present two novel techniques, which extend the basic PSO algorithm. The first algorithm called multi-dimensional PSO (MD PSO) deals with problems in which the dimension of the solution space is not known apriori (recall that PSO and most evolutionary algorithms assume a fixed dimension). M-D PSO includes two interleaved PSO iteration processes, a positional PSO (equivalent to the basic PSO operation) followed by a dimensional PSO in which the dimension of a particle is allowed to vary. In a multidimensional search space where the optimum dimension is unknown, swarm particles can seek both positional and dimensional optima. Since the backbone of MD PSO is the basic PSO, it is still susceptible to premature convergence, especially at high dimensions. To address this problem, we propose a second extension of the basic PSO algorithm, called Fractional Global Best Formation (FGBF) technique. Instead of being guided by the best particle in the swarm (the member of the swarm that achieves the best value of the objective so far) a new particle is created whose j'th component is the best corresponding component of all particles in the whole swarm (i.e. a component-wise best particle). The new particle is essentially a better guide to the swarm than PSO's native global best, since it makes use of the larger diversity existing between the components of the swarm particles. In order to validate the proposed algorithms, the techniques are applied in two well-known domains, nonlinear function minimization and data clustering. An extensive set of experiments shows that in both application domains, MD PSO equipped with FGBF exhibits an impressive speed gain and converges to the global optima at the true dimension regardless of the search space dimension, swarm size, and complexity of the problem. MD-PSO has recently been used in a novel application to automatically design Artificial Neural Networks (ANNs) by evolving the network to the optimal configuration(s) within an architecture space [3], The optimum dimension converged at the end of a MD PSO process corresponds to a unique ANN configuration where the network parameters (connections, weights and biases) can then be resolved from the positional optimum reached on that dimension. The architecture space is defined over feed-forward, fully-connected ANNs so as to use the conventional techniques such as back-propagation and some other evolutionary methods in this field. In another application, MD-PSO was used to extract perceptual dominant colors in a content-based image retrieval application. Extracting dominant colors that are prominent in a visual scene is of utmost importance since the human visual system primarily uses them for perception and similarity judgment. In this application, dominant color extraction is addressed as a dynamic clustering problem and MD-PSO is used for finding the optimal number of dominant colors in a given color space, distance metric, and a proper validity index function. In order to extract perceptually important colors and to further improve the discrimination factor for a better clustering performance, an efficient color distance metric, which uses a fuzzy model for computing color (dis-) similarities over HSV (or HSL) color space is proposed. The comparative evaluations against MPEG7 dominant color descriptor show the superiority of the proposed technique. Finally, we present another application of MD-PSO in macroinvertebrate biomonitoring, Aquatic ecosystems are facing a growing number of human induced changes and threats, and macroinvertebrate biomonitoring is particularly efficient in pinpointing the cause-effect structure between slow and subtle changes and their detrimental consequences in aquatic ecosystems. In this application, we focus on classification and data retrieval that are instrumental when processing large macroinvertebrate image datasets. To accomplish this for a routine biomonitoring, we propose an automated and highly accurate river macroinvertebrate classifier using evolutionary RBF networks. MD-PSO is used to find the best classifier, which is trained over a dataset of river macroinvertebrate specimens. The classifier is then used in the content-based indexing and retrieval (MUVIS) framework [6] for efficient search and retrieval of particular macroinvertebrate peculiars. Classification and retrieval results present such a delicate accuracy that can match experts' ability for taxonomic identification.