Имитационная система ИСТРА

3.1. Понятие имитационной системы

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

3.2. Назначение и исходные предпосылки

Имитационная система ИСТРА ориентирована на исследование и оптимизацию крупных объектов транспорта во взаимодействии с производством. Однако достаточно универсальные принципы построения позволяют использовать ее для решения задач на любом виде транспорта, а также для моделирования производственных объектов другого рода.

Система построена таким образом, чтобы учитывать следующие условия:

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

2) модели должны допускать использование частично-формализованных знаний (знаний опытного характера);

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

4) модели должны достаточно хорошо отображать технологические и информационные процессы, а также процессы иерархического управления;

5) имитационная система должна допускать возможность оптимизации моделей по различным критериям;

6) необходимо достаточно полное описание факторов случайного характера;

7) необходимость специальных процедур, «сужающих» исходное множество вариантов и сокращающих итерационный процесс имитационного исследования;

8) простота входного языка и наглядность выдаваемых результатов.

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

Рис. 2.

Схема использования ИСТРЫ для моделирования транспортных систем

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

ИСТРА позволяет строить модели основных видов транспорта (рис. 3), хотя структура понятий и алгоритмов более ориентирована на железнодорожный.

Рис. 3.

Виды транспорта, моделируемые при помощи системы ИСТРА

Система ИСTPA позволяет формировать модели, ориентированные на решение целого ряда различных задач (рис.4). Если модель детерминированная, то в каждом эксперименте воспроизводится про­цесс функционирования моделируемой системы и выдаются результаты, позволяющие достаточно полно оценить ее. Когда модель стохастическая (учитывает случайные процессы), требуется набор экспериментов при одних и тех же исходных данных, но с разными значениями датчика случайных чисел. Поиск рационального решения по тому или иному параметру осуществляется проведением ряда итерационных экспериментов с использованием специальных ускоряющих процедур (например, разработанного для этой системы " имитационного спуска").

Рис. 4.

Решение задач с помощью системы ИСТРА

Имитационная система ИСТРА дает возможность строить: разнохарактерные модели, в том числе:

детерминированные;

слабоуправляемые вероятностные, близкие по принципам функционирования к системам массового обслуживания;

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

3.3. Структура имитационной системы

Абстрактная модель S представляет собой упорядоченную тройку

S=(X, P, f),

где X - множество элементов.

P - множество операций,

f - оператор управления.

Структура абстрактной модели выбрана таким образом, чтобы получить наиболее адекватное описание транспортных процессов и наиболее экономную реализацию на ЭВМ.

3.3.1. Элементы

Элементом x_i X называется линейный дискретный полуавтомат, который определяют следующие параметры:

состояние q_i(t) из пространства Q_i, q_i(t) Î Q_i;

Q_i={0, 1, 2,..., Q_i }, t Î Z₀, Z₀={0, 1, 2,..., };

- вход D q_i⁺(t) Î Q_i⁺;

- выход D q_i^-(t) Î Q_i^-;

- линейная функция перехода в новое состояние

q_i(t+1)= q_i(t)+ D q_i⁺(t)- D q_i^-(t)

Элемент функционирует в дискретном времени. Шаг дискретизации (такт моделирования) выбирается в зависимости от размеров объекта, цели моделирования и памяти ЭВМ.

На множестве X задаются два непересекающихся подмножества:

числовых элементов и логических

, .

У числовых элементов различные состояния качественно однородны и отличаются только количественно. У логических разные состояния имеют различный качественный смысл, т.е. между ними нельзя ставить соотношения «больше» – «меньше».

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

Множество логических элементов разбивается на подмножества элементов с двузначной логикой (булевых) и элементов с многозначной логикой (мулевых):

, .

Состояние элементов с двузначной логикой может принимать значение «ноль» или «единица»:

.

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

Состояние элементов с многозначной логикой выбирается из некоторого подмножества:

.

Такие элементы служат для описания процессов управления. Состояние элемента означает тип принятого решения на некотором уровне диспетчерского управления. Ноль означает, что решение не принималось.

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

