국소 탐색

국소 탐색은 최적화 문제를 해결하기 위한 메타휴리스틱 접근법으로, 탐색 과정의 핵심은 '탐색 공간'과 '이웃'이라는 개념에 기반한다. 탐색 공간은 문제의 모든 가능한 해, 즉 후보해의 집합을 의미한다. 이 공간은 문제의 제약 조건을 만족하는 해들로 구성되며, 그 크기는 문제의 복잡도에 따라 유한하거나 무한할 수 있다. 예를 들어, 외판원 문제에서 탐색 공간은 모든 가능한 도시 방문 순서의 집합이다.

이러한 탐색 공간 내에서 알고리즘은 항상 하나의 '현재 해'를 유지하며 작동한다. 국소 탐색의 기본 아이디어는 현재 해를 완전히 버리고 새로운 해를 찾는 것이 아니라, 현재 해 주변의 유사한 해들을 살펴보면서 점진적으로 개선해 나가는 것이다. 이때 '이웃'이란 현재 해로부터 작은 변화를 통해 도달할 수 있는 다른 모든 해들의 집합을 지칭한다. 이 변화를 정의하는 규칙을 '이웃 구조'라고 하며, 이는 알고리즘의 성능을 결정하는 중요한 요소이다.

예를 들어, 이진수 문자열로 표현된 해에서 이웃 구조는 "한 비트를 뒤집는다"로 정의될 수 있다. 이 경우, 3비트 문자열 '010'의 이웃은 '110', '000', '011'이 된다. 조합 최적화 문제에서는 두 도시의 방문 순서를 교환하는 방식이 흔히 사용되는 이웃 구조이다. 이웃 구조는 탐색의 세밀함과 효율성을 동시에 고려하여 설계되며, 너무 크면 탐색이 비효율적이고 너무 작으면 지역 최적해에서 벗어나기 어려워진다.

따라서, 탐색 공간과 이웃 구조의 정의는 국소 탐색 알고리즘을 설계하는 첫 단계이다. 알고리즘은 이 정의된 이웃 내에서 목적 함수 값을 평가하며, 더 나은 해를 발견하면 현재 해를 그 해로 이동시키는 과정을 반복한다. 이 과정을 통해 알고리즘은 탐색 공간의 일부 지역을 집중적으로 탐사하게 된다.

목적 함수는 국소 탐색 알고리즘에서 탐색의 방향과 성공 여부를 결정하는 핵심 척도이다. 이 함수는 주어진 해에 대해 그 해의 품질이나 비용을 수치적으로 평가하는 역할을 한다. 국소 탐색은 현재 해의 이웃 해를 생성하고, 이웃 해의 목적 함수 값을 계산하여 현재 해보다 더 나은(더 높은 품질 또는 더 낮은 비용) 해를 선택하는 과정을 반복한다. 따라서 목적 함수의 설계와 계산 효율성은 알고리즘의 전체 성능에 직접적인 영향을 미친다.

목적 함수의 형태는 문제의 특성에 따라 다양하다. 조합 최적화 문제에서는 일반적으로 총 비용을 최소화하거나 총 이익을 최대화하는 함수를 정의한다. 예를 들어, 외판원 문제에서는 이동 경로의 총 거리를, 작업 스케줄링 문제에서는 모든 작업이 완료되는 시간을 목적 함수로 설정한다. 기계 학습에서는 모델의 매개변수를 조정하여 손실 함수라는 특수한 형태의 목적 함수 값을 최소화하는 과정이 국소 탐색의 일종으로 볼 수 있다.

국소 탐색 알고리즘은 목적 함수 값의 개선을 유일한 탐색 기준으로 삼기 때문에, 이 함수의 지형도가 알고리즘의 동작을 결정한다. 목적 함수 값이 지역 최적해에 빠지면, 그 지점 주변의 모든 이웃 해가 현재 해보다 나쁘기 때문에 알고리즘이 더 이상 진전을 이루지 못하고 정지하게 된다. 이러한 한계를 극복하기 위해 시뮬레이티드 어닐링이나 탭 서치 같은 고급 메타휴리스틱은 일시적으로 목적 함수 값이 나빠지는 이동을 허용하여 지역 최적해에서 탈출할 기회를 제공한다.

