타부 탐색법

타부 탐색법(Tabu search, TS)은 수학적 최적화에 사용되는 지역 탐색법을 사용하는 메타휴리스틱 탐색 방법이다. 1986년 프렐드 W. 글로버에 의해 만들어졌고 1989년에 공식화되었다.

지역(이웃) 탐색은 문제에 대한 잠재적인 솔루션을 선택하고 개선된 솔루션을 찾기 위해 바로 이웃(즉, 아주 소수의 사소한 세부 사항을 제외하고 유사한 솔루션)을 확인한다. 지역 탐색 방법은 최적이 아닌 지역이나 많은 솔루션이 동일하게 적합한 정체 상태에 머무르는 경향이 있다.

타부 탐색법은 기본 규칙을 완화하여 지역 탐색 성능을 향상시킨다. 첫째, 개선 가능한 이동이 없는 경우(예: 탐색이 엄격한 지역 최소값에 고정된 경우) 각 단계에서 악화되는 이동이 허용될 수 있다. 또한 이전에 방문한 솔루션으로 다시 탐색하는 것을 방지하기 위해 금지 사항(따라서 tabu라는 용어)이 도입되었다.

타부 탐색의 구현은 방문한 솔루션이나 사용자가 제공한 규칙 집합을 설명하는 메모리 구조를 사용한다. 특정 단기 기간 내에 이전에 잠재적인 솔루션을 방문했거나 규칙을 위반한 경우 알고리즘이 해당 가능성을 반복적으로 고려하지 않도록 "타부"(tabu, 금기)로 표시된다.

 의사 코드 
sBest ← s0
bestCandidate ← s0
tabuList ← []
tabuList.push(s0)
while (not stoppingCondition())
    sNeighborhood ← getNeighbors(bestCandidate)
    bestCandidateFitness ← -∞
    for (sCandidate in sNeighborhood)
        if ( (not tabuList.contains(sCandidate))
            and (fitness(sCandidate) > bestCandidateFitness) )
            bestCandidate ← sCandidate
            bestCandidateFitness ← fitness(bestCandidate)
        end
    end
    if (bestCandidateFitness is -∞)
        break;
    end
    if (bestCandidateFitness > fitness(sBest))
        sBest ← bestCandidate
    end
    tabuList.push(bestCandidate)
    if (tabuList.size > maxTabuSize)
        tabuList.removeFirst()
    end
end
return sBest

 각주 

 외부 링크 
 Visualization of the Tabu search algorithm (Applet)
 Metaheuristic International Conference (MIC 2011) – Udine
 The Reactive Search Community 
 LION Conference on Learning and Intelligent Optimization techniques 

분류:1989년 도입
분류:검색 알고리즘
분류:메타휴리스틱