7.1.  Программная среда

Эффективность (оптимальность) любого алгоритма, по сравнению с аналогичными алгоритмами, может быть доказана в результате:

•    теоретического исследования, т. е. сравнения оценок временной сложности алгоритмов и пространственной сложности алгоритмов;

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

При выполнении исследования реализуется серия экспериментов, собираются тестовые данные и проводится статистическое исследование этих данных.

Объектами, на которых проводятся исследования, являются такие оптимизационные задачи на графах, как разбиение; размещение вершин графа на плоскости и в линейке; задача о коммивояжере; раскраска графов; построение независимых подмножеств, клик графов и распознавания изоморфизма графов, рассмотренные выше.

Исследование алгоритмов направлено на то, чтобы обеспечить возможность получения ответов на вопросы прикладного характера, например: какое время потребуется для нахождения локального или глобального решения; какие графы алгоритм обрабатывает более эффективно.

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

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

питаний, после чего применяют регрессионный анализ для определения зависимости реакции от факторов.

Зависимость Y — F (Хі, Х2) может быть сведена к семейству зависимостей вида: Y — F (Х\) при Х2 = const; Y — F (Х2) при Х\ = const, т. е. фиксируем один из параметров и изменяем второй, в результате чего получаем семейство кривых, которые показывают зависимость выходного параметра от исследуемого. При обработке экспериментальных данных важной задачей является определение (идентификация) закона распределения, к которому можно отнести полученные данные. Если частота наблюдаемых событий близка к величине, предсказываемой теорией, то в дальнейшем можно строить модель исходных или ожидаемых событий на основе теоретического распределения, т. е. упрощается проблема дополнительной генерации необходимого количества данных.

Для оптимизационных задач на графах общей совокупностью являются всевозможные множества произвольных объектов. Наблюдаемые в последовательности п экспериментов значения образуют частичную совокупность значений случайной величины Y. Для обеспечения надежности экспериментальных выводов необходимо решить два основных вопроса:

•    какое число единиц частичной совокупности достаточно велико для того, чтобы по нему можно было делать надежные выводы об изучаемом явлении;

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

«Степень уверенности» или «мера риска» (доверительная вероятность) определяется величиной вероятности, с которой делается соответствующее заключение. Допустимая ошибка при исследованиях устанавливается в зависимости от природы изучаемого явления. В большинстве случаев допустимая ошибка принимается равной 0,05. Число наблюдений определяется по таблице больших чисел, составленной на основании теоремы Бернулли.

Среди свойств распределения одной случайной величины важными являются закон распределения случайной величины и два ее первых момента: математическое ожидание и дисперсия.

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

•    панель ввода/вывода, позволяющую загружать/сохранять тестовые примеры (графы с настройками), выводить на печать и т. п;

•    редактор графов;

•    панели настроек алгоритма и ввода параметров;

•    панель, позволяющую отображать в процессе работы значение ЦФ, график изменения ЦФ по популяции, абсолютно лучшее значение ЦФ, для визуальной оценки выполнения алгоритма.

Рассмотрим программные модули системы:

1.   Программный модуль (ПМі) исследования различных модификаций генетических операторов — оператора рекомбинации, кроссинговера, му™ тации, инверсии, сегрегации, транслокации, их модификаций и совместного использования. Данный модуль построен на основе ПГА и используется для сравнения выходных характеристик одного и того же ГА для одинаковых графов при различных генетических операторах. При этом результатами являются: время работы алгоритма, стабильность алгоритма, лучшее решение, достигнутое в процессе работы, оценка алгоритма по сходимости. Общая структурная схема данного программного модуля приведена на рисунке 7.1.

В эту схему входят следующие блоки:

•    блок ввода данных задачи (ввод переменных и параметров исследуемых моделей, матриц соединений, критериев и т. п.);

•    блок ввода данных настроек алгоритма (размер популяции, типы применяемых операторов, вероятности их. использования и т. п.);

•    ГА с учетом настроек алгоритма;

•    блок редактирования различных оптимизационных задач;

•    блок выдачи результатов.

2.   Программный модуль (ПМ2) исследования применяемых в алгоритме эвристических методов поиска, блока итерационного и статистического улучшения. Данная схема выполнена по аналогии с ПМі и состоит из (рис. 7.2):

•    блока ввода/вывода;

•    блока ввода параметров настроек алгоритма (включаемые функции оптимизации поиска);

•    ГА с учетом настроек оптимизации поиска;

•    блока выдачи результатов (в качестве выходных данных используются те же характеристики, что и в ПМі).

•    редактор различных оптимизационных задач;

•    панель настроек, позволяющую отключать (или подключать) различные методики улучшения процесса поиска;

•    панель работы алгоритма, в которой выводится информация о текущем значении лучшей ЦФ, и график изменения значения ЦФ популяции, а также график изменения решения по всей генерации алгоритма. Кроме того, в процессе работы создается файл отчета, содержащий в себе код всех хромосом всех итераций на текущей генерации, лучшее значение по каждой популяции и результат глобального экстремума.

