RL and Mathematical Programming: 비즈니스 업무 최적화

# 최적화: 수학적 계획과 강화학습의 가교

수십 년 동안 고전적인 수학적 계획 방법은 경로 최적화, 생산 계획, 물류 등 비즈니스 프로세스를 자동화하고 최적화하는 기반이 되어 왔습니다. 그러나 인공지능, 특히 강화학습(RL)의 발전으로 중요한 질문이 제기됩니다: 이러한 새로운 패러다임이 복잡한 최적화 문제를 해결하는 데 전통적 접근법을 능가하거나 보완할 수 있을까요? 이 글에서는 조합 최적화에서 RL의 잠재력을 탐구하며, 통합 전략과 독립형 솔루션을 분석하고, 구체적인 물류 사례를 살펴봅니다.

조합 최적화에서의 RL: 하이브리드와 독립 접근법

강화학습의 발전은 반복적인 테스트 덕분인데, 각 작업이 모델 개선의 실험장이 됩니다. 이 시행착오 접근법으로 RL은 가능한 해의 공간이 방대하고 복잡한 조합 최적화(CO) 문제에 적응할 수 있게 되었습니다. CO에서 RL은 기존 알고리즘을 강화하는 구성 요소나 독립적인 솔루션 탐색 기술로 두 가지 주요 방식으로 활용됩니다. 이는 계산 복잡성을 극복하고 시스템 적응성을 높이는 새로운 가능성을 열어줍니다.

전통 최적화 방법과의 RL 통합

RL을 고전 최적화 방법과 통합하면 각 접근법의 강점을 활용할 수 있습니다. RL은 경험 학습과 적응성을 제공하며, 고전 알고리즘은 수렴 보장과 검증된 휴리스틱을 줍니다. 이 하이브리드 접근은 순수 고전 방법에서 지수적 복잡성 증가를 겪는 문제를 효과적으로 해결합니다.

주요 통합 전략:

초기 해 생성기로서의 RL: RL 에이전트가 고품질 초기 해를 학습해 생성한 후, 분기 한정법이나 선형 계획 같은 정확 방법으로 다듬습니다. 이는 최적 해 탐색 시간을 크게 줄여줍니다. 예를 들어 여행 세일즈맨 문제(TSP)에서 RL이 근최적 경로를 빠르게 제안할 수 있습니다.
지역 탐색을 활용한 하이브리드 알고리즘: RL이 개선 방향을 식별하고, 2-opt, 3-opt 같은 지역 휴리스틱이 구체적 수정 작업을 합니다. 에이전트는 현재 상태에서 가장 효과적인 연산을 선택하도록 학습해 계산 부하를 줄이고 수렴을 가속화합니다.
메타휴리스틱 매개변수 적응을 위한 RL: 유전자 알고리즘, 시뮬레이티드 어닐링 같은 메타휴리스틱은 조정 가능한 매개변수가 많습니다. RL 에이전트가 솔루션 과정에서 이 매개변수를 동적으로 조정해, 예를 들어 유전자 알고리즘의 교차 및 돌연변이 확률을 현재 진행 상황에 맞게 최적화합니다.
문제 분해를 위한 계층적 RL: 복잡한 문제를 하위 문제로 분해해 각 RL 에이전트나 고전 알고리즘으로 해결합니다. TSP에서 상위 레벨에서 RL이 도시를 클러스터링하고, 하위 레벨에서 정확 방법이 클러스터 내 경로를 최적화하는 식입니다.
분기 한정법에서의 RL: 다음 분기 선택, 노드 잠재력 평가, 경계 예측으로 탐색 공간을 pruning해 알고리즘 효율성을 높입니다.

신경 조합 최적화(NCO): 현대 구현과 한계

신경 조합 최적화(NCO)는 신경망과 조합 최적화 요구를 결합한 분야입니다. NCO는 빠른 해 생성이 필요한 동적 문제나 전통 방법이 너무 느린 시나리오에서 특히 효과적입니다. 그러나 현재 NCO 능력은 제한적이며 모든 문제의 만능 솔루션이 아닙니다. 성공 사례는 주로 학술 환경이나 특정 제약이 있는 소규모 문제에 국한됩니다.

NCO로 이론적으로 해결 가능한 문제 예시 (크기와 조건에 주의):

여행 세일즈맨 문제(TSP): 주어진 도시를 한 번씩 방문하는 최단 경로 찾기. Pointer Networks나 그래프 신경망(GNN)으로 순열 생성.
차량 경로 문제(VRP): 용량이나 시간 창 제약을 고려한 차량 플릿 경로 최적화.
배낭 문제: 무게/부피 제약 하 최대 가치 아이템 선택.
집합 피복 문제: 모든 원소를 덮는 최소 집합 선택.
잡숍 스케줄링: 작업을 기계에 배정해 총 완료 시간 최소화.
그래프 색칠: 인접 정점에 색상 최소화, 스케줄링에 사용.
시설 위치 문제: 창고나 충전소 최적 배치.
공급망 최적화: 불확실성을 고려한 조달, 생산, 배송 계획.
대입 문제: 택시-승객 같은 에이전트-작업 최적 매칭.
SAT 문제: 불리언 공식 만족성 판단.

