The Application Research Of Parallel Genetic Algorithm In Bin Packing Problem

Bin Packing problem(BPP) is one of the most famous combinatorial optimization problem. And it is the emphasis of the analysis of approximation algorithms. As one of the earliest studied NP-hard problem, it works as a research platform for the complexity theory and gives directors to other NP-Hard problems. Bin packing comes from our lives and has many important applications such as multiprocessor scheduling, resource allocation, and real-world planning, packing and scheduling optimization problems. the problems has been studied more than forty years, many famous combinatorial optimization researchers have built up integrate theories and explored many algorithms for the problem, but the topics are far from ending.By using the parallel genetic algorithm to solve the one-dimensional bin packing problem, for the one-dimensional packing problem, centering on how to improve the efficiency of the parallel algorithms and the data computing precision, the paper puts forword a number of key technologies. The following key elements:1 .By comparing with the grouping genetic algorithm achieving better result in the one-dimensional bin packing problem , for the lack of crossover operator of the grouping genetic algorithm, the paper put forward an improved crossover operator,adding a "replacement" mechanism in the crossover process.The crossover operator ensure reduceing the number of bins to the extent possible and making every bin filled with items as much as possible in the crossover process.2.In order to increase the diversity of species in the evolutionary process, jumping out of the local optimal solution, we design a new mutation operator. the main operators is adding a bin,deleting a bin,or the same number of bins but the items in bins is combined appropriately.3.Starting with the "coarse-grained and more groups" genetic algorithm model, enlightened by the "pyramid" model , the paper proposed a "pyramid hierarchical model" of parallel genetic algorithm.according to the average fitness ,the population will be divided into different levels, the different levels populations have different probability of crossover and mutation. The higher level populations have the low probability of crossover and mutation, the migration only happen from the lower level population to the higher level population. 4.For the migration strategy, in order to minimize communication costs, the paper proposed a "dual-threshold migration strategy". Seting up the dual-threshold according to the population fitness variance, the migration will be relocated into three situations: less than the minimum threshold, migration doesn't happen; between the dual-threshold, replacing the poor individual of the higher level population with the outstanding individuals of the lower level population; larger than the largest threshold, adjusting the levels the populations.5.In the migration cycle, the paper use the not fixed interval migration cycle, a migration applications happens only when the evolution is very slow.Based on the above study, this paper gives the pseudo-code realization of the parallel genetic algorithm for one-dimensional bin packing problem. And in practice using pseudo-parallel genetic algorithm to simulate parallel genetic algorithm to solve the one-dimensional bin packing problem , through actual data computing precision and efficiency ,this algorithm shows its advantages.