Множество Х^и представляет собой совокупность подмножеств Х^иn информационных элементов определенного (n-го) иерархического уровня

,

Множество Х^и1 получается изоморфным отображением множества Х^т. Формула отображения имеет вид

q_i^и1(t) = l_i q_i^т(t),

где q_i^и1(t) - состояние информационного элемента первого (нижнего) иерархического уровня;

q_i^т(t) - состояние соответствующего технологического элемента;

l_i - коэффициент искажения, который имитирует запаздывание, потери и искажение сообщений; l_i Î L_i;

L_i - пространство значений l_i.

Все отображения осуществляются с помощью информационных операций.

Множество информационных элементов каждого последующего уровня получается эпиморфным отображением предыдущего

где n - иерархический уровень,

X_i^иn - множество прообразов элемента x_i^иn+1

X_i^иn = { x_i^иn }

l_m Î L_m - коэффициент искажения.

Таким образом, при движении информации вверх происходит ее обобщение. «Горизонтальное» движение информации в пределах одного уровня описывается оператором управления f(t). Информационные элементы верхних уровней описывают отображение в памяти людей некоторых обобщенных параметров - числа вагонов на станции, в узле, числа груженых вагонов, числа свободных локомотивов и др.

Множество управляющих элементов Х^у также подразделяется на подмножества Х^уn

,

где - верхний иерархический уровень.

Управляющие элементы n -го уровня служат для запоминания управляющих решений (n+1) -го уровня, поэтому верхний уровень управляющих элементов не имеет. Управляющие сигналы «передаются» с помощью управляющих операций, при этом также возможны различного рода искажения.

3.3.2. Операции

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

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

Операция p_î Î P является элементарной моделью, входящей в абстрактную модель. Операция p_î определяется на множестве элементов X_jÌ X.

Операции могут быть:

- технологическими - x_ij Î X_j (x_ij Î X^т) (прием поезда, расформирование состава и др.);

- информационными - $x_ij Î X_j (x_ij Î X^и) (передача сообщений о прибытии поезда, выгрузке вагонов и т.п.);

- управляющими - x_ij Î X_j (x_ij Î X^у) (передача и запоминание управляющих решений).

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

,

где - снимаемая емкость с i -го элемента в момент времени t;

- заносимая емкость на i -й элемент в момент времени t;

Т – период расчета.

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

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

,

или

,

где - величина заносимой емкости на y -й информационный элемент в момент времени t;

- величина снимаемой емкости с y -го информационного элемента в момент времени t;

- величина заносимой емкости на i -й технологический элемент в момент времени ;

- коэффициент перехода в момент времени t.

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

,

где - состояние информационного элемента в момент времени t;

- состояние технологического элемента в момент времени ;

- время задержки информации при передаче диспетчеру;

- коэффициент искажения информации;

- коэффициент потери информации.

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

Рис. 5.

Отображение времени задержки

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

Коэффициент потери информации отображает в модели возможную потерю информации. Потеря информации возникает, когда сообщение не было передано и когда оно не было воспринято. Моделируется использованием случайных величин. По определенному закону распределения коэффициент может принимать два значения: 1 - информация поступила; 0 - информация потеряна:

,

где - вид закона распределения с параметрами.

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

,

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

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

,

где - подмножество информационных элементов, участвующих в описании s -й ситуации;

, - состояние y -го информационного элемента;

- минимальное и максимальное значение состояний для y -го информационного элемента в s -й ситуации;

- состояние управляющего элемента;

b - номер решения, соответствующего s -й ситуации;

- s -я ситуация.

В единое целое элементарные модели объединяет оператор управления f(t).

3.3.3. Оператор управления

Оператор управления f(t) объединяет элементарные модели в единую модель. Оператор f(t) выполняет две функции:

- задает алгебраическую структуру á G, jñ на множестве графов G_j, G={ G_j };

- реализует управление n(t) в пространстве состояний H абстрактной модели.

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

