Parallel Simulated Annealing with Adaptive Neighborhood using Different Target Acceptance Ratio
Hiroki HIRAO* , Yuichiro UEDA** , Mitsunori MIKI*** and Tomoyuki HIROYASU1
(Received January 7, 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 numerous local optima, the automatic control of the size of the neighborhood becomes necessary to obtain good performance. 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 performed in parallel with different 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
1.
Simulated Annealing(SA)
1) 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:hhirao@mikilab.doshisha.ac.jp
** 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 1 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)
2)
SA(Simulated Annealing with Advanced Adaptive Neighborhood SA/AAN)3)
SA(Neighborhood Parallel Simu- lated Annealing NPSA)4)
2
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)
3.
3.1
2
3 Rastrigin 5)
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.
4 Griewank 5)
fR(x) =N ×10 + N i=1
x2i−10 cos(2πxi)
(3) :−5.12< xi≤5.12
:fR(x) = (0,0,· · ·,0) = 0
fG(x) = 1 + N i=1
x2i 4000 −
N i=1
cos
√xi
i
(4) :−512< xi≤512 :fG(x) = (0,0,· · ·,0) = 0 3
9.94×10−1 7.4×10−3
3.2
Fig. 2 Fig. 2
30
Fig. 2 3 Rastrigin 1.0
Griewank 6.0
(a) Rastrigin function (b) Griewank function Neighborhood range
101 10-1
10-2
10-3 100
10-1 100
Energy
Neighborhood range 101 102 103 10-1 100
10-2 10-1 100 101 102
Energy
Fig. 2. Effect of the neighborhood range on the energy.
4. SA
SA(SA/AAN)
3)
4.1
SA/AAN (5)
m
H
H (6)
2.0 2
⎧⎪
⎪⎨
⎪⎪
⎩
m=m×g(p)
g(p) =H if p > p1 g(p) = 0.5 if p < p2 g(p) = 1.0 otherwise
(5)
⎧⎪
⎪⎨
⎪⎪
⎩
H=H×H(p), (Initial setting H= 2.0) H(p) = 2.0 if p> p1
H(p) = 0.5 if p< p2 H(p) = 1.0 otherwise
(6)
0 1 2 3 4 5 6 7 8
10-2 10-1 100 101 102
Annealing steps (㬍10 )
Energy
10-2 10-1 100 101 102
Neighborhood range
㪋 Energy Best energy Neighborhood range
Fig. 3. History of energy and neighborhood range in SA/AAN.
Corana
6) 0.5
3)
4.2 SA/AAN SA/AAN
SA/AAN 0.1 Rastrigin
Fig. 3 Fig. 3
5. SA
SA/AAN
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.
SA(Parallel Simulated Annealing with Advanced Adaptive Neighborhood us- ing Different Target Acceptance Ratio : ARPSA)
Fig. 4
6.
6.1
0.1 0.4 Fig. 5
0 2 4 6 8 10
10-2 10-1 100
Neighborhood range
Annealing steps (㬍10 ) 㩷㪇㪅㪈 㩷㪇㪅㪋
4
Fig. 5. History of the neighborhood range with differnt target acceptance ratio.
Fig. 5 0.1 0.4
6.2
2 Fig. 6
Fig. 6
6.3
Neighborhood range
Annealing steps (㬍10 )4
1.85 1.90 1.95 2.00 2.05
10-2 10-1 100
10-2 10-1 100 101
Energy
Best energy (P1) Best energy (P2)
Neighborhood range (P1) Neighborhood range (P2)
Fig. 6. History of energy and neighborhood ranges.
7.
7.1
Fig. 7
Fig. 7 100
Table 1
⎧⎪
⎪⎨
⎪⎪
⎩
SA : PSA/FN SA : PSA/AAN SA : ARPSA PSA/FN
PSA/AAN 0.1 3) ARPSA 0.05 0.1 0.2 0.4 4
Fig. 7 ARPSA
(a)Rastrigin PSA/FN
(b)Griewank PSA/FN
PSA/FN
7.2 6.3
Type A
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 meth- ods.
Fig. 8 Fig. 8
2 100
Table 1
Fig. 8 (a)Rastrigin (Type B) (b)Griewank (Type A)
2.1
8.
SA/AAN ARPSA
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
Type A Type B Type A
Type B
Fig. 8. Distribution of optimum solutions in 2 types.
SA
1)
Vol.9 No.6 pp.875-880 1997 2)
Vol.90 No.123 pp.23-29 1990 3)
Vol.44 No.1 pp.1-6 2003
4)
Transactions of JSCES Vol.2006 20060026 2006
5) D. Whitley and K. Mathias and S. Rana and J. Dzu- bera Evaluating Evolutionary Algorithms Ar- tificial Intelligence Vol.85 pp.245-2761 1996 6) A. Corana and M. Marchesi and C. Martini and S.
Ridella Minimizing Multimodal Functions of Con- tinuous Variables with the Simulated Annealing Al- gorithm ACM Trans. on Mathematical Software Vol.13 No.3 pp.262-280 1987
