Acceleration for Fireworks Algorithm Based on Amplitude Reduction Strategy and Local Optima-Based Selection Strategy

Abstract

We propose two strategies for improving the performance of the Fireworks Algorithm (FWA). The first strategy is to decrease the amplitude of each firework according to the generation, where each firework has the same initial amplitude and decreases in size every generation rather than by dynamic allocation based on its fitness. The second strategy is a local optima-based selection of a firework in the next generation rather than the distance-based selection of the original FWA. We design a set of controlled experiments to evaluate these proposed strategies and run them with 20 benchmark functions in three different dimensions of 2-D, 10-D and 30-D. The experimental results demonstrate that both of the two proposed strategies can significantly improve the performance of the original FWA. The performance of the combination of the two proposed strategies can further improve that of each strategy in almost all cases.

1 Introduction

Swarm intelligence has attracted the attention of many researchers because of its simplicity, robustness, parallelism and others. It simulates the mutual cooperation among simple individuals to achieve complex social behavior, such as in particle swarm optimization (PSO) [1] and ant colony optimization [2]. The fireworks algorithm (FWA) [3] is an emerging swarm intelligence algorithm proposed in 2010, which repeatedly simulates the explosion of fireworks to find the optimal solution.

Some improved versions of FWA have subsequently been proposed. For example, the enhanced fireworks algorithm (EFWA) [4] improves several operations of the original FWA and can achieve a better performance. Dynamic FWA (dynFWA) [5] uses a dynamic explosion amplitude for the currently best firework.

Although these modifications versions of FWA have improved the performance of the original FWA, there are still some limitations, and many researchers are still trying to propose new improvements.

The objective of this paper is to propose two strategies and improve the performance of the original FWA with the same cost consumption. The first approach used to attain this objective is to decrease the amplitude of each firework in accordance with the firework’s generation rather than its fitness in order to achieve a good balance between exploration and exploitation. The second approach proposes a local optima-based selection strategy to keep the diversity of the population instead of the distance-based selection used in original FWA. We compare the performances of each proposal and their combination together with the original FWA.

We introduce the framework of original FWA and propose our two new strategies in Sect. 2. Then, we evaluate them compared with the original FWA using 20 benchmark functions of 3 different dimensions in Sect. 3. Finally we discuss the experimental evaluations in Sect. 4.

2 Improvements of Fireworks Algorithm

2.1 Original Fireworks Algorithm

In the real world, fireworks are launched into the sky, and many sparks are generated around the fireworks. The explosion process of a firework can be viewed as a local search around a specific point. FWA simulates the explosion process iteratively to find the optimal solution. Figure 1 demonstrates the explosive process of the FWA. Algorithm 1 shows the flowchart of FWA consisting of three operations principally: explosion, mutation and selection [3].

Fig. 1.

Search process of FWA. (a) fireworks are generated, (b) sparks are generated around each firework, and mutation point is generated, (c) new fireworks are generated in the next generation using the (b). The (b) and (c) are iterated until a termination condition is satisfied.

2.2 Proposed Improvements

In this paper, we propose two strategies to replace the corresponding operations of the original FWA. The firework amplitudes of the original FWA are automatically decided by their fitness values using the formula mentioned in the previous section. Better fireworks have relatively smaller amplitudes, while worse fireworks have relatively larger amplitudes.

The first strategy is to decrease the amplitude sizes of all fireworks from one generation to the next regardless of their fitness. We use the formula of Eq. (1) to determine the amplitude of fireworks. Figure 2 shows how the amplitude changes throughout the exploration period.

