统计物理学习讲义.ppt

统计物理学习讲义,中科院数学院复杂系统研究中心复杂系统学习班(CSSGBJ)韩 靖2003年10月27日,统计物理、自旋玻璃和复杂系统,统计物理做什么？自旋玻璃(Spin Glasses)是什么？它们在复杂系统研究中有何应用？它们的局限性？探讨：对我们的研究有何启发？,学习提纲和计划(欢迎补充修改),基本概念介绍Entropy,Boltzmann分布(partition function)Example:K-SAT问题的相变Dynamics and Landscapes各态历尽,landscapes,Monte Carlo SimulationExample:Simulated Annealing(模拟退火)Meanfield,Replica Symmetry,Cavity MethodsMeanfield 用于网络动力学的例子Replica Symmetry 用于组合问题的例子Cavity Methods:Survey Propagation Critical Phenomena&Power-law相变SOC,HOT/COLD理论,统计物理,Statistical physics is about systems composed of many parts.集体行为 组合数学和概率理论Traditional examples:气体、液体、固体-原子或分子；金属、半导体-电子;量子场-量子，电磁场-光子等Complex systems examples:生态系统-物种社会系统-人计算机网络-计算机市场-经纪人agent鱼群-鱼、鸟群-鸟、蚁群-蚂蚁组合问题 变量 研究复杂系统为什么要学习统计物理？,Collective Behavior 群体行为,集体行为：系统由大量相似的个体组成全局行为不依赖于个体的精确细节，而相互作用必须合理定义，并且不要太复杂；个体在单独存在的行为与在整体中的行为很不一样.(在整体中各个体行为变得相似)；相互作用的类型：吸引、抗拒、对齐主要的集体现象：相变、模式形成、群组运动、同步 研究手段：统计物理、多主体计算机模拟“磁化”现象:go个体行为 邻居动作的平均方向同步掌声恐慌现象,http:/angel.elte.hu/vicsek/,自旋玻璃(Spin Glasses),简单的理想模型，性质丰富，易于研究个体:spin si;系统:多个spin局部相互作用以最简单的Ising模型为例：si=1 或者 1在lattice上排列，相邻spin之间有相互作用能量(Hamiltonian)：E=-J(i-1)isi-1siJij0,偏好相邻同向；Jij0,偏好相邻不同向；Jij=0,无相互作用考虑外部场 E=-Jijsisj-hisi性质：有序/无序、受挫、相变、对称破缺现实中的例子：组合问题、恐慌人群、经济模型,E=-Jijsisj,Spin Glass,Configuration r=s1,s2,snHamiltonian(E,Cost function):E(r)J=HJ(r)=-JiksiskQuenched variable:J,random variable a probability distribution P(J)Different Spin model:different P(J)Notation:=PJ(s)g(s)So-called Disorder:Structural parameter J is random and have large complexity,自旋玻璃例子-K-SAT问题,经典NP-完全问题N个布尔变量:xi=True/False,si=1/-1M个clauses:M个含k个变量的逻辑表达式K=3,3-SAT:c1:x1 or(not x3)or x8,c2:(not x2)or x3 or(not x4),c3:x3 or x7 or x9,目标：满足所有M个clauses 的 N个布尔变量的一组赋值Spin glass 的能量 E=-a=1,M(Ca=T),Ground State E=-M 解状态结果：当K=3,M/N 4.25,问题求解困难,恐慌现象,行人建模：期望移动速度、与他人的排斥力、与墙壁的作用力、个人速度的扰动恐慌（由于火灾或者大众心理）：人们希望移动更快人与人之间的物理冲突更厉害；出口处障碍、堵塞形成；危险压力出现；人群开始出现大众恐慌心理；看不到其它的出口；计算机模拟实验：(Go)单出口房间：无恐慌、恐慌、惊跑、带圆柱、火灾走廊：直走廊、中间加宽的走廊人群：个人主义、群体心理、两者综合,Begin,统计物理能做什么？怎么做？基本点：只关心状态的概率，并不关心演化的过程（假设各态历经）熵最大核心：Boltzmann分布(partition function),学习提纲和计划,基本概念介绍Entropy,Boltzmann分布(partition function)Example:K-SAT问题的相变Dynamics and Landscapes各态历尽,landscapes,Monte Carlo SimulationExample:Simulated Annealing(模拟退火)Meanfield,Replica Symmetry,Cavity MethodsMeanfield 用于网络动力学的例子Replica Symmetry 用于组合问题的例子Cavity Methods:Survey Propagation Critical Phenomena&Power-law相变SOC,HOT/COLD理论,Entropy,Microstate r:a specific configuration of systemMacrostate 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 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!.nN!,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 want to know the most probable distribution of microstates Maximize S=-kpilogpi 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 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 temperatures: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 pilnpi,Z and#sol(ground state),Z(T)=re-E(r)/T=H=1,2,r|E(r)=H e-H/T When T0,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(0).In T0,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.,学习提纲和计划,基本概念介绍Entropy,Boltzmann分布(partition function)Example:K-SAT问题的相变Dynamics and Landscapes各态历尽,landscapes,Monte Carlo SimulationExample:Simulated Annealing(模拟退火)Meanfield,Replica Symmetry,Cavity MethodsMeanfield 用于网络动力学的例子Replica Symmetry 用于组合问题的例子Cavity Methods:Survey Propagation Critical Phenomena&Power-law相变SOC,HOT/COLD理论,各态历尽,对任意2个系统状态r1和r2,r1可以经过有限部变换到r2.,00,01,10,11,熵最大分布的三个条件,Rij=probability of ri changes to rj 方程的平衡状态是熵最大分布,必须要满足：p=Rp,R 有唯一的主特征向量(特征值为1)各态历经细致平衡：平衡态时，piRij=pjRji,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 low:pi/pj=e-(Ei-Ej)/T,Monte Carlo Simulation,设定状态转换矩阵，使得系统演化服从我们希望的状态分布 P。如果各态历尽和细致平衡，有 把P代入就可以得到Rij,Simulated Annealing,目标P是Boltzmann分布：pie-Ei/T。Rij/Rji=e-(Ej-Ei)/T Rij=1if EjEi e-(Ej-Ei)/T if EjEiSimulated Annealing:We want to minimize ET=0,ergodicity breaking,favors minimal ET0,barriers can be crossed,favors more states Most problems have many metastable states(local optima),various scales of barriers heights,学习提纲和计划,基本概念介绍Entropy,Boltzmann分布(partition function)Example:K-SAT问题的相变Dynamics and Landscapes各态历尽,landscapes,Monte Carlo SimulationExample:Simulated Annealing(模拟退火)Meanfield,Replica Symmetry,Cavity MethodsMeanfield 用于网络动力学的例子Replica Symmetry 用于组合问题的例子Cavity Methods:Survey Propagation Critical Phenomena&Power-law相变SOC,HOT/COLD理论,Replica Approach and P(J),For a given J,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=s1s2sn exp-a=1nHJ(sa)si is the i th replica.fn=-1/(nN)ln Zn,ln Z=Lim n0(Zn-1/n)We get:=Lim n0 fn f0,参考教材,Mark Newman 2001 复杂系统暑期学校教材 http:/www.santafe.edu/mark/budapest01/K-SAT相变:Nature,Vol 400,July 1999,p133-137Survey Propagation:Science,Vol 297,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,robustness,and risk aversion.M.E.J.Newman,Michelle Girvan and J.Doyne Farmer,