圆片下料并行遗传算法的设计与实现

针对制造行业中的圆片下料问题，为了在合理的计算时间内使材料的利用率尽可能高，提出并行遗传下料算法（PGBA），以下料方案的材料利用率作为优化目标函数，将下料方案作为个体，采用多线程的方式对多个子种群并行进行遗传操作。首先，在并行遗传算法的基础上设计特定的个体编码方式，采用启发式方法生成种群的个体，以提高算法的搜索能力和效率，避免早熟现象的发生；然后，采用性能较好的遗传算子进行自适应的遗传操作，搜索出一种近似最优的下料方案；最后，通过多种实验验证算法的有效性。结果表明，与启发式算法相比，PGBA的计算时间有所增加，但材料利用率得到了较大的提高，能有效提高企业的经济效益。

Design and implementation of parallel genetic algorithm for cutting stock of circular parts

For the cutting stock problem of circular parts which is widely existed in many manufacturing industries， a new parallel genetic algorithm for cutting stock was proposed to maximize the material utilization within a reasonable computing time， namely Parallel Genetic Blanking Algorithm （PGBA）. In PGBA， the material utilization rate of cutting plan was used as the optimization objective function， and the multithread was used to perform the genetic manipulation on multiple subpopulations in parallel. Firstly， a specific individual coding method was designed based on the parallel genetic algorithm， and a heuristic method was used to generate the individuals of population to improve the search ability and efficiency of the algorithm and avoid the premature phenomena. Then， an approximate optimal cutting plan was searched out by adaptive genetic operations with better performance. Finally， the effectiveness of the algorithm was verified by various experiments. The results show that compared with the heuristic algorithm proposed in literature， PGBA takes longer computing time， but has the material utilization rate greatly improved， which can effectively improve the economic benefits of enterprises.