Материал: Оптимизация и моделирование в автоматизированных системах

–время работы алгоритма;

–число циклов алгоритма;

–в течение n - поколений не появляются особи лучше тех, которые были. На практике далеко не всегда получается составить функцию пригодно-

сти. Например, необходимо решить оптимизационную задачу: У компании было n-лицензий k-типов. Спустя некоторое время, компания решает оптимизировать траты, и в результате оптимизации было выдвинуто предложение о сокращении бюджета на закупку лицензий, например, на 10 процентов. Вам необходимо проанализировать последствия и определить оптимальный набор типов и количества лицензий для покупки. Компания основными показателями рационального использования лицензий считает наличие очередей на получение доступа к ПО и количество неиспользуемых лицензий (или используемых крайне редко). Другими словами, компания хочет, что бы количество закупленных лицензий удовлетворяло условиям:

–необходимое количество: отсутствие очереди на получение доступа к ПО;

–достаточное количество: нет простаивающих лицензий (лицензии, которые никто не использует).

Вреальном мире на интенсивность использования лицензий может влиять множество факторов, например:

–рассматриваемый промежуток времени, так как подавляющее большинство пользователей запускает все необходимые программы в самом начале рабочего дня;

–избыток или недостаток того или иного типа лицензий: если пользователь не может получить доступ к одному типу ПО, он либо дождется своей очереди, либо попытается получить доступ к другому типу - аналогу.

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

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

Принцип расчета оптимального соотношения типов и количества лицензий

15

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

Литература

1.Николенко, С.И. Самообучающиеся системы / С.И. Николенко, А.Л. Тулупьев. – М.: МЦНМО, 2009. – 288 с.

2.Гладков, Л.А. Генетические алгоритмы системы / Л.А. Гладков, В.В. Курейчик, В.М. Курейчик. – М.: Физматлит, 2010. – 368 с.

3.Аверченков, В.И. Эволюционное моделирование и его применение / В.И. Аверченков. – М.: ФЛИНТА, 2016. – 201 с.

ФГБОУ ВО «Воронежский государственный технический университет», Россия

УДК 519.173

А.А. Котенко

МАТРИЧНЫЕ АЛГОРИТМЫ ОПТИМИЗАЦИИ ГРУППОВЫХ ПЕРЕМЕЩЕНИЙ НА ГРАФЕ

Представим математическую модель оптимизации числа непересекающихся кластеров A := {ai }iA=1≤M <+∞ из элементов некоторого потенциально неогра-

ниченного множества B := {bi }iB=1<+∞ . Ограничим сверху допустимое число кластеров A ≤ M < +∞ , мощность каждого кластера ограничим положительной

константой L. Критерий оптимизации: минимизация суммы затрат S на перемещение элементов bi между вершинами данного графа G(V,R).

Пусть G(V,R) – неориентированный граф с фиксированным множеством V вершин, в которых возможно перераспределение находящихся там элементов

bi между кластерами aj, и фиксированным множеством R = {ri }iR=1 размеченных

рёбер, по которым производится перемещение кластеров aj. Нужно обеспечить доставку всех элементов bi из исходных вершин (пунктов отправления) в заданные вершины (пункты назначения).

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

16

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

Пусть известны одинаковые для кластеров любой допустимой мощности фиксированные положительные веса d(r) рёбер r графа G, соответствующие затратам на перемещение по ним одного элемента. Критерий S зададим актуальным прогнозом суммы затрат на перемещение всех элементов bi.

Характерная черта указанных прикладных задач заключается в скачкообразном изменении во времени t как числа элементов B(t) , так и числа состав-

ленных кластеров A(t) . Пусть в момент t в вершинах графа и на его рёбрах н а- ходится некоторое известное число элементов B(t) , составляющих A(t) класте-

ров. Время меняется тактами переменной положительной продолжительности: следующий актуальный момент времени ti+1 появляется за моментом ti, если хотя бы в одной вершине графа G (V,R) можно переформировать хотя бы один кластер. Поток таких возможностей аксиоматизируем подобно потоку ординарных событий в теории массового обслуживания. Фактически переформирование производится, лишь если оно улучшит прогноз критерия S согласно актуальной в момент ti+1 информации о диспозиции всех кластеров и их элементов.

