Parallel Simulated Annealing with Adaptive Neighborhood

(1)

Parallel Simulated Annealing with Adaptive Neighborhood

Hiroki H ÎRAO ^* , Yuichiro U ÊDA ^* , Mitsunori M ÎKI ^ and Tomoyuki H ÎROYASU ^*

(Received January 20, 2009)

Simulated Annealing(SA) is one of the general heuristic method to solve the optimization problems. In that case that SA is applied to the continuous problem, the determination of the neighborhood is very important.

However the appropriate neighborhood range depends on target problems and their dimensions. Therefore it is not easy to find the appropriate neighborhood range. The solution to this problem is the introduction of an adaptive mechanism for changing the neighborhood range into SA method. In this paper, we propose the new method with multiple neighborhood ranges by parallelization, compare them, and it is found that the proposed method is very useful and effective.

Key words optimization, simulated annealing, parallel, adaptive neighborhood

!"#$%

&('*)*+*,.-0/*1*2*3 465.7.8 96:.;6<*= > ?A@*B*< CED*F

GIHKJILIMONQPSRITIUKMWVKXIYIZIMO[I\K]I^

1.

^_`ab

cdefghijkljnm

Simulated Anneal- ing:SA

ohprqtsvuxwyizt{r|~}rtrtr

~

ce

wi

v# kk~

}

1)

SA

^pjkk kcjcjcjk~jkkc

}k

¡

trtv¢£¤~¥r¦§

y¨t}

r

v©ª«tv¬

£

p®x¯°

£±

|}

2)

SA

^p ^² ^« ^¢t³´$% yzt{r|}rµt¶·

t¸

}

¹º

¡

»h¹ºg

SA

^°h¨¹}

$%

pv¼½¾t¿

±À

½¾ÁÂÃxwÄ~}

Å

rÆtÇ

~

È

cÉ

|

$%Ê

yzË

jÌÍ

#trk$%Ê

Å s £

p

ÅÎ# Ï

ÄÐ¨x¯

}rÑÒ

rÓÔ

* Graduate Student, Department of Knowledge Engineering and Computer Sciences, Doshisha University, Kyoto Telephone:+81-774-65-6921, Fax:+81-774-65-6716, E-mail:[email protected]

** Department of Knowledge Engineering and Computer Sciences, Doshisha University, Kyoto Telephone:+81-774-65-6930, Fax:+81-774-65-6716, E-mail:[email protected]

*** Faculty of Life and Medical Sciences, Doshisha University, Kyoto

Telephone:+81-774-65-6932, Fax:+81-774-65-6019, E-mail:[email protected]

®x¯

È

Õ$%Ê

rÖx×

£

prØÙ

#trÓÔÚÛ

pÜrÝ¨t}rØÙ

ÏtvÞß

wÐ¨x¯

} É

r

à

j$%kÊ

jáâ~p

ÓÔkÚÛcvÅ

s

vãkä

jå~æ

}

1)

$%Êtç

¨~}rèé~pr®l¯

×|

¤

sr

3)

^dÌÍ ^#

rÕÓÔêë

p Å s

r$%ÊÅÎ#ÓÔ

ÕÓÔ

ì

ëh

píÖî×

ï$h%hÊh

ØhÙ

#eÓhÔ

íðòñ

É y

e³

È

Ïhó

«g»ÜºÝh¨¹}

É

yºhô»¿õ

¤h£

} wí¿gw

$%Ê

Öx×¯¨t}rö÷

rø

}tyØÙ Ïtvù

}

~

}

$»%»Ê

ºÖú×

£

½»¾

Ø»Ù Ï¹ºù

õr

¹p

û

rØÙ

Ï

rütýþ

¨ É yv

s

r£

à

ï$%Ê

ÿ

¨}

É

y y

}

4)

É |

r¦

w

ð

èé

³

È

¨~}

"

#$%

SA

^m

SA with Advanced Adaptive

(2)

Neighborhood:SA/AAN

^o

⁵⁾

^Ð ^{$»%» !}

SA

^m

Neigh- borhood Parallel SA:NPSA

^o

⁶⁾

^×

|

¤»£

}

SA/AAN

^p ^Ó»Ô

°

£»¤»$%

Ê

Ã

¨t}

~

È

NPSA

^p ^} ^$%Ê

°

£¤ !trÓÔ

rðxñ

t

}

y

¥r$

%Ê

v~

Ã w

t

}

pxy¨t}

¨t}r

à

t

È

p !

r$%Ê

° £

}r

à

pr®

¯#"#$%

'&

y

}

(

è~é

p

$t%~Ê

Ã y

~!tl)

w

#*

"$%

ÿ

~"t#l$~%tÊ

xð ñ

!

SA

^yw ^¤t

2

^!,+$%

,-

Û

SA

m

PSA/AN(2N)

^o ^¢t³r´

3

^!+$% ^- ^Û

SA

^m

PSA/AN(3N)

^o ^.k¨~} ^. ^p ^}

$%Ê

©/t"$%

ÿ

ÓÔ

rð

£

Ì Ó

Ô0

/1ty

*

"$%

ÿ

2345

rðxñ

.6

*

"$%

ÿ

ÓÔtr¢

ý }

$%Ê

p

ïÏ

78

9:£

¤"#t

×|t}

É |

³

È

k$%Ê

r

t

Ã w

;tr£ !

/

#tvÓÔ

÷<

s}

=>

#~

/?

ç / Ö tr

°w û

Ú

@

¨

2.

^A,BC,D

E,F'G#HJIKL

(SA) SA

^NMtPONQ

Fig. 1

^@ ^¨ ^6R ^² ^«

T

S

÷á

w

åæ

±

|

S

÷»½¾

x 0

^¿

±

þUT

w

¤À

½¾

x

⁰

VW

w û

XYZ

E

⁰

â[¨t}

¢»À

½»¾

UVW

wÄ¹}

»Å

ºÆ¹Ç

$»%»Ê

y z»Ë

Àgí

X\Y\ZgU]\!

∆E(= E

⁰

− E)

^y ^² ^«

T

^k ^í"

^ ¤ _

t

â[xw

tp

À

½¾

`a

¨

}

