| Global Convergence Analysis of Non-Crossover Genetic Algorithm and Its Application to Optimization |
| |
| 作者姓名： | Dai Xiaoming Sun Rang Zou Runmin Xu Chao & Shao Huihe |
| |
| 作者单位： | . Dept. of Auto.，School of Electric and Information，Shanghai Jiaotong University，Shanghai 200030，P. R. China; College of Information Science and Enginereing，Central South University，Changsha |
| |
| 摘 要： | Selection, crossover, and mutation are three main operators of the canonical genetic algorithm (CGA). This paper presents a new approach to the genetic algorithm. This new approach applies only to mutation and selection operators. The paper proves that the search process of the non-crossover genetic algorithm (NCGA) is an ergodic homogeneous Markov chain. The proof of its convergence to global optimum is presented. Some nonlinear multi-modal optimization problems are applied to test the efficacy of the NCGA. NP-hard traveling salesman problem (TSP) is cited here as the benchmark problem to test the efficiency of the algorithm. The simulation result shows that NCGA achieves much faster convergence speed than CGA in terms of CPU time. The convergence speed per epoch of NCGA is also faster than that of CGA.
|
Global Convergence Analysis of Non-Crossover Genetic Algorithm and Its Application to Optimization |
| |
| Dai Xiaoming,Sun Rang,Zou Runmin,Xu Chao & Shao Huihe.Global Convergence Analysis of Non-Crossover Genetic Algorithm and Its Application to Optimization[J].Journal of Systems Engineering and Electronics,2002,13(2). |
| |
| Authors: | Dai Xiaoming SUN Rong Zou Runmin Xu Chao Shao Huihe |
| |
| Abstract: | Selection, crossover, and mutation are three main operators of the canonical genetic algorithm (CGA). This paper presents a new approach to the genetic algorithm. This new approach applies only to mutation and selection operators. The paper proves that the search process of the non-crossover genetic algorithm (NCGA) is an ergodic homogeneous Markov chain. The proof of its convergence to global optimum is presented. Some nonlinear multi-modal optimization problems are applied to test the efficacy of the NCGA. NP-hard traveling salesman problem (TSP) is cited here as the benchmark problem to test the efficiency of the algorithm. The simulation result shows that NCGA achieves much faster convergence speed than CGA in terms of CPU time. The convergence speed per epoch of NCGA is also faster than that of CGA. |
| |
| Keywords: | Canonical Genetic algorithm Ergodic homogeneous Markov chain Global convergence |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
