Keywords

1 Introduction

1.1 Background

Swarm intelligence is a field of artificial intelligence (AI) that gained high popularity over last couple of years [1]. Swarm intelligence gets inspiration from the collective behavior of social swarms of bees, ants, worms, termites, schools of fish and flock of birds. Although the main constituent of these swarms is the individuals, a coordinated behavior exists among these individuals that assist them in obtaining their desired goals. A self-organizing behavior exists inside the whole system which is the result of this coordinated behavior and swarm intelligence or collective intelligence and a simple rule based interaction of multi-agent systems. A coordinated interaction among different individuals in the swarm performs this well-managed behavior.

A trade-off is required between the collection of new information (Exploration) and the use of existing information (exploitation) during the search of new food sources [2]. The process of exploration and exploitation is used by the bee colony for maximizing the nectar amount and minimizing the foraging efforts. A collective behavior is shown by the swarm of individuals for foraging, reproduction, living and division of important tasks among the available individuals. In fact, a decentralized manner by individuals based on local information collected from the environment is used for decision making.

Swarm intelligence is a research field which is concentrated on the collective behavior inside a decentralized and self-organized system. Beni and Wang [3] used this term for the first time in the sense of cellular robotic system that consists of simple agents organizing themselves using neighborhood interaction system. Recently, the swarm intelligence methods have been applied in the robot control systems, solving optimization problems, load balancing and routing in new mobile telecommunication networks, demanding flexibility and robustness. Examples of swarm intelligence methods used for solving optimization problems include PSO (Particle swarm optimization) [4], ant colony optimization (ACO) [5], artificial bee colony optimization (ABC) [6,7,8]. Recently, some more advanced swarm intelligence optimization algorithms e.g. cuckoo search [9], firefly algorithm (FA) [10], bat algorithm [11], krill herd bio-inspired optimization algorithm [12] and clustering algorithms [13] have been introduced.

1.2 Firefly Algorithm (FA)

Firefly algorithm is one of the most recently introduced swarm intelligence technique developed by Yang [10] by taking inspiration from flash light signals which is the source of attraction among fireflies for potential mates. All the fireflies are unisexual and attract each other according to the intensities of their flash lights. Higher the flash light intensity, higher is the power of attraction and vice versa. For solving optimization problem, the brightness of flash is associated with the fitness function to be optimized. The light intensity I(r) of a firefly at distance r is given by Eq. (1):

$$ {\text{I}}\left( {\text{r}} \right) = \frac{{I_{0} }}{{r^{2} }} $$
(1)

where I 0 is the intensity of light at source. With the fixed light absorption coefficient γ of the medium, the intensity of light I at distance r is given by Eq. (2):

$$ {\text{I}} = {\text{I}}_{0} { \exp }\,\left( { -\upgamma{\text{r}}^{2} } \right) $$
(2)

where r represents the distance between the fireflies in the firefly algorithm. Since the attractiveness of the fireflies by the adjacent fireflies is directly proportional to the intensity of light of the fireflies, the attractiveness of a firefly by another firefly is given by the Eq. (3):

$$ {\rm B} =\upbeta_{0} { \exp }\,\left( { -\upgamma{\text{r}}^{\text{m}} } \right)\,\left( {{\text{m}}\, \ge \,1} \right) $$
(3)

where β 0—represents the attractiveness at distance r = 0. The distance between two fireflies’ x i and y j called as Euclidian distance is given by Eq. (4):

$$ {\text{r}}_{\text{ij}} = \left| {{\text{x}}_{\text{i}} - {\text{y}}_{\text{j}} } \right| = \sqrt {\mathop \sum \limits_{k = 1}^{d} \left( {x_{i,k} - y_{j,k} } \right)^{2} } $$
(4)

In each generation, the position of the firefly can be changed according to the following Eq. (5):

$$ {\text{X}}_{\text{i}} = {\text{x}}_{\text{i}} +\upbeta_{0} { \exp }\,\left( { -\upgamma{\text{r}}_{\text{ij}}^{2} } \right)\,\left( {{\text{x}}_{\text{i}} - {\text{y}}_{\text{j}} } \right) +\upalpha \upvarepsilon $$
(5)

where α represents the parameter of randomization, ε represents random number generated in Gaussian distribution.

