Application of statistical mechanics to combinatorial optimization problems: The chromatic number problem andq-partitioning of a graph

Methods of statistical mechanics are applied to two important NP-complete combinatorial optimization problems. The first is the chromatic number problem, which seeks the minimal number of colors necessary to color a graph such that no two sites connected by an edge have the same color. The second is partitioning of a graph intoq equal subgraphs so as to minimize intersubgraph connections. Both models are mapped into a frustrated Potts model, which is related to theq- state Potts spin glass. For the first problem, we obtain very good agreement with numerical simulations and theoretical bounds using the annealed approximation. The quenched model is also discussed. For the second problem we obtain analytic and numerical results by evaluating the groundstate energy of theq=3 and 4 Potts spin glass using Parisi's replica symmetry breaking. We also perform some numerical simulations to test the theoretical result and obtain very good agreement.     

The traveling salesman problem and its analogy with two-dimensional spin glasses

The low-temperature regime of the Euclidean traveling salesman problem is studied numerically. The specific heat behavior is analyzed in terms of the number of cities and compared with that of spin-glasses. A properly defined order parameter shows the existence of freezing effects at low temperature. The Euclidean TSP behaves as a spin glass in two dimensions.     

Quantum elastic net and the traveling salesman problem

Theory of computer calculations strongly depends on the nature of elements the computer is made of. Quantum interference allows to formulate the Shor factorization algorithm turned out to be more effective than any one written for classical computers. Similarly, quantum wave packet reduction allows to devise the Grover search algorithm which outperforms any classical one. In the present paper we argue that the quantum incoherent tunneling can be used for elaboration of new algorithms able to solve some NP-hard problems, such as the Traveling Salesman Problem, considered to be intractable in the classical theory of computer computations.     

On the inverse problem in statistical mechanics

For quantum spin systems it is known that for a suitable space of potentials the equilibrium states areW*-dense in the set of all translation invariant states. The problem discussed in this paper is how to recognize such equilibrium states and how to find the corresponding potential. A necessary and sufficient condition for a state to be an equilibrium state for some potential is given in Sect. 3.     

On the inverse problem in statistical mechanics

We review briefly the status of some inverse problems in classical equilibrium statistical mechanics.This paper is dedicated to Professor P. G. Bergmann on the occasion of his sixtieth birthday.Supported by NSF grant No. GP42614X.     

Optimization with extremal dynamics for the traveling salesman problem

By mapping the optimization problems to physical systems, the paper presents a general-purpose stochastic optimization method with extremal dynamics. It is built up with the traveling salesman problem (TSP) being a typical NP-complete problem. As self-organized critical processes of extremal dynamics, the optimization dynamics successively updates the states of those cities with high energy. Consequently, a near-optimal solution can be quickly obtained through the optimization processes combining the two phases of greedy searching and fluctuated explorations (ergodic walk near the phase transition). The computational results demonstrate that the proposed optimization method may provide much better performance than other optimization techniques developed from statistical physics, such as simulated annealing (SA). Since the proposed fundamental solution is based on the principles and micromechanisms of computational systems, it can provide systematic viewpoints and effective computational methods on a wide spectrum of combinatorial and physical optimization problems.     

Improved extremal optimization for the asymmetric traveling salesman problem

This paper presents an improved extremal optimization (IEO) algorithm for solving the asymmetric traveling salesman problem (ATSP). At each update step, the IEO algorithm proceeds through two main steps: extremal dynamics and cooperative optimization. As an improvement of extremal optimization (EO), the IEO provides a general combinatorial optimization framework by emphasizing the step of cooperative optimization. In the paper, an effective cooperative optimization strategy with combination of greedy search and random walk is designed in terms of the microscopic characteristics of the ATSP solutions. Simulation results on a set of benchmark ATSP instances show that the proposed IEO algorithm provides satisfactory performance on computational effectiveness and efficiency.     

Use of local search in the metric traveling salesman problem

The traveling salesman problem (TSP) for points in the Euclidean plane is considered. For several approximation algorithms, such as the tree algorithm and algorithms based on matching, a local search method using permutation in groups of closely placed points in a route is applied. Some modifications of these algorithms are presented. The effect of applying the local search method for partially constructed routes is examined for the modifications. In this paper, experimental results from statistical modeling with randomly equidistributed points are discussed. It allows one to conclude on the advantage of one or the other algorithms. Tomsk State University. Translated from Izvestiya Vysshikh Uchebnykh Zavedenii, Fizika, No. 3, pp. 129–134, March, 1999     

N-city traveling salesman problem: Optimization by simulated annealings

