This paper introduces drift analysis approach in studying the convergence and hitting times of evolutionary algorithms. First the methodology of drift analysis is introduced, which links evolutionary algorithms with M...This paper introduces drift analysis approach in studying the convergence and hitting times of evolutionary algorithms. First the methodology of drift analysis is introduced, which links evolutionary algorithms with Markov chains or supermartingales. Then the drift conditions which guarantee the convergence of evolutionary algorithms are described. And next the drift conditions which are used to estimate the hitting times of evolutionary algorithms are presented. Finally an example is given to show how to analyse hitting times of EAs by drift analysis approach.展开更多
Let h(t) be a smooth function, Bt a standard Brownian motion and th=inf{t;Bt=h(t)} the first hitting time. In this paper, new formulations are derived to evaluate the probability density of the first hitting time. If ...Let h(t) be a smooth function, Bt a standard Brownian motion and th=inf{t;Bt=h(t)} the first hitting time. In this paper, new formulations are derived to evaluate the probability density of the first hitting time. If u(x, t) denotes the density function of x=Bt for t th, then uxx=2ut and u(h(t),t)=0. Moreover, the hitting time density dh(t) is 1/2ux(h(t),t). Applying some partial differential equation techniques, we derive a simple integral equation for dh(t). Two examples are demonstrated in this article.展开更多
The exponentially-distributed random timestepping algorithm with boundary test is implemented to evaluate the prices of some variety of single one-sided barrier option contracts within the framework of Black-Scholes m...The exponentially-distributed random timestepping algorithm with boundary test is implemented to evaluate the prices of some variety of single one-sided barrier option contracts within the framework of Black-Scholes model, giving efficient estimation of their hitting times. It is numerically shown that this algorithm, as for the Brownian bridge technique, can improve the rate of weak convergence from order one-half for the standard Monte Carlo to order 1. The exponential timestepping algorithm, however, displays better results, for a given amount of CPU time, than the Brownian bridge technique as the step size becomes larger or the volatility grows up. This is due to the features of the exponential distribution which is more strongly peaked near the origin and has a higher kurtosis compared to the normal distribution, giving more stability of the exponential timestepping algorithm at large time steps and high levels of volatility.展开更多
In this paper, a novel scheduling mechanism is proposed to handle the real-time overload problem by maximizing the cumulative values of three types of tasks： the soft, the hard and the imprecise tasks. The simulation...In this paper, a novel scheduling mechanism is proposed to handle the real-time overload problem by maximizing the cumulative values of three types of tasks： the soft, the hard and the imprecise tasks. The simulation results show that the performance of our presented mechanism in this paper is greatly improved, much better than that of the other three mechanisms： earliest deadline first （EDF）, highest value first （HVF） and highest density first （HDF）, under the same conditions of all nominal loads and task type proportions.展开更多
For a birth and death process X = { X( t), t 【 σ } with explosion and lifespan a distributions and joint distributions of first hitting time and first hitting location after explosion of set Bn - {0,1, …, n} have b...For a birth and death process X = { X( t), t 【 σ } with explosion and lifespan a distributions and joint distributions of first hitting time and first hitting location after explosion of set Bn - {0,1, …, n} have been found.展开更多
We present an explicit and recursive representation for high order moments of the first hitting times of single death processes.Based on that,some necessary or sufficient conditions of exponential ergodicity as well a...We present an explicit and recursive representation for high order moments of the first hitting times of single death processes.Based on that,some necessary or sufficient conditions of exponential ergodicity as well as a criterion on■-ergodicity are obtained for single death processes,respectively.展开更多
An explicit and recursive representation is presented for moments of the first hitting times of birth-death processes on trees. Based on that, the criteria on ergodicity, strong ergodicity, and l-ergodicity of the pro...An explicit and recursive representation is presented for moments of the first hitting times of birth-death processes on trees. Based on that, the criteria on ergodicity, strong ergodicity, and l-ergodicity of the processes as well as a necessary condition for exponential ergodicity are obtained.展开更多
IT is well known that the distribution of hitting time, hitting point, last exiting time, and lastexiting point for Brownian motion to balls has been extensively studied. A similar investi-gation of rectangles or cube...IT is well known that the distribution of hitting time, hitting point, last exiting time, and lastexiting point for Brownian motion to balls has been extensively studied. A similar investi-gation of rectangles or cubes has also been well done. However, analogous questions for Brow-nian motion to ellipsoid are rarely concerned. Bai and Cai obtained the distribution of展开更多
In this paper,we consider weak horseshoe with bounded-gap-hitting times.For a flow(M,Ф),it is shown that if the time one map(M,Ф_(1))has weak horseshoe with boundedgap-hitting times,so is(M,Ф_(τ))for all τ≠0.In ...In this paper,we consider weak horseshoe with bounded-gap-hitting times.For a flow(M,Ф),it is shown that if the time one map(M,Ф_(1))has weak horseshoe with boundedgap-hitting times,so is(M,Ф_(τ))for all τ≠0.In addition,we prove that for an affine homeomorphism of a compact metric abelian group,positive topological entropy is equivalent to weak horseshoe with bounded-gap-hitting times.展开更多
In this paper, the authors compute the explicit formulas for the joint distributions of thehitting time and place for a sphere or concentric spherical shell by Brownian motion, when theprocess starts either outside th...In this paper, the authors compute the explicit formulas for the joint distributions of thehitting time and place for a sphere or concentric spherical shell by Brownian motion, when theprocess starts either outside the sphere or the region bounded by concentric spheres.展开更多
基金Supported by Engineering and Physical Science Research Courcil(GR/R52541/01)and State Laboratory of Software Engineering at Wuhan University
文摘This paper introduces drift analysis approach in studying the convergence and hitting times of evolutionary algorithms. First the methodology of drift analysis is introduced, which links evolutionary algorithms with Markov chains or supermartingales. Then the drift conditions which guarantee the convergence of evolutionary algorithms are described. And next the drift conditions which are used to estimate the hitting times of evolutionary algorithms are presented. Finally an example is given to show how to analyse hitting times of EAs by drift analysis approach.
文摘Let h(t) be a smooth function, Bt a standard Brownian motion and th=inf{t;Bt=h(t)} the first hitting time. In this paper, new formulations are derived to evaluate the probability density of the first hitting time. If u(x, t) denotes the density function of x=Bt for t th, then uxx=2ut and u(h(t),t)=0. Moreover, the hitting time density dh(t) is 1/2ux(h(t),t). Applying some partial differential equation techniques, we derive a simple integral equation for dh(t). Two examples are demonstrated in this article.
文摘The exponentially-distributed random timestepping algorithm with boundary test is implemented to evaluate the prices of some variety of single one-sided barrier option contracts within the framework of Black-Scholes model, giving efficient estimation of their hitting times. It is numerically shown that this algorithm, as for the Brownian bridge technique, can improve the rate of weak convergence from order one-half for the standard Monte Carlo to order 1. The exponential timestepping algorithm, however, displays better results, for a given amount of CPU time, than the Brownian bridge technique as the step size becomes larger or the volatility grows up. This is due to the features of the exponential distribution which is more strongly peaked near the origin and has a higher kurtosis compared to the normal distribution, giving more stability of the exponential timestepping algorithm at large time steps and high levels of volatility.
基金supported by the Shanghai Applied Materials Foundation (Grant No.06SA18)
文摘In this paper, a novel scheduling mechanism is proposed to handle the real-time overload problem by maximizing the cumulative values of three types of tasks： the soft, the hard and the imprecise tasks. The simulation results show that the performance of our presented mechanism in this paper is greatly improved, much better than that of the other three mechanisms： earliest deadline first （EDF）, highest value first （HVF） and highest density first （HDF）, under the same conditions of all nominal loads and task type proportions.
文摘For a birth and death process X = { X( t), t 【 σ } with explosion and lifespan a distributions and joint distributions of first hitting time and first hitting location after explosion of set Bn - {0,1, …, n} have been found.
基金The authors thank the anonymous referees for their very valuable suggestions and careful reading of the draft,which greatly improved the quality of the paperThis work was supported by the National Natural Science Foundation of China(Grant Nos.11571043,11771047,11871008).
文摘We present an explicit and recursive representation for high order moments of the first hitting times of single death processes.Based on that,some necessary or sufficient conditions of exponential ergodicity as well as a criterion on■-ergodicity are obtained for single death processes,respectively.
基金The author acknowledges the constructive discussion with Professors Mu-Fa Chen, Yong-Hua Mao, and Yutao Ma, and thanks the anonymous referees for their very valuable suggestions and careful reading of the draft, which greatly improved the quality of the paper. This work was supported by the National Natural Science Foundation of China (Grant Nos. 11571043, 11771047, 11871008).
文摘An explicit and recursive representation is presented for moments of the first hitting times of birth-death processes on trees. Based on that, the criteria on ergodicity, strong ergodicity, and l-ergodicity of the processes as well as a necessary condition for exponential ergodicity are obtained.
文摘IT is well known that the distribution of hitting time, hitting point, last exiting time, and lastexiting point for Brownian motion to balls has been extensively studied. A similar investi-gation of rectangles or cubes has also been well done. However, analogous questions for Brow-nian motion to ellipsoid are rarely concerned. Bai and Cai obtained the distribution of
基金Leiye Xu is partially supported by NNSF of China(11801538,11871188)the USTC Research Funds of the Double First-Class Initiative.Junren Zheng is partially supported by NNSF of China(11971455).
文摘In this paper,we consider weak horseshoe with bounded-gap-hitting times.For a flow(M,Ф),it is shown that if the time one map(M,Ф_(1))has weak horseshoe with boundedgap-hitting times,so is(M,Ф_(τ))for all τ≠0.In addition,we prove that for an affine homeomorphism of a compact metric abelian group,positive topological entropy is equivalent to weak horseshoe with bounded-gap-hitting times.
文摘In this paper, the authors compute the explicit formulas for the joint distributions of thehitting time and place for a sphere or concentric spherical shell by Brownian motion, when theprocess starts either outside the sphere or the region bounded by concentric spheres.
