|
Karva Notation: The Native Language of GeneXproTools
Karva notation is used internally by GeneXproTools as it
allows the compact encoding and rapid expression of complex models.
And although very simple to understand, you don't actually have to know
it in order to model with GeneXproTools, as all the code generated
by GeneXproTools is automatically converted into the most commonly
used programming languages (a total of 16 in GeneXproTools 4.0). But
since it is so simple and so handy, we encourage you to learn about
this representation so that you can benefit from some of the most
advanced features of GeneXproTools.
Karva notation was developed
specifically for Gene Expression
Programming (GEP) and consists of a
universal way of compactly representing any
mathematical or logical expression that can
be represented as a tree.
Besides its compactness, this universal
representation is also linear, and this is a
fundamental characteristic for any system
that has to breed mathematical expressions
to create new, more precise ones.
The linear structures of GEP are called
chromosomes and each
chromosome contains one or more
genes. And each gene is associated
with its own K-expression
("K" or "Kappa" is for Karva notation).
Genes and K-expressions are very easy to
decode. For example, the gene:
0123456
+/*abcd
can be represented as a diagram or expression tree (ET):
The translation of the gene into the corresponding ET is straightforward: The first element in the gene (position 0) corresponds to the root of the ET; then, below that node, are attached as many nodes as there are arguments to that function (two, in this case); then these nodes are filled consecutively with the elements in the gene (in this case, positions 1 and 2), and so forth. The process is repeated until a line composed of only terminals is formed (in this case, the third line).
More formally, both the gene and ET above
can be represented by the mathematical
expression:
Usually the genes evolved by GEP are more
interesting than the gene presented above,
not only with noncoding regions
at their ends but also with more diverse
branching structures. For example, consider the gene:
01234567890123456
Q/a*+b-cbabaccbac
where "Q" represents the square root
function. This gene has a head
(from position 0 through 7 and shown in
blue) of length 8 and a tail
(from position 8 through 16) of length 9.
Note that the head contains both functions
(which may take 1, 2,..., n
arguments) and terminals (the variables and
constants in a problem), whereas the tail
contains exclusively terminals (this
structural organization is indeed the
cornerstone of GEP as it ensures that all
the programs encoded in the genes are
syntactically correct). The translation of such genes is done exactly as in the
previous example, giving: 
Note that, in this case, not all the elements in the gene were used to construct the ET, as the translation ends whenever a line containing only terminals is formed. In this
particular case, the gene ends at position 16 whereas the K-expression ends at position 9.
Furthermore, GEP chromosomes are usually multigenic, and each gene codes for a sub-ET or sub-program. After translation, the sub-ETs are linked by a particular
linking function: addition, subtraction, multiplication, or division
for all kinds of mathematical models in
GeneXproTools 4.0 and And, Or, Nand, Nor, Xor, Nxor, Less Than, Greater Than, Less Or Equal,
and Greater Or Equal for logical expressions.
For example, the following chromosome composed of three genes (position 0 indicates the beginning of each gene):
012345678012345678012345678
*aQ+abbaa/Q*/aababa*+Qaabba
encodes the following sub-ETs:
Then the sub-ETs are afterwards linked by one of the available linking
functions. For instance, if the linking function were addition, then the following program would be
obtained (the linking function is shown in gray):
Note that the ET above can be easily linearized into a single K-expression:
01234567890123456
++a*/aQQ*+/aaabba
These manipulations are important in order to fully explore all the
features of GeneXproTools, especially the Change Seed
method, which allows you to take an existing model, tinker (or not)
with it a bit, and then use it to breed even better models.
But unless you want to use extraneous models, you don't have to
be fluent in Karva as all the models evolved by GeneXproTools in its native
Karva code are automatically converted not only into a wide range of
programming languages
(Ada, C, C++, C#, Fortran, Java, Java Script, Matlab, Pascal, Perl, PHP, Python, Visual Basic, VB.Net, Verilog, and
VHDL) but also into diagram representations or expression trees
for an immediate visualization of the model
structure.
Last modified: September
1, 2007
Cite this as:
Ferreira, C. "Karva Notation: The Native Language of GeneXproTools." From GeneXproTools
Tutorials – A Gepsoft Web Resource.
http://www.gepsoft.com/tutorial003.htm
|
