기술 요약: 학습된 최적화 정책으로부터의 휴리스틱 프로그램의 교사 인지 진화

1. 문제 제기

조합 최적화 문제 (예: 스케줄링, 라우팅, 그래프 최적화) 는 종종 컴팩트하고 해석 가능한 휴리스틱 규칙에 의존합니다. 이러한 규칙은 빠르고 배포가 용이하지만, 이를 설계하려면 일반적으로 상당한 도메인 전문성과 경험적 튜닝이 필요합니다. 최근 대규모 언어 모델 (LLM) 기반 자동 휴리스틱 설계 (AHD) 방법은 진화적 탐색을 통해 실행 가능한 휴리스틱을 생성하는 데 유망한 결과를 보여주고 있습니다. 그러나 기존 접근법은 진화를 안내하기 위해 주로 지연된 엔드포인트 성능 (전체 롤아웃 후 최종 목적 함수 값) 이나 내부 LLM 피드백 (텍스트성 성찰, 개체군 통계) 에 의존합니다.

이러한 엔드포인트 피드백에 대한 의존성은 탐색 신호의 세분화를 제한합니다. 본 논문은 학습된 최적화 정책(Deep Reinforcement Learning 또는 Neural Combinatorial Optimization 을 통해 훈련됨) 이 풍부하고 행위 수준의 행동 정보를 포함하고 있으며, 이는 현재 미활용되고 있다고 주장합니다. 이러한 신경 정책은 일반적으로 솔버로 사용되지만, 특정 상태에서 후보 결정에 대한 선호도를 제공하는 "행위 교사" 역할을 할 수 있습니다. 과제는 최종 프로그램이 교사를 모방하거나 배포 시 신경 추론을 수행할 필요 없이, 이러한 학습된 정책을 활용하여 정적 실행 가능 휴리스틱 프로그램의 진화를 안내하는 것입니다.

2. 방법론

저자들은 LLM 기반 휴리스틱 탐색 루프에 독립적으로 훈련된 블랙박스 최적화 정책을 외부 행동 교사로서 통합하는 교사 인지 진화 프레임워크를 제안합니다.

핵심 메커니즘: 온-정책 교사 진단

교사를 배포하거나 직접 모방에 사용하는 대신, 이 프레임워크는 후보 휴리스틱 프로그램이 실행 중에 방문하는 상태에 대해 교사를 쿼리합니다.

• 상태 샘플링: 후보 휴리스틱 $h$에 대해 시스템을 롤아웃하여 상태의 궤적 $S_h$를 생성합니다.
• 교사 쿼리: 이러한 특정 상태에 대해 교사 정책 $T$를 쿼리하여 선호하는 행동 $a_T(s)$ 또는 행동 점수 $Q_T(s, a)$를 결정합니다.
• 정렬 신호: 시스템은 다음을 계산합니다:
  • Top-1 일치: 후보의 행동이 교사의 선호 행동과 일치하는 빈도.
  • 정규화된 교사 가치: 점수가 제공되는 경우, 실현 가능한 행동 집합에 대한 후보가 선택한 행동의 정규화된 가치.
  • 백분위 순위: 교사의 순서에 따른 후보 행동의 순위.

교사 유도 성찰 및 수정

이러한 진단 신호는 LLM 분석가를 위한 실행 가능한 피드백으로 변환됩니다. 경량 작업 인터페이스 어댑터는 피드백이 문맥상 관련성이 있도록 보장합니다. 분석가 LLM 은 다음 세 가지 특정 교사 유도 연산자를 기반으로 수정 개요를 생성합니다:

1. 구조적 재작성: 불일치가 반복적인 구조적 실패를 드러낼 때 고수준 의사결정 구성 요소를 수정합니다.
2. 매개변수 보정: 프로그램이 합리적인 행동을 선택하지만 교사에 비해 지역적으로 잘못 보정된 경우 가중치, 임계값 또는 게이트를 조정합니다.
3. 메커니즘 수준 융합: 성능이 우수한 메커니즘과 정렬이 우수한 메커니즘을 결합하여 교사에서 파생된 행동 편향을 수용하면서도 성능을 유지합니다.

개체군 관리

이 프레임워크는 파레토 방식의 비우세 정렬을 사용하는 다목적 선택 전략을 채택합니다. 각 후보는 벡터 $z(h) = (F(h), -Align(h))$로 평가되며, 여기서$F(h)$는 최소화되는 작업 목적 함수이고$Align(h)$는 최소화되는 교사 정렬도입니다.

• 선택: 최종 휴리스틱은 교사 충실도가 아닌 작업 성능에 기반하여 선택됩니다. 이는 출력이 특정 작업을 위해 최적화된 정적이며 효율적인 프로그램으로 유지되도록 보장하며, 교사의 압축 버전이 아님을 의미합니다.

