oikawa.dvi

23 3 9964

1 1 2 SA 3 2.1 SA.......................................... 3 2.2 SA................................... 3 2.3 SA......................................... 6 2.4 SA....................................... 7 3 SA 9 3.1.................................. 9 3.2................................ 1 3.3...................................... 1 4 SA 14 4.1 SA..................................... 14 4.2 SA................................ 14 4.3 SA.................................. 16 5 SA 21 5.1...................................... 21 5.2............................ 21 5.3........................................... 25 6 3 6.1............................................ 3 6.2......................................... 3 i

1 1 Genetic Algorithm : GA Simulated Annealing : SA SA 2 3 SA SA 4 5 SA SA SA SA 2, 6 12 SA 13 15 16, 17 SA SA 2 SA SA SA SA SA SA Temperature Parallel Simulated Annealing : TPSA) 18, 19 SA

2 SA Neighborhood Parallel Simulated Annealing NPSA NPSA SA NPSA 2 SA 3 SA 4 NPSA SA 5 NPSA 6 2

2 SA 2.1 SA 2 SA 2 SA SA SA ( ) SA 2.2 SA SA Ω x E(x) SA 3

SA x SA Fig. 2.1 T x x E E(= E E) T k T k T k+1 Set initial parameter Generate No Acceptance criterion Yes Transition Cooling criterion No Yes Cooling Terminal criterion No End Yes Fig. 2.1 Algorithm of simulated annealing 2.2.1 Generate x x x x G(x, x ) x x (2.1) n(x) x 4

G(x, x )= 1 n(x) 2.2.2 Accept criterion (2.1) x E x E E(= E E) T (2.2) Metropolis 3 A(E,E 1 if E <,T)= exp ( E ) T otherwise (2.2) T 2.2.3 Cooling ( ) k T k T k+1 (2.3) T k+1 = T 1 log k (2.3) (2.3) (2.4) T k+1 = γt k (.8 γ<1) (2.4) (2.4) Fig. 2.2 2.2.4 2 Terminal criterion 5

Max Temperature Min Time Fig. 2.2 Temperature schedule 2.3 SA SA (2.4) 2 21 2, 6, 7 14, 15, 22, 23 4 SA 4, 24 SA SA (1) (2), (3), (4) SA 2 21 1 (1),(2),(3) (4) 2 x y z x x y z x z y y z 2 (4) (1),(2),(3) (AG ) AG 1 AG AG SA 6

2.4 SA SA 25, 26 Pseudo-parallelization of SA SA SA SA SA Data Configuration Partition(DCP) Parallel independent annealing(pia) Parallel Markov Chains(PMC) Simulated Annealing Parallel Algorithm (SAPA) SAPA SA SA SAPA SA Parallel Markov Chains(PMC) Parallel Markov Trials(PMT) Adaptive Parallel Simulated Annealing(APSA) Spectulative Trees Systolic PMC SA Pseudo-parallelization of SA SAPA SA Data Configuration Partition(DCP) DCP SA SA 24, 27, 28 Parallel Independent Annealing(PIA) PIA SA SA 4, 27 PIA SA Parallel Markov Chains(PMC) PMC SA PIA SA PMC PMC PIA 4, 24, 28 7

Parallel Markov Trials(PMT) SAPA SA 4, 24, 29 Adaptive Parallel Simulated Annealing(APSA) PMC PMT PMC PMT 4, 28 PMT SAPA Speculative Trees SA 24 Systolic 24, 3 SA 8

3 SA 3.1 SA Fig. 3.1 Fig. 3.1 2 x x ( ) 1 16, 17 2 FSA(Fast Simulated Annealing) Cauchy 14 3 VFA(Very Fast Annealing) 15 2 dimensional problem space Neighborhood x 1 x x 2 x Fig. 3.1 Two dimensional problem space 9

