1 Introduction

In real-life, there are many complicated problems which cannot be solved easily. Exact optimization algorithms may be chosen to solve these complex problems; However, high dimensionality and non-differentiability properties of hard-computing problems, make exact optimization algorithms unsuitable tools to achieve a good result. Hence, approximate algorithms have been introduced to solve complex problems, faster and more reliable. Generally, searching algorithms are classified into two main categories: individual-based and population-based algorithms. There are some advantages and disadvantages for these two categories. For example, individual-based algorithms are fast in process and reliable for simple models. However, they depend on gradient information and cannot find global optimums in complex problems. Second group can fly from local optima better than first group and overcome complex environments with information sharing between individuals. However, they suffer from high computational cost compared to individual-based algorithms.

In literature, various meta-heuristic algorithms like physics-based [2, 19, 39, 46, 47], nature-based [6, 26, 34, 40, 48], animal-based [7, 22, 25, 42, 43], mathematics-based [31, 36, 41], evolutionary-based [13, 44] and virus-based [23, 32] algorithms have been reported. Physical laws of nature are basic ideas of physics-based algorithms which try to model physical relations to solve the problem. Nature-based algorithms are inspired by natural phenomena like lightning, ocean ecosystem, plant growth etc. The inspiration of animal-based algorithms is the behavior of animals in the co-operative foraging, mating fight etc. Mathematics-based algorithms are another group of meta-heuristic algorithms which consider the mathematic relations like gradient theorem, sine and cosine functions, … to find the solution. Evolutionary-based algorithms use natural selection or Darwinian theory to converge the global optimum. However, the implementation of Darwinian theory is different in this group of meta-heuristic algorithms. Virus-based algorithms are inspired by attacking, transmission and activity of virus in human bodies.

The mechanism of population-based algorithms is generally similar. The algorithm starts with initial candidate solutions. Usually, they are generated randomly with uniform distribution to cover the space. Then, the algorithm tries to find better locations in the searching process from generation to generation according to updating rules. Finally, the algorithm converges to the reasonable optimum by the end of run. However, there are some drawbacks to achieve the goal. Maintaining diversity is one of the major challenges of the meta-heuristic algorithms in solving complex problems. Also, premature convergence and becoming trapped in the local optima are other concerns of the optimization algorithms. To overcome these shortages, several algorithms have been developed in recent decades [24, 29].

Dhiman and Kaur introduced Sooty Tern Optimization Algorithm (STOA) to compromise between exploration and exploitation terms in the searching strategy [9]. To continue with the survey of articles, a new searching algorithm based on spiral movement of emperor penguins in the colony was proposed to solve different optimization problems [17]. Bouchekara developed a novel approach based on interaction between electric charged particles to design a circular antenna array [4]. Fathollahi-Fard et al. considered the mating behavior of the male red deer and suggested a new algorithm in this issue [12]. Black Widow Optimization (BWO) is another meta-heuristic approach which was reported for continuous nonlinear problems [21]. In literature, various algorithms are introduced in different issues by researchers. For example, Khare et al. proposed a hybrid classifier model for intrusion detection [30]. Recently, a novel optimizer inspired by barnacles mating behavior was introduced to solve reactive power dispatch problems [45].

In this paper, a novel meta-heuristic algorithm inspired by the explosion of fireworks in the sky, is introduced. We found out categorizing of the population helps the algorithm avoid trapping in local optima points and leads to faster convergence. Hence, three different categories are defined to cover most volunteer solutions of the global optimum and better sweep the search space. The proposed method is set by local optimum knowledge which has been obtained before and tries to find better locations according to distance between sub-optimal points. A strict selection is considered to optimize the elitism strategy and vast random search is applied to reinforce the exploration. The innovations of our work are summarized as follows: 1) simplicity: FOA is as easy as well as robust searching algorithm. 2) efficient update rules: the location of light particles is updated with new rules which have not been reported before. 3) few control parameters: FOA has only two tuning parameters to explore searching space. Also, adapting formulas are suggested for these two parameters. 4) selection: new selection mechanism is employed in FOA algorithm.

The remainder of the paper is arranged as follows: The Fireworks Optimization Algorithm (FOA) is described in details and basic steps of the implementation are given in Section 2. The proposed algorithm is tested using famous continuous benchmarks and well-known test images and comparative results are presented in Section 3. Finally, Section 4 concludes this work.

2 Fireworks optimization algorithm

FOA is inspired by the explosion of pyrotechnic devices in the sky with production of noise, light and smoke. In some cases, explosion repeats several times from the beginning point like a branch (Fig. 1a). It means that a spike can blast and produce new spikes around itself and this exhibition continues to illuminate the sky. We model a population-based searching algorithm, named Fireworks Optimization Algorithm (FOA) from the behavior of fireworks explosion.

