统计物理学习讲义 中科院数学院复杂系统研究中心 复杂系统学习班 (CSSGBJ) 韩 靖 2003 年 10 月 27 日.

Presentation on theme: "统计物理学习讲义 中科院数学院复杂系统研究中心 复杂系统学习班 (CSSGBJ) 韩 靖 2003 年 10 月 27 日."— Presentation transcript:

1 统计物理学习讲义 中科院数学院复杂系统研究中心 复杂系统学习班 (CSSGBJ) 韩 靖 2003 年 10 月 27 日

2 统计物理、自旋玻璃和复杂系统 统计物理做什么？ 自旋玻璃 (Spin Glasses) 是什么？ 它们在复杂系统研究中有何应用？ 它们的局限性？ 探讨：对我们的研究有何启发？

3 学习提纲和计划 ( 欢迎补充修改 ) 基本概念介绍 Entropy, Boltzmann 分布 (partition function) Example: K-SAT 问题的相变 Dynamics and Landscapes 各态历尽, landscapes, Monte Carlo Simulation Example: Simulated Annealing( 模拟退火 ) Meanfield, Replica Symmetry, Cavity Methods Meanfield 用于网络动力学的例子 Replica Symmetry 用于组合问题的例子 Cavity Methods: Survey Propagation Critical Phenomena & Power-law 相变 SOC, HOT/COLD 理论 谁报名来主讲？

4 统计物理 Statistical physics is about systems composed of many parts. 集体行为 组合数学和概率理论 Traditional examples: 气体、液体、固体 - 原子或分子； 金属、半导体 - 电子 ; 量子场 - 量子，电磁场 - 光子等 Complex systems examples: 生态系统 - 物种 社会系统 - 人 计算机网络 - 计算机 市场 - 经纪人 agent 鱼群 - 鱼、鸟群 - 鸟、蚁群 - 蚂蚁 组合问题 – 变量 – 研究复杂系统为什么要学习统计物理？

5 Collective Behavior 群体行为 集体行为： 系统由大量相似的个体组成 全局行为不依赖于个体的精确细节， 而相互作用必须合理定义，并且不要太复杂； 个体在单独存在的行为与在整体中的行为很不一样. ( 在整体中各个体行为变得相似 ) ； 相互作用的类型：吸引、抗拒、对齐 … 主要的集体现象：相变、模式形成、群组运动、同步 … 研究手段：统计物理、多主体计算机模拟 “ 磁化 ” 现象 :go 个体行为  邻居动作的平均方向go 同步掌声 恐慌现象 http://angel.elte.hu/~vicsek/

6 自旋玻璃 (Spin Glasses) 简单的理想模型，性质丰富，易于研究 个体 :spin s i ; 系统 : 多个 spin 局部相互作用 以最简单的 Ising 模型为例： s i =1 或者 –1 在 lattice 上排列，相邻 spin 之间有相互作用 能量 (Hamiltonian) ： E = -  J (i-1)i s i-1 s i J ij >0, 偏好相邻同向； J ij <0, 偏好相邻不同向； J ij =0, 无相互作用 考虑外部场 E = -  J ij s i s j -  h i s i 性质：有序 / 无序、受挫、相变、对称破缺 … 现实中的例子：组合问题、恐慌人群、经济模型 (-) (+) ? sisi s i+1 s i-1 J (i-1)i J i(i+1) E=-  J ij s i s j

7 Spin Glass Configuration r = {s 1,s 2, …,s n } Hamiltonian (E, Cost function): E(r) J =H J (r) = -∑J ik s i s k Quenched variable: J, random variable a probability distribution P(J) Different Spin model: different P(J) Notation: =∑P J (s)g(s) So-called ‘ Disorder ’ : Structural parameter J is random and have large complexity

8 自旋玻璃例子 - K-SAT 问题 经典 NP- 完全问题 N 个布尔变量 : x i =True/False, s i =1/-1 M 个 clauses: M 个含 k 个变量的逻辑表达式 K=3, 3-SAT: c 1 :x 1 or (not x 3 ) or x 8, c 2 :(not x 2 ) or x 3 or (not x 4 ), c 3 :x 3 or x 7 or x 9, … 目标：满足所有 M 个 clauses 的 N 个布尔变量的一组赋值 Spin glass 的能量 E = -  a=1,M  (C a =T), Ground State E=-M  解状态 结果：当 K=3, M/N ~4.25, 问题求解困难

9 恐慌现象 行人建模： 期望移动速度、与他人的排斥力、与墙壁的作用力、个 人速度的扰动 恐慌（由于火灾或者大众心理）： 人们希望移动更快 人与人之间的物理冲突更厉害； 出口处障碍、堵塞形成； 危险压力出现； 人群开始出现大众恐慌心理； 看不到其它的出口； 计算机模拟实验： (Go)(Go) 单出口房间：无恐慌、恐慌、惊跑、带圆柱、火灾 走廊：直走廊、中间加宽的走廊 人群：个人主义、群体心理、两者综合

10 Begin … 统计物理能做什么？怎么做？ 基本点： 只关心状态的概率，并不关心演化的过程 （假设各态历经） 熵最大 核心： Boltzmann 分布 (partition function)

