Математические модели и алгоритмы дискретной оптимизации распределенных баз данных

Ключевой проблемой современной теории управления является оптимизация. Решение этой проблемы требует разработки и практического применения методов оптимизации, основанных на использовании последних достижений в области новых информационных и компьютерных технологий. Среди прикладных задач оптимизации важное место занимают задачи дискретного программирования. Большинство задач этого типа (коммивояжера, классическая задача теории расписаний, задача о раскраске, об оптимальном покрытии, о максимальном разрезе, о ранце и ряд других) являются универсальными задачами целенаправленного перебора и относятся к числу 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], не оптимизируются.

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

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

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

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

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

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

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

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

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

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

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

В заключении формулируются результаты работы в целом.

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

1. Система математических моделей оптимизации параметров логической и физической структур РБД.

2. Способы определения границы решения и порядка ветвления переменных в методе ветвей и границ на основе теории двойственности.

3. Способы определения границы решения и порядка ветвления переменных в методе ветвей и границ на основе, А — оценок и разрешающих множителей МС-М.

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

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

Апробация работы. Материалы диссертации докладывались, обсуждались и одобрены на VII Международной конференции «Алгебраические, вероятностные, геометрические, комбинаторные и функциональные методы в теории чисел», г. Воронеж (1995г.), III Российской международной конференции «Современные проблемы теории чисел и её приложения», г. Тула (1996г.), НТК ТВАИУ (1995г., 1997 г.), НТК ВАА им. М. И. Калинина (1996г.).

Публикации. Материалы диссертации опубликованы в НТС ТВАИУ (1994;1996г.г.), НТС ВАА им. М. И. Калинина (1996г.)| ;

Реализация. Результаты исследований реализованы в НИР «Лукошко — АН», ОКР «Бинт — Т», внедрены в учебном процессе Тульского АИИ.

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

126 Выводы.

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

2. Результаты экспериментальной оценки способов определения границ решения с использованием теории двойственности показали, что наиболее эффективным является однократное решение двойственной задачи итерационными методами, который позволяет уточнять оценки переменных и определить порядок их ветвления. Среднее время решения с применением данного способа в 7−42 раза относительно первого, в 3−13 раза относительно второго и в 1.1−2.2 раза относительно третьего способа меньше. С ростом числа ограничений и переменных задачи это преимущество возрастает.

3. Применение разрешающих множителей модифицированного симплекс-метода сокращает время решения задачи в 3.02−8.05 раза относительно алгоритма с определением верхних границ при ветвлении базисных переменных с помощью А-оценок и в 2.44−3.42 раза относительно алгоритма с определением границ симплекс-методом.

4. Упорядочивание ограничений по жесткости и включение дополнительного отсева бесперспективных вариантов по условиям метода ветвей и границ с использованием двойственной задачи в способе встречного решения дает выигрыш по времени в 2.3−14.8 раза за счет уменьшения числа решений функциональных уравнений динамического программирования (числа итераций).

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

ЗАКЛЮЧЕНИЕ

.

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

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

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

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

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

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

— оптимизация состава оперативного резерва информации в РБД по критерию минимума суммарного среднего времени обработки запросов пользователейдля параметров физической структуры РБД:

— оптимизация размещения экземпляров логических записей по страницам ИМ по критерию минимума затраченной памяти при синтезе страниц массивов;

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

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

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

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

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

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

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

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

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