Wave Function Collapse Set Covering and the Hill Climbing Algorithm: A New, Fast Heuristic and Metaheuristic Pairing for the Minimum Set Cover Problem
In this paper, we present a new heuristic that focuses on the optimization problem for the Minimum Set Cover Problem. Our new heuristic involves using Wave Function Collapse and is called Wave Function Collapse Set Covering (WFC-SC). This algorithm goes through observation, propagation, and collapsing, which will be explained more later on in this paper. We optimize this algorithm to quickly find optimal coverings that are close to the minimum needed. To further optimize this algorithm, we pair it with the Hill Climbing metaheuristic to help WFC-SC find a better solution than its "local optimum." We benchmark our algorithm using the well known OR library from Brunel University against other proficient algorithms. We find that our algorithm has a better balance between both optimality and time.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
When Does Hillclimbing Fail on Monotone Functions: An entropy compression argument
Hillclimbing is an essential part of any optimization algorithm. An important benchmark for hillclimbing algorithms on pseudo-Boolean functions $f: \{0,1\}^n \to \mathbb{R}$ are (strictly) montone functions, on which a s…
Hybrid Genetic Algorithm and Hill Climbing Optimization for the Neural Network
In this paper, we propose a hybrid model combining genetic algorithm and hill climbing algorithm for optimizing Convolutional Neural Networks (CNNs) on the CIFAR-100 dataset. The proposed model utilizes a population of c…
Hill Climbing on Value Estimates for Search-control in Dyna
Dyna is an architecture for model-based reinforcement learning (RL), where simulated experience from a model is used to update policies or value functions. A key component of Dyna is search-control, the mechanism to gene…
Model-based Reinforcement LearningReinforcement LearningReinforcement Learning (RL)Bandit-Based Random Mutation Hill-Climbing
The Random Mutation Hill-Climbing algorithm is a direct search technique mostly used in discrete domains. It repeats the process of randomly selecting a neighbour of a best-so-far solution and accepts the neighbour if it…
Clustering by Hill-Climbing: Consistency Results
We consider several hill-climbing approaches to clustering as formulated by Fukunaga and Hostetler in the 1970's. We study both continuous-space and discrete-space (i.e., medoid) variants and establish their consistency.
Clustering