📂최적화이론

최적화이론에서의 타부 탐색

용어

최적화 문제에 있어서 타부 탐색^{tabu search}이란, 말 그대로 금기^tabu 사항을 두어서 반복되는 탐색을 방지하는 메타-휴리스틱 기법이다.

설명

타부 탐색은 글로버^Glover에 의해 1986년 제안되었으며, 어떤 최적화 문제에서나 적용할 수 있기 때문에 메타-휴리스틱 기법이라 불린다¹. 타부 탐색이 정말로 주어진 문제에서 유용한가와는 별개로, 타부 탐색의 아이디어는 이론적인 배경이 어찌되든, 사용하려는 기법이 무엇이든간에 네이버후드^neighborhood와 타부 리스트^{tabu list}를 정의함에 따라 적용할 수 있다.

예를 들어 경로 최적화 문제가 있다면, 어떤 패스 $P$ 의 네이버후드는 에지가 하나씩만 다른 패스들의 집합으로 정의할 수 있을 것이다. 타부 서치를 경로 탐색에 적용한다는 것은 그 목적 함수의 값을 계산하며 네이버후드를 먼저 탐색하고, 그들 중 최적화에 도움이 되지 않는 패스들을 타부 리스트에 추가해가며 쓸데없는 계산을 피하는 식이다. 이렇게 아낀 자원들을 더 깊고 넓은 탐색에 투자함으로써, 결과적으로는 더 좋은 최적화를 추구한다.

목적함수가 유클리드 공간에서 연속함수라는 가정을 할 수 있다면, 우리는 굳이 함수값이 좋지 않은 곳을 꼼꼼히 탐색하는 것보다 조금이라도 가능성이 높은 곳을 탐색하는 편이 단기적으로 더 효율적일 수 있다. 최적화 측면에서 좋지 않은 해들을 타부 리스트에 추가해가며, 새로운 해의 후보가 타부 리스트 중 하나와 충분히 가깝다면―다시 말해 네이버후드에 들어간다면 굳이 그 해를 깊게 파고들 이유가 없다. 이렇듯 타부 탐색은 문제가 이산적인든 연속적이든, 어떤 방법을 사용하든 ‘굳이 더 탐색할 필요가 없는 곳’에 대한 개념만 명확하다면 어디에나 적용할 수 있다².