타부 검색

Tabu search

타부 검색은 수학 최적화에 사용되는 지역 검색 방법을 채택한 메타휴리스틱 검색 방법이다. 1986년[1] 프레드 W. 글로버에 의해 만들어졌고 1989년에 공식화되었다.[2][3]

로컬(이웃) 검색은 문제에 대한 잠재적 해결책을 취하고 개선된 해결책을 찾기를 바라면서 문제의 가까운 이웃(즉, 사소한 세부사항을 거의 제외하고 비슷한 해결책)을 점검한다. 국지적 검색 방법은 최적 수준이 낮은 지역이나 많은 솔루션이 동등하게 적합한 고지에 고착되는 경향이 있다.

타부 검색은 기본 규칙을 완화하여 로컬 검색의 성능을 향상시킨다. 첫째, 각 단계에서 (수색이 엄격한 국지적 최소치로 고착된 경우처럼) 개선 조치를 사용할 수 없는 경우 악화되는 움직임을 허용할 수 있다. 또한, 검색이 이전에 방문했던 해결책으로 되돌아오는 것을 막기 위해 금지령(tabu라는 용어를 사용함)이 도입된다.

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

배경

타부라는 단어는 통란어에서 유래하여 신성한 것이기 때문에 만질 수 없는 것을 가리키는 말이다.[4]

타부 검색(TS)은 결합 최적화 문제(최적적인 옵션 순서와 선택이 필요한 문제)를 해결하는 데 사용할 수 있는 메타휴리스틱 알고리즘이다.

TS의 현재 적용 분야는 자원 계획, 통신, VLSI 설계, 재무 분석, 스케줄링, 공간 계획, 에너지 분배, 분자 공학, 물류, 패턴 분류, 유연한 제조, 폐기물 관리, 광물 탐사, 생물의학 분석, 환경 보존 및 o의 점수 분야에 걸쳐 있다.최근 몇 년 동안, 다양한 분야의 저널들은 효과적으로 처리할 수 있는 문제들의 경계를 넓히는데 있어서 타부 검색에 의한 성공을 기록한 튜토리얼 기사와 계산 연구를 발표하였다. 즉, 이전에 적용했던 방법들에 의해 얻어진 것을 훨씬 능가하는 품질의 해결책을 내놓는다. 실제 구현을 통해 얻은 이익에 대한 요약 설명을 포함한 포괄적인 애플리케이션 목록은 다음에서 확인할 수 있다.

기본설명

Tabu 검색은 일부 중지 기준(일반적으로 시도 제한 또는 점수 임계값)이 충족될 때까지 또는 인접 검색 절차를 사용하여 x x의 하나의 잠재적 솔루션 x에서 개선된 솔루션 {\ x으)로 반복적으로 이동한다. 지역 검색 절차는 점수가 낮은 지역이나 점수가 높은 지역에 종종 고착된다. 이러한 함정을 피하고 다른 지역 검색 절차에서 미개척된 검색 공간의 지역을 탐색하기 위해 타부 검색은 검색이 진행됨에 따라 각 해결책의 주변을 주의 깊게 탐색한다. 새로운 이웃인 ( ) 에 인정된 해결책은 메모리 구조의 사용을 통해 결정된다. 이러한 메모리 구조를 사용하여 검색은 현재 x 에서 () 의 향상된 솔루션 x으)로 반복적으로 이동함으로써 진행된다.

Tabu 검색은 시뮬레이션된 어닐링과 몇 가지 유사성을 가지고 있는데, 둘 다 언덕 아래로 이동할 수 있기 때문이다. 사실, 시뮬레이션된 어닐링은 특별한 형태의 TS로 볼 수 있는데, 여기서 우리는 "졸업된 종신 재직권"을 사용함으로써, 즉, 이동은 특정한 확률을 가진 타부가 된다.