3. Программный модуль (ПМз) исследования применяемых моделей эволюций, эвристических методов поиска, блока итерационного и статистического улучшения. Данная схема выполнена по аналогии с ПМ і и имеет в своем составе (рис. 7.3):

•    блок ввода данных задачи;

•    блок ввода параметров настроек алгоритма (включаемые функции оптимизации поиска);

•    библиотеку различных моделей эволюций;

•    ГА с учетом настроек оптимизации поиска;

•    блок выдачи результатов (в качестве выходных данных используются те же характеристики, что и в ПМ2).

•    блок ввода/вывода;

•    редактор различных оптимизационных задач;

•    панель настроек, позволяющую отключать (или подключать) различные методики улучшения процесса поиска и различные модели эволюций;

•    панель работы алгоритма, в которой выводится информация о текущем значении лучшей ЦФ и график зависимости максимального и минимального значения ЦФ популяции, а также график изменения решения по всей генерации алгоритма.

4. Программный модуль (ПМ4) исследования применяемых в алгоритме методик поиска, блока итерационного и статистического улучшения, блока адаптации. Эта схема выполнена по аналогии с ПМз и имеет в своем составе

1 /П-

•    блок ввода данных задачи;

•    блок ввода параметров настроек алгоритма (включаемые функции оптимизации поиска);

•    ГА с учетом настроек оптимизации поиска;

•    библиотеку различных моделей эволюций;

•    блок адаптации;

•    блок настроек параметров;

•    блок анализа сходимости алгоритмов;

•    блок выдачи результатов (в качестве выходных данных используются те же характеристики, что и в ПМз).

•    блок ввода/вывода;

•    редактор различных оптимизационных задач;

•    панель настроек, позволяющую отключать (или подключать) различные методики улучшения процесса поиска, разнообразные модели эволюций, а также блок адаптации.

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

Алгоритмы выполнения исследовательского программного модуля по тестированию элементов структуры ГА показаны на рисунках 7.5-7;7. Выполнение программного модуля данной подсистемы начинается с ввода сведений о задачах. Далее выполняется настройка общих и частных параметров алгоритма, к которым относятся:

•    начальное распределение коэффициентов и критериев;

•    начальный размер популяции;

•    ограничение на число итераций алгоритма (число шагов);

•    ограничение на число генераций (количество запусков алгоритма);

•    ограничение по значению ЦФ (если не задано — поиск глобального оптимума);

•    вероятности использования генетических операторов.

Приведем частные параметры для программного модуля (рис. 7.5): тип операторов кроссинговера, мутации, инверсии, сегрегации, транслокации и селекции. После выполнения всех известных генетических операторов выполняется проверка ЦФ. При неудовлетворительном значении ЦФ процесс исследования начинается сначала.

Частными параметрами для программного модуля (рис. 7.6) являются использование эвристик на основе: статистических методов оптимизации; градиентных методов; методов дихотомии; методов Фибоначчи; методов золотого сечения; фрактальных множеств и др. После выполнения всех известных и поисковых методов выполняется ГА. Если критерий «останова» достигнут, то — выход; если нет, то процесс исследования начинается сначала.

Частные параметры для программного модуля (рис. 7.7) следующие: использование моделей эволюций Дарвина, Ламарка, де Фриза, Поппера, блока адаптации, блока анализа и преодоления сходимости.

После реализации моделей эволюций выполняется ГА. Блок адаптации отвечает за обратные связи и установления баланса. Далее выполняется непосредственно ГА в соответствии с используемой схемой с установленными генетическими операторами, которые влияют в итоге на качественные характеристики поиска. Вычислительная сложность данного алгоритма равна 0(п), при этом выполняется только генетический поиск.

ГА реализуется с лучшим постоянным набором операторов, определенных при тестировании. В процессе работы алгоритма применяются разработанные методики настройки поиска. Временная сложность данного алгоритма в общем случае при всех включенных эвристиках равна 0(п3 ). Основная цель эксперимента — выявление общего улучшения, вносимого эвристиками в процесс поиска, а также их поведения при различных типах графов.

Затем выполняется ГА с установленным по результатам проведенного тестирования набором операторов, с выполнением всех эвристических

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

Сущность данных экспериментов заключается в тестировании:

а)   алгоритмов на одной конкретной задаче с последовательным включением всех разработанных эвристик на одной стандартной задаче и определением значений улучшаемых параметров. Это позволяет оценить эффективность используемых в алгоритме методик оптимизации поиска.

б)   алгоритмов на некоторых стандартных тестах с последующим сравнением полученных результатов с уже имеющимися для данной задачи (бенчмарками), просчитанными на каком-либо другом алгоритме. Это позволяет оценить практическую эффективность алгоритма и программных модулей.

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

Для адекватного сравнения использовались стандартные оценки по производительности различных систем (бенчмаркам), представленных ведущими фирмами мира.