Enhancements to Extremal Optimisation for Generalised Assignment

摘要

Extremal optimisation (EO) is a relatively new meta-heuristic technique that is based on the principles of self organising criticality. It allows for a poorly performing solution component to be removed at each iteration of the algorithm and be replaced by a random one. Over time, improvements emerge and the system is driven towards good quality solutions. There has been very little literature concerning EO and combinatorial optimisation and relatively few computational results have been reported. In this paper, an enhanced model of EO, which allows the traversal feasible and infeasible spaces, is presented. This improved version is able to operate on single solutions as well as populations of solutions. In addition to local search, a simple partial feasibility restoration heuristic is introduced. The computational results for the generalised assignment problem indicate that it provides significantly better quality solutions over a sophisticated ant colony optimisation implementation.