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



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

Литература


  1. А.Ахо, Дж.Ульман. Теория синтаксического анализа, перевода и компиляции, т.1. – М., Мир, 1978.

  2. А.Ахо, Дж.Хопкрофт, Дж.Ульман. Построение и анализ вычислительных алгоритмов. – М., Мир, 1979.

  3. Н.Вирт. Алгоритмы и структуры данных. – М., Мир, 1989.

  4. С.Гудман, С.Хидетниеми. Введение в разработку и анализ алгоритмов. – М., Мир, 1981.

  5. А.Лозовой, Б.Мельников, А.Радионов. Применение генетических алгоритмов и специальных несогласованных ν-фильтров для минимизации корреляционных шумов БФМ сигналов. – В кн.: Тезисы докладов 3 международной научной конференции и выставки «Цифровая обработка сигналов и её применение», М., Инсвязьиздат, 2000.

  6. М.Макаров и др. Теория выбора и принятия решений. – М., Наука, 1982.

  7. Б.Мельников. Эвристики в программировании недетерминированных игр. – «Програмирование» (Известия РАН), 2001, №5, с.63–80.

  8. Б.Мельников, А.Мосеев. Недетерминированные игры и экономика. – В кн.: Сборник материалов 2 международной научно-технической конференции «Математические методы и компьютеры в экономике», Пенза, изд-во ПТИ, 1999.

  9. Б.Мельников, А.Мосеев. Функции риска в краткосрочном прогнозе. – В кн.: Труды 4 научной конференции «Математическое моделирование…», секция математики, Ульяновск, изд-во УлГУ, 2001.

  10. Б.Мельников, А.Пушкин. Варианты системы поддержки принятия торговых решений на рынке FOREX. – В кн.: Сборник материалов 2 международной научно-практической конференции «Развивающиеся интеллектуальные системы…», Новочеркасск, изд-во ЮРГТУ, 2001.

  11. Б.Мельников, А.Радионов. О выборе стратегии в недетерминированных антагонистических играх. – «Програмирование» (Известия РАН), 1998, №5, с.55–62.

  12. Б.Мельников, А.Радионов. Эвристические алгоритмы в специальных задачах дискретной оптимизации. – В кн.: Тезисы докладов международной научной конференции «Дискретный анализ и исследование операций», Новосибирск, изд-во Института математики, 2000.

  13. Б.Мельников, Н.Романов. Ещё раз об эвристиках для задачи коммивояжёра. – В кн.: Теоретические проблемы информатики и ее приложений, вып.4, Саратов, изд-во СГУ, 2001, с.81–92.

  14. Ф.Новиков. Дискретная математика для программистов. – СПб, изд-во «Питер», 2002.

  15. А.Саломаа. Жемчужины теории формальных языков. – М., Мир, 1986.

  16. И.Сигал, А.Иванова. Введение в прикладное дискретное программирование. – М., Физматлит, 2002.

  17. С.Яблонский. Введение в дискретную математику. – М., Наука, 1986.

  18. D.Applegate, R.Bixby, V.Chvátal, W.Cook, Finding cuts in the TSP (A preliminary report), DIMACS Technical Report 95-05, March.

  19. M.Bellmore, G.Nemhauser, The Traveling Salesman Problem: A Survey, Operation Reasearch, Vo.16 (1968) p.p.538–558.

  20. M.Dorigo, L.Gambardella, Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem.
    – IEEE Transactions on Evolutionary Computation, Vo.1, No.1 (1997) 53–66.

  21. T.Jiang, B.Ravikumar. Minimal NFA Problems are Hard. – SIAM J. Comput., Vo.22 (1993).

  22. D.Johnson, L.McGeoch, The Traveling Salesman Problem: A Case Study in Local Optimization, in “Local Search in Combinatorial Optimization”, eds E.Aarts, J.Lenstra. – John Wiley Ed., 1997, p.p.215–310.

  23. T.Kameda, P.Weiner. On the State Minimization of Nondeterministic Finite Automata. – IEEE Trans.on Computers, C-19 (1970) 617–627.

  24. Ch.Hageman, A.Musholl. Computing ε-free NFA from Regular Expression in O(n·log2(n)) Time. – Theoret. Inform. Appl. (1999).

  25. K.Hashiguchi. Algorithms for Determining Relative Star Height and Star Height. – Inform. Comput. No.78 (1987) 124–169.

  26. K.Hashiguchi. Algorithms for Determining the Smallest Number of Nonterminals (States) Sufficient for Generating (Accepting) a Regular Language. – ICALP, 1991.

  27. M.Jünger, S.Thienel, G. Reinelt, Provably good solutions for the traveling salesman problem. – Zeitschrift für Operations Research, Vo.40 (1994) 183-217.

  28. B.Melnikov. A new algorithm of the state-minimization for the nondeterministic finite automata. – The Korean Journal of Computational and Applied Mathematics, Vo.6, No.2 (1999) 277–290.

  29. B.Melnikov. Once more about the state-minimization of the nondeterministic finite automata. – The Korean Journal of Computational and Applied Mathematics, Vo.7, No.3 (2000) 655–662.

  30. B.Melnikov, E.Kashlakova. Some grammatical structures of programming languages as simple bracketed languages. – Informatica (Lithuanian Acad. Sci.), Vo.11, No.4 (2000) 441–454.

  31. B.Melnikov, A.Melnikova. Edge-minimization of non-deterministic finite automata. – The Korean Journal of Computational and Applied Mathematics, Vo.8, No.3 (2001) 469–479.

  32. B.Melnikov, A.Melnikova. Some properties of the basis finite automaton. – The Korean Journal of Computational and Applied Mathematics, Vo.9, No.1 (2002) 131–150.

  33. B.Melnikov, N.Sciarini-Guryanova. Possible edges of a finite automaton defining a given regular language. – The Korean Journal of Computational and Applied Mathematics, Vo.9, No.2 (2002) 475–485.

