Title
Razvoj i analiza metaheurističkih metoda za ispitivanje zadovoljivosti formula u verovatnosnim logikama
Creator
Stojanović, Tatjana, 1974-
Copyright date
2015
Object Links
Select license
Autorstvo-Nekomercijalno 3.0 Srbija (CC BY-NC 3.0)
License description
Dozvoljavate umnožavanje, distribuciju i javno saopštavanje dela, i prerade, ako se navede ime autora na način odredjen od strane autora ili davaoca licence. Ova licenca ne dozvoljava komercijalnu upotrebu dela. Osnovni opis Licence: http://creativecommons.org/licenses/by-nc/3.0/rs/deed.sr_LATN Sadržaj ugovora u celini: http://creativecommons.org/licenses/by-nc/3.0/rs/legalcode.sr-Latn
Language
Serbian
Cobiss-ID
Inventory ID
D-2888
Theses Type
Doktorska disertacija
description
Datum odbrane: 22.01.2016.
Other responsibilities
mentor
Ognjanović, Zoran, 1964-
član komisije
Davidović, Tatjana
član komisije
Ikodinović, Nebojša, 1973-
član komisije
Ivanović, Miloš, 1978-
Academic Expertise
Prirodno-matematičke nauke
Academic Title
-
University
Univerzitet u Kragujevcu
Faculty
Prirodno-matematički fakultet
Publisher
Kragujevac : [T. Stojanović],
Format
PDF/A (110 listova)
description
Prilog.
Umnoženo za odbranu.
Univerzitet u Kragujevcu, Prirodno-matematički fakultet, 20160122, Dr matematičke nauke, matematičke nauke.
Bibliografija: listovi 103-110.
Izvod ; Summary.
Abstract (en)
At the beginning of this thesis basics of probabilistic and default logics are given, as
well as basics of optimization approach to solving different types of problems. Probabilistic
logics presented are LPP2, LPPext
2 and LPCP. Together with default logic they make
a good base for presenting imprecise and incomplete knowledge and reasoning above
this knowledge. Emphasis is given on meta-heuristic approaches, that have already been
used for solving satisfiability problem in LPPext
2 . Beside these methods, Bee Colony
Optimization method (BCO) is presented. It previously gave good results solving hard
combinatorial problems, this being the first time it is used as basic method for dealing
with formula satisfiability problems. Also, all previous uses of BCO consisted improving
the some feasible solution of the given problem. This is the first implementation of BCO
method for finding solutions.
Main parts of thesis are dedicated to implementation of BCO on solving satisfiability
problem for LPCP logic, and BCO implementation on default reasoning. Satisfiability
problem for LPCP logic had no automated solver before this thesis. All of the existing
solutions dealing with satisfiability problem in probabilistic logics considered logics with
absolute probability operators, with real value probabilities. This is the first time that a
solver that accepts formulas with conditional probabilities has been presented. Additionally,
it allows probability values to be from Hardy fields Q["].
Thesis presents, in detail, the way of reducing satisfiability problem in LPCP logic
to linear programming problem, as well as application of BCO method for solving the
resulting linear problem. BCO method is chosen based on experience of roviding better
results then the using evolutionary methods, due to the fact that it allow solution quality
degradation. On the other hand, solutions based on local search easily reach local optima,
which often prevents the system from finding solutions. Thesis shows and analyzes testing
results. For the purposes of results comparison, direct approach to solving resulting linear
programming problem, Fourier-Motzkin elimination method (FME) was used. Results
show great advantage of heuristic approach over FME, both regarding the success rate
and time required for reaching conclusion.
Application of BCO to default reasoning required adjusting the developed algorithm,
as well as new approach to representing numbers from Hardy’s field Q["]. In order to
improve efficiency in default reasoning testing of different strategies was required. This
thesis shows detailed results of these tests. In case of default reasoning, results were also
compared to results of FME method. Again, great advantage of heuristic approach was
demonstrated. The method used presents the first heuristic approach to solving problems
in default reasoning. All previous solvers were based on different direct approach methods.
Authors Key words
Veštačka inteligencija
Classification
004.8(043.3)
Subject
Veštačka inteligencija - Logika LPP2
Type
monograph
manuscript text - theses
Text
“Data exchange” service offers individual users metadata transfer in several different formats. Citation formats are offered for transfers in texts as for the transfer into internet pages. Citation formats include permanent links that guarantee access to cited sources. For use are commonly structured metadata schemes : Dublin Core xml and ETUB-MS xml, local adaptation of international ETD-MS scheme intended for use in academic documents.