Задача геометрического покрытия
Авторы: Кошлаков Н.В. | |
Опубликовано в выпуске: #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).