集约简算法和改进遗传算法混合求解集合覆盖问题  

A Hybrid Method of Set Reduction Algorithom and Modified Genetic Algorithm for Set Covering Problem

作　　者：陈向阳[1] 李汪根 胡东辉[3] 

机构地区：[1]安庆医药高等专科学校公共基础部 [2]安徽师范大学数学计算机科学学院 [3]合肥工业大学计算机与信息学院

出　　处：《池州学院学报》2017年第6期41-44,共4页Journal of Chizhou University

基　　金：安徽省自然基金项目(1508085MF115);高校优秀中青年骨干人才国内外访学研修重点项目(gxfx ZD2016336)

摘　　要：集合覆盖问题是一个经典的组合优化问题,在实践中得到了广泛的应用。提出一种集合覆盖问题的混合算法:通过集约简算法,它成为最简单的网络;然后通过选择染色体的种群启发式改进的遗传参数获得最佳的解决方案。模拟实验表明,当测试集的规模比原来的问题小十倍以内时集约简算法效果明显;在全局搜索最小和收敛速度上改进遗传算法具有明显的效果。Set covering problem is a classical combinatorial optimization problems, has been widely applied in practice. The hybrid algorithm for solving the set covering problem is put forward. It becomes the simplest network by the set reduction algorithm. And then, it obtains the optimal solution through the selection and genetic parameters in population heuristic improvement of chromosome. The simulated experiment shows that SRA has obvious effect,that the scale of test set is from several to ten times smaller than the original problem. The MGA has obvious effect in global searching for minima and convergence speed.

关 键 词：集合覆盖问题 集约简算法(SRA) 改进遗传算法(MGA) 混合算法 

分 类 号：TP319[自动化与计算机技术—计算机软件与理论]