Analysis of Schema Grammar

Abstract

Recently, several variants of the Schema Grammar (SG) algorithm have been proposed. This novel algorithm learns linkage between the values of variables of a problem. The linkage information learned is based on co-occurrence of allele tuples. Several variants of SG will be tested on laboratory benchmark problems and it will be shown that the framework is effectively and efficiently able to solve the problems tested. The computational complexity of the model-building algorithm will be improved from O(n3 · p3) to O(n2 · p · log(n · p) + n · p2) and a new version of SG will be proposed. This version will be able to outperform the original results on all problems tested in terms of run-time and fitness function evaluations. Additionally, this new version is able to solve problems with comparable results to Linkage Tree Genetic Algorithm (LTGA) on Trap, 2D Spin Glasses and NK-landscapes. This version achieves comparable run-time scaling behaviour to LTGA. In addition the relation to other algorithms (including LTGA, Apriori and Krimp) will be explored. The latter two algorithms originate from the field of Frequent Pattern Set Mining.