论文部分内容阅读
自旋玻璃理论从上世纪七八十年代开始建立起来的。最早的平均场理论使用副本方法(Replica Method)处理自旋玻璃模型中随机变量(Quenched Disorder)的平均。对于全连接的自旋玻璃模型(比如Sherrington-Kirkpartrick模型),Parisi的副本对称破缺理论可以给出很好的理论理解,但有限连接的自旋玻璃模型(比如Viana-Bray模型)却不容易用副本方法研究。近年以来,由于空腔方法(Cavity method)的发展,特别是种群动力学算法的引入,使得有限连接的自旋玻璃可以被很好的研究。然后有限连接的自旋玻璃的研究方法被迅速应用到到组合优化问题,信息编码问题和神经网络等问题中。本文是沿着这个方向,将有限连接自旋玻璃理论,特别是空腔方法应用到一些组合优化问题,比如顶点覆盖问题和隐藏解的KSAT问题,和神经网络中,比如作为联想记忆的Hopfield模型。本文的第一章简单介绍了有限连接自旋玻璃的平均场理论和我们要研究的组合优化问题和神经网络。第二章和第三章介绍吸引子神经网络的一些动力学和静态的研究。在动态的方面我们介绍如何对并行的Glauber动力学进行圈展开,从而使得一些复杂拓扑上的神经网络模型的并行动力学可以被理论预测。在静态方面我们用空腔方法和种群动力学研究了有限连接的Hopfield模型,特别是模型在温度-存储绿率平面上的相图以及副本对称性的不稳定边界(可以认为是有限连接Hopfield模型的AT线)。第四章研究了有限温度顶点覆盖问题的平均场理论,分析了副本对称解和一阶副本对称解的稳定性。第五张我们介绍隐藏解KSAT问题的平均场理论分析。我们研究了三类隐藏解KSAT问题,一种是均匀隐藏解问题(uniform planting),第二种是有偏向的隐藏解问题(biased planting),第三种是无偏向性的隐藏解问题(unbiased planting)。主要结论是对于3SAT和4SAT问题,均匀隐藏解问题是简单的问题,系统内只有一个铁磁态。有偏向的隐藏解问题中偏向性的大小控制着解空间的结构。对于无偏向性的隐藏解问题,隐藏的解簇不影响原有随机KSAT问题的解空间结构,也不影响原有随机问题的难易程度。在论文的附录中我们附了顶点覆盖问题的种群动力学的c++代码,为的是给没有种群动力学经验,但想在别的问题或者领域中应用种群动力学的同学参考。