ГИБРИДНЫЙ ГЕНЕТИЧЕСКИЙ АЛГОРИТМ ДЛЯ АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ ОПТИМАЛЬНЫХ ТРАЕКТОРИ Й

Г. В. Пушкарёва (Новосибирск)
 

Впервые методология моделирования эволюции, основанная на аналогии процессов натуральной селекции в биологии, была применена Холландом в 1975 г. к искусственным системам [7]. Использование генетического программирования обусловлено хорошими результатами, полученными при решении различных задач из САПР и АСТПП, и простотой идеи этого метода, позволяющей сосредоточиться на его эффективной реализации.

В данной работе рассматривается применение методологии генетического программирования при автоматизированном проектировании управляющих программ для станков с ЧПУ термической резки металла.

Траектория движения режущего инструмента состоит из следующих элементов: внешних контуров вырезаемых деталей; внутренних контуров; траекторий, связывающих смежные контуры; траекторий переходов инструмента в выключенном состоянии от одной точки врезки к другой.

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

Имеется множество деталей, состоящих из внутренних и внешних контуров. Каждый контур имеет точку врезки. Обозначим расстояние между точками врезки i-го и -го контура в рамках k-ой детали через , между точкой врезки внешнего контура -ой детали и точкой врезки внутреннего контура k-ой детали через . Необходимо найти кратчайший маршрут K* из множества маршрутов , удовлетворяющий всем технологическим ограничениям, проходящий через каждую деталь ровно по одному разу и минимизирующий суммарное пройденное расстояние между точками врезки разных деталей и суммарное расстояние между точками врезки контуров в рамках одной детали:

                                     (1)

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

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

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

Основная особенность генетического алгоритма (ГА) состоит в том, что анализируется не одно решение, а некоторое подмножество квазиоптимальных решений, называемых хромосомами и состоящих из генов. Это подмножество носит название «популяция». В данной реализации начальная популяция формируется случайным образом и в неё включается хромосома, описывающая путь по «жадному» алгоритму. Для рассматриваемой задачи хромосома описывает порядок вырезания контуров деталей с указанием координат начала вырезки каждого контура, поэтому имеет дискретно-непрерывную структуру. Для хромосомы вычисляется целевая функция F(K), называемая эволюционной, где K – маршрут, описываемый хромосомой. Такие функции вычисляют относительный вес каждой хромосомы. В данном случае целевая функция представляет собой длину траектории движения режущего инструмента. Каждый ген в хромосоме состоит из порядкового номера вырезаемого контура и координат начала вырезки этого контура.

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

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

После скрещивания и мутации размер популяции увеличивается. Однако для последующих преобразований необходимо сократить число хромосом текущей популяции. Такая процедура носит название селекции. В текущей популяции, состоящей из родителей и потомков, производится отбор лучших решений, т. е. хромосом с наилучшим значением fittnes-функции (целевой функции). Эта функция показывает, насколько исследуемая хромосома близка к оптимальному решению.

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

На основе тестовых данных в ходе экспериментальных исследований выбираются параметры рассматриваемого генетического алгоритма (см. таблицу 1).

Таблица 1

Параметры реализованного генетического алгоритма

№ п/п

Наименование параметра

Обозначение

Рекомендуемое значение

1

Размер популяции

RP

100–200

2

Число генераций

TG

50–100

3

Вероятность скрещивания

PS

0,7–0,9

4

Вероятность мутации

PM

0,003–0,01

5

Степень обновления популяции

SO

0,95–1,0

6

Количество попыток

KP

3–5

7

Вид металла

TM

1-тонколистовой,
2-толстолистовой

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

KI = (1,0 – SO) * RP,                                                           (2)

где SO – степень обновления популяции, RP – размер популяции.

Как было указано выше, генетический алгоритм обрабатывает популяцию решений, закодированных в хромосомы. В процессе обработки популяции, к ней последовательно применяются различные генетические операторы, такие как скрещивание, мутация с заданными вероятностями (PS и РМ соответственно) и другие операторы. Затем проводится селекция увеличившейся популяции для отбора лучших решений, которые составят следующее поколение, после чего цикл (генерация) повторяется. Число таких циклов называется числом генераций TG.

