Моделирование времени обработки деталей из листа с использованием дробно-степенны рядов и генетического алгоритма

УДК 519.855 / 621.98.01

Моделирование времени обработки деталей из листа с использованием дробно-степенны х рядов и генетического алгоритма

А. Х. Тлибеков

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

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

Введение

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

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

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

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

МЕТ^^^РАБОТК)»

тельные алгоритмы, основанные на использовании производных.

Среди методов решения многопараметрических, многокритериальных и мультимодаль-ных задач наиболее эффективными являются алгоритмы ЛП-поиска [1, 2], поведенческие алгоритмы, например метод «пчелиного роя» (Bees Algorithm) [3-5], и генетические алгоритмы1 [6-10].

В данной работе приведены комбинированный генетический алгоритм (КГА) и результаты его тестирования. В ходе тестирования решались тестовые задачи и задачи аппроксимации табличных значений времени обработки деталей из листа как функции нескольких переменных дробно-степенны! ми рядами. Сравнивались полученные результаты с результатами, вычисленными методом Ньютона.

Постановка задачи математического программирования

Комбинированный генетический алгоритм

Алгоритм (рис. 1) построен на основе комбинации двух методов: пассивного поиска минимума [11] и генетического алгоритма.

1. Формирование вариантов управляемых параметров модели (детерминированный метод). Для каждого управляемого параметра выполняется деление интервала неопределенности I на равноотстоящих точек, где — число из последовательности Фибоначчи. Порядковый номер д > 10 числа Фибоначчи назначается как целая часть числа, рассчитанного на основе максимальной длины интервала неопределенности ^шах : д = 2п [| 1§(!тах) | -1] / е. Ф°рмируется матрица управляемых параметров: строки матрицы представляют линейную сетку по каждому управляемому параметру, столбцы матрицы содержат варианты управляемых параметров.

Задаются пределы изменения управляемых параметров а1, ..., аг или параметрические ограничения а* < а^ < а**, ] = 1, г, которые образуют в г-мерном параллелепипеде П допустимое множество Б е П. Длина граней па-

Г** *

г_________________,„,„ ^ = а* - а* определяет длину интервала неопределенности.

Целевая функция, или критерий оптимальности Фп(а), V = 1, к, позволяет количественно сравнить альтернативные варианты управляемых параметров.

Принцип оптимальности: оптимальное решение найдено, когда все критерии оптимальности улучшили свои значения, т. е. те, которые должны увеличиться, — увеличились, а те, которые должны уменьшиться, — уменьшились. Этот принцип называется принципом оптимальности по Парето, согласно которому требуется найти такое множество Па-рето Р е Б, для которого Ф(Р) = штаеБФ(а), где Ф(Р) = (Фх(а), ..., Фк(а)} — целевая функция. В результате решения определяют вектор управляемых параметров а0, принадлежащий множеству Р и являющийся наиболее предпочтительным (или оптимальным) из всех векторов этого множества.

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

Рис. 1. Блок схема комбинированного генетическо-гоалгоритма

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

3. Поиск минимального значения целевой функции. Минимальное значение целевой функции Фт1п (а0д, ..., а0,г) = minфmin, где

Фmin = V(ф8д)2 + ••• + (Фа,k)2 , s — номер итерации поиска; а0 1, ..., a0 r — точка промежуточного оптимума (если s = 0 — «нулевая точка»).

4. Сужение интервала неопределенности около точки промежуточного оптимума: а* = = а0 - KcIj, а** = а0 + KcIj, где Kc < 1,0 — коэффициент сужения интервала неопределенности.

5. Скрещивание.

5.1. Формирование начальной популяции особей (формирование вариантов управляемых параметров) детерминированным методом и методом случайных чисел.

5.2. Скрещивание особей методом панмик-сии. Генерируются случайные числа 1 < t < Kt (целые числа) и 0,0 < p < 1,0. Ситуация совпадения чисел t ислючается. Каждому гену (или управляемому параметру) ставится в соответствие одно из чисел t. Брачная пара образуется выбором двух пар случайных чисел: t1 и t2; p1 и p2 = 1,0 - p1. Формируется новый ген (новое значение управляемого параметра): aj = p1a^ + p2ata. Новые гены образуют новые хромосомы (вариант значений управляемых параметров) и новое поколение из Kt особей (все варианты значений управляемых параметров).

