arXiv:1908.10705

Improving a State-of-the-Art Heuristic for the Minimum Latency Problem with Data Mining

Ítalo Santana, Alexandre Plastino, Isabel Rosseti

제출 2019-08-28

원문 초록

Recently, hybrid metaheuristics have become a trend in operations research. A successful example combines the Greedy Randomized Adaptive Search Procedures (GRASP) and data mining techniques, where frequent patterns found in high-quality solutions can lead to an efficient exploration of the search space, along with a significant reduction of computational time. In this work, a GRASP-based state-of-the-art heuristic for the Minimum Latency Problem (MLP) is improved by means of data mining techniques for two MLP variants. Computational experiments showed that the approaches with data mining were able to match or improve the solution quality for a large number of instances, together with a substantial reduction of running time. In addition, 88 new cost values of solutions are introduced into the literature. To support our results, tests of statistical significance, impact of using mined patterns, equal time comparisons and time-to-target plots are provided.

함께 살펴볼 논문

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

arXiv:2410.01432v3cs.LG공통 태그 Efficient Exploration공식 코드 · Papers with Code

상각 샘플러를 위한 적응형 교사

Adaptive teachers for amortized samplers

상각 추론(Amortized inference)은 신경망과 같은 매개변수 모델을 학습시켜, 정확한 샘플링이 불가능한 주어진 비정규화 밀도(unnormalized density)의 분포를 근사하는 작업이다. 샘플링이 순차적 의사결정 과정으로 구현될 때, 생성 플로우 네트워크(generative flow networks)와 같은 강화학습(RL) 방법을 사용하여 샘플링 정책을 학습시킬 수 있다. 오프-정책 강화학습 학습은 다양하고 보상이 높은 후보를 발견하는 데 도움이 되지만, 기존 방법들은 효율적인 탐험에서 여전히 어려움을 겪는다. 우리는 적응형 학습 분포(\teacher)를 사용하여 주된 상각 샘플러(\student)의 학습을 안내할 것을 제안한다. 보조 행동 모델인 \teacher는 \student의 손실이 큰 영역에서 샘플링하도록 학습되며, 아직 탐험되지 않은 모드들로 일반화할 수 있어 효율적인 학습 커리큘럼을 제공함으로써 모드 커버리지(mode coverage)를 향상시킨다. 우리는 탐험 과제를 제시하도록 설계된 합성 환경, 두 가지 확산 기반 샘플링 과제, 그리고 네 가지 생화학적 발견 과제에서 이 접근법의 효과를 검증하며, 샘플 효율성과 모드 커버리지를 개선할 수 있음을 보인다. 소스 코드는 https://github.com/alstn12088/adaptive-teacher 에서 확인할 수 있다.

토론

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