A Note on the First Hitting  Time of (1+N) Evolutionary Algorithm  for Linear Functions with Boolean Inputs

Jun He

doi:10.1109/CEC.2010.5586055

A Note on the First Hitting Time of (1+N) Evolutionary Algorithm for Linear Functions with Boolean Inputs

Jun He

Department of Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference Proceeding (Non-Journal item)

4 Citations (Scopus)

Abstract

Linear functions, as a canonical model of unimodal problems, have been widely used in the theoretical study of evolutionary algorithms (EAs). However in most of cases, only the simplest linear function, i.e. One-Max function, is taken in the theoretical study. A question arises naturally: whether can the results for One-Max function be generalized to linear functions? The main contribution of this paper is to generalize a result about the first hitting time of (1 + λ) EA from One-Max function to linear functions. A new proof is proposed based on drift analysis. This work is a direct extension of the previous analysis of (1 + 1) EA for linear functions.

Original language	English
Title of host publication	Proceedings of 2010 IEEE Congress on Evolutionary Computation
Publisher	IEEE Press
Pages	1-6
Number of pages	6
ISBN (Print)	978-1-4244-6900-3
DOIs	https://doi.org/10.1109/CEC.2010.5586055
Publication status	Published - 27 Sept 2010
Event	IEEE Congress on Evolutionary Computation (CEC) - Barcelona, Spain Duration: 18 Jul 2010 → 23 Jul 2010

Conference

Conference	IEEE Congress on Evolutionary Computation (CEC)
Country/Territory	Spain
City	Barcelona
Period	18 Jul 2010 → 23 Jul 2010

Access to Document

10.1109/CEC.2010.5586055

Permanent link

Persistent link

Cite this

@inproceedings{afef910681f449f2aa79ae17c5e6ecfc,

title = "A Note on the First Hitting Time of (1+N) Evolutionary Algorithm for Linear Functions with Boolean Inputs",

abstract = "Linear functions, as a canonical model of unimodal problems, have been widely used in the theoretical study of evolutionary algorithms (EAs). However in most of cases, only the simplest linear function, i.e. One-Max function, is taken in the theoretical study. A question arises naturally: whether can the results for One-Max function be generalized to linear functions? The main contribution of this paper is to generalize a result about the first hitting time of (1 + λ) EA from One-Max function to linear functions. A new proof is proposed based on drift analysis. This work is a direct extension of the previous analysis of (1 + 1) EA for linear functions.",

author = "Jun He",

year = "2010",

month = sep,

day = "27",

doi = "10.1109/CEC.2010.5586055",

language = "English",

isbn = "978-1-4244-6900-3",

pages = "1--6",

booktitle = "Proceedings of 2010 IEEE Congress on Evolutionary Computation",

publisher = "IEEE Press",

address = "United States of America",

note = "IEEE Congress on Evolutionary Computation (CEC) ; Conference date: 18-07-2010 Through 23-07-2010",

}

TY - GEN

T1 - A Note on the First Hitting Time of (1+N) Evolutionary Algorithm for Linear Functions with Boolean Inputs

AU - He, Jun

PY - 2010/9/27

Y1 - 2010/9/27

N2 - Linear functions, as a canonical model of unimodal problems, have been widely used in the theoretical study of evolutionary algorithms (EAs). However in most of cases, only the simplest linear function, i.e. One-Max function, is taken in the theoretical study. A question arises naturally: whether can the results for One-Max function be generalized to linear functions? The main contribution of this paper is to generalize a result about the first hitting time of (1 + λ) EA from One-Max function to linear functions. A new proof is proposed based on drift analysis. This work is a direct extension of the previous analysis of (1 + 1) EA for linear functions.

AB - Linear functions, as a canonical model of unimodal problems, have been widely used in the theoretical study of evolutionary algorithms (EAs). However in most of cases, only the simplest linear function, i.e. One-Max function, is taken in the theoretical study. A question arises naturally: whether can the results for One-Max function be generalized to linear functions? The main contribution of this paper is to generalize a result about the first hitting time of (1 + λ) EA from One-Max function to linear functions. A new proof is proposed based on drift analysis. This work is a direct extension of the previous analysis of (1 + 1) EA for linear functions.

UR - http://hdl.handle.net/2160/11907

U2 - 10.1109/CEC.2010.5586055

DO - 10.1109/CEC.2010.5586055

M3 - Conference Proceeding (Non-Journal item)

SN - 978-1-4244-6900-3

SP - 1

EP - 6

BT - Proceedings of 2010 IEEE Congress on Evolutionary Computation

PB - IEEE Press

T2 - IEEE Congress on Evolutionary Computation (CEC)

Y2 - 18 July 2010 through 23 July 2010

ER -