Cognitive discrete gravitational search algorithm for solving 0-1 knapsack problem

Fast Polynomial Time Approximate Solution for 0-1 Knapsack Problem

0-1 Knapsack problem (KP) is NP-hard. Approximate solution is vital for solving KP exactly. In this paper, a fast polynomial time approximate solution (FPTAS) is proposed for KP. FPTAS is a local search algorithm. The best approximate solution to KP can be found in the neighborhood of the solution of upper bound for exact k-item knapsack problem (E-kKP) where k is near to the critical item s. FPTAS, in practice, often achieves high accuracy with high speed in solving KP. The computational experiments show that the approximate algorithm for KP is valid.

A Feature-Independent Hyper-Heuristic Approach for Solving the Knapsack Problem

Recent years have witnessed a growing interest in automatic learning mechanisms and applications. The concept of hyper-heuristics, algorithms that either select among existing algorithms or generate new ones, holds high relevance in this matter. Current research suggests that, under certain circumstances, hyper-heuristics outperform single heuristics when evaluated in isolation. When hyper-heuristics are selected among existing algorithms, they map problem states into suitable solvers. Unfortunately, identifying the features that accurately describe the problem state—and thus allow for a proper mapping—requires plenty of domain-specific knowledge, which is not always available. This work proposes a simple yet effective hyper-heuristic model that does not rely on problem features to produce such a mapping. The model defines a fixed sequence of heuristics that improves the solving process of knapsack problems. This research comprises an analysis of feature-independent hyper-heuristic performance under different learning conditions and different problem sets.