Exploitation Strategies in Conditional Markov Chain Search: A case study on the three-index assignment problem
The Conditional Markov Chain Search (CMCS) is a framework for automated design of metaheuristics for discrete combinatorial optimisation problems. Given a set of algorithmic components such as hill climbers and mutations, CMCS decides in which order to apply those components. The decisions are dictated by the CMCS configuration that can be learnt offline. CMCS does not have an acceptance criterion; any moves are accepted by the framework. As a result, it is particularly good in exploration but is not as good at exploitation. In this study, we explore several extensions of the framework to improve its exploitation abilities. To perform a computational study, we applied the framework to the three-index assignment problem. The results of our experiments showed that a two-stage CMCS is indeed superior to a single-stage CMCS.
Code (0)
등록된 구현이 없습니다.
Methods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Controlling Exploration-Exploitation in GFlowNets via Markov Chain Perspectives
Generative Flow Network (GFlowNet) objectives implicitly fix an equal mixing of forward and backward policies, potentially constraining the exploration-exploitation trade-off during training. By further exploring the lin…
Mixing Properties of Conditional Markov Chains with Unbounded Feature Functions
Conditional Markov Chains (also known as Linear-Chain Conditional Random Fields in the literature) are a versatile class of discriminative models for the distribution of a sequence of hidden states conditional on a sequ…
Learning Multiple Markov Chains via Adaptive Allocation
We study the problem of learning the transition matrices of a set of Markov chains from a single stream of observations on each chain. We assume that the Markov chains are ergodic but otherwise unknown. The learner can s…
Conditional Markov Chain Search for the Generalised Travelling Salesman Problem for Warehouse Order Picking
The Generalised Travelling Salesman Problem (GTSP) is a well-known problem that, among other applications, arises in warehouse order picking, where each stock is distributed between several locations -- a typical approac…
Markov Chain Monte Carlo Methods for Estimating Systemic Risk Allocations
We propose a novel framework of estimating systemic risk measures and risk allocations based on Markov chain Monte Carlo (MCMC) methods. We consider a class of allocations whose jth component can be written as some risk …