Fig. 1
figure 1

a Fireworks display in the night sky, b population framework in FOA

Full size image

The step-wise implementation of FOA is described as follows:

  1. Step 1:

    similar to other heuristic algorithms, initialization of the problem is the first step. Input range values (Lmin and Lmax), number of groups (G) and population size (N) are defined at this stage. The position of light particles is initialized as follows

$$ {\displaystyle \begin{array}{l}X\left\{i\right\}={L}_{min}+\left({L}_{max}-{L}_{min}\right)\times \boldsymbol{R}\\ {}i=1,\dots, G\\ {}\boldsymbol{R}={\left[{r}_{ij}\right]}_{\frac{N}{G}\times K}\kern0.75em ,\kern0.5em {r}_{ij}\in \left[0,1\right]\end{array}} $$
(1)

Where X{i} denotes the group number i which has \( \frac{N}{G} \) members. R is random matrix with uniform distribution arrays which has \( \frac{N}{G} \) rows and K columns. K is the dimension of the problem. The whole population X is aggregation of all groups.

$$ \boldsymbol{X}=\bigcup \limits_{i=1}^GX\left\{i\right\}=\left[\begin{array}{ccc}{x}_{11}& \cdots & {x}_{1K}\\ {}\vdots & \ddots & \vdots \\ {}{x}_{N1}& \dots & {x}_{NK}\end{array}\right]\kern0.5em $$
(2)
  1. Step 2:

    evaluate fitness of all individuals. The best position of a group named GroupBest and the best position of all members is known as GBest.

  2. Step 3:

    every group has three categories: a, b and c as shown in Fig. 1b. Members belong to category a search the distance between GBest and GroupBest. The position update mechanism of category a is different from discrete and continuous versions; because, in the discrete problem, the search space is countable and the exploitation is more reliable than exploration. Instead, in the continuous problem, more exploration is needed to reach a feasible solution. The second category is category b which tries to find valuable solutions between GroupBests. Category c is the last category of the population which searches the area around GBest. The category c is considered in the algorithm to maintain the diversity of the population.

In two categories a and b, positions are updated by GroupBest and GBest, which reduces the diversity of the whole population. The update rule of individuals is defined as

  • For discrete space

