  In the present paper we describe new heuristic technique, which can be
applied to the optimization of pseudo-Boolean functions including Black-Box
functions. This technique is based on a simple procedure which consists in
transition from the optimization problem over Boolean hypercube to the
optimization problem of auxiliary function in a specially constructed metric
space. It is shown that there is a natural connection between the points of the
original Boolean hypercube and points from the new metric space. For the
Boolean hypercube with fixed dimension it is possible to construct a number of
such metric spaces. The proposed technique can be considered as a special case
of Variable Neighborhood Search, which is focused on pseudo-Boolean
optimization. Preliminary computational results show high efficiency of the
proposed technique on some reasonably hard problems. Also it is shown that the
described technique in combination with the well-known (1+1)-Evolutionary
Algorithm allows to decrease the upper bound on the runtime of this algorithm
for arbitrary pseudo-Boolean functions.
