Control Systems and Computers

DOI: https://doi.org/10.15407/usim.2016.05.025

Upr. sist. maš., 2016, Issue 5 (265), pp. 25-31.

UDC 519.87

Kryvtsun Olena Volodymyrivna – PhD student, Zaporizhzhya National University, ave. Zhukovsky, 66, Zaporozhye, Ukraine, 69600, E-mail: kryvtsun@ukr.net

Evolutionary-Fragmentary Algorithm of Finding the Minimal Axiom Set

Introduction. The problem of finding the minimal axiom set (MinA) underlies in searching a set of sentences with minimal cardinality that, by applying to it, a given set of relations can be obtain. Any set of sentences, from which, we can obtain the full set of sentences in such a way, is called a core. The cardinality of the core is an objective function of the problem minimization.

The purpose of the work is to develop and to test the hybrid  volutionary-fragmentary algorithm for approximate solving MinA.

Methods. A fragmentary structure for the problem is proposed, a given set of relations is defined on, where the elementary fragments are distinct as the relations from that set. The rules of the elementary fragment joining for forming the next
feasible fragment are presented. The “greedy” algorithm that allows for any numbers of permutation to build the core is formulated.The built fragmentary model of the problem allows the use of the standard evolutionary algorithm on permutations
to find the approximate solution. As the basic set, the subset of permutations is used. The size of the problem is the length of the permutation, which is cardinality of the set of relations. As a crossover operator, geometric crossover on permutations is
assumed. It preserves the relative order of elements. The mutation operator performs random transposition of two elements of permutation with a given probability. The hybrid algorithm constructed in this way is called the evolutionary-fragmentary algorithm of the problem.

Results. Performance of evolutionary-fragmentary (EVF) algorithm is compared with two approximate algorithms: the random search and the local search. For tests we generated collections of the instances, which differ both in size and in the data structure. Results of the study show the advantage of EVF-algorithm compared to the random search for both structures of input data. In comparison with the algorithm of the local search EVF-algorithm shows the higher efficiency for the input data with less ordered structure, while for the data with highly ordered structure performances of these algorithms are almost the same.

Conclusions. The proposed algorithm shows high efficiency for finding MinA on data with the different structures.

Download full text! (In Russian).

Keywords: minimal axiom set, axiom pinpointing, combinatorial optimization, fragmentary structure, evolutional algorithm.

1. Pudlak, P., 1975. “Polynomially complete problems in the logic of automated discovery”. Mathematical Foundations of Comp. Sci. 1975, Lecture Notes in Comp. Sci.Berlin: Springer, 32. pp. 358–361. http://link.springer. com/chapter/ 10.1007%2F3-540-07389-2_221#page-1
2. Geri, M., Dzhonson, D., 1982. Vychislitelnyye mashiny i trudnoreshayemyye zadachi. M.: Mir, 416 p. (In Russian).
3. Schlobach, S., Cornet, R., 2003. “Non-standard reasoning services for the debugging of description logic terminologies”. Int. Joint Conf. on Artificial Intelligence, 3, pp. 355–362. http://ijcai.org/Proceedings/03/Papers/053.pdf
4. Kalyanpur, A., Horridge, M., Sirin, E., 2007. “Finding All Justifications of OWL DL Entailments”. In The Semantic Web. 6th Int. Semantic Web Conf., 2nd Asian Semantic Web Conf., ISWC 2007, ASWC 2007, Busan, Korea, Nov. 11–15, Proc. Berlin Heidelberg: Springer, pp. 267–280.  http://link.springer.com/ chapter/10.1007%2F978-3-540-76298-0_20
5. Penaloza, R., Sertkaya, B., 2010. “On the Complexity of Axiom Pinpointing in the EL Family of Description Logics”. Proc. of the Twelfth Int. Conf. on Principles of Knowl-edge Representation and Reasoning (KR 2010). AAAI Press, 2010. pp. 289–289.  https://www.aaai.org/ocs/ index.php/KR/KR2010/ paper/viewFile/1345/1629
6. Kozin, I.V., Krivtsun, Ye.V., 2016. “Modelirovaniye odnosloynykh i dvukhsloynykh trassirovok”. Upravlausie sistemy i masiny, 2, pp. 58–64. (In Russian). Kozin, I.V., Krivtsun, Ye.V., Polyuga, S.I., 2014. “Fragmentarnaya struktura i evolyutsionnyy algoritm dlya zadach pryamougol’nogo raskroya”. Vísn. Zaporíz’k. nats. un-tu: Zb. nauk. prats’. Zaporízhzhya: ZNU, 2. pp. 65–72. (In Russian).
7. Kozin, I.V., 2008. “Fragmentarnyye struktury i evolyutsionnyye algoritmy”.Pytannya prykladnoyi matematyky i matematychnoho modelyuvannya: Zb. nauk. prats. D.: Vyd-vo Dnipropetr. nats. un-tu im. Olesya Honchara, pp. 138–146. (In Russian).
8. Kozin, I.V., Polyuga, S.I., 2012. “O svoystvakh fragmentarnykh struktur”. Visn. Zaporizʹk. nats. un-tu: Zb. nauk. pratsʹ. Fizyko-matematychni nauky. Zaporizhzhya: Zb. nauk. prats, 1, pp. 99–106. (In Russian).

Received   25.07.2016