Title :
A note on the first hitting time of (1 + λ) evolutionary algorithm for linear functions with boolean inputs
Author_Institution :
Dept. of Comput. Sci., Aberystwyth Univ., Aberystwyth, UK
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.
Keywords :
Boolean algebra; evolutionary computation; Boolean Inputs; EA; evolutionary algorithm; first hitting time; linear functions; one max function; Ant colony optimization; Evolutionary computation; Genetics; Helium; Lead; Markov processes; Upper bound;
Conference_Titel :
Evolutionary Computation (CEC), 2010 IEEE Congress on
Conference_Location :
Barcelona
Print_ISBN :
978-1-4244-6909-3
DOI :
10.1109/CEC.2010.5586055