Hybrid tabu search – strawberry algorithm for multidimensional knapsack problem

Multidimensional Knapsack Problem (MKP) has been widely used to model real-life combinatorial problems. It is also used extensively in experiments to test the performances of metaheuristic algorithms and their hybrids. For example, Tabu Search (TS) has been successfully hybridized with other techniq...

Full description

Saved in:

Bibliographic Details
Main Author:	Wong, Jerng Foong
Format:	Thesis
Language:	eng eng
Published:	2022
Subjects:	LB1025-1050.75 Teaching (Principles and practice)
Online Access:	https://etd.uum.edu.my/10133/1/s824481_01.pdf https://etd.uum.edu.my/10133/2/s824481_02.pdf
Tags:	Add Tag No Tags, Be the first to tag this record!

id	my-uum-etd.10133
record_format	uketd_dc
spelling	my-uum-etd.101332022-12-14T08:32:13Z Hybrid tabu search – strawberry algorithm for multidimensional knapsack problem 2022 Wong, Jerng Foong Benjamin, Aida Mauziah Awang Had Salleh Graduate School of Arts & Sciences Awang Had salleh Graduate School of Art & Sciences LB1025-1050.75 Teaching (Principles and practice) Multidimensional Knapsack Problem (MKP) has been widely used to model real-life combinatorial problems. It is also used extensively in experiments to test the performances of metaheuristic algorithms and their hybrids. For example, Tabu Search (TS) has been successfully hybridized with other techniques, including particle swarm optimization (PSO) algorithm and the two-stage TS algorithm to solve MKP. In 2011, a new metaheuristic known as Strawberry algorithm (SBA) was initiated. Since then, it has been vastly applied to solve engineering problems. However, SBA has never been deployed to solve MKP. Therefore, a new hybrid of TS-SBA is proposed in this study to solve MKP with the objective of maximizing the total profit. The Greedy heuristics by ratio was employed to construct an initial solution. Next, the solution was enhanced by using the hybrid TS-SBA. The parameters setting to run the hybrid TS-SBA was determined by using a combination of Factorial Design of Experiments and Decision Tree Data Mining methods. Finally, the hybrid TS-SBA was evaluated using an MKP benchmark problem. It consisted of 270 test problems with different sizes of constraints and decision variables. The findings revealed that on average the hybrid TS-SBA was able to increase 1.97% profit of the initial solution. However, the best-known solution from past studies seemed to outperform the hybrid TS-SBA with an average difference of 3.69%. Notably, the novel hybrid TS-SBA proposed in this study may facilitate decisionmakers to solve real applications of MKP. It may also be applied to solve other variants of knapsack problems (KPs) with minor modifications. 2022 Thesis https://etd.uum.edu.my/10133/ https://etd.uum.edu.my/10133/1/s824481_01.pdf text eng 2025-09-28 staffonly https://etd.uum.edu.my/10133/2/s824481_02.pdf text eng public other masters Universiti Utara Malaysia
institution	Universiti Utara Malaysia
collection	UUM ETD
language	eng eng
advisor	Benjamin, Aida Mauziah
topic	LB1025-1050.75 Teaching (Principles and practice)
spellingShingle	LB1025-1050.75 Teaching (Principles and practice) Wong, Jerng Foong Hybrid tabu search – strawberry algorithm for multidimensional knapsack problem
description	Multidimensional Knapsack Problem (MKP) has been widely used to model real-life combinatorial problems. It is also used extensively in experiments to test the performances of metaheuristic algorithms and their hybrids. For example, Tabu Search (TS) has been successfully hybridized with other techniques, including particle swarm optimization (PSO) algorithm and the two-stage TS algorithm to solve MKP. In 2011, a new metaheuristic known as Strawberry algorithm (SBA) was initiated. Since then, it has been vastly applied to solve engineering problems. However, SBA has never been deployed to solve MKP. Therefore, a new hybrid of TS-SBA is proposed in this study to solve MKP with the objective of maximizing the total profit. The Greedy heuristics by ratio was employed to construct an initial solution. Next, the solution was enhanced by using the hybrid TS-SBA. The parameters setting to run the hybrid TS-SBA was determined by using a combination of Factorial Design of Experiments and Decision Tree Data Mining methods. Finally, the hybrid TS-SBA was evaluated using an MKP benchmark problem. It consisted of 270 test problems with different sizes of constraints and decision variables. The findings revealed that on average the hybrid TS-SBA was able to increase 1.97% profit of the initial solution. However, the best-known solution from past studies seemed to outperform the hybrid TS-SBA with an average difference of 3.69%. Notably, the novel hybrid TS-SBA proposed in this study may facilitate decisionmakers to solve real applications of MKP. It may also be applied to solve other variants of knapsack problems (KPs) with minor modifications.
format	Thesis
qualification_name	other
qualification_level	Master's degree
author	Wong, Jerng Foong
author_facet	Wong, Jerng Foong
author_sort	Wong, Jerng Foong
title	Hybrid tabu search – strawberry algorithm for multidimensional knapsack problem
title_short	Hybrid tabu search – strawberry algorithm for multidimensional knapsack problem
title_full	Hybrid tabu search – strawberry algorithm for multidimensional knapsack problem
title_fullStr	Hybrid tabu search – strawberry algorithm for multidimensional knapsack problem
title_full_unstemmed	Hybrid tabu search – strawberry algorithm for multidimensional knapsack problem
title_sort	hybrid tabu search – strawberry algorithm for multidimensional knapsack problem
granting_institution	Universiti Utara Malaysia
granting_department	Awang Had Salleh Graduate School of Arts & Sciences
publishDate	2022
url	https://etd.uum.edu.my/10133/1/s824481_01.pdf https://etd.uum.edu.my/10133/2/s824481_02.pdf
_version_	1776103748640178176

Hybrid tabu search – strawberry algorithm for multidimensional knapsack problem

Similar Items