#_ p

.b

(1)

^@ ^¨· ^$c ^ÿ ^9d

° £ } É

e

f

È'g

w

¼#h

² «

T

^k^#i#j

½¾

k

w

±

e

ð

£À

² «

T

^k

+1

l

à

m´ÓÔ

à } É

re p

b

(2)

° £ } !

²

«tnt

È

ìopq

k

w

±iÓÔ

ìo

¨t}

r¢ïÓÔ pq

p ²

«Ð ÓÔ0

/

r æ ± | (

èé

p ÓÔN0

/ ìNopq ykw

¤£

}

A(E, E

⁰

, T ) =







1 if ∆E < 0

exp(− ∆E

T ) otherwise (1)

T

^k

+1 = γT

^k

(0.8 ≤ γ < 1) (2)

Initial Parameter Setting

Generation

Acceptance Criterion

Transition

Cooling Criterion

Cooling

Terminal Criterion

End Yes

Yes

Yes No

No

Fig. 1. Algorithm of Simulated Annealing.

3.

^s#t,uv

(

èé

¦§

y¨t}

¡ ç / Ö tr

p À

2

ç /

c

} b

(3)

^@ ^¨

Rastrigin

^ç ^/

⁷⁾

^p ^ØkÙ

Ï

xwyk½

hk¨ } ®z Úcç

/ È À{

/

2

100

^~vØÙ ^Ï ^b

(4)

^@ ^¨

Griewank

ç /

7)

p

á»â|/}

¹çU~

¨¹}º®z Ú¹ç

/

t

}

ÅÎ#t

pz Útç

/t

³ ñ

rÚ

¥

ØÙ

#

p®#/ØÙ Ï

h¨}

À#{

/

3

^y¨t}yrs

Rastrigin

^ç ^/

Griewank

ç

/c

dk kÏ

Z~p

û

|k|.

9.94

10

⁻

¹

7.4

10

⁻

³

^} ^(## ^p ^~É ^| ^³ ^È ^¥£ ^X#YZ

y}áâ#|/

Î Ï

Î y

#

¨}

f R ( x ) = (N × 10) +

N

X

i

=1

x ²

i

− 10 cos(2πx

ⁱ

)

#

Î

: −5.12 < x

ⁱ

≤ 5.12,

Ï

: min(f R ( x )) = f R (0, 0, . . . , 0),

Z

: f R ( x ) = 0 (3)

f G ( x ) = 1 +

N

X

i

=1

x ²

i

4000

−

N

Y

i

=1

cos

x

ⁱ

√ i

#

Î

: − 512 < x

i

≤ 512,

Ï

: min(f G ( x )) = f G (0, 0, . . . , 0),

