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

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

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

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

Рис 2.4. Ввод числа индивидов в турнирной группе

В разделе Остальные параметры (Other parameters) указывается размеры популяции и число поколений, при этом число поколений является критерием остановки алгоритма.

Дополнительной опцией является возможность в разделе Мутация (Mutation) пользователю самому устанавливать значение вероятности мутации.

В разделе Вид оптимизируемой функции (Kind of test function) можно устанавливать по какой функции проводится оптимизация, то есть функцию вычисления определенного коэффициента готовности. При выборе любой из функций в строке Объективный оптимум (The Objective optimum Y), еще до запуска алгоритма, выводится значение функции в точке оптимума, известное в результате выполненной ранее целочисленной оптимизации. Это сделано с целью удобства сравнения решений найденных генетическим алгоритмом с целочисленной оптимизацией.

Обязательным параметром является число запусков одного и того же ГА с фиксированной структурой, по которым проводятся усреднения показателей эффективности (рис. 2.5.)

Рис. 2.5 Начальное окно программной системы ГА

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

Рис. 2.6 Файл отчета по работе программной системы ГА

На рисунке 2.7 представлено результирующее окно программы. На нем изображены графики сходимости ГА по нескольким запускам: значения целевой функции лучшего индивида популяции (верхний график), среднее значение целевой функции по популяции (средний график), значение целевой функции худшего индивида по популяции(нижний график). А также вычислены величины эффективности работы запущенной структуры ГА, скорость ее сходимости (на каком в среднем поколении был найден заданный оптимум) и интервал поколений, на котором гарантированно при всех установленных запусках, был найден оптимум. Рассмотрим это более подробно позже. В случае необходимости можно сохранить (кнопка Save as) полученные графики или вывести на принтер (кнопка Print).

Рис. 2.7 Результирующее окно программной системы ГА

Результаты оптимизации с помощью ГА

Известно, что ГА обладает глобальной сходимостью. К тому же генетические алгоритмы есть вероятностные (стохастические) процедуры. Для анализа эффективности их работы необходимо проводить статистическое усреднение по нескольким запускам. В данной работе приведена усредненная информация по 100 запускам каждого генетического алгоритма с заданной структурой. Структурой ГА будем считать набор параметров алгоритма: вид селекции, мутации, рекомбинации. Качество работы ГА будет оцениваться по трем критериям в порядке их важности: надежность, скорость, разброс (интервал поколений в котором найдено решение).

Постоянные параметры генетического алгоритма: численность популяции равна 25, число поколений равно 30. То есть число вычислений целевой функции равно 750, что составило порядка 0.3% от всей области определения функции (т.к. аргумент функции был представлен в виде булевого вектора (хромосомы) длиной 18 бит.) Размер в элитарной и турнирной группах был равен 5.

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

Выводы:

· оптимальной структурой ГА в данной задаче является: турнирная селекция, слабая (средняя см. табл. 3. приложения А) мутация, равномерная рекомбинация,

· ГА успешно справился с задачей оптимизации (т.к. показатели надежности равны 1),

· для всех оптимальных структур (для каждой из функций) для нахождения глобального максимума не потребовалось выполнения всех отведенных поколений (т.е. глобальный максимум был найден уже после 20-21 поколения).