Skip to content

Commit ffeed8b

Browse files
hazhaz
committed
Put in the first attempt of a dynamic heuristic selection.
1 parent fac42b3 commit ffeed8b

1 file changed

Lines changed: 118 additions & 51 deletions

File tree

‎flow-shop/flow.py‎

Lines changed: 118 additions & 51 deletions
Original file line numberDiff line numberDiff line change
@@ -6,30 +6,31 @@
66
##############
77
## Settings ##
88
##############
9-
TIME_LIMIT = 10
10-
9+
TIME_LIMIT = 30
10+
TIME_INCREMENT = 5
11+
DEBUG_SWITCH = True
1112

1213
##############################
1314
## Neighbourhood Generators ##
1415
##############################
1516

16-
def _neighbours_random(ctx, perm, num = 1):
17+
def _neighbours_random(data, perm, num = 1):
1718
candidates = [perm]
1819
for i in range(num):
1920
candidate = perm[:]
2021
random.shuffle(candidate)
2122
candidates.append(candidate)
2223
return candidates
2324

24-
def _neighbours_swap(ctx, perm):
25+
def _neighbours_swap(data, perm):
2526
candidates = [perm]
2627
for (i,j) in combinations(range(len(perm)), 2):
2728
candidate = perm[:]
2829
candidate[i], candidate[j] = candidate[j], candidate[i]
2930
candidates.append(candidate)
3031
return candidates
3132

32-
def _neighbours_LNS(ctx, perm, size = 2):
33+
def _neighbours_LNS(data, perm, size = 2):
3334
candidates = []
3435
for subset in combinations(range(len(perm)), size):
3536
best_make = makespan(data, perm)
@@ -38,7 +39,7 @@ def _neighbours_LNS(ctx, perm, size = 2):
3839
candidate = perm[:]
3940
for i in range(len(ordering)):
4041
candidate[subset[i]] = perm[ordering[i]]
41-
res = makespan(ctx['data'], candidate)
42+
res = makespan(data, candidate)
4243
if res < best_make:
4344
best_make = res
4445
best_perm = candidate
@@ -51,15 +52,15 @@ def _neighbours_LNS(ctx, perm, size = 2):
5152
## Heuristics ##
5253
################
5354

54-
def _heur_hillclimbing(ctx, candidates):
55-
scores = [(makespan(ctx['data'], perm), perm) for perm in candidates]
55+
def _heur_hillclimbing(data, candidates):
56+
scores = [(makespan(data, perm), perm) for perm in candidates]
5657
return sorted(scores)[0][1]
5758

58-
def _heur_random(ctx, candidates):
59+
def _heur_random(data, candidates):
5960
return random.choice(candidates)
6061

61-
def _heur_random_hillclimbing(ctx, candidates):
62-
scores = sorted([(makespan(ctx['data'], perm), perm) for perm in candidates])
62+
def _heur_random_hillclimbing(data, candidates):
63+
scores = sorted([(makespan(data, perm), perm) for perm in candidates])
6364
i = 0
6465
while (random.random() < 0.5) and (i < len(scores)):
6566
i += 1
@@ -70,27 +71,70 @@ def _heur_random_hillclimbing(ctx, candidates):
7071

7172

7273
STRATEGIES = [
73-
{'name': 'Random search.',
74-
'heur': _heur_random,
75-
'neigh': partial(_neighbours_random, num=1)},
76-
{'name': 'Random neighbours, pseudo-random selection.',
77-
'heur': _heur_random_hillclimbing,
78-
'neigh': partial(_neighbours_random, num=100)},
79-
{'heur': _heur_random_hillclimbing,
80-
'neigh': partial(_neighbours_LNS, size=2)},
81-
{'heur': _heur_random_hillclimbing,
82-
'neigh': partial(_neighbours_LNS, size=3)}
74+
{
75+
'name': 'Random search.',
76+
'heur': _heur_random,
77+
'neigh': partial(_neighbours_random, num=1),
78+
'weight': 1
79+
},
80+
{
81+
'name': 'Random neighbours, randomly biased selection.',
82+
'heur': _heur_random_hillclimbing,
83+
'neigh': partial(_neighbours_random, num=100),
84+
'weight': 1
85+
},
86+
{
87+
'name': 'Random neighbours, hillclimbing selection.',
88+
'heur': _heur_hillclimbing,
89+
'neigh': partial(_neighbours_random, num=100),
90+
'weight': 1
91+
},
92+
{
93+
'name': 'Large Neighbourhood Search (size 2), hillclimbing selection.',
94+
'heur': _heur_hillclimbing,
95+
'neigh': partial(_neighbours_LNS, size=2),
96+
'weight': 1
97+
},
98+
{
99+
'name': 'Large Neighbourhood Search (size 3), hillclimbing selection.',
100+
'heur': _heur_hillclimbing,
101+
'neigh': partial(_neighbours_LNS, size=3),
102+
'weight': 1
103+
},
104+
{
105+
'name': 'Large Neighbourhood Search (size 2), randomly biased selection.',
106+
'heur': _heur_random_hillclimbing,
107+
'neigh': partial(_neighbours_LNS, size=2),
108+
'weight': 1
109+
},
110+
{
111+
'name': 'Large Neighbourhood Search (size 3), randomly biased selection.',
112+
'heur': _heur_random_hillclimbing,
113+
'neigh': partial(_neighbours_LNS, size=3),
114+
'weight': 1
115+
}
83116
]
84117

85118

