1 '''module simulated_annealing
2 - implements a simulated annealing optimization concept
3 - main function can be called either from console or from GUI(recommended)
4 - saves solution files in standard folder for data
5
6 @author: Tobias Heimpold
7 '''
8 import math, numpy, random, os
9 from dsc_suite.tools.toolpaths import FOLDER_FOR_DATA
10 from time import strftime, time
11
13 '''generate_simulated_annealing_data
14 parameter:
15 - functions: dictionary with functions from datastructure
16 essential keys:
17 - "randomSolution" : returns a random representation
18 - "changeSolution" : returns a function to change the given
19 representation
20 - "costEvaluation" : returns the calculated costs for the
21 given representation
22
23 - parameters : dictionary with algorithm parameters
24 essential keys:
25 - "Tstart" : initial temperature of algorithm
26 - "Tend" : temperature to reach with annealing
27 - "Tsteps" : steps between start and end temperature
28 - "Tsamples" : number of generated solutions each step
29 - "correct_factor" : factor to adjust the acceptance probability
30
31 - file_info: dictionary with information about the file names of the data files
32 essential keys:
33 - "trial_name" : name of trial given in GUI
34 - "file_name_list" : additional information included in file name (can be empty string)
35
36 - time_check: boolean
37 True: estimates runtime with reduced samples
38 False: full calculation with saving data to files
39 '''
40
41 import psyco
42 psyco.full()
43 if time_check:
44 tsamples = parameters["Tsamples"]
45 parameters["Tsamples"] = 10
46 tsteps = parameters["Tsteps"]
47 parameters["Tsteps"] = 3
48
49 temp = parameters["Tstart"]
50 n = 1./(parameters["Tsteps"]-1.)
51 alpha = (float(parameters["Tend"])/float(parameters["Tstart"]))**n
52
53
54
55
56
57 correct_factor = float(((-1)*math.log(0.1)*float(parameters["Tend"]))/parameters["correct_factor"])
58
59 solution = functions["randomSolution"]()
60 costs = functions["costEvaluation"](solution)
61
62 cost_data = []
63 for cost in costs:
64 cost_data.append([])
65 cost_data.append([])
66
67
68
69 while temp >= parameters["Tend"]:
70
71 tabu_list = []
72 istart = time()
73
74 number_of_acepted = 0
75 number_of_impr = 0
76
77 i = 0
78 while (i < parameters["Tsamples"]):
79 i +=1
80
81 new_solution = functions["changeSolution"]()(solution)
82
83 tries = 0
84 while (new_solution in tabu_list) and (tries < parameters["Tsamples"]):
85 new_solution = functions["changeSolution"]()(solution)
86 tries += 1
87
88 tabu_list.append(new_solution)
89
90 old_cost = functions["costEvaluation"](solution)
91 sum_old = old_cost[len(old_cost)-1]
92 new_cost = functions["costEvaluation"](new_solution)
93 sum_new = new_cost[len(new_cost)-1]
94
95 d_cost = sum_new - sum_old
96
97 randcrit = random.random()
98
99 if d_cost < 0:
100 number_of_impr +=1
101 solution = new_solution
102 for cost in new_cost:
103 cost_data[new_cost.index(cost)].append(cost)
104 cost_data[len(cost_data)-1].append(temp)
105
106 elif d_cost == 0:
107 pass
108
109 else:
110
111 exp = math.exp(-1*(d_cost*correct_factor/temp))
112 print exp
113
114 if randcrit < exp and exp < 1.0:
115 number_of_acepted +=1
116 solution = new_solution
117 for cost in new_cost:
118 cost_data[new_cost.index(cost)].append(cost)
119 cost_data[len(cost_data)-1].append(temp)
120
121 iend = time()
122
123 print "Temp "+str(temp)
124 print "Improved "+str(number_of_impr)
125 print "Accepted "+str(number_of_acepted)
126
127 temp *= alpha
128
129
130 psyco.stop()
131
132 iruntime = iend - istart
133
134 if time_check:
135 parameters["Tsamples"] = tsamples
136 parameters["Tsteps"] = tsteps
137 if time_check:
138 runtime = tsteps*tsamples*iruntime/10
139 return runtime
140
141 trial_name = file_info["trial_name"]
142 file_name_list = file_info["file_name_list"]
143 path = '/' + trial_name + '/Simulated Annealing/'
144 if not os.path.exists(FOLDER_FOR_DATA + path):
145 os.makedirs(FOLDER_FOR_DATA + path)
146 filename_list = []
147 for list in cost_data:
148 file_name_begin = file_name_list[cost_data.index(list)]
149 i = 1
150 filename = file_name_begin + ' %02i sta%.1f end%.1f ste%i sam%i.npy' % (i, parameters["Tstart"], parameters["Tend"], parameters["Tsteps"] ,parameters["Tsamples"])
151 while os.path.exists(FOLDER_FOR_DATA + path + filename):
152 i += 1
153 print i
154 filename = file_name_begin + ' %02i sta%.1f end%.1f ste%i sam%i.npy' % (i, parameters["Tstart"], parameters["Tend"], parameters["Tsteps"] ,parameters["Tsamples"])
155 filename_list.append(path + filename)
156 if not time_check:
157 numpy.save(FOLDER_FOR_DATA + path + filename, numpy.float64(list))
158
159 return filename_list
160