Geum.ru

Б. Ф. Мельников (Тольяттинский государственный университет, B. Melnikov@tltsu ru, bormel@mail ru) Аннотация Внастоящей статье рассматриваются эвристические методы принятия решений в различных задача

Вид материалаЗадача

Содержание


4. Об одном подходе к оценкам эффективности эвристических алгоритмов
5. Применение генетических алгоритмов. Турнирное самообучение как старт незавершённого метода ветвей и границ
Подобный материал:
1   2   3   4   5   6   7

4. Об одном подходе к оценкам эффективности эвристических алгоритмов


Автор убеждён, что при сравнении эффективности двух эвристических алгоритмов, решающих одну и ту же ЗДО, совершенно не уместны сложные математические теории, в частности, теория сложности алгоритмов. Поэтому в предыдущих публикациях автора (некоторые из них приведены ниже в списке литературы, остальные цитируются в этих работах) специально опущены вопросы сложности тех алгоритмов, которые явно приводятся в этих работах или могут быть легко описаны на основе доказываемых там утверждений. Применительно, например, к вышеупомянутым задачам минимизации НКА это делается в связи со следующими обстоятельствами. (Отметим заранее, что каждый из приведённых аргументов легко переносится на случай любой другой задачи дискретной оптимизации.)
  • Функции разметки состояний и их таблицы соответствия [28], а также специальные бинарные отношения [30,32] при практическом программировании строятся в этих алгоритмах одновременно, одни из них применяются для быстрого построения других – поэтому применение стандартных методов оценки сложности в данном случае весьма затруднительно.
  • Формулы, полученные стандартным образом, согласно стандартным методам оценки сложности алгоритмов ([2–4] и мн.др.) в случае таких сложных объектов, которыми являются НКА, обязательно «включают комбинаторный взрыв» – и, следовательно, вряд ли представляют интерес для задач практического программирования. (А ведь именно для подобных задач и разрабатываются методы оценки сложности алгоритмов.)
  • Более того, существует много задач, в которых стандартные методы оценки сложности алгоритмов дают результаты, фактически противоречащие получаемым на практике. Среди многочисленных известных автору подтверждающих примеров приведём два наиболее показательных. Во-первых, при построении эвристических алгоритмов проверки эквивалентности двух состояний некоторого заданного НКА26 могут решаться подзадачи определения, существует ли выходное слово, допускаемое обоими данными состояниями, и существует ли слово, допускаемое ровно одним из этих состояний. При практическом программировании вторая из этих подзадач значительно проще (этот факт кажется очевидным) – однако формальные оценки сложности соответствующих алгоритмов дают обратный результат.27 Во-вторых, при построении по заданному НКА эквивалентного регулярного выражения28 возникает подзадача оптимального упорядочения вершин рассматриваемого НКА, рассматривающая всевозможные циклы между этими вершинами. Согласно классическим методам оценки сложности алгоритмов, число этих циклов факториально зависит от числа вершин – отсюда можно получить, что и любой эвристический алгоритм решения данной задачи имеет не менее чем факториальную сложность. Однако такая же факториальная оценка сложности получается и при самом тривиальном, переборном методе решения задачи. Итак, при «одинаковых» оценках в реальных условиях, конечно, переборный алгоритм абсолютно неприемлем, а эвристический даёт неплохие практические результаты.

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

Кроме того, в каждой из ЗДО возникают вопросы, схожие с поставленным выше в одной из сносок раздела 2: что такое «в среднем» для некоторого алгоритма? к каким именно объектам в рассматриваемой ЗДО нужно применять два или более сравниваемых алгоритма? Применительно к задачам минимизации НКА эти вопросы можно переформулировать так: необходимо описать некоторую процедуру генерации автоматов и показать, что исследуя именно такие автоматы для нужных задач и применяя к ним именно эти эвристические алгоритмы, можно получить хорошие результаты в реальных прикладных задачах минимизации (например, в подзадачах теории трансляции). Для этого можно, например, описать некоторые «внутренние» свойства автоматов и показать, что «реальные» НКА, встречающиеся в конкретных прикладных задачах (при описании вспомогательных грамматических структур языков программирования, в LR-анализе и др.) «чаще всего» обладают именно этими свойствами. Однако в настоящей статье мы не будем рассматривать вопросы, поставленные в этом абзаце.

В заключение раздела стоит отметить, что автор не считает материал этого раздела чем-то новым (как и материал раздела 2, т.е. описание незавершённого МВГ). Просто, по мнению автора, в современных публикациях, посвящённых алгоритмам для решения ЗДО, неоправданно большое внимание уделяется оценкам сложности этих алгоритмов – в ущерб публикациям каких-либо статистических результатов их работы. Последние же, к сожалению, гораздо чаще удаётся находить не в научных публикациях, а на интернетовских страницах.

