Multidimensional particle swarm optimization and applications in data clustering and image retrieval

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