405. 최적화 휴리스틱 타부 서치 (Tabu Search, 금기 탐색)

핵심 인사이트 (3줄 요약)

본질: 타부 서치(Tabu Search)는 지역 최적해(Local Minima)에 갇히는 것을 막기 위해, 한 번 가봤거나 나쁜 결과를 냈던 길(경로)을 '금기 목록(Tabu List)'에 적어두고 일정 기간 동안은 절대 그 길로 다시 돌아가지 못하게 강제하는 인간의 '단기 기억' 모방 알고리즘이다.

가치: 경사 하강법이나 일반적인 휴리스틱 탐색 기법들은 골짜기에 빠지면 방금 내려온 오르막길로 다시 올라갔다가 또 내려오는 멍청한 '무한 루프(Cycling)'에 빠지기 쉬운데, 타부 서치는 "방금 온 길은 10턴 동안 진입 금지!"라는 룰을 통해 탐색자가 억지로라도 새로운 길을 개척하도록 등을 떠민다.

판단 포인트: 금기 목록의 크기(Tabu Tenure)가 핵심인데, 목록이 너무 길면 탐색자가 갈 곳이 없어져 우주 미아가 되고, 너무 짧으면 금방 까먹고 다시 웅덩이로 빠지므로 도메인에 맞춰 인간의 단기 기억 용량(보통 7±2)처럼 적절한 제약을 설계해야 한다.

Ⅰ. 개요 및 필요성

로봇을 미로에 풀었다. 로봇은 눈앞에 보이는 길 중 '제일 넓은 길'로만 가도록 프로그래밍되어 있다(Hill Climbing, 탐욕적 탐색). 그런데 막다른 골목(Local Minima)에 도착했다. 로봇은 제일 넓은 길인 '방금 자신이 들어왔던 길'로 다시 나갔다가, "어? 저쪽이 제일 넓네?" 하고 다시 막다른 골목으로 들어온다. 영원한 무한 루프다.

이 바보 같은 로봇에게 인간의 지능을 하나 추가해 보자. "수첩을 하나 주고, 방금 지나온 3개의 길은 수첩에 적어놔. 그리고 수첩에 적힌 길은 아무리 넓어 보여도 3턴 동안은 절대 가지 마!" 이것이 바로 막다른 골목에서 로봇이 억지로 좁고 험한 샛길(오르막길)로 빠져나가게 만들어, 결국 미로의 진짜 출구(Global Minima)를 찾게 해주는 **타부 서치(Tabu Search)**의 본질이다.

📢 섹션 요약 비유: 쇼핑 중독자가 맨날 똑같은 백화점에 가서 과소비하는 걸 막으려고, 방금 방문한 백화점 3곳을 블랙리스트(Tabu List)에 올려서 출입을 금지시켜 억지로라도 새로운 시장(새로운 탐색 공간)을 구경하게 만드는 충동 통제 시스템이다.

Ⅱ. 아키텍처 및 핵심 원리

타부 서치는 기본적으로 '이웃 탐색(Local Search)'을 하면서, 기억(Memory)이라는 자료구조를 들고 다니는 아키텍처다.

┌────────────────────────────────────────────────────────┐
│             [ 타부 서치(Tabu Search)의 3대 핵심 컴포넌트 ]      │
├────────────────────────────────────────────────────────┤
│ 1. 이웃 탐색 (Neighborhood Search)                     │
│    - 현재 위치에서 한 걸음 갈 수 있는 모든 후보(이웃)를 평가    │
│    - 원칙: 내 주변에서 제일 좋은(점수 높은) 곳으로 일단 간다!   │
│                                                        │
│ 2. 금기 목록 (Tabu List) : 단기 기억 (Short-term Memory) │
│    - 방금 선택해서 이동한 길(행동)은 Tabu List에 올림        │
│    - 큐(Queue) 구조: 최근 5개의 행동만 기억함 (꽉 차면 옛날 건 지움)│
│    - 다음 탐색 때, 1등으로 좋은 길이라도 Tabu List에 있으면 무시함!│
│                                                        │
│ 3. 열망 조건 (Aspiration Criterion) : 예외 처리 룰        │
│    - "규칙은 깨라고 있는 것!"                               │
│    - Tabu List에 있는 금지된 길이라도, 그 길이 역대급 신기록     │
│      (Global Best)을 갱신하는 어마어마한 정답이라면?          │
│    - 금기를 깨고(예외 허용) 그 길로 가는 것을 허락함!           │
└────────────────────────────────────────────────────────┘

