타부 탐색법(英: Tabu Search)은 메타휴리스틱 최적화 기법 중 하나로, 1980년대 초 프레드 G 러버(Fred G. Glover)가 개발하였다. 이름은 “taboo”(금지된, 금기된)에서 유래했으며, 탐색 과정에서 이미 방문한 해를 일시적으로 금지(tabu)함으로써 지역 최적에 머무는 현상을 방지한다.
핵심 원리
- 현재 해와 이웃 해: 현재 해(해답)에서 정의된 인접 연산자를 이용해 이웃 해 집합을 생성한다.
- 탐색: 이웃 해 중 목표 함수값이 가장 좋은 해를 후보 해로 선택한다.
- 타부 리스트: 최근에 수행한 이동(예: 변수 교환)이나 해 자체를 일정 기간 “타부” 상태로 기록한다. 타부 리스트에 포함된 이동은 일정 기간 동안 선택되지 않는다.
- 타부 조건 완화: 타부 리스트는 고정된 길이(또는 시간) 후에 자동으로 삭제되며, 새롭게 해가 탐색될 수 있다.
- 반복: 위 과정을 정해진 반복 횟수 또는 종료 조건(예: 일정 시간, 개선 없음)까지 반복한다.
특징
- 다양한 탐색: 타부 리스트가 해의 재방문을 제한하므로 탐색이 넓은 영역을 포괄한다.
- 전역 최적에 근접: 완전 탐색은 불가능한 큰 문제에서도 전역 최적에 가까운 해를 찾는 경우가 많다.
- 파라미터: 타부 리스트 길이, 이웃 연산자, 강인성(aspiration) 기준 등 여러 파라미터가 성능에 영향을 미친다.
- 강인성 조건: 타부 상태이더라도 현재 해보다 현저히 좋은 해가 발견되면 타부 제약을 무시하고 채택할 수 있다.
적용 분야
- 조합 최적화: 여행 판매원 문제(TSP), 작업 스케줄링, 배정 문제, 배치 설계 등.
- 공학 설계: 전력망 설계, 회로 배치, 물류 네트워크 최적화.
- 데이터 과학: 특징 선택, 클러스터링 파라미터 튜닝 등.
한글 명칭 및 어원
- “Tabu”는 프랑스어 “tabou”에서 차용된 단어로, ‘금기’·‘금지’를 의미한다. 한국어 표기 “타부”는 영어 발음을 음절 단위로 옮긴 형태이다.
- “탐색법”은 ‘search method’를 직역한 것으로, 전체 용어는 “Tabu Search”를 그대로 번역한 것이다.
참고 문헌 및 자료
- Glover, F. (1989). “Tabu Search — Part I”. ORSA Journal on Computing, 1(3), 190‑206.
- Glover, F., & Laguna, M. (1997). Tabu Search. Kluwer Academic Publishers.
- 한국정보과학회, “메타휴리스틱 알고리즘의 적용 사례” 등 학술지에 다수 보고서가 실려 있다.
(본 내용은 공개된 학술 자료와 일반적인 알고리즘 교재에 기반한 객관적 서술이며, 추가적인 상세 구현 방법은 해당 분야 전문 문헌을 참고한다.)
