Theory - (2018) Volume 7, Issue 3

Multi-layer Explosion Based Fireworks Algorithm

Jun Yu1*, Hideyuki Takagi2 and Ying Tan3
1Graduate School of Design, Kyushu University, 4-9-1, Shiobaru, Minami-ku, Fukuoka, Japan, E-mail: [email protected]
2Faculty of Design, Kyushu University, 4-9-1, Shiobaru, Minami-ku, Fukuoka, Japan, E-mail: [email protected]
3School of Electronics Engineering and Computer Science, Peking University, District, Beijing, China, E-mail: [email protected]
*Corresponding Author: Jun Yu, Graduate School of Design, Kyushu University, 4-9-1, Shiobaru, Minami-ku, Fukuoka, Japan, Tel: +81 92-553-4400 Email:

Abstract

We propose a new multi-layer explosion strategy inspired by various explosion patterns of real reworks to accelerate reworks algorithm (FWA). Each rework individual conducts multiple explosions to explore a local fitness landscape carefully instead of a single layer explosion used in canonical FWA. In the proposal, each rework individual generates a small number of sparks in the first layer randomly, then the generated sparks conduct the second layer explosions to generate new diverse sparks. These new sparks repeat the above operations until the number of this iteration reaches the predefined maximum layer number. Theoretically, the number of explosion layers can be set to any positive integer, and the proposed strategy expects to generate various potential sparks using the multi-layer explosion strategy without changing the total number of generated sparks. The proposed strategy can combine with not only basic FWA but also other versions of FWA algorithms easily and replace their corresponding explosion operations to develop a new version, multi-layer explosion-based FWA. To evaluate the performance of our proposal, we select a more powerful variant of FWA, Enhanced FWA (EFWA) as the baseline algorithm and combine with our proposed explosion strategy. We run our proposal on 28 benchmark functions from CEC2013 test suites of 2-dimensions (2-D), 10-D and 30-D with 30 trial runs and compare with several state-of-theart EC algorithms. The experimental results confirm that the proposed strategy is effective and promising, which can obtain a better performance for FWA in terms of convergence speed and convergence accuracy. We finally analyze composition as well as feasibility of proposal and list some open topics.

Keywords: Swarm intelligence; Fireworks algorithm; Optimization; Multi-layers explosion

Introduction

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 [1].

One of the representative swarm intelligence algorithms is Particle Swarm Optimization (PSO) [2] 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 [3], artificial bee colony algorithm [4], cuckoo search [5], bat algorithm [6], krill herd [7], elephant herding optimization [8], and others. Besides, some researchers also developed other optimization algorithms inspired by natural phenomenon and human society, such as brain storm optimization algorithm [9], imperialist competitive algorithm [10] and others.

Fireworks Algorithm (FWA) [11] 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) [12] improves the corresponding five operations of the conventional FWA and can achieve a better performance. Dynamic FWA (dynFWA) [13] 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 [14] are also proposed and integrated into FWA to improve its performance obviously. A novel guiding spark [15] 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 [16] 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 [17], constrained portfolio optimization [18], web information retrieval [19], multilevel image thresholding [20], RFID network planning [21] and privacy preserving [22], 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 [23], 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.

Fireworks Algorithm

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.

swarm-intelligence-evolutionary-computation-firework

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 [12].

Algorithm 1

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.

Proposed Multi-layer Explosion Strategy

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.

swarm-intelligence-evolutionary-computation-layers

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; equation is the j-th spark individual (j=1~mi(k) ) generated in the k-th layer explosion180 under the fi. Relationships among them are equation and equation The i-th subgroup is formed by the i-th firework individuals fi, and all its sparks equation 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, equation to the remained explosion layers. The total number of sparks in subsequent explosion layers is equation We simply distribute an equal number of sparks to each layer, equation After all firework individuals complete their first explosions, their second explosions are triggered by not the firework individuals but their generated spark individuals, equation. The second key problem is how to decide the search radius around equation and how to divide equation explosion sparks to each equation in each layer. These two parameters are decided by the fitness of the equation adaptively. This layer explosion is repeated until explosions repeat l times.

Algorithm 2

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

• For equation

• 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.

Experimental Evaluations

We use 28 functions from the CEC2013 test suite [24] to evaluate the performance of our proposal [24]. 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.

No. Types Characteristics Optimum fitness
F1 Uni Sphere function −1400
F2 Rotated high conditioned elliptic function −1300
F3 rotated Bent Cigar function −1200
F4 Rotated discus function −1100
F5 different 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
F11 Rastrigin’s function −400
F12 Rotated Rastrigin’s function −300
F13 Non-continuous rotated Rastrigin’s function −200
F14 Schwefel’s function −100
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.

Parameters Values
# 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.

Function 2-D 10-D 30-D
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 difference between them.

Function 2-D 10-D 30-D
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.

Function 2-D 10-D 30-D
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 different 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.

Discussions

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.

Conclusion

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.

Acknowledgments

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.

References

Citation: Yu J, Takagi H, Tan Y (2018) Multi-layer Explosion Based Fireworks Algorithm. J Swarm Intel Evol Comput 7: 173.

Copyright: © 2018 Yu J, et al. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.