遗传算法中的联结关系  

Linkage in genetic algorithms

作　　者：周树德[1] 孙增圻[2] 

机构地区：[1]中国电子科学研究院,北京100041 [2]清华大学计算机系,北京100084

出　　处：《智能系统学报》2009年第6期483-489,共7页CAAI Transactions on Intelligent Systems

基　　金：国家自然科学基金资助项目(60736023;60674053;90716021)

摘　　要：进化计算领域的一个根本问题是哪些问题适合遗传算法求解,为此需要研究问题的结构对算法性能的影响.变量之间的联结关系是问题的本质属性,决定了遗传算法求解问题的难度.如果某个变量对函数值的影响非线性依赖于其他变量,则认为这些变量之间存在联结关系不,对遗传算法的联结关系这一理论问题进行了深入研究,给出了分析一般离散问题联结结构的理论基础,通过分析傅里叶系数与函数子空间的关系,提出了检测黑箱问题联结结构的确定性和随机性算法,通过试验分析说明了算法的正确性和有效性.One of the most challenging and fundamental problems in the field of evolutionary computation is identification of the classes of problems for which genetic algorithms are especially well（or ill） suited.This is closely related to the question of how the structure of the fitness landscape affects the performance of genetic algorithms.The linkage is referred to as a nonlinear interaction between variables.This is the intrinsic characteristic of the optimization problem,determining the degree of difficulty in solving it.The authors focused on the linkage problem with genetic algorithms and were able to establish a theoretical foundation for the analysis of linkage structures.Based on Fourier analysis of problem structure,it was proven that mask strings with nonzero Fourier coefficients accurately reflect linkage structure.A deterministic and stochastic algorithm for identifying the linkage structure of black-box problems was discussed and experimental results verified its correctness and efficiency.

关 键 词：遗传算法 联结关系 适应值函数 傅里叶分析 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]