Filling a rectangle with unequal sized circles with genetic algorithm

Question

Yesterday I came up with a question that I have no answer for it.

We have a random sized rectangle and we also have some circles with different radius, which we got limited amount of each of those circles. Each circle has a specified cost. We wanted to completely fill our rectangle with those circles, approaching the smallest cost.

Now I wanted to solve this problem with genetic algorithm, but I won't found any article in the web, which is somehow the same with my problem.

Does anyone has any idea?

Answer 1

Your problem is related to the Knapsack problem: Out of a set of N items with weights W and values V you want to select that group of items that have maximal value, but the sum of their weights remains lower than some bound.

Your problem however is more complex, since the evaluation of the weight-constraint is not a simple addition, but depends on the arrangement of the circles. I think that this constitutes another NP-hard problem to solve. You will have to find some quick approximation on that constraint that tell you if it's possible (and which sometimes may tell you it's not possible, even though it would be).

The arrangement of objects inside a container can be described as a packing problem. You may want to look at circle packing and related literature. A simple relaxation could also be based on rectangles. There are quick methods for rectangle packing which you can use if you treat your circles as rectangles. If your circles are of highly different size, however this may be a bad relaxation.