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

undergraduate thesis

• Title (english): Applicability of the Simulated Annealing Metaheuristic in Solving the p-Median Problem
• Author: Ivan Bartolec
• Mentor: Lea Skorin-Kapov (mentor)
• Committee member: Lea Skorin-Kapov (predsjednik povjerenstva)
• Committee member: Ognjen Dobrijević (član povjerenstva)
• Committee member: Ivan Slivar (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2015-07-13, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Electrical Engineering

Abstract

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.

Abstract (english)

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.

• Keywords: optimizacija; problem lokacije; p-median problem; metaheuristika; simulirano hlađenje; implementacija; Python; analiza parametara
• Keywords (english): optimization; location problem; p-median problem; metaheuristics; simulated annealing; implementation; Python; analysis of the impact of parameters
• Language: croatian
• URN:NBN: urn:nbn:hr:168:650407
• Study programme: Title: Computing; Study programme type: university; Study level: undergraduate; Academic / professional title: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2018-02-06 07:46:28