Задача геометрического покрытия

Авторы: Кошлаков Н.В.
Опубликовано в выпуске: #1(18)/2018
DOI: 10.18698/2541-8009-2018-1-227
Раздел: Информатика, вычислительная техника и управление | Рубрика: Системный анализ, управление и обработка информации, статистика
Ключевые слова: задача оптимизации геометрического покрытия, NP-трудная задача, метаэвристические алгоритмы
Опубликовано: 20.12.2017

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

Литература

[1] Канторович Л.В., Залгаллер В.А. Рациональный раскрой промышленных материалов. 3-е изд., перераб. и доп. Новосибирск, Наука, 2012, 300 с.

[2] Юдаков П.В. Задача о трехмерной упаковке и методы ее решения. Инженерный вестник. Электрон. журн., 2015, № 2. URL: http://engbul.bmstu.ru/doc/781936.html (дата обращения 15.09.2017).

[3] Фроловский В.Д., Забелин С.Л. Разработка и анализ приближенных методов решения оптимизационных задач геометрического покрытия. Информационные технологии в проектировании и производстве, 2012, № 3. URL: https://elibrary.ru/download/elibrary_16897548_69207742.pdf (дата обращения 16.08.2017).

[4] Чуб И.А. Математическая модель оптимизационной задачи размещения пожароопасных объектов с учетом рельефа области размещения. Математичне та компютерне моделювання, 2013, c. 88–93.

[5] Курейчик В.В., Глущенко А.Е., Орлов А.Н. Гибридный подход для решения задачи трехмерной упаковки. Известия ЮФУ. Технические науки, 2016, № 6 (156), с. 196–204.

[6] Dorigo M. Optimization, Learning and Natural Algorithms, PhD thesis — Politecnico di Milano, Italie, 2012.

[7] Забелин С.Л., Фроловский В.Д., Жеголко К.В. Разработка и исследование генетического алгоритма для автоматизации проектных процедур оптимизации геометрического покрытия. Вестник ТГТУ, 2015, Т. 21. № 2. URL: http://vestnik.tstu.ru/rus/t_21/pdf/21_2_005.pdf (дата обращения 16.08.2017).

[8] Сравнение алгоритма двумерных матриц и муравьиного алгоритма для задачи геометрического покрытия [Электронный ресурс]. URL: http://lab18.ipu.ru/projects/conf2010/1/21.htm (дата обращения 17.08.2017).

[9] Гладков Л.А., Курейчик В.В., Курейчик В.М., Сороколетов П.В. Биоинспирированные методы в оптимизиации. Москва, Физматлит, 2012, 380 с.

[10] Забелин С.Л., Фроловский В.Д. Исследование метаэврестических алгоритмов для задач оптимального геометрического покрытия. Перспективные информационные технологии в научных исследованиях, проектировании и обучении, 2012. URL: http://www.ssau.ru/files/science/conferences/pit2012/pit_12_0_6_v1_36.pdf (дата обращения 23.08.2017).