Genetic Algorithm With Random Crossover and Dynamic Mutation on Bin Packing Problem

Hairil Fiqri Sulaiman, Bruri Trya Sartana, Utomo Budiyanto

Abstract


Bin Packing Problem (BPP) is a problem that aims to minimize the number of container usage by maximizing its contents. BPP can be applied to a case, such as maximizing the printing of a number of stickers on a sheet of paper of a certain size. Genetic Algorithm is one way to overcome BPP problems. Examples of the use of a combination of BPP and Genetic Algorithms are applied to printed paper in Digital Printing companies. Genetic Algorithms adopt evolutionary characteristics, such as selection, crossover and mutation. Repeatedly, Genetic Algorithms produce individuals who represent solutions. However, this algorithm often does not achieve maximum results because it is trapped in a local search and a case of premature convergence. The best results obtained are not comprehensive, so it is necessary to modify the parameters to improve this condition. Random Crossover and Dynamic Mutation were chosen to improve the performance of Genetic Algorithms. With this application, the performance of the Genetic Algorithm in the case of BPP can overcome premature convergence and maximize the allocation of printing and the use of paper. The test results show that an average of 99 stickers can be loaded on A3 + size paper and the best generation is obtained on average in the 21st generation and the remaining space is 3,500mm2.

Keywords


Bin Packing Problem; Genetic Algorithms; Dynamic Mutation; Random Crossover; Premature Convergence

Full Text: PDF

Refbacks

  • There are currently no refbacks.