遗传算法交叉算子性能对比研究  

Comparation of Crossover Operators in Genetic Algorithm

作　　者：熊军[1] 高敦堂[1] 沈庆宏[1] 都思丹[1] 

机构地区：[1]南京大学电子科学工程系,南京210093

出　　处：《南京大学学报（自然科学版）》2004年第4期432-437,共6页Journal of Nanjing University（Natural Science）

基　　金：国家自然科学基金 (6 0 2 75 0 4 1) ;南瑞继保研究生基金 (2 0 0 3)

摘　　要：就交叉算子性能对比问题 ,提出了算子子代在海明距离上分布的分析方法 ,对遗传算法中常见的单点、双点和均匀交叉算子子代生成空间上子代生成特点进行了系统分析 ,并使用具有代表性的NKLandscape上两种基因关联模型 (NK RND和NKADJ)和两种遗传算法模型 (SGA和SSGA)进行试验 ,试验结果表明不存在算子性能的绝对差异 ,实际问题基因间的关联紧密度及遗传算法模型对交叉算子性能有很大影响 ,当解空间基因位置关联紧密时应用双点交叉算子性能最好 ,而均匀交叉算子性能受SGA和SSGA的影响最小 .Crossover operator is the key search operator in Genetic Algorithm,and one-point,two-point and uniform crossover operators are most frequently used.Previous researchers have made attempts in comparing the performance of these crossover operators,but all neglect the fact that crossover operator must be put into the real implementation of GA with a real problem to see its performance. In this paper we present the comparison of the three crossover operators by analyzing their children generation abilities in the Hamming space.Two kinds of children generation model are used:first,one of the parents is fixed and the other is selected at random;second,both parents are fixed with maximum hamming distance. To illustrate the effects of different problem models and different GA models,experiments are carried out on two types of NK landscape in both the SGA and SSGA model.Results show that no crossover operator is definitely superior to others.The performance of a crossover operator should be measured with different problems and different GA models.Two-point crossover outperforms other crossover operators in problems with adjacent gene connection,and the uniform crossover is more insensitive to different GA models such as SGA and SSGA.

关 键 词：遗传算法 交叉算子 子代生成空间 NK LANDSCAPE 

分 类 号：O224[理学—运筹学与控制论]