Fireworks algorithm

In general the Fireworks Algorithm (FWA) is an approach to exploring a very large solution space by choosing a set of random points confined by some distance metric in the hopes that one or more of them will yield promising results, allowing for a more concentrated search nearby.

Inspired by the ﬁreworks explosion in the sky at night, ﬁreworks algorithm (FWA) was proposed by the author in 2010, through the observation of the way that ﬁreworks explode is much similar to the way that an individual searches the optimal solution in swarm intelligence algorithms. Recently, FWA has been received extensive concerns of many active researchers in the community of swarm intelligence. This chapter presents the fundamental principle, main constitution, implementation and performance of the FWA, aiming to elaborate the FWA systematically and completely. The main contents include the key components, the realization, the characteristic and the impact of operations of FWA, as well as the comparisons with genetic algorithm and particle swarm optimization^[1].

Introduction

Setting off ﬁreworks is an important creative and joyful activity during Spring Festival in China. At this time, tens of thousands of ﬁreworks explode in the night sky and show beautiful patterns of sparks. Usually, ﬁre-works with different prices and speciﬁcations produce entirely different patterns. For example, the ﬁreworks with lower price produce less sparks with larger amplitude compared with higher price ﬁreworks and vice versa.

The way that ﬁreworks explode is similar to the way that an individual searches the optimal solution in swarm intelligence algorithms. As a swarm intelligence algorithm, ﬁreworks algorithm consists of four parts, i.e., the explosion operator, the mutation operator, the mapping rule and selection strategy. The effect of the explosion operator is to generate sparks around ﬁreworks. The number and amplitude of the sparks are governed by the explosion operator. After that, some sparks are produced by mutation operator. The mutation operator utilizes Gaussian operator to produce sparks in Gaussian distribution. Under the effect of the two operators, if the produced spark is not in the feasible region, the mapping rule will map the new generated sparks into the feasible region. To select the sparks for next generation, the selection strategy is used at last. Fireworks algorithm runs iteratively until reaches the termination conditions.

FWA Principle

Explosion Operator

In initialization, FWA generates N ﬁreworks randomly. Then, the N ﬁreworks generate sparks by explosion operations. The explosion operator is a key in FWA and plays an important role. The explosion operator including explosion strength, explosion amplitude and displacement operation.

Explosion Strength

The explosion strength is a core operation in explosion operator. It simulates the way of explosion of ﬁreworks in real life. When a ﬁrework blasts, the ﬁrework vanished in one second and then many small bursts appear around it. Fireworks algorithm first determines the number of sparks, then calculates the amplitudes of each explosion.

Through the observations on the curves of some typical optimization functions, it can be seen that there are more points with good ﬁtness values around the optima than that away from the optima. Therefore, the ﬁreworks with better ﬁtness values produce more sparks, avoiding swing around the optima but fail to locate it. For the ﬁreworks with worse ﬁtness values, their generated sparks are less in number and sparse in distribution, avoiding unnecessary computing. The ﬁreworks with worse ﬁtness values are used to explore the feasible space, preventing the algorithm from premature convergence. Fireworks algorithm determines the number and amplitude of the ﬁreworks according to their ﬁtness values, letting the ﬁreworks with better ﬁtness values produce more sparks within a smaller amplitude and vice versa.

File:GoodFireworks.png

The good explosions of a ﬁrework.

It can be seen that the ﬁreworks with better ﬁtness values produce more sparks within a smaller amplitude (good explosion) than those with worse ﬁtness values within a larger amplitude (bad explosion). After determining the number of sparks, it is needed to calculate the amplitude of the sparks in the explosion of a ﬁrework.

Explosion Amplitude

