Метод отжига (стр. 2 из 3)

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

В качестве y для получения плотности распределений

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

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

(2)

где

- независимые случайные величины, распределенные равномерно на

Доказано, что закон изменения температуры

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

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

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

независимо от размерности S.

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

Алгоритм Ксин Яо

Алгоритм Ксин Яо был повторным применением идеи предыдущего алгоритма. В качестве

выбирается

Утверждается, что при изменении температуры по закону

достигается статистическая гарантия нахождения глобального минимума.

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

Таким образом, несмотря на то. Что этот процесс итерировать до бесконечности, получая законы изменения температуры, ценность таких “улучшений” представляется сомнительной. Более того, легко видеть, что в пределе это приводит к тривиальному методу случайного поиска, которым является метод отжига при T= 0.

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

Метод “тушения”

Далеко не всегда хватает вычислительных ресурсов на поиск глобального минимума. Кроме того, зачастую достаточно достигнуть не глобального оптимального решения задачи, а достаточно близкого к нему. Методы “тушения” не гарантируют нахождения глобального минимума, но, как правило, быстро находят близкое решение, а на практике зачастую и сам оптимум.

Основная идея этих методов заключается в том, чтобы скомбинировать семейство распределений

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

Например, можно рассматривать нормальное распределение

из Больцмановского отжига, но при этом уменьшать температуру по закону .

Как правило, в этом случае c выбирается между 0.7 и 0.99. Такой метод очень быстро сходится, и для конкретных задач может давать весьма неплохое решение, близкое к оптимальному, в условиях реального времени.

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

Анализ результатов

Программа была запущенна с разными исходными данными большое количество раз. Результаты эксперимента занесены в таблицу.

N– количество предметов; R– объём рюкзака.

