Razvoj i analiza metaheurističkih metoda za ispitivanje zadovoljivosti formula u verovatnosnim logikama

Abstract

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.