국소 탐색에서 탐색의 궁극적 목표는 문제의 최적해를 찾는 것이다. 최적해는 주어진 목적 함수를 최대화하거나 최소화하는, 탐색 공간 내의 모든 가능한 해 중 가장 좋은 해를 의미한다. 그러나 많은 실제 문제, 특히 조합 최적화 문제에서는 탐색 공간이 너무 방대하여 모든 해를 평가해 보는 것이 불가능하므로, 전역 최적해를 보장하는 해를 찾는 것은 매우 어렵다.

이에 따라 국소 탐색 알고리즘은 보다 현실적인 목표인 지역 최적해를 찾는 데 초점을 맞춘다. 지역 최적해는 현재 해의 이웃 해들 중 더 나은 해가 존재하지 않는 해를 말한다. 즉, 주변의 작은 범위 내에서는 가장 좋은 상태이지만, 전체 탐색 공간을 고려했을 때는 더 나은 해가 다른 곳에 존재할 수 있다. 탐욕 알고리즘의 성격을 띠는 국소 탐색은 초기 해에서 출발해 주변을 탐색하며 목적 함수 값을 개선해 나가다가, 더 이상 개선할 수 없는 지역 최적해에 도달하면 탐색을 종료하게 된다.

이러한 지역 최적해에 빠지는 현상을 국소 최적점 함정이라고 부르며, 이는 국소 탐색의 가장 큰 한계점 중 하나이다. 알고리즘이 초기 해에 따라 다른 지역 최적해에 수렴할 수 있어, 찾은 해의 질이 일정하지 않을 수 있다. 따라서 시뮬레이티드 어닐링이나 탭 서치와 같은 고급 메타휴리스틱 기법들은 이 지역 최적점 함정에서 벗어나 전역 최적해에 더 가까운 해를 찾기 위해, 일시적으로 목적 함수 값을 악화시키는 이동을 허용하는 등의 전략을 사용한다.

경사 하강법은 연속 최적화 문제를 해결하기 위한 대표적인 국소 탐색 알고리즘이다. 이 방법은 목적 함수의 기울기 또는 경사를 계산하여, 함수값이 가장 가파르게 감소하는 방향으로 현재 해를 반복적으로 업데이트한다. 기본적으로 미분 가능한 함수에 적용되며, 학습률이라는 매개변수를 통해 각 단계의 이동 크기를 조절한다. 이는 기계 학습 분야, 특히 신경망의 가중치를 조정하는 역전파 과정에서 핵심적인 역할을 한다.

알고리즘의 동작 과정은 간단하다. 먼저 초기 해를 임의로 설정한 후, 현재 위치에서 목적 함수의 기울기 벡터를 계산한다. 그런 다음, 계산된 기울기의 반대 방향으로 일정한 학습률만큼 이동하여 새로운 해를 생성한다. 이 과정을 기울기가 0에 가까워져 더 이상 개선이 이루어지지 않을 때까지 반복한다. 이때 학습률이 너무 크면 최적해를 지나쳐 발산할 수 있고, 너무 작으면 수렴 속도가 매우 느려질 수 있어 적절한 값을 설정하는 것이 중요하다.

경사 하강법은 구현이 비교적 간단하고, 각 반복에서의 계산 비용이 낮다는 장점이 있다. 그러나 볼록 함수가 아닌 경우, 시작점에 따라 지역 최적해에 빠질 수 있다는 근본적인 한계를 가진다. 또한 목적 함수의 형태에 따라 진동 현상이 발생하거나 수렴이 더디게 이루어질 수 있다. 이러한 단점을 보완하기 위해 확률적 경사 하강법, 모멘텀, AdaGrad 등 다양한 변형 알고리즘이 개발되어 활용되고 있다.

최급 강하법은 탐욕 알고리즘의 일종으로, 국소 탐색 알고리즘 중 가장 기본적인 형태에 속한다. 이 방법은 현재 해의 이웃 해 집합을 모두 평가하여, 그중에서 목적 함수 값을 가장 크게 개선시키는 방향으로 한 단계씩 이동하는 방식을 취한다. 즉, 매 단계에서 가장 가파른 경사를 따라 내려가기 때문에 '최급 강하'라는 이름이 붙었다. 이는 경사 하강법과 개념적으로 유사하나, 주로 이산적인 조합 최적화 문제에 적용된다는 점에서 차이가 있다.