Согласно [1,2] рассмотрим симметрическую матрицу

Ω = d(vi , v j )iV, j=1

смежности вершин простого неориентированного графа G(V,R) с неотрицательными весами рёбер без петель:

d(vi ,vi )= 0 , 1 ≤ i ≤ V .

Несмежность вершин vi и vj оценим бесконечностью. Окаймим матрицу Ω справа и снизу первоначальными бесконечными верхними оценками кратчайших расстояний между вершинами матрицы G(V,R):

Для определения всех кратчайших путей из вершины v1 применим следующие преобразования 1-4 матрицы Ω0.

1. Заменим бесконечную оценку в первой строке правого окаймления нулём:

17

2. Поэлементно прибавим правый столбец окаймления к остальным столбцам матрицы Ω0 и заменим элементы нижней окаймляющей строки минимальными элементами соответствующего столбца:

4. Критерий остановки алгоритма: если полученный правый столбец окаймления не изменился, то поиск кратчайших расстояний от вершины v1 до остальных вершин v2, ,vV завершён. В противном случае повторим шаги 2–4.

5. Полученный набор правых столбцов окаймления даст список путей, упорядоченный по уменьшению суммарных затрат на перемещение элемента от вершины v1 до всех остальных вершин графа G(V,R).

Для определения кратчайших путей из вершины v2 применим преобразования 1–4 матрицы Ω0, начиная с правого столбца окаймления, содержащего 0 во второй строке. И т.д.

Повторив алгоритм, состоящий из преобразований 1–4, необходимое число раз, получим искомые списки путей, ведущих из любой вершины графа G(V,R) в любую другую вершину.

Матричным алгоритмом определения кратчайших путей в момент време-

ния элемента bi в актуальный момент времени t, bif – пункт назначения элемен-

18

где {u j }rj≥=10 V . Здесь u0 – начало пути (1) в вершине u0 := bis (t) V . Последняя вершина пути (1): ur := bif V .

В момент времени t ≥ 0 поставим каждому элементу bi = (bis (t),bif ) B(t) набор всех найденных маршрутов

в виде ориентированного дерева T(t,bi) с корнем bis (t) V и дугами, ведущими по соответствующим рёбрам к вершине bif V .

Листьями дерева T(t,bi) служат слова, описывающие маршруты (2), а промежуточными узлами (между корнем и листьями) являются все подслова слов, представляющих все листья. Ветви дерева T(t,bi) обозначают собственное включение подслов без промежуточных узлов.

Произведём разметку вершин и дуг ориентированного дерева T(t,bi).

a. Разметим вершины x дерева T(t,bi) положительными весами x + , равными прогнозируемым в актуальный момент времени t затратам на переме-

щение элемента bi = (bis (t),bif ) B(t) из корня bis (t) V в вершину X V графа G(V,R), соответствующую узлу x ориентированного дерева T(t,bi).

Корню bis (t) припишем нулевой вес bis (t) = 0 .

Маршрут на ориентированном дереве T(t,bi) назовём оптимальным для элемента bi = (bis (t),bif ) B(t), если он из корня bis (t) V ведёт к листу минималь-

ного веса. В каждый актуальный момент времени t для каждого элемента bi B(t) существует хотя бы один оптимальный маршрут. Различные оптималь-

ные маршруты будем называть альтернативными оптимальными. Маршрут минимального веса среди всех неоптимальных назовём субоптимальным I-го порядка и т.д.

Фиксируя момент времени t ≥ 0 , составим квадратную симметрическую

ванные вершины и главную диагональ T(t,bi(t)), 1≤ i ≤ B(t) , матрицы B2(t).

Полученную матрицу обозначим так же: B2(t). Её элементы покажут, на каких участках найденных путей можно включить разные элементы в один кластер. Составление массива матриц B2(t) при всех возможных диспозициях элементов bi производится в оф-лайн режиме. Он занимает значительный объём внешней памяти АРМ диспетчера. Поступление диспозиции всех элементов и кластеров в он-лайн режиме занимает мало времени и оперативной памяти, так как затрагивает лишь единственный кластер и его элементы. Это позволяет вести оптимальную диспетчеризацию кластеров в реальном времени.

19