기술 요약: 이성분 결합 조합 최적화를 위한 CoEvo-AHD

1. 문제 정의

본 논문은 솔루션이 서로 의미론적으로는 구별되지만 상호 의존적인 두 개의 의사결정 구성 요소로 이루어진 이성분 결합 조합 최적화(Bi-Component Coupled Combinatorial Optimization, CO) 문제를 다룹니다. 핵심 과제는 한 구성 요소의 수정이 다른 구성 요소의 상태에 전적으로 의존하여 타당성이나 목적 함수 값이 결정된다는 점입니다. 결과적으로, 연산자(operator)의 효용은 내재적인 것이 아니라 **관계적(relational)**입니다. 즉, 단독으로는 잘 작동하는 연산자가 두 번째 구성 요소의 하위 최적 상태와 결합될 경우 전체 솔루션을 저하시킬 수 있습니다.

저자들은 이 프레임워크를 두 가지 대표적인 문제에 적용하여 구현하였습니다:

• Traveling Thief Problem (TTP): 경로 최적화(TSP)와 패킹(0–1 Knapsack Problem)을 결합합니다. 투어 순서가 운송되는 화물의 무게에 따른 이동 속도에 영향을 미치며, 패킹 계획은 각 단계에서 운송되는 무게를 결정합니다.
• Traveling Purchaser Problem (TPP): 시장 선택/경로 최적화와 조달 결정을 결합합니다. 방문 순서와 시장 선택은 가능한 구매 옵션과 비용을 결정하며, 구매 결정은 특정 시장을 방문하는 가치에 영향을 미칩니다.

기존의 LLM 기반 자동 휴리스틱 설계(AHD) 방식은 일반적으로 휴리스틱을 고립된 알고리즘 단위나 탐색 전략(예: 생성 vs. 복구)으로 진화시킵니다. 이러한 방식은 이성분 결 결합 문제에서 요구되는 **문제 구조 유도형 상보성(problem-structure-induced complementarity)**을 포착하지 못합니다. 즉, 이 문제에서는 이질적인 솔루션 구성 요소 전반에 걸쳐 시너지를 낼 수 있도록 연산자들이 공동 진화되어야 합니다.

2. 방법론: CoEvo-AHD

저자들은 쌍을 이루는 구성 요소 연산자를 자동으로 발견하고 정교화하기 위해 설계된 LLM 기반 이중 인구 공동 진화 프레임워크인 CoEvo-AHD를 제안합니다. 이 프레임워크는 네 단계로 작동합니다:

2.1 이중 인구 초기화 (Dual-Population Initialization)

구성 요소 A(예: 경로 연산자)를 위한 $P_A$와 구성 요소 B(예: 패킹 연산자)를 위한 $P_B$라는 두 개의 별도 연산자 인구를 유지합니다.

• 초기화: 인구는 수동으로 지정된 시드 연산자와 LLM이 생성한 연산자의 혼합으로 시작됩니다.
• 검증: 생성된 모든 연산자는 인구에 진입하기 전 구문, 인터페이스, 실행 범위 및 구성 요소 타당성 검증을 거칩니다.
• 인터페이스: 연산자는 글로벌 컨텍스트를 위한 공유 정보 메모리와 외부 도구에 의존하여, 자신이 담당하는 특정 구성 요소에 대한 후보 업데이트만을 반환합니다.

2.2 협력적 평가 (Cooperative Evaluation)

연산자를 독립적으로 점수화하는 전통적인 방식과 달리, CoEvo-AHD는 완전한 솔루션에 대한 **쌍 실행(paired execution)**을 통해 연산자를 평가합니다.

• 선택: Thompson Sampling 전략을 사용하여 각 탐색 재시작 시 $P_A$에서 하나의 연산자와 $P_B$에서 하나의 연산자를 선택합니다.
• 교대 최적화: 선택된 쌍은 탐색 궤적 내에서 교대로 호출됩니다. 예를 들어, 경로 연산자가 도시 순열을 제안하면, 이는 패킹 연산자(또는 그 반대)로 전달됩니다.
• 복구 및 재구성: 구성 요소들이 결합되어 있기 때문에 중간 후보가 불가능할 수 있습니다. 프레임워크는 **도구 증강 문제 환경(tool-augmented problem environment)**을 활용하여 타당성 복구, 재구성 및 전체 목적 함수 평가를 수행합니다.
• 공유 정보: 가변 딕셔너리(shared_info)를 통해 연산자들이 직접 다른 구성 요소의 로직을 덮어쓰지 않으면서도 소프트 검색 신호(예: 부하 프로필, 후보 삽입 큐)를 교환할 수 있도록 합니다.

2.3 인구 관리 및 진화 (Population Management & Evolution)

프레임워크는 인구를 정교화하기 위해 공동 진화 루프를 사용합니다:

• 점수 산정: 보상은 완전한 결합 솔루션의 개선도를 기준으로 계산됩니다. 이 보상은 세 가지 통계치, 즉 $o_A$와 $o_B$에 대한 개별 점수, 그리고 특정 연산자 쌍에 대한 **쌍별 시너지 점수($S_{ij}$)**를 업데이트합니다.
• 가지치기: 성과가 낮은 연산자는 각각의 인구에서 제거됩니다.
• LLM 기반 진화: 빈 자리는 세 가지 진화 연산을 통해 채워집집니다:
  1. 구성 요소 내 돌연변이(Intra-component Mutation): 단일 부모 연산자를 정교화합니다.
  2. 구성 요소 내 동종 교차(Intra-component Homogeneous Crossover): 동일한 인구 내의 두 연산자를 재결합합니다.
  3. 구성 요소 간 합동 교차(Cross-Component Joint Crossover): 시너지 점수를 바탕으로 가장 성능이 좋은 쌍 $(o_A^*, o_B^*)$을 선택하고, LLM이 이들을 통합되고 조정된 하나의 엔티티로 다시 쓰도록 유도합니다. 이는 호환 가능한 통신 프로토콜과 상보적인 탐색 가정을 가진 연산자 생성을 장려합니다.

