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

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

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

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

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