An Analytical Framework for Runtime of a Class of Continuous Evolutionary Algorithms

Although there have been many studies on the runtime of evolutionary algorithms in discrete optimization, relatively few theoretical results have been proposed on continuous optimization, such as evolutionary programming (EP). This paper proposes an analysis of the runtime of two EP algorithms based on Gaussian and Cauchy mutations, using an absorbing Markov chain. Given a constant variation, we calculate the runtime upper bound of special Gaussian mutation EP and Cauchy mutation EP. Our analysis reveals that the upper bounds are impacted by individual number, problem dimension number n, searching range, and the Lebesgue measure of the optimal neighborhood. Furthermore, we provide conditions whereby the average runtime of the considered EP can be no more than a polynomial of n. The condition is that the Lebesgue measure of the optimal neighborhood is larger than a combinatorial calculation of an exponential and the given polynomial of n.


Introduction
The running time to optimum is a key factor in determining the success of an evolutionary programming (EP) approach. Ideally, an implementation of an EP approach should run for a sufficient number of generations when the probability of achieving an optimum is greater than some desired value. However, few results on the running time of EP approaches can be found in the current literature.
As a technique of finite state machine, EP was first proposed for continuous optimization [1]. It has since been widely adopted as a powerful optimizing framework for solving continuous optimization problems [2][3][4]. More recently, EP research has mainly concentrated on the function of its parameters and its improvement by adaptive strategies. As a result, several EP variants have been proposed, distinguishing from each other mainly with different mutation schemes based on different probability distributions.
Arguably, the first EP algorithm that was widely considered successful was the one with Gauss mutation that has been termed as classical evolutionary programming (CEP) [2]. CEP has been intensively analyzed by Fogel [3,4], Bäck and Schwefel [5], and Schwefel [5,6]. Subsequently, Yao et al. proposed a fast evolutionary programming algorithm (FEP) with a new mutation scheme based on the Cauchy distribution [7]. Computational experiments showed that FEP is superior to CEP when tackling the optimization problems of multimodal and dispersed peak functions. Another EP variant [8] was later proposed by using the Lévy distribution based mutation, which we call Lévy evolutionary programming (LEP) in this paper. Empirical analyses show that, overall, LEP exceeds CEP and FEP when solving the benchmark problems of multimodal and highly dispersed peak functions.
CEP [2], FEP [7], and LEP [8] can be considered as classical evolutionary programming algorithms. Several modified types of EP have since been designed based on these three basic approaches [2,7,8].
The performances of EP approaches such as CEP, FEP, and LEP have oftentimes been verified experimentally rather than theoretically. The theoretical foundations of EP have been an open problem ever since it was first put forward [1,2]. In particular, Bäck and Schwefel [5] and Schwefel [6] suggested the convergence analysis of EP algorithms as a 2 Computational Intelligence and Neuroscience research topic in their surveys of evolutionary algorithms. Fogel [2][3][4] presented an initial proof of EP convergence on the basis of the discrete solution space. Rudolph [9][10][11] then showed that CEP and FEP can converge with an arbitrary initialization; this result is more general since it applies to a continuous solution space.
Previous convergence studies only considered whether an EP algorithm is able to find an optimum within infinite iteration but did not mention the speed of convergence, that is, lacking running time analysis. To date, running time analyses have mainly focused on Boolean individual EAs like (1 + 1)EA [12], ( + )EA [13], multiobjective EA [14][15][16], and so forth. Alternative theoretical measures for evaluating the running time of Boolean-individual EA approaches have also been proposed [17,18]. Recently, the impact of particular components of EA on runtime has also been studied, on mutation, selection [19], and population size [18,20,21]. In addition to these studies on EAs solving Boolean functions, some results of runtime analysis have been obtained on some combinatorial optimization problems [22][23][24]. Lehre and Yao [25] completed the runtime analysis of the (1 + 1)EA on computing unique input output sequences. Zhou et al. presented a series of EA analysis results for discrete optimization like the minimum label spanning tree problem [26], the multiprocessor scheduling problem [27], and the maximum cut problem [28]. Other proposed studies are on the topics of tight bounds on the running time of EA and randomized search heuristic [29][30][31].
As summarized above, the majority of runtime analyses are limited to discrete search space; analyses for continuous search space require a more sophisticated modeling and remain relatively few, which is unsatisfactory from a theoretical point of view. Jägersküpper conducted a rigorous runtime analysis on (1 + 1)ES, (1 + )ES minimizing the Sphere function [32,33]. Agapie et al. modeled the continuous EA as a renewal process under some strong assumption and analyzed the first hitting time of (1+1)EA on inclined plane and Sphere function [34,35]. Chen et al. [36] proposed general drift conditions to estimate the upper bound of the first hitting time for EAs to find -approximation solutions. Inspired by the studies above, especially the estimating approach in [17] for discrete situation, this paper presents an analytical framework for the running time of evolutionary programming. We also discuss whether the running time of CEP and FEP is influenced by individual number, problem dimension number, searching range, and the Lebesgue measure of the optimal neighborhood in the target problem. Furthermore, we give the approximate conditions under which the EP can converge in a timespan less than a polynomial of .

