A Genetic Algorithm with Weight-Based Encoding for One-Dimensional Bin Packing Problem

Abstract:

This paper proposes a specialized genetic algorithm (GA) based on an expended relational representation named weight-based encoding for solving one-dimensional bin packing problem (BPP-1). The encoding provides a totally constraint-handling scheme to address general and specific constraints, while naturally eliminates redundancy and infeasibility of previous representations for BPP-1. The current study performs experiments for solving some problem instances from a benchmark data set by our specific coded genetic algorithm with one-point, two-point and grouping crossovers. Experimental results show that the proposed methodology works well for solving BPP-1 and performs well on experimented benchmark instances. In addition, the results also show that two-point and grouping crossovers work better than one-point crossover in our experiments.

• Periodical: Applied Mechanics and Materials (Volumes 182-183)
• Pages: 2100-2104
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.182-183.2100
• Online since: June 2012
• Authors: Yao Tang Lin, Jia Li Hou
• Keywords: Constraint Handling, Genetic Algorithm (GA), One-Dimensional Bin Packing Problem (BPP-1), Weight-Based Encoding

References

[1] S. Martello and P. Toth, Knapsack problems : Algorithms and Computer Implementation, John Wiley and Sons, (1990).

[2] D. Smith, Bin Packing with Adaptive Search, Proceeding of an International Conference on Genetic Algorithms and Their Application, pp.202-206, (1985).

[3] C. Reeves, Hybrid genetic algorithms for bin-packing and related problems, Annals of Operations Research, Vol. 63, pp.371-396, (1996).

DOI: 10.1007/bf02125404

[4] A. Stawowy, Evolutionary based heuristic for bin packing problem, Computers & Industrial Engineering, Volume 55, Issue 2, pp.465-474, September (2008).

DOI: 10.1016/j.cie.2008.01.007

[5] E. Falkenauer, The Grouping Genetic Algorithms-Widening The Scope of The GAs, JORBEL-Belgian Journal of Operations Research, Statistics and Computer Science, 33(1, 2), pp.79-102, (1992).

[6] E. Falkenauer, A hybrid grouping genetic algorithm for bin packing, Journal of Heuristics, Vol. 2, Issue 1, pp.5-30, (1996).

DOI: 10.1007/bf00226291

[7] Benchmark data sets on http: /www. wiwi. uni-jena. de/Entscheidung/binpp.

[8] J. S. Chen and Y. T. Lin, A Partitioned Portfolio Insurance Strategy by Relational Genetic Algorithm, Expert Systems with Applications, Volume 36(2), part 2, pp.2727-2734, (2009).

DOI: 10.1016/j.eswa.2008.01.081

[9] S. Martello,D. Pisinger, P. Toth, Dynamic programming and strong bounds for the 0-1 knapsack problem, Management Science, Volume 45, p.414–424, (1999).

DOI: 10.1287/mnsc.45.3.414