Robotics and Automation Engineering Journal

Swarm Intelligence Algorithms as the Promising Tool for Solving Optimisation Problems

Nafrizuan Mat Yahya*

Faculty of Manufacturing Engineering, University Malaysia Pahang, Pahang, Malaysia

Submission: July 19, 2017; Published: September 22, 2017

*Corresponding author: Nafrizuan Mat Yahya, Faculty of Manufacturing Engineering, University Malaysia Pahang, Pahang, Malaysia, Tel: +6018-6652051, Email: nafrizuanmy@ump.edu.my

How to cite this article: Nafrizuan M Y. Swarm Intelligence Algorithms as the Promising Tool for Solving Optimisation Problems. Robot Autom Eng J. 2017; 1(4): 555567.

DOI: 10.19080/RAEJ.2017.01.555567

Keywords: Genetic algorithm (GA); Evolutionary strategy (ES); Evolutionary programming (EP); Genetic programming (GP); Differential evolution (DE); Bacterial foraging optimisation (BFO); Artificial bee colony (ABC); Particle swarm optimisation (PSO); Ant colony optimization (ACO); Artificial immune system (AIS); Bat Algorithm (BA)

Introduction

A quote by George Bernhard Dantzig, a famous American mathematical scientist who made important contributions to operations research, computer science, economics, and statistics [1]: “True optimisation is the revolutionary contribution of modern research to decision processes”. Optimisation according to the definition of Merriam-Webster Dictionary Merriam-Webster [2] is an act, process, or methodology of making something (as a design, system, or decision) as fully perfect, functional, or effective as possible.

In general, optimisation is the process of obtaining either the best minimum or maximum result under specific circumstance Singiresu [3], Xin-She & Suash [4]. Sanghamitra & Sriparna [5], Statnikov et al. [6], Xin-She [7] added that the optimisation process engages with defining and examining objective or fitness function that suits some parameters and constraints. Nowadays, a vast range of business, management and engineering applications utilise the optimisation approach to save time, cost and resources while gaining better profit, output, performance and eficiency.

Optimisation problems can be divided into two categories: continuous and combinatorial (discrete) Laszlo [8]. A combinatorial optimisation problem has a finite number of solutions but this is not in the case with a continuous optimisation problem where the number of solutions is infinite. This research concentrates only on continuous optimisation problems. So in this thesis, optimisation will refer solely to continuous optimisation problems.

Normally, the optimisation problems can further be classified into two major types namely; single objective optimisation and multi objective optimisation. Naturally, solving a single objective optimisation is about finding an optimised solution to the problem at hand based on the single objective. Multi objective optimisation, on the other hand, is multifaceted and solving the problem is to seek compromised solutions based on a set of conflicting objectives Castro-Gutierrez et al. [9], Dragan & Parmee [10], Ivan [11], Xin-She [12]. As there will be no unique solution to a multi objective optimisation problem Ngatchou et al. [13], a set of ‘trade-o’ solutions, referred to as Pareto optimum solutions, compromising the objectives is produced Coello [14], Zhou et al. [15].

Meanwhile, the single objective optimisation can be designated as either unconstrained or constrained depending on whether or not the problem contains constraints. Conn et al. [16] elaborates the unconstrained single objective optimisation problem (or widely known as single objective optimisation problem) as a problem that has no constraints specified on the variables and usually is less complicated. However, a constrained single objective optimisation problem (or widely referred as constrained optimisation problem) comes with lack of explicit mathematical formulation but has discrete definition domains, mixed with continuous and discrete design variables and also strong nonlinear objective functions with multiple complex constraints Leticia [17], Harish [18], Fei et al.[19].

According to Seok & Zong [20], over the past forty years, many techniques have been established to solve different optimisation problems efficiently. On the words of Jones et al. [21]; many optimisation problems work with mathematical or numerical linear and nonlinear programming methods and use simple and ideal models to get the optimum result. However, stressed that the numerical optimisation method tends to improve the solution locally which is different from a real world problem, often more complex and unpredictable. In addition, due to their computational drawbacks, plus the requirement of substantial gradient information, traditional numerical programming strategies have been incapable of solving any optimisation problem consistently Sadollah et al. [22].

Due to stated limitations and other downsides as listed by Coello [14], the alternative prospect to solve an optimisation problem is by heuristic or metaheuristic method Liqun et al. [23], Tsung-Jung [24], Jacqueline & Richard [25]. Even though the metaheuristic methods are computationally laborious and give no guarantee of the quality of the results as stated by Xin- She [7], the methods are still in the top ranking of optimisation solving tools. Metaheuristic methods offer significant advantages such as; easy to develop and implement, with a broad range of applicability, able to give a global perspective to the problem domains that are needed to be solved Afshar et al. [26] and the convergence rate of the global or nearly global optimum results are better than other optimisation approaches Ali [27].

