2.2.2 Сравнительный статистический анализ алгоритмов сглаживания

Анализ временных рядов

2.2.2 Сравнительный статистический анализ алгоритмов сглаживания

Анализ временных рядов

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

Затем опишем общийкласс моделей, которые могут быть использованыдля описания рядов и построения прогнозов(модели авторегрессии и скользящего среднего).

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

Общее введение

Вначале дадим краткий обзор методов анализаданных, представленных в виде временных рядов,т.е. в виде последовательностей измерений,упорядоченных в неслучайные моменты времени.

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

Подробное обсуждение этих методов можно найтив следующих работах: Anderson (1976), Бокс и Дженкинс(1976), Kendall (1984), Kendall and Ord (1990), Montgomery, Johnson, and Gardiner (1990),Pankratz (1983), Shumway (1988), Vandaele (1983), Walker (1991), Wei (1989).

Две основные цели

Существуют две основные цели анализа временныхрядов: (1) определение природы ряда и (2)прогнозирование (предсказание будущих значенийвременного ряда по настоящим и прошлымзначениям). Обе эти цели требуют, чтобы модельряда была идентифицирована и, более или менее,формально описана.

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

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

Идентификация модели временныхрядов

За более полной информацией о простыхавтокорреляциях (обсуждаемых в этом разделе) идругих автокорреляциях, см. Anderson (1976), Box and Jenkins(1976), Kendall (1984), Pankratz (1983), and Vandaele (1983). См. также:

Систематическая составляющая ислучайный шум

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

Два общих типа компонентвременных рядов

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

Сезоннаясоставляющая — это периодически повторяющаясякомпонента. Оба эти вида регулярных компонентчасто присутствуют в ряде одновременно.

Например, продажи компании могут возрастать изгода в год, но они также содержат сезоннуюсоставляющую (как правило, 25% годовых продажприходится на декабрь и только 4% на август).

Эту общую модель можно понять на»классическом» ряде — Ряд G (Бокс иДженкинс, 1976, стр. 531), представляющем месячныемеждународные авиаперевозки (в тысячах) втечение 12 лет с 1949 по 1960 (см. файл Series_g.sta).

График месячных перевозок ясно показывает почтилинейный тренд, т.е. имеется устойчивый ростперевозок из года в год (примерно в 4 раза большепассажиров перевезено в 1960 году, чем в 1949).

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

Этотпример показывает довольно определенный типмодели временного ряда, в которой амплитудасезонных изменений увеличивается вместе стрендом. Такого рода модели называются моделямис мультипликативной сезонностью.

Анализ тренда

Не существует «автоматического» способаобнаружения тренда в временном ряде. Однако еслитренд является монотонным (устойчиво возрастаетили устойчиво убывает), то анализировать такойряд обычно нетрудно. Если временные рядысодержат значительную ошибку, то первым шагомвыделения тренда является сглаживание.

Сглаживание. Сглаживание всегда включаетнекоторый способ локального усреднения данных,при котором несистематические компонентывзаимно погашают друг друга. Самый общий методсглаживания — скользящее среднее, в которомкаждый член ряда заменяется простым иливзвешенным средним n соседних членов, где n— ширина «окна» (см.

Бокс и Дженкинс, 1976; Vellemanand Hoaglin, 1981). Вместо среднего можно использоватьмедиану значений, попавших в окно. Основноепреимущество медианного сглаживания, всравнении со сглаживанием скользящим средним,состоит в том, что результаты становятся болееустойчивыми к выбросам (имеющимся внутри окна).

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

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

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

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

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

Подгонка функции. Многие монотонныевременные ряды можно хорошо приблизить линейнойфункцией. Если же имеется явная монотоннаянелинейная компонента, то данные вначале следуетпреобразовать, чтобы устранить нелинейность.Обычно для этого используют логарифмическое,экспоненциальное или (менее часто)полиномиальное преобразование данных.

Анализ сезонности

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

Можно легко видеть,что каждое наблюдение очень похоже на соседнее;дополнительно, имеется повторяющаяся сезоннаясоставляющая, это означает, что каждоенаблюдение также похоже на наблюдение, имевшеесяв том же самом месяце год назад.