5. Применение генетических алгоритмов.

Турнирное самообучение как старт незавершённого метода ветвей и границ


Как уже было сказано в разделе 3, и в завершённом, и в незавершённом алгоритмах МВГ нам необходимо воспользоваться тем фактом, что в разных конкретных подзадачах одной и той же ЗДО относительно лучше работают разные эвристики. Раздел 3 был посвящён краткому описанию авторских алгоритмов принятия решений в случае наличия нескольких программ-экспертов – нескольких предикторов. Мы кратко упоминали там и об усреднении, которое делается с помощью набора коэффициентов – но, в основном, раздел 3 было описано использование динамических функций риска.

Однако совсем без набора коэффициентов для усреднения результатов, возвращаемых различными предикторами, обойтись невозможно. Простейший аргумент приведём на основе ЗКВ. Первый из предикторов, описанный в точности на основе [4], упорядочивает нули приведённой матрицы по сумме минимумов в строке и столбце рассматриваемого нуля; т.е. можно сказать, что «единицы измерения» этого предиктора суть единицы стоимости проезда. Второй из ранее упомянутых в разделе 3 предикторов – это количество строк и столбцов, в которых содержится более одного нуля; поэтому «единицы измерения» здесь другие. Даже этот простейший пример показывает необходимость введения коэффициентов для усреднения результатов предикторов. И также в разделе 3 было отмечено, что иногда, в предыдущих работах по использованию МВГ в различных ЗДО, авторы действительно использовали несколько эвристик одновременно.

Однако результат использования такого множества эвристик – т.е. выбор конкретного разделяющего элемента матрицы стоимостей для ветвления с использованием бэктрекинга – в известных автору алгоритмах всегда считался на основе суммы результатов этих разных эвристик, умноженных на заранее заданный набор весовых коэффициентов. Эти коэффициенты каким-то образом подбирались для организации наилучшей работы МВГ – однако автору не известно работ, в которых бы исследовались вопросы автоматизированного выбора этих коэффициентов. Именно эти коэффициенты усреднения являются предметом самообучения в данной статье, т.е. предметом применения генетических алгоритмов (ГА). Более того, стоит специально отметить: в отличие от всех известных автору вариантов применения ГА в ЗКВ, предметом самообучения ГА в нашем случае является не выбор маршрута для конкретной, одной, заданной ЗКВ – а набор-геном коэффициентов для целого класса однотипных задач.

Автор в своих программах, написанных для использования незавершённого МВГ в различных ЗДО, использовал собственные модификации ГА для стартового выбора набора таких коэффициентов.29 В качестве посылки для организации процесса вычисления оптимального набора-генома коэффициентов была принята следующая очевидная цель: создать алгоритм, зависящий от этих коэффициентов, при которых случайно сгенерированная матрица стоимостей была бы посчитана в среднем за наименьшее время. При этом указанный набор коэффициентов (геном) должен быть выбран за ограниченное время – имеющееся в распоряжении исследователя. Важно отметить, что такой выбор оптимального набора-генома коэффициентов производился только для старта некоторого вычислительного процесса, а в процессе работы алгоритма такие наборы коэффициентов модифицируются30 – т.е. выбираются в зависимости от текущей ситуации в самой задаче.

Однако у описываемого метода имеются следующие две проблемы. Во-первых, применение самообучения коэффициентов при работе такого сложного алгоритма, как МВГ с несколькими эвристиками, вряд ли сможет быстро дать хорошие результаты: связь между набором коэффициентов и конкретным рассматриваемым вариантом некоторой ЗДО, конечно же, существует, но вряд ли может быть быстро найдена. Во-вторых, сравнение двух наборов коэффициентов может быть хорошо произведено только при наличии системы тестов с заранее известными результатами31; в реальных же условиях такие системы тестов имеются только для самой известной из рассматриваемых задач, а именно ЗКВ – а для других вышеупомянутых ЗДО их получение часто весьма затруднительно.

