This implementation of GA bin packing is based on the paper: Falkenauer, E., Delchambre, A., A genetic algorithm for bin packing and line balancing. In Proceedings of the IEEE 1992 International Conference on Robotics and Automation, Nice, France, 1992, 1186–1192.
The chromosome is variable length, and basically the length of the chromosome equals the number of bins used in current packing. The genetic operators work by removing bins and repacking their content, reordering the bins, and by inserting bins from other solutions (leading to the removal and repacking of bins). (Naturally you also need to code which box goes to which bin, but the genetic operators don't touch that part directly, so don't worry about that.)
Fitness function is (Σi=1..N(filli/C)k)/N, where N is the number of bins, filli is the sum of the sizes of objects in bin i, C is bin capacity and k is constant, it is recommended that k equals 2.
The members of the first population are created by packing the boxes in random order into bins using the First Fit heuristic.
Mutation is done by selecting the most empty bin and a few (at least two) bins at random, removing them from the solution, and repacking the now unpacked boxes in random order with FF heuristic. My algorithm always selects just three bins in total (more could be better, I suppose).
Crossover works as follows (working with copies of the parents so as not to modify them). Two crossing sites are chosen from both parents. The bins between the crossing sites in the first parent are copied to the location to the second parent at the location of the first crossing site in it. Any bins originally in the second parent containing boxes also packed in the inserted bins are removed, and the boxes now left unpacked are repacked with First Fit Descending heuristics (my algorithm only does FF, not FFD).
Also mentioned in the paper is inversion, but I didn't bother doing that (last minute lazyness). It could improve the results.
Population is updated incrementally (not en bloc). Parents produce only one child. Duplicate chromosomes aren't allowed (this isn't working perfectly at the moment). Best chromosome (according to its fitness function) is preserved (élitist model). For crossover one of the parents is chosen randomly with the probability of choosing a chromosome increasing with its fitness. The other parent is chosen with uniform probability.
Execution will terminate on its own when a solution is achieved that is of equal quality of the best known solution. There are no other termination conditions (use the Stop-button to stop, Halt for temporary pause). The best solution is displayed when execution ends. Halting temporarily also displays best solution so far.
Copyright 2003,2008 Ilkka Forsblom. GABinPacker is available under the terms of the GNU General Public License.