5.3. Система с подстройкой параметров генетических алгоритмов

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

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

 

 

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

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

•    имитационная модель служит для составления плана и использует для этого набор эвристических правил для определения приоритета того или иного заказа включаемого в план работ;

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

•    ЭС предназначена для изменения параметров поиска на основе некоторых представлений человека-оператора о перспективности той или иной стратегии поиска.

Рассмотрим работу такой гибридной системы на примере системы планирования работы цеха [135-139].

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

Все элементы участка представлены в имитационной модели в терминах среды РДО как ресурсы.

Для планирования в относительно простой имитационной модели были описаны следующие операции (они описаны в РДО как модифицированные продукционные правила):

•    обработка партии на станке; время обработки рассчитывается как число деталей в партии, умноженное на время выполнения операции;

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

•    наладки станков;

•    изменения маршрута обработки партии, когда время превышает минимальное время начала обработки заказа.

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

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

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

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

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

ЭС осуществляет направленный выбор таких параметров ПГА, как: размер популяции, вероятности скрещивания и мутации. Кроме того, она применяет некоторые правила для сохранения особей с высоким значением

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

ЭС таким образом представляет область комбинации знаний о генетических алгоритмах, вычислительной математике, искусственном интеллекте и знаний эксперта. Прикладная область для ЭС хорошо не определена, и пространство поиска плохо структурировано; именно поэтому ЭС работает наряду с ПГА на основе текущих данных относительно популяции и текущего состояния имитатора.

В отличие от имитатора, в ПГА и ЭС нет потребности учитывать временной аспект. Поэтому образцы действий в РДО для ПГА и ЭС представляют собой обычные продукционные правила.

С помощью ПГА оптимизировалось расписание операций для цеха, состоящего из семи станков; портфель заказов содержал 10 позиций; общее количество операций, выполняемых над деталями, составляло 64 (от 3 до 13 операций на деталь). Управляемые переменные при оптимизации были приоритеты заказов. Приоритет заказа был задан целым числом в диапазоне от 1 до 8, увеличение значения приоритета ускоряет обработку заказа. Приоритет кодируется тремя битами, длина битовой строки-хромосомы равнялась 30 битам (10 раз по 3). Функция оценки качества получаемого расписания S представляла собой сумму штрафов для каждого заказа. Значение штрафа вычислялось следующим образом. Если заказ опоздал к плановому сроку, то штраф равнялся значению величины опоздания в квадрате, если изготовление заказа завершалось раньше планового срока, но не более, чем на 4 часа, то штраф равнялся нулю. Если же опережение было больше четырех часов, то штраф равнялся значению величины опережения минус 4 часа.

Задача оптимизации формулировалась следующим образом: найти сочетание приоритетов заказов, минимизирующее значение штрафной функции.

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

где S — функция оценки качества расписания.

Поскольку функция оценки качества расписания неотрицательна, то функция пригодности меняется от 1 при 5 = 0 (наилучшее расписание) до 0 при 5, стремящимся к бесконечности.

Предварительные результаты минимизации этой функции с помощью ПГА с различным значением размера популяции N показывают возможность улучшить качество расписания. Так, в различных прогонах модели с N = 50 ... 400, среднее значение функции пригодности увеличено с приблизительно 0,18 (первое поколение) до 0,64 0,68 в десятом-двадцатом поколениях, что соответствует значениям S-функции, уменьшающейся от 90 до менее чем 10. Некоторые результаты минимизации функции пригодности с помощью ПГА при различных значениях его параметров показаны на графиках (рис. 5.15). На графиках приведены средние значения функции

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

Некоторые исследовательские прогоны модели, когда процесс поиска управляется ЭС (рис. 5.16), показывают возможность увеличить эффективность поиска, даже применяя довольно простые правила в ЭС. Примеры правил:

•    Если (/ (uji) лучшей особи в текущем поколении меньше чем / (иі) лучшей особи в предыдущем поколении) То (заменить самую плохую особь в текущем поколении на лучшую особь в предыдущем поколении);

•    Если ((/тах - /тіпУ/шеап < 1) То (Р(ОК) = 0,9, Р(ОМ) = 0,7);

•    Если ((/тах - /пппУДпеап > 1) То (Р(ОК) = 0,6, Р(ОМ) = 0,1), где /max, /гпіп? /mean — максимальное, минимальное и среднее значения функции пригодности последнего поколения.

Как видно из результатов исследования

(рис. 5.16), лучшее значение функции пригодности без ЭС — 0,541, в то время как с использованием ЭС — 0,648 (для N = 50).

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