Участник:Щекалев Алексей Андреевич/Поиск минимального покрытия булевой матрицы

1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

Работа посвящена исследованию и реализации генетического алгоритма поиска минимального покрытия булевой матрицы. В общем случае алгоритмы поиска минимального покрытия имеют экспоненциальную сложность. Поэтому они малопригодны на практике для задач большой размерности. Одним из способов решения данной проблемы является переход от поиска точного решения к приближенному. Например, генетический алгоритм позволяет найти покрытие близкое к минимальному. И поскольку результат работы такого алгоритма зависит от начального приближения, а оно выбирается произвольно, то для увеличения точности решения, генетический алгоритм запускают многократно. Чтобы увеличить скорость работы будем запускать генетический алгоритм из различных начальных приближений параллельно.

1.2 Математическое описание алгоритма

Пусть [math]V = {v_1,v_2,...,v_m}, E = {e_1,e_2,...,e_n}[/math] два конечных множества и [math]P (x, y)[/math] некоторый предикат заданный на множестве [math]V \times E [/math]. Обычно множество [math]E[/math] – называют покрывающим, а множество [math]V[/math] – покрываемым. Если [math]P (v_i,e_j) = 1[/math], то говорят, что [math]e_j[/math] покрывает [math]v_i[/math], а [math]v_i[/math] покрывается [math]e_j[/math]. Пусть [math]M \subseteq E[/math]. Обозначим через [math]\mu_M(v_i)[/math] число всех элементов [math]e_i[/math] из [math]M[/math] , которые покрывают элемент [math]v_i[/math], т.е. [math]\mu_M(v_i) = |\{e_j \in M|P(v_i,e_j) = 1\}|[/math].

Определение 1. Множество [math]M[/math] называется покрытием множества [math]V[/math], если [math]\forall v_i \in V: \mu_M(v_i) \ge 1[/math] Другими словами каждый элемент множества [math]V[/math] покрывается по крайней мере одним элементом из [math]M[/math]. Определение 2. Покрытие называется неприводимым, если при удалении любого его элемента данное покрытие перестает быть покрытием.

Пусть каждому элементу [math]e_j[/math] из множества E приписан вес [math]p(e_j) \gt 0[/math] . Весом покрытия называется число [math]P(M) = p(e_j)[/math]. Задача нахождения покрытия минимального веса называется задачей о покрытии.

3 Литература

1. Дюкова Е.В., Журавлев Ю.И., Сотнезов Р.М., Construction of an Ensemble of Logical Correctors of the Basis of Elementaty Classifiers

2. R.M. Sotnesov, "Genetic Algorithms in Problems of Discrete Optimisation and Recognition"