統(tǒng)計(jì)物理學(xué)習(xí)講義 - home for complex systems

1、統(tǒng)計(jì)物理學(xué)習(xí)講義,中科院數(shù)學(xué)院復(fù)雜系統(tǒng)研究中心復(fù)雜系統(tǒng)學(xué)習(xí)班 (CSSGBJ)韓 靖2003年10月27日,統(tǒng)計(jì)物理、自旋玻璃和復(fù)雜系統(tǒng),統(tǒng)計(jì)物理做什么？自旋玻璃(Spin Glasses)是什么？它們?cè)趶?fù)雜系統(tǒng)研究中有何應(yīng)用？它們的局限性？探討：對(duì)我們的研究有何啟發(fā)？,學(xué)習(xí)提綱和計(jì)劃 (歡迎補(bǔ)充修改),基本概念介紹Entropy, Boltzmann分布(partition function)Example: K-

2、SAT問(wèn)題的相變Dynamics and Landscapes各態(tài)歷盡, landscapes, Monte Carlo SimulationExample: Simulated Annealing(模擬退火)Meanfield, Replica Symmetry, Cavity MethodsMeanfield 用于網(wǎng)絡(luò)動(dòng)力學(xué)的例子Replica Symmetry 用于組合問(wèn)題的例子Cavity Methods: Sur

3、vey Propagation Critical Phenomena & Power-law相變SOC, HOT/COLD理論,,統(tǒng)計(jì)物理,Statistical physics is about systems composed of many parts. 集體行為 組合數(shù)學(xué)和概率理論Traditional examples:氣體、液體、固體 - 原子或分子；金屬、半導(dǎo)體 - 電子;量子場(chǎng) - 量子，電

4、磁場(chǎng) - 光子等Complex systems examples:生態(tài)系統(tǒng) - 物種社會(huì)系統(tǒng) - 人計(jì)算機(jī)網(wǎng)絡(luò) - 計(jì)算機(jī)市場(chǎng) - 經(jīng)紀(jì)人agent魚(yú)群 - 魚(yú)、鳥(niǎo)群 - 鳥(niǎo)、蟻群 - 螞蟻組合問(wèn)題 – 變量 –研究復(fù)雜系統(tǒng)為什么要學(xué)習(xí)統(tǒng)計(jì)物理？,Collective Behavior 群體行為,集體行為：系統(tǒng)由大量相似的個(gè)體組成全局行為不依賴于個(gè)體的精確細(xì)節(jié)，而相互作用必須合理定義，并且不要太復(fù)雜；個(gè)體在單獨(dú)

5、存在的行為與在整體中的行為很不一樣.(在整體中各個(gè)體行為變得相似)；相互作用的類型：吸引、抗拒、對(duì)齊…主要的集體現(xiàn)象：相變、模式形成、群組運(yùn)動(dòng)、同步… 研究手段：統(tǒng)計(jì)物理、多主體計(jì)算機(jī)模擬“磁化”現(xiàn)象:go個(gè)體行為 ? 鄰居動(dòng)作的平均方向同步掌聲恐慌現(xiàn)象,http://angel.elte.hu/~vicsek/,自旋玻璃(Spin Glasses),簡(jiǎn)單的理想模型，性質(zhì)豐富，易于研究個(gè)體:spin si; 系統(tǒng):多個(gè)s

6、pin局部相互作用以最簡(jiǎn)單的Ising模型為例：si=1 或者 –1在lattice上排列，相鄰spin之間有相互作用能量(Hamiltonian)：E = - ?J(i-1)isi-1siJij>0, 偏好相鄰?fù)颍籎ij<0, 偏好相鄰不同向；Jij=0,無(wú)相互作用考慮外部場(chǎng) E = - ?Jijsisj - ?hisi性質(zhì)：有序/無(wú)序、受挫、相變、對(duì)稱破缺…現(xiàn)實(shí)中的例子：組合問(wèn)題、恐慌人群、經(jīng)濟(jì)模型,E

7、=- ?Jijsisj,Spin Glass,Configuration r = {s1,s2,…,sn}Hamiltonian (E, Cost function): E(r)J=HJ(r) = -∑JiksiskQuenched variable: J, random variable a probability distribution P(J)Different Spin model: different P(J)N

