Методическое пособие 662

Рис. 2. Распределение температуры на поверхность шара при граничных условиях u(R,Τ ) в виде 3-D поверхности

Литература

1.Голоскоков, Д. П. Уравнения математической физики: учебник для вузов / Д. П. Голоскоков. СПб: СПбГУВК, 2004. 513 с.

2.Арсенин, С. Я. Методы математической физики и специальные

функции / С. Я. Арсенин. М.: Главная редакция физико-математической литературы, 1984. 385 с.

3. Владимиров, В. С. Уравнения математической физики / В. С. Владимиров. М.: Наука. 1971. 456 с.

Воронежский государственный технический университет

УДК 519.873

К. А. Айвазян, С. А. Олейникова

АНАЛИЗ СУЩЕСТВУЮЩИХ МЕТОДОВ И АЛГОРИТМОВ РЕШЕНИЯ ОПТИМИЗАЦИОННОЙ ЗАДАЧИ О РЮКЗАКЕ

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

101

1. Постановка задачи и ее особенности

Задача о рюкзаке может быть сформулирована следующим образом. Имеется множество предметов i = 1, 2, …, n, каждый из которых характеризуется своим весом pi и ценностью ci. Имеется рюкзак емкостью R. Необходимо принять решение о предметах, которые следует поместить в ранец таким образом, чтобы суммарная ценность всех предметов была бы максимальной.

Математически данную задачу можно сформулировать следующим образом:

NP-полной, то есть для нее не существует полиномиального алгоритма, решающего её за приемлемое время [2]. Таким образом, необходимо использовать или быстрый алгоритм без гарантии получения оптимального результата, или точный алгоритм, который позволит найти наилучшее решение, но данный поиск займет слишком много времени. Проанализируем данные алгоритмы.

2. Обзор методов решения задачи о рюкзаке 2.1. Точные алгоритмы

Самый простой из методов решения данной задачи – полный перебор. Допустим, есть N предметов, которые нужно поместить в рюкзак. Для каждого из них существует 2 варианта: 1 – предмет кладется в рюкзак, 0 - нет. Таким образом, перебор всех комбинаций даст ʹ вариантов , что удовлетворяет лишь малому количеству предметов. С ростом числа предметов, методом полного перебора данную задачу решать нецелесообразно. Поэтому возникает необходимость применения методов, которые, снизив количество перебираемых значений, позволили бы найти решение, оптимальное или близкое к нему за приемлемое время.

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

102

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

Метод динамического программирования является одним из наиболее эффективных алгоритмов для задач, обладающих так называемой оптимальной подструктурой [3]. Согласно данному методу в данный момент времени надо принимать такое решение, чтобы суммарный выигрыш на данном шаге и всех последующих шагах был бы максимальным». Данный метод для задачи о рюкзаке даёт точное решение, причём одновременно вычисляются решения для всех размеров рюкзака от 1 до W (максимального веса). Временная сложность алгоритма будет порядка O(N·W).

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

2.2. Приближенные алгоритмы

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

К эвристическим методам относятся жадные алгоритмы, предлагающие на каждом шаге выбирать такую стратегию, которая в данный момент приводит к оптимальному результату. Для решения задачи о рюкзаке жадным алгоритмом сначала необходимо отсортировать входные данные по их удельным ценностям (отношение ценности к весу). Итоговая сложность алгоритма O(N*log(N)) при необходимости сортировки и O(N) при уже отсортированных данных [3].

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

Пример. Пусть вместимость рюкзака W = 50. Исходные данные представлены в таблице. В третьем столбце рассчитана удельная ценность предметов.

Применим жадный алгоритм. Среди предметов из таблицы, разумно бы было взять второй и третий предметы, но при работе жадного алгоритма,

103

выбираются предметы один и два, что является не самым оптимальным решением в данном случае.

Таблица

Таким образом, жадные алгоритмы не применимы для решения задачи о рюкзаке.

Генетический алгоритм это метаэвристический алгоритм, за основу работы которого взяты процессы эволюции в природе [1]. Данный алгоритм ориентирован на поиск субоптимального решения в условиях невозможности полного перебора вариантов. Имитируя процесс естественного отбора, генетические алгоритмы способны «разрабатывать» решения реальных задач, если они правильно закодированы. Рассмотрим основные этапы генетического алгоритма:

1.Формирование начальной популяции.

2.Пока не будет выполнен критерий остановки, выполнять:

2.1. селекция 2.2 скрещивание

2.3мутация.

Вкачестве критериев остановки можно выбрать следующие:

глобальное оптимальное (или субоптимальное) решение найдено;

число поколений, отпущенных на эволюцию, исчерпано;

время, отпущенное на эволюцию, исчерпано.

Можно использовать некоторый синтез из предложенных вариантов. Оператор селекции предназначен для выбора из множества потомков

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

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

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

104

Скрещивание или кроссинговер в разных алгоритмах определяется поразному. Данный метод зависит от представления данных и специфики задачи. Главное требование — чтобы потомки имели возможность унаследовать черты обоих родителей, «смешав» их каким-либо способом.

Следующий оператор - мутация. Она необходима для поддержания разнообразия в популяциях. Без данного этапа некоторые гены, начиная с определенного шага могут уйти из обращения, а результаты сходиться не к глобальному, а к некоторому локальному решению. Как правило, вероятность мутации равна примерно 1%.

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

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

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

Литература

1.Гладков Л. А. Генетические алгоритмы/ Л. А. Гладков, В. В. Курейчик, В. А. Курейчик/ под ред. В. М. Курейчика. – М.: ФИЗМАТЛИТ,

2010. – 368 с.

