自旋玻璃理論在組合優(yōu)化和神經(jīng)網(wǎng)絡(luò)中的應(yīng)用.pdf

1、自旋玻璃理論從上世紀七八十年代開始建立起來的。最早的平均場理論使用副本方法(Replica Method)處理自旋玻璃模型中隨機變量(Quenched Disorder)的平均。對于傘連接的自旋玻璃模型(比如Sherrington-Kirkpartrick模型)，Parisi的副本對稱破缺理論可以給出很好的理論理解，但有限連接的自旋玻璃模型(比如Viana-Bray模型)卻不容易用副本方法研究。近年以來，由于空腔方法(Cavity me

2、thod)的發(fā)展，特別是種群動力學算法的引入，使得有限連接的自旋玻璃可以被很好的研究。然后有限連接的自旋玻璃的研究方法被迅速應(yīng)用到到組合優(yōu)化問題，信息編碼問題和神經(jīng)網(wǎng)絡(luò)等問題中。本文是沿著這個方向，將有限連接自旋玻璃理論，特別是空腔方法應(yīng)用到一些組合優(yōu)化問題，比如頂點覆蓋問題和隱藏解的KSAT問題，和神經(jīng)網(wǎng)絡(luò)中，比如作為聯(lián)想記憶的Hopfield模型。本文的第一章簡單介紹了有限連接自旋玻璃的平均場理論和我們要研究的組合優(yōu)化問題和神經(jīng)網(wǎng)絡(luò)

3、。第二章和第三章介紹吸引子神經(jīng)網(wǎng)絡(luò)的一些動力學和靜態(tài)的研究。在動態(tài)的方面我們介紹如何對并行的Glauber動力學進行圈展開，從而使得一些復雜拓撲上的神經(jīng)網(wǎng)絡(luò)模型的并行動力學可以被理論預(yù)測。在靜態(tài)方面我們用空腔方法和種群動力學研究了有限連接的Hopfield模型，特別是模型在溫度-存儲綠率平面上的相圖以及副本對稱性的不穩(wěn)定邊界(可以認為是有限連接Hopfield模型的AT線)。第四章研究了有限溫度項點覆蓋問題的平均場理論，分析了副本對稱解

4、和一階副本對稱解的穩(wěn)定性。第五張我們介紹隱藏解KSAT問題的平均場理論分析。我們研究了三類隱藏解KSAT問題，一種是均勻隱藏解問題(uniform planting)，第二種是有偏向的隱藏解問題(biased planting)，第三種是無偏向性的隱藏解問題(unbiased planting)。主要結(jié)論是對于3SAT和4SAT問題，均勻隱藏解問題是簡單的問題，系統(tǒng)內(nèi)只有一個鐵磁態(tài)。有偏向的隱藏解問題中偏向性的大小控制著解空間的結(jié)構(gòu)。對