1. Introduction
Optimizing problems are ubiquitous around us, for instance, traveling salesman problem, bin-packing problem, assignment problem, flow shop scheduling problem, etc. It is well known that these problems are NP-hard, which makes it almost impossible to obtain the optimal solution through various enumeration methods and precise algorithms under the existing computing capacity. Therefore, compared with the traditional optimization algorithm, the meta-heuristic algorithm is proposed, which is a mixture of stochastic algorithm and local search algorithm.
With the intention of developing a new meta-heuristic algorithm, researchers seek inspiration from the fields of biology, physics, and sociology.This makes the study of optimization contains many algorithms, such as particle swarm optimization (PSO) [1], artificial bee colony (ABC) [2], whale optimization algorithm (WOA) [3], ant colony optimization [4], wasp swarm algorithm [5], Monkey Search [6], ageist spider monkey optimization (ASMO) [7], and wolf colony search algorithm [8], etc. These algorithms developed from the mechanism of biological evolution and population cooperation and improved the optimization effect compared with the traditional optimization algorithms. In addition to biology, physical phenomena are also the ideal source of meta-heuristics. Algorithms inspired from these phenomena include simulated annealing (SA) [9], gravity search algorithm (GSA) [10], galaxy based search algo- rithm (GBSA) [11], charged system search (CSS) [12], central force optimization (CFO) [13], black hole algorithm (BH) [14], etc. In addition to developing new algorithms, scholars are also focusing on developing a range of variations on existing algorithms or propose a variant of the algorithm to solve a major problem in an algorithm. For example, since the ABC converges slowly, Huang et al. [15] proposed an enhanced version of ABCIS (artificial bee colony algorithm with special division and intellective search). Moreover, in order to resolve the parameter selection problem of support vector machine (SVM) algorithm, Zhao and Long [16] proposed an improved particle swarm optimization algorithm to optimize the parameters of SVM. To improve exist algorithms, Song et al. [17] proposed a variant of artificial bee colony algorithm which is highly efficient and two-strategy adaptive. Chen et al. [18] proposed ABC-EO II and IABC-EO II, the updated version of ABC-EO and IABC-EO, where extremal optimization (EO) is introduced to these two algorithms in dissimilar ways. Li et al. [19] proposed a two-level imperialist competitive algorithm (TICA), in which two levels refers to the corresponding strongest empire and other empires.
In this paper, we developed the photon search algorithm, which is based on knowledges of physics. Without ambiguity, we abbreviate it as PSA. In the algorithm proposed, we give some formulas according to the behaviors designed for the algorithm, these formulas initialize the position, velocity, and distance of photons (search agents) in each iteration. These formulas are inspired by the photon hypothesis and quantum physics. Further, we present the pseudo-code of PSA. However, studies on optimization are most concerned about the performance of algorithms. Therefore, so as to show various properties of PSA, the experiments solving 23 functions are designed. The results of experiments indicate that the PSA has advantages compared to other algorithms.
The overview of the paper are as follows. We present inspiration, mathematical expression and algorithm design in Section 2. In Section 3, functions for tests and experimental results are described in detail. Section 4 shows the improvement of PSA named UFPSA and presents the experimental results of this algorithm under unimodal functions. In Section 5, we summarize the algorithms and give our proposal and prospect for future research.
2. Photon Search Algorithm
We will describe the core design of the PSA algorithm in this section. The inspiration of the algorithm proposed will be introduced firstly, and then the corresponding mathematical expression will be given.
2.1 Inspiration Source
On December 14, 1900, at a regular meeting of German physics, Max Planck made an impressive presentation [20]. In his report, he made the point that electromagnetic energy could be emitted only in quantized form, in other words, the energy could only be a multiple of an elementary unit. This idea proposed by Planck marked the birth of the quantum theory.
It is 5 years since the quantum theory was first proposed, it has received little notice, but it eventually caught Einstein's attention. In March 1905, Einstein [21] proposed the quantum hypothesis. He thought that the propagation of light in space is also discontinuous, and he named this discontinuous energy unit “light quantum”. And, he argues, for the average value of time, light behaves like a wave; for the instantaneous value of time, the light behaves as a particle. This is the first time in history to reveal the unity of microscopic object volatility and particle property, namely wave-particle duality.
After that, de Broglie [22] made a point in 1924: microscopic particles also have volatility. He connected the properties of microscopic particles with the so-called de Broglie relation based on the relationship between light waves and photons. Frequency ν and wavelength [TeX:] $$\lambda$$ are respectively:
According to the statistical interpretation put forward by Bohn, the wave represents the probability of the appearance of particles at various positions in space, and the diffusion of the wave packet is actually the diffusion of particle probability, rather than the disintegration of particles themselves. To some extent, this interpretation solves the contradiction between volatility and particle property, which is now accepted by most scholars.
However, in the process of the development of quantum mechanics, we must mention Wolfgang Pauli, whose Pauli Exclusion Principle has also contributed to the development of microphysics.
It is under the inspiration of these physical theories the algorithm PSA proposed by this paper.
2.2 Mathematical Model
The mathematical expression of photon motion and mathematical expression of observation based on the uncertainty principle will be presented in this section. Inspired by these knowledges, we propose photon search algorithm (PSA).
The design of PSA applies a lot of knowledges related to quantum mechanics. Inspired by these knowledges, this paper transforms these knowledges into the main algorithmic behavior and controls the search process of the algorithm. The three main behaviors are Photon motion, Observation, and Search exclusion principle, which will be explained in detail in the next section.
Later, we combined the three components in Section 2.3 to show how the PSA works.
2.2.1 Photon motion
In PSA, each photon is a search agent, and they will be targeted at the current optimal solution value at the beginning of generation and obtain a uniform fixed speed. After each movement, the photons submit their solution values to the algorithm. The algorithm will compare all the received solutions with the current optimal solution and leave the superior solution. When the algorithm runs to the termination condition, it will finish running and output the obtained optimal solution value.
According to Einstein's Principle of Light Speed being Constant, it is easy to know that in any space, no matter who is observing at any time, light travels at about 300 million meters per second, and the speed is independent of the state of motion of the emitter. This also means that if the observation intervals are the same, the distance traveled by the light is unchanged.
Consider an environment with N photons (agents). The position of the ith agent can be defined by:
where [TeX:] $$x_{i}^{d}$$ is the exact position of ith search agent in dth dimension.
It is easy to know that the Euclidian distance between ith photon and current global optimum Xg at the specific time t is:
However, since the distance of light moving at a fixed time is constant, the distance [TeX:] $$R_{L e n}$$ that the photon passes through in an iteration is equal to the scale of the distance between the most distant points in the search space, in this paper:
where Scl represents the scale value (default value is 0.1), [TeX:] $$X_{U_{p p r r}}$$ is the point takes the upper bound value on all dimensions, and [TeX:] $$X_{\text {Lower}}$$ is the opposite one.
Hence, for certain time “t”, the speed v in dth dimension of photon “i” is defined as following:
Furthermore, the location of photon “i” is updated by the following formula:
where De adjusts the convergence of the search process. After several experiments, ext=2 is adopted in this paper.
In order to simulate the uncertainty principle of quantum, after updating the position, the photons still need to be observed to obtain the final specific position. Specific steps of “Observation” behavior will be given below.
2.2.2 Observation
In the theory of quantum mechanics, the exact position and velocity of a particle are hard to be measured simultaneously according to the uncertainty principle proposed by Heisenberg. If we know the precise momentum of a particle, the particle represents a plane wave, whereas a plane wave is diffuse across space, so its position is uncertain. As we turn to the precise position of the particle, the particle appears in the range of the wave packet in the form of probability.
Based on this quantum property, we designed the “Observation” behavior of the algorithm. In other words, when the algorithm decides to obtain the position of photon “i”, it will appear in the region where it is likely to occur with probability, near the updated position [TeX:] $$X_{i}.$$
Here is the formula for the position of the photon after “Observation”:
where randA refers to a random value ranged with [-1, 1].
2.2.3 Search exclusion principle
Pauli Exclusion Principle is one of the fundamental laws of the motion of microscopic particles. It states that a system of fermions cannot have two or more particles in the same state.
In PSA, the position and fitness of photon were determined after Observation behavior. If the new value discovered by the current search agent has better fitness value than the existing global optimum, the new global target will be generated at the position as a special particle. However, as described by the Pauli Exclusion Principle, two particles of the same state cannot appear at the same time. Hence, we must move the particle at the current global optimum to somewhere else. This is what we call the Search exclusion principle.
This paper assumes that PSA will has a certain understanding of the search range at the very beginning of the search and that it is necessary to make search agents have shorter search processes. So, we randomly put all the search agents on the “Search Axis”, where all the points on it have the same position value in all dimensions:
Its mathematical expression is as follows:
where [TeX:] $$x L o w^{d}$$ refers to the value of lower boundary of corresponding dimensions, and [TeX:] $$x U p p^{d}$$ refers to the contrary one. Particularly, randB is a random value within the range [0, 1], which is generated only once in each iteration and used by all search agents.
2.3 Algorithm Design
In this section, we combine the behavior of each algorithm to show the specific operation of PSA. The pseudo code of PSA is given in Fig. 1.
Theoretically, PSA is behaved as a global optimization algorithm, and “Observation” behavior ensures that the algorithm avoids local optimization. In addition, PSA has one common characteristic of algorithms that follow evolutionary rules, which requires algorithms to retain the optimal solution after each iteration. In theory, this ensures that the algorithm has competitiveness when dealing with unimodal functions, but it sometimes traps the algorithm into local optimum.
Such results may be caused by the high demand for convergence in this paper. How to balance convergence and optimal performance may be one of the available subjects of future studies.
3. Experiments Evaluations
3.1 Unimodal Functions Evaluation
The calculating performance of the PSA is evaluated by testing 23 numerical optimization problems proposed by the literature [3]. The first 7 functions are unimodal functions, and the last 16 are multimodal functions. Tables 1 and 2 represent the math expression of benchmark functions used in our experiment. Figs. 2 and 3 give the 2D representations of these benchmark functions.
We tested PSA, WOA, GSA, and PSO with these benchmark functions and the results are compared later. In all cases, the population N is set to 20. Test dimension is set to 30 (Dim = 30) and the number of iterations is limited to 300 for benchmark functions of Tables 1 and 2. In particular, for PSO, c1 and c2 are set to 2 and factor w is set to 0.4.
Before presenting test results, let’s firstly introduce WOA and GSA independently.
Whale Optimization Algorithm
The inspiration of WOA comes from a unique hunting method of humpback whales: bubble net prey. And WOA was presented by constructing the mathematical model of encircling prey, spiral bubble net hunting maneuver and prey searching. Below, we introduce each of these models.
The mathematical model of encircling prey:
where [TeX:] $$X^{*}$$ is position vector for the best solution so far, [TeX:] $$\vec{X}$$ is the position vector, [TeX:] $$\vec{A}=2 \vec{a} \cdot \vec{r}-\vec{a} \text { and } \vec{C}=2 \cdot \vec{r}$$ denote coefficient vectors, and [TeX:] $$\vec{a}$$ decreases linearly from 2 to 0 during the iteration, [TeX:] $$\vec{r}$$ is a random vector in [0, 1].
The mathematical model of spiral bubble net hunting manner:
where [TeX:] $$\overrightarrow{D^{\prime}}=|\overrightarrow{X^{*}}(t)-\vec{X}(t)|$$ denotes the distance of the ith whale to the prey, b is a constant that defines the shape of a logarithmic spiral, l is a random number in [-1, 1], and p is a random number in [0, 1].
The mathematical model of prey searching:
where [TeX:] $$\overrightarrow{X_{r a n d}}$$ represents the position vector of a random whale selected from the current population.
Description of unimodal functions, [TeX:] $$\mathrm{F}_{1}-\mathrm{F}_{7}$$
2. Description of multimodal functions, [TeX:] $$\mathrm{F}_{8}-\mathrm{F}_{23}$$
Two-dimensional (2D) representations of unimodal benchmark functions [TeX:] $$\left(\mathrm{F}_{1}-\mathrm{F}_{7}\right).$$
Typical 2D representations of multimodal benchmark functions [TeX:] $$\left(\mathrm{F}_{8}-\mathrm{F}_{16}\right)$$
Gravitational Search Algorithm
GSA was proposed by the law of interaction between gravity and mass. During the execution of GSA, let [TeX:] $$x_{i}^{d}$$ be the position of the ith search-agent in the d-th dimension and [TeX:] $$X_{i}=\left(x_{i}^{1}, \ldots, x_{i}^{d}, \ldots, x_{i}^{n}\right)$$ be the position of the ith search-agent for i=1,2…,N, the calculation formula of the interaction force and the location and speed of the search-agent as follow.
The force [TeX:] $$F_{i j}^{d}(t)$$ on mass i from mass j and the total force on search-agent i in the dth dimension at time t are defined as follows:
where [TeX:] $$M_{a j}$$ denotes the active gravitational mass associated with search-agent j, [TeX:] $$M_{p i}$$ is the passive gravitational mass associated with search-agent [TeX:] $$I, G(t)=G\left(G_{0}, t\right)$$ is gravitational constant, [TeX:] $$G_{0}$$ is the original value, [TeX:] $$\varepsilon$$ is a sufficiently small positive number [TeX:] $$\boldsymbol{R}_{i j}(t)=\left\|X_{i}(t), X_{j}(t)\right\|_{2}$$ counts the Euclidian distance between two search-agent i and j, and [TeX:] $$\text {rand}_{j}$$ is a random constant in [0, 1].
The location and speed of the search-agent at time t are defined as follows:
where [TeX:] $$a_{i}^{d}(t)=F_{i}^{d}(t) / \mathrm{M}_{i i}(t)$$ [TeX:] $$M_{i i}(t)$$ is the inertial mass of the ith search-agent, rand denotes the uniform random variable in [0, 1].
[TeX:] $$\mathrm{F}_{1}-\mathrm{F}_{7}$$ are unimodal benchmark functions. They can be used to evaluate the algorithm's local search capability since they have only one global best solution. As shown by Fig. 4, average best-so-far (average number of the best solution obtained so far in each iteration) of 30 runs, PSA for unimodal function has not only good convergence but also has high convergence rate. Compared with other algorithms, it can get closer to the global optimum in fewer iterations. This means that PSA has better performance handling the problems that require less computing time.
Comparison results of convergence performance when dealing with unimodal functions.
Statistical results for 30 runs of F1–F7 are listed in Table 3. Best, Avg, and Std represent best fitness ever found, average fitness and corresponding standard deviation, respectively. In parallel comparison, bold font represents the best effect. If there is no bold font in parallel comparison, this means that all algorithms perform well.
Real machine test results of 7 unimodal functions
Obviously, PSA is very competitive when compares with other algorithms in dealing with functions [TeX:] $$\mathrm{F}_{3}-\mathrm{F}_{7}.$$ Especially, its test results under functions [TeX:] $$\mathrm{F}_{3}-\mathrm{F}_{5}$$ are significantly better than those of other algorithms, and it can achieve the accuracy that other algorithms are difficult to achieve. Although the results of dealing with F1 and F2 are not best, PSA still maintains considerable accuracy.
With the aim of analyzing the performance of algorithms, it is first necessary to be clear that the search process of most optimization algorithms is divided into two main stages: exploration and exploitation [3]. The exploration phase is responsible for letting the algorithm determine the approximate location of the global optimization, while the exploitation phase is responsible for allowing the algorithm to dig deeper into the global optimal solution. PSA also has these two phases. Through further analysis, since the PSA algorithm itself has good convergence performance, it can quickly find the region where the global optimum is located. It is not practical to get most of the algorithms to perform well in exploration and exploitation at the same time. It can be known from Eq. (9) that after the Observation step, the location of the search agent will change around the current location, to avoid falling into local optimum. This step also causes the search agent to shift around the global best, causing some bias. The Observation step is to obtain excellent exploration performance, avoid falling into local optimum, and the effect is visible. The algorithm obtains excellent convergence performance but sacrifices some exploitation per formance. This also leads to the results of Table 3. For F1, F2, F6, and F7, PSA has excellent performance, and it can stably find the position of the global optimal solution in multiple iterations, showing excellent exploration performance, but due to Exploitation performance is slightly insufficient, so PSA cannot dig deeper into the global optimal solution as WOA does. For F3, F4, F5, we can easily find that these three functions may have a lower gradient or even a zero gradient during the search process. At this time, the PSA's exploration performance is fully reflected.
Finally, considering the convergence of the algorithm, it can be said that PSA performs quite well when dealing with unimodal functions.
3.2 Multimodal Functions Evaluation
[TeX:] $$\mathrm{F}_{8}-\mathrm{F}_{23}$$ are multimodal benchmark functions. Most of the multimodal functions are complex in structure and have many local optimal values, which have a considerable test for the convergence performance of the algorithm. However, these multimodal functions are more closely related to the models of real-life problems, and in other words, they can be used to evaluate the robustness of meta-heuristic algorithms.
Table 4 shows that the multimodal function test results, compared with other algorithms, PSA in function [TeX:] $$\mathrm{F}_{8} / \mathrm{F}_{12} / \mathrm{F}_{14} / \mathrm{F}_{16} / \mathrm{F}_{21} / \mathrm{F}_{22} / \mathrm{F}_{23}$$ have remarkable performance. In the test of these functions, PSA not only found a better solution but also maintained a lower average value and standard deviation, which showed strong stability. Although PSA did not get the best result in the test of [TeX:] $$\mathrm{F}_{9} / \mathrm{F}_{10} / \mathrm{F}_{11} / \mathrm{F}_{13} / \mathrm{F}_{15} / \mathrm{F}_{17} /\mathrm{F}_{18} / \mathrm{F}_{19} / \mathrm{F}_{20}$$ functions, it still maintains high accuracy and stability in these function tests.
Real machine test results of multimodal functions
Combined with the test of unimodal functions, PSA has an excellent ability to explore so that it will perform well in the test of multimodal functions. However, in order to make the algorithm have a faster convergence speed, PSA must sacrifice some of the Exploitation ability, which also makes the performance of some functions, not the best, but the performance is still excellent.
The function [TeX:] $$\mathrm{F}_{8}-\mathrm{F}_{13}$$ are normal multi-peak function. For the functions [TeX:] $$\mathrm{F}_{8} \text { and } \mathrm{F}_{12},$$ the performance of the PSA is perfect, while for the [TeX:] $$\mathrm{F}_{9}-\mathrm{F}_{11} \text { and } \mathrm{F}_{13},$$ the performance is not the best, but it is maintained at a reasonable level. As can be seen from Table 4, the PSA is very close to the global best and maintains an excellent convergence performance, so that it can adapt to some computing scenarios that require less computing time.
Although the functions [TeX:] $$\mathrm{F}_{14}-\mathrm{F}_{23}$$ are multi-peak functions of fixed dimensions, the performance of each optimization algorithm is roughly the same as that of [TeX:] $$\mathrm{F}_{8}-\mathrm{F}_{13},$$ but it is worth noting that PSA performs better and more stable for the [TeX:] $$\mathrm{F}_{21}-\mathrm{F}_{23}$$ function.
As can be seen from Fig. 5, PSA still has good convergence for the function [TeX:] $$\mathrm{F}_{8}-\mathrm{F}_{19}$$ and has advantages over other algorithms. For [TeX:] $$\mathrm{F}_{20},$$ PSA can converge rapidly, but its accuracy is not very good. However, it performs very well for [TeX:] $$\mathrm{F}_{21}-\mathrm{F}_{23}.$$ As can be seen from the Figure, PSA maintains a perfect convergence, accuracy, and converge speed every time it searches in these functions.
Comparison results of convergence performance when dealing with multimodal functions.
4. Improvement of PSA for Unimodal Functions
It is known that unimodal functions have only one extreme value (minimum or maximum) within a given range. Therefore, it is not necessary to worry about whether the algorithm is stuck at a local extreme when exploring the search space. However, the convergence speed and accuracy of the algorithm should be given priority of considering. Based on the characteristics of the unimodal functions, we improve PSA and get an algorithm specifically for the unimodal function, which we called UFPSA.
For PSA, the only requirement is to modify the photon position formula and its updated position formula. The modifications are as follows.
UFPSA updates the location of photon “i” by following formula:
where De adjusts the convergence of the search process. After several experiments, let ext=2 and b=1.5 in this paper.
The position of the photon is calculated according to the following formula:
where Normrnd(t) refers to the random number created from the normal distribution with mean 0 and standard deviation 0.6.
Convergence performance of UFPSA and PSA when dealing with unimodal functions.
Unimodal function test of UFPSA and PSA
Experiments and Evaluations of UFPSA
We used the same test environment to test UFPSA and PSA (Dim=30, N=20, MaxIter=300). Looking at Fig. 6 and Table 5, we can clearly find that UFPSA can converge faster and maintain higher accuracy when dealing with unimodal function compared with PSA. In the case that the dimension is equal to 30, UFPSA can converge to a higher accuracy in a very few iterations, which enables it to perform some optimization operations requiring higher time complexity.
5. Conclusion
This paper provides a brand new meta-heuristic algorithm PSA which based on the quantum properties of photon. According to the test results of 23 benchmark functions, note that PSA has perfect convergence and strong ability of global search. Further, we can see that PSA can always decrease to an acceptable accuracy within a few iterations, whether in unimodal or multimodal functions, what implies that the algorithm can achieve a better approximate solution in a shorter time. The strong global search capability also makes PSA more competitive in comparison with other algorithms. However, the PSA still has some room for improvement. For instance, while guaranteeing the convergence of PSA, the accuracy for solving multimodal functions could be further improved.