| New Hybrid Genetic Algorithm for Vertex Cover Problems |
| |
| 作者姓名： | 霍红卫 许进 |
| |
| 作者单位： | Huo Hongwei & Xu Jin
1. School of Computer Science，Xidian University，Xi'an 710071，P. R. China;
2. Department of Control Science and Engineering，Huazhong University of
Science and Technology，Wuhan 430074，P. R. China |
| |
| 基金项目： | This project was supported by the National Natural Science Foundation of China，the Open Project Foundation of Comput-er Software New Technique National Key Laboratory of Nanjing University. |
| |
| 摘 要： | This paper presents a new hybrid genetic algorithm for the vertex cover problems in which scan-repair and local improvement techniques are used for local optimization. With the hybrid approach, genetic algorithms are used to perform global exploration in a population, while neighborhood search methods are used to perform local exploitation around the chromosomes. The experimental results indicate that hybrid genetic algorithms can obtain solutions of excellent quality to the problem instances with different sizes. The pure genetic algorithms are outperformed by the neighborhood search heuristics procedures combined with genetic algorithms.
|
New Hybrid Genetic Algorithm for Vertex Cover Problems |
| |
| Huo Hongwei & Xu Jin
. School of Computer Science,Xidian University,Xi'an ,P. R. China.New Hybrid Genetic Algorithm for Vertex Cover Problems[J].Journal of Systems Engineering and Electronics,2003,14(4). |
| |
| Authors: | Huo Hongwei & Xu Jin
School of Computer Science Xidian University Xi'an P R China |
| |
| Institution: | 1. School of Computer Science, Xidian University, Xi'an 710071, P. R. China
2. Department of Control Science and Engineering, Huazhong University of Science and Technology, Wuhan 430074, P. R. China |
| |
| Abstract: | This paper presents a new hybrid genetic algorithm for the vertex cover problems in which scan-repair and local improvement techniques are used for local optimization. With the hybrid approach, genetic algorithms are used to perform global exploration in a population, while neighborhood search methods are used to perform local exploitation around the chromosomes. The experimental results indicate that hybrid genetic algorithms can obtain solutions of excellent quality to the problem instances with different sizes. The pure genetic algorithms are outperformed by the neighborhood search heuristics procedures combined with genetic algorithms. |
| |
| Keywords: | vertex cover hybrid genetic algorithm scan-repair local improvement |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