최급 강하법의 동작 과정은 다음과 같다. 먼저 초기 해를 선택한 후, 현재 해의 모든 이웃 해를 생성하고 각각의 목적 함수 값을 계산한다. 계산 결과, 현재 해보다 목적 함수 값이 더 좋은(최소화 문제라면 더 작은) 이웃 해가 하나라도 존재하면, 그중에서 가장 개선 정도가 큰 해를 새로운 현재 해로 선택한다. 이 과정을 더 이상 개선 가능한 이웃 해가 없을 때까지 반복한다. 이 알고리즘은 구현이 간단하고 각 단계에서 확실한 개선을 보장하며, 수렴 속도가 비교적 빠르다는 장점이 있다.

그러나 최급 강하법은 지역 최적해에 빠지기 쉽다는 근본적인 한계를 지닌다. 알고리즘이 더 이상 주변에 개선된 해가 없는 지점에 도달하면 탐색을 종료하는데, 이 지점이 전체 탐색 공간에서의 최선의 해, 즉 전역 최적해라는 보장이 없다. 특히 목적 함수의 표면이 복잡하고 요철이 많은 문제에서는 초기 해의 선택에 따라 성능이 크게 좌우될 수 있다. 이러한 단점을 보완하기 위해 시뮬레이티드 어닐링이나 탭 서치와 같은 더 정교한 메타휴리스틱 알고리즘이 개발되었다.

이 방법은 운용 과학의 다양한 문제, 예를 들어 여행하는 외판원 문제나 작업 스케줄링 문제 같은 NP-난해 문제에 대한 휴리스틱 솔루션으로 널리 활용되어 왔다. 또한 기계 학습에서 모델 파라미터를 튜닝하거나 인공지능에서 퍼즐 문제를 해결하는 데에도 응용된다.

힐 클라이밍은 탐욕 알고리즘의 일종으로, 최적화 문제를 해결하기 위한 단순하면서도 직관적인 국소 탐색 기법이다. 이 알고리즘은 현재 해의 이웃 해 중에서 목적 함수 값을 개선하는 방향으로만 이동하며, 더 이상 개선할 수 있는 이웃이 없을 때 종료한다. 이는 마치 언덕을 오르듯 항상 상승 방향으로 나아가기 때문에 '언덕 오르기'라는 이름이 붙었다.

힐 클라이밍의 작동 과정은 다음과 같다. 먼저 초기 해를 임의로 선택한 후, 현재 해의 이웃 해들을 평가한다. 평가 기준은 주어진 목적 함수(예: 비용 최소화 또는 이익 최대화)이다. 현재 해보다 더 나은 이웃 해가 존재하면, 그 중 가장 좋은 해를 새로운 현재 해로 선택한다. 이 과정을 더 이상 개선된 이웃이 발견되지 않을 때까지 반복한다. 알고리즘이 종료되는 지점은 지역 최적해에 도달한 상태이다.

이 알고리즘의 가장 큰 장점은 구현이 간단하고 계산 비용이 비교적 낮으며, 특히 탐색 공간이 크지 않거나 좋은 초기 해를 쉽게 얻을 수 있는 문제에서 빠르게 합리적인 해를 찾을 수 있다는 점이다. 그러나 주요 단점은 전역 최적해가 아닌 지역 최적해에 빠질 위험이 매우 크다는 것이다. 알고리즘이 처음 도달한 지역 최적점에서 탈출할 수 없기 때문에, 초기 해의 선택에 따라 결과의 질이 크게 좌우된다.

이러한 한계를 극복하기 위해, 힐 클라이밍은 종종 다른 메타휴리스틱 알고리즘의 구성 요소로 사용되거나, 다중 시작 힐 클라이밍처럼 서로 다른 초기점에서 알고리즘을 여러 번 실행하는 방식으로 개선된다. 이러한 변형들은 조합 최적화 문제나 NP-난해 문제와 같이 정확한 해를 구하기 어려운 다양한 인공지능 및 운용 과학 문제에 적용된다.

