💻 computer science

Latent Heuristic Search: Continuous Optimization for Automated Algorithm Design

본 논문은 고정된 대규모 언어 모델을 조건부로 활용하여 조합 최적화 문제에 대한 고성능 휴리스틱을 효율적으로 생성하기 위해 인코더, 미분 가능한 대리 모델 및 정규화 흐름을 사용하는 학습된 잠재 매니폴드 내에서 연속 최적화를 활용하는 잠재 휴리스틱 검색 프레임워크를 소개한다.

원저자: Cheikh Ahmed, Mahdi Mostajabdaveh, Zirui Zhou

게시일 2026-05-19

📖 3 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Cheikh Ahmed, Mahdi Mostajabdaveh, Zirui Zhou

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

복잡한 퍼즐을 해결하는 새로운 초고효율 방법을 발명하려 한다고 상상해 보세요. 예를 들어, 트럭 대열을 위한 배송 경로를 조직하거나 여행 가방을 완벽하게 포장하는 것과 같습니다. 전통적으로 인간은 시행착오를 거치며 규칙을 반복적으로 조정해 왔습니다.

최근 과학자들은 이러한 규칙을 자동으로 발명하는 데 도움을 주기 위해 대규모 언어 모델 (LLM)—코드 작성에 사용되는 동일한 유형의 AI—을 활용하기 시작했습니다. 그들은 AI 를 창의적인 파트너처럼 취급하여 새로운 "레시피"(알고리즘) 를 생성하도록 요청하고, 어떤 것이 가장 잘 작동하는지 테스트합니다.

그러나 현재 이 방식을 수행하는 방법은 요리책에서 한 단어씩 무작위로 변경하여 완벽한 레시피를 찾으려는 것과 비슷합니다. "소금"을 "설탕"으로, "밀가루"를 "모래"로 변경하며 더 나은 요리를 우연히 발견하기를 바랄 수 있습니다. 이는 느리고, messy 하며, 단어와 기호의 혼란스러운 "이산적"(discrete) 공간을 탐색하기 때문에 종종 먹지 못할 결과를 초래합니다.

이 논문은 "잠재적 휴리스틱 탐색 (Latent Heuristic Search, LHS)"이라는 더 지능적인 방법을 제안합니다.

일상적인 비유를 사용하여 작동 방식을 간단히 설명하면 다음과 같습니다:

1. "마법 지도"(잠재 공간)

연구자들은 레시피를 단어별로 살펴보는 대신, 가능한 모든 레시피를 부드럽고 연속적인 지도 위의 단일 점으로 변환합니다.

비유: 가능한 모든 배송 경로를 거대한 3 차원 풍경 위의 점으로 상상해 보세요. 좋은 경로는 높고 햇살이 비치는 언덕에, 나쁜 경로는 깊고 어두운 계곡에 위치합니다.
문제: 기존 방법에서는 점과 점 사이를 무작위로 뛰어다녀야 했습니다. 이 새로운 방법에서는 AI 가 이 풍경의 모양을 학습하여 최고의 언덕을 향해 부드럽게 "미끄러져" 갈 수 있습니다.

2. "번역기"(인코더 및 대리 모델)

이 지도를 작동시키기 위해 시스템은 두 가지 특수 도구를 사용합니다:

인코더: 이는 messy 한 서면 레시피 (코드) 를 지도 위의 깨끗한 좌표로 변환하는 번역기처럼 작동합니다.
대리 모델 (Surrogate): 이는 지도 위의 좌표만 보고 레시피가 얼마나 좋을지 예측하는 "수정구"입니다. 실제로 케이크를 굽는 (코드를 실행하는) 것 없이도 맛이 좋을지 알 수 있습니다. 수정구가 이를 추측하므로 막대한 시간을 절약할 수 있습니다.

3. "안전망"(정규화 흐름)

여기서 까다로운 부분이 있습니다. 지도 위를 그냥 미끄러진다면, 유효한 레시피가 존재하지 않는 곳 (예: "설탕 500 파운드를 추가하라"는 좌표) 으로 떨어질 수 있습니다.

해결책: 연구자들은 **정규화 흐름 (Normalizing Flow)**을 사용합니다. 이는 마치 마법 같은 신축성 있는 고무 시트와 같습니다. 이는 messy 하고 불규칙한 레시피 지도를 완벽하고 매끄러운 둥근 공 (가우시안 형태) 으로 늘려줍니다.
도움되는 이유: AI 가 최고의 레시피를 찾을 때 이 완벽한 공 안에서 미끄러집니다. 공의 모양이 매우 잘 잡혀 있기 때문에 AI 가 "말도 안 되는" 영역으로 미끄러질 가능성이 훨씬 낮아집니다. 이는 탐색을 안전하고 체계적으로 유지합니다.

4. "역번역기"(매핑러 및 LLM)

AI 가 부드러운 공 위의 완벽한 좌표 (최고의 지점) 를 찾으면, 그 좌표를 다시 실제 실행 가능한 컴퓨터 프로그램으로 변환해야 합니다.

