Memory-restricted black-box complexity of One Max

被引：6

作者：

Doerr, Benjamin ^{[1
]}

Winzen, Carola ^{[1
]}

机构：

[1] Max Planck Inst Informat, D-66123 Saarbrucken, Germany

来源：

INFORMATION PROCESSING LETTERS | 2012年 / 112卷 / 1-2期

关键词：

Algorithms; Black-box complexity; Query complexity; Bounded memory;

D O I：

10.1016/j.ipl.2011.10.004

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We show that the black-box complexity with memory restriction one of the n-dimensional ONEMAX function class is at most 2n. This disproves the Theta(n logn) conjecture of Droste, Jansen, and Wegener (Theory Computing Systems 39 (2006) 525-544). (C) 2011 Elsevier B.V. All rights reserved.

引用

页码：32 / 34

页数：3

共 50 条

[31] Unbiased Black-Box Complexities of Jump Functions [J].

Doerr, Benjamin ;

Doerr, Carola ;

Koetzing, Timo .

EVOLUTIONARY COMPUTATION, 2015, 23 (04) :641-670

[32] Too Fast Unbiased Black-Box Algorithms [J].

Doerr, Benjamin ;

Koetzing, Timo ;

Winzen, Carola .

GECCO-2011: PROCEEDINGS OF THE 13TH ANNUAL GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE, 2011, :2043-2050

[33] Distributed Evolution Strategies for Black-Box Stochastic Optimization [J].

He, Xiaoyu ;

Zheng, Zibin ;

Chen, Chuan ;

Zhou, Yuren ;

Luo, Chuan ;

Lin, Qingwei .

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2022, 33 (12) :3718-3731

[34] An evolutionary approach to black-box optimization on matrix manifolds? [J].

He, Xiaoyu ;

Zhou, Yuren ;

Chen, Zefeng ;

Jiang, Siyu .

APPLIED SOFT COMPUTING, 2020, 97

[35] Collective Learning of Low-Memory Matrix Adaptation for Large-Scale Black-Box Optimization [J].

Duan, Qiqi ;

Zhou, Guochen ;

Shao, Chang ;

Yang, Yijun ;

Shi, Yuhui .

PARALLEL PROBLEM SOLVING FROM NATURE - PPSN XVII, PPSN 2022, PT II, 2022, 13399 :281-294

[36] White-Box or Black-Box Decision Tree Algorithms: Which to Use in Education? [J].

Delibasic, Boris ;

Vukicevic, Milan ;

Jovanovic, Milos ;

Suknovic, Milija .

IEEE TRANSACTIONS ON EDUCATION, 2013, 56 (03) :287-291

[37] A taxonomy of constraints in black-box simulation-based optimization [J].

Le Digabel, Sebastien ;

Wild, Stefan M. .

OPTIMIZATION AND ENGINEERING, 2024, 25 (02) :605-+

[38] Faster Black-Box Algorithms Through Higher Arity Operators [J].

Doerr, Benjamin ;

Johannsen, Daniel ;

Koetzing, Timo ;

Lehre, Per Kristian ;

Wagner, Markus ;

Winzen, Carola .

FOGA 11: PROCEEDINGS OF THE 2011 ACM/SIGEVO FOUNDATIONS OF GENETIC ALGORITHMS XI, 2011, :163-171

[39] Marginalized Stochastic Natural Gradients for Black-Box Variational Inference [J].

Ji, Geng ;

Sujono, Debora ;

Sudderth, Erik B. .

INTERNATIONAL CONFERENCE ON MACHINE LEARNING, VOL 139, 2021, 139

[40] Lower Bounds on Black-Box Reductions of Hitting to Density Estimation [J].

Tell, Roei .

35TH SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2018), 2018, 96

← 1 2 3 4 5 →