시뮬레이티드 어닐링은 금속의 담금질 공정에서 영감을 얻은 메타휴리스틱 알고리즘이다. 이 알고리즘은 국소 탐색의 한계인 지역 최적해에 빠지는 문제를 해결하기 위해 설계되었다. 기본 원리는, 초기 고온 상태에서 금속 원자들이 활발하게 움직이다가 서서히 냉각되면서 안정적인 결정 구조를 형성하는 물리적 과정을 모방한다. 알고리즘에서는 이 과정을 탐색 공간에서의 해 탐색에 대응시킨다.

알고리즘의 핵심은 탐욕 알고리즘과 달리, 일정 확률로 현재 해보다 나쁜 이웃 해로 이동할 수 있다는 점이다. 이 확률은 '온도'라는 매개변수에 의해 조절되며, 초기에는 높은 온도로 인해 나쁜 해로의 이동이 비교적 자유롭게 허용된다. 탐색이 진행됨에 따라 서서히 온도를 낮추어(냉각 스케줄) 점차 나쁜 해로 이동할 확률을 줄여나가, 결국 전역 최적해에 가까운 해를 찾도록 유도한다.

이러한 특성 덕분에 시뮬레이티드 어닐링은 조합 최적화 문제나 NP-난해 문제와 같이 탐색 공간이 방대하고 복잡한 문제를 해결하는 데 효과적으로 적용된다. VLSI 배치, 경로 계획, 작업 스케줄링 등 다양한 운용 과학 및 공학 설계 문제에서 활용된다.

탭 서치는 프레드 글로버(Fred Glover)가 1986년에 제안한 메타휴리스틱 알고리즘이다. 이 방법은 탐욕 알고리즘의 한계, 즉 지역 최적해에 빠지는 문제를 극복하기 위해 설계되었다. 기본 아이디어는 탐색 과정에서 최근에 방문한 해들을 '탭'(Taboo, 금지) 목록에 기록하여 일정 기간 동안 재방문하지 못하도록 하는 것이다. 이를 통해 해 공간에서의 순환을 방지하고, 새로운 영역을 적극적으로 탐색하여 전역 최적해를 찾을 가능성을 높인다.

탭 서치의 핵심 메커니즘은 이웃 해 생성, 평가, 그리고 탭 목록의 관리에 있다. 알고리즘은 현재 해의 이웃 중 가장 좋은 해를 선택하지만, 그 해가 탭 목록에 등록되어 있다면 다른 대안을 선택한다. 탭 목록은 일반적으로 선입선출(FIFO) 방식으로 관리되며, 목록의 크기는 탐색의 다양성과 집중도를 조절하는 중요한 매개변수가 된다. 때로는 특별한 기준을 만족하는 우수한 해에 대해서는 탭 규칙을 무시하는 '포부 기준'(Aspiration Criteria)을 적용하기도 한다.

이 알고리즘은 특히 조합 최적화 문제나 NP-난해 문제와 같이 탐색 공간이 방대한 문제에 효과적으로 적용된다. 경로 탐색 문제, 작업 스케줄링, 물류 네트워크 설계 등 다양한 운용 과학 분야의 문제 해결에 널리 사용된다. 또한 기계 학습에서의 하이퍼파라미터 튜닝이나 공학 설계 최적화와 같은 분야에서도 그 유용성이 입증되었다.

탭 서치는 비교적 간단한 원리와 강력한 성능으로 인해 다른 메타휴리스틱인 시뮬레이티드 어닐링이나 유전 알고리즘과 함께 자주 비교 및 연구된다. 구현의 유연성과 문제에 따른 적응 가능성이 높아, 이후 그래디언트 부스팅이나 안티 콜로니 최적화와 같은 다양한 진화형 알고리즘 개발에도 영향을 미쳤다.

국소 탐색의 가장 큰 장점은 일반적으로 계산 비용이 낮고 구현이 비교적 간단하다는 점이다. 탐욕 알고리즘의 특성을 가지므로, 매 단계에서 주변의 이웃 해 중 가장 좋은 해를 선택하는 직관적인 방식으로 동작한다. 이는 복잡한 전역 최적해를 찾기 위한 사전 정보나 모델 구축 없이도 빠르게 해를 개선할 수 있게 해준다.

또한, 탐색 공간이 매우 크거나 문제의 구조가 명확하지 않은 경우에도 적용 가능한 실용적인 접근법이다. 특히 조합 최적화 문제나 NP-난해 문제와 같이 모든 가능한 해를 일일이 평가하는 것이 불가능한 문제에서 메타휴리스틱으로서 유용하게 쓰인다. 메모리 사용량도 적은 편이어서 대규모 문제를 다룰 때 부담이 적다.