The problem of finding the shortest closed path connectingN randomly chosen points is one of the classicNp-complete problems. We show that the length of tour depends logarithmically on the cooling rateQ in a simulated Monte Carlo anneal. We speculate that this is a general property of allNp-complete problems.     

A quantitative analysis of the simulated annealing algorithm: A case study for the traveling salesman problem

A quantitative study is presented of the typical behavior of the simulated annealing algorithm based on a cooling schedule presented previously by the authors. The study is based on the analysis of numerical results obtained by systematically applying the algorithm to a 100-city traveling salesman problem. The expectation and the variance of the cost are analyzed as a function of the control parameter of the cooling schedule. A semiempirical average-case performance analysis is presented from which estimates are obtained on the expectation of the average final result obtained by the simulated annealing algorithm as a function of the distance parameter, which determines the decrement of the control parameter.     

The statistical mechanics of turbo codes

The “turbo codes”, recently proposed by Berrou et al. [1] are written as a disordered spin Hamiltonian. It is shown that there exists a threshold such that for signal to noise ratios the error probability per bit vanishes in the thermodynamic limit, i.e. the limit of infinitely long sequences. The value of the threshold has been computed for two particular turbo codes. It is found that it depends on the code. These results are compared with numerical simulations. Received 14 March 2000 and Received in final form 17 July 2000     

关于统计力学的基本原理

文章简要讨论有关统计力学基本原理的几个问题,包括正则系综理论、系综分布函数的支集、与热力学的对应、不可逆性及分布函数的时间演化。     

On the statistical mechanics of rigid particles

In this paper, generalized functions are used in the configuration partition function for fluids composed of arbitrarily shaped, rigid particles. This leads to new expressions for the basic statistical thermodynamic functions and some equations that may be useful in developing approximate theories, such as the scaled particle theory, for such fluids. The results are applicable to a large class of arbitrarily shaped, rigid particles and reduce exactly to the usual hard-sphere expressions.     

Polymers on disordered trees,spin glasses,and traveling waves

We show that the problem of a directed polymer on a tree with disorder can be reduced to the study of nonlinear equations of reaction-diffusion type. These equations admit traveling wave solutions that move at all possible speeds above a certain minimal speed. The speed of the wavefront is the free energy of the polymer problem and the minimal speed corresponds to a phase transition to a glassy phase similar to the spin-glass phase. Several properties of the polymer problem can be extracted from the correspondence with the traveling wave: probability distribution of the free energy, overlaps, etc.     

Spin glass,the travelling salesman problem,neural networks and all that

This paper presents an overview of diverse topics that are seemingly different but interrelated, with strong connections to statistical mechanics on the one hand and spin glass physics on the other. Written primarily for an inter-disciplinary audience, we start with a brief recapitulation of the relevant aspects of statistical mechanics, particularly those needed for understanding the recently-popular simulated-annealing technique used in optimization studies. Then follows a survey of the spin glass problem, with particular attention to the consequences of quenched randomness. The travelling-salesman problem is considered next, as also the impact made on it by the spin glass problem. Several examples are then presented of optimization studies wherein the simulated-annealing concept has been profitably used. Attention is also drawn in this context to the lessons provided by the spin glass problem. Finally, a brief survey of neural networks is made, essentially from a physicist’s point of view. The different learning schemes proposed are discussed, and the relevance of spin models and their statistical mechanics is also discussed.     

On the statistical mechanics of constrained biophysical systems

A well-known class of biophysical models, first introduced by Kerner, is shown to admit a convenient Hamiltonian formulation in which motion through the phase space of system variables involves explicit constraints. To treat the macroscopic properties of such models, we develop an ensemble theory of systems subjected to phase space constraints. For such systems we obtain a generalized Hamiltonian statistical mechanics which preserves much of the structure and efficacy of the corresponding physical theory. In a first application of the method, we recover Kerner's original biological ensemble as a special case involving information optimality and conservative biosystems.Funding for this project was provided through the generosity of the National Research Council of Canada. The work reported here was carried out while CJL was a graduate scholar of the National Research Council.     

统计物理的微观动力学基础

统计的基本出发点是研究系统具有的随机性,不同系统在不同情形下的宏观热力学性质起源于系统内部随机性的差异,通过对宏观热力学系统的微观非线性动力学进行研究探索，我们可以进一步更为深入地理解物态方程、相变等诸多的宏观热力学现象。本文通过哈密顿系统的非线性动力学研究，以及遍历性理论的动力学随机性研究对此问题进行了分析，研究表明，动力学系统的全局性混沌是系统统计成立的根本要素，系统的无限大自由度（热力学极限）已不是决定性的因素，人们可以在此基础上建立少自由度系统的统计力学及热力学。