과정: "소프트 프롬프트"(보이지 않는 특수 지시문의 집합) 를 사용하여 LLM 에게 속삭입니다: "이 지도 위의 완벽한 지점을 바탕으로 새로운 배송 경로 알고리즘을 작성해 주세요."
그런 다음 LLM 은 실제 코드를 생성하며, 이것이 실제로 작동하는지 테스트합니다.

그들은 무엇을 발견했나요?

연구자들은 이 방법을 네 가지 고전적인 퍼즐에 대해 테스트했습니다:

외판원 문제: 여러 도시를 방문하는 가장 짧은 경로를 찾는 문제.
차량 경로 문제: 제한된 트럭 공간으로 여러 집에 패키지를 배송하는 문제.
배낭 문제: 무게 제한이 있는 가방에 가장 가치 있는 물품을 최대한 담는 문제.
컨테이너 적재 문제: 도착하는 물품을 상자에 맞게 채우는 문제.

결과:

성능: 그들의 새로운 방법은 무작위 단어 교체에 의존하는 기존 최선 방법과同等하거나 때로는 더 나은 솔루션을 찾았습니다.
효율성: 이러한 솔루션을 더 빠르고 신뢰성 있게 찾았습니다.
안정성: "안전망"(고무 시트) 덕분에 시스템이 실행할 수 없는 깨진 코드를 생성하는 경우는 거의 없었습니다.

결론

이 논문은 문제 해결 알고리즘의 발명을 자동화하는 방법을 제시하며, "다음 단어 추측"이라는 혼란스러운 게임이 아닌 매끄러운 수학적 미끄럼틀로 탐색 과정을 변환합니다. 이는 AI 의 힘을 활용하여 좋은 솔루션의 형태를 이해하게 함으로써, 잡음 속에 길을 잃지 않고 최고의 아이디어로 곧바로 미끄러져 갈 수 있게 합니다.

기술 요약: 잠재 휴리스틱 검색 (LHS)

문제 정의

여행하는 세일즈맨 문제 (TSP), 차량 경로 문제, 배낭 문제와 같은 조합 최적화 문제에 대한 고품질 휴리스틱 알고리즘 설계는 전통적으로 반복적 정제와 심층적인 도메인 지식이 필요한 전문가 주도 과정이었습니다. 최근의 발전은 이러한 발견 과정을 자동화하기 위해 진화 프레임워크 (예: FunSearch, EoH, ReEvo) 에 대규모 언어 모델 (LLM) 을 통합했습니다. 그러나 기존 방법들은 주로 프로그램 구문의 이산 공간에서 작동합니다. 이들은 확률적 샘플링, 토큰 단위 돌연변이, 그리고 재결합에 의존하여 매우 비볼록한 최적화 지형을 탐색합니다. 이러한 접근 방식은 일관된 개선을 발견하기 위해 많은 수의 비용이 많이 드는 실행 기반 평가가 필요하며, 이산 검색 공간의 취약성으로 인해 어려움을 겪습니다.

방법론

본 논문은 **잠재 휴리스틱 검색 (LHS)**을 제안하며, 이는 최적화 과정을 이산 토큰 공간에서 학습된 연속 잠재 다양체로 전환하는 프레임워크입니다. 방법론은 네 가지 상호 연결된 구성 요소로 구성됩니다:

잠재 인코딩: 사전 훈련된 코드 인코더 ( $E$ ) 가 이산 휴리스틱 프로그램을 연속 벡터 임베딩 ( $z \in \mathbb{R}^d$ ) 으로 매핑합니다.
대리 모델링: 휴리스틱의 잠재 임베딩을 기반으로 성능 점수를 예측하도록 훈련된 미분 가능한 대리 모델 ( $f_\theta$ ) 이 사용됩니다. 노이즈가 있는 평가와 스케일 변화에 대한 견고성을 보장하기 위해, 모델은 후보들의 상대적 순서에 초점을 맞추는 **쌍대 순위 손실 (RankNet)**을 사용하여 훈련되며, 점별 회귀 대신 사용됩니다.
정규화 흐름을 통한 정규화된 최적화: 원시 인코더 임베딩에서 종종 발견되는 이방성과 저밀도 영역을 해결하기 위해, 프레임워크는 가역적 정규화 흐름 (invertible normalizing flow) ( $F_\phi$ ) 을 사용합니다. 이 흐름은 복잡한 프로그램 임베딩 공간을 구조화되고 볼록한 가우시안 사전 공간 ( $u \in \mathbb{R}^d$ ) 으로 매핑합니다. 최적화는 이 사전 공간 내에서 경사 상승을 통해 수행되어, 검색 궤적이 타당하고 유효한 휴리스틱의 다양체에 가깝게 유지되도록 합니다.
소프트 프롬프트를 통한 디코딩: 최적화된 잠재 벡터는 학습된 잠재 - 프롬프트 매핑기 ( $\phi_\omega$ ) 를 사용하여 고정된 디코더 전용 LLM 의 입력 공간으로 투영됩니다. 이 매핑기는 LLM 이 새로운 실행 가능한 휴리스틱 코드를 생성하도록 유도하는 연속적인 "소프트 프롬프트" (조건부 임베딩) 를 생성합니다. 생성된 코드는 구문을 검증하고 벤치마크 인스턴스에서 평가되어 데이터 세트를 업데이트합니다.

