Abstract
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.
TopIntroduction
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) .
Key Terms in this Chapter
Optimization: Optimization is the process of finding the conditions that give the maximum or minimum of a function. It is an act of obtaining the best result under given circumstances.
Cluster Validity Index: Cluster validity Index is the measure of how good the clustering is.
Beta Index: It computes the ratio of total variation and within class variation. For a given data set higher is the beta value better is the clustering.
Multi-Objective Optimization: Multi-objective optimization involves more than one objective function to be optimized simultaneously. The task is more challenging as it results in a number of solutions with different trade-offs among criteria, also known as Pareto optimal or efficient solutions.
Fitness Function: Quantifies the performance of particle.
Topology: Topology determines the way in which the constitute parts (in this context particles) are interrelated or arranged and how they communicate and share information with each other.
Global Optimization vs. Local Optimization: Global optimization refers to finding the optimal value of a given function among all possible solution whereas local optimization finds the optimal value within the neighboring set of candidate solution.
Objective Function: An objective function is one which we want to minimize or maximize.
Pheromone: Pheromone is a type of chemical emitted by ants and other organism which act as a medium to communicate between members of the same species.
Clustering vs. Classification: Clustering deals with unlabeled data i.e., no class labels is provided. It does not involve any training. On the contrary classification is a two-step process training and testing. During training it deals with label data while it deals with unlabeled data for testing.
Swarm/Population: Swarm refers to a flock of birds, school of fishes swarming bee/ants/insects.