PAGE-16-文献综述报告题目基于模拟退火遗传算法的变压器硅钢片优化排样的研究姓名王雪红导师魏福玉教授层次硕士所在学院机械科学与工程学院专业机械工程学号2010414048日期2011年9月20日目录TOC\o"1-2"\h\z\uHYPERLINK\l"_Toc309982248"目录PAGEREF_Toc309982248\h-1-HYPERLINK\l"_Toc309982249"一、优化排料算法国内外发展状况PAGEREF_Toc309982249\h-2-HYPERLINK\l"_Toc309982250"1.1、优化排料算法国外发展现状PAGEREF_Toc309982250\h-2-HYPERLINK\l"_Toc309982251"1.2、优化排料算法国内发展现状PAGEREF_Toc309982251\h-2-HYPERLINK\l"_Toc309982252"二、排料算法的类型与特点PAGEREF_Toc309982252\h-3-HYPERLINK\l"_Toc309982253"2.1、简单遗传算法PAGEREF_Toc309982253\h-3-HYPERLINK\l"_Toc309982254"2.2、遗传算法的特点PAGEREF_Toc309982254\h-5-HYPERLINK\l"_Toc309982255"2.3、标准遗传算法的局限性及其改进方式PAGEREF_Toc309982255\h-5-HYPERLINK\l"_Toc309982256"2.4、混合遗传算法PAGEREF_Toc309982256\h-6-HYPERLINK\l"_Toc309982257"三、参考文献PAGEREF_Toc309982257\h-11-一、优化排料算法国内外发展状况1.1、优化排料算法国外发展现状对于优化排样问题，国外进行得比较早，1939年Kantorovich就提出了一维排样问题。之后，Gilmore和Gomory提出了解决一维排样的方案并深入分析探讨了二维优化排样问题。Maneri和Silverman提出运用向量空间的理论处理排样问题。70年代后，越来越多的学者和专家发现了排样问题的经济价值和社会价值，并对其进行了深入研究，提出了许多算法理论和解决排样问题的方案，并取得重大成果。1970年Haims等提出了动态规划理论和相关算法，Herz提出了一种树叉型搜索策略，并将其用于动态规划理论中。Han和Cintra等将零件拆分技术用于求解排样问题，Faina将模拟退火算法运用于切割下料问题。到了80年代，智能优化算法相继出现，并被广泛运用于求解矩形件和不规则件排样问题。80年代后，智能算法的研究达到一个快速发展的时期，如模拟退火算法、遗传算法、神经网络、蚁群算法、人工免疫算法等算法，这些算法具有一般搜索算法所不具有的优越性，为了充分利用它们的优越特性，人们开始探索组合算法，以求获得更佳的排样效果。MarcelloBraglia用模拟退火算法改善遗传算法求解单排排样问题，Troutt和Bingul用遗传和模拟退火算法对矩形件排样进行了研究，RameshBabu等用启发式算法来改善遗传算法求解二维排样优化问题，Cristina用免疫算法来改善遗传算法求解二维矩形排样问题。此时，对矩形件排样问题的研究已经取得了相当的成就。1.2、优化排料算法国内发展现状20世纪90年代初国内开始了排样问题的研究，主要是基于简单排样件或矩形件的排样。曹炬博士采用背包算法等来研究不同排样环境下的矩形件排样，对矩形件排样算法进行了深入的研究。徐彦欣采用基于产生式规则和图形靠接算法进行二维零件的排样，讨论和比较了移动靠接算法、碰撞靠接算法、临界多边形算法的特点。此处，董长双深入研究了冲裁件的二维优化排样，周建华深入研究和探索了不规则排样技术，滕健提出用神经网络的相关理论来求解二维不规则零件的排样问题。2000年以后，排样问题进一步得到广大学者和专家的重视，排样件从矩形件逐步发展到规则件和不规则件，排样算法的运用逐步由单一算法发展二种以上算法的组合，并且算法的运用范围和领域也不断扩大。贾志欣采用遗传算法和模拟退火算法来求解矩形件排样问题，提出了最低水平线排样定位算法。吴浩扬等提出了基于模拟退火机制的多种群并行遗传算法。智能算法的出现进一步促进了排样问题的发展，它分别从不同的角度模拟人类的智能活动或某些自然现象，被广泛用来解决工程中存在的复杂问题，如求函数最值、TSP问题、