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

ТУЛЬСКИЙ АРТИЛЛЕРИЙСКИЙ ИНЖЕНЕРНЫЙ ИНСТИТУТ

МАТЕМАТИЧЕСКИЕ МОДЕЛИ И АЛГОРИТМЫ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ РАСПРЕДЕЛЕННЫХ БАЗ ДАННЫХ

Специальность 05.13.16 Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях

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

Румянцева Инна Ивановна

ДИССЕРТАЦИЯ на соискание ученой степени кандидата технических наук

Научный руководитель: доктор технических наук, профессор В.Д. Киселев

Тула 1999

СОДЕРЖАНИЕ

стр.

Введение..................................................................................................................4

1.АНАЛИЗ ПРИМЕНЕНИЯ МЕТОДОВ ОПТИМИЗАЦИИ ДЛЯ РЕШЕНИЯ ЗАДАЧ ПРОЕКТИРОВАНИЯ РАСПРЕДЕЛЕННЫХ БАЗ ДАННЫХ

1.1 Этапы, задачи и методы проектирования РБД..................................13

1.2. Математические модели оптимизации параметров логической структуры РБД............................................................................................21

1.2.1. Выбор и обоснование показателя эффективности функционирования РБД...................................................................................21

1.2.2. Оптимизация распределения ИМ по узлам ВС по критерию суммарного среднего времени обработки запросов пользователей.......................................................................................................33

1.2.3. Определение оптимального состава оперативного резерва информации в РБД..............................................................................40

1.3. Математические модели оптимизации параметров физической структуры РБД.-...........................................................................................44

1.4. Особенности комбинаторных методов оптимизации и пути повышения их эффективности.........................................................................53

Выводы...................................................................................................................57

2.ПРИМЕНЕНИЕ ТЕОРИИ ДВОЙСТВЕННОСТИ В МЕТОДЕ ВЕТВЕЙ И ГРАНИЦ И ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

2.1. Предварительное сокращение размерности задачи на основе теории двойственности...........................................................................59

2.2. Способы оценки границ решения при использовании теории двойственности........................................................................................63

2.3. Определение порядка ветвления переменных и оценка границ решения задачи целочисленного программирования с булевыми переменными....................................................................................................72

2.4. Применение разрешающих множителей модифицированного симплекс-метода для повышения эффективности метода ветвей и границ...............................................................................................................77

2.5. Применение теории двойственности в методе встречного решения функциональных уравнений динамического программирования.......82

Выводы...................................................................................................................89

3 .ЭКСПЕРИМЕНТАЛЬНАЯ ОЦЕНКА МЕТОДОВ ОПТИМИЗАЦИИ НА ОСНОВЕ РАЗРАБОТАННОГО ПАКЕТА ПРИКЛАДНЫХ ПРОГРАММ

3.1. Экспериментальная оценка эффективности методов и алгоритмов оптимизации.............................................................................................90

3.2.Практические рекомендации по оптимизации параметров структуры РБД специального назначения.............................................113

Выводы.................................................................................................................126

Заключение..........................................................................................................128

Литература...........................................................................................................131

Приложения...............................................................................141

Приложение 1.....................................................................142

Приложение 2.....................................................................168

Приложение 3.....................................................................174

Введение.

Ключевой проблемой современной теории управления является оптимизация. Решение этой проблемы требует разработки и практического применения методов оптимизации, основанных на использовании последних достижений в области новых информационных и компьютерных технологий. Среди прикладных задач оптимизации важное место занимают задачи дискретного программирования. Большинство задач этого типа (коммивояжера, классическая задача теории расписаний, задача о раскраске, об оптимальном покрытии, о максимальном разрезе, о ранце и ряд других) являются универсальными задачами целенаправленного перебора и относятся к числу NP-сложных. Для их решения до настоящего времени не найдены эффективные алгоритмы, трудоемкость которых полиномиально зависела бы от размерности задачи[1-8]. Поэтому остается актуальной задача дальнейшего совершенствования и модификации алгоритмов решения, разработки их современного программного обеспечения.

Среди общих методов дискретного программирования [9-13] можно выделить три основных: отсечения, ветвей и границ, динамического программирования.

Идейно наиболее простым является метод отсечения. Однако, он обладает существенными недостатками: нерегулярность вычислительной процедуры и плохая сходимость к целочисленному решению. Первым примером реализации метода отсечения служат известные алгоритмы Р.Гомори [14]. В работах Колоколова A.A. [15-18] развивается новый подход к анализу метода отсечения и задач целочисленного линейного программирования, в основе которого лежит идея исследования эффективности алгоритмов с помощью специальных разбиений допустимой области соответствующей непрерывной задачи. В терминах такого разбиения определяется "объем" отсекаемой части (дробного накрытия) и глубина отсе-

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

Введение более одного дополнительного ограничения на каждом шаге итерации (как в методе отсечения) приводит к построению дерева возможных вариантов, оценке для каждой вершины границы решения, отбрасыванию бесперспективных вершин. Все перечисленные особенности легли в основу метода ветвей и границ, идея которого впервые была сформулирована в известном алгоритме А.Лэнд и А.Дойг для решения задачи ЦЛП [19]. Широкую популярность метод получил после его применения Д.Литтлом, К.Мурти, Д.Суини, С.Кэрэл к решению задачи коммивояжера [20].

