Analysis of Selection Algorithms: A Markov Chain Approach

Uday Kumar Chakraborty; Kalyanmoy Deb; Mandira Chakraborty

doi:10.1162/evco.1996.4.2.133

Analysis of Selection Algorithms: A Markov Chain Approach

Uday Kumar Chakraborty, Kalyanmoy Deb, Mandira Chakraborty

Research output: Contribution to journal › Article › peer-review

Abstract

A Markov chain framework is developed for analyzing a wide variety of selection techniques used in genetic algorithms (GAs) and evolution strategies (ESs). Specifically, we consider linear ranking selection, probabilistic binary tournament selection, deterministic s-ary (s = 3,4, …) tournament selection, fitness-proportionate selection, selection in Whitley's GENITOR, selection in (μ, λ)-ES, selection in (μ + λ)-ES, (μ, λ)-linear ranking selection in GAs, (μ + λ)-linear ranking selection in GAs, and selection in Eshelman's CHC algorithm. The analysis enables us to compare and contrast the various selection algorithms with respect to several performance measures based on the probability of takeover. Our analysis is exact—we do not make any assumptions or approximations. Finite population sizes are considered. Our approach is perfectly general, and following the methods of this paper, it is possible to analyze any selection strategy in evolutionary algorithms.

Original language	American English
Journal	Electronic Commerce
Volume	4
DOIs	https://doi.org/10.1162/evco.1996.4.2.133
State	Published - Jun 1 1996
Externally published	Yes

Disciplines

Mathematics
Applied Mathematics
Theory and Algorithms
Artificial Intelligence and Robotics

Access to Document

10.1162/evco.1996.4.2.133License: Unspecified

Cite this

@article{f9a95b504fcd47928eb2ddde8ca6072c,

title = "Analysis of Selection Algorithms: A Markov Chain Approach",

abstract = " A Markov chain framework is developed for analyzing a wide variety of selection techniques used in genetic algorithms (GAs) and evolution strategies (ESs). Specifically, we consider linear ranking selection, probabilistic binary tournament selection, deterministic s-ary (s = 3,4, …) tournament selection, fitness-proportionate selection, selection in Whitley's GENITOR, selection in (μ, λ)-ES, selection in (μ + λ)-ES, (μ, λ)-linear ranking selection in GAs, (μ + λ)-linear ranking selection in GAs, and selection in Eshelman's CHC algorithm. The analysis enables us to compare and contrast the various selection algorithms with respect to several performance measures based on the probability of takeover. Our analysis is exact—we do not make any assumptions or approximations. Finite population sizes are considered. Our approach is perfectly general, and following the methods of this paper, it is possible to analyze any selection strategy in evolutionary algorithms.",

author = "Chakraborty, {Uday Kumar} and Kalyanmoy Deb and Mandira Chakraborty",

note = "MIT Press Journals is a mission-driven, not-for-profit scholarly publisher devoted to the widest dissemination of its content.",

year = "1996",

month = jun,

day = "1",

doi = "10.1162/evco.1996.4.2.133",

language = "American English",

volume = "4",

journal = "Electronic Commerce",

}

TY - JOUR

T1 - Analysis of Selection Algorithms: A Markov Chain Approach

AU - Chakraborty, Uday Kumar

AU - Deb, Kalyanmoy

AU - Chakraborty, Mandira

N1 - MIT Press Journals is a mission-driven, not-for-profit scholarly publisher devoted to the widest dissemination of its content.

PY - 1996/6/1

Y1 - 1996/6/1

N2 - A Markov chain framework is developed for analyzing a wide variety of selection techniques used in genetic algorithms (GAs) and evolution strategies (ESs). Specifically, we consider linear ranking selection, probabilistic binary tournament selection, deterministic s-ary (s = 3,4, …) tournament selection, fitness-proportionate selection, selection in Whitley's GENITOR, selection in (μ, λ)-ES, selection in (μ + λ)-ES, (μ, λ)-linear ranking selection in GAs, (μ + λ)-linear ranking selection in GAs, and selection in Eshelman's CHC algorithm. The analysis enables us to compare and contrast the various selection algorithms with respect to several performance measures based on the probability of takeover. Our analysis is exact—we do not make any assumptions or approximations. Finite population sizes are considered. Our approach is perfectly general, and following the methods of this paper, it is possible to analyze any selection strategy in evolutionary algorithms.

AB - A Markov chain framework is developed for analyzing a wide variety of selection techniques used in genetic algorithms (GAs) and evolution strategies (ESs). Specifically, we consider linear ranking selection, probabilistic binary tournament selection, deterministic s-ary (s = 3,4, …) tournament selection, fitness-proportionate selection, selection in Whitley's GENITOR, selection in (μ, λ)-ES, selection in (μ + λ)-ES, (μ, λ)-linear ranking selection in GAs, (μ + λ)-linear ranking selection in GAs, and selection in Eshelman's CHC algorithm. The analysis enables us to compare and contrast the various selection algorithms with respect to several performance measures based on the probability of takeover. Our analysis is exact—we do not make any assumptions or approximations. Finite population sizes are considered. Our approach is perfectly general, and following the methods of this paper, it is possible to analyze any selection strategy in evolutionary algorithms.

UR - http://dx.doi.org/10.1162/evco.1996.4.2.133

U2 - 10.1162/evco.1996.4.2.133

DO - 10.1162/evco.1996.4.2.133

M3 - Article

VL - 4

JO - Electronic Commerce

JF - Electronic Commerce

ER -

Analysis of Selection Algorithms: A Markov Chain Approach

Abstract

Disciplines

Access to Document

Other files and links

Cite this