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 simpl...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.展开更多
基金This work was supported by the National Natural Science Foundation of China (Grant No. 69974026).
文摘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.