Ситуационное управление строится следующим образом. В пространстве возможных состояний системы выделяются расчетные ситуации, для которых решения известны (из опыта или рассчитаны заранее). Ситуаций ровно столько, сколько решений. Это можно представить в виде таблицы решений, где строкой является ситуация, а столбцом - решение. Если на пересечении строки и столбца стоит единица, то решение соответствует ситуации, в противном случае в клетке стоит - ноль. Число состояний, входящих в одну ситуацию, по которой принимается решение, в сложных системах составляет миллион и более. Число решений на несколько порядков меньше. Если изменилось состояние системы, то проверяется, не изменилась ли ситуация, то есть не требуется ли принимать новое решение. При изменении ситуации принимается новое решение. Для этого существует специальный аппарат укрупнения ситуаций укрупнения ситуаций и " сведения" конкретного состояния моде­ли к одной из ситуаций., Если ситуация изменилась, то принимается новое решение. Таким образом для реализации на ЭВМ ситуационного управления необходимо задать:

-язык описания ситуаций,

-алгоритм сведения состояния системы к одной из ситуаций,

-набор расчетных ситуаций,

-набор управляющих решений.

В абстрактной модели ситуации задаются в пространстве состояний, поэтому введем понятие пространства состояний. Из теории управления динамическими объектами известно, что в понятие состо­яния входит не только текущее значение определенных параметров, но и необходимая " предыстория". У динамической системы существует своего рода инерция. В однопроцессорных ЭВМ элементарные действия производятся только последовательно. Значит, последовательно в модели будут выполняться операции. Поэтому в понятие состояния мо­дели будет входить состояние некоторой группы элементов (текущее значение параметров) и информация о том, какая операция выполнялась перед этим (предыстория). Известно, что для принятия решения, в каком-то районе системы (например, на станции) не требуется знать состояние всей системы. Значит, состояние модели, необходимое для принятия управляющего решения, однозначно описывается значением лишь некоторых параметров, а именно состоянием некоторого подмножества элементов и типом (номером) последней выполняемой операции. Для различных иерархических уровней состав подмножества может меняться.

Содержательно пространство состояний разбивается на:

- технологическое, где выполняются все технологические операции и происходит динамика всех технологических элементов (прием и отправление поездов, погрузка-выгрузка вагонов и пр.);

- информационное, где происходят информационные процессы – передача информации вверх по уровням с учетом обобщения и обмен информацией внутри уровня;

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

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

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

3.4. Оптимизация на имитационной модели

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

- функционал и ограничения заданы, как правило, в неявном виде;

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

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

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

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

В моделях, получаемых с помощью рассматриваемой системы, существенно используется два типа управления - регулирование в пределах одной операции и иерархической управление, реализуемое оператором f(t). Таким образом, в каждом эксперименте присутствует уже многофакторная оптимизация, которая позволяет получать при выбранных исходных данных достаточно хорошие результаты. Неблагоприятное развитие случайных процессов активно компенсируется управлением и функционирование модели «выравнивается». Управление как бы ограждает модель от нежелательных тупиков и результат инвариантен относительно некоторого подкласса начальных условий. Если добавить к этому, что имитационным моделированием должен заниматься лишь опытный специалист, то вероятность того, что модель может быть улучшена сразу по нескольким параметрам, весьма мала. Известно, что множество вариантов, каждый из которых не может быть улучшен по нескольким параметрам одновременно, называется множеством Парето. Оптимизация на множестве Парето означает выбор такого компромиссного варианта, когда улучшение одних параметров дает больший эффект, чем ухудшение других.

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

Движение на множестве результатов, т.е. последовательность имитационных экспериментов, задает «имитационный спуск». В этом случае модель строится так, чтобы оптимизируемый показатель (функционал) был пропорционален (прямо или обратно) суммарной величине задержек

где - стоимость единичной задержки из-за элемента ;

- задержка в операции из-за элемента в момент t.

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

Сопоставим задержкам весовые коэффициенты . Составим множество . Преобразуем его в множество таким образом. что

, .

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

,

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

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

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

Рис. 6.

Схема «имитационного спуска»