EP Algorithms and the Associated
Markov Chain 2.1. Introduction to EP Algorithms. This section introduces the two EP algorithms CEP [2] and FEP [7] that are studied in this paper. The skeleton of EP algorithms analyzed in this paper is given in Algorithm 1; the sole difference among CEP, FEP, and LEP lies in their treatments of Step (3).
(2) Calculate the fitness of each individual.
(5) Select individuals by a tournament rule.
(6) If the terminal condition is satisfied, output the bestso-far solution found and exit; otherwise, go back to Step (3). In Step (1), the generated individuals are denoted by a couple of real vectors k = (x , ), = 1, 2, . . . , , where the elements x = ( 1 , 2 , . . . , ) are the variables to be optimized, and the elements = ( 1 , 2 , . . . , ) are variation variables that affect the generation of offspring. We set the iteration number = 0 and the initial ≤ 2 ( = 1, . . . , ) as proposed in [8]. The fitness values in Steps (2) and (4) are calculated according to the objective function of the target problem. In Step (3), a single k = (x i , i ) is generated for each individual k , where = 1, . . . , . For = 1, . . . , , where ( ) denotes a renewing function of variation variable . The renewing function = ( ) may have various forms, and a representative implementation of it can be found in [7]. However, for ease of theoretical analysis, we will consider a kind of simple renewing function, that is, constant function, in our case studies (see Section 4): The three EP algorithms differ in how x is derived, which can be explained as follows (in this paper, we only consider CEP and FEP): where (0, 1) is a newly generated random variable by Gaussian distribution for each and is a Cauchy random number produced anew for th dimension, whose density function is In Step (5), for each individual in the set of all parents and offsprings, different opponent individuals are uniformly and randomly selected to be compared. If the selected individual's fitness value is more than the opponent's, the individual obtains a "win." The top individuals with the most "wins" are selected to be the parents in the next iteration, breaking ties by greater fitness.
Computational Intelligence and Neuroscience 3

Target Problem of EP Algorithms.
Without loss of generality, we assume that the EP approaches analyzed in this study aim to solve a minimization problem in a continuous search space, defined as follows.
Definition 2 (minimization problem). Let S ⊆ R be a finite subspace of the -dimensional real domain R , and let : S → R be an -dimensional real function. A minimization problem, denoted by the 2-tuple (S, ), is to find an -dimensional vector x min ∈ S such that, ∀x ∈ S, (x min ) ≤ (x).
Without loss of generality, we can assume that S = ∏ =1 [− , ] where = > 0. The function : S → R is called the objective function of the minimization problem. We do not require to be continuous, but it must be bounded. Furthermore, we only consider the unconstrained minimization.
The following properties are assumed, and we will make use of them in our analyses: (1) The subset of optimal solutions in S is nonempty.
(2) Let * = min{ ( ) | ∈ S} be the fitness value of an optimal solution, and let S * ( ) = { ∈ S | ( ) < * + } be the optimal epsilon neighborhood. Every element of S * ( ) is an optimal solution of the minimization problem.
The first assumption describes the existence of optimal solutions to the problem. The second assumption presents a rigorous definition of optimal solution for continuous minimization optimization problems. The third assumption indicates that there are always solutions whose objective values are distributed continuously and arbitrarily close to the optimal, which makes the minimization problem solvable.