3.2 (3.1) Rastrigin (3.2) Griewank n Fig. 3.2 Rastrigin Griewank n ( F Rastrigin (x i ) = 1n + x 2 i 1 cos(2πx i ) ) (3.1) ( 5.12 x i < 5.12) F Griewank (x) = 1+ n i=1 i=1 x 2 n i 4 (x i = x i/1 5.12 x i < 5.12) i=1 ( cos ( x ) ) i (3.2) i 3.3 SA SA 3.3.1 Rastrigin 5.12 1/1 Griewank 1/1 1 2 1 Table 3.1 (2.4) 32 Table 3.1 Parameters in preliminary experiments Max temperature 1. Minimum temperature.1 Number of cooling Steps 32 Cooling cycle 124 Number of cnnealings 124 32 3.3.2 SA 3 Fig. 3.3 1

4 8 6 4 2-5 -2.5 2.5 5-5 -2.5 5 2.5 2-2 -4-4 -2 2 4 (a) Landscape of Rastrigin (b) Contour map of Rastrigin 4 2 1 5-5 -2.5 2.5 5-5 -2.5 5 2.5-2 -4-4 -2 2 4 (c) Landscape of Griewank (d) Contour map of Griewank.1 2 1.5 1.5 -.1 -.5.5.1.5 -.5.1 -.1.5 -.5 -.1 -.1 -.5.5.1 (e) Local landscape of Griewank (f) Local contour map of Griewank Fig. 3.2 Landscape and contour map (Rastrigin, Griewank) 11

(a) 2 dimensional Rastrigin (b) 1 dimensional Rastrigin (c) 2 dimensional Griewank (d) 1 dimensional Rastrigin Fig. 3.3 Relation between neighborhood range and energy (Rastrigin, Griewank) 12

3.3.3 Fig. 3.3 a 2 Rastrigin 1. 1. Fig. 3.2 b 1 Rastrigin.1 2 2 Griwank.4.7 Fig. 3.2 f 1.5 13

4 SA 4.1 SA 3.3 SA 2 SA 4.2 SA SA SA SA Neighborhood Parallel Simulated Annealing :NPSA NPSA Fig. 4.1 Fig. 4.2 New neighborhood are assigned for all SA processes. SA SA SA SA Adjust Neighborhood Gather energy Sort Assign neighborhood in order of energy SA SA SA SA Adjust Neighborhood SA SA SA SA Adjust Neighborhood SA SA SA SA Each processor has a different neighborhood. Neighborhood are adjusted at each cooling step Fig. 4.1 Neighborhood Parallel Simulated Annealing NPSA NPSA, 14

Set initial parameters Generate No Acceptance criterion Transition Yes Cooling criterion No Yes Cooling Adjust Neighborhood Scynclonize Sort energy Assign neighborhood No Terminal criterion End Yes Fig. 4.2 Algorithm of NPSA 15

NPSA NPSA SA 4.3 SA 4.3.1 NPSA 3 3 SA SA SA PSA NPSA 2 Rastrigin Griewank 3.3 SA PSA Rastrigin 1. Griewank.5 NPSA Rastrigin 1/1 Griewank 1/1 PSA NPSA 32 SA SA 1/32 SA SA Table 4.1 Table 4.1 Parameters in experiments Method SA PSA, NPSA Number of processes 1 32 Max temperature 1. 1. Minimum temperature.1.1 Number of cooling steps 32 32 Cooling cycle 124 32 Number of annealings 124 32 (32 32) 32 4.3.2 Rastrigin Griewank 3 Fig. 4.3 a, b 3 PSA NPSA Fig. 4.4 Fig. 4.5 Fig. 4.4 a Fig. 4.5 a PSA Fig. 4.4 b Fig. 4.5 b NPSA 16

(a) Rastrigin (b) Griewank Fig. 4.3 Comparison of the qualities of solutions 17

(a) PSA (b) NPSA Fig. 4.4 History of energy and neighborhood range for Rastrigin 18

(a) PSA (b) NPSA Fig. 4.5 History of energy and neighborhood range for Griewank 19

4.3.3 Fig. 4.3 a, b SA PSA NPSA Fig. 4.4 Fig. 4.5 PSA NPSA NPSA SA PSA NPSA 2