Z

: f G ( x ) = 0 (4)

(3)

Neighborhood range 10¹ 10^-1

10^-2

10^-3 10⁰

10^-1 10⁰

(a) Rastrigin function

Neighborhood range 10¹ 10² 10³ 10^-1 10⁰

10^-2 10^-1 10⁰ 10¹ 10²

(b) Griewank function

Energy Energy

Fig. 2. Effect of the neighborhood range on the en- ergy.

4.

^,uvb

SA

4.1

¡

tr

SA

°¨}

$%

p

~

}

w

à } É y

s}

É

ÆtÇ

$%Ê

yzË

1

^³

ñ

j$k%Ê

jákâ~p

ÓkÔkÚkÛ~jÅ

s

jãä

jåcæ

}

1)

ÉÉrÕ$%Ê

ÓÔt

å~æ

}

ãä

yw

¤ÕÏó

«

y

$%Ê

ç~

Fig. 2

^@ ^¨

Fig. 2

^p ^r$%

Ê

XYZ

@

w û

||t

$%Êtr¢£¤

30

ð

ÓkÔ

jð

õ ¤

ÄkX.Y.Zc

"!

Z

c

}

j¢k

À{

/~p

3

^~ ^}

Fig. 2

^³ ^È

3

^À{

Rastrigin

ç /

p

1.0 Griewank

^ç ^/ ^p

6.0

^# ^$ ^XY

Zt$%

t

}

r¢eÉ

| ±

Ztp

*trtr¢

ý }

ØÙ ÏJ

ñ

w}'&y Ì(

¨}

wõ

¤

SA

p

ÓÔ

ó

«t$t¯

}

$%Ê

hxw

eÉ

Ztp

t

¨t}ty*) æ }

6

Õ+tr$%Ê

á w

£

y

ÓÔ

ó

«p',

¨}

4.2

^-bs./ ^G01r2

3

³ ñ

SA

^¢

ý }

Ó»Ô

ó

«p

$

%ÊtrÅ

st¯

¨t}

6

*¦§trt

p û

|

#~jÓÔ

vð ñ É

yv

sk}

$k%Ê

h¨c}

wr¿tw eÉ

$%Ê

¨t}

p4 Åt

t

}

.6

Õ¦§tr

r©ª

}ty ÕÓÔ

½

5

»³

õ

¤»6+¹º$»%»Ê

U

} É y ¥ r æ ±

|}

É

r

à

ïÓÔ

½ 5

r"

^

$%Ê

"#t

¨

}

,M'OQ

y r æ ±

|t}

ð

èké

p É

"7

¦ w

¤ÕÅ

s ¯

2

^8:9 ^"

$

t×|

¤£

}

1

p';

À

}=<

¨ }

e"e#e$e%

SA(SA/AAN) ^{5 )}

^>

ò

È

¥

1

^p ^!g ^î ^}?< ^$ ^% ^g!

SA(NPSA) ^{6 )}

^> ^}

SA/AAN

^p ^ÓÔ, ^° ^£¤$%Ê

¨t}

yrp

ïÓÔ

VW

w

Ì

/t

À

½¾t

ñ@

wA

@

¨ É

p

$%Ê

Ð

ÓÔ

½ 5

¨t}r

à É

9:£

$

%Ê

tvðxñ

É y

ïÓÔ

½ 5

r"

^

$%Ê

Ãá

¨c}

É

yv

sk}

5)

^ÌB

NPSA

^p ^}

$»%»Ê

° £

Ó»Ô

©/¹"$%

ÿ °

£»¤

ð

£»

Ì

}"&N1cy

*

".$%

ÿ

Ä

Ï

45k¨~}

É y

ÓÔ

½ 5

"

^

$%Ê

Ä}

}

6)

y

¥r$%Ê

Ã

s}

t

} w

¿cw

SA/AAN

^p ^y ^£

ñ

8k

µc¶k·

¸

³

õ ¤ l à

} t

} 6

NPSA

p

*

"$%

ÿ ° £ }

$%Ê

C

#t

Zlyw

¤

å~æ

}~wv¿

¯ É

Z

D

w

¤ÓÔ

vðlñ

à

v

Ï

45

wixyw

¤t¥rFEtrÓÔ

½ 5

r"

w

¤£

}

yrp)

£G£

É

r

p

"$%

ÿ /

H

Ðxw®8

$%Êt³

}

ÓÔ

rðtæ

