【摘要】 最大独立子集问题是组合优化问题中的一个重要问题,该问题是一个NP难题,其目标是在一个环图中找到一个最大的独立子集.提出了一种改进的遗传算法来解决这个问题,用一种基于条件的遗传算子来代替通常的基于概率的遗传算子.实验结果表明提出的算法是有效的.更多还原

【Abstract】 The maximum independent set problem(MISP) is of central importance combinatorial optimization problem.It has many practical applications in science and engineering. The goal of this NP-complete problem is to find a maximum independent set in a given circle graph.In this paper,we propose a genetic algorithm based approach to solve the problem. In the proposed approach,the genetic operators are performed basing on condition instead of probability.The proposed algorithm is tested on a large number of instances and the simulation results show that the proposed method is superior to its competitors.更多还原