Towards the Automatic Programming of NEPs - Foundations on Natural and Artificial Computation - page 303

Some of the authors of this paper have proposed new evolutionary automatic
programming algorithms (Attribute Grammar Evolution, AGE, [5] and Chris-
tiansen Grammar Evolution, CGE, [11]) as powerful tools to design complex
systems to solve specific tasks.
Both techniques, AGE and CGE, wholly describe the candidate solutions,
both syntactically and semantically, by means, respectively, of attribute and
Christiansen grammars; thus improving the performance of other approaches,
because they reduce the search space by excluding non-promising individuals
with syntactic or semantic errors.
NEPs are abstract devices with a complex structure, because some of their
components depend on others. This dependence makes it dicult to use genetic
techniques to search NEPs because, in this circumstance, genetic operators usu-
ally produce a great number of incorrect individuals (either syntactically or
semantically).
This paper shows the steps we have taken to implement a real platform to
automatically design (or program) NEPs by means of our genetic algorithms
(AGE/CGE). We have chosen a well known family of NEPs, able to solve a very
simple problem [4]: the application of context free rules by classic NEPs. It is
worth noticing that context free rules are not allowed in the classic family of
NEPs. In this family, it is just allowed to replace a symbol by a single symbol
(rather than a string of symbols, as in context free grammars). We are currently
interested in developing the complete platform and have designed a static (non
adaptable) simple context free grammar (without attributes) that could be used
as the kernel for further Christiansen or attribute versions. This grammar gen-
erates a family of NEPs that includes that of [4]. To reduce the size of the search
space, we have fixed all the components of the NEPs except the sets of rules and
filters. We also have used an empty fitness function, because our goal is just to
generate a valid initial population. In the future, we will include our simulator
(jNEP [6]) in the fitness function used to evolve the initial individuals.
Our final goal is to test our techniques for the automatic design of NEPs to
solve given tasks. We hope that our experiments may result in the proposal of a
methodology to automatically design NEPs.
Figure 1 graphically describes the different blocks which can be considered to
propose a general way to program natural computers similar to NEPs to solve
a given problem.
This method takes as inputs the following elements:
-

The target problem to be solved.

The computing device that will be used to solve the problem.
And it consists of the following modules:
-

-

An evolutionary engine , used as an automatic programming algorithm. This
engine has to handle candidate solutions with a complex structure. We pro-
pose using AGE or CGE.

- A formal description of the computing device being programmed.

- A simulator for the computing device that will be used to compute the fitness

function.