Full Text

Современные CAD/CAM системы, используемые на производстве, позволяют генерировать управляющие программы (УП) для режущего оборудования с ЧПУ в автоматическом режиме. Поэтому возникает необходимость оптимизации маршрута режущего инструмента (РИ) еще до генерации самой УП. Сформированный маршрут РИ должен обладать следующими свойствами: - корректностью, т.е. не должен нарушать используемую технологию резки; - рациональностью, т.е. быть близким к оптимальному и без лишних перемещений РИ. Общая длина маршрута РИ представляется суммой длин рабочего и холостого хода. При использовании стандартной технологии резки, при которой контур детали имеет ровно одну точку врезки и вырезается без прерывания, возможно уменьшить только длину холостого хода. При этом данный подход позволит сократить время работы режущего оборудования [1]. Особенность задачи минимизации длины холостого хода РИ заключается в том, что она основана на задаче коммивояжера (TSP - Travelling Salesman Problem), которая, как известно, является NP-трудной. Из этого следует невозможность применения точных методов оптимизации, так как число вариантов перемещения РИ очень велико. В подобных случаях, когда для решения задачи оптимизации не применимы точные методы, используются эвристические и метаэвристические подходы. Они не гарантируют достижения наилучшего решения задачи (глобального оптимума), но находят «достаточно хорошее» (квазиоптимальное) решение за приемлемое время [2]. Целью данной работы являются выбор эффективной метаэвристики и разработка на её основе алгоритма минимизации длины холостого хода РИ. Анализ существующих работ показывает, что наиболее популярными методами оптимизации маршрута РИ являются генетические (GA - Genetic Algorithms) [3] и муравьиные алгоритмы (ACO - Ant Colony Optimization) [4, 5]. При удачной настройке перечисленные методы позволяют получить сравнимые результаты для данной задачи. Недостаток GA и ACO заключается в наличии большого числа управляющих параметров, что затрудняет настройку методов для решения конкретных задач. В [6] для решения классического варианта TSP успешно применен метод имитации отжига (SA - Simulated Annealing), получивший кратчайший маршрут по сравнению с ACO, GA и рядом других метаэвристик. В [7] отмечено, что SA способен находить приемлемое решение быстрее, чем GA. В книге [8] рекомендуется отдавать предпочтение данному методу при решении широкого круга задач оптимизации. Основная идея SA заключается в том, чтобы всегда переходить в лучшее решение и с некоторой вероятностью в худшее. При этом на начальном этапе работы алгоритма вероятность перехода к худшему решению относительно высока и практически нулевая в конце работы. Для этого используется специальный параметр, называемый температурой, которая понижается в процессе работы алгоритма. К достоинствам метода имитации отжига относятся простая структура алгоритма и небольшое число операций, выполняемых при поиске решения. Это позволяет сконцентрироваться на эффективной реализации и настройке метода для решения конкретных задач оптимизации. Интересными для исследования и применения являются метод пороговой допустимости (TA - Threshold Accepting) [9] и алгоритм всемирного потопа (GD - Great Deluge Algorithm) [10]. Эти метаэвристики имеют некоторое сходство с SA, однако не так хорошо освещены в литературе на русском языке. Основное отличие TA и GD от SA заключается в использовании детерминированных правил перехода к новому решению. Достоинство данных методов заключается в наличие небольшого числа управляющих параметров, что значительно упрощает настройку алгоритмов, разработанных на их основе. В методе TA переход к новому решению осуществляется, если оно не намного хуже, чем текущее. При этом метод использует специальный параметр, определяющий допустимую величину ухудшения значения целевой функции при переходе из лучшего решения в худшее. При использовании GD переход к новому решению выполняется, если значение целевой функции будет лучше некоторой величины (уровня воды), которая увеличивается (уменьшается) в процессе решения задачи на максимизацию (минимизацию). Отличие GD от предыдущих методов заключается в том, что возможность перехода к новому решению не зависит от значения целевой функции для текущего решения. Таким образом, для разработки и экспериментальной проверки алгоритма минимизации длины холостого хода РИ были выбраны три метаэвристики: - метод имитации отжига (SA); - метод пороговой допустимости (TA); - алгоритм всемирного потопа (GD). Исходными данными при решении задачи минимизации длины холостого хода РИ являются карты раскроя, содержащие информацию о контурах деталей (пример дан на рис. 1). Каждый контур представлен набором геометрических объектов (ГО), который состоит из отрезков, дуг и окружностей. Выделяют две группы контуров: - внешние контуры, присутствующие у каждой детали; - внутренние контуры, которые могут отсутствовать. Рис. 1. Пример карты раскроя, сформированной программным комплексом ITAS NESTING [11] В результате решения данной задачи будут определены координаты точек врезки и допустимая последовательность вырезания контуров. При этом полученный маршрут перемещения РИ на холостом ходу должен удовлетворять ряду ограничений, связанных с особенностями процесса резки листового материала: 1. Маршрут начинается и заканчивается в начале координатной системы. 2. Маршрут проходит только через одну точку каждого контура (точку врезки). 3. Внешний контур детали вырезается только после всех внутренних контуров. Данная задача с учетом ограничений 1-3 соответствует обобщенной задаче коммивояжера с условиями предшествования, которая является NP-трудной, как и базовый вариант TSP [12]. Введем ряд обозначений. Конечное множество контуров на карте раскроя обозначим . При построении пути РИ, если применяется стандартная технология резки, на каждом контуре необходимо выбрать единственную точку врезки . Поскольку контур является непрерывной геометрической фигурой, состоящей из набора ГО, точка врезки выбирается из конечного множества потенциальных точек врезки -го контура . Для определения точек врезки, которые попадут в конечный маршрут РИ, а также для формирования допустимой последовательности вырезания контуров необходимо выполнить оптимизацию пути. В качестве метрики в данной задаче выступает евклидово расстояние между двумя точками на плоскости, определяемое по формуле (1) где - координаты первой точки, - координаты второй точки. Отметим, что согласно [8] многие приближенные методы для метрических задач работают значительно лучше, чем для TSP в базовой постановке. При минимизации общей длины холостого хода РИ целевая функция представляет собой сумму длин допустимых переходов между точками: (2) где - общая длина холостого хода РИ, - допустимый маршрут. Последовательность вырезания контуров , при которой достигается минимальное значение целевой функции (2), должна принадлежать множеству K допустимых маршрутов, где - перестановка чисел , такая, что получаемый маршрут удовлетворяет ограничениям 1-3. Для решения поставленной задачи предложена обобщенная схема алгоритма, состоящая из десяти этапов: 1) получение списка контуров; 2) определение множества потенциальных точек врезки для каждого контура; 3) инициализация параметров метаэвристики; 4) создание начального маршрута; 5) генерация нового маршрута; 6) проверка маршрута на допустимость; 7) переход к новому маршруту; 8) сохранение лучшего маршрута; 9) если выполнен критерий остановки, то переход на 10, иначе на 5; 10) выдача лучшего решения. Конкретизация этапов 3, 7, 9 зависит от выбора SA, TA или GD в качестве метода оптимизации маршрута, остальные этапы являются общими и не зависят от используемой метаэвристики. Рассмотрим этапы 2, 4, 5, 6 более подробно. Для определения множества потенциальных точек врезки контура (этап 2) в работе используются следующие правила: - для каждого отрезка, составляющего контур, в качестве потенциальных точек врезки рассматриваются начальная и конечная точки; - координаты потенциальных точек дуг и окружностей, составляющих контур, определяются с некоторым шагом, который зависит от длины дуги или окружности; - если длина контура мала, то используется только одна фиксированная точка врезки, так как оптимизация размещения точки врезки на маленьком контуре слабо влияет на общую длину холостого хода, но увеличивает пространство поиска и, как следствие, время работы алгоритма. Использование перечисленных правил позволяет формировать маршрут, не нарушающий стандартные подходы к резке, используемые на производстве. Для создания начального маршрута (этап 4) может быть использован модифицированный вариант жадного алгоритма ближайшего соседа (NN - Nearest Neighbor Algorithm). NN начинает работу из начала координатной системы и строит решение поэтапно, добавляя на каждом шаге по одному допустимому контуру в маршрут, который имеет ближайшую потенциальную точку врезки к последней добавленной в маршрут. Алгоритм закончит работу, когда в маршрут будут добавлены все контуры. Для генерации нового маршрута (этап 5) в данной статье используется следующая процедура: 1. Выбираются два случайных контура в текущем маршруте. 2. Выполняется инверсия порядка всех контуров между ними, включая выбранные. 3. Для каждого переставленного контура случайным образом перевыбирается точка врезки из множества потенциальных точек врезки данного контура. При выполнении предложенной процедуры возможно появление недопустимого маршрута из-за нарушения ограничения 3. В данном случае значение целевой функции будет умножаться на некоторую большую константу, что ухудшит качество решения, и оно не будет сохранено как «лучшее». Отметим, что при генерации нового маршрута начальная точка (начало системы координат) считается фиксированной и переставляться не будет. При проверке маршрута на допустимость (этап 6) необходимо проверять только ограничение 3, так как остальные ограничения будут всегда выполнены при использовании предложенной процедуры генерации нового маршрута. С целью определения наиболее эффективной из рассматриваемых метаэвристик и подтверждения работоспособности алгоритма минимизации длины холостого хода РИ был проведен вычислительный эксперимент. В ходе эксперимента использовалась тестовая карта раскроя, содержащая пятьдесят три контура, включая внутренние (рис. 2), где пример построенного маршрута показан красной линией. При проведении вычислительного эксперимента было выполнено по десять запусков алгоритма минимизации длины режущего инструмента для каждой из метаэвристик SA, TA, GD. Поскольку методам необходимо различное время для получения сравнимых результатов, время работы алгоритма было синхронизировано и разбито на два интервала: - быстрый поиск маршрута, t1 = 3…5 c; - длительный поиск маршрута, t2 = 10…15 c; Рис. 2. Тестовая карта раскроя Полученные результаты для обоих временных интервалов представлены в таблице, а также в виде линейчатой диаграммы на рис. 3 (только лучшие результаты). Результаты вычислительного эксперимента t 3-5 с 10-15 с № SA TA GD SA TA GD 1 3454 3368 3391 3303 3128 3005 2 3395 3371 3355 3168 3178 3117 3 3436 3355 3357 3156 3075 3114 4 3405 3349 3248 3315 3044 2973 5 3374 3397 3386 3361 3088 3056 В таблице символом № обозначен номер испытания, в заголовках столбцов приведены названия метаэвристик, в первом столбце - номера испытаний, значения в ячейках - длина холостого хода РИ. Из рис. 3 видно, что разработанный алгоритм минимизации длины холостого хода продемонстрировал наилучший результат при использовании GD в обоих временных интервалах, худший результат был получен при использовании SA. Отметим, что маршрут с минимальной длиной холостого хода при использовании GD был достигнут за 11,04 с, а при использовании SA и TA за 14,6 и 13,1 с соответственно. Таким образом, использование GD в алгоритме минимизации длины холостого хода позволило получить лучший результат за меньшее время. Рис. 3. Лучшие результаты оптимизации длины холостого хода Блок-схема алгоритма минимизации длины РИ при использовании GD в качестве метода оптимизации представлена на рис. 4. Приведенная блок-схема показывает реализацию обобщенного алгоритма минимизации длины холостого хода РИ для GD. Поскольку часть шагов не зависит от выбранной метаэвристики, разработанный алгоритм может быть легко адаптирован и для других рассмотренных методов. Рис. 4. Блок-схема алгоритма минимизации длины холостого хода РИ с использованием метаэвристики GD Таким образом, в работе рассмотрена задача минимизации длины холостого хода РИ, разработан метод её решения. В ходе вычислительного эксперимента была выбрана метаэвристика GD. Разработанный на основе GD алгоритм показал лучшие результаты при минимизации длины холостого хода РИ за меньшее время.

About the authors

R. T Murzakaev

Perm National Research Polytechnic University

Email: rustmur@gmail.com

V. S Shilov

Perm National Research Polytechnic University

Email: vadim.shilov@gmail.com

A. V Burylov

Perm National Research Polytechnic University

Email: artyom.burylov@mail.ru

References

Statistics

Views

Abstract - 19

PDF (Russian) - 20

Refbacks

• There are currently no refbacks.