The Max problem revisited: The importance of mutation in genetic programming

被引：12

作者：

Koetzing, Timo ^{[1
]}

Sutton, Andrew M. ^{[2
]}

Neumann, Frank ^{[2
]}

O'Reilly, Una-May ^{[3
]}

机构：

[1] Max Planck Inst Informat, Dept Algorithms & Complex, D-66123 Saarbrucken, Germany

[2] Univ Adelaide, Sch Comp Sci, Evolutionary Computat Grp, Adelaide, SA 5005, Australia

[3] MIT CSAIL, Cambridge, MA 02139 USA

来源：

THEORETICAL COMPUTER SCIENCE | 2014年 / 545卷

关键词：

Genetic programming; Mutation; Theory; Runtime analysis;

D O I：

10.1016/j.tcs.2013.06.014

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We study the importance of mutation in genetic programming and contribute to the rigorous understanding of genetic programming algorithms by providing runtime complexity analyses for the well-known Max problem. Several experimental studies have indicated that it is hard to solve the Max problem with crossover-based algorithms. Our analyses show that different variants of the Max problem can provably be solved efficiently using simple mutation-based genetic programming algorithms. Our results advance the body of computational complexity analyses of genetic programming, indicate the importance of mutation in genetic programming, and reveal new insights into the behavior of mutation-based genetic programming algorithms. (C) 2013 Elsevier B.V. All rights reserved.

引用

页码：94 / 107

页数：14

共 17 条

[1]

[Anonymous], 2003, Genetic programming IV: routine human-competitive machine intelligence

[2]

Auger A., 2011, Theory of randomized search heuristics: Foundations and recent developments

[3]

Cathabard S, 2011, FOGA 11: PROCEEDINGS OF THE 2011 ACM/SIGEVO FOUNDATIONS OF GENETIC ALGORITHMS XI, P173

[4]

Durrett G, 2011, FOGA 11: PROCEEDINGS OF THE 2011 ACM/SIGEVO FOUNDATIONS OF GENETIC ALGORITHMS XI, P69

[5]

Feldman V, 2008, ACM S THEORY COMPUT, P619

[6]

Gathercole C., 1996, Genetic Programming. Proceedings of the First Annual Conference 1996, P291

[7]

Goldberg D. E., 1998, Genetic Programming. First European Workshop, EuroGP'98. Proceedings, P16, DOI 10.1007/BFb0055925

[8] LIMIT THEOREMS IN AN OCCUPANCY PROBLEM [J].

IVCHENKO, GI .

THEORY OF PROBILITY AND ITS APPLICATIONS,USSR, 1971, 16 (02) :293-&

[9] The Max Problem Revisited: The Importance of Mutation in Genetic Programming [J].

Koetzing, Timo ;

Sutton, Andrew M. ;

Neumann, Frank ;

O'Reilly, Una-May .

PROCEEDINGS OF THE FOURTEENTH INTERNATIONAL CONFERENCE ON GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE, 2012, :1333-1340

[10]

Kötzing T, 2011, GECCO-2011: PROCEEDINGS OF THE 13TH ANNUAL GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE, P2091

← 1 2 →