## Control Systems and Computers, N5, 2016, Article 3

##### 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 studentZaporizhzhya 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.