PARAMETRIC SYNTHESIS ALGORITHMS IN THE DESIGN OF FLEXIBLE MANUFACTURING SYSTEMS BASED ON COMPUTER MODELING

Full Text

Введение Растущее конкурентное давление вынуждает разработчиков более точно анализировать проектируемые высокоавтоматизированные производственные системы. Стохастическая природа и постоянно возрастающая сложность этих систем делают большинство аналитических моделей чрезмерно упрощенными или вычислительно трудноразрешимыми. Поэтому дискретно-событийное моделирование становится одним из наиболее широко используемых и принятых инструментов анализа и проектирования производственных систем. Популярность имитационного моделирования в процессе проектирования объясняется отсутствием аналитического аппарата, позволяющего определять требуемые характеристики таких сложных систем, как гибкие производственные системы (ГПС). Разработка проекта ГПС начинается с определения номенклатуры и объема производимых изделий. При подборе оборудования и конфигурации системы, включая количество и характеристики оборудования, проектировщик неоднократно модифицирует входные параметры, после чего проверяет на имитационной модели, до достижения заданной эффективности производства запланированной номенклатуры изделий. В процессе поиска эффективного проектного решения выполняется анализ и сопоставление различных возможных вариантов, общее количество которых, как правило, чрезвычайно велико, соответственно, анализ всех возможных вариантов проектируемой системы человеком невозможен. Из сказанного следует, что заданию на проектирование ГПС соответствует большое число структурно-параметрических вариантов; причем выбрать вариант вряд ли возможно чисто расчетным путем, поскольку он связан с необходимостью решения задачи оптимизации с противоречивыми критериями. Построение имитационных моделей ГПС позволяет на стадии их проектирования находить и устранять узкие места, учитывать влияние отказов и аварийных ситуаций на выполнение производственного плана. Одновременно могут быть решены задачи параметрического синтеза: получены такие важные показатели, как скорости перемещения транспортных средств, время загрузки и выгрузки заготовок, средние и максимальные размеры очередей, длительность межоперационного складирования объектов производства и другие. При детальной проработке моделей определяют потребность в приспособлениях, оснастке, инструменте. Имитационное моделирование позволяет установить и исследовать такие технико-экономические показатели работы ГПС, как коэффициент загрузки оборудования, длительность производственного цикла, объем незавершенного производства, размер партий запуска, график запуска заготовок, график выпуска изделий, циклограммы загрузки оборудования, производительность системы, которые напрямую зависят от проектных решений, принятых на этапах структурного и параметрического синтеза. Однако, любая имитационная модель позволяет оценить только один вариант системы. При проектировании новой системы необходимо проанализировать несколько комбинаций проектных переменных (входных данных), чтобы определить наилучший проектный вариант. Проверенные статистические процедуры, которые относительно легко понять и реализовать, применимы для анализа отдельных систем или сравнения небольшого конечного числа альтернатив. Однако, большинство систем проектирования будет более эффективным, если использовать оптимизационный подход. Методика исследований Алгоритмы поиска целенаправленно подводят имитационную модель к решению, близкому к оптимальному с заданной точностью, как показано на рисунке 1. Рисунок 1 - Процесс оптимизации компьютерной модели Процесс инициируется пользователем, вводящим исходные данные для значений расчетных переменных. Эти значения передаются в программу моделирования. Запуск имитационной модели определяет выходной показатель эффективности, который оценивается алгоритмом поиска. Качество выходных данных предопределяет для алгоритма выбор новых входных значений и процесс повторяется. Поиск может быть прекращен после определенного числа итераций (выбор новых входных значений) или после того, как более улучшенные входные данные не могут быть найдены. Большинство оптимизационных алгоритмов содержат встроенные механизмы для увеличения числа повторений на итерацию по мере приближения к окончательному решению. Поэтому при инициализации выполняют грубый поиск, в то время как последние итерации выполняют более точный поиск. В научной литературе по нелинейному программированию проводится общее сравнение алгоритмов поиска, описываются их преимущества и недостатки. Существует несколько неубедительных сравнений между глобальными поисковыми алгоритмами, поскольку результаты, как правило, очень специфичны для конкретных задач. Качество и скорость сходимости решений с моделированием отжига и генетического алгоритма очень чувствительны к выбору параметров [1]. В литературе по применению моделирования, как правило, не дается количественной оценки эффективности оптимизационных алгоритмов или качества их решений. Смоделированные системы слишком сложны для сравнения с аналитическими решениями. В некоторых статьях проводится качественное сравнение алгоритмов поиска с помощью моделирования. Известны публикации о количественном сравнении между поиском по образцу, методологией поверхности отклика и генетическим алгоритмом для задачи без ограничений с двумя переменными. В них отмечается, что генетический алгоритм значительно улучшил качество решения, но потребовал большего количества прогонов моделирования [1]. Отсутствие достаточного количества публикаций по исследованию оптимизационных алгоритмов для имитационного моделирования обуславливает необходимость расширения количественной оценки эффективности для дополнительных алгоритмов и более сложных задач. Методы оптимизационного поиска можно классифицировать как локальные или глобальные. Локальные методы незначительно модифицируют входные параметры, при которых найдено текущее оптимальное решение в надежде определить еще более лучшее решение. Такие ограниченные стратегии рискуют остановиться в области локального оптимума. Глобальные методы имеют особые механизмы, позволяющие избежать локальных оптимумов. Среди методов локального поиска оптимальных значений для выходных данных моделирования можно выделить метод покоординатного спуска, прямой поиск по образцу Хука-Дживса. Метод покоординатного спуска эффективен для одноэкстремальных функций. Для сокращения количества вычислений величину шага изменяют на каждом переходе от одной координаты к другой. Алгоритм оптимизации Хука-Дживса чередует исследовательский поиск и поиск по образцу. Исследовательский поиск изменяет одно значение переменной за раз от текущего лучшего решения. Поиск по образцу изменяет все переменные одновременно в зависимости от результатов исследовательского поиска. Размер шага автоматически ускоряет поиск перспективных направлений, что во многих случаях быстро приводит к оптимальному решению. Наиболее распространенные методы глобального поиска - это имитация отжига и генетические алгоритмы. Это общие подходы, требующие разработки конкретного алгоритма и выбора параметров для решения каждой проблемы. Алгоритмы имитации отжига могут избежать локальных минимумов, учитывая во время поиска решения неполноценного качества. Вероятность принятия худшего хода зависит от разницы в ценности решения и текущей стадии алгоритма. Генетические алгоритмы используют операции кроссовера, объединяющие части двух хороших решений, и операции мутации, модифицирующие хорошие решения, для создания новых решений. Генетические алгоритмы, разработанные специально для оптимизации моделирования, показали многообещающие результаты для ограниченного набора задач [1]. Рассмотрим некоторые из отмеченных методов оптимизации более подробно. Одним из простых безградиентных методов оптимизации является метод покоординатного спуска, в котором для выявления направления спуска выбирается в качестве один из координатных векторов . Это дает возможность последовательно варьировать все независимые переменные x1, x2,…, xn для того, чтобы на каждой из них определить минимум (максимум) целевой функции. Очередность изменения независимых переменных задается произвольно и в процессе поиска остается неизменной. Таким образом, многомерный поиск подменяется рядом одномерных поисков, использующих любой одномерный метод оптимизации. Алгоритм метода покоординатного спуска может быть представлен следующими этапами [2, 3]. 1. Задается начальная точка поиска . 2. Выбирается направление поиска, например, для варьируемой переменной x1, то . 3. Выполняется первый шаг по направлению . Значение λ1, выбирается удвоением или минимизацией функции по λ1. 4. После того, как по координате x1 положение минимума определено, делается шаг в направлении к . Значение λ2, находят, минимизируя функцию по λ2 и так далее. 5. Условием окончания поиска является выражение Так как данный метод сводит задачу поиска экстремума функции нескольких переменных к многократному поиску оптимума функции одной переменной определимся с методом одномерной оптимизации. Одним из эффективных методов является метод золотого сечения [3]. 1. Задаются начальные границы отрезка a, b и точность e. 2. Рассчитывают начальные точки деления: , , где - пропорция золотого сечения равная 1,618. 3. Определяют значения в них целевой функции: y1=f(x1); y2=f(x2). Если y1>y2 (для поиска максимума изменить неравенство на y1<y2), то a=x1, иначе b=x2. 4. Если |b-a|<e, то x=(a+b)/2 и останов, иначе возврат к шагу 2. Метод оптимизации Хука-Дживса был первоначально опубликован в 1961 - это прямой поисковый метод, который предназначен для оптимизации целевой функции. Метод Хука-Дживса вычисляет новую точку, используя значения целевой функции в соответствующих точках вокруг начальной. Алгоритм состоит из исследовательского поиска и поиска по образцу. Исследовательский поиск происходит по всем переменным на пути улучшения значения целевой функции для определения новой базовой точки и направления минимизации (максимизации) значения целевой функции. Поиск по образцу выполняется в направлении соединения двух соседних базовых точек для более быстрого уменьшения (увеличения) значения целевой функции [4]. 1. Выбирается начальная точка x(0), переменные приращения , коэффициент уменьшения и параметр завершения . 2. Выполняется исследовательский поиск следующим образом (для минимизации целевой функции): - выбирается и переменное приращение ; - вычисляется и - определяется . - установить , соответствующий . 3. Если - шаг считается удачным; перейти к пункту 5 алгоритма, если нет - перейти к пункту 4. 4. Выполняется проверка завершения, , для (i = l, 2 ... N) и переход к пункту 2. 5 Выполнение шага по образцу. Положим и положим 6. Выполняется исследовательский поиск, используя в качестве базовой точки. 7. Проверяется, является ли ? Если да, то устанавливается и осуществляется переход к пункту 5. Если нет - то выполняется переход к пункту 4. Генетические алгоритмы относятся к методам случайного поиска решения задач оптимизации. Они основаны на имитации механизмов естественного отбора и природных генетических механизмов (выживание наиболее приспособленных). Генетические алгоритмы продемонстрировали значительные успехи при решении многих сложных задач оптимизации и привлекают все большее и большее внимание. Если целевые функции в решаемых задачах оптимизации являются многоэкстремальными или пространства поиска частично нерегулярны, требуются алгоритмы, обладающие высокой робастностью для предотвращения застревания в локальных оптимумах. Достоинством генетических алгоритмов как раз и является способность получать действительно глобальное оптимальное решение [5]. Работа генетического алгоритма начинается с генерации возможных решений или отдельных особей. Каждая особь закодирована в векторе (также называемом хромосомой) и представляет собой потенциальное решение проблемы. Начальная популяция генетического алгоритма генерируется случайным образом с учетом ограничений, накладываемых на входные переменные. Как только начальная популяция установлена, рассчитывается целевая функция для каждой особи. Этот шаг известен как оценка пригодности. Следующим шагом является турнирный выбор, который заключается в отборе подмножества особей для турнира и выборе лучшей из них с точки зрения целевой функции. Турниры проходят в парах, победители каждого турнира переходят на операцию кроссовера. На этом этапе отобранные особи, или родители, рекомбинируются в случайном месте и обмениваются своей информацией для создания новых кандидатов решения (потомков). Затем новые кандидаты в решения мутируют. Этот шаг введен, чтобы помочь генетическому алгоритму уйти от локальных оптимальных решений и добавить диверсификации к поиску. Мутация осуществляется путем внесения с заданной вероятностью небольшого изменения в особь. В этом случае изменение осуществляется в пределах ограничений переменной, чтобы избежать невозможных решений. В каждом поколении из общей совокупности родителей и потомков отбираются лучшие особи, чтобы количество кандидатов на начальное решение оставалось постоянным. Процесс останавливается в случае определения искомого значения, если оно задано, в случае если текущее лучшее решение отличается от предыдущего на величину менее заданной точности поиска или после того, как оценивается максимальное количество поколений [6]. Для исследования алгоритмов оптимизации разработана программа компьютерного моделирования процессов функционирования гибких производственных систем на основе результатов исследований, описанных в работах [7-9]. Каждый из алгоритмов оптимизации реализован программно в соответствии с рисунками 2-4. Рисунок 2 - Реализация метода золотого сечения Рисунок 3 - Реализация алгоритма Хука-Дживса Рисунок 4 - Реализация генетического алгоритма Результаты и их обсуждение Для исследования алгоритмов параметрического синтеза проведены вычислительные эксперименты, с помощью которых подбирались такие параметры ГПС как время смены заготовки на робокаре, с, время смены заготовки на станке, с, маршевая скорость перемещения робокара, м/с, количество позиций в пристаночном накопителе паллет с заготовками у станка, шт. Критерием оптимизации выступал максимум коэффициента загрузки ГПС, %. За основу структурной схемы ГПС взята схема из работы [10], за исключением автоматизированной системы инструментального обеспечения, так как моделирование выполняется на уровне технологической операции (рисунок 5). 1 - автоматический склад заготовок; 2 - позиция связи с внешним транспортом заготовок; 3 - позиция остановки робокара при обслуживании станка; 4 - робокар; 5 - пристаночный накопитель паллет; 6 - рабочая зона станка; Рисунок 5 - Схема ГПС Моделирование выполнялось для варьирующегося числа станков от 5 до 10. Сначала были определены минимальные и максимальные значения коэффициента загрузки для каждого варианта количества станков при заданном диапазоне варьирования параметров. После этого для каждого варианта ГПС выполнен синтез технических параметров с применением каждого из трех реализованных алгоритмов. Результаты эксперимента приведены на рисунке 6. Рисунок 6 - Найденные значения коэффициента загрузки ГПС Следует отметить различные условия завершения поиска, у алгоритма покоординатного спуска по методу золотого сечения - это достижение минимального значения изменения параметра, у алгоритма Хука-Дживса - определение оптимума с заданной точностью, остановка работы генетического алгоритма выполнена по всем трем условиям, отмеченным ранее [6]: достижение заданного значения, минимальное отличие предыдущего оптимума от текущего, достижение алгоритмом максимального количества поколений (в данном эксперименте 1000 поколений). Время работы алгоритмов не оценивалось, однако, было отмечено, что работа алгоритмов Хука-Дживса и покоординатного спуска занимает менее секунды, а работа генетического алгоритма может длиться до 1,5 мин. Это объясняется тем, что для каждой из 30 особей популяции (кортеж входных параметров) выполняется моделирование процесса функционирования ГПС. Хотя генетический алгоритм показал самую длительную работу, он для всех вариантов ГПС определил параметры, при которых с точностью до 1 % достигается глобальное максимальное значение коэффициента загрузки оборудования (рисунок 7). Рисунок 7 - Отклонение найденного оптимального значения от глобального оптимума Выводы. Проведенное исследование показывает высокую эффективность определения глобального оптимума генетическим алгоритмом при самой высокой длительности работы. Хорошие результаты показывает алгоритм покоординатного спуска, реализованный с использованием метода оптимизации золотого сечения. Алгоритм Хука-Дживса показал самую высокую нестабильность определения оптимума, что требует дополнительных исследований по определению величины исследующего поиска и величины поиска по образцу. Дополнительным преимуществом генетического алгоритма является то, что он может определить различные сочетания параметров, при которых достигается оптимальное значение коэффициента загрузки, что дает возможность выбора из предложенных альтернатив наименее затратного варианта. Сократить время поиска возможно за счет исследования влияния величины мутации, которая не позволяет алгоритму застрять в области локального оптимума, но ухудшает сходимость решения (в исследовании вероятность мутации составляла 30 %).

About the authors

A. I Sergeev

Orenburg State University

Email: alexandr_sergeew@mail.ru
Orenburg, Russia

S. E Krylova

Orenburg State University

Email: krilova27@yandex.ru
Orenburg, Russia

S. Yu Shamaev

Orenburg State University

Email: aki_2123@mail.ru
Orenburg, Russia

T. R Mamukov

Orenburg State University

Email: mamukov_2015@mail.ru
Orenburg, Russia

References

Supplementary files