For the past decades, evolutionary algorithms that are part of metaheuristic methods have become popular among the researchers to deal with the complexity of a wide variety of single and multi objective optimisation problems Wenyin et al. [28], Yong et al. [29], Xin-She & Gandomi [30]. Evolutionary algorithms have been derived from a combination of a set of rules or restrictions and randomness by populations in generations. Evolutionary algorithms imitate or simulate the successful characteristics of natural phenomena of physical systems (e.g. simulated annealing algorithm) or biological systems (e.g. animal behaviours-based algorithms) Ricardo & Coello [31].

Evolutionary algorithms offer some advantages. According to Alex et al. [32], the major advantages of evolutionary algorithms are that they are very good in general applicability that cover the vast range of problems as well as prior knowledge of the problem considered as inessential. An evolutionary algorithms only needs an explicit or implicit objective function to optimise the problem Janez et al. [33], Qie & Ling [34]. An evolutionary algorithm kicks off with some guessed solutions, updates solutions in a synergistic manner then navigates the search agents to balance between exploitation of good found- so-far positions and exploration of new anonymous search positions toward the optimum global solution Janez et al. [33], Qie H & Ling [34], Hui et al. [35], Mezura-Montes E & Coello [36], Zhang et al. [37]. Alex et al. [32] divided the evolutionary algorithms to some sub-fields. The sub fields include Genetic Algorithm (GA) by Holland in 1975, Evolutionary Strategy (ES) by Rechenberg in 1965, Evolutionary Programming (EP) by Fogel in 1966, Genetic Programming (GP) by Koza in 1992 and Differential evolution (DE) by Storn and Price in 1995.

Among most popular evolutionary algorithms that have already captured the attention of researchers today are swarm intelligence algorithms. Swarm intelligence algorithms are inspired by the collective behaviour of swarms through a complex interaction between individuals and their neighbourhood with nature such as a colony of ants, bacteria, bees, bats, birds and fishes Leandro & Viviana [38], Erik & Miguel [39], Adil et al. [40]. In general, swarms have selforganisation and decentralised control features and all the swarm follows the same system where a population of swarm cooperates and interacts with each other in the group and the environment under certain rules during foraging or socialising. The most remarkable features of any swarm intelligence algorithm are that it has advantages of memory, diverse multicharacters capability, rapid solution improvement mechanism and is adaptable to internal and external changes Erik & Miguel [39], Harish [18].

There are some well-known swarm intelligence algorithms developed over the past two decades. Kennedy & Eberhart [41] pioneered Particle Swarm Optimisation (PSO) algorithm that simulates the social behaviour and choreography of a bird flock. It was followed by Ant Colony Optimisation (ACO) algorithm by Marco [42]. The algorithm simulates the activity of ants while seeking a path to a food source. In micron scale of swarm intelligence algorithms, the characteristics and behaviour of the vertebrate immune system have led Hofmeyr & Forrest [43] to develop an Artificial Immune System (AIS) algorithm. Passino [44] successfully imitated the social foraging behaviour of Escherichia coli (E. -coli) for search of nutrients with the Bacterial Foraging Optimisation (BFO) algorithm.

In 2007, the Artificial Bee Colony (ABC) optimisation method that was modelled from a colony of bee raised attention of research community after developed by Dervis & Bahriye [45]. Then, Timothy et al. [46] initiated Roach Infestation Optimisation (RIO) algorithm that was inspired from social characteristics of an intrusion of cockroaches. Later, Xin- She [47] introduced Bat Algorithm (BA) which imitated the echolocation of bats to find prey with different levels of pulse and loudness emitted. The algorithm was the third from him after a Cuckoo Search (CS) algorithm Xin-She & Suash [48] encouraged from compellation of social parasitism practised by a group of cuckoo and the firefly algorithm (FA) Xin-She [49] idealised from the flashing behaviour of fireflies a year before.

Tawfeeq [50] also utilised the concept of echolocation of bats to find prey to develop a new swarm intelligence algorithm. Different from the algorithm developed by Xin-She [47] as cited before, this algorithm models the principles of bats sonar used in echolocation to search for the optimum solution to a speci c problem Tawfeeq [50]. It is worth mentioning, to strengthen the swarm intelligence algorithms or to cater for a specific problem, the versions of swarm intelligence algorithms hybridised between each other or with other conventional approaches have also existed.