The schema deceptiveness and deceptive problems of genetic algorithms

作     者：李敏强 寇纪淞 

作者机构：1. Institute of Systems Engineering Tianjin University 300072 Tianjin China 

出 版 物：《Science in China(Series F)》 (中国科学（F辑英文版）)

年 卷 期：2001年第44卷第5期

页      面：342-350页

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 081104[工学-模式识别与智能系统] 08[工学] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：This work was supported by the National Natural Science Foundation of China (Grant No. 69974026) 

主　　题：genetic algorithms schema competition schema deceptiveness GA deceptive problems. 

摘      要：Genetic algorithms (GA) are a new type of global optimization methodology based on na-ture selection and heredity, and its power comes from the evolution process of the population of feasi-ble solutions by using simple genetic operators. The past two decades saw a lot of successful industrial cases of GA application, and also revealed the urgency of practical theoretic guidance. This paper sets focus on the evolution dynamics of GA based on schema theorem and building block hypothesis (Schema Theory), which we thought would form the basis of profound theory of GA. The deceptive-ness of GA in solving multi-modal optimization problems encoded on {0,1} was probed in detail. First, a series of new concepts are defined mathematically as the schemata containment, schemata compe-tence. Then, we defined the schema deceptiveness and GA deceptive problems based on primary schemata competence, including fully deceptive problem, consistently deceptive problem, chronically deceptive problem, and fundamentally deceptive problem. Meanwhile, some novel propositions are formed on the basis of primary schemata competence. Finally, we use the trap function, a kind of bit unitation function, and a NiH function (needle-in-a-haystack) newly designed by the authors, to dis-play the affections of schema deceptiveness on the searching behavior of GA.