{ Ï s}

û

r

à

p®#/#"$%

ÿ

y

ÈI

ÿ

¿¿}

(

èé

p eÉ

$%Ê

Ã

y

!~)

w

.;t£ !

/

³

}

ÓÔ

yw

¤

<

2

^!+$

% -

Û

SA

^m

PSA/AN(2N)

^o ^> ^¢t³v´ ^<

3

!+»$»%

-

Û

SA

^m

PSA/AN(3N)

^o ^>

¨t}

É | ±

p

k !³

õ ¤ }

$%

Ê ° £

SA

^³ ^} ^ÓÔ ^ðxñ ^yKJ ^r* ^"$% ^ÿ

ÓÔ~r¢£¤t¥r$%Ê

"#t

¨~}

M~

OQ

¨t}

}

!L

ý

t

¯

*

"$%

ÿ

r¢£¤t¥v$%Ê

"#~

Ã

¨t}

É y

®

/t"$%

ÿ ° £ R

rÓÔ

½ 5

v"

wi

$%Ê

Ã

#t

¨t}

É

yr

s}

NMO

É | ±

£¤P

w¯

}

5. 2

QRS-TUVW/X'YZ

SA

(PSA with Adaptive Neighborhood using Two Neighborhood ranges PSA/AN(2N)) 5.1

^{[\]^}

ÌÍ

#tv

¼ht

ÓÔ_

Ï

Ît

|~{

$%

Ê

Öx×¯i¨t}

É y

ØÙ

#ÓÔ

ØÙ Ï #

$

|

{

$%Ê

Å

st¯¨t}

É y

ÅÎ#ÓÔ

û

||

(4)

t

} û

Ér

p

ïÅ

Ö

2

}

$%Ê

°

£¤ !ÓÔ

rðxñ

û w

¤

Ì

÷

(

^r÷}&

)

^1ty ^* ^"$% ^ÿ ^{v¢£¤íÓÔ} ^½ ⁵ ^v"

^

$%Ê

tðxñ

É |

³

È

.;tr£ !

/

ÅÎ#ÓÔ

yiØÙ

#ÓÔ

·

OQ

rö

r

¨

}

ÓÔ

Û y È ïÓÔ

½ 5

r"

w

$%Ê

Ã

÷#<

s}

5.2

^{G ,I}

(

p

2

"#$%

ÿ

Å

Ö

}

$%Ê

á

¨t}

ÉÉ

û

||t"$%

ÿ

Å$%

Ö

$%

yzË

û w

¤ É | ±

2

^$%Ê ^Ã

w

±ÓÔ

à }

É Ã

»·

OQ

P

M n 6

}

¢

M

n

b

(5)

^¿ ^±'b

(7)

^r¢ ^ý ^}

N

^l

N

^s ^p ^Å

$%

Ö

$%~r¢

ý }

$%Ê

Z

r

^p ^Å

@

¨

6

Fig. 3

^É ^· ^#O,Q

@

¨

(a-1)

^Å$% $Z7#8×|yrs

( N

^lnext

= N

^lcur

N

^snext

= N

^scur

× r (5) (a-2)

^Ö ^$% $Z7#8×|yrs

( N

^lnext

= N

^lcur

× 1/r N

^snext

= N

^scur

(6)

(b)

^$Z7#8 ^£

(

^Å

M

Ö¨}

)

^ys

( N

^lnext

= N

^lcur

× r

N

^snext

= N

^scur

× 1/r (7)

(

p Ì

÷

(

^r÷N}&

)

^1~y ^* ^"$% ^ÿ

$Z¹7#8

ð

ô|¿

_

¨}

b

(5)

^#b

(6)

@ ¨ ³ ñ

Å$%

$'%

±

{ Å»

Ö

$%

t±

{ Öxw

78

_ ö

$%xy×|~}

$%

Ê

w

Å

Ö

2

^$%Ê ^Å ^s× ^|

(

^$

%Ê

)

^¨} ^ÌB ^$Z7#8 ^r£ ^ysp ^b

(7)

^@ ^¨ ^³ ^ñ ^vjÅ$k% ^Å ^wiÖ ^$%

Ölw kÉ

$Z7#8

ð

ô|}

6 f È'g

¨

L w

v$%Ê

vÝ

áâ.|/

}c

Å

s~×

n

û

10

⁻

³

^Å ^st×y ^t± ^¿ ^{^} ^à ^à ^¤¢ ^s

û

