Home // ICCGI 2012, The Seventh International Multi-Conference on Computing in the Global Information Technology // View article

Mix-matrix Method in Problem of Discrete Optimization

Authors:
Iakov Karandashev
Boris Kryzhanovsky

Keywords: optimization; binary optimization; combinatorial optimization; area of attraction; local search; random search; energy landscape transformation; mix-matrix

Abstract:
The problem of a quadratic functional minimization in the configuration space of N binary states is considered. In order to increase the efficiency of the random-search algorithm, we suggest to vary the attraction area of the deepest minima of the functional by changing the matrix T it is based on. The new matrix M, called mix-matrix, is a mixture of T and T2. We demonstrate that this brings about changes of the energy surface: deep minima displace very slightly in the space (the Hemming distance of the shift is of about 0.01*N ), they become still deeper and their attraction areas grow significantly. The experiment shows that use of the approach results in a considerable displacement of the spectrum of sought-for minima to the area of greater depths, while the probability of finding the global minimum increases abruptly (by a factor of 10^3 in the case of a two-dimensional Ising model)

Pages: 218 to 224

Copyright: Copyright (c) IARIA, 2012

Publication date: June 24, 2012

Published in: conference

ISSN: 2308-4529

ISBN: 978-1-61208-202-8

Location: Venice, Italy

Dates: from June 24, 2012 to June 29, 2012