Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
The Mix-Matrix Method in the Problem of Binary Quadratic Optimization
verfasst von : Iakov Karandashev, Boris Kryzhanovsky
Erschienen in: Artificial Neural Networks and Machine Learning – ICANN 2012
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In the paper we deal with the NP-complete problem of minimization a quadratic form of
N
binary variables. The minimization approach based on extensive random search is considered. To increase the efficiency of the random-search algorithm, we 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
T
2
. We demonstrate that such a substitution 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. At the same time the probability of finding close to optimal solutions increases abruptly (by 2-3 orders of magnitude in case of a 2D Ising model of size 12
×
12 and in case of dense instances of size 500).