Convergence of a modified algorithm of fast probabilistic modeling
- PDF / 86,370 Bytes
- 6 Pages / 595 x 842 pts (A4) Page_size
- 15 Downloads / 245 Views
CONVERGENCE OF A MODIFIED ALGORITHM OF FAST PROBABILISTIC MODELING
UDC 519.854
D. A. Gobov
The convergence of fast probabilistic modeling algorithms (G-algorithms) is analyzed. A G-algorithm is modified based on a new probabilistic approach, used to reject points in the neighborhood of the current solution. A theoretically justified estimate of the rate of convergence, independent of the initial approximation, is obtained for this modification. A computational experiment is conducted to compare the performance of the modified G-algorithm with that of the classical one. Keywords: combinatorial optimization, convergence, probabilistic modeling algorithm, G-algorithm. INTRODUCTION Combinatorial optimization problems frequently appear in practice (for example, in prediction, scheduling, resource management, traffic control, budgeting, network routing, and many other problems). Probabilistic mechanisms are promising for the creation of discrete optimization methods. Let us consider stochastic local search methods such as simulated annealing [1], one of the most famous examples of such algorithms. Along with performance evaluation of this method via computational experiments, theoretical analysis of its convergence is of importance. For example, the papers [2–4] present sufficient conditions for a sequence of temperatures, such that the sequence of solutions obtained at each iteration of annealing algorithms converges in probability to the optimal vector. The papers [5, 6] propose temperature schedules that satisfy the necessary and sufficient conditions for the convergence in probability to a set of global solutions. Rajasekaran [7] proposes another approach to analyze the convergence of the simulated annealing algorithm, which guarantees the determination of the global solution. The scheme of fast probabilistic modeling algorithms (G-algorithms) is similar to that of the simulated annealing method (see [8] and the references therein). Turchin [9] analyzes the convergence of the classical G-algorithm. The present paper proposes a new modification of the fast probabilistic modeling algorithm and analyzes its convergence. 1. MODIFIED FAST PROBABILISTIC MODELING ALGORITHM AND ITS CONVERGENCE A combinatorial optimization problem is characterized by three main aspects [10]: • the search space W, consisting of a finite number of points (occasionally countable); • the objective function f ( x ) defined on the search space W ; • the constraints for search space. More formally, it consists in the following: find a point x * ÎW such that x * = arg min x ÎW f ( x ) . Without loss of generality, we assume that f ( x ) > 0, and W is a finite metric space with metric d. Definition 1. By the neighborhood of a point x ÎW of arbitrary radius r > 0 is called a set N ( x ) = { y Î W , d ( x, y ) £ r}, where d ( x, y ) is a metric defined on the space W.
V. M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, Kyiv, Ukraine, [email protected]. Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 173–179, Ja
Data Loading...