Количество поколений, которое требуется для нахождения кратчайшего маршрута, зависит также от начальной генетической информации в первом поколении. Поэтому оно меняется от попытки к попытке. Для получения наилучшего результата работы генетического алгоритма рекомендуется сделать несколько попыток (3–5).

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

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

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

  Рис. 1. Общая схема реализованного ГА (графическая нотация Rational Rose)

  Оператор скрещивания представляет собой процесс, в ходе которого выбирают двух подходящих индивидуумов и скрещивают их. При этом потомство получит некоторые черты от обоих родителей. Механизм скрещивания для рассматриваемой задачи имеет ряд особенностей. Один индивидуум выбирается с наилучшим значением целевой функции в текущей популяции, а другой индивидуум выбирается случайным образом. Обмен значениями случайно выбранного гена в хромосомах происходит только в том случае, если вероятность обмена меньше заданной вероятности скрещивания PS. В данной реализации оператор скрещивания является модифицированным, так как в нём предусмотрен механизм, исключающий возникновение «нелегальных» решений. Такими решениями считаются хромосомы, не отвечающие условию задачи.

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

Оператор разнообразия также вносит изменения в отдельного индивидуума, но это очень небольшие изменения в каждой хромосоме, а не сильное изменение хромосомы, как происходит при мутации. С целью улучшения значения целевой функции каждая хромосома обрабатывается итерационным алгоритмом, основанным на методе циклического координатного спуска. Идея метода заключается в том, что его итерация (цикл) состоит из последовательности шагов. В процессе реализации каждого шага значения целевой функции F(K) улучшаются, так как минимизируется компонента целевой функции Lj(x,y), зависящая от координат начальной точки вырезки соответствующего j-го контура (j=1,2,…,n).

В ходе работы итерационного алгоритма смежные участки траектории движения попарно рассматриваются и заменяются отрезком или ломаной линией, минимально возможной длины, с учётом принадлежности начальных точек вырезки соответствующим контурам деталей. Для минимизации количества врезок исполнительного инструмента приоритетным является выбор начальной точки вырезки контура, совпадающей с начальными точками вырезки смежных контуров. Если изменение целевой функции F(K) для двух последних итераций не превысило заданную точность ε, то итерационный алгоритм оператора разнообразия прекращает свою работу.

Оператор селекции формирует новое поколение из хромосом с лучшими значениями целевой функции F(K). Он уничтожает большую часть популяции и освежает генетический материал, пополняя популяцию большим количеством новых членов. В результате выполнения оператора селекции размер популяции нового поколения вновь становится равным RP.

После выполнения всех генераций TG очередной попытки определяется хромосома с наилучшим значением целевой функции F(K). В результате реализации заданного количества попыток KP будет получен кратчайший путь движения исполнительного инструмента за время работы генетического алгоритма F(K*).

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

 

  Рис. 2. Реализация ГА для фрагмента технологической карты раскроя

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

Таблица 2

Хромосома результирующей траектории движения

Порядковый номер контура в наборе

3

4

5

2

8

0

1

7

6

Первая координата начальной точки вырезки контура

69,5

69,5

78,2

253,8

253,8

273,9

305,9

221,3

221,3

Вторая координата начальной точки вырезки контура

117,7

117,7

125,8

290,0

290,0

210,7

84,3

58,3

58,3

  Программный комплекс реализован как пользовательское VLX-приложение системы AutoCAD, включающее в себя fas-проекты, и разработан в среде VisualLISP.

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

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

Литература

1.      Батищев Д.И. Генетические алгоритмы решения экстремальных задач. – Воронеж, 1995.

2.      Дегтярев Ю.И. Методы оптимизации. – М.: Сов. радио, 1980.

3.      Новиков Ф.А. Дискретная математика для программистов. – М.: Питер, 2001.

4.      Полещук Н.Н. VisualLISP и секреты адаптации AutoCAD-СПб.:БХВ-Петербург, 2001.

5.      Сигал И.Х. Приближённые методы и алгоритмы в дискретной оптимизации. – М.: МИИТ, 2000.

6.      Сухарев А.Г. и др. Курс методов оптимизации. – М.: Наука, 1986.

7.      J. Holland. Adaptation in natural and artificial systems. University of Michigan Press Ann Arbor, USA, 1975.