분지 도약

최적설계 분자동역학 수치해석 마지막 수정: 2026-08-15 04:51:06

1. 개요[편집]

산을 넘기가 힘들면 산을 없애면 된다. 없앨 방법은 이미 손에 있었다 — 국소 최소화기.

분지 도약(basin hopping, BH)은 목적함수를 국소 최소화로 계단 함수로 변환한 뒤, 그 변환된 지형 위에서 무작위 섭동과 메트로폴리스 수락을 반복하는 전역 최적화 메타휴리스틱이다. 한 번의 반복은 “현재 해를 흔든다 → 국소 최소화한다 → 에너지가 내려갔거나 메트로폴리스 판정을 통과하면 받아들인다”로 끝난다. 구현은 20줄이면 되는데, 원자 클러스터 구조 탐색에서는 아직도 이걸 이기기가 쉽지 않다.

이 문서는 왜 그 지형 변환이 탐색을 쉽게 만드는가에 초점을 둔다. 국소해에 갇히는 문제 일반과 다중 시작 전략은 지역 최적해, 유역이라는 개념 자체는 흡인 유역 문서에 정리돼 있다.

2. 지형 변환이 전부다[편집]

원래 목적함수를 $E(\mathbf{X})$ , 국소 최소화 연산자를 $\mathcal{L}$ 이라 하자. 분지 도약이 실제로 탐색하는 것은 $E$ 가 아니라

\tilde{E}(\mathbf{X}) = E\bigl(\mathcal{L}(\mathbf{X})\bigr) = \min\bigl\{ E \bigm| \mathbf{X}\ \text{에서 국소 최소화 출발} \bigr\}

이다. $\mathcal{L}$ 은 각 점을 자기 흡인 유역의 최소점으로 보내므로, $\tilde E$ 는 유역마다 상수인 계단 함수가 된다. 이 변환이 갖는 성질 셋이 알고리즘의 전부다.

전역 최소값이 보존된다. $\min \tilde E = \min E$ 이고 최소점도 그대로다. 즉 변환된 문제를 풀면 원래 문제를 푼 것이다. 공짜로 얻은 게 아니라 $\mathcal{L}$ 이 그만큼 계산을 먹는다.
전이 상태 장벽이 사라진다. 원래 지형에서 이웃 최소점 둘 사이를 오가려면 안장점 높이만큼의 장벽을 넘어야 한다. 계단 지형에서 두 유역 사이의 “높이 차”는 두 최소점의 에너지 차뿐이다. 몬테카를로 수락률이 장벽 높이가 아니라 최소점 간 에너지 차만 보게 되는 것 — 이게 결정적이다. 원래 지형에서는 통계적으로 도달 불가능했던 이동이 계단 지형에서는 흔한 이동이 된다.
잡음이 지워진다. 얕은 국소 최소가 만드는 미세한 요철은 국소 최소화가 통째로 먹어 치운다. 탐색이 보는 것은 유역의 배치뿐이라 유효 차원이 극적으로 줄어든다.

이 사상 $\mathbf{X}\mapsto \mathcal{L}(\mathbf{X})$ 는 통계물리에서 스틸린저-웨버의 고유 구조(inherent structure) 분해로 이미 알려져 있던 것이다. 순간 배열을 담금질해 대응 최소점으로 보내고 상태공간을 유역 단위로 세는 그 사상 그대로다. 분지 도약은 그 분해를 분석 도구가 아니라 탐색 도구로 뒤집어 쓴 셈이다.¹

3. 알고리즘[편집]

초기 배열 $\mathbf{X}_0$ 에서 국소 최소화 → 현재 상태 $\mathbf{X}_{\mathrm{cur}}$ , 에너지 $E_{\mathrm{cur}}$ .
무작위 섭동: $\mathbf{X}' = \mathbf{X}_{\mathrm{cur}} + \Delta$ . 원자계에서는 모든 좌표에 $[-s, s]$ 균등 난수를 더하는 것이 표준.
국소 최소화: $\mathbf{X}'' = \mathcal{L}(\mathbf{X}')$ , $E'' = E(\mathbf{X}'')$ .
메트로폴리스 판정: $E'' \le E_{\mathrm{cur}}$ 이면 무조건 수락, 아니면 확률 $\exp[-(E''-E_{\mathrm{cur}})/T]$ 로 수락.
지금까지 본 최저 에너지를 따로 기록하고 2로 돌아간다.

여기서 반드시 짚어야 할 두 가지가 있다.

$T$ 는 물리 온도가 아니다. 계단 지형 위 MC의 수락 척도일 뿐이며, 대응하는 물리적 앙상블 같은 것은 없다. 그래서 담금질 모사와 달리 냉각 스케줄이 필수가 아니다. 고정 $T$ 로 끝까지 돌리는 것이 표준 사용법이다.
기록과 상태는 별개다. 수락된 현재 상태가 최저점일 필요가 없다. 최저점은 항상 따로 저장한다 — 이 분리가 없으면 탐욕 알고리즘이 된다.

파라미터 두 개를 만지면 된다.

T \sim \langle \Delta E \rangle_{\text{인접 최소점}}, \qquad s \ \text{는 수락률} \approx 0.5\ \text{가 되도록 적응}

$T$ 가 너무 낮으면 단조 하강이 되어 첫 깔때기에 갇히고, 너무 높으면 무작위 재시작(다중 시작)으로 퇴화한다. 웨일스-도이는 레너드-존스 클러스터에서 $T \approx 0.8\varepsilon$ 을 썼다. 스텝 크기 $s$ 는 최근 수락률을 보며 곱셈적으로 조정하는 것이 관행이고, 목표 수락률 0.5는 보통의 마르코프 연쇄 몬테카를로 튜닝 관행과 같다.

원자 클러스터에서는 실무 장치가 하나 더 필요하다. 구속 상자다. 섭동이 크면 원자 하나가 클러스터에서 떨어져 나가 무한히 멀어지는데(증발), 이 상태는 에너지가 나쁘지만 국소 최소이긴 해서 탐색을 낭비한다. 최소화 후 질량중심에서 일정 반경 밖으로 나간 원자를 되돌리는 구속을 걸어 막는다.

4. 누가 언제 만들었나[편집]

두 갈래의 계보가 있고, 둘 다 인정하는 것이 정확하다.

1987년 리-셰라가가 단백질 접힘의 다중 최소 문제를 풀기 위해 몬테카를로 최소화(Monte Carlo-minimization, MCM)라는 이름으로 사실상 같은 알고리즘을 제안했다. 메트-엔케팔린 같은 작은 펩타이드가 시험 대상이었다.
1997년 웨일스-도이가 이를 basin-hopping이라 명명하고, 에너지 지형 변환이라는 관점에서 왜 통하는지를 설명했으며, 최대 110개 원자의 레너드-존스 퍼텐셜 클러스터에 대해 알려진 전역 최소를 전부 재현했다. 악명 높은 LJ38, LJ75~77 포함이라 당시 상당한 충격이었다.

조합 최적화 쪽에서는 같은 뼈대를 반복 국소 탐색(iterated local search, ILS)이라 부른다. “섭동 → 국소 탐색 → 수락 판정”의 삼단 구조가 완전히 동일하고, 다른 것은 국소 탐색이 연속 최적화기냐 이웃 탐색이냐 뿐이다. 서로 다른 커뮤니티에서 독립적으로 같은 구조에 도달한 사례.²

5. 어디까지 되는가 — LJ 클러스터라는 시험대[편집]

레너드-존스 클러스터는 전역 최적화의 표준 벤치마크다. 원자 수 $N$ 이 늘면 국소 최소 개수가 대략 지수적으로 증가한다고 알려져 있어, 완전 탐색은 일찌감치 포기해야 한다.

대부분의 $N$ 에서는 쉽다. 이십면체 껍질 구조가 명백한 깔때기를 이루고, 분지 도약은 수천~수만 회 반복 안에 바닥을 찾는다.
LJ38이 유명한 반례다. 전역 최소는 fcc 절단팔면체인데, 그 유역의 부피는 지형 전체에서 아주 작다. 반면 이십면체 깔때기는 훨씬 넓고 깊이도 비슷하다. 이중 깔때기(double funnel) 지형이라 부르며, 고정 $T$ 분지 도약은 넓은 쪽에 오래 머문다.
LJ75~77은 마크스 십면체가 답인데 역시 좁은 깔때기다. LJ98의 사면체 구조도 같은 부류.

처방은 계열 안에서 나온다.

변형	아이디어
병렬 템퍼링 결합	여러 $T$ 사슬을 동시에 굴리고 교환. 넓은 깔때기 탈출률을 올린다
단조 수열 BH (MSBH)	개선될 때만 수락하되 섭동 크기를 크게. 좁은 깔때기 탐색에 유리
대칭화 이동	무작위 대신 대칭성 높은 배열로 점프하는 이동을 섞는다
이중 끝점(double-ended) 탐색	두 최소점을 잇는 경로와 안장점을 명시적으로 찾아 지형 자체를 지도화

여기서 얻어야 할 일반 교훈이 있다. 전역 최소의 유역이 넓다는 보장은 어디에도 없다. 분지 도약이 잘 되는 문제는 지형이 “깔때기형”(funnel-like), 즉 에너지가 낮을수록 전역 최소에 가까운 문제이고, 이 성질이 깨지면 어떤 메타휴리스틱도 고전한다. 골프 코스 지형(평평한 데 구멍 하나)에서 잘 되는 알고리즘은 존재하지 않는다.

6. 사촌들과의 비교[편집]

방법	탐색하는 지형	핵심 파라미터	성격
분지 도약	계단화된 $\tilde E$	$T$ , 스텝 크기	단일 사슬, 국소 최소화가 비용의 대부분
담금질 모사	원래 $E$	냉각 스케줄	장벽을 실제로 넘어야 함, 스케줄 민감
유전 알고리즘	원래 $E$ (개체군)	개체수, 교차·변이율	교차로 부분 구조를 조합, 구조 최적화에서 강력
다중 시작	계단화된 $\tilde E$	시행 횟수	기억이 없음. BH에서 $T\to\infty$ 인 극한
입자 군집 최적화 · 타부 서치	원래 $E$	군집·기억 구조	개체군 또는 이력 기반

담금질 모사와의 대비가 가장 교육적이다. SA는 원래 지형에서 장벽을 넘어야 하므로 온도를 충분히 높게 시작해 천천히 내려야 하고, 그 스케줄이 성능을 지배한다. BH는 장벽을 지형 변환으로 미리 제거했기 때문에 온도를 굳이 바꿀 이유가 없다. 대신 반복마다 국소 최소화를 완주해야 해서 한 스텝이 훨씬 비싸다. BH는 스텝 수를 줄이는 대신 스텝 단가를 올린 거래라고 보면 정확하다.

기울기가 있느냐가 이 거래의 손익을 결정한다. 해석적 기울기가 있어 준-뉴턴법류 국소 최소화가 수십 회 반복으로 끝나면 BH가 압도적이다. 기울기가 없고 함수 평가가 비싸면 국소 최소화 한 번에 수백 회 평가가 들어가 거래가 뒤집힌다. 잡음 있는 목적함수에서도 $\mathcal{L}$ 이 제대로 수렴하지 않아 계단 변환 자체가 성립하지 않는다.

또 하나 흔한 오해 — 확률적 경사하강법의 잡음이 국소해를 빠져나가게 한다는 이야기와 BH는 다른 종류의 주장이다. SGD의 잡음은 미니배치에서 자동으로 오는 부산물이고 크기를 직접 통제하기 어렵지만, BH는 섭동을 명시적으로 크게 넣고 그다음 반드시 완전한 국소 최소화를 붙인다. 전자는 “얕은 골짜기에 오래 머물지 않는다”에 가깝고, 후자는 “골짜기를 통째로 갈아탄다”에 가깝다.

7. 몇 번 돌려야 하나 — 비용 모형[편집]

전역 최적화에는 수렴 정리가 없으니, 대신 통계로 이야기한다. 한 번의 독립 실행이 $n$ 회 반복 안에 전역 최소를 만날 확률을 $p(n)$ 이라 하면, $m$ 회 독립 재시작 중 적어도 한 번 성공할 확률은

P_{\mathrm{succ}} = 1 - \bigl(1 - p(n)\bigr)^{m}

이고, 총비용은 $m \times n \times C_{\mathcal{L}}$ ( $C_{\mathcal{L}}$ 은 국소 최소화 1회 비용)이다. 문헌에서 실제로 보고하는 지표는 $p$ 가 아니라 최초 조우 시간(first-encounter time)의 분포다. 같은 조건으로 100회 독립 실행을 돌려 전역 최소를 처음 찾은 반복 횟수의 중앙값과 사분위수를 적는 식이며, 평균만 적으면 꼬리가 긴 분포에 속는다.

여기서 나오는 실무 판단이 **“길게 한 번이냐, 짧게 여러 번이냐”**다.

지형이 단일 깔때기면 길게 한 번이 유리하다. 사슬이 계속 내려가는 중이라 재시작은 그 진척을 버리는 것이다.
이중 깔때기처럼 갇힐 수 있는 지형이면 짧게 여러 번이 유리하다. 최초 조우 시간 분포가 두꺼운 꼬리를 가지면 재시작이 기대 비용을 줄인다.
중간 전략이 병렬 템퍼링 결합이다. 낮은 $T$ 사슬은 깊게 파고, 높은 $T$ 사슬은 널리 훑고, 교환으로 정보를 넘긴다. 코어가 여러 개면 사실상 공짜다.

$C_{\mathcal{L}}$ 이 비용을 지배한다는 점도 잊으면 안 된다. 최소화 수렴 판정을 지나치게 빡빡하게 잡으면 반복 하나가 몇 배 비싸지는데, 계단 지형을 만드는 데 필요한 정밀도는 생각보다 낮다 — 어느 유역인지만 구별되면 된다. 탐색 단계에서는 느슨한 수렴 판정으로 반복 수를 벌고, 최종 후보 몇 개만 조여서 다시 최소화하는 2단 전략이 표준이다.

8. 실무[편집]

파이썬에서는 scipy.optimize.basinhopping 이 그대로 있다.

res = basinhopping(func, x0,
                   niter=200, T=1.0, stepsize=0.5,
                   minimizer_kwargs={"method": "L-BFGS-B", "jac": True},
                   callback=cb)

minimizer_kwargs 로 국소 최소화기를 지정한다. 기울기를 줄 수 있으면 반드시 줘라(jac=True). 비용의 90% 이상이 여기서 나므로 수치 미분으로 때우면 그대로 몇 배 손해다.
T 는 목적함수의 스케일에 맞춰야 한다. 에너지 단위가 $10^3$ 인데 T=1.0 을 그대로 두면 단조 하강이 되고, 반대면 무작위 재시작이 된다. 인접 국소 최소들의 에너지 차 분포를 몇 번 재보고 정하는 것이 정석.
take_step 으로 이동 방식을 갈아 끼울 수 있다. 원자계라면 균등 난수 대신 각 좌표 섭동 + 구속 상자를, 각도 변수라면 주기성을 고려한 이동을 넣는다. 문제 구조를 아는 이동을 넣는 것이 온도 튜닝보다 대체로 효과가 크다.
callback 으로 조기 종료를 건다. 전역 최적화에는 수렴 판정이라는 게 원리적으로 없어서, 실무 종료 조건은 “최저값이 $k$ 회 연속 갱신되지 않으면 정지”다.

응용 영역은 대략 이렇다. 분자동역학·계산물리 쪽의 클러스터·결정 구조 예측과 포텐셜 에너지 표면 탐색, 조대 격자 모형에서의 단백질 접힘 구조 예측, 그리고 국소해가 많은 일반 공학 문제의 파라미터 적합. 어느 경우든 결과에 대한 정직한 표현은 “전역 최소를 찾았다”가 아니라 “추정 전역 최소(putative global minimum)” 다. 분지 도약은 최적성 증명을 전혀 제공하지 않는 메타휴리스틱이며, LJ 클러스터 문헌에서도 이 표현을 고집스럽게 쓴다.³

9. 여담[편집]

볼록 최적화의 세계에서는 국소 최소가 곧 전역 최소라 이 문서 전체가 무의미하다. 분지 도약이 필요하다는 것 자체가 문제가 비볼록임을 인정했다는 선언이다. 비볼록 문제를 만나면 먼저 볼록 완화가 가능한지 확인하고, 안 되면 그때 이런 도구를 꺼내는 순서가 맞다.
알고리즘이 20줄인데 30년 가까이 표준으로 살아남은 비결은 국소 최소화기의 발전을 공짜로 흡수한다는 데 있다. $\mathcal{L}$ 이 좋아지면 BH도 그만큼 좋아진다. 좋은 메타 알고리즘의 조건이 뭔지 보여주는 사례.⁴
이름이 “분지 도약”인데 정작 도약하는 것은 유역 사이가 아니라 점이다. 섭동된 점이 어느 유역에 떨어질지는 던져 봐야 안다. 흡인 유역 경계가 프랙탈인 문제에서는 이 “어디에 떨어지나”가 사실상 난수 생성기와 다를 바 없다.

10. 관련 문서[편집]

지역 최적해 · 흡인 유역 · 포텐셜 에너지 표면 · 안장점
담금질 모사 · 병렬 템퍼링 · 유전 알고리즘 · 입자 군집 최적화 · 타부 서치
볼록 최적화 · 확률적 경사하강법 · 준-뉴턴법
레너드-존스 퍼텐셜 · 분자동역학 · 계산물리 · 밀도범함수이론
마르코프 연쇄 몬테카를로 · 몬테카를로 방법 · 전역 최적화 · 메타휴리스틱 · 단백질 접힘

고유 구조 분해는 원래 액체와 유리의 열역학을 유역 단위로 재구성하기 위한 개념이었다. “상태를 세는 방법”을 “상태를 찾는 방법”으로 바꿔 쓴 것이 분지 도약의 발상 전환이고, 논문 한 편이 인용 수천을 먹는 종류의 전환이다. ↩
이런 재발견은 최적화 분야의 국룰에 가깝다. 같은 알고리즘이 분야마다 다른 이름을 달고 다니는 탓에, 새 논문을 읽을 때 “이거 내가 아는 그건데” 감각이 생기면 대체로 맞다. 문제는 그 감각이 생기기까지 논문을 백 편쯤 읽어야 한다는 것. ↩
LJ 클러스터 전역 최소 목록(케임브리지 클러스터 데이터베이스)은 지금도 갱신된다. 30년 넘게 “이게 최소다”라고 알려졌던 배열이 뒤집히는 일이 실제로 일어나므로, 논문에 “전역 최소를 찾았다”고 단정해 쓰면 나중에 곤란해진다. ↩
반대 사례도 많다. 국소 최소화기를 통째로 자기 내부에 재구현해 넣은 코드는 최적화 라이브러리가 발전해도 혜택을 못 받고 그대로 낡는다. 인터페이스만 잡고 알맹이는 갈아 끼울 수 있게 두는 것이 오래 사는 코드의 조건. ↩