矩形件优化排样的自适应遗传模拟退火算法

中国机械工程 ›› 2013, Vol. 24 ›› Issue (18): 2499-2504.

矩形件优化排样的自适应遗传模拟退火算法

董德威;颜云辉;张尧;李骏

东北大学，沈阳，110819

出版日期:2013-09-25 发布日期:2013-09-30
基金资助:
国家自然科学基金资助项目(50574019)；国家高技术研究发展计划(863计划)资助项目( 2008AA04Z135)；中央高校基本科研业务费专项资金资助项目(N100603002)
National Natural Science Foundation of China（No. 50574019）;

National High-tech R&D Program of China (863 Program) （No. 2008AA04Z135）;
Fundamental Research Funds for the Central Universities( No. N100603002 )

Adaptive Genetic Simulated Annealing Algorithm in Optimal Layout of Rectangular Parts

Dong Dewei;Yan Yunhui;Zhang Yao;Li Jun

Northeastern University,Shenyang,110819

Online:2013-09-25 Published:2013-09-30
Supported by:

National Natural Science Foundation of China（No. 50574019）;

National High-tech R&D Program of China (863 Program) （No. 2008AA04Z135）;
Fundamental Research Funds for the Central Universities( No. N100603002 )

摘要/Abstract

摘要：

针对理论上属于NP完全问题的矩形件优化排样问题，提出了一种基于小生境技术的自适应遗传模拟退火算法。研究了将矩形件在板材上的排列方式转换为特定编码的方法，利用遗传模拟退火算法进行全局优化概率搜索，考虑到算法中交叉概率和变异概率的选择影响到算法收敛性，提出了自适应的交叉概率和变异概率，并通过小生境技术对子辈个体是否替换父辈个体加以控制，最终得到矩形件排样的最优次序和排放方式，采用最低水平线策略的启发式排样算法实现自动排样。排样实例表明，该优化排样算法行之有效，具有广泛的适应性。

关键词: 矩形件优化排样, 自适应遗传模拟退火算法, 小生境技术, 启发式算法

Abstract:

Aiming at the optimal layout problem of two dimensional rectangular parts, which is a NP-complete problem, an adaptive niched genetic simulated annealing algorithm was presented. This paper translated the layout of rectangular parts on a rectangle into a special coding of genetic algorithm, the proposed approach automatically looked for the best sequence of the rectangular parts and each part's optimum rotation by the genetic simulated annealing algorithm. Considering the choice of crossover probability and mutation probability affected algorithm convergence, the adaptive crossover probability and mutation probability were put forward. The niche technology controlled whether the child individual replacement the parent individual or not. Finally, the lowest horizontal algorithm completed the automatic layout. Examples indicate that the algorithm is effective and practical.

Key words: optimal layout of rectangular parts, adaptive genetic simulated annealing algorithm, niche technology, heuristic algorithm

中图分类号:

TP391.7

董德威;颜云辉;张尧;李骏. 矩形件优化排样的自适应遗传模拟退火算法[J]. 中国机械工程, 2013, 24(18): 2499-2504.

参考文献

[1]Farley A A. Mathematical Programming Models forCutting Stock Problems in the Clothing Industry[J]. Journal of the Operational Research Society,1988,39(1):41-53.
[2]Reda M S, Abd E A. An Interactive Technique forthe Cutting Stock Problem with Multiple Objects[J]. European Journal of Operational Research,1994,78(3):304-317.
[3]Shpitalni M, Manevich V. Optimal OrthogonalSubdivision of Rectangular Sheets[J]. Transactionsof ASME Journal of Manufacturing Science and En-gineering, 1996 , 118(3) :281-288.
[4]曹炬,周济.矩形件排样优化的背包算法[J].中国机械工程,1994,5(2):11-12.
[5]李明[1,2],周泽魁[1].基于粒子群算法的矩形件优化排样[J].电路与系统学报,2007,12(2):39-42.
[6]史俊友[1],苏传生[1],翟红岩[1].不规则零件优化排样的神经网络混合优化算法[J].工程设计学报,2009,16(4):271-275.
[7]Liu D Q, Teng H F. An Improved BL— algorithmfor Genetic Algorithm of the Orthogonal Packing ofRectangles[J]. European Journal of Operational Re-search,1999,112(2):413-420.
[8]杨威,罗阳,刘胜青.大规模矩形零件优化套排的遗传算法[J].四川大学学报：工程科学版,2001,33(5):59-62.
[9]Babu A R,Babu N R. Effective Nesting of Rectan-gular Parts in Multiple Rectangular Sheets UsingGenetic and Heuristic Algorithms [J]. InternationalJournal of Production Research,1999,37(7) : 1625-1643.
[10]Bekiroglu S,Debe T, Ayvaz Y. Implementation ofDifferent Encoding Types on Structural Optimiza-tion Based on Adaptive Genetic Algorithm[J]. Fi-nite Elements in Analysis and Desigh, 2009,45(11):826-835.
[11]Lee C P,Lin W S, Chen Y M, et al. Gene Selec-tion and Sample Classification on Microarray DataBased on Adaptive Genetic Algorithm/k—nearestNeighbor Method[J]. Expert Systems with Appli-cations,2011,38(5) :4661-4667.
[12]周明,孙树栋编著.遗传算法原理及应用[M],1999:203.
[13]王小平曹立明.遗传算法-理论、应用与软件实现[M].西安:西安交通大学出版社,2001..
[14]Suman B. Study of Simulated Annealing Based Al-gorithm for Multi Objective Optimization of aConstrained Problem [J]. Computer & ChemicalEngineering,2004 ,28(9) : 1849-1871.
[15]贾志欣,殷国富,罗阳.二维不规则零件排样问题的遗传算法求解[J].计算机辅助设计与图形学学报,2002,14(5):467-470.