Эволюционно-фрагментарный алгоритм поиска минимального множества аксиом

Построена фрагментарная структура задачи поиска минимального множества аксиом. Наличие такой структуры позволяет использовать стандартный эволюционный алгоритм на перестановках для поиска приближенных решений. Для тестирования построенного ЭВФ-алгоритма сгенерированы два набора данных с различными с...

Повний опис

Збережено в:
Бібліографічні деталі
Дата:2016
Автор: Кривцун, Е.В.
Формат: Стаття
Мова:Russian
Опубліковано: Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України 2016
Назва видання:Управляющие системы и машины
Теми:
Онлайн доступ:http://dspace.nbuv.gov.ua/handle/123456789/113396
Теги: Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:Эволюционно-фрагментарный алгоритм поиска минимального множества аксиом / Е.В. Кривцун // Управляющие системы и машины. — 2016. — № 5. — С. 25-31. — Бібліогр.: 9 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id irk-123456789-113396
record_format dspace
spelling irk-123456789-1133962017-02-08T03:03:22Z Эволюционно-фрагментарный алгоритм поиска минимального множества аксиом Кривцун, Е.В. Фундаментальные и прикладные проблемы информатики и информационных технологий Построена фрагментарная структура задачи поиска минимального множества аксиом. Наличие такой структуры позволяет использовать стандартный эволюционный алгоритм на перестановках для поиска приближенных решений. Для тестирования построенного ЭВФ-алгоритма сгенерированы два набора данных с различными структурами. Побудовано фрагментарну структуру задачі пошуку мінімальної множини аксіом. Наявність такої структури дозволяє використовувати стандартний еволюційний алгоритм на перестановках для пошуку наближених рішень. Для тестування побудованого ЕВФ-алгоритму згенеровано два набори даних з різними структурами. 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 evolutionary-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. 2016 Article Эволюционно-фрагментарный алгоритм поиска минимального множества аксиом / Е.В. Кривцун // Управляющие системы и машины. — 2016. — № 5. — С. 25-31. — Бібліогр.: 9 назв. — рос. 0130-5395 http://dspace.nbuv.gov.ua/handle/123456789/113396 519.87 ru Управляющие системы и машины Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
language Russian
topic Фундаментальные и прикладные проблемы информатики и информационных технологий
Фундаментальные и прикладные проблемы информатики и информационных технологий
spellingShingle Фундаментальные и прикладные проблемы информатики и информационных технологий
Фундаментальные и прикладные проблемы информатики и информационных технологий
Кривцун, Е.В.
Эволюционно-фрагментарный алгоритм поиска минимального множества аксиом
Управляющие системы и машины
description Построена фрагментарная структура задачи поиска минимального множества аксиом. Наличие такой структуры позволяет использовать стандартный эволюционный алгоритм на перестановках для поиска приближенных решений. Для тестирования построенного ЭВФ-алгоритма сгенерированы два набора данных с различными структурами.
format Article
author Кривцун, Е.В.
author_facet Кривцун, Е.В.
author_sort Кривцун, Е.В.
title Эволюционно-фрагментарный алгоритм поиска минимального множества аксиом
title_short Эволюционно-фрагментарный алгоритм поиска минимального множества аксиом
title_full Эволюционно-фрагментарный алгоритм поиска минимального множества аксиом
title_fullStr Эволюционно-фрагментарный алгоритм поиска минимального множества аксиом
title_full_unstemmed Эволюционно-фрагментарный алгоритм поиска минимального множества аксиом
title_sort эволюционно-фрагментарный алгоритм поиска минимального множества аксиом
publisher Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
publishDate 2016
topic_facet Фундаментальные и прикладные проблемы информатики и информационных технологий
url http://dspace.nbuv.gov.ua/handle/123456789/113396
citation_txt Эволюционно-фрагментарный алгоритм поиска минимального множества аксиом / Е.В. Кривцун // Управляющие системы и машины. — 2016. — № 5. — С. 25-31. — Бібліогр.: 9 назв. — рос.
series Управляющие системы и машины
work_keys_str_mv AT krivcunev évolûcionnofragmentarnyjalgoritmpoiskaminimalʹnogomnožestvaaksiom
first_indexed 2024-03-30T09:26:58Z
last_indexed 2024-03-30T09:26:58Z
_version_ 1796149984381370368