3 叶片排序的逐步调优模拟搜索算法.pdf

维普资讯 第 18卷 第 1期 四川理工学院学报 (自然科学版) Vo1．18No．1 JOURNALOFSICHUANUNIVERSITYOF 2005年 3月 SCIENCEENGINEERING(NATURALSCIENCEEDITIoN) Mar．2005 文章编号：1673—1549 (2005)01—0088—07 叶片排序的逐步调优模拟搜索算法 岳健民 ，柏宏斌 1，刘自川2，廖翠华 (1．四川理工学院数学系，四川 自贡 643000；2．重庆垫江普顺学校，重庆 垫江 408300) 摘 要：文章根据叶片重量和频率的工艺要求，讨论了压气机叶片的排序算法问题，该问题是一个 NP难题，直接求解很困难。建立了一个组合优化模型，给出了逐步调整优化的模拟搜索算法，并利用 MATLAB软件实现算法，且进行了实现的时间复杂度检验，最后求得了最优的结果。 关键词：叶片排序；NP难题；逐步调整4L4L；模拟搜索 中图分类号：F224．9 文献标识码：A 1问题 的提 出 在实际生产中，由于加 ：出的压气机叶片的重量和频率不同，所 以，在安装时就需要按 i艺要求对 叶片进行重新排序 。具体的 艺要求有： (1) 压气机 24片叶片均匀分布在一圆盘边上，分成六个象限，每象限4片叶片的总重苗与相邻 象限4片叶片的总重鼙之差不允许超过 8g。 (2) 叶片排序不仅要保证重量差，还要满足频率要求，两相邻叶片频率差尽量大，使相邻叶片频 率差不小于 6Hz。 (3) 当叶片不满足上述要求时，允许更换少量叶片。 表 1两组叶片的重量和频率数据 现在根据表 1所给出的两组具体数据，讨论下列问题： 第一，给 出按重量排序的算法； 第二，给出按重量和频率排序的算法； 第三，在叶片不满足重量和频率要求时，指出所更换叶片及新叶片的重量和频率值范闸； 第四，当叶片保证了重量筹和频率差时，按排列顺序输出叶片的序号； 收稿 日期：2004—10—18 作者简介：岳健民 (1964一)，男，四川人，副教授，主要从事最优化理论研究． 维普资讯 第18卷 第 1期 岳健民等：叶片排序的逐步调优模拟搜索算法 89 第五，建立模型确定叶片工业标准 (重量与频率)和加工出最佳方案。 2 问题分析 2．1按重量排序的算法的制定 问题讨论的是有限制条件的排序算法，根据表 1，所有可能的排序有 24组，即约有 10 组，这是 一 个很人的数字，要是用穷举法，算法的时间复杂度太人，直接给出排序是不可能的。为此寻找一种快 速算法 ，是本题的关键。在考虑叶片满足重量限制条件的基础上，就只需考虑 6个象限之 间的关系，叶 片与叶片之间的排序暂时不考虑。同时，挖掘出题 目中的约束条件，由象限之间的重量之差的上限要求， 可知质量的偏差越小，组合的结果就越优。在这些约束条件的限制之下，去掉不合条 ：的组，逐步的缩 小最优解的范围，求出尽量少的可能满足条件的组的集合。 所以，我4t．1$1J定一个组合优化的目标函数，用重量上限作为约束条件。为了使 目标函数以最快的收 敛速度达到最优，我们没有必要求出所有的组合，在程序搜索处理之前，先去掉可能满足条件但不是较 优的组，从而减少循环次数，逐步优化，最后得出最优的组合。 2．2按重量和频率排序算法的给出 在按重量排序的算法给定后，用该算法可 以先求出满足重量限制要求的最优组合，在这些最优的组 合里，相同的质量对应的频率可能不同，在重量排序给定的前提下，相邻叶片要满足频率差的限制。这 就需要对象限中的同质量的叶片重新排序，确定满足叶片频率要求的序号。 为方便算法的给出，我们给出了一个原则：在一个象限中，频率按 “人小大小”的顺序排列，排列 出的数之间的差值要达到最入。 在此