|
Consider the following problem. Give the unit square and a specified number of circles (constrained to have equal radii), find the best possible packing; i.e. position the circles in the square to maximize
the ratio between the area contained within the circles and the area of the square, enforcing the constraint that all circles must be
fully contained within the square. This problem is a simplified but similar problem to many real-world problems in logistics, network planning, etc.
For the purposes of evaluating optimization algorithms, Circles in a Square packing is a source of benchmark problems with several attractive features.
Here you can download (free for research/non-commercial use) a Matlab implementation of this problem set suitable for use in evaluating optimization algorithms.
Problem Formulation
The Circles in a Square packing problem involves finding the arrangement of n circles in a unit square such that the radius of the circles, r, is maximised, where no two circles overlap and no part of a circle leaves the square. This is equivalent to the problem of placing n points in a square such that the minimum distance, m between any two points is maximised. The relationship between the radius, r, and the distance m is as follows:
m = 2r/(1-2r)
r = m/(2+2m)
The solution is a value of the radius (or distance) and the set of co-ordinates of the circle-centres (or points) that gives that value. The relationship between the co-ordinates of the circle centres, c, and the point co-ordinates, p is as follows:
c = (m/2 + p)/(1 + m)
p = (c - r)/(1 - 2r)
Values of c are constrained to the range [r, 1-r]. Values of p are constrained to the range [0, 1].
When n > 2, this is a hard optimisation problem with multiple local optima. For certain values of n there are several, distinct, globally optimal solutions.
This problem can be generalised by working in a higher-dimensional space (d-spheres in a d-cube), or by using different shapes for packing (circles in a circle, cylinders in a tetrahedron, etc.).
The circ_in_square MATLAB function
The Matlab file circ_in_square.m provides and objective function for the Circles in a Square problem. This function uses the "distance between points" form of the problem, with co-ordinates in the range [0, 1]. This function also generalises to the d-spheres in a d-cube for n d-circles, where d >= 1 and n >= 2.
The function has the following form, where all parameters are required:
score = circ_in_square(num, dim, flags, inputs)
Parameters:
- num - the number of circles or d-spheres in the problem, n
- dim - the dimensionality of the d spheres and d-cube
- flags - 2 x 1 vector of flag variables to set options for the function
- flags(1) - Minimisation or maximisation
- 0 - minimisation problem
- 1 - maximisation problem
- flags(2) - Constraint handling
- 0 - Handle constraint violations by repairing the input values that violate the constraints of the problem.
- 1 - Handle constraint violations by returning a single, poor value if there is any violation.
- 2 - Repair any violations, then add a penalty that is proportional to the magnitude of the violations.
- inputs - the set of co-ordinates of the points, unrolled into a vector of length n * d. The first n values are the co-ordinates of the first dimension, the next n values are the co-ordinates of the second dimension, and so on up to the dth dimension.
Return Value:
- score - for a solution that doesn't violate any constraints, the score is the minimum distance between any two points. For a minimisation problem, the distance is multiplied by -1.
Code
- circ_in_square.m - Objective function for the circles in a square problem
- plot_circ_in_square.m - function to plot a solution using coordinates entered into circ_in_square
- solutions1-200.mat - Matlab structure containing coordinates and values from packomania.com (1-200 circles). Note that these were correct to 12 decimal places of accuracy at the time the file was created.
Example usage
- To evaluate a random solution to the 5-circle problem, with a 2D packing problem (i.e. 2D circles in a 2D square), treating the problem as a minimization problem and repairing constraint violations:
>> soln = rand(1,10);
>> circ_in_square(5,2,[0;0],soln)
>> plot_circ_in_square(soln)
Acknowledgement
This software was originally implemented by Lachlan Dufton.
More Information
The site Packomania keeps information and diagrams for the best known solutions of the Circles in a Square problem. This includes circle radius, point distance and co-ordinates for all solutions where 1<=n<=300, and select solutions where 300<n<1000.
References
|