전체 과정은 반복적입니다: 시드 프로그램이 인코딩되고, 잠재 사전 공간에서 최적화되며, 새로운 코드로 디코딩되고, 평가된 후, 대리 모델과 흐름 모델을 정제하기 위해 훈련 풀에 추가됩니다.

주요 기여

연속 휴리스틱 발견: 본 논문은 이산 토큰 단위 진화 검색에서 학습된 프로그램 표현에 대한 연속 최적화로의 패러다임 전환을 소개하여, 휴리스틱 설계에 경사 기반 방법의 사용을 가능하게 합니다.
흐름 정규화 검색: 프로그램 임베딩을 구조화된 사전으로 매핑하기 위해 정규화 흐름을 사용하는 것이 필수적임을 보여줍니다. 이러한 정규화는 검색이 잠재 공간의 유효하지 않은 영역으로 표류하는 것을 방지하여, 원시 임베딩 공간에서의 직접 최적화에 비해 생성된 코드의 성공률을 크게 향상시킵니다.
순위 기반 대리 모델: 쌍대 순위 대리 모델의 사용은 노이즈가 있는 평가 환경에서 절대 점수 회귀와 관련된 취약성을 피하면서 경사 상승을 위한 안정적인 학습 신호를 제공합니다.
소프트 프롬프트 조건부: 프레임워크는 잠재 벡터를 소프트 프롬프트로 변환하는 학습 가능한 매핑기를 활용하여, 내부 매개변수를 수정하지 않고도 고정된 LLM 을 유도할 수 있게 합니다.

실험 결과

LHS 프레임워크는 TSP, 용량 제한 차량 경로 문제 (CVRP), 배낭 문제 (KSP), 온라인 박스 패킹 (OBP) 의 네 가지 조합 최적화 작업에서 평가되었습니다.

성능: 경로 작업 (TSP 및 CVRP) 에서 LHS 는 최첨단 성능을 달성하여 이산 진화 기반선 (FunSearch, EoH, ReEvo) 과 MCTS 기반 접근법을 일관되게 능가했습니다. 예를 들어, TSP-200 에서 LHS 는 12.49 의 목적 함수 값을 달성하여 ReEvo(12.58) 와 EoH(13.15) 보다 우수한 결과를 보였습니다.
효율성: LHS 는 경쟁력 있거나 우수한 런타임 효율성을 보여주었습니다. TSP 실험에서 LHS 는 더 나은 결과를 달성하면서 ReEvo(29.61 초) 에 비해 훨씬 적은 시간 (예: TSP-200 의 경우 4.86 초) 을 필요로 했습니다.
절대 연구:
- No-Flow: 정규화 흐름을 제거하고 원시 임베딩 공간에서 직접 최적화한 결과, 생성된 코드의 성공률이 크게 하락했습니다 (74% 대비 61%). 이는 흐름이 검색을 안정화하는 역할을 확인시켜 줍니다.
- No-Grad: 경사 상승을 단순 보간으로 대체한 경우 높은 유효성 (86%) 을 보였으나 최적화 능력은 저조했습니다 (더 나쁜 목적 함수 점수). 이는 고품질 휴리스틱을 발견하기 위해 경사 신호가 필수적임을 강조합니다.
일반화: 이 방법은 검색 단계에서 사용된 것보다 큰 인스턴스 크기 (예: TSP-100, TSP-200) 에서도 잘 수행되는 강력한 크기 간 일반화를 보여주었습니다.

중요성과 주장

저자들은 LHS 가 기존 이산 진화 접근법에 대한 상호 보완적인 방법론적 대안을 제공한다고 주장합니다. 프로그램을 연속 잠재 벡터로 취급함으로써, 이 프레임워크는 실행 기반 평가의 엄격성을 유지하면서 경사 정보를 통해 휴리스틱 설계 공간을 체계적으로 탐색할 수 있게 합니다.

본 논문은 연속 최적화가 고정된 평가 예산 내에서 우수한 목적 함수 값을 달성할 수 있는 강력한 이산 검색의 보완재임을 강조합니다. 그러나 저자들은 LHS 의 효능이 근본적으로 대리 모델의 품질과 초기 훈련 말뚝에 달려 있다는 점을 인정하며 제한 사항에 대해 겸손한 태도를 보입니다. 과도하게 공격적인 최적화 단계는 후보들을 실행 가능한 코드의 다양체에서 벗어나게 할 수 있음을 인정하며, 향후 연구는 전역 탐색과 지역 정제 사이의 균형을 맞추기 위해 LHS 를 이산 진화 연산자와 혼합하는 것을 탐구해야 한다고 제안합니다. 이 프레임워크는 특히 초기 데이터 생성 비용을 분산시킬 수 있는 관련 작업에 대한 반복적 검색이 필요한 시나리오에서 효과적으로 자동화된 알고리즘 설계를 위한 더 미분 가능한 파이프라인을 향한 한 걸음으로 제시됩니다.