이러한 메모리 구조는 Tabu 목록으로 알려진 것, 규칙 집합 및 검색에 의해 탐색될 ){\ N에 어떤 솔루션이 허용될 것인지를 필터링하는 데 사용되는 금지된 솔루션을 형성한다. 가장 간단한 형태에서, tabu 목록은 최근 방문한 솔루션들의 단기 집합이다({\개 이전 반복보다 작음, 서n {\은 저장해야 할 이전 솔루션 수(tabu tenergy라고도 함). 더 일반적으로, 타부 리스트는 한 솔루션에서 다른 솔루션으로 이동하는 과정에 의해 변경된 솔루션으로 구성된다. 코딩되고 그러한 속성으로 표현되는 "솔루션"을 이해하는 것은 설명하기 쉽도록 편리하다.

메모리 종류

타부 검색에 사용되는 메모리 구조는 대략 다음과 같은 세 가지 범주로 나눌 수 있다.[6]

  • 단기: 최근 고려된 해결책 목록. 타부 목록에 잠재적 해결책이 나타나면 만료점에 도달할 때까지 재방문할 수 없다.
  • 중간 기간: 검색 공간의 유망한 영역으로 검색을 치우치기 위한 강화 규칙.
  • 장기: 검색을 새로운 영역으로 유도하는 다양화 규칙(즉, 검색이 고원 또는 차선의 데드엔드에 고착되는 경우 리셋에 관한 규칙).

단기, 중기, 장기기억은 실무에서 중복될 수 있다. 이러한 범주 내에서 메모리는 변경의 빈도 및 영향과 같은 조치에 의해 더욱 구별될 수 있다. 중기 메모리 구조의 한 예는 특정 속성(예: 특정 변수에 대해 바람직하지 않거나 바람직한 값을 포함하는 솔루션)을 포함하는 솔루션이나 특정 이동을 방지하거나 유도하는 메모리 구조(예: 의 솔루션 공유 기능에 적용되는 주파수 메모리에 기반)를 금지하거나 권장하는 것이다. 과거에 발견된 매력적이지 않거나 매력적인 해결책과 공통적인 것). 단기 메모리에서는 최근 방문한 솔루션에서 선택된 속성은 "tabu-active"라는 레이블이 붙는다. tabu-active 요소를 포함하는 솔루션은 금지된다. 흡인 기준은 솔루션의 타부 상태를 재정의하기 위해 사용되며, 따라서 허용된 집합에 제외된 용액을 포함한다(용액이 품질 또는 다양성의 측정에 따라 "충분히 양호"할 경우). 단순하고 일반적으로 사용되는 흡인 기준은 현재 가장 잘 알려진 솔루션보다 더 나은 솔루션을 허용하는 것이다.


단기 기억력만으로도 기존의 현지 검색 방식에 의해 발견된 것보다 우수한 솔루션을 달성하기에 충분할 수 있지만, 더 어려운 문제를 해결하기 위해서는 중·장기 구조가 필요한 경우가 많다.[7] Tabu 검색은 종종 시뮬레이션 어닐링, 유전자 알고리즘, 개미 군집 최적화 알고리즘, 반응형 검색 최적화, 유도형 로컬 검색 또는 탐욕스러운 무작위 적응형 검색과 같은 다른 메타휴리스틱 방법에 대해 벤치마킹된다. 또한, 타부 검색은 때때로 다른 메타휴리스틱스와 결합되어 하이브리드 방법을 만든다. 가장 일반적인 타부 검색 하이브리드는 타부 검색과 공통점을 갖는 인구 기반 절차의 한 종류인 [8][9]분산 검색과 TS를 결합함으로써 발생하며, 대형 비선형 최적화 문제를 해결하는 데 종종 사용된다.

가성음

다음의 유사코드는 위에서 설명한 바와 같이 타부 검색 알고리즘의 단순화된 버전을 나타낸다. 이 구현은 초보적인 단기 기억력을 가지고 있지만, 중장기 기억 구조를 포함하고 있지 않다. "능력"이란 수학적 최적화를 위한 객관적 함수로 구체화된 후보 해법에 대한 평가를 말한다. 

sbest ← s0 베스트 캔디다이트 ← s0 tabuList ← [] tabuList.밀다(s0) 하는 동안에 (아닌 정지조건())     이웃나라 ← getNeighbors(베스트 캔디다이트)     베스트 캔디다이트 ← 이웃나라[0]     을 위해 (칸디다테 에 이웃나라)         만일 ( (아닌 tabuList.포함하다(칸디다테)) 그리고 (피트니스(칸디다테) > 피트니스(베스트 캔디다이트)) )             베스트 캔디다이트 ← 칸디다테         종지부를 찍다     종지부를 찍다     만일 (피트니스(베스트 캔디다이트) > 피트니스(sbest))         sbest ← 베스트 캔디다이트     종지부를 찍다     tabuList.밀다(베스트 캔디다이트)     만일 (tabuList.사이즈를 맞추다 > maxTabuSize)         tabuList.먼저 제거()     종지부를 찍다 종지부를 찍다 돌아오다 sbest

라인 1-4는 초기 설정을 나타내며, 각각 초기 솔루션(아마도 무작위로 선택됨), 초기 솔루션을 현재까지 가장 잘 알려진 솔루션으로 설정하고, 이 초기 솔루션으로 타부 리스트를 초기화한다. 이 예에서 타부 목록은 단순히 방문한 주의 요소에 대한 기록을 포함할 단기 기억 구조일 뿐이다.

핵심 알고리즘 루프는 5행에서 시작한다. 이 루프는 사용자가 지정한 정지 조건이 충족될 때까지 최적의 솔루션을 계속 검색할 것이다(이러한 조건의 두 가지 예는 간단한 시간 제한 또는 피트니스 점수의 임계값이다). 주변 솔루션은 9행의 타부 요소를 점검한다. 또한 알고리즘은 타부(tabu)가 아닌 인접 지역에서 가장 좋은 솔루션을 추적한다.

피트니스 함수는 일반적으로 수학 함수로서, 점수를 반환하거나 흡인 기준이 충족된다. 예를 들어, 흡인 기준은[4] 새로운 검색 공간이 발견되는 것으로 간주될 수 있다. 지역 최고의 후보가 현재 최고(13라인)보다 체력적 가치가 높을 경우, 새로운 최고(14라인)로 설정된다. 지역 최고의 후보는 항상 타부 리스트(16줄)에 추가되며, 타부 리스트가 꽉 차면(17줄) 일부 요소가 만료될 수 있다(18줄). 일반적으로 요소들은 추가된 순서와 동일한 순서에 따라 목록에서 만료된다. 이 절차는 지역 최적에서 벗어나기 위해 지역 최고의 후보(sBest보다 체력이 더 좋지 않음)를 선정한다.

이 프로세스는 사용자가 지정한 정지 기준을 충족할 때까지 계속되며, 이 시점에서 검색 프로세스 중에 확인된 최선의 해결책이 반환된다(라인 21).

예: 출장 판매원 문제

여행 판매원 문제(TSP)는 타부 검색의 기능을 보여주기 위해 사용되기도 한다.[7] 이 문제는 간단한 질문을 던진다. 도시 목록을 보면, 모든 도시를 방문하는 가장 짧은 경로는 무엇인가? 예를 들어 A시와 B시가 나란히 있고 C시가 더 멀다면 C시를 방문하기 전에 A시와 B시를 차례로 방문하면 총 이동거리가 짧아진다. 최적의 솔루션을 찾는 것이 NP-hard이기 때문에 휴리스틱스 기반의 근사법(로컬 검색 등)은 최적화에 가까운 솔루션을 고안하는 데 유용하다. 좋은 TSP 솔루션을 얻기 위해서는 그래프 구조를 이용하는 것이 필수적이다. 문제 구조를 악용하는 가치는 메타휴리스틱 방법에서 되풀이되는 테마로, 타부 검색은 이에 잘 맞는다. ejection chain method라고 불리는 tabu 검색과 관련된 일련의 전략들은 고품질 TSP 솔루션을 효율적으로 얻을 수 있게 만들었다.

한편, 간단한 타부 검색은 여행 판매원 문제에 대한 만족스러운 해결책(즉, 그래프 구조를 이용하여 얻은 높은 품질은 아니지만 적정성 기준을 만족하는 해결책)을 찾는 데 사용될 수 있다. 검색은 임의로 또는 가장 가까운 이웃 알고리즘에 따라 생성될 수 있는 초기 솔루션으로 시작한다. 새로운 솔루션을 만들기 위해 두 도시를 잠재적 솔루션으로 방문하라는 순서가 바뀐다. 모든 도시 사이의 총 이동 거리는 한 해결책이 다른 해결책에 비해 얼마나 이상적인지를 판단하는 데 사용된다. 사이클(즉, 특정 솔루션 세트를 반복적으로 방문)을 방지하고 로컬 최적화에 고착되지 않도록 솔루션 인접 (x ) N에 수용되는 경우 솔루션을 타부 목록에 추가한다

임의의 반복 횟수와 같은 일부 정지 기준이 충족될 때까지 새로운 해결책이 만들어진다. 단순 타부 검색이 중지되면 실행 중에 발견된 최상의 솔루션을 반환한다.

참조

  1. ^ Fred Glover (1986). "Future Paths for Integer Programming and Links to Artificial Intelligence". Computers and Operations Research. 13 (5): 533–549. doi:10.1016/0305-0548(86)90048-1.
  2. ^ a b Fred Glover (1989). "Tabu Search – Part 1". ORSA Journal on Computing. 1 (2): 190–206. doi:10.1287/ijoc.1.3.190.
  3. ^ Fred Glover (1990). "Tabu Search – Part 2". ORSA Journal on Computing. 2 (1): 4–32. doi:10.1287/ijoc.2.1.4.
  4. ^ a b "Courses" (PDF).
  5. ^ F. Glover; M. Laguna (1997). Tabu Search. Kluwer Academic Publishers. ISBN 978-1-4613-7987-4.
  6. ^ Fred Glover (1990). "Tabu Search: A Tutorial". Interfaces.
  7. ^ a b M. Malek; M. Huruswamy; H. Owens; M. Pandya (1989). "Serial and parallel search techniques for the traveling salesman problem". Annals of OR: Linkages with Artificial Intelligence.
  8. ^ F. Glover, M. Laguna & R. Marti (2000). "Fundamentals of Scatter Search and Path Relinking". Control and Cybernetics. 29 (3): 653–684.
  9. ^ M. Laguna & R. Marti (2003). Scatter Search: Methodology and Implementations in C. Kluwer Academic Publishers. ISBN 9781402073762.
  10. ^ D. Gamboa, C. Rego & F. Glover (2005). "Data Structures and Ejection Chains for Solving Large Scale Traveling Salesman Problems". European Journal of Operational Research. 160 (1): 154–171. CiteSeerX 10.1.1.417.9789. doi:10.1016/j.ejor.2004.04.023.

외부 링크