Разработка и исследование моделей, методов и алгоритмов для синтеза и анализа решений задач геометрического покрытия
Аннотация
Задача геометрического покрытия относится к классу NP -трудных задач комбинаторной оптимизации и исследуется в рамках проблемы «раскроя и упаковки». Требуется расположить различные геометрические объекты на покрываемой поверхности таким образом, чтобы вся поверхность была покрыта с наименьшей площадью перекрытий объектов, а также использовать наименьшее количество объектов. В статье рассматриваются реализации алгоритмов первого подходящего, вероятностного, экстремального, муравьиного и генетического алгоритмов. Данные метаэвристические алгоритмы можно адаптировать для решения задач в различных системах: освещения, агротехнических, охранных, беспроводной связи, воздушного наблюдения. Алгоритмы помогут повысить эффективность систем и уменьшить затраты на их проектирование и реализацию.
Список литературы
1. Стоян Ю.Г., Яковлев С.В. Математические модели и оптимизационные методы геометрического проектирования. Киев. Наукова думка. 1986. 268 с.
2. Канторович Л.В., Заллгаллер В.А. Рациональный раскрой промышленных материалов. СПб. Невский диалект. 2012. -304 с.
3. Романовский И.В. Алгоритмы решения экстремальных задач. М. Наука. 1977. -420 с.
4. Мухачева Э.А., Верхотуров М.А., Мартынов В.В. Модели и методы расчёта раскроя-упаковки геометрических объектов. Уфа. УГАТУ. 1998. 216 с.
5. Мухачева Э.А., Валихметов Ю.И., Телицкий С.В., Хасанова Э.И. Проектирование размещения ортогональных объектов на полигонах с препятствиями. Информационные технологии. 2010. № 10. – С. 16-22.
6. Мухачева А. С. Простые эвристики для решения двумерной задачи максимального покрытия. // Принятие решений в условиях неопределённости. Межвузовский научный сборник. Вып.2. Ч.1. Уфа: УГАТУ. 2005. С.24-32.
7. Телицкий С.В., Филиппова А.С. Комплексный подход к решению задачи покрытия области заготовками неопределённых размеров. Научно-технические ведомости СПбГПУ. Информатика. Телекоммуникации. Управление. 2012. 2(145)/2012. – С. 61-67.
8. Филиппова А.С., Кузнецов В.Ю. Задачи о минимальном покрытии ортогональных многоугольников с запретными участками. Информационные технологии. 2008. №9 (145). 2008. С. 60-65.
9. Курейчик В.М., Гладков Л.А., Курейчик В.В. Генетические алгоритмы. М. ФИЗМАТЛИТ. 2006. -320 с.
10. Фроловский В.Д. Приближённые методы решения NP-трудных задач в системах автоматизации проектирования. Новосибирск. НГТУ. 2006. 100 с.
11. Фроловский В.Д. Оптимизация раскроя материалов на оборудовании с ЧПУ (модели, методы, алгоритмы). Издательский Дом: LAP LAMBERT Academic Publishing. Saarbrücken, Germany. 2011. 124 с.
12. 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.
Рецензия
Для цитирования:
Забелин С.Л., Фроловский В.Д. Разработка и исследование моделей, методов и алгоритмов для синтеза и анализа решений задач геометрического покрытия. Вестник СибГУТИ. 2013;(2):42-53.
Просмотров:
170
Послать статью по эл. почте 