Содержание к диссертации
Введение
1. Анализ современных моделей и методов проектирования двумерного размещения 13
1.1. Автоматизация проектирования и технологической подготовки заготовительного производства 13
1.2. Классификация задач размещения и место исследуемых задач в ней ,„.15
1.3, Общая постановка задач двумерного размещения 17
1.4, Математические модели двумерного размещения 18
1.5. Обзор методов решения задачи двумерного размещения 19
1.5.1. Точные методы, их достоинства и недостатки 22
1.5.2. Простые эвристики 24
1.5.3. Методы локального поиска оптимума. Общая схема и метаэвристики 28
1,6, Автоматизированные системы проектирования размещения деталей.,.,32
1.7. Выводы 36
2. Эвристические методы размещения деталей на заданных объектах 38
2.1. Схемы кодирования 38
2.1.1. Прямая схема кодирования 39
2.1.2, Кодирование приоритетным списком, перестановкой 39
2.1.3, Кодирование парой последовательностей 41
2,1,4. Кодирование блок-структурой 42
2.2. Однопроходные эвристики проектирования размещения 44
2.2.1. Декодер "нижний левый" 47
2.2.2. Декодер "усовершенствованный нижний левый" 48
2.2.3. Блочный декодер 50
2.2.4. Двойственный декодер 52
2.2.5. Метод размещения деталей в открытую область на базе двойственного алгоритма 53
2.2.6. Декодер замещения 55
2.2.7. Метод локальной перестройки 58
2.2.8. Схема применения алгоритма замещения для размещения деталей на листы 61
23. Выводы 63
3. Генетический алгоритм решения задач прямоугольной упаковки 64
3.1. Генетический алгоритм с позиций локального поиска экстремума 64
3.2, Процедуры скрещивания и мутации 66
3.3, Модификации генетического алгоритма 68
3.4. Схема ограничения поиска решений в генетическом алгоритме 72
3.5. Выводы 74
4 Автоматизированный комплекс построения рационального размещения. Численные эксперименты 75
4.1.. Организация раскройно-заготовительного производства 75
4.2. Структура САПР рационального размещения 77
4.3. Описание автоматизированного комплекса построения рационального , размещения 81
4.3.1. Схема нахождения рационального размещения 81
4.3.2. Выполнение задачи размещения автоматизированным комплексом 83
4.3.3. Функциональные возможности автоматизированного комплекса84
4.4. Постановка численных экспериментов и анализ их результатов 87
4.4.1. Исследование работы генетического алгоритма с различными декодерами 87
4.4.2. Решение задач размещения на полосу на примерах Bortfeld 92
4.4.3. Решение задач размещения на листы на примерах S.P Fekete и J. Schepers 93
4.4.4. Решение задач размещения прямоугольных объектов в свободной области 96
4.5. Выводы 98
Заключение 99
Список литературы
- Автоматизация проектирования и технологической подготовки заготовительного производства
- Кодирование приоритетным списком, перестановкой
- Генетический алгоритм с позиций локального поиска экстремума
- Организация раскройно-заготовительного производства
Введение к работе
Диссертационная работа посвящена созданию автоматизированного комплекса расчета и проектирования рационального размещения прямоугольных деталей на поступающем в производство материале в виде рулонов, листов и открытых областей. Для создания комплекса разработаны эффективные методы и алгоритмы, ориентированные на системы автоматизации проектирования.
Актуальность темы исследования. Результатом роста промышленного производства в России является появление новых производств и увеличение конкуренции среди них. Основными факторами успеха при этом являются: снижение стоимости и повышение качества продукции, гибкость при внедрении новой продукции, сокращение времени вывода ее на рынок. Существенного уменьшения времени цикла проектирования и подготовки производства, увеличения гибкости можно добиться благодаря внедрению автоматизированных систем управления и проектирования. В сложной системе автоматизации определенное место занимают подсистемы автоматизации заготовительного производства, в составе которого важное место занимают программные комплексы расчета рационального размещения деталей. Эти подсистемы должны базироваться на решении оптимизационной задачи, а именно, задачи размещения (упаковки) деталей. Двумерная целочисленная задача размещения относится к классу NP-трудных задач комбинаторной оптимизации. Это означает, что не известно алгоритма полиномиальной сложности для поиска оптимального решения, и точный результат в общем случае может быть получен только за экспоненциальное время.
Поскольку при производстве, как правило, задачи размещения имеют большую размерность, а решение должно быть получено в ограниченное время, актуальной становится проблема разработки и использования эвристических методов поиска и построения решения с организацией эффективных способов перебора. При этом существенную роль выполняют различные алгоритмы конструирования упаковок - декодеры.
6 В настоящее время используются системы автоматизированного
W проектирования размещения деталей (как отечественных, так и зарубежных разработок), отличающиеся структурой и объемом выполняемых работ, качеством конструирования решения и технологической подготовки производства. В первую очередь были разработаны автоматизированные
*\ системы «Нестинга» (размещение деталей сложных форм), особого внимания заслуживают разработки В.Д. Фроловского и А.А, Петунина. Система «Техтран-Раскрой» компании «НИП-Информатика», разработанная под руководством Фроловского В.Д., объединяет возможности САМ-системы с функциями организации производственного процесса [48]. Система «Сириус» (А.А. Петунии) предназначена для проектирования рационального раскроя, а также для подготовки управляющих программ резки [43], Однако в различных системах проектирования долгое время вопросы экономии материальных
ресурсов уходили на второй план. Внимание уделялось главным образом логическим, а не расчетным операциям. Расчеты и проектирование выполнялись быстро за счет использования простых однопроходных эвристик. Попытка объединить два критерия, затраты времени и экономия материала, была осуществлена в докторской диссертации ЭА. Мухачевой[34]. Она использовала в системах автоматизации линейное программирование. Это оказалось возможным в условиях массового производства.
v В современную эпоху, когда появилось много средних и малых
предприятий, непрерывная релаксация в линейном программировании оказывается мало приемлемой. Сиразетдинов Т.П. развил эффективные подходы для расчета гильотинного раскроя, которые базируются на локальном поиске оптимума, и они дали прекрасные результаты. Предлагаемый комплекс посвящен не гильотинному размещению деталей на материале различного вида:
т рулонах, листах, открытых областях (производство плат).
Для внедрения оптимизационных систем расчета упаковки в АСТПП
требуются существенные временные и материальные затраты, что
непозволительно для мелких и средних предприятий- Поэтому и
разрабатываются быстрые алгоритмы, значительно превосходящие по
м> эффективности использования материала простые эвристики.
Все вышесказанное определяет актуальность решаемой в данной работе Чг задачи расчета рационального размещения деталей в системах автоматизированного проектирования.
Цель работы
Создание автоматизированного комплекса проектирования размещения Щ прямоугольных деталей на рулонах, листах и в открытых областях на базе математического моделирования и численных методов решения задач рационального размещения.
Для достижения цели работы были поставлены следующие задачи:
Провести анализ существующих систем автоматизации проектирования размещения прямоугольных деталей, а также методов и алгоритмов решения данной задачи. Выявить их недостатки, определить возможность по совершенствованию процесса проектирования и технологической подготовки производства новых изделий, а также наметить направление улучшения методов расчета поставленных задач;
Разработать технологию применения однопроходных декодеров в рамках общей метаэвристики для решения задачи размещения прямоугольных деталей на полосу, листы и в открытую область;
Mt 3, Разработать новые алгоритмы для построения экономной карты
размещения прямоугольных деталей на базе информации, получаемой на каждом шаге генетического алгоритма; модифицировать известные алгоритмы-декодеры конструирования рационального размещения прямоугольных деталей;
4. Разработать автоматизированный комплекс проектирования
рационального размещения прямоугольных деталей на рулонном, листовом
<Ш материале и в открытых областях на основе разработанных алгоритмов;
Реализовать учет технологических параметров, таких, как припуск на ширину реза, окантовку рулона или листов, получения деловых отходов;
Исследовать эффективность предложенных алгоритмов с помощью численного эксперимента и выработать рекомендации по их использованию.
Методы исследования
#
Результаты исследований, выполненных в работе, базируются на теории и
практике автоматизации проектирования, методах исследования операций,
принципах модульного и структурного программирования. Для анализа
эффективности методов применялись численные эксперименты и методы их
м^ обработки.
На защиту выносятся
Генетический алгоритм с мультиметодным представлением алгоритмов-декодеров, как основа автоматизации проектирования рациональных карт размещения деталей;
Модификации алгоритма замещения, разработанного на базе блочного представления упаковки, предназначенные для получения карт размещения
'^ деталей на листовом и рулонном материале; метод локальной перестройки;
3. Модификация алгоритмов конструирования упаковки, ориентированной
на размещении деталей в открытой области:
3.1. Двойственный алгоритм, разработанный на базе блочного
представления упаковки для получения карты размещения
деталей в открытой области;
л 3-2- Модификация алгоритма размещения деталей в открытую
область, основанный на представлении в виде пары последовательностей;
4. Автоматизированный комплекс построения рационального размещения
деталей на рулонном, листовом материале и открытой области;
5. Результаты численных экспериментов и рекомендации по
Ш использованию предлагаемых алгоритмов.
Научная новизна работы
1. Автоматизированный комплекс построения рационального размещения прямоугольных деталей на рулонном, листовом материале и в открытой области, новизна которого состоит в комбинации генетического алгоритма с множеством
разработанных однопроходных эвристик. Комплекс позволяет производить
W* расчет рационального размещения деталей с учетом технологических
параметров в рамках рабочего места технолога раскройно-заготовительного
производства по двум критериям, уменьшая время расчета и повышая качество
проектирования;
ф| 2, Разработана схема ограничения области поиска решений генетическим
алгоритмом. Новизна состоит в отказе от просмотра неперспективных решений в эволюционном процессе генетического алгоритма, основанного на сравнении нижней границы решения, соответствующей списку прямоугольников с полученным рекордом;
3. Разработаны методы и алгоритмы конструирования размещения
деталей;
,фі вычислительная схема применения алгоритма замещения для
размещения прямоугольных деталей на листы. Основана на учете дополнительного ограничения по длине листа при укладке деталей;
метод локальной перестройки в составе алгоритма замещения, новизна которого состоит в выработке принципов перестановки прямоугольников внутри блоков полосы, листа. Он позволяет повысить эффективность метода замещения без существенных затрат дополнительного времени;
метод для решения задачи размещения прямоугольных деталей в открытую область на базе двойственного алгоритма упаковки деталей в полосе. Основан на ограничении одной из направляющих открытой области,
^ Практическая значимость работы
L Разработан автоматизированный комплекс размещения деталей на полосу, листы, открытую область в составе автоматизированного рабочего места технолога раскройно-заготовительного производства. Разработаны методики применения комплекса в составе АСТ111І- Комплекс позволяет автоматизировать процесс нахождения карты размещения деталей, эффективно использовать
имеющийся материал, значительно сократить время проектирования по сравнению с традиционным ручным способом;
2. Разработано математическое обеспечение двумерного прямоугольного размещения деталей в рамках автоматизированного комплекса. Его применение позволяет повысить коэффициент использования материала в среднем на 5-10% по сравнению с ручным способом или применением простых эвристик;
3- Разработана система учета технологических параметров, учитывающих специфику производства. Применение данной системы в рамках автоматизированного комплекса расширяет круг решаемых практических задач. Разработанные методы решения задачи являются инвариантными и могут быть легко адаптированы под конкретное производство.
Внедрение результатов в виде автоматизированной системы проектирования рационального размещения прямоугольных деталей осуществлено на следующих предприятиях:
1, ООО «Научно-инженерное предприятие - Информатика», г, С.-Петербург -
внедрение в промышленную систему «Тенхтран-Раскрой», 2005.
2. УГАТУ — учебный процесс по специальностям: 080116 «Математические
методы в экономике», 010503 «Математическое обеспечение и
администрирование информационных систем», в рамках курсов «Методы
оптимизации» и «Математические методы и модели исследования
операций» и при выполнении курсовых и дипломных работ, 2004-2005.
Связь исследования с научными проблемами
Работа выполнялась при частичной поддержке грантов Российского Фонда Фундаментальных Исследований (РФФИ), проекты 99-01-000937, 01-01-000510 и 03-01-07002.
Апробация работы и публикации
Первые результаты в виде генетического алгоритма с двумя известными алгоритмами конструирования размещения нашли свое место в дипломной работе «Генетический алгоритм на базе различных декодеров для решения задачи распределения двумерного ресурса», которая была отмечена медалью
11 Министерства Образования РФ «За лучшую научную студенческую работу». Созданный программный комплекс отмечен дипломом за первое место в конкурсе на «Лучшую программу для ЭВМ, созданную при дипломном проектировании» Уфимского государственного авиационного технического университета.
Результаты работы, а также отдельные ее разделы докладывались, обсуждались и получили положительную оценку на конференциях: Республиканский конкурс научных работ (Уфа, 2000 (доклад отмечен дипломом), 2002 (работа отмечена грамотой дипломата конкурса научных работ)); Двенадцатая Байкальская международная конференция «Методы оптимизации и их приложения» (Иркутск, 2001); Международная конференция «Компьютерные науки и информационные технологии» CSIT (Уфа, 2001, 2002, 2005); Всероссийская научно-практическая конференция ''Ресурсосберегающие технологии: математическое обеспечение оптимизационных задач в системах автоматизированного проектирования" ОПТИМ-2001 (С.-Петербург, 2001); Всероссийская конференция «Дискретный анализ и исследование операций» (Новосибирск, 2002, 2004); Всероссийская научно-техническая конференция с международным участием «Мехатроника, Автоматизация, Управление» (Уфа, 2005); семинары кафедры вычислительной математики и кибернетики Уфимского государственного авиационного технического университета.
По теме диссертации опубликовано 17 работ. Правовая сторона автоматизированного комплекса защищена «Свидетельством об официальной регистрации программ для ЭВМ» № 2002610945,
Выражаю глубокую благодарность к.ф.-м.н., доценту Мухачсвой-Филипповой Анне Сергеевне, д.т.н., профессору Мухачевой Элите Александровне за их ведущую роль при подготовке совместных публикаций, советы и помощь при проведении экспериментов и редактировании текста диссертации.
Структура и объем работы
Диссертация состоит из введения, 4-х глав, выводов, списка литературы, и приложений, включающих табличные результаты численных экспериментов, блок-схему генетического алгоритма. Работа изложена на 115 страницах машинописного текста, кроме того, содержит 31 рисунок и 10 таблиц, Библиофафический список включает 107 наименований и занимает 11 страниц.
Автоматизация проектирования и технологической подготовки заготовительного производства
Целью технологической подготовки производства является достижение в процессе изготовления продукции оптимального соотношения между затратами и получаемыми результатами. Увеличение доли мелкосерийного производства требует создания автоматизированных систем технологической подготовки, так как именно при данном характере производства преимущества использования автоматизированных систем проявляются в наибольшей степени [52].
Разработки в области автоматизации технологической подготовки производства (ТПП) создали условия для широкого внедрения автоматизированных систем ТПП и автоматизированного программирования систем ЧПУ. Объектами ТПП являются заготовки, основное и вспомогательное оборудование. Заготовка - это объект, подвергаемый в процессе ТПП JS непосредственному воздействию режущего инструмента. Множество заготовок, специфика их использования в производстве, может дать обоснование выбору технологического процесса. Речь идет о единичном, мелко-серийном, а также массовом производстве. Вид материала - это еще одна из характеристик объекта ТПП, так как сведения о материале детали являются одним из критериев проектирования технологического процесса наряду с требованиями к
УК инструменту и станкам.
Процесс производства деталей принято делить на заготовительный этап и этап механической обработки. Трудоемкости обоих этапов связаны между собой, т.е. уменьшение ее на одном из этапов может привести к увеличению трудоемкости на другом. Необходимо подчеркнуть, что создание систем автоматизированной технологической подготовки заготовительного w производства актуально и в настоящее время.
Раскройно-заготовительные работы являются одной из начальных стадий ТГШ и закладывают основы рационального функционирования всех последующих производственных звеньев. Именно на этом этапе определяются оптимальные размеры заготовок, находится оптимальный способ их размещения на заданном материале, по сгенерированным планам размещения деталей рассчитываются нормы расхода, как на каждую деталь, так и заказ материала на плановый период в целом. Процесс составления планов размещения деталей является сложным и трудоемким, особенно в условиях единичного и мелкосерийного производства, которые отличаются большой номенклатурой деталей и типоразмеров используемого материала, частой сменяемостью заказов,
Поэтому технолог без использования средств автоматизации не в состоянии качественно спроектировать планы размещения деталей, состоящие из большого количества разногабаритных деталей с минимальными отходами и с учетом технологических ограничений в сжатые сроки.
Под системой автоматизированного проектирования размещения деталей понимается совокупность математических, программных» технических и іч организационных средств, предназначенных для расчета и внедрения % рационального плана размещения деталей. Структура САПР размещения содержит три основные подсистемы:
1. Подсистема препроцессорной обработки исходной информации об объектах и областях размещения; она предназначена для подготовки, хранения и редактирования данных о геометрии объектов для решения конкретной задачи,
2. Подсистема генерирования карт размещения» основной целью которой является формирование рационального размещения геометрических объектов в автоматическом режиме, 3, Подсистема постпроцессорной обработки информации о размещенных геометрических объектах (подсистема разработки технологического процесса размещения). Она формирует управляющие программы для станков с ЧПУ на основе карт размещения и нормативно-справочной информации (НСИ).
Автоматизированное рабочее место технолога планово-заготовителыюго производства включает в себя подсистему препроцессорной обработки информации и подсистему генерирования карт размещения, которое предназначено для решения задач размещения деталей,
В представленной диссертации подробно рассматриваются различные аспекты этих двух подсистем в условиях единичного и мелко-серийного производств.
Проектирование с использованием методов оптимизации на всех этапах разработки технологического процесса позволяет добиться высокого качества проектных решений и эффективности процесса производства в целом.
Кодирование приоритетным списком, перестановкой
Данная схема кодирования удобна для построения визуального отображения карты размещения ни практически непригодна для расадтОБ и размещения прямоугольников, осуществления поиска рационального решения.
В качестве кода размещения используете щзеледовдтальпость номеров прямоугольников, представляющая порядок их размещения; % {\{%\ 2[ж]? ..., т[тг}. Это соответствие устанавливается с помощью некоторого алгоритма. Например, алгоритма прочтения размещения прямоугольников «сверху вниз»3 мелева-направо» (Above Boilom - Left Right, AB-LK).
Разместим пол у бесконечную полосу в прямоугольной системе координат так, как это показано на рис. 5. При этом горизонтальная ось ОХ{ совпадает е 4) нижней горизонтальной стороной полосы, а вертикальная ось ОХ-} проходит через вертикальную сторону ОА этой полосы. 1 рнс5 приведено размещение w\ девгги различных нрямоугшыш&ое. Прммоутояшиш №1 и Н&2 опираются на сторону ОЛ5 которую назовем начальной опорной гранью. При этом прямоугольник №1 короне прямоугольника №2 и его сторона O.At швт&гс?, опорной для следующего прямоугольника № 3. Далее сторона О-Л прямоугольника Ш 2 служит опорной для двух прямоугольников № 4 и jsfeS ш при зтом имеется остаток. Далее заметим, что прямоугольники №3 и №4 оказались расположенными так, что они заканчиваются одновременно и объединение их сторон (1гА-% служит опорной гранью щт размещения следующих прямоугольников Дгб ш ХЙ7 и соответствующего ши. остатка, Продолжая процесс перечисления уложенных прямоугольников "сверху-вниз" по мерс формирования очередной опорной грани "слева - виправо" получим последовательность {I;2; 3; 4; 5; 6;7; К: 9}.
Таким образом имея размещение и перечисляя прямоугольники согласно правилу «сверху-вниз», получаем единственный шифр в виде перестановки я. Сложнее наоборот, т.е. но перестановке ж восстановить размещение. Например, если прямоугольник Шб ш Мй7 сместить вниз до упора с прямоугольником Л5, то следушїций прямоугольник Ш% не разместиться так, как это показано на рис. 5.
Существуют и другие правила укладки прямоугольников, которые задаются отдельно внутри эвристики-де кодера. Данное представление удобно для его использования в генетических алгоритмах, поскольку они как раз и работают с последовательностями (ген), кодирующими размещение деталей (индивидуум).
Murata и др. [95] предложили схему кодирования названную парой последовательностей. Пример размещения, закодированного парой последовательностей, представлен нарис, 6.
Основываясь на этом кодированном решении, относительные местоположения для каждой пары і и j прямоугольников строятся следующим образом: Если і располагается перед j в обеих перестановках, мы должны разместить і левее j. Если і располагается перед j во+ и после j в а-, то мы помещаем і выше j. Например, на рисунке 1, " 1 расположен перед 4 в обеих перестановках, и, следовательно, 1 левее, чем 4 ", "4 располагается перед 2 в т+ и после 2 в а-9 и, следовательно, 4 - выше, чем 2" и так далее. 2.L4. Кодирование блок-структурой
Пусть имеется некоторое прямоугольное размещение деталей, RP. Разобьем его вертикальными линиями на прямоугольные блоки одной и той же ширины W и различной длины. При этом начало первого блока совпадает с началом полосы, а конец - с концом самого короткого прямоугольника входящего в блок. Каждый последующий блок j=2,... начинается, как только заканчивается предыдущий. На рисунке 7(a) приведено безотходное размещение девяти различных прямоугольников в полосу ширины W. Штриховой линией обозначено разбиение размещения на пять различных блоков. Обозначим длину каждого блока j через Xj
Генетический алгоритм с позиций локального поиска экстремума
Локальный поиск (Local Search, LS) - метод усовершенствования, который многократно изменяет текущее решение с целью получения лучшего решения. Локальный поиск стартует с начального допустимого решения х(0) и неоднократно заменяет его лучшим в окрестностях N(x), до тех пор, пока не может быть найдено никакое лучшее решение в N(x), где N(x) - набор решений, полученных от х небольшим преобразованием. Решение х в локальном масштабе оптимально, если никакое лучшее решение х не может быть найдено в N(x). Простой алгоритм локального поиска с начальным решением х(0), окрестностью N(x) и целевой функцией формально описывается следующим образом: Шаг 1. Начальное решение х = х(0). Шаг 2. Поиск соседнего решения в окрестности х. Шаг 3. Если есть выполнимое решение x eN(x) такое, что верно f(x ) f(x), устанавливаем х = х и возвращаемся к Шагу 2. Иначе (то есть, f(x) f(x )верно для всех решений x N(x)), выводим локальное оптимальное решение х и останавливаемся.
Процедуру поиска следующего решения х в Шаге 2 называют поиском окрестностей, и набор всех решений, которые могут быть потенциально просмотрены в этом алгоритме, называется пространством поиска. Выполнение алгоритма зависит от начального решения, выбора окрестности и стратегии движения.
Генетический алгоритм (Genetic Algorithm, GA) [79] основан на эволюционных процессах в природе. GA многократно генерирует новые решения Q, применяя операции скрещивания и/или мутации текущих решений Р. Скрещивание генерирует одно или более новых решений, комбинируя два или более текущих решений, а мутация генерирует новое решение путём минимального отклонения от текущего решения. GA начинает с начального решения Р и заменяет его на P cPljQ, согласно правилам выбора (целевой функции). Генетический алгоритм с позиций локального поиска описывается следующим образом: Ф Шаг 1. Генерация первоначального множества решений Р и назначение х лучшим решением из Р. Шаг 2. Повторение шагов 2.1 и 2.2: получение новых решений Q до тех пор, пока не будет сформирован новый набор решений. 2.1. Выбор двух или более решений, принадлежащих Р, и их скрещивание для генерации одного или более новых решений. 2.2. Выбор решения, принадлежащего Р и его мутация для генерации Ф нового решения. Шаг 3: Если решение xtQ и f(x) f(x ), выберем лучшее решение х е Q и значение х = х. Шаг 4: Выбираем заданное количество решений Р1 из результирующего Р U Q и множество Р=Р\ Шаг 5: Если критерии остановки удовлетворены, выводим лучшее решение р и останавливаемся. Иначе возвращаемся к шагу 2.
На шаге 4 часто используют: случайный выбор, случайный круговой выбор, и элитизм. Вышеописанный метод называют простым генетическим алгоритмом.
Идея генетического алгоритма по аналогии с живой природой состоит в организации эволюционного процесса, целью которого является получение оптимального решения. При этом необходимо идентифицировать законы эволюции так, чтобы быстрее достичь оптимальное или близкое к нему, решение. Основным понятиям и методам конструирования генетических алгоритмов посвящена работа Батищева Д.И. [б]. Генетический алгоритм упаковки работает с цифровыми строками. Базовыми понятиями алгоритма являются ген, хромосома, популяция. Хромосома (запись, фрейм) - это одно из возможных решений, закодированное определённым образом. Хромосомы Ш состоят из более мелких элементов — генов (полей, слотов). Хромосомы преобразовываются за счёт модификации генов (аллелей). Операции производятся не над одной хромосомой, а над целым набором хромосом. Этот набор называется популяцией. Аллелями, то есть значениями генов, как правило, Ф являются значения проектных параметров.
Направленный перебор решений осуществляется с помощью генетических операторов кроссовера, мутации, селекции. Сначала формируется случайным образом исходное поколение, состоящее из к хромосом (объектов).
Выбор начальной популяции не влияет на сходимость процесса в асимптотике. Однако формирование хорошей начальной хромосомы, а вслед за ней начальной популяции сокращает время достижения оптимума.
В используемом генетическом алгоритме на каждом шаге эволюции с помощью оператора селекции выбираются два решения (родители). Оператор скрещивания (кроссовер) строит новое решение, которое добавляется в популяцию, а решение с наихудшей оценкой удаляется из нее. Если оценка меняется мало или по истечении заданного количества итераций, текущее решение подвергается небольшим случайным изменениям, мутации.
Организация раскройно-заготовительного производства
Автоматизированный комплекс построения рационального размещения состоит из интерфейсной части, отвечающей за получение, отображение, сохранение данных задачи и результатов ее расчета и расчетной, осуществляющей нахождение рационального размещения. Архитектура щ автоматизированного комплекса представлена на рис. 24. Функциональные возможности интерфейсной части автоматизированного комплекса; чтение исходных данных задачи с поддержкой различных форматов исходных данных; редактирование и создание новых исходных данных задачи ш w средствами разработанного редактора и автоматического генератора задач; настройка технологических параметров решения задачи, а также переменных, управляющих процессом расчета задачи; получение статистических данных задачи и результатов ее решения с сохранением в специальных файлах; визуальное отображение карт размещения с возможностью сохранения данных. Предоставляются стандартные возможности масштабирования, прокрутки, получения справочной, а также дополнительной информации; многодокументный интерфейс; поддержка различных алгоритмов-декодеров по расчету размещения деталей и настройка их опций; система запуска и остановки расчета рационального размещения; запуск и анализ численного эксперимента.
Функциональные возможности расчетной части: расчет перестановок прямоугольников операторами генетического алгоритма: скрещивание, мутация, селекция; расчет карт раскроя различными алгоритмами-декодерами; решение задач размещения деталей на полосе, открытой области и листах; расчет статистических данных задачи; учет в системе расчета возможности поворота деталей и других технологических параметров; подсистема ограничения поиска решений.
Автоматизированный комплекс состоит из четырех основных элементов: — модуль проверки корректности входных данных служит для отсева некорректных входных данных и для определения возможности решения задачи методом; — модуль подготовки входных данных производит инициализацию структур данных вычислительной части алгоритма; — вычислительный модуль выполняет все необходимые операции для получения решения задачи, в процессе решения модулю интерфейса системы передается информация о проценте выполнения задачи; — модуль подготовки выходных данных производит освобождение памяти от данных вычислительной части алгоритма и формирование результата.
Опции расчетного модуля позволяют задавать и учитывать различные технологические ограничения, предъявляемые ко всей карте раскроя. Технологические ограничения любого типа запрограммированы только в коде алгоритма-деко дера, в интерфейсной части предусмотрен лишь универсальный механизм изменения настроек: — запрет поворота деталей; — припуски на резы и окантовка листов, полосы,
В автоматизированном комплексе предусмотрена возможность автоматического проведения численных экспериментов, что позволяет более полно оценивать работу методов решения задач размещения, избежать ошибок, возникающих при выполнении рутиной работы человеком. Здесь представлены результаты сравнения работы реализованных алгоритмов и их анализ. В качестве основной характеристики решений взят коэффициент раскроя (КРа). В некоторых экспериментах также учитывается отклонение от нижней границы решения.
При проведении вычислительного эксперимента множество возможных задач разбивается на конечное число классов. Каждый класс задач характеризуется интервалом отношения ширины и длины прямоугольников к ширине полосы и количеством различных прямоугольников. Внутри каждого класса задач со случайным разбросом формируются задачи для эксперимента (ширина полосы и размеры прямоугольников).
