Обработка информации

ОБРАБОТКА ИНФОРМАЦИИ

45-52

1, 2

1 Сибирский государственный университет телекоммуникаций и информатики

2 Новосибирский государственный технический университет

1. 6

2. г. Новосибирск,

1. *****@***ru

2. *****@***cs. *****

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

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

УДК

519.6

Ключевые слова

метаэвристические алгоритмы, задачи геометрического покрытия, NP-трудные задачи, муравьиный алгоритм, вероятностный алгоритм, экстремальный алгоритм, задачи оптимизации покрытия

Список литературы

, Заллгаллер раскрой промышленных материалов. СПб.: Невский диалект. 20с. , , Мартынов и методы расчета раскроя-упаковки геометрических объектов // Уфа. УГАТУ. 19с. Романовский решения экстремальных задач //М.: Наука. 19с. , Яковлев модели и оптимизационные методы геометрического проектирования. Киев: Наукова думка. 19с. , Кузнецов о минимальном покрытии ортогональных многоугольников с запретными участками. Информационные технологии. 2008. №9 (14С. 60-65. Фроловский раскроя материалов на оборудовании с ЧПУ (модели, методы, алгоритмы). ISBN-13: 0163-9. Издательский Дом: LAP LAMBERT Academic Publishing. Saarbrücken, Germany. 20с. 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.

Дата поступления

12.02.2013

Английская часть статьи (переведенная, предварительная или окончательная)

INFORMATION PROCESSING

S. L. Zabelin , V. D. Frolovsky 

Development and application of metaheuristic algorithms for solving the problem of covering

The problem of geometric coverage is a special case of the problem of optimal design and belongs to the class of "cutting and packaging." Required to place certain geometric objects on the substrate in such a way that the entire surface was covered entirely with the smallest area overlaps and misses objects, and use the least amount of objects. Described program helps to solve problems in agricultural irrigation. Implemented the first fit, probabilistic, extreme, genetic, ant algorithms and other.

Keywords:

metaheuristic algorithms, geometric coverage problems, NP-completeness problems, ant algorithms, probabilistic algorithm, extreme algorithm, the optimization problem of the coverage