A New Meta-Heuristic for Improving General Multi-Start Procedures

최적화의 세계에서 과학자와 엔지니어들은 종종 단순해 보이지만 복잡한 가능성이 숨겨진 문제에 직면하곤 합니다. 그것은 바로 창고나 기지국 같은 시설들을 어떻게 배치해야 흩어져 있는 인구를 가장 효율적으로 서비스할 수 있는가 하는 문제입니다. 목표는 사람들이 가장 가까운 시설에 도달하기 위해 이동해야 하는 총 거리를 최소화하는 것입니다. 이를 p-메디안(p-median) 문제라고 합니다. 가능한 해답의 지형이 매우 광대하고 불규ul적이며, 최선의 답처럼 보이지만 실제로는 함정에 불과한 수많은 국소적 정점(local peaks)들로 가득 차 있기 때문에, 연구자들은 멀티 스타트(multi-start) 절차라고 불리는 전략에 의존합니다. 안개가 자욱한 산맥에서 가장 높은 지점을 찾는 과정을 상상해 보십시오. 무작위 지점에 등산객을 떨어뜨리고, 그가 더 높이 올라갈 수 없을 때까지 오르게 한 다음, 다른 시작 지점에서 이 과정을 수천 번 반복하는 것입니다. 그 모든 시도 중에서 발견된 가장 높은 정점이 대개 정답입니다. 그러나 수천 번의 시도를 거치더라도, 지형이 너무 복垒하기 때문에 등산객들이 진정한 정상에 도달하지 못할 수도 있습니다.

두 명의 연구자, 즈비 드레즈너(Zvi Drezner)와 잭 브림버그(Jack Brimberg)는 디지털 등산객들이 훨씬 더 많은 시간을 들여 탐색하지 않고도 더 나은 정점을 찾을 수 있도록 돕는 새로운 방법을 제안했습니다. 그들은 이 새로운 기술을 POST라고 부릅니다. POST는 단순히 수천 번의 탐색을 실행하고 단 하나의 최선 결과를 선택하는 대신, 일괄 처리된 탐색 중 상위 몇 개의 결과를 가져와 새로운 하이브리드 시작 지점을 만드는 데 사용합니다. 이것은 마치 가장 뛰어난 등산객들의 강점을 추출하여 결합함으로써, 더 유망한 위치에서 등반을 시작할 수 있는 새로운 가이드를 만드는 것과 비슷합니다. 연구자들은 최대 10,000개의 수요 지점과 100개의 시설이 포함된 48개의 서로 다른 시나리오를 대상으로 이 방법을 테스트했습니다. 그들은 이 새로운 접근 방식이 표준 탐색에 소요되는 시간과 거의 동일한 시간 내에 모든 테스트 케이스에서 기존의 최선 솔루션들을 일관되게 개선하며 더 나은 답을 찾아낸다는 것을 발견했습니다.

핵한 과제는 문제 자체의 본질에 있습니다. 평면 위에 시설을 배치하여 그룹의 지점들을 서비스하려고 할 때, 수학적 지형은 믿기 힘들 정도로 험난합니다. 여기에는 수백만 개의 국소 최적해(local optima), 즉 주변보다 더 낫지만 전체적으로는 최선이 아닌 해답들이 존재합니다. 표준 알고리즘은 종 often 이러한 국소적 정점에 갇히곤 합니다. 이를 극복하는 전통적인 방법은 무작위 위치에서 시작하여, 무작위 시작 중 하나가 진정한 전역 최적해(global optimum)에 충분히 가까이 착륙하여 알고리즘이 정상까지 오를 수 있기를 바라며 탐색 알고리즘을 여러 번 실행하는 것입니다. 연구자들은 현재 이 작업에 가장 효과적인 도구 중 하나인 CLUST라는 강력한 개선 알고리즘을 사용했으며, 초기 테스트에서 80,000개의 서로 다른 시작 지점에서 이를 실행했습니다.

POST의 혁신은 그 초기 실행 이후에 일어나는 일입니다. 연구자들은 최선의 결과가 발견되었을 때 멈추는 대신, 일괄 실행된 결과 중 상위 5개의 서로 다른 솔루션을 가져와 "부모"로 취급합니다. 그런 다음 이 부모들의 시설 위치를 혼합하여 새로운 "자손" 솔루션을 만듭니다. 이를 위해, 연구자들은 결합된 시설 그룹의 중심을 통과하는 가상의 선을 긋습니다. 첫 번째 부모의 시설 중 선의 한쪽에 있는 시설들은 두 번째 부모의 반대편에 있는 시설들과 짝을 이룹니다. 이렇게 하면 두 부모의 강점을 모두 물려받은 새로운 구성이 생성됩니다. 연구자들은 이러한 새로운 구성을 여러 개 생성하고, 개선 알고리즘을 실행하여 더 나은 솔루션으로 이어지는지 확인합니다. 만약 그렇다면, 이 과정은 새로운 최선 솔루션들을 다음 단계의 혼합을 위한 부모로 사용하여 반복됩니다.

