Information Technology Reference
In-Depth Information
in the individual. The cardinality of the set of possible configurations of layers
equals
l
l
.Thethird
production rule codifies the input connections of every position in the ordered
list separated by the divider token. Notice that the node occupying the first
position in the list always receives zero input connections, as nodes can only be
forward connected. For this reason, the codified connections start at the second
position in the list, which can only receive one input connection from the first
position. The second codified set of connections, after the divider token, refers to
the second position in the list of nodes, which can receive input connections from
positions one and two. The last production rule establishes that the class node
may be connected with
c
!
,which,inthisexample,isequalto
n
!
insofar as
n
=
nodes. Notice that connections refer to positions
in the list of nodes, not actual nodes.
=3
a)
G
3212
=(
∑
N
, ∑
T
,
S, P)
∑
N
= { S, ORDER, CONNECTIONS, CLASS }
∑
T
= {0, 1, n
0
,n
1
,n
2
,:}
P
=
{
S::= ORDER CONNECTIONS : CLASS
ORDER::= n
0
n
2
n
1
|n
1
n
0
n
2
CONNECTIONS::= 1:10 | 1:01 | 1:00 | 0:10 | 0:01 | 0:00
CLASS::= 110 | 101 | 100 | 011 | 010 | 001
}
b)
n
0
n
2
n
1
0:01:101
Sentence:
Genotype:
Phenotype:
S
n
0
n
2
n
1
ORDER
CONNECTIONS
:
CLASS
class
n
0
n
2
n
1
0:01
101
Fig. 3. a) Sample grammar
G
3212
automatically generated by the CFG generator. b)
Sample individual that belongs to the language generated by
G
3212
.
Figure 2.b shows an individual that belongs to the language generated by
G
3323
. The derivation tree shown on the left is built by choosing the third conse-
quent produced by “ORDER”, that establishes the ordered list
n
1
,n
0
,n
2
.Then
the third consequent produced by “CONNECTIONS” is chosen, codifying one
input connection for the second node (
n
0
) coming from the first node (
n
1
), and
another one for the third node (
n
2
) coming from the second node. Finally, the
first consequent produced by “CLASS” fully connects the class node with
n
0
,n
1
and
n
2
. This derivation tree is the genotype that codifies the sentence shown
in the upper-right of the diagram. The sentence codifies the phenotype of the
individual, shown in the lower-right of the diagram.
Figure 3.a shows another sample grammar
G
3212
generated for the values
n
.Thisgrammarfollowsthesamestructure
as presented in Figure 2.a. In this example, nodes
=3
,l
=2
,p
=1
and
c
=2
(
n
=3)
are alternatively
distributed across two layers
(
l
=2)
:
layer
1=
{
n
0
,n
2
}
and
layer
2=
{
n
1
}
.
Insofar as only layers are reordered, the second rule produces only
{
n
0
,n
2
,n
1
}
and
{
n
1
,n
0
,n
2
}
, a total of
l
!
orders. The third and fourth production rules limit
Search WWH ::
Custom Search