LLM으로 조합 최적화 문제의 휴리스틱을 자동 설계하는 새 방법 PRS(Perturbation-Rewrite Search)가 arXiv에 논문으로 공개됐다. 논문 제목은 'Directing to Diversify: Multi-Directional Search for Automatic Heuristic Design'이며, 발행일은 2026년 10월 22일이다.
저자들은 생성 단계(generation level)에서 방향성 탐색의 기본 연산으로 휴리스틱 변형을 분해하는 것이 PRS의 핵심이라고 설명했다. 여러 조합 최적화 과제에서 실험한 결과 PRS가 고품질 휴리스틱을 꾸준히 찾아냈다고 밝혔다.
LLM은 사람의 개입 없이 NP-hard 조합 최적화 과제의 휴리스틱을 설계할 잠재력을 보여 왔다. 저자들은 최근 방법 대부분이 진화 연산 틀에 의존하며, 다양성이 진화 연산식 연산자나 이후 선택 과정에서 주로 생긴다고 짚었다. 휴리스틱을 어느 방향으로 변형할지는 거의 활용되지 않았다는 것이 문제 제기다.
PRS는 휴리스틱의 아이디어를 세 방향으로 바꾼다. 확장은 더 풍부하고 표현력 있는 설계로, 압축은 더 단순하고 덜 특화된 설계로 옮긴다. 미세 조정(steering)은 세밀하게 다듬는 방향이다. 이 세 방향이 함께 작동해 설계 공간의 다양한 영역을 더 넓고 오래 탐색하게 한다는 것이 저자들의 설명이다.
후보 탐색은 너비 우선 탐색 기반 과정으로 묶고, 연산자를 상황에 맞게 조절한다. 저자들은 이 구조가 후보를 충분히 활용하게 하고 탐색을 지속시키며, 너무 일찍 한 곳으로 수렴하는 것을 막는다고 주장했다.
출처
이 기사는 아래 자료를 바탕으로 정리했습니다. 제목을 누르면 원문이 새 창으로 열립니다.