1.
Introduction
Quantum computation (QC) is a new research field that has attracted the attention of many researchers in the past decade. Quantum computation is based on several principles of quantum theory, such as the qubit, the superposition of quantum states, the collapsing into one state, and entanglement [2,3]. Several review studies reviewed quantum computation computing methods, such as [4] which reviewed quantum computing methods, and [5] reviewed the important quantum supremacy and theoretical challenges. The authors in [6] addressed the scalable model for a distributed quantum computation. At the same time, a programmable superconducting processor was used to Quantum supremacy in [7]. In [8], Quantum Computing was discussed in the Noisy Intermediate-Scale Quantum era. Aaronson, S. and Chen, L in [9] reviewed some theoretical foundations for quantum computers as evidence of quantum supremacy. The challenges of building quantum computers and their applications were discussed in [10]. The authors in [11] addressed the challenges of quantum information technology such as quantum interconnects, quantum internet, superconducting, etc. Also, in [12], they proposed a framework of quantum neural networks based on supervised learning over classical and quantum data. Lloyd, S in [13] modified the quantum approximate optimization algorithm using two alternating Hamiltonians.
In quantum computing, a quantum algorithm is an algorithm that runs on a realistic model of quantum computation, which can be classified into two categories [2,3,14]. The first category comprises the quantum algorithms that are implemented on quantum computers [15,16,17], such as Grover's quantum search [18], quantum annealing [19], and the adiabatic quantum algorithm [20]. The second category encompasses the Quantum-Inspired Evolutionary Algorithms based on principles of quantum computation, including standing waves, entanglement, and collapse algorithms. The second category is divided into two sub-categories. The first one includes quantum computing-inspired evolutionary algorithms that are based on several postulates of quantum computing. Q-bits are used instead of binary representations. Superposition, quantum gates, and quantum measurements are applied to solve varied optimization problems. Several good examples of Quantum-Inspired Algorithms (QIA) are the genetic algorithm [21], the cuckoo search and firefly algorithm [22], Quantum-inspired immune clone optimization [23], the artificial bee colony algorithm [24], the gravitational search algorithm [25], the binary firefly algorithm [26], the space search algorithm [27], and the harmony search algorithm [28]. The second one embraces evolutionary algorithms based on quantum concepts. The experience of every particle is used in quantum space. An individual particle of the quantum system moves in quantum multi-dimensional space based on the state of a particle. It is depicted by the wave function ψ(x,t) instead or by the position and velocity. Particle swarm optimization [29] and the gravitational search algorithm [25] are good examples of this type. Several previous studies established the quantum delta potential well-based model for several algorithms [30,31,32,33,34]. Moreover, the authors in [35] proposed a quantum-behaved gravitational search algorithm, where each candidate mass moves in a Delta potential well in the feasible space with a weighted average center of all kbests. In contrast, the authors in [36] proposed a novel version of the harmony search algorithm based on quantum concepts to solve the multi-objective optimizations problems. A similar study in [29], added a parameter to enhance the balance between the diversification and intensification of the quantum-behaved particle swarm optimization algorithm. Likewise, [37] used two methods to enhance a quantum particle swarm optimization based on Lévy fight and straight fight. The fruit fly optimization algorithm was improved based on a quantum Delta potential well [38]. The same, in [39] used quantum behaved to enhance fruit fly optimization algorithm. The authors in [40] hybridized the quantum evolutionary algorithm with the colliding bodies, then, they used delta potential well and Schrodinger's uncertainty principle to enhance the proposed hybrid algorithm. A truncated mean stabilization strategy is used to improve the diversification of quantum PSO in [41]. Three metaheuristics algorithms, particle swarm optimization, genetic algorithm, and firefly algorithm. were enhanced using the quantum concepts in [42]. In a similar study [43], beetle antennae search was improved based on quantum behaved.
On the other hand, several studies used quadratic interpolations to improve the convergences, such as [44] employed the quadratic interpolations to improve the controlled random search algorithm. Also, [45] compared some versions of the controlled random search algorithm. Also, they proposed a novel modification of the original algorithm to improve its efficiency based on the quadratic interpolations. While [46] improved the exploitation process of the whale optimization algorithm using quadratic interpolations. A similar study in [47] extended a self-organizing migrating algorithm using quadratic interpolations. The authors in [48] hybridized the colliding bodies optimization Morlet wavelet mutation and quadratic interpolation. Furthermore, the authors in [49] proposed a quadratic interpolation method to speed the convergence and improve the intensification performance of the whale optimization algorithm.
On the other hand, the Sperm Motility Algorithm SMA [1] was inspired by the human fertilization process. In the original SMA, Stokes equations were chosen as the best mathematical model for simulating sperm flow. A heuristic mechanism for sperm, guided by chemoattractant ovum secretion, was mathematically modeled so that the moving agent (sperm) approached the goal (ovum).
In order to further improve efficiency and global search capability and based on the fact that the Schrödinger equation can be derived from the Stokes equation, we can replace the Stokes equation with the time-independent Schrodinger equation. Then, the Delta-potential well function is used to solve the time-independent Schrodinger equation.
Hence, the delta potential well-based QSMA is then proposed. In this algorithm, the state of sperm is described by the wave function ψ(x,t) in place of the Stokes mathematical model.
However, the QSMA algorithm still needs to enhance convergence acceleration and more accurate solutions while solving global optimization problems.
Therefore, the intensification ability and fast convergence of QSMA will be improved by adding a quadratic interpolation operator to the position update process.
Hence, we can summarize the contribution of this work through the following main points:
● We derived the equivalent of the Schrödinger equation of Stokes equation.
● We proposed a new algorithm, QSMA, which is based on a hybrid Sperm Motility Algorithm and a quantum delta potential well-based.
● We improved the QSMA by using a quadratic interpolation operator for more balanced between the exploitation and exploration process, which leads to more accuracy and quality of solutions.
This paper is organized as follows: In Section 2, an overview of quantum computing is introduced. In Section 3, the standard SMA is described. The proposed algorithms are introduced in Section 4. All benchmark examples and results are presented in Section 5. Finally, the paper is concluded in Section 6.
2.
Overview of quantum computing
2.1. Q-bit definition
The quantum bit (Q-bit) is the smallest unit of information that can be stored in a two-state quantum computer [50]. Quantum computers work based on the manipulation of Q-bits and the application of quantum logic gates. Three states of a Q-bit can be presented by "1", or "0", or any superposition of "1", and "0". It is denoted by |ψ⟩ and defined as:
where α and β are complex numbers that refer to the probability amplitudes of the states "0" and "1", respectively. The values |α|2and|β|2 are the probabilities that the Q-bit states that are "0" or "1, " respectively. The equation used for the normalization is:
Therefore, a Q-bit is a pair of numbers (α, β), denoted by
2.2. Quantum superposition
In a typical quantum system, n Q-bits are employed to represent an agent, as follows:
where |αd|2+|βd|2=1, for d = 1, 2, …, n. In a quantum system, |ψn⟩, an arbitrary superposition of states up to 2n different states exists and is given by:
where Ci is the probability amplitude of state i, and Si is the binary string (x1,x2,…,xn), xd∈{0,1},d=1,2,…,n. In contrast, only one state of these 2n states can exist in a standard computer at any time. The probabilistic superposition of 0 and 1 are used to represent a Q-bit. Moreover, this representation can be extended to multi-Q-bits systems.
2.3. Quantum measurement
The probabilistic observation process for measuring the dth Q-bit is presented in the following pseudo-code [50]. Here, a random number is generated by a uniformly distributed probability function in the range [0, 1], as follows:
The observation process is in QIAs.
3.
Overview of Sperm Motility Algorithm
The Sperm Motility Algorithm (SMA) [1] is a metaheuristic algorithm that mimics the fertilization process in humans. The following rules are assumed in the search process:
(1) All sperms are attracted to the ovum due to the secreted chemoattractant.
(2) Attractiveness is proportional to chemoattractant concentration.
(3) Type A sperm, the highest quality sperm, will be selected for the next generation.
(4) The ovum is penetrated by the best sperm. In the case of fraternal twins, the ovum is penetrated by more than one sperm. This case suits the multi-objective optimization.
(5) More than 250 million sperm move randomly with the velocity vi at position xi toward the ovum. The Stokes equation is used to describe the sperm motility [51,52] as follows:
where p is the pressure (including the gravitational potential), µ is the kinematic viscosity, f(x)=δ(x−ξ)F is the force density, and v is the velocity vector field in the domain Ω.
For a micro-swimmer such as sperm, the Reynolds number (Re) is approximately 0.01 and can be neglected. Hence, the Stokes equation can be transformed to its linearized form (Navier-Stokes equations), as follows:
The velocity solution corresponding to this fundamental singularity is given as follows:
where Sij(x,ξ)=(δijr+rirjr3) is known as the Stokeslet that is the solution of the Stokes flow equations, or the Oseen-Burgers tensor, δij is the Dirac delta distribution centered at ζ, the flow is due to a force Fj concentrated at the point ζ, r is dimensionless radial length in two dimensions, and ri=xi−ξi,r2=|x−ξ|2=r21+r22+r23.
The position is updated as follows:
The nonlinear spatial chemoattractant concentration gradient field is given by:
where c(t) is the concentration, x(t) is the position, c1 is the proportion coefficient, b is the power of the significant term position, c0 represents the initial concentration and g∗ is the current best solution found among all solutions at the current generation/iteration.
The basic steps of the SMA can be summarized by the pseudo code shown below.
4.
The proposed Quantum-Inspired Sperm Motility Algorithm
4.1. Schrödinger wave representation of Navier-Stokes equation
Several studies have derived a Schrödinger equation equivalent to the Navier-Stokes equation [53,54,55]. The Schrödinger equation has been solved, while the exact solution of the Navier-Stokes equation remains an open problem in mathematical physics. Therefore, Schrödinger's equation is preferred to the Navier-Stokes equation. Moreover, the Schrödinger equation can describe the quantum state of the velocity field and defines the velocity potential.
Equation (6) can be rewritten as follows:
If the viscosity coefficients ξ and η are linearly dependent of the density ρ, then,
where the kinematic viscosity coefficients of ξ and υ are constant. The solutions to Eq (11) can be found in the form, provided that the function χsatisfies the following equation:
where h(ρ)is the specific enthalpy. Based on [54], the Navier-Stokes equation (11) can be reduced to its equivalent Schrödinger equation. This could be written as follows:
where V is the potential energy, j is the imaginary unit, ℏis Planck's constant, and Ψ is the wave function.
4.2. Quantum mechanics
In quantum mechanics, the changes in the quantum state through time can be described by the Schrödinger equation. In addition, the complex wave function Ψ(X,t) can be used to depict the quantum state instead of using the position and velocity. The time-dependent Schrödinger equation (13) is the governing equation that can be expressed as:
where Ψ(X,t) is the wave function that has no physical meaning, but the square of its amplitude gives the probability of sperm position in anyone-dimension X at time t, and H is a time-independent Hamiltonian operator given as:
where ∇2 is the Laplacian operator, m is the mass of the sperm, and V(X) is the potential energy distribution. In the Schrödinger equation, the unknown is the wave function Ψ(X,t). However, its amplitude squared, |Ψ|2, is the probability of the agent's (the sperm in this case) motion. This relationship allows the probability of finding sperm in a particular region and computing the time t.
The collapsing concept is used to map the probability of finding a particular position in the quantum search space and its actual position in the solution space. Hence, the wave function Ψ(X,t) in a 3-Dimensional space with coordinates x1,x2,x3 can be written as:
where Qdx1dx2dx3 is the probability of measurement of the sperm's position at time t in the 3-Dimensional space and |Ψ|2 is then a probability density function that satisfies the condition:
The integration is taken over the range of the entire feasible space. The separation of variables method is used to solve (14). The wave function becomes a product of the spatial term ψ(X) and the temporal term f(t),
The time-independent equation is derived from the time-dependent equation by substituting (18) in (14),
This equation can be rewritten as:
The left side of Eq (20) is a function of t, and the right side is a function of X. Thus, the two sides must be equal to some constant, called it E, which represents the energy of the sperm. Therefore, two differential equations can be derived from (20):
and
(21) is easily solved to yield:
Hence:
|Ψ|2 refers to the probability of finding sperm at a particular position in the quantum search space and is given by:
The probability density function |Ψ(X,t)|2 is a time-independent function. Therefore, solving the time-independent Schrödinger equation (22) gives the wave function ψ(X).
4.3. The quantum model of SMA
Now, suppose that each sperm has a quantum behavior and a wave function that describe the sperm state. For the sake of simplicity, a sperm in a quantum system with a 1-dimensional search space will be considered. In this case, the position vector X is reduced to scalar x.
Let
where g is a position that has a high chemoattractant concentration. To increase the convergence of QSMA, y should approach zero. Therefore, an attractive potential field centered at zero is applied. According to the analysis of convergence behavior of sperms in SMA, several forms of potential attraction centered around g must exist. Therefore, the δ potential well can be set at g and the most simple and effective expression of its potential energy function is the delta potential well,
where δ(y) is the Dirac delta function. This function is called a delta potential well if γ is negative and a delta potential barrier if γ is positive. Here, γ is a positive number related to the "depth" of the potential well. The depth at the origin is infinite and is zero elsewhere. The Schrödinger equation is:
When y≠0, (29) can be written as:
The following boundary condition is used for more convergence of sperm:
Then, the solution to (30) is:
In addition, with the normalization condition being satisfied.
the probability density function Q will be as follows:
The position and the velocity cannot be determined simultaneously according to the Heisenberg principle of uncertainty [56]. Thus, in the QSMA and IQSMA, the velocity and position terms will not exist together in the updated equations, compared to those in the standard SMA.
4.4. Measurement of the position
The positions of sperm in the SMA are the candidate solutions for a given optimization problem. And the position of the sperm in the QSMA can be measured by the Stokes equation, while the sperm itself follows quantum rules. To connect these workspaces, the quantum state needs to ''collapse'' the wave function of a moving sperm into the measurement space. The Monte Carlo Method (MCM) is used to achieve localization.
The quantum boundary of the sperm is guaranteed by the delta potential well. The position of the sperm should be determined to evaluate the fitness value. Since the quantum state function can calculate the probability density function, the sperm appears at the position y. Hence, we must calculate the position of the sperm, which is termed collapsing the quantum state to the classical state.
This measurement process is simulated by MCM, which generates a random variable. Equation (34) can be simplified to:
or
that is
Thus, the precise position of a sperm is measured by:
It is supposed that ℏ2√−2mE=c|g−x|, where c is a constant and |g−x| is used to scale the variation
of the newly created sperm around one of the ovum. Therefore, for an n-dimensional search space system, this equation can be written as follows:
where r and S are two random numbers in the interval (0, 1), c is a parameter used to balance the exploration and exploitation, and gdiis the current best position with the highest chemoattractant concentration.
4.5. The proposed QSMA
In this proposed algorithm, the position of each sperm is updated using the finally deducted Eq (40) in the sperm movement solution search. At the end of each generation, the new sperm is accepted if it gives a better fitness than the other sperm. The process is repeated until the stopping criterion is satisfied.
The steps of the proposed quantum Delta-Potential-well-based SMA Algorithm are as follows:
4.6. Improved QSMA with interpolation operator
In this method, three points in the current population are selected. x1 is obtained as the best optimization point (the sperms have a minimum fitness function value), where x2, x3 are randomly chosen [57]. The objective functions values are assumed as follows [58,59]:
Trial point design variables pj are defined as the minimum of the parabola, written as follows:
j=1,2,…,N. To avoid quadratic interpolations that become ill-conditioned or present trial point design variables as maxima of the parabola (see Figure 1), a mean objective function value fg and a local variability measure around the best point, α, are used and are usually calculated as follows:
where fh and fl are the highest and lowest function values, respectively, these equations are used when quadratic interpolation is well-conditioned, and the best point is not contained between any other two points.
In this case, a set of centroid design variables gj are defined, as in Eq (44), and through these variables, the trial point design variables pj , are defined by the variability-based reflection around the best point, as in (45) [57,60,61], as follows:
4.7. The proposed IQSMA
Herein, a Controlled Random Search-Variability Based Reflections CRS-VBR Algorithm is used to generate a new sperm in the search space [57,60,61]. In the sperm movement solution search, the position of each sperm is updated using the Eq (40). After that, the interpolation operator is implemented by selecting another two sperm randomly and applying the Eqs (41–45). So, herein, the final position of each sperm is updated using the Eq (45). At the end of each generation, the new sperm is accepted if it is better than the other sperm. The process is repeated until a better solution is obtained or for a certain number of generations. This method increases the diversity as promising new solution points are investigated because of the interpolation process. The new sperm positions are included in the domination comparison interpolation process. This methodology is very different from the usual method of retaining sperm with the best fitness function values for the recombination process. Moreover, for simplicity, we can evaluate the time complexity for both proposed algorithms based on the steps of algorithms 2 and 3. Both algorithms contain a number of primitive operations and two loops, so we can consider that the time complexity of both algorithms belongs to the quadratic class. Thus, the time complexity of both algorithms depends on the population's size and the number of iterations.
The computational steps of the improved algorithm are as follows:
5.
Results and discussion
To investigate the performance of the proposed algorithms, we choose various functions that are widely used in the literature [1,62,63,64,65]. We classify the test benchmarks function into four groups where the first group represents unimodal benchmarks functions shown in Table 1. In contrast, the second group represents the multimodal benchmarks functions listed in Table 2. Also, Table 3 reports the fixed-dimension multimodal benchmarks functions, and Table 4 presents the CEC-C06 2019 test functions. Comparison between IQSMA and QSMA algorithms and SMA[1], EO [66], SCA [67], and SSA [68] algorithms were performed. The number of iterations and the population size of all algorithms were fixed at 500 and 30, respectively, to achieve fairness, and the algorithms were also implemented using MATLAB R2011 on a Core (TM) i3, 2.27 GHz processor. The simulation parameter settings that were the result of EO, SCA, SSA, and SMA algorithms are present in Table 5 as follows:
The unimodal benchmarks functions (F01–F07) are used to investigate the proposed algorithms' intensification, and the multimodal benchmarks functions (F08–F13) are employed to examine the proposed algorithms12' diversification, while the fixed-dimension multimodal benchmarks functions (F14–F23) are used to test the ability of the proposed algorithms to scan the feasible region efficiently in low dimensions. Also, the CEC-C06 2019 test functions [65] are used to further evaluate the performance of the proposed algorithms. All present algorithms are compared using average, standard deviation, and elapsed time.
The numerical results presented in Table 6 show the objective function in terms of the average, standard deviation, and elapsed time. The best solution obtained for each test problem is shown in Tables 2–4; the numbers in bold indicate the best solution obtained according to mean fitness values and the convergence time. The results show that the performance of both proposed algorithms is superior in most benchmark functions, and they are competitors in some other benchmark functions compared to other present algorithms.
Regarding the proposed algorithms' performance on the unimodal benchmark functions (F01–F07), as observed, IQAMA achieved the first rank in this category.
The superior performance of IQSMA is seen on average in functions of F01–F04, and F07. In F05, the superior performance was for the SCA algorithm, while the EO algorithm had the superior performance in F06. We can deduce the high exploitability of the proposed algorithms based on the results of the unimodal functions.
As for the performance of the proposed algorithms on the multimodal benchmark functions (F08–F013). As can be seen, IQSMA achieves the best performance in F08 F10. both IQSMA and EO reached the exact optimal solution in F09. Also, in F11, the three QSMA, SMA, and EO algorithms achieved the optimal solution. The EO algorithm obtained the best mean solution for the F12 function, while the best mean solution was obtained for the F13 function by SSA.
Regarding the fixed-dimension multimodal benchmarks functions (F14–F23), the best mean solution was reached by IQSMA, EO in F14. the performance of QSMA is the best in F15, F17. Four algorithms, IQSMA, QSMA, SMA, and SSA, got on the best mean solution in F16. Also, the IQSMA, QSMA, SMA, EO are equal in the performance in F18. While in F19, both proposed algorithms and the EO algorithm reached the best optimal solution. Similarly, in F21 and F22, the best solutions were obtained by both proposed algorithms and the SSA algorithm. IQSMA reached the best optimum in F20. In contrast, both proposed algorithms were equal in the best performance in the F23.
Moreover, we calculated the root of the sum of the squares of deviations from the optimal solutions mentioned in the Tables 2–4, we found that the rank of the IQSMA algorithm comes first, and then QSMA comes second, while the OE algorithm comes in the third rank, and the SMA occupies the fourth rank. SSA and SCA algorithms occupied the last places, respectively. When summing the computational times, we found that the IQSMA algorithm has the minimum computational time, then the SCA algorithm, after that, the SSA algorithm, the fourth was SMA, and the fifth was QSMA, while the EO algorithm is the last in terms of convergence speed. The convergence speed of the IQAMA algorithm is due to the importance of the interpolation operator.
Figure 2 presents two panels for all functions (F01–F23), where the left panel displays the function in 2-D versions while the right panel represents a comparison of convergence curves for all present optimization algorithms. We can see from Figure 2 that both proposed algorithms, QSMA, IQSMA have a steady convergence and a slow convergence acceleration on these benchmark functions compared with (SMA, EO, SCA, and SSA). Furthermore, the IQSMA got better solutions and faster convergence compared to other algorithms.
Moreover, Table 7 presents a comparison of the numerical results of the CEC-2019 benchmarks functions mentioned in Table 5. Again, we find that the proposed algorithms gave the best solutions compared to the other algorithms presented in this work. It is worth noting here that the EO algorithm, although it takes a long time, performed better than the rest of the SCA, SSA, and SMA algorithms, as it was competitive with the QSMA and IQSMA algorithms. Also, the IQSMA algorithm got on the minimum root of the sum of deviations from the optimal solution, followed by the QSMA algorithm, then the SMA algorithm, and then the EO algorithm, while it comes in the last ranks with the SCA and SSA algorithms respectively.
Regarding the amount of computational time, the IQSMA algorithm had the lowest value in this respect, followed by the SMA algorithm, then the SCA and SSA algorithms, then the QSMA, whereas EO had the highest value. This shows faster convergence and higher efficiency of the proposed algorithms in solving optimization problems. Figure 3 illustrates the convergence curves of all algorithms presented in this paper.
We can conclude from the above comparisons and the behavior of convergence curves that the proposed algorithms are a competitor candidate for the well-known metaheuristics algorithms in solving mathematical optimization problems. They have proven their ability to reach the promised optimum solution at a high convergence speed in various unimodal, multimodal with high or fixed dimensional and composition optimization problems.
6.
Conclusions
In this paper, we have formulated a quantum variant of the SMA algorithm named QSMA, and We proposed an improved version of the QSMA, namely the IQSMA algorithm based on an interpolation operator. Thirty-three various test benchmark functions were used to validate the performance of both proposed algorithms so that the convergence behavior and the ability to reach the optimal solution were analyzed. The results indicated the superiority of both the proposed algorithms and their competitors to the well-known metaheuristics algorithms; also, the results showed the superiority of the IQSMA, considering the convergence time due to the effectiveness of the interpolation operator. Future work could involve improving these algorithms to handle multi-objective optimization problems. Moreover, the performance of these algorithms could also be tested on combinatorial optimization problems and real-life optimization applications.
Acknowledgments
This work was supported by the Research Supporting Project Number (RSP-2021/389), King Saud University, Riyadh, Saudi Arabia.
Conflict of interest
We have no conflicts with competing interests to disclose.