Разработка и исследование гибридного алгоритма решения сложных задач оптимизации
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
?е результаты:
функции расчета коэффициента готовности КА как на целочисленной решетке, так и в пространстве булевых переменных унимодальные и монотонные,
функции расчета коэффициентов готовности целевой аппаратуры (ЦА) и бортового комплекса управления (БКУ) - полимодальные и немонотонные,
рассчитанный по модели максимальный коэффициент готовности космического аппарата получается, как и предполагалось, при наименьших интенсивностях отказов и при наибольших интенсивностях восстановления подсистем.
2.2 Оптимизация показателей эффективности технологического контура генетическим алгоритмом
После анализа результатов целочисленной оптимизации было предложено выполнить оптимизацию коэффициентов готовности с помощью генетического алгоритма ГА, так как две из трех функций вычисления коэффициентов являются многоэкстремальными и было интересно как справится ГА с оптимизацией.
Для оптимизации коэффициентов готовности КА автором самостоятельно была разработана программная система, в которой пользователю предоставлена возможность выбора тех или иных настроек ГА. В основе этой программной системы лежит алгоритмическая последовательность, схема которой изображена на рис. 1.7. Параллельно с оптимизацией коэффициентов готовности решалась задача определения оптимальной структуры ГА.
Главное окно программы представлено на рисунке 2.4. При выборе турнирной или элитарной селекции пользователю предлагается ввести число индивидов в турнирной или элитарной группах, соответственно (рисунок 2.4).
Рис 2.4. Ввод числа индивидов в турнирной группе
В разделе Остальные параметры (Other parameters) указывается размеры популяции и число поколений, при этом число поколений является критерием остановки алгоритма.
Дополнительной опцией является возможность в разделе Мутация (Mutation) пользователю самому устанавливать значение вероятности мутации.
В разделе Вид оптимизируемой функции (Kind of test function) можно устанавливать по какой функции проводится оптимизация, то есть функцию вычисления определенного коэффициента готовности. При выборе любой из функций в строке Объективный оптимум (The Objective optimum Y), еще до запуска алгоритма, выводится значение функции в точке оптимума, известное в результате выполненной ранее целочисленной оптимизации. Это сделано iелью удобства сравнения решений найденных генетическим алгоритмом iелочисленной оптимизацией.
Обязательным параметром является число запусков одного и того же ГА с фиксированной структурой, по которым проводятся усреднения показателей эффективности (рис. 2.5.)
Рис. 2.5 Начальное окно программной системы ГА
Также необходимо отметить, что все промежуточные вычисления можно посмотреть в создаваемом файле-отчете, имя которого указано в нижней части формы. Файл отчет включает в себя пошаговое описание действий алгоритма, а также: индивидов сгенерированной популяции, тех индивидов, которые были отобраны селекцией при генерировании каждого из потомков, точки рекомбинации соответствующих родителей, те гены потомка, которые подверглись мутации. На рисунке 2.6 представлена в качестве примера страница файла отчета.
Рис. 2.6 Файл отчета по работе программной системы ГА
На рисунке 2.7 представлено результирующее окно программы. На нем изображены графики сходимости ГА по нескольким запускам: значения целевой функции лучшего индивида популяции (верхний график), среднее значение целевой функции по популяции (средний график), значение целевой функции худшего индивида по популяции(нижний график). А также вычислены величины эффективности работы запущенной структуры ГА, скорость ее сходимости (на каком в среднем поколении был найден заданный оптимум) и интервал поколений, на котором гарантированно при всех установленных запусках, был найден оптимум. Рассмотрим это более подробно позже. В случае необходимости можно сохранить (кнопка Save as) полученные графики или вывести на принтер (кнопка Print).
Рис. 2.7 Результирующее окно программной системы ГА
Результаты оптимизации с помощью ГА
Известно, что ГА обладает глобальной сходимостью. К тому же генетические алгоритмы есть вероятностные (стохастические) процедуры. Для анализа эффективности их работы необходимо проводить статистическое усреднение по нескольким запускам. В данной работе приведена усредненная информация по 100 запускам каждого генетического алгоритма с заданной структурой. Структурой ГА будем считать набор параметров алгоритма: вид селекции, мутации, рекомбинации. Качество работы ГА будет оцениваться по трем критериям в порядке их важности: надежность, скорость, разброс (интервал поколений в котором найдено решение).
Постоянные параметры генетического алгоритма: численность популяции равна 25, число поколений равно 30. То есть число вычислений целевой функции равно 750, что составило порядка 0.3% от всей области определения функции (т.к. аргумент функции был представлен в виде булевого вектора (хромосомы) длиной 18 бит.) Размер в элитарной и турнирной группах был равен 5.
В приложении А приводятся таблицы результатов работы ГА с различной структурой для каждой целевой функции с выделенными в них параметрами ГА, которые оказались оптимальными с точки зрения тех критериев, о которых уже было упомянуто выше: надежность, скорость, разброс. Также привед