авторефераты диссертаций БЕСПЛАТНАЯ РОССИЙСКАЯ БИБЛИОТЕКА - WWW.DISLIB.RU

АВТОРЕФЕРАТЫ, ДИССЕРТАЦИИ, МОНОГРАФИИ, НАУЧНЫЕ СТАТЬИ, КНИГИ

 
<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:   || 2 | 3 | 4 |

Локальные элиминационные алгоритмы для разреженных задач дискретной оптимизации

-- [ Страница 1 ] --

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

ЩЕРБИНА Олег Александрович

ЛОКАЛЬНЫЕ ЭЛИМИНАЦИОННЫЕ АЛГОРИТМЫ ДЛЯ

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

05.13.17 – теоретические основы информатики

АВТОРЕФЕРАТ

диссертации на соискание ученой степени

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

Москва – 201…

Работа выполнена в Таврическом национальном университете

им. В.И. Вернадского (г. Симферополь, Украина)

Официальные оппоненты: доктор физико-математических наук,

профессор,

Владимир Алексеевич Емеличев

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

профессор,

Юрий Анатольевич Зуев

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

профессор,

Николай Николаевич Кузюрин

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

кибернетики Московского государственного

университета им. М.В. Ломоносова.

Защита диссертации состоится …. ………. 201… г. в ….-00 час.

на заседании диссертационного совета Д 002.017.02 в Учреждении

Российской академии наук Вычислительный центр имени

А.А.Дородницына РАН по адресу:

119333, г. Москва, ул. Вавилова, д.40.

С диссертацией можно ознакомиться в библиотеке ВЦ РАН.

Автореферат разослан “ “ _____________ 201… г.

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

совета Д 002.017.02, д.ф.-м.н., профессор В.В. Рязанов

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

Актуальность темы.

Методы исследования дискретных структур играют все более важную роль в современных приложениях математики.

Использование моделей и алгоритмов дискретной оптимизации (ДО) позволяет решать многие практические задачи, такие, как задачи теории расписаний, оптимизации на сетях, маршрутизации трафика в коммуникационных сетях, задачи размещения экономических объектов, задачи оптимизации автоматизированных систем планирования ресурсов (ERP), задачи логистики, в частности, оптимизацию цепочек предложения (Supply Chain Management), доказательство теорем, задачи искусственного интеллекта и робототехники и т. п. Это обусловлено тем, что дискретные оптимизационные модели адекватно отражают нелинейные зависимости, неделимость объектов, учитывают ограничения логического типа и всевозможные технологические, в том числе и имеющие качественный характер, требования. К сожалению, большинство интересных задач ДО являются NP-трудными и решение их в худшем случае может требовать построения дерева поиска решений экспоненциального размера. Многие практические задачи ДО содержат огромное число переменных и/или ограничений, что создает сложности при попытке решения этих задач с помощью современных решателей.

А. Н. Колмогоров отмечает [2, с.28]: «Весьма вероятно, что с развитием современной вычислительной техники будет понято, что в очень многих случаях разумно изучение реальных явлений вести, избегая промежуточный этап их стилизации в духе представлений математики бесконечного и непрерывного, переходя прямо к дискретным моделям. Особенно это относится к изучению сложно организованных систем, способных перерабатывать информацию».

В настоящее время среди наиболее перспективных направлений исследований в дискретной оптимизации можно выделить следующие подходы:

1) разработка эффективных вычислительных алгоритмов (как точных, так и приближенных) для решения задач ДО.

2) поиск специальных классов задач ДО, на которых хорошо работают те или иные алгоритмы;

3) теоретический анализ сложности и трудоемкости алгоритмов ДО.

4) разработка и исследование алгоритмов ДО с эффективным распараллеливанием вычислений.

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

1) комбинаторные методы, в том числе:

1.1) методы ветвей и границ, методы ветвления и отсечения;

1.2) локальные алгоритмы Ю. И. Журавлева [2];

1.3) метод последовательного анализа и отсеивания вариантов, предложенный В. С. Михалевичем и Н.З. Шором [3];

1.4) последовательностные схемы В. А. Емеличева [4];

1.5) аппроксимационно-комбинаторный метод [5];

1.6) метод динамического программирования [6];

2) приближенные методы;

3) эвристические подходы (табу, генетические алгоритмы, метод отжига (simulated annealing) и др.), мета-эвристические методы (см. [11]).

4) методы глобальной оптимизации для решения задач смешанного нелинейного целочисленного программирования [ 8, 9].

5) декомпозиционные методы.

6) другие методы, в том числе методы отсечения; теоретико-групповые методы; гибридные методы [9].

Следует особо выделить весьма общие и эффективные при решении ряда конкретных прикладных задач дискретной оптимизации схемы, такие как метод последовательного конструирования, анализа и отсева вариантов В. С.  Михалевича [3], общая схема глобального равновесного поиска (И. В. Сергиенко, В. П. Шило [10]), последовательностные схемы В. А. Емеличева [4], локальные алгоритмы Ю. И. Журавлева [2].

