Genetic Algorithm for a class of Knapsack Problems
The 0/1 knapsack problem is weakly NP-hard in that there exist pseudo-polynomial time algorithms based on dynamic programming that can solve it exactly. There are also the core branch and bound algorithms that can solve large randomly generated instances in a very short amount of time. However, as the correlation between the variables is increased, the difficulty of the problem increases. Recently a new class of knapsack problems was introduced by D. Pisinger called the spanner knapsack instances. These instances are unsolvable by the core branch and bound instances; and as the size of the coefficients and the capacity constraint increase, the spanner instances are unsolvable even by dynamic programming based algorithms. In this paper, a genetic algorithm is presented for spanner knapsack instances. Results show that the algorithm is capable of delivering optimum solutions within a reasonable amount of computational duration.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Evaluating the impact of different types of crossover and selection methods on the convergence of 0/1 Knapsack using Genetic Algorithm
Genetic Algorithm is an evolutionary algorithm and a metaheuristic that was introduced to overcome the failure of gradient based method in solving the optimization and search problems. The purpose of this paper is to eva…
A Novel Genetic Algorithm using Helper Objectives for the 0-1 Knapsack Problem
The 0-1 knapsack problem is a well-known combinatorial optimisation problem. Approximation algorithms have been designed for solving it and they return provably good solutions within polynomial time. On the other hand, g…
Hybrid Firefly-Genetic Algorithm for Single and Multi-dimensional 0-1 Knapsack Problems
This paper addresses the challenges faced by algorithms, such as the Firefly Algorithm (FA) and the Genetic Algorithm (GA), in constrained optimization problems. While both algorithms perform well for unconstrained probl…
Computational EfficiencyGenetic Algorithm for the 0/1 Multidimensional Knapsack Problem
The 0/1 multidimensional knapsack problem is the 0/1 knapsack problem with m constraints which makes it difficult to solve using traditional methods like dynamic programming or branch and bound algorithms. We present a g…
C++ codeA Denoising Autoencoder that Guides Stochastic Search
An algorithm is described that adaptively learns a non-linear mutation distribution. It works by training a denoising autoencoder (DA) online at each generation of a genetic algorithm to reconstruct a slowly decaying mem…
Denoising