Метод ветвей и границ [21] сравнительно легок в применении: он не требует для своей реализации большого объема машинной памяти; его вычислительная схема проста и хорошо обозрима; конечность вычислений, как правило, не нуждается в доказательстве. Однако, решение многих практических задач большой размерности с помощью алгоритмов данного метода проблематично, так как экспериментальные оценки трудоемкости этих алгоритмов имеют экспоненциальную зависимость от размеров решаемых задач.

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

линейного программирования, неопределенных множителей Лагранжа, градиентные методы и, прежде всего, метод динамического программирования.

Метод динамического программирования был разработан Р.Беллманом [22], связан с работами А.А.Маркова и А.Вальда. Он основан на принципе оптимальности, который используется также в методе последовательного анализа вариантов В.С.Михалевича [23] и локальных вариаций Н.Н.Моисеева [24]. К положительным сторонам этого метода следует отнести: возможность решения вариационных задач с ограничениями-неравенствами и конечномерных экстремальных задач с дискретной структурой, упрощение поиска оптимальных решений задач комбинаторного типа за счет резкого сокращения объемов вычислений. В то же время, метод обладает рядом недостатков, таких как: отсутствие универсального алгоритма, пригодного для решения различных типов задач (алгоритмы, используемые в рамках динамического программирования, объединены лишь общей идеей и в каждом конкретном случае должны формироваться применительно к условиям задачи), большие трудности при решениии многомерных задач.

Существенно повысить эффективность методов ветвей и границ и динамического программирования и преодолеть их недостатки позволяет теория двойственности [25-31].

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

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

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

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

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

Методы оптимизации эффективно применяются в самых различных областях человеческой деятельности, особенно, при проектировании больших технических систем, к которым можно отнести вычислительные сети[32-39], распределенные банки и базы данных[40-42].

Вопросам проектирования структур распределенных баз данных посвящено большое количество работ известных авторов: Кульба В.В., Ма-миконов А.Г., Цвиркун А.Д.,Ужастов И.А., Якубайтис Э.А. [43-47].

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

для разработки логических и физических структур РБД недостаточно формализован и базируется, в основном, на использовании опыта и интуиции разработчиков, что не позволяет оптимизировать процессы проектирования и функционирования РБД.

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

В настоящее время, несмотря на многообразие моделей и методов проектирования распределенных баз данных, отсутствует единый комплекс взаимосвязанных формализованных моделей и методов анализа и синтеза оптимальных по заданным критериям эффективности логических структур РБД, локальных БД и сетевых каталогов, позволяющих автоматизировать процесс проектирования РБД на всех основных этапах их разработки. Реализация формализованных моделей и методов, пакетов прикладных программ (ППП) и систем автоматизированного проектирования представлена в настоящее время ограниченным числом разработок БД [4854], отдельных процедур проектирования РБД [55-62].

В работах отечественных [55,63,64] и зарубежных авторов [57, 5861] исследуются вопросы проектирования отдельных компонентов логического уровня РБнД, разработка которых осуществляется независимо, что приводит к существенному снижению эксплуатационных характеристик РБД.

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

информации и процедур ее обработки; многообразием критериев эффективности; ограничениями СУРБД, СУБД, операционных систем и технических средств; недостаточной разработкой используемых формальных методов проектирования.

Практика разработки логических структур РБД базируется на использовании эвристических методов проектирования рациональных и формализованных методов проектирования оптимальных логических структур РБД [45, 46, 52, 53, 55, 59-61, 65].

Большинство разработанных в настоящее время моделей синтеза логических структур РБД основывается на исследовании задач размещения баз данных или информационных массивов и программ по узлам вычислительной сети заданной конфигурации [55, 59-62], которые решаются с использованием методов целочисленного линейного [59, 60], нелинейного [58, 61], квадратичного [62] и динамического [66] программирования. В качестве элементов размещения используются базы данных или информационные массивы, структуры которых, в отличие от моделей [43, 46, 65, 67, 68], не оптимизируются.

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

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

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

Поставленная цель достигается решением ряда взаимосвязанных задач:

- разработка моделей оптимизации параметров логической структуры РБД;

- разработка моделей оптимизации параметров физической структуры РБД;

- совершенствование алгоритмов и методов решения задач оптимизации и оценка их эффективности.

Содержание этих решений изложено в трех главах настоящей работы.

В первой главе рассматриваются этапы и задачи проектирования РБД, проводится анализ и уточнение системы математических моделей оптимизации параметров логической и физической структур РБД, включающей: модель оптимизации распределения информационных массивов по узлам вычислительной сети по критерию суммарного среднего времени обработки запросов пользователей, модель оптимизации состава оперативного резерва информации в РБД по критерию суммарного среднего времени обработки запросов пользователей, модель оптимизации размещения экземпляров логических записей по страницам информационных массивов(ИМ) по критерию затраченной памяти при синтезе страниц массивов, модель оптимизации распределения логических массивов по типам памяти по критерию суммарного среднего времени доступа к ИМ. Показа-

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

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