이러한 특성 덕분에 국소 탐색은 다양한 실시간 응용 분야나 초기 해를 빠르게 개선해야 하는 상황에서 널리 사용된다. 기계 학습에서 모수 조정이나 운용 과학의 스케줄링 문제 등에서 효율적인 개선을 보여준다.

국소 탐색의 가장 큰 단점은 지역 최적해에 빠질 위험이 높다는 점이다. 알고리즘이 현재 해 주변의 이웃 해만을 탐색하기 때문에, 탐색 범위를 벗어난 더 우수한 전역 최적해를 발견하지 못하고 조기에 수렴해버릴 수 있다. 이는 특히 목적 함수의 표면이 복잡하거나 요철이 많은 문제에서 두드러진다.

이러한 지역 최적해 문제를 완화하기 위해 시뮬레이티드 어닐링이나 탭 서치와 같은 메타휴리스틱 기법들이 개발되었다. 이 기법들은 일시적으로 목적 함수 값이 나빠지는 이동을 허용하거나, 탐색 이력을 기억하여 반복을 피하는 방식으로 지역 최적해에서 탈출할 가능성을 높인다. 그러나 이러한 개선 기법을 적용하더라도 여전히 전역 최적해를 보장하지는 못하며, 추가적인 계산 비용이 발생한다.

또 다른 단점은 탐색의 성능이 초기 해와 이웃 구조의 정의에 크게 의존한다는 것이다. 나쁜 초기 해에서 시작하거나 이웃을 생성하는 규칙이 비효율적이라면, 알고리즘은 좋은 해를 찾는 데 실패하거나 수렴 속도가 매우 느려질 수 있다. 따라서 문제에 대한 사전 지식을 바탕으로 초기화 전략과 이웃 설계를 신중하게 수행해야 하는 부담이 따른다.

마지막으로, 국소 탐색은 일반적으로 하나의 해에서 출발하여 개선하는 과정을 거치기 때문에 탐색의 다양성이 부족할 수 있다. 이는 유전 알고리즘이나 개미 군집 최적화와 같은 군집 기반 최적화 알고리즘과 대비되는 특징이다. 따라서 해 공간에 여러 개의 좋은 해가 분포해 있는 문제나 다목적 최적화 문제에는 직접 적용하기 어려운 경우가 있다.

기계 학습 분야에서 국소 탐색은 모델의 매개변수를 조정하거나 하이퍼파라미터를 최적화하는 과정에서 널리 활용되는 핵심적인 최적화 기법이다. 특히 신경망의 훈련 과정에서 손실 함수를 최소화하기 위한 경사 하강법 및 그 변형 알고리즘들은 국소 탐색의 전형적인 예시에 해당한다. 이 알고리즘들은 현재 매개변수 지점에서 함수의 기울기 정보를 바탕으로 주변을 탐색하여 손실을 줄이는 방향으로 매개변수를 반복적으로 업데이트한다.

국소 탐색은 지도 학습과 비지도 학습을 막론하고 모델 성능을 극대화하는 데 필수적이다. 예를 들어, 서포트 벡터 머신의 결정 경계를 찾거나, 클러스터링 알고리즘에서 군집의 중심을 조정할 때, 또는 강화 학습에서 정책을 개선할 때 국소 탐색 원리가 적용된다. 또한 특성 선택이나 모델 선택과 같은 조합 최적화 문제를 해결하는 데에도 탭 서치나 시뮬레이티드 어닐링 같은 고급 국소 탐색 알고리즘이 사용된다.

그러나 기계 학습의 목적 함수는 대체로 매우 복잡하고 비볼록한 형태를 띠는 경우가 많아, 기본적인 국소 탐색 알고리즘은 지역 최적해에 빠지기 쉽다는 근본적인 한계를 가진다. 이를 극복하기 위해 모멘텀, 적응적 학습률, 또는 확률적 경사 하강법과 같은 기법들이 도입되어 탐색의 효율성과 전역 최적해를 찾을 가능성을 높인다. 따라서 기계 학습에서의 효과적인 최적화는 국소 탐색의 효율성과 이를 넘어서는 탐색 전략 사이의 균형을 찾는 과정이라고 할 수 있다.

