Primjena metaheuristike simuliranog hlađenja kod rješavanja p-median problema

završni rad

• Naslov (engleski): Applicability of the Simulated Annealing Metaheuristic in Solving the p-Median Problem
• Autor: Ivan Bartolec
• Mentor: Lea Skorin-Kapov (mentor)
• Član povjerenstva: Lea Skorin-Kapov (predsjednik povjerenstva)
• Član povjerenstva: Ognjen Dobrijević (član povjerenstva)
• Član povjerenstva: Ivan Slivar (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; Zagreb
• Datum i država obrane: 2015-07-13, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Elektrotehnika

Sažetak

Ovaj rad bavi se p-median problemom. To je problem lokacije objekata, problem gdje je potrebno pronaći podskup zadanih točaka koji će posluživati ostale točke tj. klijente. Problem je NP-težak i nije ga moguće riješiti korištenjem egzaktnih algoritama u polinomijalnom vremenu. Stoga koristimo poboljšavajuće heuristike (algoritmi koji daju približno dobro rješenje) ,odnosno metaheuristike koje su algoritmi koji su primjenjivi na više različitih vrsta problema.
Simulirano hlađenje spada pod metaheuristike, i analogno je hlađenju metala u prirodi. Brže hlađenje, odnosno brzo pretraživanje, donosi lošije rezultate, dok sporije hlađenje donosi bolje rezultate. Simulirano hlađenje je dobro za rješavanje velikih problema jer omogućuje izlazak iz lokalnih optimuma u potrazi za onim globalnim.
U ovom radu implementiran je algoritam simuliranog hlađenja koji se može primjeniti na p-median probleme. Algoritam je nazvan SA_pmed i napisan je u programskom jeziku Python, verziji 2.7.10 . Algoritam kao rješenje izbacuje najbolje pronađeno rješenje funkcije cilja te omogućuje analizu utjecaja parametara algoritma na kvalitetu dobivenog rješenja.

Sažetak (engleski)

This paper focuses on the p-median problem. It is a facility location problem where you need to find a subset of the given points that will serve other points. The problem is NP-hard and can not be solved using exact algorithms in polynominal time. Therefore, we use metaheuristics (alghorithms which provide good solution) that are applicable to many different types of problems.
Simulated annealing is a metaheuristic which is analogous to the cooling of metal in nature. Faster cooling (a quick search) brings worse results, while slower cooling brings better results. Simulated annealing escapes local optima and therefore is good for solving very large problems.
In this thesis, a simulated annealing algorithm is implemented which can be applied to the p-median problem. The algorithm is called SA_pmed and is written in Python version 2.7.10 . When finished, the algorithm prints out the best solution found. The algorithm further enables analysis of the impact of different parameters on the quality of the found solution.

• Ključne riječi: optimizacija; problem lokacije; p-median problem; metaheuristika; simulirano hlađenje; implementacija; Python; analiza parametara
• Ključne riječi (engleski): optimization; location problem; p-median problem; metaheuristics; simulated annealing; implementation; Python; analysis of the impact of parameters
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:650407
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: preddiplomski; Akademski / stručni naziv: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (univ.bacc.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2018-02-06 07:46:28