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



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

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

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


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

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

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

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


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

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

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