Хотя возможности построения полиномиальных точных алгоритмов решения задач дискретной оптимизации общего вида и представляются сомнительными [11], тем не менее, в последнее время наблюдается потребность в построении и анализе точных алгоритмов, существенно более быстрых, чем полный перебор, но пока еще не полиномиальных (так называемых супер-полиномиальных алгоритмов, с помощью которых находятся оптимальные решения NP-полных задач [12]).

Не останавливаясь подробно на приближенных методах решения задач дискретной оптимизации, заметим, тем не менее, что в основе многих приближенных методов лежит идея локального поиска. Достаточно эффективными показали себя такие приближенные алгоритмы локального поиска, как метод глобального равновесного поиска [11] – развитие метода вектора спада, разработанного И. В. Сергиенко и его учениками [13], локально-стохастические алгоритмы [14-16]. Результаты многочисленных вычислительных экспериментов для множества задач дискретной оптимизации с использованием алгоритма глобального равновесного поиска доказывают перспективность этого метода [11].

Общая теория локальных алгоритмов для решения ряда важных задач дискретной математики была развита Ю. И. Журавлевым [2]. Идея локального алгоритма основана на введении понятия «близости», на основе которого определяется окрестность элемента, т. е. множество элементов, «близких» к данному. Локальный алгоритм на каждом шаге изучает окрестности элементов (а не все элементы множества) и накапливает о них информацию, которая затем используется на последующих шагах алгоритма. Отметим, что в методе вектора спада и локально-стохастическом алгоритме используются окрестности решений задачи ДО. Алгоритмы локального поиска (называемые по-другому алгоритмами с окрестностями (neighborhood search algorithms)) [17] на каждой итерации находят улучшенное решение путем поиска в окрестности текущего решения. Эффективность подобных методов существенно зависит от способа выбора окрестности решения. К подходам, использующим локальный поиск, относятся методы отжига, табу, меметические алгоритмы. Дальнейшее развитие методы локального поиска получили в метаэвристических методах [16], [18], в которых локальный поиск используется совместно с эвристическими алгоритмами, такими как, например, алгоритм муравьиных колоний [19] и генетический алгоритм [ 20].

Теоретические основы для ускорения процесса решения сложных задач ДО предложены в [ 10], где описана РЕСТАРТ-технология, основанная на использовании РЕСТАРТ-распределения и РЕСТАРТ-критерия останова алгоритма.

В последнее время интересные результаты были получены в теории удовлетворения ограничений (Constraint Satisfaction) [21], находящейся на пересечении искусственного интеллекта и информатики.

Одним из наиболее перспективных подходов к решению задач дискретной оптимизации является построение гибридных (комбинированных) методов, основанных на сочетании и взаимодействии в рамках нового метода двух или более известных методов. Важные теоретические исследования, служащие основой для дальнейшего развития гибридных алгоритмов [9], проведены в известных работах Ю. И. Журавлева [22].

Ряд подходов из теории удовлетворения ограничений [21, 64] может быть использован при создании гибридных алгоритмов ДО и глобальной оптимизации [7].

Поскольку разработка эффективных точных алгоритмов для решения задач дискретной оптимизации общего вида, как отмечено выше, представляется сомнительной, то имеет смысл исследовать более узкие классы задач и строить более эффективные методы, основанные на изучении особенностей частных подклассов задач. Следует отметить, что успехи, достигнутые к настоящему времени в теории и практике ДО достаточно часто были связаны именно со специальной структурой задач ДО. Действительно, хорошие результаты получены при решении задач ДО, обладающих специальной структурой (так, методы отсечения успешно применялись при решении задач о покрытии, последовательностные схемы В. А. Емеличева особенно хорошо работают при решении задач о размещении, высокая эффективность метода ветвей и границ достигается при решении задач с ограничениями специального вида, например, многократного выбора [23]), градиентные алгоритмы хорошо работают на матроидах [ 24] и т. д.

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

Понимание принципиального характера трудности решения задач дискретной оптимизации стимулировало интенсивное развитие теории сложности [25 28]. Одной из наиболее важных теоретических проблем в теории сложности является известная проблема «P=NP?». В теории сложности используются в числе прочих понятия временнй и емкостной сложности алгоритма. Грубо говоря, под временнй сложностью понимается время работы алгоритма (оцениваемое числом шагов), под емкостной сложностью объем памяти, необходимый алгоритму для решения задачи.

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

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

Отметим работы В. А. Емеличева [29], в которых сложность решения задачи линейного программирования оценивается косвенно, путем нахождения диаметра многогранника допустимых решений.

В связи о вышесказанным приобретает особую актуальность разработка в ДО декомпозиционных подходов [30 40].

