BINARY OPTIMIZATION: A RELATION BETWEEN THE DEPTH OF A LOCAL MINIMUM AND THE PROBABILITY OF ITS DETECTION

B. V. Kryzhanovsky, V. M. Kryzhanovsky, A. L. Mikaelian

2007

Abstract

The standard method in optimization problems consists in a random search of the global minimum: a neuron network relaxes in the nearest local minimum from some randomly chosen initial configuration. This procedure is to be repeated many times in order to find as deep an energy minimum as possible. However the question about the reasonable number of such random starts and whether the result of the search can be treated as successful remains always open. In this paper by analyzing the generalized Hopfield model we obtain expressions describing the relationship between the depth of a local minimum and the size of the basin of attraction. Based on this, we present the probability of finding a local minimum as a function of the depth of the minimum. Such a relation can be used in optimization applications: it allows one, basing on a series of already found minima, to estimate the probability of finding a deeper minimum, and to decide in favor of or against further running the program. The theory is in a good agreement with experimental results.

Paper Citation

in Harvard Style

V. Kryzhanovsky B., M. Kryzhanovsky V. and L. Mikaelian A. (2007). BINARY OPTIMIZATION: A RELATION BETWEEN THE DEPTH OF A LOCAL MINIMUM AND THE PROBABILITY OF ITS DETECTION . In Proceedings of the Fourth International Conference on Informatics in Control, Automation and Robotics - Volume 1: ICINCO, ISBN 978-972-8865-82-5, pages 5-10. DOI: 10.5220/0001621000050010

in Bibtex Style

@conference{icinco07,
author={B. V. Kryzhanovsky and V. M. Kryzhanovsky and A. L. Mikaelian},
title={BINARY OPTIMIZATION: A RELATION BETWEEN THE DEPTH OF A LOCAL MINIMUM AND THE PROBABILITY OF ITS DETECTION},
booktitle={Proceedings of the Fourth International Conference on Informatics in Control, Automation and Robotics - Volume 1: ICINCO,},
year={2007},
pages={5-10},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0001621000050010},
isbn={978-972-8865-82-5},
}

in EndNote Style

TY - CONF
JO - Proceedings of the Fourth International Conference on Informatics in Control, Automation and Robotics - Volume 1: ICINCO,
TI - BINARY OPTIMIZATION: A RELATION BETWEEN THE DEPTH OF A LOCAL MINIMUM AND THE PROBABILITY OF ITS DETECTION
SN - 978-972-8865-82-5
AU - V. Kryzhanovsky B.
AU - M. Kryzhanovsky V.
AU - L. Mikaelian A.
PY - 2007
SP - 5
EP - 10
DO - 10.5220/0001621000050010