Genetic algorithm paper wins award

A paper co-authored by Maptek was recognised at the Genetic and Evolutionary Computation Conference in Denver, Colorado in July.

Breaking the Billion Variable Barrier in Real-World Optimization Using a Customized Evolutionary Algorithm  written by Christie Myburgh and Professor Kalyanmoy Deb of Michigan State University, won best paper in the genetic algorithm category.

Maptek™ Principal Research & Development Engineer Myburgh said that attending the Genetic and Evolutionary Computation Conference (GECCO), and in particular the presentation session, was a great experience.

‘The session was packed and people were standing out in the hallway to listen,’ Myburgh said.

The paper details a solution to a simply stated problem: A metal foundry produces different types of castings; each casting requires different volumes of metal; you have a number of total orders of various castings to fill, by pouring them from sequential heats of a crucible of known volume, typically significantly larger than any one casting. What are the pouring sequences required to (a) fill the orders and (b) minimise the number of heats?

Crucible heats are expensive because of energy costs. Every crucible pour retains material if the remaining liquid metal can only partially fill a mould, so there is either wastage or the need to reheat this residual metal.

The optimal sequence for producing the castings to minimise wastage is not obvious. Try working it out manually with pen and paper for a 10L crucible and n=20 random orders among a set of three 3L, 4L and 5L castings!

A population-based optimisation approach allowed the authors to develop a computationally fast method to arrive at a near-optimal solution.

Two popular softwares (glpk and cplex) are not able to handle around n=300 (10 orders and 30 heats) and n=2000 (10 orders and 200 heats) variables respectively, despite running for hours.

However, Myburgh and Deb’s proposed method is able to find a near-optimal solution in less than a second on the same computer.

The highlight of the study is that the method scales in almost linear computational complexity and so can handle up to n=1,000,000,000 on a laptop PC, memory permitting!

Maptek Product Development Director Simon Ratcliffe said a similar class of optimisation algorithms is critical to the Maptek Evolution mine scheduling software, and the ability to scale up to large datasets is vital.

‘This is the beauty of computer science,’ Ratcliffe said. ‘Examples are not to be taken at face value. Algorithms are abstract and can therefore often provide solutions to a huge variety of seemingly different problems in the real world.’

‘One of the keys of engineering analysis in computing is spotting or knowing when a certain class of algorithm may be applicable in a new domain.’

‘Customising and incorporating domain-specific knowledge in the design of an optimisation algorithm is crucial when it is applied to large scale, complicated and heavily constrained real world problems.’

Christie Myburgh (second left) and Kalyanmoy Deb (third left) with students from the Computational Optimization and Innovation Lab who attended GECCO 2016

Forge Home