운용 과학은 한정된 자원을 효율적으로 활용하여 의사결정을 최적화하는 분야이다. 이 분야에서는 물류 네트워크 설계, 생산 계획, 재고 관리, 일정 계획 등 복잡한 조합 최적화 문제가 빈번하게 발생한다. 이러한 문제들은 종종 NP-난해 문제에 속하여 모든 가능한 해를 일일이 검토하는 것은 현실적으로 불가능하다. 따라서 국소 탐색과 같은 메타휴리스틱 알고리즘은 운용 과학에서 최적 또는 우수한 실용적 해를 찾는 핵심 도구로 활용된다.

운용 과학에서 국소 탐색은 주어진 문제를 탐색 공간과 이웃 구조로 모델링하는 것에서 시작한다. 예를 들어, 화물차 배송 경로 문제에서는 하나의 가능한 경로가 '현재 해'가 되고, 두 고객의 방문 순서를 바꾸는 것이 하나의 '이웃 해' 생성 방법이 될 수 있다. 알고리즘은 현재 해의 이웃을 평가하여 목표(예: 총 이동 거리 최소화)를 더 잘 만족하는 해를 찾아 이동하는 과정을 반복한다. 탐욕 알고리즘의 성격을 띠는 힐 클라이밍이나, 지역 최적점에 빠지는 것을 피하기 위해 일시적으로 악화된 해로 이동을 허용하는 탐색 범위 조절 기법을 사용하는 시뮬레이티드 어닐링 등 다양한 변형 알고리즘이 상황에 맞게 적용된다.

이러한 기법들의 적용은 구체적인 문제 해결로 이어진다. 공항의 게이트 할당, 병원의 수술실 스케줄링, 통신 네트워크의 대역폭 할당 등의 문제에서 국소 탐색은 복잡한 제약 조건 하에서 실행 가능한 우수한 해를 신속하게 도출하는 데 기여한다. 또한 물류 및 운송 분야의 차량 경로 문제(VRP)나 공장의 작업 스케줄링 문제처럼 실시간으로 변화하는 조건에 대응하여 해를 개선해야 하는 동적 환경에서도 그 유연성 때문에 널리 사용된다.

공학 설계 분야는 국소 탐색 알고리즘이 널리 활용되는 대표적인 영역이다. 복잡한 시스템이나 제품의 설계 과정은 종종 수많은 설계 변수와 제약 조건, 그리고 이를 평가하는 다중 목적 함수를 포함하는 최적화 문제로 모델링된다. 이러한 문제들은 조합 최적화 문제의 특성을 가지며, 탐색 공간이 방대하여 전역 최적해를 찾는 것이 매우 어려운 경우가 많다. 이때 국소 탐색은 주어진 시간과 자원 내에서 실용적이고 효율적인 설계안을 도출하는 강력한 도구로 작용한다.

구체적으로, 항공우주공학에서는 익형의 공력 성능을 최적화하거나, 구조 설계에서는 재료 사용량을 최소화하면서 강도와 안전성을 확보하는 문제에 국소 탐색이 적용된다. 전자공학에서는 집적회로의 배치 및 배선 문제, 통신공학에서는 안테나 배열 설계나 네트워크 자원 할당 최적화에도 사용된다. 또한 로봇공학에서 로봇의 경로 계획이나 제어 파라미터 튜닝, 자동차공학에서 차체의 공기역학적 형상 설계 등 다양한 세부 분야에서 그 유용성이 입증되었다.

공학 설계에 국소 탐색을 적용할 때의 주요 장점은 문제의 복잡한 물리적 모델이나 시뮬레이션 결과를 직접 목적 함수로 활용할 수 있다는 점이다. 예를 들어, 유한 요소 해석이나 전산 유체 역학 시뮬레이션 결과를 바탕으로 설계를 개선해 나가는 과정에 힐 클라이밍이나 시뮬레이티드 어닐링과 같은 알고리즘을 결합할 수 있다. 이를 통해 설계자는 수작업으로는 도달하기 어려운 우수한 설계점을 자동화된 과정을 통해 발견할 수 있으며, 이는 제품 개발 기간 단축과 성능 향상으로 이어진다.