Differences

This shows you the differences between two versions of the page.

--- 전산물리학:열풀림_시늉 [2025/07/03 16:33] – created admin
+++ 전산물리학:열풀림_시늉 [2026/01/09 15:18] (current) – admin
@@ Line 1: / Line 1: @@
+======최대 절단(max-cut) 문제======
+모든 노드가 한쪽에 몰려 있는 상황에서 시작해보자. 즉 모든 노드 $k$에 대해 side[k]=+1이다. 이때 목적함수의 값은 obj=0에서 출발한다. 노드 사이의 실선은 +1의 가중치, 점선은 -1의 가중치를 의미한다.
+{{:전산물리학:maxcut0.png?250|}}
+노드 하나를 무작위로 골라서 반대편으로 보낸다. $k=3$가 선택되었다고 하자.
+{{:전산물리학:maxcut1.png?400|}}
+side[k]=-1이 되고, 목적함수의 값은 obj=1로 변할 것이다. 그런데 이것은 원래 $k=3$이 가지고 있었던 링크들의 가중치를 모두 더한 것에 불과하다.
+따라서 애초에 chg[1]=1+1=2, chg[2]=1-1-1=-1, chg[3]=1+1-1=1, 그리고 chg[4]=-1+1=0을 미리 계산해두었더라면 그 중 하나를 옮겼을 때 obj가 얼마나 변할지 바로 알 수 있었다. 즉 obj += chg[k]이다.
+위에서처럼 이미 $k=3$이 옮겨진 상황에서, 하나를 골라서 다른 쪽으로 보낸다면 obj가 얼마가 변할지도 미리 알 수 있을까? 다시 $k=3$이 선택된다면 답은 쉽다. 제자리로 돌아가는 것이므로 chg[3]은 조금 전에 자신이 가지던 값에서 부호만을 바꾼 것이다.
+$k=1$이 선택된다면?
+{{:전산물리학:maxcut2.png?400|}}
+그림처럼 다시금 obj=1이므로, 옮기기 전에 이미 chg[1]=0이었어야 했다. 이는 다음처럼 이해할 수 있다. 노드 1을 옮기면 1과 3이 같은 쪽에 속하므로 그 사이의 연결은 obj에 세어지지 않고, 1과 2 사이의 연결이 obj에 셈해진다. 노드 1이 가지는 연결 중 하나는 +1의 기여를 하고 다른 하나는 -1의 기여를 하므로 chg[1]=0이다. 그런데 1과 2 사이의 연결은 맨 처음에 chg[1]을 계산할 때 이미 한번 더해졌던 것이기 때문에, $k=3$을 옮길 때에 앞으로는 1과 3 사이 연결이 가지는 가중치가 반대의 역할을 하게 되리라는 것만 고려해주어도 된다. 즉 $k=3$을 옮겼을 때에 chg[1] += (-2)*1로 갱신해주었으면 된다. 마찬가지 논리로 $k=3$을 옮겼을 때 미리 chg[2] += (-2)*(-1)와 chg[4] += (-2)*1로 갱신해주도록 하자. 이 결과는 옳다. 따라서 지금까지의 내용을 정리해보면, $k$를 옮기면서 $k$에 연결된 노드 $v$들을 찾고, $v$와 $k$ 사이 연결의 가중치 $w$를 찾아서 chg[v] += (-2)*w를 해주면 될 것처럼 보인다.
+이제 $k=1$을 옮겼으므로 방금 우리가 추측한 것처럼 $k=1$이 넘어간 그 순간에 chg의 값들을 갱신해보도록 하자. chg[1]이 -chg[1]으로 주어져 0임은 자명하다. $k=1$은 2와 3에 연결되어 있고 둘 모두 +1의 가중치로 연결되어 있다. 그러면 chg[2] += (-2)*1로서 chg[2]=-1이 된다. 이 값은 옳다. chg[3]도 chg[3] += (-2)*1로서 -3이 될까? 그렇지 않다. 옳은 값은 chg[3] += 2*1로서 chg[3]이 +1이 되는 것이다. 왜냐하면 노드 1과 3이 같은 편에 있게 되므로 1이 다시 왼쪽으로 넘어간다면 둘 사이의 가중치는 +의 역할을 하는 것이다. 따라서 옳은 규칙은 다음과 같다.
+  * 반대쪽으로 옮길 노드 $k$를 고른다.
+  * $k$에 연결된 노드 $v$들을 찾는다.
+  * $v$와 $k$가 원래 같은 쪽에 있다가 헤어지는 것이라면 둘 사이의 연결의 가중치 $w$를 찾아서 chg[v] += (-2)*w로 갱신한다.
+  * 그렇지 않고 다른 쪽에 있다가 만나는 것이라면 chg[v] += 2*w로 갱신한다.
+{{:전산물리학:maxcut3.png?400|}}
+그림처럼 $k=3$을 골라서 다시 왼쪽으로 보냈다고 하고 (obj=2) 위의 규칙대로 chg의 값들을 갱신해보자. chg[3]은 부호만 뒤집으면 되므로 chg[3]=-1이다. chg[1]+=(-2)*1로서 chg[1]=-2가 된다. chg[2]+=2*(-1)로서 chg[2]=-3이 된다. 마지막으로, chg[4]+=2*1로서 chg[4]=0이 된다. 이 값들은 모두 옳다.
+위 규칙을 코드로 구현하고 열풀림 시늉으로 풀어본 결과는 아래와 같다.
+<code:python>
+from numpy import zeros, array, ones
+from numpy.random import randint, uniform
+from math import exp
+n = G.number_of_nodes()
+m = G.number_of_edges()
+chg = zeros(n, int)
+for a, b, data in G.edges(data=True):
+  u = int(a)-1
+  v = int(b)-1
+  w = int(data.get('weight'))
+  chg[u] += w
+  chg[v] += w
+side = ones(n, int)
+obj = 0
+best = 0
+beta = 0.0
+betamax = 10
+dbeta = 10**(-5)
+blist = []
+while beta<betamax:
+  k = randint(n)
+  if chg[k]>=0 or uniform() < exp(beta*chg[k]):
+    obj += chg[k]
+    side[k] *= -1
+    chg[k] *= -1
+    for origin, destination, data in G.edges(str(k+1), data=True):
+      u = int(origin) - 1
+      v = int(destination) - 1
+      vw = int(data.get('weight'))
+      chg[v] += vw * (2 - 4 *(side[k] != side[v]))
+    if obj > best:
+      for i in range(n):
+        best = obj
+  beta += dbeta
+  blist.append(best)
+plt.plot(blist)
+plt.show()
+print(side)
+print(best)
+</code>
 ======참고문헌======
-  * Spears, William M. //Simulated annealing for hard satisfiability problems//, Cliques, Coloring, and Satisfiability **26** (1993): 533-558.
+  * [[https://www.researchgate.net/publication/2769769_Simulated_Annealing_for_Hard_Satisfiability_Problems|Spears, William M., Simulated annealing for hard satisfiability problems, Cliques, Coloring, and Satisfiability **26** (1993): 533-558.]]
-  * Myklebust, Tor GJ. "Solving maximum cut problems by simulated annealing." arXiv preprint arXiv:1505.03068 (2015).
+  * [[https://arxiv.org/abs/1505.03068|Myklebust, Tor GJ., Solving maximum cut problems by simulated annealing]]
   * https://www.math.wustl.edu/~feres/Math350Fall12.html
   * https://www.physics.rutgers.edu/~haule/509/Traveling_Salesman1.html
+  * Aarts and Korst, Simulated Annealing and Boltzmann Machines (Wiley, Chichester, 1989).