基于最大独立集的钢种集约问题求解方法  

Algorithms for solving steel grade intensivism problem based on maximum independent set

作　　者：易剑[1,2] 贾树晋[2] 谭树彬[1] 杜斌[1,2] 

机构地区：[1]东北大学信息科学与工程学院,辽宁沈阳110819 [2]宝钢研究院自动化研究所,上海201900

出　　处：《系统工程学报》2014年第3期414-422,共9页Journal of Systems Engineering

基　　金：国家自然科学基金和宝钢联合资助项目(50974145);上海市科委重点科研项目基金资助项目(09DZ1120900)

摘　　要：针对炼钢生产中的钢种集约问题,建立了数学模型,并以图论的思路设计了一种基于最大独立集的求解方法.首先基于图论知识,构造了钢种集约问题的图,并证明了最大独立集的独立数是它的主目标的下界;然后对图进行赋权,以实现对次要目标的控制;最后在最大独立集的基础上,采用图分解的方法,对赋权图递归分解来获得优化后的钢种集约方案.选择实际生产数据构造了一些测试案例,对它们进行仿真计算,结果表明所提出的算法明显好于遗传算法;同时分析了图的顶点、密度变化对算法性能的影响,揭示了它们之间的关系.The steel grade intensivism problem（SGIP） in steelmaking production was described and its math- ematic model was constructed. Algorithms based on maximum independent set（MIS） of graph theory were proposed to solve the model. Firstly, the graph of SGIP was set up by using the graph theory and the lower bound of the prime goal was proven to be the cardinality of MIS. Then, the weights were labeled on the graph in order to control the subordinate goal. Thirdly, on the basis of MIS, algorithms that the weighted graph was decomposed recursively were designed to obtain the optimal combination project of steel grade. After simulation on some experiments from actual production data, the results show that the presented algorithms are much better than genetic algorithm. Moreover, the impacts on algorithms performance from the nodes number or density of the graph are analysed and their relations are expressed by the figure.

关 键 词：钢种集约 图论 最大独立集 遗传算法 

分 类 号：O157.6[理学—数学] TP301[理学—基础数学]