2.4 도구 증강 환경 (Tool-Augmented Environment)

LLM이 비효율적이거나 오류가 발생하기 쉬운 저수준 코드를 생성하는 것을 방지하기 위해, 프레 lack워크는 핵심 연산(예: 로컬 서치 델타 계산, 그리디 재구성, 타당성 체크)을 표준화된 호출 가능 도구로 캡슐화합니다. 이를 통해 LLM 생성 연산자가 고수준의 이웃 설계 및 구성 요소 간 조정에 집중할 수 있게 합니다.

3. 주요 기여

1. 문제 정식화: 본 논문은 LLM 기반 AHD를 이성분 결합 CO에 특화하여 정식화하였으며, 연산자의 효용을 관계적이며 이질적인 솔루션 구성 요소 전반에 걸친 공동 평가가 필요한 것으로 정의했습니다.
2. CoEvo-AHD 프레임워크: 다음과 같은 특징을 가진 새로운 공동 진화 아키텍처를 제안합니다:
   • 구성 요소별 연산자 인구.
   • 교차 구성 요소 상호작용을 포착하기 위한 쌍 실행 기반 평가.
   • 상보적인 연산자 쌍 선택을 가이드하기 위한 쌍별 시너지 점수 산정.
   • 상호 호환 가능한 연산자를 진화시키기 위한 구성 요소 간 합동 교차.
3. 구조화된 통신 및 도구화: 구조화된 구성 요소 간 통신 프로토콜과 문제 특화 연산을 표준화하는 도구 증강 환경을 도입하여, LLM이 견고하고 고수준의 휴리스틱 로직을 생성할 수 있도록 했습니다.

4. 실험 결과

프로임워크는 TTP 및 TPP 벤치마크에서 최신 전통적 휴리스틱 및 최근 LLM 기반 베이스라인들과 비교 평가되었습니다.

• Traveling Thief Problem (TTP):

  • CoEvo-AHD는 소-중규모 인스턴스(TTP20, TTP50)에서 MATLS, S5, CoCo와 같은 베이스라인을 능가하며 최고의 결과를 달성했습니다.
  • 대규모 인스턴스(TTP100, TTP200)에서는 CoCo에 이어 두 번째로 좋은 전체 평균을 기록했으나, MATLS와 S5보다는 크게 앞섰습니다.
  • 이는 프레임워크가 작은 탐색 공간에서는 결합을 효과적으로 포착하지만, 매우 큰 인스턴스에서는 탐색 깊이 측면에서 어려움이 있음을 시사합니다.

• Traveling Purchaser Problem (TPP):

  • CoEvo-AHD는 뚜렷한 전반적 우위를 보여주었습니다. 5개의 인스턴스 규모(150×100, 150×150과 같은 대규모 포함)에서 최고의 결과를 얻었으며, 나머지 3개 규모에서도 두 번째로 좋은 성적을 거두었습니다.
  • 두 번째로 좋은 베이스라인(TA) 대비 평균 목적 함수 값을 약 2.76% 감소시켰으며, ALNS와 비교해서는 최대 **11.42%**까지 감소시켰습니다.
  • 결과는 이 프레임워크가 TPP에서의 경로 최적화와 조달 결정 사이의 시너지를 활용하는 데 특히 효과적임을 나타냅니다.

• 절제 연구 (Ablation Studies):

  • 이중 인구 공동 진화를 제거(하나의 구성 요소만 진화)했을 때 상당한 성능 저하(예: TPP에서 약 11% 하락)가 발생하여, 구성 요소를 분리하여 최적화하는 것이 불충분함을 확인했습니다.
  • 도구 증강 환경을 제거했을 때도 성능 저하(예: TTP에서 약 5.5% 하락)가 발생하여, 신뢰성과 효율성을 위한 표준화된 인터페이스의 중요성을 입증했습니다.

5. 의의 및 주장

본 논문은 CoEvo-AHD가 LLM 기반 AHD의 패러다임을 고립된 알고리즘 역할을 생성하는 것에서 문제 구조 유도형 연산자 상보성을 모델링하는 것으로 전환시킨다고 주장합니다. 이질적인 연산자 인구를 명시적으로 공동 진화시키고 이를 합동 실행을 통해 평가함으로써, 프레임워크는 결정 하부 구조 간의 강력한 결합을 처리할 수 없는 기존 방식의 한계를 해결합니다.

저자들은 이 연구가 결정 구성 요소들이 깊게 상호 의존하는 복잡한 실제 최적화 문제에 대해 더 일반화 가능한 자동 휴리스틱 설계를 향한 단계라고 위치시킵니다. 또한, 프레임워크가 매우 경쟁력 있지만 탐색 깊이와 매우 큰 규모의 인스턴스에 대한 견고성 측면에서 개선의 여지가 남아 있음을 겸허히 언급하며, 향-후 연구를 통해 두 개 이상의 결합된 구성 요소를 가진 문제로 확장하는 것을 목표로 한다고 밝혔습니다.