二、排料算法的类型与特点-吉林大学研究生教育管理信息系统

《二、排料算法的类型与特点-吉林大学研究生教育管理信息系统》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、文献综述报告题目基于模拟退火遗传算法的变压器硅钢片优化排样的研究姓名王雪红导师魏福玉教授层次硕士所在学院机械科学与工程学院专业机械工程学号2010414048日期2011年9月20日-16-目录目录-1-一、优化排料算法国内外发展状况-2-1.1、优化排料算法国外发展现状-2-1.2、优化排料算法国内发展现状-2-二、排料算法的类型与特点-3-2.1、简单遗传算法-3-2.2、遗传算法的特点-5-2.3、标准遗传算法的局限性及其改进方式-5-2.4、混合遗传算法-6-三、参考文献-11--16-一、优化排料算法国内外发展

2、状况1.1、优化排料算法国外发展现状对于优化排样问题，国外进行得比较早，1939年Kantorovich就提出了一维排样问题。之后，Gilmore和Gomory提出了解决一维排样的方案并深入分析探讨了二维优化排样问题。Maneri和Silverman提出运用向量空间的理论处理排样问题。70年代后，越来越多的学者和专家发现了排样问题的经济价值和社会价值，并对其进行了深入研究，提出了许多算法理论和解决排样问题的方案，并取得重大成果。1970年Haims等提出了动态规划理论和相关算法，Herz提出了一种树叉型搜索策略，并将其用

3、于动态规划理论中。Han和Cintra等将零件拆分技术用于求解排样问题，Faina将模拟退火算法运用于切割下料问题。到了80年代，智能优化算法相继出现，并被广泛运用于求解矩形件和不规则件排样问题。80年代后，智能算法的研究达到一个快速发展的时期，如模拟退火算法、遗传算法、神经网络、蚁群算法、人工免疫算法等算法，这些算法具有一般搜索算法所不具有的优越性，为了充分利用它们的优越特性，人们开始探索组合算法，以求获得更佳的排样效果。MarcelloBraglia用模拟退火算法改善遗传算法求解单排排样问题，Troutt和Bingu

4、l用遗传和模拟退火算法对矩形件排样进行了研究，RameshBabu等用启发式算法来改善遗传算法求解二维排样优化问题，Cristina用免疫算法来改善遗传算法求解二维矩形排样问题。此时，对矩形件排样问题的研究已经取得了相当的成就。1.2、优化排料算法国内发展现状20世纪90年代初国内开始了排样问题的研究，主要是基于简单排样件或矩形件的排样。曹炬博士采用背包算法等来研究不同排样环境下的矩形件排样，对矩形件排样算法进行了深入的研究。徐彦欣采用基于产生式规则和图形靠接算法进行二维零件的排样，讨论和比较了移动靠接算法、碰撞靠接算法

5、、临界多边形算法的特点。此处，董长双深入研究了冲裁件的二维优化排样，周建华深入研究和探索了不规则排样技术，滕健提出用神经网络的相关理论来求解二维不规则零件的排样问题-16-。2000年以后，排样问题进一步得到广大学者和专家的重视，排样件从矩形件逐步发展到规则件和不规则件，排样算法的运用逐步由单一算法发展二种以上算法的组合，并且算法的运用范围和领域也不断扩大。贾志欣采用遗传算法和模拟退火算法来求解矩形件排样问题，提出了最低水平线排样定位算法。吴浩扬等提出了基于模拟退火机制的多种群并行遗传算法。智能算法的出现进一步促进了排样

6、问题的发展，它分别从不同的角度模拟人类的智能活动或某些自然现象，被广泛用来解决工程中存在的复杂问题，如求函数最值、TSP问题、自适应控制、机械领域下料问题、机器人控制方面、服装下料等问题。近几年来，智能算法得到更进一步的发展，如在遗传算法、人工免疫算法、神经网络等等方面的研究。这些方法在搜索过程中具有随机性，具有比数学规划方法更大的优越性，主要表现在：①具有通用性且易于应用；②搜索速度快，所需的时间复杂度小，并且能更快地获得较优排样结果。正是由于这些优点使这类算法在工程问题上具有更为广泛的应用前景，吸引了更多学者和专家对

7、其进行研究和探讨。智能算法也有其自身的缺点，因此学者们开始研究智能算法之间的结合，通过取长补短的办法来达到更好解决工程中遇到的排样问题。二、排料算法的类型与特点2.1、简单遗传算法遗传算法在自然与社会现象模拟、工程计算等方面得到了广泛的应用。在各个不同的应用领域，为了取得更好的结果，人们对GA进行了大量的改进。为了不至于混淆，我们把Holland所提出的算法称为标准遗传算法(CanonicalGeneticAlgorithm)，简称GA或SGA。SGA是一种随机搜索方法，其算法流程如图1所示。与生物种群的进化过程相似，S

8、GA从随机生成的种群(优化问题的解集)开始，按照适者生存的原则，经过选择、交叉、变异等遗传操作，使种群的整体适应度(优化问题的目标函数值)向着增大的方向进化。SGA的核心思想包括:(1)优化问题的一个解经过适当的编码与解码算法，与生物种群中个体的染色体对应，种群的进化操作是针对染色体的。-16-(2)优化问题的目标函