Б. Ф. Мельников (Тольяттинский государственный университет, B. Melnikov@tltsu ru, bormel@mail ru) Аннотация Внастоящей статье рассматриваются эвристические методы принятия решений в различных задача
| Вид материала | Задача |
- Программа профилирующей дисциплины "теория игр и исследование операций" Содержание, 69.55kb.
- Аннотация рабочей программы дисциплины методы принятия управленческих решений По направлению, 115.63kb.
- Аннотация программы дисциплины «Методы принятия управленческих решений» Цели и задачи, 22.87kb.
- Анализ принятия управленческих решений, 54.28kb.
- Программа «Методы принятия решений». Гу-вшэ, 2010 г. Министерство экономического развития, 750.51kb.
- Аннотация рабочей программы дисциплины методы принятия управленческих решений для направления, 31.71kb.
- Автор повинен правильно оформити літературу. Удк 338., 87.87kb.
- Исследование по вопросу о коренных народах и праве на участие в процессе принятия решений, 537.75kb.
- Аннотация рабочей программы учебной дисциплины методология и методы исследований, 173.52kb.
- Электронное научное издание «Труды мгта: электронный журнал», 106.8kb.
Мультиэвристический подход к задачам дискретной оптимизации1
Б.Ф.Мельников
(Тольяттинский государственный университет,
B.Melnikov@tltsu.ru, bormel@mail.ru)
Аннотация
В настоящей статье рассматриваются эвристические методы принятия решений в различных задачах дискретной оптимизации. Целью для каждой из этих задач является построение т.н. anytime-алгоритмов (псевдо-оптимальных алгоритмов реального времени). Среди решаемых задач – классическая задача коммивояжёра и задачи минимизации недетерминированных конечных автоматов в разных постановках. Описываемые в статье методы решения данных задач строятся на основе комбинации эвристик, взятых из нескольких различных областей теории искусственного интеллекта. А именно, применяется незавершённый метод ветвей и границ; для выбора очередного шага этого метода – при наличии нескольких эвристик – применяются динамические функции риска; одновременно с функциями риска применяются и генетические алгоритмы – для подбора коэффициентов усреднения; а упрощённое самообучение генетическими методами применяется и для старта незавершённого метода ветвей и границ. Данные комбинации эвристик представляют собой специальный поход к построению anytime-алгоритмов для задач дискретной оптимизации.
1. Введение. Краткий обзор решаемых задач
В настоящей статье рассматриваются эвристические методы принятия решений в различных задачах дискретной оптимизации (ЗДО). Целью для каждой из этих задач является построение т.н. anytime-алгоритмов2 – т.е. алгоритмов реального времени, которые в каждый определённый момент работы имеют лучшее (на данный момент) решение, при этом пользователь может просматривать эти псевдо-оптимальные решения в режиме реального времени, а последовательность таких решений в пределе даёт оптимальное решение.
Построение подобных алгоритмов является одной из задач, которые могут быть объединены общей тематикой с примерным названием «Обучение нечётких систем». Автор надеется, что материал данной статьи формулирует метод построения anytime-алгоритмов для целого класса задач. Однако стоит отметить, что основная цель статьи, цель этого метода – практические вопросы построения алгоритмов, а вовсе не создание соответствующей теории.
Сначала, перед описанием применяемых методов принятия решений, перечислим сами рассматриваемые задачи, точнее – классы рассматриваемых задач.
Во-первых, классическая задача коммивояжёра (ЗКВ). Среди множества публикаций отметим классическую [4] (в ней имеется постановка задачи, а также некоторые из переборных и эвристических методов её решения), а также более современную [27]. Вообще, задаче коммивояжёра на протяжении последних десятилетий было посвящено очень много публикаций, но, конечно, проблемы остаются: какого-либо «универсального» метода решения ЗКВ просто не может существовать. В последние несколько лет авторы работ по эвристическим методам решения ЗКВ чаще других рассматривают так называемые симметричные ЗКВ – т.е. когда симметричной относительно главной диагонали является матрица стоимостей – и особенно их частные случаи, т.н. метрические ЗКВ. При этом для их решения чаще всего применяются либо различные модификации методов мультиагентной оптимизации – [20,22] и мн.др., либо фактическое сведéние работы с матрицей ЗКВ к работе с координатами городов – [18] и др. Однако, по мнению автора настоящей статьи, классический метод ветвей и границ (МВГ) может также с успехом применяться – для получения не только точного решения ЗКВ, но и различных эвристических;3 при этом сведéние задачи к работе с координатами городов не используется. Отметим, что нами рассматриваются модификации МВГ, не использующие т.н. 1-деревья [16], представляющие собой альтернативу эвристическому выбору очередного шага МВГ.4 В связи с изложенным в данном абзаце автор считает наиболее интересной т.н. псевдо-метрическую ЗКВ; более подробно см. ниже, прежде всего – в разделах 2 и 5.
Во-вторых, несколько связанных между собой задач минимизации недетерминированных конечных автоматов (альтернативные названия – конечные автоматы-распознаватели, автоматы Рабина-Скотта, автоматы Медведева; ниже – НКА). Наиболее важной из них, по-видимому, является задача вершинной минимизации – задача построения НКА, допускающего заданный регулярный язык и имеющего минимально возможное число вершин. С момента выхода книги [1] (в оригинале – 1972 г.) в описании точных алгоритмов мало что изменилось: все описанные в литературе алгоритмы являются экспоненциальными – относительно числа состояний имеющегося автомата. Последнее обстоятельство связано с тем, что все имеющиеся алгоритмы требуют построения эквивалентного канонического конечного автомата – или какой-либо аналогичной графоподобной структуры.
С точки зрения теории сложности все алгоритмы, описанные в [21,23,26], эквивалентны – однако работы автора данной статьи [28,29] формулируют подобные алгоритмы таким образом, что на их основе наиболее удобно конструировать anytime-алгоритмы для решения той же самой задачи.
Кроме этого, к задачам минимизации НКА относятся задачи дуговой минимизации автоматов ([31]; автору неизвестно каких-либо других алгоритмов решения этой задачи), а также звёздно-высотной минимизации. Описание решения последней задачи имеется только в [25], однако на основе того решения создать компьютерный алгоритм, по-видимому, невозможно. Решение этой задачи автором настоящей статьи ещё не опубликовано5, однако на основе этого решения действительно удаётся сделать работающие программы – причём как для точного решения этой задачи (при малых размерностях), так и для anytime-алгоритмов.
В-третьих, примером рассматриваемой автором задачи является классическая задача минимизации дизъюнктивных нормальных форм (ДНФ). Точные алгоритмы минимизации получены достаточно давно (и давно попали в классические учебники, например, [17]), однако созданные на их основе компьютерные программы не могут работать даже с числом переменных, равным 20, – за исключением, конечно, многочисленных тривиальных случаев. Автору неизвестны работы с описанием каких-либо anytime-алгоритмов для данной задачи – но и в случае наличия таких работ, подход, предлагаемый в настоящей статье, конечно же, может быть использован в альтернативных вариантах компьютерных программ.
В-четвёртых – известная в теории радиолокации задача построения т.н. бинарных фазоманипулированных (БФМ) сигналов с минимальными автокорреляционными свойствами. В [5]6 приводилось решение данной задачи на основе почти исключительно генетических алгоритмов, других эвристик практически не применялось. Однако к настоящему моменту автором получено некоторое улучшение результатов, описанных в [5] – путём применения тех же самых эвристик, что и в других рассматриваемых здесь задачах.
Отметим ещё, что описанные четыре группы задач не ограничивают круг задач, которые могут эвристически решаться с помощью приёмов, описанных в настоящей работе. Некоторые другие группы задач перечислены в заключении. И вообще, по-видимому, практически все прикладные ЗДО могут решаться таким образом.
Общим во всех описанных задачах являются следующие обстоятельства. Каждая из задач может быть просто решена для небольших размерностей (например – для матриц небольших размерностей в ЗКВ и в задаче вершинной минимизации конечных автоматов), но при переходе к большим размерностям7 данные задачи в реальное время невозможно точно решить даже с помощью МВГ и других эвристик. Например, задача коммивояжёра – даже в упрощённой постановке, как известно, принадлежит классу NP-полных. Более того, все описанные выше задачи минимизации НКА имеют экспоненциальную сложность – при условии, что нам действительно нужно построить эквивалентные канонические автоматы для рассматриваемого языка и его зеркального образа.8
Описываемые в статье методы решения данных задач строятся на основе комбинации эвристик, взятых из нескольких различных областей теории искусственного интеллекта. Во-первых, используется незавершённый метод ветвей и границ. Во-вторых, для выбора очередного шага этого метода при наличии нескольких эвристик применяются динамические функции риска. В-третьих, одновременно с функциями риска для подбора коэффициентов усреднения различных эвристик применяются генетические алгоритмы. В-четвёртых, упрощённое самообучение теми же генетическими методами применяется и для старта незавершённого метода ветвей и границ. Таким образом, можно сказать, что данные комбинации эвристик представляют собой специальный поход к построению anytime-алгоритмов для задач дискретной оптимизации.
Перейдём к подробному описанию самих эвристических методов решения ЗДО.