Remember Me
Or use your Academic/Social account:


Or use your Academic/Social account:


You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.


Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message


Verify Password:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Asta, Shahriar; Özcan, Ender; Parkes, Andrew J. (2016)
Publisher: Elsevier
Languages: English
Types: Article
The online bin packing problem is a well-known bin packing variant which requires immediate decisions to be made for the placement of a lengthy sequence of arriving items of various sizes one at a time into fixed capacity bins without any overflow. The overall goal is maximising the average bin fullness. We investigate a ‘policy matrix’ representation which assigns a score for each decision option independently and the option with the highest value is chosen for one dimensional online bin packing. A policy matrix might also be considered as a heuristic with many parameters, where each parameter value is a score. We hence investigate a framework which can be used for creating heuristics via many parameters. The proposed framework combines a Genetic Algorithm optimiser, which searches the space of heuristics in policy matrix form, and an online bin packing simulator, which acts as the evaluation function. The empirical results indicate the success of the proposed approach, providing the best solutions for almost all item sequence generators used during the experiments. We also present a novel fitness landscape analysis on the search space of policies. This study hence gives evidence of the potential for automated discovery by intelligent systems of powerful heuristics for online problems; reducing the need for expensive use of human expertise.
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • Burke, E.K., Hyde, M., Kendall, G., Ochoa, G., O¨ zcan, E., Woodward, J.R., 2010. A classification of hyper-heuristic approaches, in: Gendreau, M., Potvin, J.Y. (Eds.), Handbook of Metaheuristics. Springer US. volume 146 of International Series in Operations Research and Management Science, pp. 449-468.
    • Burke, E.K., Hyde, M.R., Kendall, G., 2006. Evolving bin packing heuristics with genetic programming, in: Proceedings of the 9th International Conference on Parallel Problem Solving from Nature (PPSN 2006), Reykjavik, Iceland. pp. 860-869.
    • Burke, E.K., Hyde, M.R., Kendall, G., Ochoa, G., O¨ zcan, E., Woodward, J.R., 2009. Exploring hyper-heuristic methodologies with genetic programming, in: Kacprzyk, J., Jain, L.C., Mumford, C.L., Jain, L.C. (Eds.), Computational Intelligence. Springer Berlin Heidelberg. volume 1 of Intelligent Systems Reference Library, pp. 177-201.
    • Burke, E.K., Hyde, M.R., Kendall, G., Woodward, J., 2007a. Automatic heuristic generation with genetic programming: evolving a jack-of-all-trades or a master of one, in: Proceedings of the 9th annual conference on Genetic and evolutionary computation, ACM, New York, NY, USA. pp. 1559-1565.
    • Burke, E.K., Hyde, M.R., Kendall, G., Woodward, J.R., 2007b. The scalability of evolved on line bin packing heuristics, in: Srinivasan, D., Wang, L. (Eds.), 2007 IEEE Congress on Evolutionary Computation, IEEE Computational Intelligence Society. IEEE Press, Singapore. pp. 2530-2537.
    • Chakhlevitch, K., Cowling, P., 2008. Hyperheuristics: Recent developments, in: Cotta, C., Sevaux, M., So¨rensen, K. (Eds.), Adaptive and Multilevel Metaheuristics. Springer Berlin / Heidelberg. volume 136 of Studies in Computational Intelligence, pp. 3-29.
    • Coffman, Jr., E.G., Garey, M.R., Johnson, D.S., 1997. Approximation algorithms for bin packing: a survey. PWS Publishing Co., Boston, MA, USA. pp. 46-93.
    • Coffman Jr., E.G., Csirik, J., Galambos, G., Martello, S., Vigo, D., 2013. Bin packing approximation algorithms: Survey and classification, in: Pardalos, P.M., Du, D.Z., Graham, R.L. (Eds.), Handbook of Combinatorial Optimization. Springer New York, pp. 455-531.
    • Coffman Jr, E.G., Galambos, G., Martello, S., Vigo, D., 1999. Bin packing approximation algorithms: Combinatorial analysis, in: Du, D.Z., Pardalos, P. (Eds.), Handbook of Combinatorial Optimization. Kluwer Academic Publishers. volume 1 of Intelligent Systems Reference Library, pp. 151-207.
    • Csirik, J., Woeginger, G., 1998. On-line packing and covering problems, in: Fiat, A., Woeginger, G. (Eds.), Online Algorithms. Springer Berlin / Heidelberg. volume 1442 of Lecture Notes in Computer Science, pp. 147-177.
    • Poloni, C., Beume, N. (Eds.), Parallel Problem Solving from Nature - PPSN X. Springer Berlin / Heidelberg. volume 5199 of Lecture Notes in Computer Science, pp. 1140-1149.
    • Wright, S., 1932. The roles of mutation, inbreeding, crossbreeding and selection in evolution. Proc.Int.Cong.Gen. 1, 356-366.
  • No related research data.
  • No similar publications.

Share - Bookmark

Cite this article