Tabu Tenure (금기 기간): 목록에 한 번 올라간 행동이 며칠 동안이나 금지당할지를 결정하는 변수다. Tenure가 10이면 최근 10번의 행동을 금지하는 것이다. (현업에서는 7~15 정도의 텐션을 주로 쓴다.)
장기 기억 (Long-term Memory): 단기 기억인 Tabu List 외에도 빈도 기반 기억을 쓸 수 있다. "지난 1,000턴 동안 A구역만 너무 많이 뒤졌네? 이제 A구역은 그만 가고 한 번도 안 가본 C구역으로 가보자!"라며 탐색의 다양성(Diversification)을 강제하는 고급 기법이다.

📢 섹션 요약 비유: 게임에서 방금 쓴 필살기에는 쿨타임(Tabu Tenure)이 돌아서 한동안 못 쓰는 것과 같다. 쿨타임 덕분에 유저(AI)는 얍삽한 기술 하나만 쓰며 정체되는 걸 멈추고, 억지로라도 여러 가지 다양한 콤보(새로운 최적해 탐색)를 시도하게 된다.

Ⅲ. 비교 및 연결

NP-Hard 문제를 부수기 위한 3대 메타 휴리스틱 알고리즘의 'Local Minima(웅덩이) 탈출 전략'을 비교해 본다.

비교 항목	유전 알고리즘 (GA)	시뮬레이티드 어닐링 (SA)	타부 서치 (Tabu Search)
탈출 전략	1% 확률의 돌연변이(Mutation)	고온일 때 더 나쁜 곳으로 점프 허용	나쁜 길이라도 좋으니 과거의 길은 피해서 전진
기억력 (Memory)	유전자에 흔적이 남지만 의도적 기억은 아님	없음 (방금 전 상태 1개만 앎)	있음 (최근 수십 턴의 과거 행동을 완벽히 기억)
탐색 방식	수천 개의 헬기를 띄우는 전역 탐색	1명이 미친 듯이 튕기며 탐색	1명이 수첩에 오답 노트를 쓰며 꼼꼼히 탐색
최적 활용처	설계, 병렬 최적화	칩셋 레이아웃 설계	외판원 순회(TSP), 차량 경로 배차(VRP)

SA(모의 담금질)는 주사위를 던지는 완벽한 확률(Random) 게임이다. 반면 타부 서치는 무작위성이 아니라 "기억된 리스트를 피한다"는 지독하게 논리적이고 결정론적인(Deterministic) 탐색을 수행한다. 그래서 휴리스틱 중에서도 가장 이지적이고 꼼꼼한 알고리즘으로 평가받는다.

📢 섹션 요약 비유: 길을 잃었을 때 GA가 군인을 1,000명 풀어 산을 다 뒤집는 거고, SA가 눈 감고 이리저리 미친 듯이 뛰어다녀 보는 거라면, 타부 서치는 지도를 들고 "여긴 아까 가봤으니 X표 쳐놓자"며 차근차근 소거법으로 길을 찾는 탐험가다.

Ⅳ. 실무 적용 및 기술사 판단

실무 적용 시나리오: 쿠팡 로켓배송의 트럭 배차 시스템(VRP, Vehicle Routing Problem)이다. 트럭 100대가 서울 시내 1만 개의 아파트를 돌아야 한다. 데이터 과학자는 경로의 거리를 줄이기 위해 파이썬으로 2-opt(두 경로를 엑스자로 꼬아보는 것) 이웃 탐색에 Tabu Search를 결합한다. "A아파트 다음 B아파트를 가는 경로"를 50턴 동안 금지(Tabu List)시켜버리자, 알고리즘은 억지로 C아파트를 거쳐 가는 새로운 우회로를 시도하게 되고, 결국 기존 배송망보다 거리가 10km나 단축된 새로운 글로벌 최적해를 찾아낸다.

