Meta-Heuristics Approach to Knapsack Problem in Memory Management
Emmanuel Ofori Oppong
Department of Computer Science, KNUST, Ghana.
Stephen Opoku Oppong *
Faculty of Computing and Information Systems, GTUC, Ghana.
Dominic Asamoah
Department of Computer Science, KNUST, Ghana.
Nuku Atta Kordzo Abiew
Faculty of Computing and Information Systems, GTUC, Ghana.
*Author to whom correspondence should be addressed.
Abstract
The Knapsack Problems are among the simplest integer programs which are NP-hard. Problems in this class are typically concerned with selecting from a set of given items, each with a specified weight and value, a subset of items whose weight sum does not exceed a prescribed capacity and whose value is maximum. The classical 0-1 Knapsack Problem arises when there is one knapsack and one item of each type. This paper considers the application of classical 0-1 knapsack problem with a single constraint to computer memory management. The goal is to achieve higher efficiency with memory management in computer systems.
This study focuses on using simulated annealing and genetic algorithm for the solution of knapsack problems in optimizing computer memory. It is shown that Simulated Annealing performs better than the Genetic Algorithm for large number of processes.
Keywords: Knapsack, memory management, genetic algorithm, simulated annealing.