1 Данная статья написана при частичной поддержке гранта РФФИ № 04-01-00863.

2 Аналогичного краткого русского термина, к сожалению, не существует. Название «алгоритмы реального времени» недостаточное (оно не полностью отражает суть), а «постепенно приближающие псевдо-оптимальные алгоритмы реального времени» весьма громоздко.

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

4 Автор вместо 1-деревьев использует для метрической ЗКВ процесс построения последовательности левых задач, имеющий аналогию с процессом построения последовательности правых задач, изложенным ниже. Однако более подробное описание этого вспомогательного алгоритма не является предметом данной статьи.

5 См., однако, это решение в ещё не опубликованной статье (сданной в печать): http://www.gordon.ru/konkurssite/texts/new-sh-j.pdf.

6 Где, среди прочего, приведено краткое описание других эвристических подходов к решению данной задачи. Стоит отметить, что предлагаемые ранее подходы не могут быть отнесены к «обычным» методам дискретной оптимизации.

7 Примерно 20 (переменных) в задаче минимизации ДНФ, 30 (состояний эквивалентного канонического автомата) в задаче вершинной минимизации конечного автомата, 70 (городов) в случайной ЗКВ, 100 (точек) в задаче построения БФМ-сигнала.

8 Это условие является весьма существенным – алгоритмов, которые бы не использовали данных построений, в литературе не описано; вероятно, таких алгоритмов не существует. Как было отмечено выше, все имеющиеся алгоритмы (описанные, например, в вышеуказанных работах) такие построения используют.

9 Такое дополнительное условие – безотносительно того факта, является ли задача метрической – называется условием симметричности. Также и ЗКВ при этом называется симметричной.

10 Важно отметить, что псевдометрическая ЗКВ симметричной, вообще говоря, не является.

11 И это – самая важная «экологическая ниша» для алгоритмов, рассматривающихся в данной статье, применительно к ЗКВ. Например, в алгоритмах, которые могут быть найдены на http://www.math.princeton.edu/tsp (и по ссылкам с указанного сайта), подобные эвристики практически не используются.

12 Здесь уместна следующая аналогия с гораздо более простой задачей; эта аналогия почему-то не встречалась автору в каких-либо публикациях, хотя она очень проста и достаточно очевидна. Поставим вопрос: зачем нужен алгоритм QuickSort сортировки массива, в худшем работающий как алгоритм порядка n2? Ответ прост: потому нужен, что при его применении «нужно» считать сложность в среднем, а не в худшем. Что такое «в среднем» для сортируемых массивов – это, с некоторыми оговорками понятно, но что это понятие означает для ЗКВ и тому подобных ЗДО? Можно ответить, что все эвристические алгоритмы для решения этой задачи, по большому счёту, и предназначены для ответа на этот вопрос.

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

