автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Методы покрытия многосвязных ортогональных многоугольников для задач оптимального размещения сенсоров в области мониторинга

На правах рукописи

КУЗНЕЦОВ Вячеслав Юрьевич

МЕТОДЫ ПОКРЫТИЯ МНОГОСВЯЗНЫХ ОРТОГОНАЛЬНЫХ МНОГОУГОЛЬНИКОВ ДЛЯ ЗАДАЧ ОПТИМАЛЬНОГО РАЗМЕЩЕНИЯ СЕНСОРОВ В ОБЛАСТИ МОНИТОРИНГА

05.13.18 - Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

1 О ДЕК 2009

Уфа-2009

003488052

Работа выполнена в ГОУ ВПО «Уфимский государственный авиационный технический университет» на кафедре вычислительной математики и кибернетики и кафедре компьютерной математики

Научный руководитель

Официальные оппоненты

Заслуж. деят. науки РФ,

д-р техн. наук, проф.

Мухачева Элита Александровна

д-р физ.-мат. наук, проф. Газизов Рафаил Кавыевич, зав. кафедрой высокопроизводительных вычислительных технологий и систем, Уфимский государственный авиационный технический университет

Ведущая организация

канд. техн. наук, доц. Петупип Александр Александрович, проф. кафедры информационных технологий и автоматизации проектирования, Уральский государственный технический университет - Уральский политехнический институт

Башкирский государственный университет

Защита состоится 2009 г. в/&/%Яисов

на заседании диссертационного совета Д-212.288.03

при Уфимском государственном авиационном техническом университете по адресу: 450000, Уфа-центр, ул. К. Маркса 12, УГАТУ

С диссертацией можно ознакомиться в библиотеке университета Автореферат разослан 2009 г.

Ученый секретарь диссертационного совета д-р техн. наук, проф. I Миронов В.В.

Общая характеристика работы

Актуальность проблемы. В качестве многосвязных ортогональных многоугольников будем рассматривать многоугольные области, содержащие односвязные ортогональные многоугольники с запретом на размещение в них центров кругов и называть их кратко многоугольниками с препятствиями (МП). Задачи покрытия МП кругами находят широкое применение при решении прикладных проблем в различных отраслях деятельности человека. В астрономических исследованиях решается задача покрытия кругами плоскости; в химии применяется задача покрытия шарами трехмерной области; замощения дорог моделируются покрытиями плоскостей плитами различной геометрической формы. Как правило, задачи покрытая являются первичными при решении более сложных технических проблем. Примером могут служить работы А. И. Ерзина, Ю. В. Шамардина и В. В. Залюбовского, посвященные построению беспроводной сенсорной сети. В диссертации рассматриваются задачи покрытия ортогональных многоугольников кругами и приведены технические задачи, связанные с процессом размещения заданных объектов в МП.

А. И. Ерзиным рассматривается следующая задача: заданы круги одного или нескольких радиусов; требуется покрыть этими кругами плоскость таким образом, чтобы минимизировать суммарную площадь перекрытия кругов. Аналогичные задачи покрытия рассматривал Стоян Ю.Г. В его постановке минимизируется количество кругов, покрывающих плоскую область сложной формы. Для решения задачи Стоян Ю. Г. использовал аппарат Ф-функций, предложенный им ранее при описании геометрических объектов. Это позволило применить методы математического программирования. Однако Ф-функции порождают большое количество уравнений, поэтому для задач с большим количеством объектов метод мало пригоден. Этим и другими фактами обуславливается, что сопутствующие технические задачи в большинстве случаев решаются вручную. Например, задача размещения газоанализаторов, рассматриваемая в представленной работе, в настоящее время решается на предприятиях вручную, что приводит к большим затратам времени и материальных средств. При проектировании систем виртуальной реальности возникает задача генерации карт вейпоинтов, которая также в настоящее время решается мало эффективными методами, что требует значительных затрат. Приведенные и другие технические проблемы часто сводятся к решению задачи покрытия МП кругами. Поэтому разработка эффективных алгоритмов для решения задач покрытия многоугольников кругами является актуальной проблемой. Важным является создание программной реализации, позволяющей решать производственные задачи за приемлемое время. Разработанные методы и программное обеспечение становятся конкурентоспособными. В этом состоит актуальность данной разработки.

Целью работы является повышение эффективности территориального распределения технических объектов с использованием эвристических методов покрытия плоских областей.

Для ее достижения были поставлены и решены следующие задачи:

1. Формализовать постановку задачи покрытия ортогонального многосвязного многоугольника кругами.

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

3. Реализовать эволюционный метод (1+1)-ЕА для решения задач покрытия ортогонального многосвязного многоугольника кругами.

4. Создать программное обеспечение, реализующее предложенные алгоритмы и применить его для моделирования покрытий.

5. Провести численный эксперимент с анализом эффективности разработанных алгоритмов.

6. Применить разработанные методы при решении некоторых технических задач.

На защиту выносятся:

1. Новая математическая постановка задачи покрытия многоугольников кругами. Задача поставлена впервые.

2. Новые эвристические методы покрытия многоугольников кругами: блочная и гексагональная эвристики;

3. Реализация эволюционной метаэвристики (1+1)-ЕА с модификацией мутации.

4. Новый алгоритм расчета нижней границы для оценки значения целевой функции в поставленных задачах.

5. Комплекс алгоритмов и программ, реализующий предложенные методы решения задач покрытия.

6. Результаты численного эксперимента на основе созданного математического и программного обеспечения.

Научная новизна работы. Новыми в работе являются:

1. Математическая постановка задачи поиска оптимального покрытия кругами многосвязных ортогональных многоугольников. Она позволяет моделировать процессы территориального распределения объектов в областях с препятствиями.

2. Методы последовательного конструирования покрытия: блочный и гексагональный. Блочный метод основан на блочной технологии, ранее предложенной для решения задач упаковки. Она позволяет находить допустимые покрытия, близкие к оптимальным. Гексагональный алгоритм основан на использовании гексагональной решетки. Он в большинстве случаев превосходит по эффективности блочный алгоритм и может использоваться в качестве декодера в многопроходных эвристиках с целью улучшения значения целевой функции.

3. Реализация эволюционного алгоритма (1+1)-ЕА для локального поиска оптимума в окрестностях допустимых покрытий. На ряду со случайной мутацией, применяемой в метаэвристиках, предложен новый оператор, направленный на улучшение значения целевой функции и связанный с результатом его работы новый способ кодирования особей. Это улучшило

экономические показатели работы алгоритма и, следовательно, повысило его эффективность.

4. Нижняя граница значения целевой функции и ее интеграция в общий алгоритм (1+1)-ЕА. Она лучше традиционной материальной границы оценивает качество решения на каждой итерации и, тем самым, сокращает их количество; а также позволяет проводить сравнение эффективности различных алгоритмов.

Практическая значимость работы: предложенные в диссертационной работе методы ориентированы на достаточно широкий класс прикладных задач, связанных с покрытием многоугольных областей равными кругами. Результаты диссертации могут быть рекомендованы к решению различных технических задач, например, задачи размещения газоанализаторов, задачи размещения ламп в помещениях и т.д. Разработанный комплекс внедрен па ряде предприятий, в том числе на ООО «Дип Гейме» и ООО «Агро-Весна», а также в учебном процессе, в том числе на общенаучном факультете Уфимского государственного авиационного технического университета.

Апробация работы

Основные научные и практические результаты диссертационной работы докладывались и обсуждались на следующих конференциях и семинарах: Зимней школе для аспирантов и молодых ученых (Уфа, УГАТУ, 2006, 2008); 3-ей Всероссийской конференции «Проблемы оптимизации и экономические приложения» (Омск, 2006); 13-й Всероссийской конференции "Математическое программирование и приложения" (Екатеринбург, 2007); научных семинарах кафедры вычислительной математики и кибернетики и кафедры компьютерной математики Уфимского государственного авиационного технического университета.

По теме диссертации опубликовано 7 работ, в том числе 2 статьи в рецензируемых журналах из списка ВАК. Правовая сторона программного продукта защищена «Свидетельством об официальной регистрации программ для ЭВМ» №2008615665.

Структура и объем работы

Диссертация состоит из введения, четырех глав и заключения. Объем работы составляет 156 страниц машинописного текста, включая 60 рисунков, 23 таблицы, и библиографию, содержащую 92 названия.

