arXiv:2604.13385v3 cs.NE

동적 기회 제약 노천광 채굴 일정 계획 문제를 위한 진화적 최적화 활용에 관한 연구

On the use of evolutionary optimization for the dynamic chance constrained open-pit mine scheduling problem

Ishara Hewa Pathiranage, Aneta Neumann

제출 2026-04-15

저자 비고

arXiv Comments

Accepted to publish in 2026 IEEE World Congress on Computational Intelligence (WCCI), This version corrected typo in Table 2

한국어 초록

노천광 채굴 일정 계획(Open-pit mine scheduling)은 불확실한 경제적 가치와 동적으로 변화하는 자원 용량을 수반하는 복잡한 실세계 최적화(optimization) 문제입니다. 진화 알고리즘(evolutionary algorithm)은 불확실하고 변화하는 환경에 쉽게 적응할 수 있어 이러한 시나리오에서 특히 효과적입니다. 그러나 실세계 문제에서 불확실성과 동적 변화는 종종 개별적으로 연구됩니다. 본 논문에서는 블록의 경제적 가치가 확률적이고 채굴 및 처리 용량이 시간에 따라 변하는 동적 기회 제약 노천광 채굴 일정 계획 문제를 연구합니다. 우리는 기대 할인 이익을 극대화하는 동시에 표준편차를 최소화하는 이중 목적 진화적 정식화를 채택합니다. 동적 변화에 대처하기 위해, 변화가 감지될 때마다 실행 불가능한 해의 일부를 복구하고 실행 가능한 해를 추가로 도입하는 다양성 기반 변화 대응 메커니즘을 제안합니다. 네 가지 다목적 진화 알고리즘에 걸쳐 이 메커니즘의 효과를 평가하고, 재평가 기반 변화 대응 전략 기준선(baseline)과 비교합니다. 6개의 채굴 인스턴스에 대한 실험 결과는 제안된 접근 방식이 다양한 불확실성 수준과 변화 빈도 전반에 걸쳐 기준선 방법들을 일관되게 능가함을 보여줍니다.

원문 초록

Open-pit mine scheduling is a complex real-world optimization problem that involves uncertain economic values and dynamically changing resource capacities. Evolutionary algorithms are particularly effective in these scenarios, as they can easily adapt to uncertain and changing environments. However, uncertainty and dynamic changes are often studied in isolation in real-world problems. In this paper, we study a dynamic chance-constrained open-pit mine scheduling problem in which block economic values are stochastic and mining and processing capacities vary over time. We adopt a bi-objective evolutionary formulation that simultaneously maximizes expected discounted profit and minimizes its standard deviation. To address dynamic changes, we propose a diversity-based change response mechanism that repairs a subset of infeasible solutions and introduces additional feasible solutions whenever a change is detected. We evaluate the effectiveness of this mechanism across four multi-objective evolutionary algorithms and compare it with a baseline re-evaluation-based change-response strategy. Experimental results on six mining instances demonstrate that the proposed approach consistently outperforms the baseline methods across different uncertainty levels and change frequencies.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2604.13385v3

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

arXiv:2607.23316v2cs.NE공통 태그 Evolutionary Algorithms, Scheduling, Combinatorial Optimization

학생 학습 자원 배분을 위한 유전 알고리즘

A genetic algorithm for student academic resource allocation

개별 학생에게 학습 자원을 최적으로 배분하는 것은 학습자 다양성을 다루고 공평한 교육 성과를 촉진하는 데 필수적이다. Erasmus+ KA220-SCH 프로젝트의 틀 안에서, 본 논문은 고등학교 수학 학생을 위한 교육 자료 선택을 엄격한 학습 시간 제약을 따르는 0-1 이진 조합 최적화(optimization) 문제로 모델링한다. 이 공식화의 NP-hard 복잡도를 고려할 때, 자원 카탈로그가 확대될수록 정확한 해법은 계산적으로 다루기 어려워진다. 이 과제를 해결하기 위해, 우리는 이진 결정 공간을 효과적으로 탐색하기 위해 특화된 제약 복구 메커니즘과 통합된 유전 알고리즘(Genetic Algorithm)을 제안한다. 10회의 독립 실행에 걸친 실험적 평가는 빠른 수렴, 높은 해 품질, 그리고 서로 다른 기본 시드에 걸친 강한 알고리즘적 안정성을 보여준다. 이 결과는 중등 교육에서 실시간 의사결정 지원 시스템을 위한 메타휴리스틱(metaheuristic) 접근법의 실용적 유용성을 확인한다.

arXiv:2610.03316v2cs.AI공통 태그 Evolutionary Algorithms, Scheduling, Combinatorial Optimization

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 성능이 향상되어, 여러 방법 전반에 걸친 유효성을 뒷받침합니다.

arXiv:2609.23180v1quant-ph공통 태그 Evolutionary Algorithms, Stochastic Optimization, Combinatorial Optimization

잡음이 있는 QAOA 최적화를 위한 적응형 차분 진화 및 다중 시작 탐색

Adaptive Differential Evolution and Multistart Search for Noisy QAOA Optimization

