Local Search Efficiency when Optimizing Unimodal Pseudoboolean Functions

Article type: Research Article

Authors: Antamoshkin, Alexander | Semenkin, Eugene

Affiliations: Siberian Aerospace Academy, P.O.Box 486, Krasnoyarsk, Russia-660014. E-mail: ant@iea.krasnoyarsk.su

Abstract: This work is a continuation of our previous papers devoted to exploration of the regular search procedures efficiency in binary search spaces. Here we formulate the problem in a rather general form as a problem of optimization of an unimodal pseudoboolean function given implicitly and obtain analitical estimates of the expected time of a minimum point search for procedures of direct local search. These estimates are polinomial for the case of weakly nonmonotone functions and exponential for the general case of arbitrary unimodal functions. We hope that the proposed result will be usefull first of all for practical applications.

Keywords: unimodal pseudoboolean functions, local search techniques, convergence analysis

DOI: 10.3233/INF-1998-9302

Journal: Informatica, vol. 9, no. 3, pp. 279-296, 1998