В общем,периодическая зависимость может быть формальноопределена как корреляционная зависимостьпорядка k между каждым i-м элементом ряда и(i-k)-м элементом (Kendall, 1976). Ее можно измерить спомощью автокорреляции (т.е.

корреляции междусамими членами ряда); k обычно называют лагом(иногда используют эквивалентные термины:сдвиг, запаздывание). Если ошибка измерения неслишком большая, то сезонность можно определитьвизуально, рассматривая поведение членов рядачерез каждые k временных единиц.

Автокорреляционная коррелограмма. Сезонныесоставляющие временного ряда могут быть найденыс помощью коррелограммы.

Коррелограмма(автокоррелограмма) показывает численно играфически автокорреляционную функцию (AКФ),иными словами коэффициенты автокорреляции (и ихстандартные ошибки) для последовательностилагов из определенного диапазона (например, от 1до 30).

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

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

Если первый член ряда тесносвязан со вторым, а второй с третьим, то первыйэлемент должен также каким-то образом зависетьот третьего и т.д.

Это приводит к тому, чтопериодическая зависимость может существенноизмениться после удаления автокорреляцийпервого порядка, т.е. после взятия разности слагом 1).

Частные автокорреляции. Другой полезныйметод исследования периодичности состоит висследовании частной автокорреляционнойфункции (ЧАКФ), представляющей собойуглубление понятия обычной автокорреляционнойфункции.

В ЧАКФ устраняется зависимость междупромежуточными наблюдениями (наблюдениями внутрилага).

Другими словами, частная автокорреляция наданном лаге аналогична обычной автокорреляции,за исключением того, что при вычислении из нееудаляется влияние автокорреляций с меньшимилагами (см. Бокс и Дженкинс, 1976; см. также McDowall,McCleary, Meidinger, and Hay, 1980).

На лаге 1 (когда нетпромежуточных элементов внутри лага), частнаяавтокорреляция равна, очевидно, обычнойавтокорреляции. На самом деле, частнаяавтокорреляция дает более «чистую» картинупериодических зависимостей.

Удаление периодической зависимости. Какотмечалось выше, периодическая составляющая дляданного лага k может быть удалена взятиемразности соответствующего порядка. Это означает,что из каждого i-го элемента ряда вычитается (i-k)-йэлемент. Имеются два довода в пользу такихпреобразований.

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

Во-вторых, удаление сезонных составляющихделает ряд стационарным,что необходимо для применения АРПССи других методов, например, спектральногоанализа.

АРПСС

Дополнительная информация о методах Анализавременных рядов дана также в следующихразделах:

Общее введение

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

Отдельные наблюдениясодержат значительную ошибку, тогда как выхотите не только выделить регулярные компоненты,но также построить прогноз. Методология АРПСС,разработанная Боксом и Дженкинсом (1976), позволяетэто сделать.

Данный метод чрезвычайно популяренво многих приложениях, и практика подтвердилаего мощность и гибкость (Hoff, 1983; Pankratz, 1983; Vandaele, 1983).Однако из-за мощности и гибкости, АРПСС — сложныйметод. Его не так просто использовать, итребуется большая практика, чтобы овладеть им.

Хотя часто он дает удовлетворительныерезультаты, они зависят от квалификациипользователя (Bails and Peppers, 1982). Следующие разделыпознакомят вас с его основными идеями. Дляинтересующихся кратким, рассчитанным наприменение, (нематематическим) введением в АРПСС,рекомендуем книгу McCleary, Meidinger, and Hay (1980).

Два основных процесса

Процесс авторегрессии. Большинствовременных рядов содержат элементы, которыепоследовательно зависят друг от друга. Такуюзависимость можно выразить следующимуравнением:

xt = + 1*x(t-1) + 2*x(t-2) + 3*x(t-3) + … +

Здесь:
                 -константа (свободный член),
 1,2,3  — параметры авторегрессии.

Вы видите, что каждое наблюдение есть суммаслучайной компоненты (случайное воздействие, ) и линейнойкомбинации предыдущих наблюдений.

Требование стационарности. Заметим, чтопроцесс авторегрессии будет стационарнымтолько, если его параметры лежат в определенномдиапазоне. Например, если имеется только одинпараметр, то он должен находиться в интервале -1

