Study on Application of Double Population Hybrid Genetic Algorithm in Cut Order Planning

doi:10.3778/j.issn.1002-8331.2007-0013

Abstract

Abstract:

In order to solve the problem of cut order planning in apparel production, a multi-objective mathematical model of cut order planning is established for optimization based on the influencing factors of production process and order requirements, and an improved double population particle swarm-genetic hybrid algorithm is used to solve the model. The hybrid algorithm divides the evolutionary population into a general population and an elite population, uses an improved genetic algorithm to search the evolutionary general population globally and screen the elite individuals, and combines the particle swarm optimization algorithm to evolve the elite population. Crossover and mutation ensure the diversity of the population, the optimization mechanism of particle swarm improves the speed of evolution, and the two groups constantly search for the optimal solution due to their cross influence during evolution. The experimental results show that the hybrid algorithm is stable in solving the multi-objective cut order planning problem. It has a faster optimization speed than the improved genetic algorithm. It reduces one cutting bed than the manual calculation method, and the cutting time is shortened by 5 min. The number of overcuts is reduced by 60%, which can adapt to different neets, and has certain application value in the actual production of cut order panning.

Key words: cut order planning, multi-objective, double population, genetic algorithm, particle swarm optimization, cross influence

摘要：

为解决服装生产中的裁剪分床计划问题，结合生产过程的影响因素和订单需求，建立了裁剪分床的多目标数学模型进行优化，使用一种改进的双种群粒子群-遗传混合算法对模型进行求解。混合算法将进化种群划分为普通种群和精英种群，利用改进的遗传算法来全局搜索进化普通群体并筛选精英个体，同时结合粒子群优化算法进化精英群体。交叉和变异保证种群的多样性，粒子群寻优机制提升进化速度，两种群在进化时交叉影响不断寻找最优方案。实验结果表明：混合算法在解决多目标的生产订单裁剪分床问题上表现稳定，相比改进的遗传算法有更快的寻优速度，比手工计算方法减少1个裁床，裁剪时间缩短5?min且超裁数量降低60%，可以适应不同目标需求，针对实际生产中的裁剪分床有一定的应用价值。

关键词: 裁剪分床计划, 多目标, 双种群, 遗传算法, 粒子群优化, 交叉影响

DU Shouxin, WU Tao. Study on Application of Double Population Hybrid Genetic Algorithm in Cut Order Planning[J]. Computer Engineering and Applications, 2021, 57(22): 182-189.

杜守信，毋涛. 双种群混合遗传算法的裁剪分床应用研究[J]. 计算机工程与应用, 2021, 57(22): 182-189.

References

[1] 庹武，郑攀，常亭亭，等.基于层次分析法的服装裁剪分床影响因素[J].纺织学报，2013，34（4）：148-152.
TUO W，ZHENG P，CHANG T T，et al.Analysis of factors affecting cutting scheme based on analytical hierarchy process[J].Journal of Textile Research，2013，34（4）：148-152.
[2] JELIL R A.Review of artificial intelligence applications in garment manufacturing[M]//Artificial intelligence for fashion industry in the big data era.Singapore：Springer，2018：97-123.
[3] üNAL C，YüKSEL A D.Cut order planning optimisation in the apparel industry[J].Fibres & Textiles in Eastern Europe，2020（139）：8-13.
[4] NASCIMENTOD B，DE FIGUEIREDO J N，MAYERLE S F，et al.A state-space solution search method for apparel industry spreading and cutting[J].International Journal of Production Economics，2010，128（1）：379-392.
[5] M’HALLAH R，BOUZIRI A.Heuristics for the combined cut order planning two-dimensional layout problem in the apparel industry[J].International Transactions in Operational Research，2014，23（1/2）：321-353.
[6] 王学骥，周俊.基于粒子群优化算法的多目标裁剪优化分配的研究[J].工业控制计算机，2014，27（12）：112-114.
WANG X J，ZHOU J.Multi-objective optimization of cutting distribution based on particle swarm optimizer[J].Industrial Control Computer，2014，27（12）：112-114.
[7] 江丽林，周巨栋，董辉.基于自适应加速因子粒子群优化算法的裁剪分床研究[J].计算机测量与控制，2018，26（1）：181-184.
JIANG L L，ZHOU J D，DONG H.Research on cutting distribution based on self-adaptive acceleration factor particle swarm optimization[J].Computer Measurement & Control，2018，26（1）：181-184.
[8] 刘艳梅，颜少聪，纪杨建，等.大批量定制服装裁剪分床计划的两阶段优化方法[J].计算机集成制造系统，2012，18（3）：479-485.
LIU Y M，YAN S C，JI Y J，et al.Two stage optimization method of cut order planning for apparel mass customization[J].Computer Integrated Manufacturing Systems，2012，18（3）：479-485.
[9] XU Y，THOMASSEY S，ZENG X.Optimization of garment sizing and cutting order planning in the context of mass customization[J].The International Journal of Advanced Manufacturing Technology，2020，106：3485-3503.
[10] ABEYSOORIYA R P，FERNANDO T G I.Hybrid approach to optimizecut order plan solutions in apparel manufacturing[J].International Journal of Information Communication Technology Research，2012，2（4）：348-353.
[11] TSAO Y-C，VU T-L，LIAO L-W.Hybrid heuristics for the cut ordering planning problem in apparel industry[J].Computers & Industrial Engineering，2020，144：106478.
[12] 马永杰，云文霞.遗传算法研究进展[J].计算机应用研究，2012，29（4）：1201-1206.
MA Y J，YUN W X.Research progress of genetic algorithm[J].Application Research of Computers，2012，29（4）：1201-1206.
[13] 杨俊胜，沈航驰，葛鹏，等.粒子群优化算法[J].软件，2020，41（5）：228-230.
YANG J S，SHEN H C，GE P，et al.Particle swarm optimization algorithm[J].Computer Engineering & Software，2020，41（5）：228-230.
[14] 张超群，郑建国，钱洁.遗传算法编码方案比较[J].计算机应用研究，2011，28（3）：819-822.
ZHANG C Q，ZHENG J G，QIAN J.Comparison of coding schemes for genetic algorithms[J].Application Research of Computers，2011，28（3）：819-822.
[15] TSOULOSIG，TZALLAS A，TSALIKAKIS D.PDoublePop：an implementation of parallel genetic algorithm for function optimization[J].Computer Physics Communications，2016，209：183-189.
[16] 王东风，孟丽.粒子群优化算法的性能分析和参数选择[J].自动化学报，2016，42（10）：1552-1561.
WANG D F，MENG L.Performance analysis and parameter selection of PSO algorithms[J].Acta Automatica Sinica，2016，42（10）：1552-1561.
[17] 董红斌，李冬锦，张小平.一种动态调整惯性权重的粒子群优化算法[J].计算机科学，2018，45（2）：98-102.
DONG H B，LI D J，ZHANG X P.Particle swarm optimization algorithm with dynamically adjusting inertia weight[J].Computer Science，2018，45（2）：98-102.
[18] 刘文英，张自鲁，路慎强，等.基于粒子群-遗传混合算法的函数优化研究[J].计算机技术与发展，2019，29（10）：170-174.
LIU W Y，ZHANG Z L，LU S Q，et al.Research on function optimization based on particle swarm-genetic hybrid algorithm[J].Computer Technology and Development，2019，29（10）：170-174.