N	R	α	Стоимость	Вес предметов	МДП	МИО
10	10	0,1	6 5 2 3 4 5 4 8 7 3	2 2 2 1 2 2 3 3 1	27/0,17с	27/0,0156с
20	10	0,1	6 5 2 3 4 5 4 8 7 36 5 2 3 4 5 4 8 7 3	2 2 2 1 2 2 3 3 12 2 2 1 2 2 3 3 1	29/0,18с	29/0,0156с
20	20	0,10,50,9	2 4 10 12 6 8 11 3 4 7 2 4 10 12 6 8 11 3 4 7	13 19 8 6 10 8 4 9 8 5 13 19 8 6 10 8 4 9 8 5	46/0,21с	45/0,0156с45/0,0572с46/0,109с
30	20	0,10,50,9	2 9 1 10 5 7 1 12 3 4 2 9 1 10 5 7 1 12 3 4 2 9 1 10 5 7 1 12 3 4	5 6 2 3 7 2 5 12 5 2 2 3 7 2 5 2 5 12 5 2 2 3 7 2 5 6 8 7 3 3	66/0,23с	64,7/0,014с65,3/0,0218с66/0,115с
40	10	0,1	6 5 2 3 4 5 4 8 7 36 5 2 3 4 5 4 8 7 36 5 2 3 4 5 4 8 7 36 5 2 3 4 5 4 8 7 3	2 2 2 1 2 2 3 3 12 2 2 1 2 2 3 3 12 2 2 1 2 2 3 3 12 2 2 1 2 2 3 3 1	30/0,23с	30/0,0156
40	20	0,10,50,9	1 4 6 8 2 4 3 9 7 10 3 1 2 6 3 7 5 4 5 5 7 1 10 3 2 2 6 8 3 9 1 10 9 5 2 3 6 7 4 2	2 6 8 10 12 4 6 6 8 9 2 3 10 4 6 8 2 5 15 2 1 4 2 5 6 7 9 3 2 8 5 6 4 5 2 3 5 7 8 1	54/0,23с	52/0,0156с52/0,031с52/0,468с
50	10	0,10,5	3 4 3 5 4 4 2 6 3 1 6 7 5 6 4 3 3 5 6 2 2 7 7 8 5 6 3 2 5 4 6 6 5 4 6 4 5 3 2 4 7 3 2 1 2 3 8 5 6 5	2 3 4 1 2 5 4 4 3 1 2 2 2 1 3 2 4 3 3 1 4 2 3 5 4 1 1 2 3 4 2 1 2 2 1 3 2 1 4 3 5 3 4 4 2 2 2 3 3 1	49/0,21с	48,8/0,0652с49/0,35с
50	20	0,1	1 4 6 8 2 4 3 9 7 10 3 1 2 6 3 7 5 4 5 5 7 1 10 3 2 2 6 8 3 9 1 10 9 5 2 3 6 7 4 2 1 4 6 8 2 4 3 9 7 10	2 6 8 10 12 4 6 6 8 9 2 3 10 4 6 8 2 5 15 2 1 4 2 5 6 7 9 3 2 8 5 6 4 5 2 3 5 7 8 1 1 8 7 5 3 2 5 4 6 5	57/0,24с	57/0,125с
5050	2030	0,10,50,90,1	4 5 4 4 6 3 7 6 5 6 8 7 7 8 6 5 7 3 4 5 6 6 5 4 7 6 6 5 7 4 5 5 6 3 4 5 8 7 6 5 5 6 7 6 5 4 4 5 3 4	5 10 2 5 7 12 9 5 2 2 7 1 1 8 2 13 1 1 8 5 6 9 3 1 7 4 8 10 2 9 1 3 1 5 5 5 3 12 5 6 3 2 2 10 11 5 4 7 10 9	79/0,2398/0,21	77,8/0,0249с78/0,0769с78,8/0,503с98/0,0156с
5050	3020	0,10,10,50,9	9 8 7 6 7 5 10 7 5 11 9 3 4 3 3 8 6 12 5 12 11 6 5 3 5 8 10 6 3 3 5 5 15 4 6 7 8 10 9 10 11 7 5 4 5 2 7 8 10 8	8 10 8 7 2 5 4 5 7 11 10 9 10 8 7 6 4 15 5 5 3 3 6 10 8 5 3 5 6 11 12 5 12 6 8 3 3 4 3 9 11 5 7 10 5 7 6 7 8 9	84/0,21с59/0,21с	84/0,0262с57/0,0512с57,8/0,07с58/0,61с
50	30	0,1	9 8 7 6 7 5 10 7 5 11 9 3 4 3 3 8 6 12 5 12 11 6 5 3 5 8 10 6 3 3 5 5 15 4 6 7 8 10 9 10 11 7 5 4 5 2 7 8 10 8	9 10 8 15 11 20 9 7 7 10 22 9 9 8 10 21 9 8 8 7 8 20 16 17 14 8 5 7 20 10 11 7 17 15 2 5 9 5 10 6 9 10 13 9 10 10 7 8 10 20	55/0,20с	55/0,0124с
50	50	0,10,50,9	3 4 3 5 4 4 2 6 3 1 6 7 5 6 4 3 3 5 6 2 2 7 7 8 5 6 3 2 5 4 6 6 5 4 6 4 5 3 2 4 7 3 2 1 2 3 8 5 6 5	25 21 20 30 21 19 31 32 20 15 23 20 15 23 20 15 21 33 33 21 18 34 20 15 22 16 34 25 20 14 15 30 21 19 31 20 23 15 23 20 14 21 15 30 21 34 18 20 15 16 14 22 25	21/0,21с	18,5/0,017с19/0,0311с19,8/0,565с
50	50	0,1	3 4 3 5 4 4 2 6 3 1 6 7 5 6 4 3 3 5 6 2 2 7 7 8 5 6 3 2 5 4 6 6 5 4 6 4 5 3 2 4 7 3 2 1 2 3 8 5 6 5	25 3 20 15 5 23 30 35 6 2 2 29 31 7 31 8 25 3 2 2 30 33 24 20 19 10 15 35 7 1 2 33 34 25 20 21 25 22 2 33 31 15 10 11 10 5 3 30 31 5	66/0,20с	66/0,0156с

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

Сравнение по среднему значению целевой функции

α = 0,9

Сравнение по среднему времени работы программы

Сравнение по среднему значению целевой функции

α = 0,5

Сравнение по среднему времени работы программы

Сравнительный анализ работы алгоритмов

Для решения задачи компоновки рюкзака на плоскости использовались два алгоритма: имитации отжига и метод динамического программирования.

В результате тестирования программы были получены данные, представленные в таблице. По этим данным легко увидеть, что при α = 0,9 алгоритм имитации отжига дает оптимальное решение задачи или достаточно близкого к нему, но время выполнения программы превышает время выполнения метода динамического программирования при большом количестве предметов; при α = 0,5 алгоритм имитации отжига имеет наиболее высокую скорость нахождения решения по сравнению с метод динамического программирования и дает решение, близкое к оптимальному.

Литература

1. Лопатин А.С. Метод отжига: «http://www.math.spbu.ru/user/gran/sb1/lopatin.pdf»

2. Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы: Учеб. пособ. – Изд. 2-е, испр. – М.: ФИЗМАЛИТ, 2003. – 240 с.