13 Здесь, в отличие от вопроса, поставленного в предыдущей сноске, сам автор проводил статистические подсчёты. Так, на «средних современных» компьютерах (с тактовой частотой около 2 ГГц и оперативной памятью 256 МБ) за реальное время (10 минут или менее) по классическому алгоритму МВГ считаются 100% случайных задач размерности 45 (контр-примеров, случайно сгенерированных компьютером, у автора нет), около 50% случайных задач размерности 60 и менее 1% случайных задач размерности 100. Как было отмечено выше, метрические задачи для решения сложнее – например, при тех же самых ограничениях удаётся решить только около 50% задач размерности 25 и около 10% задач размерности 30.

14 Простейшая из них – организация свопинга. Конечно же, желательно, чтобы его организовал сам автор программы, а не операционная система.

Необходимость применения свопинга можно объяснить, например, следующим несложным подсчётом. Существует процедура генерации старта процесса для решения метрической ЗКВ. (Отметим, что аналогично рассмотренному далее процессу построения последовательности правых задач, эту процедуру можно было бы назвать построением последовательности левых задач – так и было сделано в одной из предыдущих сносок.) И при размерности 130 (это число является размерностью одного из стандартных тестов для метрической ЗКВ, т.н. Churritz-test) получается более 8000 «левых» подзадач для последующего решения. Причём впоследствии, при работе МВГ, это значение увеличивается – см. об этом далее. А если одно значение матрицы коммивояжёра занимает 4 б, то, как несложно посчитать, вся матрица размерности 130 занимает более 66 Кб, т.е. оперативная память объёмом 256 Мб сможет вместить менее 4000 подзадач необходимой размерности.

Конечно же, приведённый подсчёт является приблизительным (поскольку многие подзадачи имеют меньшую размерность), но суть отражает верно.

15 Это псевдо-оптимальное решение было выбрано с помощью действий, описанных в предыдущем пункте.

Стоит ещё отметить, что в этом вопросе не всё так очевидно. Иногда процесс построения ППЗ может быть прерван ранее – для получения оптимального решения некоторой промежуточной задачи, например, методом перебора (при небольшой размерности задачи) или каким-либо иным методом. Этот вопрос связан с материалом раздела 6 (о вспомогательных эвристиках), а также с одной из задач для дальнейшего решения, формулируемой в заключении.

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

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

17 Кроме того, изредка использовались и эвристики (и нестандартные алгоритмы) не для ветвления, а для построения границ – однако мы не будем рассматривать этот вопрос.

18 Как уже однажды было сделано выше, приведём некоторую упрощающую аналогию с иной областью математики – вспомним одну классическую задачу теории вероятностей. Двое часов показывают разное время – но у первых значительно больше точность (т.е. значительно меньше дисперсия). Как определить математическое ожидание текущего времени?

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

19 Эта книга посвящена теории принятия решения и не связана напрямую с рассматриваемыми нами ЗДО. Однако все описанные в этой книге алгоритмы принятия решений (при наличии оценок нескольких экспертов-программ) легко связываются с рассматриваемым нами случаем.

20 Можно применить следующую аналогию с некоторыми видами спорта, в которых судьи выставляют оценки спортсменам ([13]). При этой аналогии рассматриваемый нами метод не имеет ничего общего с большинством из таких видов спорта (прыжки с трамплина, гимнастика и пр.) – где оценки судей суммируются. Наш метод похож на применяемый в фигурном катании – где конкретные оценки, с точки зрения математика, не играют никакой роли, а значение имеет лишь место, занимаемое каждым спортсменом с точки зрения каждого судьи. Однако в нашем случае «судьи имеют разные веса» – причём эти веса зависят не только от их «опыта» (хотя и этот фактор тоже имеет значение), но и, главное, от того, является ли спортсмен лидером соревнований или, наоборот, аутсайдером. А именно, для лидера мы больше прислушиваемся к судьям, которые его оценили плохо («выясняем, почему именно это произошло»), а для аутсайдера, наоборот, «пытаемся найти его небольшие плюсы» у судей, которые всё же хоть как-то смогли его оценить.