3. 주요 기여

본 논문은 네 가지 주요 기여를 주장합니다:

1. 형식화: LLM 기반 휴리스틱 진화를 위한 외부 행동 교사로서 독립적으로 훈련된 블랙박스 최적화 정책을 사용하는 개념을 도입합니다.
2. 샘플링 온-정책 교사 정렬: 후보가 유도한 상태에 대해 교사를 쿼리하고 그 선호도를 지역적 행동 탐색 신호로 변환하는 방법으로, 표준 모방 학습과 구별됩니다.
3. 교사 인지 성찰적 진화: 교사 정렬 요약과 불일치 사례를 활용하여 휴리스틱 프로그램의 구조적 및 매개변수적 수정을 안내하는 프레임워크입니다.
4. 실증적 검증: JSSP, TSP, CVRP, MaxCut 의 네 가지 순차적 조합 최적화 도메인 전반에 걸친 실증을 통해 학습된 정책이 정적, 해석 가능, 효율적인 휴리스틱 발견을 효과적으로 안내할 수 있음을 입증합니다.

4. 실험 결과

이 방법은 네 가지 벤치마크 (Job-Shop Scheduling (JSSP), Traveling Salesman Problem (TSP), Capacitated Vehicle Routing Problem (CVRP), MaxCut) 에서 평가되었습니다.

• 성능: 제안된 방법은 분포 내 및 분포 외 (OOD) 설정에서 모두 성능 주도 LLM 베이스라인 (EoH, ReEvo) 과 고전적 디스패칭 규칙보다 일관되게 우수한 성과를 거두었습니다.
  • JSSP: 10x10, 15x15, 20x20 인스턴스에서 최고의 메이크스팬을 달성했으며, 더 큰 무작위 인스턴스와 Taillard 벤치마크에 대한 우수한 일반화를 보여주었습니다.
  • 라우팅 (TSP/CVRP): LLM 진화 휴리스틱 중 최고의 솔루션 품질을 달성하여 특수 솔버 (LKH 등) 와의 격차를 줄이면서도 정적 프로그램의 속도를 유지했습니다.
  • MaxCut: 훈련 분포에서 경쟁력 있는 성능을 보였으며, Barabási–Albert 에서 Erdős–Rényi 로의 그래프 분포 변경 및 다양한 규모에 대한 강력한 전이성을 보여주었습니다.
• 효율성: 결과적으로 생성된 휴리스틱은 배포 시 신경 추론이 필요 없는 정적 실행 가능 프로그램입니다. 이들은 안내에 사용된 학습된 신경 정책 (교사) 보다 훨씬 빠릅니다.
• 절대 실험: 교사에서 파생된 피드백을 제거 ("Performance-only") 하면 결과가 일관되게 저하되어 행동 신호의 가치를 확인시켰습니다. 특정 구성 요소 (분석가 안내, 교사 유도 연산자, 또는 파레토 업데이트) 를 제거하는 것도 성능 저하, 특히 OOD 일반화에서 성능 저하를 초래했습니다.

5. 중요성 및 주장

본 논문은 학습된 최적화 정책을 자동 휴리스틱 발견을 위한 행동 피드백 소스로 재사용할 수 있다고 주장합니다. 그 중요성은 신경 정책의 역할을 최종 솔버에서 지역적 의사결정 수준 피드백의 원천으로 전환하는 데 있습니다.

• 상호 보완성: 교사 선호도는 엔드포인트 적합성과 보완적인 신호를 제공하여, 유용한 학습된 편향을 유지하면서 특정 약점을 수정하는 휴리스틱으로 탐색를 안내합니다.
• 정적 vs. 신경: 이 프레임워크는 학습된 신경 정책의 높은 성능과 정적 휴리스틱의 해석 가능성/효율성 사이의 간극을 성공적으로 연결합니다.
• 겸손함: 저자들은 방법론이 정렬 가능한 학습된 교사, 작업별 인터페이스 어댑터, 분석가 호출이 필요하다는 한계를 인정합니다. 모든 솔버를 대체하는 것이 아니라 정적 휴리스틱의 발견 과정을 개선하는 것이라고 주장하지 않습니다.

요약하자면, 이 연구는 학습된 정책을 "모방해야 할 솔버"가 아닌 "행위 교사"로 취급함으로써, 심층 학습의 풍부한 지역적 의사결정 신호를 활용하면서도 그 계산 오버헤드는 물려받지 않는 고성능이자 효율적인 정적 휴리스틱을 진화시킬 수 있음을 보여줍니다.