To overcome the problem of balancing between the exploration and exploitation, many researchers introduced modifications in the standard FA to improve its efficiency. The improved versions of FA were introduced by the authors in [14,15,16]. All these authors introduced a single point modifications in some parts of the FA e.g. some authors modified the random movements of the FA, some authors brought some changes in the light absorption coefficient factor whereas other authors modified the step size of the firefly changing position equation. All these authors have addressed one or other issue mentioned earlier but failed to address all these problems identified in the FA. To balance the exploration and exploitation of the FA, many researchers have hybridized the FA with other optimization algorithms. FA has been used by the authors in [17,18,19] in hybrid mechanism with other optimization algorithms. In these approaches, the authors have used FA for exploration and other optimization algorithms for exploitation purposes or the other algorithms for exploration and FA for exploitation purposes but all these authors have not properly addressed the issues raised in the standard FA. In our work, we will develop a new hybrid firefly algorithm which will eliminate the major drawbacks for getting the most optimal value or at least the values better than the standard firefly algorithm when solving optimization problems.

2 Proposed Approach

The standard firefly algorithm, different modifications introduced in different parts of firefly algorithm and its different hybrid approaches suffer from three major drawbacks. The initial solution is generated randomly that results in imbalanced exploration and exploitation at this stage. The solution is trapped into local optima if the randomization factor in firefly changing position is very small and may skip the best solution if this is very large. Thirdly, if the maximum generation reaches and the solution obtained is not the most optimal solution. The improved hybrid approach is based on hybridization of three algorithms namely genetic algorithm, firefly algorithm and pattern search which will overcome all these three drawbacks. The newly introduced approach is called GA-FA-PS. The proposed approach is developed using following steps.

  • Step 1: Initial Population Generation

The initial population is generated randomly using the dependent and independent variables. The independent variables represent the variables to be optimized. The dependent variable represents the function to be optimized.

  • Step 2: Applying Genetic Algorithm

After the initial population is generated randomly, the independent and dependent variables are given as input to the genetic algorithm to represent genes and chromosomes of genetic algorithm. Genetic algorithm is a bio-inspired optimization approach that is inspired from the behavior transferring phenomenon of parents into children using heredity characteristics. Different types of characters are transferred from parents into children using various types of operators e.g. selection, mutation and cross over operators.

  • Step 3: Fitness function evaluation

After the assignment of independent and dependent variables, the fitness of each individual which represents the fitness value of the function to be optimized is evaluated.

  • Step 4: Generate the solution set for firefly algorithm

The genetic algorithm is run for a fixed number of iteration to generate the initial solution set for the firefly algorithm.

  • Step 5: Specification of fireflies and light intensities

From the solution set generated in step 4, assign the values of independent variables to fireflies and the dependent variable to light intensity associated with each firefly.

  • Step 6: Firefly changing position

During running the firefly algorithm, if the solution is not improved after few generations, modification is brought by introducing the cross over operator to enhance the exploitation at this stage.

  • Step 7: Firefly algorithm termination

The firefly algorithm is run for maximum number of generation and then terminated.

  • Step 8: Embed pattern search

If the maximum number of generations of firefly algorithm reaches and the solution obtained is not the most optimal solution, then the pattern search algorithm is introduced to further enhance the exploration and exploitation of the solution search space to obtain the most optimal solution or at least the solution better than the so far obtained solution. Pattern search is a kind of optimization algorithm having strong capability of solving various kinds of optimization problems where other standard optimization algorithms face failure in finding the most optimal solution. Its easy implementation, conceptual simplicity and computational efficiency make it more applicable than the other optimization techniques.

The proposed approach is shown in Fig. 1.

Fig. 1.
figure 1

Proposed approach

Full size image

3 Experimental Setup

All the experiments were carried out using Core i3 with Windows 7 and Matlab 2015a installed on it. The detailed description of the whole experimental setup is given in this section. Different parameters of GA, FA and the proposed GA-FA-PS approaches are shown in Table 1.

Table 1. Comparative analysis of the proposed approach with other algorithms
Full size table

GA parameters

FA parameters

GA-FA-PS parameters

Maximum generations

200

MaxIt

200

MaxIt

200 (GA = 60, FA = 70, PS = 70)

Population

80

nPop

30

nPop

30

Cross over

One point cross over

Gamma

1

Gamma

1

Cross over probability

0.9

Beta

2

Beta

2

Mutation rate

0.1

Alpha

0.2

Alpha

0.2

Selection method

Rank based selection

