1 /*--------------------------------------------------------------------------------------------------
2   Anneal a system to a low cost.
3 --------------------------------------------------------------------------------------------------*/
4 #include <math.h>
5 #include <stdlib.h>
6 #include "dv.h"
7 #include "dw.h"
8 #define AN_RANDOM_SYSTEMS 32
9 #define AN_MOVES_PER_ELEMENT 20
10 #define AN_FREEZE_TEMP 0.1
11 
12 double anTemperature;
13 int64 anCost;
14 
15 /*--------------------------------------------------------------------------------------------------
16   Find the standard deviation of random systems.
17 --------------------------------------------------------------------------------------------------*/
findInitialTemperature(void)18 static double findInitialTemperature(void) {
19     int64 costs[AN_RANDOM_SYSTEMS];
20     int64 totalCost = 0;
21     int64 totalOfSquares = 0;
22     int64 averageCost, difference;
23     uint16 xRandomSystems;
24 
25     for(xRandomSystems = 0; xRandomSystems < AN_RANDOM_SYSTEMS;
26         xRandomSystems++) {
27         anCost = anCost + anRandomizeSystem();
28     }
29     for(xRandomSystems = 0; xRandomSystems < AN_RANDOM_SYSTEMS; xRandomSystems++) {
30         anCost = anCost + anRandomizeSystem();
31         costs[xRandomSystems] = anCost;
32         totalCost = totalCost + costs[xRandomSystems];
33     }
34     averageCost = totalCost/AN_RANDOM_SYSTEMS;
35     for(xRandomSystems = 0; xRandomSystems < AN_RANDOM_SYSTEMS; xRandomSystems++) {
36         difference = costs[xRandomSystems] - averageCost;
37         totalOfSquares = totalOfSquares + difference*difference;
38     }
39     return sqrt(totalOfSquares/AN_RANDOM_SYSTEMS);
40 }
41 
42 /*--------------------------------------------------------------------------------------------------
43   Anneal a system to a low cost.
44 --------------------------------------------------------------------------------------------------*/
anAnneal(double coolingFactor)45 void anAnneal(
46     double coolingFactor)
47 {
48     uint32 xMove, movesPerCycle;
49     uint32 numElements;
50     int64 deltaCost;
51 
52     anCost = anInitializeSystem(&numElements);
53     movesPerCycle = numElements*AN_MOVES_PER_ELEMENT;
54     anTemperature = findInitialTemperature();
55     if(numElements > 0) {
56         do {
57             anInitializeCycle(anTemperature);
58             for (xMove = 0; xMove < movesPerCycle; xMove++) {
59                 deltaCost = anMakeRandomMove();
60                 if (deltaCost > 0 && (int32)(UINT16_MAX*exp(-deltaCost/anTemperature)) <= (int32)utRandN(UINT16_MAX)) {
61                     anUndoMove();
62                 } else {
63                     anCost = anCost + deltaCost;
64                 }
65             }
66             anTemperature *= coolingFactor;
67         } while(anTemperature > 0.1);
68     }
69 }
70