Evolutionary Heuristics for the Bin Pack

In this paper we investigate the use of two evolutionary based heuristics for the bin packing problem (BPP). The intractability of this problem serves as a motivation for developing heuristics that yield approximate solutions. Unlike other evolutionary heuristics employed in optimization problems, our approach does not utilize domain-specific knowledge and lacks specialized genetic operators. Instead, it makes use of a straightforward fitness function enhanced by a graded penalty term to penalize infeasible solutions. The encoding in our method involves strings of integer values, as opposed to the permutation representations used in most existing approaches. We apply a different representation and provide justifications for this choice. Several problem instances are tested using both a greedy heuristic and the proposed evolutionary algorithms, and we perform a comparative analysis of the results. The findings lead us to several observations and suggestions on the effective application of evolutionary heuristics for combinatorial optimization problems.