Reševanje problema geometrijskega 0/1-nahrbtnika

diplomsko delo

Nejc Škrbec (Author), Luka Fürst (Mentor)

Abstract

V diplomski nalogi obravnavamo problem geometrijskega 0/1-nahrbtnika. Cilj tega NP-težkega problema je iskanje optimalne zapolnjenosti pravokotnih vsebnikov z naborom predmetov različnih velikosti. V raziskavi smo uporabili več determinističnih in stohastičnih pristopov za reševanje tega problema. Implementirali in testirali smo strategijo najboljšega prileganja, konstruktivni hevristični algoritem in hevristiko skupnega obsega. Zmogljivost teh metod smo izboljšali z uporabo globalnih optimizacijskih algoritmov, kot so simulirano ohlajanje in genetski algoritem. Izkazalo se je, da je izmed vseh algoritmov vstavljanja najbolj uspešna hevristika skupnega obsega, največje izboljšanje rešitev pa je pri vseh algoritmih vstavljanja prinesla uporaba v kombinaciji z genetskim algoritmom.

Keywords

algoritmi;metahevristika;genetski algoritem;simulirano ohlajanje;optimizacija;univerzitetni študij;diplomske naloge;

Data

Language:	Slovenian
Year of publishing:	2024
Typology:	2.11 - Undergraduate Thesis
Organization:	UL FRI - Faculty of Computer and Information Science
Publisher:	[N. Škrbec]
UDC:	004(043.2)
COBISS:	202276099
Views:	115
Downloads:	15
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	Solving the geometric knapsack problem
Secondary abstract:	This thesis addresses the geometric 0/1 knapsack problem. The goal of this NP-hard problem is finding the optimal packing of a rectangular container with a set of items of different sizes. We employed and tested various deterministic and stochastic approaches to solve this problem, including the best-fit-first strategy, the constructive heuristic algorithm, and the common perimeter heuristic. Additionally, we improved the performance of the insertion algorithms using global optimization algorithms such as simulated annealing and genetic algorithms. Among the employed insertion algorithms, the common perimeter heuristic performed the best. For all insertion algorithms, the greatest improvement was attained by using them in combination with the genetic algorithm.
Secondary keywords:	algorithms;metaheuristics;genetic algorithm;simulated annealing;computer and information science;optimization;diploma;Računalništvo;Univerzitetna in visokošolska dela;
Type (COBISS):	Bachelor thesis/paper
Study programme:	1000468
Embargo end date (OpenAIRE):	1970-01-01
Thesis comment:	Univ. v Ljubljani, Fak. za računalništvo in informatiko
Pages:	83 str.
ID:	24530570