Забелин Сергей Леонидович,
Фроловский Владимир Дмитриевич
Аннотация
Задача геометрического покрытия относиться к классу NP-трудных задач комбинаторной оптимизации и исследуется в рамках проблемы «раскроя и упаковки». Требуется расположить некоторые геометрические объекты на покрываемой поверхности таким образом, чтобы вся поверхность была покрыта целиком с наименьшей площадью перекрытий и промахов объектов, а также использовать наименьшее количество объектов. В статье предлагаются алгоритмы и программы, которые применяются к решению соответствующих оптимизационных задач в агротехнических системах полива. Реализованы следующие алгоритмы: первый подходящий, вероятностный, экстремальный, генетический, муравьиных колоний и др.
Ключевые слова: метаэвристические алгоритмы, задачи геометрического покрытия, NP-трудные задачи, муравьиный алгоритм, вероятностный алгоритм, экстремальный алгоритм, задачи оптимизации покрытия
Авторы:
Забелин Сергей Леонидович
аспирант Сибирского государственного университета телекоммуникации и информатики. Основное направление научных исследований: оптимальное размещение геометрических объек-тов в задачах «раскроя–упаковки–покрытия». Имеет 10 публикаций. E-mail: zabelinsl@mail.ru
Фроловский Владимир Дмитриевич
доктор технических наук, профессор кафедры автоматизированных систем управления Новосибирского государственного технического университета. Основное направление на-учных исследований: моделирование и автоматизация процессов геометрического проектирования. Имеет бо-лее 100 публикаций, в том числе 2 монографии, 5 учебных пособий. E-mail: frolovsky@asu.cs.nstu.ru
Список литературы
[1] Канторович Л.В. Рациональный раскрой промышленных материалов / Л.В. Канторович, В.А. Заллгаллер. – СПб.: Невский диалект, 2012. – 304 с.
[2] Мухачева Э.А. Модели и методы расчета раскроя-упаковки геометрических объектов / Э.А. Мухачева, М.А. Верхотуров, В.В. Мартынов. – Уфа: УГАТУ, 1998. – 216 с.
[3] Романовский И.В. Алгоритмы решения экстремальных задач / И.В. Романовский. – М.: Наука, 1977. – 420 с.
[4] Стоян Ю.Г. Математические модели и оптимизационные методы геометрического проектирования / Ю.Г. Стоян, С.В. Яковлев. – Киев: Наукова думка, 1986. – 268 с.
[5] Филиппова А.С. Задачи о минимальном покрытии ортогональных многоугольников с запретными участками / А.С. Филиппова, В.Ю. Кузнецов // Информационные технологии. – 2008. – № 9 (145). – С. 60–65.
[6] Фроловский В.Д. Оптимизация раскроя материалов на оборудовании с ЧПУ (модели, методы, алгоритмы) / В.Д. Фроловский. – Saarbrücken, Germany: LAP LAMBERT Academic Publishing, 2011. – 124 с.
[7] Dorigo M. The ant system: Optimization by a colony of cooperating agents / M. Dorigo, V. Maniezzo, A. Colorni // IEEE Transactions on Systems, Man and Cybernetics. – 1996. – № 26. – P. 29–41.
