Исследование влияния начальных параметров 'алгоритма отжига' на скорость и точность нахождения оптимального решения
Исследование
влияния начальных параметров «алгоритма отжига» на скорость и точность
нахождения оптимального решения
Выполнил:
студент группы ИТ-051 Дадаев Е.О.
Проверил: Сыркин И.С.
Вариант: 16
Цель работы: обретение навыков оптимальной настройки
параметров алгоритма отжига при решении задачи коммивояжера
Задание 1
алгоритм
отжига результат функция
Количество городов равно 40. Города расположены
по кругу. Размер поля принять равным 1400х1400. Сравнить точность нахождения
результата алгоритмом отжига и аналитическим методом. Функция охлаждения 2.5.
Оптимальный путь: 4284
Эксперименты
1) Начальная температура To=30,
Конечная температура Tn=0,5
Число повторов при одной температуре 100,
Коэффициент N=40.
Число шагов: 38
Лучшее расстояние: 8327
Изменяем начальную температуру:
|
№
опыта
|
Начальная
температура To
|
Конечная
температура Tn
|
Число
повторов при одной температуре
|
Коэффициент
N
|
Число
шагов
|
Лучшее
расстояние
|
|
2
|
50
|
0,5
|
100
|
40
|
31
|
7635
|
|
3
|
100
|
0,5
|
100
|
40
|
40
|
8425
|
|
4
|
200
|
0,5
|
100
|
40
|
31
|
7113
|
|
5
|
300
|
0,5
|
100
|
40
|
40
|
7996
|
|
6
|
400
|
0,5
|
100
|
40
|
36
|
8539
|
|
7
|
1000
|
0,5
|
100
|
40
|
40
|
9099
|
|
8
|
2000
|
0,5
|
100
|
40
|
40
|
9857
|
|
9
|
3000
|
0,5
|
100
|
40
|
39
|
9894
|
Изменяем число повторов при одной температуре:
|
№
опыта
|
Начальная
температура To
|
Конечная
температура Tn
|
Число
повторов при одной температуре
|
Коэффициент
N
|
Число
шагов
|
Лучшее
расстояние
|
|
10
|
30
|
0,5
|
200
|
40
|
37
|
6674
|
|
11
|
30
|
0,5
|
500
|
40
|
28
|
6135
|
|
12
|
30
|
0,5
|
1000
|
40
|
9
|
7506
|
|
13
|
30
|
0,5
|
2000
|
40
|
12
|
6809
|
|
14
|
30
|
0,5
|
4000
|
40
|
10
|
6375
|
|
15
|
30
|
0,5
|
8000
|
40
|
4
|
4284
|
Изменяем коэффициент N:
|
№
опытаНачальная температура ToКонечная температура TnЧисло
повторов при одной температуреКоэффициент NЧисло шаговЛучшее расстояние
|
|
|
|
|
|
|
|
16
|
30
|
0,5
|
100
|
60
|
39
|
9994
|
|
17
|
30
|
0,5
|
100
|
80
|
43
|
9630
|
|
18
|
30
|
0,5
|
100
|
90
|
59
|
8494
|
|
19
|
30
|
0,5
|
100
|
100
|
53
|
8724
|
Графики
Влияние начальной температуры на результат:
Влияние числа повторов на результат:
Влияние коэффициента N
на результат:
Результаты:
Лучшие результаты (небольшое число шагов и
максимальная приближенность лучшего расстояния к оптимальному пути) достигаются
при:
увеличении начальной температуры,
увеличении числа повторов при одной температуре,
меньшем коэффициенте N.
Задание 2
Эксперименты
. Сравнить функции 2.5 и 2.7. Начальные
параметры: количество ферзей 30; Количество итераций при одной температуре
150-200; Конечная температура 0.1-0.5;
Функция: 2.5. T[i] =
((To-Tn)*(N+1)/N*(i+1)) + To - ((To-Tn)*(N+1)/N)
1) Начальная температура To=30,
Конечная температура Tn=0,1
Число повторов при одной температуре 150,
Коэффициент N=40.
Число шагов: 37
Лучшая энергия: 0
Изменяем начальную температуру To:
|
№
опыта
|
Начальная
температура To
|
Конечная
температура Tn
|
Число
повторов при одной температуре
|
Коэффициент
N
|
Число
шагов
|
Лучшая
энергия
|
|
2
|
200
|
0,1
|
150
|
40
|
35
|
2
|
|
3
|
500
|
0,1
|
150
|
40
|
40
|
2
|
|
4
|
1000
|
0,1
|
150
|
40
|
38
|
6
|
Изменяем конечную температуру Tn:
|
№
опыта
|
Начальная
температура To
|
Конечная
температура Tn
|
Число
повторов при одной температуре
|
Коэффициент
N
|
Число
шагов
|
Лучшая
энергия
|
|
5
|
30
|
0,2
|
150
|
40
|
29
|
2
|
|
6
|
30
|
0,3
|
150
|
40
|
34
|
2
|
|
7
|
30
|
0,4
|
150
|
40
|
24
|
2
|
|
8
|
30
|
0,5
|
150
|
40
|
23
|
2
|
Изменяем количество повторов:
|
№
опыта
|
Начальная
температура To
|
Конечная
температура Tn
|
Число
повторов при одной температуре
|
Коэффициент
N
|
Число
шагов
|
Лучшая
энергия
|
|
9
|
30
|
0,1
|
160
|
40
|
34
|
2
|
|
10
|
30
|
0,1
|
170
|
40
|
23
|
4
|
|
11
|
30
|
0,1
|
180
|
40
|
37
|
2
|
|
12
|
30
|
0,1
|
190
|
40
|
25
|
2
|
|
13
|
30
|
0,1
|
200
|
40
|
27
|
4
|
Изменяет коэффициент N:
|
№ опыта
|
Начальная
температура To
|
Конечная
температура Tn
|
Число
повторов при одной температуре
|
Коэффициент
N
|
Число
шагов
|
Лучшая
энергия
|
|
14
|
30
|
0,1
|
150
|
60
|
25
|
4
|
|
15
|
30
|
0,1
|
150
|
80
|
51
|
0
|
|
16
|
30
|
0,1
|
150
|
100
|
37
|
0
|
Функция: 2.7. T[i] =
(1/2)*(To-Tn)(1+cos(i*pi/N)) + Tn
2) Начальная температура To=30,
Конечная температура Tn=0,1
Число повторов при одной температуре 150,
Коэффициент N=0,5.
Число шагов: 28
Лучшая энергия: 4
Изменяем To:
|
№
опыта
|
Начальная
температура To
|
Конечная
температура Tn
|
Число
повторов при одной температуре
|
Коэффициент
N
|
Число
шагов
|
Лучшая
энергия
|
|
18
|
100
|
0,1
|
150
|
0,5
|
30
|
6
|
|
19
|
200
|
0,1
|
0,5
|
29
|
6
|
|
20
|
400
|
0,1
|
150
|
0,5
|
30
|
8
|
|
21
|
1000
|
0,1
|
150
|
0,5
|
30
|
2
|
|
22
|
2000
|
0,1
|
150
|
0,5
|
30
|
8
|
Изменяем конечную температуру,
Tn:
|
№
опыта
|
Начальная
температура To
|
Конечная
температура Tn
|
Число
повторов при одной температуре
|
Коэффициент
N
|
Число
шагов
|
Лучшая
энергия
|
|
23
|
30
|
0,2
|
150
|
0,5
|
28
|
2
|
|
24
|
30
|
0,3
|
150
|
0,5
|
30
|
4
|
|
25
|
30
|
0,4
|
150
|
0,5
|
29
|
2
|
|
26
|
30
|
0,5
|
150
|
0,5
|
29
|
4
|
Изменяем число повторов при одной температуре:
|
№
опыта
|
Начальная
температура To
|
Конечная
температура Tn
|
Число
повторов при одной температуре
|
Коэффициент
N
|
Число
шагов
|
Лучшая
энергия
|
|
27
|
30
|
0,1
|
160
|
0,5
|
29
|
4
|
|
28
|
30
|
0,1
|
170
|
0,5
|
30
|
0
|
|
29
|
30
|
0,1
|
180
|
0,5
|
29
|
2
|
|
30
|
30
|
0,1
|
190
|
0,5
|
28
|
4
|
|
31
|
30
|
0,1
|
200
|
0,5
|
28
|
2
|
Изменяем коэффициент N (0.5
- 3):
|
№
опытаНачальная температура ToКонечная температура TnЧисло
повторов при одной температуреКоэффициент NЧисло шаговЛучшая энергия
|
|
|
|
|
|
|
|
32
|
30
|
0,1
|
150
|
1
|
54
|
4
|
|
33
|
30
|
0,1
|
150
|
1,5
|
82
|
0
|
|
34
|
30
|
0,1
|
150
|
2
|
114
|
0
|
|
35
|
30
|
0,1
|
150
|
2,5
|
140
|
2
|
|
36
|
30
|
0,1
|
150
|
3
|
165
|
2
|
Графики
Функция: 2.5. T[i]
= ((To-Tn)*(N+1)/N*(i+1)) + To - ((To-Tn)*(N+1)/N)
Влияние начальной температуры на результат:
Влияние конечной температуры на результат:
Влияние числа повторов на результат:
Влияние коэффициента N
на результат:
Результаты:
Лучшие результаты (небольшое число шагов и
минимальная энергия) достигаются при:
возрастании начальной температуры,
уменьшении конечной температуры,
возрастании числа повторов при одной
температуре,
уменьшении коэффициента N.
Функция: 2.7. T[i]
= (1/2)*(To-Tn)(1+cos(i*pi/N)) + Tn
Влияние начальной температуры на результат:
Влияние конечной температуры на результат:
Влияние числа повторов на результат:
Влияние коэффициента N
на результат:
Результаты:
Лучшие результаты (небольшое число шагов и
минимальная энергия) достигаются при:
возрастании начальной температуры,
уменьшении конечной температуры,
возрастании числа повторов при одной
температуре,
возрастании коэффициента N.
Вывод по заданию 2
Лучшей функцией для расчетов является функция
2.5 т.к. с ее помощью можно найти решение быстрее (минимальная энергия при
меньшем числе шагов), чем, используя функцию 2.7.
Вывод
Научился настраивать параметры алгоритма отжига
при решении задачи коммивояжера