Markov Chain Associated with EP Algorithms.
Our running time analyses are based on representing the EP algorithms as Markov chain. In this section, we explain the terminologies and notations used throughout the rest of this study.
Definition 3 (stochastic process of EP). The stochastic process of an evolutionary programming algorithm EP is denoted by is the th individual at the th iteration.
The stochastic status EP represents the individuals of the th iteration population for the algorithm EP. All stochastic processes examined in this paper are discrete-time; that is, Definition 4 (status space). The status space of EP is Ω EP is the set of all possible population statuses for EP. Intuitively, each element of Ω EP is associated with a possible population in the implementation of EP. Let x * ∈ S * ( ) be an optimal solution. We define the optimal status space as follows.
Hence, all members of Ω * EP ( ) contain at least one optimal solution represented by individual x * .
Proof. The proof is given in the appendix.
We now show that the stochastic process { EP } +∞ =0 of EP is an absorbing Markov chain, defined as follows.
Proof. The proof is given in the appendix. This property implies that once an EP algorithm attains an optimal state, it will never leave optimality.

General Runtime Analysis Framework for EP Algorithms
The analysis of EP algorithms has usually been approximated using a simpler measure known as the first hitting time [13,17], which is employed in this study.
If an EP algorithm is modeled as an absorbing Markov chain, the running time of the EP can be measured by its first hitting time EP . We denote its expected value by EP which can be calculated by Theorem 11.
Let EP = { EP ∈ Ω * EP ( )} = { EP ≤ } be the probability that EP has attained an optimal state by time .

Corollary 12.
The expected first hitting time can also be expressed as

Computational Intelligence and Neuroscience
Proof. The proof is given in the appendix.
The conclusions of Theorem 11 and Corollary 12 are a direct approach to calculating the first hitting time of EP. However, Corollary 12 is more practical than Theorem 11 for this purpose since = { EP ∈ Ω * EP ( ) | EP −1 ∉ Ω * EP ( )}, which is the probability that the process first finds an optimal solution at time , is dependent on the mutation and selection techniques of the EP. Hence, the framework of Corollary 12 is similar to the one in [17]. However, the estimating method [17] is based on a probability in discrete optimization is a probability for continuous status while is for the discrete one. In general, the exact value of is difficult to calculate. Alternatively, first hitting time can also be analyzed in terms of an upper and a lower bound of , as shown by the following Corollaries 13 and 15.
Proof. The proof is given in the appendix.
Corollary 13 indicates that EP can be studied by the lower bound and upper bound of { EP ∈ Ω * EP ( ) | EP −1 ∉ Ω * EP ( )}. Therefore, the theorem and corollaries introduce a first-hitting-time framework for the running time analysis of EP. The running times of EP based on Gaussian and Cauchy mutation are studied following the framework.

Runtime Upper Bounds of CEP and FEP
In this section, we use the framework proposed in Section 3 to study the running time of EP based on Gaussian and Cauchy mutations, that is, CEP and FEP. Moreover, our running time analysis aims at a class of EP with constant variation, as shown in (2).

