Packing equal disks in a unit square: an immunological optimization approach
- 1 July 2015
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1-5
Abstract
Packing equal disks in a unit square is a classical geometrical problem which arises in many industrial and scientific fields. Finding optimal solutions has been proved to be NP-hard, therefore, only local optimal solutions can be identified. We tackle this problem by means of the optimization Immune Algorithm (optIA), which has been proved to be among the best derivative-free optimization algorithms. In particular, OPTIA is used to pack up to 150 disks in a unit square. Experimental results show that the immune algorithm is able to locate the putative global optimum for all the instances. Moreover, a comparison with the Covariance Matrix Adaptation Evolution Strategy (CMA-ES) shows that OPTIA is more robust.Keywords
This publication has 16 references indexed in Scilit:
- Clonal selection: an immunological algorithm for global optimization over continuous spacesJournal of Global Optimization, 2011
- Greedy vacancy search algorithm for packing equal circles in a squareOperations Research Letters, 2010
- A Literature Review on Circle and Sphere Packing Problems: Models and MethodologiesAdvances in Operations Research, 2009
- Solving circle packing problems by global optimization: Numerical results and industrial applicationsEuropean Journal of Operational Research, 2008
- A New Verified Optimization Technique for the "Packing Circles in a Unit Square" ProblemsSIAM Journal on Optimization, 2005
- Exploring the Capability of Immune Algorithms: A Characterization of Hypermutation Operators2004
- More Optimal Packings of Equal Circles in a SquareDiscrete & Computational Geometry, 1999
- Packing circles in a square: A review and new results1992
- The Densest Packing of 9 Circles in a SquareCanadian Mathematical Bulletin, 1965
- On a Geometric Extremum ProblemCanadian Mathematical Bulletin, 1965