We introduce to the runtime analysis of evolutionary algorithms two powerful techniques: probability-generating functions and variable drift analysis. They are shown to provide a clean framework for proving sharp uppe...
详细信息
ISBN:
(纸本)9781450305570
We introduce to the runtime analysis of evolutionary algorithms two powerful techniques: probability-generating functions and variable drift analysis. They are shown to provide a clean framework for proving sharp upper and lower bounds. As an application, we improve the results by Doerr et al. (GECCO 2010) in several respects. First, the upper bound on the expected running time of the most successful quasirandom evolutionary algorithm for the One Max function is improved from 1.28n ln n to 0.982n ln n, which breaks the barrier of n ln n posed by coupon-collector processes. Compared to the classical (1+1) EA, whose runtime will for the first time be analyzed with respect to terms of lower order, this represents a speedup by more than a factor of e = 2.71 ...
We study the delay performance of a queue with a place reservation mechanism. The objective of this discipline is to provide a better quality of service to arriving packets that are delay sensitive at the cost of allo...
详细信息
We study the delay performance of a queue with a place reservation mechanism. The objective of this discipline is to provide a better quality of service to arriving packets that are delay sensitive at the cost of allowing higher delays for the best effort packets and was first proposed by Burakowski and Tarasiuk. In our model, we consider a discrete-time queue with arrivals of type 1 (delay sensitive) and type 2 (best-effort). Whenever a packet of type 1 enters the queue, it takes the position of the reservation that was created there by a previous arrival of type 1 and creates a new reservation at the end of the queue. Type 2 arrivals always take place at the end of the queue in the usual way. We present the analysis of this model based oil the use of generatingfunctions and provide results for the mean value, variance and tail behaviour of the delay experienced by both the delay-sensitive and the best-effort traffic. For a specific example, we compare the delay performance of this reservation discipline to the performance of all absolute priority discipline on the one hand, and to the reference discipline first-in first-out on the other. (C) 2006 Elsevier Ltd. All rights reserved.
A simple MP system consisting of an input-output facility and a central processor is modeled as a two-parameter Markov chain. The conditions for stability are demonstrated, and the steady-state joint probabilities are...
详细信息
A simple MP system consisting of an input-output facility and a central processor is modeled as a two-parameter Markov chain. The conditions for stability are demonstrated, and the steady-state joint probabilities are calculated explicitly. Various priority and capacity assignments result in radically different analytical situations, some of which have been considered in the literature. The present work treats a version that was considered for a time intractable. This paper emphasizes the analytical properties of the probability-generating functions and a method to solve a resultant functional equation. The numerical results display the importance of dependence between variables in the model.
The class of probability-generating function (PGF) kernels is introduced, which consists of kernels supported on the unit hypersphere, for the purposes of spherical data analysis. PGF kernels generalize RBF kernels in...
详细信息
ISBN:
(纸本)9783031723315;9783031723322
The class of probability-generating function (PGF) kernels is introduced, which consists of kernels supported on the unit hypersphere, for the purposes of spherical data analysis. PGF kernels generalize RBF kernels in the context of spherical data. The properties of PGF kernels are studied. A semi-parametric learning algorithm is introduced to enable the use of PGF kernels with spherical data.
Understanding cascading processes on complex network topologies is paramount for modelling how diseases, information, fake news and other media spread. In this article, we extend the multi-type branching process metho...
详细信息
Understanding cascading processes on complex network topologies is paramount for modelling how diseases, information, fake news and other media spread. In this article, we extend the multi-type branching process method developed in Keating et al., (2022), which relies on networks having homogenous node properties, to a more general class of clustered networks. Using a model of socially inspired complex contagion we obtain results, not just for the average behaviour of the cascades but for full distributions of the cascade properties. We introduce a new method for the inversion of probabilitygeneratingfunctions to recover their underlying probability distributions;this derivation naturally extends to higher dimensions. This inversion technique is used along with the multi-type branching process to obtain univariate and bivariate distributions of cascade properties. Finally, using clique-cover methods, we apply the methodology to synthetic and real-world networks and compare the theoretical distribution of cascade sizes with the results of extensive numerical simulations.
暂无评论