论文部分内容阅读
集合覆盖问题是组合优化中的典型问题,在日常生活中有着广泛的应用.提出了一种改进遗传算法来解决集合覆盖问题.算法对标准遗传算法的改进主要表现在:1)结合启发式算法和随机生成,设计了新的产生初始种群的方法;2)引入修补操作处理不可行解使其转换成可行解;3)对重复个体进行处理再利用;4)对多点交叉进行推广,提出了新的交叉算子;5)针对可行解和不可行解,采取两种自适应多位变异操作.数值实验结果表明该算法对于解决规模较大的集合覆盖问题是有效的.
Set covering problem is a typical problem in combinatorial optimization and has been widely used in daily life.An improved genetic algorithm is proposed to solve the set covering problem.The improvement of the standard GA is mainly as follows: 1) Combining heuristic algorithm And randomly generated, designed a new method to generate the initial population; 2) the introduction of repair operations to deal with the infeasible solution to make it feasible solution; 3) the repeated individual processing and reuse; 4) the promotion of multi-point crossover, put forward A new crossover operator is proposed.5) For adaptive and infeasible solutions, two adaptive multi-bit mutation operations are taken.The numerical experiments show that the proposed algorithm is effective to solve the large-scale set-covering problem.