Parallel Simulated Annealing with Adaptive Neighborhood
Hiroki HIRAO*, Yuichiro UEDA*, Mitsunori MIKI** and Tomoyuki HIROYASU***
(Received January 20, 2009)
Simulated Annealing(SA) is one of the general heuristic methods to solve the optimization problems. In the case that SA is applied to continuous problems, 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
1.
Simulated Anneal- ing:SA
1)
SA
2)
SA
SA
* Graduate Student, Department of Knowledge Engineering and Computer Sciences, Doshisha University, Kyoto Telephone:+81-774-65-6921, Fax:+81-774-65-6716, E-mail:yueda@mikilab.doshisha.ac.jp
** Department of Knowledge Engineering and Computer Sciences, Doshisha University, Kyoto Telephone:+81-774-65-6930, Fax:+81-774-65-6716, E-mail:mmiki@mail.doshisha.ac.jp
*** Faculty of Life and Medical Sciences, Doshisha University, Kyoto
Telephone:+81-774-65-6932, Fax:+81-774-65-6019, E-mail:tomo@is.doshisha.ac.jp
1) 3)
4)
SA SA with Advanced Adaptive
Neighborhood:SA/AAN 5) SA Neigh- borhood Parallel SA:NPSA 6)
SA/AAN
NPSA
SA 2 SA
PSA/AN(2N) 3
SA PSA/AN(3N)
2. (SA)
SA Fig. 1 T
x0
x E
ΔE(= E−E) Tk
(1)
Tk
Tk+1
(2)
A(E, E, T) =
⎧⎨
⎩
1 if ΔE <0 exp(−ΔE
T ) otherwise (1) Tk+1=γTk(0.8≤γ <1) (2)
Initial Parameter Setting
Generation
Acceptance Criterion
Transition
Cooling Criterion
Cooling
Terminal Criterion
End Yes
Yes
Yes No
No
No
Fig. 1. Algorithm of Simulated Annealing.
3.
2 (3) Rastrigin 7)
2
100 (4) Griewank
7)
3 Rastrigin Griewank
9.94 10−1 7.4 10−3
fR(x) = (N×10) + N i=1
x2i −10 cos(2πxi)
:−5.12< xi≤5.12,
:min(fR(x)) =fR(0,0, . . . ,0),
:fR(x) = 0 (3)
fG(x) = 1 + N i=1
x2i 4000 −
N i=1
cos
√xi
i
:−512< xi≤512,
:min(fG(x)) =fG(0,0, . . . ,0),
:fG(x) = 0 (4)
Neighborhood range 101 10-1
10-2
10-3 100
10-1 100
(a) Rastrigin function
Neighborhood range 101 102 103 10-1 100
10-2 10-1 100 101 102
(b) Griewank function
Energy Energy
Fig. 2. Effect of the neighborhood range on the en- ergy.
4. SA
4.1
SA
1
1)
Fig. 2 Fig. 2
30
3 Fig. 2 3 Rastrigin
1.0 Griewank 6.0
SA
4.2
SA
2 1
SA(SA/AAN)5 )
1 SA(NPSA)6 )
SA/AAN
5) NPSA
6)
SA/AAN
NPSA
2
SA PSA/AN(2N) 3
SA PSA/AN(3N)
SA
5. 2 SA
(PSA with Adaptive Neighborhood using Two Neighborhood ranges PSA/AN(2N)) 5.1
2
( )
5.2
2
2
(5) (7) Nl Ns
r Fig. 3
(a-1)
Nlnext=Nlcur
Nsnext=Nscur×r (5) (a-2)
Nlnext =Nlcur ×1/r Nsnext =Nscur
(6)
(b) ( )
Nlnext=Nlcur ×r
Nsnext =Nscur ×1/r (7)
( )
(5) (6)
2 (
) (7)
10−3
2
C C
D
Annealing steps
C
Neighborhood range
Fig. 3. Change in neighborhood of PSA/AN(2N).
㪇 㪉 㪋 㪍
10-2 10-1 100 101 102
㩷㪙㪼㫊㫋㩷㪼㫅㪼㫉㪾㫐
㪘㫅㫅㪼㪸㫃㫀㫅㪾㩷㫊㫋㪼㫇㫊㩷㩿㬍㪈㪇
㪋㩷㪀
㪜㫅㪼㫉㪾㫐
100 101 102 103 104 㩷㪣㪸㫉㪾㪼㩷㫅㪼㫀㪾㪿㪹㫆㫉㪿㫆㫆㪻㩷㫉㪸㫅㪾㪼 㩷㪪㫄㪸㫃㫃㩷㫅㪼㫀㪾㪿㪹㫆㫉㪿㫆㫆㪻㩷㫉㪸㫅㪾㪼
㪥㪼㫀㪾㪿㪹 㫆㫉㪿㫆㫆㪻 㩷㫉㪸㫅㪾㪼
Fig. 4. History of Energy and Neighborhood ranges in PSA/AN(2N).
Fig. 4 Fig. 4
6. 3 SA
(PSA with Adaptive Neighborhood using Three Neighborhood ranges PSA/AN(3N)) 6.1
3
( )
PSA/AN(2N)
6.2
3
3
(8) (11) Nl Nm Ns
r Fig. 5
(a-1)
⎧⎪
⎪⎨
⎪⎪
⎩
Nlnext=Nlcur×r
Nmnext=Nmcur×r(=Nlcur) Nsnext=Nscur×r(=Nmcur)
(8)
(a-2)
⎧⎪
⎪⎨
⎪⎪
⎩
Nlnext=Nmcur×r Nmnext =Nmcur
Nsnext =Nmcur ×1/r
(9)
(a-3)
⎧⎪
⎪⎨
⎪⎪
⎩
Nlnext=Nlcur×1/r(=Nmcur) Nmnext =Nmcur ×1/r(=Nscur) Nsnext =Nscur ×1/r
(10)
(b) ( )
⎧⎪
⎪⎨
⎪⎪
⎩
Nlnext =Nlcur×r Nmnext=Nmcur
Nsnext=Nscur×1/r
(11)
PSA/AN(2N) 3
(8) (10)
(11)
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 100 101 102
㩷㪙㪼㫊㫋㩷㪼㫅㪼㫉㪾㫐
㪘㫅㫅㪼㪸㫃㫀㫅㪾㩷㫊㫋㪼㫇㫊㩷㩿㬍㪈㪇
㪋㩷㪀
㪜㫅㪼㫉㪾㫐
10-2 10-1 100 101 102 103 㩷㪣㪸㫉㪾㪼㩷㫅㪼㫀㪾㪿㪹㫆㫉㪿㫆㫆㪻㩷㫉㪸㫅㪾㪼 㩷㪤㫀㪻㪻㫃㪼㩷㫅㪼㫀㪾㪿㪹㫆㫉㪿㫆㫆㪻㩷㫉㪸㫅㪾㪼 㩷㪪㫄㪸㫃㫃㩷㫅㪼㫀㪾㪿㪹㫆㫉㪿㫆㫆㪻㩷㫉㪸㫅㪾㪼
㪥㪼㫀㪾㪿㪹 㫆㫉㪿㫆㫆㪻 㩷㫉㪸㫅㪾㪼
Fig. 6. History of Energy and Neighborhood ranges in PSA/AN(3N).
1 Fig. 6 Fig. 6
(a) Type A Annealingsteps
Neighborhood range (b) Type B (c) Type C
Fig. 7. Change in neighborhood of PSA/AN(3N).
Table 1. Ratio of solutions that reached the opti- mum solution area.
Algorithms Type A Type B Type C Rastrigin function 66% 86% 93%
Griewank function 54% 55% 59%
6.3
PSA/AN(3N)
Fig. 7 3
Type A : Type B : Type C :
3
100 Table 1
Table 1 Type C
Type A Type B
Type C
Type C
7.
7.1
PSA/AN(3N)
PSA/AN(2N)
PSA/AN(2N) PSA/AN(3N) 3
Table 2 Table 3
3 SA 2
SA 2/3
SA (Synchronization interval) (Increasing ratio) 2
PSA/AN
r
7.2
100
Fig. 8 PSA/AN(2N)
PSA/AN(3N) 1
Rastrigin
10.24 1.0
Griewank 1024
6.0
PSA/AN(3N) PSA/AN(2N)
8.
SA
Table 2. Parameters for Rastrigin function.
Methods PSA/AN(2N) PSA/AN(3N)
Total steps 57600 38400
Cooling number 32 32
Max. temperature 10.0 10.0
Min. temperature 0.01 0.01
Max. neighborhood range 10.24 10.24
Min. neighborhood range 10.24×10−3 10.24×10−3
Synchronization interval 450 400
Increasing ratio 1.5 2.0
Table 3. Parameters for Griewank function.
Methods PSA/AN(2N) PSA/AN(3N)
Total steps 115200 76800
Cooling number 32 32
Max. temperature 20.0 20.0
Min. temperature 0.001 0.001
Max. neighborhood range 1024 1024
Min. neighborhood range 1024×10−3 1024×10−3
Synchronization interval 180 150
Increasing ratio 2.0 2.0
PSA/AN(2N) PSA/AN(3N)
PSA/AN(2N)
1)
Vol.9 No.6 pp.870-875 1997 2) L. Ingber Genetic Algorithms and Very Fast
Simulated Reannealing : A Comparison , Mathe- matical and Computer Modelling Vol.16 No.11
Optimum solution area Optimum solution area
0 20 40 60 80 100
10-6 10-4 10-2 100
Energy
Trial number (sorted) PSA/AN(2N) PSA/AN(3N)
0 20 40 60 80 100
10-6 10-4 10-2
Energy
Trial number (sorted) PSA/AN(2N) PSA/AN(3N)
(a) Rastrigin function (b) Griewank function
Fig. 8. Distribution of optimum solutions.
pp.87-100 1992 3)
1990
4) 2
67 Vol.1 pp.259-260 2005 5)
Vol.44 No.1 pp.1-6 2003
6)
No.20060026 2006
7) D. Whitley and K. Mathias and S. Rana and J. Dzubera Evaluating Evolutionary Algo- rithms Artificial Intelligence Vol.85 pp.245- 2761 1996
