타부탐색 (Tabu Search)
쉽게 풀면
미로를 탐색할 때 이미 지나온 길을 표시해두면 같은 곳을 반복해서 헤매지 않고 새로운 길을 찾는 데 집중할 수 있습니다. 타부탐색은 이와 비슷하게, 최근에 시도했던 해나 움직임을 잠시 '금지' 목록에 올려두어 그 자리로 곧바로 되돌아가지 못하게 합니다. 이렇게 하면 당장은 해가 나빠지는 방향으로 이동하더라도, 결국 더 넓은 영역을 탐색해 처음에 갇혔던 지역해를 벗어날 수 있습니다. 금지 목록은 영원히 유지되지 않고 일정 기간이 지나면 풀려서, 필요하면 다시 그 자리를 탐색할 수 있습니다.
왜 중요한가
단순한 탐색 기법들은 해가 더 나빠지는 방향으로는 움직이지 않기 때문에 국소적으로 가장 좋은 지점에 갇히기 쉽습니다. 타부탐색은 이런 한계를 극복하기 위해 고안된 방법으로, 산업공학의 스케줄링, 배치, 경로 최적화처럼 지역해가 많은 조합 최적화 문제에서 실용적인 성능을 보여 널리 활용됩니다.
논문에서는 이렇게 쓰입니다
처음 얻은 해가 국소적으로만 좋은 상태에 머물지 않도록 금지 목록을 활용해 더 나은 해로 이동했다는 뜻입니다.
금지 목록을 얼마나 오래 유지할지에 따라 탐색 결과가 어떻게 달라지는지 살펴봤다는 의미입니다.
조금 더 깊게 보면
타부탐색은 현재 해의 이웃 해들을 평가한 뒤, 금지 목록에 없는 것 중 가장 좋은 이웃으로 이동하는 방식으로 진행됩니다. 다만 특정 이동이 지금까지 발견된 것보다 훨씬 좋은 해로 이어진다면 금지를 해제하는 '열망 기준'을 함께 두는 경우가 많습니다. 금지 목록의 길이(타부 기간)를 어떻게 설정하느냐가 탐색의 다양성과 수렴 속도에 영향을 줍니다.
주의할 점
타부탐색도 전역 최적해를 항상 보장하지는 않으며, 금지 목록의 관리 방식과 문제의 이웃 구조 정의에 따라 성능 차이가 크게 날 수 있습니다.