Media Coverage
March 2011
Dice & Deviations: The Value of Cheating
Here at the office, we deal with optimisation algorithms on a daily basis, some mentioned directly in this column and some through example. However, it is occasionally difficult to provide real-world analogies to algorithms whose effectiveness relies on the computational power available to them.
By handing over responsibility for the grunt work to PCs, we lose visibility into the process. Arthur C. Clarke, renowned science fiction writer widely credited for the idea of using geostationary satellites in telecommunication, stated that, “any sufficiently advanced technology is indistinguishable from magic”.
Algorithms can take on a similar air; subtle tweaks in the rules and parameters applied result in massive deviations where the link is not immediately apparent. Computers have spoiled us; they can crunch through thousands of solutions in seconds, providing algorithms with a feast of data behind the veil of a user interface.
But there is still merit, as our consulting department found, in stepping away from the keyboard and getting your hands dirty. They recently performed a manual exercise with a genetic algorithm – a rule set that allows for evolution of several potential scenarios through multiple iterations and randomised effects to obtain the best-of-breed.
A genetic algorithm requires a genetic representation of the solution – usually shown in a binary or character string format for ease of use – and an essential function that checks the solution’s quality in terms of your objective. The algorithm includes a way of selecting the best proposed solutions from the initial randomly generated population for breeding, and generating a second population from the first.
They decided to solve a scheduling problem involving eight customers (chromosome) and six types of delivery profiles. Six initial specimens (or, in this case, Styrofoam boats) were generated manually with coloured pins, dice and a standard spread-sheet. The aim was to minimise the distance travelled and then, later, weigh the importance of certain delivery profiles over others.
With the Styrofoam boats docked for pin passengers and dice in hand, they proceeded to create generation after generation of solutions. Taking the six solutions, another two boats were created by mutating one of the boats and randomly create an entirely new boat. From that selection of eight, the best two were selected and given random mates, which created two pairs of offspring by crossing over A fixed number of profiles, determined by the roll of an 8-sided die (essentially swapping a portion of the profiles on one boat for the profiles on another).
The best solution was known, but attempting, via this genetic algorithm, to converge on the solution manually provided insight into which of the governing parts of the algorithm aided or hindered the journey. Since they knew the solution, they sometimes cheated to speed up the process by changing the rules of the algorithm on the fly – they could literally see where the blockages were, and remove them.
The value of ‘cheating’ in this context cannot be overestimated.
Have you ever wanted to meet a particular scheduling goal – say, reducing the cost of travel – but have company policies that govern your activities? Company policy may dictate that all drivers need to perform at least one drive a day. By creating a simple scenario and manually playing it out, you’ll quickly realise that forcing a driver to perform a delivery can result in overlapping deliveries to customers close to each other.
‘Cheating’ in this instance – putting multiple deliveries on a vehicle and allowing unused drivers to stay back at the depot – isn’t a flaw in the game (or scheduling program), but in the rules that prohibit such an outcome. The game can’t tell you to cheat, but it can allow it; it’s up to you to take the gap.
This kind of manual simulation, while quite time consuming can give deep insights into algorithms, as in this case, or business processes that need to be optimised.As usual, if you have any comments or questions please contact me at david@opsi.co.za.