Выражаю глубокую благодарность научному консультанту, д.т.н. Филипповой Анне Сергеевне за существенную помощь при подготовке диссертации и регулярные консультации по ее содержанию.

СОДЕРЖАНИЕ ДИССЕРТАЦИИ

Во введении к диссертации обоснована актуальность работы; сформулирована цель и задачи исследования; приведены результаты, выносимые на защиту; отмечена их практическая значимость и научная новизна. Приведены сведения об апробации работы и публикациях.

В первой главе проведен аналитический обзор моделей и постановок различных задач покрытия и упаковок; приведена классификация задач

покрытия и упаковки, рассмотрены некоторые технические задачи, сводимые к покрытию областей, а также ставятся цели и задачи исследования. Приведены задачи покрытия множеств, графов, задачи замощения и ряд геометрических задач.

Задачами замощения занимались J. Kari, W. J. Efstathiou, H. Wang, R. Berger и другие. Показано, что в общем случае задачи замощения алгоритмически неразрешимы. Аналитически находят решения для различных частных случаев. Например, установлено существование 14 классов замощений выпуклыми пятиугольниками. Некоторые частные задачи являются алгоритмически разрешимыми, но NP-трудными. Например, задача покрытия Ванга, задачи домино.

Исследуя задачу максимального прямоугольного покрытия, Е. Зак показал взаимосвязь задач покрытия и упаковки и применил методы решения задач упаковки для нахождения покрытий. А. С. Филиппова предложила новые эвристики для решения этих задач.

Y. Cheng, S. S. Iyegnar, R. L. Kashyap рассмотрели задачу покрытия ортогонального многоугольника минимальным количеством прямоугольников. Эта задача находит применение в сжатии изображений, в проектировании микросхем и т.д. Установлено, что задача NP-трудна. Для частного случая задачи, когда ортогональный многоугольник является выпуклым, найден точный полиномиальный алгоритм.

T. Calamoneri, M. Lauria и др. рассмотрели задачу энергоэффективного покрытия в беспроводных сенсорных сетях. Ими показано, что задача NP-трудна и предложен эвристический алгоритм для ее решения. Алгоритм решает задачу в два этапа: выбирается некоторое покрытие области кругами; по выбранному покрытию определяются маршруты передачи информации. В настоящей диссертации рассматривается задача покрытия кругами ортогональных многоугольников с препятствиями. Алгоритмы ее решения можно применять на первом этапе при решении задачи энергоэффективного покрытия. Это позволяет увеличить эффективность эвристик построения беспроводных сетей.

Во второй главе рассматриваются математическая постановка задачи покрытия МП кругами и методы ее решения.

Математическая постановка задачи покрытия МП кругами. Заданы многосвязный ортогональный многоугольник Р и вещественное число г. Требуется покрыть Р кругами радиуса г так, чтобы их количество N достигло минимума.

Задача покрытия многоугольника легко сводится к более простой проблеме покрытия прямоугольной области с препятствиями (ПП). Для этого выделим четыре крайние в многоугольнике грани, см. рис. 1 а. Граница многоугольника обозначена сплошной линией, крайние грани - жирными линиями. Через крайние грани проведем стороны описанного вокруг МП прямоугольника, они обозначены пунктиром. Исходный многоугольник обозначим Р, ограниченную прямоугольником область - А. Дополнение А\Р будем трактовать как множество фиктивных препятствий. Далее будем

работать с прямоугольной областью с препятствиями1. Заданные и фиктивные препятствия на рисунке заштрихованы.

На плоскости введем систему координат (ОХ, ОУ) таким образом, чтобы оси координат совпадали с нижней и левой сторонами покрываемой прямоугольной области А. Исходная информация задачи может быть представлена следующим набором данных: где Ж и I - ширина и

длина покрываемого прямоугольника А; 2 - препятствия, заданные множеством прямоугольников 2 Ът}. Стороны прямоугольников из

2 параллельны осям координат; Z¡ = [г',, г[„ г',, - прямоугольник,

моделирующий препятствие, где (¿х; г'г) - координаты нижне-левого угла прямоугольника 7.и (г); г'г) - длина и ширина прямоугольника 2,. Многоугольник А\2 требуется покрыть минимальным количеством N равных кругов радиуса г.

Решения задачи могут быть представлены в виде набора данных Я = (И,Х,\), где N - количество покрывающих кругов в решении; X = {х/, х2, ..., Хц}, У = {у,, у2, ..., ун} - векторы координат центров кругов.

Решение Я является допустимым покрытием, если выполняются следующие условия:

1° Круги находятся внутри прямоугольника А:

х} > 0; у] > 0; < Ь; у} < IV; V/ = \..., N ■ 2° Центры кругов не лежат внутри препятствий:

Выполняется хотя бы одно из неравенств: (х) - х',)^ - г'х (У) ~ - 2'у ' 21) -0 Для всех •-- ти] = 1,..., N.

г> 0 или

области А \2, то

3° Покрыта вся область А12;

Если (рх;ру) - произвольная точка на

Допустимое решение Я является оптимальным, если число N кругов покрытия минимальное.

Пример покрытия приведен на рис. 1 б. Препятствия на рисунке изображены темным цветом.

7/'//:

а б

Рисунок 1 - Покрытие многоугольника с препятствиями: а - сведение задачи покрытия МП к задаче покрытия ПП с добавленными фиктивными препятствиями; б - покрытие МП кругами

1 Будем именовать далее область А многоугольником, т.к. она является его частным случаем.

Рассмотрены эвристические подходы к решению задачи покрытия МП кругами. Блочная эвристика использует для решения задачи адаптацию блочной технологии, которая была предложена Э. А. Мухачевой и развита А. С. Филипповой для приближенного решения задач упаковки.

Блочная эвристика покрытия (Block Cover, ВС). Допустимое решение задачи покрытия ПП кругами может быть получено в результате сведения к задаче покрытия квадратами. С этой целью круги заменяются вписанными в них квадратами. Блочная эвристика покрытия представляет модификацию блочной упаковки. Ее суть основана на том, что в задачах упаковки детали не пересекаются и в итоговой упаковке могут оставаться пустоты; в задачах покрытия детали могут пересекаться и пустот в итоговом решении нет.

Пусть имеется схема частичного покрытия, содержащая препятствия и уже размещенные квадраты. Через вертикальные стороны фигур проводятся прямые. Таким образом, область разбивается на вертикальные блоки. Пример блок-структуры размещения объектов на прямоугольной области ширины

Блок-структура (BS')-это последовательность {Bv}, v = 1, ..., и, блоков. Блок Bv -

последовательность элементов, заданная

списком

bj - j'-ый элемент блока, L, - длина блока. В текущем блоке могут размещаться элементы2 трех типов: препятствия (Z), покрытые участки (D) и пустые участки (F). При этом j-й элемент задается парой ('!),№ 1), где 7} - тип элемента, Wj - ширина у'-го элемента. Блок-структура используется для поиска пустых участков, чтобы на их место вставить очередной квадрат. Пусть пустой участок

1 находится в v-ом блоке в позиции j, тогда его координаты вычисляются по

v-l J-1

формулам = ^lk,y, , где lk - длина к-то блока, wk - ширина к-го

к. 1 i=J

элемента в v-м блоке (рис. 2).

При решении задач упаковки в область блок-структура формируется последовательно слева направо. До начала решения задачи блок-структура пуста. По мере упаковки прямоугольных элементов создаются блоки. Для

2 Далее будем понимать «элемент» как полностью расположенный в блоке объект, так и его фрагмент, принадлежащий блоку.

W~245 и длины ¿=451 приведен на рис. 2.

позиция ннясяв-левого угла очередного размещаемого квадрата

Рисунок 2 - Блок-структура покрытия

решения задачи покрытия МП алгоритм построения блок-структур нужно модифицировать, поскольку запреты фиксированы на многоугольнике и допускается перекрытие элементов. Модифицированная блок-структура удовлетворяет следующим дополнительным требованиям:

• блок-структура - последовательность блоков, в которых могут храниться элементы трех типов: I- запретные участки, ¡?- свободные участки, и - покрывающие объекты. В задачах упаковки блоки могут содержать: детали или их фрагменты и свободные участки;