11 学习提纲和计划 基本概念介绍 Entropy, Boltzmann 分布 (partition function) Example: K-SAT 问题的相变 Dynamics and Landscapes 各态历尽, landscapes, Monte Carlo Simulation Example: Simulated Annealing( 模拟退火 ) Meanfield, Replica Symmetry, Cavity Methods Meanfield 用于网络动力学的例子 Replica Symmetry 用于组合问题的例子 Cavity Methods: Survey Propagation Critical Phenomena & Power-law 相变 SOC, HOT/COLD 理论

12 Entropy Microstate r: a specific configuration of system Macrostate R: an evaluation value Ω(R): number of microstates related to a macrostate Micro-canonical entropy: S(R)=k log Ω(R) More General forms: A macrostate R: {p i } for system be found in a microstate i A distribution of microstates. Gibbs Entropy: S(R) =-k ∑p i logp i Maximum  the most possible distribution of microstates Without constraint on p i, p i =1/N  S is maximized Ω({n i })=M!/n 1 !n 2 !...n N !, p i =n i /M

13 With Constraint on p i : Partition Function Z Observable quantity E (Hamiltonian) Ergodic Hypothesis (time average=ensemble average) We know: From experiments:, E i for all r i, and = = ∑p i E i, ∑p i =1. We want to know the most probable distribution of microstates Maximize S=-k∑p i logp i and we get: p i =e -βE i /Z, Z=∑ i e -βE i (β=(kT) -1 ) So, {p i } and β is decided by {E i } and Knowing βor T and {E i }, we can define the most possible distribution of microstates {p i } and Z β   T     Z  distribution is less symmetrical

14 Toy Example Three microstates: E 1 =0, E 2 =2, E 3 =3 We have p 1 E 1 +p 2 E 2 +p 3 E 3 = e.g. 2p 2 +3p 3 =, and p 1 +p 2 +p 3 =1 3 temperatures: decreasing order of T β Zp1p1 p2p2 p3p3 11.50.1052.5400.3930.3190.287 210.4201.7160.5830.2520.165 30.31.0831.1540.8670.0990.034

15 Important concepts Partition function: Z(T,E)=∑ r e - 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 ∑p i lnp i

16 Z and #sol (ground state) Z (T)=∑ r e -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)=0 Z(0)= ∑ r|E(r)=0 e -0 =∑ r|E(r)=0 So, number of ground states = Z(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.

17 学习提纲和计划 基本概念介绍 Entropy, Boltzmann 分布 (partition function) Example: K-SAT 问题的相变 Dynamics and Landscapes 各态历尽, landscapes, Monte Carlo Simulation Example: Simulated Annealing( 模拟退火 ) Meanfield, Replica Symmetry, Cavity Methods Meanfield 用于网络动力学的例子 Replica Symmetry 用于组合问题的例子 Cavity Methods: Survey Propagation Critical Phenomena & Power-law 相变 SOC, HOT/COLD 理论

18 各态历尽 对任意 2 个系统状态 r 1 和 r 2, r 1 可以经过有限部 变换到 r 2. 00 01 10 11

19 熵最大分布的三个条件 R ij =probability of r i changes to r j 方程的平衡状态是熵最大分布, 必须要满足： p=R·p, R 有唯一的主特征向量 ( 特征值为 1) 各态历经 细致平衡：平衡态时， p i ·R ij =p j ·R ji

20 Ergodicity breaking and Landscape Mapping of microstates onto energies barrier r1r1 r2r2 r3r3 rnrn … Very high, unlikely to cross, when system size is large, T is low: p i /p j =e -(Ei-Ej)/T

21 Monte Carlo Simulation 设定状态转换矩阵，使得系统演化服从我们希望的状 态分布 P 。 如果各态历尽和细致平衡，有 把 P 代入就可以得到 R ij

22 Simulated Annealing 目标 P 是 Boltzmann 分布： p i  e -Ei/T 。 R ij /R ji =e -(Ej-Ei)/T R ij = 1if E j  E i e -(Ej-Ei)/T if E j >E i Simulated Annealing: We want to minimize E T=0, ergodicity breaking, favors minimal E T>0, barriers can be crossed, favors more states Most problems have many metastable states (local optima), various scales of barriers heights

23 学习提纲和计划 基本概念介绍 Entropy, Boltzmann 分布 (partition function) Example: K-SAT 问题的相变 Dynamics and Landscapes 各态历尽, landscapes, Monte Carlo Simulation Example: Simulated Annealing( 模拟退火 ) Meanfield, Replica Symmetry, Cavity Methods Meanfield 用于网络动力学的例子 Replica Symmetry 用于组合问题的例子 Cavity Methods: Survey Propagation Critical Phenomena & Power-law 相变 SOC, HOT/COLD 理论

24 Replica Approach and P(J) For a given J, free energy density: f J =-1/(βN) ln Z J For a P(J), we want to know: =∑P(J)f J For n replicas: Z n =∑ J P(J)(Z J ) n ≡ (Z J ) n =∑ {s 1 } ∑ {s 2 } … ∑ {s n } exp{-∑ a=1 n βH J (s a )} s i is the i th replica. f n =-1/(βnN) ln Z n, ln Z= Lim n → 0 (Z n -1/n) We get: = Lim n → 0 f n ≡ f 0

25 参考教材 http://groups.yahoo.com/group/CSSGBJ/ Mark Newman 2001 复杂系统暑期学校教材 http://www.santafe.edu/~mark/budapest01/ http://www.santafe.edu/~mark/budapest01/ K-SAT 相变 : Nature, Vol 400, July 1999, p133-137 Survey 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