5.3. Вычисление пригодностей хромосом. Для каждой хромосомы из начальной популяции вычисляется ее пригодность (или для каждого варианта управляемых параметров: вычисляется значение целевой функции). Минимальному значению пригодности соответствует перспективная хромосома. Поиск минимального значения пригодности (поиск минимального значения целевой функции) выполняется по методу п. 3.

6. Мутации. Изменению подвергается каждый ген перспективной хромосомы а0 в пределах а* < аj < aj . Вычисляются пригодности мутированных хромосом, и выполняется поиск минимального значения пригодностей по методу п. 3.

7. Расширение интервала неопределенности около точки промежуточного оптимума: а* = а0 - KpIj, а** = а0 + KpIj, где K > 1,0 -

№ 1(73)/2013

коэффициент расширения интервала неопределенности.

8. Остановка вычислений выполняется контролем принятого предельного числа циклов поиска 8 (количества поколений особей) и заданного изменения целевой функции А на каждом шаге итерации.

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

Тестирование алгоритма

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

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

Таблицы тестовых данных были образованы N значениями функции в зависимости от <1 переменных (табл. 2). Аппроксимация производилась по ограниченной выборке из к, табличных значений дробно-степенны!м рядом Пюизё2:

/ (а) = £ <<=1 + £ ^ В^х* 1 + +ВихР'хЪ + СП <=1 х* ,

2 Ряд Пюизё с одной переменной — это алгебраическое выражение вида: ¥(X) = ^ = апХп/т, в котором число п0 — целое, число m — натуральное (при m = 1 получается обычный степенной ряд), коэффициенты an — рациональные числа. В данной работе для аппроксимации табличных значений функции от нескольких переменных предлагается использовать ряд Пюизё, включающий суммы и произведения переменных.

29]

МЕТ^ПЛОО^РАБОТК^

Мультимодальные модели для тестирования КГА

Таблица 1

Модель Уравнения тестовой функции Параметрические ограничения

Розенброка (Rozenbrok) F(a1, a2) = 100(a2 - a2)2 + (1 - a)2 -5,0 < a1 < 5,0; -5,0 < a2 < 5,0

Растригина (Rastrigin) F(ai, a2) = 20 + aj2 + aj2 - 10(cos2nai + cos2na2) -2,0 < a1 < 2,0; -2,0 < a2 < 2,0

Шекеля (Shekel) F(a1, a2) = [1 + (a1 - 2)2 + (a2 - 10)2 ]-1 + + [2 + (a1 - 10)2 + (a2 - 15)2 ]-1 + [2 + (a1 - 18)2 + (a2 - 4)2 ]-1 0 < a1 < 20,0; 0 < a2 < 20,0

Химмельблау (Himmelblau) F(a1, a2) = (a2 + a2 - 11)2 + (a1 + a2 - 7)2 -10,0 < a1 < 10,0; 10,0 < a2 < 10,0

в)

г)

Рис. 2. Фрагменты поверхностей, отображающие тестовые функции в пределах параметрических ограничений (табл. 1): а — Розенброка; б — Растригина; в — Шекеля; г — Химмельблау

где управляемые параметры а обозначены как А, В, С, Ь, у, §, X, причем для й = 1 Да) = Ахя,

для й = 2 f (а) = А1Х11 + А2Х22 + ВхЬ х2>.

Аппроксимация табличных данных также выполнена методом Ньютона. Метод Ньютона — это бесконечно шаговый алгоритм второго порядка, основанный на замене минимизируемой функции квадратичной частью ряда Тейлора [11], поэтому его использование для аппроксимации дробно-степенны м рядом, если удается исключить нулевые значения аргументов, обеспечивает устойчивость вычислительного процесса.

Точность аппроксимации рассчитывалась по формуле: е = (Фр - Фт) / Фт, где Фр и Фт — суммы расчетных и табличных значений критериев оптимальности.

