Seond T rials for Calulating a Cooling Shedule using Data Set 50a

0 2 4 6 8 10 12 14 16 18 2.3

2.4 2.5 2.6 2.7 2.8 2.9 3 3.1 3.2 3.3

Residual plot

Residual sum

Instance of Frozen Factor

Figure4.9:Showstheresidualsumforallfrozenfators,blueline.Theblaklineistheaverage

residual sum forinstanes 6 to 18,greenlinesare mean

± 10%

^.

have been identied.Thisshedule is

T ₀ = 15

^,

r = 1 − 10 ⁻¹³

^and

F = 2

^.

20 40 60 80 100 120 140 160 0

200

T 0 =21 Residual sum=1.4974

OPT Value

Maximum route length

20 40 60 80 100 120 140 160 0

0.5

Residual ratio

20 40 60 80 100 120 140 160

0 50 100 150 200 250

T 0 =11 Residual sum=1.4493

OPT Value

Maximum route length

20 40 60 80 100 120 140 160 0

0.1 0.2 0.3 0.4 0.5

Residual ratio

20 40 60 80 100 120 140 160

0 200

T 0 =10 Residual sum=1.6201

OPT Value

Maximum route length

20 40 60 80 100 120 140 160 0

0.5

Residual ratio

20 40 60 80 100 120 140 160

0 200

T 0 =6, Residual sum=1.5168

OPT Value

Maximum route length

20 40 60 80 100 120 140 160 0

0.5

Residual ratio

Figure4.10: Shows resultsforfour dierent temperatures. Bluesline anddotsaretheaverage

valueandthealulatedobjetivevalues,theredlinearethebestknownobjetivevaluesand

the greenline isthe residual ratio.

Results for Initial Temperature,

T ₀

^{, using Data Set 50a}

Intheseondrunforinspetingpossiblevaluesfor

T ₀

^{,eahombinationof}

