Solving two-dimensional packing problem using particle swarm optimization
Abstract
Particle swarm optimization is one of the evolutionary computations which is inspired by social behavior of bird flocking or fish schooling. This research focuses on the application of the particle swarm optimization to two-dimensional packing problem. Packing problem is a class of optimization problems which involve attempting to pack the items together inside a container, as densely as possible. In this study, when the arbitrary polygon-shaped packing region is given, the total number of items in the region is maximized. The optimization problem is defined not as the discrete-value optimization problem but as the continuous- value optimization problem. The problem is solved by two algorithms, original and improved PSOs. In the original PSO, the particle position vector is updated by the best particle position in all particles (global best particle position) and the best position in previous positions of each particle (personal best position). The improved PSO utilizes, in addition to them, the second best particle position in all particles (global second best particle position) in the stochastic way. In the numerical example, the algorithms are applied to three problems. The results show that the improved PSO can pack more items than the original PSO and therefore, number of the successful simulations is also improved.
Keywords
packing problem, particle swarm optimization, global best position, global second best position, personal best position,References
[1] J.H. Holland. Adaptation in Natural and Artificial Systems. University of Michigan Press, 1st. edition, 1975.[2] S. Kirkpatrick, C.D. Gelatt Jr., M.P. Vecchi. Optimization by simulated annealing. Science, 220(4598): 671–680, 1983.
[3] J. Kennedy, R.C. Eberhart. Particle swarm optimization. In Proceedings of IEEE the International Conference on Neural Networks, volume 6, pages 1942–1948, 1995.
[4] Hallard T. Croft, Falconer Kenneth J., Guy Richard K. Unsolved Problems in Geometry. Springer-Verlag, 1991.
[5] J. Melissen. Packing 16, 17 or 18 circles in an equilateral triangle. Discrete Mathematics, 145: 333–342, 1995.
[6] Erich Friedman. Packing unit squares in squares: a survey and new results. The Electronic Journal of Combinatorics, DS7, 2005.
[7] D.S. Liu, K.C. Tan, S.Y. Huang, C.K. Goh, W.K. Ho. On solving multiobjective bin packing problems using evolutionary particle swarm optimization. European Journal of Operational Research, 190(2): 357–382, 2008.
[8] Chen Zhao, Liu Lin, Cheng Hao, Liu Xinbao. Solving the rectangular packing problem of the discrete particle swarm algorithm. In Business and Information Management, 2008. ISBIM ’08. International Seminar on, volume 2, pages 26–29, 2008.
[9] Chuan He, Yuan-Biao Zhang, Jian-Wen Wu, Cheng Chang. Research of three-dimensional container-packing problems based on discrete particle swarm optimization algorithm. In Test and Measurement, 2009. ICTM ’09. International Conference on, volume 2, pages 425–428, dec. 2009.
[10] P. Thapatsuwan, J. Sepsirisuk,W. Chainate, P. Pongcharoen. Modifying particle swarm optimisation and genetic algorithm for solving multiple container packing problems. In Computer and Automation Engineering, 2009. ICCAE ’09. International Conference on, pages 137 –141, march 2009.
[11] Ryan Forbes, Mohammad Nayeem Teli. Particle swarm optimization on multi-funnel functions. http://www.cs.colostate.edu/nayeem/papers/pso−paper.pdf.
[12] M. Clerc. The swarm and the queen: towards a deterministic and adaptive particle swarm optimization. In Proceedings of 1999 Congress on Evolutionary Computation, volume 3, pages 1951–1957, 1999.
