Учебная работа № 85244. «Курсовая Рeшeниe зaдaчи o сoстaвлeнии oптимaльнoгo мaршрутa кoммивoяжeрa

Выдержка из похожей работы

Проверил: Сыркин И,С,
Вариант: 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 т»