M ∈ { 10, 20, 40, 50, 70, 80, 100, 130, 1

and

T ₀ ∈ { 6, 7, 8, ..., 32, 33 }

^{ran 100 times. This wasdone to limit therandom fators inthe}

algorithm. The four best results areshownin Figure

4.10

^{. Note that individual results from}

thistest an be seeninthe appendix

D.2.4

^.

Theresidualsumforallvaluesof

T ₀

^{wasthenplottedinFigure}

4.11

^{.Thebestvalueaording}

to this test was

T ₀ = 6

^{, the old value}

T ₀ = 15

^{is marked on Figure}

4.11

^{with a red dot. In}

the rst trials

T ₀ = 6

^{gave a rather highresidual sum, see Figure}

4.5

^{, but inreased number}

of test for eah ombination should limit the eets of random fators. In the previous test

T ₀ = 9

^and

T ₀ = 19

^{gave good results, inthis test both initial} temperatures perform better than average. Thisanbeseenbyinspeting theblaklinedisplaying theaverage results,for

all

T ₀

^,inFigure

4.11

^.

Individual result foreah possible

T ₀

^{an beseen intheappendix.}

Theinitial temperature isnowset to

T ₀ = 6

^{until otherwise speied.}

Results for RredutionFator,

r

^{, using Data Set 50a}

The seond run for theredutionfator gave dierent result than therst one. The value of

r

^{giving the lowest residual ratio sum was}

r = 1 − 10 ⁻⁵

^{.The four best results areshown in}

Figure

4.12

^{.Thefour results arethefour highestvalues,of redutionfator,tested.}

5 10 15 20 25 30 35 1.4

1.5 1.6 1.7 1.8 1.9 2

Residual plot

Residual sum

Temperature, T 0

Figure 4.11: This gues shows the residual sum for some temperatures, blue line. The blak

line is the average residual sum for temperatures and green line is the mean

± 10%

^{. The red}

dot is thebest resultfromtheprevious test.

20 40 60 80 100 120 140 160 0

200

r=1−10 ⁻² , Residual sum= 2.0413

OPT Value

Maximum route length

20 40 60 80 100 120 140 160 0

0.5

Residual ratio

20 40 60 80 100 120 140 160

0 200

r=1−10 ⁻³ , Residual sum=2.1497

OPT Value

Maximum route length

20 40 60 80 100 120 140 160 0

0.5

Residual ratio

20 40 60 80 100 120 140 160

0 200

r=1−10 ⁻⁴ , Residual sum=2.2982

OPT Value

Maximum route length

20 40 60 80 100 120 140 160 0

0.5

Residual ratio

20 40 60 80 100 120 140 160

0 200

r=1−10 ⁻⁵ , Residual sum=1.9960

OPT Value

Maximum route length

20 40 60 80 100 120 140 160 0

0.5

Residual ratio

Figure 4.12: Shows results for four dierent temperatures. Blue line and dotsaretheaverage

valueandthealulatedobjetivevalues,theredlinearethebestknownobjetivevaluesand

the greenline istheresidual ratio.

LetusnowinspetFigure

4.13

^{.Aspreviouslytheplotisofinstaneofredutionfatorsversus}

theresidualsum.Theonlyinstaneremovedfromthetrialsetwas

r = 0.5

^{asitgavetheworst}

results.Therefore theinstanes are

{ 1 − 10 ⁻² , 1 − 10 ⁻³ , 1 − 10 ⁻⁴ , ...1 − 10 ⁻¹³ , 1 − 10 ⁻¹⁴ }

^.The

plot

4.13

^{shows that the highest values tested resulted in the lowest sum of residual ratio.}

Comparedto the previoustest, of redutionfator,

r = 1 − 10 ⁻¹⁰

^{is theonly of theprevious}

topfour results to preform better than average. Notethatall otherresults fromthis test an

be seeninthe appendix

D.2.5

^.

The redutionfator isnowset to

r = 1 − 10 ⁻⁵

^{until otherwise speied.}

Results for Stopping Criteria,

F

^{, using Data Set 50a}

The four best results, theones withthe lowest residual sum, an be seen inFigure

4.14

^and

the singlebestresultfoundistheresidualsumof1.9757when

F = 1 − 10 ⁻⁶

^{,thisistheresult}

displayedinthe bottom right ourner ofFigure

4.14

^{.Other resultsfromthis testan beseen}

intheappendix

D.2.5

^.

InFigure

4.15

^{aplotofthedierentresidualsumomparedwiththedierentinstanesanbe}

seen.Theinstanesare:

F ∈ { 4, 3.5, 3, 2.5, 2, 1.5, 1, 0.58, }

^and

F ∈ { 10 ⁻¹ , 10 ⁻² , 10 ⁻³ , ...10 ⁻⁹ , 10 ⁻¹⁰ }

^.

Inthisplot, Figure

4.15

^{,it isapperant thatthere aretwo loalminimum values andof those}

one isthe globalminimumvalue. Thisglobalminimumvalueisfound when

F = 10 ⁻⁶

^.Inthe

0 2 4 6 8 10 12 14 1.9

2 2.1 2.2 2.3 2.4 2.5 2.6 2.7

Reduction factor plot

Residual sum

Instance

Figure 4.13: Shows theresidual sum for all redution fators, blueline. The blak line isthe

average residualsum for allinstanes, greenlinesaremean

± 10%

^.

20 40 60 80 100 120 140 160

0 200

F=0.5, Residual sum=2.2656

Objective Value

Maximum route length

20 40 60 80 100 120 140 160 0

0.5

Residual ratio

20 40 60 80 100 120 140 160

0 200

F=10 ⁻¹ , , Residual sum=2.2141

Objective Value

Maximum route length

20 40 60 80 100 120 140 160 0

0.5

Residual ratio

20 40 60 80 100 120 140 160

0 200

F=10 ⁻⁵ , , Residual sum=2.2708

Objective Value

Maximum route length

20 40 60 80 100 120 140 160 0

0.5

Residual ratio

20 40 60 80 100 120 140 160

0 200

F=10 ⁻⁶ , , Residual sum=1.9757

Objective Value

Maximum route length

20 40 60 80 100 120 140 160 0

0.5

Residual ratio

Figure 4.14: Shows results for four dierent temperatures. Blue line and dotsaretheaverage

valueandthealulatedobjetivevalues,theredlinearethebestknownobjetivevaluesand

the greenline istheresidual ratio.

0 2 4 6 8 10 12 14 16 18 1.8

1.9 2 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8

Stopping criteria plot

Residual sum

Instance

Figure 4.15: Shows the residual sum for all frozen fators, blue line. The blak line is the

average residualsum for allinstanes, greenlinesaremean

± 10%

^.

rsttrials

F = 10 − 6

^{also gave goodresults.}

Thefrozen fatoris not setas

F = 10 ⁻⁶

^{until otherwisespeied.}

In document B R efACA
e (Sider 52-57)