5 SA 5.1 4.3 NPSA SA NPSA (5.1) Egg Holder (5.2) Rana n 1 ( ) ( ) F Eggholder (x) = x i sin ( x ) i P P sin P + x i /2 (5.1) P = x i+1 +47 i=1 (x i = x i /1 5.12 x i < 5.12) n 1 ( F Rana (x) = x i sin(q)cos(r)+(x i +1)cos(Q)sin(R) ) (5.2) i=1 Q = x i+1 +1 x i, R = x i+1 +1+x i (x i = x i /1 5.12 x i < 5.12) Fig. 5.1 Egg Holder Rana 3.3 Egg Holder Rana Rastrigin Fig. 5.2 Egg Holder Rana Fig. 5.2 Egg Holder Rana Fig. 5.1 b d NPSA 5.2 5.2 5.2.1 Hinton 22 x T k D (5.3) ( 1 x 2 ) g k ( x) = exp (5.3) (2πT k ) D/2 2T k (5.3) 21

4 2 1 5-5 5 2.5-5 -2-2.5-2.5-4 2.5 5-5 -4 (a) Landscape of Egg Holder -2 2 4 (b) Contour map of Egg Holder 4 2 5 25-25 -5-5 5 2.5-2 -2.5-2.5-4 2.5 5-5 -4 (c) Landscape of Rana -2 2 (d) Contour map of Rana Fig. 5.1 Landscape and contour map (Egg Holder, Rana) 22 4

(a) 2 dimensional Egg Holder (b) 2 dimensional Rana Fig. 5.2 Relation between neighborhood range and energy (Egg Holder, Rana) 5.2.2 5 1/4 6.5536 4.6.1 1 2 Fig. 5.3 (5.3) 1/1 1/4 6.5536 1 4 2 Fig. 5.4 a Fig. 5.4 b 23

.4 f(x).3.2.1-3 -2-1 1 2 3 x Fig. 5.3 The generation percentage within average 2.2.15.1.5-4 -2 x2 2 4 4 2 x1-2 -4 (a) Normal distribution at max temperature 2 15 1 5-4 -2 x2 2 4 4 2 x1-2 -4 (b) Normal distribution at minimum temperature Fig. 5.4 Normal distribution 24

5.3 5.3.1 NPSA Egg Holder Rana SA SA SA PSA NPSA 3 124 2 6 32768 Table. 5.1 Table 5.1 Parameters in experiments Method SA PSA, NPSA Number of processes 1 32 Number of cooling steps 32 32 Max temperature 6.6636 6.5536 Minimum temperature 6.5536 1 4 6.5536 1 4 5.3.2 Egg Holder Rana Fig. 5.5 a, b 3 32768 PSA NPSA Fig. 5.6 Fig. 5.7 Fig. 5.6 a Fig. 5.7 a PSA Fig. 5.6 b Fig. 5.7 b NPSA 1 124 2.56 2.56 1 2 25

(a) Egg Holder (b) Rana Fig. 5.5 Performance of methods 26

(a) PSA (b) NPSA Fig. 5.6 History of energy and SD for Egg Holder 27

(a) PSA (b) NPSA Fig. 5.7 History of energy and SD for Rana 28

5.3.3 Fig. 5.5 a, b SA PSA NPSA PSA NPSA NPSA Rana Egg Holder PSA PSA NPSA PSA NPSA PSA NPSA NPSA SA PSA 29

6 6.1 SA SA Neighborhood Parallel Simulated Annealing : NPSA NPSA SA NPSA SA NPSA NPSA PSA NPSA NPSA SA 6.2 NPSA 3

31

