위키백과, 무료 백과사전
타부 탐색법(Tabu search, TS)은 수학적 최적화에 사용되는 지역 탐색법을 사용하는 메타휴리스틱 탐색 방법이다. 1986년[1] 프렐드 W. 글로버에 의해 만들어졌고 1989년에 공식화되었다.[2][3]
지역(이웃) 탐색은 문제에 대한 잠재적인 솔루션을 선택하고 개선된 솔루션을 찾기 위해 바로 이웃(즉, 아주 소수의 사소한 세부 사항을 제외하고 유사한 솔루션)을 확인한다. 지역 탐색 방법은 최적이 아닌 지역이나 많은 솔루션이 동일하게 적합한 정체 상태에 머무르는 경향이 있다.
타부 탐색법은 기본 규칙을 완화하여 지역 탐색 성능을 향상시킨다. 첫째, 개선 가능한 이동이 없는 경우(예: 탐색이 엄격한 지역 최소값에 고정된 경우) 각 단계에서 악화되는 이동이 허용될 수 있다. 또한 이전에 방문한 솔루션으로 다시 탐색하는 것을 방지하기 위해 금지 사항(따라서 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
Seamless Wikipedia browsing. On steroids.