rÆtÇ

tæ

r£t³ ñ

¨t}

6

n

r¢£¤

Ö

$%

$Zt!Ö

78x×|

¤t¥rï

$Z~78

õjyvp"

× R

2

^$%Ê ^| ^× ^r£

C C

D

Annealing steps

C

Neighborhood range

Fig. 3. Change in neighborhood of PSA/AN(2N).

㪇㪉㪋㪍

10^-2 10^-1 10⁰ 10¹ 10²

㩷㪙㪼㫊㫋㩷㪼㫅㪼㫉㪾㫐

㪘㫅㫅㪼㪸㫃㫀㫅㪾㩷㫊㫋㪼㫇㫊㩷㩿㬍㪈㪇 ^㪋

^㩷

㪀

㪜㫅㪼㫉㪾㫐

10⁰ 10¹ 10² 10³ 10⁴

㩷㪣㪸㫉㪾㪼㩷㫅㪼㫀㪾㪿㪹㫆㫉㪿㫆㫆㪻㩷㫉㪸㫅㪾㪼㩷㪪㫄㪸㫃㫃㩷㫅㪼㫀㪾㪿㪹㫆㫉㪿㫆㫆㪻㩷㫉㪸㫅㪾㪼㪥㪼㫀㪾㪿㪹㫆㫉㪿㫆㫆㪻㩷㫉㪸㫅㪾㪼

Fig. 4. History of Energy and Neighborhood ranges in PSA/AN(2N).

r¢

r÷

p É | 6

ÓÔ

$Z

#$

w

_ ¿

±ÓÔ

m%

¨t}

É |

³

È

k

$Z

#$

w

_ Ï

Î p ØÙ

#ÓÔt³ È ¬ £

Ïó

« Ä ±

|}

É

y&'×|t}

ÉÉr

(

Ï

Î~(k

w

ð

ÓÔ

êë¢

ý } $Zy

$%Ê

)*

Fig. 4

@ ¨

Fig. 4

^³ ^È ^íÓÔêë ^Ö ^$% ^Å ^wi+ ^º ^$

Zt78x×i|xyrs

} É

|tp Å$%

B

$%

,-

Ä~}

É y

ØÙ

Ï

vütýþ

w

É y

>

w

¤£

} É | ³ È ØÙ

Ïtrù

õ

¤t¥rÅ$%t³

õ ¤

ØÙ Ït

ütýþ

wÐ¨

£ÓÔ

rð

õ

¤£

}ty*) æ }

6. 3

QRS-TUVW/X'YZ

SA

(PSA with Adaptive Neighborhood using Three Neighborhood ranges PSA/AN(3N)) 6.1

^{[\]^}

(

p

ïÅ

Ö

3

}

$%Ê

°

£¤

!ÓÔ

vðlñ

û w

¤

Ì

÷

(

^v÷}&

)

^1~y ^*

(5)

"$%

ÿ

v¢£¤ïÓÔ

½ 5

v"

^

$%Ê

ðñ

É |

³

È

PSA/AN(2N)

^y ^;r£

! /

ÅÎ#ÓÔ

yØÙ

#ÓÔ

·

ONQ

rö

¨t}

ÓÔ

Û y È ïÓÔ

½ 5

r"

w

$%Ê

Ã

r÷#<

s}

6.2

G ,I

(

p

3

"#$%

ÿ

Å,

Ö#

}

$%Ê

á

¨¹}

É»Éº»

û

|»|¹"$U%

ÿ

Å»$%»

r$%

Ö

$%

yzË

û w

¤cÉ

| ±

3

$%Ê

,

Ã

w

±ÓÔ

à }

É Ã

»·

OQ

P

M n 6

}

v¢

M

n~

b

(8)

^¿ ^±b

(11)

^v¢

ý }

N

^l

N

^m

N

^s

p

Å$%$%

Ö

$%¢

ý }

$%Ê

Z

r

^p

Å @

¨

.6

Fig. 5

^É ^· ^#OQ

@

¨

(a-1)

^Å$% $Z7#8×|yrs



 



 



N

^lnext

= N

^lcur

× r

N

^mnext

= N

^mcur

× r(= N

^lcur

) N

^snext

= N

^scur

× r(= N

^mcur

)

(8)

(a-2)

^$% $Z7#8×|yrs



 



 



N

^lnext

= N

^mcur

× r N

^mnext

= N

^mcur

N

^snext

= N

^mcur

× 1/r

