Learning to Schedule Heuristics for the Simultaneous Stochastic Optimization of Mining Complexes
원문 초록
The simultaneous stochastic optimization of mining complexes (SSOMC) is a large-scale stochastic combinatorial optimization problem that simultaneously manages the extraction of materials from multiple mines and their processing using interconnected facilities to generate a set of final products, while taking into account material supply (geological) uncertainty to manage the associated risk. Although simulated annealing has been shown to outperform comparing methods for solving the SSOMC, early performance might dominate recent performance in that a combination of the heuristics' performance is used to determine which perturbations to apply. This work proposes a data-driven framework for heuristic scheduling in a fully self-managed hyper-heuristic to solve the SSOMC. The proposed learn-to-perturb (L2P) hyper-heuristic is a multi-neighborhood simulated annealing algorithm. The L2P selects the heuristic (perturbation) to be applied in a self-adaptive manner using reinforcement learning to efficiently explore which local search is best suited for a particular search point. Several state-of-the-art agents have been incorporated into L2P to better adapt the search and guide it towards better solutions. By learning from data describing the performance of the heuristics, a problem-specific ordering of heuristics that collectively finds better solutions faster is obtained. L2P is tested on several real-world mining complexes, with an emphasis on efficiency, robustness, and generalization capacity. Results show a reduction in the number of iterations by 30-50% and in the computational time by 30-45%.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
대규모 최적화 학습: 확률적 조합 최적화를 위한 Benders 분해-TransfORmer 프레임워크
Learning to Optimize at Scale: A Benders Decomposition-TransfORmers Framework for Stochastic Combinatorial Optimization
우리는 대규모 2단계 확률적 혼합정수 프로그램을 풀기 위한 학습 보강 Benders 분해 프레임워크를 제안한다. 우리는 수요 불확실성 하의 2단계 확률적 용량 제약 lot-sizing 문제(TSSCLSP)에 초점을 맞춘다. 우리의 방법은 시나리오 하위 문제(subproblem)에 대한 고품질 근사해를 신속하게 생성하기 위해 사전학습된 TransfORmer 모델을 사용하여 분해의 수렴을 가속화한다. 이 하이브리드 전략은 TransfORmer 예측을 활용해 강력한 최적성 및 실행 가능성 컷(cut)을 생성하여 Benders 마스터 문제를 효과적으로 안내한다. 우리의 프레임워크에는 새로운 확장 가능 생성 메커니즘이 포함되어, 고정된 시간 구간(horizon)에서 학습된 모델이 임의 길이의 인스턴스를 풀 수 있게 한다. 검토한 테스트 세트에서 우리의 방법은 T = 270까지의 인스턴스를 풀며, 이는 기존 접근법으로는 다루기 어려웠던 규모이며, 생성된 하위 문제 해에서 실행 불가능성(infeasibility)을 0으로 유지한다. 이는 고전적 분해 알고리즘 내에 내장된 강력한 대리(surrogate) 솔버로서 TransfORmer의 잠재력을 보여준다.
방사선 치료 스케줄링을 위한 최적화 모델 비교
Comparing Optimization Models for Radiotherapy Scheduling
방사선 치료 스케줄링 문제(Radiotherapy Scheduling Problem, RTSP)는 방사선 치료를 받는 환자들에 대한 최적 일정을 결정하는 문제로, 방사선 치료가 암 치료에서 핵심적인 역할을 하므로 임상 결과에 큰 영향을 미치는 과업이다. 하루가 끝날 때 새로 도착한 모든 환자를 함께 스케줄링하는 일일 배치 접근법은 정수 선형 계획(Integer Linear Programming)으로 모델링되며, 현재 RTSP에 대한 가장 효과적인 방법 중 하나이다. 그러나 이러한 형식화는 시간과 메모리 측면에서 상당한 계산 자원을 필요로 한다. 본 연구에서는 RTSP First Fit과 RTSP Best Fit이라는 두 가지 새로운 탐욕적 휴리스틱(greedy heuristics)을 개발하고, 이를 시뮬레이티드 어닐링(Simulated Annealing, SA) 접근법의 구성적 휴리스틱(constructive heuristics)으로 사용하여 스케줄링을 최적화함으로써 이러한 한계를 해결한다. 제안된 방법——휴리스틱 단독 및 SA와의 결합——은 공개 데이터셋에서 두 가지 서로 다른 최신 정확 솔버(exact solvers)로 풀린 정수 선형 프로그램(integer linear program) 형식화와 비교하여 평가된다. 평가 지표에는 환자 대기 시간, 선호도 충족, 선형 가속기(linear accelerator) 배정 변경(네 가지 서로 다른 가중치 구성으로 집계)을 포착하는 여섯 가지 스케줄링 목표, 풀이 시간, 메모리 소비가 포함된다. 결과는 새로운 휴리스틱이 정확한 방법들의 해에 근접한 해를 달성하면서 실행 시간과 메모리 사용량을 극적으로 줄인다는 것을 보여준다. 또한 SA와 결합하면 실행 시간과 메모리 사용량을 낮게 유지하면서 해의 품질을 더욱 향상시킨다.
지능의 그림자 가격: LLM 추론에서의 품질 저하와 재시도 피드백
The Shadow Price of Intelligence: Quality Degradation and Retry Feedback in LLM Inference
대규모 언어 모델 제공자는 연산 자원이 제약되어 있으며, 혼잡에 대한 일반적인 대응은 서비스를 저하시키는 것이다. 즉, 질의를 더 작은 모델로 라우팅하거나, 추론 예산을 줄이거나, 컨텍스트 윈도를 단축한다. 만족스럽지 못한 답을 받은 사용자는 재시도하여 시스템이 바쁜 동안 부하를 늘리거나, 이탈하여 잠재적으로 고객 이탈로 이어진다. 우리는 추론 서비스를 서비스 품질이 제공자의 의사결정인 제어 문제로 모델링한다. 재시도를 서비스율에 포함한 2국면 유체 근사는 닫힌 형태의 궤적과 교차 시간을 제공하므로, 품질 등급에 대한 동적 계획법에 시뮬레이션이 필요하지 않다. 우리는 더 약한 등급이 작업당 에너지는 덜 쓰지만 작업당 용량은 더 쓰는 영역을 규명하고, 유체 모델에서 그러한 등급으로의 반응적 스로틀링이 큐가 해소되지 못하게 할 수 있음을 보인다. 이질적인 고객이 있는 경우 이 문제는 재시도로 부풀려진 용량 계수를 갖는 수송 문제가 되며, 최적 라우팅은 $c\mu$ 유형의 지수를 따르고, 용량 제약의 쌍대는 클래스와 시간별로 질의 하나를 더 처리하는 한계 비용을 제공한다. 우리는 공개 벤치마크 데이터로 보정한 다섯 가지 사례에서 이 방법을 예시한다.
SupplyNetPy: 임의 공급망 및 재고 네트워크의 고충실도 모델링과 시뮬레이션을 위한 오픈소스 Python 라이브러리
SupplyNetPy: An Open-Source Python Library for High-Fidelity Modeling and Simulation of Arbitrary Supply Chain and Inventory Networks
본 논문은 임의의 다단계 구조를 갖는 공급망 네트워크의 모델링 및 이산 사건 시뮬레이션을 위한 오픈소스 Python 라이브러리인 SupplyNetPy를 소개한다. 이 라이브러리는 다양한 보충 정책, 부패 가능 재고, 노드(node) 장애, 확률적 수요 및 리드 타임을 지원한다. 모든 컴포넌트는 상속을 통해 확장 가능하다. 사용자는 노드와 링크 속성을 가진 그래프로 공급망을 기술하며, 라이브러리는 시뮬레이션을 처리하고 로그 및 노드·네트워크 수준의 상세 성능 보고서를 제공한다. 본 논문은 SupplyNetPy의 개발 동기, 설계, 주요 기능, 아키텍처와 함께 상세한 검증(validation) 결과(분석적 벤치마크, 상용 도구, 발표된 사례 연구와의 비교)를 제시한다. SupplyNetPy 개발의 핵심 동기는 복잡한 모델의 프로그래밍 방식 생성 및 시뮬레이션으로, 설계 공간 탐험(exploration), 가상 시나리오 분석, 학습(training) 데이터 생성, 공급망 디지털 트윈을 가능하게 하는 데 있다.
학생 학습 자원 배분을 위한 유전 알고리즘
A genetic algorithm for student academic resource allocation
개별 학생에게 학습 자원을 최적으로 배분하는 것은 학습자 다양성을 다루고 공평한 교육 성과를 촉진하는 데 필수적이다. Erasmus+ KA220-SCH 프로젝트의 틀 안에서, 본 논문은 고등학교 수학 학생을 위한 교육 자료 선택을 엄격한 학습 시간 제약을 따르는 0-1 이진 조합 최적화(optimization) 문제로 모델링한다. 이 공식화의 NP-hard 복잡도를 고려할 때, 자원 카탈로그가 확대될수록 정확한 해법은 계산적으로 다루기 어려워진다. 이 과제를 해결하기 위해, 우리는 이진 결정 공간을 효과적으로 탐색하기 위해 특화된 제약 복구 메커니즘과 통합된 유전 알고리즘(Genetic Algorithm)을 제안한다. 10회의 독립 실행에 걸친 실험적 평가는 빠른 수렴, 높은 해 품질, 그리고 서로 다른 기본 시드에 걸친 강한 알고리즘적 안정성을 보여준다. 이 결과는 중등 교육에서 실시간 의사결정 지원 시스템을 위한 메타휴리스틱(metaheuristic) 접근법의 실용적 유용성을 확인한다.
LLM을 활용한 제로샷 교차 문제 일반화를 위한 다중 작업 진화
Multi-Task Evolution for Zero-Shot Cross-Problem Generalization using LLMs
다양한 조합 최적화(combinatorial optimization) 문제를 위한 효과적인 휴리스틱(heuristic)을 설계하는 것은 상당한 전문성과 반복적인 탐색을 필요로 합니다. 대규모 언어 모델(LLM)은 휴리스틱 생성과 개선을 자동화하지만, 휴리스틱 탐색은 일반적으로 최적화 대상 문제의 평가 피드백에 의존합니다. 따라서 소스 작업 피드백만을 사용하여 새로운 문제 정의로 일반화하는 것은 여전히 핵심적인 과제로 남아 있습니다. 본 논문에서는 제로샷(zero-shot) 교차 문제 일반화를 위한 LLM 기반 다중 작업 진화 프레임워크인 MECo를 소개합니다. MECo는 작업 조건부 휴리스틱 개체군을 유지하며, 교차 작업 개체군 성능에 기반한 전이 격차(transfer gap)를 활용해 이들의 상호작용을 유도합니다. 이러한 상호작용은 휴리스틱의 전이와 재조합을 가능하게 합니다. 그런 다음 상호보완적 선택 기준을 통해 각 개체가 소스 조합에 대해 제공하는 추가적인 커버리지를 보상함으로써 간결한 휴리스틱 세트를 구성합니다. 선택된 세트는 추가적인 탐색이나 적응 과정 없이 타깃 문제에 바로 적용됩니다. 차량 경로 문제(VRP) 및 유연한 잡숍 스케줄링(FJSP) 전반에 걸친 32가지 변형 문제를 대상으로 한 실험에서, MECo는 동일한 예산 하에 8개의 자동화된 휴리스틱 설계(AHD) 기준선과 비교해 가장 낮은 평균 비용을 달성함을 보여줍니다. 도메인 외(OOD) 문제에서도 각 제품군에서 가장 강력한 기준선을 능가합니다. 나아가 MECo 프레임워크를 서로 다른 AHD 방법들과 통합했을 때 두 제품군 모두에서 ID 및 OOD 성능이 향상되어, 여러 방법 전반에 걸친 유효성을 뒷받침합니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.