Hyper-Heuristics, Live

Nine posts in, every search strategy in this series has handed you its dials and waited:

• the ant colony wanted an evaporation rate
• the genetic algorithm and its program-breeding cousin wanted mutation rates and population sizes
• simulated annealing put you in charge of the thermostat
• the swarm asked for inertia, own memory and peer pressure
• variable neighbourhood search needed to know how many neighbourhoods to shake through
• CMA-ES adapted its own step size, but still took a population and a starting sigma from you
• differential evolution asked for F and CR
• tabu search, one post ago, wanted its tenure set

Hyper heuristics are inherently meta. It searches for the right way to search, optimizing by choosing the best optimizer.

It's a heuristic for choosing heuristics, and the field calls it a hyper-heuristic.

The problem this demo is chewing on is exam timetabling, which is very close to what I solved during my studies. My PhD went on rostering BT's engineers, and exam timetabling is the same family of problem with students in place of shifts: easy to state, brutal to solve, and impossible to explain to friends and family what makes it so difficult.

Twenty exams, seven slots, three rooms

Any of us who have been to college / university have likely experienced the hellish end of term exam period. Most students stick to specific degree programs, so if you're a 'generic' student, your exams will likely be spaced fairly evenly. If you, however, are doing a triple major of sports, theoretical physics and nursing, you are the most likely to be screwed over, as screwing up people with that specific triple-threat (just you) is less of a failure than messing up everyone who just took generic psychology classes exams.

The instance below is twenty exams, labelled A to T, to be placed into seven timeslots with three rooms available per slot. A seeded random conflict graph decides which pairs of exams share students. From that, one number to shrink. Two conflicting exams in the same slot is a hard constraint violation and costs '100', because somewhere a student is expected to be in two rooms at once.

Conflicting exams in adjacent slots cost 1 to 3 (scaled by how many students they share), because back-to-back exams are legal, but far from ideal. And a fourth exam squeezed into a three-room slot costs 10 per extra exam. That weighting is the standard trick for mixing hard and soft constraints into one objective.

A timetable is not usable until the hard count reaches zero. Everything after that is how an "acceptable" timetables progresses towards "ok", and hopefully, "good", or even better, "optimal".

The manager and the workers

Four low-level heuristics do the standard heuristic solving business. H1 nudge moves one random exam to a random slot. H2 swap picks two exams and trades their slots. H3 worst-to-best finds the exam contributing the most penalty and moves it to the slot where it does the least damage. H4 ruin kicks three random exams to random slots, a small controlled demolition.

Above them sits the manager - it keeps a score for each worker, rewards a worker whenever its move is accepted and improves the cost, and lets every score decay over time. Even the manager's least favourite heuristic keeps getting the odd chance, because a heuristic useless so far might be useful later down the line when the circumstances change.

Cowling, Kendall and Soubeiga used the same pattern to schedule a sales summit^[2], in the paper that named the modern field.

Intentionally Blind

The manager can't see the timetable. It doesn't know what an exam is. It has no idea students exist. It just has four levers to pull and keeps records of what is working well just now, what isn't, and keeps chugging.

All it ever observes is "I pulled lever three and the cost went down by 40" or "I pulled lever one and the move was rejected". That blindness is called the domain barrier, and it sounds like a handicap but it's necessary.

Because the manager only ever hears cost deltas, you can unplug the four timetabling workers, plug in "move a nurse to another shift" and "swap two delivery routes", and the same manager, unchanged, starts learning which of those levers earns its keep. The domain knowledge lives entirely in the cheap, disposable workers. Burke (who was briefly my supervisor at Stirling) and colleagues' survey^[3] maps how far that one trick works.

Great Deluge: the tide going out

The manager decides which move to try. Something still has to decide which results to keep: Gunter Dueck's Great Deluge, published in 1993^[1] does the trick.

Dueck told it as a story about rain - it rains without end, the water rises, and a hiker who wants to end up on a high peak just has one goal: keep their feet dry!

For minimisation, just turn it upside down: cost is depth, and the search is a fish that must stay submerged. The tide goes out, the pool drains, and the fish is herded into the deepest hollow of the reef it can still reach, or mermaids, or whatever, it's a metaphor you get the idea.

Compare the two acceptance rules. Simulated annealing accepts a worsening move with probability exp(−Δ/T), which means choosing a starting temperature, a cooling schedule, and possibly reheats: a small family of dials, as the demo showed. Great Deluge accepts any move that lands at or below the water level. Uphill, downhill, sideways: if you are under the surface, woohoo.

Watch the manager learn

Watch the probability bars first. That row is the manager's opinion of its workers, updating live. Early on, H3 hoovers up credit, because on a messy random timetable the biggest offender is obvious. Then the easy repairs run out, H3 stalls, decay eats its lead, and you can watch H1 and H4 claw back probability as disruption starts earning acceptances that greedy repair cannot find.

Then watch the flood chart. The shaded water is the accepted region, the line is the cost swimming inside it, and whenever the tide presses down on the line, the level is doing the forcing.

The tide, too fast and too slow

Drain the water too fast, by pushing the drop rate to maximum, and the level crashes below any cost the search can actually reach. From then on nothing passes the test at all: the accepted-moves stat falls to zero while the hard-conflict count sits stranded above it, and after 600 rejections in a row the demo gives up and says so. The search hasn't converged. The tide stranded it partway down the reef, which is the deluge's version of quenching hot metal too quickly.

Drain it too slowly and the level stays miles above the cost, the rule accepts almost everything, and the search wanders: plenty of motion, nothing pushing the cost down. The chart shows a cost line bouncing around far below a distant water surface but going nowhere in particular. All the forcing comes from the tide.

Then turn learning to zero. The manager stops keeping score and picks workers uniformly at random: a committee with no memory. Restart a few runs at learning zero, then a few at full learning, and compare how long the hard-conflict counter takes to hit zero.

The ladder up

There is a tradition in this series of me telling you that some dial matters enormously and then making you tune it by hand: mutation rates, evaporation rates, cooling schedules, F and CR, tabu tenures. CMA-ES staged the first escape from that tradition, adapting its own search distribution as it ran; a hyper-heuristic takes the idea to its limit and moves the whole choice of which heuristic to use inside the run.

It doesn't remove the design decisions: I still chose the workers, the reward, the decay and the floor. Turtles, all the way up.

References

1. Dueck, G. (1993). New Optimization Heuristics: The Great Deluge Algorithm and the Record-to-Record Travel. Journal of Computational Physics, 104(1), 86–92. https://doi.org/10.1006/jcph.1993.1010
2. Cowling, P., Kendall, G., & Soubeiga, E. (2001). A Hyperheuristic Approach to Scheduling a Sales Summit. In Practice and Theory of Automated Timetabling III (PATAT 2000), LNCS 2079, 176–190. https://doi.org/10.1007/3-540-44629-X_11
3. Burke, E. K., Gendreau, M., Hyde, M., Kendall, G., Ochoa, G., Özcan, E., & Qu, R. (2013). Hyper-heuristics: a survey of the state of the art. Journal of the Operational Research Society, 64(12), 1695–1724. https://doi.org/10.1057/jors.2013.71