이러한 혼합과 개선의 순환은 여러 배치(batch)에 걸쳐 반복됩니다. 연구자들은 이 배치를 구성하는 다양한 방식을 테스트했습니다. 한 설정에서는 초기 탐색을 1,000번 실행하고, 상위 5개의 결과를 가져와 혼합한 뒤, 이 전체 사이클을 70번 반복했습니다. 또 다른 설정에서는 10,000번의 탐색을 실행하고 사이클을 8번 반복했습니다. 세 번째 설정에서는 80,000번의 전체 실행을 단일 배치로 수행했습니다. 결과는 명확한 패턴을 보여주었습니다. 탐색을 더 작은 배치로 나누고 각 배치에서 발견된 최선의 결과를 반복적으로 정교화하는 것이 전체 탐색을 한 번에 실행하는 것보다 더 나은 결과를 냈습니다. 1,000번의 초기 탐색을 수행하고 정교화 과정을 70번 반복한 방법이 가장 일관된 개선을 보여주었으며, 48개의 모든 테스트 케이스에 대해 이전의 어떤 방법보다 더 나은 솔루션을 찾아냈습니다.

연구자들은 이 혼합 과정에 소비되는 추가 시간이 미미하다는 것을 확실히 하기 위해 주의를 기울였습니다. 혼합을 통해 생성된 새로운 시작 지점들은 이미 고품질의 솔루션이기 때문에, 개선 알고리즘은 무작위 시작 지점보다 훨씬 빠르게 국소 최적해에 수렴합니다. POST 방식에 필요한 총 시간은 표준 멀티 스타트 접근 방식보다 약간 더 길었지만, 일관되게 우수한 결과를 찾아냈습니다. 균등(uniform) 테스트 케이스의 경우, 새로운 방법은 최선 솔루션을 평균 0.062% 개선했으며, 비균등(non-uniform) 케이스의 경우 0.068% 개선했습니다. 이러한 백분율이 작아 보일 수 있지만, 대규모 물류 및 시설 계획의 맥락에서 이는 거리와 비용의 상당한 절감을 의미합니다.

연구는 또한 이 접근 방식의 한계를 탐구했습니다. 연구자들은 만약 멀티 스타트 절차가 이미 절대적인 최적해를 찾아냈다면, POST 방법이 이를 더 이상 개선할 수 없다고 언급했습니다. 그러나 p-메디안 문제는 수백만 개의 국소 최적해를 가진 것으로 알려져 있으므로, 표준 탐색이 우연히 완벽한 답을 찾을 가능성은 매우 낮습니다. POST가 모든 사례에서 결과를 개선했다는 사실은 표준 탐색이 실제로 POST가 탈출할 수 있었던 국소적 정점에 갇혀 있었음을 시사합니다. 연구자들은 또한 단일 배치에서의 초기 탐색 횟수를 늘리는 것이 항상 더 나은 결과를 가져오는 것은 아니라는 점을 관찰했습니다. 사실, 더 많은 반복을 동반한 더 작은 배치가 더 나은 성능을 보였습니다. 이는 그들이 "적을수록 많다(Less is More)"라고 부르는 원칙을 뒷받-는데, 이는 몇 가지 유망한 영역을 깊고 반복적으로 탐색하는 것이 넓은 그물을 한 번 던져서 행운을 바라는 것보다 더 효과적임을 시사합니다.

POST의 성공은 한 가지 유형의 문제에 국한되지 않았습니다. 연구자들은 수요 지점이 고르게 퍼져 있는 균등 인스턴스와 지점들이 특정 방식으로 클러스터링된 비균등 인스턴스 모두에 대해 테스트했습니다. 두 시나리오 모두에서 이 방법은 수개월의 컴퓨팅 시간을 들여 달성한 최근의 다른 연구들의 최선 결과들을 포함하여 기존의 기법들을 능가했습니다. 새로운 방법은 아주 짧은 시간 내에 이러한 결과를 달성했으며, 가장 효과적인 구성의 총 실행 시간은 전체 테스트에 대해 약 13일이 걸렸습니다. 연구자들은 문제의 규모에 따라 실행 시간이 어떻게 확장되는지 추정하는 공식도 제공했는데, 수요 지점이 10배 증가할 때 필요한 시간은 약 15~17배 증가하는 반면, 시설 수가 두 배가 되면 시간은 2배 미만으로 증가한다는 점을 명시했습니다.

앞으로의 전망에 대해 저자들은 이 기술이 데이터 포인트 클러스터링이나 네트워크 분할과 같이 현재 멀티 스타트 방식으로 해결되는 다른 최적화 문제에도 적용될 수 있다고 제안합니다. 그들은 향후 연구에서 '부모' 솔루션을 선택하는 다양한 방법을 탐구할 수 있다고 보는데, 예를 들어 단순히 품질뿐만 아니라 서로 얼마나 다른지를 기준으로 선택하여 더 다양한 탐색을 보장하는 방식입니다. 또한, 혼합에 사용되는 엘리트 집단의 솔루션 수를 늘리는 것이 더 나은 결과를 낼 수 있지만, 이를 위해서는 더 많은 컴퓨팅 파워가 필요할 것이라고도 제안합니다. 이 연구는 기존 알고리즘에 간단한 사후 최적화(post-optimization) 단계를 추가함으로써, 과도한 노력의 증가 없이 솔루션의 품질을 크게 향mathcal 수 있으며, 이는 가장 복잡한 공간 계획 문제를 다루기 위한 강력한 새로운 도구를 제공한다고 결론짓습니다.