Исследование влияния начальных параметров «алгоритма отжига» на скорость и точность нахождения оптимального решения

Исследование влияния начальных параметров «алгоритма отжига» на скорость и точность нахождения оптимального решения Выполнил:

студент группы ИТ-051 Дадаев Е.О.

Проверил: Сыркин И.С.

Вариант: 16

Цель работы: обретение навыков оптимальной настройки параметров алгоритма отжига при решении задачи коммивояжера Задание 1

алгоритм отжига результат функция Количество городов равно 40. Города расположены по кругу. Размер поля принять равным 1400×1400. Сравнить точность нахождения результата алгоритмом отжига и аналитическим методом. Функция охлаждения 2.5.

Оптимальный путь: 4284

Эксперименты

1) Начальная температура To=30,

Конечная температура Tn=0,5

Число повторов при одной температуре 100,

Коэффициент N=40.

Число шагов: 38

Лучшее расстояние: 8327

Изменяем начальную температуру:

Изменяем число повторов при одной температуре:

Изменяем коэффициент N:

Графики Влияние начальной температуры на результат:

Влияние числа повторов на результат:

Влияние коэффициента 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:

Изменяем конечную температуру Tn:

Изменяем количество повторов:

Изменяет коэффициент N:

Функция: 2.7. T[i] = (½)*(To-Tn)(1+cos (i*pi/N)) + Tn

2) Начальная температура To=30,

Конечная температура Tn=0,1

Число повторов при одной температуре 150,

Коэффициент N=0,5.

Число шагов: 28

Лучшая энергия: 4

Изменяем To:

Изменяем конечную температуру, Tn:

Изменяем число повторов при одной температуре:

Изменяем коэффициент N (0.5 — 3):

Графики Функция: 2.5. T[i] = ((To-Tn)*(N+1)/N*(i+1)) + To — ((To-Tn)*(N+1)/N)

Влияние начальной температуры на результат:

Влияние конечной температуры на результат:

Влияние числа повторов на результат:

Влияние коэффициента N на результат:

Результаты:

Лучшие результаты (небольшое число шагов и минимальная энергия) достигаются при:

— возрастании начальной температуры,

— уменьшении конечной температуры,

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

— уменьшении коэффициента N.

Функция: 2.7. T[i] = (½)*(To-Tn)(1+cos (i*pi/N)) + Tn

Влияние начальной температуры на результат:

Влияние конечной температуры на результат:

Влияние числа повторов на результат:

Влияние коэффициента N на результат:

Результаты:

Лучшие результаты (небольшое число шагов и минимальная энергия) достигаются при:

— возрастании начальной температуры,

— уменьшении конечной температуры,

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

— возрастании коэффициента N.

Вывод по заданию 2

Лучшей функцией для расчетов является функция 2.5 т.к. с ее помощью можно найти решение быстрее (минимальная энергия при меньшем числе шагов), чем, используя функцию 2.7.

Вывод Научился настраивать параметры алгоритма отжига при решении задачи коммивояжера