基于扩张-收缩机制的遗传算法求解一维下料问题

Solving One-dimensional Cutting Stock Problem with Genetic Algorithm Based on Expansion-Contraction Mechanism

针对一维下料问题,基于原材料序列和零件序列计算原材料的利用率,建立了以利用率最大为目标的0-1规划模型,选取通用性高、并行性好的遗传算法求解.算法设计上,首先采用双种群编码对应于原材料序列和零件序列,可以有效避免不可行解的产生;其次构造了遗传算法的扩张-收缩机制,分别基于轮盘赌策略和锦标赛策略以及复合变异操作使当前种群迅速扩张为两倍规模;然后定义了综合考虑基因差异性和适应度差异性的个体相似度,据此进行种群收缩,使扩张种群收缩到原种群规模.最后,选取已有文献中四个代表性算例进行仿真实验,求解结果均优于原文献结果,表明所设计算法在求解精度和收敛速度上均有更好的性能体现,验证了其可行性和有效性.

For one-dimensional cutting stock problem,the utilization rate of raw materials is calculated based on the sequence of raw materials and parts,and a 0-1 programming model is established to maximize the utilization rate.The genetic algorithm with high generality and good parallelism is used to solve the problem.In the algorithm design,firstly,the double population coding is used to correspond to the raw material sequence and the part sequence,which can effectively avoid the generation of infeasible solutions;secondly,the expansion contraction mechanism of genetic algorithm is constructed,which makes the current population rapidly expand to twice the size based on roulette strategy,tournament strategy and compound mutation operation respectively;secondly,it defines the comprehensive consideration of gene diversity and fitness Based on the difference of individual similarity,the population shrinkage is carried out,and the expanded population is contracted to the original population size.Finally,four representative examples in the literature are selected for simulation experiments,and the results are better than the literature results,which shows that the proposed algorithm has better performance in solving accuracy and convergence speed,and verifies its feasibility and effectiveness.