From Optimization to Clustering: A Swarm Intelligence Approach

From Optimization to Clustering: A Swarm Intelligence Approach

Megha Vora (Anna University, India) and T. T. Mirnalinee (Anna University, India)
DOI: 10.4018/978-1-5225-0788-8.ch058


In the past two decades, Swarm Intelligence (SI)-based optimization techniques have drawn the attention of many researchers for finding an efficient solution to optimization problems. Swarm intelligence techniques are characterized by their decentralized way of working that mimics the behavior of colony of ants, swarm of bees, flock of birds, or school of fishes. Algorithmic simplicity and effectiveness of swarm intelligence techniques have made it a powerful tool for solving global optimization problems. Simulation studies of the graceful, but unpredictable, choreography of bird flocks led to the design of the particle swarm optimization algorithm. Studies of the foraging behavior of ants resulted in the development of ant colony optimization algorithm. This chapter provides insight into swarm intelligence techniques, specifically particle swarm optimization and its variants. The objective of this chapter is twofold: First, it describes how swarm intelligence techniques are employed to solve various optimization problems. Second, it describes how swarm intelligence techniques are efficiently applied for clustering, by imposing clustering as an optimization problem.
Chapter Preview


The concept of optimization is as ageless as time and is in-built in the nature of the universe. It begins in the microcosm where atoms try to form bonds in order to minimize the energy of their electrons. It can also be seen in the Darwinian principle of survival of the fittest which, together with biological evolution, leads to better adaptation of species to their environment. Here, a local optimum is a well-adapted species that dominates all other animals in its surroundings. Optimization also plays a significant role in our daily life. We strive to achieve the best under given circumstances. Instances of these are finding shortest route, optimal budgeting, maximizing profit and sales while keeping cost as low as possible etc. (Xin-SheYang, 2010). Optimization is the collection of mathematical principles and methods used for solving quantitative problems in many disciplines, including physics, biology, engineering, economics and business. The goal of optimization is to find the best possible elements x from a set X according to a set of criteria. These elements are expressed as mathematical functions, the so-called objective functions. Thus optimization finds the most suitable value for a function (called objective function) within a given domain.

Optimization is the core to many real world problems. Numerous techniques have been proposed to solve optimization problems viz. linear programming, quadratic programming, integer programming, nonlinear programming, dynamic programming, simulated annealing, evolutionary algorithm etc. (Rao, 2009). Evolutionary algorithms have shown a great success in solving complex optimization problems. Evolutionary algorithm comprises number of different algorithms viz, genetic algorithm, genetic programming, evolutionary programming, gene expression programming and differential evolution. Among these genetic algorithm is most popular and widely used in practice. Genetic algorithms (GA) (Goldberg & Sastry, 2007) are robust. It is based on Darwin’s principle of natural selection and genetic inheritance. Genetic algorithm can be straightforward applied to solve multidimensional and multimodal optimization problem. The main advantage of this algorithm is that no extra information such as continuity and/or, differentiability of objective function constraint is required while solving the problem. GA works with a population of candidate of solution. A population of randomly chosen candidate solution is constructed and objective function values are evaluated corresponding to these solution. Every solution is assigned a fitness value. The population of chromosome is evaluated using three operators: selection, crossover and mutation. Although two parent crossovers is widely used in practice, a good number of multi-parent crossover is widely used such as unimodal distribution crossover (UDIX) (Ono, Kita, & Kobayashi, 2003), simplex crossover (SPX) (Tsutsui, Yamamura, & Higuchi, Multi-parent Recombination with Simplex Crossover in Real Coded Genetic Algorithms, 1999), parent centric crossover (PCX) (Deb, Anand, & Joshi, 2002) and triangular crossover (TC) (Elfeky, Sarker, & Essam, 2008). Since their introduction, GAs has frequently being applied as a search and optimization tool in numerous applications in engineering and science (Vasant & Barsoum, Hybrid genetic algorithms and line search method for industrial production planning with non-linear fitness function., 2009) (Vasant, A Novel Hybrid Genetic Algorithms and Pattern Search Techniques for Industrial Production Planning,, 2012)(Leng & Chen, 2012) (Hutterer & Affenzeller, 2013)(Murray, Walsh, Kelliher, & O’Sullivan, 2014) .

Complete Chapter List

Search this Book: