타부 서치

1. 개요

타부 서치(Tabu Search, TS)는 프레드 글로버가 1986년에 정식화한 메타휴리스틱으로, 지역 탐색이 방금 지나온 이동을 일정 기간 금지(taboo)해 같은 자리를 맴도는 것을 막는 방법이다. 핵심 아이디어는 한 문장으로 끝난다 — 더 나빠지더라도 이웃 중 가장 좋은 곳으로 반드시 이동하되, 방금 왔던 길은 잠시 막아 둔다.

담금질 모사가 “확률적으로 나쁜 이동을 받아들여” 국소 최적을 탈출한다면, 타부 서치는 결정론적 기억으로 같은 일을 한다. 동전을 던지는 대신 메모장을 든 셈이다.¹

2. 왜 금지 목록이 필요한가

순수한 최급강하 지역 탐색은 지역 최적해에 갇히면 끝이다. 그렇다고 “이웃 중 최선으로 무조건 이동”하도록 규칙을 바꾸면 더 나쁜 일이 생긴다. 국소 최적 $x^*$ 에서 나와 이웃 $y$ 로 갔다가, $y$ 의 이웃 중 최선이 다시 $x^*$ 이므로 되돌아오고, 다시 $y$ 로 가고 — 주기 2짜리 무한 루프에 빠진다.

타부 서치의 처방은 단순하다. $y$ 로 이동했다면 그 이동을 되돌리는 연산을 테뉴어(tenure) $t$ 회 반복 동안 금지 목록에 올린다. 되돌아갈 수 없으니 탐색은 강제로 새 영역으로 밀려나간다. 국소 최적은 이제 벽이 아니라 통과점이다.

3. 구성 요소

• 이웃 구조 $N(x)$: 무엇을 한 번의 “이동”으로 볼 것인가. 외판원 문제면 2-opt 간선 교환, 그래프 분할이면 정점 하나를 다른 파티션으로 옮기기, 일정계획이면 두 작업 순서 맞바꾸기.
• 타부 리스트: 무엇을 금지할지가 설계의 절반이다.
  • 해 기반: 방문한 해 전체를 저장. 정확하지만 메모리를 먹고 비교 비용이 크다.
  • 속성 기반: “간선 $(i,j)$ 를 다시 넣는 것”처럼 이동의 속성만 저장. 실전의 표준이다. 대신 같은 속성을 공유하는, 아직 안 가 본 해까지 덤으로 막히는 부작용이 생긴다.
• 테뉴어 $t$: 금지 기간. 너무 짧으면 순환이 다시 살아나고, 너무 길면 갈 곳이 없어 탐색이 굶는다. 문제 크기 $n$ 에 대해 $\sqrt{n}$ 근처를 쓰거나, 구간 안에서 무작위로 흔드는 반응형 타부 서치(Battiti–Tecchiolli)가 흔하다.²
• 열망 기준(aspiration criterion): 금지된 이동이라도 지금까지의 최선해보다 좋은 해를 만든다면 금지를 무시하고 실행한다. 속성 기반 리스트의 과잉 차단을 푸는 안전밸브라, 사실상 필수 장치다.

4. 최소 작동 예제 — 그래프 색칠

말로만 보면 추상적이니 구체적인 계를 하나 놓고 보자. 정점 $n$ 개 그래프를 $k$ 색으로 칠하되 같은 색으로 칠해진 인접 정점 쌍의 수를 목적함수로 두는 문제(TabuCol, 에르츠·드베르너 1987)다.

• 해: 각 정점에 색 하나를 배정한 벡터 $s\in\{1,\dots,k\}^n$.
• 목적함수 $f(s)$: 충돌 간선 수. $f=0$ 이면 정상적인 $k$-색칠을 찾은 것이다.
• 이웃: 충돌에 관여한 정점 $v$ 하나의 색을 $c$ 로 바꾼다. 충돌 없는 정점은 건드려 봐야 좋아질 리 없으므로 후보에서 뺀다 — 이것만으로 이웃 크기가 $O(nk)$ 에서 $O(|V_{\text{conf}}|k)$ 로 줄어든다.
• 타부 속성: 방금 $(v,c_{\text{old}})$ 를 떠났다면 “정점 $v$ 를 다시 $c_{\text{old}}$ 로” 를 $t$ 회 금지한다. 해 전체가 아니라 (정점, 색) 쌍 하나만 $n\times k$ 정수 배열에 “언제까지 금지”로 적어 두면 되므로, 금지 여부 판정이 $O(1)$ 이다.
• 열망: 그 이동이 지금까지의 최선 $f^\*$ 를 깬다면 금지를 무시한다.
• 증분 평가: $v$ 의 색을 바꿀 때 $\Delta f$ 는 $v$ 의 이웃만 보면 되므로 $O(\deg v)$ 다. 전체 $f$ 를 다시 세면 $O(|E|)$ 라, 이 차이가 곧 실행 시간의 차이가 된다.

전형적인 테뉴어는 $t = \alpha\,|V_{\text{conf}}| + \mathrm{rand}(0,10)$ 꼴로, 충돌이 많을수록 오래 금지한다. 문제 상태에 따라 금지 기간이 스스로 늘었다 줄었다 하는 이 형태가 고정 테뉴어보다 훨씬 튼튼하다.

5. 강화와 다양화

단기 기억(타부 리스트)만으로는 넓은 해 공간을 훑기 어렵다. 글로버의 원래 틀에는 장기 기억이 함께 들어 있다.