Источник: http://statsoft.ru/home/textbook/modules/sttimser.html

Введение в анализ сложности алгоритмов (часть 2)

2.2.2 Сравнительный статистический анализ алгоритмов сглаживания

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

Тем не менее, лично мне этот текст помог упорядочить имеющиеся знания по анализу сложности алгоритмов. Надеюсь, что он окажется полезен и кому-то ещё. Из-за большого объёма оригинальной статьи я разбила её на части, которых в общей сложности будет четыре.

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

ранее:

Часть 1

Сложность

Из предыдущей части можно сделать вывод, что если мы сможем отбросить все эти декоративные константы, то говорить об асимптотике функции подсчёта инструкций программы будет очень просто. Фактически, любая программа, не содержащая циклы, имеет f( n ) = 1, потому что в этом случае требуется константное число инструкций (конечно, при отсутствии рекурсии — см. далее).

Одиночный цикл от 1 до n, даёт асимптотику f( n ) = n, поскольку до и после цикла выполняет неизменное число команд, а постоянное же количество инструкций внутри цикла выполняется n раз.

Руководствоваться подобными соображениями менее утомительно, чем каждый раз считать инструкции, так что давайте рассмотрим несколько примеров на закрепление этого материала.

Следующая PHP-программа проверяет, содержится ли в массиве A размера n заданное значение:
Такой метод поиска значения внутри массива называется линейным поиском. Это обоснованное название, поскольку программа имеет f( n ) = n (что означает «линейный» более точно, мы рассмотрим в следующем разделе).

Инструкция break позволяет программе завершиться раньше, даже после единственной итерации. Однако, напоминаю, что нас интересует самый неблагоприятный сценарий, при котором массив A вообще не содержит заданное значение. Поэтому f( n ) = n по-прежнему.

Упражнение 2Систематически проанализируйте, сколько инструкций необходимо для приведённой выше PHP-программы при наиболее неблагоприятном случае, чтобы затем вывести её асимптотику (аналогично тому, как в первой части мы анализировали программу на Javascript). Должно получиться f( n ) = n.

Давайте рассмотрим программу на Python, которая складывает два значения из массива и записывает результат в новую переменную: v = a[ 0 ] + a[ 1 ]
Здесь у нас постоянное количество инструкций, следовательно, f( n ) = 1.

Следующая программа на C++ проверяет, содержит ли вектор (своеобразный массив) A размера n два одинаковых значения:

bool duplicate = false;for ( int i = 0; i < n; ++i ) { for ( int j = 0; j < n; ++j ) { if ( i != j && A[ i ] == A[ j ] ) { duplicate = true; break; } } if ( duplicate ) { break; }}

Два вложенных цикла дадут нам асимптотику вида f( n ) = n2.

Практическая рекомендация: простые программы можно анализировать с помощью подсчёта в них количества вложенных циклов. Одиночный цикл в n итераций даёт f( n ) = n. Цикл внутри цикла — f( n ) = n2. Цикл внутри цикла внутри цикла — f( n ) = n3. И так далее.
Если в нашей программе в теле цикла вызывается функция, и мы знаем число выполняемых в ней инструкций, то легко определить общее количество команд для программы целиком. Рассмотрим в качестве примера следующий код на Си:int i;for ( i = 0; i < n; ++i ) { f( n );}
Если нам известно, что f( n ) выполняет ровно n команд, то мы можем сказать, что количество инструкций во всей программе асимптотически приближается к n2, поскольку f( n ) вызывается n раз.

Практическая рекомендация: если у нас имеется серия из последовательных for-циклов, то асимптотическое поведение программы определяет наиболее медленный из них. Два вложенных цикла, идущие за одиночным, асимптотически тоже самое, что и вложенные циклы сами по себе. Говорят, что вложенные циклы доминируют над одиночными.

