Prioritizing Search Space Regions in the Low Autocorrelation Binary Sequences Problem

기술 요약: 저자기상 상관 이진 수열(LABS) 문제에서의 탐색 공간 영역 우선순위 지정

문제 정의
저자기상 상관 이진 수열(Low Autocorrelation Binary Sequences, LABS) 문제는 이진 수열 $S = \{s_1, \dots, s_L\}$ (단, $s_i \in \{+1, -1\}$)를 찾아 제곱 비주기 자기상관(aperiodic autocorrelations)의 합을 최소화하는 것을 목표로 하는 도전적인 조합 최적화 과제입니다. 목적 함수는 수열 에너지 $E(S)$를 이용하여 정의되는 메리트 팩터(merit factor) $F(S) = L^2 / 2E(S)$를 최대화하는 것입니다. 탐색 공간은 $2^L$로 지수적으로 증가하며, 수많은 지역 최솟값(local minima)과 희귀하고 고립된 전역 최솟값(global minima)이 존재하는 험난한 지형(rugged landscape)을 특징으로 합니다. 왜 대칭 수열(skew-symmetric sequences, $s_{k+1+i} = (-1)^i s_{k+1-i}$를 만족하는 수열)은 탐색 공간을 줄이고 홀수 이동(odd-shift) 자기상관을 제거하지만, 큰 $L$에 대해 최적의 수열을 찾는 것은 전수 조사 방식으로는 계산적으로 불가능합니다.

방법론
저자들은 온라인 의사결정과 병렬 확률적 탐색을 통합하여 LABS 탐색 공간 전체에 계산 자원을 동적으로 할당하는 하이브리드 탐색 프레임워크인 TS-SAW를 제안합니다. 이 방법론은 세 가지 핵심 구성 요소로 이루어집니다:

1. 분할 우선순위 지정을 위한 톰슨 샘플링(Thompson Sampling for Partition Prioritization):
   탐색 공간은 수열의 처음 $p$개 요소를 고정함으로써 정의되는 "제한 클래스(restriction classes)" 또는 분할(partition)이라 불리는 서로 소인 영역으로 분해됩니다. 이 분할들은 멀티 암드 밴딧(multi-armed bandit) 문제의 "팔(arms)"로 모델링됩니다. 정적 휴리스틱(예: 잠재값)을 사용하여 분할의 순위를 매기는 대신, 저자들은 톰슨 샘플링을 사용하여 분할을 적응적으로 선택합니다.

   • 각 분할 $k$는 기대 메리트 팩터를 나타내는 미지의 파라미터 $\theta_k$와 연관됩니다.
   • 베타 분포 $Beta(\alpha_k, \beta_k)$가 $\theta_k$에 대한 사전 분포(prior) 역할을 합니다.
   • 알고리즘은 연속적인 보상(정규화된 메리트 팩터)을 처리하기 위해 **분수 톰슨 샘플링(Fractional Thompson Sampling)**을 사용합니다. 분할에서의 탐색 결과로 보상 $r_t \in [0, 1]$이 나오면, 파라미터는 $(\alpha_k, \beta_k) \leftarrow (\alpha_k + r_t, \beta_k + 1 - r_t)$로 업데이트됩니다.
   • 이 메커니즘은 덜 샘플링된 영역에 대한 탐색(exploration)을 유지하면서, 경험적으로 더 높은 메리트 팩터를 산출하는 분할로 계산적 노력을 동적으로 전환합니다.

2. GPU 상의 병렬 자기 회피 보행(Parallel Self-Avoiding Walks, SAW on GPU):
   분할이 선택되면, 알고리 birlikte 제한된 공간 내에서 수열을 최적화하기 위해 자기 회피 보행을 수행합니다.

   • 구현: 보행은 NVIDIA GPU(CUDA)에서 병렬로 실행됩니다. 각 보행은 CUDA 블록 내에서 독립적인 에이전트로 작동합니다.
   • 순환 방지: 과도한 메모리 사용 없이 방문한 상태를 재방문하는 것을 방지하기 위해, **블룸 필터(Bloom filter)**가 방문한 수열의 해시를 저장합니다.
   • 효율성: 이웃 평가에는 왜 대칭 수열을 위한 선형 시간 플립(flip) 연산이 사용되어, 낮은 메모리 점유율과 높은 처리량을 보장합니다.
   • 공유 학습: 보행이 병렬로 실행되는 동안, 이들은 각 배치(batch)의 보행이 끝난 후 업데이트되는 전역 사후 믿음($\alpha_k, \beta_k$)을 공유하여 학습 과정을 가속화합니다.

