Исследование влияния начальных параметров "алгоритма отжига" на скорость и точность нахождения оптимального решения
Контрольная работа - Математика и статистика
Другие контрольные работы по предмету Математика и статистика
Исследование влияния начальных параметров алгоритма отжига на скорость и точность нахождения оптимального решения
Выполнил:
студент группы ИТ-051 Дадаев Е.О.
Проверил: Сыркин И.С.
Вариант: 16
Цель работы: обретение навыков оптимальной настройки параметров алгоритма отжига при решении задачи коммивояжера
Задание 1
алгоритм отжига результат функция
Количество городов равно 40. Города расположены по кругу. Размер поля принять равным 1400х1400. Сравнить точность нахождения результата алгоритмом отжига и аналитическим методом. Функция охлаждения 2.5.
Оптимальный путь: 4284
Эксперименты
1)Начальная температура To=30,
Конечная температура Tn=0,5
Число повторов при одной температуре 100,
Коэффициент N=40.
Число шагов: 38
Лучшее расстояние: 8327
Изменяем начальную температуру:
№ опытаНачальная температура ToКонечная температура TnЧисло повторов при одной температуреКоэффициент NЧисло шаговЛучшее расстояние2500,51004031763531000,51004040842542000,51004031711353000,51004040799664000,510040368539710000,510040409099820000,510040409857930000,510040399894
Изменяем число повторов при одной температуре:
№ опытаНачальная температура ToКонечная температура TnЧисло повторов при одной температуреКоэффициент NЧисло шаговЛучшее расстояние10300,52004037667411300,55004028613512300,51000409750613300,520004012680914300,540004010637515300,580004044284
Изменяем коэффициент N:
№ опытаНачальная температура ToКонечная температура TnЧисло повторов при одной температуреКоэффициент NЧисло шаговЛучшее расстояние16300,51006039999417300,51008043963018300,51009059849419300,5100100538724Графики
Влияние начальной температуры на результат:
Влияние числа повторов на результат:
Влияние коэффициента 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Число шаговЛучшая энергия22000,11504035235000,115040402410000,115040386
Изменяем конечную температуру Tn:
№ опытаНачальная температура ToКонечная температура TnЧисло повторов при одной температуреКоэффициент NЧисло шаговЛучшая энергия5300,2150402926300,3150403427300,4150402428300,515040232
Изменяем количество повторов:
№ опытаНачальная температура ToКонечная температура TnЧисло повторов при одной температуреКоэффициент NЧисло шаговЛучшая энергия9300,11604034210300,11704023411300,11804037212300,11904025213300,120040274
Изменяет коэффициент N:
№ опытаНачальная температура ToКонечная температура TnЧисло повторов при одной температуреКоэффициент NЧисло шаговЛучшая энергия14300,11506025415300,11508051016300,1150100370
Функция: 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Число шаговЛучшая энергия181000,11500,5306192000,11500,5296204000,11500,53082110000,11500,53022220000,11500,5308
Изменяем конечную температуру, Tn:
№ опытаНачальная температура ToКонечная температура TnЧисло повторов при одной температуреКоэффициент NЧисло шаговЛучшая энергия23300,21500,528224300,31500,530425300,41500,529226300,51500,5294
Изменяем число повторов при одной температуре:
№ опытаНачальная температура ToКонечная температура TnЧисло повторов при одной температуреКоэффициент NЧисло шаговЛучшая энергия27300,11600,529428300,11700,530029300,11800,529230300,11900,528431300,12000,5282
Изменяем коэффициент N (0.5 - 3):
№ опытаНачальная температура ToКонечная температура TnЧисло повторов при одной температуреКоэффициент NЧисло шаговЛучшая энергия32300,1150154433300,11501,582034300,11502114035300,11502,5140236300,115031652
Графики
Функция: 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
Влияние начальной температуры на результат:
Влияние конечной температуры на результат:
Влияни