TIDE: 튜닝 통합 동적 진화를 통한 LLM 기반 자동 휴리스틱 설계

TIDE: Tuning-Integrated Dynamic Evolution for LLM-Based Automated Heuristic Design

대규모 언어 모델(LLM)은 자동 휴리스틱 설계 분야에서 상당한 발전을 가져왔지만, 알고리즘 진화를 단일한 텍스트 생성 작업으로 취급하는 방식은 이산적인 알고리즘 구조와 연속적인 숫자 매개변수 간의 상호 의존성을 간과합니다. 그 결과, 기존 방법은 종종 보잘것없는 상수 값으로 인해 유망한 알고리즘을 버리거나, 단순한 유사성 측정 기준으로 인해 조기에 수렴하는 문제를 겪습니다. 이러한 한계를 극복하기 위해, 우리는 구조적 추론과 매개변수 최적화를 분리하도록 설계된 튜닝 통합 동적 진화 프레임워크인 TIDE를 제안합니다. TIDE는 트리 유사성 편집 거리를 사용하여 구조적 다양성을 유도하는 외부 병렬 아일랜드 모델과, LLM 기반 논리 생성과 차등 돌연변이 연산자를 통합하여 매개변수 튜닝을 수행하는 내부 루프를 특징으로 하는 중첩된 아키텍처를 갖습니다. 또한, UCB 기반 스케줄러는 높은 효율성을 보이는 프롬프트 전략을 동적으로 우선순위화하여 리소스 할당을 최적화합니다. 9가지 조합 최적화 문제에 대한 광범위한 실험 결과, TIDE는 최첨단 기준 성능을 크게 능가하는 휴리스틱을 발견하며, 검색 효율성을 향상시키고 계산 비용을 절감하는 것으로 나타났습니다.

Although Large Language Models have advanced Automated Heuristic Design, treating algorithm evolution as a monolithic text generation task overlooks the coupling between discrete algorithmic structures and continuous numerical parameters. Consequently, existing methods often discard promising algorithms due to uncalibrated constants and suffer from premature convergence resulting from simple similarity metrics. To address these limitations, we propose TIDE, a Tuning-Integrated Dynamic Evolution framework designed to decouple structural reasoning from parameter optimization. TIDE features a nested architecture where an outer parallel island model utilizes Tree Similarity Edit Distance to drive structural diversity, while an inner loop integrates LLM-based logic generation with a differential mutation operator for parameter tuning. Additionally, a UCB-based scheduler dynamically prioritizes high-yield prompt strategies to optimize resource allocation. Extensive experiments across nine combinatorial optimization problems demonstrate that TIDE discovers heuristics that significantly outperform state-of-the-art baselines in solution quality while achieving improved search efficiency and reduced computational costs.