[6152] | 1 | This package defines ECJ's Grammatical Evolution package. |
---|
| 2 | |
---|
| 3 | Grammatical Evolution uses an arbitrarily-long integer list representation. |
---|
| 4 | An individual is evaluated by taking the list and interpreting it according |
---|
| 5 | to a grammar to produce (in the case of ECJ) a GP tree-style Individual, which |
---|
| 6 | is then evaluated. The fitness of the GP individual becomes the fitness of |
---|
| 7 | the Grammatical Evolution list representation individual |
---|
| 8 | |
---|
| 9 | Grammatical Evolution's mapping from list to tree uses a grammar file |
---|
| 10 | specified in GESpecies. The grammar file defines the grammar for the tree. |
---|
| 11 | Here is a very simple example for Artificial Ant: |
---|
| 12 | |
---|
| 13 | <prog> ::= <op> |
---|
| 14 | <op> ::= (if-food-ahead <op> <op>) |
---|
| 15 | <op> ::= (progn2 <op> <op>) |
---|
| 16 | <op> ::= (progn3 <op> <op> <op>) |
---|
| 17 | <op> ::= (left) | (right) | (move) |
---|
| 18 | |
---|
| 19 | We say this is simple because practically the only expanded variable name is |
---|
| 20 | <op>. This doesn't have to be the case -- a GE grammar can have a rich collection |
---|
| 21 | of expanded variables. Grammatical Evolution's use of a grammar in fact allows |
---|
| 22 | it to define a fairly complex type system that's not easy to replicate with ECJ's |
---|
| 23 | (or GP in general) standard typing options. |
---|
| 24 | |
---|
| 25 | The mapping works as follows. We start with the first variable (in this case, |
---|
| 26 | <prog>. It expands solely to <op>. Now we have a choice -- what should <op> |
---|
| 27 | expand to? There are six choices from the grammar above. To make the decision, |
---|
| 28 | we consult the first number in the GE Individual, mod 6. That result is our |
---|
| 29 | expansion. We then proceed to expand each of the new elements: for example, |
---|
| 30 | if <op> had expanded to (if-food-ahead <op> <op>), we now have two new <op>s |
---|
| 31 | to expand. We proceed depth-first, each time consulting the next number in |
---|
| 32 | the GE Individual. When the GPTree is completed and there are no more |
---|
| 33 | expansions, it's handed to a GPProblem to be tested. |
---|
| 34 | |
---|
| 35 | If the Individual doesn't have enough integers to cover all the needs of |
---|
| 36 | the grammar, it is considered to be a "bad" Individual and is given a poor |
---|
| 37 | fitness. |
---|
| 38 | |
---|
| 39 | Thus a Grammatical Evolution problem requires several pieces: |
---|
| 40 | |
---|
| 41 | 1. A grammar file to interpret by. |
---|
| 42 | 2. A GEIndividual (basically a ByteVectorIndividual) to hold the numbers. |
---|
| 43 | 3. A GESpecies to load the grammar and be available to perform the mapping |
---|
| 44 | from GEIndividual to GPIndividual. |
---|
| 45 | 4. A GEProblem to take a GEIndividual, map it through the GEPSpecies, and |
---|
| 46 | hand it off to a GPProblem to be tested. |
---|
| 47 | 5. A GPProblem to do the testing. |
---|
| 48 | |
---|
| 49 | Grammatical Evolution can handle ERCs and ADFs as well. To handle the multiple |
---|
| 50 | trees required by an ADF, we provide multiple grammar files. See the Lawnmower |
---|
| 51 | example (ec/app/lawnmower) for a demonstration. |
---|
| 52 | |
---|
| 53 | Grammatical Evolution requires quite a lot of manipulation of the GP subsystem |
---|
| 54 | to pull all this off. Notably: |
---|
| 55 | |
---|
| 56 | 1. The problem will be a GEProbem. It in turn holds onto the "true" GPProblem |
---|
| 57 | in a 'problem' parameter |
---|
| 58 | 2. The species will be a GESpecies. It in turn holds onto the "true" GPSpecies |
---|
| 59 | in a 'gp-species' parameter. |
---|
| 60 | |
---|
| 61 | Generally Grammatical Evolution is surprisingly easy to implement in ECJ. The |
---|
| 62 | ec/gp/ge/ge.params file will do most of the heavy lifting for you if you're dealing |
---|
| 63 | with just a single tree (no ADFs say). But in some cases we'll need to add |
---|
| 64 | special GP elements to this subsidiary GPSpecies, mostly for additiona trees. |
---|
| 65 | For example, in the Lawnmower problem, to have three trees, we need to define |
---|
| 66 | them manually as shown in ec/app/lawnmower/ge.params |
---|
| 67 | |
---|
| 68 | Grammatical Evolution has two common breeding operators for its lists of |
---|
| 69 | integers: |
---|
| 70 | |
---|
| 71 | - TRUNCATION: Integers unused during the mapping process are later chopped off |
---|
| 72 | the end of the Individual. |
---|
| 73 | |
---|
| 74 | - GENE DUPLICATION: A string of integers in the list is copied and reinserted |
---|
| 75 | "downstream" in the list. This is implemented elsehwere by the class |
---|
| 76 | ec/vector/breed/GeneDuplicationPipeline |
---|
| 77 | |
---|
| 78 | To this any number of other list crossover and mutation operators could be used. |
---|
| 79 | NOTE that the pipeline defined in ge.params is pretty arbitrary -- you might want |
---|
| 80 | to build something better. |
---|
| 81 | |
---|
| 82 | |
---|
| 83 | |
---|
| 84 | EXAMPLES |
---|
| 85 | |
---|
| 86 | See the ec/app/ant, ec/app/regression, and ec/app/lawnmower directories for |
---|
| 87 | GE versions of these GP problems. |
---|
| 88 | |
---|
| 89 | |
---|
| 90 | |
---|
| 91 | CLASSES |
---|
| 92 | |
---|
| 93 | |
---|
| 94 | GEIndividual.java |
---|
| 95 | |
---|
| 96 | This class is just a simple subclass of ByteVectorIndividual which also prints out |
---|
| 97 | the tree form of the Individual. |
---|
| 98 | |
---|
| 99 | |
---|
| 100 | GESpecies.java |
---|
| 101 | |
---|
| 102 | A version of IntegerVectorSpecies which loads the grammar file or files, holds onto |
---|
| 103 | the GPSpecies, and performs the actual mapping prior to evaluation of GEIndividuals. |
---|
| 104 | |
---|
| 105 | |
---|
| 106 | GrammarParser.java |
---|
| 107 | |
---|
| 108 | The parser which reads the grammar rules from the provided grammar files and converts |
---|
| 109 | them into a parse graph. This parse graph is then what's actually used by GESpecies |
---|
| 110 | to map GEIndividuals into GPIndividuals. You can replace this parser with one of your |
---|
| 111 | own. |
---|
| 112 | |
---|
| 113 | |
---|
| 114 | GrammarNode.java |
---|
| 115 | GrammarFunctionNode.java |
---|
| 116 | GrammarRuleNode.java |
---|
| 117 | |
---|
| 118 | These form the actual objects in the parse graph. GrammarNode is an abstract superclass. |
---|
| 119 | GrammarFunctionNode defines functions with arguments (its children). GrammarRuleNode |
---|
| 120 | defines rules with rule options (its children). |
---|
| 121 | |
---|
| 122 | |
---|
| 123 | GEProblem.java |
---|
| 124 | |
---|
| 125 | A version of Problem which is inserted in lieu of the GPProblem, and which in turn |
---|
| 126 | holds onto the GPProblem. The GEProblem first maps the GEIndividual into a GPIndividual |
---|
| 127 | using the GESpecies. It then hands the GPIndividual to the GPProblem to be evaluated. |
---|
| 128 | |
---|
| 129 | |
---|
| 130 | [in the ec.gp.ge.breed subpackage] |
---|
| 131 | |
---|
| 132 | GETruncationPipeline.java |
---|
| 133 | |
---|
| 134 | A special list operator which only works with GEIndividuals. Truncates from the |
---|
| 135 | list all those integers which weren't used during the mapping process. |
---|
| 136 | |
---|
| 137 | |
---|
| 138 | [elsewhere in the ec.vector.breed package] |
---|
| 139 | |
---|
| 140 | GeneDuplicationPipeline.java |
---|
| 141 | |
---|
| 142 | A special list operator which duplicates genes downstream. Generally used by |
---|
| 143 | GEIndividuals but it's available in ec.vector.breed because it can be used by any |
---|
| 144 | VectorIndividual if you'd really want to. |
---|
| 145 | |
---|