119+
def _pick_strategy(strategies):
120+
total = sum([strat['weight'] for strat in strategies])
121+
pick = random.uniform(0, total)
122+
count = strategies[0]['weight']
123+
i = 0
124+
while pick > count:
125+
count += strategies[i+1]['weight']
126+
i += 1
127+
return (strategies[i],i)
128+
129+
86130
def parse_problem(filename):
87-
131+
88132
with open(filename, 'r') as f:
89133
problem_line = 'number of jobs, number of machines, initial seed, upper bound and lower bound :'
90134
lines = map(str.strip, f.readlines())
91135
lines = lines[3:lines.index(problem_line, 1)]
92136
data = map(lambda x: map(int, map(str.strip, x.split())), lines)
93-
137+
94138
return zip(*data)
95139

96140

@@ -99,88 +143,111 @@ def makespan(data, perm):
99143

100144

101145
def compile_solution(data, perm):
102-
146+
103147
nmach = len(data[0])
104-
148+
105149
mach_times = [[] for i in range(nmach)]
106-
150+
107151
# Assign the initial job to the machines
108152
mach_times[0].append(0)
109153
for mach in range(1,nmach):
110154
mach_times[mach].append(mach_times[mach-1][0] + data[perm[0]][mach-1])
111-
155+
112156
# Assign the remaining jobs
113157
for i in range(1, len(perm)):
114158
job = perm[i]
115159
mach_times[0].append(mach_times[0][-1] + data[perm[i-1]][0])
116160
for mach in range(1, nmach):
117161
mach_times[mach].append(max(mach_times[mach-1][i] + data[perm[i]][mach-1],
118162
mach_times[mach][i-1] + data[perm[i-1]][mach]))
119-
163+
120164
return mach_times
121165

122166

123167
def solve(data):
124168

125-
context = {'data':data}
169+
global STRATEGIES
126170

127-
#neighbourhood = partial(_neighbours_random, num=50)
128-
neighbourhood = partial(_neighbours_LNS, size=3)
129-
#neighbourhood = _neighbours_swap
130-
131-
#heuristic = _heur_random
132-
heuristic = _heur_hillclimbing
171+
improvements = [0] * len(STRATEGIES)
133172

134173
perm = range(len(data))
135-
174+
136175
best_make = makespan(data, perm)
137176
best_perm = perm
138-
139-
count = 0
177+
res = best_make
178+
179+
iteration = 0
140180
time_limit = time.time() + TIME_LIMIT
181+
time_last_switch = time.time()
182+
141183
while time.time() < time_limit:
142-
143-
count += 1
144184

145-
perm = heuristic(context, neighbourhood(context, perm))
185+
iteration += 1
186+
187+
(s,i) = _pick_strategy(STRATEGIES)
188+
189+
old_val = res
190+
perm = s['heur'](data, s['neigh'](data, perm))
146191
res = makespan(data, perm)
147-
192+
193+
improvements[i] += res - old_val
194+
195+
if time.time() > time_last_switch + TIME_INCREMENT:
196+
results = sorted([(improvements[i], i) for i in range(len(STRATEGIES))])
197+
198+
if DEBUG_SWITCH:
199+
print "\nComputing another switch..."
200+
print "Best performer: %s (%d)" % (STRATEGIES[results[0][1]]['name'], results[0][0])
201+
print "Worst performer: %s (%d)" % (STRATEGIES[results[-1][1]]['name'], results[-1][0])
202+
203+
for i in range(len(STRATEGIES)):
204+
STRATEGIES[results[i][1]]['weight'] += len(STRATEGIES) - i
205+
time_last_switch = time.time()
206+
207+
print results
208+
print sorted([STRATEGIES[i]['weight'] for i in range(len(STRATEGIES))])
209+
210+
improvements = [0] * len(STRATEGIES)
211+
212+
148213
if res < best_make:
149214
best_make = res
150215
best_perm = perm[:]
151216

152-
print "\nWent through %d iterations." % count
217+
218+
219+
print "\nWent through %d iterations." % iteration
153220

154221
return (best_perm, best_make)
155222

156223

157224
def print_solution(data, perm):
158-
225+
159226
sol = compile_solution(data, perm)
160-
227+
161228
print "\nPermutation: %s\n" % str([i+1 for i in perm])
162-
229+
163230
print "Makespan: %d\n" % makespan(data, perm)
164-
231+
165232
row_format ="{:>15}" * 4
166233
print row_format.format('Machine', 'Start Time', 'Finish Time', 'Idle Time')
167234
for mach in range(len(data[0])):
168235
finish_time = sol[mach][-1] + data[perm[-1]][mach]
169236
idle_time = (finish_time - sol[mach][0]) - sum([job[mach] for job in data])
170237
print row_format.format(mach+1, sol[mach][0], finish_time, idle_time)
171-
238+
172239
print "\n"
173240
print row_format.format('Job', 'Start Time', 'Finish Time', 'Idle Time')
174241
results = []
175242
for i in range(len(data)):
176243
finish_time = sol[-1][i] + data[perm[i]][-1]
177244
idle_time = (finish_time - sol[0][i]) - sum([time for time in data[perm[i]]])
178245
results.append((perm[i]+1, sol[0][i], finish_time, idle_time))
179-
246+
180247
for r in sorted(results):
181248
print row_format.format(*r)
182-
183-
249+
250+
184251
print "\n\nNote: Idle time does not include initial or final wait time.\n"
185252

186253

0 commit comments

Comments
 (0)