• размеры блок-структуры покрытия не изменяются в процессе размещения элементов и совпадают с размерами прямоугольной области А. В задачах упаковки в процессе размещения элементов длина блок-структуры увеличивается;

• блок-структура покрытия содержит по крайней мере один блок и один элемент в блоке, а именно изначально блок-структура содержит только элемент типа Р. В задачах упаковки блок-структура изначально не содержит элементов и ее длина равна 0;

• если в блоке покрытия последовательно размещены 2 однотипных элемента, то они с целью сокращения временных затрат на вычисление координат объединяются в один общий элемент. Это возможно, так как блок-структура не используется далее для восстановления покрытия. В задачах упаковки объединять элементы нельзя;

• перекрытие двух элементов в блоке покрытия определяется по следующему правилу: свободные участки замещаются любыми элементами; запретные участки не замещаются никакими элементами.

При размещении очередного квадрата может возникнуть ситуация, когда его центр попадает внутрь препятствия. Следовательно центр круга в задаче покрытия кругами МП также попадет внутрь препятствия. В этом случае квадрат нужно передвинуть таким образом, чтобы его центр попал на границу запретного участка. На рис. 3 изображена такая ситуация. Поскольку покрытие осуществляется слева направо и снизу вверх, то сдвигать квадрат нужно влево или вниз, в противном случае в блок-структуре останутся непокрытые области. На рис. 3 цифрами 1-5 показаны возможные перемещения квадрата. Перемещение центра квадрата осуществляется по любой из допустимых траекторий, но целесообразно осуществлять сдвиг на возможно меньшее расстояние. В таком случае положение центра будет ближе к расчетному, что снижает плотность покрытия и может привести к сокращению количества покрывающих кругов. Поэтому в примере, приведенном на рисунке, квадрат будет передвинут по траектории 3. По окончании процесса покрытия, квадраты заменяются кругами.

Цвшпр квадрата

О к/или Р

Гс-знааб запрета

Рисунок 3 - Иллюстрация обхода запретного участка

Однако, даже для случая плоскости без препятствий такое покрытие не является оптимальпым. В качестве другого подхода используем методологию замощения правильными шестиугольниками. Известно, что оптимальным покрытием плоскости (с наименьшей плотностью покрытия) является гексагональное покрытие кругами, центры которых размещены в узлах гексагональной решетки3. А именно, центры кругов лежат в узлах решетки, составленной из равносторонних треугольников, со стороной равной г-В, где г - радиус круга (рис. 4). При таком расположении кругов достигается

наименьшая плотность покрытия К= «1.22.