$$ {x}_i\left(t+1\right)=\left\{\begin{array}{c}{G}_{Best}(t)+{p}_1\times {r}_1\times \left[{G}_{Best}(t)-{Group}_{Best\ i}\ (t)\right]\kern0.75em if\ {x}_i\in cat\ a\\ {}\\ {}{Group}_{Best\ i}\ (t)+{r}_2\times \left[{Group}_{Best\ m}-{Group}_{Best\ n}\right]\kern0.75em if\ {x}_i\in cat\ b\ \\ {}\\ {}{G}_{Best}(t)+{p}_2\times {r}_3\times \left[{L}_{max}-{L}_{min}\right]\kern8em if\ {x}_i\in cat\ c\end{array}\right. $$
(3-a)

  • For continuous space

$$ {x}_i\left(t+1\right)=\left\{\begin{array}{c}{p}_1\left[{r}_1\times \left({L}_{max}-{L}_{min}\right)+{r}_2\times \left({G}_{Best}(t)-{Group}_{Best\ i}\ (t)\right)\right]\kern0.5em if\ {x}_i\in cat\ a\\ {}\\ {}{Group}_{Best\ i}\ (t)+{r}_3\times \left[{Group}_{Best\ m}-{Group}_{Best\ n}\right]\kern0.75em if\ {x}_i\in cat\ b\ \\ {}\\ {}{r}_4\times {G}_{Best}(t)\kern9.25em if\ {x}_i\in cat\ c\end{array}\right. $$
(3-b)

The convergence of the algorithm is guaranteed. When the algorithm finds a good solution, all light particles begin to approach GBest and three so-called categories stop searching. To clarify the matter, we trace the population in two sequence iterations in Fig. 2. Three groups are considered in this figure. Every group has initial members and after the fitness calculation, GBest and GroupBests are assigned. Then, the only GroupBests remains and generates new group population according to the distance between neighbor GroupBest and GBest. Figure 2b shows population generation of group 1 in the next iteration.

Fig. 2
figure 2

Population generation in two sequence iterations

Full size image

According to above description, the pseudocode of FOA is shown in Fig. 3.

Fig. 3
figure 3

Pseudo code of FOA

Full size image

Similar to other natural-inspired algorithms, initialization is done by the random process. We used a grouping strategy to avoid premature convergence of the proposed algorithm. This technique was considered in various algorithms such as GGSA [10]. In FOA, the best individual is noted as GBest and produces a new generation which acts as GBest in PSO or leader in SSA [38]. However, update rules are different in concept. Elitism is employed in our algorithm to prune the offspring generation which some methods such as ADS [18] and ALO [35] have used this technique before. Also, in FOA control parameters (i.e., p1 and p2) have been adapted to the iteration number like WOA [37].

3 Results and discussions

To evaluate the robustness of the introduced searching algorithm and compare it with other state-of-art natural-inspired methods, two experiments are done in this section. In the first experiment, image thresholding is considered. Multilevel thresholding is a segmentation method which partitions the image I into two or more subsets based on t threshold values. It is considered that a gray-scale image has L intensity levels. Multilevel thresholding can be defined as

$$ {\displaystyle \begin{array}{c}{R}_0=\Big\{g\left(x,y\right)\in I\left|0\le g\left(x,y\right)\le {t}_1-1\kern4.75em \right.\\ {}\vdots \\ {}{R}_K=\Big\{g\left(x,y\right)\in I\left|{t}_K\le g\left(x,y\right)\le L-1\kern4.5em \right.\end{array}} $$
(4)

Where g(x, y) is an image pixel, ti (i = 1, …, k) indicates threshold value and K is the total threshold number. A criterion which is used in the multilevel thresholding is the energy function. To define the energy function of an image, a neighbourhood system of pixels must be introduced first. The neighbourhood mask N of order d for a pixel located at (i, j) is configured as \( {N}_{pq}^d=\left\{\left(i+u,j+v\Big),\left(u,v\right)\in {N}^d\right)\right\} \) [15]. We only study the second order of neighbourhood (i.e d = 2). The second order neighbourhood mask \( {N}_{ij}^2 \) is shown in Fig. 4.

Fig. 4
figure 4

Neighbourhood of central pixel (i, j)

Full size image

Energy function is calculated for each gray level. For a given gray level l, a binary matrix Bl with the size of m × n (the same size as the original image) is built as Bl = {bij, 1 ≤ i ≤ m, 1 ≤ j ≤ n} where bij = 1 if g(x, y) > l; else bij =  − 1. In other words, Bl indicates which pixel of the original image has lower or upper intensity than level l. Similarly, another matrix C is defined as C = {cij, 1 ≤ i ≤ m, 1 ≤ j ≤ n} with elements of ones. i.e. cij = 1, ∀ (i, j). Energy function at gray level l is formulated as

$$ {E}_l=\sum \limits_{i=1}^m\sum \limits_{j=1}^n\sum \limits_{pq\in {N}_{ij}^2}\left({c}_{ij}{c}_{pq}-{b}_{ij}{b}_{pq}\right)\kern0.5em $$
(5)

We define the matrix C to satisfy the positive energy condition El ≥ 0. Kapur method is an entropy-based criterion which tries to make a centralized PDF distribution for each class on the segmented histogram [27]. The early algorithm is proposed for bi-level thresholding which tries to obtain an optimal threshold to extract the object from the background. Then this concept is applied to multilevel thresholding and utilized in many research studies. The thresholding problem can be mentioned as follows.

$$ \operatorname{Maximize}\ f\left({t}_0,\dots, {t}_K\right)={\sum}_{i=0}^K{H}_i $$

Where

$$ {\displaystyle \begin{array}{c}{H}_0=-\sum \limits_{i=0}^{t_1-1}\frac{p_i}{\omega_0}\ln \frac{p_i}{\omega_0}\\ {}\vdots \\ {}{H}_K=-\sum \limits_{i={t}_K}^{L-1}\frac{p_i}{\omega_K}\ln \frac{p_i}{\omega_K}\end{array}} $$
(6)

Eight famous methods, differential evolution (DE) [3], particle swarm optimization (PSO) [11], bat algorithm search (BAT) [5], flower pollination algorithm (FPA) [1], artificial bee colony (ABC) [28], harmony search (HS) [33], grey wolf optimizer (GWO) [20] and whale optimization algorithm (WOA) [14] with FOA are implemented to solve the image thresholding on the test images shown in Fig. 5 to prove the superiority of our proposed method. These methods are selected because of their good performance in previous works of image segmentation. These test images are well-known classical benchmarks used in the image processing literature. Figure 6 shows the related energy curve of images.

Fig. 5
figure 5

Classical test images used to evaluate the proposed algorithm

Full size image
Fig. 6
figure 6

Energy curve of test images. a energy curve of Test 1, b energy curve of Test 2, c energy curve of Test 3, d energy curve of Test 4, e energy curve of Test 5, f energy curve of Test 6, g energy curve of Test 7, h energy curve of Test 8, i energy curve of Test 9, j energy curve of Test 10

Full size image

Kapur entropy is selected to compare the efficiency of different methods and the accuracy of the obtained solutions. To have an identical condition, the initial members of the searching methods are selected from the uniform distribution between [0, 255]. The goal is to find the best threshold values of four levels. To obtain a fair comparison between the searching algorithms, the number of iterations is set to 30, and the population size is assigned 150 for all methods. The control parameters of meta-heuristic algorithms are listed in Table 1. These parameters are chosen from original papers and best achieved by a trial-error procedure. The results are shown in Tables 2 and 3. The shown fitness is the average score of running each algorithm over 30 times and four threshold levels relate to the best optimal solution found by the algorithm over these runs. The peak signal to noise ratio (PSNR) is defined as

$$ PSNR=20\ \mathit{\log}\left(255/ RMSE\right)\kern1.5em $$
(7-a)
$$ RMSE=\sqrt{\sum \limits_{i=1}^M\sum \limits_{j=1}^N{\left(I\left(i,j\right)-I\prime \left(i,j\right)\right)}^2/ MN}\kern1.25em $$
(7-b)

Where, N are the size of the test image, I(i, j) and I ′ (i, j) denote original and segmented images respectively and RMSE is the root mean-squared error between original and segmented images. SSIM describes the similarity of original and output images, which is defined as

$$ SSIM=\frac{\left(2{\mu}_I{\mu}_{I^{\prime }}+{c}_1\right)\left(2{\sigma}_{I{I}^{\prime }}+{c}_2\right)}{\left({\upmu}_I^2+{\mu}_{I^{\prime}}^2+{c}_1\right)\left({\sigma}_I^2+{\sigma}_{I^{\prime}}^2+{c}_2\right)}\kern1.25em $$
(8)

Where μ and σ are the mean and variance of I and I’ images respectively.\( {\sigma}_{I{I}^{\prime }} \) is the covariance between I and I’. c1 and c2 are the constants related to the pixel-values. Apparently, higher PSNR or SSIM indicates better image segmentation. These measurements increase with higher threshold values because the segmentation process is done resulting in higher precision. Tables 4 and 5 present PSNR and SSIM values of different algorithms respectively. We can observe from these tables that FOA gives better results than other algorithms; because, these algorithms converge in local sub-regions and cannot give satisfying threshold values. However, FOA achieves higher values in terms of objective function over 30 runs and outperforms other methods in exploring and exploiting the search space. Therefore, FOA is an efficient method for image multi-level thresholding as it does not waste time to search invaluable areas and manages the diversity of searching agents properly.

Table 1 Control parameters for searching algorithms
Full size table
Table 2 Obtained threshold results of different algorithms based on Kapur method (level = 4)
Full size table
Table 3 Obtained fitness results of different algorithms based on Kapur method (level = 4)
Full size table
Table 4 PSNR values using Kapur method for 4 levels thresholding
Full size table
Table 5 SSIM values using Kapur method for 4 levels thresholding
Full size table

The segmented images based on Kapur method are shown in Figs. 7 and 8. The convergence curves of test images based on Kapur method are shown in Fig. 9 with 30 iterations. Fitness plots reveals that in most cases, FOA converges to the global optima in fewer iterations uniformly in comparison with other methods. Moreover, the proposed algorithm achieves higher Kapur fitness values in all test images. For example, for test 1 the sequence is FPA < HS < WOA < PSO < ABC < BAT< DE < GWO < FOA according the increasing order of fitness.

Fig. 7
figure 7

Segmented images based on Otsu method (level = 4)

Full size image
Fig. 8
figure 8

Segmented images based on Otsu method (level = 4)

Full size image
Fig. 9
figure 9

Convergence curves based on Kapur method (level = 4)

Full size image

Also, to prove the competency of the proposed algorithm, performance of FOA based multilevel thresholding method is tested by 20 images which have been selected from two MRI (Magnetic Resonance Imaging) and SAR (Synthetic-Aperture Radar) datasets and results are compared with other methods. Two metrics, Kapur fitness and RMSE (Root Mean Square Error) are considered in this experiment. Figure 10 depicts these MRI and SAR test images.

Fig. 10
figure 10

Original test images, MRI images: test 11 to test 20, SAR images: test 21 to test 30

Full size image

For all the algorithms the population size is kept at 150 and number of iterations is set to 30 for K = 4. Table 6 reports mean fitness of Kapur entropy over 30 independent runs. The best results are marked in boldface. As seen in this table, FOA clearly outperforms its competitors except for test 21 and test 24. RMSE measurements are computed through threshold value K = 4 and results are shown in Table 7. According to this table, FOA produces better results in 7 cases of 20 cases which achieves first rank while the second rank goes to ABC. This means that FOA exhibits more detailed and accurate image information at threshold level 4.

Table 6 Comparison of Kapur fitness values computed by various algorithms (level = 4)
Full size table
Table 7 Comparison of RMSE values computed by various algorithms (level = 4)
Full size table

In the next experiment, natural-inspired algorithms are examined by multimodal continuous problems and a number of optimization benchmarks are tested to evaluate the robustness of algorithms. Table 8 shows these benchmark functions with their global minimum. Similar to the first experiment, the population is set to 150 and 30 runs is considered. The results are shown in Table 9. According to this table, we concluded that FOA has an excellent performance in low dimensional problems and provides good solutions in most cases of high dimensional problems. It can be seen that FOA obtains the best results in 21 cases as first rank and WOA in 11 cases as the second rank. Other methods have not significant superiority over FOA and WOA. It means that FOA searches the space with a better sensitivity compared to other classical algorithms and converges to the global optimum faster than others; because, the mechanism of exploring is better organized and fewer individuals get stuck in the local optimums.

Table 8 Benchmark functions with formula and global minimum for \( \overset{\rightharpoonup }{x}=\left[{x}_1,\dots, {x}_K\right] \)
Full size table
Table 9 Obtained results of executing different algorithms over 30 runs
Full size table

A processing time comparison of various methods based on above benchmarks is considered to evaluate the convergence speed. Figure 11 shows the average running time of executing different algorithms over test functions. Based on obtained data, we conclude that FOA has an accepting computation time in solving continuous problems. Taking into account of the computational time, we can line up them as BAT < PSO < HS < DE < WOA < GWO < FOA < FPA < ABC according to the increasing order of execution time. Although BAT ranks to be the first among them, it suffers the problem of converging to local optimum points.

Fig. 11
figure 11

Average running time of executing different algorithms

Full size image

Moreover, a statistical pair-wise test named Wilcoxon signed rank test is examined to determine the accuracy of the null hypothesis (same distribution of populations) [8]. Wilcoxon signed rank test returns p-values which should be less than 0.05 to reject the null hypothesis with 95% confidence. This test is done for various methods over 30 runs and results are registered in Table 10 for benchmark functions. The values more than 0.05 are boldfaced. From the overall comparison of obtained data, it can be stated that FOA performs significantly better than other meta-heuristic algorithms.

Table 10 Comparison results with FOA p-values and other algorithms over test functions
Full size table

As seen in results, FOA is a powerful algorithm to find solutions in discrete and continuous problems. However, it has a drawback. To produce next generation, GBest and GroupBest remain and other individuals are deleted. Hence, a strict selection mechanism is applied to the population and valuable potential solutions maybe eliminated in high dimensional problems. In these cases, increasing population size or keeping some random individuals helps the population diversity. Also, changing update rules according to first and second rank of GBest and GroupBest may mitigate this limitation.

4 Conclusion

A simple and robust meta-heuristic algorithm inspired by the explosion of fireworks in the sky, was suggested in this paper. With taking advantage of grouping the population, fewer individuals were fallen in local optimums and premature convergence was mitigated. Another technique used in FOA is categorizing members. Three categories were considered which help the algorithm sweeping the search space very well and saving the time to explore invaluable areas. FOA was presented in two continuous and discrete versions which have similar mechanism of finding the global optimum and are different a little in the updating location of sparks.

The experiments are conducted on 30 images for subjective as well as objective assessments on 4-levels image thresholding segmentations in the discrete space. Also, the objective analysis is done on 15 state-of-the-art continuous benchmarks and compared with eight methods namely; ABC, BAT, WOA, FPA, GWO, HS, PSO and DE. The effectiveness of the new method has been studied in terms of convergence behavior which uses Kapur entropy as an objective function for extracting optimal thresholds. The experimental analysis revealed that the proposed method outperforms the existing compared methods for multi-levels image thresholding segmentation as well as objective functions in the continuous version. Compared to other algorithms, we can conclude that the computational complexity of FOA is better than WOA, ABC and GWO.

Three main research directions are foreseen for future work. First, the possibility of extending the proposed optimization algorithm to other image processing domains like image enhancement and classification can be worked out. Second, improving this algorithm in attaining its global optima using Minimum Cross entropy and Renyis entropy can be investigated for different image datasets. Another research direction is applying FOA to deep learning training and parameter optimization in the smoke detection application [16].