확률적 초점 검색(PFS)을 통한 최적화 탐색 가속
Probabilistic Focal Search: Accelerating Bounded-Suboptimal Search via Lower-Bound Advancement
arXiv기존 탐색 기법인 Focal Search(FS)의 한계를 극복하기 위해 확률적 초점 검색(PFS)이 개발되었습니다. PFS는 가이드 선택과 하한선 전진을 결합하여 효율적인 경계 이하 최적화 탐색을 가능하게 합니다.
- PFS는 특정 확률($p$)로 가이드 기반 노드를 선택하고 나머지 확률($1-p$)로는 최소 비용 노드 확장을 유도합니다. 이 두 요소를 균형 있게 활용함으로써 탐색 과정의 병목 현상을 해소하는 것이 핵심입니다.
- 특히 하한선이 정체되어 중요한 탐색 기회가 지연되는 경우에 가장 큰 효과를 발휘하며, 일부 테스트에서는 노드 확장을 90% 이상 줄여 최적화 시간을 크게 단축했습니다.
- 다만, 결정론적 검색 자체가 효율적으로 진행될 때는 이점이 작을 수 있습니다. 따라서 PFS의 성능은 적용하는 문제 도메인과 경계 조건에 따라 달라질 수 있음을 고려해야 합니다.
경계 이하 최적화 탐색은 주어진 해답이 최적해로부터 특정 계수 $w$ 내에 존재하도록 하면서도 전체적인 탐색 노력을 줄이는 것을 목표로 합니다. 기존의 Focal Search (FS)는 휴리스틱 가이드라인을 활용하지만, 결정론적 정책으로 인해 많은 확장이 이루어져도 최소 비용($f_{\min}$)이 변하지 않는 한계가 있었습니다.
Probabilistic Focal Search (PFS)는 이러한 문제를 해결하기 위해 도입되었습니다. PFS는 확률 $p$로 FS의 가이드 선택을 따르고, 나머지 확률 $1-p$로는 최소-$f$ OPEN 노드를 확장하는 방식을 결합합니다. 이 두 가지 요소를 균형 있게 활용함으로써 하한선 전진을 장려하고 FOCAL 영역을 넓혀 실현 가능한 해답으로 이어질 수 있는 노드 진입을 가능하게 합니다.
PFS는 특히 $f_{\min}$이 정체되어 유용한 FOCAL 진입이 지연되는 경우에 큰 이점을 보입니다. 일부 테스트에서는 PFS가 노드 확장을 약 90% 이상 줄여 최적화 시간을 단축하는 결과를 보여주었습니다 (예: N-Puzzle 및 TSP). 다만, 결정론적 검색 자체가 효율적으로 진행될 때는 그 효과가 작을 수 있으며, 성능은 적용되는 문제 도메인과 경계 조건에 따라 달라집니다.