Обе упомянутые проблемы кажутся мало связанными друг с другом; более того, для решения этих проблем применяются две разные эвристики. Кратко первая из этих эвристик может быть описана как применение вместо МВГ упрощённого жадного алгоритма, который был ранее (в разделе 2) назван под-алгоритмом построения ППЗ, а вторая эвристика – как сравнение работы ровно двух32 наборов коэффициентов на случайно сгенерированном варианте ЗДО; но это очень краткая характеристика, ниже мы опишем данные эвристики немного подробнее. Итак, обе упомянутые проблемы и обе эвристики кажутся мало связанными друг с другом; однако на самом деле связь существует (практика решения самых разных ЗДО показала, что одна из этих двух эвристик без другой не даёт заметных результатов) – поэтому можно сказать, что две вышеупомянутые проблемы решаются автором в различных задачах дискретной оптимизации с помощью одного общего подхода. Этот подход был взят из игрового программирования,33 отсюда и его название – турнирное самообучение; но он не менее удачно может применяться практически в любой ЗДО.

Суть подхода заключается в следующем. Из множества наборов-геномов коэффициентов, каждый из которых (наборов) представляет собой один из объектов самообучения, выбираются некоторые два – и между ними проводится т.н. «матч». Каждый матч заключается в том, что для каждого из нескольких случайно сгенерированных вариантов рассматриваемой ЗДО34 применяется один и тот же упрощённый алгоритм её решения – а именно, для исходной ЗДО формируется ППЗ, описанная выше в разделе 2. Далее для двух вариантов одного и того же алгоритма с разными наборами-геномами коэффициентов (или, что то же самое – двух разных алгоритмов, «участников турнира набора коэффициентов») запоминается:
  • либо информация о том, на каком из наборов получено относительно лучшее решение,
  • либо отношение границ, полученных при применении описанных жадных алгоритмов

(возможны и некоторые другие варианты) – в зависимости от конкретного способа реализации алгоритма турнирного самообучения.

Из подобных «сыгранных матчей» формируется «турнир»; некоторые из возможных «систем проведения турниров» были кратко описаны в [7]. Выбор худших наборов-геномов (объектов самообучения) для их последующей замены с помощью стандартных (и нестандартных) генетических операторов происходит именно на основе результатов турнира. При этом мы избавляемся от необходимости иметь систему тестов – т.е. набор конкретных задач рассматриваемой ЗДО. Очень важно отметить, что при этом также нет необходимости применять некоторую конкретную случайно сгенерированную ЗДО ко всем наборам коэффициентов. А такое применение, хоть и кажется на первый взгляд оправданным, на практике могло бы привести к самым разным проблемам. Одна из них – необходимость применения каких-либо специальных алгоритмов теории принятия решений, аналогичных, например, описанным в [6], либо в одной из предыдущих публикаций автора данной статьи. Другая проблема – необходимость динамической генерации системы тестов (как было упомянуто, в большинстве задач подобные системы тестов априори отсутствуют), поскольку объекты самообучения сменяются в процессе работы алгоритма постепенно.

Конечно же, легко показать, что сама по себе описанная эвристика («жаднейшая», т.е. «более жадная», чем обычный незавершённый МВГ) крайне редко может дать результат, приемлемый для anytime-алгоритмов. Например, практически любой из примеров книги [4] является подтверждением этой мысли; кроме того, разделы 2 и 3 настоящей статьи описывают значительно более эффективные алгоритмы. Однако автор применяет результаты турнирного самообучения не сами по себе, а в качестве старта для незавершённого МВГ, точнее – для продолжения самообучения наборов коэффициентов уже в более сложном случае. Другими словами – для применения того же самого набора-генома для более сложных целей – одновременного использования различных эвристик при выборе очередного шага МВГ (это было подробно описано в разделе 3), т.е. фактически, после дальнейшего обучения уже для самого МВГ – для окончательных, итоговых версий anytime-алгоритмов.

Действия, подобные описанным в предыдущем абзаце, можно сравнить с многократно описанным в литературе применением между двумя шагами процесса работы ГА некоторого «чужого» шага – например, с применением одного шага градиентного спуска при решении генетическими алгоритмами системы линейных алгебраических уравнений.35 Однако отметим, что эта аналогия, как уже несколько раз было выше, несколько упрощает реальную ситуацию, т.е. применение турнирного самообучения в качестве старта для МВГ значительно сложнее.

В заключение раздела отметим, что из-за ограничений на объём статьи мы практически не коснулись самих алгоритмов модификации наборов-геномов – т.е. того, что некогда считалось главным вопросом ГА. Однако, возможно, это и не является недостатком статьи: по мнению автора, описание конкретных алгоритмов модификации в настоящий момент уже не представляет большого интереса – и выбор таких алгоритмов (например, среди многих описанных в литературе за последние несколько лет) полностью ложится на разработчика алгоритма и интересен лишь ему. В этом разделе были рассмотрены не алгоритмы модификации наборов-геномов, а общие вопросы применения ГА среди других эвристик при решении ЗДО.