Improved Running Time Analysis of the (1+1)-ES on the Sphere Function

Jiang, Wu1; Qian, Chao1; Tang, Ke2

10.1007/978-3-319-95930-6_74

2018

16113349

1611-3349

INTELLIGENT COMPUTING THEORIES AND APPLICATION, PT I

10954

729-739

Wuhan, China

GEWERBESTRASSE 11, CHAM, CH-6330, SWITZERLAND

SPRINGER INTERNATIONAL PUBLISHING AG

During the last two decades, much progress has been achieved on the running time analysis (one essential theoretical aspect) of evolutionary algorithms (EAs). However, most of them focused on discrete optimization, and the theoretical understanding is largely insufficient for continuous optimization. The few studies on evolutionary continuous optimization mainly analyzed the running time of the (1+1)-ES with Gaussian and uniform mutation operators solving the sphere function, the known bounds of which are, however, quite loose compared with the empirical observations. In this paper, we significantly improve their lower bound, i.e., from Omega(n) to Omega(e(cn)). Then, we study the effectiveness of 1/5-rule, a widely used self-adaptive strategy, for continuous EAs using uniform mutation operator for the first time. We prove that for the (1+ 1)-ES with uniform mutation operator solving the sphere function, using 1/5-rule can reduce the running time from exponential to polynomial.

Running time analysis Continuous optimization Evolution strategies

其他

英语

CPCI-S ; EI

Computer Science

Computer Science, Artificial Intelligence ; Computer Science, Theory & Methods

WOS:000484465800074

20183405735637

Computation theory ; Evolutionary algorithms ; Intelligent computing ; Spheres

Computer Theory, Includes Formal Logic, Automata Theory, Switching Theory, Programming Theory:721.1 ; Artificial Intelligence:723.4 ; Optimization Techniques:921.5

Web of Science

1.Univ Sci & Technol China, Anhui Prov Key Lab Big Data Anal & Applicat, Hefei 230027, Anhui, Peoples R China
2.Southern Univ Sci & Technol, Shenzhen Key Lab Computat Intelligence, Shenzhen 518055, Peoples R China

Jiang, Wu,Qian, Chao,Tang, Ke. Improved Running Time Analysis of the (1+1)-ES on the Sphere Function[C]. GEWERBESTRASSE 11, CHAM, CH-6330, SWITZERLAND:SPRINGER INTERNATIONAL PUBLISHING AG,2018:729-739.