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



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

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

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


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

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

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

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

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

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

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

  • либо информация о том, на каком из наборов получено относительно лучшее решение,

  • либо отношение границ, полученных при применении описанных жадных алгоритмов

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

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

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

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

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

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