Важно отметить, что приведённая аналогия часто проявляется и в обычной сравнительной оценке человеком-экспертом некоторых событий. См. по этому поводу обоснования выбора конкретных функций риска в [7] и далее в настоящей работе.

21 Эту задачу также можно рассматривать как одну из ЗДО.

22 С точки зрения оценок эффективности алгоритмов очень важно отметить, что описанные алгоритмы использования специальных методов усреднения путём применения функций риска составляют очень малую часть от общего объёма вычислений. (В любой из рассматриваемых ЗДО – например, в ЗКВ с размерностью 50 и более – эта часть вычислений составляет значительно менее 1%.)

23 В отличие от [7]: там чаще рассматривался отрезок [-1,1]. Однако в подобных случаях мы всегда можем применить нормировку.

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

25 Исследовались как экспертные оценки, упомянутые в предыдущем разделе, так и некоторые другие. При этом случаи, когда размерность рассматриваемой матрицы составляла менее трети от размерности исходной (т.е. становилась 24 и менее), не рассматривались.

26 Специально отметим недетерминированность автомата – иначе задача тривиальна. Эта задача может быть решена стандартными алгоритмами – см. [1] и мн.др. Однако на практике часто нежелательно для каждого из рассматриваемых НКА строить эквивалентный канонический автомат – ведь построение последнего только для одного автомата, первоначально заданного, превращает любой алгоритм в экспоненциальный. Поэтому на практике желательно применять альтернативные алгоритмы, включающие самые разные эвристики. Появление в литературе целого цикла работ вроде [24] автор считает хорошим признаком, признаком того, что связанными вопросами занялись и «чистые математики», специалисты по вопросам теории сложности алгоритмов.

27 Как уже дважды было сделано выше, можно провести упрощающую аналогию. В данном случае – между двумя данными задачами и кажущимися на первый взгляд похожими задачами построения эйлеровых и гамильтоновых циклов. См. по этому поводу [14, стр.267].

28 Это делается, например, методом, близким к изложенному в [15], и практически не имеет отношения к статье [24] (цитировавшейся немного выше) и тому подобным работам. Соответствующая задача схожа с задачей звёздно-высотной минимизации (см. раздел 1), точнее – с построением для неё anytime-алгоритма.

29 См. [5]. Очень кратко эти модификации могут быть описаны следующим образом. Были расширены и дополнены традиционные генетические операторы кроссинговера и мутации: изменения были вызваны спецификой рассматриваемых задач. Например, оператор мутации был растянут на несколько поколений, т.е. аппарат мутации из однотактового превратился в многотактовый. Также было введено понятие оптимизирующей мутации.

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

30 Мы не будем подробно рассматривать в этой статье сами алгоритмы модификации наборов-геномов.

31 Причём желательно наличие не только оптимального решения (конкретного тура ЗКВ и т.п.), но и информации о времени получения данного решения стандартным МВГ (или какой-либо его модификацией) на некотором компьютере известной конфигурации. При этом мы можем подробно проследить работу различных anytime-алгоритмов (или одного и того же алгоритма с разным набором коэффициентов), исследовав при этом характеристики алгоритмов, приведённые в разделе 4.

32 Важно, что не более, чем двух.

33 Точнее – из применения генетических алгоритмов в задачах самообучения для программирования интеллектуальных игр. Подробнее см. [7], а также другие работы, ссылки на которые имеются в указанной.

34 Т.е. сгенерированную по некоторым правилам. Про подходы к возможным «правилам генерации» конкретных ЗДО см. немного подробнее в разделах 2 и 4 – однако этот вопрос является отдельной, ещё до конца не исследованной темой.

35 См., например, http://www.users.kpi.kharkov.ua/mahotilo, а также некоторые ссылки с указанного сайта. Автор настоящей статьи в этом случае (т.е. при решении генетическими алгоритмами системы линейных алгебраических уравнений) обычно применяет один шаг градиентного метода после
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