Анализ полученных результатов и выводы

Предложенный метод аппроксимации использует компания Weber Engineering в практике проектирования технологических процессов, когда по ограниченному числу рассчитанных в САМ-системах или полученных

Таблица 2

Описательная статистика тестовых функций, полученная с использованием КГА

Описательная статистика Функция

Розенброка Растригина Шекеля Химмельблау

aL = 1,0 a2 = 1,0 a1 = 0,0 a2 = 0,0 a1 = 2,0 a2 = 10,0 a1 = 3,0 a2 = 2,0

Среднее 1,0 0,999998 0,0 0,0 2,0012 10,001 3,0 2,0

Стандартное отклонение 0,0 4,47 • 10-6 0,0 0,0 0,0 0,0 0,0 0,0

Дисперсия выборки 0,0 2 • 1011 0,0 0,0 0,0 0,0 0,0 0,0

Минимум 1,0 0,99999 0,0 0,0 2,0012 10,001 3,0 2,0

Максимум 1,0 1,0 0,0 0,0 2,0012 10,001 3,0 2,0

Таблица 3

Результаты аппроксимации табличных данных методами КГА и Ньютона

d N k r Ф Метод КГА Метод Ньютона

Ф р S е, % Ф р е, %

1 41 12 2 110,6 121,5 38 -9,86 121,5 -9,86

2 38 7 7 1,464 1,454 790 -0,69 1,466 0,14

3 23 4 19 8,92 8,90 674 -0,27 8,91 -0,07

4 594 38 25 1094,6 1100,3 1004 0,51 1071,3 -2,13

хронометражом норм времени обработки деталей из листа необходимо достоверно определить время обработки всей программы деталей [12]. В табл. 3 представлены задачи, решенные в ряде проектов.

Первый тест ^ = 1) — определение периметра детали из листа по площади ее поверхности. Тестовая таблица содержала значения площади поверхности и периметра для 41 детали N = 41). Сумма всех периметров равнялась 110,6 мм (Фт = 110,6). Использованием выборки из 12 деталей ^ = 12) методом аппроксимации получено значение периметра всех деталей, равное 121,5 мм (Фр = 121,5). Погрешность аппроксимации не превысила 10 %.

Второй тест ^ = 2) — определение времени обработки деталей (мин) на координатно-револьверном прессе3 в зависимости от количества ударов инструмента (жх) и количества смен инструмента (х2), необходимых для изготовления детали. Аппроксимация с использованием выборки из 7 деталей позволила рассчитать общее время обработки 38 деталей с погрешностью менее 1 %.

3 Здесь и далее приводятся данные, полученные при эксплуатации оборудования компании LVD (Бельгия) для обработки листа, эксклюзивным представителем которой в России и странах СНГ является ООО «Weber Co Mechanics»

Третий тест ^ = 3) — определение времени гибки деталей (мин) на прессе для свободной гибки в зависимости от максимальной высоты полки (жх), массы детали ^2) и количества линий гибки ^3). Аппроксимация с использованием выборки из 4 деталей позволила рассчитать общее время обработки 23 деталей с погрешностью менее 0,5 %.

Четвертый тест ^ = 4) — время резки детали (мин) на машине для лазерной резки в зависимости от толщины листа (x1), периметра внутренних и наружных контуров ^2), предела прочности материала листа при растяжении ^3) и количества врезок ^4). Аппроксимация с использованием выборки из 38 деталей позволила рассчитать общее время обработки 594 деталей с погрешностью около 0,5 %.

Результаты тестирования показывают, что использование КГА для аппроксимации времени обработки на различном оборудовании дробно-степеннь1ми рядами позволяет выполнить расчеты с погрешностью, допустимой для практического использования. Это значительно сокращает время проектирования.

Использование метода Ньютона также обеспечивает высокую точность аппроксимации, причем время вычислений у этого метода гораздо меньше. Для сравнения: решение тестовых задач методом КГА для d = 1 составило 0,48 мин, для d = 2 — 7,78 мин, для

МЕТ^ПЛОО^РАБОТК^

