Network Crossover Performance on NK Landscapes and Deceptive Problems

摘要

Practitioners often have some information about the problem being solved, which may be represented as a graph of dependencies or correlations between problem variables. Similar information can also be obtained automatically, for example by mining the probabilistic models obtained by EDAs or by using other methods for linkage learning. This information can be used to bias variation operators, be it in EDAs (where it can be used to speed up model building) or in GAs (where the linkages can be explored by modifying crossover). This can allow us to solve problems unsolvable with conventional, problem-independent variation operators, or speed up adaptive operators such as those of EDAs. This paper describes a method to build a network crossover operator that can be used in a GA to easily incorporate problem-specific knowledge. The performance of this operator in the simple genetic algorithm(GA) is then compared to other operators as well as the hierarchical Bayesian Optimization Algorithm (hBOA) on several different problem types, all with both elitism replacement and Restricted Tournament Replacement (RTR). The performance of all the algorithms are then analyzed and the results are discussed.