Expecting a homepage? No such luck. Here's an old project of mine from when I was studying in University of Helsinki to pass a second of your time. There's also Mystery Tauren Theater 2000: WotLK Intro available.

Bin packing with generic algorithms: GABinPacker

GABinPacker 1.02, Copyright 2003,2008 Ilkka Forsblom. GABinPacker comes with ABSOLUTELY NO WARRANTY. This is free software, and you are welcome to redistribute it under certain conditions. See the end of this page for details.

Your browser is completely ignoring the <APPLET> tag! You're missing out on all the fun!

What it does

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.

From the paper

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.

Implementation specific

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.

Get the source

For the daring, there is the source.

Copyright 2003,2008 Ilkka Forsblom. GABinPacker is available under the terms of the GNU General Public License.