Reševanje problema geometrijskega 0/1-nahrbtnika

diplomsko delo

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

Povzetek

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.

Ključne besede

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

Podatki

Jezik:	Slovenski jezik
Leto izida:	2024
Tipologija:	2.11 - Diplomsko delo
Organizacija:	UL FRI - Fakulteta za računalništvo in informatiko
Založnik:	[N. Škrbec]
UDK:	004(043.2)
COBISS:	202276099
Št. ogledov:	115
Št. prenosov:	15
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	Solving the geometric knapsack problem
Sekundarni povzetek:	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.
Sekundarne ključne besede:	algorithms;metaheuristics;genetic algorithm;simulated annealing;computer and information science;optimization;diploma;Računalništvo;Univerzitetna in visokošolska dela;
Vrsta dela (COBISS):	Diplomsko delo/naloga
Študijski program:	1000468
Konec prepovedi (OpenAIRE):	1970-01-01
Komentar na gradivo:	Univ. v Ljubljani, Fak. za računalništvo in informatiko
Strani:	83 str.
ID:	24530570