A hybrid extremal optimisation approach for the bin packing problem

Pedro Gómez-Meneses, Marcus Randall

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

Extremal Optimization
Bin Packing Problem
Hybrid Optimization
Bins
Local Search
Feasible region
Assignment

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
Gómez-Meneses, Pedro ; Randall, Marcus. / A hybrid extremal optimisation approach for the bin packing problem. Artificial Life: Borrowing from Biology - 4th Australian Conference, ACAL 2009, Proceedings. Vol. 5865 LNAI 2009. pp. 242-251 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{4e265f15c70d4d4799e4d9417b3a0778,
title = "A hybrid extremal optimisation approach for the bin packing problem",
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.",
author = "Pedro G{\'o}mez-Meneses and Marcus Randall",
year = "2009",
doi = "10.1007/978-3-642-10427-5_24",
language = "English",
isbn = "3642104266",
volume = "5865 LNAI",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "242--251",
booktitle = "Artificial Life: Borrowing from Biology - 4th Australian Conference, ACAL 2009, Proceedings",

}

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, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5865 LNAI, pp. 242-251, 4th Australian Conference on Artificial Life: Borrowing from Biology, ACAL 2009, Melbourne, VIC, Australia, 1/12/09. https://doi.org/10.1007/978-3-642-10427-5_24

A hybrid extremal optimisation approach for the bin packing problem. / Gómez-Meneses, Pedro; Randall, Marcus.

Artificial Life: Borrowing from Biology - 4th Australian Conference, ACAL 2009, Proceedings. Vol. 5865 LNAI 2009. p. 242-251 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5865 LNAI).

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

TY - GEN

T1 - A hybrid extremal optimisation approach for the bin packing problem

AU - Gómez-Meneses, Pedro

AU - Randall, Marcus

PY - 2009

Y1 - 2009

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=78650447532&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-10427-5_24

DO - 10.1007/978-3-642-10427-5_24

M3 - Conference contribution

SN - 3642104266

SN - 9783642104268

VL - 5865 LNAI

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 242

EP - 251

BT - Artificial Life: Borrowing from Biology - 4th Australian Conference, ACAL 2009, Proceedings

ER -

Gómez-Meneses P, Randall M. 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. 2009. p. 242-251. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-642-10427-5_24