[1]ZHOU Shu-de,SUN Zeng-qi.Linkage in genetic algorithms[J].CAAI Transactions on Intelligent Systems,2009,4(6):483-489.[doi:10.3969/j.issn.1673-4785.2009.06.003]
Copy

Linkage in genetic algorithms

CAAI Transactions on Intelligent Systems[ISSN 1673-4785/CN 23-1538/TP] Volume: 4 Number of periods: 2009 6 Page number: 483-489 Column: 学术论文—人工智能基础 Public date: 2009-12-25
Title:
Linkage in genetic algorithms
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
CLC:
TP18
DOI:
10.3969/j.issn.1673-4785.2009.06.003
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.
Similar References:

Memo

-

Last Update: 2010-02-17

Copyright © CAAI Transactions on Intelligent Systems