Particle Swarm Optimization in Bioinformatics, Image Processing, and Computational Linguistics

Introduction

The field of optimization aims at deriving a set of optimal solutions for given real valued function(s). Over the years, it has remained one of the major research frontiers in the field of mathematics and computer science.

There are a number of limitations that constrain the performance of an optimization algorithm, with the major ones being (a) nature of the problem, (b) domain and range of the functions being optimized, and (c) time, space and computational bounds. Optimization problems are of two types: test functions, and real-world problems, such as mechanical design problems, transmission network management, vehicle routing optimization problem, power system operation problems, to name a few (Kaveh & Talatahari, 2009; Zahara & Kao, 2009; Galiana et al., 2003; Mahmoudi & Zhou, 2016; Kheshti & Ding, 2017) Some of the well-known test functions¹ are the highly multimodal Ackley function, Schwefel function and the extremely nonlinear Schaffer's f6 function. The reliability and efficiency of such optimization algorithms is usually checked against these set of existing benchmark functions that can also be modified to test the algorithm's robustness.

Optimization algorithms can be broadly categorized into two main categories; (a) Exact Optimization and (b) Heuristic Optimization algorithms. The former aims to obtain the exact optimum solution(s) of a problem; while the latter outputs a well-approximated non-optimal solution(s) for the exact optimal solution(s). Exact algorithms (Rothlauf, 2011) like numerical methods (Newton-Raphson method, for example), dynamic programming, non-linear programming, branch and bound algorithms etc. produce optimal solutions but are inefficient for solving real world problems which are highly constrained, multimodal, time-varying and multidimensional. Heuristic algorithms are usually preferred over the exact algorithms due to limitations of computational power and time. Therefore, they are the preferred choice of optimization methods to solve problems that have non-polynomial time complexity and hence gradually become intractable with increasing scale of the problem. Particle Swarm Optimization (PSO) (Eberhart & Kennedy, 1995) is one of the notable heuristic search methods without any concrete mathematical proof of its convergence to exact global optima.

The well-known heuristic methods (Silver, 2004) developed take inspiration from the characteristics of natural occurrences or organisms such as annealing in metallurgy, biological evolution, behavior of bird flocks, schools of fish, colonies of ants and swarms of bees. Such nature-inspired heuristics can be divided into (a) Single-solution based and (b) Population based. The former, comprising of algorithms such as simulated-annealing (Laarhoven & Aarts, 1987), iterated local search(Lourenco &Stutzle, 2003) and variable neighborhood search (Mladenovic & Hansen, 1997), randomly select an initial candidate solution, which is simply a position in the search space of the problem, and then improve upon this single solution to reach the required optimum. On the other hand, any population based algorithm generates multiple such candidate points that are randomly spread across the entiredomain as much as possible. It then proceeds to iteratively improve the solutions by taking into consideration the fitter positions found by the population and combine the candidates to arrive at the final optimal solution. The function to be optimized is taken as a measure of fitness. It is to be noted that both the above mentioned categories do not guarantee that solution returned is the global optimal solution.