Гексагональная эвристика покрытия {Hexagonal Cover, HQ.

Эвристика НС для покрытия МП состоит в выполнении трех этапов:

• выполняется гескагональное покрытие области А в предположении, что нет препятствий.

• препятствия восстанавливаются; круги с центрами внутри них объявляются запретными и удаляются.

• выполняется поиск и покрытие пустых участков, возникших после удаления запретных кругов.

Трудоемкий процесс поиска пустых участков заменим поиском их границ (рис. 5). Граница Г пустых участков состоит из дуг окружностей и отрезков прямых, образованных кругами, границами препятствий и области А: Г = {у,, ..., у ¡...,у J, где у i = a¡ или у; = l„ a¡ = {х,у,а,0) - дуга окружности с центром в точке (х, у), начинающаяся с полярного угла а и заканчивающаяся углом /?, дуга от а ориентирована против часовой стрелки (рис. 6); /, = (x„y¡,x2,y1) - отрезок прямой, начинающийся в точке (x¡, у;) и заканчивающийся в точке (х2, y¡).

Предположим, что алгоритмы поиска и покрытия Г известны, тогда для покрытия пустых участков воспользуемся следующей процедурой:

Шаг 1. Определить Г.

Шаг 2. Если {Г} = 0, то конец процедуры.

Шаг 3. Покрыть Г.

Шаг 4. Перейти к шагу 1.

Для поиска Г нужно определить непокрытые дуги окружностей и непокрытые отрезки препятствий и области А. Рассмотрим разработанный алгоритм поиска непокрытых дуг окружности; поиск непокрытых отрезков аналогичен поиску дуг. Дуга a¡ является покрытой, если выполняется хотя бы одно из следующих условий: а, лежит вне области A; a¡ лежит внутри области Z; a¡ лежит внутри другого размещенного круга.

Алгоритм поиска непокрытых дуг окружности:

Шаг 1. Поиск покрытых дуг.

Шаг 1.1. Поиск покрытых дуг, образованных пересечением круга с границей А.

3 Л.Ф. Тот Расположения на плоскости, на сфере и в пространстве. М.: Государственное издательство физико-математической литературы, 1958.

Шаг 1.2. Поиск покрытых дуг, образованных пересечением круга с границей Z.

Шаг 1.3. Поиск покрытых дуг, образованных пересечением круга с другими кругами. Шаг 2. Объединение пересекающихся покрытых дуг. Шаг 3. Находим С\СА, где С - окружность, С.А - множество покрытых дуг окружности.

Препятствие

Пустой участок

Рисунок 4 - Гексагональная решетка

Рисунок 5 - Пустой участок и его граница

Непокрытые дуги

Рисунок 6 - дуга окружности

Покрытые дуеи

Рисунок 7 - Покрытые и непокрытые дуги

После выполнения шага 2 алгоритма покрытые и непокрытые дуги будут чередоваться и можно выбрать все непокрытые дуги (рис. 7). Алгоритм покрытия Г состоит в выполнении шагов: Шаг 1. Если 7 = {0}, то перейти к (11). Шаг 2. Выбор дуги у, = (х,у,а,р) из /"наибольшей длины.

Шаг 3. Если р - а > —, то/? = а + —, т. е, покрывается дуга с углом —.

3 3 3

Шаг 4. Вычислить х, = х + г-сов ^+ а ; у, =у+г-$.т-+а.

1 2 2

В-а

Шаг 5. Вычислить А = г ■ сад —-.

2

Шаг 6. Вычислить л2 = х + 2И-^—~; уг =ул-гЬ——

;* г

Шаг 7. Если (л^; у2) лежит внутри Z, то передвинуть (хь у2) на границу 2 вдоль отрезка (х^ух,хг,у^.

Шаг 8. Разместить круг радиуса г таким образом, чтобы его центр совпал с (х2; у 2) ■

Шаг 9. Пересчитать Г. Шаг 10. Перейти к (1).

(Kl,yl)

Шаг 11. Конец алгоритма. Все пустые участки покрыты.

На рис. 8 приведены пояснения к шагам (2) - (6) алгоритма.

На базе эвристики НС построена однопроходная псевдогексагональная эвристика (Pseudo Hexagonal Cover, РНС) последовательного покрытия МП. На области размещаются один или несколько кругов (координаты центров кругов являются входными данными для эвристики). Проводится процесс поиска и покрытия пустых участков, аналогичный покрытию пустых участков в эвристике НС. РНС используется в модификации эволюционного алгоритма (1+1)-ЕА в качестве декодера.

Методология замощения используется и при других формах решеток. В данной работе она модифицирована также для покрытия МП кругами, размещенными в вершинах квадратной решетки. На рис. 9 изображены гексагональное (НС) и квадратное (Square Cover, SC) покрытия. Предложенные алгоритмы являются однопроходными. Следующий этап повышения эффективности покрытия возможен при использовании многопроходных метаэвристик.

Здесь предложена реализация простого эволюционного алгоритма с декодером РНС со случайной и целенаправленной мутацией.

ЯШ

, ...............'. н

(х2;у2)

Рисунок 8 - Покрытие дуги кругом с центром в (х2; уг)

iV=75 N=8 0

а б

Рисунок 9 - Примеры покрытий, созданные эвристиками НС (а) и SC (б)

Эволюционная метаэвристика. Эволюционные алгоритмы (Evolution Algorithm, ЕА) включают в себя группу метаэвристик, предназначенных для поиска и отбора лучших решений. В основе ЕА находятся элементарные понятия эволюции: наследственность, мутация, селекция. Идея ЕА состоит в построении множества решений (популяции) и получения путем случайных действий новых решений взамен плохо пригодных старых. Ключевыми моментами ЕА являются механизмы отбора особей с хорошей пригодностью (в качестве оценки пригодности можно использовать, например, рекордное значение целевой функции). В общей схеме ЕА популяция размерности с определяется как вектор //"fi,, s2, ..., sj, компоненты s,-, i = 1, ..., ç, которого

принято трактовать как особи. Начальная популяция строится некоторым алгоритмом 1пИ. К преобразованию популяции на каждой итерации применяются операторы Тс - селекции, Тр - репродукции и Т. - выживания, предназначенные соответственно - для выбора родительских особей, построения новых особей и отбора их в новую популяцию. Кроме того, используется оператор Ти - мутации, который выводит особи из текущей окрестности. Хранение информации о нескольких допустимых решениях на каждой итерации создает эффект параллельных вычислений и казалось бы, повышает шансы нахождения оптимума. Однако и алгоритмы с одной пробной точкой (одна особь в популяции) часто являются эффективными. Это относится и к скорости решения и к получению качественных результатов. В диссертации используется реализация эволюционного одноточечного алгоритма (1+1)-ЕА для задач покрытия МП кругами. Оператор мутации Тм выполняется на каждой итерации. Он осуществляет построение новой особи. Оператор выживания Тв выбирает текущее решение, если значение рекорда не изменилось и решение, полученное Тм, если значение рекорда улучшено.

Общая схема (1+1)~ЕА:

Шаг 0. Применить 1пИ для построения начального решения Л®; I := 0.

Шаг 1. Вычислить рекорд.

Шаг 2. Для г := 1 ДО ¿тах ВЫПОЛНИТЬ!

Шаг 2.1.

Шаг 3. Конец алгоритма: лучшее из найденных решений.

П. А. Борисовский и А. В. Еремеев теоретически показали, что в случае монотонности мутации по вероятности, алгоритм (1+1)-ЕА предпочтительнее других эволюционных алгоритмов4. Они отметили, что теоретически доказать монотонность мутации для конкретной задачи весьма трудно, чаще всего преимущество алгоритма подтверждается численными экспериментами.

Реализация эволюционной эвристики покрытия базируется на следующем наблюдении: гексагональная эвристика НС в процессе покрытия пустых участков может создавать скопления кругов. Устранить этот недостаток можно, выполняя следующие шаги:

» найти область пересечения максимального количества кругов (не меньше четырех);

• определить центр найденной области;

• покрытие начинать не с нижне-левого угла (согласно эвристики НС), а с центра найденной области при помощи эвристики РНС.

Для реализации алгоритма (1+1)-ЕА требуется ввести следующие определения и параметры: особь, код особи, процедуру 1пН генерации начальной популяции, оператор мутации, декодер, критерий останова.

Особью назовем допустимое покрытие. Закодируем покрытие множеством кругов, подаваемых на вход эвристики РНС. В качестве процедуры 1пИ построения начальной популяции предлагается использовать

4 О сравнении некоторых эволюционных алгоритмов / П. А. Борисовский, А. В. Еремеев II Автоматика и телемеханика 2004. №3. С.3-9.

НС. Код начальной особи С" = 0. В качестве декодера будем использовать РНС. Определим оператор целенаправленной мутации. Оператор мутации.

Шаг 0. Входная информация оператора мутации: С - код особи i; М - вероятность случайной мутации.

Шаг 1. Из кода особи С при помощи декодера РНС восстановить покрытие. Шаг 2. Найти области Si, ..., Sk пересечения большого (больше 4) числа кругов. Шаг 3. Сгенерировать случайное числорт. Если рт > М, то сгенерировать случайную точку V на области A\Z; С"' = U ; Перейти к 7.

Шаг 4. Найти центры О/.....О* областей Si.....St

Шаг 5. Сгенерировать случайное число w из диапазона 1.....к.

Шаг6. См = С'иО..

Шаг 7. Конец алгоритма. Результат работы код особи С1*1. Шаг (3) оператора мутации приводит к случайному изменению кода особей и нужен для изменения окрестности в процессе расширения области поиска. Модифицированный алгоритм мутации сходен с известной вероятностной модификацией детерминированных эвристик. Его работа состоит в выборе альтернативы из подмножества Я' с Я при многократном запуске декодера. Таким образом, в нашей модификации декодером является РНС. Что касается мутации, то она случайно или целенаправленно изменяет код особи, т.е. допустимого решения. Эвристика заканчивает работу либо при достижении заданного числа итераций, либо при выполнении другого критерия останова. В качестве такового можно принять N - Nmi„ < К, где N - число кругов в решении, Nmin - нижняя граница числа кругов, К - заданное отклонение от нижней границы.

Предлагается использовать следующую границу числа кругов

gap =----—, где 5/ - площадь объединения запретных

2 71

участков, г - радиус кругов, введенный JI. Ф. Тотом показатель -¡= «1.22 -

v27

наименьшая плотность системы равных кругов, покрывающих плоскость, Р -периметр области A\Z. Оценку gap можно рассматривать как сумму двух

W-L-Z

составляющих: gap = В + Cz- Ее основная часть В =-,— К представляет

лг~

нижнюю границу числа кругов, покрывающих область A\Zс учетом К. Остаток ^ Р-12 2л--3

Cz ~---- количество кругов, суммарная площадь которых равна

г 12л-

наименьшей суммарной площади секторов кругов, которые выйдут за пределы области A\Z. Пусть (х; yi) - (х; у2) - вертикальная правая сторона препятствия. Тогда оценка получена из предположения, что координаты кругов, расположенных возле запретов, вычисляются по следующим формулам:

XX,- = х + г/2; уу, = уу,-/ + г43 ;yyi — yi + ——, где (хх,; уу,) - координаты центра

i-ro круга. Для остальных сторон препятствий формулы аналогичны.

С предложенными алгоритмами проведены численные эксперименты. Их результаты представлены в главе 4.

В третьей главе рассматривается техническая задача, которая сводится к решению задачи покрытия многосвязного ортогонального многоугольника.

Задача оптимального размещения сенсоров о области мониторинга. Зона мониторинга сенсора представляется в виде круга радиуса г с центром в месте расположения сенсора. Требуется разместить минимальное количество сенсоров, обеспечивающих мониторинг (покрытие) всей области.

Далее приведены некоторые частные случаи этой задачи.

Задача размещения газоанализаторов. Предположим, что на предприятии, связанном с опасным производством (например, нефтеперерабатывающем), имеются установки, в которых рабочая среда является взрывоопасной (горючие газы). Вокруг оборудования на установке, согласно РД БТ 39-0147171-003 "Требования к установке датчиков стационарных газосигнализаторов в производственных помещениях и на наружных площадках предприятий нефтяной и газовой промышленности", должны размещаться газоанализаторы, которые будут сигнализировать о возможной утечке газа. Зона действия каждого газоанализатора - круг определенного радиуса. Кроме того, влияние газоанализаторов должно охватывать всю территорию завода. Так как каждый газоанализатор имеет определенную стоимость (в зависимости от типа анализируемых газов по состоянию на 2009г цена варьируется от 100000 руб. до 500000 руб.), возникает вопрос о том, как наиболее экономно их расставить, с учетом стандартных требований к пожаро- и взрыво- безопасности.

Производственные установки моделируются прямоугольниками (возможно, пересекающимися), газоанализаторы, включая сферу их влияния, -кругами. Требуется минимизировать количество кругов, полностью покрывающих заданную область.

В главе приведены примеры и некоторых других прикладных проблем, требующих решения задач аналогичных покрытию, например, задача размещения поливальных установок в агрохозяйствах и задача генерации карт вейпоинтов.

В четвертой главе рассматриваются вопросы проектирования программного обеспечения и проведения численного эксперимента на различных классах задач. Предложена архитектура программного обеспечения, которая позволила решать различные по постановкам задачи покрытия. Алгоритмы подключаются к комплексу в виде внешних модулей. Таким образом, создано универсальное ПО, которое может применяться в различных предметных областях без изменений головного модуля. Для оценки качества алгоритмов, а также для сравнения алгоритмов между собой, проведен численный эксперимент на задачах различных классов.

Для каждой задачи вычисляется нижняя граница gap (см. главу 2) и количество кругов, полученных различными алгоритмами. Количество задач из каждого класса не меньше 100. Эволюционный алгоритм выполнял по 1000 итераций на каждую задачу, при этом затрачивалось время около 100 с. По каждому классу вычислялась оценка математического ожидания числа кругов и дисперсии. Оценки дисперсии по всем классам оказались приблизительно

равными. Средняя оценка дисперсии составила 120. Результаты эксперимента приведены на рис. 11-12. На рисунках приведены оценки математического ожидания количества кругов по каждому классу. Доверительные интервалы при уровне надежности 0,95 составили ±3.

Результаты эксперимента позволяют сформулировать следующие выводы:

• блочный алгоритм ведет себя хуже на задачах с малым заполнением области препятствиями, по сравнению с гексагональным алгоритмом. Это связано с тем, что блочный алгоритм решает задачу покрытия квадратами. На сильно заполненных областях гексагональный алгоритм ведет себя хуже блочного из-за тенденции «скопления» кругов;

• при числе компонент связности свободных участков п > 2 следует использовать ВС;

• модификация эволюционного алгоритма (1+1)-ЕА находит решения, отличающиеся от нижней границы не более чем на 10%;

• на всех классах задач 5'С хуже чем ВС и НС;

• чем больше заполнена область А препятствиями, тем ближе результаты БС к НС и ВС._______________________________________________________________________________

120 ----—------—-

'ёНШЙШЙПН

Рис. 11 Сравнение эвристик ВС, БСнНС

ИЛ

йи

Рис. 12 Результаты численного эксперимента для (1+1)-ЕА

На роль декодера в эволюционной метаэвристике (1+1)-ЕА был выбран, по причине большей эффективности, алгоритм РНС. С ним и проведен эксперимент, результаты которого представлены на рис. 14. Вместе с тем, полезно учитывать влияние и других двух алгоритмов (ВС и БС), тем более, что в некоторых случаях результат их работы превосходит НС.

В заключении приведены основные результаты работы и выводы.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ И ВЫВОДЫ

Создана' методика покрытия кругами многосвязных ортогональных многоугольных областей (многоугольников с препятствиями, МП), включающая в себя постановку задач, эвристические методы их решения, разработку программного обеспечения, проведение численных экспериментов и применение для решения задач территориального распределения технических объектов. В ходе решения поставленных задач получены научные и практические результаты:

1. Предложена математическая модель задачи покрытия кругами многосвязных ортогональных многоугольников. Она позволила предложить и применить различные подходы к разработке эвристических методов построения карт покрытия.

2. Разработаны эвристические алгоритмы последовательного конструирования рациональных покрытий кругами МП. Блочный алгоритм использует технологию блок-структур ортогональной упаковки, адаптированную к решению задач покрытия, что упростило обход препятствий. Гексагональный алгоритм основан на использовании гексагонального покрытия, которое является оптимальным для случая покрытия плоскости без препятствий. С учетом препятствий покрытие не является точным, но позволяет получать и оценивать допустимые решения, близкие к оптимальным.

3. Реализация эволюционного алгоритма (1+1)-ЕА строит множество различных покрытий и выбирает среди них наилучшее. При этом поиск ведется целенаправленно: первоначальное решение строится гексагональным алгоритмом; затем оператор мутации, в отличие от стандартных алгоритмов, целенаправленно изменяет структуру покрытия. Предложенная модификация оператора мутации позволяет с небольшими временными затратами находить покрытия близкие к оптимальным.

4. Разработано программное обеспечение, реализующее предложенные алгоритмы. Программное обеспечение позволяет подключать внешние модули с различными алгоритмами покрытия, т. е. его ядро инвариантно к техническим задачам.

5. Поставлены численные эксперименты, направленные на определение эффективности разработанных алгоритмов. Результаты экспериментов показали, что существуют классы задач, на которых гексагональный алгоритм дает решения лучшие, чем блочный, а также существуют классы задач, на которых блочный алгоритм ведет себя лучше гексагонального. Оба алгоритма работают очень быстро - расстановка 200 кругов происходит за время, меньшее 0,1 с. Применение эволюционного алгоритма повышает эффективность расчетов. Время его выполнения не превышает 5 мин. Результаты экспериментов показали, что все предложенные алгоритмы могут применяться при решении технических задач, выбор конкретного алгоритма диктуется требованиями к задаче.

6. Разработанное программное обеспечение применено для решения технических задач расстановки газоанализаторов, размещения поливальных

установок на полях агрохозяйства и генерации карт вейпоинтов. Его применение позволяет сократить количество технических объектов до 10%, а затраты времени с учетом ручной обработки данных - в 8 раз. Результаты диссертационной работы приняты к внедрению в ООО "Агро-Весна" и ООО "Дип Гейме".

СПИСОК ПУБЛИКАЦИЙ В периодических изданиях из списка ВАК

1. Задачи покрытия ортогональных многоугольников с запретными участками / В. Ю. Кузнецов // Вестаик УГАТУ: науч. журн. Уфимск. гос. авиац. техн. ун-та. Сер. Управление, информатика и выч. техника. 2008. Т. 10, №2 (27). С. 177-182.

2. Задачи о минимальном покрытии ортогональных многоугольников с запретными участками / А. С. Филиппова, В. Ю. Кузнецов // Информационные технологии. 2008. № 9 (145). 2008. С. 60-65.

В других изданиях

3. Задача покрытая и ее приложения / В. Ю. Кузнецов // Интеллектуальные системы обработки информации и управления: сб. ст. per. зимн. шк.-сем. аспирантов и молодых ученых. 2006. Т.1. С.129-135.

4. Задача размещения газоанализаторов при условиях покрытия зонами их действия территорий с запрещенными участками / В. Ю. Кузнецов,

A. С. Филиппова // Проблемы оптимизаций и экономические приложения: 3-я Всерос. конф. матер, конф. (Омск, 11-15 июля 2006). 2006. С.182.

5. Задача покрытия двумерной области кругами с запретными участками /

B. Ю. Кузнецов // Математическое программирование и приложения: Информационный бюллетень ассоциации математического программирования. 2007. № li. С.189.

6. Задачи покрытия: модели, алгоритмы и приложения / В. Ю. Кузнецов, М. С. Егорова // Принятие решений в условиях неопределенности: сб. науч. тр. 2008. С. 138-143.

7. Два алгоритма решения задачи о минимальном покрытии прямоугольной области с запретными участками / В.Ю.Кузнецов // Актуальные проблемы в науке и технике : сб. ст. третьей всероссийской зимн. шк.-сем. аспирантов и молодых ученых, 20-23 февраля 2008. 2008. Т.2.

C.227-235.

8. Свид. об офиц. per. программы для ЭВМ №2008615665. Покрытие кругами области с запретами / А. С. Филиппова, В. Ю. Кузнецов. М.: Роспатент, 2008.

Диссертант В.Ю.Кузнецов

Кузнецов Вячеслав Юрьевич

МЕТОДЫ ПОКРЫТИЯ МНОГОСВЯЗНЫХ ОРТОГОНАЛЬНЫХ МНОГОУГОЛЬНИКОВ ДЛЯ ЗАДАЧ ОПТИМАЛЬНОГО РАЗМЕЩЕНИЯ СЕНСОРОВ В ОБЛАСТИ МОНИТОРИНГА

Специальность 05.13.18 -Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Подписано в печать 18.11.2009. Формат 60x84 1/16. Бумага офсетная, Печать плоская. Гарнитура Тайме. Усл. печ. л. 1,0. Усл.кр.-отт. 1,0. Уч.-изд. л. 0,9. Тираж 100 экз. Заказ № 572.

ГОУ ВПО Уфимский государственный авиационный технический университет Центр оперативной полиграфии 450000, Уфа-центр, ул. К. Маркса, 12

Использованные обозначения.

Введение.

1.Модели и методы покрытий.

1.1. Постановки задач покрытия.

1.2. Упаковки и их связь с покрытиями.

Выводы по главе 1.

2.Методы конструирования покрытий кругами многосвязных ортогональных многоугольников.

2.1. Математическая модель задачи покрытия кругами многосвязных ортогональных многоугольников.

2.2. Блочная эвристика (Block Cover, ВС) покрытия кругами многосвязного ортогонального многоугольника.

2.3. Гексагональная эвристика (Hexagonal Cover, НС) покрытия кругами многосвязного ортогонального многоугольника.

2.4. Эволюционная эвристика (1+1)-ЕА.

Выводы по главе 2.

3.Задача оптимального размещения сенсоров в области мониторинга и ее технические приложения.

3.1. Задача размещения газоанализаторов на территории нефтеперерабатывающего завода.

3.2. Задача генерации карт вейпоинтов.

3.3. Другие задачи территориального распределения объектов.

Выводы по главе 3.

4. Проблемно-ориентированный комплекс программ и проведение численного эксперимента.

4.1. Пректирование комплекса программ.

4.2. Численный эксперимент с анализом его результатов.

Выводы по главе 4.

Основные результаты работы и выводы.

Актуальность проблемы. В качестве многосвязных ортогональных многоугольников будем рассматривать многоугольные области (территориальные участки), содержащие односвязные ортогональные многоугольники (здания, технические сооружения, сложные ландшафты и т.д.) с запретом на размещение в них центров кругов (технических объектов) и называть их кратко многоугольниками с препятствиями (МП). Задачи покрытия МП кругами находят широкое применение при решении прикладных проблем в различных отраслях деятельности человека. В астрономических исследованиях решается задача покрытия кругами плоскости; в химии применяется задача покрытия шарами трехмерной области; замощения дорог моделируются покрытиями плоскостей плитами различной геометрической формы [38,39,43,44]. Как правило, задачи покрытия являются первичными при решении более сложных технических проблем. Примером могут служить работы А. И. Ерзина, Ю. В. Шамардина и В. В. Залюбовского, посвященные построению беспроводной сенсорной сети.

В работе А. И. Ерзиным рассматривается следующая задача: заданы круги одного или нескольких радиусов; требуется покрыть этими кругами плоскость таким образом, чтобы минимизировать суммарную площадь перекрытия кругов. Аналогичные задачи покрытия рассматривал Стоян Ю.Г в работах [28-34]. В его постановке минимизируется количество кругов, покрывающих плоскую область сложной формы. Для решения задачи Стоян Ю. Г. использовал аппарат Ф-функций, предложенный им ранее при описании геометрических объектов. Это позволило применить методы математического программирования. Однако Ф-функции порождают большое количество уравнений, поэтому для задач с большим количеством объектов метод мало пригоден. Этим и другими фактами обуславливается, что сопутствующие технические задачи в большинстве случаев решаются вручную. Например, задача размещения газоанализаторов [11] в настоящее время решается на предприятиях вручную, что приводит к большим затратам времени и материальных средств. При проектировании систем виртуальной реальности возникает задача генерации карт вейпоинтов [12], которая также в настоящее время решается мало эффективными методами, что требует значительных затрат. Приведенные и другие технические проблемы часто сводятся к решению задачи покрытия МП кругами. Поэтому разработка эффективных алгоритмов для решения задач покрытия многоугольников кругами является актуальной проблемой. В диссертации рассматриваются задачи покрытия ортогональных многоугольников кругами и приведены технические задачи, связанные с процессом территориального распределения заданных объектов в МП. Важным является создание программной реализации, позволяющей решать производственные задачи за приемлемое время. Разработанные методы и программное обеспечение становятся конкурентноспособными. В этом также состоит актуальность данной разработки.

Целыо работы является повышение эффективности территориального распределения технических объектов с использованием эвристических методов покрытия плоских многоугольных областей.

Для ее достижения были поставлены и решены следующие задачи:

1. Формализовать постановку задачи покрытия ортогонального многосвязного многоугольника кругами.

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

3. Реализовать эволюционный метод (1+1)-ЕА для решения задач покрытия ортогонального многосвязного многоугольника кругами.

4. Создать программное обеспечение, реализующее предложенные алгоритмы и применить его для моделирования покрытий.

5. Провести численный эксперимент с анализом эффективности разработанных алгоритмов.

6. Применить разработанные методы при решении некоторых технических задач.

На защиту выносятся:

1. Новая математическая постановка задачи покрытия многоугольников кругами.

2. Новые эвристические методы покрытия многоугольников кругами: блочная и гексагональная эвристики; эволюционная метаэвристика (1+1)-ЕА.

3. Новый алгоритм расчета нижней границы для оценки значения целевой функции в поставленных задачах.

4. Комплекс алгоритмов и программ, реализующий предложенные методы решения задач покрытия.

5. Результаты численного эксперимента на основе созданного математического и программного обеспечения.

Научная новизна работы. Новыми в работе являются:

1. Математическая постановка задачи поиска оптимального покрытия кругами многосвязных ортогональных многоугольников. Она позволяет моделировать процессы территориального распределения объектов в областях с препятствиями.

2. Методы последовательного конструирования покрытия: блочный и гексагональный. Блочный метод основан на блочной технологии, ранее предложенной для решения задач упаковки. Она позволяет находить допустимые покрытия, близкие к оптимальным. Гексагональный алгоритм основан на использовании гексагональной решетки. Он в большинстве случаев превосходит по эффективности блочный алгоритм и может использоваться в качестве декодера в многопроходных эвристиках с целью улучшения значения целевой функции.

3. Реализация эволюционного алгоритма (1+1)-ЕА для локального поиска оптимума в окрестностях допустимых покрытий. Наряду со случайной мутацией, применяемой в метаэвристиках, предложен новый оператор, направленный на улучшение значения целевой функции и связанный с результатом его работы новый способ кодирования особей. Это улучшило экономические показатели работы алгоритма и, следовательно, повысило его эффективность.

4. Нижняя граница значения целевой функции и ее интеграция в общий алгоритм (1+1J-EA. Она лучше традиционной материальной границы оценивает качество решения на каждой итерации и, тем самым, сокращает их количество; а также позволяет проводить сравнение эффективности различных алгоритмов.

Практическая значимость работы: предложенные в диссертационной работе методы ориентированы на достаточно широкий класс прикладных задач, связанных с покрытием многоугольных областей равными кругами. Результаты диссертации могут быть рекомендованы к решению различных технических задач, например, задачи размещения газоанализаторов, задачи размещения ламп в помещениях и т.д. Разработанный комплекс внедрен на ряде предприятий, в том числе на ООО «Дип Гейме» и ООО «Агро-Весна», а также в учебном процессе, в том числе на общенаучном факультете Уфимского государственного авиационного технического университета.

Апробация работы

Основные научные и практические результаты диссертационной работы докладывались и обсуждались на следующих конференциях и семинарах: Зимней школе для аспирантов и молодых ученых (Уфа, УГАТУ, 2006, 2008); 3-ей Всероссийской конференции «Проблемы оптимизации и экономические приложения» (Омск, 2006); 13-й Всероссийской конференции "Математическое программирование и приложения" (Екатеринбург, 2007); научных семинарах кафедры вычислительной математики и кибернетики и кафедры компьютерной математики Уфимского государственного авиационного технического университета.

По теме диссертации опубликовано 7 работ, в том числе 2 статьи в рецензируемых журналах из списка ВАК. Правовая сторона программного продукта защищена «Свидетельством об официальной регистрации программ для ЭВМ» №2008615665.

Структура и объем работы

Диссертация состоит из введения, четырех глав и заключения. Объем работы составляет 156 страниц машинописного текста, включая 60 рисунков, 23 таблицы, и библиографию, содержащую 93 названия.

Основные результаты работы и выводы

Создана методика покрытия кругами многосвязных ортогональных многоугольных областей (многоугольников с препятствиями, МП), включающая в себя постановку задач, эвристические методы их решения, разработку программного обеспечения и проведение численных экспериментов. В ходе решения поставленных задач получены научные и практические результаты:

1. Предложена математическая модель задачи покрытия кругами многосвязных ортогональных многоугольников. Она позволила предложить и применить различные подходы к разработке эвристических методов построения карт покрытия.

2. Разработаны эвристические алгоритмы последовательного конструирования рациональных покрытий кругами МП. Блочный алгоритм использует технологию блок-структур ортогональной упаковки, адаптированную к решению задач покрытия, что упростило обход препятствий. Гексагональный алгоритм основан на использовании гексагонального покрытия, которое является оптимальным для случая покрытия плоскости без препятствий. С учетом препятствий покрытие не является точным, но позволяет получать и оценивать допустимые решения, близкие к оптимальным.

3. Реализация эволюционного алгоритма (1+1)-ЕА строит множество различных покрытий и выбирает среди них наилучшее. При этом поиск ведется целенаправленно: первоначальное решение строится гексагональным алгоритмом; затем оператор мутации, в отличие от стандартных алгоритмов, целенаправленно изменяет структуру покрытия. Предложенная модификация оператора мутации позволяет с небольшими временными затратами находить покрытия близкие к оптимальным.

4. Разработано . программное обеспечение, реализующее предложенные алгоритмы. Программное обеспечение позволяет подключать внешние модули с различными алгоритмами покрытия, т. е. его ядро инвариантно к техническим задачам.

5. Поставлены численные эксперименты, направленные на определение эффективности разработанных алгоритмов. Результаты экспериментов показали, что существуют классы задач, на которых гексагональный алгоритм дает решения лучшие, чем блочный, а также существуют классы задач, на которых блочный алгоритм ведет себя лучше гексагонального. Оба алгоритма работают очень быстро - расстановка 200 кругов происходит за время, меньшее 0,1с. Применение эволюционного алгоритма повышает эффективность расчетов. Время его выполнения не превышает 5 мин. Результаты экспериментов показали, что все предложенные алгоритмы могут применяться при решении технических задач, выбор конкретного алгоритма диктуется требованиями к задаче.

6. Разработанное программное обеспечение применено для решения технических задач расстановки газоанализаторов, размещения поливальных установок на полях агрохозяйства и генерации карт вейпоинтов. Его применение позволяет сократить количество технических объектов до 10%, а затраты времени с учетом ручной обработки данных - в 8 раз. Результаты диссертационной работы приняты к внедрению в ООО "Агро-Весна" и ООО "Дип Гейме".

1. Алексеев О. Г. ; Комплексное применение методов дискретной оптимизации. М.: Наука, 1987.

2. Ахо А. Построение и анализ вычислительных алгоритмов. / Ахо. А., Хопкрофт Дж., Ульман Дж. М.: Мир, 1979.

3. Борисовский П. А. О сравнении некоторых эволюционных алгоритмов / Борисовский П. А., Еремеев А. В. // Автоматика и телемеханика, №3. М.: Изд. «Наука», 2004. С.3-9.

4. Гилл Ф. Практическая оптимизация. Пер. с англ. / Гилл Ф., Мюррей У., Райт М., М. Мир, 1985.

5. Гребенник И. В. Учет погрешностей при построении математических моделей оптимизационных комбинаторных задач. / Гребенник И. В., Романова Т. Е. // АСУ и приборы автоматики, Вып. 119. 2002. С.64-69.

6. Гэри М. Вычислительные машины и труднорешаемые задачи. / Гэри М., Джонсон Д., М.: Мир, 1982.

7. Емеличев В. А. Лекции по теории графов. М.: Наука, 1990.

8. Емец О. А. Интервальная математическая модель комбинаторной задачи цветной упаковки прямоугольников. / Емец О. А., Евсеева Л. Г., Романова Н. Г. // Кибернетика и системный анализ, №3. 2001. С.131-138.

9. Кузнецов В. Ю. Задача покрытия и ее приложения //Интеллектуальные системы обработки информации и управления: сб. ст. per.зимн.шк.-сем. Аспирантов и молодых ученых, Т.1, Уфа: УГАТУ. 2006, С.260-267.

10. Кузнецов В. Ю. Задача покрытия двумерной области кругами с запретными участками. // Математическое программирование и приложения: Информационный бюллетень ассоциации математического программирования, №11. Научное издание. Екатеринбург. 2007. С. 189.

11. Кузнецов В. Ю. Задачи покрытия: модели, алгоритмы и приложения. / Кузнецов В. Ю., Егорова М. С. // Принятие решений в условиях неопределенности: сб.науч.тр. Уфа: УГАТУ. 2007. С.82-88.

12. Кузнецов В. Ю. Задачи покрытия ортогональных многоугольников с запретными участками. // Вестник УГАТУ. Серия: «Управление, вычислительная техника и информатика», Т. 10, №2(27). Уфа: УГАТУ. 2008. С.177-182.

13. Ламот А. Программирование трехмерных игр для Windows. Советы профессионала по трехмерной графике и растеризации. Пер. с англ., М.: Изд. дом «Вильяме», 2004.

14. Липовецкий А. И. К оптимизации свободного размещения прямоугольников // Автоматизация проектирования в машиностроении. 1985. С.80-87.

15. Ловас Л. Прикладные задачи теории графов. / Ловас. Л., Пламмер М. М.Мир, 1998.

16. Мухачева А. С. Задачи двухмерной упаковки в контейнеры: новые подходы к разработке методов локального поиска оптимума. / Мухачева А. С., Валеева А. Ф., Картак В. М. М.: МАИ. 2004. С. 193.

17. Мухачева А. С. простые эвристики для решения двумерной задачи максимального покрытия. // Принятие решений в условиях неопределенности. Межвузовский нацчный сборник. Вып.2. 4.1. Уфа: УГАТУ. 2005. С.38-43.

18. Мухачева Э. А. Метод последовательного уточнения оценок: алгоритм и численный эксперимент для задачи одномерного раскроя. / Мухачева Э. А., Мухачева А. С., Белов Г. И. // Информационные технологии. Машиностроение, Т.2. 2000. С.13-18.

19. Мухачева Э. А. • Проектирование прямоугольных упаковок с использованием декодеров блочной структуры. / Мухачева Э. А., Назаров Д. А., Филиппова А. С. // Автоматика и телемеханика, №6. 2006. С. 161 -173.

20. Пападимитроу X. Комбинаторная оптимизация. Алгоритмы и сложность. Пер. с англ. / Пападимитроу X., Стайглиц К. М.: Мир, 1985.

21. Пушкин Д. В. Принцип максимального заполнения и характеристики подрешеток атомов элементов IV-VI периодов. / Пушкин Д. В., Сережкин В. Н. Самара: Самарский Государственный Университет, 2002.

22. Рейнгольд Э. Комбинаторные алгоритмы. / Рейнгольд Э., Нивергельт Ю., Део Н., М. Мир. 1980.

23. Слоэн Н. Дж. А. Упаковка шаров. М.: Наука, 1984. С.72-82.

24. Стоян Ю. Г. Методы и алгоритмы размещения плоских геометрических объектов. Киев: Наук, думка, 1976.

25. Стоян Ю. Г. Решение некоторых многоэкстремальных задач методом сужающихся окрестностей. / Стоян Ю. Г., Соколовский В. 3. Киев: Наук, думка, 1980.

26. Стоян Ю. Г. Математические модели и оптимизационные методы геометрического проектирования. / Стоян Ю. Г., Яковлев С. В. Киев: Наук, думка, 1986.

27. Стоян Ю. Г. Адаптация метода ветвей и границ для решения задачи размещения прямоугольников с учетом минимально и максимально допустимых расстояний. / Стоян Ю. Г., Аристова И. В., Яськов Г. Н. Харьков: НАН Украины. Ин-т пробл. Машиностроения, 1995.

28. Стоян Ю. Г. Комбинаторная оптимизационная задача размещения прямоугольников с учетом погрешностей в исходных данных. / Стоян Ю. Г., Романова Т. Е., Евсеева Л. Г. // Докл. НАН Украины, №7. 1997. С.56-60.

29. Стоян Ю. Г. Оптимизационная задача размещения правильных интервальных многоугольников. / Стоян Ю .Г., Романова Т. Е., Сысоева Ю. А. // Докл. НАН Украины, №9. 1998. С.114-120.

30. Стоян Ю. Г. Выпуклые интервальные многоугольники // Доп. НАН Украины, №5. 2000. С.33-39.

31. Тот JI. Ф. Расположения на плоскости, на сфере и в пространстве. М.: Гос. издат. Физико-математической литературы, 1958.

32. Филиппова А. С. Задачи о минимальном покрытии ортогональных многоугольников с запретными участками. / Филиппова А. С., Кузнецов В. Ю. // Информационные технологии, №9(145). 2008. С.60-65.

33. Akiyama J. Variations of the tiling problem. /Akiyama J., Nakamura G. Oxford University Press. 2008.

34. Allausen C. Tiling Problems. / Allausen C., Durand B. New York: Brooklyn Polytechnik Institute, 1982

35. Berger R. The undecidability of the domino problem // Memoirs Amer. Math. Soc., #66. 1966.

36. Berman P. Approximating rectilinear polygon cover problems / Berman P., DasguptaB. // Algorithmic?. #17(4). 1997. P.331-356.

37. Bronnimann H. almost optimal set covers in finite VC-dimension. / Bronnimann H., Goodrich M. // Discrete comput. Geom., #14. 1995. P.263-279.

38. Cheng Y. A new method for image compression using irreducible covers of maximal rectangles. / Cheng Y., Iyegnar S. S., Kashyap R. L. // IEEE transactions on software engineering. V.14, #5. 1988. P.651-658.

39. Cohen H. A variational principle for domino tilings. / Cohen H., Kenyon R., Propp J. // J. Amer. Math. Soc., V.14, #2. 2001. P.297-346.

40. Cohen M. F. Wang Tiles for image and texture generation / Cohen M. F., Shade J., Hiller S., Deussen O. // ACM Trans. Graphics, #22(3). 2003. P.287-294.

41. Culberson J. C. Covering polygons is hard. / Culberson J. C., Reckhow R. A. // Journal of algorithms, #17. 1994. P.2-44.

42. Dyckhoff H. Typology of cutting and packing problems // European journal of operational research, #44. 1990. P.145-159.

43. Dyckhoff H. Cutting and packing in production and distribution. / Dyckjoff H., Finke U. Berlin: Springer Verlag, 1992.

44. Finch S. R. Circular coverage constants. Cambridge: Cambridge University Press, 2003.

45. Fowler R. J. Optimal packing and covering in the plane are NP-complete. / Fowler R. J., Paterson M. S., Tatimoto S. L. // Information Proc. Let., #12. 1981. P.133-137.

46. Franklin P. Optimal rectangle covers for convex rectilinear polygons. Simon Fraser University, 1986.

47. Franzblau D. S. An algorithm for constructing regions with rectangles. / Franzblau D. S., Kleitman D. J. // Information and control, #63. 1984. P. 164-189.

48. Gehring H. A genetic algorithm foe solving the container loading problem. / Gehring H., Bortfeld A. // International transactions in operational research, V.4, #5/6. 1997. P401-418.

49. George J.A. Packing different-sized circles into a rectangular container. / George J. A., George J. M., Lamar B. W. // European Journal of Operational Research, #84. 1995. P.693-712.

50. George J. A. Multiple container packing: a case study of pipe packing // Journal of the Operational Research Society, #47. 1996. P.1098-1109.

51. Glover F. Tabu search and adaptive memory programming advances, applications and challenges. // Interfaces in computer science and operational research. 1996. P. 1-75.

52. Golomb S. Polyominoes. Princeton: Princeton University Press. 1994.

53. Grunbaum В. Tilings and patterns. / Grunbaum В., Shephard G. C. New York. 1986.

54. Gudmundsson J. Close approximations of minimum rectangular coverings. / Gudmundsson J., Levcopoulos C. // FST&TCS'96. LNCS,V.l 180. 1996. P.135-146.

55. Gudmundsson J. Lower bounds for approximate polygon decomposition and minimum gap. / Gudmundsson J., Levcopoulos C. // Information Processing Letters, V.81, Issue 3. 2002. P.137-141.

56. Gurevich Y. Remarks on Berger's paper on the domino problem. / Gurevich Y., Koryakov I. 1972.

57. Gwee В. H. Polyominoes tiling by a genetic algorithm. / Gwee В. H., Lim M. H. // Computational optimization and applications, #6. 1996. P.273-291.

58. Hahn S. G. On the optimal cutting of defective sheets // Operations Research, #16. 1968. P.l 100-1114.

59. Imahori S. Local search algorithms for the rectangle packing problem with general spatial costs / Imahori S., Yagiura M., Ibaraki T. // Mathematical programming, #97. 2003. P'.543-569.

60. Johnson D.S. Approximation algorithms for combinatorial problems // Journal of omputing and systems sciences, #9. 1974. P.256-278.

61. Kari J. Deterministic aperiodic tile sets / Kari J., Papasoglu P. // Geometric and functional analysis, #9. 1999. P.353-369.

62. Kaucher E. Interval Analysis in the Extended Interval Space IR // Сотр. Suppl., #2. 1980. P.33-49.

63. Knuth. D.E. The art of computer programming. V.l. Fundamental algorithms. Massachusetts: Addison-Wesley, 1973.

64. Kolountzakis M. N. On the Steinhaus tiling problem / Kolountzakis M. N., Wolff T. // Mathematica, #46. 1999. P.253-280.

65. Kolountzakis M.' The Steinhaus tiling problem and the range of certain quadratic forms / Kolountzakis M., Papadimitrakis M. N. // J. Math., #46. Illinois. 2002. P.947-951.

66. Lagae A. Aperiodic sets of square tiles with colored corners / Lagae A., Kari J., Dutre P. // Submitted to Discrete Mathematics, 1978.

67. Loris F. An application of simulated annealing to the cutting stock problem // European journal of operational research, #114. 1999. P.532-556.

68. Lovasz L. On the ratio of optimal integral and fractional covers // Journal of discrete mathematics, #13. 1975. P.383-390.

69. Maddox S.J. Tiling and adaptive tiling. / Maddox S.J., Efstathiou W.J. // MNRAS, 1990.

70. Manabe S. A neuro-based optimization algorithm for tiling problems with rotation / Manabe S., Asai. H. // Neural Processing Letters. 2001.

71. Masek W.J. Some NP-complete set covering problems / Manuscript. MIT,1977.

72. Mauldin R.D. Comments about the Steinhaus tiling problem / Mauldin R. D., Yingst A. //Proc. Amer. Math. Soc., #131. 2003.

73. Monsefi R. A genetic-neuro algorithm for tiling problems with rotation and/or reflection of figures / Monsefi R., Toosi M. A. // Iranian journal of science and technology. 2002

74. Neville E.H. On the solution of numerical functional equations, illustrated by an account of a popular puzzle and of its solution // Proc. London Math. Soc., #14. 1915. P.308-326.

75. Polak E. Computation methods in optimization. London: Academic Press,1971.

76. Stein S. K. Algebra and tiling: homomorphism in the service of geometry / Stein S. K., Szabo S. // Cams Mathematical Monograph, 25. 1994.

77. Robinson R. Undecidability and non-periodicity for tilings of the plane.1971.

78. Schattschneider D. Tiling the plane with congruent pentagons // Mathematics magazine, #51. 1978. P.29-44.

79. Stoyan Yu. G. The extended interval space and elementary mappings // Proc of the IMACS-GAMM Intern. Symp. on Numerical Methods and Error Bounds. Oldenburg. 1995. P.270-279.

80. Stoyan Yu. G. analytical description of interactions of point sets // Journal of mechanical engineering, V.4, №1-2. 2001. P.77-88.

81. Stoyan Yu. Packing of various radii solid spheres into a parallelepiped / Stoyan Yu., Yaskov G., Scheithauer G. // Preprint MATH-NM-17-2001. Dresden: Technical University of Dresden, 2001.

82. Stoyan Yu. G. Ф-function and its basic properties // Докл. HAH Украины. Сер. A, №8. 2001. P.l 12-117.

83. Stoyan Yu. G. Ф-function for 2D primary objects / Stoyan Yu. G., Terno J., Scheithauer G., Gil N., Romanova T. // Studia Informatica, V.2,№1. Paris. 2002. P.l-32.

84. Stoyan Yu. G. Construction of a Ф-function for two convex polytopes / Stoyan Yu. G., Terno J., Gil M., romanova Т., Scheithauer G. // Applicationes Mathematicae, V. 2, №29. 2002. P. 199-218.

85. Stoyan Yu. G. Ф-function for primary 3D objects / Stoyan Yu. G., Scheithauer G., Pridatko D., Romanova T. // Prepr. Dresden : Technische Univarsitat Dresden, 2002. P.27

86. Stoyan Yu. G. Ф-function for complex 2D objects / Stoyan Yu. G., Scheithauer G., Gil M., Romanova T. // 40R Quarterly Journal of the Belhian, French and Italian Operations Research Societies, V. 2, #1. 2004. P.69-84.

87. Sugimoto Т. Problem of tesselating convex pentagons / Master Thesis. University of Tsukuba, 1999.

88. Wang H. Proving theorems by pattern recognition II // Bell System Tech. Journal, #40(1). 1961. P.l-41.

89. Wang H. Dominoes and the 898-case of the decision problem // Proc. Symp. on Mathematical Theory of Automata. 1962. P.23-55.