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

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

ИВАНОВА Светлана Диадоровна

ИССЛЕДОВАНИЕ ЗАДАЧИ О ШИРИНЕ ГРАФА И ЕЕ ОБОБЩЕНИЙ

05.13.01 - системный анализ, управление и обработка информации (в научных исследованиях)

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

Омск - 2006

Работа выполнена в ГОУ ВПО "Омский государственный университет им. Ф.М. Достоевского"

Научный руководитель: доктор физико-математических

наук, профессор

Колоколов Александр Александрович. Официальные оппоненты: доктор физико-математических

Защита состоится 21 декабря 2006 г. в 14 часов на заседании диссертационного совета ДМ 212.179.03 при ГОУ ВПО "Омский государственный университет им. Ф.М. Достоевского" по адресу: 644077, Омск, ул. Нефте-заводская, 11.

С диссертацией можно ознакомиться в библиотеке Омского государственного университета им. Ф.М. Достоевского.

Автореферат разослан "/¿Е" ноября 2006 г.

Ученый секретарь диссертационного со:

наук, доцент

Ерзин Адиль Ильясович,

кандидат физико-математических наук, доцент

Заблоцкая Ольга Александровна.

Ведущая организация: Институт вычислительной математики

, и математической геофизики СО РАН

к. ф.-м. н., доцент

А.М. Семенов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Графы успешно применяются для моделирования и анализа систем, имеющих сложную сетевую структуру, например, транспортных, информационно-вычислительных сетей, систем взаимоотношений в коллективе и т.д. [1, 5]. Граф можно рассматривать как структурную схему системы [4], в которой вершины соответствуют элементам системы, а ребра -взаимосвязям между ними. Таким образом, графы являются адекватными и наглядными математическими моделями многих реальных систем.

Задача о ширине графа относится к классу задач оптимальной нумерации. Она имеет ряд важных приложений, таких как решение систем линейных уравнений, проектирование интегральных схем и других объектов. Задача о ширине графа является ЛГР-трудной [10], поэтому актуально выделение ее полиномиально разрешимых частных случаев. Недостаточно изученными являются вопросы сложности рассматриваемой задачи на решеточных графах, которые часто возникают в приложениях. Для решеточных графов задача о ширине также остается ЛГР-трудной [8], и до настоящего времени в этом классе был известен лишь один нетривиальный полиномиально разрешимый случай [7]. Обзор результатов по задаче о ширине графа, а также по другим задачам оптимальной нумерации можно найти в работах [2, 6].

Задачи проектирования изделий сложной структуры также имеют важное прикладное значение. Они возникают, например, при проектировании одежды из натурального меха или кожи. В связи с ТУР-трудностью этих задач для них актуальна разработка эффективных алгоритмов приближенного решения.

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

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

Научная новизна. В работе проведено исследование задачи о ширине графа и ее обобщений. Выделены новые полиномиально разрешимые случаи задачи о ширине графа. Для приближенного решения задачи проектирования изделий сложной структуры предложен генетический алгоритм, проведены экспериментальные расчеты.

Основные результаты работы заключаются в следующем:

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

2. Получена нижняя оценка мощности ¿-накрытия для лексикографической постановки задачи о ширине графа. Показано, что его мощность при некоторых упорядочениях переменных ограничена снизу экспонентой от ширины графа; это указывает на трудность решения задачи рядом алгоритмов целочисленного программирования.

3. Для задачи проектирования изделий сложной структуры построены математические модели, которые использованы при создании одежды из натурального меха; разработан генетический алгоритм приближенного решения задачи.

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

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

Апробация работы. Основные результаты диссертации докладыва-

лись на Российских конференциях "Дискретный анализ и исследование операций (Новосибирск, 2002, 2004), международной научно-технической конференции "Динамика систем, механизмов и машин" (Омск, 2002), XII- Всероссийской конференции "Математическое программирование и приложения" (Екатеринбург, 2003), международной конференции "Проблемы оптимизации и экономические приложения" (Омск, 2003, 2006), The XIV Meeting of EURO Working Group on Location Analysis (Корфу, Греция, 2003), The 2-nd International Workshop "Discrete Optimization Methods in Production and Logistics" (Омск, 2004), XIII Байкальской международной школе-семинаре "Методы оптимизации и их приложения" (Иркутск, 2005), а также на научных семинарах в Институте вычислительной математики и математической геофизики СО РАН, Институте математики им. C.JI. Соболева СО РАН и его Омском филиале.

Публикации. Основные результаты диссертации опубликованы в работах [11-24].

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

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении обосновывается актуальность темы диссертации и излагается содержание диссертационной работы.

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

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

