Evolutionary algorithms in open pit scheduling

There are many methods for solving complex problems. A significant number of them rely on “classical” techniques such as dynamic programming, branch & bound and local search, or more sophisticated heuristic techniques including tabu search and simulated annealing.

Classical techniques rely on manipulating a single solution.

To speed up the calculations, instances of the same problem can be resolved using more computers or parallel processing. However, all we get are more solutions of the problem in less time, with no improvement in quality.

This is the beauty of using evolutionary algorithms as we can run with a population of solutions in parallel. Why is this important?

Let’s go back to the word evolutionary. We are simulating the evolutionary process in our space and in real time. That is, each solution is fighting or competing against the other solutions to ensure that it can be used in future generations. The key word is ‘against’, with the implication that each of the competing solutions is aware of the other solutions within the entire population.

A population of 100 solutions is completely different from running a single solution 100 times, due to this information exchange between solutions.

Consider a block model within a pit design which has 1,000 blocks defining the grade and tonnage characteristics of the mining reserve. If we arbitrarily define a sequence through this model that ensures that everything is geometrically correct (i.e. no undercutting), then the result is a sequence which is 1,000 blocks long.

Now, let’s extend this so that there are 99 more sequences making a total population of 100 sequences. These sequences are independent of each other and by implication are also exploring the search space in parallel.

Assuming we want to define our schedule by finding both a mill target and a mining target, we can now convert our sequence into a schedule by ‘cutting up’ the sequence into discrete ‘period’ lengths. A measure of success is how well we fit our objectives (i.e. mill and mining targets) to our sequence. The better the fit, the better the schedule which meets our objectives.

In our population we will have some good quality sequences which fit our objectives well and others which don’t. When these parent schedules ‘mate’ (or exchange information) to produce a new generation of child schedules, some of these child schedules are even better than the parent schedules.

These child schedules will also have to compete with the parent schedules for inclusion into the next generation. In most cases we will see improvements in the fitness function and convergence towards a near optimal solution. This is what is called ‘survival of the fittest’.

We will also see that these sequences are robust in meeting their objectives. In this case robust means that small changes in the initial parameters will result in a small change in the final outcome. We don’t want ‘risky’ schedules, where small changes in the initial parameters lead to significant changes in the final outcomes.

In summary, the concept of being able to meet multiple objectives is easy to model within the evolutionary framework, allowing us to mimic reality as closely as possible without making assumptions or simplifications.