(9)

(a-3)

^Ö ^$% $Z7#8×|yrs



 



 



N

^lnext

= N

^lcur

× 1/r(= N

^mcur

) N

^mnext

= N

^mcur

× 1/r(= N

^scur

) N

^snext

= N

^scur

× 1/r

(10)

(b)

^$Z7#8 ^£

(

^Å

M

Ö¨}

)

^ys



 



 



N

^lnext

= N

^lcur

× r N

m_next

= N

m_cur

N

^snext

= N

^scur

× 1/r

(11)

(

t¥

PSA/AN(2N)

^y ^Å, ^Ö

3

$»%»Ê

Ó»Ô,

Ï

U78»½

5

"

^ ¤ | × ¹}

$UZgU7\8¹

}¹yís

#b

(8)

^¿ ^± ^b

(10)

^@ ^¨

³ ñ

rÕÀ

÷

r¢£¤

p 78

õv

$%

r$

%

yw

¤ÓÔ

r¡tý

} ÌB Õ

$Zt78t

r£

y

s

b

(11)

^@ ^¨ ^³ ^ñ ^r$% ^û ^6#6 ^w ^¤

C C

D

Annealing steps

C

Neighborhood range

C

Fig. 5. Change in neighborhood of PSA/AN(3N).

㪇㪉㪋㪍㪏㪈㪇㪈㪉

10^-4 10^-3 10^-2 10^-1 10⁰ 10¹ 10²

㩷㪙㪼㫊㫋㩷㪼㫅㪼㫉㪾㫐

㪘㫅㫅㪼㪸㫃㫀㫅㪾㩷㫊㫋㪼㫇㫊㩷㩿㬍㪈㪇 ^㪋

㩷

㪀

㪜㫅㪼㫉㪾㫐

10^-2 10^-1 10⁰ 10¹ 10² 10³

㩷㪣㪸㫉㪾㪼㩷㫅㪼㫀㪾㪿㪹㫆㫉㪿㫆㫆㪻㩷㫉㪸㫅㪾㪼㩷㪤㫀㪻㪻㫃㪼㩷㫅㪼㫀㪾㪿㪹㫆㫉㪿㫆㫆㪻㩷㫉㪸㫅㪾㪼㩷㪪㫄㪸㫃㫃㩷㫅㪼㫀㪾㪿㪹㫆㫉㪿㫆㫆㪻㩷㫉㪸㫅㪾㪼㪥㪼㫀㪾㪿㪹㫆㫉㪿㫆㫆㪻㩷㫉㪸㫅㪾㪼

Fig. 6. History of Energy and Neighborhood ranges in PSA/AN(3N).

Å$%

Å w Ö

$%

Öx×t}

û |

t¥

78

r£

yrs

m´tÉ

78t

ð

ôr|t}

6 f È

g ¨

6 $Zt78t

ð

ôr|

¿õvxyrs Ö

$%

n

k

w

¤£

|t{

ïÅ$%L

ý

t

¯

r$%~¥

Å

w

ÅÎ#ÓÔ

rðxñ

É |

³ È

ØÙ Ï ¿ ±

üýþ

wÐ¨¯

}ty r æ ±

|}

ÉÉr

(

Ï

Ît(k

w

}

1

^ð

¢

ý

}X#YZy

$%Ê

)*

Fig. 6

^@ ^¨

Fig. 6

^³ ^È ^ÓhÔ ºëgí¢»£h¤h$»%hÊ

Öîw

¤

£ }

¥

ô ± R

$Zt78t

r£tÉ

yv¿

±

ØÙ

Ïtrù

õ

¤£

}ty r æ ±

|}

wr¿tw û

trÅ$

% y v$%

Å w

¤£

¯

v

$Zt78x×|

¤£

} É

|¹pºØ»Ù Ï ¿ ±

ü¹ý»þ

w

¤»£

}¹y r æ ±

|¹}

×

±rrïÓÔ

ì

ëtr¢£¤

Ö

$%

Öxw

¤£

¯

r

$Zt78x×|

¤£

} É

|~p Ï

Îtv¢£¤

$%Ê

Ö¨t}

É y

ØÙ

#ÓÔ

rð

£

¬

£Ïó

«trÄ

± |

¤£

} É y

>

w

¤£

} É | ³ È Õ$%

Ê

Å

· OQ

ït

- Û w

¤£

} É yr

×|

Parallel Simulated Annealing with Adaptive Neighborhood