이러한 예시에도 불구하고 고전 공식화에서 RL의 이론적 능력과 실무 적용 간 큰 격차가 있습니다. 이 격차를 메우려면 추가 연구가 필요합니다.

실무 사례: RL을 활용한 화물 운송 연료 정차 최적화

물류 분야 실무 문제로 화물 운송의 연료 비용 최적화를 보죠. 연료 비용은 운영 비용의 상당 부분(종종 1/3)을 차지합니다. 경로상 주유소 가격 차이를 고려한 전략적 정차 계획으로 비용을 크게 줄일 수 있습니다. 종종 운전자에게 맡겨지는데, 이들은 비용 최소화에 항상 집중하지 않아 최적화 여지가 큽니다.

비즈니스 과제: 경로상 최적 주유소 위치와 주유량 결정, 총 비용 최소화하며 제약 준수:

최소 연료 수준: 경로 어느 지점에서도 탱크 연료가 지정 임계값 아래로 떨어지지 않음.
탱크 용량: 주유량이 최대 탱크 용량 초과 금지.
최종 연료 수준: 경로 끝에서 탱크에 최소 임계량 연료 보유.
최소 주유량: 경제적으로 viable한 주유, 지정 최소량 초과.

RL 적용 시 연속 주유량 공간을 이산화합니다. 예: 사용 가능 탱크 공간의 0%, 25%, 50%, 75%, 100% 다섯 옵션. 연구 목적으로 결과 왜곡 없이 RL 상태 관리를 단순화합니다.

비선형 계획으로 문제 공식화

주유소 선택과 주유량 최적화 문제를 비선형 계획으로 공식화합니다. 다음 구성 요소:

색인:

i — 주유소 색인.

상수:

c_i — 주유소 i-1과 i 간 연료 소비량.
p_i — 주유소 i 주유 비용.
v_min — 주유소 최소 주유량.
s_0, s_n — 경로 시작/끝 탱크 연료량.
s_lb, s_ub — 탱크 최소/최대 연료량.
w — 최소 연료 수준 위반 패널티 크기.

변수:

s_i — i번째 주유소 주유 후 탱크 연료량 (실수).
v_i — i번째 주유소 주유량 (실수).
q_i — i번째 주유소 주유 비율 (정수, 0~4: 0%,25%,50%,75%,100%).
b_i — i번째 주유소 주유 여부 지표 (이진).
z_i — 최소 연료 수준 위반 정도 (실수).

목적 함수: 총 연료 비용과 최소 연료 위반 패널티 최소화:

min Σ (p_i v_i + w z_i) 모든 i에 대해.

제약:

연료 균형: s_i = s_{i-1} - c_i + v_i 모든 i. 다음 주유소 도달 및 주유 후 연료 변화 반영.
주유 배수: v_i = 0.25 q_i (s_ub - s_{i-1} + c_i) 모든 i. 사용 가능 탱크 공간 비율로 주유량 정의.
최소 연료 수준: s_{i-1} - c_i + z_i >= s_lb 모든 i. 다음 주유소 도달 연료 충분, 위반 시 패널티 z_i 허용.
경로 끝 연료: s_{|I|} - c_{|I|+1} >= s_n. 경로 끝 특정 연료량 요구.
v_i >= v_min * b_i 모든 i. 충분량 주유만 허용.
주유 지표: q_i <= 4 * b_i 모든 i. 주유 비율을 이진 지표와 연동.

이 공식화에서 최소 연료량에 "soft" 제약을 사용해 모든 제약 엄격 준수가 불가능한 현실에 적응합니다. 모델 운영 신뢰성을 높입니다. 이산 행동 공간과 위반 패널티를 가진 복잡 문제에 RL 적용으로 순수 고전 방법으로는 어려운 효과적 전략을 찾을 수 있으며, 특히 수백 주유소와 동적 가격 변화 시 유리합니다.

주요 요약

RL은 고전 방법을 보완, 대체 아님: 강화학습은 전통 최적화 방법을 완전히 대체하려 하지 않고 통합해 효율성을 높이거나 한계를 극복합니다.
하이브리드 전략이 핵심: RL이 초기 해 생성, 메타휴리스틱 매개변수 적응, 문제 분해를 담당하고 정확 방법이 세부 다듬는 하이브리드 알고리즘이 가장 유망합니다.
NCO는 확장되지만 한계 있음: 신경 조합 최적화는 복잡 문제 해결 잠재력을 보이지만 문제 크기와 특이성으로 제한적, 일반화 연구 필요.
물류 실무 적용성: 화물 운송 연료 정차 최적화는 RL이 운영 비용 절감에 적용되는 대표 사례로, 수동 관리보다 유연하고 경제적입니다.
RL을 위한 이산화: 연속 변수를 이산(예: 주유량)으로 변환하는 것은 실무 비즈니스 문제를 RL 알고리즘에 적합하게 만드는 효과적 방법으로, 에이전트 상태/행동 관리를 단순화합니다.

— Editorial Team