Мультиэвристический подход к задачам дискретной оптимизации1



Скачать 475.48 Kb.
страница1/9
Дата17.01.2013
Размер475.48 Kb.
ТипДокументы
  1   2   3   4   5   6   7   8   9

Мультиэвристический подход к задачам дискретной оптимизации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-алгоритмов для задач дискретной оптимизации.

Перейдём к подробному описанию самих эвристических методов решения ЗДО.

  1   2   3   4   5   6   7   8   9

Похожие:

Мультиэвристический подход к задачам дискретной оптимизации1 iconЭлементы дискретной математики
П. А. Корнилов, Н. И. Никулина, Семенова О. Г. Элементы дискретной математики. Учебное пособие. Ярославль: Изд-во ягпу им. К. Д....
Мультиэвристический подход к задачам дискретной оптимизации1 iconСитуационный подход к задачам поиска текстовой информации
Здесь тоже присутствуют идеи такого рода: будет использоваться некий набор экстралингвистических отношений, и эти экстралингвистические...
Мультиэвристический подход к задачам дискретной оптимизации1 iconУрок по геометрии в 7-м классе на тему "Некоторые свойства прямоугольных треугольников"
Раздаточный материал: карточки с тестом, листы с чертежами к задачам самостоятельной работы, листы для ответов к задачам самостоятельной...
Мультиэвристический подход к задачам дискретной оптимизации1 iconЛингвистические противоречия в терминологической системе дискретной математики
Именно таким путем язык может разрешить определяющее противоречие говорящего и слушающего, которое в терминологической системе дискретной...
Мультиэвристический подход к задачам дискретной оптимизации1 iconСборник упражнений для студентов математического факультета пединститута
В сборник включены упражнения по дискретной математике. Основная цель упражнений – отработка основных понятий дискретной математики,...
Мультиэвристический подход к задачам дискретной оптимизации1 icon"Построение конечно-разностных формул на границе дискретной области счёта"
При численном решении уравнений математической физики важным становится вопрос замены непрерывной области изменения аргумента дискретной...
Мультиэвристический подход к задачам дискретной оптимизации1 iconВ. П. Голубятников известный специалист в области геометрии, топологии и их приложений к задачам математического моделирования и к обратным задачам. Он опубликовал 160 научных работ, в том числе монографию Uniqueness q
«Uniqueness questions in reconstruction of multidimensional objects from tomography-type projection data», изданную в Голландии,...
Мультиэвристический подход к задачам дискретной оптимизации1 iconПрограмма курса Дополнительные главы дискретной математики для групп 318, 319 кафедры математической кибернетики
«Дополнительные главы дискретной математики» (для студентов 3-го курса 2-го потока). В нее включены разделы, относящиеся к конечнозначным...
Мультиэвристический подход к задачам дискретной оптимизации1 iconЛичностно-ориентированный подход к обучению иностранному языку
Личностный подход к обучающимся при организации учебно– воспитательного процесса
Мультиэвристический подход к задачам дискретной оптимизации1 iconМеждународный опыт в области инклюзивного образования: Норвегия
...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org