Constrained circles packing test problems: all the optimal solutions known

Abstract

Taking a satellite module layout design as engineering background, this paper gives constrained test problems for an unequal circle packing whose optimal solutions are all given. Given a circular container D with radius R, the test problem can be constructed in the following steps. First, M=217 circles are packed into D without overlaps by ‘packing with a tangent circle’ to get the values of radii and centroid coordinates of the circles, which are expressed by R. Then the 217 circles are arranged in descending sequence of radius and are divided into 23 groups according to the radius. Finally, seven test problems are constructed according to the circles of q=1, 2, …, 7 groups. The optimal solution to the test problems as well as its optimality and uniqueness proof are also presented. The experimental results show that the test problems can effectively evaluate performances of different evolutionary algorithms.

Keywords:

• test problem
• circle packing
• performance constraint
• evolutionary algorithms
• satellite module layout

2000 AMS Subject Classification:

• 52C26

C.R. Categories:

• I.2.8

Acknowledgements

We would like to acknowledge the National Natural Science Foundation of the People's Republic of China for the sponsorship (Grants No. 50275019, 50335040, 50575031).