НАУЧНЫЙ ВЕСТНИК


НОВОСИБИРСКОГО ГОСУДАРСТВЕННОГО ТЕХНИЧЕСКОГО УНИВЕРСИТЕТА

ISSN (печатн.): 1814-1196          ISSN (онлайн): 2658-3275
English | Русский

Последний выпуск
№3(72) Июль - Сентябрь 2018

Разработка и применение метаэвристических алгорит-мов для решения задач геометрического покрытия

Выпуск № 2 (51) Апрель - Июнь 2013
Авторы:

Забелин Сергей Леонидович,
Фроловский Владимир Дмитриевич
Аннотация
Задача геометрического покрытия относиться к классу NP-трудных задач комбинаторной оптимизации и исследуется в рамках проблемы «раскроя и упаковки». Требуется расположить некоторые геометрические объекты на покрываемой поверхности таким образом, чтобы вся поверхность была покрыта целиком с наименьшей площадью перекрытий и промахов объектов, а также использовать наименьшее количество объектов. В статье предлагаются алгоритмы и программы, которые применяются к решению соответствующих оптимизационных задач в агротехнических системах полива. Реализованы следующие алгоритмы: первый подходящий, вероятностный, экстремальный, генетический, муравьиных колоний и др.
Ключевые слова: метаэвристические алгоритмы, задачи геометрического покрытия, NP-трудные задачи, муравьиный алгоритм, вероятностный алгоритм, экстремальный алгоритм, задачи оптимизации покрытия

Список литературы
[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.
Просмотров: 521