• 강화(intensification): 좋은 해들이 공유하는 구조를 찾아 그 근방을 집중 탐색한다. 엘리트 해 집합을 저장했다가 주기적으로 복귀하는 방식이 대표적이다.
• 다양화(diversification): 각 속성이 지금까지 몇 번 쓰였는지 빈도를 세어, 자주 쓰인 속성에 벌점을 매긴다. 탐색이 한 동네에 오래 머물수록 그 동네를 떠나라는 압력이 커진다.
• 경로 재연결(path relinking): 두 엘리트 해를 잇는 궤적 위의 중간 해들을 훑는다. 나중에 유전 알고리즘의 교차와 개념적으로 합류한 지점이다.

이웃 크기가 $O(n^2)$ 이상이면 매 반복 전수 평가가 병목이 된다. 그래서 후보 리스트 전략(유망한 부분집합만 평가)과 증분 평가(이동 전후의 목적함수 차이만 $O(1)$ 로 갱신)가 성능의 나머지 절반을 차지한다.

6. 다른 메타휴리스틱과의 관계

같은 문제를 놓고 계열별로 무엇이 다른지 정리하면 선택 기준이 선다.

• 담금질 모사: 이웃 하나를 무작위로 뽑아 확률적으로 수용. 기억이 없고(마르코프적), 파라미터가 냉각 일정 하나로 단순하다. 이웃 전수 평가가 비싼 문제에서는 오히려 이쪽이 유리하다.
• 타부 서치: 이웃을 (부분적으로) 전수 평가해 최선으로 결정론적 이동. 기억이 있다. 이웃 평가가 증분적으로 값싼 문제에서 강하다.
• 유전 알고리즘: 해 집단을 유지하며 재조합. 전역 구조를 섞는 데 강하지만 국소 정련이 약해, 실전에서는 각 개체에 지역 탐색을 붙인 메메틱 알고리즘 형태로 쓰인다. 그 지역 탐색 자리에 타부 서치가 들어가는 조합이 흔하다.
• 가변 이웃 탐색(VNS): 이웃 구조 자체를 여러 개 두고 갈아 끼운다. 타부 서치와 직교하는 아이디어라 함께 쓸 수 있다.

정리하면 타부 서치는 “이웃을 잘 정의할 수 있고 증분 평가가 싼 이산 문제” 의 기본기다. 연속 변수 문제에는 잘 맞지 않는다 — 무엇을 “금지”할지 정의하기가 애매해서, 굳이 쓰려면 변수 공간을 격자로 이산화하는 편법이 필요하다.

7. 성능과 한계

타부 서치는 1990년대에 여러 조합 최적화 벤치마크에서 최고 기록을 갈아치우며 이름을 알렸다. 특히 작업일정계획(job shop scheduling), 차량 경로 문제, 그래프 색칠, 2차 배정 문제에서 강했고, 지금도 이 계열 문제의 강력한 기준선이다. 유한요소 메시 생성 후의 도메인 분할이나 위상 최적화의 이산 변수 버전처럼 CAE 쪽 이산 문제에도 그대로 얹힌다.

솔직한 약점도 있다.

• 파라미터가 많다. 테뉴어, 열망 기준, 후보 리스트 크기, 빈도 벌점 가중치 — 문제마다 다시 맞춰야 하고, 잘 맞춘 타부 서치와 대충 맞춘 타부 서치의 격차가 크다.
• 수렴 보증이 없다. 담금질 모사는 (실용성 없는 냉각 일정에 한해) 전역 최적 수렴이 증명돼 있지만, 타부 서치에는 그런 정리가 없다. 하계도 주지 않으므로 나온 해가 최적 대비 얼마나 떨어졌는지 알 수 없다. 절단평면법이나 분지한정법으로 하계를 따로 뽑아 간극을 함께 보고하는 것이 성실한 태도다.
• 이웃 구조에 종속적이다. 좋은 이웃 정의가 없으면 어떤 기억 장치를 붙여도 소용없다. 결국 문제를 이해한 만큼 성능이 나온다.³

8. 관련 문서

• 조합 최적화 · 지역 최적해 · 최적설계
• 담금질 모사 · 유전 알고리즘 · 입자 군집 최적화
• 외판원 문제 · 정수계획법 · 분지한정법 · 절단평면법
• 위상 최적화 · 메시 생성

9. Footnotes

1. 글로버는 “tabu”라는 철자를 고집했다. 사전적으로 더 흔한 “taboo”가 아니라 폴리네시아어 원형에 가까운 쪽을 골랐다는데, 덕분에 검색할 때 두 철자를 다 넣어야 하는 소소한 세금이 40년째 부과되고 있다. ↩

2. 고정 테뉴어의 함정은 실습해 보면 바로 걸린다. 주기 $2t+2$ 짜리 긴 순환이 생겨서, 금지 목록이 멀쩡히 돌아가는데도 탐색이 큰 원을 그리며 제자리로 돌아온다. 로그를 찍어 보기 전까지는 “잘 돌아가는 중”으로 보이는 게 특히 얄밉다. ↩

3. 메타휴리스틱 전반에 해당하는 이야기지만, “No Free Lunch” 정리는 모든 문제에 대해 평균을 내면 어떤 탐색 알고리즘도 무작위 탐색과 같다고 말한다. 그러니까 타부 서치가 잘 듣는다는 건 알고리즘이 잘나서가 아니라 당신이 고른 이웃 구조가 그 문제의 구조와 맞아떨어졌다는 뜻이다. 칭찬은 이웃 구조에게. ↩