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, genetic algorithms are well suited for solving the knapsack problem and they find reasonably good solutions quickly. A naturally arising question is whether genetic algorithms are able to find solutions as good as approximation algorithms do. This paper presents a novel multi-objective optimisation genetic algorithm for solving the 0-1 knapsack problem. Experiment results show that the new algorithm outperforms its rivals, the greedy algorithm, mixed strategy genetic algorithm, and greedy algorithm + mixed strategy genetic algorithm.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
A Theoretical Assessment of Solution Quality in Evolutionary Algorithms for the Knapsack Problem
Evolutionary algorithms are well suited for solving the knapsack problem. Some empirical studies claim that evolutionary algorithms can produce good solutions to the 0-1 knapsack problem. Nonetheless, few rigorous invest…
Evolutionary AlgorithmsGenetic 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++ codeGenetic 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 …
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…
Contravening Esotery: Cryptanalysis of Knapsack Cipher using Genetic Algorithms
Cryptanalysis of knapsack cipher is a fascinating problem which has eluded the computing fraternity for decades. However, in most of the cases either the time complexity of the proposed algorithm is colossal or an insuff…
Cryptanalysis