Розроблення і використання генетичних алгоритмів для розв’язання задач САПР розкрою плоских заготовок

Abstract

In the thesis the method of location and spacing of rectanglar shape blanks and the algorithm for solving location and spacing issues of arbitrary shape blanks on an arbitrary plane based on the theory of genetic algorithms have received the further development. Particular attention is paid to the methods of flat parts grouping in a plane and using templates, which helped optimize cutting area and reduce the waste material. This thesis investigates the influence of patterns for optimal solutions, using genetic algorithms and based on theorem templates added stochastic variable mathematical model for determining the number of templates. Structure of the system was developed for genetic search, which provided an important role for working on template decision. Program-Methodical Complex, which are built on the developed framework allows to investigate factors that affect the temporal performance of various types of evolutionary algorithms. В диссертации исследованы особенности решения задач раскроя плоских заготовок. Проанализированы существующие методы оптимизации планов раскроя промышленных материалов. Исследовано также развитие эволюционных алгоритмов, идея работы которых заимствована у живой природы. Проведена классификация программных продуктов в данной области. Исследовав особенности раскроя прямоугольных заготовок, можно выделить два важных аспекта. Первый состоит в формировании критерия оптимальности, а второй – в выборе эффективного метода решения задачи оптимизации по выбранному критерию. Целевыми функциями для проектирования планов раскроя могут служить любые показатели, которые обеспечивают экономию сырья или характеризуют эффективность работы оборудования для раскроя или цеха раскроя прямоугольных заготовок. С целью оптимизации решения задачи раскроя прямоугольных объектов был использован генетический алгоритм. В данном алгоритме использована диплоидная модель описания хромосом решений, в которой содержится не только информация о последовательности заготовок, но и об их ориентации. Соответственно выбранной модели был построен оператор скрещивания, максимально приближенный реальным биологическим процессам. Использование шаблонов в генетическом алгоритме привело к более быстрому нахождению решения задачи прямоугольного раскроя. Задача размещения объектов произвольной формы является значительно более сложной, чем для прямоугольных объектов. В работе эта задача разбивается на две составляющие. Первая – это построение карты раскроя с использованием определенных эвристических подходов. Вторая составляющая – оптимизация последованости размещения с целью получения максимальной плотности расположения заготовок, что обеспечивает минимальные потери. Для улучшения группирования заготовок использованы результаты анализа сегментов их ограничивающих контуров. Заготовки с минимальными потерями площади при стыковке объединяются в группы. Для решения задачи размещения объектов произвольной формы при их группировании предложено использовать шаблоны в алгоритмах генетического типа. Рассмотрены особенности работы с шаблонами. Результаты исследований показали, что использование шаблонов приводит к значительному ускорению получения оптимального результата. С учетом особенностей генетических алгоритмов разработана структура программной системы, где кроме основных генетических операторов большое внимание уделяется работе над шаблонами решений. Разработанный программно-методический комплекс “ГЕН” позволяет максимально компактно оперировать данными, создавать модели генетических алгоритмов и т.д. В дисертації на основі теорії генетичних алгоритмів отримав подальший розвиток метод розкрою прямокутних об’єктів і алгоритм розв’язання задач розкрою і розміщення заготовок довільної форми в площині довільної форми. Особливу увагу приділено методам групування плоских заготовок в площині і використанню шаблонів, що дало змогу оптимізувати площу розкрою і зменшити відходи матеріалу. В роботі досліджено вплив застосування шаблонів на знаходження оптимального рішення за допомогою генетичних алгоритмів, а також, на основі теореми шаблонів, доповнено стохастичною змінною математичну модель визначення кількості шаблонів. Було розроблено структуру системи для генетичного пошуку, в якій важлива роль надається роботі над шаблоном рішень. Програмно-методичний комплекс, створений на основі розробленої структури, дозволяє дослідити чинники, що впливають на часову ефективність різних видів алгоритмів еволюційного типу.