반복된 로컬 검색

반복 로컬 검색^[1][2](ILS)은 이산적 최적화 문제를 해결하기 위해 로컬 검색이나 힐 클라이밍 방법의 수정을 정의하는 응용 수학 및 컴퓨터 과학 용어다.

현지 검색 방법은 개선되는 이웃이 없는 지역적 최소치에 걸릴 수 있다.

단순 수정은 다른 초기 구성에서 시작할 때마다 로컬 검색 루틴에 대한 반복 호출로 구성된다.이를 반복된 로컬 검색이라고 하며, 이전 로컬 검색 단계에서 얻은 지식이 사용되지 않음을 암시한다.학습은 예를 들어 이전에 발견된 지역 미니마에 대한 기억과 같은 이전 역사를 채굴하여 지역 검색을 위한 더 좋고 더 나은 출발점을 만들어 낸다는 것을 암시한다.

암묵적 가정은 국소 미니마의 군집화된 분포의 것이다. 함수를 최소화할 때, 좋은 국소 최소값을 무작위 지점에서 시작할 때보다 낮은 값을 가진 국소 최소값에서 시작할 때 좋은 국소 미니마를 결정하는 것이 더 쉽다.유일한 주의사항은 주어진 유인 유역에 구속되지 않도록 하는 것이다. 따라서 국소 최소 장치를 다음 주행을 위한 출발점으로 변환하기 위한 킥은 적절하게 강해야 하지만 너무 강하면 메모리가 없는 무작위 재시작으로 되돌아가지 않도록 한다.

반복된 로컬 검색은 다음을 통해 로컬에서 최적의 솔루션을 구축하는 것을 기반으로 한다.

1. 현재 국소 최소값을 혼란스럽게 하는 경우
2. 수정된 솔루션에서 시작한 후 로컬 검색 적용.

섭동 강도는 궤적을 다른 지역 최적지로 유도하는 다른 유인 분지로 유도하기에 충분해야 한다.

섭동 알고리즘

ILS를 위한 섭동 알고리즘은 쉬운 일이 아니다.주 목적은 동일한 지역적 최소치에 걸리지 않는 것이며, 이 속성을 실현하기 위해 실행 취소 작업이 금지된다.그럼에도 불구하고, 좋은 순열은 두 가지 종류의 나쁜 순열이 있기 때문에 많은 가치를 고려해야 한다.

1. 너무 약함: 동일한 국소 최소값으로 다시 떨어짐
2. 너무 강력함: 임의 재시작

벤치마크 섭동

이 절차는 이 값들이 예를 들어 평균 확률과 드물지 않게 유의하도록 섭동에 대한 여러 값을 고정하는 것으로 구성된다.그 후, 통과된 인스턴스에 대한 평균적인 아이디어를 얻기 위해 런타임에 벤치마크 플롯을 확인할 수 있을 것이다.

적응 섭동

어떤 것이 주어진 섭동에 가장 적합한 값인지를 알려주는 선행 기능이 없기 때문에, 가장 좋은 기준은 그것을 적응시키는 것이다.예를 들어 Battiti와 Protasi는 ILS 프레임워크에 완벽하게 맞는 MAX-SAT에 대한 대응형 검색 알고리즘을 제안했다.그들은 타부 검색 알고리즘에 의해 구현되는 "방향" 섭동 계획을 수행하고 각 섭동 후에는 표준 국부 강하 알고리즘을 적용한다.섭동을 적응시키는 또 다른 방법은 수색 중에 결정적으로 강도를 바꾸는 것이다.

섭동 최적화

또 다른 절차는 문제의 하위 부분을 최적화하는 것이다. 그렇지 않은 속성이 계속 활성화되도록 하는 것이다.만약 이 절차가 가능하다면, 섭동 후에 생성된 모든 해결책은 매우 좋은 경향이 있다.게다가 새로운 부품들도 최적화되어 있다.

결론들

이 방법은 잡샵 스케줄링 문제,^[3][4] 플로우 샵 문제,^[5] 차량 라우팅^[6] 문제 등 여러 조합 최적화 문제에 적용되었다.

참조

^[1]