Information Technology Reference
In-Depth Information
words without auxiliary symbols. At this point the rotation of “s” has finished.
This cicle could be repeated as many times as needed until finding the symbol
to which we want to apply the rule (“A”).
As we have explained before, we have decided to reduce the characteristics
and functuonality of general NEPs. In this first proof we have used
-
rules of all the kinds described in [8,1,9,2]
-
filters based on
random context conditions
, that is, the four usual types of
filters described in [8]
-
the same graph structure as in [4]
-
In addition, we have bounded the number of symbols of the alphabet (see
the grammar below)
This is the context free grammar we have used (notice that symbols “[” and “]”
are used to enclose non terminal symbols in the right hand side of the rules while
the XML markers for tags “
<
”and“
>
” have to appears literally):
NEP ::=
<
?xml version=”1.0”?
><
NEP nodes=“[nodes]”
>
[alphabetTag] [graphTag]
[processorsTag] [stoppingConditionsTag]
<
/NEP
>
nodes ::= 5
alphabetTag ::=
<
ALPHABET symbols=“a b c o p q r s t u v w x y z”/
>
graphTag ::=
<
GRAPH
><
EDGE vertex1=“0” vertex2=“1”/
><
EDGE vertex1=“1”vertex2=“2”/
>
<
EDGE vertex1=“2” vertex2=“3”/
><
EDGE vertex1=“3” vertex2=“4”/
><
/GRAPH
>
<
EVOLUTIONARY
PROCESSORS
>
[nodeTagInit] [nodeTag] [nodeTag] [node-
processorsTag ::=
Tag] [nodeTag]
<
/EVOLUTIONARY PROCESSORS
>
nodeTagInit ::=
<
NODE initCond=”input”
>
[evolutionaryRulesTag] [nodeFiltersTag]
<
/NODE
>
nodeTag ::=
<
NODE initCond=”
”
>
[evolutionaryRulesTag] [nodeFiltersTa
g
]
<
/NODE
>
evolutionaryRulesTag ::=
<
EVOLUTIONARY RULES
>
[ruleTag]
<
/EVOLUTIONARY RULES
>
ruleTag ::=
RULE ruleType=“[ruleType]” actionType=“[actionType]” symbol=“[symbol]”
newSymbol=“[symbol]”/
<
>
[ruleTag]
λ
ruleType ::= insertion
|
deletion
|
substitution
actionType ::= LEFT
|
RIGHT
|
ANY
nodeFiltersTag ::=
ruleTag ::=
<
FILTERS
>
[inputFilterTag] [outputFilterTag]
<
/FILTERS
>
nodeFiltersTag ::=
<
FILTERS
>
[inputFilterTag]
<
/FILTERS
>
nodeFiltersTag ::=
<
FILTERS
>
[outputFilterTag]
<
/FILTERS
>
nodeFiltersTag ::=
<
FILTERS
><
/FILTERS
>
inputFilterTag ::=
<
INPUT [filterSpec]/
>
outputFilterTag ::=
>
filterSpec ::= type = “[filterType]” permittingContext = “[symbolList]” forbiddingContext
= “[symbolList]”
filterType ::= 1
|
2
|
3
|
4
wordList ::= [symbolList] [wordList]
<
OUTPUT [filterSpec]/
|
λ
symbolList ::= [auxList]
|
λ
auxList ::= [symbol]
|
[symbol]
[auxList]
symbol ::= a
|
b
|
c
|
o
|
p
|
q
|
r
|
s
|
t
|
u
|
v
|
w
|
x
|
y
|
z
stoppingConditionsTag ::=
<
STOPPING CONDITION
CONDITION type = “NonEmptyNodeStop-
pingCondition” nodeID = “[lastNodeID]”/
><
><
CONDITION type = “Maximum-
StepsStoppingCondition” maximum = “20”/
><
/STOPPING CONDITION
>
4.1 Testing the Framework
We have introduced the previous grammar in our CGE engine and run a prelim-
inary evolutionary search. The framework creates a lot of different valid NEPs
as expected. One of these NEPs is shown below.
An example of the generated NEPs.
This NEP fullfils the functional and struc-
tural constraints imposed by the grammar. It has 4 nodes, connected sequentially.
Search WWH ::
Custom Search