Through the observation on the curves of some typical optimization functions, the points around the local optima and global optima always have better ﬁtness values. Therefore, by controlling the explosion amplitude, the amplitude of the ﬁreworks with better ﬁtness values gradually reducing, leading ﬁreworks algorithm ﬁnd the local optima and global optima. On the contrary, the ﬁreworks with worse ﬁtness values will explore the optima through a large amplitude. This is how the FWA controls the magnitude of the explosion amplitude.

Displacement Operation

After the calculation of explosion amplitude, it is necessary to determine the displacement within the explo-sion amplitude. FWA uses the random displacement. In this way, each ﬁrework has its own speciﬁc explosion number and amplitude of sparks. FWA generates different random displacements within each amplitude to ensure the diversity of population. Through the explosion operator, each ﬁrework generates a shower of sparks, helping ﬁnding the global optimal of an optimization function.

Mutation Operator

Gaussian Mutation

To further improve the diversity of a population, the Gaussian mutation is introduced to FWA. The way of producing sparks by Gaussian mutation is as follows: choose a ﬁrework from the current population, then apply Gaussian mutation to the ﬁrework in randomly selected dimensions.

For Gaussian mutation, the new sparks are generated between the best ﬁrework and the selected ﬁreworks. Still, Gaussian mutation may produce sparks exceed the feasible space. When a spark lies beyond the upper or lower boundary, the mapping rule will be carried out to map the spark to a new location within the feasible space.

Covariance Mutation^[2]

The covariance mutation selects the sparks with better fitness values from the sparks produced by a firework, calculates the mean value of the selected sparks and the covariance matrix of all the sparks. With the mean value and covariance matrix, covariance mutation estimates the local distribution of a function and produces sparks according to normal distribution, aiming to find potential sparks with better fitness values. The covariance mutation contains three steps.

First of all, the mutation operator calculates the mean value of the better explosion sparks. The number of better sparks is deﬁned as µ, whereas the number of all the sparks is denoted as λ. The mean value of better sparks is represented as m and calculated by the following equation.

${m}=\sum \limits _{i=1}^{\mu }{{w_{i}}{x_{i}}},$

where $w_{i}$ is the weight of the $i^{th}$ spark and individual $x_{i}$ represents the $i^{th}$ better spark selected. The parameter $w_{i}$ is calculated as follows.

${w_{i}}={1}/{\mu }\quad (i=1,2,...,\mu ).$

It is clear that $m$ is the mean value of the µ individuals, not of all individuals.

Secondly, the mutation operator calculates the covariance matrix C.

$C=\left({\begin{array}{*{20}{c}}{cov({d_{1}},{d_{1}})}&{cov({d_{1}},{d_{2}})}&\cdots &{cov({d_{1}},{d_{D}})}\\{cov({d_{2}},{d_{1}})}&{cov({d_{2}},{d_{2}})}&{}&\vdots \\\vdots &{}&\ddots &\vdots \\{{\mathop {\rm {cov}} }({d_{D}},{d_{1}})}&\cdots &\cdots &{cov({d_{D}},{d_{D}})}\end{array}}\right),$

where $cov(d_{i},d_{j})$ stands for the covariance of the sparks in $i^{th}$ and $j^{th}$ dimension. Vector $d_{i}$ represents the sparks in the $i^{th}$ dimension and $D$ denotes the number of dimensions.

${\mathop {\rm {cov}} }(a,b)={\frac {\sum \limits _{i=1}^{\mu }{({a_{i}}-{\bar {A}})({b_{i}}-{\bar {B}})}}{\mu }},$

where ${\bar {A}}$ and ${\bar {B}}$ denote the mean values of $\lambda$ sparks in different dimensions. Moreover, $a_{i}$ is the $i^{th}$ data in the former dimension and $b_{i}$ is the $i^{th}$ data in the latter dimension. Note that $\mu -1$ is taken as a denominator when calculating the covariance, but the denominator is $\mu$ . Therefore, the way to calculate the covariance is different from the usual way.

Thirdly, the mutation operator utilizes the mean value $m$ and covariance matrix C to produce mutation sparks according with normal distribution.

