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

Исследование ГА для решения поставленной задачи проведено с использованием псевдослучайных матриц тестов размерностями 1000×50, 1000×100, 1000×200, 1000×300, 1000×400, 1000×500, 2000×500. Элементы матриц определяются псевдослучайным образом, после чего производится удаление поглощающих строк. Значения весов, стоимостей и ущербов признаков также определяются как псевдослучайные величины, равномерно распределенные в интервале [0; 1]. Мощность n0 искомого подмножества тестов для всех экспериментов равна 300.

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

Значения штрафов установлены следующим образом:, ,, ,. Рассматривается ГА с турнирной селекцией с размером турнира равным 6, двухточечным оператором кроссинговера, битовой мутацией и 1 элитной особью. По итогам 100 независимых запусков для каждой из рассматриваемых матриц оцениваются результаты, как по полученному лучшему значению функции приспособленности, так и по параметрам, сформулированным в статье [10] и характеризующим стабильность решений, полученных в различных запусках:

• 1. Критерий стабильности, учитывающий частоту pi встречаемости i-го теста во всех решениях, полученных по результатам 100 запусков ГА. Чем больше количество тестов, для которых значение pi равно или близко к 1, тем выше сходимость алгоритма.
• 2. Суммарное количество () ББДТ, не вошедших в полученные решения. Чем больше значение, тем выше сходимость алгоритма.

Полученные лучшие значения целевой функции, усредненные по 100 запускам, для различных матриц ББДТ в зависимости от размера популяции показаны на рис. 1. При увеличении размера (r) популяции наблюдаем улучшение результатов, однако это улучшение весьма незначительно, в большинстве случаев, порядка 10−2.

Анализ решений, полученных при различных настройках ГА, показал, что сформированные по 100 запускам подмножества тестов, соответствующие различным параметрам ГА, отличаются незначительно. Например, для матрицы тестов 1000×500 при размерах популяции 50 и 200 особей полученные подмножества тестов отличались только на 35 тестов, что позволяет сделать вывод о достаточно высокой степени сходимости алгоритма. Однако значительное количество тестов, встречающихся менее чем в 50% решений (соответственно, 460 и 162 для популяций из 50 и 200 особей) свидетельствует о возможности повышения эффективности работы ГА и сходимости результатов.

Также было проведено исследование зависимости состава подмножества тестов, сформированного по результатам нескольких запусков ГА, от количества запусков. При использовании матрицы тестов размерностью 1000×500 результаты ГА с популяцией размером 50 особей для 10, 20, 30, 40, 50, 60, 70, 80, 90 и 100 запусков совпадают для 245 тестов (из 300 искомых). Совпадение с результатами ГА с популяцией 200 особей составляет 244 теста. Таким образом, несмотря на различное количество запусков и размер популяции, 245 и 244 теста присутствуют в большинстве найденных решений.

Отметим, что увеличение размера популяции способствует повышению сходимости ГА по критериям из статьи [10], однако получены результаты, свидетельствующие о том, что для матриц тестов, имеющих не больше 1000 строк, анализ решений, сформированных при использовании сравнительно небольшого размера популяции и малого количества запусков, позволяет построить подмножество тестов, близкое к оптимальному.

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

Таким образом, сокращение количества особей в популяции в a1 раз и количества запусков ГА в—a2 раз, позволяет уменьшить вычислительные затраты и время поиска решения пропорционально произведению a1a2.