Alpha_damp

0.98

Alpha_damp

0.98

3.1 Test Functions

For testing the performance of the proposed GA-FA-PS approach, three numerical benchmark functions namely Ackley’s function, Rosenbrock’s function and sphere functions were used in the experiments [20]. The global optimal value and the range of parameters are described as follow.

3.1.1 Ackley’s Function

Ackley’s function is a type of multimodal function mainly applied for testing the performance of the optimization algorithms and expressed by the following mathematical Eq. (6):

$$ {\text{f}}\,1\,\left( {\text{x}} \right) = - 20\,*\,{ \exp }\,[ - 0.2\sqrt {(\frac{1}{d} \mathop \sum \limits_{i = 2}^{d} x_{i}^{2} )} ]{-}{ \exp }\,*\,[\frac{1}{d}\mathop \sum \limits_{i = 2}^{d} \cos \left( {2pi\,*\,x_{i} } \right)] + \left( {20 + {\text{e}}} \right) $$
(6)

where the global minima for this function has been set to 0 in the range of [−50, 50]d where d represents the dimensions of problem and i = (1, 2, …, d).

3.1.2 Rosenbrock’s Function

Rosenbrock is a type of unimodal optimization function with mathematical representation by Eq. (7):

$$ {\text{f}}2\,\left( {\text{x}} \right) = \mathop \sum \limits_{i = 1}^{d - 1} \left[ {\left( {1 - x_{i} } \right)^{2} + 100\,*\, (x_{i + 1} - x_{i}^{2} )^{2} } \right] $$
(7)

The initial range for this function has been set to [−120, 120]d whereas the global minima for this function has been set to −5 to test the efficiency of the proposed optimization approach.

3.1.3 Sphere Function

The sphere function is given by Eq. (8):

$$ {\text{f}}3\,\left( {\text{x}} \right) = \mathop \sum \limits_{i = 1}^{d} x_{i}^{2} $$
(8)

The initial range for this function has been set to [−100, 100]d whereas the global minima has been set to −10.

3.2 Results

The proposed approach has been compared with the standard firefly algorithm and the standard genetic algorithm. For making proper comparison and meaningful analysis, extensive experimentation has been carried out. All of the three algorithms namely genetic algorithm, standard firefly algorithm and the proposed GA-FA-PS algorithms have been run 20 times and the results are shown in Table 1. The proposed approach was compared with the standard FA and GA by computing their best case, average best case, worst case and average worst case as shown in Table 1.

It is evident from the above table that the proposed approach outperforms both the FA and GA algorithms for all the three benchmark functions namely Ackley, Rosenbrock and Sphere functions.

3.3 Convergence

The convergence rate of the three algorithms is shown in Figs. 2, 3 and 4 respectively.

Fig. 2.
figure 2

Convergence rates of GA, FA and GA-FA-PS for Ackley’s function

Full size image
Fig. 3.
figure 3

Convergence rates of GA, FA and GA-FA-PS for Rosenbrock’s function

Full size image
Fig. 4.
figure 4

Convergence rates of GA, FA and GA-FA-PS for sphere function

Full size image

Figure 2 shows the convergence rates of genetic algorithm, standard firefly algorithm and the proposed approach.

In the convergence of the three algorithms, up to iteration 60, the lowest convergence has been observed for genetic algorithm followed by firefly algorithm and the proposed approach, respectively. After iteration 80, there is continuous improvement in the convergence rate of the proposed algorithm with sharp improvement after iteration 135 with the introduction of pattern search for bringing improvement.

Figure 4 shows the convergence rate of the genetic algorithm, firefly algorithm and the proposed approach. For the sphere function, the proposed approach has sudden changes in the convergence rate for getting the most optimal value.

4 Conclusion

In this paper, a new hybrid algorithm of firefly algorithm in combination with the genetic algorithm and pattern search has been developed. In the proposed approach, the initial solution set was generated by genetic algorithm. To further enhance the convergence rate of the firefly algorithm, arithmetic cross over operator was introduced in firefly changing position. Pattern search was applied to further improve the solution quality of the firefly algorithm. The proposed approach was tested on three benchmark optimization functions namely Ackley’s function, Rosenbrock and sphere function. The performance of the proposed approach was compared with the genetic algorithm and standard firefly algorithm. The developed algorithm outperforms both of these algorithms in terms of local and global convergence rate that results into better solution quality.