우리는 $N=12$, $p=3$, $D=6$ 조건에서 네 가지 비용 해밀토니안(cost-Hamiltonian) 계열에 걸쳐 고정된 저심도(low-depth) 양자 근사 최적화 알고리즘(Quantum Approximate Optimization Algorithm, QAOA) 앤자츠(ansatz)에 대한 고전적 최적화를 벤치마크한다. 10개의 옵티마이저를 10,000회 및 30,000회의 함수 평가(function evaluations, FEs)라는 공통 상한 하에서 25회의 독립 실행에 걸쳐 비교하며, 먼저 정확한 상태벡터(statevector) 목적함수로, 이후 두 가지 수준의 가산 관측 잡음(observation noise)을 적용하여 비교한다. 정확한 목적함수에서는 다중 시작(multistart) BFGS와 다중 시작 CMA-ES가 우세하다. 잡음이 있는 피드백 하에서는 적응형 개체군(population) 기반 방법들이 더 경쟁력을 갖게 되지만, 그 순위는 성능을 방문한 최적의 정확한 지점으로 측정하는지 아니면 잡음이 있는 관측값으로부터 선택된 지점으로 측정하는지에 따라 달라진다. 각 계열별로 사전 선별된 세 가지 인스턴스 전체에 대한 표적 확장 실험은 이러한 국면 전환(regime change)을 확인해주는 동시에, 명명된 적응형 차분 진화(adaptive-DE) 우승자들이 인스턴스에 따라 달라짐을 보여준다: 동일 인스턴스 요약에서 jSO-lite는 저잡음 오라클 탐색을, iL-SHADE는 고잡음 오라클 탐색을, L-SRTDE는 고잡음 선택 해(solution)를 각각 주도한다. 부트스트랩(bootstrap) 분석은 무시할 수 없는 수준의 고잡음 탐색-선택 격차(search-selection gap)를 정량화하며, 소급적 고정 예산 검증 프록시(retrospective fixed-budget verification proxy)는 최종 재평가를 위해 소량의 측정 예산을 남겨두는 것이 30,000 FEs에서 열 가지 방법 모두에 걸쳐 선택된 해의 품질을 향상시킴을 보여준다. 추가적인 구조 인식(structure-aware) 연구는 나아가 이러한 조건에서 QAOA의 교차 심도 제한(cross-depth restriction)과 연속적 분지 정제(continuous basin refinement)가 단독 몬테카를로 트리 탐색(Monte Carlo tree-search) 선택보다 더 유용함을 보여준다. 전반적으로 옵티마이저 선택은 지형 구조(landscape structure), 관측 잡음, 그리고 최종 지점 식별(final-point identification)에 공동으로 의존한다.

arXiv:2607.22550v1math.OC공통 태그 Stochastic Optimization, Scheduling, Combinatorial Optimization

대규모 최적화 학습: 확률적 조합 최적화를 위한 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의 잠재력을 보여준다.

arXiv:2607.22539v1math.OC공통 태그 Stochastic Optimization, Scheduling, Combinatorial Optimization

방사선 치료 스케줄링을 위한 최적화 모델 비교

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와 결합하면 실행 시간과 메모리 사용량을 낮게 유지하면서 해의 품질을 더욱 향상시킨다.

arXiv:2607.24049v1cs.AI공통 태그 Evolutionary Algorithms, Scheduling, Combinatorial Optimization

단기 교란 하에서 도착-출발 선로 활용 조정을 위한 양자 영감 진화 이웃 탐색

Quantum-Inspired Evolutionary Neighborhood Search for Arrival-Departure Track Utilization Adjustment under Short-Term Disturbances

주요 여객 철도역에서 발생하는 단기 교란은 열차 도착·출발 시각과 역 자원의 해제 순서를 바꾼다. 따라서 효과적인 복구를 위해서는 도착-출발 선로 배정, 역 자원 점유, 열차 재시각 조정을 조율해야 한다. 본 연구는 열차 도착, 선로 점유, 출발 운영에 관여하는 역 자원을 구역 수준의 자원 점유 구간으로 표현한다. 도착-출발 선로 배정 조정 모델을 수립한다. 실행 가능성 조건으로 자원 호환성을 부과하고, 열차 지연과 자원 재배정 비용을 함께 고려한다. 모델을 풀기 위해 이웃 탐색(neighborhood search)과 결합한 양자 영감 진화 알고리즘(QEA-NS)을 제안한다. 독일 프랑크푸르트 중앙역(Frankfurt Hauptbahnhof)의 GTFS 시간표 데이터를 이용해 교란 인스턴스를 구성한다. QEA-NS는 동일한 후보 자원 집합과 실행 가능성 기준 하에서 CP-SAT와 비교한다. 두 방법 모두 모델링된 자원 호환성 제약을 만족하는 해를 생성한다. QEA-NS는 총 지연이 388분으로, CP-SAT의 519분 대비 25.2% 감소를 나타낸다. 지연된 열차의 평균 지연은 4.99분에서 3.73분으로 줄어들지만, QEA-NS는 더 긴 해 탐색 시간이 필요하다. 10개의 무작위 교란 인스턴스 전반에서 QEA-NS는 모든 경우에 더 낮은 총 지연을 달성한다. 평균 총 지연과 표준편차는 각각 390.5분과 35.945분으로, CP-SAT의 673.8분과 105.739분에 비해 낮다. 결과는 채택된 자원 표현과 제약 하에서 QEA-NS가 복구 계획의 지연 성능을 개선함을 보여준다. 그러나 계산 효율은 추가 개선이 필요하다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.