A hybrid extremal optimisation approach for the bin packing problem

Extremal optimisation (EO) is a simple and effective technique that is influenced by nature and which is especially suitable to solve assignment type problems. EO uses the principle of eliminating the weakest or the least adapted component and replacing it by a random one. This paper presents a new hybrid EO approach that consists of an EO framework with an improved local search for the bin packing problem (BPP). The stochastic nature of the EO framework allows the solution to move between feasible and infeasible spaces. Hence the solution has the possibility of escaping from a stagnant position to explore new feasible regions. The exploration of a feasible space is complemented with an improved local search mechanism developed on the basis of the proposed Falkenauer's technique. The new local search procedure increases the probability of finding better solutions. The results show that the new algorithm is able to obtain optimal and efficient results for large problems when the approach is compared with the best known methods.