Adaptive Algorithms for solving the Knapsack Problem

Hamed, S. Adaptive Algorithms for solving the Knapsack Problem. Bachelor's Thesis, Artificial Intelligence.

Preview	Text bAI_2019_HamedSS.pdf Download (337kB) | Preview
	Text toestemming.pdf Restricted to Registered users only Download (110kB)

Abstract

This thesis describes and compares three algorithms for solving the 0-1 knapsack problem. The latter is a combinatorial optimization problem in which the aim is to maximize value with some constraint. The knapsack problem is NP-complete which means there is no algorithm that can solve every knapsack problem in polynomial time, furthermore it is also NP-hard since there is no algorithm that can verify in polynomial time if a solution is optimal. Due to their strong correlations and high coefficients of the elements, the knapsack problems that are used for this thesis are hard to solve. One of the three algorithms to be tested and compared is an evolutionary algorithm named PBIL. This is an already existing algorithm adjusted for this thesis. PBIL is a genetic algorithm that creates a population of knapsack solutions by using a probability distribution. Each iteration this probability distribution is updated and mutated to generate a new knapsack population. The second algorithm that will tested is based on the Boltzmann exploration function. This is a reinforcement/bandit algorithm that uses reward and punishment to learn which solutions are promising to try. As a third algorithm, this thesis presents the Tsetlin Machine. This is a finite state machine/bandit algorithm that learns by updating states. The results show that both Boltzmann and Tsetlin perform significantly better than PBIL in all conditions. The changing independent variables are the knapsack length, the coefficient range and the height of the constraint. Tsetlin performs significantly better than Boltzmann in eight of the nine conditions. Boltzmann performed significantly better than Tsetlin.

Item Type:	Thesis (Bachelor's Thesis)
Supervisor name:	Wiering, M.A.
Degree programme:	Artificial Intelligence
Thesis type:	Bachelor's Thesis
Language:	English
Date Deposited:	06 Jan 2020 11:46
Last Modified:	06 Jan 2020 11:46
URI:	https://fse.studenttheses.ub.rug.nl/id/eprint/21374

Actions (login required)

View Item