Mapping Rule

If a ﬁrework is near the boundary of the feasible space, while its explosion amplitude covers both the feasible and infeasible space, the generated sparks may lie out of the feasible space. As such, the spark beyond the feasible space is useless. Therefore, it needs to be getting back into the feasible space. The mapping rule is used to deal with this situation. The mapping rule ensures that all sparks are in the feasible space. If there is any spark that is generated by a ﬁrework beyond the feasible space, it will be mapped back to the feasible space.

Selection Strategy

After applying the explosion operator, the mutation operator and the mapping rule, some of the generated sparks need to be selected and passed down to the next generation. The distance-based strategy is used in ﬁreworks algorithm. In order to select the sparks for next generation, ﬁrst of all, the best spark is always kept for next generation. And then, the other (N − 1) individuals are selected based on distance maintaining the diversity of the population. The individual that is farther from other individuals has more chance to be selected than those individuals near the other individuals.

Implementation of FWA

FWA starts to run iteratively till the given termination conditions are met. It consists of the explosion operator, the mutation operator, the mapping rule and the selection strategy. There are two termination conditions, such as meeting the accuracy requirements or reach the maximum number of function evaluations.

The realization of FWA consists of four steps as follows.

1. Randomly generate ﬁreworks in the feasible space.

2. Calculate the ﬁtness value of each ﬁrework according to the ﬁtness function. The number of sparks is calculated based on immune concentration theory in immunology and the ﬁreworks with better ﬁtness values produce more sparks.

3. Considering the ﬁreworks phenomena in reality and the landscape of the functions, the ﬁreworks generate sparks within a certain amplitude in FWA. The explosion amplitude is determined by the ﬁtness value of that ﬁrework. The explosion amplitude for the ﬁrework with better ﬁtness value is smaller and vice versa. Each spark represents a solution in the feasible space. To keep the diversity of the population, mutation operation is needed and the Gaussian mutation is one of them.

4. Calculate the best ﬁtness value. If the terminal condition is met, stop the algorithm. Otherwise, continue the iteration process. The best spark and the selected sparks formed a new population.

Applications of FWA

Fireworks algorithm can be applied to many real-life applications that requires to solve optimization algorithms. These applications can be generally transferred to single objective or multiple objective optimization problems, and thus ﬁreworks algorithm can be applied to solve these problems easily and directly. We will verify how ﬁreworks algorithms can be applied to various applications in different areas. These applications include related pattern recognition problems (non-negative matrix factorization, document clustering, spam detection and image recognition), complex model estimation problem (seismic inversion) and emerging swarm robotics searching problem. These applications sit in areas differs greatly than each other and have different requirements for the optimization algorithms. Fireworks algorithm can solve these problems successfully which illustrates that FWA has a great adaptiveness to different requirements in real-world applications.

File:The ﬂowchart of FWA..png

The ﬂowchart of FWA.

External links

http://www.cil.pku.edu.cn/research/fa/

This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it.

^ Tan, Ying. Fireworks Algorithm - Springer. doi:10.1007/978-3-662-46353-6.
^ Yu, Chao; Kelley, L. C.; Tan, Ying (2015-05-01). "Dynamic search fireworks algorithm with covariance mutation for solving the CEC 2015 learning based competition problems". 2015 IEEE Congress on Evolutionary Computation (CEC): 1106–1112. doi:10.1109/CEC.2015.7257013.

[1] Tan, Ying. Fireworks Algorithm - Springer. doi:10.1007/978-3-662-46353-6.

[2] Yu, Chao; Kelley, L. C.; Tan, Ying (2015-05-01). "Dynamic search fireworks algorithm with covariance mutation for solving the CEC 2015 learning based competition problems". 2015 IEEE Congress on Evolutionary Computation (CEC): 1106–1112. doi:10.1109/CEC.2015.7257013.

[1]

[2]