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



Скачать 475.48 Kb.
страница9/9
Дата17.01.2013
Размер475.48 Kb.
ТипДокументы
1   2   3   4   5   6   7   8   9
нескольких «генетических» шагов; заметим, что шаг градиентного метода требует значительно больше времени. Число шагов генетическими методами зависит от размерности задачи; например, при размерности сильно разрежённой матрицы системы линейных алгебраических уравнений около 200 число шагов методами ГА примерно равно 10.

Однако данная тема, относящаяся к области ГА, не относится к дискретной оптимизации, и поэтому практически не связана с темой настоящей статьи. Вследствие этого мы не будем приводить здесь более подробную информацию.

36 Кроме уже неоднократно цитировавшейся статьи [7], посвящённой в первую очередь программированию бэкгеммона, имеется также её научно-популярное изложение в издании РФФИ; см. http://www.rfbr.ru. См. также другую научно-популярную публикацию – в журнале “Game.EXE” (М., «Издательский дом Компьютерра»), №9 – 2003, http://www.computerra.ru.

37 Экспертные оценки перспективности некоторого шага МВГ, данные несколькими разными программами-предикторами, аналогичны оценкам позиций в случае разных показаний кубиков в бэкгеммоне.

38 О желательности совместного самообучения этих параметров было сказано в [7]. Добавим к изложенному там, что такое самообучение, конечно же, удобно проводить раздельно для упомянутых здесь различных классов позиций.

39 О том, что оценка позиции в программировании игр имеет аналог для ЗДО, было сказано выше.

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

41 А согласно классическому описанию МВГ, мы обязаны в первую очередь рассматривать подзадачи с относительно меньшими значениями границ – независимо от их размерности.

42 Стоит отметить, что на практике ещё лучше работает вариант этого алгоритма, когда попеременно вызываются следующие варианты выбора очередной задачи:

  • согласно наименьшей границе,

  • согласно наименьшей размерности,

  • согласно описанной линейной функции двух этих характеристик.

Как неоднократно было сделано ранее, приведём ещё одну упрощающую аналогию – сравним этот алгоритм попеременного выбора с одним из классических.
А именно, в некоторых конкретных практических задачах, даже в современных программных системах, быстрее всего работает алгоритм шейкерной сортировки.

При описанном здесь алгоритме попеременного выбора задач из списка по разным критериям возникает весьма интересная практическая задача – о наилучшей организации структур данных для такого выбора. (Такая задача возникает в связи с тем, что размерность указанного списка в реальных задачах весьма велика. Например, при размерности исходного варианта случайной ЗКВ около 75 или метрической ЗКВ около 35 длина этого списка часто превышает 500000 – даже при применении всевозможных «программистских хитростей», о которых уже шла речь выше.) Эта задача не связана с материалом данной статьи – и стоит отметить, что автор пока не имеет для неё красивого решения, поскольку реальное число критериев для попеременного выбора подзадач может быть и более 3.

43 Здесь мы считаем, что при необходимости была применена нормализация.

44 Наиболее подробно этот вопрос был исследован автором применительно к вышеописанной задаче «звёздно-высотной» минимизации НКА. В ней «единицы измерения» для большинства предикторов формулируются в разных единицах, каждая из которых связана со специальными показателями вложенности циклов графа переходов минимизируемого НКА

Стоит ещё отметить, что, конечно, априорное наличие информация об отрезке возможных оценок предикторов весьма желательно – оно позволяет упростить многие вспомогательные алгоритмы.

45 Отметим по этому поводу, что многие соответствующие (т.е. вспомогательные) эвристики для более известной ЗКВ фактически уже были приведены в предыдущих разделах.

46 Заметим, что можно легко доказать, что данная задача сводится к известной задаче о рюкзаке. Автор применяет алгоритмы, не применяющие такого сведéния.

47 А здесь имеется аналогия с выпуклостью функций риска в реальных задачах – см. подробнее [7].

48 Имеются в виду следующие работы, выполненные под научным руководством автора настоящей статьи. Отметим, что названия работ отражают не только вопросы, подробно рассматривавшиеся в данной статье, но и некоторые близкие к ним задачи искусственного интеллекта и методы их решения.

  • А.Радионов. Моделирование и нестандартные алгоритмы выбора стратегий в недетерминированных антагонистических играх и родственных задачах. Диссертация … кандидата технических наук. Ульяновск, УлГУ, 1999.

А также следующие дипломные работы студентов Ульяновского государственного университета. (6 из нижеперечисленных 11 студентов-дипломников имеют и соответствующие публикации в сборниках трудов студентов и аспирантов УлГУ, однако конкретных ссылок приводить не будем.)

  • М.Бузин. Функции риска в игре “Sokoban” и связанные проблемы искусственного интеллекта. УлГУ, 1995.

  • Д.Медведков. Использование функций риска для псевдо-планарного размещения графа. УлГУ, 1995.

  • И.Боброва. Быстрый алгоритм канонизации недетерминированного конечного автомата. УлГУ, 1997.

  • Ю.Ревва. Использование принципов программирования недетерминированных игр при программировании шахмат. УлГУ, 1998.

  • Д.Верник. Сложность алгоритмов вершинной минимизации недетерминированных конечных автоматов Рабина-Скотта. УлГУ, 1999.

  • А.Мосеев. Некоторые эвристики, альтернативные функциям риска, в программировании недетерминированных игр. УлГУ, 1999.

  • В.Долгов. Специальное описание всех регулярных языков, чьи канонические автоматы содержат не более 3 состояний. УлГУ, 2000.

  • В.Марунин. Сложность алгоритмов дуговой минимизации недетерминированных конечных автоматов. УлГУ, 2000.

  • С.Козлов. Эвристические алгоритмы в задаче минимизации ДНФ. УлГУ, 2001.

  • В.Гумаюнов. Принцип «турнирного» самообучения для генетических алгоритмов. УлГУ, 2003.

  • Е.Скиценко. Эвристические методы построения псевдо-оптимальных регулярных выражений. УлГУ, 2003.

Автор настоящей статьи благодарит своих бывших студентов и аспирантов за сотрудничество и выражает надежду, что результаты хотя бы некоторых из упомянутых здесь работ всё же будут защищены в качестве кандидатских диссертаций.

49 Некоторые соответствующие программы можно скачать на сайте http://www.bormel.narod.ru, либо получить непосредственно у автора по электронной почте: bormel@mail.ru, B.Melnikov@tltsu.ru.

50 См. также некоторые другие работы, ссылки на которые приведёны в библиографии указанных статей.

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

Добавим ещё к одной из предыдущих сносок, что в 2004 г. под руководством автора данной статьи готовятся защиты двух дипломных работ на эту тему – распределённые вычисления и МВГ.

52 По мнению автора, именно такие алгоритмы и стоит называть искусственным интеллектом в чистом виде!
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