기술사 판단 포인트 (Trade-off): 타부 서치 아키텍처 설계 시 기술사는 '금기 대상(What to Tabu)'의 메모리 비용을 완벽하게 계산해야 한다.

"A $\rightarrow$ B $\rightarrow$ C 경로 전체"를 금기 목록에 넣으면 메모리가 터지고 목록이 너무 커져서 탐색이 막힌다.
따라서 기술사는 경로 자체가 아니라, **"방금 맞바꾼 행위(예: A와 B의 순서를 스왑함)"**라는 아주 작은 속성(Attribute)만을 금기 목록에 저장해야 한다.
속성만 금지하면 메모리는 몇 바이트밖에 먹지 않으면서도, 알고리즘이 똑같은 짓을 반복하는(Cycling) 것을 완벽하게 막아내는 가성비 최고의 메타 휴리스틱 파이프라인이 완성된다.

📢 섹션 요약 비유: 범죄자를 막기 위해 "검은 모자에 선글라스를 끼고 키 180인 30대 남자"를 블랙리스트에 올리면 방어막이 너무 좁아 다른 범죄자가 뚫고 온다. 그냥 "검은 모자 쓴 사람 5일간 출입 금지"라는 단일 속성만 룰로 정하는 게 시스템 부하도 적고 통제도 쉽다.

Ⅴ. 기대효과 및 결론

타부 서치(Tabu Search)는 기계 학습에 '기억(Memory)'이라는 인간의 인지적 특성을 부여한 최적화 알고리즘의 진주다. 무작위 주사위 던지기(SA, GA)에 의존하던 메타 휴리스틱 세계에, 논리적이고 체계적인 인공지능의 시각을 던져주었다.

결론적으로 타부 서치는 딥러닝에 가려져 대중적인 인지도는 낮지만, 제조업의 공정 스케줄링(Job-shop Scheduling)이나 통신망 라우팅처럼 '수조 개의 제약 조건이 얽혀 수학으로는 절대 풀 수 없는' 현실 세계의 B2B 솔루션 뒤에서 가장 조용히, 그리고 가장 강력하게 세상을 돌리고 있는 진짜 돈을 버는 코어 엔진이다. 기술사는 아무리 딥러닝이 화려해도, 순서(Permutation)를 섞어서 최적화해야 하는 문제 앞에서는 주저 없이 이 '수첩을 든 탐험가'를 소환해야 한다.

📢 섹션 요약 비유: 딥러닝이 방대한 데이터의 바다에서 1초 만에 얼굴을 찾아내는 화려한 전투기 조종사라면, 타부 서치는 좁고 복잡한 하수구 미로 속에서 오답 노트를 꼼꼼히 적어가며 막힌 파이프(최적해)를 기어코 뚫어내는 전설적인 배관공이다.

📌 관련 개념 맵

상위 개념: 메타 휴리스틱 (Meta-Heuristic), 조합 최적화 (Combinatorial Optimization)
하위 개념: 단기 기억 (Tabu List), 열망 조건 (Aspiration Criterion), 이웃 탐색 (Local Search)
연결 개념: 시뮬레이티드 어닐링 (SA), 유전 알고리즘 (GA), 외판원 순회 문제 (TSP)

👶 어린이를 위한 3줄 비유 설명

로봇이 미로를 빠져나가려는데, 길이 막히면 뒤로 한 칸 왔다가 다시 그 좁은 골목으로 들어가는 바보 같은 짓을 계속 반복해요.
그래서 로봇에게 오답 노트를 쥐여 주고 "방금 가본 길은 아무리 좋아 보여도 10분 동안은 절대 들어가지 마!"라고 규칙을 정해줬어요.
로봇은 억지로라도 새로운 좁은 길(오르막길)로 갈 수밖에 없었고, 결국 그 길 끝에서 진짜 미로의 출구를 찾아냈답니다!