CLAIM – научно-образовательный кластер

Филиппович Андрей, Ходеев Александр

Принятие решения в допечатном производстве с помощью экспертных систем и систем имитационного моделирования

В данной статье рассматриваются некоторые аспекты принятия решения в допечатных процессах (ДП). Для автоматизации управленческой деятельности можно использовать различные классы систем. В статье сравниваются возможности применения СИМ и ЭС.

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

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

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

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

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

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

Продукционные системы впервые изобретены Постом в 1941 г. и имеют следующую схему [Герман, 1995, С.18]:

(t₁, t₂, … t_n) / t,

Несколько изменим представление правил. Будем считать, что из посылок может следовать несколько заключений, т.е.

(x₁, x₂, … x_n) / (y₁, y₂, … y_m),

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

x_i, x_i+1 (x_i, x_i+1) (x_{i *} x_i+1), где i=1,n

y_i, y_i+1 (y_i, y_i+1) (y_{i *} y_i+1), где i=1,m

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

При x₁ = y₁ (x_1* x_2* …_* x_n) / (y_1* y_2*…_*y_m)= (x_2*…_*x_n) / (y_2*…_*y_m).

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

Prav = {Prav₁, … Prav_p}

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

Теорема 1. Для любых двух или более правил их суперпозиция коммутативна.

Prav_i, Prav_j, … Prav_n

Prav_i * Prav_j = Prav_j * Prav_i

Доказательство:

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

Prav_i, Prav_j

Prav_i * Prav_j = V₁ Prav_j * Prav_i = V₂  V₂ V₁ =>

Используя операцию свертки, получаем:

1 1;

Отсюда следует, что предположение неправильное, а теорема верна.

Теорема 2. Для любых правил их суперпозиция ассоциативна.

Prav_i, Prav_j, Prav_n

Prav_i * (Prav_j* Prav_n,) = (Prav_i * Prav_j)* Prav_n,

Доказательство:

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

Prav_i, Prav_j, Prav_n

Prav_i * (Prav_j* Prav_n,) = V₁ (Prav_i * Prav_j)* Prav_n = V₂

V₂ V₁ =>

x_i >0, x'_i >0; x''_i >0;

Используя операцию свертки, получаем:

1 1;

Отсюда следует, что предположение неправильное, а теорема верна.

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

Prav_i * Prav_i = Prav_i² = Prav_i

Аналогичное утверждение справедливо для посылок и заключений.

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

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

Теорема 3. Если при суперпозиции правил Prav₁ … Prav_n, хотя бы в одном правиле присутствует заключение y₀, то суперпозиция приводит к отказу O.

Prav₁ … Prav_n,

Prav_i = (x₁, x₂, … x_n) / (y₁, y₂, …y₀, … y_m)

Prav₁ * Prav₂*… * Prav_n,= O.

Доказательство:

Prav_i, …, Prav_q

Из теоремы 1 и теоремы 2 следует, что

Из этой теоремы вытекают очень важные практические следствия. Например, можно принять, что Y0 соответствует отрицательному ответу на вопрос "Можно ли выполнить данный заказ".

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

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

Для пояснения понятия такта разобьем все множество правил Prav на r подмножеств Prav_Ш.

Prav = Prav_Ш1 Prav_Ш2 … Prav_Шr

Разбиение есть некая функция F1, которая зависит от исходных данных и от стратегии вывода. На каждом такте может быть применено одно из нескольких правил. Совокупность всех этих правил образует подмножество такта Prav_Ш. С каждым тактом уменьшается количество возможных правил. Если обозначить количество правил на такте L как результат функции разбиения, то можно записать следующее:

L1 > L2 > L3 >….>Lr

Li = Func (L_i-1, Strat, Id)

Итак, если вывод осуществляется по стратегии отказа, то порядок выбора правил должен определяться близостью к заключению Y0.

Для ускорения процесса вывода можно заранее просчитать матрицы расстояний и переходов. Ниже приведена таблица переходов. Она показывает цепочки порядков применения правил, приводящих к отказу. Например цепочка Prav₁ Prav₃ Prav₄ Prav_n О будет иметь следующий вид (табл.1).

Таблица 1. Таблица переходов.

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

Таблица 2. Таблица обратных переходов.

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

Таблица 3. Общая таблица переходов.

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

Таблица 4. Таблица расстояний.

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

Чтобы изменять длину перехода в зависимости от исходных данных (посылок), представим их в виде матрицы коэффициентов M_i.

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

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

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

Сортировка есть перестановка [Кнут, 1978, С.23]

P = p(1)p(2) … p(n) такое, что

Kp(1)< Kp(2)< … Kp(n),

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

Таблица 5. Таблица тактов отказа.

Задача приближенного вычисления времени выполнения заказа.

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

T_{в.р.виз.выв.} = (Q*R*C)/A4 * t_A4 * k_оч,

t_вер. = F₁[t₁, t₂]

Если F₁-max => t_вер. = max[t₁, t₂] = t₂,

= t_вер. + T_{в.р.виз.выв.}, где – суммарное время выполнения работы.

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

Если вероятность выполнения задачи P не стопроцентная, то суммарное время выполнения работы будет возрастать.

= + *(1–P)

Критерий выбора СИМ и ЭС.

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

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

Пусть в ЭС существует постоянное (или среднее) время для осуществления одного вывода t_1в.

t_1в = const | t_1в= t_1в.ср. = t_1вi / n,

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

t_{пол.выв.} = m * t_1в.ср,

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

t_бл. = const | t_бл.= t_бл.ср. = t_блi / r,

t_мод. = k_б * t_бл.ср * Tr * I,

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

Если время моделирования t_мод. меньше или равно времени полного вывода, то тогда СИМ эффективнее, чем ЭС, потому что ее результаты более точные и подробные.

t_{пол.выв} <= t_мод.

Более того, время моделирования должно быть значительно больше, чем время вывода с помощью ЭС.

t_{пол.выв} << t_мод.

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

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

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

x = const, t_i+1=t_i +x

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

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

В последнем случае может возникнуть ситуация когда время выполнения заказа, просчитанное СИМ, будет варьироваться в некотором диапазоне.

t_k = t_kк -t_kн,

где	tk –	разница между максимальным и минимальным временем выполнения заказа;
	tkк – максимальное время выполнения заказа;
	tkн – минимальное время выполнения заказа.

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

t_зак. = t_kн * k_1,  k₁= (k_2, ),

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

t_зак. = t_kн * k₃,

где k_3. – максимальный коэффициент запаса.

Роль определителя оптимального коэффициента запаса может выполнять экспертная система, изменяя его значение во время диалога с пользователем.

Если при моделировании в СИМ вести статистику времени выполнения различных работ, то при появлении нового заказа, аналогичного или близкого к уже сделанным, можно произвести приблизительную оценку.

t_zi t_zср.

t_zср. = (t_z1 + t_z2 + … + t_zn ) / n,

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

Zi |Z1-Zi| 0 или |Z1-Zср| 0

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

Кр = {W, Ex, D …},

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

= k_w*W + k_ex*Ex +k_d*D …,

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

|k_t*T – | = .

Если > 0, то временной критерий важнее, чем качественный.

Если < 0, то качественный критерий важнее, чем временной.

Если = 0, то качественный критерий равнозначен временному.

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

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

Если удастся построить адекватную СИМ, то она позволит проводить значительное количество исследований (имитаций) и, несомненно, будет обладать рядом преимуществ.

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

Литература

 © НОК CLAIM, 2006-2012. Замечания, вопросы и сведения об ошибках просим сообщать в форуме или присылать администратору сайта.