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

Adran Cyfrifiadureg

Allbwn ymchwil: Pennod mewn Llyfr/Adroddiad/Trafodion Cynhadledd › Trafodion Cynhadledd (Nid-Cyfnodolyn fathau)

4 Dyfyniadau (Scopus)

Crynodeb

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.

Iaith wreiddiol	Saesneg
Teitl	Proceedings of 2010 IEEE Congress on Evolutionary Computation
Cyhoeddwr	IEEE Press
Tudalennau	1-6
Nifer y tudalennau	6
ISBN (Argraffiad)	978-1-4244-6900-3
Dynodwyr Gwrthrych Digidol (DOIs)	https://doi.org/10.1109/CEC.2010.5586055
Statws	Cyhoeddwyd - 27 Medi 2010
Digwyddiad	IEEE Congress on Evolutionary Computation (CEC) - Barcelona, Sbaen Hyd: 18 Gorff 2010 → 23 Gorff 2010

Cynhadledd

Cynhadledd	IEEE Congress on Evolutionary Computation (CEC)
Gwlad/Tiriogaeth	Sbaen
Dinas	Barcelona
Cyfnod	18 Gorff 2010 → 23 Gorff 2010

Mynediad at Ddogfen

10.1109/CEC.2010.5586055

Cysylltiad parhaol

Dolen barhaus

Ffeiliau eraill a chysylltiadau

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

Dyfynnu hyn

@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 -