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

/

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

Выполнил:

студент группы ИТ-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] = (1/2)*(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] = (1/2)*(To-Tn)(1+cos(i*pi/N)) + Tn

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

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

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

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

Результаты:

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

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

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

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

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

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

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

Вывод

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