АЛГОРИТМ СТРУКТУРНОЙ ОПТИМИЗАЦИИ СЛОЖНЫХ ДИСКРЕТНЫХ СИСТЕМ Кузнецова О.В.

Московский государственный технический университет им. Н.Э. Баумана


Номер: 9-1
Год: 2017
Страницы: 13-20
Журнал: Актуальные проблемы гуманитарных и естественных наук

Ключевые слова

оптимизация, структурная оптимизация, сложная дискретная система, генетический алгоритм, optimization, structural optimization, complex discrete system, genetic algorithm

Просмотр статьи

⛔️ (обновите страницу, если статья не отобразилась)

Аннотация к статье

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

Текст научной статьи

Введение В связи с непрерывным ростом сложности и размерности систем, таких как автоматизированные системы управления технологическими процессами, транспортные, вычислительные, информационные системы и пр., решение задач изучения качества функционирования и преобразования подобных систем становится невозможным без вычислительных средств. На данный момент одной из наиболее актуальных задач в области, связанной с компьютерным анализом сложных систем, является оптимизация[1]. Постановка задачи В общем виде оптимизация может представляться как процесс, состоящий из трех этапов. Рис.1. IDEF0-диаграмма процесса оптимизации сложной дискретной системы Этапы процесса оптимизации. • Анализ системы: изучается функционирования системы в условиях, максимально приближенных к условиям реального мира. • Преобразование системы: на основании полученной информации о функционировании системы проводится ее изменение с целью улучшения характеристик. • Анализ новой системы: производится анализ системы, синтезированной на предыдущем шаге, и производится ее сравнение с исходной системой. Выделяют 2 типа оптимизации[1]: параметрическую, при которой изменяются только параметры элементов системы, и структурную (изменение топологии системы). Однако достижение наилучших показателей функционирования системы за счет лишь параметрической оптимизации невозможно, поэтому практический интерес представляет задача оптимизации структуры. Для постановки задачи оптимизации необходимо определить объект оптимизации, критерии оптимальности и ограничения на получаемые решения. Для формализации сложных систем будем применять концепцию систем массового обслуживания. Система массового обслуживания определяется свойствами входящих в нее приборов обслуживания, однако элементы исследуемой системы дополнительно должны обладать свойствами объекта[5], моделью которого они являются. Важными из них являются свойства функциональной идентичности и взаимозаменяемости. Функциональная идентичность подразумевает, что элементы, с точки зрения реального объекта, выполняют один и тот же набор функций. Взаимозаменяемость описывает свойство системы менять приборы (добавлять, удалять, переставлять) без нарушения функций системы в целом. Не все элементы анализируемой системы проявляют одинаковые характеристики по указанным выше свойствам, поэтому в системе выделяются классы элементов, обладающие свойствами функциональной идентичности и взаимозаменяемости. Таким образом, если в системе присутствуют элементы, неудовлетворяющие требованиям функциональной идентичности и взаимозаменяемости, то эксперту необходимо разделить их на блоки, объединяющие в себе элементы одного класса (то есть обладающие указанными свойствами). Для каждой подсистемы, образуемой элементами одного класса, выделим три группы параметров[8]: входные параметры, выходные параметры, управляющие параметры. Входные параметры - параметры модели, задаваемые до начала исследования. К данной группе параметров относятся: 1. Матрица инцидентности N - размерность системы, - бинарная матрица, описывающая потоки заявок между приборами обслуживания, элемент которой определяется формулой (1). (1) 2. Множество приборов обслуживания с векторами параметров обслуживания: • максимальные длины очередей ; • законы распределений интервалов обслуживания заявок . 3. Множество законов распределений поступления заявок. • -- закон вероятности распределения интервалов поступления заявок, • -- математическое ожидание, • -- среднеквадратичное отклонение. 4. Набор правил, описывающих требования к топологии системы. Эти правила задаются с помощью следующих сущностей: • вектор номеров приборов обслуживания , входящие потоки заявок которых эквивалентны входящим потокам системы в целом; • вектор номеров приборов обслуживания , исходящие потоки которых эквивалентны исходящим потокам системы; • множество пар номеров приборов обслуживания , которые должны быть расположены параллельно друг другу; • множество пар номеров приборов обслуживания , которые должны быть расположены последовательно. Выходные параметры модели представляются в виде матрицы инцидентности преобразованной системы и оценки функционирования системы. Наиболее полную информацию о функционировании системы отражают загруженность и отказоустойчивость системы [2]. Таким образом, выделим 2 критерия оптимальности: • отказоустойчивость системы. Под отказоустойчивостью подразумевается доля непотерянных заявок в системе. ,где - количество заявок, поступивших в систему, - количество заявок, обслуженных системой. Эта величина определяется по следующей формуле: , -- количество заявок, потерянных в системе (количество отказов системы); • загруженность системы (также может быть назван полезностью системы, коэффициентом полезного действия). КПД системы массового обслуживания определяется как доля времени, в течение которого система производила полезную работу, и записывается в виде следующего соотношения: ,где - среднее время выполнения полезной работы системой при обслуживании одной заявки, определяется как . А среднее время выполнения полезной работы системы вычисляется как среднее арифметическое времен всех приборов , -- суммарное время пребывания заявки в системе. Данная величина определяется как сумма времени обслуживания и времени ожидания обслуживания: - время обслуживания заявки i-м прибором обслуживания, - время ожидания обслуживания i-м прибором, - количество приборов обслуживания, посещенных заявкой. Следовательно, определяется следующим образом . Так как обе величины являются безразмерными, то целесообразно построение целевой функции по аддитивному критерию, следовательно целевая функция примет вид: , где - отказоустойчивость системы, - загруженность системы, - весовые нормирующие коэффициенты. Подходы к решению задачи Среди методов решения задачи структурной оптимизации можно выделить следующие: • формальные методы: методы, применяющиеся для определенных систем и использующие в логике своей работы математический аппарат. Формальные методы предполагают вычисление каких-либо параметров модели, т.е. для реализации необходима априорная информация хотя бы о приблизительном характере поверхности целевой функции. Cреди методов, применяющихся при решении задач структурной оптимизации, выделяется 2 множества: численные методы и методы теории графов. Одним из примеров применения градиентных методов к задаче структурной оптимизации может быть представлен метод, описанный в [6], в котором рассматривается один из подходов к решению задачи структурной оптимизации системы массового обслуживания. Решаемая задача является однокритериальной, критерием в ней выступает среднее время ответа (время прохождения заявки через систему). Метод основывается на поиске градиента через аппроксимацию поверхности отклика в области текущих точек фазового пространства некоей гиперболической зависимостью; • эвристические методы: методы, базирующиеся на эксперной логике; • комбинаторно-логические: методы, в основе работы которых лежат алгоритмы теории принятия решений. В данной группе методов реализуется выбор решения среди множества альтернатив. Пример применения эволюционных методов в решении задачи структурной оптимизации разобран в [7], в которой описывается адаптация генетического алгоритма для решения задачи оптимизации структуры магистральной сети связи; • специальные методы: методы, которые решают поставленную задачу, но не принадлежат ни к одной из описанных выше групп. Наиболее распространенные среди них образуют подкласс методов оптимизации систем коммуникации. Стохастический характер модели, представленной в виде системы массового обслуживания, делает невозможным применение классических методов оптимизации. Поэтому необходимо использование методов, реализующих поиск экстремумов функции, априорная информация о рельефе которой отсутствует. Среди таких методов особую популярность получили эволюционные [3] и популяционные [4] методы. Наиболее применимым к задачам оптимизации оказывается генетический алгоритм [9]. Это объясняется следующими его преимуществами над другими методами. Поиск экстремума осуществляется не из единственной точки , а из нескольких точек пространства. Во-вторых, в генетическом алгоритме производится анализ только информации о целевой функции, другая дополнительная информация (например, о производной функции) не используется, что существенно упрощает поиск и требования к виду целевой функции. И в-третьих, правила выбора носят вероятностный, а не детерминированный характер. Эти особенности генетического алгоритма исключают сходимость поиска лишь к ближайшему экстремуму. Описание метода решения задачи структурной оптимизации В общем виде схема алгоритма представляется в виде последовательности этапов (рисунок 2). Рис. 2. Схема алгоритма оптимизации. 1. Инициализация начальной популяции. Для реализации эволюционного преобразования системы необходимо, чтобы начальная популяция состояла из более чем одной системы. Одной из систем является исходная система, вторая система -- случайной топологии. 2. Выбор родительской пары. Так как дочерние особи должны обладать наилучшим значением функции приспосабливаемости, то наиболее вероятно получение систем с такими характеристиками от родительских особей с наилучшими значениями целевой функции. Следовательно, в качестве родительских особей выбираются 2 прототипа системы с наилучшими (наименьшими) значениями целевой функции. 3. Применение оператора кроссовера. Оператор кроссовера реализуется в 2 этапа. Определение позиции кроссовера. Так как топология системы кодируется в виде матрицы инцидентности, то имеем дело с двухмерным оператором кроссовера. Таким образом, позиция кроссовера определяется как случайное число в интервале от 1 до , где -- размерность системы. -- позиция кроссовера. Применение оператора кроссовера. После определения позиции кроссовера выполняется процедура применения данного оператора: перестановка элементов в матрице, т.е. для двух матриц родительских особей элементы, чьи горизонтальные и вертикальные индексы больше или равны позиции кроссовера переставляются. Это можно записать в виде двух соотношений (2), (3). (2) (3) , - хромосомы дочерних особей. , - хромосомы родительских особей. 1. Применение дополнительных операторов генетического алгоритма. В виду того, что в результате реализации оператора кроссовера теряется основное свойство системы -- ее целостность, целесообразна реализация дополнительного оператора генетического алгоритма, восстанавливающая отсутствующие связи посредством наследования их у родительских хромосом. Поэтому данный оператор носит название "Наследование". В рамках данного оператора для всех элементов каждой дочерней особи итерационно реализуется следующая процедура. Если , тогда . В противном случае . 2. Селекция. Существует много способов отбора особей для включения в популяцию. В данном случае дочерние особи включаются в репродукционную группу, а из репродукционной группы отбирается N «лучших» (с наибольшей приспосабливаемостью, или минимальным значением целевой функции) особей для создания популяции. 3. Оценка критерия останова эволюции. Завершение работы алгоритма производится в случае, когда разница между целевыми функциями на соседних итерациях станет меньше заданного значения точности. , где - текущее значение целевой функции, - значение целевой функции с предыдущей итерации, - заданная точность. Стоит отметить, что помимо основного критерия завершения эволюционного цикла есть дополнительный, обеспечивающий прекращение поиска экстремума в случае, если в течение нескольких поколений репродуктивная группа оставалась неизменной. Заключение Предложенная реализация генетического алгоритма была опробована на системах различной топологии и размерности. При изменении размерности системы произвольной топологии было получено среднее улучшение целевой функции в 1.2 раз. Для оценки улучшения системы по значению целевой функции вводится параметр улучшения системы , описываемый следующей формулой: , где -- целевая функция новой системы, -- целевая функция исходной системы. Таким образом, результаты проведенных исследований отображены в таблице 1 и на графике (рисунок 3). Таблица 1 Оценка значений целевых функций Размер F исходной системы F полученной системы E 2 3.17 2.41 0.24 3 3.12 2.31 0.26 4 2.91 2.36 0.19 5 2.82 2.23 0.21 6 2.82 2.34 0.17 7 2.77 2.05 0.26 8 2.75 2.20 0.20 Рис. 3. Зависимость значения целевой функции от размера системы Также проводилось сравнение предложенного генетического алгоритма с алгоритмом полного перебора. При размерности системы более 20-25 элементов, алгоритм полного перебора значительно уступает данной модификации генетического алгоритма. Результаты сравнения отображены в таблице 2. Таблица 2 Сравнение времени генетического алгоритма и полного перебора Размер Генетический алгоритм Полный перебор 4 504.58 402.48 8 853.92 9108.48 12 2617.92 248217,6 16 4663,44 4244766,72 20 10069,85 86226347,52 24 19514,448 - 28 31429,99 - 32 48804,0 - 36 69338,88 - 40 107917,92 - Таким образом, предложенный метод структурной оптимизации позволяет повысить качество функционирования систем различной топологии и размерности с эффективностью, значительно превосходящей эффективность полного перебора.

Научные конференции

 

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