й = 3 — 8,27 мин, для й = 4 — 1 ч 3 мин; время расчета методом Ньютона не превышало 0,5 мин для всех тестовых задач. Это объясняется тем, что увеличение количества управляемых параметров модели (с г = 2 до г = 25, табл. 4) значительно увеличивает число циклов поиска (с 8 = 38 до 8 = 1004, табл. 4). Однако решение задач аппроксимации методом Ньютона имеет недостаток — точность расчета зависит от выбора «начальной точки»: в процессе тестирования установлено, что в зависимости от значений управляемых параметров, с которых начинаются вычисления, в случае мультимодальной целевой функции (й > 1) погрешность аппроксимации составляла более 100 %. Выполнить тесты с погрешностью, показанной в табл. 4, позволил длительный подбор начальных значений управляемых параметров. Работа алгоритма по методу КГА не требует задавать начальные значения управляемых параметров. Они устанавливаются в процессе пассивного поиска минимума и корректируются при сужении и расширении интервалов неопределенности.

Литература

1. Соболь И. М., Статников Р. Б. Выбор оптимальных параметров в задачах со многими критериями качества. М.: Наука, 1981. 110 с.

2. Статников И. Н., Фирсов Г. И. ПЛП-поиск — эвристический метод решения прикладных задач оптимизации // Практика применения научного обеспечения в образовании и научных исследованиях. — СПб.: СПбГУ, 2003. С. 54-57.

3. Karaboga D. An idea based on honey bee swarm for numerical optimization // Technical report — TR06. Erciyes University, Engineering Faculty, Computer Engineering Department. 2005.

4. Pham D. T., Ghanbarzadeh A., Koc E. [et al.]. The Bees Algorithm // Technical Note. Manufacturing Engineering Centre, Cardiff University, UK. 2005.

5. Гришин А. А., Карпенко А. П. Исследование эффективности метода пчелиного роя в задаче глобальной оптимизации // Электрон. науч.-техн. изд. «Наука и образование». 8 авг. 2010.

6. Ворожейкин А. Ю., Семенкин Е. С. Вероятностный генетичнский алгоритм для задач многокритериальной оптимизации // Вестн. Сибир. гос. аэрокосм. ун-та им. акад. М. Ф. Решетнева. 2007. № 3. C. 41-45.

7. Исаев С. А., Виндман П. А. Оптимизация многоэкстремальных одномерных функций с помощью генетических алгоритмов // Вестн. Нижегород. ун-та им. Н. И. Лобачевского. Сер. Математическое моделирование и оптимальное управление. 2003. № 1. С. 180189.

8. Курносова Е. Е., Полупанов А. А. Методы повышения качества решений в эволюционно-генетических алгоритмах // Изв. Юж. федерал.ун-та. Техн. науки. 2009. Т. 93, № 34. С. 62-66.

9. Дмитриев С. В. Об эффективном взаимодействии генетического алгоритма и метода Хука-Дживса для решения многомерных задач оптимизации. ISSN 1813-7903 // Вестн. ИжГТУ. 2007. № 1. С. 58-63.

10. Тенеев В. А. Решение задачи многокритериальной оптимизации генетическими алгоритмами. ISSN 1813-7911 // Интеллектуальные системы в производстве. 2006. № 2. С. 103-109.

11. Тлибеков А. Х., Досько С. И. Прикладные задачи моделирования и оптимизации механических систем: Учеб. пособие для аспирантов и магистров. ISBN 978-3-8473-9944-5. Palmarium Academic Publishing, 2012. 252 р.

12. Тлибеков А. Х. Эффективность проекта модернизации производства деталей из листа // Металлообработка. 2012. № 3 (69). С. 45-51»

Сведения об авторе

Тлибеков Алексей Хабиевич — д-р техн. наук, профессор, гл. инженер проектов ООО «Weber Engineering». 115088, Москва, Шарикоподшипниковская ул., д. 4; тел. (495) 221-12-36 (доб. 1528), факс (495) 229-28-96, моб. тел. (919) 101-38-27, e-mail: tlibekov@weber.ru; сайт: www.weber-engineering.ru