A hybrid extremal optimisation approach for the bin packing problem

Pedro Gómez-Meneses*, Marcus Randall

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

6 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationArtificial Life: Borrowing from Biology - 4th Australian Conference, ACAL 2009, Proceedings
Pages242-251
Number of pages10
Volume5865 LNAI
DOIs
Publication statusPublished - 2009
Event4th Australian Conference on Artificial Life: Borrowing from Biology, ACAL 2009 - Melbourne, VIC, Australia
Duration: 1 Dec 20094 Dec 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5865 LNAI
ISSN (Print)03029743
ISSN (Electronic)16113349

Conference

Conference4th Australian Conference on Artificial Life: Borrowing from Biology, ACAL 2009
CountryAustralia
CityMelbourne, VIC
Period1/12/094/12/09

    Fingerprint

Cite this

Gómez-Meneses, P., & Randall, M. (2009). A hybrid extremal optimisation approach for the bin packing problem. In Artificial Life: Borrowing from Biology - 4th Australian Conference, ACAL 2009, Proceedings (Vol. 5865 LNAI, pp. 242-251). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5865 LNAI). https://doi.org/10.1007/978-3-642-10427-5_24