변수이웃탐색 (Variable Neighborhood Search)

한 줄 정의: 국소최적해에 갇히면 이웃 구조를 체계적으로 바꿔 가며 더 좋은 해를 찾는 메타휴리스틱입니다.

쉽게 풀면

해를 조금씩 바꿔 보는 탐색은 주변에 더 나은 해가 없으면 멈춥니다. 변수이웃탐색은 이때 '조금 바꾸기'의 방식 자체를 더 크게 바꿔 다른 곳으로 뛰어 본 뒤 다시 탐색합니다. 여러 크기의 이웃을 번갈아 쓰는 것이 핵심입니다.

왜 중요한가

구조가 단순하고 조정할 매개변수가 적어 차량경로·스케줄링·입지 문제 등 조합최적화 논문에서 널리 쓰입니다. 다른 메타휴리스틱과 결합한 혼합 기법의 뼈대로도 자주 등장합니다.

논문에서는 이렇게 쓰입니다

"초기해는 탐욕 규칙으로 생성하고, 세 가지 이웃 구조를 갖는 변수이웃탐색으로 개선하였다."

사용한 이웃 구조 수를 밝힌 예문입니다.

조금 더 깊게 보면

Mladenović와 Hansen(1997)이 제안했습니다. 기본 VNS는 k번째 이웃에서 무작위 해를 뽑는 흔들기(shaking), 국소탐색, 개선 시 k를 1로 되돌리고 아니면 k를 늘리는 이동 규칙으로 이뤄집니다. 국소탐색 없이 이웃만 바꾸는 축소형(RVNS), 국소탐색 단계에서 여러 이웃을 차례로 쓰는 변수이웃하강(VND) 같은 변형이 있습니다. 한 이웃에서의 국소최적이 다른 이웃에서는 아닐 수 있다는 관찰에 기반합니다.

주의할 점

타부탐색이 금지목록으로 되돌아가기를 막는 것과 달리, 변수이웃탐색은 이웃 구조를 바꾸는 방식으로 국소최적을 탈출합니다. 약어 VNS는 의학의 미주신경자극술과 같으므로 논문에서는 처음에 전체 이름을 적어 주는 것이 좋습니다.