3.1 Quantum fireworks optimization algorithm model (QFA)
The fireworks algorithm (FA) is the simulation of the entire fireworks explosion process. When the fireworks explode, a large number of sparks will be generated, and the sparks can continue to explode, resulting in beautiful and colorful patterns. In the fireworks algorithm, each firework can be regarded as a feasible solution in the solution space of the optimization problem, so the spark generated by fireworks explosion can be regarded as a process of searching for the optimal solution. In the specific optimization problem, the fireworks algorithm needs to consider the number of sparks produced by each fireworks explosion, the explosion radius, and how to select a set of optimal fireworks and sparks to carry out the next explosion.
In the fireworks algorithm, the most important three components are explosion operator, mutation operator, and selection strategy.
(1) Explosion operator: The number
Si and radius
Ai of sparks produced by each firework
xi(
i = 1, 2⋯
n) are calculated according to the fitness of the fireworks.
$$ {S}_i=M\times \frac{y_{\mathrm{max}}-f\left({x}_i\right)+\varepsilon }{\sum \limits_{i=1}^N\left({y}_{\mathrm{max}}-f\left({x}_i\right)\right)+\varepsilon } $$
(1)
$$ {R}_i=\widehat{R}\times \frac{f\left({x}_i\right)-{y}_{\mathrm{min}}+\varepsilon }{\sum \limits_{i=1}^N\left(f\left({x}_i\right)-{y}_{\mathrm{min}}\right)+\varepsilon } $$
(2)
In the above formula, ymax and ymin represent the maximum and minimum fitness values of the current population, f(xi) is the fitness value of fireworks xi, and M is a constant, which is used to adjust the number of sparks produced. \( \widehat{R} \) is a constant, which is used to adjust the explosion radius of fireworks. ε is the smallest part of the machine to avoid zero operation.
(2) Mutation operator: The mutation operator is set to increase the diversity of the explosive spark population. The mutation spark in the fireworks algorithm is to generate the Gaussian mutation spark by the Gaussian mutation of the explosive spark. Assuming that fireworks xi is selected for Gaussian mutation, the k-dimensional Gaussian mutation operation is \( {\widehat{x}}_{ik}={x}_{ik}\times e \), where xik represents k-dimensional variant fireworks and e represents N(1, 1) Gaussian distribution.
The explosive sparks and mutation sparks generated by the explosive operator and mutation operator in the spark algorithm may exceed the boundaries of the feasible region Ω, which is mapped to a new position by mapping rules. The formula is as follows:
$$ {\widehat{x}}_{ik}={x}_{LB,k}+\left|{\widehat{x}}_{ik}\right|\%\left({x}_{UB,k}-{x}_{LB,k}\right) $$
(3)
where xUB, k and xLB, k is the upper and lower bounds of solution space on k dimension respectively.
(3) Selection strategy: In order to transmit the information of the excellent individuals in the group to the next generation, it is necessary to select a certain number of individuals as the fireworks of the next generation from the explosive sparks and variant sparks.
Assuming
K candidates and
N populations, the individuals with the best fitness in the candidate set will be identified as the next-generation fireworks. The remaining
N − 1 fireworks are selected by probability. For fireworks
xi, the probability formula for its selection is:
$$ p\left({x}_i\right)=\frac{R\left({x}_i\right)}{\sum \limits_{x_j\in K}{x}_j} $$
(4)
$$ R\left({x}_i\right)=\sum \limits_{x_j\in K}d\left({x}_i-{x}_j\right)=\sum \limits_{x_j\in K}\left|{x}_i-{x}_j\right| $$
(5)
In the upper form, R(xi) is the sum of the distances between all the individuals in the current individual candidate set. In the candidate set, if the individual density is high, that is, when there are other candidates around the individual, the probability of the individual being selected will be reduced.
3.2 Quantum evolutionary algorithm
The development of quantum mechanics makes quantum computation more and more applied in all aspects. In quantum computation, the representation of quantum states is performed by quantum bits. Usually, the representation of quantum information is performed by the 0 and 1 binary method; besides the “0” and “1” states which can be in the basic state, the quantum states can also be in the arbitrary linear superposition of the “0” and “1” states, that is, the two states can be in the same state at the same time. To a great extent, it challenges the representation of classical positions in classical mechanics. The superposition state of quantum state can be expressed by the lower form:
$$ \left|\psi \ge \alpha \right|0>+\beta \mid 1>,{\left|\alpha \right|}^2+{\left|\beta \right|}^2=1 $$
(6)
In the above formula, 0 and 1 denote two states of a quantum;
α and
β denote the probability amplitude of a quantum; |
α|
2 denotes the probability of a quantum state at 0; and |
β|
2 denotes the probability of a quantum state at 1. Quantum algorithm is updated through quantum revolving door, and its adjustment strategy is as follows:
$$ \left(\begin{array}{l}{\alpha}_i^{\hbox{'}}\\ {}{\beta}_i^{\hbox{'}}\end{array}\right)=\left(\begin{array}{cc}\cos \left(\theta \right)& -\sin \left(\theta \right)\\ {}\sin \left(\theta \right)& \cos \left(\theta \right)\end{array}\right)\left(\begin{array}{l}{\alpha}_i\\ {}{\beta}_i\end{array}\right) $$
(7)
where
\( \left(\begin{array}{cc}\cos \left(\theta \right)& -\sin \left(\theta \right)\\ {}\sin \left(\theta \right)& \cos \left(\theta \right)\end{array}\right) \) is a quantum revolving gate and
θ is a quantum rotation angle.
Quantum evolutionary algorithm is a kind of algorithm based on probability search. The concept of quantum bit and quantum superposition makes quantum evolutionary algorithm have many advantages, such as better population diversity and strong global optimization ability, especially the algorithm has strong robustness and can be well combined with other algorithms.
3.3 Quantum fireworks algorithm
In the solution space,
N fireworks are randomly generated and their coordinates are initialized. Here, we use the probability amplitude of the quantum bit as the encoding of the current position of the fireworks.
$$ {p}_i=\left[\begin{array}{l}\cos \left({\theta}_{i1}\right)\kern0.5em \cos \left({\theta}_{i2}\right)\kern0.5em \cdots \kern0.5em \cos \left({\theta}_{in}\right)\\ {}\sin \left({\theta}_{i1}\right)\kern0.5em \sin \left({\theta}_{i2}\right)\kern0.5em \cdots \kern0.5em \sin \left({\theta}_{in}\right)\end{array}\right] $$
(8)
where
θij = 2
πrand() is a random number and the
n is the number of solution space.
i = 1, 2, ⋯
n.Therefore, the probability amplitudes of the quantum states of ∣0> and ∣1> are as follows:
$$ {p}_{ic}=\left(\cos \left({\theta}_{i1}\right)\kern0.5em \cos \left({\theta}_{i2}\right)\kern0.5em \cdots \kern0.5em \cos \left({\theta}_{in}\right)\right) $$
(9)
$$ {p}_{is}=\left(\sin \left({\theta}_{i1}\right)\kern0.5em \sin \left({\theta}_{i2}\right)\kern0.5em \cdots \kern0.5em \sin \left({\theta}_{in}\right)\right) $$
(10)
(2)
Solution space transformation
The searching process of fireworks optimization algorithm is carried out in the actual parameter space [a, b]. Since the probabilistic amplitude of fireworks location is within [0, 1], it is necessary to decode the probabilistic amplitude into the actual parameter space [a, b], so as to facilitate the searching of fireworks algorithm; if the firework on the individual fireworks
pi is
\( \left[{\alpha}_i^j,{\beta}_i^j\right] \), the corresponding solution space is changed. The formula is
$$ {X}_{ic}^j=0.5\left[{b}_i\left(1+{\alpha}_i^j\right)+{a}_i\left(1-{\alpha}_i^j\right)\right]\kern0.5em \operatorname{rand}\left(\right)<{p}_{id} $$
(11)
$$ {X}_{is}^j=0.5\left[{b}_i\left(1+{\beta}_i^j\right)+{a}_i\left(1-{\beta}_i^j\right)\right]\kern0.5em \operatorname{rand}\left(\right)>{p}_{id} $$
(12)
where rand() is the random number between [0, 1];
\( {X}_{ic}^j \) is the actual parameter value of the position of the
jth dimension when the quantum state of the first fireworks individual is ∣0>;
\( {X}_{is}^j \) is the actual parameter value of the position of the
jth dimension when the quantum state of the second fireworks individual is ∣1>.
ai and
bi are the upper and lower limits of individual
pi search range respectively.
(3)
Fitness value f(xi) of each firework was calculated, and the number of sparks produced by the explosion radius Ri of each firework was calculated as formulas (1 and 2)
(4)
Fireworks individual location update
In this paper, the quantum revolving gate is used to replace the uniformly distributed
U(
a,
b) to update the position of fireworks.
$$ \left(\begin{array}{l}{\alpha}_{jd}^{k+1}\\ {}{\beta}_{jd}^{k+1}\end{array}\right)=\left(\begin{array}{cc}\cos \left({\theta}_{jd}^{k+1}\right)& -\sin \left({\theta}_{jd}^{k+1}\right)\\ {}\sin \left({\theta}_{jd}^{k+1}\right)& \cos \left({\theta}_{jd}^{k+1}\right)\end{array}\right)\left(\begin{array}{l}{\alpha}_{jd}^k\\ {}{\beta}_{jd}^k\end{array}\right) $$
(13)
\( {\alpha}_{jd}^{k+1} \),
\( {\beta}_{jd}^{k+1} \) is the probability amplitude of the
j-firework
d-dimension space in the first
k + 1 iteration.
\( {\theta}_{jd}^{k+1} \) is the rotation angle. In addition, to adapt to the operation mechanism of fireworks algorithm, the updated probability amplitudes
\( {\alpha}_{jd}^{k+1} \) and
\( {\beta}_{jd}^{k+1} \) are transformed into solution spaces.
$$ {X}_{ic}^j=0.5\left[{b}_i\left(1+{\alpha}_{jd}^{k+1}\right)+{a}_i\left(1-{\alpha}_{jd}^{k+1}\right)\right]\kern0.5em \operatorname{rand}\left(\right)<{p}_{id} $$
(14)
$$ {X}_{is}^j=0.5\left[{b}_i\left(1+{\beta}_{jd}^{k+1}\right)+{a}_i\left(1-{\beta}_{jd}^{k+1}\right)\right]\kern0.5em \operatorname{rand}\left(\right)>{p}_{id} $$
(15)
And then calculate the position offset:
$$ {h}_{jc}^d={R}_i\times {X}_{jc}^d $$
(16)
$$ {h}_{js}^d={R}_i\times {X}_{js}^d $$
(17)
In cross-boundary detection, if the spark of explosion exceeds the boundary of feasible region, the particle position is updated according to formula (
3):
(5)
Individual mutation operation
The main reason for premature convergence and local optimum of fireworks population is that the diversity of the population is lost in the process of searching. In quantum fireworks algorithm, quantum mutation is used to replace the Gaussian mutation in the original algorithm to increase the diversity of the population, thus effectively avoiding the abovementioned problems; random selecting of fireworks
xi, quantum variation spark
\( \widehat{M} \) is generated. Its operation is shown in the following formula:
$$ \left[\begin{array}{l}01\\ {}10\end{array}\right]\left[\begin{array}{l}\cos \left({\theta}_{ij}\right)\\ {}\sin \left({\theta}_{ij}\right)\end{array}\right]=\left[\begin{array}{l}\cos \left(\frac{\pi }{2}-{\theta}_{ij}\right)\\ {}\sin \left(\frac{\pi }{2}-{\theta}_{ij}\right)\end{array}\right] $$
(18)
The probability of individual variation of fireworks is
pm, and rand () is a random number between 1,0; if rand() <
pm, the above formula is used to mutate the individual fireworks, change the probability amplitude in the quantum bit, and finally transform the mutated individual fireworks into a solution space and save it to the mutated spark population.
$$ {X}_{jc}^d=\frac{1}{2}\left[{b}_j\left(1+\cos \left(\frac{\pi }{2}-{\theta}_{ij}\right)\right)+{a}_j\left(1-\cos \left(\frac{\pi }{2}-{\theta}_{ij}\right)\right)\right]\kern0.5em \operatorname{rand}\left(\right)<{p}_{id} $$
(19a)
$$ {X}_{js}^d=\frac{1}{2}\left[{b}_j\left(1+\sin \left(\frac{\pi }{2}-{\theta}_{ij}\right)\right)+{a}_j\left(1-\sin \left(\frac{\pi }{2}-{\theta}_{ij}\right)\right)\right]\kern0.5em \operatorname{rand}\left(\right)>{p}_{id} $$
(19b)
(6)
Using the probability selection formula from fireworks, explosive sparks and Gaussian variant spark population p(xi) selects N individuals as fireworks for next-generation iteration calculation