Mean Running Time of CEP. CEP [2]
is a classical EP, from which several continuous evolutionary algorithms are derived. This subsection mainly focuses on the running time of CEP proposed by Fogel [3], Schwefel [6], and Schwefel [5,6]. The mutation of CEP is based on the standard normal distribution indicated by (3).
(2) The right part of the inequality of conclusion (1) is maximum when = 2 .
Proof. The proof is given in the appendix.
In Theorem 14, Part (1) indicates a lower bound of the probability that an individual x can be renewed to be x in the optimal neighborhood S * ( ). As a result, the lower bound is a function of variation . Part (2) presents the lower bound that Part (1) will be tightest if = 2 . By this, the key factor of (2) ∀ > 0, Proof. The proof is given in the appendix.
Corollary 15 shows that CEP converges globally and that the upper bound of CEP's running time decreases as the Lebesgue measure of the optimal neighborhood (S * ( )) of S * ( ) increases. A larger (S * ( )) translates to a larger optimal neighborhood ∀ > 0, which allows the solution of CEP more easily. Moreover, an increase in problem dimension number can increase the upper bound, and enlarging the individual number will make the upper bound smaller.
According to (6), has a smaller upper bound when the population size increases. Approximately, since (

Mean
Running Time of FEP. FEP was proposed by Yao et al. [7] as an improvement to CEP. The mutation for FEP is based on the Cauchy distribution indicated by (4). The property of the probability Theorem 16 ( = 0, 1, . . .).
be the stochastic process of FEP, and then one has the following: (2) The right part of the inequality of conclusion (1) is maximum when = 2 .
Proof. The proof is given in the appendix.
Similar to Theorem 14, FEP with = 2 may lead to a tight lower bound of the probability in Part (1) and Part (3). Theorem 16 indicates that (S * ( )) affects the convergence of FEP directly. A larger (S * ( )) allows FEP to more easily arrive at a status in the optimal state space (Definition 5). Conversely, a bigger (the bounds of search space) increases the difficulty of the problem for FEP. Given this convergence time framework, Corollary 17 summarizes the convergence capacity and running time upper bound of FEP.
Proof. The proof is given in the appendix.
Corollary 17 proves the convergence of FEP and indicates that a larger (S * ( )) can make FEP converge faster. Using a similar analysis to that for CEP, a larger dimension number of problems can increase the upper bound of FEP, but larger individual number can lead to a smaller upper bound. Furthermore, [− , ] is the maximum interval bound for each dimension of the variables to be optimized (Definition 2). As a result, the second conclusion of Corollary 17 also implies that a larger search space will increase the upper bound of EP .

Conclusion
In this paper, we propose a running time framework to calculate the mean running time of EP. Based on this framework, the convergence and mean running time of CEP and FEP with constant variation are studied. We also obtain some results at the worst running time of the considered EP, although the results show that the upper bounds can be tighter if the variation = 2 where 2 is the length of the searching interval per dimension. It is shown that the individual number, problem dimension number, searching range, and the Lebesgue measure of the optimal neighborhood of the optimal solution have a direct impact on the bounds of the expected convergence times of the considered EP. Moreover, the larger the Lebesgue measure of the optimal neighborhood of the optimum, the lower the upper bound of the mean convergence time. In addition, the convergence time of the EP can be polynomial on average on the condition that the Lebesgue measure is greater than a value that is exponential to .
However, it is possible to make an improvement on the running time framework and analysis given in this study. The deduction process in the proofs for Theorems 14 and 16 uses few properties of the distribution functions of the mutations, and so it is possible to tighten the results. By introducing more information on the specific mutation operations, more sound theoretical conclusions may be derivable. More importantly, unlike the rigorous conditions under which CEP and FEP can converge in polynomial time, the running time analysis of specific EP algorithms for real-world and constructive problems would have a more significant and practical impact. Future research could also focus on the runtime analysis of specific case studies of EP.
The proposed framework and results can be considered as a first step for analyzing the running time of evolutionary programming algorithms. We hope that our results can serve as a basis for further theoretical studies.
Proof of Lemma 9. EP ∈ Ω * EP ( ) when ∃(x * ( ) , ( ) ) ∈ EP where x * ( ) is an optimal solution. Given Steps (5)-(6) of EP, x * ( ) will have the most "wins" as well as the highest fitness, so x * ( ) will be selected for the next iteration with probability one if there are less than optimal solutions in the tournament. x * ( ) might be lost but other optimal solutions will be selected if there are more than optimal solutions in the parent and offspring. Thus, { EP +1 ∉ Ω * EP ( ) | EP ∈ Ω * EP ( )} = 0, and { EP } +∞ =0 is an absorbing Markov chain to Ω * EP ( ).