| 一种改进遗传算法在最大独立子集问题中的应用 |
| |
| 引用本文： | 王淑礼,王煜霞.一种改进遗传算法在最大独立子集问题中的应用[J].数学的实践与认识,2011,41(11). |
| |
| 作者姓名： | 王淑礼 王煜霞 |
| |
| 作者单位： | 1. 信阳师范学院计算机与信息技术学院,河南信阳,464000
2. 河南信息工程学校基础科学系,河南郑州,450002 |
| |
| 基金项目： | 河南省教育厅自然科学研究计划项目 |
| |
| 摘 要： | 最大独立子集问题是组合优化问题中的一个重要问题,该问题是一个NP难题,其目标是在一个环图中找到一个最大的独立子集.提出了一种改进的遗传算法来解决这个问题,用一种基于条件的遗传算子来代替通常的基于概率的遗传算子.实验结果表明提出的算法是有效的.
|
| 关 键 词： | 遗传算法 条件遗传 组合优化 最大独立子集 |
Application of Solving MISP Based on Improved Genetic Algorithm |
| |
| WANG Shu-li,WANG Yu-xia.Application of Solving MISP Based on Improved Genetic Algorithm[J].Mathematics in Practice and Theory,2011,41(11). |
| |
| Authors: | WANG Shu-li WANG Yu-xia |
| |
| Institution: | WANG Shu-li~1,WANG Yu-xia~2 (1.School of Computer and Information Technology,Xinyang Normal University,Xinyang 464000,China) (2.Department of Basic Science,Henan Information Engineering School,Zhengzhou,450002,China) |
| |
| 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... |
| |
| Keywords: | genetic algorithm conditional GA combinatorial optimization maximum independent set |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
