Application Of Spin Glass Theory In Combinatorial Optimization Probems And Neural Networks

Mean-field theory of Spin Glasses was developed in the 1970s.The earlier mean-fieldtheory used Replica method to average over Quenched Disorder in the spin glass models.For some infinitely-connected spin glass models like Sherrington-Kirkpartrick model,ReplicaSymmetry Broken theory of Parisi can give good description of the system.However,replicamethod can not give satisfied description to finite connectivity models like Viana-Bray model.Recently,cavity method,together with population dynamics simulation were developed tostudy properties of finite-connectivity spin glasses.And soon,physicists find many applicationof finite-connectivity spin glass theory in applied mathematics,computer science,information theory and biological systems.Cavity method and population dynamics wereused to study mean-field properties of combinatorial optimization problems,coding problemsand some hard problems in biological systems.In this thesis,we follow this line to use cavitymethod studying some combinatorial optimization problems (vertex cover problem andhiding K-SAT problem) and neural networks(finite connectivity Hopfield model).The first chapter of this these briefly introduces mean-field theory of finite-connectivityspin glasses and some concepts of combinatorial optimization problems and neural networksThe second chapter and third chapter study dynamics and equilibrium properties of attractorneural networks.In the part of dynamics,we study loop series expansion of parallel Glauberdynamics,and apply the theory to the parallel dynamics of some attractor neural networkson the complex topology (which contain many loops).In the part of equilibrium,we studyfinite-connectivity Hopfield model and its phase diagram in the Temperature-storage ratioplane.We also study stability of replica symmetry solution(can be thought as AT line offinite-connectivity version).The fourth chapter we studied statistical mechanics of finitetemperaturevertex cover problem,especially the stability of replica symmetry and first-stepreplica symmetry broken solution.In fifth chapter,we study K-SAT problem with hidingsolutions(planted solution).We study three classes of hiding problem:uniform planting,whose configuration space is just a ferromagnetic.Biased planting,whose configurationdepends on the degree of bias.Unbiased planting,whose configuration space is a spin-glasspart plus a ferromagnetic state.The major finding is that in the biased planting problem,ferromagnetic state do not change neither the original spin-glass state nor the easy-hardpattern.In another words,the ferromagnetic state is transparent planted.