- author = "Zahra Zojaji",
- title = "Improving The Performance of Genetic Programming Through Developing Fitness-based Schema Theory",
- school = "Computer Engineering Department, Amirkabir University of Technology",
- year = "2017",
- address = "Tehran, Iran",
- month = aug,
- keywords = "genetic algorithms, genetic programming, Schema theory, Building blocks, Locality, Mutual information, Semantic genetic programming",
-
URL = "
http://www.cs.ucl.ac.uk/staff/W.Langdon/ftp/papers/zojaji_thesis.pdf",
- size = "191 pages",
-
abstract = "Genetic programming (GP) is a subfield of evolutionary
computation, in which computer programs evolve to solve
a specified problem. Despite the empirical success in
various applications, GP is still not known as a
reliable problem-solving technique. One of the most
important issues of GP is its ineffective search
procedure. In contrast to natural evolution, which is
based on the gradualism, in GP neither the
representation nor the operators are local. This
feature, cause GP to have sudden movement in genotype
and semantic spaces. We employed schema theory as a
tool for investigating and addressing this
issue.
Schema theory is the most well-known model of evolutionary algorithms. Imitating from genetic algorithms (GA), nearly all schemata defined for GP refer to a set of points in the search space that share some syntactic characteristics. In GP, syntactically similar individuals do not necessarily behave similarly. Hence, there are several major issues with relying on prior schema theories as a behavioral model of GP. As a result, these theories have been rarely applied practically in the literature. In this study, we propose and use the first semantic schema theory for GP. The proposed theory is a more realistic model of GP that could be potentially employed for improving GP in practice. This schema partitions the search space according to semantics of trees, regardless of their syntactic variety. We interpret the semantics of a tree in terms of the mutual information between its output and the target. The semantic schema is characterized by the occurrence of semantic building blocks in promising individuals. These building blocks are introduced and extracted in the proposed semantic space. An extraction method that looks for the most significant schema of the population is provided. Moreover, an exact microscopic schema theorem is suggested that predicts the expected number of schema samples in the next generation.
The main purpose of this study is proposing schema based genetic programming (SBGP), which control and guide the GP search. SBGP is equipped with some semantic local operators that bias offspring toward a specfied schema and perform a local search around it. To achieve this aim, initially the significant schema of the population is extracted. Then, predefined local operators are applied to generate offspring. The schema is upgraded incrementally during the evolution. Therefore, local in-schema search is combined with schema evolution as a global search towards the target. In this reaerch, the algorithm is devoted to symbolic regression problems. However, it can be simply extended to other problem types.
For evaluating the proposed method, we use both synthetized and real world problems. Experiments are conducted in two sections of schema theory and SBGP. Results demonstrate the capability of the proposed schema definition in both generalization and diversity preserving aspects and the high accuracy of schema theory estimations. The results of second class of experiments indicate that SBGP has overally superior performance in terms of accuracy and generalization, in comparison to other GP versions.",
-
notes = "in Persian
Tehran Polytechnic.
Improving The Performance of Genetic Programming Through Developing Semantic Schema Theory
Supervisor: Mohammad Mehdi Ebadzadeh",
