Постановка задачи. 
Применение мягких вычислений для формирования оптимального подмножества тестов

Дана матрица тестов T с заданными весами, стоимостью и ущербами признаков.

Необходимо выделить такую подматрицу T0, содержащую n0 строк, чтобы соответствующее ей множество тестов N0 обеспечивало выполнение следующих критериев в порядке их следования: 1) в N0 должно содержаться максимальное число псевдообязательных признаков; 2) N0 должно содержать минимальное общее число признаков; 3) N0 должно иметь максимальный суммарный вес; 4) N0 должно иметь наименьшую суммарную стоимость; 5) N0 должно иметь наименьший суммарный ущерб.

Генетический алгоритм

Для решения поставленной задачи предлагается использовать ГА, представляющий итерационный вероятностный эвристический алгоритм поиска. Отличительной особенностью ГА является одновременная работа со множеством точек (популяцией) из пространства потенциальных решений. Каждое возможное решение представлено бинарной хромосомой (строкой) длины n, каждый i-й символ которой кодирует включение i-го диагностического теста в итоговое подмножество.

Будем вычислять приспособленность k-й особи c хромосомой h путем оценки качества соответствующей подматрицы в соответствии с выражением [5]:

,.

где — весовой коэффициент j-го критерия, соответствующий его значимости; - количество единичных разрядов в бинарной строке; - функция штрафа за невыполнение j-го критерия:

.

где и — соответственно суммарный вес, стоимость и ущерб по всем тестам множества, соответствующего матрице ;

и ;

соответственно количество единичных разрядов в конъюнкции и дизъюнкции по всем строкам бинарной матрицы .

Поскольку необходимо максимизировать максимальное количество псевдообязательных признаков в искомом подмножестве ББДТ (критерий 1), а также его суммарный вес (критерий 3), но рассматривается задача минимизации целевой функции f, то в выражениях для соответствующих критериям функций штрафа и используется вычитание количества псевдообязательных признаков и веса от максимальных значений. Аналогичные рассуждения использовались при выборе вида функций штрафов для критериев 2, 4 и 5.

Отметим, что выбор значений штрафов зависит от рассматриваемой прикладной задачи.