3. 2단계 최적화 파이프라인:
   프레임워크는 솔루션을 정교화하기 위해 2단계 전략을 채택합니다:

   • 1단계 (제한적): 병렬 SAW가 분할된 왜 대칭 탐색 공간을 탐색합니다. 퀵셀렉트(quickselect) 알고리즘을 통해 선택된 상위 $m$개의 후보가 다음 단계로 전달됩니다.
   • 2단계 (비제한적): 이 후보들은 비제한적 탐색 공간에서 추가적인 정교화 과정을 거칩니다. 이 단계에서는 왜 대칭성과 분할 제약을 제거하고, 우선순위 큐와 수열 연산자(회전 및 플립)를 사용하여 더 넓은 영역을 탐색하고 솔루션 품질을 개선합니다.
   • 수열 연산자: 짝수 길이의 수열을 처리하기 위해, 최적화된 홀수 길이 수열을 짝수 길이 변형으로 변환하는 연산자를 적용하며, 이는 다시 정교화 단계로 피드백됩니다.

주요 기여

• 적응형 자원 할당: 정적 휴리스틱 순위 지정에서 벗어나 톰슨 샘플링을 사용하여 탐색 공간 영역의 우선순위를 동적으로 지정하는 새로운 온라인 방법을 제시합니다.
• 하이브리드 알고리즘 (TS-SAW): 멀티 암드 밴딧 의사결정과 GPU 가속 병렬 자기 회피 보행을 결합한 새로운 알고리즘입니다.
• 확장 가능한 아키텍처: 초기 탐색을 위한 대규모 병렬 처리와 최종 최적화를 위한 비제한적 정교화를 활용하는 2단계 파이프라인을 갖추고 있습니다.
• 새로운 최적해(Best-Known Solutions) 도출: $450 \le L \le 527$ 범위의 35개 서로 다른 길이와 $L = 573$에 대해 새로운 기록적인 수열들을 생성했습니다.

실험 결과
실험은 NVIDIA A100 GPU가 탑재된 Vega 슈퍼컴퓨터에서 수행되었습니다. 방법론은 $450 \le L \le 527$ 및 $L = 573$ 길이의 이진 수열에 대해 테스트되었으며, 초기 단계를 위해 100,000회의 반복(iteration)을 수행했습니다.

• 메리트 팩터 개선: 제안된 방법은 테스트된 35개 모든 길이에 대해 기존의 최적 메리트 팩터를 개선했습니다. 개선된 수열들의 평균 메리트 팩터 증가량은 0.1967이었습니다.
• 기록 경신:
  • $L = 451$의 경우, 이 방법은 메리트 팩터 $F = 8.0555$를 달성하여 이전 기록보다 0.8248 높았습니다. 이는 문헌에 보고된 내용 중 메리트 팩터가 8.0을 초과하는 가장 긴 수열로 보고되었습니다.
  • $L = 573$의 경우, 메리트 팩터가 0.2564 개선되었으며, 이는 $F > 7.0$인 알려진 가장 긴 수열을 나타냅니다.
• 분할 분석: $L=461$에 대한 실험은 톰슨 샘플링이 고성능 분할을 효과적으로 식별함을 보여주었습니다. 알고리즘은 이론적인 "정규화된 잠재력(normalized potential)"이 높은 분할에서 벗어나, 경험적으로 더 나은 결과를 산출하는 분할로 초점을 전환했으며, 이는 정적 휴리스틱보다 데이터 기반 할당의 가치를 입증합니다.

의의 및 주장
본 논문은 제안된 프레임워크가 LABS 문제에서 메리트 팩터를 극대화하기 위한 확장 가능하고 효과적인 전략을 제공한다고 주장합니다. 확률적 의사결정과 고성능 병렬 컴퓨팅을 통합함으로써, 이 접근 방식은 매우 험난한 탐색 공간에서 탐색(exploration)과 이용(exploitation) 사이의 균형을 성공적으로 맞추었습니다. 저자들은 수열의 길이가 길어질수록 개선이 점점 더 어려워지지만, 데이터 기반의 분할 가이드 확률적 최적화 방식이 최첨단 기술(state-of-the-art)을 발전시키는 유망한 방향임을 확언합니다. 결과는 온라인 적응형 자원 할당이 이러한 종류의 조합 최적화 문제에서 정적 휴리스틱 우선순위 지정보다 우월함을 검증합니다. 저자들은 이 프레임워크가 탐색 공간을 의미 있게 분할할 수 있는 다른 어려운 조합 최적화 문제들을 위한 적응형 탐색 전략의 경로를 제공한다고 결론짓습니다.