А сейчас давайте переключимся на интересную систему обозначений, используемую теоретиками. Когда мы выясняем точную асимптотику f, мы говорим, что наша программа — Θ( f( n ) ). Например, в примерах выше программы Θ( 1 ), Θ( n2 ) и Θ( n2 ), соответственно. Θ( n ) произносится как «тета от n». Иногда мы говорим, что f( n ) (оригинальная функция подсчёта инструкций, включая константы) есть Θ( что-то ). Например, можно сказать, что f( n ) = 2n — это функция, являющаяся Θ( n ). В общем, ничего нового. Можно так же написать, что 2n ∈ Θ( n ), что произносится: «два n принадлежит тета от n». Пусть вас не смущает такая нотация: она просто говорит о том, что если мы посчитаем количество необходимых программе команд, и оно будет равно 2n, то асимптотика этого алгоритма описывается как n (что мы находим, отбрасывая константу). Имея данную систему обозначений, приведём несколько истинных математических утверждений:

  1. n6 + 3n ∈ Θ( n6)
  2. 2n + 12 ∈ Θ( 2n )
  3. 3n + 2n ∈ Θ( 3n )
  4. nn + n ∈ Θ( nn )

Кстати, если вы решили упражнение 1 из первой части, то это его правильный ответ.

Мы называем эту функцию (т.е. то, что пишем Θ( здесь )) временной сложностью, или просто сложностью нашего алгоритма. Таким образом, алгоритм с Θ( n ) имеет сложность n.

Также существуют специальные названия для Θ( 1 ), Θ( n ), Θ( n2 ) и Θ( log( n ) ), потому что они встречаются очень часто.

Говорят, что Θ( 1 ) — алгоритм с константным временем, Θ( n ) — линейный, Θ( n2 ) — квадратичный, а Θ( log( n ) ) — логарифмический (не беспокойтесь, если вы ещё не знаете, что такое логарифм — скоро мы об этом поговорим).

Практическая рекомендация: программы с большим Θ выполняются медленнее, чем с меньшим.

Нотация «большое О»

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

Это делает жизнь проще, так как чёткого указания на то, насколько быстр наш алгоритм, у нас может и не появиться, даже при условии игнорирования констант (как раньше). Всё, что нам нужно — найти эту границу, а как это сделать — проще объяснить на примере.

Наиболее известной задачей, которую используют при обучении алгоритмам, является сортировка.

Даётся массив A размера n (звучит знакомо, не так ли?), и нас просят написать программу, его сортирующую. Интерес тут в том что, такая необходимость часто возникает в реальных системах. Например, обозревателю файлов нужно отсортировать файлы по имени, чтобы облегчить пользователю навигацию по ним.

Или другой пример: в видеоигре может возникнуть задача сортировки 3D объектов, демонстрируемых на экране, по их расстоянию от точки зрения игрока в виртуальном мире. Цель: определить, какие из них будут для него видимы, а какие — нет (это называется Visibility Problem).

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

b = []n.times do m = a[ 0 ] mi = 0 a.each_with_index do |element, i| if element < m m = element mi = i end end a.delete_at( mi ) b

Источник: https://habr.com/post/195482/

Методика сравнения алгоритмов и для чего она ещё может пригодиться

2.2.2 Сравнительный статистический анализ алгоритмов сглаживания

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

Чем и предлагаю заняться в данной статье.

Итак, по каким критериям можно сравнить алгоритмы аналогичные «имитации отжига»? Чаще всего сравнивают: • эффективность • скорость работы • использование памяти И хотелось бы ещё добавить • повторяемость (То есть проверить, насколько стабилен алгоритм в получаемых результатах).

Критерии оценки

В качестве первого критерия будем использовать длину получившегося маршрута. Понятия не имею, каков самый лучший маршрут на случайно сгенерированном наборе точек. Что делать? Попробуем, для простоты, всё прогонять на одном наборе.

Более педантичные, для большей достоверности результатов, могут потом расширить на несколько наборов и усреднить результаты. А пока надо добавить считывание тестового набора из файла для возможности повторения эксперимента. Для определения скорости работы посчитаем затраченное процессором на алгоритм время, благо есть в Octave такая функция.

Конечно на разных компьютерах результат будет тоже разным. Поэтому можно для сравнения все результаты масштабировать по какому либо одному алгоритму, прогоняемому всегда. Например, по алгоритму из исходной статьи, раз уж он попался первым. По расходу памяти сходу ничего не придумалось. Поэтому попробуем прикинуть на пальцах.