8、otation:=∑PJ(s)g(s)So-called ‘Disorder’: Structural parameter J is random and have large complexity,自旋玻璃例子- K-SAT問(wèn)題,經(jīng)典NP-完全問(wèn)題N個(gè)布爾變量: xi=True/False, si=1/-1M個(gè)clauses: M個(gè)含k個(gè)變量的邏輯表達(dá)式K=3, 3-SAT: c1:x1 or (not x3) or x8,

9、c2:(not x2) or x3 or (not x4), c3:x3 or x7 or x9,…目標(biāo)：滿足所有M個(gè)clauses 的 N個(gè)布爾變量的一組賦值Spin glass 的能量 E =- ?a=1,M?(Ca =T),Ground State E=-M ?解狀態(tài)結(jié)果：當(dāng)K=3, M/N ~4.25, 問(wèn)題求解困難,恐慌現(xiàn)象,行人建模：期望移動(dòng)速度、與他人的排斥力、與墻壁的作用力、個(gè)人速度的擾動(dòng)恐慌

10、（由于火災(zāi)或者大眾心理）：人們希望移動(dòng)更快人與人之間的物理沖突更厲害；出口處障礙、堵塞形成；危險(xiǎn)壓力出現(xiàn)；人群開(kāi)始出現(xiàn)大眾恐慌心理；看不到其它的出口；計(jì)算機(jī)模擬實(shí)驗(yàn)： (Go) 單出口房間：無(wú)恐慌、恐慌、驚跑、帶圓柱、火災(zāi)走廊：直走廊、中間加寬的走廊人群：個(gè)人主義、群體心理、兩者綜合,Begin…,統(tǒng)計(jì)物理能做什么？怎么做？基本點(diǎn)：只關(guān)心狀態(tài)的概率，并不關(guān)心演化的過(guò)程（假設(shè)各態(tài)歷經(jīng)）熵最大核心： Boltz

11、mann分布 (partition function),學(xué)習(xí)提綱和計(jì)劃,基本概念介紹Entropy, Boltzmann分布(partition function)Example: K-SAT問(wèn)題的相變Dynamics and Landscapes各態(tài)歷盡, landscapes, Monte Carlo SimulationExample: Simulated Annealing(模擬退火)Meanfield, Re

12、plica Symmetry, Cavity MethodsMeanfield 用于網(wǎng)絡(luò)動(dòng)力學(xué)的例子Replica Symmetry 用于組合問(wèn)題的例子Cavity Methods: Survey Propagation Critical Phenomena & Power-law相變SOC, HOT/COLD理論,Entropy,Microstate r: a specific configuration of s

13、ystemMacrostate R: an evaluation value?(R): number of microstates related to a macrostateMicro-canonical entropy: S(R)=k log ?(R) More General forms:A macrostate R: {pi} for system be found in a microstate i

14、 A distribution of microstates.Gibbs Entropy: S(R) =-k ∑pi logpi Maximum ? the most possible distribution of microstates Without constraint on pi, pi=1/N ? S is maximized,?({ni})=M!/n1!n2!...n

15、N!, pi=ni/M,,,With Constraint on pi: Partition Function Z,Observable quantity E (Hamiltonian)Ergodic Hypothesis (time average=ensemble average)We know: From experiments: , Ei for all ri, and = = ∑piEi, ∑pi=1.We wa

16、nt to know the most probable distribution of microstates Maximize S=-k∑pilogpi and we get: pi=e-βEi/Z, Z=∑ie-βEi (β=(kT)-1)So, {pi} and β is decided by {Ei} and Knowing βor T and {Ei}, we can define

17、the most possible distribution of microstates {pi} and Zβ? ? T? ? ? ? Z? distribution is less symmetrical,Toy Example,Three microstates: E1=0, E2=2, E3=3We have p1E1+p2E2+p3E3= e.g. 2p2+3p3=, and p1+p2+p3=1 3 tem

18、peratures: decreasing order of T,Important concepts,Partition function: Z(T,E)=∑re- E(r)/T Knowing this, we can do a lot of things!Variance of E, #sol, …Free Energy: F = -k T lnZ (?)Entropy S=- (?F/? T)E=-k ∑piln

