Analysis of noisy evolutionary optimization when sampling fails

Qian，Chao1; Bian，Chao1; Yu，Yang2; Tang，Ke3; Yao，Xin3

2018-07-02

10.1145/3205455.3205643

ALGORITHMICA   影响因子和分区

0178-4617

1432-0541

In noisy evolutionary optimization, sampling is a common strategy to deal with noise, which evaluates the fitness of a solution multiple times (called sample size) independently and then uses the average to approximate the true fitness. Previous studies mainly focused on the empirical design of efficient sampling strategies, and the few theoretical analyses mainly proved the effectiveness of sampling with a fixed sample size in some situations. There are many fundamental theoretical issues to be addressed. In this paper, we first investigate the effect of sample size. By analyzing the (1+1)-EA on noisy LeadingOnes, we show that as the sample size increases, the running time can reduce from exponential to polynomial, but then return to exponential. This discloses that a proper sample size is crucial in practice. Then, we investigate what other strategies can work when sampling with any fixed sample size fails. By two illustrative examples, we prove that using parent populations can be better, and if using parent populations is also ineffective, adaptive sampling (i.e., sampling with an adaptive sample size) can work.

Computational complexity Evolutionary algorithms Noisy optimization Running time analysis Sampling

EI ; CPCI-S ; SCI

英语

其他

European Society of Surgical Oncology[2016QNRC001] ; Ministry of Science and Technology[2017YFC0804003] ; National Natural Science Foundation of China[61603367] ; Royal Society[NA150123] ; Innovation and Technology Commission[ZDSYS201703031748284]

Computer Science ; Mathematics

Computer Science, Software Engineering ; Mathematics, Applied

WOS:000631041800003

Association for Computing Machinery, Inc

20183105630298

Computational complexity ; Evolutionary algorithms ; Optimization

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

ENGINEERING

2-s2.0-85050612434

Scopus

1.University of Science and Technology of China, ,Hefei,China
2.Nanjing University, ,Nanjing,China
3.Shenzhen Key Laboratory of Computational Intelligence, Southern University of Science and Technology, ,Shenzhen,China

Qian，Chao,Bian，Chao,Yu，Yang,et al. Analysis of noisy evolutionary optimization when sampling fails[J]. ALGORITHMICA,2018,83(4):1507-1514.

Qian，Chao,Bian，Chao,Yu，Yang,Tang，Ke,&Yao，Xin.(2018).Analysis of noisy evolutionary optimization when sampling fails.ALGORITHMICA,83(4),1507-1514.

Qian，Chao,et al."Analysis of noisy evolutionary optimization when sampling fails".ALGORITHMICA 83.4(2018):1507-1514.