Насколько я понял, основные расходы у автора — это два массива индексов. Один для текущего маршрута, другой — для маршрута-кандидата. Ну и, конечно, массив точек маршрута по две координаты на точку. Остальные расходы учитывать не будем, так как они будут разные в разных средах выполнения и не зависят от размера тестовых данных.

(Возможно здесь я несколько резок, но вполне открыт для предложений). Итого основные расходы N*4, где N — количество точек которые надо обойти.

Небольшое отступление: всё описанное здесь проверялось не в MatLab, как в оригинальной статье, а в Octave [http://www.gnu.org/software/octave/].

Причин тому несколько — во-первых, она у меня есть, во-вторых, её язык программирования почти полностью совмести с MatLab, ну и наконец, она может быть у каждого ибо бесплатна и общедоступна.

Анализируем..

Для начала убеждаемся в совместимости для имеющегося кода (скачивается по ссылке в конце исходной статьи). Всё работает, но оказывается, что там нет кода генерирующего приводимые в ней красивые графики. Не беда — напишем свою функцию из которой вызываем оригинальный алгоритм и рисуем результат. Всё равно она понадобится для обвеса всего сбором статистики.

Итак функция Analyze:function [timeUsed, distTotal] = Analyze( ) % считывание массива городов из файла для повторяемости результата load points_data.dat cities % засечка времени выполнения timeStart = cputime(); % собственно поиск маршрута result = SimulatedAnnealing(cities, 10, 0.

00001); % определение затраченного процессором времени timeUsed = cputime — timeStart; % вычисление общей длины маршрута distTotal = PathLengthMat(result); % рисование итогового маршрута plot(result(:,1), result(:,2), '-*'); drawnow ();end Функцию для генерации файла с массивом координат городов писать не стал.

Сделать это можно прямо из командной строки: cities = rand(100, 2)*10; save points_data.dat cities; Да, если кто заметил, что для оценки не используется функция CalculateEnergy из исходного алгоритма, то тому есть две причины. Во-первых, есть мысль попробовать работу на других метриках, а результат лучше всё же оценивать евклидовым расстоянием.

А во-вторых, хотя автор исходной статьи и описал подробно вычисление евклидова расстояния, код в исходниках вычисляет манхэттенское. Евклидово для двух точек правильно вычислять так:function [dist] = distEuclid(A, B) dist = (A — B).

2; dist = sum(dist); dist = sqrt(dist);end Ну и, чтобы определить насколько результат стабилен от раза к разу, будем запускать всё это в цикле много раз, собирать результаты и оценивать их среднее и степень разброса результатов:function [] = Statistics testNum = 1000; % инициализация массивов для сбора статистики timeUsed = zeros(testNum,1); distTotal = zeros(testNum,1); for n=1:testNum [timeUsed(n), distTotal(n)] = Analyze; end % определение средних значений и разброса time = [mean(timeUsed), std(timeUsed)] dist = [mean(distTotal), std(distTotal)]end Первое разочарование — как всё долго! На компьютере core i5-3450 3.1GHz 8Gb ОЗУ один проход выполняется в среднем 578 секунд. Так хотелось для пущей достоверности запустить и усреднить 1000 циклов но это… 6.69 суток. Пришлось запустить на 100 циклов и через примерно 16 часов 4 минуты (то есть наутро) имеем результат: среднее время вычисления 578.1926 (стандартное отклонение в выборке 3.056), средняя длина получившегося пути 91.0844 (стандартное отклонение 2.49). То есть всё более чем стабильно, а, следовательно, пригодно к использованию. Но как же долго. Не удержался и соблазнился заняться оптимизацией.

Оптимизация

Первый кандидат для ускорения — оценка расстояния. Octave, как и MatLab оптимизированы для матричных вычислений — под это и перепишем. Функция будет принимать два массива: A — начала отрезков, B — их концы соответственно:function [dist] = distEuclid(A, B) dist = (A — B).

2; dist = sum(dist, 2); dist = sqrt(dist); dist = sum(dist);end Чтобы вызвать эту функцию введём ещё одну, которая подготовит данные, циклически сдвинув исходный массив точек для получения массива концов отрезков:function [length] = PathLengthMat(cities) citiesShifted = circshift(cities, 1); length = distEuclid(cities, citiesShifted);end Ну и, конечно, надо переписать функцию SimulatedAnnealing и GenerateStateCandidate для работы непосредственно с массивами точек. Полный код приводить не буду, в конце будет ссылка на архив со всеми исходниками для тех, кому интересно. Запускаем, смотрим… среднее время вычисления 70.554 (стандартное отклонение в выборке 0.096), средняя длина получившегося пути 90.403 (стандартное отклонение 2.204). Прирост скорости более чем в восемь раз! Дальше стараться уже и не интересно — такого прироста уже не получить. Правда расход памяти (по предложенной методике) теперь два массива точек по две координаты (текущее решение и новый кандидат), то есть … N*4. Ничего не изменилось. Но, раз уж оценивать алгоритм, проверим данные температур. Исходная «энергия» сгенерированных массивов точек колеблется около 500 — 700 итоговые маршруты на выходе колеблются около 90 плюс/минус 5. Следовательно выбранные автором температуры практически обеспечивают только ограничение в 100000 итераций (кстати, оно также и жёстко забито в коде. Для предотвращения зацикливания, наверное. Я поднял до десяти миллионов, зачем себя сдерживать при проверке алгоритма?). И действительно, немного поэкспериментировав получаем примерно те же результаты для Tmax=300 и Tmin=0.001. При этом время выполнения сократилось до 21 секунды.

Исследуем варианты

Теперь попробуем сравнить с чем-нибудь. Изначально была идея сравнить с манхэттенской метрикой, но оказалось, что она и была реализована. Потом ещё эта оптимизация. Короче — добавляем код для матричного расчёта манхэттенского расстояния и пробуем для него. Так же интересно как покажет себя другая функция изменения температуры.

Тех, кто обманулся обещанной в исходной статье линейностью функции изменения температуры, вынужден разочаровать — она таковой не является. Чтобы это понять достаточно посмотреть на её график: Наверное имелась ввиду линейность знаменателя функции, ибо знаменатели всех остальных используемых в науке вариантов действительно выглядят страшнее.

Для сравнения попробуем ещё функцию температуры T = Tmax*(Ak) где A выбирается, обычно, в пределах 0.7 — 0.999. (При реализации она вообще не жадная — Ti=A*Ti-1). Варианты «отжига» с её использованием называются «тушением». Она значительно быстрее падает до минимальной температуры, но более пологая на начальном этапе.

То есть, с ней алгоритм больше экспериментирует вначале, но быстрее заканчивает работу. Итак — сводная таблица результатов:

Алгоритм Длина(Разброс) Время(разброс) Память
Из статьи91.0844 (2.4900)578.1926 (3.0560)N*4
Матричный(10-0.00001)90.4037 (2.2038)70.

554593 (0.096166)

N*4
Матричный(300-0.001)90.7956 (2.1967)20.94024 (0.16235)N*4
Матричный манхэттенский(10-0.00001)90.0506 (3.2397)70.96909 (0.7807)N*4
Матричный «тушение»(300-0.001)92.0963 (2.3129)22.59591 (0.

39581)

N*4

Выводы

  1. Возможность количественно оценить результаты работы алгоритма полезная даже если его не с кем сравнивать.
  2. Если учитывать особенности инструмента при написании программы — можно сэкономить много времени.
  3. Если подобрать параметры под конкретную задачу — можно сэкономить ещё немного.

  4. Сравнивать алгоритмы по скорости без оптимизации бессмысленно — время выполнения будет почти случайной величиной.
  5. Для современных процессоров возвести в степень и извлечь корень почти так же просто, как и взять модуль — можно не извращаться и писать математику почти без упрощений.
  6. Многие вариации одного алгоритма дают очень близкие результаты, если не графоман — используй что удобнее (или привычнее).

Обещанные исходники можно найти по ссылке

Ну и если понравилось — можно через какое-то время сравнить с ещё чем-нибудь.

  • оптимизация
  • отжиг
  • для начинающих
  • octave
  • 7 июля 2015 в 01:56
  • 21 июня 2015 в 19:44
  • 19 января 2014 в 21:17

Источник: https://habr.com/post/210812/

Scicenter1
Добавить комментарий