2.Струченков В. И. Дискретная оптимизация. Модели, методы, алгоритмы решения прикладных задач [Электронный ресурс]/ Струченков В. И.— Электрон. текстовые данные.— Москва: СОЛОН-ПРЕСС, 2016.— 192 c.—

Режим доступа: http://www.iprbookshop.ru/53817.html.— ЭБС «IPRbooks».

3.Пантелеев А. В. Методы оптимизации [Электронный ресурс]: учебное пособие/ Пантелеев А. В., Летова Т. А.— Электрон. текстовые данные.

—Москва: Логос, 2011.— 424 c.— Режим доступа: http://www.iprbookshop.ru/9093.html.— ЭБС «IPRbooks».

Воронежский государственный технический университет

105

УДК 519.876.5

Е. Ю. Бозюкова, С. А. Олейникова

ОСОБЕННОСТИ ИМИТАЦИОННОЙ МОДЕЛИ ДИСПЕТЧЕРСКОГО УПРАВЛЕНИЯ ШАХТНЫМ ТРАНСПОРТОМ

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

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

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

1. Постановка задачи и ее особенности

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

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

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

2. Имитационная модель агента «транспортное средство»

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

106

взаимодействовало с остальными во время движения по специально выделенному маршруту.

Следовательно, подход, который будет использоваться при реализации такой подсистемы будет основываться на многоагентных системах, где каждое ТС – агент.

Немаловажно заметить, что каждый агент должен контролировать график своего движения и быть мобильным в случае изменения различных факторов. Таких как скорость движения, время погрузки/выгрузки и т.д.

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

Таким образом, агент – «Транспортное средство» должен выдавать два вида информации:

-о приближении к точке начала-окончания очередного отрезка;

-о «захвате» некоторого отрезка и, как следствие, невозможности его использования до освобождения остальными транспортными средствами. Исходя из этого, обобщенная модель для отдельного агента - «транспортное средство» будет выглядеть следующим образом (рис. 1).

Без ограничения общности, представим фрагмент функционирования агента «Транспортное средство» на небольшом сегменте транспортной сети, представленном на рис. 1.

Рис. 1. Фрагмент моделируемой транспортной сети

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

Фрагмент модели для агента, маршрут которого проходит по отрезкам

[A1, A2]; [B1,B2] и [D1,D2], представлен на рис.2.

107

Рис. 2. Фрагмент модели для агента, движущегося по маршруту A1-D2

Агент создается в момент, соответствующий началу движения данного транспортного средства, заданного в расписании. Далее осуществляется движение, согласно заданному маршруту. Без наличия общих сегментов пути и других агентов была бы возможность организации движения сразу от начальной точки А1 до конечной – D2 (а затем - обратно). Однако, в связи с общими сегментами, движение каждый раз осуществляется до текущей контрольной точки. Далее проверяется незанятость данного сегмента маршрута, и лишь только после этого выполняется его захват и имитируется движение по нему.После окончания движения по общему сегменту (пересечения другой контрольной точки) – ресурс освобождается. Работа (Work) и разгрузка (Razgr) происходят в соответствии с временными характеристиками, указанными в базе данных. Далее в блоке «EndofSm» осуществляется проверка – является ли данное время конечным для данного транспортного средства или необходимо работать далее. В соответствии с этим, происходит или удаление данного агента или возврат на следующий шаг цикла для повторного движения.

Модель агента «транспортное средство» была реализована с помощью, встроенной в AnyLogic железнодорожной библиотеки [1, 2]. Представим результат работы модели для трех агентов, первый из который движется по маршруту A1-D2; второй – по маршруту A1-E2; третий – по маршруту С1 – Е2 (рис.3).

На данном рисунке видно, что агент 2 в настоящее время движется по общему сегменту; агент 3 ожидает возможности движения по нему у контрольной точки, а агент 1 только подходит к общему сегменту. Как только агент 2 освободит сегмент, его захватит агент 3 (поскольку он пришел раньше), а после освобождения он будет захвачен агентом 1 и т.д.

Рассмотрим особенности диспетчерского управления движением транспорта. В частности, интересен случай, когда по каким-либо причинам два агента попали на общий сегмент. В этом случае диспетчер должен подать

108

сигнал об остановке движения каждому из агентов. В данном фрагменте модели это регулируется семафорами, которые загораются красным цветом в случае невозможности движения.

Рис. 3. Результат работы модели

Получив данный сигнал, агент – транспортное средство должен немедленно остановиться. Программно это реализуется изменением текущей скорости агента с помощью метода setSpeed() агента «Транспортное средство» (установкой данного значения в 0) [3].

Целью работы являлась модели, имитирующей функционирование агентов «Транспортное средство» для подземных шахт и особенности диспетчерского управления этим движением. Был рассмотрен фрагмент реализации безопасного движения шахтного транспорта в среде AnyLogic при помощи мультиагентного подхода, а также особенностям диспетчерского управления в случае, если по каким-либо причинам два агента оказались на общем сегменте пути.

Литература

1.Боев В. Д. Концептуальное проектирование систем в AnyLogic и GPSS World [Электронный ресурс]/ Боев В. Д.— Электрон. текстовые данные.— Москва: Интернет-Университет Информационных Технологий (ИНТУИТ),

2016.— 542 c.— Режим доступа: http://www.iprbookshop.ru/73656.html.— ЭБС «IPRbooks».

2.Карпов Ю. Имитационное моделирование систем. Введение в моделирование с AnyLogic 5. – СПб.: БХВ – Петербург, 2005. – 400 с.

3.Borshchev A. The Big Book of Simulation Modeling. Multimethod

Modeling with AnyLogic 6 [Электронный ресурс]. – Режим доступа: https://www.anylogic.ru/resources/books/big-book-of-simulation-modeling/.

Воронежский государственный технический университет

109