$$\begin{aligned} A_i = \left\{ \begin{array}{lll} A_{init} * (1-\frac{FE_{cur}}{FE_{max}}) &{} \;\;\;\;\;\; &{} {if \quad FE_{cur}< c*FE_{max} }\\ A_{init} * (1-c) &{} \;\;\;\;\;\; &{} { \quad Others} \end{array} \right. \end{aligned}$$

(1)

where, $A_{init}$ is the initial maximum amplitude of fireworks; $FE_{cur}$ and $FE_{max}$ represent the current and maximum number of fitness evaluations, respectively; and c is a constant for preventing the amplitude from becoming too small.

Fig. 2.

Changes in amplitude throughout the exploration period

The second proposed strategy is to use a local optima-based selection of fireworks in the next generation instead of the distance-based selection used in the original FWA. Since the generated sparks can be considered as a local search around each firework, a set of a firework and its generated sparks can be considered a local subgroup. Then, we can obtain n local subgroups and a mutation subgroup consisting of all mutated sparks as the $(n+1)$-th subgroup. Because n new fireworks should be selected in the next generation, we merge the mutation subgroup and the subgroup of the worst firework into a new subgroup. The proposed local optima-based selection strategy takes the best firework or spark from each subgroup to form the next generation. Figure 3 demonstrates this selection strategy.

Fig. 3.

The best one in each subgroup will be selected and go to next generation.

3 Experimental Evaluations

We use 20 benchmark functions from the CEC2013 benchmark test suite [6] in our evaluations. Table 1 shows their types, characteristics, variable ranges, and optimum fitness values. These landscape characteristics include shifted, rotated, global on bounds, unimodal and multi-modal. We test them with 3 dimensional settings: $D=$ 2, 10 and 30.

Table 1. Benchmar Function: Uni = unimodal, Multi = multimodal.

To analyze the effect of each proposed improvement, we design the following four experiments; Experiments 1, 2, 3, and 4 are, respectively, the original FWA, the original FWA + the first proposed strategy (amplitude decrease strategy), the original FWA + the second proposed strategy (selection method of the firework in the next generation), and the original FWA + both strategies. Table 2 shows the parameter settings of the canonical FWA. The parameter settings for Experiments 2–4 are the same as the canonical FWA except the initial amplitudes; initial amplitudes $A_{init}$ and constant c of the Eq. (1) are set as 10 and 0.95, respectively.

Table 2. Parameter setting of original FWA.

We evaluate convergence along the number of fitness calls instead of generations. We test each benchmark function with 30 trial runs in 3 different dimensional spaces. We apply the Friedman test and Holm’s multiple comparison to the fitness values at the stop condition, i.e. maximum number of fitness calculations, for each benchmark function to check for significant difference among the methods. Table 3 shows the result of these statistical tests.

Table 3. Statistical test result of the Friedman test and Holm’s multiple comparison for average fitness values of 30 trial runs of 4 methods. $A \gg B$ and $A > B$ mean that A is significant better than B with significant levels of 1% and 5%, respectively. $A \approx B$ means that there is no significant difference between A and B. Numbers in the table represent that 1: original FWA, 2: original FWA $+$ proposed strategy 1, 3: original FWA $+$ proposed strategy 2, and 4: original FWA $+$ proposed strategies 1 and 2.

4 Discussions

We begin our discussion with an explanation of the superiority of our proposed strategies. In the original FWA, better fireworks can obtain more resources within a small range, thus undertaking responsibility for exploitation. Exploration is achieved by worse fireworks obtaining less resources in a larger range through the whole search period. However, exploration should be a task performed primarily in the early stages of search, while exploitation should be gradually emphasized along with the convergence of the population. So the first proposed strategy uses a decrement strategy to make all fireworks responsible for exploration in the early generations, with this exploration ability becoming gradually weaker as the exploitation ability becomes gradually stronger to achieve a good balance between exploration and exploitation.

We simply use the number of fitness evaluations to control the amplitude of fireworks in this paper, but this is not the unique realization of the proposed strategy 1; there must be other realizations which would allow us to improve its performance even more. For example, the amplitude can be adjusted adaptively according to optimization tasks, not just based on the number of fitness evaluations.

The distance-based selection used in the original FWA aims to preserve the diversity of fireworks, but there are still some shortcomings. This selection strategy gives higher selection probabilities to individuals located far away from other individuals. However, there is no guarantee that the fireworks selected by this original strategy have better fitness in the next generation than those in the current generation except the best individual. Further, there is also no guarantee that individuals coming from each subgroup will be selected fireworks in the next generation. If no individual from a certain subgroup is selected in the next generation, the area will not be explored in the next generation and the diversity may be lost.

The second proposed strategy can overcome these shortcomings and ensure each local optimum individual can remain in the next generation to maximize and the preserve the population diversity. This strategy may develop to become a new niche method for finding multi local or global optima at one time run.

Next, we discuss the effectiveness of our proposed strategies. To analyze their performances, Friedman test and Holm’s multiple comparison test were applied at the stop condition in three different dimensions. The two strategies do not add additional fitness computation cost. Nevertheless, the statistical results in the Table 3 show that either of the two proposed strategies can improve the performance of the original FWA, and their combination can further improve performance in almost all evaluation cases.

Fig. 4.

Convergence curves of the original FWA, the original FWA $+$ proposed strategy 1, the original FWA $+$ proposed strategy 2, and the original FWA $+$ proposed strategies 1 and 2 for 30-D $f_{11}$–$f_{14}$, respectively.

Although combining two proposed strategies 1 and 2 with original FWA works well, it did not show clear performance for $f_{11}$–$f_{14}$ in the Table 3. Figure 4 shows the average convergence curves of 4 methods for these 30-dimensional benchmark functions. These improved strategies for Rastrigin’s function and Schwefel’s function showed better performance in the early searching stages, while it could not keep their better performance in the later period and even became worse than the original FWA. It may be due to their many local optima; the local optima-based selection can maximize the diversity of the population, but it may reduce the convergence speed. We need further analysis of this result to understand the real reason and develop its solution.

5 Conclusion

We proposed two strategies to enhance the performance of the original FWA. The first strategy further emphasizes the balance between exploration and exploitation, and the second one selects local optimum individuals to preserve search diversity. Controlled experiments confirmed that they can improve the performance of the original FWA significantly.

In future work, we will further study these strategies and make full use of local information to obtain better performance.