Geum.ru

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

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

Содержание


7. Заключение. Некоторые полученные результаты и задачи для дальнейшего решения
Подобный материал:
1   2   3   4   5   6   7

7. Заключение.

Некоторые полученные результаты и задачи для дальнейшего решения


Итак, основную тему данной статьи можно немного упрощённо сформулировать как применение динамических функций риска и смежных эвристик в различных задачах дискретной оптимизации.

К сожалению, конкретные результаты счёта для большинства из изложенных выше ЗДО, а также их численные сравнения с работами предыдущих авторов, опубликованы только во «внутренних» публикациях Ульяновского государственного университета.48 Основная причина того, что вопросы применения эвристических алгоритмов не интересуют большинство журналов, посвящённых дискретным математическим наукам, уже была отмечена автором в [7]; повторим эту мысль ещё раз. В связи с наличием многих эвристик, желательность применения которых практически невозможно доказать строго, статьи на данную тему часто критикуются «чистыми математиками». И, к сожалению, в настоящее время подобная ситуация прослеживается практически во всех областях искусственного интеллекта.

Однако для некоторых задач (прежде всего – для упомянутых во введении) имеются и соответствующие публикации в центральных российских и зарубежных изданиях.49 А именно, очень краткое изложение некоторых разделов данной статьи (в виде тезисов) приведено в [12]. В каждой из работ [28–33], посвящённых, прежде всего, формулировке различных «неэвристических» алгоритмов минимизации НКА, имеются замечания и сноски про возможное применение в этих задачах эвристик.50 Возможные подходы к программированию недетерминированных игр, а также полученные результаты, приведены в [7,11]. О применении функций риска в краткосрочном прогнозировании различных экономических параметров, прежде всего – курсов валют, см. в [8–10]. Первые результаты решения задачи оптимизации БФМ-сигналов приведены в [5], в настоящее время в печать сдана статья о применении в этой задаче ДФР. Авторские подходы к решению ЗКВ приведены в [13]; очень важно отметить, что в той статье было описано применение ДФР в ЗКВ не только для МВГ, но и для другого подхода, связанного с т.н. алгоритмами мультиагентной оптимизации. Однако в связи с ограничениями на объём статьи не будем приводить здесь сравнение результатов авторских алгоритмов с имевшимися ранее – см. подробнее [13].

Итак, основная тема статьи – применение ДФР в различных ЗДО. Однако во всех предыдущих публикациях вид этих функций выбирался только согласно результатам самообучения – например, аналогично [7]. В настоящее время сдана в печать работа о виде этих функций в произвольном случае; конечно, при этом ставятся требования выполнения всех необходимых условий на эти функции. Некоторые из этих условий уже были отмечены в [7,13]; среди условий, не отмеченных в этих работах, упомянем, например, необходимость сходимости последовательности значений после нескольких применений ДФР – при любых допустимых значениях набора усредняемых с помощью ДФР значений.

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

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

В заключение статьи отметим следующий интересный факт. Применяя описанные выше эвристики в самых разных ЗДО, автор статьи при достаточно больших размерностях задач не получил ни одного примера, когда бы оптимальное решение получалось бы более чем за 5% от времени, необходимого для общего решения задачи. Этот факт косвенно свидетельствует в пользу всех описанных эвристик – причём даже в том случае, когда само оптимальное решение неизвестно, поскольку не может быть получено за приемлемое время.