Watchmaker for bin packing problems

17 views
Skip to first unread message

Elliott Wolin

unread,
Nov 2, 2016, 5:00:59 PM11/2/16
to Watchmaker Framework for Evolutionary Computation
I am new to GAs and have a bin packing problem.  I read a paper by Falkenauer arguing that standard GAs are not efficient for bin packing for a number of reasons.  Most important is that the solution space is multi-valued, i.e. many different computer solutions map to the same actual solution since order doesn't matter in bin packing.  Also crossover can do unexpected things, and a few other problems.  He advocates using a Hybrid Grouping Genetic Algorithms.  I may not be stating his concerns correctly, best to check out one of his papers (I have "A Hybrid Grouping Genetic Algorithm for Bin Packing", 1996).

The article is somewhat old.  Is this still a concern?  Does Watchmaker address this somehow?  Are there better choices for bin packing problems?

Sincerely,

Elliott Wolin

Klaas Hölscher

unread,
Nov 11, 2016, 9:40:25 AM11/11/16
to watch...@googlegroups.com
Hello Elliot,

thank you for providing food for thought. Since watchmaker is a framework, you may implement the described hybrid grouping genetic algorithm inside the framework.
The concerns stated in the paper are valid, a GA with naive encoding seems not really that good. 
I guess since 1996 more people have come up with solvers for different bin packing problem complexity classes - a GA is never that efficient. You could look for greedy solvers or
an exact solver if the parameters are simple enough

regards,
Klaas

--
You received this message because you are subscribed to the Google Groups "Watchmaker Framework for Evolutionary Computation" group.
To unsubscribe from this group and stop receiving emails from it, send an email to watchmaker+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Reply all
Reply to author
Forward
0 new messages