A New Meta-Heuristic for Improving General Multi-Start Procedures, With an Application to the Planar p-Median Location Problem

당신이 거대한 평면 도시에서 다섯 개의 새로운 피자 가게를 세울 가장 완벽한 지점을 찾으려고 노력하고 있다고 상상해 보십시오. 당신은 모든 사람이 피자 한 조각을 먹기 위해 걸어야 하는 총 거리를 최소화하고 싶습니다. 이것이 바로 **평면 p-중앙 문제(Planar p-Median Problem)**입니다. 듣기에는 단순해 보이지만, 도시는 함정들로 가득 찬 미로와 같습니다. 만약 당신이 단순히 어떤 지점을 정하고 그곳이 더 나은지 확인하기 위해 돌아다닌다면, 당신은 작은 언덕 위에 서서 그것이 가장 높은 봉우리라고 생각하며 갇혀버릴 수도 있습니다. 하지만 바로 옆 능선 너머에 거대한 산이 있을 수도 있습니다. 수학적 용어로, 이러한 언덕들을 "지역 최적해(local optima)"라고 부르며, 이 문제에는 수백만 개의 지역 최적해가 존재할 수 있습니다.

수십 년 동안 연구자들은 **멀티-스타트(Multi-Start)**라고 불리는 전략을 사용해 왔습니다. 이것은 800,000명의 서로 다른 정찰병(또는 800,000개의 별도 피자 배달 경로)을 고용하는 것과 같습니다. 각 정찰병은 어떤 지역적 언덕에 갇힐 때까지 달리고, 그러면 당신은 그 모든 정찰병의 결과 중 가장 좋은 것을 선택합니다. 효과적이긴 하지만, 이는 마치 백발백중의 과녁을 향해 백만 개의 다트를 던져서 그중 하나가 명중하기를 바라는 것과 같습니다.

새로운 기술: "엘리트 부대"와 "아기 걸음"

저자인 즈비 드레즈너(Zvi Drezner)와 잭 브림버그(Jack Brimberg)는 RPT(Repeated POST의 약자)라고 불리는 영리한 새로운 메타 휴리스틱(스마트한 해결 규칙)을 제안합니다. 그들은 단순히 800,000명의 정찰병으로부터 얻은 단 하나의 최적의 결과만을 유지하는 대신, 찾아낸 상위 5개의 최적 결과로 구성된 작은 "엘리트 부대(Elite Squad)"를 유지해야 한다고 주장합니다.

여기 마법 같은 부분이 있습니다:

1. 섞고 조합하기 (Mix-and-Match): 두 개의 서로 다른 "엘리트" 해법(서로 다른 피자 가게 위치 세트)을 가져옵니다. 이들을 각각 '부모 A'와 '부모 B'라고 상상해 보십시오.
2. 자손 만들기: 도시를 가로지르는 선을 하나 긋습니다. 부모 A의 가게 중 선의 한쪽에 있는 것들과, 부모 B의 가게 중 선의 반대편에 있는 것들을 가져옵니다. 방금 당신은 두 부모의 장점을 결합한 새로운 "자식" 해법, 즉 하이브리드 지도를 만들어냈습니다.
3. 다듬기: 이 새로운 자식 해법에 대해 표준 개선 알고리즘을 실행합니다. 아마도 이 자식은 새로운 언덕에 갇힐 수도 있지만, 그 언덕은 이전보다 더 높은 언덕일 수 있습니다.
4. 반복: 만약 이 새로운 자식이 현재의 최고 해법보다 더 낫다면, 당신은 그것을 엘리트 부대에 포함시키고 다시 다른 것들과 섞어봅니다. 더 나은 "자식"을 찾을 수 없을 때까지 이 과정을 반복합니다.

논문에서는 초기 혼합 단계를 POST(post-optimizing step)라고 부릅니다. 전체 RPT 전략은 이 과정을 한 단계 더 발전시킵니다. 800,000명의 정찰병을 한꺼번에 돌리는 대신, 작업을 작은 배치 단위로 나눕니다. POST 과정을 통해 작은 그룹을 실행하여 상위 5개를 찾고, 이들을 섞은 다음, 이 전체 사이클을 여러 번 반복합니다(가장 뛰어난 테스트에서는 구체적으로 700번 반복했습니다).

그들이 발견한 것 (그리고 발견하지 못한 것)

저자들은 48개의 서로 다른 도시 지도(고르게 퍼진 고객 24개, 뭉쳐 있는 불균일한 클러스터 24개)를 대상으로 테스트를 진행했습니다. 그들은 두 가지 서로 다른 "정찰" 알고리즘을 사용했습니다: 고전적인 ALT(쿠퍼의 전통적인 방식)와 더 새롭고 화려한 CLUST 알고리즘입니다.

