Исследование влияния начальных параметров "алгоритма отжига" на скорость и точность нахождения оптимального решения
Оптимальная настройка параметров "алгоритма отжига" при решении задачи коммивояжера. Влияние начальной температуры, числа поворотов при одной температуре и коэффициента N на результат. Сравнение и определение лучшей функции для расчётов задачи.
| Рубрика | Математика |
| Вид | контрольная работа |
| Язык | русский |
| Дата добавления | 20.11.2011 |
| Размер файла | 329,9 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Исследование влияния начальных параметров «алгоритма отжига» на скорость и точность нахождения оптимального решения
Выполнил:
студент группы ИТ-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
Эксперименты
6. Сравнить функции 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 |
150 |
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.
Вывод
Научился настраивать параметры алгоритма отжига при решении задачи коммивояжера
Размещено на Allbest.ru
Подобные документы
Методы решения задачи коммивояжера. Математическая модель задачи коммивояжера. Алгоритм Литтла для нахождения минимального гамильтонова контура для графа с n вершинами. Решение задачи коммивояжера с помощью алгоритма Крускала и "деревянного" алгоритма.
курсовая работа [118,7 K], добавлен 30.04.2011Понятие генетического алгоритма и механизм минимизации функции многих переменных. Построение графика функции и ее оптимизация. Исследование зависимости решения от вида функции отбора родителей для кроссинговера и мутации потомков, анализ результатов.
контрольная работа [404,7 K], добавлен 04.05.2015Сущность графического метода нахождения оптимального значения целевой функции. Особенности и этапы симплексного метода решения задачи линейного программирования, понятие базисных и небазисных переменных, сравнение численных значений результатов.
задача [394,9 K], добавлен 21.08.2010Суть задачи коммивояжера, ее применение. Общая характеристика методов ее решения: метод полного перебора, "жадные" методы, генетические алгоритмы и их обобщения. Особенности метода ветвей и границ и определение наиболее оптимального решения задачи.
курсовая работа [393,2 K], добавлен 18.06.2011Форма для ввода целевой функции и ограничений. Характеристика симплекс-метода. Процесс решения задачи линейного программирования. Математическое описание алгоритма симплекс-метода. Решение задачи ручным способом. Описание схемы алгоритма программы.
контрольная работа [66,3 K], добавлен 06.04.2012Нахождение полинома Жегалкина методом неопределенных коэффициентов. Практическое применение жадного алгоритма. Венгерский метод решения задачи коммивояжера. Применение теории нечетких множеств для решения экономических задач в условиях неопределённости.
курсовая работа [644,4 K], добавлен 16.05.2010Доказательство существования или отсутствия алгоритма для решения поставленной задачи. Определение алгоритмической неразрешимости задачи. Понятия суперпозиции функций и рекурсивных функций. Анализ схемы примитивной рекурсии и операции минимизации.
курсовая работа [79,5 K], добавлен 12.07.2015Сущность и содержание, основные понятия и критерии теории графов. Понятие и общее представление о задаче коммивояжера. Описание метода ветвей и границ, практическое применение. Пример использования данного метода ветвей для решения задачи коммивояжера.
контрольная работа [253,0 K], добавлен 07.06.2011Применение математических и вычислительных методов в планировании перевозок. Понятие и виды транспортных задач, способы их решения. Особенности постановки задачи по критерию времени. Решение транспортной задачи в Excel, настройка параметров решателя.
курсовая работа [1,0 M], добавлен 12.01.2011Исследование метода квадратных корней для симметричной матрицы как одного из методов решения систем линейных алгебраических уравнений. Анализ различных параметров матрицы и их влияния на точность решения: мерность, обусловленность и разряженность.
курсовая работа [59,8 K], добавлен 27.03.2011