Как известно, метод декомпозиции впервые был использован для решения задач смешанного целочисленного программирования в [41], позднее были развиты и другие методы декомпозиции. Принцип декомпозиции Данцига-Вулфа для задач ЛП имеет аналог в целочисленном программировании [40]. Этот подход использует мастер-задачу целочисленного ЛП (ЦЛП), которая неявно решает задачу ЦЛП с большим числом переменных с помощью процедуры построения столбцов задачи ЦЛП, известную как алгоритм ветвей и оценок (branch-and-price) [42], использование которого позволило решить в последние годы большие задачи ДО.

Задачи ДО и, в частности, задачи ЦП с блочной структурой возникают естественным образом во многих приложениях [38], [ 43]. При этом блоки обычно представляют в модели отдельные объекты, либо решения в подразделениях фирмы, в техническом устройстве, либо отвечают периоду времени. Эти блоки связаны между собой ограничениями, отражающими необходимость польльзования одними и теми же ресурсами или отражающими взаимосвязь решений для всей компании, технического процесса или периода планирования. В качестве примеров можно привести составление расписаний для транспортных средств [ 44], задачи в области телекоммуникаций [43], [ 45], в том числе задачи оптимального назначения радиочастот [46], задачи стохастического целочисленного программирования [47]. Блочную структуру имеют задачи оптимизации многопродуктовых потоков [48]. Следует упомянуть также множественную задачу о ранце [49], блоки которой являются задачами о ранце, а связывающие блоки ограничения являются неравенствами упаковки и разбиения множества. Задачи ЦЛП блочного типа были получены в результате моделирования системы туризма [65].

Перспективными декомпозиционными методами, использующими разреженность матрицы ограничений задач ДО, представляются локальные элиминационные алгоритмы (ЛЭА) [66], включающие локальные алгоритмы декомпозиции [62], [67], алгоритмы несериального динамического программирования (НСДП) [50], [69], алго­ритмы сегментной элиминации [51]. Для выделения специальных структур задач ДО представляются перспективными такие графовые декомпозиционные подходы, как методы древовидной декомпозиции (ДД) [52], [70]. Несмотря на обширную библиографию по этой тематике за рубежом, в отечественной литературе публикаций по ДД практически нет (можно отметить лишь близкие по тематике работы по локальным алгоритмам декомпозиции [67], а также обзор [70]). Важность и актуальность указанных подходов в ДО обусловлены результатами Courcelle [53], Arnborg et al. [54], доказавших, что ряд NP-трудных задач, поставленных в монадической логике второго порядка, могут быть решены за полиномиальное время с помощью методов динамического программирования на графах, описывающих структуру задачи ДО, имеющих ограниченную древовидную ширину. Методы ДД показали свою эффективность при решении задач ДО: задач кольцевой маршрутизации, задачи коммивояжера [55], задачи оптимального назначения радиочастот1 [46].

Среди блочных структур особо выделим блочно-древовидную струк­туру, частным случаем которой является «лестничная» или квазиблоч­ная структура.

Одним из первых классов больших разреженных задач линейного про­граммирования, которые начал изучать Dantzig, был класс квазиблочных задач ЛП для динамического планирования [56]. Другие примеры квазиблочных задач ЛП для многоэтапного планирования, составления расписаний, назначений и многоэтапного структурного проектирования содержатся во множестве тестовых квазиблочных задач, опубликованных Ho & Loute [57]. Квази­блочную структуру имеют задачи оптимального резервирования гости­ничных номеров [82], аналогичные последним темпоральные зада­чи о ранце [58], получившие в последнее время применение при ре­шении задач предварительного резервирования вычислительных ресурсов в Grid Computing, задачи линейного динамического программирования [59], некоторые задачи управления трудовыми ресурсами [60], динамические модели экономики, учитывающие в явном виде фактор времени [61], задачи управления в иерархических (обычно древовидных) структурах, сетевые задачи, задачи многоэтапного стохастического программирования.

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

Отметим, что локальный элиминационный алгоритм долгое время оставался чисто теоретическим алгоритмом. В [71] впервые приводятся результаты вычислительного эксперимента по решению задач ДО с помощью локального алгоритма. В [72] приводятся результаты исследования эффективности локального алгоритма для квазиблочных задач ДО, причем была показана слабая зависимость асимптотической средней оценки эффективности локального алгоритма от эффективности алгоритма ДО, решающего подзадачи для блоков. Это объясняется тем, что средняя оценка эффективности рассматривалась на множестве всех квазиблочных структур, но, как отмечалось в [63], локальные алгоритмы эффективны для задач с ограниченной связностью блоков.

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

Цель работы. В связи с вышеизложенным основными целями диссер­та­ционной работы являются:

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

На защиту выносятся следующие результаты:



Pages:   || 2 | 3 | 4 |
 





 
© 2013 www.dislib.ru - «Авторефераты диссертаций - бесплатно»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.