Задача о ширине графа формулируется следующим образом. Пусть G — (V,E) - неориентированный граф, N = |V|. Нумерацией графа G называется биекция (р : V(G) —* {l,...,iV}. Множество всех нумераций графа G обозначим через Ф((Р). Длиной ребра uv при нумерации ip называется величина |<^(и) — <^(г>)|. Наибольшая длина ребра называется шириной нумерации ip и обозначается B(G,cp).

Задача состоит в отыскании нумерации <£>*, для которой значение В{Оу<р*) минимально. Величина В(С) = В(С,<р*) называется шириной графа (7, а нумерация <р* - оптимальной нумерацией.

Задача проектирования изделий сложной структуры является обобщением задачи о ширине графа. Предположим, что проектируемое изделие состоит из конечного числа образующих элементов. Структура изделия задается графом б? = (V, Е), вершины которого соответствуют возможным местам размещения элементов, а ребро между парой вершин указывает взаимосвязь данных позиций. Элементы изделия выбираются из конечного множества и характеризуются фиксированным числом параметров, значения которых могут быть выражены в числовых величинах. Если пара элементов оказывается размещенной во взаимосвязанных позициях графа, то могут накладываться ограничения на разность значений их параметров. Требуется расположить в вершинах графа совокупность из |У| элементов таким образом, чтобы полученное размещение удовлетворяло указанным условиям и являлось оптимальным в смысле одного или нескольких критериев. Поскольку для каждого параметра известен "вес", соответствующий его относительной важности, то в качестве целевой функции может быть выбрана, например, линейная свертка критериев — взвешенная сумма максимальных разностей значений параметров взаимосвязанных элементов.

В п. 1.2 рассматриваются приложения исследуемых в работе задач.

В п. 1.3 вводятся определения и дастся обзор известных результатов по задаче о ширине графа.

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

Н С <2 - граф Н является подграфом графа С?; [-21, г2] = {¿1, гх + 1,..., г2}, где z1} г2 г2;

~ решеточный граф с множеством вершин Уст п — [1, га] х [1,п], где т,п> 1;

<7(а) - граф, полученный из решеточного графа С? путем сдвига на

вектор а = (0:1,0:2) € Z2; 9ш,п = {Ст,»(а) : а € Z2}.

Графы семейства От,п будем называть прямоугольными решетками размера т х п. Для прямоугольных решеток задача о ширине полиномиально разрешима [7].

Будем говорить, что две вершины V — и ги = ((ш,^) решеточного

графа находятся на одной диагонали, если г« + = + з^.

Нижняя диагональная нумерация решеточного графа строится следующим образом: вершины нумеруются по диагоналям, и каждая диагональ просматривается сверху вниз, т.е. ^¿(г«,^) < <^(гы>9.1и>), если и только если выполено одно из условий: 1. Л- зУ = г«, + Зю и г„ < 2. г„ + ¡у < %у} + Зги. Аналогично определяется верхняя диагональная нумерация <ри: (ри(ч,3ь) < фи^илЗу)), если и только если выполено одно из условий: 1. -I- ¿у = г«, + ^ и > г'^, 2. г„ + ^ < гю + jw•

В п. 1.4 проводится исследование задачи о ширине графа с помощью подхода, основанного на регулярных разбиениях пространства Кп [3].

Для задачи о ширине графа используется следующая модель целочисленного линейного программирования (ЦЛП) [9]. Пусть V — {их,..., у^}. Введем переменные

= 1, И ПОЛОЖИМ X = (Х\\,Х\2, ^21,^22, .-.>^2^5 Мо-

дель ЦЛП имеет вид:

1, если — з, О в противном случае,

У -»•

Ш1П

(1)

N

N

£ кХгк - £ кхзк < У,

N

А:=1 N

>1,3 : ущ € Е

(2)

X) "С кхгк < У У

N

(3)

¿=1

N

(4)

3=1

Хц > о, 1,з =

ху е Ъ, 1,3 = 1,...,АГ.

> .

(5)

(6)

Пусть ö — у* — у, где у* и у - оптимальные значения целевых функций для задач (1)-(6) и (1)-(5), соответственно.

Теорема 1.2. Разрыв двойственности S для задачи (1)-(6) равен B{G).

Перейдем к исследованию задачи о ширине графа с помощью /^разбиения [3].

Точки х,у G Rn (х У у) называются L-эквивалентными, если не существует отделяющей их точки z Е Zn, для которой х >z z >z у- Это отношение порождает разбиение пространства Rn на непересекающиеся L-классы. Данное разбиение называется L-разбиением.

Пусть М - выпуклое многогранное множество в Rn. Рассмотрим задачу целочисленного программирования (ЦП) в лексикографической постановке:

найти г" = lexmin(M П Zn). (7)

Множество М называется релаксационным множеством задачи (7), а множество М* = {ж G М : х -< z для всех 2 € (М Г) Zn)} - ее дробным накрытием. Фактор-множество M*/L называется L-накрытием задачи (7). Оно играет важную роль в исследовании задачи, поскольку в некоторых методах ЦП (например, в алгоритмах отсечения или в методе перебора L-классов [3]) происходит последовательное исключение точек из Л/*. Мощность L-накрытия входит в оценки числа итераций для алгоритмов, поэтому ее можно рассматривать как показатель сложности решения задачи данными алгоритмами.

Релаксационное множество М задачи (1)-(6) задается ограничениями (2)-(5). Пусть s = (у;х). Введем множество М' = {ä £ R^2+1 : у > О, х е М} и рассмотрим следующую лексикографическую постановку:

найти 2* = lexmin(M' П ZN*+1). (8)

Дробное накрытие дайной задачи имеет вид:

Mi = {s е М': s X г для всех z е (М'П ZN4l)}. В работе получена следущая оценка мощности L-накрытия задачи (8): Теорема 1.3. \M'JL\ > (B{G) - 1)!

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

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

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

Прямоугольная решетка с одной угловой выемкой представляет собой решеточный граф Ь с множеством вершин Уь = Устп \ И, где У\ — [1,01] х [п - &х + 1,п], т,п > 3, ах € [1,т - 2], е [1 ,п — 2]. Такой граф изображен на рис. 1. _

6 01 г

1

т Рис. 1

Введем обозначения: гах = га — а\, п\ = п — Ь\. Нетрудно показать, что В(Ь) = В(Ь, (ра) = п при т\ > п, и В{Ь) — В(Ь, сри) = га при п\ > га, поэтому далее будем считать, что т\ < п и п\ < га. Следующая теорема позволяет определить ширину любого графа из данного семейства по значениям его параметров.

Теорема 2.2. Пусть щ < га, т\ < п. Если п\ = 7П1, то = п\ 4-1, е противном случае В(Ь) = тах(п1, гах).

При этом нижняя диагональная нумерация является оптимальной в случае п\ > чщ, а верхняя диагональная нумерация оптимальна при щ < Шх.

Прямоугольная решетка с двумя угловыми выемками в противоположных углах - это связный решеточный граф Ь с множеством вершин Уь = У0т>п \ {Ух и У2), где V-! = [1,01] х [п - 61 + 1,п], у2 = [т - а2 + 1,га] х [1,62], га,п > 3, € [1,га - 2], е [1,п — 2] (г = 1,2). Такой граф изображен на рис. 2.

Введем обозначения: га* = га — а,, п,- = п — 6,- (г = 1,2), р = га — <21 — <22, <7 = п — 61 — &2- Поскольку !?(£) = В(Ь,(р<1) — п при р > п, и

ь а 1 Г / > >Ь2

А

1

"2 >г>2 ► Т1 О!

I а.2

I

С

т т

Рис. 2 Рис. 3

В(Ь) = В(Ь,(ри) = т при д > ш, далее считаем, что р < п и д < т. В силу связности графа Ь имеем тах(р, q) >1. Без ограничения общности считаем, что тп2 > пх > тт(га1, п2) и выполнены следующие условия:

1) если тах(р, д) = 1, то т\ > п2,

2) если П1 = тп\ < шт(п2, гп2), то р < д.

Положим <5(£) = тах{В(Н) : Л" - максимальная по включению прямоугольная подрешетка графа Ь}. В графе Ь существует не больше четырех таких подрешеток.

Теорема 2.4. Если выполнено одно из условий:

(О р = т,

(и) п\ — гп\ < ппп(п2, пг2), п^щ — 1) — рд — 1 > п\(2п1 — р — — 2), то В(Ь) = пх 4- 1, в противном случае В(Ь) — 6(Ь) — тах(пх,р).

В случае п\ — т\ < тт(712,7712), 711(711 — 1) — рд — 1 < П1(2П1 — р — д — 2) предложен способ построения оптимальной нумерации, которая является комбинацией верхней и нижней диагональных. В остальных случаях оптимальной является одна из диагональных нумераций, в зависимости от соотношений между значениями параметров, графа.

Прямоугольная решетка с двумя угловыми выемками в смежных углах - это решеточный граф Ь с множеством вершин У& = Уст>п \ (VI и 14), где 14 — [1, а\) х [п — 4-1, п], Ц = [га — аг 4-1, т] х [п —• Ьг 4-1, п], га > 4, п > 3, а{ £ [1,771 — 3], е [1,п — 2] (г = 1,2), а\ 4- а2 < га — 2. Такой граф изображен на рис. 3.

Пусть щ — п — Ьг (г = 1,2), р = т — а\ — а2. Без ограничения общности считаем, что < Ь2 и выполнено условие: если п\ — п2, то а\ < а2.

Поскольку В{Ь) = В(Ь, сри) = т при гс2 > га, и В{Ь) = В(Ь, <ра) = п при далее будем считать, что п2 < га и р < п. Введем обозначение: /3 = гшп{/?1, /?2, /?з, Д4}, где (3\ — тах(п1 + п2,р), /?2 = тах(пй,р +ах), /?3 = тах(п1,р + тт(а2,7г2)), /?4 = п. ■

Теорема 2.5. Если выполнено одно из условий:

щ + п2 = р, (и) п2 = р + а\ < 0з, (Ш) п\ = р + тт(а2, п2) < /?2, то #(!/) = (3 + 1, в противном случае В(Ь) — (3.

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

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

Пусть га, п > 1. Рассмотрим граф Dтntn, который представляет собой прямоугольную решетку С?т,п с дополнительными диагональными ребрами. Множество Ел диагональных ребер определяется следующим образом: ьги € Еа для V = (г^,^), гу = (г^,.?'„,), если и только если выполнено одно из условий:

1) г„ - нечетное, ^ = ^ + 1, \гу — г'и,| = 1,

2) - четное, = ^ — 1, |г\, — г„,| = 1.

Пример такого графа изображен на рис. 4.

171

Рис. 4

Теорема 2.6. В{ОтуП) — ют(ш,п+ 1).

При этом в случае п + 1 < га оптимальная нумерация ср* имеет вид: <р*{Ъз) = п{г - 1) +.7, ге [1 ,га],.7 € [1,п]. 11

Если же п + 1 > га, то для г G [l,m], j € [1,п]

-ч _ J ttx(j — 1) + г/2, если г четно, ^ 4 1 m(j1) + [m/2j + (г + 1)/2 в противном случае.

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

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

Пусть п = |У|, т - количество размещаемых элементов (т > vi), р -число параметров, К С {1, - множество номеров параметров, на которые накладываются ограничения. Введем обозначения: o>i > 0 - значение к-го параметра г-го элемента, г = 1, ...,т, к = 1, ...,р, Ьк > 0 - ограничение на разность значений по к-му параметру, к Е К, wk > 0 - "вес" fc-ro параметра, соответствующий его относительной важности, к = 1,...,р.

Пусть <р : V —► {1,...,т} - размещение совокупности п элементов в вершинах графа G, т.е. <p(v) - это номер элемента, расположенного в вершине v. Множество всех таких размещений обозначим через Фт(С?). Получаем следующую задачу дискретной оптимизации:

f{<p) = £ ti^mglaj^ - акф)\ - min ke.K,

tp <E Фт(С).

Если m = n, p — 1, К = 0, w1 — 1 и af = г для любого г = 1,..., т, то мы получаем задачу о ширине графа.

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

В п. 3.2 предлагается генетический алгоритм для задачи проектирования изделий сложной структуры.

Опишем общую схему генетического алгоритма (ГА).

Требуется найти максимум или минимум функционала / на множестве допустимых решений в пространстве X. Процесс работы ГА представляет собой последовательную смену популяций, состоящих из фиксированного числа особей. Особь состоит из генотипа д и фенотипа х(д). Генотип - это строка фиксированной длины, состоящая из генов - символов некоторого алфавита. Фенотип отображает генотип в пространство поиска X. Процесс поиска идет с учетом значений функции пригодности, заданной на множестве генотипов, которая определяет степень "приспособленности" особи.

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

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

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

Для задачи проектирования изделий сложной структуры предлагается следующий вариант генетического алгоритма. Пусть V = {г>1,..., ип}. Генотип д = д1,..., дт представляет собой перестановку т элементов, первые п генов кодируют номера элементов, размещенных в соответствующих вершинах графа, т.е. дг = у?(г^) при г = 1,п. Остальные гены соответствуют номерам неразмещенных элементов. Функция пригодности имеет вид:

f

f(x(o)). если max lafc, — akA < bk лля всех k G К.

где С - достаточно большая константа.

В качестве схемы воспроизводства используется схема с элитой: при формировании очередной популяции сохраняется без изменений элита -фиксированное число лучших по пригодности особей. Отбор родителей реализован по принципу турнирной селекции - случайным образом из популяции извелекается фиксированное число особей с равномерным распределением, затем выбирается лучшая из них. Для скрещивания применяется униформный вариант кроссинговера с частичными сочетаниями (Partially-Mapped Crossover), который строит потомков, выбирая часть генов от одного из родителей и сохраняя максимально возможное число генов другого родителя.

Опишем оператор мутации. Для iyj — 1, ...,га, к = 1 ,...,р положим J а

k Г 1

fk. = ) г: ,

I о

в противном случае, и определим величину — ф\ — Ф2, где

Ф\ = <

ф2 = <

р

^2и}к тах(/£, /£•), если тах(/--, ЙЛ < Ък для всех к е К, к=1

С + X) гу*(тах(/£, ЙЛ — 6*) в противном случае, к£К

р

тах(Й, /Д), если тах(/£, /£) < Ьк для всех к € К,

к=1

С + С ^*(тах(/£, /»*) — Ьк) в противном случае. кеК

Пусть smut ~ положительное целое число, р € [0,1]. Оператор мутации устроен следующим образом. С равномерным распределением выбирается s €Е {0,..., smut} и 5 раз выполняется следующая процедура:

1. Выбрать случайно с равномерным распределением позиции i е {1,...,га} и j е {1,...,т}\{г};

2. Если > 0, то гены дг и gi меняются местами, в противном случае дг и gi меняются местами с вероятностью р.

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

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

Элементами проектируемого изделия (например, мехового пальто) являются пушно-меховые полуфабрикаты. Имеется схема изделия, разбитая на шаблоны — возможные места размещения полуфабрикатов, на основе которой строится граф (рис. 5). Ребро в графе изделия указывает на наличие общей границы у соответствующей пары шаблонов. Меховые полуфабрикаты характеризуются рядом свойств (таких как цвет, толщина кожевой ткани, длина волоса и т.п.), которые оказывают влияние на внешний вид и качество готовой одежды. Так, например, желательно, чтобы соседние элементы (имеющие в изделии общую границу) как можно меньше отличались по каждому из рассматриваемых параметров. При этом одни характеристики полуфабрикатов могут влиять на качество больше, чем другие.

Расчеты проводились для пяти задач с реальными исходными данными следующих размерностей (данные представлены в формате число элементов/ число вершин в графе/число параметров)'. 20/18/3, 23/18/4, 42/25/5, 50/50/4, 50/50/5. Для вычислений использовалась ЭВМ с процессором AMD Athlon-1900 (1.6 GHz). Задачи решались с учетом требования симметричности. Во всех задачах генетическим алгоритмом были получены достаточно хорошие решения с малыми разностями значений параметров.

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

Таблица 1. Максимальная разность значений параметров

к соседние позиции симметричные позиции А*

Р ГА+ ГА дк Р ГА+ ГА дк

1 Ö.56 0.56 0.32 0.04 0.46 0.24 0.14 0.01 0.78

2 0.89 0.8 0.24 0.06 0.44 0.33 Ö.1Ö 0 1.03

3 0.82 0.54 Ö.37 0.1 Ö.38 0.18 0.18 0 1.57

4 1.19 0.4 Ö.23 0.07 1.06 Ö.1S 0.13 0 1.46

5 0.78 0.47 0.3 0.1 0.41 0.25 0.11 0 1

Здесь к - номер параметра, 6к и Д&- нижняя и верхняя оценки максимума модуля разности для к-го параметра, к = 1, ...,5. Значение целевой функции при ручной раскладке равно 6.99, при комбинированном варианте (раскладка ГА с ручным отбором элементов) - 3.92 и при раскладке ГА - 2.21. Данные решения были найдены генетическим алгоритмом и комбинированным вариантом за 3,86 сек и 2.95 сек, соответственно.

Проведенный вычислительный эксперимент позволяет сделать вывод о том, что на основе ГА можно быстро получить ряд альтернативных решений, которые по большинству рассматриваемых параметров лучше, чем решения, найденные ручным способом.

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

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

[1] Дементьев В.Т., Ерзин А.И., Ларин P.M., Шамардин Ю.В. Задачи оптимизации иерархических структур. - Новосибирск: Изд-во Новосиб. ун-та, 1996. - 167 с.

[2] Иорданский М.А. Оптимальные нумерации вершин графов // Мат. вопросы кибернетики. - 2001. - Вып. 10. - С. 83-102.

[3] Колоколов A.A. Регулярные разбиения и отсечения в целочисленном программировании // Сиб. журнал исследования операций. - 1994. -N 2. - С. 18-39.

[4] Перегудов Ф.И., Тарасенко Ф.П. Основы системного анализа. - Томск: НТЛ, 1997. -396 с.

[5] Попков В.К. Математические модели связности. 4.2. Гиперграфы и гиперсети. - Новосибирск: Изд-во ИВМиМГ СО РАН, 2001. - 180 с.

[6] Chinn P.Z., Chvdtalovd J., Dewdney A.K., Gibbs N.E. The bandwidth problem for graphs and matrices - a survey //J. Graph Theory. - 1982. -V. 6. - P. 223-254.

[7] Chv&talova J. Optimal labelling of a product of two paths //' Discrete Math. - 1975. - V. 11. - P. 249-253.

[8] Diaz J., Penrose M.D., Petit J., Serna M.J. Approximating layout problems on random geometric graphs //J. Algorithms. - 2001. - V. 39, N 1. -P. 78-116.

[9] Lam P., Shiu W., Lin Y.: Duality in the bandwidth problem // Congressus Numerantium. - 1997. - V. 124. - P. 117-127.

[10] Papadimitriou Ch.H. The NP-completeness of the bandwidth minimization problem // Computing. - 1976. - V. 16. - P. 263-270.

РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

[11] Архипенко М.Ю., Иванова С.Д., Колоколов А.А., Нагорная З.Е. Автоматизация процесса размещения меховых полуфабрикатов в скрое изделия // Естественные и технические науки. - 2004. - N 4(13). -С. 269-274.

[12] Иванова С.Д. Некоторые полиномиально разрешимые случаи задачи о ширине графа - Препринт. - Омск: "Полиграфический центр КАН", 2006. - 32 с.

[13] Иванова С.Д. О задаче оптимальной нумерации вершин графа // Материалы Российской конф. "Дискретный анализ и исследование операций". - Новосибирск, 2004. - С. 106.

[14] Иванова С.Д. О сложности некоторых задач нумерации вершин графа // Материалы Всероссийской конф. "Проблемы оптимизации и экономические приложения". - Омск, 2003.- С. 92.

[15] Иванова С.Д. Об одном полиномиально разрешимом случае задачи о ширине графа // Материалы Всероссийской конф. "Проблемы оптимизации и экономические приложения". - Омск, 2006. - С. 97.

[16] Иванова С.Д. Ширина Т-образного наложения прямоугольных решеток // Прикладная математика и информационные технологии: Сб. науч. и метод, трудов. - Омск: Изд-во ОмГТУ, 2005. - С. 38-51.

[17] Иванова С.Д. Ширина решеточных графов специальной структуры // Труды XIII Байкальской международной школы-семинара "Методы оптимизации и их приложения". - Иркутск, 2005. - Т. 1.,- С. 485-490.

[18] Иванова С.Д., Колоколов А.А. Оценки мощности L-накрытий для задачи о ширине графа // Омский научный вестник. - 2006. - N 4(38). -С. 68-71.

[19] Колоколов А.А., Нагорная З.Е., Иванова С.Д. О некоторых задачах проектирования изделий сложной структуры // Материалы Российской конф. "Дискретный анализ и исследование операций". - Новосибирск, 2002. - С. 243.

[20] Колоколов А.А., Нагорная З.Е., Архипенко М.Ю., Иванова С.Д. Проектирование меховых изделий с использованием математического моделирования // Материалы IV Международной научно-технической конф. "Динамика систем, механизмов и машин" - Омск, 2002. - Кн. 1. -С. 297-299.

[21] Колоколов А.А., Нагорная З.Е., Архипенко М.Ю., Иванова С.Д. Разработка моделей и алгоритмов для некоторых задач оптимального проектирования // Материалы Всероссийской конф. "Математическое программирование и приложения". - Екатеринбург, 2003. - С. 149-150.

[22] Ivanova S.D. A polynomial time solvable case of bandwidth minimization problem on lattice graphs // Proceedings of the 2nd International Workshop "Discrete Optimization Methods in Production and Logistics". -Omsk, 2004. - P. 169 - 175.

[23] Ivanova S.D. On the complexity of bandwidth minimization problem for some graphs // Abstracts of the XIV Meeting of EURO Working Group on Location Analysis. - Corfu, Greece, 2003. - P. 31.

[24] Kolokolov A.A., Nagornaya Z.E., Arkhipenko M.Yu., Ivanova S.D. Discrete optimization models and algorithms for some design problems // Abstracts of the XIV Meeting of EURO Working Group on Location Analysis. -Corfu, Greece, 2003. - P. 37.

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

Подписано в печать 15.11.2006. Формат 60x84 1/16. Бумага офсетная. Усл. печ. л. 1,25. Уч.-изд. л. 1,3. Тираж 110 экз. Заказ JV» 176

Отпечатано в "Полиграфическом центре КАН" 644050, г. Омск, пр. Мира, На, тел. (3812) 65-47-31 Лицензия ПЛД № 58-47 от 21.04.97.

Введение

1. Задача о ширине графа и ее обобщения

1.1. Постановки задач.

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

Графы традиционно и успешно применяются для моделирования и анализа различных систем, имеющих сложную сетевую структуру, например, транспортных, информационно-вычислительных сетей, систем взаимоотношений в коллективе и т.д. [6,27].

Широко распространенной моделью реальных систем является структурная схема системы [26]. Она содержит информацию об элементах системы, о связях между элементами, а также о связях системы с окружающей средой. Абстрагируясь от содержательной стороны структурной схемы и выявляя ее математическую сущность, мы получаем схему, в которой содержится только информация о наличии элементов и связей между ними. Эта схема может быть представлена графом, вершины которого соответствуют элементам системы, а ребра - наличию связей между элементами. Таким образом, графы являются адекватными и наглядными математическими моделями многих реальных систем.

В задаче о ширине графа требуется пронумеровать вершины графа последовательными натуральными числами так, чтобы минимизировать максимальное значение модуля разности номеров смежных вершин. Она интересна как с теоретической, так и с практической точки зрения, поскольку имеет ряд важных приложений в различных областях, таких как решение систем линейных уравнений, проектирование интегральных схем и других объектов. Задача о ширине графа относится к задачам оптимальной нумерации. Общим для всех задач данного класса является вид допустимого решения - нумерация вершин, а отличаются они друг от друга лишь оптимизируемой функцией. Этот класс включает, в частности, задачу оптимального линейного упорядочения, которой посвящено значительное число работ [28,66,68,77], а также ряд других задач [3,30,60,78]. Обзор результатов по задачам нумерации можно найти в [39,63].

Задачи оптимальной нумерации, в свою очередь, можно отнести к более широкому классу задач размещения графа на линии. Они изучаются в работах [9,10,19,79].

Приведем содержательную постановку задачи проектирования изделий сложной структуры. Предположим, что проектируемое изделие состоит из конечного числа образующих элементов. Структура изделия задается графом, вершины которого соответствуют возможным местам размещения элементов, а ребро между парой вершин указывает на взаимосвязь данных позиций. Элементы изделия характеризуются фиксированным числом параметров, которые могут быть выражены в числовых величинах. Если пара элементов оказывается размещенной во взаимосвязанных позициях, то могут накладываться ограничения на разность значений их параметров. Требуется расположить в вершинах графа элементы изделия (по одному в каждой вершине) таким образом, чтобы полученное размещение являлось оптимальным в смысле одного или нескольких критериев. Как правило, для каждого параметра известен "вес", поэтому в качестве целевой функции может быть выбрана, например, линейная свертка критериев - взвешенная сумма максимальных разностей значений параметров взаимосвязанных элементов.

Эта задача имеет важное прикладное значение. Она возникает, в частности, при проектировании изделий из натурального меха или кожи. Заметим, что если число элементов равно числу вершин, и каждый элемент имеет единственный параметр, значение которого совпадает с номером элемента, мы получаем задачу о ширине графа.

Задача о ширине графа, а следовательно, и более общая задача проектирования, являются TVP-трудными [71], поэтому особый интерес представляет выделение полиномиально разрешимых частных случаев и разработка алгоритмов приближенного решения этих задач. Исследованиям в области алгоритмов для задачи о ширине графа посвящены работы [30,34,36,40,44,45,51-53,67,72,73,76]. В работах [29,32,33,41,54,56, 62,70,74,75] описываются некоторые классы графов, для которых задача о ширине может быть решена за полиномиальное время. Заметим, что задача о ширине остается TVP-трудной даже для графов достаточно простой структуры - деревьев с максимальной степенью вершины 3 [45], а также для решеточных графов [38]. Граф называется решеточным, если множество его вершин - это подмножество множества Z2, и две вершины смежны тогда и только тогда, когда евклидово расстояние между ними равно единице.

Вопросы вычислительной сложности задачи о ширине на решеточных графах являются недостаточно изученными. До настоящего времени в этом классе был известен лишь один нетривиальный полиномиально разрешимый случай - прямоугольные решетки [33]. Решеточные графы часто возникают в приложениях. Так, например, в задаче проектирования изделий из меха граф изделия обычно либо решеточный, либо имеет структуру, близкую к решеточной. Поэтому актуально выделение новых подклассов решеточных графов, для которых задача о ширине полиномиально разрешима.

Поскольку задача проектирования изделий сложной структуры является /VP-трудной, помимо выделения полиномиально разрешимых частных случаев этой задачи актуален также поиск приближенных решений. В последнее время для получения приближенных решений NP-трудных задач дискретной оптимизации активно разрабатываются подходы, основанные на аналогиях с природой. К данному классу относятся, в частности, эволюционные алгоритмы, алгоритмы имитации отжига, муравьиной колонии. Эволюционные алгоритмы основаны на принципе моделирования процесса биологической эволюции и хорошо зарекомендовали себя при решении многих оптимизационных задач.

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

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

Основные результаты работы заключаются в следующем.

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

2. Получена нижняя оценка мощности L-накрытия для лексикографической постановки задачи о ширине графа. Показано, что его мощность при некоторых упорядочениях переменных ограничена снизу экспонен-той от ширины графа; это указывает на трудность решения задачи рядом алгоритмов целочисленного программирования.

3. Для задачи проектирования изделий сложной структуры построены математические модели, которые использованы при создании одежды из натурального меха; разработан генетический алгоритм приближенного решения задачи.

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

Заключение

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

1. Архипенко М.Ю., Иванова С.Д., Колоколов АА., Нагорная З.Е. Автоматизация процесса размещения меховых полуфабрикатов в скрое изделия // Естественные и технические науки. - 2004. - N 4(13). -С. 269-274.

2. Батищев Д.И. Генетические алгоритмы решения экстремальных задач Учебное пособие. - Воронеж: Воронеж, гос. техн. ун-т, 1995. -69 с.

3. Головач П.А., Фомин Ф.В. Суммарная величина вершинного разделения и профиль графов // Дискретная математика. 1998. - Т. 10, N 1. - С. 87-94.

4. Гольдберг М.К., Клипкер И.А. Алгоритмы минимальной нумерации вершин дерева // Сообщения АН ГрССР. 1976. - Т. 81, N 3. - С. 553-558.

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

6. Дементьев В.Т., Ерзин А.И., Ларин P.M., Шамардин Ю.В. Задачи оптимизации иерархических структур. Новосибирск: Изд-во Ново-сиб. ун-та, 1996. - 167 с.

7. Еремеев А.В. Генетический алгоритм для задачи о покрытии // Дискрет. анализ и исслед. операций. 2000. - Сер. 2. - Т. 7, N 1. - С. 47-60.

8. Заблоцкая О. А., Колоколов А А. Вполне регулярные отсечения в булевом программировании // Управляемые системы. Новосибирск: Наука, 1983. - Вып. 23. - С. 55-63.

9. Забудский Г. Г. О целочисленной постановке одной задачи размещения объектов на линии // Управляемые системы Новосибирск: Наука, 1990,- Вып. 30. - С. 35-45.

10. Забудский Г.Г. Задачи оптимального размещения объектов на линии с минимально допустимыми расстояниями Препринт АН СССР. Сиб. отд-ние ВЦ: Новосибирск. 1990. - 32 с.

11. Заозерская JI.A. Об одном алгоритме перебора//-классов для решения задачи о покрытии множества // Труды XI Байкальской международной школы-семинара "Методы оптимизации и их приложения". Иркутск, 1998. - N.1. - С. 139-142.

12. Иванова С.Д. Некоторые полиномиально разрешимые случаи задачи о ширине графа Препринт. - Омск: "Полиграфический центр КАН", 2006. - 32 с.

13. Иванова С.Д. О задаче оптимальной нумерации вершин графа // Материалы Российской конф. "Дискретный анализ и исследование операций". Новосибирск, 2004. - С. 106.

14. Иванова С.Д. О сложности некоторых задач нумерации вершин графа // Материалы Всероссийской конф. "Проблемы оптимизации и экономические приложения". Омск, 2003.- С. 92.

15. Иванова С.Д. Об одном полиномиально разрешимом случае задачи о ширине графа // Материалы Всероссийской конф. "Проблемы оптимизации и экономические приложения". Омск, 2006. - С. 97.

16. Иванова С.Д. О ширине Т-образного наложения прямоугольных решеток // Прикладная математика и информационные технологии: Сб. науч. и метод, трудов. Омск: Изд-во ОмГТУ, 2005. - С. 38-51.

17. Иванова С.Д. Ширина решеточных графов специальной структуры // Труды XIII Байкальской международной школы-семинара "Методы оптимизации и их приложения". Иркутск, 2005. - Т. 1. -С. 485-490.

18. Иванова С.Д., Колоколов А.А. Оценки мощности L-накрытий для задачи о ширине графа // Омский научный вестник. 2006. -N 4(38). - С. 68-71.

19. Иорданский М.А. Оптимальные нумерации вершин графов // Мат. вопросы кибернетики. 2001. - Вып. 10. - С. 83-102.

20. Колоколов А.А. Регулярные разбиения и отсечения в целочисленном программировании j j Сиб. журн. исслед. операций. 1994. - T.l, N 2. - С.18-39.

21. Колоколов А.А., Девятерикова М.В. Анализ устойчивости L-разбиения в конечномерном пространстве // Дискретный анализ и исследование операций. Новосибирск: ИМ СО РАН, 2000. - Сер.2.- N 2.- С. 47-53.

22. Колоколов А.А., Нагорная З.Е., Иванова С.Д. О некоторых задачах проектирования изделий сложной структуры // Материалы Российской конф. "Дискретный анализ и исследование операций". Новосибирск, 2002. - С. 243.

23. Лепин В.В., Задача о профиле матриц и графов Препринт АН БССР. - Минск: Изд-во ин-та математики, 1986 - N 33(269).

24. Перегудов Ф.И., Тарасенко Ф.П. Основы системного анализа. -Томск: НТЛ, 1997. 396 с.

25. Попков В.К. Математические модели связности. 4.2. Гиперграфы и гиперсети. Новосибирск: Изд-во ИВМиМГ СО РАН, 2001. - 180 с.

26. Adolfson D., Ни Т.С. Optimal linear ordering // SIAM J. Appl. Math.- 1973. V. 25, N 3. - P. 403-423.

27. Assman S.F., Peck G.W., Syslo M.M., and Zak J. The bandwidth of caterpillars with hair of lengths 1 and 2 // SIAM J. on Algebraic and Discrete Meth. 1981. - V. 2. - P. 387-393.

28. Blum A., Konjevod G., Ravi R., and Vempala S. Semi-definite relaxations for minimum bandwidth and other vertex-orderind problems // Theoretical Computer Science. 2000. - V.235, N 1. - P. 25-42.3137

29. Chinn P.Z., Chvatalova J., Dewdney A.K., Gibbs N.E. The bandwidth problem for graphs and matrices a survey // J. Graph Theory. - 1982. - V. 6. - P. 223-254.

30. Chinn P.Z., Lin Y., Yuan J., Williams K. Bandwidth of the composition of certain graph powers // Ars Combinatoria. 1995. - V. 39. - P. 167-173.

31. Chvatalova J. Optimal labelling of a product of two paths // Discrete mathematics. 1975. - 11. - P. 249-253.

32. Cuthill E., McKee J. Reduction the bandwidth of sparse symmetric matrices // Proc. of 24th Nat. Conf. ACM, 1969. P. 157-172.

33. Davis L. Handbook of Genetic Algorithms. New York: Van Nostrand Reinhold, 1991. - 371 p.

34. Dueck G.H., Jeffs J. A heuristic bandwidth reduction algorithm // J. Combinatorial Mathematics and Combinatorial Computing. 1995. -V. 18. - P. 97-108.

35. Dfaz J., Gibbons A.M., Paterson M.S., Toran J. The Minsumcut problem //In Algorithms and Data Structures, F. Dehen, R. J. Sack, and N. Santoro, Eds. Lecture Notes in Computer Science, 1991. V. 519. - P. 65-79.

36. Dfaz J., Penrose M.D., Petit J., Serna M.J. Approximating layout problems on random geometric graphs // J. Algorithms. 2001. - V. 39, N 1, P. 78-116.

37. Diaz J., Penrose M.D., Petit J., Serna M.J. A survey on graph layout problems // ACM Computing Surveys. 2002. - V.34, N 3. - P. 313-356.

38. Dunagan J., and Vempala S. On Euclidian embedclings and bandwidth minimization //In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques, Lecture Notes in Computer Science. 2001. - V. 2129. - P. 229-240.

39. Eitner P.G. The bandwidth of the complete multipartite graph // Presented at the Toledo Symposium on Applications of Graph Theory, 1979.

40. Ellis J., Sudborough I. H., and Turner J. The vertex separation and search number of a graph // Information and Computation. 1979. -V. 113. - P.50-79.

41. Eremeev A.V. A Genetic Algorithm with a Non-Binary Representation for the Set Covering Problem // Proc. of Operations Research: Springer Verlag, 1999. P. 175-181.

42. Feige U. Approximating the bandwidth via volume respecting embeddings // J. Comput. Syst. Sci. 2000. - V. 60, N 3. - P. 510539.

43. Garey M.R., Graham R.L., Johnson D.S., Knuth D.E. Complexity results for bandwidth minimization // SIAM J. Appl. Math. 1978. - V. 2. - P. 477-495.

44. Garey M.R., Johnson D.S., Stockmeyer L. Some simplified NP-complete graph problems // Theoretical Computer Science. 1976. - V. 1. - P. 237-267.

45. Gavril F. Some NP-complete problems on graphs //In Proc. of 11th Conf. on Information Sciences and Systems: Johns Hopkins University, Baltimore, 1977. P. 91-95.

46. Gibbs N.E., Poole W.G., and Stockmeyer P.K. An algorithm for reducing the bandwidth and profile of a sparse matrix // SIAM J. Num. Anal. -1976. V. 13, N 2. - P. 236-250.

47. Goldberg D.E. Genetic Algorithms in Search, Optimization and Machine Learning Reading: Addison Wesley, 1989. - 412 p.

48. Goldberg D.E. and Lingle R. Alleles, Loci and the Travelling Salesman Problem // Proc. of an International Conference on Genetic Algorithms, Lawrence Erlbaum Associates (Hillsdale), 1985.

49. Gupta A.: Improved bandwidth approximation for trees and chordal graphs // J. Algor. 2001. - V. 40, N 1. - P. 24-36.53.54