Алгоритмы_Отжиг_1

1.

Алгоритм имитации отжига

2. Природные алгоритмы. АИО

Алгоритм имитации отжига – модель из металлургии
Изменение свойств стали
а) закалка
б) отпуск (= отжиг)
Закалка: 1) нагрев
2) быстрое охлаждение
Отпуск: 1) нагрев
2) медленное охлаждение

3. Природные алгоритмы. АИО

Изменение свойств стали = отжиг:
1) нагрев
2) охлаждение

4. Природные алгоритмы. АИО

Отжиг на микроуровне
Кристаллическая решетка вещества (например, металла):

5. Природные алгоритмы. АИО

Повышение температуры:
Атомы могут либо переходить в состояние с большим уровнем
энергии, либо оставаться на месте. Ненулевая вероятность
перехода в состояние с меньшим уровнем энергии.
Вероятность перехода в новое состояние увеличивается
пропорционально температуре.
Понижение температуры:
Атомы могут либо переходить в состояние с меньшим уровнем
энергии, либо оставаться на месте. Ненулевая вероятность
перехода в состояние с большим уровнем энергии
Вероятность перехода в новое состояние уменьшается

6. Природные алгоритмы. АИО

Алгоритм имитации отжига – имитация процессов в
кристаллической решетке при охлаждении.

7. Природные алгоритмы. АИО

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

8. Природные алгоритмы. АИО

• ..\Практика\0-68263-324211.gif

9. Природные алгоритмы. АИО

Начало отжига:
– начальное состояние системы (= текущее)
– начальная температура, конечная температура
– энергия (функция качества) состояния системы
Цикл отжига:
– определить новое состояние системы
– определить энергию нового состояния системы
– если энергия нового состояния предпочтительней энергии
текущего, заменить текущее на новое,
иначе либо оставить текущее, либо с некоторой
вероятностью заменить на новое
– снизить температуру

10. Природные алгоритмы. АИО

Состояния системы: S={S1, S2, S3, …, Sn}
Функция энергии g: S → U,
U – упорядоченное
Функция изменения состояния: f: S × T → S
Вероятность изменения состояния: P(g(Si), g(Si+1),ti)
Функция изменения температуры: t : T → T

11. Природные алгоритмы. АИО

Вероятность изменения состояния: P(g(Si), g(Si+1),ti)
D = g(Si) – g(Si+1)
P=e^(– D / ti)
Функция изменения температуры: t : T → T
a) Больцмана:
t(i) = t0 / ln(1+i)
b) Коши:
t(i) = t0 / i
с) линейная:
t(i) = t0 – i · C
d) Квадратичная

12. Природные алгоритмы. АИО

Функция изменения температуры: t : T → T
Больцмана
Коши
Линейная
Квадратичная
2,5
2
1,5
1
0,5
1
3
5
7
9
11
13
15
17
19
21
23
25
27
29
31
33
35
37
39
41
43
45
47
49
51
53
55
57
59
61
63
65
67
69
71
73
75
77
79
81
83
85
87
89
91
93
95
97
99
0

13. Природные алгоритмы. АИО

Пример.
Неизвестный вектор G.
Найти вид вектора.
G=(1 1 1 1 1 1 1 1 1 1)
Функция энергии – расстояние Хэмминга.

14. Природные алгоритмы. АИО

(1 1 1 1 1 1 1 1 1 1)
(0 0 0 0 0 0 0 0 0 0) 10
Диапазон 10 до 1
ti+1= ti – 1
10 – 7 изменить 3 комп
6 – 3 изменить 2 комп
2 – 1 изменить 1 комп
f (0 0 0 0 0 0 0 0 0 0),10) = ( 0 1 1 1 0 0 0 0 0 0)
f (0 0 0 0 0 0 0 0 0 0), 2) = ( 0 0 0 0 0 0 0 0 0 1)
f (0 0 0 0 0 0 0 0 0 0), 2) = ( 1 0 0 0 0 0 0 0 0 0)
D = g(Si) – g(Si+1)
P=e^(– D / ti)

15. Природные алгоритмы. АИО

ss = (1 1 1 0 0 0 0 1 1 1) 4
t4= 4-1=3
10 – 7 изменить 3 комп
6 – 4 изменить 2 комп
3 – 1 изменить 1 комп
ns = f ((1 1 1 0 0 0 0 1 1 1), 3) = ( 0 1 1 0 0 0 0 1 1 1) 5
D = 4 – 5 = –1
D = g(Si) – g(Si+1)
P=e^( D / ti)=e^( -1 / 3) = 1/sqrt3(е) = 0,7