✦ LIBER ✦

Drift analysis and average time complexity of evolutionary algorithms

✍ Scribed by Jun He; Xin Yao

Publisher: Elsevier Science
Year: 2001
Tongue: English
Weight: 212 KB
Volume: 127
Category: Article
ISSN: 0004-3702
DOI: 10.1016/s0004-3702(01)00058-3

No coin nor oath required. For personal study only.

✦ Synopsis

The computational time complexity is an important topic in the theory of evolutionary algorithms (EAs). This paper reports some new results on the average time complexity of EAs. Based on drift analysis, some useful drift conditions for deriving the time complexity of EAs are studied, including conditions under which an EA will take no more than polynomial time (in problem size) to solve a problem and conditions under which an EA will take at least exponential time (in problem size) to solve a problem. The paper first presents the general results, and then uses several problems as examples to illustrate how these general results can be applied to concrete problems in analyzing the average time complexity of EAs. While previous work only considered (1 + 1) EAs without any crossover, the EAs considered in this paper are fairly general, which use a finite population, crossover, mutation, and selection.

📜 SIMILAR VOLUMES

Erratum to: Drift analysis and average t

Erratum to: Drift analysis and average time complexity of evolutionary algorithms: [Artificial Intelligence 127 (2001) 57–85]

✍ Jun He; Xin Yao 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 54 KB

The proof of Theorem 6 in the paper by J. He and X. Yao [Artificial Intelligence 127 (1) (2001) 57-85] contains a mistake, although the theorem is correct [S. Droste et al., Theoret. Comput. Sci. 276 (2002) 51-81]. This note gives a revised proof and theorem. It turns out that the revised theorem is

The time-dependent shortest pair of disj

The time-dependent shortest pair of disjoint paths problem: Complexity, models, and algorithms

✍ Sherali, Hanif D.; Ozbay, Kaan; Subramanian, Shivaram 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 160 KB 👁 3 views

In this paper, we examine complexity issues, models, and algorithms for the problem of finding a shortest pair of disjoint paths between two nodes of a network such that the total travel delay is minimized, given that the individual arc delays are time-dependent. Such disjoint paths address the issu

Probabilistic analysis of the time compl

Probabilistic analysis of the time complexity of quicksort

✍ Tadashi Mizoi; Shunji Osaki 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 460 KB

## Abstract Quicksort is a well‐known sorting algorithm based on the divided control. the array to be sorted is divided into two sets as follows. an element in the array is specified, and the set of values larger than the value of that element and the set of values smaller than that value are const

Average complexity of divide-and-conquer

Average complexity of divide-and-conquer algorithms: Information processing letters vol. 29, no. 6 (8 December 1988) pp. 319–326

✍ Boris S. Veroy 📂 Article 📅 1989 🏛 Elsevier Science 🌐 English ⚖ 44 KB

Complexity of Intercalation of Hydrazine

Complexity of Intercalation of Hydrazine into Kaolinite—A Controlled Rate Thermal Analysis and DRIFT Spectroscopic Study

✍ Ray L. Frost; János Kristof; Erzsébet Horvath; Wayde N. Martens; J.T. Kloprogge 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 167 KB

Optimal and suboptimal smoothing algorit

Optimal and suboptimal smoothing algorithms for identification of time-varying systems with randomly drifting parameters

✍ Maciej Niedźwiecki 📂 Article 📅 2008 🏛 Elsevier Science 🌐 English ⚖ 617 KB

Noncausal estimation algorithms, which involve smoothing, can be used for off-line identification of nonstationary systems. Since smoothing is based on both past and future data, it offers increased accuracy compared to causal (tracking) estimation schemes, incorporating past data only. It is shown