19、pi,Z and #sol (ground state),Z (T)=∑re-E(r)/T = ∑H={1,2,…}∑r|E(r)=H e-H/T When T→0, system are most likely in the ground state. e-E(r)/T →0 except E(r)=0Z(0)= ∑ r|E(r)=0 e-0 =∑ r|E(r)=0So, number of ground states = Z(

20、0).In T>0, Z also counts other r that E(r)>0. But the lower T, the r with lower E(r) Z counts. Z is decreasing when T is decreasing.The K-SAT result considers T=0.,學(xué)習(xí)提綱和計(jì)劃,基本概念介紹Entropy, Boltzmann分布(partition f

21、unction)Example: K-SAT問(wèn)題的相變Dynamics and Landscapes各態(tài)歷盡, landscapes, Monte Carlo SimulationExample: Simulated Annealing(模擬退火)Meanfield, Replica Symmetry, Cavity MethodsMeanfield 用于網(wǎng)絡(luò)動(dòng)力學(xué)的例子Replica Symmetry 用于組合問(wèn)題的例子

22、Cavity Methods: Survey Propagation Critical Phenomena & Power-law相變SOC, HOT/COLD理論,各態(tài)歷盡,對(duì)任意2個(gè)系統(tǒng)狀態(tài)r1和r2, r1可以經(jīng)過(guò)有限部變換到r2.,00,01,10,11,熵最大分布的三個(gè)條件,Rij=probability of ri changes to rj 方程的平衡狀態(tài)是熵最大分布,必須要滿足：p=R

23、83;p, R 有唯一的主特征向量(特征值為1)各態(tài)歷經(jīng)細(xì)致平衡：平衡態(tài)時(shí)，pi·Rij=pj·Rji,Ergodicity breaking and Landscape,Mapping of microstates onto energies,barrier,r1,r2,r3,rn,…,Very high, unlikely to cross, when system size is large,T is

24、 low:pi/pj=e-(Ei-Ej)/T,Monte Carlo Simulation,設(shè)定狀態(tài)轉(zhuǎn)換矩陣，使得系統(tǒng)演化服從我們希望的狀態(tài)分布 P。如果各態(tài)歷盡和細(xì)致平衡，有 把P代入就可以得到Rij,Simulated Annealing,目標(biāo)P是Boltzmann分布：pi?e-Ei/T。Rij/Rji=e-(Ej-Ei)/T Rij= 1if Ej?Ei e-(E

25、j-Ei)/T if Ej>EiSimulated Annealing:We want to minimize ET=0, ergodicity breaking, favors minimal ET>0, barriers can be crossed, favors more states Most problems have many metastable states (local op

26、tima), various scales of barriers heights,,學(xué)習(xí)提綱和計(jì)劃,基本概念介紹Entropy, Boltzmann分布(partition function)Example: K-SAT問(wèn)題的相變Dynamics and Landscapes各態(tài)歷盡, landscapes, Monte Carlo SimulationExample: Simulated Annealing(模擬退火)M

27、eanfield, Replica Symmetry, Cavity MethodsMeanfield 用于網(wǎng)絡(luò)動(dòng)力學(xué)的例子Replica Symmetry 用于組合問(wèn)題的例子Cavity Methods: Survey Propagation Critical Phenomena & Power-law相變SOC, HOT/COLD理論,Replica Approach and P(J),For a given J

28、, free energy density:fJ=-1/(βN) ln ZJFor a P(J), we want to know: =∑P(J)fJFor n replicas: Zn=∑JP(J)(ZJ)n≡ (ZJ)n=∑{s1}∑{s2}…∑{sn} exp{-∑a=1nβHJ(sa)}si is the i th replica. fn=-1/(βnN) ln Zn, ln Z= Lim n→0 (Zn-1/n)

29、We get: = Lim n→0 fn ≡f0,參考教材,http://groups.yahoo.com/group/CSSGBJ/Mark Newman 2001 復(fù)雜系統(tǒng)暑期學(xué)校教材 http://www.santafe.edu/~mark/budapest01/ K-SAT相變: Nature, Vol 400, July 1999, p133-137Survey Propagation: Science, Vol 297

30、, Aug. 2002, p812-815, p784-785.SOC: 《大自然如何工作》, Per Bak.HOT/COLD:HOT: Highly Optimized Tolerance: A Mechanism for Power Laws in Designed Systems. J. M. Carlson, John Doyle. (April 27, 1999)COLD: Optimal design, robus