Parallel Simulated Annealing with Adaptive Neighborhood using Different Target Acceptance Ratio

(1)

Parallel Simulated Annealing with Adaptive Neighborhood using Different Target Acceptance Ratio

Hiroki H IRAO ^* , Yuichiro U EDA ^* , Mitsunori M IKI ^ and Tomoyuki H IROYASU ^*

(Received January 20, 2009)

This paper deals with a new approach in Simulated Annealing (SA), and proposes an adaptive neighborhood mechanism for continuous optimization problems. When applying SA to continuous optimizing problems with nu- merous local optima, the automatic control of the size of the neighborhood becomes necessary to obtain good per- formance.We have already proposed the method called Simulated Annealing with Advanced Adaptive Neighborhood (SA/AAN).This method has an adaptive neighborhood adjustment mechanism maintaining a given target acceptance ratio, and it shows very good performance for continuous optimization problems.The target acceptance ratio in this method is determined experimentally. In order to overcome this problem, SA/AAN is perfomed in parallel with differnt target acceptance ratios.The proposed methods are applied to solve many continuous optimization problems, and it is found that the methods are very useful and effective.

Key words optimization, simulated annealing, parallel, adaptive neighborhood

!"#$%

&('*),+*-(.(/ 021 354 ),6*7(8:9*; /,<(=

>:? @ A,B(C,D*E F G2H*I*D J,K*L

MONQPOROSUTWVYXOZO[QS]\Q^O_O`OSUaObQcOd

1.

^efgh

Simulated Annealing(SA)

ⁱ kjmlnompqrmsut vuwxymz{u|}m{u~u

p

#

mv

1)

SA

ⁱ ^q$%qrs

t

vum

m

v

u

mu

¡

q

p¢£k$%

iu¤¥¦m§m¨©¥¦ª«¬

p

v

®

{u¯m°umm±

²$%³´qrµ

·¶¸

#

$%³mu¹´º

* 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]

»

¢£

iu¼½

#mnu¾¿ÀÁ

iÂ

Ãv

¼½ Ä

ÅÆ

pÇ Ã´È

n ± kÉ

$%³mu®ml

»

¢£

i

®Ê#

Ä

Ç Ã´È

n v

uËÌmnu¾¿muÍ

È n v

p

Î Ïk$%³ {uÐÑ

uÒÓ´qun

v

1)

^ou ^¡

Ôq

Õmn$%³

ÐÑÃvÖ

q

i×Ø

n »

$%³

Ù

ÃÚvÛÜ

i Í È

nÚº tÏÚl

2)

Õ´nÝmÞß

Úàuá

q

ÃÚv

"m#$m%

âã

SA(Simulated Annealing with Advanced Adaptive

(2)

Neighborhood SA/AAN) ³⁾

ⁱ ^$%³ ^¾¿ ^{ ^Ý

Þß

»

Ï"#

¬

l vÖ

q

§m¨

nu´qºtÏ

» v p §

p

i àá

ÝÞß

q

»

m

v Ö{

mn {u¯°

i

¨

tÏ

» v

Ö{ ¯°

§¨

#

v p § n È

¾¿

¥

ÎÏ

i

Õ

n »

¢£

¨ t v

¶

$% !

SA(Neighborhood Parallel Sim- ulated Annealing NPSA) ⁴⁾

ⁱ ^!n ^v ^$%³ ^{

" #

{ $ %& '

u)(*

+´±

n

¨

!,Þ

- Ö q $%³

{uÐÑm

¬

´pÏ

» v p § p

i

/.0mnu$%³

v

1

Í

È { $ %

&

324Ó´qn v

ÛÜ

i Ö t ¨

2

^{§m¨ 5} ⁶ ^!mn ^vmà

á

ÝÞß

" #

{ $%&

2

uÏ¾¿

Ãmv

78

:9;

< =Ãv

± ¾¿

¥m

">

m

¾¿

"#

p

§

ã?

n »

!

#

m{

ß#mnu¾¿m* @

l v

A B

#n

#C

Ù #

²¹

p D

{

À

EÃ

2.

^FGHI

JK3LMONP Q

(SA)

SA

^{ ^7R8m:9R;

Fig. 1

^EÃ ^oS

T

T *

ÐÑ

pU

¨

t

T *

¥¦

x 0

^§¨VXW

p

Ï

©¥¦

x ⁰

^{Y Z} ^p/D ^{{[ \}

E ⁰

^uÃmv ⁿ

] © ¥ ¦

XY^Z

p

v ® { ¯ ° $ % ³ q r µ

©m

[ \

{_

0

∆E(= E ⁰ − E)

^q

T ^k

^">

ÏÝÞ`

Ñ

p ÝÞ

{

¢²£

i ©¥¦bac Ãv

Ý Þ^`

Ñ

i

dfe

1

^gm ^E ^Ã ⁶ ^%h ^{'^ij}

» v Ö{

,Þ

k±3l

p

¤m

{

T ^k

^no ^¥

¦mp

p ¨

~

,Þ

- » © {

T k +1

q

1u

r^s

¾¿

t1

v Ö { ~

,Þ

i

dfe

2

^g

» v

. 0

um

±:vwxy

p p

¨

¾¿

v

wuÃmv

n ] k¾¿

x y

iu

Ç¾¿z

#

n{u

¨ t

ÛÜ

i

¾¿z

#

vwxy

qpÏ

» v

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.

^|}~

3.1

ÛÜ¡

q

Ãv

Ù

#

¹u

i ©m

EÃ

2

^ã{ ^Ù

#

²v

de

3

^g ^EÃ

Rastrigin

^Ù

#

5)

i

¼½

Äm

¥m m Ãmv

Í À

Ù #

m±

Ð

#

mÙ

uâ

mn

»

de

4

^g ^EÃ

Griewank

Ù #

5)

i Ð

#R

Ù

âã

ÍÀ

Ù #

v ® Ê # iX

À Ù # { n À^

ã

¼½

#

i Í # {

¼½

Ä

m Ãv

f R ( x ) = N × 10 +

N

X

i =1

x ² i − 10 cos(2πx ⁱ ) (3)

Ñ

Ê

: − 5.12 < x i ≤ 5.12

Ä

: f R ( x ) = (0, 0, · · · , 0) = 0

f G ( x ) = 1 +

N

X

i =1

x ² i

4000

−

N

Y

i =1

cos

x i

√ i

(4)

Ñ

Ê

: −512 < x i ≤ 512

Ä

: f G ( x ) = (0, 0, · · · , 0) = 0

©

#

3

^q ^Ãmv ^q lu ^Ù ^# ^{j ^Ä ^{ ⁱ ^D

tt

9.94 × 10 ⁻ ¹

7.4 × 10 ⁻ ³

^v

i Ö t ±

»

[ \

q

vuÐ

#

{

Ê

Ä

Êq

ÑÃv

(3)

(a) Rastrigin function (b) Griewank function

Neighborhood range

10¹ 10^-1

10^-2

10^-3 10⁰

10^-1 10⁰

Energy

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

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

Energy

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

3.2

$%³m ¾¿

v

qp Ïk$%³´q Ä

{

ÙX

Fig. 2

^E ^Ã ⁿ ^]

Fig. 2

ⁱ ^$ ^%

³

[ \

EÃ

Ö{[ \

i Ù # ]

» Ï

30

-

¾¿

-

ÎuÏ

[ \

{

EÃ

Fig. 2

^±

3

^© ^{

Rastrigin

^Ù

# i

1.0 Griewank

^Ù ^# ⁱ

6.0

^$ ^[\ ^m±

Ö t ¨ {

u mnu$%³

{

´q:

¨ t v ou

Ö

t ¨ { i

¼½

Ä { p {

$ {

®l º

v

Ö{Ö

q

§¨

k$%³

i

nu¾¿

v m

m

pD

{ ±

u¹´º

»

¢£

iu¼½

Ä

± Ç Ã´È

n v q3

¨ t v

4.

^{|}~ !"}

SA

Õ n Ý Þ ß àká

q Ã v " # $ % â ã

SA(SA/AAN)

ⁱ ^# ^Ñ ^pÝÞß ^$ã ^$%

³

"#

Ãv

n%

©

v

ÖÖu

ÝÞß´q

i

k¾¿

Y Z

p

¶ Ñ # {

©¥

¦ { &

ÝÞ´p'£

BÃ

¾¿()

$%³mu¹

º

+*v

¢£

i [ \

{_

-,¹

n ±

ÝÞßmu®

l È n v

·¶

k¾¿

v )

$%³mu®ml

+*v

¢£

i

ËÌn¾¿Í È n ±

ÝÞß

i

¹º

È n v

pmÎ Ïk¾¿

{

ÝÞß

i/.

»

Ï$%³

ÃmvÖ

q

1032n

¡

u

] » Ï¾¿

¥ m

"p$%³

vÖ

q

l v

q3

¨ t v

3)

4.1

⁴⁵⁶⁷ ^M89

SA/AAN

^{ ^X7 ⁸ ⁹ ^; ⁱ ^{^d}

(5)

^E ^Ã:; ^Ù

#

»

Ï¾¿

{

ÝÞß

§¨

$%³

m

<ÑÃmv

Ã

n=

&

kÝÞßm

àá

{u ±?>

»

¢£

i

$%

³

H

^@ ^w ^ºBA ^u ^{^} ^± ^» ^¢£ ⁱ ^$% ^³

0

D

¹ºBA

q l $ % ³ ®ß

H

d

(6)

^{

rG

# Ñ

p²ÝÞßum

± È

»

qul

i E

®ß

}m

w º?A

v Ã

n=

& E

®ß

{ T

*

2.0

^qp²ÝÞß ^àá ^{ ^±?> ^»

¢£

i E

®ß

2

^@m ^w ^º?A ^v ^{Ö{ H} ^9;

±IE

®ß

i » È ¨

®ln

q ± v



 



 



m ⁰ = m × g(p)

g(p) = H if p > p ₁ g(p) = 0.5 if p < p ₂ g(p) = 1.0 otherwise

(5)



 



 



H = H × H(p ⁰ ), (Initial setting

^J

H = 2.0) H(p ⁰ ) = 2.0 if p ⁰ > p 1

H(p ⁰ ) = 0.5 if p ⁰ < p ₂ H(p ⁰ ) = 1.0 otherwise

(6)

K p ·² T *

i·²

> » 1·$²% ³

Ð

#LR M

} o

E

®ÚpÏ-#

Ñ p ¹´ºun Ý

Þß

-N

¤ p È » Ö{

R1 ¾²¿/()

i

Corana

{

6)

^b ^» ^ÏÝÞß

0.5

ⁿ ^v ^$%³

Ãmv

D { UPO

Ñ

$%³

¾¿

- » ÝÞß

#

Ñ

pmo

Q ?

pUk¹´ºunuÝÞß

à

# Ã

7839;

» v

3)

4.2 SA/AAN

^R

SA/AAN

ⁱ ^Í ^Èu{ ^¢£ ^mnu¾¿ ^- ^v ^u

¾¿

v ) ] »

Ï¾¿STpÏ´po Ö

q

v

ÖÖu

SA/AAN

^{màá ^ÝÞß

0.1

^qpÏ

Rast- rigin

^Ù

#

p´qul

{

¾¿UV

Fig. 3

^EÃ

Fig. 3

ⁱ ^3-W/X´º ^tS ^¾¿-STÚp ^Ï

» v

¾¿

v )

ium

v-YZ

Âuª { [

c Ý

Þ´p

ÈÈ

n ± ÝÞßmum

v

1u$%³m

D

¹\

Â

n v D {

1u

¼½

Ä

Î Ï

» v

¢£

u$

%³muÕmnu®mlmºuo

E

®´pun

» º

¨u

¶

¼

½ Ä Ê

-

±

¾¿mu]Úq

©¥¦

YZ

Â

Y

Z

ºt

v

¢£muÍ

È n v Ö t

^

»

ÝÞß

i È n

v

1u$%³mmº

¨u D

¹Úp

¼½

Ä

§m¨?_+`V ÃmÖ

q

i

±ab

qn v

¶

² Ä

Ê

c p p

d=

¨ S P

n efmu

¨

tmn

»

¢£m

v

Ö t i

$%³ { E

®

ß }m

´º?A v H

9;

uâã

1 k v #

Ä

Ê ÅÆ

pun

»g

ÁÀ

h

]1

mv

q

¨ t v

(4)

0 1 2 3 4 5 6 7 8 10^-2

10^-1 10⁰ 10¹ 10²

Annealing steps (㬍10 )

E n e rg y

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

N e ig h b o rh o o d ra n g e

㪋 Energy Best energy Neighborhood range

Fig. 3. History of energy and neighborhood range in SA/AAN.

5.

~"+ !"

SA

SA/AAN

^] ^» ^Ï ⁱ ^# ^àá ^ÝÞß ^u

¾¿

D { O Ñ

p$%³

pÏ

» p §

p ÕmnuÝÞß

i

¾¿

¥ m

Î Ï !mn

v

1uPO

Ñ

p

àá

ÝÞß { i

4Spq

i n

»

¶¸

k¾¿/()

i

®Ê#¾¿

-

1

àá

ÝÞß

È

p$%³

E

®´º?Ak¾¿

v )

iu¼½

#¾¿

-

R1

à á ÝÞß

>ÚÈ

p$%³

D ¹

º?A vÖ

qumomp

»

/K´p

¼½ Ä Ê

Î Ï

» v

d3=

¨ S àá

ÝÞßm

> »

¢£Ç *

Ä

Ê

W p

d+=

¨ S à á

ÝÞßm

» ¢

£

i

¾¿

ËÌ

Y

>Ïpo

D

Ö

"#

{$% &'Ú

»

¾m¿

¥R´

"

> Ï à á

ÝÞß

º-A

v

78Ú9 ;Úqmp Ï

! n v Ý Þ ß à·á

q Ã v " # $ % â ã !

SA(Parallel Simulated Annealing with Advanced Adaptive Neighborhood using Different Target Ac- ceptance Ratio : ARPSA)

^{< =Ãmv} ^{

Fig. 4

^EÃ

< =

{

78m:9;

i

k !

$ %& '

pÏ

Dt t !n vmàá

ÝÞß

u

¶

Ñ

*mÔq

M

$%&'{

(*

q ± ãã

¾¿

1 v

(*

i

+ mn

$ %&'

§m¨m

> » àá

ÝÞß

v

K´pk¾¿

¥ m

">$%³

-

i

¾ ¿

¥^

Ñ p ^U

(X*

q v 4 Ó v

D {

1uu´u

*´q(

(*

q ± àá

ÝÞß { r '

±

Ï - Ö qq

Ãv

Ö t

±

+m n

$ %& '

i > »

àá

SA SA SA

SA

SA SA SA

SA

SA SA SA

SA

exchange each ratio

target acceptance ratio 0.05

0.1

0.2

0.4 Synchronization

Fig. 4. Concept of ARPSA.

ÝÞßm '

±

Ï ¨

t$%³m

D

¹\

Â

n ± /D

{

Ä $ {

¼²½

#²¾¿

º

¨

R1 vÖ

q b*@

l v

¶

+m

n »

$ %& '

i /

»

àá

Ý

Þßm '

±

Ï ¨

t$%³m

E

®\

Â

n ±

¼½

Ä

Î Ï

»

´qpÏu/D

{

¼½

Ä

§m¨V

p Ä

Ê

cp ÃmvÖ

q*@ºt v

6.

^LNI89 ^!

6.1

^"#

àá

ÝÞßm

0.1

^q

0.4

^{$%&' ^] ^` ^v ^$%³

{

UV

Fig. 5

^EÃ

Fig. 5

^± ^àá ^ÝÞß

0.1

^§m¨

0.4

^>´È ⁿ ^v

q

±

¹´ºunu$%³

N

¤ l vÖ

qu=

§ v p

mÎ Ï mn

$ %& '

> » à á ÝÞß

v

Ö q

± > »

Ä

¨

tq3

¨ t v

p §

pk Ä

Ê ª {

c p

ß

i$

q%{

mn

È j

Ä

§m¨?_+` V ÃÖ

qu

ln

§

Î

Ö t

i

¾¿

v ) ] »

Ï àá

ÝÞß

mà

# Ã

1

$%

³ D

¹\

Â v

t1 ¶ $ % ³ D ¹ Ã v q

¼½ Ä

_+`V

Ã

1

4Ónu®mlºuo

/E

® ln

»

1

v

q3

¨ t v

6.2

&'67 M89

( {

Ä

<Ãv

1

i

àá

ÝÞß

Ù

n È

$%³

E

®´º?A

v

4Óm

v

$ %&'

]

» Ï ( *

+uÄ

{

WXmn

`

tms

¼½

Ä

Î Ï

» v

q:`)ÚpkÝÞß

Ù

n È M

$ %& 'm{

$%³

uÐ

#/L M

}m{

®mlºuo

E

®´º?A v

$%³

E

®´p* U

ÝÞß

i

um

v

u àá

ÝÞß

mà

#

Ãm H

9;

{

1u²$%³

i+

2

D

¹

Ãmv

Ö

Öu

k¾¿

v ) ] ` v

2

$ %& 'm{[ \

Úq$%³

{

UV

Fig. 6

^EÃ

(5)

0 2 4 6 8 10 10

^-2

10

^-1

10

⁰

Neighborhood range

Annealing steps (㬍10 ) 㩷㪇㪅㪈㩷㪇㪅㪋

4

Fig. 5. History of the neighborhood range with dif- fernt target acceptance ratio.

N ei g hb o rho o d r a ng e

Annealing steps (㬍10 )

4

1.85 1.90 1.95 2.00 2.05

10^-2 10^-1 10⁰

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

E ner g y

Best energy (P1) Best energy (P2)

Neighborhood range (P1) Neighborhood range (P2)

Fig. 6. History of energy and neighborhood ranges.

Fig. 6

^± ^X ^$%&' ^] ^» ^Ï$%³ ^o

E

®´p U

D

¹´pÏ

» v

+m WX´º tÏ

»

v Ã

n=

&

²$%³

E

®

ÃmvÖ

q

¼½

Ä

§m¨

_`V pÏ

» v

q3

¨ t v

6.3

^R

$%³ E ®

H

9;

±

Ä

Ê

-c p p

d+=

¨ S Ê {

V Ï´puo

Ö

q

v

v #

Ä

Ê ÅÆ

º A v

1

i Ö

to

F n ¾ ¿

{ Ã 4 Ó v D Ö

(*U

i

$%b&'²

²

§¨

¾¿

Ã v

Ö t

± ¶

u Ä

Ê

c p

Ã

tms $%

³m

+ 2

D

¹Úp

¼½

#¾¿

- Ö q > »

Ä

¨ t vÖ

q

$

ºt v

7.

7.1

^!

"$#

q < = { À Á

&%$'

p e f

Fig.

7

^EÃ

Fig. 7

ⁱ ^Ù

# ] »

Ï(u

{

Table 1. Parameters in each method.

Function Rastirigin Griewank

Total steps 25600 × 4 76800 × 4

Cooling steps 32

Max.(Initial) temperature 10 20

Min.(Final) temperature 0.01 0.001

Initial neighborhood range 1.0 5.12 6.0 512

Neighborhood adjustment interval 50

Neighborhood range’s parameter

adjustment interval 200

Optimum solution area Optimum solution area

10-4 10-2 100

Energy

Trial number (sorted)

10-6 10-4 10-2

Energy

Trial number (sorted)

(a) Rastrigin function (b) Griewank function

0 20 40 60 80 100

㩷㪧㪪㪘㪆㪝㪥㩷㪧㪪㪘㪆㪘㪘㪥㩷㪘㪩㪧㪪㪘

0 20 40 60 80 100

㩷㪧㪪㪘㪆㪝㪥㩷㪧㪪㪘㪆㪘㪘㪥㩷㪘㪩㪧㪪㪘

Fig. 7. Distribution of optimum solutions in 3 methods.

100

- S ã - »

²

)

m

s*

u

{u

±

[^\

F - z #

XE

p Ï » v

n ]

i

Table 1

^EÃ



 



 



ÕnO

Ñ

$%³

» v

!

SA : PSA/FN

ÕnÝÞß

àá

q

Ãv

!

SA : PSA/AAN

!n

v

ÝÞß

àá

q

Ãv

!

SA : ARPSA

o

PSA/FN

^] ^` ^v ^O ^Ñ ^$%²³ ^i+, ^N

Î Ï q

1·²²Õ nb

b

» Ï » v D pÏ²

PSA/AAN

{ à·á

Ý Þ ß i

"-#

q º·t Ï » v

0.1

^q ^p

³⁾

ARPSA

^{ ^à ^á ^Ý ^Þ ^ß ⁱ

0.05

0.1

0.2

0.4

^{

4

^ã

{

qp

Fig. 7

^± ^Ä ^ã ^» ^Ï ⁱ ^» ^S ^t ^{ ^Ù

#

] » Ï ²

ARPSA

^/Úne3f ^Ï ^» ^v

o Ä Ê ª { c p ß i

(a)Rastrigin

^Ù ^#

i

PSA/FN

^. ^v ^{ ^{

(b)Griewank

^Ù

#

i

PSA/FN

^q(&/ ^{1> ^» ^e ^f ^Ï ^» ^v ^K ^p

PSA/FN

^{ ^+$, ^N ^§ ^§ ^v ¹⁰ ^' ⁶ ² ^Ã ^v

q

< =

m

mv

q:

¨ t v Î Ï

<

=

"3#

²

±

ne/f

²Ï

» v q v

Parallel Simulated Annealing with Adaptive Neighborhood using Different Target Acceptance Ratio