Виды имитационного моделирования

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

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

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

Интенсивностью перехода называют величину , где — вероятность перехода из состояния в состояние за время .

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

Обычно принимается условие: система или останется в старом или перейдет в новое состояние - сумма вероятностей перехода из состояния Si в состояние Sj равна 0
или , где — число состояний. V_ii – вероятность того, что система останется в старом состоянии.

На рис. 1 приведен пример марковской цепи в виде графа перехода состояний, а в табл. 1 представлена матрица интенсивностей переходов для этого примера.

V_ii – вероятность того что система останется в старом состоянии. V_{11 =}-V₁₂-V₁₃-V₁₄

Таблица 1

Состояние

уравнения Колмогорова
- производная вероятности каждого состояния равна сумме всех потоков вероятности, идущих из других состояний в данное состояние, минус сумма всех потоков вероятностей, идущих из данного состояния в другие.

Простейшая СМО с накопителем: S₀ –система свободна, S₁ –пришла первая заявка, S₂ – пришла вторая, третья и т.д.). На рис. представлен граф состояний рассматриваемой СМО, где — состояние с заявками в системе. Нужно выразить все через

Рис.Пример СМО с накопителем (к заявками в системе)

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

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

- для любой СМО, при любом характере потока заявок, при любом распределении времени обслуживания, при любой дисциплине обслуживания среднее время пребывания заявки в системе равно среднему числу заявок в системе, деленному на интенсивность потока заявок T_av =N_{av/лямбда,}

- среднее время пребывания заявки в очереди равно среднему числу заявок в очереди, деленному на интенсивность потока заявок T_or = Q_{av/ лямбда ,}

8. Проектные процедуры автоматизированного проектирования. Задачи и методы оптимизации. Область и принцип Парето. Поисковые методы. Одномерная и многомерная оптимизация. Методы случайного и направленного поиска.

Моделирование на компьютере предполагает использование в качестве объекта отладки программной математической модели проектируемой системы (устройства). Автоматизированное проектирование включает решение задач расчета, анализа, оптимизации и синтеза. Эти задачи называются проектными процедурами

· оптимизация - определение наилучших значений выходных параметров и характеристик путем целенаправленного изменения внутренних параметров устройства. Это является содержанием параметрической оптимизации. Оптимизация структуры устройства является содержанием структурной оптимизации.

При постановке задачи оптимизации необходимо:

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

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

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

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

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

Для решения задачи оптимизации необходимо:

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

. Область, в пределах которой выполняются все условия реализуемости и работоспособности, называют областью работоспособности. Множество точек пространства выходных параметров, из которых невозможно перемещение, приводящее к улучшению всех выходных параметров (участок кривой AB на см. рис. 1), называют областью компромиссов, или областью Парето. Аппроксимация множества Парето формирует фронт Парето. Оптимальность по Парето — такое состояние системы, при котором значение каждого частного показателя, характеризующего систему, не может быть улучшено без ухудшения других.

Рис. 1. Области Парето и работоспособности Рис. 2. Допусковая область и область работоспособности

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

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

Основными методами оптимизации в САПР являются поисковые методы. Поисковые методы основаны на пошаговом изменении управляемых параметров
где в большинстве методов приращение вектора управляемых параметров вычисляется по формуле

(1)

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

Конкретные методы определяются следующими факторами:

1. способом вычисления направления поиска g(x_k) в формуле (1);

2. способом выбора шага h;

3. способом определения окончания поиска.

Методы оптимизации классифицируют по ряду признаков. В зависимости от числа управляемых параметров различают методы одномерной и многомерной оптимизации. В методах одномерной оптимизации управляемый параметр единственный, в других размер вектора X не менее двух. Реальные задачи в САПР многомерны, методы одномерной оптимизации играют вспомогательную роль на отдельных этапах многомерного поиска.

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

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

Среди методов оптимизации нулевого порядка в САПР находят применение методы покоординатного спуска, Розенброка, конфигураций, деформируемого многогранника.

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

9. Задача принятия решения, критерии, альтернативы, морфологические таблицы, риски. Схема принятия решения в технике и при отборе кандидатов на должность. Человеческая система переработки информации. Экспертные интеллектуальные системы, задачи классификации.

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

Задачу принятия решения (ЗПР) формулируют следующим образом:

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

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

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

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

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

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

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

Рис. Схема процесса принятия решения в технике

Человеческая система переработки информации и ее связь с принятием решений.

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

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

Формальные задачи классификации: имеется N - диагностических признаков, S – число оценок качества на шкале i-го диагностического признака, Q – количество классов, к которым могут принадлежать объекты.

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

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

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

Рассмотрим достоинства и недостатки стандартных методов на примере классической задачи коммивояжера (TSP - travelling salesman problem). Суть задачи состоит в том, чтобы найти кратчайший замкнутый путь обхода нескольких городов, заданных своими координатами. Оказывается, что уже для 30 городов поиск оптимального пути представляет собой сложную задачу, побудившую развитие различных новых методов (в том числе нейросетей и генетических алгоритмов). Каждый вариант решения (для 30 городов) - это числовая строка, где на i-ом месте стоит номер j-ого по порядку обхода городов. В этой задаче 30 параметров, причем не все комбинации значений допустимы.

Естественно, первой идеей является полный перебор всех вариантов обхода. Переборный метод наиболее прост по своей сути и тривиален в программировании. Для поиска оптимального решения (точки максимума целевой функции) требуется последовательно вычислить значения целевой функции во всех возможных точках, запоминая максимальное из них. Недостатком этого метода является большая вычислительная стоимость. В частности, в задаче коммивояжера потребуется просчитать длины более 10³⁰ вариантов путей, что совершенно нереально. Однако, если перебор всех вариантов за разумное время возможен, то можно быть абсолютно уверенным в том, что найденное решение будет действительно оптимально.
Второй популярный способ основан на методе градиентного спуска. При этом вначале выбираются некоторые случайные значения параметров, а затем эти значения постепенно изменяют, добиваясь наибольшей скорости роста целевой функции. Достигнув локального максимума, такой алгоритм останавливается, поэтому для поиска глобального оптимума потребуются дополнительные усилия. Градиентные методы работают очень быстро, но не гарантируют оптимальности найденного решения. Они идеальны для применения в так называемых унимодальных задачах, где целевая функция имеет единственный локальный максимум (он же - глобальный). Легко видеть, что задача коммивояжера унимодальной не является.

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

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

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

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

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