1) Reeves, C.R.,,.., 1997. 2) Kirkpatrick, S., Gelett Jr. C. D.,, Vecchi, M. P. Optimization by Simulated Annealing. Science, 1983. 3) Metropolis, N., Rosenbluth, A., Rosenbluth, M., Teller, A., Teller, E. Equation of State Calculation by Fast Computing Machines. Journ. of Chemical Physics, 1953. 4) E. Aarts and J. Korst. Simulated Annealing and Boltzmann Machines. john Wiley & Sons, 1989. 5).., 1998. 6) E. Aarts and P.J.M. Van Laarhoven. Statistical cooling: A general approach to combinatorial optimization problems. Philips J. Res, Vol. 4, pp. 193 226, 1985. 7) M. Lundy and A. Mees. Convergence of an annealing algorithm. Math. Programming, Vol. 34, pp. 111 124, 1986. 8) David T.CONNOLY. An improved annealing scheme for the qap. European Journal of Operational Research, Vol. 46, pp. 93 1, 199. 9) Mark Fielding Harry Cohn. Simulated annealing: Searching for an optimal temperature schedule. SIAM J. Optim, Vol. 9, pp. 779 82, 1999. 1) Mark Fielding. Simulated annealing with an optimal fixed temperature. SIAM J., Vol. 11, No. 2, pp. 289 37, 2. 11) F.Romeo M.D.Huang and A.Sangiovanni-Vincentelli. An efficient general cooling schedule for simulated annealing. IEEE, pp. 225 23, 1986. 12) Steave R. White. Concepts of scale in simulated annealing. Proceeding IEEE Intl. Conf. Comp. Des.(ICCD), pp. 646 651, 1984. 13) B. Rosen. Functional Optimization based on Advance Simulated Annealing. IEEE Workshop on Physics and Computation, 1992. 14) Harold Szu and Ralph Hartley. Fast simulated annealing. Physics Letters A, Vol. 122, No. 3,4, pp. 157 162, 1987. 15) L. Ingber and B. Rosen. Genetic algorithms and very fast simulated reannealing: A comparison. Mathematical and Computer Modelling, Vol. 16, No. 11, pp. 87 1, 1992. 32

16) Marchesi M. Martini C. Corana, A. and S. Ridella. Minimizing Multimodal Functions of Continuous Variables with the Simulated Annealing Algorithm. ACM Trans. on Mathematical Software, 1987. 17),,.., 23. 18).., Vol. NC9-1,, 199. 19),,.., Vol. 36, No. 4, pp. 797 87, 1995. 2) Collins, N E, Eglese, R W andgolden, B L Simulated Annealing-an annotated bibliography. AmericanJ Math Management Sci, 1988. 21) Rosen, B E,.., 1994. 22) Sejnowski T.J. Hinton, G.E. and D.H. Achley. Boltzmann machines: constraint satisfaction networks that learn. Technical Report CMU-CS, pp. 84 119, 1984. 23) L. Ingber. Very fast simulated re-annealing. Mathematical and Computer Modelling, Vol. 12, pp. 967 973, 1989. 24) Daniel R. Greening. Parallel simulated annealing techniques. Physica D, Vol. 42, pp. 293 36, 199. 25) Hector Sanvicente S. and Juan Frausto S. A methodology to parallel the temperature cycle in simulated annealing. Lectures Notes on Computer Science, pp. 63 74, 2. 26) Hector Sanvicente S. and Juan Frausto S. Mpsa : A methodology to parallelize simulated annealing and its application to the traveling salesman problem. MICAI22, LNAI3213, pp. 89 97, 22. 27) K. Ganeshan K. Krishna and D. Janaki Ram. Distributed simulated annealing algorithms for job shop scheduling. IEEE Transactions on Systems, man, and Cybernetics, Vol. 25, No. 7, pp. 112 119, 1995. 28) R. Luling R. Diekmann and J. Simon. Problem independent distributed simulated annealing and its application. Proceeding of the 4th IEEE SPDP, pp. 1 23, 1993. 29) James R.A. ALLWRIGHT. A distributed implementation of simulated annealing for the traveling salesman problem. Parallel Computing, Vol. 1,. 33

3) P.M.A. Sloot J.M. Voogd and R.v.Dantzig. Comparison of vector and parallel implementation of simulated annealing algorithm. Future Generation Computer Systems, special issue HPCN 94, Vol. 11,. 34