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 条

[41] Optimistic tree search strategies for black-box combinatorial optimization [J].

Malherbe, Cedric ;

Grosnit, Antoine ;

Tutunov, Rasul ;

Wang, Jun ;

Bou-Ammar, Haitham .

ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 35 (NEURIPS 2022), 2022,

[42] Black-Box Data-efficient Policy Search for Robotics [J].

Chatzilygeroudis, Konstantinos ;

Rama, Roberto ;

Kaushik, Rituraj ;

Goepp, Dorian ;

Vassiliades, Vassilis ;

Mouret, Jean-Baptiste .

2017 IEEE/RSJ INTERNATIONAL CONFERENCE ON INTELLIGENT ROBOTS AND SYSTEMS (IROS), 2017, :51-58

[43] Optimal Parameter Choices via Precise Black-Box Analysis [J].

Doerr, Benjamin ;

Doerr, Carola ;

Yang, Jing .

GECCO'16: PROCEEDINGS OF THE 2016 GENETIC AND EVOLUTIONARY COMPUTATION CONFERENCE, 2016, :1123-1130

[44] On Finding Multiplicities of Characteristic Polynomial Factors of Black-box Matrices [J].

Dumas, Jean-Guillaume ;

Pernet, Clement ;

Saunders, B. David .

ISSAC2009: PROCEEDINGS OF THE 2009 INTERNATIONAL SYMPOSIUM ON SYMBOLIC AND ALGEBRAIC COMPUTATION, 2009, :135-142

[45] On the impact of objective function transformations on evolutionary and black-box algorithms [J].

Storch, Tobias .

GECCO 2005: Genetic and Evolutionary Computation Conference, Vols 1 and 2, 2005, :833-840

[46] Large-scale Expensive Black-Box Function Optimization [J].

Rashid, Kashif ;

Bailey, William ;

Couet, Benoit .

NUMERICAL ANALYSIS AND APPLIED MATHEMATICS (ICNAAM 2012), VOLS A AND B, 2012, 1479 :1143-1146

[47] Interpreting Black-Box Models: A Review on Explainable Artificial Intelligence [J].

Hassija, Vikas ;

Chamola, Vinay ;

Mahapatra, Atmesh ;

Singal, Abhinandan ;

Goel, Divyansh ;

Huang, Kaizhu ;

Scardapane, Simone ;

Spinelli, Indro ;

Mahmud, Mufti ;

Hussain, Amir .

COGNITIVE COMPUTATION, 2024, 16 (01) :45-74

[48] Optimal parameter choices via precise black-box analysis [J].

Doerr, Benjamin ;

Doerr, Carola ;

Yang, Jing .

THEORETICAL COMPUTER SCIENCE, 2020, 801 :1-34

[49] Effective Sampling, Modeling and Optimization of Constrained Black-box Problems [J].

Bajaj, Ishan ;

Hasan, M. M. Faruque .

26TH EUROPEAN SYMPOSIUM ON COMPUTER AIDED PROCESS ENGINEERING (ESCAPE), PT A, 2016, 38A :553-558

[50] Black-box optimization for the design of a jet plate for impingement cooling [J].

Cocchi, Lorenzo ;

Marini, Filippo ;

Porcelli, Margherita ;

Riccietti, Elisa .

OPTIMIZATION AND ENGINEERING, 2025,

← 1 2 3 4 5 →