2D Strip Packing Problem Solution using Genetic Algorithm
This online calculator tries to find optimal 2D strip packing solution using genetic algorithm
Here we deal with the strip packing problem  2dimensional geometric minimization problem. Here is the problem definition from wikipedia: given a set of axisaligned rectangles and a strip of bounded width and infinite height, determine an overlappingfree packing of the rectangles into the strip minimizing its height. This problem is a cutting and packing problem and is classified as an Open Dimension Problem according to Wäscher et al.^{1}.
In order to use the calculator you should input the strip width, then the rectangles you are going to pack. For simplicity, assuming there are number of rectangles with the same dimensions, you enter them one type per line, using width x height x quantity notation. After that you can play with genetic algorithm parameters (if you want to)  tweak the population size, the number of generations and the chance of random mutation. You can read about the genetic algorithm below the calculator.
Genetic Algorithm
Although there are exist polynomial time approximation algorithms with proven approximation guarantee (refer to the Wikipedia article mentioned above), I decided to use genetic or evolutionary algorithm. It does not guarantee an optimal solution, or even an upperbounded solution ("upperbounded" is then you have guarantee that the found solution will be not worse than 2 optimal heights, for example), but it is usually able to find a solution, good enough for any practical purposes. Besides, generally speaking, it is very easy to implement, compared to other algorithms.
The basic idea of genetic algorithm is very simple: you generate the set of random solution, then you calculate the fitness score for each solution, using a fitness function. Then you use the survival of the fittest principle: only the fittest solutions (f.e. top 50%) produce the new generation, when the algorithm produces children by combining the 'genes' of their parents. Also, to prevent the algorithm from being stuck in an suboptimal solution, some randomness is introduced in the form of the gene's mutation, which gives the algorithm the chance to escape the local maximum. That's it. Simple as that. As with other heuristic algorithms, there is no guarantee that is will be able to reach the good solution, you just run it and cross your fingers. If the end result looks like it is not good enough for you, you run the algorithm again and again, may be tweaking the number of generations or the population size until you are satisfied with the result. You can even just try several times without tweaking anything, because each time the algorithm starts from the set of random solutions, and you probably will get the different result anyway.

Wäscher, Gerhard; Haußner, Heike; Schumann, Holger (16 December 2007). "An improved typology of cutting and packing problems". European Journal of Operational Research. ↩
Kommentare