arXiv:2609.09796v1 cs.LG

중규모 블랙박스 전역 최적화를 위한 실용적인 DIRECT 유형 알고리즘

A practical DIRECT-type algorithm for medium-scale black-box global optimization

Linas Stripinis, Remigijus Paulavičius

제출 2026-09-09

한국어 초록

DIRECT 알고리즘은 다목적성과 균형 잡힌 탐험(exploration)-활용(exploitation) 전략으로 알려진 결정론적 전역 최적화 방법이다. 그러나 DIRECT 유형 알고리즘은 주로 저차원 문제에서 효과적이며, 차원이 증가함에 따라 수렴(convergence)이 느려지는 경우가 많아 더 복잡한 최적화 과제에 대한 적용성이 제한된다. 이러한 한계를 해결하기 위해 본 논문은 동적 분할(dynamic partitioning)과 하이브리드화(hybridization) 기법을 결합한 새로운 DIRECT 유형 알고리즘인 X-DTC-GL을 제안한다. 동적 분할 방식은 국소 1차원 대리 모델(surrogate model)을 기반으로 탐색 공간을 적응적으로 세분화하여, 유망한 초직육면체(hyper-rectangle)를 빠르게 분할할 수 있게 한다. 하이브리드화 전략은 대리 모델이 식별한 유망 영역을 활용하기 위해 언덕 오르기(hill-climbing) 방법을 선택적으로 사용한다. 서로 다른 네 가지 벤치마크 스위트에 대한 광범위한 실험 결과, X-DTC-GL은 기존 DIRECT 유형 베이스라인을 크게 능가하여 해결 가능성(solvability)에서 약 12%, 해의 품질에서 약 27%의 향상을 달성했다. 성능 프로파일(performance-profile) 분석에 따르면, 최대 약 40%의 인스턴스에서 가장 빠른 수렴을 보였고, 약 17%의 문제에서 최고의 실행 시간 성능을 기록했으며, 전체 실행 시간 또한 경쟁력을 갖추었다. 이러한 발전은 분할 기반 프레임워크 내에서 성능을 개선함으로써, 최첨단 블랙박스 최적화 분야에서 이 알고리즘의 경쟁력을 강화한다.

원문 초록

The DIRECT algorithm is a deterministic global optimization method known for its versatility and balanced exploration-exploitation strategy. However, DIRECT-type algorithms are primarily effective for low-dimensional problems and often exhibit slow convergence as dimensionality increases, limiting their applicability to more complex optimization tasks. To address this limitation, this paper introduces X-DTC-GL, a novel DIRECT-type algorithm that incorporates dynamic partitioning and hybridization techniques. The dynamic partitioning approach adaptively refines the search space based on local one-dimensional surrogate models, enabling rapid subdivision of promising hyper-rectangles. The hybridization strategy selectively employs a hill-climbing method to exploit promising regions identified by the surrogate models. Extensive experiments on four diverse benchmark suites demonstrate that X-DTC-GL significantly outperforms existing DIRECT-type baselines, achieving improvements of ~12% in solvability and ~27% in solution quality. Performance-profile analyses indicate the fastest convergence on up to ~40% of instances, the best runtime performance on ~17% of problems, and competitive overall execution times. By improving performance within the partition-based framework, these advances strengthen the algorithm's competitiveness in state-of-the-art black-box optimization.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2609.09796v1제출 시각 미확인

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

공통 태그로 연결된 공개 논문이 아직 없습니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.