[1]周树德,孙增圻.遗传算法中的联结关系[J].智能系统学报,2009,4(06):483-489.[doi:10.3969/j.issn.1673-4785.2009.06.003]
 ZHOU Shu-de,SUN Zeng-qi.Linkage in genetic algorithms[J].CAAI Transactions on Intelligent Systems,2009,4(06):483-489.[doi:10.3969/j.issn.1673-4785.2009.06.003]
点击复制

遗传算法中的联结关系(/HTML)
分享到:

《智能系统学报》[ISSN:1673-4785/CN:23-1538/TP]

卷:
第4卷
期数:
2009年06期
页码:
483-489
栏目:
出版日期:
2009-12-25

文章信息/Info

Title:
Linkage in genetic algorithms
文章编号:
1673-4785(2009)06-0483-07
作者:
周树德1孙增圻2
1.中国电子科学研究院,北京 100041; 2.清华大学 计算机系,北京 100084
Author(s):
ZHOU Shu-de1 SUN Zeng-qi2
1. China Academy of Electronic and Information Technology, Beijing 100041, China; 2. Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China
关键词:
遗传算法联结关系适应值函数傅里叶分析
Keywords:
genetic algorithm linkage fitness function Fourier analysis
分类号:
TP18
DOI:
10.3969/j.issn.1673-4785.2009.06.003
文献标志码:
A
摘要:
进化计算领域的一个根本问题是哪些问题适合遗传算法求解,为此需要研究问题的结构对算法性能的影响.变量之间的联结关系是问题的本质属性,决定了遗传算法求解问题的难度.如果某个变量对函数值的影响非线性依赖于其他变量,则认为这些变量之间存在联结关系不,对遗传算法的联结关系这一理论问题进行了深入研究,给出了分析一般离散问题联结结构的理论基础,通过分析傅里叶系数与函数子空间的关系,提出了检测黑箱问题联结结构的确定性和随机性算法,通过试验分析说明了算法的正确性和有效性.
Abstract:
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.

参考文献/References:

[1]THIERENS D. Scalability problems of simple genetic algorithms[J].Evolutionary Computation, 1999, 7(4):331-352.
[2]GOLDBERG D E. The design of innovation: lessons from and for competent genetic algorithms[M]. Boston: Kluwer Academic Publishers, 2002:88-95.
[3]MENON A. Frontiers of evolutionary computation[M]. London: Kluwer Publisher, 2004:23-27.
[4]周树德.遗传算法中联结关系检测的理论和方法研究[D].北京:清华大学,2007.
          ZHOU Shude. Research on theory and methods for linkage detection in genetic algorithms[D]. Beijing:Tsinghua University,2007.
[5]DAVIDOR Y. Epistasis variance: a viewpoint on GA-hardnes[C]//Proceedings of the 6th International Conference on Genetic Algorithms. San Mateo:Morgan Kaufmann, 1995:133-138.
[6]CHEN Y P. Extending the scalability of linkage learning genetic algorithms: theory and practice[D]. Champaign: UIUC, 2004.
[7]HECKENDORN R B. Embedded landscapes[J]. Evolutionary Computation, 2002, 10(4):345-369.
[8]HECKENDORN R B, WRIGHT A. Efficient linkage discovery by limited probing[J]. Evolutionary Computation, 2004, 12(4):517-545.

相似文献/References:

[1]周本达,陈明华.随机化均匀设计混合遗传算法求解图的二划分问题[J].智能系统学报,2009,4(01):91.
 ZHOU Ben-da,CHEN Ming-hua.Solving the 2-way graph partitioning problem using a genetic algorithm based on randomized uniform design[J].CAAI Transactions on Intelligent Systems,2009,4(06):91.
[2]康 琦,汪 镭,刘小莉,等.基于群体智能框架理念的遗传算法总体模式描述[J].智能系统学报,2007,2(05):42.
 KANG Qi,WANG Lei,LIU Xiao-li,et al.General mode description genetic algorithms based on a framework of swarm intelligence[J].CAAI Transactions on Intelligent Systems,2007,2(06):42.
[3]马 炫,张亚龙.基于遗传算法的大规模矩形件优化排样[J].智能系统学报,2007,2(05):48.
 MA Xuan,ZHANG Ya-long.A genetic algorithm for the layout of large scale rectang ular parts[J].CAAI Transactions on Intelligent Systems,2007,2(06):48.
[4]徐 雄.人工情感的进化控制系统实现[J].智能系统学报,2008,3(02):135.
 XU Xiong.Implementation of an evolutionary control system based on artificial emotion[J].CAAI Transactions on Intelligent Systems,2008,3(06):135.
[5]刘 胜,李高云,孙天英.一种基于种群多样度的实数编码并行遗传算法[J].智能系统学报,2008,3(05):423.
 L IU Sheng,L I Gao-yun,SUN Tian-ying.A real coding parallel genetic algorithm based on diversity of population[J].CAAI Transactions on Intelligent Systems,2008,3(06):423.
[6]张 涛,费树岷,李晓东.基于GARBF神经网络及边界不变特征的车辆识别[J].智能系统学报,2009,4(03):278.
 ZHANG Tao,FEI Shu-min,LI Xiao-dong.Vehicle recognition using boundary invariants and a genetic algorithm trained radial basis function neural network[J].CAAI Transactions on Intelligent Systems,2009,4(06):278.
[7]秦世引,高书征.面向救援任务的地面移动机器人路径规划[J].智能系统学报,2009,4(05):414.[doi:10.3969/j.issn.1673-4785.2009.05.005]
 QIN Shi-yin,GAO Shu-zhen.Path planning for mobile rescue robots in disaster areas with complex environments[J].CAAI Transactions on Intelligent Systems,2009,4(06):414.[doi:10.3969/j.issn.1673-4785.2009.05.005]
[8]程显毅,巩向普.改进的模糊C-均值算法在医学图像分割中的应用[J].智能系统学报,2010,5(01):80.
 CHENG Xian-yi,GONG Xiang-pu.An improved fuzzy Cmeans algorithm for segmentation of medical images[J].CAAI Transactions on Intelligent Systems,2010,5(06):80.
[9]王斐,闻时光,吴成东,等.基于模糊逻辑的多移动机器人自适应协作围捕[J].智能系统学报,2011,6(01):44.
 WANG Fei,WEN Shiguang,WU Chengdong,et al.Adaptive cooperative hunting for multiple mobile robots based on fuzzy logic[J].CAAI Transactions on Intelligent Systems,2011,6(06):44.
[10]夏琳琳,张健沛,初妍.计算智能在移动机器人路径规划中的应用综述[J].智能系统学报,2011,6(02):160.
 XIA Linlin,ZHANG Jianpei,CHU Yan.An application survey on computational intelligence for path planning of mobile robots[J].CAAI Transactions on Intelligent Systems,2011,6(06):160.

备注/Memo

备注/Memo:
收稿日期:2009-04-15.
基金项目:国家自然科学基金资助项目(60736023,60674053,90716021).
作者简介
周树德,男,1980年生,博士,主要研究方向为智能优化理论和算法、复杂系统分析与设计.发表学术论文10余篇.
孙增圻,男,1943年生,教授,博士生导师,主要研究方向为智能控制、机器人、模糊系统和神经网络、计算机控制理论及应用等.发表学术论文300余篇.
更新日期/Last Update: 2010-02-17