• 결과: 48개의 모든 테스트 케이스에서 RPT(CLUST) 방식이 표준 멀티-스타트 방식보다 더 나은 해법을 찾아냈습니다. (참고: 표준 RPT(ALT) 방식은 결과를 크게 개선했지만 48개 사례 모두에서 새로운 최적해를 찾지는 못했습니다. 이 특정 성과는 CLUST 알고리즘과 결래 결합된 RPT 방식의 업적입니다.)
• 속도: 핵심은 이 섞고 조합하는 데 걸린 추가 시간이 거의 없었다는 점입니다. 균일한 24개 사례의 경우, 표준 ALT를 실행하는 데 걸린 평균 시간은 약 257.68분이었습니다. RPT 방식은 약 257.45분이 걸렸습니다. 그들은 거의 같은 시간 안에 더 나은 결과를 얻었습니다.
• 개선 정도: 표준 ALT 방식의 해법은 알려진 최적의 결과보다 평균적으로 약 0.80% 나빴습니다. RPT는 이를 **0.53%**로 줄였습니다. 일부 특정 사례에서는 오차를 60% 또는 70% 이상 줄이는 등 개선 폭이 엄청났습니다.

더 느린 최신 알고리즘인 CLUST를 사용했을 때, 결과는 더욱 인상적이었습니다. 표준 CLUST 방식은 이미 매우 좋은 해법을 찾았지만, RPT는 모든 균일 사례 24개와 모의 비균일 사례 24개에서 새로운 최적해를 찾아냈습니다. 실제로 균일 테스트의 경우, 특정 설정(I = 1,000)을 사용한 RPT 방식은 단독으로 24개 중 14개 사례에서 최적의 해법을 찾아냈습니다. 만약 서로 다른 설정(I=1,000과 I=10,000)의 결과를 결합하면, 24개 중 21개 사례에서 새로운 최적해를 찾았습니다. 비균일 테스트의 경우, RPT 방식은 단독으로 24개 중 13개 사례에서 최적해를 찾았으며, 설정을 결합했을 때는 24개 전부에 대해 최적해를 찾아냈습니다.

그들이 제외한 것 (한계점)

이 논문은 이 방법이 아닌 것이 무엇인지도 명확히 밝히고 있습니다.

• 이 방법은 매번 완벽한 전역 최적해(global optimum)를 보장하는 마법의 지팡이가 아닙. 저자들은 "만약 멀티-스타트 휴리스틱이 최적해를 찾는다면, 당연히 RPT도 이를 개선할 수 없다"고 명시했습니다. 이미 절대적인 최선의 답을 찾았다면 RPT는 그것을 더 좋게 만들 수 없습니다.
• 이 방법은 컴퓨터를 며칠 동안 더 돌려야 하는 방법이 아닙. 저자들은 추가되는 시간이 "무시할 수 있는 수준"이라고 주장합니다.
• 또한, 완벽한 파라미터(예: 정찰병을 정확히 몇 명 사용할지)를 찾는 데 집착할 필요가 없다고 제안합니다. 그들은 다양한 그룹 크기(예: 1,000 대 10,000)를 테스트했고 성능이 비슷하게 나타났기에, "합리적인 파라미터를 선택하기만 하면 비슷하게 잘 작동할 것"이라고 설명했습니다.

그들의 확신은 어느 정도인가?

저자들은 자신들의 수치에 매우 확신하고 있는데, 그 이유는 Intel i7 프로세서를 탑로한 데스크톱 컴퓨터에서 실제 시뮬레이션을 수행했기 때문입니다. 그들은 단순히 추측한 것이 아니라 측정했습니다.

• 그들은 통계적 검정(paired t-tests)을 사용하여 개선 사항이 통계적으로 유의미함을 확인했습니다 (p-값이 $6.7 \times 10^{-5}$까지 내려갔습니다).
• 그들은 이 방법이 "일반적인 멀티-스타트 개선 알고리즘"에 적용 가능하다고 주장하지만, 오직 평면 p-중앙 문제에서만 이를 입증했습니다. 그들은 이 방법이 다른 문제(예: 클러스터링)에도 작동할 수 있다고 제안하지만, 아직 증명하지는 못했습니다.

요약

이 문제를 해결하는 기존 방식이 백만 개의 다트를 던져서 그중 하나가 명중하기를 바라는 것이라면, 새로운 RPT 방식은 지금까지 던진 다섯 개의 가장 좋은 다트를 가져와서, 그것들을 반으로 자른 뒤, 가장 좋은 부분들을 서로 붙여서 새로운 '슈퍼 다트'를 만드는 것과 같습니다. 그런 다음 그 새로운 다트를 던집니다. 만약 그 다트가 더 잘 맞는다면, 그것을 유지하고 다시 시도합니다.

이 논문은 이 "섞고 조합하는" 접근 방식이 기존 알고리즘을 사용하여 컴퓨터가 작업을 끝내기를 며칠씩 기다릴 필요 없이, 더 나은 해법을 짜내기 위한 강력하고 비용 효율적인 방법임을 시사합니다. 이는 "충분히 좋은" 탐색을 "훌륭한" 탐색으로 바꾸며, 거의 공짜로 말입니다.