Keywords: Swarm intelligence; Fireworks algorithm; Optimization; Multi-layers explosion
Swarm Intelligence algorithms are a kind of population-based optimization technique and mainly simulate the cooperation among simple individuals to achieve complex group behaviours. They have attracted many practitioners thanks to their outstanding characteristics, such as, easy-to-use, robustness, parallelism, intelligence and others. Meanwhile, many practical problems encountered become more complicate and traditional optimization methods, e.g. linear programming and Newton method, are powerless to solve them perfectly, which also prompts such algorithms used in industry widely. For example, the nose cone of the N700 series Shinkansen (bullet train) was redesigned by genetic algorithm, Mazda used multi-objective optimization algorithm to simulate the design of next-generation vehicle structure .
One of the representative swarm intelligence algorithms is Particle Swarm Optimization (PSO)  that simulates the foraging behaviour of birds to and the global optimum. So far, many efficient algorithms have been proposed, e.g. bacterial foraging optimization algorithm , artificial bee colony algorithm , cuckoo search , bat algorithm , krill herd , elephant herding optimization , and others. Besides, some researchers also developed other optimization algorithms inspired by natural phenomenon and human society, such as brain storm optimization algorithm , imperialist competitive algorithm  and others.
Fireworks Algorithm (FWA)  is a new family member of swarm intelligence and repeatedly simulates the explosion of multiple fireworks simultaneously to achieve wide search and each rework explosion can be regarded as a local search. In recent years, many researchers have further improved its performance by proposing various variants with novel mechanisms. The Enhanced FWA (EFWA)  improves the corresponding five operations of the conventional FWA and can achieve a better performance. Dynamic FWA (dynFWA)  uses a dynamic explosion amplitude for the current best firework to tune the search range more intelligently.
An amplitude reduction strategy and local optima-based selection strategy  are also proposed and integrated into FWA to improve its performance obviously. A novel guiding spark  with promising direction and adaptive length is proposed to enhance the information use in FWA and guide the evolution of fireworks effectively. Loser-out tournament based FWA  introduces competition mechanism and analyze the potential of each rework individual. The losers who cannot catch up with the best one with its current progress rate will be eliminated and reinitialized. FWA has also been applied to many real problems and achieved encouraging successes. For example, regional seismic waveform inversion , constrained portfolio optimization , web information retrieval , multilevel image thresholding , RFID network planning  and privacy preserving , etc.
Although many novel and effective mechanisms are integrated into the FWA to improve its search capabilities, few attentions have been devoted to the explosive manner of reworks. Honestly, fireworks have many ways to explode in the real world and do not limited to circular explosion. For example, the shape of real fireworks explosion we can often see has continuous explosion , fan-shaped explosion, and others. Inspired by various explosion modes, this paper proposes a new explosion strategy to enhance the understanding and utilization of local fitness landscape.
The main objective of this paper is to propose multi-layer explosion strategy to use local fitness information more efficiently and guide individual evolution reasonably. At the first attempt, we construct two layers of explosions successively to understand local fitness landscape distribution information. The secondary objective is to analyze the performance as well as applicability of the proposed explosion strategy. Finally, we introduce some topics for open discussion.
The remaining paper is organized as following. We brie y review the framework of conventional FWA in the Section 2. The proposed explosion strategy is clearly presented in the Section 3. To evaluate the performance of our proposal, we com-pare it with several state-of-theart Evolutionary Computation (EC) algorithms using 28 benchmark functions from CEC 2013 with 3 different dimensions in the Section 4.
Finally, we analyze and discuss the effects of our proposed explosion strategy and give some open topics in the Section 5; and conclude the current work in the Section 6.
In real world, a firework is launched into the sky then many sparks are generated around it. A re-work explosion can be abstracted as a local search model around a specific point. FWA simulates the explosion process iteratively to find the optimal candidate solution. Figure 1 demonstrates a general explosive model of the FWA. Conventional FWA has two types of reworks, better rework and poor rework. A better rework may close to an optimum so that many sparks are generated around it within a smaller range, while a poor firework may far from the optimum so less sparks are generated, and search range should be larger. Algorithm 1 shows the general ow of FWA mainly consisting of three operations: explosion, mutation and selection.
Figure 1: Search process of FWA. (a) Fireworks are random generated, (b) sparks (red solid points) are generated around each firework, and mutation sparks (blue solid points) are also generated, (c) new fireworks are selected to enter the next generation using the (b). The (b) and (c) are iterated until a termination condition is satisfied.
Since there are some limitations in the conventional FWA and its performance is also poorer than that of all subsequent variants, such as EFWA and dynFWA. Wherefore, we employ much more powerful EFWA as a baseline algorithm and combine it with our proposed strategy. The EFWA introduces five major improvements into conventional FWA:
• A new minimal explosion amplitude is set to each firework,
• A new mechanism for generating sparks,
• A new mechanism for generating sparks,
• A new operator for generating Gaussian sparks, and
• A new selection strategy is used to choose next generation.
Many experiments confirm that it can significantly improve the performance of conventional FWA by modifying the corresponding operations without changing the overall framework and thought. Due to space limitations, we do not describe these previous works in detail, and all works can be referenced in .
The general framework of FWA.
• Initialize n fireworks randomly.
• Evaluate the fitness of each firework.
• While termination condition is not satisfied do
• Generate sparks for each firework.
• Generate Gaussian mutation sparks.
• If sparks are generated outside search area, then
• Use a mapping rule to bring it back to search space.
• End if
• Evaluate the fitness of generated sparks.
• Select n new fireworks for next generation.
• End while
• Output found feasible solution.
With the development of production techniques, various exquisite fireworks explosion shapes can be customized, commonly there, heartshaped explosion, multi-layer explosion and specific area explosion, etc. Inspired by various explosion ways and shapes, we firstly introduce a different explosion model, multi-layer explosion to enhance the use of the local fitness landscape, while conventional FWA generates spark individuals around a firework individual at once. Figure 2 illustrates the generation process of sparks using our proposed strategy. As our first attempt, we set the number of layers to 2 in this paper thought. It can be set to any positive integer theoretically.
Figure 2 : The general framework of our proposed multi layers explosion strategy, where a two-layer explosion is shown as an example. (a) and (b) are the first and the second explosions, respectively, where black pentagrams represent firework individuals, four-pointed stars and solid dots of various colors represent generated sparks in the first layer and the second layer, respectively. A dashed circle represents the search radius of a firework and spark individuals.
First layer explosion
The explosion of a firework is determined by two factors, number of sparks and amplitude of explosion. They individually determine how many spark individuals can be generated by a firework and its search radius (amplitude). In the first layer, each firework determines its search radius adaptively allocated according to its fitness, which is the same as conventional FWA.
However, we treat each firework equally in the first layer, and all fireworks generate the same number of a few number of spark individuals to investigate its surrounding fitness landscape within its own search radius. These generated spark individuals in the first layer are evaluated with an objective function and used to determine the explosive shape of the second layer and the allocation of spark individuals in the second layer. The number of generated spark individuals for each firework in the first layer is decided adaptively according to its fitness.
Subsequent layer explosion
Let's define symbols temporally to explain the main idea of this paper, multi-layer explosions. N is the number of firework individuals; fi is the i-th firework individual; m is the total number of sparks. l is the maximum number of explosion layers; mi is the total number of sparks in all layer explosions under the fi; mi(k) is the number of sparks in the k-th explosion layer; is the j-th spark individual (j=1~mi(k) ) generated in the k-th layer explosion180 under the fi. Relationships among them are and The i-th subgroup is formed by the i-th firework individuals fi, and all its sparks Figure 2. Since search parameters in each explosion layer are independently decided in each subgroup, we explain the multi-explosion process at the i-th subgroup in the below.The first key problem is how to distribute the remaining number of sparks, to the remained explosion layers. The total number of sparks in subsequent explosion layers is We simply distribute an equal number of sparks to each layer, After all firework individuals complete their first explosions, their second explosions are triggered by not the firework individuals but their generated spark individuals, . The second key problem is how to decide the search radius around and how to divide explosion sparks to each in each layer. These two parameters are decided by the fitness of the adaptively. This layer explosion is repeated until explosions repeat l times.
The general framework of the proposed multi-layer explosion strategy. See the definition of symbols in the sub-Section subsequent layer explosion.
• For i = 0; i < n; i + + do
• Decide the number of generated sparks, mi(1), in the first layer for each firework.
• Decide a search radius around the i-th firework according to its fitness.
• Conduct the first layer explosion for each firework.
• While the number of explosions does not reach a pre-defined maximum layer do
• Decide the number of sparks generated by the j-th spark in the previous layer.
• Decide a search radius of around the j-th spark in the previous layer.
• End for
• Generate the next explosion sparks for
• Each spark in the previous layer.
• End while
• End for
• End of explosion.
Our proposed strategy divides sparks in multi-layer explosion, and sequential explosions expand searching areas to better directions gradually layer by layer according to the fitness of sparks in each layer explosion, while the fitness of a firework individual decides all sparks at once. It is important to note that our proposed explosion strategy just change the layer of the explosions without changing any other operations, i.e. generation of spark individuals and mutation operation. Algorithm 2 shows the flow of our proposed explosion strategy. When it is combined with other versions of the FWA, only their corresponding explosion operation is replaced.
We use 28 functions from the CEC2013 test suite  to evaluate the performance of our proposal . The test suite is devoted to the approaches, algorithms, and techniques for solving real parameter single objective optimization. Table 1 shows their types, characteristics, variable ranges, and optimum fitness values, and these landscape characteristics include shifted, rotated, unimodal and multi-model.
|F2||Rotated high conditioned elliptic function||−1300|
|F3||rotated Bent Cigar function||−1200|
|F4||Rotated discus function||−1100|
|F5||diﬀerent powers function||−1000|
|F6||Multi||Rotated Rosenbrock’s function||−900|
|F7||Rotated Schaffers function||−800|
|F8||Rotated Ackley’s function||−700|
|F9||Rotated Weierstrass function||−600|
|F10||Rotated Griewank’s function||−500|
|F12||Rotated Rastrigin’s function||−300|
|F13||Non-continuous rotated Rastrigin’s function||−200|
|F15||Rotated Schwefel’s function||100|
|F16||Rotated Katsuura function||200|
|F17||Lunacek BiRastrigin function||300|
|F18||Rotated Lunacek BiRastrigin function||400|
|F19||Expanded Griewank’s plus Rosenbrock’s function||500|
|F20||Expanded Scaffer’s F6 function||600|
|F21||Comp.||Composition Function 1 (n=5, Rotated)||700|
|F22||Composition Function 2 (n=3, Unrotated)||800|
|F23||Composition Function 3 (n=3, Rotated)||900|
|F24||Composition Function 4 (n=3, Rotated)||1000|
|F25||Composition Function 5 (n=3, Rotated)||1100|
|F26||Composition Function 6 (n=5, Rotated)||1200|
|F28||Composition Function 7 (n=5, Rotated)||1300|
|F28||Composition Function 8 (n=5, Rotated)||1400|
Table 1: Benchmark Functions. Uni: Unimodal; Multi: Multimodal; Comp: Composition.
EFWA which performance is better than original FWA as a baseline algorithm. We integrate our proposed explosion strategy into EFWA and compare it with original EFWA and several other state-of-the-art EC algorithms. The Table 2 shows the parameter settings of EFWA used in our experiments, where the definition of the symbols is the same in the original literature [11,12]. The Table 3 shows the parameter settings of PSO used in our experiments.
|# of fireworks for 2-D, 10-D and 30-D search||5|
|# of sparks m||60|
|# of Gauss mutation sparks,||5|
|constant parameters||a = 0.04 b = 0.8|
|Maximum amplitude Amax||40|
|Stop condition; max. # of fitness evaluations, MAXNFC, for 2-D, 10-D, and 30-D search||1000, 10,000, 40,000|
Table 2: Parameter setting of EFWA.
|Population size for 2-D, 10-D, and 30-D search||70|
|inertia factor w||1|
|constant c1 and c2||1.49445, 1.49445|
|max. and min. speed Vmax and Vmin||2.0, −2.0|
|Stop condition; max. # of fitness evaluations, MAXNFC, for 2-D, 10-D, and 30-D search||1000, 10,000, 40,000|
Table 3: PSO algorithm parameter settings.
For fair evaluations, we evaluate convergence along the number of fitness calls rather than generations. We test each benchmark function with 30 trial runs in 3 different dimensional spaces, D=2 (2-D), 10 (10- D), and 30 (30-D), respectively. To evaluate the effectiveness of our proposed explosion strategy, we design two sets of control experiments. In the first experiment, we only compare the conventional EFWA and (EFWA+our proposed strategy), and the Wilcoxon signed-rank test at the maximum number of fitness calculations is used to test significant difference. In the second experiment, we compare (EFWA+our proposed strategy) with PSO and guided FWA that is one of the most competitive variation of FWA. The Kruskal-Wallis test and Holm's multiple comparison test are applied to check whether there is a difference among these three algorithms at the stop condition. Finally, the Tables 4 and 5 show the statistical test results of the first and second controlled experiments, respectively. Note that we do not use a complete replication guided FWA published in but instead integrate the concept of guiding spark into EFWA with the following two modifications: (1) We do not calculate a guided spark for all firework individuals but only the best firework individual, and (2) all sparks generated by the best firework is divided into two groups, better than the firework and worse than the firework. All sparks in both groups are involved in calculating guided spark rather than sparks in the front of the two groups. Our proposed strategy and other efficient strategies for FWA can be compared based on the same baseline algorithm, which can make the experiment fairer.
|f1||proposal ≫EFWA||EFWA ≫ proposal||EFWA ≫ proposal|
|f2||proposal ≈ EFWA||proposal ≈ EFWA||EFWA > proposal|
|f3||proposal ≈ EFWA||proposal ≫ EFWA||proposal ≈ EFWA|
|f4||proposal > EFWA||proposal ≫ EFWA||proposal ≫ EFWA|
|f5||proposal ≫ EFWA||proposal ≫ EFWA||proposal ≈ EFWA|
|f6||proposal ≫ EFWA||proposal ≈ EFWA||proposal ≈ EFWA|
|f7||proposal ≫ EFWA||proposal ≫ EFWA||proposal > EFWA|
|f8||proposal ≫ EFWA||proposal ≈ EFWA||proposal > EFWA|
|f9||proposal ≫ EFWA||proposal ≫ EFWA||proposal ≫ EFWA|
|f10||proposal ≫ EFWA||proposal ≫ EFWA||EFWA ≫ proposal|
|f11||proposal ≫ EFWA||proposal ≫ EFWA||proposal ≫ EFWA|
|f12||proposal ≫ EFWA||proposal ≫ EFWA||proposal ≫ EFWA|
|f13||proposal ≫ EFWA||proposal ≫ EFWA||proposal ≫ EFWA|
|f14||proposal ≈ EFWA||proposal ≫ EFWA||proposal ≫ EFWA|
|f15||proposal ≈ EFWA||proposal > EFWA||proposal ≈ EFWA|
|f16||EFWA ≈ proposal||EFWA ≈ proposal||EFWA ≈ proposal|
|f17||proposal ≫ EFWA||proposal ≫ EFWA||proposal ≫ EFWA|
|f18||proposal ≫ EFWA||proposal ≫ EFWA||proposal ≫ EFWA|
|f19||proposal ≫ EFWA||proposal > EFWA||proposal ≫ EFWA|
|f20||proposal ≫ EFWA||proposal ≫ EFWA||proposal ≈ EFWA|
|f21||proposal ≈ EFWA||EFWA ≫ proposal||proposal ≈ EFWA|
|f22||proposal > EFWA||proposal ≫ EFWA||proposal ≫ EFWA|
|f23||proposal ≫ EFWA||proposal ≫ EFWA||proposal > EFWA|
|f24||proposal ≫ EFWA||proposal ≫ EFWA||proposal ≫ EFWA|
|f25||proposal ≫ EFWA||proposal ≫ EFWA||proposal ≫ EFWA|
|f26||proposal ≈ EFWA||proposal ≫ EFWA||proposal ≫ EFWA|
|f27||proposal > EFWA||proposal ≫ EFWA||proposal ≫ EFWA|
|f28||proposal > EFWA||proposal ≫ EFWA||proposal ≫ EFWA|
Table 4: Statistical test results of the Wilcoxon signed-rank test for average fitness values of 30 trial runs of the proposal (EFWA+our proposed mechanism) and EFWA at the stop condition, MAXNFC. A ≫B and A > B mean that A is significantly better than B with significant levels of 1% and 5%, respectively. A ≈ B means that although A is better than B, there is no significant diﬀerence between them.
|f1||proposal ≫ PSO ≫ GEFWA||GEFWA ≫ proposal ≫ PSO||GEFWA ≫ proposal ≫ PSO|
|f2||proposal ≈ GEFWA > PSO||PSO ≫ proposal ≈ GEFWA||PSO ≈ GEFWA ≫ proposal|
|f3||proposal ≫ PSO ≈ GEFWA||PSO ≈ proposal ≈ GEFWA||PSO ≫ proposal ≈ GEFWA|
|f4||proposal ≈ GEFWA ≫ PSO||PSO ≫ proposal ≫ GEFWA||proposal ≫ PSO > GEFWA|
|f5||proposal ≫ PSO ≈ GEFWA||PSO ≫ proposal ≫ GEFWA||proposal ≈ GEFWA ≫ PSO|
|f6||PSO ≈ proposal ≫ GEFWA||PSO ≈ proposal ≈ GEFWA||PSO ≈ proposal ≈ GEFWA|
|f7||proposal > PSO > GEFWA||PSO ≫ proposal > GEFWA||PSO ≫ proposal ≫ GEFWA|
|f8||proposal ≈ PSO ≈ GEFWA||proposal ≈ PSO ≈ GEFWA||proposal ≈ GEFWA ≈ PSO|
|f9||proposal ≈ PSO ≈ GEFWA||proposal ≈ PSO ≫ GEFWA||PSO ≈ proposal ≫ GEFWA|
|f10||proposal ≫ GEFWA ≈ PSO||PSO ≫ proposal ≫ GEFWA||GEFWA ≫ proposal ≫ PSO|
|f11||proposal ≫ PSO ≈ GEFWA||proposal ≫ PSO ≫ GEFWA||proposal ≫ PSO ≫ GEFWA|
|f12||proposal ≈ PSO ≈ GEFWA||PSO ≫ proposal ≫ GEFWA||PSO ≈ proposal ≫ GEFWA|
|f13||proposal ≫ PSO ≈ GEFWA||proposal ≈ PSO ≫ GEFWA||proposal ≫ PSO ≫ GEFWA|
|f14||PSO ≈ proposal ≈ GEFWA||proposal ≫ PSO ≈ GEFWA||proposal ≫ GEFWA > PSO|
|f15||PSO ≈ proposal ≈ GEFWA||PSO ≈ proposal ≫ GEFWA||proposal > GEFWA > PSO|
|f16||GEFWA > proposal ≈ PSO||GEFWA ≈ proposal ≫ PSO||GEFWA ≈ proposal ≫ PSO|
|f17||proposal ≫ PSO ≈ GEFWA||proposal ≈ PSO ≫ GEFWA||proposal ≫ PSO ≫ GEFWA|
|f18||proposal ≈ PSO ≈ GEFWA||proposal ≫ PSO ≫ GEFWA||proposal ≫ GEFWA > PSO|
|f19||proposal ≈ GEFWA ≈ PSO||proposal ≫ PSO ≈ GEFWA||PSO ≈ proposal > GEFWA|
|f20||proposal ≫ PSO ≈ GEFWA||PSO ≈ proposal > GEFWA||proposal ≈ GEFWA ≫ PSO|
|f21||PSO ≈ proposal ≈ GEFWA||GEFWA ≫ proposal ≫ PSO||proposal ≈ GEFWA ≫ PSO|
|f22||PSO ≈ proposal ≫ GEFWA||proposal ≈ PSO ≫ GEFWA||proposal ≫ PSO ≈ GEFWA|
|f23||PSO ≈ proposal ≈ GEFWA||proposal ≈ PSO ≈ GEFWA||proposal ≈ PSO ≈ GEFWA|
|f24||proposal ≈ PSO ≈ GEFWA||PSO ≈ proposal ≫ GEFWA||PSO ≈ proposal ≫ GEFWA|
|f25||PSO ≈ proposal ≫ GEFWA||PSO ≈ proposal ≫ GEFWA||proposal ≫ PSO ≈ GEFWA|
|f26||PSO ≈ proposal > GEFWA||PSO ≈ proposal ≈ GEFWA||proposal ≈ PSO ≫ GEFWA|
|f27||PSO > proposal > GEFWA||PSO ≈ proposal ≈ GEFWA||PSO > proposal ≫ GEFWA|
|f28||PSO ≈ proposal > GEFWA||proposal ≈ PSO ≫ GEFWA||proposal ≫ PSO ≫ GEFWA|
Table 5: Statistical test results of the Kruskal-Wallis test and Holm’s multiple comparison test for average fitness values of 30 trial runs of the proposal (EFWA+our proposed mechanism), PSO and guided EFWA (GEFWA) at the stop condition, MAXNFC. A ≫ B, A > B and A ≈ B represent the same meaning as the symbols in the Table 4.
Besides, we set the number of generated spark individuals in the first layer to 3, 4 and 5 to investigate its influence on the performance, and other parameter settings is the same with the Table 2 completely. The Friedman test and Holm's multiple comparison test are applied to check significant difference among them at the stop condition. The Table 6 presents the statistical tests result of different parameter settings of generated sparks in the first layer.
|f1||FN3 ≈ FN4 ≈ FN5||FN3 ≈ FN4 ≈ FN5||FN5 ≈ FN4 ≈ FN3|
|f2||FN3 ≈ FN4 ≈ FN5||FN3 ≈ FN4 ≈ FN5||FN3 ≈ FN4 ≈ FN5|
|f3||FN3 ≈ FN4 ≈ FN5||FN3 ≈ FN4 ≈ FN5||FN3 ≈ FN4 ≈ FN5|
|f4||FN3 ≈ FN4 ≈ FN5||FN4 ≈ FN3 ≈ FN5||FN4 ≈ FN3 > FN5|
|f5||FN3 ≈ FN4 ≈ FN5||FN3 ≈ FN4 ≫ FN5||FN3 ≫ FN4 ≈ FN5|
|f6||FN4 ≈ FN3 ≈ FN5||FN3 ≈ FN5 ≈ FN4||FN3 ≈ FN5 ≈ FN4|
|f7||FN3 ≈ FN4 > FN5||FN3 ≈ FN4 ≈ FN5||FN5 > FN3 ≈ FN4|
|f8||FN3 ≈ FN5 ≈ FN4||FN3 ≈ FN5 ≈ FN4||FN3 ≈ FN4 ≈ FN5|
|f9||FN4 ≈ FN5 ≈ FN3||FN3 ≈ FN5 ≈ FN4||FN3 ≈ FN4 ≈ FN5|
|f10||FN5 ≈ FN4 ≈ FN3||FN3 ≈ FN4 ≈ FN5||FN3 ≈ FN4 ≫ FN5|
|f11||FN3 ≈ FN4 ≈ FN5||FN3 ≫ FN4 ≈ FN5||FN3 ≫ FN4 > FN5|
|f12||FN3 ≈ FN4 ≈ FN5||FN3 ≈ FN4 ≈ FN5||FN3 > FN4 ≈ FN5|
|f13||FN3 > FN4 ≈ FN5||FN3 ≈ FN5 ≈ FN4||FN3 ≈ FN5 ≈ FN4|
|f14||FN3 ≈ FN4 ≈ FN5||FN3 ≈ FN5 ≈ FN4||FN3 ≈ FN4 ≈ FN5|
|f15||FN5 ≈ FN4 ≈ FN3||FN3 ≈ FN4 ≈ FN5||FN3 ≈ FN4 ≈ FN5|
|f16||FN4 ≈ FN3 ≈ FN5||FN3 ≈ FN4 > FN5||FN5 ≈ FN4 ≈ FN3|
|f17||FN3 ≈ FN4 ≈ FN5||FN3 > FN4 ≈ FN5||FN3 ≈ FN4 ≫ FN5|
|f18||FN4 ≈ FN3 ≈ FN5||FN3 ≈ FN5 ≈ FN4||FN4 ≈ FN3 ≈ FN5|
|f19||FN3 ≈ FN4 ≈ FN5||FN3 ≈ FN4 ≈ FN5||FN3 ≈ FN4 ≈ FN5|
|f20||FN3 ≈ FN4 ≈ FN5||FN3 ≈ FN4 ≈ FN5||FN5 ≈ FN3 ≈ FN4|
|f21||FN4 ≈ FN3 ≈ FN5||FN4 ≈ FN3 ≈ FN5||FN4 ≈ FN5 ≈ FN3|
|f22||FN3 ≈ FN4 ≈ FN5||FN3 ≈ FN4 ≈ FN5||FN3 ≈ FN4 ≈ FN5|
|f23||FN3 ≈ FN5 ≈ FN4||FN3 ≈ FN4 ≈ FN5||FN4 ≈ FN3 ≈ FN5|
|f24||FN3 ≈ FN4 ≈ FN5||FN3 ≈ FN4 ≈ FN5||FN3 ≈ FN4 ≈ FN5|
|f25||FN4 ≈ FN3 ≈ FN5||FN3 ≈ FN4 ≈ FN5||FN3 ≈ FN5 ≈ FN4|
|f26||FN3 ≈ FN4 ≈ FN5||FN5 ≈ FN3 ≈ FN4||FN3 ≈ FN4 ≈ FN5|
|f27||FN3 ≈ FN5 ≈ FN4||FN3 ≈ FN5 ≈ FN4||FN4 ≈ FN3 ≈ FN5|
|f28||FN4 ≈ FN5 ≈ FN3||FN3 ≈ FN4 ≈ FN5||FN3 ≈ FN5 ≈ FN4|
Table 6: Statistical test results of the Friedman test and Holm’s multiple comparison test for average fitness values of 30 trial runs of diﬀerent parameter settings of generated sparks in the first layer at the stop condition, MAXNFC. FN3, FN4 and FN5 mean the number of generated spark individuals in the first layer is 3, 4 and 5 for each firework individual, respectively. A≫B, A > B and A≈ B represent the same meaning as the symbols in the Table 4.
Analysis of compositions of our proposal
We begin our discussion on the superiority of our proposed explosion strategy. Original FWA and several its powerful variant versions, have paid little attention to the use of the fitness landscape information to generate spark individuals efficiently and reasonably. Besides, they only use a small amount of firework individuals to explore fitness landscape and generate a large number of spark individuals.
Although it can achieve a fine local search around a firework individual, many generated spark individuals are used in only a selection operation and then destroyed. It results that many spark individuals are not fully used in fact and generating a large number of sparks from only a few fireworks is risky.
Thus, our proposal can overcome the above deficiencies without adding any additional fitness calculations. With the same number of fitness calculations, our multi-layer explosion strategy can explore and use the features of the local fitness landscape more effectively. In the first layer, each firework individual generates several spark individuals to further explore the local fitness landscape carefully, while conventional FWA only uses a firework individual to achieve it. The objective of the first explosion is to enhance the understanding of local fitness landscape with multiple tentative individual’s firework individuals and spark individuals in the first layer). Subsequently, the following layer explosion is adaptively conducted based on the results of the previous explosion. Meanwhile, the center of the explosion is transferred from firework individuals to spark individuals generated in the previous layer, which can increase the diversity of generated spark individuals and achieve a more refined local search. Thus, the objective of following explosion is to be more reasonable to generate diverse and potential spark individuals based on the characteristic of local fitness landscape. As a summary, the proposed strategy can achieve more careful local search automatically based on the characteristics of local fitness landscape without adding any fitness cost consumption.
Secondly, we want to discuss the potential of our proposed explosion strategy. Although we evaluated the simplest two-layer explosion model in this paper to improve the understanding of local fitness landscape, the proposed explosion mechanism can be extended to any layers to explore local fitness information more accurately. Note that the conventional FWA is a special case of our proposal as a singlelayer explosion. Thus, our proposed explosion mechanism is flexible and can be adjusted to any number of layers as needed. It becomes a potential topic to develop an adaptive version determining the number of explosion layers according to the characteristics of optimization problems and computational cost.
Not only conventional FWA but also our proposed explosion strategy can be easily combined with other variations of FWA with few modifications to their original framework. In this paper, we select EFWA as a baseline algorithm. The main objective of this paper is to use the proposed multi-layer explosion strategy to speed up any FWA rather than improve a particular version, e.g. dynFWA and adaptive FWA. Surely, the proposed strategy can replace the explosion operations of these future versions easily, and we can infer that their performance is further improved based on our experimental results. Thus, we can say that our proposal is widely applicable and easy to use.
The third discussion is how to improve the cost performance of our proposal. Although our proposal strengthens the acquisition of the local fitness landscape information, many generated spark individuals still are not fully used. As a possible attempt, we may identify more potential directions based on the shape of the multiple explosions and assigned number of spark individuals and use these pieces of information to guide evolution more effectively. Besides, past spark individuals can also be recorded to extract more accurate fitness landscape information, for example, using past information to make an approximate fitness model [25,26]. Thus, it is also a topic worthy of continued research to improve the rate of used generated spark individuals.
To analyze the performance of our proposal two controlled experiments was designed. For the first controlled experiment, we apply the Wilcoxon signed-rank test between conventional EFWA and conventional EFWA with our proposed strategy at the stop condition. The statistical results shown in the Table 4 confirmed that our proposed explosion strategy could improve the performance of FWA significantly, especially for complex cases (multi modal optimization and combinatorial optimization). For high-dimensional F1 and F2 unimodal functions, our proposal is worse than conventional EFWA. Perhaps it was because the proposal makes spark individuals explore local fitness landscape fully and thus lead to them distributed widely. It may cause the slow convergence for unimodal optimization, while it is useful to avoid falling into the local minima in multimodal optimization. For F16, our proposal did not show accelerated convergence. It is necessary to further investigate to apply our proposed explosion strategy well.
The second controlled experiment compares our proposal with PSO and a powerful variant of FWA, guided FWA. The Kruskal-Wallis test and Holm's multiple comparison test are used to check significant difference among three algorithms at the stop condition. The statistical results shown in the Table 5 indicate that our proposal performs well in most cases and always have better performance than the guided EFWA. To ensure fairness of comparison, we apply our proposal and guiding spark strategy to the same baseline algorithm. The results reveal that our proposed strategy has stronger performance, and we can infer that our proposed strategy can be combined with not only the guided FWA but also any other variations of FWA to further enhance their performance. This is possible because the guiding spark strategy is only predicting a potential direction in a local area, while our proposed strategy can explore the local fitness land scape more comprehensively. Meanwhile, the proposed multi-layer explosion strategy uses sparks in the previous layer to generate new potential sparks to improve diversity. Thus, we can say that our proposal is promising thanks to its comprehensive exploration with local information. We also compared our proposal with PSO. The statistical results showed that our proposal was better than PSO in low dimensions except f27, but it became worse on some functions, e.g. f3 and f7 in the high dimension. It may be because the number of fireworks is insufficient for the increased dimensions, and PSO uses not only the local optimum of individuals in past generations but also the global best information. It gives us a new inspiration; strengthening the communication among fireworks may further increase performance of our proposal. One of our future works is to investigate the relationship between population size and dimensions and increase collaboration among individuals.
Analysis of parameter settings of proposal
To investigate the effect of the number of generated spark individuals in the first layer on the performance of our proposed strategy, we add an experiment and set different number of generated spark individuals in the first layer using the same parameter settings with the Table 2. We apply the Friedman test and Holm's multiple comparison test to check significant difference at the stop condition.
The statistical results reproduced in the Table 6 shows that the number of generated sparks does not have a large impact on the performance of our proposal. Although the difference is small, the smaller the number of sparks in the first layer, the higher the precision of the final result. When the computational cost is limited, we recommend not to spend too much resources in the first layer, and it depends on the optimization problem and computational cost.
Next, we want to discuss parameter settings. Although it has been discussed for long years, there is no unified methods to guide it. We often do not have sufficient its a priori knowledge for practical applications and a variety of optimization problems, and it is difficult to decide appropriate parameter values. As the first attempt, we set all parameters in this paper based on previous relevant literatures and experiences. We can note that the key point affecting performances is the distribution number of sparks in different layers. When the number of sparks in the first layer is small, sufficient information on a local fitness landscape cannot be obtained and sufficient resources for searching cannot be used in the following layers. Thus, it is important to balance the number of sparks in different layers and develop an adaptive allocation version. Finally, when our proposed strategy is applied to different variants of FWA, we need to consider their characteristics and select appropriate parameter values to achieve the best performance. In summary, there is no established method to guide parameter settings, but we may be able to give rough recommended parameter settings through a large number of trial run experiments in our future work.
Potential and future topics
Inspired by the various explosion modes of real fireworks, we propose a multi-layer explosion strategy to enhance the understanding of the local fitness landscape. Many other different explosions can be developed to enhance different capabilities of FWA. For example, treeshaped or fan-shaped explosions can be developed to track potential directions instead of searching randomly or equally in a space. As many spark individuals are generated by a firework individual in conventional FWA, it is also worth to develop different strategies to generate spark individuals to increase diversity and reduce too intensive risk. Overall, there is still much room to further improve the performance of FWA by introducing novel mechanisms. It is an attractive topic to tune parameters adaptively to maintain the strong performance of FWA at all times. We can also develop adaptive versions from the following three aspects: (1) adaptive decision of the number of explosion layers without limiting to two layers, (2) adaptive decision of the distribution of spark individuals at different levels, and (3) adaptive decision of a search radius on each dimension.
We propose multi-layer explosion strategy to use local fitness information more efficiently and guide individual evolution reasonably, and it can be extended or zoomed to any number of layers. The controlled experiment results reveal that our proposal is competitive and can improve the performance of the FWA significantly. We will further analyse the applicability of our proposal, develop a more powerful adaptive version as our future works. We also focus on the use of generated spark individuals in all layers to search more efficiently.
This work was supported in part by Grant-in-Aid for Scientific Research (18K11470, 17H06197,15K00340) and the Natural Science Foundation of China (NSFC) under grant no. 61673025.